Линейное программирование

      Метод Гомори. Нахождение решения задачи целочисленного программирования методом Гомори начинают с определения симплексным методом оптимального плана задачи (78) – (80) без учета целочисленности переменных. После того как этот план найден, просматривают его компоненты. Если среди компонент нет дробных чисел, то найденный план является оптимальным планом задачи целочисленного программирования (78) – (81). Если же в оптимальном плане задачи (78) – (80) переменная принимает дробное значение, то к системе уравнений (79) добавляют неравенство

(82)

и находят решение задачи (78) – (80), (82).

      В неравенстве (82) и – преобразованные исходные величины и значения которых взяты из последней симплекс–таблицы, а и – дробные части чисел (под дробной частью некоторого числа а понимается наименьшее неотрицательное число b такое, что разность между а и b есть целое). Если в оптимальном плане задачи (78) – (80) дробные значения принимают несколько переменных, то дополнительное неравенство (82) определяется наибольшей дробной частью.

      Если  в найденном плане задачи (78) – (80), (82) переменные принимают дробные  значения, то снова добавляют одно дополнительное ограничение и процесс  вычислений повторяют. Проводя конечное число итераций, либо получают оптимальный  план задачи целочисленного программирования (78) – (81), либо устанавливают ее неразрешимость.

      Если  требование целочисленности (81) относится лишь к некоторым переменным, то такие задачи называются частично целочисленными. Их решение также находят последовательным решением задач, каждая из которых получается из предыдущей с помощью введения дополнительного ограничения. В этом случае такое ограничение имеет вид

(83)

где определяются из следующих соотношений:

1) для , которые могут принимать нецелочисленные значения,

(84)

2) для , которые могут принимать только целочисленные значения,

(85)

      Из  изложенного выше следует, что процесс  определения оптимального плана  задачи целочисленного программирования методом Гомори включает следующие  основные этапы:

1. Используя симплексный метод,  находят решение задачи (78) – (80) без учета требования целочисленности переменных.

2. Составляют дополнительное ограничение  для переменной, которая в оптимальном  плане задачи (78) – (80) имеет максимальное дробное значение, а в оптимальном плане задачи (78) – (81) должна быть целочисленной.

3. Используя двойственный симплекс–метод, находят решение задачи, получающейся из задачи (78) – (80) в результате присоединения дополнительного ограничения.

4. В случае необходимости составляют  еще одно дополнительное ограничение  и продолжают итерационный процесс  до получения оптимального плана  задачи (78) – (81) или установления  ее неразрешимости.

      Пример 22.

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

(86)

при условии

(87)

(88)

– целые  (89)

Дать  геометрическую интерпретацию решения  задачи.

      Решение. Для определения оптимального плана задачи (86) – (89) сначала находим оптимальный план задачи (86) – (88) (табл. 22).

      Таблица 22

      Как видно из табл. 22, найденный оптимальный план задачи (86) – (88) не является оптимальным планом задачи (86) – (89), поскольку две компоненты и имеют нецелочисленные значения. При этом дробные части этих чисел равны между собой. Поэтому для одной из этих переменных составляется дополнительное ограничение. Составим, например, такое ограничение для переменной . Из последней симплекс–таблицы (табл. 22) имеем

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

или

т.е.

(90)

      Таблица 23

      Находим теперь максимальное значение функции (86) при выполнении условий (87), (88) и (90) (табл. 23).

      Из  таблицы 23 видно, что исходная задача целочисленного программирования имеет  оптимальный план При этом плане значение целевой функции равно . Дадим геометрическую интерпретацию решения задачи. Областью допустимых решений задачи (86) – (88) является многоугольник OABCD (рис. 12). Из рис. 12 видно, что максимальное значение целевая функция принимает в точке С (19/2; 7/2), т. e. что Х = (19/2; 7/2; 0; 0; 34) является оптимальным планом. Это непосредственно видно и из таблицы 22. Так как Х = (19/2; 7/2; 0; 0; 34) не является оптимальным планом задачи (86) – (89) (числа и – дробные), то вводится дополнительное ограничение . Исключая из него и подстановкой вместо них соответствующих значений из уравнений системы ограничений (87), получим отсекающий от многоугольника OABCD треугольник EFC.

      Как видно из рис. 12, областью допустимых решений полученной задачи является многоугольник OABEFD. В точке Е(9; 4) этого многоугольника целевая функция данной задачи принимает максимальное значение. Так как координаты точки Е – целые числа и неизвестные , и принимают целочисленные значения при подстановке в уравнение (87) значений и , то является оптимальным планом задачи (86) – (89). Это следует и из таблицы 23.

      Пример 23.

      Методом Гомори найти решение задачи, состоящей  в определении максимального  значения функции

(91)

при условиях

(92)

(93)

– целые. (94)

Дать  геометрическую интерпретацию решения  задачи.

      Решение. Сформулированную задачу перепишем так: найти максимальное значение функции

(95)

при условиях

(96)

(97)

– целые. (98)

Задача (95) – (98) является частично целочисленной, так как переменные и могут принимать нецелочисленные значения.

Находим симплексным методом решение  задаяи (95) – (97) (таблица 24).

      Таблица 24

      После II итерации получаем оптимальный план данной задачи При этом плане переменная приняла нецелочисленное значение. Поэтому необходимо перейти к новой задаче, добавив к системе ограничений (95) – (97) еще одно ограничение или

(99)

      Находим теперь решение задачи, состоящей  в определении максимального  значения функции (95) при условиях (96), (97) и (99). Данную задачу решаем двойственным симплекс–методом (таблица 25).

      Таблица 25

      Из  таблицы 25 видно, что  является оптимальным планом построенной задачи. Так как при этом плане переменные и принимают целые значения, то он также является оптимальным планом исходной задачи (95) – (98).

      Дадим геометрическую интерпретацию решения  задачи. На рис. 13 показана область допустимых решений задачи (95) – (97). Из рисунка  видно, что максимальное значение целевая  функция принимает в точке  , т.е. что является оптимальным планом задачи (95) – (97). В то же время не является планом задачи (95) – (98), так как переменная принимает дробное значение. Поэтому вводим дополнительное ограничение откуда, подставляя вместо его значение из второго уравнения системы уравнений (96), получаем . Этому неравенству на рис. 13 соответствует полуплоскость, ограниченная прямой , отсекающей от многоугольника ОАВС треугольник ADE. В области ODEBC находим точку Е(1; 1), в которой функция (95) принимает максимальное значение. Так как координаты точки Е – целые числа, то является оптимальным планом задачи (95) – (97). Это видно и из таблицы 25.