Введение в линейное программирование. Палий И.А. - 79 стр.

UptoLike

ВУЗ: 

СибАДИ | Омск

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

Рубрика: 

Формальное описание алгоритма
Шаг 1. Найти исходное допустимое решение двойственной задачи,
положив
);,,1(,min micu
ij
j
i
L==
).,,1(),(min njucv
iij
i
j
L
=
−
=
При таком допустимом решении в каждой строке и каждом столбце
матрицы затрат появится по крайней мере одна допустимая клетка.
Шаг 2. Положить
jiijij
vucc
−
−
=
′
,
mi ,,1 L
=
, n
j
,,1 L
=
.
Шаг 3. Решить задачу о максимальном потоке, считая допустимыми
клетки с нулями в матрице
C
′
. Возможны два случая:
а) все потребности удовлетворены;
б) не все потребности удовлетворены.
В случае а) перейти к шагу 6, в случае б) – к шагу 4.
Шаг 4. Прочеркнуть в матрице стоимостей
C
′
непомеченные строки и
помеченные столбцы (покрывающее множество рядов) и найти
минимальный элемент
h в оставшейся части матрицы (h > 0).
Шаг 5. Пересчитать двойственные переменные по правилу (9.14).
Прейти к шагу 2.
Шаг 6. Положить x
ij
=0, если дуги (A
i
, B
j
) нет в транспортной сети или
поток на ней равен 0. В противном случае положить x
ij
=x(A
i
, B
j
).
Оптимальные значения перевозок найдены. Конец.
Для удобства вычислений шаг 5 формулируется по-другому.
Шаг 5. Вычесть h из всех непрочеркнутых элементов матрицы
стоимостей
C
′
и прибавить к дважды прочеркнутым. Перейти к шагу 3.
Решим Т3, заданную в табл. 9.4.
∑∑
==
=
6
1
5
1 j
j
i
i
ba
= 270, Т3 закрыта.
Таблица 9.4
Потребители
Поставщики
В
1
В
2
В
3
В
4
В
5
В
6
Запасы
A
1
6 5 4 7 6 8 90
A
2
7 6 5 9 6 5 20
A
3
8 5 6 6 3 8 30
A
4
6 7 5 7 4 9 50
A
5
5 4 7 8 5 2 80
Потребности 40 60 80 30 10 50
Шаг 1. Определяем допустимое решение двойственной задачи.

Страницы