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

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

Пример 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)

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