Пример 21.

Для выполнения работ могут быть использованы п механизмов. Производительность i–го механизма  при выполнении j–й работы  равна  . Предполагая, что каждый механизм может быть использован только на одной работе и каждая работа может выполняться только одним механизмом, определить закрепление механизмов за работами, обеспечивающее максимальную производительность. Построить математическую модель задачи.

Решение. Введем переменную x_ij, значение которой равно 1, если при выполнении i–й работы используется j–й механизм, и равно 0 в противном случае. Тогда условия использования каждого механизма только на одной работе выражаются равенствами

(74)

а условия выполнения работы только одним механизмом – равенствами

(75)

(76)

Таким образом, задача состоит в определении таких значений неизвестных  , удовлетворяющих системам уравнений (74) и (75) и условию (76), при которых достигается максимальное значение функции

(77)

Сформулированная задача является задачей целочисленного программирования.

Определение оптимального плана задачи целочисленного программирования. Рассмотрим задачи целочисленного программирования, в которых как целевая функция, так и функции в системе ограничений являются линейными. В связи с этим сформулируем основную задачу линейного программирования, в которой переменные могут принимать только целые значения. В общем виде эту задачу можно записать так: найти максимум функции

(78)

при условиях

(79)

(80)

– целые  (81)

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

Метод Гомори. Нахождение решения задачи целочисленного программирования методом Гомори начинают с определения симплексным методом оптимального плана задачи (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

i	Базис	Сб	Р0	3	2	0	0	0
				P1	P2	P3	p4	p5
1 2 3 4 1 2 3 4 1 2 3 4	p3 P4 p5 p3 P1 p5 p2 P1 p5	0 0 0 0 3 0 2 3 0	13 6 9 0 7 6 27 18 7/2 19/2 34 71/2	1 1 3 –3 0 1 0 0 0 1 0 0	1 –1 1 –2 2 –1 –2 –5 1 0 0 0	1 0 0 0 1 0 0 0 1/2 1/2 1 5/2	0 1 0 0 –1 1 3 3 –1/2 1/2 2 1/2	0 0 1 0 0 0 1 0 0 0 1 0

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

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

или

т.е.

(90)

Таблица 23

i	Базис	Сб	Р0	3	2	0	0	0	0
				P1	P2	P3	p4	p5	P6
1 2 3 4 5 1 2 3 4 5	p2 P1 p5 p6 p2 P1 p5 p4	2 3 0 0 2 3 0 0	7/2 19/2 34 –1 71/2 4 9 32 1 35	0 1 0 0 0 0 1 0 0 0	1 0 0 0 0 1 0 0 0 0	1/2 1/2 1 –1 5/2 1 0 –1 1 2	–1/2 1/2 2 –1 1/2 0 0 0 1 0	0 0 1 0 0 0 0 1 0 0	0 0 0 1 0 –1/2 1/2 2 –1 1/2

Находим теперь максимальное значение функции (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

i	Базис	Сб	Р0	1	4	0	0
				P1	P2	P3	p4
1 2 3 1 2 3	p3 P4 p3 P2	0 0 0 4	19/3 4 0 5 4/3 16/3	2 1 –1 5/3 1/3 1/3	1 3 –4 0 1 0	1 0 0 1 0 0	0 1 0 –1/3 1/3 4/3

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

(99)

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

Таблица 25

i	Базис	Сб	Р0	1	4	0	0	0
				P1	P2	P3	p4	p5
1 2 3 4 1 2 3 4	p3 P2 p5 p3 P2 p1	0 4 0 0 4 1	5 4/3 –1 16/3 10/3 1 1 5	5/3 1/3 –1 1/3 0 0 1 0	1 1 0 0 0 1 0 0	1 0 0 0 1 0 0 0	–1/3 1/3 –1 4/3 –2 0 1 1	0 0 1 0 5/3 1/3 –1 1/3

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

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