Транспортная модель (транспортная задача) используют при рассмотрении различных практических ситуаций в логистическом управлении, связанных: с составлением наиболее экономичного плана перевозок продукции, управление запасами, назначением служащих на рабочее места, оборотом наличного капитала и многими другими. Кроме того, модель можно изменить, чтобы она учитывала перевозку нескольких видов продукции. В то же время транспортная модель и ее обобщение представляют собой частные случаи сетевых моделей.

Транспортная задача по существу представляет собой задачу линейного программирования, которую можно решать симплекс – методом. Однако специфическая структура условий задачи позволяет использовать более эффективные вычислительные алгоритмы.

Сущность транспортной задачи линейного программирова­ния состоит в наивыгоднейшем прикреплении поставщиков однородного продукта ко многим потребителям этого продук­та. На практике постоянно возникает необходимость решения таких задач, особенно когда количество пунктов отправления и получения грузов увеличивается.

Условие транспортной задачи обычно записывается в виде матрицы, в которой потребители однородного груза размеща­ются по столбцам, а поставщики - по строкам. В последнем столбце матрицы проставляют запас груза, имеющийся у каж­дого поставщика, а в последней строке - потребность в нем потребителей. На пересечении строк со столбцами (в клетках матрицы) записывают размер поставки, а также расстояние пробега по всем возможным маршрутам время доставки гру­за или затраты на перевозку единицы груза по этим маршру­там.

Постановка задачи и ее математическая модель. Некоторый однородный продукт, сосредоточенный у т поставщиков в количестве (), необходимо доставить п потребителям в количестве (). Известно стоимость перевозки единицы груза от го поставщика му потребителю. Необходимо составить план перевозок, имеющий минимальную стоимость. Основное предположение, используемое при построении модели, состоит в том, что величина транспортных расходов на каждом маршруте прямо пропорциональна объему перевозимой продукции. Модель транспортной задачи представлена на рис 7.1.

m

n

Рис. 7.1. Транспортная модель

На рис. 7. 1. изображена транспортная модель в виде сети с т поставщиками некоторого однородного груза и п потребителями этого груза. При этом поставщикам груза и потребителям соответствуют вершины сети. Дуга, соединяющая поставщик груза с потребителем, представляет условный маршрут, по которому перевозится продукция. Количество продукции, производимой поставщиком , обозначено через , а количество продукции, потребляемой потребителем через ; стоимость перевозки единицы продукции из в .

Запишем математическую модель задачи:

1) Объем поставок го поставщика должен равняться ко­личеству имеющегося у него груза:

2) Объем поставок му потребителю должен быть равен его спросу:

3) Запас груза у поставщиков должен равняться суммарно­му спросу потребителей:

4) Размер поставок должен выражаться неотрицательным числом:

5) общая сумма затрат на перевозку груза должна быть минимальной:

Поставленная в задаче цель может быть достигнута раз­личными методами, например, методом северо-западного угла или методом потенциалов.

Модель транспортной задачи линейного программирования так же может использоваться для планирования ряда операций, не связанных с перевозкой грузов. Так, с ее помощью решаются задачи по оптимизации размещения производства, топливно-энергетического баланса, планов загрузки оборудования распределения сельскохозяйственных культур по участкам раз­личного плодородия и т. п.

Поставленная транспортная задача линейного программирования называется сбалансированной транспортной моделью, так как объем запасов равняется объему заказов. В реальных ситуациях не всегда объем производства равен спросу, однако транспортную модель всегда можно сбалансировать.

В случае превышения запас продукции над потребностью, т. е. если , вводится фиктивный (n+1) – й потребитель с потребностью

а соответствующие стоимости перевозок считаются равными нулю. Аналогично, при , вводится фиктивный (m+1) – й поставщик с запасом груза а соответствующие стоимости перевозок считаются равными нулю. Этими действиями задача сводится к сбалансированной транспортной задаче, из оптимального плана которой, получается оптимальный план исходной задачи.

