9111

Таблица 11

Необходимое и достаточное условие разрешимости транспортной задачи

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

При выполнении условия (38) модель транспортной задачи называется закрытой. Если

открытой.

В случае открытой транспортной задачи выполнение условия (38) достигается введением фиктивного поставщика или фиктивного потребителя с соответствующими тарифами равными нулю.

Любое решение транспортной задачи представляет собой распределение перевозок xij в транспортной таблице. Оптимальному решению транспортной задачи соответствует оптимальное распределение перевозок. Перераспределение перевозок в транспортной таблице осуществляется до тех пор, пока не будет найдено оптимальное распределение перевозок.

Определение исходного допустимого решения

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

1. Метод «северо-западного угла»

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

2. Метод «наименьшей стоимости»

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

Пример. Разрешить перевозки методом «наименьшей стоимости».

В данной задаче клетка (2,1) имеет наименьшую стоимость перевозок с21 = 1. Распределение перевозок начнем с нее, то есть в эту клетку поместим перевозку х21 = 25. Затем выбираем следующую клетку с наименьшей стоимостью. Таких клеток две – (2,3) и (3,3). В них стоимости перевозок одинаковые с23 = 2 и с33 = 2. Выбираем любую из них. Например, (2,3) и поместим в нее перевозку х23 = 5, поскольку на складе А2 осталось только 5 единиц груза. (Клетку (1,1) со стоимостью с11 = 2 не берем, так как потребности потребителя B1 полностью удовлетворены). Следующая клетка (3,3). В нее помещаем перевозку x33 = 20, так как потребителю B3 не хватает 20 единиц груза и на складе A3 имеется 20 единиц груза. Берем клетку (1,2) со стоимостью c12 = 3 и помещаем в нее перевозку x12 = 40. Проверяем балансовые условия. Потребители B1 и B2 полностью удовлетворили свои потребности, а потребителю B3 не хватает 10 единиц груза. Груз остался только на складе A1 в нужном количестве, поэтому в клетку (1,3) помещаем x13 = 10.

После заполнения транспортной таблицы следует обязательно проверить количество свободных (базисных) и пустых (свободных) клеток.

Замечание. Число заполненных клеток равно m + n – 1, а пустых клеток – m × n – (m + n – 1), где m – количество пунктов отправления, n – количество пунктов назначения.

Если число заполненных клеток равно m + n – 1, то план является невырожденным. Если число заполненных клеток меньше этого значения, то план (решение) называется вырожденным. В случае вырожденности плана условно считают одну (или несколько) из пустых клеток занятой, записывая в нее нулевую перевозку так, чтобы число занятых клеток стало равным m + n – 1.

Перераспределение перевозок. Цикл пересчета

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

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

900.

Свойства цикла пересчета.

1) каждый цикл имеет четное число вершин;

решение в табл. 15 является оптимальным.

X min(30,10,20,0,30,0),

L min 2 30 3 10 1 20 2 30 150.

Решение транспортной задачи с помощью встроенного в Excel модуля «Поиск решения»

Четыре предприятия для производства продукции используют некоторое сырье. Спрос на сырье для каждого из предприятий составляет соответственно 120, 50, 190 и 110 у.е. Сырье сосредоточено в трех местах. Предложения поставщиков сырья равны 160, 140 и 200 у.е. На каждое предприятие сырье может завозиться от любого поставщика. Тарифы

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

Решение: Так как суммарные запасы превышают суммарные потребности (160 + 140 + 200 = 500 > 470 = 120 + 50 + 190 + 110), то вводим фиктивного потребителя b5,

потребность которого составляет 500 – 470 = 30. Составим экономико-математическую модель задачи:

xij − количество единиц груза, запланированных к перевозке от поставщика i к

потребителю j, i = 1, 2, 3; j = 1, 2, 3, 4, 5.

S = 7x11 + 8x12 + x13 + 2x14 + 4x21 + 5x22 + 9x23 + 8x24 + 9x31 + 2x32 + 3x33 + 6x34 + 0x15 + 0x25 + 0x35 min

