Транспортная задача линейного программирования. Бартеньев А.П - 7 стр.

UptoLike

ВУЗ: 

МичГАУ | Мичуринск

Составители: 

Рубрика: 

7
ной величиной. Обозначим эту разность через l
ij
. Проверим вы-
полнение условия l
ij
≥ 0 для каждой свободной клетки. Если это
условие выполняется, то построенный опорный план оптимален.
В противном случае переходим к новому плану.
4. Для этого вычислим l
ij
для всех незанятых клеток и среди
отрицательных величин находим наибольшую по абсолютному
значению, что соответствует клетке с максимальным нарушением
оптимальности. Такая клетка называется “плохой”.
5. Для найденной клетки строим замкнутый маршрут по за-
нятым клеткам. Такой маршрут всегда существует и определяет-
ся единственным образом. Маршрут начинается с плохой клетки
и в ней же заканчивается – маршрут замкнут. Переход от одной
клетки к другой осуществляется только по горизонтали и верти-
кали, причем в углах поворота маршрута обязательно должны
находится заполненные клетки.
6. В углах поворота маршрута проставляем знаки плюс и ми-
нус через один, начиная с “плохой” клетки, в которую записыва-
ем “+”.
7. Выбираем наименьшую поставку среди клеток, помечен-
ных знаком “-”.
8. Переходим к новому варианту плана. Для этого найденную
наименьшую поставку прибавляем в клетки, помеченные знаком
“+” и вычитаем из клеток, помеченных знаком “-”. Полученный
вариант плана вновь проверяем на оптимальность. Процесс про-
должается до тех пор, пока все свободные клетки не будут удов-
летворять условию оптимальности.
Вернемся к нашей задаче. Наибольшее число занятых клеток
имеется во второй строке. Примем потенциал этой строки рав-
ным нулю (α
2
= 0). Вычислим потенциалы остальных строк и
столбцов, исходя из условия что для всех занятых клеток
с
ij
=α
i
+β
j
. Для клетки k
22
6=0+β
2
, отсюда β
2
=6-0= 6. Далее β
3
=2-
0=2, β
4
=2-0= 2, β
5
= 4-0= 4. Перейдя в клетку k
12
, для которой по-
тенциал второго столбца известен, можно рассчитать потенциал
первой строки α
1
=2-6=-4, далее рассчитаем потенциал первого
столбца β
1
=3-(-4)=7. Остается рассчитать потенциал третей стро-
ки через оценку клетки k
15
и потенциал пятого столбца
α
3
=3-4= -1.
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com
         ной величиной. Обозначим эту разность через lij. Проверим вы-
         полнение условия lij ≥ 0 для каждой свободной клетки. Если это
         условие выполняется, то построенный опорный план оптимален.
         В противном случае переходим к новому плану.
              4. Для этого вычислим lij для всех незанятых клеток и среди
         отрицательных величин находим наибольшую по абсолютному
         значению, что соответствует клетке с максимальным нарушением
         оптимальности. Такая клетка называется “плохой”.
              5. Для найденной клетки строим замкнутый маршрут по за-
         нятым клеткам. Такой маршрут всегда существует и определяет-
         ся единственным образом. Маршрут начинается с плохой клетки
         и в ней же заканчивается – маршрут замкнут. Переход от одной
         клетки к другой осуществляется только по горизонтали и верти-
         кали, причем в углах поворота маршрута обязательно должны
         находится заполненные клетки.
              6. В углах поворота маршрута проставляем знаки плюс и ми-
         нус через один, начиная с “плохой” клетки, в которую записыва-
         ем “+”.
              7. Выбираем наименьшую поставку среди клеток, помечен-
         ных знаком “-”.
              8. Переходим к новому варианту плана. Для этого найденную
         наименьшую поставку прибавляем в клетки, помеченные знаком
         “+” и вычитаем из клеток, помеченных знаком “-”. Полученный
         вариант плана вновь проверяем на оптимальность. Процесс про-
         должается до тех пор, пока все свободные клетки не будут удов-
         летворять условию оптимальности.
              Вернемся к нашей задаче. Наибольшее число занятых клеток
         имеется во второй строке. Примем потенциал этой строки рав-
         ным нулю (α2= 0). Вычислим потенциалы остальных строк и
         столбцов, исходя из условия что для всех занятых клеток
         сij=αi+βj. Для клетки k22 6=0+β2, отсюда β2=6-0= 6. Далее β 3=2-
         0=2, β4=2-0= 2, β5= 4-0= 4. Перейдя в клетку k12, для которой по-
         тенциал второго столбца известен, можно рассчитать потенциал
         первой строки α1=2-6=-4, далее рассчитаем потенциал первого
         столбца β1=3-(-4)=7. Остается рассчитать потенциал третей стро-
         ки через оценку клетки k15 и потенциал пятого столбца
         α3=3-4= -1.

                                                                             7

PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com

Страницы