Методом Гомори найти решение следующей задачи
тin f = -4х1 - 3х2
2х1 + 3х2 + х3 = 8,
4х1 + х2 + х4 = 10,
х1, х2, х3, х4 - целые.
х1, х2, х3, х4 0
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим минимальное значение целевой функции F(X) = - 4x1 - 3x2 при следующих условиях-ограничений.
2x1 + 3x2 + x3=8
4x1 + x2 + x4=10
Поскольку уже имеется единичная матрица (последние столбцы размерности 2 x 2), то нет необходимости вводить дополнительный базис.
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
Решим систему уравнений относительно базисных переменных:
x3, x4,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,8,10)
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
|
x3 |
8 |
2 |
3 |
1 |
0 |
|
x4 |
10 |
4 |
1 |
0 |
1 |
|
F(X0) |
0 |
4 |
3 |
0 |
0 |
Переходим к основному алгоритму симплекс-метода.
Итерация №0.
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент .
Вычислим значения Di по строкам как частное от деления: bi / ai1
и из них выберем наименьшее:
min (8 : 2 , 10 : 4 ) = 21/2
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (4) и находится на пересечении ведущего столбца и ведущей строки.
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
min |
|
x3 |
8 |
2 |
3 |
1 |
0 |
4 |
|
x4 |
10 |
4 |
1 |
0 |
1 |
21/2 |
|
F(X1) |
0 |
4 |
3 |
0 |
0 |
0 |
Получаем новую симплекс-таблицу:
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
|
x3 |
3 |
0 |
21/2 |
1 |
-1/2 |
|
x1 |
21/2 |
1 |
1/4 |
0 |
1/4 |
|
F(X1) |
-10 |
0 |
2 |
0 |
-1 |
Итерация №1.
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент .
Вычислим значения Di по строкам как частное от деления: bi / ai2
и из них выберем наименьшее:
min (3 : 21/2 , 21/2 : 1/4 ) = 11/5
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (21/2) и находится на пересечении ведущего столбца и ведущей строки.
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
min |
|
x3 |
3 |
0 |
21/2 |
1 |
-1/2 |
11/5 |
|
x1 |
21/2 |
1 |
1/4 |
0 |
1/4 |
10 |
|
F(X2) |
-10 |
0 |
2 |
0 |
-1 |
0 |
Получаем новую симплекс-таблицу:
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
|
x2 |
11/5 |
0 |
1 |
2/5 |
-1/5 |
|
x1 |
21/5 |
1 |
0 |
-1/10 |
3/10 |
|
F(X2) |
-122/5 |
0 |
0 |
-4/5 |
-3/5 |
Конец итераций: индексная строка не содержит положительных элементов - найден оптимальный план
Окончательный вариант симплекс-таблицы:
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
|
x2 |
11/5 |
0 |
1 |
2/5 |
-1/5 |
|
x1 |
21/5 |
1 |
0 |
-1/10 |
3/10 |
|
F(X3) |
-122/5 |
0 |
0 |
-4/5 |
-3/5 |
Оптимальный план можно записать так:
x2 = 11/5
x1 = 21/5
F(X) = -3•11/5 + -4•21/5 = -122/5
Метод Гомори.
Нетрудно заметить, что получено оптимальное решение ослабленной задачи: Х=(19/2, 7/2, 0, 0, 34), в котором две дробные переменные, имеющие одинаковые дробные части. Поэтому дополнительное ограничение можно составлять для любой из этих переменных. Составим дополнительное ограничение для х 2. Для этого выпишем ограничение из последней таблицы для выбранной переменной
х 2 + 0,4 х 3 - 0,2 х 4 = 1,2.
Перейдем в этом ограничении к дробным частям коэффициентов и свободного члена. Очевидно, что будет справедливо неравенство:
0,4 х 3 + 0,8 х 4 1,2.
Преобразуем данное неравенство таким образом, чтобы все коэффициенты и свободный член были в нем целыми.
2х 3 + 4х 4 6.
Перейдем к ограничению-равенству, введя дополнительную переменную
2х 3 + 4х 4 - и1 = 1