Пример 3. Мебельная фабрика выпускает диваны, кресла и стулья

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

Таблица 3.4

Исходные данные

Показатели	Изделия	Наличие ресурса
спинка дивана	подлокотники кресла	ножка стула
Цена, д.е./ед. Древесина Трудозатраты Спрос				– –
	x1	x2	x3	bi

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

Решение

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

.

где d_{2 k} , d_{3 k} – варианты количеств подлокотников и ножек (k = 1.. k_i).

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

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

В результате решения задачи были получены следующие значения: max L = 320; x ₁⁰ = 10; x ₂⁰ = 4; x ₃⁰ = 12; d₂₂⁰ = d₃₃⁰ = 1; d₂₁⁰ = d₂₃⁰ = d₂₄⁰ = d₃₁⁰ = d₃₂⁰ = 0.

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

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

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

,

где d _{1 j} , d _{2 j} ,..., d_kj,... – дискретные значения, которые может принимать переменная x_j. Эта система отличается от обычной задачи распределения ресурсов появлением булевых переменных и увеличением числа ограничений.

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