Линейное целочисленное программирование

Среди практических задач важное место занимают задачи математического программирования с требованием целочисленности переменных (всех или части).

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

и удовлетворяющих условиям

,

а также условиям неотрицательности

и целочисленности

- целые, .

Метод отсечений (метод Гомори)

Метод Гомори основан на применении симплекс-метода и метода отсечения.

Алгоритм метода

1. Сформулированная задача решается симплекс-методом без учета целочисленности.

2. Если в результате получено целочисленное оптимальное решение, то цель достигнута. В противном случае выбирается переменная с нецелочисленным оптимальным значением (если дробных переменных несколько, то выбирается та, у которой дробная часть больше).

3. Для выбранной неизвестной записывается условие отсечения её нецелочисленного значения в виде линейного неравенства. Новое ограничение добавляется в симплексную таблицу с оптимальным решением, и переходим к шагу 1.

Признаком отсутствия целочисленного решения является отсутствие дробных значений коэффициентов в строке с дробным значением базисной переменной.

Для того чтобы сформулировать правило построения условия отсечения, введем некоторые обозначения. Пусть а есть некоторое действительное число. Обозначим через [а] целую часть числа а.

Целой частью числа а называется наибольшее целое число, меньшее или равное а. Приведем примеры нахождения целой части различных чисел:

Обратите внимание, что если целая часть положительного числа получается простым отбрасыванием его дробной части, то целая часть отрицательного числа получается отбрасыванием дробной части числа и увеличением модуля полученного результата на единицу.

Обозначим далее через {а} дробную часть числа а. Дробная часть числа а есть разность между данным числом и его целой частью:

Для чисел, рассмотренных выше, найдем дробные части:

Дробная часть числа всегда положительна.

Чтобы сформулировать условие отсечения в процессе решения задачи целочисленного линейного программирования, необходимо из последней (оптимальной) симплекс-таблицы выписать уравнение, содержащее выбранную нецелочисленную неизвестную х_к:

где — базисная неизвестная; — свободная неизвестная; - нецелочисленное значение базисной переменной. Тогда условие отсечения будет иметь вид

Здесь — дробные части соответствующих чисел.

Рассмотрим применение метода отсечений на конкретном примере.

Пример.

Отбрасывая требование целочисленности, решим заданную задачу как обычную задачу линейного программирования.

БП	СЧ				CO
	20	2	3	1	20/3
	40	9	7	10	4 0/7
F	0	-2	-4	-3

БП	СЧ
	20/7	-13/7	-3/7	-23/7
	40/7	9/7	1/7	10/7
F	160/7	22/7	4/7	19/7

В полученном оптимальном решении задачи имеем нецелочисленное значение неизвестной х₂ . Дополнительное ограничение формируем по элементам второй строки:

БП	СЧ				CO
	20/7	-13/7	-3/7	-23/7	-
	40/7	9/7	1 /7	10/7	40
	-5/7	-2/7	-1/7	-3/7	5
F	160/7	22/7	4/7	19/7

БП	СЧ
	5
	5
	5
F	20	2	4	1

Ответ: