ЗАДАЧА ОБ ОПТИМАЛЬНОМ РАСПРЕДЕЛЕНИИ РЕСУРСОВ

задача;
Ее экономический смысл
Свойства оптимальных решений;
Двойственная переменная (теневая цена) как ценность

ресурсов;
Понятие нормированной стоимости;
Понятие устойчивости
Определение границ интервала устойчивости.
Решение в MS Excel
Отчеты MS Excel

Под ред. В.В. Федосеева. — 2-е изд. М.: ЮНИТИ-ДАНА, 2005.

— глава 2.
Вентцель Е.С. Исследование операций: Задачи, принципы, методология. М.: Высшая школа, 2001.
Канторович Л.В. Экономический расчёт наилучшего использования ресурсов. М.: Изд-во АН СССР, 1960.
Линейное программирование. Оптимальное распределение ресурсов. Методические указания для выполнения лабораторных работ для студентов направлений подготовки бакалавриата 120700, 080100 и 080200./НМСУ «Горный». Сост. В.В. Беляев, Т.Р. Косовцева. СПб, 2012., 62 с.

Применение линейного программирования в математических моделях © Н.М. Светлов, 2007-2011

(2.2) - система ограничений; (2.3) - естественные граничные условия;

двойственной задачи ui (двойственная переменная).
2. Каждой j-ой переменной исходной задачи

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

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

5. Если исходная задача была на нахождение максимума, то двойственная будет на нахождение минимума

двойственные переменные принято называть двойственными оценками Ui или теневой ценой

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

6. Число ограничений прямой задачи равно числу пере­менных двойственной, а число ограничений двойствен­ной — числу переменных прямой.

обозначает допустимый план прямой задачи, а ui, i = 1,

2,…, m – допустимый план двойственной задачи. Тогда выполняется неравенство: ,




при этом на оптимальных планах всегда выполняется равенство (maxF = minG). Если хотя бы одна из задач не имеет допустимого плана, то ни одна из них не имеет оптимального решения.

Для того чтобы допустимые планы прямой и двойственной задач были оптимальными, необходимо и достаточно, чтобы выполнялись равенства

Эти условия называются условиями дополняющей нежесткости!

двойственные переменные принято называть двойственными оценками Ui

Теорема 2

решений прямой и двойственной задач совпадают


Двойственная оценка ui в

экономических приложениях называется теневой ценой. Теневая цена ui является коэффициентом при bi => показывает, как изменится целевая функция при изменении i-го ресурса на единицу.

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

Двойственная задача

планы прямой и двойственной задач были оптимальными, необходимо и

достаточно, чтобы выполнялись равенства

стоимость ресурсов по теневым ценам, затраченных на производство единицы продукции j-го типа.

Теорема 2

приведенная стоимость

называется нормированной стоимостью.

Если продукцию j-го типа выпускать не целесообразно, то приведенная стоимость отлична от нуля (точнее >0) и наоборот, если xj>0 (продукцию выпускать целесообразно), то соответствующая приведенная стоимость =0.

Остаток ресурса i-го типа

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

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

{aij, bi cj i=1,...,m; j=1,...,n} зафиксирован, то этому набору соответствует

некоторый оптимальный план X=(x1, …,xn), назовем этот план базовым. Среди этих значений есть ряд ненулевых значений (т.е. эти виды продукции выпускать выгодно) и, возможно, часть нулевых (эти виды продукции выпускать не выгодно).
Часть ресурсов израсходована полностью, другая часть – ресурсы в избытке.
Если при изменении параметров ЗЛП , набор видов продукции, которые выпускать выгодно не изменился и теневые цены на ресурсы остались такими же как и базовом плане, то говорят, что структура решения сохранилась.

Рассмотрим влияние изменения параметров cj (прибыль от реализации единицы продукции) и bi (запасов ресурсов) на оптимальное решение задачи.

Цель исследования решения задачи на устойчивость – определить границы изменения параметров в которых структура решения сохраняется. С.32

Нормы расхода aij, при данной технологии, как правило, не меняются

единицы продукции) на оптимальное решение задачи.
Цель исследования решения задачи

на устойчивость – определить границы изменения параметров в которых структура решения сохраняется. С.32

Малые изменения коэффициентов целевой функции приводят к небольшому повороту градиента и линий уровня относительно первоначального положения. Положение вершины, соответствующей оптимальному плану, в которой линия уровня касается многогранника допустимых решений, также не изменится. Т.е. значение целевой функции изменится, но значения переменных, при которых этот оптимум достигается, не изменятся (рис.2.1). Существенное изменение коэффициента целевой функции приводит к существенному повороту градиента (линии уровня), и оптимальное решение будет достигаться в другой точке многогранника допустимых решений.

