Задача 2.49.
Методом Гомори найти максимальное значение функции
при условиях
Дать геометрическую интерпретацию решения задачи. Решение. Для определения оптимального плана задачи (40) — (43) сначала находим оптимальный план задачи (40) — (42) (табл. 2.28).
Как видно из табл. 2.28, найденный оптимальный план 
= (19/2; 7/2; 0; 0; 10) задачи (40) —(42) не является оптимальным планом задачи (40) —(43). поскольку две компоненты 
и 
имеют нецелочисленные значения. При этом дробные части этих чисел равны между собой. Поэтому для одной из этих переменных составляется дополнительное ограничение. Составим, например, такое ограничение для переменной . Из последней симплекс-таблицы (табл. 2.28) имеем
Таким образом, к системе ограничений задачи (40)—(42) добавляем неравенство
Находим теперь максимальное значение функции (40) при выполнении условий (41), (42) и (44) (табл. 2.29).
Из табл. 2.29 видно, что исходная задача целочисленного программирования имеет оптимальный план
При этом плане значение целевой функции равно 
. Дадим геометрическую интерпретацию решения задачи. Областью допустимых решений задачи (40) — (42) является многоугольник 
(рис. 2.3). Из рис. 2.3 видно, что максимальное значение целевая функция принимает в точке 
(19/2; 7/2), т. е. что = (19/2; 7/2; 0; 0; 34) является оптимальным планом. Это непосредственно видно и из табл. 2.28. Так как = (19/2; 7/2; 0; 0; 34)
не является оптимальным планом задачи (40) — (43) (числа 19/2 и 7/2 — дробные), то вводится дополнительное ограничение 
Исключая из него 
и 
подстановкой вместо них соответствующих значений из уравнений системы ограничений (41), получим 
. Этому неравенству соответствует полуплоскость, ограниченная прямой 
, отсекающей от многоугольника 
треугольник 
.
Как видно из рис. 2.3, областью допустимых решений полученной задачи является многоугольник 
. В точке 
(9; 4) этого многоугольника целевая функция данной задачи принимает максимальное значение. Так как координаты точки — целые числа и неизвестные 
принимают целочисленные значения при подстановке в уравнения (41) значений 
является оптимальным планом задачи (40) —(43). Это следует и из табл. 2.29.
Эта задача взята со страницы решения задач по предмету «математическое программирование»:
Примеры решения задач по математическому программированию
Возможно эти страницы вам будут полезны:
