Графический способ решения типовых задач оптимизации

Графический способ решения типовых задач оптимизации

Задача 1

Решить графическим методом типовую задачу оптимизации

Имеется два вида корма I и II, содержащие питательные вещества (витамины) S1 S2 и S3. Содержание числа единиц питательных веществ в 1 кг каждого вида корма и необходимый минимум питательных веществ приведены в таблице

Стоимость 1 кг корма I и II соответственно равна 4 и 6 ден. ед.

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

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

Построим экономико-математическую модель задачи:

Пусть - количество корма 1 вида;

- количество корма 1 вида;

Тогда общая стоимость:

Ограничения по необходимому минимуму питательных веществ:

S1

S2

S3

Построим ОДР задачи

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

Функциональные ограничения (неравенства) определяют область, являющуюся пересечением полуплоскостей с граничными прямыми:

I. 3x₁ + x₂=9

II. x₁ +2x₂=8. x₁ +6x₂=12

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

A(0;9) D(12;0)

B: пересечение I и II линий

x₁ + x₂=9

x₁ +2x₂=8

Решение данной системы B(2;3).

С: пересечение III и II линий

x₁ +2x₂=8

x₁ +6x₂=12

Решение данной системы C(6;1).

. Для определения направления движения к оптимуму построим вектор-градиент, соединив его вершину V (4;6) c началом координат О (0,0).

. Построим некоторую линию уровня 4x₁ +6x₂ = а. Пусть, например, а = 0.

. При максимизации ЦФ необходимо перемещать линию уровня в направлении вектор-градиента, а при минимизации - в противоположном направлении.

Предельная точка при минимизации является т. B(2;3), при максимизации предельной точки нет.

Max f(x) =+∞ целевая функция не ограничена, т.к. ОДР является незамкнутым выпуклым многоугольником в направлении оптимизации целевой функции.

min f(x) =4*2+6*3=26

Ответ: min f(x) =26, x₁=2 x₂=3; max f(x) =+∞

Дневной рацион должен состоять из 2 кг корма 1 типа и 3 кг корма 2 типа, при этом затраты будут минимальными и составят 26 ден. ед.

Задача 2

Использовать аппарат теории двойственности для экономико-математического анализа оптимального плана задачи линейного программирования

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

Требуется:

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

) сформулировать двойственную задачу и найти ее оптимальный план с помощью теорем двойственности;

) Пояснить нулевые значения переменных в оптимальном плане;

) на основе свойств двойственных оценок и теорем двойственности:

·  проанализировать использование ресурсов в оптимальном плане исходной задачи;

·        определить, как изменится выручка от реализации продукции и план ее выпуска, если запас сырья I вида увеличить на 5 ед., а II - уменьшить на 5 ед.;

·        определить целесообразность включения в план изделия четвертого вида ценой 7 у.е., если нормы затрат сырья 2, 4 и 3 единицы

Решение

. Сформулируем прямую оптимизационную задачу на максимум выручки от реализации готовой продукции:

Получим оптимальный план выпуска продукции:

Для этого приводим эту задачу к каноническому виду и решаем симплекс-методом с естественным базисом с оформлением расчетов в симплекс-таблицах:

КЗЛП имеет необходимое число единичных столбцов, т.е. обладает очевидным начальным опорным планом (0,0,0,1,1,1)

В симплекс-таблице 2 получен оптимальный опорный план, поскольку все симплекс-разности (оценки) ∆_j≥0 j = 1, 2, 3, 4, 5, 6 . Оптимальные значения переменных равны: x₁=0, x₂ =100 , x₃=230 (основные переменные), x₄= 0, x₅ =0, x₆ =20 (дополнительные переменные). Максимальное значение целевой функции равно 1350 ден.ед.

Оптимальный план =0,=100,=230, выручка составит 1350 ден.ед.

2. Проверим, как удовлетворяется система функциональных ограничений оптимальным планом X* = (х₁ = 0, х₂ =100, х₃ = 230)

+2*100+230=430

*0+0+2*230=460 (*)

+ 4*100=400<420

Значение целевой функции на этом плане равно

f(X) =3*0+2*100+5*230=200+1150=1350

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

Для нахождения оценок у₁ у₂, у₃ используем вторую теорему двойственности. Поскольку третье ограничение в (*) выполняется как строгое неравенство, то у₃ = 0. Так как х₃ > 0 и х₂> 0, то:

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

