Транспортная задача 5 (стр. 2 из 3)

b) суммарные потребности превышают суммарные запасы

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

Найти минимальное значение линейной функции

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

,i = 1, 2, ..., m, (случай а)

, j = 1, 2, ..., n;

, i = 1, 2, ..., m, (случай б)

, j = 1, 2, ..., n,

x_ij³0 (i = 1, 2, ..., m; j = 1, 2, ..., n).

Открытая модель решается приведением к закрытой модели.

В случае (а), когда суммарные запасы превышают суммарные потребности, вводится фиктивный потребитель B_n₊₁, потребности которого b_n₊₁ =

. В случае (б), когда суммарные потребности превышают суммарные запасы, вводится фиктивный поставщик A_m₊₁, запасы которого a_m₊₁ =
.

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

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

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

3. Определение оптимального и опорного плана транспортной задачи

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

Число переменных X_ijв транспортной задаче с mпунктами отправления и nпунктами назначения равно nm, а число уравнений в системах (2) и (3) равноn+m. Так как мы предполагаем, что выполняется условие (5), то число линейно независимых уравнений равно n+m-1 отличных от нуля неизвестных.

Если в опорном плане число отличных от нуля компонентов равно в точности n+m-1, то план является не выраженным, а если меньше - то выраженным.

Для определения опорного плана существует несколько методов. Три из них - метод северно-западного угла, метод минимального элемента и метод аппроксимации Фогеля - рассмотрены ниже.

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

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

Для определения оптимального плана транспортной задачи можно использовать изложенные выше методы. Однако ввиду исключительной практической важности этой задачи и специфики ее ограничений [каждое неизвестное входит лишь в два уравнения системы (2) и (3) и коэффициенты при неизвестных равны единице] для определения оптимального плана транспортной задачи разработаны специальные методы. Два из них - метод потенциалов и Венгерский метод - рассматриваются ниже.

4. Методы определения первоначального опорного плана

4.1. Метод минимального элемента

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

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

Пример

Составить первоначальный опорный план методом минимального элемента для транспортной задачи вида:

2	3	4	15
11	6	10	1
8	9	3	3
4	1	2	21
10	20	10

Решение:

Задача сбалансирована.

Строим первоначальный опорный план методом минимального элемента.

Вторая и третья перевозки будут осуществляться с пункта производства
и
в пункт потребления
и
соответственно и составят максимально возможное число единиц продукта :
,
;
Четвертая перевозка осуществляется с пункта
в пункт потребления
, т.к.
(без учета первого, второго столбца и четвертой строки).
.
Пятая перевозка осуществляется с пункта
в пункт потребления
, т.к.
(без учета первого, второго столбца, третьей и четвертой строки).
.

6. Шестая перевозка осуществляется с пункта

в пункт потребления

т.к.

(без учета первого, второго столбца, первой, третьей и четвертой строки).

Опорный план имеет вид;

10	5	0
0	1	0
0	3	0
0	11	10

4.2. Метод аппроксимации Фогеля

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

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

Пример

Найти методом аппроксимации Фогеля первоначальный опорный план транспортной задачи:

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