Модель транспортной задачи представляет собой задачу линейного прогпаммирования и, етественно, ее можно решать с использованием метода последовательного улучшения плана или методом использованием метода последовательного улучшения оценок (симплексным методом). Но в этом случае основная трудность связана с числом переменных задачи . Поэтому специальные алгоритмы, например, такие как метод потенциалов и венгерский метод, оказываются более эффективными.

Алгоритм метода потенциалов, (его называют еще модифицированным распределительным алгоритмом) начинает работу с некоторого опорного плана транспортной задачи (допустимого плана перевозок). Для построения опорного плана обычно используется один из двух методов: метод северо-западного угла или метод минимального элемента. На конкретной задаче рассмотрим метод северо-западного угла. Он позволяет найти некоторый допустимый план перевозок.

Задача. На трех складах () имеется соответственно 140, 180 и 160 единиц однородного груза. Этот груз требуется перевести к пяти потребителям () соответственно в количествах 60, 70, 120, 130, 100 единиц. Стоимость перевозки от складов к потребителям приведена в табл. 7.2. (в правом верхнем углу каждой клетки). Например, сто­имость перевозки единицы груза со склада потребителю равна 2 у. е.

Таблица 7.2

Исходные данные для решения транспортной задачи

Поставщики	Потребители	Запасы продукции
Потребности

Найти допустимый план перевозок.

Для решения задачи на первом этапе составляется система огра­ничений и целевая функция. Система ограничений в общем виде (для задачи) имеет вид:

причем для

Целевая функция затрат на перевозку, значение которой необхо­димо минимизировать при имеющихся ограничениях, выглядит сле­дующим образом:

2 + 3 +4. + 2 + 4 + 2 , (92)

Далее перераспределяются объемы поставок грузов методом «северо-западного угла», т.е. первой заполняется верхняя левая (севе­ро-западная) клетка исходной таблицы. Примем объем перевозки со склада к потребителю максимально возможным из условий задачи и равным 60 ед. Потребитель полностью удовлетворил свою потребность, и поэтому графу « » в табл.7.3 можно исключить из даль­нейшего рассмотрения.

В таблице 7.3. найдем «северо-западный угол» (теперь это клетка )и укажем максимально возможное значение. Оно рассчитывает­ся следующим образом: со склада уже перевезено 60 ед. груза, поэто­му остаток на этом складе составляет 80 ед. (140-60). Вносим в клетку вместо значение, равное 70 ед. Потребитель полностью удовлетворил свою потребность, и поэтому графу « » в табл. 7.3. можно исключить из даль­нейшего рассмотрения. Остаток продукции на складе 10 ед. (140 – 60 – 70) припишем потребителю .Таким образом, весь груз со скла­да перевезен потребителям и первая строка табл. 7.3 исключается из дальнейшего рассмотрения.

В нашей табл.7.3 найдем новый «северо-западный угол» (клетка )и укажем в нем максимально воз­можное значение это 110 ед. (120 – 10). Остаток продукции на складе 70 ед. (180 – 110) припишем потребителю . Тем самим потребитель полностью удовлетворил свою потребность, и поэтому графу « » в табл. 7.3 можно исключить из даль­нейшего рассмотрения.

В оставшейся части табл. № найдем новый «северо-западный угол» (клетка ) и укажем в нем максимально воз­можное значение это 60 ед. (130 – 70). Остаток продукции на складе в количестве 100 ед. припишем потребителю .

Лабораторная работа №4

Транспортные модели

Цель работы: научиться находить оптимальное решение задач транспортного типа.

Задание

Вариант 1. На четырех ткацких станках с объемом рабочего времени 200, 300, 250 и 400 станко-ч за 1 час можно изготовить соответственно 260, 200, 340 и 500 м ткани трех артикулов I, II, III. Составить оптимальную программу загрузки станков, если прибыль (в ден. ед.) от реализации 1 м ткани i-го артикула при ее изготовлении на j-м станке характеризуется элементами матрицы

,

а суммарная потребность в ткани каждого из артикулов равна 200, 100 и 150 тыс. м, учитывая, что ткань Iартикула не может производиться на третьем станке.

Табличная модель:

Контрольные вопросы:

1. Как записывается математическая модель задачи транспортного типа?

