С учетом таблицы1 первое условие (10) оказывается не информативным, так как дает , а второе, принимая вид , указывает на целесообразность построения отсечения Гомори для базисной переменной с индексом i=1.
Т.о. из (9) в нашем случае условие отсечения запишется как . Вводя новую целевую функцию , внесем все это в новую симплекс-таблицу, использующую данные последней итерации Табл.1:
Табл.3
СИМПЛЕКС-Таблица с учетом условия отсечения ГОМОРИ
N итерации
Базисные Переменные
Значения
Переменные
X1
X2
X3
X4
X5
X6
X1
4 1/2
1
0
1/10
1/10
0
0
X2
20 1/2
0
1
9/10
- 1/10
0
0
X6
1/2
0
0
1/10
1/10
-1
1
-f
-24 1/2
0
0
- 1/10
-1 1/10
0
0
-j
1/2
0
0
1/10
1/10
-1
0
X1
4
1
0
0
0
1
X2
16
0
1
0
-1
9
X3
5
0
0
1
1
-10
-f
-24
0
0
0
-1
-1
-j
0
0
0
0
0
0
Видно, что дальнейшее увеличение значения целевой функции не возможно. За два шага итераций определили оптимальное полностью целочисленное решение ПЦЗ (5) , анонсированное ранее в (7).
ИНДИВИДУАЛЬНЫЕ ЗАДАНИЯ
N
f(X)=CX
AX
£
B
2*X1+9*X2
-X1+4*X2
£
7*X1+X2
£
5*X1+3*X2
5*X1+2*X2
£
3*X1+8*X2
£
X1+3*X2
-3*X1+7*X2
£
5*X1+4*X2
£
3*X1+6*X2
-3*X1+7*X2
£
7*X1+2*X2
£
2*X1+2*X2
-X1+4*X2
£
3*X1-X2
£
X1+3*X2
3*X1+7*X2
£
2*X1+10*X2
£
Ниже в таблице4 приведены варианты индивидуальных заданий, в которых следует решить как ЗОО (графическим и симплекс методами), так и соответствующую ПЦЗ методом Гомори. Проверить полученные решения ПЦЗ и ЗОО, используя надстройку «Поиск решения» табличного процессора EXCEL, либо пакет Simplex математического процессора Maple V.
N
f(X)=CX
AX
£
B
3*X1+10*X2
-3*X1-X2
£
-9
4*X1+6*X2
£
X1+2*X2
3*X1-X2
£
-X1+X2
£
4,5
X1+X2
3*X1-X2
£
-3*X1+2*X2
£
15*X1-X2
10*X1-X2
£
-X1+X2
£
5*X1+3*X2
3*X1+2*X2
£
5*X1+X2
£
11*X1-X2
10*X1-X2
£
2*X1+X2
£
25,5
Табл.4
3*X1+X2
3*X1+2*X2
£
10*X1+X2
£
15*X1-X2
10*X1-X2
£
X1+X2
£
20,5
X1+X2
2*X1+5*X2
£
6*X1+5*X2
£
2*X1+15*X2
-X1+10*X2
£
2*X1+5*X2
£
3*X1+X2
-X1+2*X2
£
3*X1-X2
£
6*X1+X2
-X1+2*X2
£
3*X1-X2
£
X1+X2
2*X1+5*X2
£
6*X1+5*X2
£
3*X1+12*X2
-3*X1+7*X2
£
6*X1-7*X2
£
X1+3*X2
2*X1-X2
£
X1+X2
£
3,2
2*X1+6*X2
-3*X1+9*X2
£
5*X1-7*X2
£
X1+3*X2
3*X1+7*X2
£
2*X1+8*X2
£
X1+9*X2
-X1+3*X2
£
7*X1+X2
£
5*X1+2*X2
5*X1+2*X2
£
3*X1+8*X2
£
X1+5*X2
-3*X1+9*X2
£
11*X1+2*X2
£
7*X1+6*X2
-3*X1+7*X2
£
7*X1+2*X2
£
12*X1-X2
-X1+X2
£
3*X1-X2
£
2*X1+5*X2
3*X1+7*X2
£
2*X1+8*X2
£
-3*X1+5*X2
-3*X1-2*X2
£
-11
4*X1+6*X2
£
X1+2*X2
2*X1-X2
£
-1
-X1+X2
£
5,2
X1+X2
2*X1-X2
£
-0,3
-X1+X2
£
11*X1-X2
10*X1-X2
£
-X1+X2
£
3*X1+X2
3*X1+2*X2
£
5*X1+X2
£
17*X1-X2
10*X1-X2
£
2*X1+X2
£
7*X1+3*X2
2*X1+9*X2
£
10*X1-X2
£
15*X1-X2
10*X1-X2
£
X1+X2
£
2*X1+3*X2
2*X1+5*X2
£
6*X1+5*X2
£
2*X1+5*X2
-X1+10*X2
£
2*X1+5*X2
£
5*X1+X2
-X1+2*X2
£
3*X1-X2
£
2*X1+9*X2
-X1+2*X2
£
11*X1-X2
£
X1+3*X2
-2*X1+5*X2
£
11*X1+5*X2
£
Использование MS EXCEL
Для решения задач оптимизации эффективна надстройка «Поиск решения», устанавливаемая через главное меню Сервис->Надстройки и запускаемая аналогично из меню Сервис->Поиск решения.
Предварительно на рабочем листе определяем ячейки:
§ целевой функции f (для определенности – B2), куда заносим ее формулу расчета (например (4)) в терминах адресов рабочего листа;
§ для левых и правых частей ограничений (4) в форме неравенств – соответственно C2,D2 и C3,D3 как это показано на Рис.2.
Рис.2
X=[X1,X2]
F(X1,X2)=CX
AX
£B
=10*A1-A2
=A1+A2
=9*A1-A2
В окне надстройки «Поиск решения»устанавливаем ссылки:
§ на целевую ячейку B2;
§ на изменяемые ячейки A2 и A3;
§ ограничения, используя кнопку «Добавить».
В мастере настройки параметров, вызываемом кнопкой «Параметры», выбираем независимые переключатели «Линейная модель» и «Неотрицательные значения».
Оптимальное решение возвращается нажатием управляющей кнопки «Выполнить»:
Рис.3
X=[X1,X2]
F(X1,X2)=CX
AX
£B
4,00
24,00
20,00
16,00
20,00
Видно, что с помощью надстройки «Поиск решения» определино оптимальное решение полностью целочисленной задачи (4), совпадающее с найденным ранее методом Гомори.
ЛИТЕРАТУРА
1. . Банди Б. Методы оптимизации. М.: Радио и связь. 1988.
2. Пантелеев А.В., Летова Т.А. Методы оптимизации в примерах и задачах, -М.: Высш. шк., 2002.
3. Волков И.К.,Загоруйко Е.А. Исследование операций. -М: МГТУ, 2002.
4. Конюховский П.В. Математические методы исследования операций.-СПб.: «Питер», 2000.
, а второе, принимая вид 
, указывает на целесообразность построения отсечения Гомори для базисной переменной с индексом i=1.
. Вводя новую целевую функцию 
, внесем все это в новую симплекс-таблицу, использующую данные последней итерации Табл.1:
, анонсированное ранее в (7).