Задача 1. Строительная фирма организовала выпуск деревянных домов двух видов А и В

Строительная фирма организовала выпуск деревянных домов двух видов А и В. Для производства первой партии домов фирма приобрела брус - на $100 тыс., вагонку – на $150 тыс. и обрезную доску – на $160 тыс. На постройку дома вида А требуется брус – на $1 тыс. и вагонка – на $3 тыс., а на постройку дома вида В – брус на $2 тыс., вагонка – на $1 тыс. и обрезная доска – на $4 тыс.

Фирма планирует продажу домов вида А по цене $10 тыс., а вида В – по цене $30 тыс.

1) Определить оптимальный план выпуска домов и прибыль от их реализации.

2) Определить наличие излишков приобретенных стройматериалов. Оценить, какую сумму можно дополнительно выручить за счет продажи излишков стройматериалов (по закупочным ценам).

3) Фирма решила не продавать излишки стройматериалов, а на имеющиеся финансовые резервы в размере $10 тыс. закупить дополнительно необходимые стройматериалы. Определить, какой вид стройматериалов целесообразно дополнительно закупить и какую дополнительную прибыль можно за счет этого получить.

Издержками считать стоимость стройматериалов.

Решение

1) Представим данные в табличной форме:

Формализуем задачу:

Изобразим допустимое множество и линию уровня целевой функции – см. рис. 4.16.

Как видно из рис. 4.16, максимум целевой функции достигается в точке В, в которой пересекаются ограничения 1 и 3. Найдем эту точку:

.

Таким образом, оптимальный план постройки домов: (20; 40). При этом фирма получит доход в размере $1.400 тыс., а прибыль составит 1.400 – 100 – 150 – 160 = 990 (тыс. долларов).

2) Из рис. 4.16 видно, что ограничение 2 не активно. Это значит, что вагонка закуплена в избытке и ее количество можно было бы сократить без изменения оптимального решения и значения целевой функции (дохода). Допустим, что фирма имеет возможность продать излишки по закупочной цене. Определим объем излишков (в тыс. долларов). Пусть мы оставляем вагонки для постройки домов на тыс. долларов. Тогда вместо 2 имеет место неравенство . Соответствующая граничная линия, очевидно, будет параллельна линии 2. Для того, чтобы оптимальная точка осталась на месте, нужно, чтобы линия была правее точки В или проходила через нее. В случае прохождения данной линии через точку В мы будем иметь минимальное значение и, таким образом, максимальную дополнительную выручку от продажи излишков: .

Итак, имеем: , и дополнительная выручка от продажи излишков равна 150 – 100 = 50 (тыс. долларов).

3) Пусть фирма имеет резерв финансовых средств на дополнительную закупку стройматериалов в размере $10 тыс. Оценим, какой вид стройматериалов целесообразно закупить.

Поскольку все константы измеряются в единых единицах (тыс. долларов), то ответ на этот вопрос непосредственно дадут множители Лагранжа (двойственные переменные) . Итак, перейдем к двойственной задаче:

.

Так как в оптимальной точке прямой задачи ограничение 2 не активно, то в оптимальной точке двойственной задачи , а так как , то оба функциональных ограничения должны выполняться как равенства:

.

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

В этой точке

Таким образом, сохранит свое значение при увеличении на 116²/₃ –100 = = 16²/₃ (тыс. долларов), что больше имеющегося резерва финансовых средств. Таким образом, $10 тыс. целесообразно использовать полностью для дополнительной закупки бруса. При этом оптимальный доход увеличится на (тыс. долларов), а прибыль на 100 – 10 = 90 (тыс. долларов).

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

Как уже отмечалось, при изменении граница 1 будет параллельно перемещаться. На рис. 4.17 изображены критические положения этой границы, когда происходит смена базиса.

Очевидно, при допустимое множество состоит из одной точки Е и .

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

При дальнейшем перемещении границы до точки С() оптимальное решение будет лежать на границе 3:

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

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