Вычислим значение целевой функции двойственной задачи:

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

Оптимальный план двойственной задачи   

3. Поясним нулевые значения переменных в оптимальном плане

=0, т.е. производить продукцию 1 вида нецелесообразно, т.к. на ее производство затрачивается большое количество ресурсов всех видов.

4. на основе свойств двойственных оценок и теорем двойственности:

·  проанализируем использование ресурсов в оптимальном плане исходной задачи:

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

В рассматриваемом примере увеличение запасов сырья I типа, на 1 привело бы к росту максимальной суммы выручки на у.е. (у₁ =), а увеличение сырьевых ресурсов II типа на 1 привело бы к росту максимальной суммы выручки на у.е. Тогда как увеличение сырьевых ресурсов III типа не повлияет на оптимальный план выпуска продукции и сумму выручки.

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

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

В данном случае недефицитным ресурсом является сырье III типа, поскольку у₃ = 0.

Острее ощущается дефицитность ресурса сырья II типа (у₂ =) - он более дефицитен, чем ресурс I типа (у₁ =1).

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

В нашем примере относительная заменяемость ресурсов определяется соотношением (нормой) :.

·  определим, как изменится выручка от реализации продукции и план ее выпуска, если запас сырья I вида увеличить на 5 ед., а II - уменьшить на 5 ед.:

Найдем пределы устойчивости двойственных оценок для сырьевых ресурсов I и II типов

После приведения задачи к канонической форме матрица А примет вид

С ненулевыми значениями в оптимальный план вошли , следовательно матрица А^* будет составлена из второго, третьего и шестого столбцов матрицы А

Для вычисления интервалов устойчивости необходимо найти обратную матрицу

D=A^*-1

При вычислении интервала устойчивости по формулам

Примем x₂^*=100=x_k=1, x₃^*=230=x_k=2, x₆^*=20= x_k=3

Интервал устойчивости первого ресурса сырье I типа

Интервал устойчивости

Интервал устойчивости второго ресурса сырье II типа

Интервал устойчивости

Определим, как изменится выручка от реализации продукции и план ее выпуска, если запас сырья I вида увеличить на 5 ед., а II - уменьшить на 5 ед. Эти изменения (430+5=435; 460-5=455) находятся в интервалах устойчивости двойственных оценок

План выпуска

x₁^*=103,75, x₂^*=27,5, x₃^*=5

Объем прибыли f(X) = 3*103,75+2*227,5+5*5=791,25 уменьшится на

,75 ден.ед.

·  определить целесообразность включения в план изделия четвертого вида ценой 7 у.е., если нормы затрат сырья 2, 4 и 3 единицы.

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

В рассматриваемом примере следует решить вопрос о целесообразности включения в план изделия пятого вида ценой 7 ден.ед, если нормы затрат сырья 2, 4 и 3 ден. ед.

невыгодно расширение ассортимента.

Задача 3

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

Промышленная группа предприятий (холдинг) выпускает продукцию трех видов, при этом каждое из трех предприятий группы специализируется на выпуске продукции одного вида: первое предприятие специализируется на выпуске продукции первого вида, второе предприятие - продукции второго вида; третье предприятие - продукции третьего вида. Часть выпускаемой продукции потребляется предприятиями холдинга (идет на внутреннее потребление), остальная часть поставляется за его пределы (внешним потребителям, является конечным продуктом). Специалистами управляющей компании получены экономические оценки а_ij (i=1,2,3; j=1,2,3) элементов технологической матрицы А (норм расхода, коэффициентов прямых материальных затрат) и элементов  вектора конечной продукции Y.

Требуется:

1) Проверить продуктивность технологической матрицы А=( а_ij) (матрицы коэффициентров прямых материальных затрат).

) Построить баланс (заполнить таблицу) производства и распределения продукции предприятий холдинга.

Решение:

1) проверим продуктивность матрицы А;

Для продуктивности матрицы А необходимо и достаточно, чтобы выполнялось условие (первый признак). Матрица (Е - А) неотрицательно обратима, т.е. существует обратная матрица (Е - А)^-1 и все ее элементы неотрицательны.

Матрица E-A неотрицательно обратима, значит матрица А продуктивна

2) построим баланс производства и распределения продукции предприятий холдинга.

Модель баланса производства и распределения продукции предприятия можно представить следующей системой уравнений:

Отсюда определяем валовую продукцию предприятий:

