Экономико-математический анализ модели ЗЛП

Размещено на http://www.allbest.ru/

Экономико-математический анализ модели ЗЛП

После нахождения оптимального решения ЗЛП естественно возникает вопрос о том, как влияют изменения параметров модели на полученное оптимальное решение. Рассмотрим на примере, как влияет на оптимальное решение изменение запасов ресурсов. Для этого будем использовать отчеты Excel. Пусть решается задача о выпуске двух видов продукции с использованием трех видов сырья. Необходимо найти такой план выпуска продукции , при котором прибыль от ее реализации будет максимальной.

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

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

Ресурс, соответствующий неактивному ограничению, называется недефицитным ресурсом, так как он имеется в избытке.

Отчет о результатах. Отчет включает в себя три таблицы. В первой таблице приводится исходное и окончательное значение целевой ячейки. Во второй таблице даны исходные и окончательные значения переменных . Третья таблица отчета содержит информацию об ограничениях. В графе Значение указано фактическое значение левой части каждого ограничения. В графе Разница указано, насколько отличаются левая и правая часть каждого неравенства системы ограничений. В частности, для ресурсных ограничений - это остаток ресурсов. Число 0 означает, что данное сырье использовано полностью. Положительное число указывает на количество неиспользованного сырья.

Графа Статус указывает на связь ограничений с оптимальным решением, а именно, какие ограничения являются активными (связанными) и неактивными (несвязанными). Оптимальное решение зависит от первых и не зависит от вторых.

Отчет об устойчивости. Отчет включает в себя две таблицы. В первой таблице указаны коэффициенты целевой функции - прибыль от реализации выпускаемой продукции, и допустимые изменения.

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

,

,

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

Если запасы ресурсов увеличить соответственно на , то можно определить влияние этих изменений на прибыль. В отчете об устойчивости указаны допустимые границы увеличения и уменьшения запасов ресурсов. , , . Если изменения запасов ресурсов удовлетворяют этим неравенствам, теневые цены остаются неизменными. Это позволяет оценить влияние этих изменений на прибыль. Определим раздельное влияние этих изменений на прибыль (для трех видов ресурсов):

, ,

Суммарное влияние на прибыль:

В данном примере: пусть .

Новая максимальная прибыль составит

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

Обозначим и - число единиц продукции и ,

- запас ресурса , - расход ресурса на единицу продукции ;

- цена продукции .

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

при ограничениях

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

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

Двойственная задача. Найти такой набор цен ресурсов , при котором общие затраты на ресурсы будут минимальными:

Коэффициенты при переменных в системах ограничений описываются матрицами:

Эти задачи обладают следующими свойствами:

1. В одной задаче ищут максимум линейной функции, в другой - минимум.

2. Каждая задача задана в стандартной форме. В задаче максимизации все неравенства вида «?», а в задаче минимизации неравенства вида «?».

3. Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой задаче.

4. Коэффициенты при переменных в целевой функции одной задачи являются свободными членами системы ограничений в другой.

5. Матрицы коэффициентов при переменных в системах ограничений обеих задач являются транспонированными друг другу.

6. Условия неотрицательности переменных имеются в обеих задачах.

Две ЗЛП, обладающие указанными свойствами, называются симметричными взаимно двойственными задачами.

Как составить математическую модель двойственной задачи:

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

2. Найти матрицу, транспонированную к матрице .

3. На основании полученной матрицы сформулировать двойственную задачу и условия неотрицательности переменных.

Пример. Дана математическая модель ЗЛП:

Математическая модель двойственной задачи:

В исходной задаче оптимальное решение . . Теневые цены (см. лекцию 3). В двойственной задаче оптимальное решение . . Основная теорема двойственности. Если одна из взаимно двойственных задач имеет оптимальное решение, то его имеет и другая, причем оптимальные значения их целевых функций равны:

Таким образом, оптимальное решение двойственной задачи - это теневые цены в отчете об устойчивости исходной задачи.

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

Осталось сравнить это число с ценой реализации . Если , продукцию можно включить в план выпуска. Если , продукцию не следует включать в план выпуска. В рассмотренном примере. Оценить целесообразность введения в план третьего вида продукции , если нормы расхода сырья на его единицу составляют соответственно 2, 1, 3, а прибыль - 2 ден. ед. , .Так как прибыль равна 2 ден. ед., то , и продукцию не следует включать в план выпуска.

Транспортная задача.

Постановка задачи. В различных местах отправки имеется однородный груз, который требуется доставить в несколько пунктов назначения. Известно, сколько груза имеется у каждого поставщика, и сколько груза должен получить каждый потребитель. Требуется организовать перевозки так, чтобы затраты на перевозки были минимальны.

Введем обозначения:

- число поставщиков (складов, хранилищ);

- число потребителей, количество пунктов назначения,

- запас груза в ом пункте (мощность i-го поставщика),

- спрос j-го потребителя, количество груза, которое должно быть завезено в й пункт,

- количество груза, перевозимого от i-го поставщика j-му потребителю,

- затраты на перевозку единицы груза от i-го поставщика j-му потребителю.

Требуется найти объемы перевозок для каждой пары «поставщик-потребитель» так, чтобы:

1) все грузы были вывезены;

2) спрос всех потребителей был удовлетворен;

3) суммарные затраты на перевозку были бы минимальны.

Пример.

1) 2)

Математическая модель задачи.

(1) (2)

(3)

На множестве неотрицательных решений системы ограничений (1) и (2) найти такое решение , при котором линейная функция (3) принимает минимальное значение. Математическая модель транспортной задачи имеет каноническую форму, так как система ограничений есть система уравнений. Для того чтобы транспортная задача была разрешима, т.е. имела оптимальный план, должно выполняться условие , т.е. суммарная мощность поставщиков должна быть равна суммарному спросу потребителей. В этом случае транспортная задача называется закрытой. Если суммарная мощность поставщиков не равна суммарному спросу потребителей, т.е. , то транспортная задача называется открытой.

Рассмотрим два случая.

Случай 1. Суммарный запас груза больше суммарного спроса потребителей:

Предложение превышает спрос. В данном случае имеется избыток запасов. Потребности потребителей будут удовлетворены полностью, а грузы будут вывезены со складов не в полном объеме. Поэтому знаки равенств в первой системе необходимо заменить знаками неравенств «<=». Система ограничений примет вид:

Случай 2. Суммарный запас груза меньше суммарного спроса потребителей:

Спрос превышает предложение. В ситуации дефицита все запасы будут вывезены полностью, а потребности будут удовлетворены не в полном объеме. Это означает, что знаки равенств во второй системе необходимо заменить знаками неравенств «<=».

целевой ячейка цена прибыль

Размещено на Allbest.ru