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

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

¦-----------------------------------------------------------------¦

¦ Текущая Ц Ф (Max.) = 3980 є ZL = 4110 ¦

+-----------------------------------------------------------------+

¦ ТЕКУЩЕЕ РЕШЕНИЕ МЕТОДА ВЕТВ.и ГРАН.- итерац.: 7 Стр.: 1 ¦

¦-----------------------------------------------------------------¦

¦ Ниж.гран. ¦Перемен.¦Верх.гран ¦Перемен.¦ Решение ¦Целев.ф-ия.¦

¦-----------+--------+----------+--------+------------+-----------¦

¦ 0 є¦ X1 ¦є 10 ¦ X1 ¦ 0.125 ¦ 500.000 ¦

¦ 0 є¦ X2 ¦є 9 ¦ X2 ¦ 9.000 ¦ 450.000 ¦

¦ 0 є¦ X3 ¦є 0 ¦ X3 ¦ 0.000 ¦ 470.000 ¦

¦ 0 є¦ X4 ¦є 0 ¦ X4 ¦ 0.000 ¦ 510.000 ¦

¦-----------------------------------------------------------------¦

¦ НЕПРЕРЫВНОЕ РЕШЕНИЕ С Ц.Ф. (Max.) = 4112.5 ZL = 4110 ¦

+-----------------------------------------------------------------+

¦ ТЕКУЩЕЕ РЕШЕНИЕ МЕТОДА ВЕТВ.и ГРАН.- итерац.: 8 Стр.: 1 ¦

¦-----------------------------------------------------------------¦

¦ Ниж.гран. ¦Перемен.¦Верх.гран ¦Перемен.¦ Решение ¦Целев.ф-ия.¦

¦-----------+--------+----------+--------+------------+-----------¦

¦ 1 є¦ X1 ¦є 10 ¦ X1 ¦ 1.000 ¦ 500.000 ¦

¦ 0 є¦ X2 ¦є 9 ¦ X2 ¦ 7.600 ¦ 450.000 ¦

¦ 0 є¦ X3 ¦є 0 ¦ X3 ¦ 0.000 ¦ 470.000 ¦

¦ 0 є¦ X4 ¦є 0 ¦ X4 ¦ 0.000 ¦ 510.000 ¦

¦-----------------------------------------------------------------¦

¦ Текущая Ц Ф (Max.) = 3920 є ZL = 4110 ¦

+-----------------------------------------------------------------+

¦ ТЕКУЩЕЕ РЕШЕНИЕ МЕТОДА ВЕТВ.и ГРАН.- итерац.: 9 Стр.: 1 ¦

¦-----------------------------------------------------------------¦

¦ Ниж.гран. ¦Перемен.¦Верх.гран ¦Перемен.¦ Решение ¦Целев.ф-ия.¦

¦-----------+--------+----------+--------+------------+-----------¦

¦ 0 є¦ X1 ¦є 0 ¦ X1 ¦ 0.000 ¦ 500.000 ¦

¦ 0 є¦ X2 ¦є 9 ¦ X2 ¦ 9.000 ¦ 450.000 ¦

¦ 0 є¦ X3 ¦є 0 ¦ X3 ¦ 0.000 ¦ 470.000 ¦

¦ 0 є¦ X4 ¦є 0 ¦ X4 ¦ 0.000 ¦ 510.000 ¦

¦-----------------------------------------------------------------¦

¦ Текущая Ц Ф (Max.) = 4050 є ZL = 4110 ¦

+-----------------------------------------------------------------+

¦ ИТОГОВЫЙ РЕЗУЛЬТАТ для clm21 Стр. : 1 ¦

¦-----------------------------------------------------------------¦

¦Переменн.¦ ¦Целев.ф-ия.¦Переменн.¦ ¦Целев.ф-ия.¦

¦No. Имена¦ Решение ¦Коэффициент¦No. Имена¦ Решение ¦Коэффициент¦

¦---------+----------+-----------+---------+----------+-----------¦

¦1 X1 ¦ 0.000¦ 500.000 ¦3 X3 ¦ 0.000¦ 470.000 ¦

¦2 X2 ¦ 8.000¦ 450.000 ¦4 X4 ¦ 1.000¦ 510.000 ¦

¦-----------------------------------------------------------------¦

¦ MAX величина цел.ф-и = 4110 Всего итераций = 9 ¦

+-----------------------------------------------------------------+

Дерево решений:

III. Решение методом Гомори:

Для того чтобы решить задачу методом Гомори, надо выйти из режима «ЦЛП» и войти в режим «Линейное программирование», ввести условие задачи без учета целочисленности переменных. При решении задачи симплекс-методом, получаем последнюю таблицу:

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

+------------------------------------------------------+

¦ ¦ ¦X1 ¦X2 ¦X3 ¦X4 ¦S1 ¦ ¦ B(i) ¦

¦ ¦ +-----+-----+-----+-----+-----¦ ¦------¦

¦Базис¦C(j) ¦500.0¦450.0¦470.0¦510.0¦ 0¦B(i) ¦A(i,j)¦

¦-----+-----+-----+-----+-----+-----+-----+-----+------¦

¦X2 ¦450.0¦1.600¦1.000¦1.400¦1.200¦0.200¦9.200¦ 0 ¦

¦-----------+-----+-----+-----+-----+-----+-----+------¦

¦ C(j)-Z(j) ¦ -220¦ 0¦ -160¦-30.0¦-90.0¦ 4140¦ ¦

¦ * Big M ¦ 0¦ 0¦ 0¦ 0¦ 0¦ 0¦ ¦

+------------------------------------------------------+

(Max.) Оптим.величина ЦФ = 4140

По элементам последней симплексной таблице сформируем дополнительное ограничение:

Так как , то . Отсюда следует, что

(выр.1-2).

Подставив выражение 1-2 в выражение 1-1, получим:

В режиме «Корректировка» вводит дополнительное ограничение. Решаем, получаем последнюю таблицу:

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

+------------------------------------------------------------+

¦ ¦ ¦X1 ¦X2 ¦X3 ¦X4 ¦S1 ¦S2 ¦ ¦ B(i) ¦

¦ ¦ +-----+-----+-----+-----+-----+-----¦ ¦------¦

¦Базис¦C(j) ¦500.0¦450.0¦470.0¦510.0¦ 0¦ 0¦B(i) ¦A(i,j)¦

¦-----+-----+-----+-----+-----+-----+-----+-----+-----+------¦

¦X4 ¦510.0¦3.000¦ 0¦2.000¦1.000¦1.000¦-5.00¦1.000¦ 0 ¦

¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦

¦X2 ¦450.0¦-2.00¦1.000¦-1.00¦ 0¦%-1.006.000¦8.000¦ 0 ¦

¦-----------+-----+-----+-----+-----+-----+-----+-----+------¦

¦ C(j)-Z(j) ¦ -130¦ 0¦ -100¦ 0¦-60.0¦ -150¦ 4110¦ ¦

¦ * Big M ¦ 0¦ 0¦ 0¦ 0¦ 0¦ 0¦ 0¦ ¦

+------------------------------------------------------------+

(Max.) Оптим.величина ЦФ = 4110

Так как в последней симплексной таблице больше нет строк, содержащих элементы с дробными частями, считаем, что мы нашли оптимальное решение:

+-----------------------------------------------------------------+

¦ ИТОГОВЫЙ РЕЗУЛЬТАТ ДЛЯ clm22-1 Стр. : 1 ¦

¦-----------------------------------------------------------------¦

1 2 3

Скачать файл