Обозначим через x ij объем перевозок от i-го поставщика j-ому потребителю. Математическая модель задачи имеет вид:

1) объем поставок i-го поставщика должен равняться количеству имеющегося у него груза

;

2) объем поставок j-ому потребителю должен быть равен его спросу

;

3) объемы поставок должны выражаться неотрицательными числами

, ;

4) общая сумма затрат на перевозку груза должна быть минимальной

.

Если суммарный объем отправляемых грузов равен суммарному объему потребностей в этих грузах по пунктам назначения

,

то такая транспортная задача называется закрытой (сбалансированной), в противном случае - открытой (несбалансированной).

Если указанные затраты неизвестны (не указаны) соответствующие значения с ij полагают равными нулю.

модель поставка потребность затрата

2. Как свести открытую транспортную задачу к закрытой?

Если имеет место открытая транспортная задача, ее необходимо свести к закрытой:

1) в случае перепроизводства – ввести фиктивного потребителя с необходимым объемом потребления (элементы матрицы с ij , связывающие фиктивные пункты с реальными, имеют значения, равные затратам на хранение невывезенных грузов);

2) в случае дефицита – ввести фиктивного поставщика с недостающим объемом отправляемых грузов (элементы матрицы с ij , связывающие фиктивные пункты с реальными, имеют значения, равные штрафам за недопоставку продукции).

3. Каковы основные ситуации, описывающие дополнительные ограничения транспортной задачи?

При решении практических задач зачастую приходится учитывать ряд дополнительных ограничений.

1. Отдельные поставки от определенных поставщиков некоторым потребителям должны быть исключены (из-за отсутствия необходимых условий хранения, чрезмерной перегрузки коммуникаций и т.д.). Это достигается искусственным значительным завышением затрат на перевозки с ij в клетках, перевозки через которые следует запретить.

2. На предприятии необходимо определить минимальные суммарные затраты на производство и транспортировку продукции. С подобной задачей сталкиваются при решении вопросов, связанных с оптимальным размещением производственных объектов. Здесь может оказаться экономически более выгодным доставлять сырье из более отдаленных пунктов, но зато при меньшей его себестоимости. В таких задачах за критерий оптимальности принимают сумму затрат на производство и транспортировку продукции.

3. Ряд транспортных маршрутов, по которым необходимо доставить грузы, имеют ограничения по пропускной способности. Если, например, по маршруту A i B j можно провести не более qединиц груза, то B j -й столбец матрицы разбивается на два столбца –

и . В первом столбце спрос принимается равным , во втором – . Несмотря на то, что фактические затраты с ij в обоих столбцах одинаковы и равны исходным, в столбце вместо истинного тарифа с ij ставится искусственно завышенный тариф М (клетка блокируется). Затем задача решается обычным способом.

4. Поставки по определенным маршрутам обязательны и должны войти в оптимальный план независимо от того, выгодно это или нет. В этом случае уменьшают запас груза у поставщиков и спрос потребителей и решают задачу относительно тех поставок, которые необязательны. Полученное решение корректируют с учетом обязательных поставок.

5. Необходимо максимизировать целевую функцию задачи транспортного типа (например, задача об оптимальном распределении оборудования). В этом случае необходимо изменить знак в тарифах на противоположный. В ответе отрицательный знак игнорируется.

Вывод: я научилась находить оптимальное решение задач транспортного типа.

Транспортная модель - это математически приближенное отображение транспортной ситуации на дороге с помощью программных средств. Транспортная модель является математической моделью, то есть обладает достаточно высокой точностью, чтобы реализовывать различные задачи, связанные с прогнозами, оптимизацией и имитацией транспортных потоков. Такая модель может использоваться как инструмент поддержки принятия решений и как хранилище статистической информации о моделируемой транспортной системе.

Транспортные модели бывают имитационные, оптимизационные, прогнозные.

Единицей имитационной модели является транспортное средство, то есть моделирование происходит на уровне единиц транспортных средств, которые могут проехать из одной части города в другую. Микромодели, отображающие микрообъекты сети, относятся к имитационным моделям. Они имитируют ситуацию на отдельном участке сети.

