Уточнение модели с помощью логических переменных

Решение возникшей проблемы моделирования невогнутых функций прибыли может быть получено за счет введения в модель двоичных переменных. Новые переменные будут управлять порядком, в котором линейные части функции прибыли используются в решении. Для моделирования функции f₂(Q), выражающей прибыль от продаж продукта Q, требуются две новых переменных и модификация предельных ограничений для продукта Q. Введем логические переменные y_q2 и y_q3, которые будут управлять верхними и нижними границами для переменных Q₁, Q₂, Q₃.

Если переменная y_q2 =1, то допускаются продажи изделий Q во втором интервале, то есть Q₂, может принимать значения от 0 до 30. Если же переменная y_q2 =0, то не допускаются продажи изделий Q во 2-м интервале, а следовательно, и в 3-м интервале, то есть Q₂=0, Q₃=0.

Если переменная y_q3 =1, то допускаются продажи изделий Q в 3-м интервале, то есть Q₃, может принимать значения от 0 до 40. Если же переменная y_q3 =0, то не допускаются продажи изделий Q в 3-м интервале, то есть Q₃=0.

С помощью введенных переменных ограничения для Q₁, Q₂, Q₃ можно записать в следующем виде:

30y_q2 ≤ Q₁ ≤ 30, 30y_q3 ≤ Q₂≤ 30y_q2, 0 ≤ Q₃ ≤ 40y_q3.

Из неравенств видно, что, если y_q3=0, то только для допускается неравенство 0. Если y_q2=1 и y_q3=0, то обязательно равно 30 и это делает допустимым увеличение . Если y_q2 =1 и y_q3 =1, то и обязательно равны 30 и это позволяет увеличить . Сочетание y_q2 =0 и y_q3 =1 является недопустимым, как отмечалось выше, так как при отсутствии продаж во втором интервале, не могут происходить продажи в третьем интервале. Такое сочетание запрещается ограничением для вводимых переменных y_q2≤ y_q3.

Рассмотренные допустимые варианты представлены в табл. 4.10.

Таблица 4.10. Вид ограничений для Q_i

	yq2=0	yq2=1
yq3=0	0≤ Q1 ≤ 30	30≤ Q1 ≤ 30
0 ≤ Q2≤0	0≤ Q2≤30
0≤ Q3≤0	0≤ Q3≤0
yq3=1		30≤ Q1 ≤ 30
	30≤ Q2≤30
	0≤ Q3≤40

Переменными R₁, R₂, R₃, составляющими R, управляет единственная двоичная переменная y_r2.

Если переменная y_r2 =1, то допускаются продажи изделий R во 2-м интервале, то есть R₂, может принимать значения от 0 до 30. Если же переменная y_r2 =0, то не допускаются продажи изделий R во 2-м интервале, а следовательно, и в 3-м интервале, то есть R₂=0, R₃=0.

С помощью введенной переменной ограничения для R₁, R₂, R₃ принимают следующий вид:

30y_r2≤ R₁ ≤ 30, 0 ≤ R₂≤30y_r2, 0≤ R₃≤40y_r2.

Таблица 4.11. Вид ограничений для R_i

yr2=0	0≤ R1 ≤ 30
0 ≤ R2≤0
0≤ R3≤0
yr2=1	30≤ R1 ≤ 30
0 ≤ R2≤30
0≤ R3≤40

Полная модель с оптимальным решением задачи ЛП без целочисленного ограничения для переменных представлена на рис.4.16

	A	B	C	D	E	F	G	H	I	J
		Линеаризация нелинейной целевой функции
	Время обработки ед изделия (мин)	P	Q	R	Фонд времени
	Станок А
	Станок В
	Станок С
	Станок D
	Прибыль/ед	P	Q	R
	От 1 до 30
	От 31 до 60
	От 61 до 100
					Ограничения cнизу	Ограничения cверху
	Интервал объема производства	Pi	Qi	Ri	Pi	Qi	Ri	Pi	Qi	Ri
	1-й		16,36
	2-й
	3-й	21,82	-1,2E-30
	Сумма	81,82	16,36
		P	Q	R
	Ограничения по фонду времени						Логическ. Перемен.		Прибыль
	Станок А		<=						7268,2
	Станок В		<=			Yq2
	Станок С	2285,46	<=			Yq3
	Станок D	1063,64	<=			Yr2
	Ограничения по фонду производства	P	Q	R
	Верхняя граница

Рис.4.16. Модель и решение задачи ЛП с дополнительными логическими переменными^[5]

Рис.4.17 Настройки «Поиска решения» для задачи ЛП

Ограничения B15:D17<=H15:J17 и B15:D17>=E15:G17 задают верхние и нижние границы переменных, соответственно. Ограничение B18:D18<=100 задает верхние границы промежуточных переменных P, Q, R. Ограничение B22:В25<=D22:D25 задает ограничение фонда времени. Наконец, последние два ограничения «G23:G25 = двоичное» и G24 <= G23 задают свойства логических переменных. Обратим внимание, что в окне «Изменяемые ячейки» к диапазону базовых переменных через разделитель ‘;’ добавлен диапазон логических переменных G23:G25.

Модель с оптимальным решением задачи ЦП представлена на рис.4.18. Настройки «Поиска решения» задачи ЦП, отличаются лишь ограничением «B15:D17=целое» (рис. 4.19).

Как в задаче ЛП, так и в задаче ЦП оптимальное решение использует для продукции P все три интервала продаж, для продукции Q только первый интервал продаж, а для продукции R первые два интервала.

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

	A	B	C	D	E	F	G	H	I	J
		Линеаризация нелинейной целевой функции
…	…	…	…	…	…	…	…	…	…	…
					Ограничения cнизу	Ограничения cверху
	Интервал объема производства	Pi	Qi	Ri	Pi	Qi	Ri	Pi	Qi	Ri
	1-й
	2-й
	3-й		-1,2E-30
	Сумма
		P	Q	R
	Ограничения по фонду времени					Логич. Перем.			ПРИБЫЛЬ
	Станок А		<=
	Станок В		<=			Yq2
	Станок С		<=			Yq3
	Станок D		<=			Yr2
	Ограничения по фонду производства	P	Q	R
	Верхняя граница

Рис.4.18 Модель и решение задачи ЦП с дополнительными логическими переменными

Действительно, округление дробных значений P₃=81.82 и Q₁=16,36 даст оптимальные значения целочисленных переменных P₃=82 и Q₁=16, соответственно.

Рис.4.19 Настройки «Поиска решения» для задачи ЦП (за пределами окна «Ограничения» осталось ограничение «G24=<G23»)

Дата добавления: 2015-07-15