Лекция: Решение
Первый алгоритм Гомори предназначен для решения полностью целочисленных задач линейного программирования
(1)
(2), i = 0, 1, 2, …, m,
(3) xj³ 0, j = 0, 1, 2, …, n,
(4) xj‑ целые, j = 0, 1, 2, …, n.
Результат:
1 -x1 -x2
x0 0 9 -1
x1 0 -1 0
x2 0 0 -1
x3 12 -1 3
x4 30 2 5
x5 22 3 2
x6 12 2 -1
x7 0 1 -3
x8 -10 -2 -5
x9 -5 -5 -1
Разрешающий элемент (4, 2)
1 -x1 -x4
x0 6 47/5 1/5
x1 0 -1 0
x2 6 2/5 1/5
x3 -6 -11/5 -3/5
x4 0 0 -1
x5 10 11/5 -2/5
x6 18 12/5 1/5
x7 18 11/5 3/5
x8 20 0 1
x9 1 -23/5 1/5
Разрешающий элемент (3, 2)
1 -x1 -x3
x0 4 26/3 1/3
x1 0 -1 0
x2 4 -1/3 1/3
x3 0 0 -1
x4 10 11/3 -5/3
x5 14 11/3 -2/3
x6 16 5/3 1/3
x7 12 0 1
x8 10 -11/3 5/3
x9 -1 -16/3 1/3
Разрешающий элемент (9, 1)
1 -x9 -x3
x0 19/8 13/8 7/8
x1 3/16 -3/16 -1/16
x2 65/16 -1/16 5/16
x3 0 0 -1
x4 149/16 11/16 -23/16
x5 213/16 11/16 -7/16
x6 251/16 5/16 7/16
x7 12 0 1
x8 171/16 -11/16 23/16
x9 0 -1 0
Отсечение
x10 -3/8 -5/8 -7/8
Разрешающий элемент (10, 2)
1 -x9 -x10
x0 2 1 1
x1 3/14 -1/7 -1/14
x2 55/14 -2/7 5/14
x3 3/7 5/7 -8/7
x4 139/14 12/7 -23/14
x5 27/2 1 -1/2
x6 31/2 0 1/2
x7 81/7 -5/7 8/7
x8 141/14 -12/7 23/14
x9 0 -1 0
Отсечение
x11 -3/14 -6/7 -13/14
Разрешающий элемент (10, 2)
1 -x9 -x11
x0 23/13 1/13 14/13
x1 3/13 -1/13 -1/13
x2 50/13 -8/13 5/13
x3 9/13 23/13 -16/13
x4 134/13 42/13 -23/13
x5 177/13 19/13 -7/13
x6 200/13 -6/13 7/13
x7 147/13 -23/13 16/13
x8 126/13 -42/13 23/13
x9 0 -1 0
Отсечение
x12 -10/13 -1/13 -1/13
Разрешающий элемент (10, 1)
1 -x12 -x11
x0 1 1 1
x1 1 -1 0
x2 10 -8 1
x3 -17 23 -3
x4 -22 42 -5
x5 -1 19 -2
x6 20 -6 1
x7 29 -23 3
x8 42 -42 5
x9 10 -13 1
Разрешающий элемент (3, 2)
1 -x12 -x3
x0 -14/3 26/3 1/3
x1 1 -1 0
x2 13/3 -1/3 1/3
x3 0 0 -1
x4 19/3 11/3 -5/3
x5 31/3 11/3 -2/3
x6 43/3 5/3 1/3
x7 12 0 1
x8 41/3 -11/3 5/3
x9 13/3 -16/3 1/3
Отсечение
x13 -1/3 -2/3 -1/3
Разрешающий элемент (10, 2)
1 -x12 -x13
x0 -5 8 1
x1 1 -1 0
x2 4 -1 1
x3 1 2 -3
x4 8 7 -5
x5 11 5 -2
x6 14 1 1
x7 11 -2 3
x8 12 -7 5
x9 4 -6 1
Ответ
целевая функция = -5
(1,4)
Отсечения:
Второй алгоритм Гомори имеет дело с более широким классом задач. Рассматривается частично целочисленная задача программирования.
Пусть Х1 – нецелочисленна:
1 -x1 -x2
x0 0 9 -1
x1 0 -1 0
x2 0 0 -1
x3 12 -1 3
x4 30 2 5
x5 22 3 2
x6 12 2 -1
x7 0 1 -3
x8 -10 -2 -5
x9 -5 -5 -1
Разрешающий элемент (4, 2)
1 -x1 -x4
x0 6 47/5 1/5
x1 0 -1 0
x2 6 2/5 1/5
x3 -6 -11/5 -3/5
x4 0 0 -1
x5 10 11/5 -2/5
x6 18 12/5 1/5
x7 18 11/5 3/5
x8 20 0 1
x9 1 -23/5 1/5
Разрешающий элемент (3, 2)
1 -x1 -x3
x0 4 26/3 1/3
x1 0 -1 0
x2 4 -1/3 1/3
x3 0 0 -1
x4 10 11/3 -5/3
x5 14 11/3 -2/3
x6 16 5/3 1/3
x7 12 0 1
x8 10 -11/3 5/3
x9 -1 -16/3 1/3
Разрешающий элемент (9, 1)
1 -x9 -x3
x0 19/8 13/8 7/8
x1 3/16 -3/16 -1/16
x2 65/16 -1/16 5/16
x3 0 0 -1
x4 149/16 11/16 -23/16
x5 213/16 11/16 -7/16
x6 251/16 5/16 7/16
x7 12 0 1
x8 171/16 -11/16 23/16
x9 0 -1 0
Отсечение
x10 -1/16 -1/240 -5/16
Разрешающий элемент (10, 2)
1 -x9 -x10
x0 11/5 121/75 14/5
x1 1/5 -14/75 -1/5
x2 4 -1/15 1
x3 1/5 1/75 -16/5
x4 48/5 53/75 -23/5
x5 67/5 52/75 -7/5
x6 78/5 23/75 7/5
x7 59/5 -1/75 16/5
x8 52/5 -53/75 23/5
x9 0 -1 0
Ответ
целевая функция = 11/5
(1/5,4)
Отсечения:
Пусть Х2 – нецелочисленна:
1 -x1 -x2
x0 0 9 -1
x1 0 -1 0
x2 0 0 -1
x3 12 -1 3
x4 30 2 5
x5 22 3 2
x6 12 2 -1
x7 0 1 -3
x8 -10 -2 -5
x9 -5 -5 -1
Разрешающий элемент (4, 2)
1 -x1 -x4
x0 6 47/5 1/5
x1 0 -1 0
x2 6 2/5 1/5
x3 -6 -11/5 -3/5
x4 0 0 -1
x5 10 11/5 -2/5
x6 18 12/5 1/5
x7 18 11/5 3/5
x8 20 0 1
x9 1 -23/5 1/5
Разрешающий элемент (3, 2)
1 -x1 -x3
x0 4 26/3 1/3
x1 0 -1 0
x2 4 -1/3 1/3
x3 0 0 -1
x4 10 11/3 -5/3
x5 14 11/3 -2/3
x6 16 5/3 1/3
x7 12 0 1
x8 10 -11/3 5/3
x9 -1 -16/3 1/3
Разрешающий элемент (9, 1)
1 -x9 -x3
x0 19/8 13/8 7/8
x1 3/16 -3/16 -1/16
x2 65/16 -1/16 5/16
x3 0 0 -1
x4 149/16 11/16 -23/16
x5 213/16 11/16 -7/16
x6 251/16 5/16 7/16
x7 12 0 1
x8 171/16 -11/16 23/16
x9 0 -1 0
Отсечение
x10 -3/16 -9/208 -3/208
Разрешающий элемент (10, 1)
1 -x10 -x3
x0 -14/3 338/9 1/3
x1 1 -13/3 0
x2 13/3 -13/9 1/3
x3 0 0 -1
x4 19/3 143/9 -5/3
x5 31/3 143/9 -2/3
x6 43/3 65/9 1/3
x7 12 0 1
x8 41/3 -143/9 5/3
x9 13/3 -208/9 1/3
Ответ
целевая функция = -14/3
(1,13/3)
Отсечения:
Третий алгоритм Гомори предназначен для решения полностью целочисленной задачи линейного программирования.
;
;
; целые.
1 -x1 -x2
x0 0 9 -1
x1 0 -1 0
x2 0 0 -1
x3 12 -1 3
x4 30 2 5
x5 22 3 2
x6 12 2 -1
x7 0 1 -3
x8 -10 -2 -5
x9 -5 -5 -1
Вспомогательная переменная
x10 9 1 1
Разрешающий элемент (10, 2)
1 -x1 -x10
x0 9 10 1
x1 0 -1 0
x2 9 1 1
x3 -15 -4 -3
x4 -15 -3 -5
x5 4 1 -2
x6 21 3 1
x7 27 4 3
x8 35 3 5
x9 4 -4 1
Отсечение
x10 -4 -1 -1
lambda = 4
Разрешающий элемент (10, 2)
1 -x1 -x10
x0 5 9 1
x1 0 -1 0
x2 5 0 1
x3 -3 -1 -3
x4 5 2 -5
x5 12 3 -2
x6 17 2 1
x7 15 1 3
x8 15 -2 5
x9 0 -5 1
Отсечение
x11 -1 -1 -1
lambda = 3
Разрешающий элемент (10, 2)
1 -x1 -x11
x0 4 8 1
x1 0 -1 0
x2 4 -1 1
x3 0 2 -3
x4 10 7 -5
x5 14 5 -2
x6 16 1 1
x7 12 -2 3
x8 10 -7 5
x9 -1 -6 1
Отсечение
x12 -1 -1 0
lambda = 6
Разрешающий элемент (10, 1)
1 -x12 -x11
x0 -4 8 1
x1 1 -1 0
x2 5 -1 1
x3 -2 2 -3
x4 3 7 -5
x5 9 5 -2
x6 15 1 1
x7 14 -2 3
x8 17 -7 5
x9 5 -6 1
Отсечение
x13 -1 0 -1
lambda = 3
Разрешающий элемент (10, 2)
1 -x12 -x13
x0 -5 8 1
x1 1 -1 0
x2 4 -1 1
x3 1 2 -3
x4 8 7 -5
x5 11 5 -2
x6 14 1 1
x7 11 -2 3
x8 12 -7 5
x9 4 -6 1
Ответ
целевая функция = -5
(1,4)
Отсечения:
4. Выводы:
Первый и третий алгоритмы Гомори предназначены для решения полностью целочисленных задач линейного программирования. Второй алгоритм Гомори имеет дело с более широким классом задач, рассматривая частично целочисленные задачи линейного программирования. Реализация на ЭВМ 1-го и 2-го алгоритмов Гомори может привести к неправильному результату из-за ошибок округления или ошибок при подсчёте дробных частей. Третий алгоритм Гомори свободен от влияния ошибок округления.