Метод Гомори. Пример решения

Задание. Решить целочисленную задачу линейного программирования, используя метод Гомори: F(X) = 8x1 + 5x2
5x1 + 2x2≤20
x1 + x2≤6

Решение находим с помощью калькулятора.
Этап I. Решим прямую задачу линейного программирования  симплексным методом, с использованием симплексной таблицы.
Определим максимальное значение целевой функции F(X) = 8x1 + 5x2 при следующих условиях-ограничений.
5x1 + 2x2≤20
x1 + x2≤6
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
5x1 + 2x2 + 1x3 + 0x4 = 20
1x1 + 1x2 + 0x3 + 1x4 = 6
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:


Решим систему уравнений относительно базисных переменных:
x3, x4,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,20,6)

План

Базис

B

x1

x2

x3

x4

0

x3

20

5

2

1

0


x4

6

1

1

0

1

Индексная строка

F(X0)

0

-8

-5

0

0

Переходим к основному алгоритму симплекс-метода.

План

Базис

B

x1

x2

x3

x4

min

1

x3

20

5

2

1

0

4


x4

6

1

1

0

1

6

Индексная строка

F(X1)

0

-8

-5

0

0

0

Итерация №0.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент.
Вычислим значения Di по строкам как частное от деления:
и из них выберем наименьшее:
 min (20 : 5 , 6 : 1 ) = 4

Следовательно, 1-ая строка является ведущей.

План

Базис

B

x1

x2

x3

x4

min

2

x1

4

1

2/5

1/5

0

10


x4

2

0

3/5

-1/5

1

31/3

Индексная строка

F(X2)

32

0

-14/5

13/5

0

0

Итерация №1.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент.
Вычислим значения Di по строкам как частное от деления и из них выберем наименьшее:
min (4 : 2/5 , 2 : 3/5 ) = 31/3
Следовательно, 2-ая строка является ведущей.
Конец итераций: найден оптимальный план
Окончательный вариант симплекс-таблицы:

План

Базис

B

x1

x2

x3

x4

3

x1

22/3

1

0

1/3

-2/3


x2

31/3

0

1

-1/3

12/3

Индексная строка

F(X3)

38

0

0

1

3

Оптимальный план можно записать так:
x1 = 22/3, x2 = 31/3. F(X) = 8•22/3 + 5•31/3 = 38

Этап II. В полученном оптимальном плане присутствуют дробные числа. Используем метод Гомори.
По 1-у уравнению с переменной x1, получившей нецелочисленное значение в оптимальном плане с наибольшей дробной частью 2/3, составляем дополнительное ограничение:
q1 - q11•x1 - q12•x2 - q13•x3 - q14•x4≤0
q1 = b1 - [b1] = 22/3 - 2 = 2/3
q11 = a11 - [a11] = 1 - 1 = 0
q12 = a12 - [a12] = 0 - 0 = 0
q13 = a13 - [a13] = 1/3 - 0 = 1/3
q14 = a14 - [a14] = -2/3 + 1 = 1/3
Дополнительное ограничение имеет вид:
2/3-1/3x3-1/3x4≤0
Преобразуем полученное неравенство в уравнение:
2/3-1/3x3-1/3x4 + x5 = 0
коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу.


План

Базис

B

x1

x2

x3

x4

x5

0

x1

22/3

1

0

1/3

-2/3

0


x2

31/3

0

1

-1/3

12/3

0


x5

-2/3

0

0

-1/3

-1/3

1

Индексная строка

F(X0)

38

0

0

1

3

0

План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
Среди отрицательных значений базисных переменных выбираем наибольший по модулю.
Ведущей будет 3-ая строка, а переменную x5 следует вывести из базиса.
В строку θ заносим следующие величины:
[ - ; - ;1:-1/3;3:-1/3; - ;] = [ - ; - ;-3;-9; - ;]
Минимальное значение θ соответствует 3-му столбцу, т.е. переменную x3 необходимо ввести в базис.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный -1/3.
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.
Представим расчет каждого элемента в виде таблицы:

B

x 1

x 2

x 3

x 4

x 5

22/3-(-2/31/3):-1/3

1-(0 • 1/3):-1/3

0-(0 • 1/3):-1/3

1/3-(-1/31/3):-1/3

-2/3-(-1/31/3):-1/3

0-(1 • 1/3):-1/3

31/3-(-2/3-1/3):-1/3

0-(0 • -1/3):-1/3

1-(0 • -1/3):-1/3

-1/3-(-1/3-1/3):-1/3

12/3-(-1/3-1/3):-1/3

0-(1 • -1/3):-1/3

-2/3 : -1/3

0 : -1/3

0 : -1/3

-1/3 : -1/3

-1/3 : -1/3

1 : -1/3

38-(-2/3 • 1):-1/3

0-(0 • 1):-1/3

0-(0 • 1):-1/3

1-(-1/3 • 1):-1/3

3-(-1/3 • 1):-1/3

0-(1 • 1):-1/3


План

Базис

B

x1

x2

x3

x4

x5

0

x1

2

1

0

0

-1

1


x2

4

0

1

0

2

-1


x3

2

0

0

[

1

-3

Индексная строка

F(X0)

36

0

0

[

2

3

Решение получилось целочисленным. Нет необходимости применять метод Гомори.
Оптимальный план можно записать так: x1 = 2, x2 = 4, x3 = 2
F(X) = 36

Пример №1. Найти полностью целочисленное решение следующих задач, сопровождая (где это возможно) решение графической иллюстрацией. Предполагается, что все Xk≥0.

Пример №2. Решить следующие частично целочисленные задачи, сопровождая (где это возможно) решение графической иллюстрацией. Предполагается, что все Xj≥0, XXi≥0 – целочисленное.

загрузка...