Линейное программирование 2 3 (стр. 4 из 6)
Ответ:
и 
.Задача 8 (16.237)
Решить полностью целочисленную задачу линейного программирования методом Гомори.
Решение:
Введем дополнительные переменные
и запишем условие вспомогательной задачи линейного программирования для рассматриваемого случая: 
Считая дополнительные переменные
базисными, запишем симплекс таблицу этой задачи, соответствующую угловой точке 
:  |  |  |  | ||
 | 1 | 0 | 2 | 1 | 8 |
 | 1 | 1 | 0 | -1 | 4 |
 | -1 | 2 | 1 | 3 | 6 |
| -1 | -3 | -3 | -3 | -18 |
Произведем преобразования исходной симплекс-таблицы симплекс-методом следующим образом: смотрим на нижнюю строку – выбираем тот столбец, в котором нижний элемент отрицательный, если таких столбцов несколько, то выбираем любой (в нашем случае выбираем первый столбец
); далее смотрим на последний и выбранный столбцы – сравниваем отношения элементов последнего и выбранного столбцов (в выбранном столбце берем только положительные числа), и выбираем тот элемент выбранного столбца, где отношение элементов будет наименьшим (в нашем случае 9/3 и 0/1, так как второе отношение наименьшее, следовательно, опорным элементом будет 1); меняем местами переменные и , остальные переменные оставляем на своих местах; на место опорного элемента ставим отношение 1/(опорный элемент); а остальных местах разрешающей строки записываем соответствующие элементы исходной таблицы, деленные на опорный элемент; на свободные места разрешающего столбца ставим со знаком минус соответствующие элементы исходной таблицы, деленные на опорный элемент; оставшиеся свободные места в новой симплекс-таблице заполняем построчно следующим образом: из строки элементов исходной таблицы вычитаем произведение ее элемента из разрешающего столбца на уже заполненную разрешающую строку новой таблицы. Производя преобразования симплекс-метода, получим такую последовательность симплекс-таблиц: | | | | | ||
| | 4/3 | -2/3 | 5/3 | -1/3 | 6 |
| | 2/3 | 5/3 | 1/3 | 1/3 | 6 |
| | -1/3 | 2/3 | 1/3 | 1/3 | 2 |
| -2 | -1 | -2 | 1 | -12 |
| | | | | ||
| | 1 | 1 | 2 | 0 | 8 |
| | 3/2 | -5/2 | -1/2 | -1/2 | 1 |
| | -1/2 | 3/2 | 1/2 | 1/2 | 3 |
| -5/2 | 3/2 | -3/2 | 3/2 | -9 |
| | | | | ||
| | 1/2 | 1/2 | 1/2 | 0 | 4 |
| | 7/4 | -9/4 | 1/4 | -1/2 | 3 |
| | -3/4 | 5/4 | -1/4 | 1/2 | 1 |
| -7/4 | 9/4 | 3/4 | 3/2 | -3 |
| | | | | ||
| | -2/7 | 8/7 | 3/7 | 1/7 | 22/7 |
 | 4/7 | -9/7 | 1/7 | -2/7 | 12/7 |
| | 3/7 | 2/7 | -1/7 | 2/7 | 16/7 |
| 1 | 0 | 1 | 1 | 0 |
Как видим, в последней строке таблицы все элементы положительны, то есть получаем решение
и 
. Но это решение не удовлетворяет условию целочисленности, поэтому дополняем последнюю симплекс-таблицу строкой, используя следующие правила: среди нецелых элементов 
выбирается произвольный элемент 
, по r-ой строке симплекс-таблицы составляется дополнительное ограничение вида 
(здесь мы полагаем, что свободные переменные 
имеют номера m+1,…,n). С помощью вспомогательной переменной 
это ограничение представляется в виде равенства 
и вводится в симплекс-таблицу дополнительной строкой