Распределение перевозок

Первоначальный план перевозок

Оптимизированный план перевозок

Потребители					Всего предложение
Поставщики	Vj
Ui
А
В	-3
С
Всего спрос

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

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

S = 130 ´ 3 + 40 ´ 2 + 20 ´ 6 + 230 ´ 3 + 160 ´ 3 + 20 ´ 2 = 1740 UAH.

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

1. Иногда в первоначальном плане или в процессе итераций количество занятых квадратов может оказаться меньше, чем m + n - 1. В этом случае имеем дело с так называемым случаем вырождения. Он грозит опасностью зацикливания, т.е. бесконечного повторения итераций. Для предупреждения зацикливания базисный план или его итерации дополняются до необходимой величины m + n - 1 квадратами, в которых помещают перевозки, равные сколь угодно малой величине. В дальнейшем с этими перевозками, которые называют «нулевыми», выполняются действия, как с обычными перевозками. Выбор квадратов для помещения в них нулевых перевозок определяется при построении плана по методу наименьшей стоимости.

Пример. В табл. 1.6 приведен пример транспортной задачи, в которой возникает необходимость использования «нулевых» перевозок.

Таблица 1.6

Потребители					Всего предложение
Поставщики	Vj
Ui
А		** 2				А
В				** 2		В
С					** 2	С
D			** 2			D
Всего спрос

В данном случае в первоначальном плане занятыми оказались квадраты А-1, В-3, С-4, D-2, т.е. лишь четыре квадрата и до количества m + n - 1 не хватает 3 занятых квадратов. Следовательно, необходимо дополнительно ввести 3 «нулевые» перевозки.

«Нулевые» перевозки расставляются в клетки с наименьшей стоимостью, таким образом, чтобы можно было рассчитать все потенциалы. Так как в первоначальном плане не осталось квадратов с двойным предпочтением не занятых перевозками, и нет квадратов, отмеченных один раз, то рассматривают неотмеченные квадраты, имеющие наименьшую стоимость. Таких квадратов оказалось четыре. Первую «нулевую» перевозку помещают в клетку В-1. Таким образом, связываются поставщики А и В с 1 и 3 потребителями. Затем помещают нулевую перевозку в клетку D-3. После введения этой перевозки у оказываются связанными поставщики А, В и D и 1, 2 и 3 потребители. Надо поставить еще одну нулевую перевозку. Для этого пригодны квадраты С-2, и D-4, в которых стоимость перевозки равна 3 UAH. Выбирается любой из них, например квадрат D-4, и расставляются потенциалы (табл. 1.7).

Таблица 1.7

Потребители					Всего предложение
Поставщики	Vj
Ui
А						А
В	-1					В
С	-1					С
D	-2					D
Всего спрос

Как видно, представленный план распределения является оптимальным.

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

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

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

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

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

Пример.Решение открытой транспортной задачи.

Составить оптимальный план перевозок от 3 поставщиков к 4 потребителям при следующих условиях:

Предложение поставщиков:а₁ = 220 ед., а₂ = 190 ед., а₃ = 250 ед. Всего предложение 660 ед. Спрос потребителей в₁ = 180 ед., в₂ = 90 ед., в₃ = 110 ед., в₄ = 190 ед. Всего спрос 570 ед.

Матрица транспортных расходов представлена в табл. 1.8.

Таблица 1.8

Транспортные расходы, UAH/ед

Поставщик	Потребитель

Решение. Поскольку сумма предложения больше общей потребности на 90 ед., вводится «фиктивный» потребитель с таким спросом. Транспортные расходы по перевозке продукта к «фиктивному» потребителю устанавливаются выше всех расходов, приведенных в матрице (табл. 1.8), а именно 10 UAH/ед.

В табл. 1.9 приведено решение данной задачи методом потенциалов.

Таблица 1.9

Дата добавления: 2014-11-29