Линейная алгебра. Линейное программирование. Тарбокова Т.В. - 119 стр.

UptoLike

ВУЗ: 

ТПУ | Томск

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

Рубрика: 

119
Рис. 2.7
Замечание. Для того, чтобы план таблицы 2.10 стал невырожденным,
надо занять одну клетку нулем (иначе нельзя определить потенциалы, а
значит, нельзя проверить на оптимальность полученный план). Нуль мож-
но записать либо в строке
2
=
i
, либо
в
столбце
4
=
j
,
ибо
они
были
ис
-
ключены
одновременно
в
четвертую
очередь
(
именно
для
этого
была
нуж
-
на
нумерация
исключаемых
строк
и
столбцов
).
В
клетке
(2, 1),
которая
от
-
мечена
звездочкой
,
записать
нуль
нельзя
:
эта
клетка
образует
цикл
с
заня
-
тыми
клетками
(1, 1), (1, 4)
и
(2, 4).
Можно
было
занимать
либо
клетку
(3,
4),
либо
клетку
(2, 3).,
которые
тоже
отмечены
звездочками
.
Последняя
клетка
и
была
занята
и
отмечена
уголком
,
хотя
в
качестве
занятой
можно
было
бы
брать
и
клетку
(3, 4)
Итак
,
построен
цикл
с
вершиной
в
отмеченной
клетке
с
наименьшей
отрицательной
оценкой
.
Если
таких
клеток
несколько
,
то
следует
брать
одну
из
них
произвольно
,
или
клетку
с
меньшим
тарифом
.
Тем
самым
вершины
разбиваются
на
две
группы
–
с
нечетными
(
отмеченная
считается
первой
,
т
.
е
.
нечетной
)
и
четными
номерами
.
Найдем
наименьшую
из
вели
-
чин
поставок
четных
вершин
(
обозначим
ее
буквой
θ
).
Эту
величину
θ
прибавим
ко
всем
вершинам
с нечетными
номерами
и
отнимем
от
вер
-
шин
с четными
номерами
.
Новое
распределение
поставок
присоединяется
к
остальным
занятым
клеткам
;
таким
образом
,
составляется
новый
опор
-
ный
план
2
X
с
)()(
1
2
XLXL
<
.
Этот
план
заносится
в
новую
таблицу
и
проверяется
на
оптимальность
методом
потенциалов
.
В
новой
таблице
не
-
обязательно
записывать
величины
i
a
и
j
b .
Улучшение
новых
планов
проводят
до
тех
пор
,
пока
очередной
план
не
станет
оптимальным
.
Для
него
все
оценки
клеток
должны
быть
неотри
-

Страницы