Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

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

Оглавление:

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

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

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

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

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

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

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

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

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

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

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

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

(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)

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

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

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

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

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.

	Дикси- Е	Дикси- В
Цена	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

X₁	5000	0
X₂	0	8333

х₁+х₂=6000

X₁

6000

X₂

6000

(5000;0)

( 0;5000)

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

X₁	4500	0
X₂	0	5500

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

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

5Х1 +3Х2 = 25 000

Х1 + Х2 = 6000

5Х1 +3Х2 = 25 000

Х1 = 6000 – Х2

30000 – 5Х2 + 3Х2 = 25000

Х1 = 6000 – Х2

Х2 = 2500

Х1 = 6000 – Х2

Х2 = 2500

Х1 = 3500

5. Подставляем найденные значения в линейную функцию

Значение целевой функции в точке С (3500; 2500) равно:

max f(x) = 1,1 * 3500 + 0,9 * 2500 = 3850 + 2250 = 6100.

6. Нахождение значения целевой функции в точке С посредством решение задач в Microsoft Excel

Заносим исходные данные: стоимость акций и прибыль, которую сможем получить при покупке определенного количества акций

Рис. 2 Исходные данные

Заносим целевую функцию Меню-Вставка-Функции-СУММПРОИЗВ

Рис.3 Целевая функция

Заполняем поле ограничения (левая часть):

- для ячейки D10 с помощью Меню-Вставка-Функции-СУММПРОИЗВ

Рис. 4 Заполнение поля ограничение для ячейки D10

- для ячейки D11

Рис. 5 Заполнение поля ограничение для ячейки D11

- для ячейки D12

Рис. 6 Заполнение поля ограничение для ячейки D12

- для ячейки D13

Рис. 7 Заполнение поля ограничение для ячейки D13

С помощью «Поиска решений» (Меню-Сервис) находим значения для Дикси-Е и для Дикси-В и прибыль, которую мы получим в результате покупки двух видов акций

Рис.8 Поиск решения

В итоге мы получаем значения для Дикси-Е и для Дикси-В

Рис.9 Значение для переменных Дикси-Е и для Дикси-В

Ответ: чтобы обеспечить оптимальную прибыль от инвестиций необходимо купить: акций Дикси-Е - 3500 шт. и акций Дикси-В - 2500 шт., при этом прибыль от двух видов купленных акций составит – 6100 долл.; Если решать задачу на min то надо двигаться по линии вектора-градиента в обратном направлении линии уровня и min f(x) = 0 достигается при, Х1 =0; Х2 = 0.

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

В течение девяти последовательных недель фиксировался спрос Y(t) (млн. руб.) на кредитные ресурсы финансовой компании. Временной ряд Y(t) этого показателя приведен в таблице:

Таблица 2

Номер

Варианта

Номер наблюдения (t=1,2,…,9)

Требуется:

1) проверить наличие аномальных наблюдений.

2) построить линейную модель Ŷ(t) = , параметры которой оценить МНК (Ŷ(t) - расчетные, смоделированные значения временного ряда);

3) оценить адекватность построенных моделей, используя свойства независимости остаточной компоненты, случайности и соответствия нормальному закону распределения (при использовании R/S-критерия взять табулированные границы 2,7 - 3,7);

4) оценить точность моделей на основе использования средней относительной ошибки аппроксимации;

5) по построенной модели осуществить прогноз спроса на следующие две недели (доверительный интервал прогноза считать при доверительной вероятности р = 70%);

6) фактические значения показателя, результаты моделирования и прогнозирования представить графически.

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

Решение:

Проверить наличие аномальных наблюдений.

Для выявления аномальных уровней временного ряда используем метод Ирвина, который предполагает использование следующей формулы:

, где

s_у - среднеквадратическое отклонение рассчитывается с использованием формул:

Находим:

= = = = 5,2

λ₂ = = 0,57

λ₃ = = 0,19

λ₄ = = 0,57

λ₅ = = 0,38

λ₆ = = 0,57

λ₇ = = 0,77

λ₈ = = 0,19

λ₉ = = 0,57

Расчетные значения λ_2, λ_3,и т.д. сравниваются с табличным значением критерия Ирвина λ_α,и если оказываются больше табличных, то соответствующее значение уt уровня ряда считается аномальным. Значение критерия Ирвина для уровня значимости α = 0,05, то есть с 5%-ной ошибкой,

λ_табл=1,5.

В результате получаем следующую таблицу:

