Реализация целочисленных моделей принятия решений

Получен оптимальный нецелочисленный план Хопт= (61/18;22/9).  Lmax = 376/9.

Т.к. у компоненты плана х2 максимальная дробная часть:
max(4/9;7/18) = 4/9, то дополнительное ограничение записываем по первой строке.

22/9 - [22/9] = (2/9 - [2/9])x3 + (-1/9 - [-1/9])x4 - S1, S1  0
22/9 - 2 = (2/9 - 0)x3 + (-1/9 - (-1))x4 - S1, S1  0
4/9 = 2/9x3 + 8/9x4 - S1, S1   0  -  первое ограничение Гомори.

Составленное ограничение дописываем к имеющимся в симплексной таблице.

После построения дополнительного ограничения имеем новую задачу линейного программирования, в которой 3 ограничения. Для получения опорного плана этой задачи необходимо найти третий базисный вектор. Для этого определяем:

min = в базис вводим вектор х4.

Рассчитываем величину = . Минимальное значение  получено по дополнительной строке, значит, не прибегая к искусственной переменной, получаем опорный план расширенной задачи.

Найденный план оптимален, но нецелочисленный. Строим новое ограничение Гомори.

Т.к. максимальная дробная часть среди компонент плана равна 1/2, записываем дополнительное ограничение по первой строке (можно и по третьей).

5/2 - [5/2] = (1/4 - [1/4])x3 + (-1/8 - [-1/8])S1 - S2, S2  0
1/2 = 1/4x3 + 7/8S1 - S2, S2  0 -   второе ограничение Гомори

Это ограничение добавляем в последнюю симплексную таблицу.

Получили задачу, в которой 4 ограничения, следовательно, в базисе должно быть 4 единичных вектора.

Определяем вектор, вводимый в базис: . Можно ввести либо x3, либо S1. Введем вектор S1.

соответствует дополнительному ограничению.

Получаем новый оптимальный нецелочисленный план. Учитывая замечание 1, вычеркиваем строку и столбец, соответствующие переменной S1.

В полученном плане максимальную дробную часть имеет компо-нента х2, поэтому записываем дополнительное ограничение по первой строке.

4/7 = 2/7х3 + 6/7S2 - S3,    S3  0    - третье ограничение Гомори.

Определяем вектор, вводимый в базис: . Это вектор х3. Минимальное значение  = 2, что соответствует дополнительной строке.

После проведения очередных симплексных преобразований получили:

План Х5 - оптимальный нецелочисленный.

Дополнительное ограничение запишем по второй строке:

1/2 = 1/4S3 - S4,  S4  0   - четвертое ограничение Гомори.

Т.к. базисной компонентой может быть S3, определяем величину . Минимальное значение получилось по 3 строке, а не по строке Гомори, следовательно, переходим к М-задаче: введем дополнительную переменную х5 в ограничение Гомори.