Двойственные оценки и их влияние на функционал

Оглавление:

I. Теоретическая часть…………………………………………………………1

1.1. Двойственные оценки как мера влияния ограничений

на функционал………………………………………………………………....1

II. Практическая часть…………………………………………………………2

2.1. Решение задачи графическим методом………………………………….2

2.2. Решение задачи на основе анализа временного ряда………………….12

2.3. Решение задачи на управление запасами………………………………23

Список использованной литературы………………………………………..25

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

I. Теоретическая часть

1. Двойственные оценки как мера влияния ограничений на      функционал

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

Любую задачу линейного  программирования в стандартной  форме можно записать в виде соотношений:

                                                           (1.1)

                                                             (1.2)

                                                                         (1.3)

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

                                                             (1.4)

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

                                         (1.5)

                                                           (1.6)  

Задача, состоящая в  нахождении минимального значения функции

                                              (1.7)

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

                                            (1.8)

 

                                                                      (1.9)

называется двойственной по отношению к задаче (1.4) – (1.6). Задачи (1.4) – (1.6) и (1.7) – (1.9) образуют пару задач, называемую в линейном программировании двойственной парой.

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

Построение двойственной ЗЛП основано на следующих пяти правилах:

1) если целевая функция исходной задачи формулируется на максимум, то целевая функция двойственной задачи – на минимум (и наоборот), при этом в двойственной задачи на максимум все неравенства в функциональных ограничениях имеют вид ≤, а в задаче на минимум – вид ≥;

2) матрица А, составленная из коэффициентов при неизвестных в системе ограничений исходной задачи, и аналогичная матрица А’ в двойственной задачи получаются друг из друга транспонированием;

3) число переменных в двойственной задаче равно числу функциональных ограничений исходной задачи, а число ограничений в системе двойственной задачи – числу переменных в исходной;

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

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

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

Многие задачи линейного программирования первоначально составляются в виде исходной или двойственной задач, поэтому имеет смысл говорить о паре двойственных задач линейного программирования.

Таким образом, задача, двойственная по отношению к задаче (1.1)-(1.3)

в стандартной форме  имеет вид:

                       (1.10)

                                                                (1.11)

                                                                          (1.12)

Различают несимметричные и симметричные двойственные задачи. В несимметричных задачах система ограничений исходной задачи задается в виде равенств, а система ограничений в двойственной задаче – в виде неравенств, причем в двойственной задаче переменные могут быть и отрицательными.

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

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

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

f (X*)=g (Y*)                                              (1.13)

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

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

4. Обе задачи имеют пустые  допустимые множества.

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

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

Вторая  теорема двойственности (теорема о дополняющей нежесткости). Пусть Х = (х_1,х_1, …, х_n) – допустимое решение прямой задачи, У = (у_1,у_1, …, у_n) – допустимое решение двойственной задачи. Для того чтобы они были оптимальными решениями соответственно прямой и двойственной задачи, необходимо и достаточно, чтобы выполнялось следующее соотношение:

 

                                   (1.14)

     

                                    (1.15)

Условие (1.14) и (1.15) позволяют, зная оптимальное решение одной из взаимно двойственных задач, найти оптимальное решение другой задачи.

Теорема об оценках. Значение переменных у_i в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов у_i системы ограничений (неравенств) прямой задачи на величину

                                              (1.16)

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

 

II. Практическая часть

2.1. Решение задачи графическим методом

 

Финансовый  консультант фирмы «ABC» консультирует клиента по оптимальному инвестиционному портфелю. Клиент хочет вложить средства (не более 25 000 долл.) в два наименования акций крупных предприятий в составе холдинга «Дикси».

Анализируются акции «Дикси-Е» и «Дикси-В». Цены на акции: «Дикси-Е» - 5долл. за акцию; «Дикси-В» - 3 долл. за акцию.

Клиент уточнил, что он хочет приобрести максимум 6000 акций обоих наименований, при  этом акций одного из наименований должно быть не более 5000 штук.

По оценкам  «ABC», прибыль от инвестиций в эти акции в следующем году составит: «Дикси-Е» - 1,1 долл.; «Дикси-В» - 0,9 долл.

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

Построить экономико-математическую модель задачи, дать необходимые комментарии  к ее элементам и получить решение графическим методом. Что произойдет, если решать задачу на минимум, и почему?

Решение:

1. Для решения задачи приведем все вышеперечисленные величины в таблицу:                                                              

                                                                                                                Таблица 1.

	Дикси- Е	Дикси- В
Цена	5 долл.	3 долл.	≤ 25 000 долл.
Прибыль	1,1 долл.	0,9 долл.

 

2. Математическая формулировка  задачи.

Пусть х₁ шт. - количество акций «Дикси-Е»;

          х₂ шт. - количество акций «Дикси-В»,

тогда количество приобретаемых акций: х₁ + х₂ <= 6000;

вложенные средства должны составить:

5х₁ + 3х₂ <= 25 000 долл.;

а максимальная прибыль выразится функцией:

F = 1,1x₁ + 0,9x₂ ®max

Получили задачу оптимизации:

найти максимальное значение линейной функции 

F = 1,1x₁ + 0,9x₂ при ограничениях:

х₁ +х₂ <= 6000

5х₁ + 3х₂ <= 25000

0≤ х₁ ≤ 5000; 0 ≤ х₂ ≤ 5000

3. Построим многоугольник решений. Для этого в системе координат х₁Ох₂ на плоскости изобразим граничные прямые

5х₁+3х₂=25000

X1	5000	0
X2	0	8333

 х₁+х₂=6000

X1	6000	0
X2	0	6000

 

        (5000;0)      

         ( 0;5000)        

Линия уровня: max f(x) = 1,1Х1 + 0,9Х2 (4500;0) (0;5500)

X1	4500	0
X2	0	5500

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок. 1 Многоугольник решений

4. При перемещении линии уровня в направлении вектора-Градиента получаем точку С, это и есть точка максимума, найдем ее координаты – оптимальное решение.