Оптимизационные транспортные модели решают задачу оптимизации, то есть находят оптимум (лучшее решение) транспортной функции с помощью методов математического программирования.

Прогнозные транспортные модели , в отличие от имитационных, отображают транспортную ситуацию на уровне потоков.

Они строятся из транспортного предложения и транспортного спроса моделируемого объекта (города, района, области). Транспортным предложением считается вся транспортная сеть, а также остановки, маршруты и расписание общественного транспорта, а транспортным спросом – потребность людей в перемещениях по транспортной сети.

Транспортная модель города является прогнозной моделью.

При создании транспортной модели города на начальном этапе создается транспортное предложение - строится транспортный граф, который включает в себя транспортные узлы (развязки, кольца, перекрестки) и отрезки между узлами (дороги). После того, как вся транспортная сеть города, включающая правила дорожного движения и полосность дорог, внесена в программный продукт, добавляется информация об общественном транспорте.

Следующим этапом создания транспортного предложения является районирование - разделение транспортной сети на районы. Сеть делится на районы для того, чтобы систематизировать информацию о перемещениях транспортных потоков. В результате проделанных этапов в программном продукте появляется транспортное предложение – каркас, согласно которому перемещаются транспортные средства.

Для построения транспортного спроса собирается различная статистическая информация о транспортных районах, которые являются местами генерации и местами притяжения транспортных потоков. Пример собираемой информации для каждого транспортного района:

• емкость района (население);
• доля работающих;
• доля учащихся;
• количество зарегистрированных автомобильных средств;
• количество рабочих мест;
• количество рабочих мест в сфере услуг;
• количество мест в учебных заведениях;
• и др.

Далее составляются слои спроса - возможные перемещения, например Дом-Работа, Работа-Дом, Дом-Школа, Школа-Дом, Дом-Прочее, Прочее – Дом. Чем больше слоев спроса, тем выше точность модели. Для каждого слоя спроса и для каждого вида транспорта(общественный, индивидуальный) составляется матрица корреспонденции – матрица, содержащая количественные данные о перемещениях людей из района в район. Далее эти матрицы соединяются по каждому виду транспорта. Это и будет являться результатом моделирования транспортного спроса.

Следующий этап построения транспортной модели - совмещение транспортного предложения и транспортного спроса. Ищется точка равновесия, при которой существующее транспортное предложение будет удовлетворять транспортный спрос. При этом учитывается важный принцип: каждое транспортное средство стремится уменьшить время и стоимость своего перемещения.

После того, как транспортные потоки , реализованные в программном средстве, достигнут равновесного положения, становится возможным рассчитать среднюю скорость потоков, количество транспортных средств на каждом участке сети и отметить появление заторов.

Последний этап создания транспортной модели города - ее калибровка . В ходе калибровки, сравниваются значения реальных транспортных потоков города и значения, полученные с помощью моделирования. При существенных различиях значений производится поиск ошибок и их устранение. Эффективность калибровки проверяется с помощью оценок качества модели. Если оценки неудовлетворительные, происходит возврат на этапы моделирования предложения и спроса. Операции построения модели и ее калибровки повторяются до тех пор, пока модель не станет адекватной.

Полученная транспортная модель может использоваться учреждениями города для стратегического планирования, анализа инфраструктурных изменений, оценки качества транспортной системы, хранения и систематизации данных и др.

Создание комплексной транспортной схемы (КТС), программы комплексного развития транспортной инфраструктуры (ПКРТИ), комлексной схемы организации дорожного движения (КСОДД), а также комплексной схемы организации транспортного обслуживания населения общественным транспортом невозможно без наличия транспортной модели.

Транспортная модель используется для составления наиболее экономичного плана перевозок одного вида продукции из нескольких пунктов изготовления (например, заводов) в пункты доставки (например, склады).

Транспортная модель может применяться при рассмотрении практических ситуаций, связанных с управлением запасами, составлением именных графиков, назначением служащих не рабочие места, оборотом наличного капитала.