Рис. 10 Нахождение аномальных наблюдений

Аномальных наблюдений во временном ряду нет, так как расчетные значения λ _t меньше табличного λ_табл=1,5 .

2. Построить линейную модель Y(t) = , параметры которой оценить МНК (Y(t) - расчетные, смоделированные значения временного ряда).

а) Построим линейную модель вида Y(t) = a₀ + a₁t по методу наименьших квадратов. Коэффициенты а₀ и а₁ линейной модели найдем из решения нормальной системы уравнений:

Известно, что

где:

Находим:

Коэффициент а₁=1,85 уравнения показывает, что в течение 9 последовательных недель спрос на кредитные ресурсы финансовой компании увеличивается в среднем на 1,85 млн. рублей.

Таким образом, получаем следующие данные:

Рис. 11 Построение линейной модели с помощью МНК

б) Оценим параметры модели (с помощью Анализ данных)

Построим линейную модель вида Y(t) = a₀ + a₁t с помощью однопараметрической модели регрессии Y(t). Для проведения регрессионного анализа выполняем следующие действия:

Выбрать команду Сервис →Анализ данных;
В диалоговом окне выбрать инструмент Регрессия (Рис.4), затем ОК;
В диалоговом окне Регрессия в поле Входной интервал Y вводится адрес одного диапазона ячеек, который представляет зависимую переменную. В поле Входной интервал X вводится адрес диапазона, который содержит значения независимой переменной t (Рис. 5);
Т.к. заголовки столбцов выделены тоже, то устанавливается флажок Метки;
Выбрать параметры вывода;
В поле График подбора поставить флажок;
В поле Остатки поставить необходимые флажки и нажать кнопку ОК.

Рис. 12 Анализ данных

Рис. 13 Регрессия

Используя пункт «Анализ данных» Регрессия получим коэффициенты уравнения регрессии согласно расчетам следующие: a₀ = 10,3 a₁= 1,85_.

Уравнение регрессии зависимости у_t (спроса на кредитные ресурсы финансовой компании) от времени t имеет вид:

Y(t) = 10,3 + 1,85t.

Рис. 14 Результат регрессионного анализа

б) Построим график эмпирического и смоделированного рядов:

Рис. 15 График эмпирического и смоделированного рядов

3. Оценить адекватность построенных моделей, используя свойства независимости остаточной компоненты, случайности и соответствия нормальному закону распределения (при использовании R/S-критерия взять табулированные границы 2,7 - 3,7).

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

Проверка равенства нулю математического ожидания уровней ряда остатков.

В моем случае = 0, поэтому гипотеза о равенстве математического ожидания значений остаточного ряда нулю выполняется.

Рис. 7 Проверка равенства нулю математического ожидания уровней ряда остатков

При проверке независимости (отсутствие автокорреляции) определяется отсутствие в ряду остатков систематической составляющей, например, с помощью d-критерия Дарбина—Уотсона по формуле. Численное значение коэффициента равно

d`= 4 – d

где:

= 0,99-(-0,16)=
= 0,14-0,99=
= 1,29-0,14=
= -2,56-1,29=
= -1,41-(-2,56)=
= 0,74-(-1,41)=
= -0,11-0,74=
= 1,04-(-0,11)=

d`= 4 – 2,03=1,97

Рис. 8 Проверка независимости

Если d попадает в интервал от d₂ до 2 (для линейной модели при 10 наблюдениях можно взять в качестве критических табличных уровней величины d₁ = 1,08, d₂ = 1,36), это говорит об отсутствии в модели автокорреляции и модель адекватна по данному признаку.

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

_{Критерий
случайности отклонений
от тренда при уровне
вероятности 0,95}_{имеет вид:}

_{6 > 2}

Число поворотных точек = 6;

6>2 – неравенство выполняется, следовательно, свойство случайности выполняется.

Рис. 9 Проверка случайности уровней ряда остатков

Соответствие ряда остатков нормальному закону распределения определим при помощи RS-критерия:

(для N=10 и 5%-го уровня значимости границы критерия (2,7 – 3,7)), 3,03 попадает в указанный интервал, следовательно, свойство нормальности распределения выполняется.

Вывод: модель статистически адекватна (выполняются все условия из четырех).

4. Оценить точность моделей на основе использования средней относительной ошибки аппроксимации

Средняя относительная ошибка:

Двойственные оценки и их влияние на функционал 📙 Контрольная → 🆔 24805