Решение задачи методом Гомори

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

            (1.1)

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

Пример.Найти наибольшее значение функции

при ограничениях:

Метод ветвей и границ

Задача линейного программирования решается без уче­та целочисленности. Такая задача называется непрерыв­ной. Далее рассматривают одну из переменных x_j, на кото­рую накладывают ограничение целочисленности, но кото­рая получила дробное значение. На основе полученного решения составляют дополнительные ограничения:

x_j ≤ [ ]и x_j ≥ [ ] + 1,

где [ ] — целая часть нецелочисленного значения перемен­ной  в оптимальном решении, и затем решаются еще две задачи линейного программирования, в каждую из которых вошли все исходные ограничения и одно из дополнительных.

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

Если одно из решений удовлетворяет требованию целочисленности, значение целевой функции принимается за граничное L_гр. При этом рассмотрение других задач про­должается до тех нор, пока не будет получено:

■ на одной из ветвей недопустимое решение;

■ на одной из ветвей целочисленное решение. Тогда зна­чение целевой функции сравнивается с L_гр (верхним - при max, нижним - при min); если полученное значе­ние хуже, оно отбрасывается; если лучше, то принимается за граничное;

■ на одной из ветвей нецелочнеленное решение, однако при этом значение целевой функции хуже граничного. Тогда дальнейшее рассмотрение также прекращается. На первом цикле расчета

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

Пример 1.

max L = 7x₁ + 3x₂,

Решение. В результате решения задачи симплекс-ме­тодом найдем оптимальное решение = 1;  = 7,5; L₁ = 29,5, где верхний индекс переменных — номер задачи.

В полученном решении x₂ = 7,5 — нецелочисленное. Поэтому для дальнейшего решения составляем две новые задачи с различными граничными условиями.

Задача 2.                                                 Задача 3.

max L = 7x₁ + 3x₂,                                                              max L = 7x₁ + 3x₂,

Результаты решения симплекс методом задачи 2: = 1,2;  = 7; L₂ = 29,4; задачи 3: = 0,75;  = 8; L₃ = 29,25;

В задаче 1 переменная  = 1 — целочисленная, а в последующих задачах при целочисленности х₂ перестала быть целочисленной x₁. Затем следует накладывать огра­ничения целочисленности на x₁ и т. д. (рис. 2).

Результаты решения непрерывной и целочисленной за­дачи вводятся в таблице 1. В качестве оптимального принимается решение задачи 5, которое дает наибольшее из целочисленных решений значение целевой функции.

Задача 4 ;

Задача 5 ;

Задача 6 ;

Задача 2 ;

Задача 3 ;

Задача 1 ;

Таблица 1.

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

Обязательное условие метода — наличие верхних гра­ниц на значения переменных D_j. Если D_j не назначена, то ее определяют по зависимости:

Где  минимальные значения всех , для которых определяется верхняя граница .

Задача выбора вариантов

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

В этом частном случае искомая переменная , в резуль­тате решения может принимать не любое целое значение, а только одно из двух: либо 0, либо 1. Чтобы такие перемен­ные отличать от обычных и каждый раз не писать [0; 1], будем их вместо , обозначать . И это уже будет означать, что в результате решения задачи  может быть равным или 0 или 1, т. е. всегда Такие переменные обычно называют булевыми (в честь предложившего их англий­ского математика Джорджа Буля, 1815-1864).

С помощью булевых переменных можно решать самые различные по содержанию задачи, в которых надо что-то выбирать из имеющихся различных вариантов (например, еще в первобытнообщинном строе глава племени наверня­ка решал такую задачу, выбирая, какого члена общины на какую работу поставить), в том числе: задачи о назначе­нии, выбора вариантов, дискретного программирования.

Пример 2. В задаче выбора вариантов примем, что для получения результата в виде максимально возможной при­были необходимы два видя ресурсов: материальные и тру­довые. Возможны четыре варианта расхода ресурсов и по­лучения прибыли (табл. 2).

Требуется выбрать, какие варианты принять для реа­лизации при условии, чтобы общее число принятых вариантов не превышало трех (k  3).

Решение. Для составления модели примем, что j-му варианту будет соответствовать (j – 1, …, 4). При этом

Тогда математическая модель задачи запишется:

max L = 65  + 80  +  + 210 ,

Последняя строка системы обеспечивает выполнение условия, чтобы общее число принятых вариантов не пре­вышало трех.

Из результатов решения этой задачи (первый столбец табл. 3) видна, что наибольшая прибыль (max L = 300) будет получена в том случае, если будут приняты третий и четвертый варианты.

Таблица 3.
Оптимальное решение	Дополнительные условия
	нет	=	+  = 1
	0	0	1
	0	1	1
	0	0	1
	1	1	0
Прибыль (max L)	300	290	235

С помощью булевых переменных можно накладывать дополнительные логические связи между вариантами. На­пример, требуется, чтобы четвертый вариант был принят только в том случае, если принят второй; а если же второй вариант не принят, то и четвертый не должен быть принят. Это условие можно записать так:  =  или в форме запи­си ограничений  -  = 0 (результат решения этой задачи во втором столбце табл. 15).

Может быть сформулирован и другой вариант допол­нительных условий. Например, требуется, чтобы был при­нят либо третий вариант, либо четвертый, т. е.  (результат решения в третьем столбце).

Сравнивая значение прибыли в оптимальном решении (max L = 300) с прибылью при выполнении дополнитель­ных условий, можно сделать вывод, что они, как всегда, приводят к снижению прибыли.

Переходя от примера с дополнительными условиями к общему случаю, задачу выбора вариантов можно записать так:

Max L =

где последнее ограничение может учитывать самые разно­образные условия.

Если накладывается требование «должен», то в  ограничении ставится знак равенства:  (число принятых вариантов «должно быть» три).

Если требование «может», то — знак неравенства, в частности:

■ если накладывается требование «И», то

например, принятие и первого и третьего вариантов запишется            ;

■ если для вариантов накладывается требование «ИЛИ», то условие запишется:

Следовательно, если принять, что  соответствует «быть», — «не быть», то извечный вопрос «быть или не быть» запишется  +  = 1. В этом случае есть два допу­стимых решения:  = 1, = 0 означает «быть»; = 0,  = 1 — означает «не быть». Так как целевая функция не сформулирована, то дать оптимальный ответ на этот воп­рос невозможно. Чтобы принять решение, необходимо знать, чего мы хотим. Но об этом мы уже неоднократно говорили.