Транспортная задача может быть сведена к задаче линейного программирования и решена симплекс-методом. Вместе с тем специфика транспортной задачи позволяет решить ее более эффективным методом. Однако, и этот метод по существу воспроизводит шаги симплекс-метода.

Определение транспортной модели

При построении транспортной модели используются:

Заметим, что потребности одного пункта назначения могут удовлетворяться из нескольких исходных пунктов, так же один пункт производства может поставлять товар в несколько пунктов потребления.

Цель построения модели заключается в определении количества продукции, которую следует перевозить из всех исходных пунктов в пункты потребления при минимальных общих транспортных расходах.

Основное предположения транспортной модели состоит в том, что величина расходов на каждом маршруте прямо пропорциональна объему перевозимой продукции.

Рассмотрим графическое представление транспортной модели

Рисунок 6

Транспортная модель такого вида называется сетевой и имеет mисходных пунктов иnпунктов назначения. Исходные пункты и пункты назначения называются вершинами сети или соответствующего графа. Маршрут по которому перевозится продукция называется дугой, количество продукции, производимая вi-ом исходно пункте обозначается. Количество потребляемой продукции вj-ом пункте -. Стоимость перевозки.

Соответствующую математическую модель можно записать в следующем виде:

Iотражает тот факт, что суммарный объем перевозок из некоторого исходного пункта не может превышать произведенного в этом пункте количества продукции.

IIпоказывает, что суммарные перевозки продукции в некоторый пункт потребления должны полностью удовлетворять потребность в спросе на эту продукцию.

Анализ транспортной модели показывает, что суммарный объем производства не должен быть меньше объема потребления.

В том случае, если что суммарный объем производства равен суммарному объему потребления, транспортная модель называется сбалансированной.

Такая модель является канонической моделью линейного программирования.

Пример транспортной модели

Заводы автомобильной фирмы расположены в Лос-Анджелесе, Детройте и Нью-Орлеане. Центры распределения в Денвере и Майами. Объем производства заводов 1000, 1500 и 1200 автомобилей соответственно. Ожидаемый спрос равен 2300 и 1400 автомобилей соответственно.

Стоимость перевозки одного автомобиля приведена в таблице 10:

Таблица 10

- количество автомобилей, которые перевозят изi-ого пункта вj-ый (i=1,2,3;j=1,2).

Суммарный объем производства автомобилей равен 3700 и равняется суммарному ожидаемому спросу. Следовательно, данная транспортная модель является сбалансированной и ее можно записать в следующем виде:

при ограничениях

Компактный способ записи транспортной модели связан с использованием транспортной таблицы или матрицы, у которой соответствуют исходным пунктам, а столбцы пунктам спроса.

Среди задач линейной оптимизации могут быть выделены два класса задач со специальной структурой:

транспортная задача

задача о назначениях.

Эти задачи используются для моделирования оптимизации экономических проблем, связанных с формированием оптимального плана перевозок, оптимального распределения индивидуальных контрактов на транспортировки, составления оптимального штатного расписания, определения оптимальной специализации предприятий, рабочих участков и станков, оптимального назначения кандидатов на работы, оптимального использования торговых агентов. Критерием эффективности в данных задачах является линейная функция, ограничения также линейны, поэтому для их решения могут применяться методы линейной оптимизации, например симплекс-метод. Однако специальная структура таких задач позволяет разработать более удобные методы их решения. Некоторые из таких методов приведены этой книге. Даны общая формулировка задач, основные термины и определения, этапы построения математических моделей, этапы получения оптимальных решений. Также приведены числовые примеры экономических задач, которые могут быть решены этими методами.

Построим транспортную модель для конкретной задачи.

Четыре предприятия данного экономического района для производства продукции используют некоторое сырье. Спрос на сырье каждого из предприятий соответственно составляет: 120, 50, 190 и 110 усл. ед. Сырье сосредоточено в трех местах.

Предложения поставщиков сырья равны: 160, 140 и 170 усл. ед. На каждое предприятие сырье может завозиться от любого поставщика. Тарифы перевозок известны и задаются матрицей

В i -й строке j -м столбце матрицы С стоит тариф на перевозку сырья от i -гo поставщика j -му потребителю, i=1, 2, 3; j =1, 2, 3, 4. Под тарифом понимается стоимость перевозки единицы сырья.