Распределение продукции между предприятиями на внутреннее потребление определяем из соотношения

 и т.д.

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

Задача 4

Исследовать динамику экономического показателя на основе анализа одномерного временного ряда

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

Требуется:

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

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

3) построить адаптивную модель Брауна Ŷ (t) = а₀ + a₁t с параметром сглаживания  = 0,4 и = 0,7; выбрать лучшее значение ;

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

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

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

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

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

Проверим наличие аномальных наблюдений, для чего построим график временного ряда

стоимость рацион производство распределение

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

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

При вычислении «вручную» по формуле

Промежуточные расчеты параметров линейной модели приведены в табл.

Уравнение регрессии зависимости у от t имеет вид

Y(t)=4.06+3.97t

3) построим адаптивную модель Брауна Y_p(t) = а₀ + a₁t с параметром сглаживания = 0,4 и  = 0,7; выберем лучшее значение ;

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

Рассмотрим один из таких методов - метод Брауна.

Расчетное значение в момент времени получается по формуле

где k - количество шагов прогнозирования (обычно k = 1).

Это значение сравнивается с фактическим уровнем, и полученная ошибка прогноза E(t)=Y(t) - Y_p(t) используется для корректировки модели. Корректировка параметров осуществляется по формулам:

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

a₀=4 a₁=4, При =0,4; 0,6

При =0,7; 0,3

4) оценим адекватность построенных моделей:

Для того чтобы модель была адекватна исследуемому процессу, ряд остатков E(t) должен обладать свойствами случайности, независимости последовательных уровней, нормальности распределения.

·  случайности остаточной компоненты по критерию пиков;

Проверку случайности уровней остаточной компоненты проводим на основе критерия поворотных точек. Для этого каждый уровень ряда E(t) сравниваем с двумя соседними. Если он больше (либо меньше) обоих соседних уровней, то точка считается поворотной и в гр. точки поворота табл. для этой строки ставится 1, в противном случае - 0. В первой и последней строке гр. ставится прочерк или иной знак, так как у этого уровня нет двух соседних уровней. Для линейной модели

Общее число поворотных точек в нашем примере равно р = 6.

Рассчитаем значение q:

.

Функция int означает, что от полученного значения берется только целая часть. При N = 9

.

Если количество поворотных точек р больше q, то условие случайности уровней выполнено. В нашем случае р = 6, q = 2, значит условие случайности уровней ряда остатков выполнено. Модель по этому критерию адекватна.

Для адаптивной модели Брауна =0,4

Общее число поворотных точек равно р = 6. Значение q=2.

p>q значит условие случайности уровней ряда остатков выполнено. Модель по этому критерию адекватна. Для адаптивной модели Брауна =0,7

Общее число поворотных точек равно р = 6. Значение q=2.

p>q значит условие случайности уровней ряда остатков выполнено. Модель по этому критерию адекватна.

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

Для линейной модели

Полученное значение сравним с табличным значением

Так как <то гипотеза принимается.

Для адаптивной модели Брауна =0,4

Полученное значение сравним с табличным значением

Так как <то гипотеза принимается.

Для адаптивной модели Брауна =0,7

Полученное значение сравним с табличным значением

Так как <то гипотеза принимается.

·  независимости уровней ряда остатков по d-критерию (в качестве критических используйте уровни d₁ = 1,08 и d₂ =1,36) или по первому коэффициенту корреляции, критический уровень которого r(1) = 0,36;

Проверку проводим двумя методами:

) по d-критерию;

) по первому коэффициенту автокорреляции r(1).

Для линейной модели

)  = 22.01/6.82 = 3.23

Примечание. В случае если полученное значение больше 2, значит имеет место отрицательная автокорреляция. В таком случае величину d уточняют, вычитая полученное значение из 4.

Уточним величину d=4-3.23=0.77

Полученное (или уточненное) значение d сравнивают с табличными значениями d1 и d2. Для нашего случая d1=l,08, a d2=1.36.

Если 0<d<d1, то уровни автокоррелированы, то есть зависимы, модель неадекватна.

Если d1<d<d2, то критерий Дарбина-Уотсона не дает ответа на вопрос о независимости уровней ряда остатков. В таком случае необходимо воспользоваться другими критериями (например, проверить независимость уровней по первому коэффициенту автокорреляции).

Если d2<d<2 , то уровни ряда остатков являются независимыми.

