Второй алгоритм Гомори

Данный алгоритм предназначен для решения задач, в которых требование целочисленности наложено на некоторые переменные (в частности и на все). Рассмотрим его применение к частично целочисленным задачам линейного программирования, имея в виду, что вычислительная схема будет справедлива и для полностью целочисленных задач. Пусть требуется максимизировать функцию

(23)

при условиях

(24)

(25)

(26)

Метод решения задачи (23) – (26) основывается на той же идее, что и метод решения полностью целочисленных задач. Сформулируем второй алгоритм Гомори в виде следующей теоремы.

Теорема 2: Пусть – оптимальное решение задачи и – соответствующая симплексная таблица. Если – не целое, то неравенство

(27)

или, что то же самое,

(28)

(29)

где

(30)

(31)

определяет оптимальное отсечение.

Мы проверим лишь условие отсечения. Для этого докажем, что оптимальное решение задачи , не являющееся допустимым решением исходной задачи (23) – (26), не удовлетворяет условиям отсечения. Пусть в оптимальном решении величина нецелая, . Так как в оптимальном решении все небазисные переменные равны нулю:

()

Тогда формула (8) примет вид

Поскольку по условию теоремы . Условие отсечения выполнено.

Правило построения правильного отсечения: Пусть не удовлетворяет условию целочисленности (26) и – симплекс-таблица, соответствующая полученному оптимальному решению задачи . Выберем

и построим правильное отсечение по формулам (28) – (31).

[11]

Date: 2016-07-22; view: 397; Нарушение авторских прав