Требуется составить план перевозок, при котором общая стоимость перевозок минимальна.

Построение математической модели

Цель задачи состоит в минимизации суммарной стоимости на перевозки. Эта цель может быть достигнута с помощью оптимальной организации перевозок сырья. Следовательно, за неизвестные можно принять количество сырья, перевозимого от каждого поставщика каждому потребителю.

Пусть хij - количество сырья, перевозимого от i -го поставщика j-му потребителю. Параметры задачи - число поставщиков и потребителей, предложение и спрос сырья в каждом пункте, тарифы на перевозки.

Ограничения задачи - это ограничения на предложение и спрос сырья. Предложения сырья всех поставщиков не должны быть меньше суммарного спроса на него во всех пунктах потребления. В данной задаче имеет место точное равенство между предложением и спросом. 120+50+190+110=160+140+170=470.

Количество сырья, вывозимого от каждого поставщика, должно быть равно наличному количеству сырья. Количество сырья, доставленное каждому потребителю, должно равняться его спросу. Последнее ограничение - условие неотрицательности хij.

Критерием эффективности (целевой функцией) являются суммарные затраты S на перевозку, равные сумме произведений тарифов на перевозку на количество перевозимого сырья от каждого поставщика каждому потребителю.

Окончательно математическая модель задачи имеет вид

Целевая функция и ограничения линейны, т.е. данная задача относится к задачам линейного программирования, однако, благодаря особой структуре, эта задача получила специальное название: транспортная задача или транспортная модель.

Определение начального плана транспортировок. Метод "северо-западного" угла

Рассмотрим метод "северо-западного" угла.

Метод "северо-западного" угла

Шаг 1. Составляют транспортную таблицу.

Шаг 2. Транспортную таблицу начинают заполнять с левого верхнего (северо-западного) угла. При заполнении двигаются по строке вправо и по столбцу вниз. В клетку, находящуюся на пересечении первой строки и первого столбца, помещается максимально возможное число единиц продукции, разрешенное ограничениями на предложение и спрос:

Если а1 < b2, то х11 = a1 и предложение первого поставщика полностью исчерпано. Первая строка вычеркивается, и двигаются по столбцу вниз. В клетку, находящуюся на пересечении первого столбца и второй строки, помещается максимально возможное число единиц продукции, разрешенное ограничениями на предложение и спрос: х21 == min(a2,b1-a1). Если b1-a1

Определить начальное решение по методу "северо-западного" угла для транспортной задачи из примера 1.

Транспортная таблица имеет следующий вид (табл. 3.1):

Таблица 3.1

В первую клетку помещают: х11 = min(160,120) = 120. Спрос первого потребителя полностью удовлетворен, первый столбец вычеркивают. Остаток сырья в первом пункте составляет: 160 - 120=40 усл. ед. Двигаемся по первой строке вправо х21 =min(160 -120,50) = 40. Предложение поставщика исчерпано, первая строка вычеркивается. Второму потребителю не хватает 50-40=10 усл. ед. Двигаемся по второму столбцу вниз х22 =min(140,50 - 40) = 10; Второй столбец вычеркивается. Двигаемся по второй строке вправо х23 = min(140 -10,90) = 130. Вторая строка вычеркивается. Двигаемся по третьему столбцу вниз x33 = min(170,190 -130) = 60. Спрос третьего потребителя удовлетворен. Двигаемся по третьей строке вправо х34 = min(170 -160, 10) = 110. Таблица заполнена. Число ненулевых значений xij,

транспортная математическая модель метод угол

равно 6. Число базисных переменных задачи 3+4 -1=6. Остальные 3*4-6=6 переменных являются свободными, их значения равны нулю.

Начальный план перевозок имеет вид

Стоимость перевозок по этому плану составляет

S1= 120*7+40*8+10*5+130*9+60*3+110*6=3220.

Метод "северо-западного" угла -- наиболее простой метод нахождения начального решения. План перевозок, полученный по этому методу, обычно бывает достаточно далек от оптимального.