Математика для экономистов - Красс М.С.
ISBN 5-94723-672-9
Скачать (прямая ссылка):
При распределении грузов может оказаться, что количество запятых клеток меньше, чем т + п - 1. В этом случае недостающее их число заполняется клетками с нулевыми поставками, такие клетки называют условно занятыми. Такая транспортная задача называется вырожденной.
Рассмотрим нахождение исходного опорного решения невырожденной транспортной задачи на конкретном примере.
Пример 1.
На складах A1, A2, A^ имеются запасы продукции в количествах 90, 400, 110 т соответственно. Потребители B1, B3, В-Л должны получить згу продукцию в количествах 140. 300, 160 т соответственно. Найти такой вариант прикрепления поставщиков к потребителям, при котором сумма затрат на перевозки была бы минимальной. Расходы по перевозке 1 т продукции заданы матрицей (у. е.)
Решение.
А. Проверим, является ли данная транспортная задача закрытой:
(1 5 2\
А 1 5
^3 6 8J
?о, .= 90+400+ 110 =600 т,
2^h1 =140 + 300+16 = 600 т.
следовательно, данная транспортная задача является закрытой. Найдем исходное опорное решение по методу минимального тарифа. Таблица исходной транспортной задачи имеет следующий вид.
14,4. Транспортная задача 289
I
2
3
140
300
160
t 2
90
2
90
а
5
2
400
1
300
I
5 ,
1
100
3
110
ъ
5U
б
8
GO
Число занятых клеток в таблице равно 5, т + и - 1 = 3 + 3 - 1 = 5, т. е. условие невырожденности выполнено. Получим исходное опорное решение, которое запишем в виде матрицы:
Г 90 0 (Л 0 300 too 50 0 60,
v
-Лпт1
Стоимость перевозки при исходном опорном решении составляет L (Хоти = 90 ¦ 2 + 300 • 1 + 100 ¦ 5 + 50 ¦ 3 + 60 ¦ 8 = 1610 усл. ед. Б. Проверка решения на оптимальность
Найденное исходное опорное решение проверяется на оптимальность методом потенциалов по елсдуювдему критерию: если опорное решение транспортной задачи является оптимальным, то ему соответствует система т + п действительных чисел U1 и Vj, удовлетворяющих условиям и, + V1 = Cn для занятых клеток и и, + L) - с„ < 0 — дтя свободных клеток.
Числа и, и Vj называют потенциалами. В распределительную таблицу добавляют строку vj и столбец ц. Потенциалы и, и у;- находят из равенства и, + V1 = с,п сираиедлиного для занятых клеток. Одному из потенциалов дается произвольное значение, например, «i = 0, тогда остальные потенциалы определяются однозначна. Так, если известен потенциал U1-, TO L) = СЧ- U,, ЄСЛИ НЗНеСТеН ПОТеНЦИал vp TO Й, = C1J - Vj.
Обозначим Д,, = н-> + Vj - которую называют оценкой свободных клеток. Если все оценки свободных клеток Д„5 0, то опорное решение
19-12І2
290 Глава 14, Линейное программирование
а'
1
но
2
зоо
3
160
щ
1
00
г
90
5
•>
0
2
400
4
1;
300
5
100
-2
3
110
2
50
6
а
60
1
: »
3
7 I
Полагаем н, =0, запишем это значение в последнем столбце первой строки таблицы. Рассмотрим запятую клетку первой строки, которая расположена в первом столбце (1, 1), для нее выполняется условие и, + и, = 2. Отсюда при u, = 1 получаем, что i\ = 2, это значение запишем в последней строке таблицы. Далее надо рассматривать ту из занятых клеток таблицы, для которых один из потенциалов известен.
Рассмотрим занятую клетку (З, 1): и^ + V1 = 3, V1 = 2, откуда Uj= 1. Для клетки (3, 3): U3+ E'3 = ?, U3= і, в3 = 7. Для клетки (2, 3): и-А + !J3 = 5. щ = 7, U1 = -2. Для клетки (2, 2): U2 + V2 = 1. иг - -2, 1.? = 3, Найденные значения потенциалов заносим в таблицу. Вычисляем оценки свободных клеток:
A12
= ц,
+ V2
c12
= 0 + 3-
5 =
-2<0,
Ліз
= ц,
+ щ
-c13
= 0 + 7 -
2 =
5>0,
A2,
= щ
= -2 + 2
- 4
= -4<0,
Д33
= ц;1
+ It2
- С31
= 1+3 -
6 =
-2<0.
является оптимальным. Если хотя бы одна на оденок A11 > 0, та опорное решение не является оптимальным и его можно улучшить, перейдя от одного опорного решения к другому.
Проверим найденное опорное решение на оптимальность, добавив в распределительную таблицу столбец uf и строку V1. Теперь дополненная таблица имеет следующий mi?.'-
14.4. Транспортная задача 291
В. Переход от одного решения к другому'.
Наличие положительной оценки свободной клетки (Дй > 0) при проверке опорного решения на оптимальность свидетельствует о том, что полученное решение не оптимально и для уменьшения значения целевой функции надо перейти к другому опорному решению. При этом надо перераспределить грузы, перемещая vrx из занятых клеток в свободные. Свободная клетка становится занятой, а одна из ранее занятых клеток — свободной.
Для свободной клетки с Д(( > 0 строится цикл (цепь, многоугольник), все вершины которого, кроме одной, находятся в занятых клетках; углы прямые, число вершин четное. Около свободной клетки цикла ставится знак (+), затем поочередно проставляют знаки (-) и (+). У вершин со знаком (-) выбирают минимальный груз, его прибавляют к грузам, стоящим у вершин со знаком (+), и отнимают от грузов у вершин со знаком (-). В результате перераспределения груза получим новое опорное решение. Это решение проверяем на оптимальность, и т. д. до тех пор, пока не получим оптимальное решение.
