Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Целочисленное програм-ние Под задачей целочисленного программирования (ЦП) понимается задача, в которой. - презентация

1 Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Целочисленное програм-ние Под задачей целочисленного программирования (ЦП) понимается задача, в которой все или некоторые переменные должны принимать целые значения. В том случае, когда ограничения и целевая функция задачи представляют собой линейные зависимости, задачу называют целочисленной задачей линейного программирования. В противном случае, когда хотя бы одна зависимость будет нелинейной, это будет целочисленной задачей нелинейного программирования. Способы решения задач целочисленного программирования: Округление до целого решений задачи ЛП или НЛП без условий целочисленности переменных Метод полного перебора (British museum technique – последовательный перебор всех вариантов с нахождением оптимума: число возможных решений любой целочисленной задачи является конечным) Методы с применением оптимизационных алгоритмов (например, метод ветвей и границ, МВГ) Важно помнить, что методы решения целочисленных задач (перебор или МВГ) во многих случаях разумно применять только тогда, когда переменные принимают небольшие (

2 Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Метод ветвей и границ Впервые метод ветвей и границ был предложен Ландом и Дойгом в 1960 году для решения общей задачи целочисленного линейного программирования (Land A.H., Doig A.G. An automatic method of solving discrete programming problems // Econometrica. V28, 1960). Алгоритм метода ветвей и границ представляет собой эффективную процедуру перебора всех целочисленных допустимых решений. 1.Решается исходная задача ЛП при условии непрерывности переменных. 2.Если все корни решения нецелочисленны (в обратном случае – оптимальное целочисленное решение найдено), производим ветвление задачи на две, для каждой из задач вводим дополнительные ограничения по одной из переменных x i a i, x i b i, где a i – наибольшее целое, не превосходящее x i, а b i – наименьшее целое, большее x i, например, при корне исходной задачи x 2 =2.3 доп. ограничение в одной ветви будет x 2 2, а по другой – x Снова решаются задачи в обеих ветвях с накладыванием последующих ограничений по другим переменным. На каждом шаге проверяется целочисленность корней. Ветку считают тупиковой, если: а) допустимое решение очередной задачи ЛП отсутствует; б) текущее решение (значение целевой функции) хуже уже найденного целочисленного решения; в) текущая задача ЛП является подзадачей ранее рассчитанной задачи.

3 Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Метод ветвей и границ Пример с оптимизацией побочного производства лесничества ЛП1 x 1 =3.6, x 2 =6.4 W=34000 ЛП2 ( x 1 3) x 1 =3, x 2 =7 W=32500 ЛП3 ( x 1 4) x 1 =4, x 2 =5.33 W=33333 ЛП4 ( x 1 4, x 2 5) x 1 =4.125, x 2 =5 W=33125 целочисленное ЛП5 ( x 1 4, x 2 6) нет решения ЛП6 ( x 1 4, x 2 5) x 1 =4, x 2 =5 W=32500 ЛП7 ( x 1 5, x 2 5) x 1 =5, x 2 =0 W=25000 целочисленное ОР целочисленное ОР Предыдущие ограничения по одной из переменных остаются в силе до их изменения при ветвлении.

4 Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Рекомендации Рекомендации по формулировке и решению задач ЦП I. Количество целочисленных переменных необходимо уменьшать насколько возможно. Например, целочисленные переменные, значения которых должно быть не менее 20, можно рассматривать как непрерывные. II. В отличие от общих задач ЛП, добавление новых ограничений особенно включающих целочисленные переменные, обычно уменьшает время решения задач ЦП. III. Если нет острой необходимости в нахождении точного оптимального целочисленного решения, отличающегося от непрерывного решения, например, 3%, тогда реализацию метода ветвей и границ для задачи максимизации можно заканчивать, если отношение разницы между верхней и нижней границ к верхней границы меньше 0,03. (W U -W L )/W U

5 Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Задача оптимизации раскроя Пример о распиловке бревен Из 50 шт. бревен длиной 6,5 м необходимо изготовить наибольшее число комплектов, в состав каждого из которых входит 2 шт. детали длиной 2 м и 3 шт. детали длиной 1,25 м. 1. Подход "в лоб", решение задачи на ЭВМ. Показатель эффективности: количество (К) готовых комплектов из 50 бревенW=K max Управляемые переменные: x A и x B – число деталей А и В, получаемых из заготовки Ограничения: по длине заготовки2x A + 1,25x B 6,5 по комплектности50x A - 2K 0; 50x В - 3K 0; (эти ограничения можно не учитывать) областные ограниченияx A 0, x В 0, K 0 - целые Расчет на ЭВМ дает x A =2, x B =2, K=33. Это означает, что если из одной заготовки выкраивать две 2 м детали А и две 1,25 м детали В, то максимальное количество комплектов будет 33.

6 Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Задача оптимизации раскроя 2. ЛПР принимает несколько вариантов раскроя, задача решается с использованием ЭВМ. Сырье может раскраиваться на заготовки различными способами - вариантами (картами) раскроя, которые сводятся в специальную таблицу (в нашем примере существует 4 варианта распиловки). В качестве показателя эффективности целесообразно взять число комплектов K, которое можно получить из заданного числа заготовок (50 бревен). Возможны другие постановки - взять число заготовок Z, которое необходимо иметь, чтобы получить заданное число комплектов или отходы O.

7 Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Задача оптимизации раскроя Управляемые переменные: x n - число заготовок, раскраиваемых по n варианту. Целевая функция: W 1 =K maxили W 1 =О=0.5x 1 +0x x x 4 min Ограничения: по числу заготовокx 1 +x 2 +x 3 +x 4 =50 по комплектности3x 1 +2x 2 +x 3 -2K 0 2x 2 +3x 3 +5x 4 -3K 0 областные ограниченияx 1,x 2,x 3,x 4,K 0 - целые

8 Теория принятия решенийПетрГУ, А.П.Мощевикин, 2004 г. Задача оптимизации раскроя Решения, полученные на ЭВМ. Из таблицы видно, что существует пять равноценных вариантов раскроя, которые приводят к получению 41 комплекта из 50 заготовок. Если данный результат сравнить с результатом, полученном в первом случае (33 комплекта из тех же самых 50 заготовок), то получаем выигрыш в 8 комплектов. ЛПР может выбрать какой-нибудь из предложенных вариантов распиловки, например, на основании предпочтений по длине отходов.