Допустимое увеличение Uj показывает, на сколько можно увеличить соответствующий коэффициент целевой функции cj (при условии постоянства остальных) без изменения оптимального плана. Допустимое уменьшение Lj показывает, на сколько можно уменьшить соответствующий коэффициент целевой функции (при условии постоянства остальных) без изменения оптимального плана.
Зная величины Lj и Uj , можно построить интервал, в котором решение (объем продукции) сохраняется. Нижняя граница этого интервала cj - Lj, верхняя граница cj + Uj. Значение целевой функции(суммарная прибыль) меняется! (На сколько ? Должен знать каждый!)

единицы продукции) на оптимальное решение задачи.
Цель исследования решения задачи

на устойчивость – определить границы изменения параметров в которых структура решения сохраняется. С.32

Допустимое увеличение показывает, на сколько можно увеличить соответствующий коэффициент целевой функции (при условии постоянства остальных) без изменения оптимального плана. Допустимое уменьшение показывает, на сколько можно уменьшить соответствующий коэффициент целевой функции (при условии постоянства остальных) без изменения оптимального плана.
Зная величины L1 и U1, можно построить интервал, в котором решение (объем продукции) сохраняется. Нижняя граница этого интервала c1-L1, верхняя граница c1+U1. Значение целевой функции(суммарная прибыль) меняется! (На сколько ? Должен знать каждый!)

Изменение cj (прибыли от реализации единицы продукции), которая входит в оптим-й план (xj>0) на величину ∆Cj вызывает изменение суммарной прибыли на величину ∆Cj *xj. Оптимальный план не меняется! (при условии cj + ∆Cj внутри интервала устойчивости!)
Если увеличение велико (вышли из интервала в право), то возможно другие виды продукции стало производить не выгодно, они обнулились! Xr=0. (r<>j)(Структура поменялась!).
Если уменьшение велико (вышли из интервала в лево), то возможно другие виды продукции стало производить более выгодно Xr>0. (r<>j), (xj=0) (Структура поменялась!).

Увеличение cj, которая не входит в оптим-й план (xj=0) на величину ∆Cj не вызывает изменение суммарной прибыли. Оптимальный план не меняется! (при условии cj + ∆Cj внутри интервала устойчивости!).
Если увеличение велико (вышли из интервала в право), то xj>0.(Структура поменялась!).
Уменьшение ничего не меняет!

– определить границы изменения параметров в которых структура решения сохраняется.

С.32

Геометрический смысл изменения количества ресурса заключается в том, что соответствующая граница многогранника допустимых решений перемещается параллельно сама себе. Это приводит к тому, что координаты точки, соответствующей оптимальному плану, меняются. При небольших изменениях количества ресурса координаты точки, соответствующей оптимальному плану, определяются пересечением того же набора прямых (гиперплоскостей), что и в базовом решении. При значительных изменениях количества ресурса, координаты точки, соответствующей оптимальному плану, определяются пересечением других прямых (гиперплоскостей). Структура меняется!
Изменение запаса ресурса вызывает изменение выручки и оптимального плана выпуска продукции (не всегда!).

Допустимое увеличение ui показывает, на сколько можно увеличить соответствующий коэффициентbi (количество соответствующего ресурса) при условии постоянства остальных без изменения структуры оптимального плана. Допустимое уменьшение li показывает, на сколько можно уменьшить bi (при условии постоянства остальных) без изменения структуры оптимального плана.
Зная величины l1 и u1, можно построить интервал устойчивости, в котором структура решение сохраняется. Нижняя граница этого интервала bi-li, верхняя граница bi+ui.

Рассмотрим влияние bi (запасов ресурсов) на оптимальное решение задачи.

При каких изменениях количества ресурса состав оптимальных базисных переменных прямой и двойственной задач не изменяется?

Пусть количество ресурса 1 изменилось на Δb1.
Ограничение на этот ресурс

при а12≠0.,

– определить границы изменения параметров в которых структура решения сохраняется.

С.32

Изменение запаса дефицитного ресурса вызывает изменение суммарной прибыли и оптимального плана выпуска продукции ( в интервале устойчивости!). ∆bi *ui

Допустимое увеличение показывает, на сколько можно увеличить соответствующий коэффициент bi (при условии постоянства остальных) без изменения структуры оптимального плана. Допустимое уменьшение показывает, на сколько можно bi (при условии постоянства остальных) без изменения структуры оптимального плана без изменения структуры оптимального плана.
Зная величины l1 и u1, можно построить интервал устойчивости, в котором структура решение сохраняется. Нижняя граница этого интервала b1-l1, верхняя граница b1+u1.

Рассмотрим влияние bi (запасов ресурсов) на оптимальное решение задачи.

При каких изменениях количества ресурса состав оптимальных базисных переменных прямой и двойственной задач не изменяется?

Пусть количество ресурса 1 изменилось на Δb1.
Ограничение

при а12≠0.,

Увеличение запаса не дефицитного ресурса не вызывает изменение суммарной прибыли и оптимального плана выпуска продукции (всегда!).

Уменьшение запаса не дефицитного ресурса не вызывает изменение суммарной прибыли и оптимального плана выпуска продукции (до определенного предела, пока он не станет дефицитным!) ( в интервале устойчивости!). .