Построение модели. Опишем модель задачи математического программирования с нелинейными функциями

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

Прибыль: Max z = f₁(P) + f₂(Q) + f₃(R)

при условиях:

Станок А: 20P+10Q+10R ≤ 2400,

Станок В: 12P+28Q+16R ≤ 2400,

Станок С: 15P+5Q+16R ≤ 2400,

Станок D: 10P+15Q+0R ≤ 2400,

Маркетинг: P ≤ 100, Q ≤ 100, R ≤ 100,

Неотрицательность: P ≥ 0, Q ≥ 0, R ≥ 0.

Чтобы линеаризовать функции модели f₁(P), f₂(Q), f₃(R), представим введенные переменные как суммы объемов продаж по трем интервалам:

Р= Р₁+Р₂+Р₃, Q= Q₁+Q₂+Q₃, R= R₁+R₂+R₃

где

Р₁, Q₁, R₁ – объемы продаж в интервале (1-30),

Р₂, Q₂, R₂ – объемы продаж в интервале (31-60),

Р₃, Q₃, R₃ – объемы продаж в интервале (61-100).

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

Р: 0≤Р₁≤30, 0≤ Р₂≤30, 0≤ Р₃≤40,

Q: 0≤Q₁≤30, 0≤ Q₂≤30, 0≤ Q₃≤40,

R: 0≤R₁≤30, 0≤ R₂≤30, 0≤ R₃≤40,

Целевая функция, выраженная через новые переменные, будет линейной:

Max z = 60*P₁+45*P₂+35*P₃+40*Q₁+60*Q₂+65*Q₃+20*R₁+70*R₂+20*R₃

Итоговая модель представляет собой задачу линейного программирования:

Max z = 60*P₁+45*P₂+35*P₃+40*Q₁+60*Q₂+65*Q₃+20*R₁+70*R₂+20*R₃

Р= Р₁+Р₂+Р₃, Q= Q₁+Q₂+Q₃, R= R₁+R₂+R₃,

20P+10Q+10R ≤ 2400,

12P+28Q+16R ≤ 2400,

15P+5Q+16R ≤ 2400,

10P+15Q+0R ≤ 2400,

P ≤ 100, Q ≤ 100, R ≤ 100,

Р₁≤30, Q₁≤30, R₁≤30,

Р₂≤30, Q₂≤30, R₂≤30,

Р₃≤40, Q₃≤40, R₃≤40,

P_i ≥ 0, Q_i ≥ 0, R_i ≥ 0, i=1,2,3.

Для решения задачи построим модель в виде электронной таблицы и воспользуемся «Поиском решения».

	A	B	C	D	E	F	G	H
	Задача о трех видах продукции
	Время обработки ед. изделия (мин)	P	Q	R	Фонд времени
	Станок А
	Станок В
	Станок С
	Станок D
	Прибыль/ед	P	Q	R	Границы	Pi	Qi	Ri
	От 1 до 30				Интервал 1
	От 31 до 60				Интервал 2
	От 61 до 100				Интервал 3

Рис. 4.14. Параметры моделируемой системы

В диапазоне B3:D6 заданы временные затраты каждого станка на производство единицы каждого вида продукции, в диапазоне B9:D11 – удельная прибыль от продажи каждого вида продукции в каждом интервале количества продаж. Наконец, в диапазоне B9:D11 заданы верхние границы количества продаж для каждого интервала.

На рис.4.15 представлена собственно модель. Искомые переменные P_i, Q_i,R_i, размещены в диапазоне B14:D16, что позволяет просто вычислить промежуточные переменные P, Q,R в диапазоне B17:D17 (например, B17=СУММ(B14:B16)). Левые части ограничений по времени работы станков заданы в диапазоне B20:B23 формулами

=СУММПРОИЗВ(B3:D3;$B$17:$D$17), =СУММПРОИЗВ(B4:D4;$B$17:$D$17),

=СУММПРОИЗВ(B5:D5;$B$17:$D$17),

=СУММПРОИЗВ(B6:D6;$B$17:$D$17).

	A	B	C	D	E	F
….	….	….	….	….	….	….
		Pi	Qi	Ri		Прибыль
	Интервал 1
	Интервал 2
	Интервал 3
	Количество продаж
		P	Q	R
	Ограничения по фонду времени
	Станок А		<=
	Станок В		<=
	Станок С		<=
	Станок D		<=
	Ограничения объема производства	P	Q	R
	Верхняя граница

Рис. 4.15. Модель и решение задачи ЛП

Правые части ограничений по времени заданы в диапазоне D20:D23, а верхние границы промежуточных переменных P, Q, R - в диапазоне B26:D26. ЦФ вычисляется в ячейке F14 по формуле =СУММПРОИЗВ(B9:D11;B14:D16).

Ограничения задаются в окне «Поиска решения» (рис.4.16):

Рис. 4.15. Модель и решение задачи ЛП

Первое ограничение B14:D16<=F9:H11 задает верхние границы переменных P_i, Q_i, R_i, i=1,2,3. Второе ограничение B17:D17<= B26:D26 задает верхние границы переменных промежуточных переменных P, Q, R. Третье ограничение B20:В23<= D20:D23 – задает сравнение левой и правой частей ограничений на время использования станков.

Полученное решение задачи ЛП представлено на рис. 4.15.

К сожалению, решение не отражает исходную ситуацию. Обратив внимание на продукт P, видим, что произведенное общее количество 90, из которых 30 шт. проданы по 60 т.р., 30 шт. - по 45 т.р., и 30 шт. продано по 35 т.р. Модель правильна, потому что функция прибыли для P является вогнутой. Когда мы смотрим на продукт Q, мы видим, что все произведенные 30 единиц проданы по 65 т.р. Но это количество отнесено не к первому, а к третьему интервалу продаж. Это недопустимо, потому что вначале продаются количества первых двух интервалов, и лишь затем общее количество продаж переходит в третий интервал. Такое же нарушение происходит и продажами продукта R, где имеется 30 продаж во втором интервале, а в первом интервале продаж нет).

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

При поиске оптимального решения, алгоритм будет, конечно, использовать значения переменных, представляющих отдельный продукт в порядке уменьшения удельной прибыли, начиная с интервала с самой высокой удельной прибылью. Это обеспечивает правильный результат для расчета прибыли от продажи продукта P, потому что в этом случае функция прибыли f₁(P) является вогнутой. Однако такой алгоритм дает неадекватные результаты для максимизации прибыли от продаж продуктов Q и R, потому что их функции прибыли f₂(Q) и f₃(R) не являются вогнутыми (рис. 4.13). Таким образом, можно сделать общий вывод, состоящий в том, что кусочно-линейные вогнутые функции могут быть успешно смоделированы для решения задачи ЛП, а моделирование кусочно-линейных функций, которые не являются вогнутыми, приводит к неадекватным результатам.

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