Информатика и выч. техника \ Прикладные методы оптимизации

Решение задач целочисленного линейного программирования на ЭВМ, страница 7

Итерация 3

╔══════╤══════╤══════╤══════╤══════╤══════╤══════╤══════╤══════╤══════╗

║Об\Зд │T1 │T2 │T3 │T4 │T5 │T6 │T7 │T8 │ **** ║

╟──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────╢

║O1 │ 0 │ 1.000│ 3.000│ 0 │ 7.000│ 4.000│ 7.000│ 2.000│ ║

║O2 │ 2.000│ 3.000│ 5.000│ 2.000│ 3.000│ 7.000│ 1.000│ 0 │<-- ║

║O3 │ 4.000│ 2.000│ 1.000│ 0 │ 0 │ 7.000│ 6.000│ 5.000│ ║

║O4 │ 0 │ 0 │ 1.000│ 2.000│ 4.000│ 4.000│ 5.000│ 6.000│ ║

║O5 │ 5.000│ 5.000│ 6.000│ 2.000│ 0 │ 3.000│ 1.000│ 1.000│ ║

║O6 │ 1.000│ 0 │ 1.000│ 1.000│ 3.000│ 2.000│ 3.000│ 4.000│ ║

║Фикт. │ 1.000│ 0 │ 0 │ 0 │ 1.000│ 0 │ 0 │ 0 │<-- ║

║ **** │ ^ │ ^ │ │ ^ │ ^ │ │ │ │ ║

╚══════╧══════╧══════╧══════╧══════╧══════╧══════╧══════╧══════╧══════╝

КОНЕЧН.ТАБЛИЦА (Всего итераций = 4)

║Об\Зд │T1 │T2 │T3 │T4 │T5 │T6 │T7 │T8 │ **** ║

║O1 │ 0 │ 1.000│ 2.000│ 0 │ 7.000│ 3.000│ 6.000│ 1.000│ ║

║O2 │ 3.000│ 4.000│ 5.000│ 3.000│ 4.000│ 7.000│ 1.000│ 0 │ ║

║O3 │ 4.000│ 2.000│ 0 │ 0 │ 0 │ 6.000│ 5.000│ 4.000│ ║

║O4 │ 0 │ 0 │ 0 │ 2.000│ 4.000│ 3.000│ 4.000│ 5.000│ ║

║O5 │ 5.000│ 5.000│ 5.000│ 2.000│ 0 │ 2.000│ 0 │ 0 │ ║

║O6 │ 1.000│ 0 │ 0 │ 1.000│ 3.000│ 1.000│ 2.000│ 3.000│ ║

║Фикт. │ 2.000│ 1.000│ 0 │ 1.000│ 2.000│ 0 │ 0 │ 0 │ ║

║ **** │ ^ │ ^ │ ^ │ ^ │ ^ │ ^ │ ^ │ ^ │ ║

┌──────────────────────────────────────────────────────────────────┐

│ СУММАРНЫЕ НАЗНАЧЕНИЯ для jjj Стр. : 1 │

╞═══════════╤══════════╤══════════╦══════════╤══════════╤══════════╡

│ Обьект │ Зад. │Затр/Приб.║ Обьект │ Зад. │Затр/Приб.│

╞═══════════╪══════════╪══════════╬══════════╪══════════╪══════════╡

│ O1 │ T4 │ 2.000 ║ O5 │ T7 │ 4.000 │

│ O2 │ T8 │ 1.000 ║ O6 │ T2 │ 2.000 │

│ O3 │ T5 │ 1.000 ║ Фикт. │ T3 │ 0 │

│ O4 │ T1 │ 1.000 ║ Фикт. │ T6 │ 0 │

╞═══════════╧══════════╧══════════╩══════════╧══════════╧══════════╡

│ MIN значение Ц Ф = 11 Всего итераций = 4 │

└──────────────────────────────────────────────────────────────────┘

Найденный опорный план: Х*=

Вручную мы получили еще два альтернативных решения получения оптимального плана данной задачи (не смотря на то, что ПЭР нам не показал, что нахождение данного ОП не является единственным)

