Решить целочисленную задачу линейного программирования для заданных значений A = ║aij║

Имеем задачу целочисленного линейного программирования (ЦЛП):
F(x) = 2·x1 + 7·x2 + 0·x3 + 0·x4 + 2·x5  max;
4·x1 + 1·x2 + 1·x3 = 14;
–3·x1 + 3·x2 + 1·x4 = 7;
–12·x1 + 6·x2 + 1·x5 = 7;
xj ≥ 0; xj – целые; j = 1, …, 5.
Решаем эту задачу методом отсечения Гомори.
Сначала решаем задачу симплексным методом без условия целочисленности.
Заполняем симплексную таблицу исходными данными задачи с учетом того, что её опорным решением является вектор x̃ = (0; 0; 14; 7; 7); F̃ = 14 с единичным базисом A3, A4, A5. Вычисляем значения в оценочной строке 4: 0·14 + 0·7 + 2·7 = 14 {столбец B}; 0·4 + 0·(–3) + 2·(–12) – 2 = –26 {столбец A1}; и т.д.
Видим, что в оценочной строке 4 (по столбцам A1 – A5) имеется отрицательный элемент, равный –26 (столбец A1). При этом столбец A1 содержит положительное число. Это значит, что данное опорное решение не является оптимальным, но также нет оснований полагать, что целевая функция неограничена сверху.
Вектор A1 следует ввести в базис . Далее следует вычислить отношения чисел столбца B ко всем соответствующим положительным числам столбца A1. Единственным таким числом в столбце A1 является число 4 в строке A3. Это отношение и будет считаться минимальным. Соответствующий вектор A3 выводим из базиса. Выбранные столбец и строка выделены цветом. Ведущий элемент x11 = 4 выделен кавычками.
№ Базис Cбаз B 2 7 0 0 2 Отношения
A1 A2 A3 A4 A5
1 A3 0 14 “4” 1 1 0 0 14/4 = 7/2 – min
2 A4 0 7 –3 3 0 1 0 –
3 A5 2 7 –12 6 0 0 1 –
4 – – 14 –26 5 0 0 0 –
Заполняем симплекс-таблицу, соответствующую новому опорному решению. При этом элементы строки A3 делим на ведущий элемент, а элементы столбца A1 полагаем равными нулю (за исключением ведущего элемента). Все остальные элементы (кроме элементов строки A3) в столбцах B и A2 – A5 вычисляем с использованием основных симплекс-формул (по правилу прямоугольника).
№ Базис Cбаз B 2 7 0 0 2 Отношения
A1 A2 A3 A4 A5
1 A1 2 3,5 1 0,25 0,25 0 0
2 A4 0 17,5 0 3,75 0,75 1 0
3 A5 2 49 0 9 3 0 1
4 – – 105 0 11,5 6,5 0 0 –
Оценочная строка 4 этой таблицы не содержит отрицательных оценок