В нашем случае 0.77<1.08, следовательно, то уровни ряда остатков являются зависимыми, модель неадекватна.

)  = -4,21/6.82 = -0.62

Если модуль рассчитанного значения первого коэффициента автокорреляции меньше критического значения |r(1)|<r_таб, то уровни ряда остатков независимы. Для нашей задачи критический уровень r_таб = 0,36. Имеем: |r(1)| = 0,62 > r_таб = 0,36, значит уровни зависимы, модель неадекватна

Для адаптивной модели Брауна =0,4

1)  =52.08/10.32=3,28=4-3.28=0.72

В нашем случае 0.72<1.08, следовательно, то уровни ряда остатков являются зависимыми, модель неадекватна.

)  =-10.32/15.87=-0.65

Имеем: |r(1)| = 0,65 > r_таб = 0,36, значит уровни зависимы, модель неадекватна по этому критерию

Для адаптивной модели Брауна =0,7

1) =109.30/32.42=3,37

d=4-3.37=0.63

В нашем случае 0.63<l,08, следовательно, то уровни ряда остатков являются зависимыми, модель неадекватна.

)  =-23.13/32.42=-0.713

Имеем: |r(1)| = 0,713 > r_таб = 0,36 - значит уровни зависимы, модель неадекватна по этому критерию

·  нормальности распределения остаточной компоненты по R/S-критерию с критическими уровнями 2,7-3,7;

Рассчитаем значение RS:

RS = (E_max-E_min)/ S,

где E_min - максимальное значение уровней ряда остатков E(t);

E_max - минимальное значение уровней ряда остатков E(t)

S - среднее квадратическое отклонение.

Для линейной модели

Emax=       1,18=          -0,96Emin = 2,13= 0,92= 2,31

Полученное значение RS сравнивают с табличными значениями, которые зависят от количества точек N и уровня значимости. Для N=9 и 5%-го уровня значимости значение RS для нормального распределения должно находиться в интервале от 2,7 до 3,7.

Так как 2.31<2,7, полученное значение RS не попало в заданный интервал. Значит, уровни ряда остатков не подчиняются нормальному распределению, модель неадекватна.

Для адаптивной модели Брауна =0,4

E max = 2,02min = -1,80max - Emin = 3,82 = 1,41

RS = 2,72

Так как 2,7<2,72<3.7, полученное значение RS попало в заданный интервал. Значит, уровни ряда остатков подчиняются нормальному распределению, модель адекватна по этому критерию.

Для адаптивной модели Брауна =0,7

Emax = 2,50= -2,54- Emin = 5,04= 2,01, RS = 2,50

Так как 2,5<2.7, полученное значение RS непопало в заданный интервал. Значит, уровни ряда остатков не подчиняются нормальному распределению, модель неадекватна по данному критерию.

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

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

где т - число параметров модели, и среднюю относительную ошибку аппроксимации -

Если ошибка не превосходит 15%, точность модели считается приемлемой. В общем случае допустимый уровень точности, а значит и надежности устанавливает пользователь модели, который в результате содержательного анализа проблемы выясняет, насколько она чувствительна к точности решения и насколько велики потери из-за неточного решения.

Для линейной модели (Неадекватная модель)

Условия точности выполнены

Для адаптивной модели Брауна =0,4 (Неадекватная модель)

Условия точности выполнены

Для адаптивной модели Брауна =0,7 (Неадекватная модель)

Условия точности выполнены

Показатели точности лучше при =0,4 меньше, чем при =0,7, значит можно сделать вывод, что значение =0,4 лучше.

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

Для линейной модели

Для учета случайных колебаний при прогнозировании рассчитываются доверительные интервалы, зависящие от стандартной ошибки , горизонта прогнозирования k, длины временного ряда n и уровня значимости прогноза а. Будущие значения Y_n+k c вероятностью (1 - а) попадут в интервал

Примем значение уровня значимости а = 0,3, а значит, доверительную вероятность - 70%. В этом случае критерий Стьюдента (при v= n- 2 = 7) равен

ta,v ⁼ 1.12.

Получим интервальный прогноз

Построение прогноза по модели Брауна

Для прогнозирования используется модель, полученная на последнем шаге (при t = N). Прогнозные оценки по модели (5.3.1) получаются путем подстановки в нее значения k = 1, 2; а интервальные - по тем же формулам, что и для кривых роста:

Для адаптивной модели Брауна =0,4

Для адаптивной модели Брауна =0,7