Специальные задачи линейного программирования

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

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

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

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

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

    max L = 65 + 80 + + 210, 

    

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

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

 

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

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

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

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

    Max L =  

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

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

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

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

 

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

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

 

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

    4. Дискретное программирование

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

    Пример 3. Мебельная фабрика выпускает диваны, кресла и стулья. Требуется определить, сколько можно изготовить спинок диванов, подлокотников кресел и ножек стульев при известном удельном расходе ресурсов (табл. 4)., чтобы доход был максимальным.

Таблица 4.

 

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

   Решение. С учетом этих требований математическая модель задачи запишется:

  L =  
 

10,

10,

10, 
 
 
 

где -  варианты количества подлокотников и ножек (k = 1, …, k_i).

    Здесь дополнительное введение булевых переменных дает возможность обеспечить выпуск изделий в кратном заданном количестве. Так, для подлокотников x₂ может принимать следующие значения: если в результате решения будет получено , а остальные то x₂; если , а остальные , то x₂ = 4 и т.д.

    Для решения задачи с учетом дополнительных условий мы ввели еще семь переменных и четыре ограничения. Следовательно, введение дополнительных требований привело к увеличению размерности задачи. Заметим, что если бы нам требовалось определить выпуск спинок, подлокотников и ножек для одного изделия (комплекта), то можно было бы записать x₂ = 2х₁; х₃ = 4x₁ и не вводить дополни тельных ограничений и булевых переменных. Но это была бы другая задача.

    В результате решения задачи были получены следующие значения: max L = 320; = 1; = 4; = 12;  0;

    При этом оказались не полностью использованы ресурсы: резерв первого равен 50, второго — 4 ед.

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

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

    max(min)  
 

    где  ,, …, , … — дискретные значения, которые может принимать переменная . Эта система отличается от обычной задачи распределения ресурсов появлением булевых переменных и увеличением числа ограничений:

    max(min)  

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

5. Методы решения  дискретных задач

    Мы  убедились, что с помощью булевых  переменных можно решать часто встречающиеся  задачи оптимизации. Но как решать?

    Есть  три метода решения задач с  булевыми переменными:

• метод ветвей и границ;
• метод сплошного перебора;
• метод фильтрующего ограничения.

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

    Совершенно  очевидно, что выполнение этих двух требований обеспечивает получение в решении значений [0; 1] т. е. равных 0 или 1.

    Пример 4. Требуется решить систему методом сплошного перебора:

max L = 3₁ - 2₂ + 5₃ 

    Решение. Так как ₁, ₂, ₃ могут принимать значения 0 или 1 в любом сочетании, рассмотрим все возможные сочетания (табл. 5) в следующей последовательности.

Таблица 5.