Итак, первоначальную таблицу (табл.1) мы заполняем таким образом, чтобы исходная наша матрица стала квадратичной:

	1	2	3	4	5	6	7	8	Ui
1	1	3	5	2	8	6	9	4	1
2	2	4	6	3	3	8	2	1	1
3	5	4	3	2	1	9	8	7	1
4	1	2	3	4	5	6	7	8	1
5	7	8	9	5	2	6	4	4	2
6	2	2	3	3	4	4	5	6	2
7	0	0	0	0	0	0	0	0	0
8	0	0	0	0	0	0	0	0	0

	1	2	3	4	5	6	7	8
1	0	2	4	1	7	5	8	3
2	1	3	5	2	2	7	1	0
3	4	3	2	1	0	8	7	6
4	0	1	2	3	4	5	6	7
5	5	6	7	3	0	4	2	2
6	0	0	1	1	2	2	3	4
7	0	0	0	0	0	0	0	0
8	0	0	0	0	0	0	0	0
Vj	0	0	0	0	0	0	0	0

1 2 3 4 5 6 7 8

Скачать файл

	1	2	3	4	5	6	7	8	Ui
1	1	3	5	2	8	6	9	4	1
2	2	4	6	3	3	8	2	1	1
3	5	4	3	2	1	9	8	7	1
4	1	2	3	4	5	6	7	8	1
5	7	8	9	5	2	6	4	4	2
6	2	2	3	3	4	4	5	6	2
7	0	0	0	0	0	0	0	0	0
8	0	0	0	0	0	0	0	0	0

	1	2	3	4	5	6	7	8
1	0	2	4	1	7	5	8	3
2	1	3	5	2	2	7	1	0
3	4	3	2	1	0	8	7	6
4	0	1	2	3	4	5	6	7
5	5	6	7	3	0	4	2	2
6	0	0	1	1	2	2	3	4
7	0	0	0	0	0	0	0	0
8	0	0	0	0	0	0	0	0
Vj	0	0	0	0	0	0	0	0

	1	2	3	4	5	6	7	8	Ui
1	1	3	5	2	8	6	9	4	1
2	2	4	6	3	3	8	2	1	1
3	5	4	3	2	1	9	8	7	1
4	1	2	3	4	5	6	7	8	1
5	7	8	9	5	2	6	4	4	2
6	2	2	3	3	4	4	5	6	2
7	0	0	0	0	0	0	0	0	0
8	0	0	0	0	0	0	0	0	0

	1	2	3	4	5	6	7	8
1	0	2	4	1	7	5	8	3
2	1	3	5	2	2	7	1	0
3	4	3	2	1	0	8	7	6
4	0	1	2	3	4	5	6	7
5	5	6	7	3	0	4	2	2
6	0	0	1	1	2	2	3	4
7	0	0	0	0	0	0	0	0
8	0	0	0	0	0	0	0	0
Vj	0	0	0	0	0	0	0	0

Решение задач целочис­ленного линейного программирования на ЭВМ, страница 7

Решение задач целочисленного линейного программирования на ЭВМ, страница 7

	1	2	3	4	5	6	7	8	Ui
1	1	3	5	2	8	6	9	4	1
2	2	4	6	3	3	8	2	1	1
3	5	4	3	2	1	9	8	7	1
4	1	2	3	4	5	6	7	8	1
5	7	8	9	5	2	6	4	4	2
6	2	2	3	3	4	4	5	6	2
7	0	0	0	0	0	0	0	0	0
8	0	0	0	0	0	0	0	0	0

	1	2	3	4	5	6	7	8
1	0	2	4	1	7	5	8	3
2	1	3	5	2	2	7	1	0
3	4	3	2	1	0	8	7	6
4	0	1	2	3	4	5	6	7
5	5	6	7	3	0	4	2	2
6	0	0	1	1	2	2	3	4
7	0	0	0	0	0	0	0	0
8	0	0	0	0	0	0	0	0
Vj	0	0	0	0	0	0	0	0