Отыскание исходного опорного плана перевозок

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

а) метод северо-западного угла;

б) метод минимального элемента в строке;

в) метод минимального элемента.

Пусть имеется транспортная задача (5.1 - 5.4). Хотя в системе (5.2 - 5.3) m+n уравнений, опорный план содержит только m+n–1 базисных переменных. Это объясняется тем, что одно из уравнений является следствием остальных, и в жордановой форме m+n–1 уравнений.

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

Возьмем клетку (А_i,В_j) с наименьшей стоимостью перевозок. Проставим в нее перевозку, равную min(a_i,b_j). Затем "уменьшаем" транспортную таблицу, руководствуясь правилами:

1) если a_i < b_j, то исключаем из дальнейшего рассмотрения пункт отправления (ПО) А_i (и соответствующую строку); а в "меньшей" таблице потребность пункта назначения (ПН) В_j полагаем равной b_j - a_i;

2) если b_j <a_i, то исключаем ПН В_j (и соответствующий столбец); в "меньшей" таблице полагаем запас ПО А_i равным a_i - b_j;

3) если a_i = b_j, то:

а) если в таблице только один ПО А_i и один ПН В_j, то алгоритм останавливается;

б) если в таблице один ПО А_i и несколько ПН, то исключаем В_j, считая в "меньшей" таблице запас пункта А_i равным 0;

в) если в таблице один ПН В_j и несколько ПО, то исключаем А_i, считая в "меньшей" таблице потребность пункта В_j, равной 0;

г) если в таблице несколько ПО и несколько ПН, то исключаем либо ПО А_i, полагая в "меньшей" таблице потребность ПН В_j равной 0, либо исключаем ПН В_j, полагая запас ПО А_i равным 0.

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

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

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

Воспользуемся примером (табл. 5. 2).

Таблица 5.2

Пн По	В1	В2	В3	В4	Запасы
А1	10^4	15 ^3	^5	^7
А2	^2	5^1	^8	^6
А3	0 ^4	^9	30^3	15 ^2
Потребности					75=75

Рассмотрим произвольную клетку (А_i, В_j) - клетку транспортной таблицы с наименьшей стоимостью перевозок - клетку (2.2). Проставим в неё перевозку x₂₂=min(a₂,b₂)=min(20,5)=5. После этого запас пункта А₂ полностью исчерпан. Исключим мысленно из таблицы вторую строку. В меньшей транспортной таблице потребность пункта В₂ положим равной 25–10=15. Рассматриваем клетку с минимальной стоимостью новой таблицы. Руководствуясь тем же правилом, проставляем в неё перевозку х₃₄=15. Потребность пункта В₄ полностью удовлетворена, и мы исключаем из таблицы четвертый столбец, а в полученной транспортной таблице запас пункта А₃ делаем равным 45–15 = 30. В клетку (3,3) с минимальной стоимостью, равной 3, проставляем перевозку х₃₃=min(30,30)=30. При этом одновременно исчерпывается запас пункта А₃ и удовлетворяется потребность пункта В₃.

Переходя к новой таблице, нельзя одновременно убрать и столбец, и строку. Нужно убрать либо столбец, либо строку. Уберем, например, столбец. Третья строка еще не исключена из таблицы, запас пункта А₃ полагаем равным 0, поэтому в клетку (3,1) с минимальной стоимостью, равной 4, ставим перевозку х₃₁=min(10,0)=0. После этого исключаем третью строку из рассмотрения. Далее полагаем х₁₂=min(15,25)=15, исключаем второй столбец, а запас пункта А₁ делаем равным 25-15=10. Наконец, в клетку (1,1) проставляем х₁₁=10. Исходный опорный план найден. Базисными переменными являются х₁₁, х₁₂, х₂₂, х₃₁, х₃₃, х₃₄. Значения базисных переменных в опорном плане равны перевозкам, проставленным в соответствующих клетках. Опорный план является вырожденным, так как х₃₁=0. Число базисных переменных равно m+n–1, т.е. 3+4–1=6.

Метод минимального элемента усваивается очень легко. Чтобы убедиться в этом, проделайте самостоятельно такой пример (табл. 5.3.):

Таблице 5.3

Пн По	В1	В2	В3	Запасы
А1	^2	^3	^1
А2	^4	^2	^5
А3	^3	^2	^6
Потребности				150=150

У вас должен получиться результат, зафиксированный в таблице 5.4.

Таблица 5.4

Пн По	В1	В2	В3	Запасы
А1	^2	^3	40 ^1
А2	20 ^4	40 ^2	0 ^5
А3	^3	^2	^6
Потребности				150=150

Дата добавления: 2014-01-07