§1.6 Целочисленные задачи линейного программирования. Метод Гомори.

В общем случае задача целочисленного программированияформулируется следующим образом. Найти максимум или минимум функции

, при условиях , .

Согласно методу Гомори задача линейного программирования сначала решается симплексным методом без учета целочисленности переменных. Если оптимальное решение оказывается целочисленным, то решение заканчивается. Если оптимальное решение нецелочисленное, то из системы ограничений выбирается уравнение, для которого дробная часть координаты оптимального решения имеет наибольшее значение и на его основе составляется дополнительное ограничение. Дополнительное ограничение отсекает от области допустимых решений нецелочисленное оптимальное решение. Но при этом сохраняет целочисленные вершины этой области.

Пусть -е ограничение задачи, находящееся в последней симплексной таблице, имеет вид

,

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

Тогда дополнительное ограничение имеет вид

,                                                                                    (3)

где - дробная часть ; - дробная часть .

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

.

         Например, для числа целая часть , дробная часть равна . Для числа целая часть , дробная часть равна . Дробная часть числа всегда неотрицательная и меньше единицы.

         В неравенство (3) вводится дополнительная переменная , получается уравнение

.

В систему ограничений задачи это ограничение записывается в виде

.                                                                     

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

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

Пример.Решить задачу целочисленного программирования

при ограничениях

, , , .

Решение.

Первоначально решим данную задачу симплекс-методом без учета требования целочисленности.

Получим

Табл.

Табл. 2

Табл.

Полученнное оптимальное решение не целочисленное, .

Применим метод Гомори. В столбце свобдных членов определим максимальную дробную часть свободных членов:

Составим ограничение, соответствующее уравнению (первой строки)

Оно имеет вид

Это неравенство заменим равенством

т.е.

Составим новую таблицу Гаусса, содержащую последний блок предыдущей таблицы, к которому присоединим построенное последнее уравнение (в таблице вводится дополнительный столбец для дополнительной неизвестной).

Табл. 4

Табл. 5

Получили новое оптимальное решение с одной целой компонентой – нецелое оптимальное решение

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

Максимальная дробная часть свободного члена в последнем блоке соответствует третьей строке, т.е. уравнению

Составим новое неравенство (отсечение):

или уравнение

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

Табл.6

Табл. 7

Табл.8

Некоторые компоненты оптимального решения не являтся целыми числами, при этом , поэтому надо строить очередное отсечение, которое соответствует уравнению (второй строки). Новое уравнение имеет вид

или

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

Табл. 9

Табл.10

Оптимальное решение имеет целые компоненты (было бы достаточно, если бы целыми были только первые четыре компоненты).

Отбрасываязначения дополнительных неизвестных, составляем ответ: и