x11 x12 x13 x14 x15 160x21 x22 x23 x24 x25 140

x31 x32 x33 x34 x35 200x11 x21 x31 120

x12 x22 x32 50x13 x23 x33 190

x14 x24 x34 110x15 x25 x35 30

xij 0, i 1,2,3; j 1,2,3,4,5

Рассмотрим технологию решения транспортной задачи, используя условия примера.

1)выберем адреса ячеек, в которые будет помещен результат решения (изменяемые ячейки) и оптимальное значение целевой функции;

Внашей задаче оптимальные значения хij будут помещены в ячейках В21:F23 (для удобства ссылок запишем в каждую из них 1), оптимальное значение целевой функции ‒ в ячейке G18 (см. рис. 11).

а) назначим ячейку для целевой функции (G18), укажем адреса изменяемых ячеек (В21:F23), установим флажок на минимум.

б) введем ограничения;

в) в строке Выберите метод решения выберем вариант «Поиск решения лин. задач симплекс-методом».

Теперь введены все необходимые условия для решения задачи:

Рис. 12.

Осталось поместить указатель мыши на кнопку Найти решение:

Рис. 13.

Ответ: от первого поставщика третьему предприятию следует перевезти 50 у.е. груза, четвертому предприятию – 110 у.е. груза;

от второго поставщика первому предприятию следует перевезти 120 у.е. груза;

от третьего поставщика второму предприятию следует перевезти 50 у.е. груза, третьему предприятию – 140 у.е. груза;

груз, предназначенный для пятого (фиктивного) потребителя остается у второго поставщика (20 у.е.) и третьего поставщика (10 у.е.).

Общая стоимость перевозок составит 1270 у.е. Рассмотрим примеры задач, близких к транспортной.

1.4. Сетевые модели

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

Модель перевозок с промежуточными пунктами.

Враспоряжении отдела сбыта компании имеется 10 генераторов, которые находятся

впункте 1. Эти генераторы необходимо доставить в пункты строительства, обозначенные как пункты 3 и 4. В пункте 3 требуется 3 генератора, в пункте 4 − семь. Из-за ограничений, касающихся наличия водителей, генераторы можно доставлять только по маршрутам, показанным на рис. 14. Какой из маршрутов будет выбран, определяется затратами, связанными с каждым маршрутом и его пропускной способностью.

Рис. 14.

Таблицы удельных затрат и пропускных способностей приводятся: cij – удельные затраты (стоимость перевозки одного генератора); uij – пропускная способность.

Пропускная

способность

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

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

Запустив Поиск решения на выполнение получим оптимальное решение задачи: Рис. 17.

Ответ: по дуге (1, 2) перевозим 10 генераторов; по дуге (2, 3) – 4 генератора; по дугам (2, 4) и (2, 5) – по 3 генератора; по дуге (3, 4) – 1 генератор; по дуге (5, 4) − 3 генератора. Затраты составят 1615 у.е.

Поиск кратчайшего пути

Задача нахождения кратчайшего пути возникает в сети, в которой с каждой дугой (i, j) связано число cij, интерпретируемое как расстояние (или стоимость, или время движения) от узла i к узлу j. Маршрут, или путь между двумя узлами – произвольная последовательность дуг, соединяющая данные узлы. Задача состоит в нахождении кратчайшего (требующего минимальных затрат, или минимального времени) пути из определенного узла в другой узел сети. Рассмотрим конкретный пример.

Фирма занимается регулярными поставками вина в семь различных пунктов. На рисунке 18 показаны эти пункты и соединяющие их маршруты. Каждой дуге на рисунке соответствует число, обозначающее расстояние между соединяемыми данной дугой узлами. Фирма считает, что суммарные затраты будут минимальными, если все поставки в любой заданный пункт будут осуществляться по кратчайшему маршруту. Найти кратчайший маршрут из исходного пункта Н в пункт 5.