Рассмотрим пример.

Методом Гоморинайти максимальное значение функ­ции

F = 3x1 + 2x2 (4)

при условиях

x1+x2+x3=13,

x1-x2+x4=6, (5)

-3x1+x2+x5=9,

 

xj ≥0 (j=1, 5), (6)

xj – целые (j=1, 2).

Решение. Для определения оптимального плана сначала решим задачу без учета целочисленности переменных. Как видно из табл. 3, найденный оптимальный план Х = (19/2; 7/2; 0; 0; 34) задачи не удовлетворяет условию целочисленности задачи, поскольку две компоненты х1 и х2 имеют нецелочисленные значения. При этом дробные части этих чисел равны между собой. Поэтому для одной из этих пере­менных составляется дополнительное ограничение. Составим, например, такое ограничение для переменной х2. Из симплекс-таблицы (табл. 3) имеем

X2+ (1/2) x3 – (1/2) x4= 7/2

 

Таким образом, к системе ограничений задачи (5) – (6) добавляем неравенство

 

f (1) x2 + f (1/2) x3 -f (-1/2) x4 ≥ f (7/2) , или (1/2) x3 + (1/2) x4 ≥ 1/2 ,

т.е.

x3+x4≥1.

Таблица 3

i Базис Сб P0
P1 P2 P3 P4 P5
P3
P4 -1
P5 -3
    -3 -2
P3 -1
P1 -1
P5 -2
    -5
P2 7/2 1/2 -1/2
P1 19/2 1/2 1/2
P5
    71/2 5/2 1/2

 

Продолжим решение задачи двойственным симплекс-методом (Таблица 4)

Из табл. 4 видно, что исходная задача целочисленного программирования имеет оптимальный план X* = (9; 4; 0; 1; 32). При этом плане значение целевой функции равно Fmax, = 35.

Таблица 4

i Базис Сб P0
P1 P2 P3 P4 P5 P6
P2 7/2 1/2 -1/2
P1 19/2 1/2 1/2
P5
P6 -1 -1 -1
    71/2 5/2 1/2
P2 -1/2
P1 1/2
P5 -1
P4 -1
    1/2

Контрольные вопросы и упражнения

  1. В чем сущность метода Гомори?
  2. Каким образом строится сечение Гомори?
  3. Сколько сечений Гомори можно построить?
  4. Перечислить этапы алгоритма метода Гомори.
  5. Используя алгоритмы метода Гомори, двойственного симплексного метода решить следующие задачи целочисленного программирования:

 

а) z = 3x1 + 3x2→max

x1+3x2 ≥ 6

3x1+2x2 ≥ 36

x2 ≤ 13

x1, x2 ≥ 0 (целые)

 

б) z = x1 + x2→max

3x1+2x2 ≤ 5

x2 ≤ 2

x1, x2 ≥ 0 (целые)

в) z = x1 →max

x1+3x2+x3 = 12

3x1 – 8x2 +x4 = 24

x1, x2 ≥ 0 (целые)