−x2 −6x3 + x4 = −5, 63. z = −x2 −3x3 → max при x ≥ 0 и x1 +5x2 −19x3 = −13,

3x2 −6x3 + x5 = −2.

4.3. Метод Гомори

Решение задачи целочисленного программирования методом Гомори начинают с определения симплексным методом оптимального плана исходной задачи без учета целочисленности переменных. Если среди его компонент нет дробных чисел, то найденный план является оптимальным планом задачи целочисленного программирования. Если же в оптимальном плане задачи переменная xk , по условию цело-

численная, принимает дробное значение, то к системе ограничений добавляют неравенство

последней симплекс таблицы из строки, содержащей переменную xk

как базисную. Если же дробные значения принимают несколько переменных, то дополнительное неравенство определяется числом с наибольшей дробной частью. Затем, используя двойственный симплексметод, находят решение исходной задачи.

Замечание 4.1. Под дробной частью некоторого числа a понимается наименьшее неотрицательное число такое, что разность a

и b есть целое. Например, {1,75} = 0,75; {−3,35} = 0,65.

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

Решим теперь задачу из примера 4.1 методом Гомори. Пример 4.3. Решить методом Гомори задачу

z = 4x1 +8x2 + 4 → max

−x1 + x2 ≤ 4,x1 + x2 ≤ 7,

x1 ≥ 0, x2 ≥ 0; x1, x2 Z.

Решение. Приведем задачу к каноническому виду

60

z = 4x1 +8x2 +4 → max

−x1 + x2 + x3 = 4,

x1 + x2 + x4 = 7,

x1 ≥ 0, x2 ≥ 0; x1, x2 Z.

и решим задачу симплекс-методом (игнорируя условие целочисленности). Выпишем исходную симплекс-таблицу.

В последней строке есть два отрицательных числа, поэтому опорное решение X = (0,0,4,7) не является оптимальным. Вводим в

базис переменную x2 , и, в соответствие с правилами симплексметода, выводим из базиса x3

Теперь разрешающий элемент выбирается однозначно. Разделив вторую строчку на 2, сделаем еще один шаг симплекс-метода.

задачи без учета условия целочисленности, но так как обе компоненты x1 и x2 являются дробными, то X не является оптимальным реше-

нием задачи целочисленного программирования. Далее, так как дробные части равны между собой, то дополнительное ограничение составляется для одной из них (например, для переменной x2 ). Выписы-

вая соответствующую строку (первую) из последней симплекс таблицы, получаем

61

Поскольку в свободном столбце имеется отрицательный элемент, то для решения задачи применяем двойственный симплексметод. Чтобы определить разрешающий столбец, находим

менной x3 . Умножаем третью строку на −1, и делаем шаг симплексметода

Получаем заключительную симплекс-таблицу, из которой, опуская балансовые переменные x3 , x4 , x5 , заключаем, что исходная задача

целочисленного программирования имеет оптимальный план X * = (5,2) . При этом значение целевой функции равно zmax = 52 .

Дадим теперь геометрическую интерпретацию введения дополнительного ограничения x3 + x4 ≥1. Допустимая область при отсутст-

вии условия целочисленности построена выше в примере 4.1. Теперь из условий задачи

62

63

z = 2x1 +4x2 → max

2x1 + x2 + x3 =19 /3,

x1 +3x2 + x4 =10,

xj ≥ 0, j =1, ,4; x1, x2 Z.

и составим для нее симплекс-таблицу

Введем в базис x2 и, соответственно, выведем из базиса переменную x4 . Найдем решение задачи без учета условия целочисленности

Включим в последнюю симплекс-таблицу дополнительное ограничение

64

zmax = z(X * ) =14.

Итак, необходимо приобрести 1 комплект первого типа и 3 комплекта второго типа. При этом суточная прибыль составит 14 у.е.

Задачи для самостоятельного решения.

Задачи 64-66 целочисленного программирования а) решить графическим методом; б) решить методом Гомори;

в) дать геометрическую интерпретацию введения дополнительного ограничения.

65

x1 + x2 ≤ 4, 66. z = x1 + x2 −6 → max при x1, x2 ≥ 0, x1, x2 Z и x1 +3x2 ≤ 9,

−3x1 + x2 ≤ 0.

67.Для увеличения прибыли компания приняла решение о приобретении нового оборудования, выделив на это 34 у.е. и предоставив площадь 60 кв. м. При этом оборудование может быть заказано двух типов. Приобретение оборудования первого типа обойдется в 3 у.е. за 1 комплект, занимающий площадь 3 кв.м. Один комплект второго т и- па занимает 5 кв. м. и обойдется в 4 у.е. При этом использование комплекта 1-го типа обеспечивает прибыль 2 у.е. в сутки, а второго – 3 у.е. в сутки. Составить оптимальный план приобретения оборудования, обеспечивающий максимальную прибыль компании, если она может приобрести не более 8 комплектов второго типа.

68.На складе имеются бревна длиной 3 м. Часть из них требуется распилить на заготовки двух видов: длиной 1,2 м и длиной 0,8 м. Заготовок первого типа нужно получить не менее 50 шт, а 2 -го типа – не менее 81 шт. Найти наименьшее число бревен, требуемое для получения необходимого числа заготовок каждого типа.

66