Смекни!
smekni.com

Исследование математических операций 2 (стр. 8 из 28)

Рассмотрим ограничение (2)

, которое представля­ет собой ограничение на недефицитный ресурс - сырье В. И в этом случае правую часть - запасы сырья В - можно уменьшать до тех пор, пока прямая L2 не достигнет точки С. При этом правая часть ограничения (2) станет равной

, что позволяет записать это ограничение в виде:
. Этот результат показывает, что ранее полученное оптимальное решение не измените, если суточный запас ресурса В уменьшить на 3 ед.

Результаты проведенного анализа можно свести в следующую таблицу:

Ресурс

Тип ресурса

Максимальное изменение запаса ресурса, ед.

Максимальное увеличение дохода от изменения ресурса, у.д.е.

1 (А)

дефицитный

12 – 9 = +3

17 – 12,8 = +4,2

2 (В)

недефицитный

10 – 13 = -3

12,8 – 12,8 = 0

3

дефицитный

4 – 1 = +3

13,4 – 12,8 = +0,6

4

недефицитный

1,4 – 2 = -0,6

12,8 – 12,8 = 0

Задача 2. Определение наиболее выгодного ресурса.

В задаче 1 анализа на чувствительность мы исследовали влияние на оптимум увеличения объема дефицитных ресурсов. При ограничениях, связанных с дополнительным привлечением ресурсов, естественно задать вопрос: какому из ресурсов следует отдать предпочтение при вложении дополнительных средств? Для этого вводится характеристика ценности каждой дополнительной единицы дефицитного ресурса, выражаемая через соответствующее приращение оптимального значения целевой функции. Такую характеристику для рассматриваемого примера можно получить непосредственно из таблицы, в которой приведены результаты решения задачи 1 на чувствительность. Обозначим ценность дополнительной единицы ресурса i через yi. Величина yi определяется из соотношения

.

Результаты расчета ценности единицы каждого из ресурсов представлены в следующей таблице:

Полученные результаты свидетельствуют о том, что дополни­тельные вложения в первую очередь следует направить на увеличе­ние ресурса А и лишь затем - на формирование соотношения спроса на продукцию П1 и продукцию П2 . Что касается недефицитных ресурсов, то, как и следовало ожидать, их объем увеличивать не следует.

Задача 3. Определение пределов изменения коэффициентов целевой функции.

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

При анализе модели ни чувствительность к изменениям коэффи­циентов целевой функции необходимо исследовать следующие вопросы:

1. Каков диапазон изменения того или иного коэффициента целевой функции, при котором не происходят изменения опти­мального решения?

2. На сколько следует изменить тот или иной коэффициент це­левой функции, чтобы сделать некоторый недефицитный ресурс дефицитным, и, наоборот, дефицитный ресурс сделать недефицит­ным?

Ответим на поставленные вопросы на нашем примере.

Рассматривая первый вопрос, обозначим через c1 и c2 доходы предприятия от продажи единицы продукции П1 и П2 соответст­венно. Тогда целевую функцию можно представить в следующем виде:

Z = с1х1 + с2х2

На рис. 2.5 видно, что при увеличении c1 или уменьшении c2 прямая, представляющая целевую функцию Z, вращается (вокруг точки С) по часовой стрелке. Если же c1 уменьшается или c2 увеличивается, эта прямая вращается в противоположном направлении - против часовой стрелки. Таким образом, точка С будет оставаться оптимальной точкой до тех пор, пока наклон прямой не выйдет за пределы, определяемые наклонами прямых для ограничений (1) и (3).

Когда наклон прямой Z станет равным наклону прямой L1, по­лучим две альтернативные оптимальные угловые точки - С и В. Аналогично, если наклон прямой Z станет равным наклону прямой для ограничения (3), будем иметь альтернативные оптимальные уг­ловые точки С и D. Наличие альтернативных оптимумов свидетель­ствует о том, что одно и то же оптимальное значение Z может до­стигаться при различных значениях переменных х1 и х2 . Как толь­ко наклон прямой выйдет за пределы указанного выше интервала c1, получим некоторое новое оптимальное решение.

Рассмотрим на нашем примере, каким образом можно найти допустимый интервал изменения c1, при котором точка С остается оптимальной. Исходное значение коэффициента c2 = 4 оставим не­изменным. На рис. 2.5 видно, что значение c1 можно уменьшать до тех пор, пока прямая Z не совпадет с прямой L1 (отрезок ВС).

Это крайнее минимальное значение коэффициента c1 можно определить из равенства углов наклонов прямой Z и прямой L1 . Так как тангенс угла наклона для прямой Z равен (c1/4) , а для прямой (1) равен 2/3, то минимальное значение c1 определим из равенства c1/4=2/3, откуда

. На рис 2.5 видно, что значение c1 можно увеличивать беспредельно, так как прямая Z при c2 = 4 и

не совпадает с прямой L3 (отрезок DC) и, следовательно, точка С при всех значениях коэффициента
будет единствен­ной оптимальной.

Интервал изменения c1, в котором точка С по-прежнему оста­ется единственной оптимальной точкой, определяется неравенством

. При c1 = 8/3 оптимальными угловыми точками будут как точка С, так и точка В. Как только коэффициент c1 становится меньше 8/3 , оптимум смещается в точку В.

Можно заметить, что, как только коэффициент c1 оказывается меньше 8/3, ресурс 3 становится недефицитным, а ресурс 4 - дефицитным. Для предприятия это означает следующее; если доход от продажи единицы продукции П1 станет меньше 8/3 д.е., то на­иболее выгодная производственная программа предприятия долж­на предусматривать выпуск максимально допустимого количества продукции П2 (полностью удовлетворять спрос на продукцию П2). При этим соотношение спроса на продукцию П1 и П2 не будет лимитировать объемы производства, что обусловит недефицитность ресурса (3). Увеличение коэффициента c1 свыше 8/3 д.е. не снимает проблему дефицита ресурсов (1) и (3). Точка С - точка пересе­чения прямых L1 и L3 - остается все время оптимальной.

Назад | Содержание | Далее

2.5. Симплекс-метод

2.5.1. Общая идея симплекс-метода

Для начала работы требуется, чтобы заданная система ограни­чений выражалась равенствами, причем в этой системе ограниче­ний должны быть выделены базисные неизвестные. Решение зада­чи при помощи симплекс-метода распадается на ряд шагов. На каждом шаге от данного базиса Б переходят к другому, новому ба­зису Б1 с таким расчетом, чтобы значение функции Z уменьшалось, т. е.

. Для перехода к новому базису из старого базиса уда­ляется одна из переменных и вместо нее вводится другая из числа свободных. После конечного числа шагов находится некоторый ба­зис Б(k) , для которого

есть искомый минимум для линейной функции Z, а соответствующее базисное решение является опти­мальным либо выясняется, что задача не имеет решения.

Назад | Содержание | Далее

2.5.2. Алгоритм симплекс-метода

Рассмотрим систему ограничений и линейную форму вида:

; (2.37)

; (2.38)

,
. (2.39)

Используя метод Жордана-Гаусса, приведем записанную систему к виду, где выделены базисные переменные. Введем условные обозначения:

x1, x2 , ... , xr - базисные переменные;