Лекции 8

ЦЕЛОЧИСЛЕННОЕ И ДИСКРЕТНОЕ ПРОГРАММИРОВАНИЕ

Под задачей целочисленного программирования (ЦП) понимается задача, в которой все или некоторые переменные должны принимать целые значения. Если все ограничения и целевая функция линейные, то её называют целочисленной задачей ЛП (ЦЗЛП). Т.к. набор значений x_i становится конечным (во всяком случаи дискретным), то задачу можно решить простым перебором, но это не является оптимальным (метод полного перебора – перебираются все точки, попадающие в допустимую область, т.е. удовлетворяющие всем ограничениям).

Поэтому обратимся к методам, в котором все возможные альтернативы не рассматриваются.

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

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

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

1. Решаем задачу ЛП без ограничения целочисленности.

Пусть ₁ – оптимальное значение целевой функции, тогда ₁ – верхняя граница задачи ЦП.

2.Проводим ветвление по одной из целочисленных переменных, имеющей дробное значение.

Выбор переменной производится по следующему правилу:

• если переменная имеет наибольшее дробное значение;

• если коэффициент в целевой функции максимальный;

• произвольно, например, с меньшим порядковым номером.

3. Пусть - дробное, , <<.

Получаем 2 новые задачи ЛП: ЛП-2 с дополнительным ограничением и ЛП-3 с дополнительным ограничением .

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

• использование наибольшего оптимального значения целевой функции;

• «последним пришел – первым вышел».

5. Каждое новое решение задачи ЛП проводим симплекс–методом или графическим. При этом если - остается целой, то ограничения для нее сохраняется, если дробное, то на очередном этапе вводят новые ограничения.

6. Процесс повторяем до получения целочисленного решения или приходим к выводу, что задача ЦП не имеет решения.

7. Из всех целочисленных решений выбираем то, где целевая функция максимальна (минимальна).

Пример:

Пусть задача ЛП-1 имеет решение , Осуществляем ветвление по .

Из 3-х целочисленных решений выбираем, где - максимальное это ЛП-2 (, ) и ЛП-6 (, ). В этих случаях , которое, кстати, не совпадает с , , где

Рекомендации и замечания

1. Рекомендуется уменьшать количество целочисленных переменных. Например, если >20, то оставлять непрерывным и округлять.

2. В отличие от задач ЛП добавление новых ограничений может уменьшить время решения задач ЦП (сокращается число циклов).

3. Если допустимая точность, например, 3% и разница между верхней границей () и нижней границей (₂ - при решении задачи ЦП) меньше 0.03, то дальнейшие вычисления можно закончить.

4. Метод ветвей и границ можно применять и для задач нелинейного программирования.

Пример: задача оптимизации раскроя.

Имеется сырьё в виде листов, брусьев и т. д. Требуется изготовить детали, имеющие определенные размеры. Число деталей должно быть максимальным. Например, из 50 шт. бревен длиной 6.5 м необходимо изготовить наибольшее число комплектов, включающие 2 шт. деталей длиной 2 м и 3 шт. деталей длиной 1.25 м – это задача линейного раскроя.

Подход 1 (формальный)

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

Пусть и - число деталей и , получаемых из одной заготовки.

Тогда возможны следующие постановки задачи:

1. Целевая функция , Z – фиксирована. Требуется найти максимум W₁

2. Целевая функция , K - фиксирована. Требуется найти минимум W₂

В примере Z – фиксирована, требуется найти максимум K.

Ограничения:

по длине заготовки :

по комплектности :

или ,

или ,

целые.

В данной задаче

Пояснения к ограничениям по комплектности. –показывает сколько деталей А было изготовлено. Так как число деталей в комплекте равно 2, то – показывает, сколько можно изготовить комплектов. Причем, если – целое, то оно равно К, если дробное, то больше К (одна деталь не вошла в комплект и осталась лишняя). Аналогично для деталей В, с той лишь разницей, что в комплект входят 3 детали В.

В первой постановке задачи ( фиксировано )

Целевая функция ,

,

,

,

целые.

Решение: , т.е. ЭВМ выбрала этот вариант.

Подход 2 (автоматизированный - с участием человека).

_{Сырье может раскраиваться разными вариантами.}

Варианты	1	2	3	4	Число деталей в комплекте
	3	2	1	0	2
	0	2	3	5	3
Отходы	0.5	0	0.75	0.25
Число заготовок, раскрываемые по вариантам

Замечание: в первом подходе был выбран безотходный вариант 2.

Но решение задачи оптимально, если не все бревна раскраивать одинаково.

Пусть переменные ,,- число заготовок, раскраиваемых по варианту 1, 2, 3, 4 соответственно.

Целевая функция число комплектов. Число заготовок задано (Z=50). Требуется найти максимум целевой функции.

Замечание. В общем случае возможны следующие постановки задачи:

1. Находиться максимум (K-число комплектов)

2. Находиться минимум (Z-число заготовок)

3. Находиться минимум (W₃ – количество отходов)

Ограничения:

По числу заготовок :

По комплектности:

или ,

или ,

-целые.

Пояснения к ограничениям по комплектности. Величина показывает, сколько деталей А было создано всего. Так как в комплект входят 2 детали А, то число комплектов не может превосходить . Аналогичное ограничение и для деталей В; суммарное количество деталей В равно , а в комплект входят 3 детали.

В первой постановке задачи .

,

,

,

- целые.

При решении получается 5 равноценных вариантов.

Решение:

Варианты	1	2	3	4	5
	0	0	0	1	0
	41	41	42	40	40
	0	1	0	1	2
	9	8	8	8	8
	41	41	41	41	41

Таким образом, второй метод («человек принимает несколько различных вариантов, а программа выбирает лучшее из них») оказался лучше, чем первый метод («программа выбирает вариант»), т.к. получилось , вместо .

Это связано с тем, что оптимальным оказывается раскраивать не все бревна по варианту 2, а некоторые раскраивать другим способом.

40