Итак, имеем: , . Для построения графика составим таблицу:

Оптималь-ная точка / отрезок	Координаты точки/ уравнение отрезка	Градиенты активных ограничений	Градиент оптимизирующей целевой функции
	A	(0;40)	(-1;0), (0;4)	-	-	-
	AB		(0;4)	(0;30)
	B	(20;40)	(0;4), (1;2)		(0;15)
	BC		(1;2)	(15;30)
	C	(40;30)	(1;2), (3;1)		(15;90)
	CD		(3;1)	(90;30)
	D	(50;0)	(3;1), (0;-1)		(90; )
	DE		(0;-1)	-	-	-
	E	(0;0)	(0;-1), (-1;0)	-	-	-
	EA		(-1;0)	-	-	-

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

График изображен на рис. 4.19.

4.6. Принцип гарантированного результата в задачах линейного программирования

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

Здесь мы рассмотрим случай осторожного ЛПР, стремящегося в наихудших условиях получить наилучший в этих условиях результат. Такой тип ЛПР исповедует так называемый принцип гарантированного результата. В данном разделе мы ограничимся рассмотрением задач линейного программирования, в которых некоторые параметры заданы интервалами в которых лежат "истинные", но неизвестные ЛПР значения. Цель ЛПР (или его помощника-аналитика) при постановке задачи линейного программирования состоит в том, чтобы выбрать в некотором смысле наихудшие значения параметров из заданных интервалов (обычно это крайние значения) так, чтобы найденный при таких условиях оптимум был гарантированным, т.е. при любых других значениях параметров он не оказался бы хуже. Иными словами, если вдруг окажется, что истинные параметры отличаются от выбранных для решения задачи, то неприятной неожиданности не произойдет: результат окажется по крайней мере не хуже рассчитанного.

В качестве иллюстрации рассмотрим следующую задачу.

Задача

Предприятие планирует выпуск продукции на следующий год. Производственные возможности предприятия позволяют выпускать продукцию трех видов: А, В и С. Для производства этих видов продукции предприятию требуется закупить сырье, стоимость единицы которого в следующем году прогнозируется в интервале от 0,8 до 1 тыс. руб.. На закупку сырья предприятие может истратить не более 770 тыс. рублей. На производство единицы продукции вида А требуется от 70 до 80 единиц сырья, вида В – от 40 до 50 единиц, вида С – от 15 до 20 единиц. Производственные мощности предприятия ограничены 550 единицами, причем на производство единицы продукции указанных видов требуется 40, 80 и 120 единиц соответственно. Прогнозируемая цена выпускаемой продукции колеблется в пределах [320; 350], [400; 430], [240; 280] тыс. руб. соответственно.

Составить оптимальный план выпуска продукции, гарантирующий максимально возможную прибыль в предположении независимости неопределенных факторов, и значение этой прибыли. Издержками считать затраты на сырье.

Решение

Представим данные в табличном виде:

Из диапазона значений параметров выберем наихудшие для производителя (уменьшающие прибыль). Для расхода и стоимости сырья это, очевидно, максимальные значения. Для цены произведенной продукции – минимальные. Составим таблицу с выбранными значениями:

Далее задача решается как обычная задача линейного программирования.

Составляем целевую функцию – прибыль от реализации продукции (с учетом или без учета издержек – не важно, поскольку они фиксированы) и ограничения на ресурсы:

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

Изобразим допустимую область и линию уровня целевой функции – см. рис. 4.20. Очевидно, решение будет находиться в точке пересечения линий 1 и 2. Поскольку в этой точке ограничение 3 не активно, то в оптимальной точке прямой задачи . Поскольку эта точка не лежит на осях координат (координаты положительны), то оба ограничения в прямой задаче в оптимальной точке должны выполняться как равенства:

Ответ: . Максимальный гарантированный доход равен 3.680 тыс руб., а прибыль, соответственно 3.680 – 770 = 2.910 тыс. руб.

Поиск по сайту: