Расчет оптимального плана с помощью теорем двойственности. Типовые задачи оптимизации

Требуется:

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

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

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

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

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

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

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

Решение. 1. Данная задача оптимизации является задачей линейного программирования. Обозначим количество выпускаемых видов продукции А, Б, В, Г, Д соответственно как х₁, х₂, х₃, х₄, х₅ . Целевой функцией задачи является общая стоимость выпускаемой продукции, которая должна быть наибольшей. Число ограничений задачи равно числу ресурсов, используемых для изготовления изделий -- 3. Дополнительно вводится условие неотрицательности переменных. Зная цены изделий, нормы их расхода и запасы ресурсов, формулируем математическую модель исходной задачи линейного программирования:

Задачу оптимизации решаем с помощью надстройки «Поиск решения» табличного процессора EXCEL (меню «Сервис»):

(для копирования снимка окна в буфер обмена данных используется комбинация клавиш Alt + Print Screen).

Использование надстройки позволило получить значения переменных оптимального плана выпуска изделий: Х*=(0; 0; 400; 550). Целевая функция имеет наибольшее для данных условий задачи значение f(X*)=9000 (прил. 1).

Таким образом, для получения наибольшей выручки от реализации продукции следует производить x₃*=400 изделий В, x₄*=550 изделий Д и не производить изделия А и Б (x₁*=0 и x₂*=0).

2. Обозначим двойственные оценки ресурсов I, II, III как y₁, y₂, y₃ соответственно. Целевой функцией двойственной задачи является общая стоимость запасов ресурсов в двойственных оценках, которая должна быть наименьшей. Число ограничений двойственной задачи равно числу переменных исходной задачи -- 4. Математическая модель двойственной задачи имеет вид:

При решении исходной задачи с помощью EXCEL одновременно определяется и оптимальное решение двойственной задачи. В «Отчете по устойчивости» (прил. 2) приводятся теневые цены ресурсов: y₁*=3; y₂*=1,5; y₃*=0.

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

совпадает (в пределах погрешности округления) с наибольшим значением целевой функции исходной задачи f(X*).

3. Выпуск изделий А и Б невыгоден для данных условий задачи. Это объясняется тем, что стоимость ресурсов на изготовление единицы этой продукции в теневых ценах превышает цену реализации:

Продукция А:

Продукция Б:

4. Проанализируем использование ресурсов в оптимальном плане. Для этого подставим в ограничения исходной задачи значения переменных оптимального плана Х*=(0; 0; 400; 550) и проверим выполнение неравенств:

Видно, что ресурсы I и II используются в оптимальном плане полностью, т. е. являются дефицитными. На это обстоятельство указывает и то, что теневые цены этих ресурсов больше нуля (y₁*>0; y₂*>0). Самым дефицитным является ресурс I, так как он имеет наибольшую теневую цену (y₁*=3); следующим по дефицитности идет ресурс II (y₂*=1,5).

Ограниченные запасы дефицитных ресурсов I, II сдерживают рост объемов выпускаемой продукции и наибольшей выручки от ее реализации. Увеличение объема ресурса I на одну единицу при неизменных объемах других ресурсов ведет к росту наибольшей выручки на 3ден.ед., увеличение объема ресурса II на единицу -- на 1,5 ден.ед.

Ресурс III является недефицитными (y₃*=0), т. е. избыточными в оптимальном плане. Увеличение объемов этих ресурсов не повлияет на оптимальный план выпуска продукции и не увеличит ее общую стоимость.

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

При этом «новая» наибольшая выручка составит

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

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

экономический математический линейный программирование

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

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

Требуется:

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

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

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

1. Матрица коэффициентов прямых затрат A является квадратной матрицей порядка n=3. Вычислим матрицу коэффициентов полных затрат

,

где -- единичная матрица порядка n=3. С помощью встроенной функции EXCEL «МОБР» получим (см. прил.):

Все элементы матрицы коэффициентов полных затрат B неотрицательны, следовательно матрица коэффициентов прямых затрат A продуктивна.

2. Вычисляем вектор валовой продукции X по формуле . С помощью встроенной функции EXCEL «МУМНОЖ» получим (см. прил.):

Распределение продукции между предприятиями (внутреннее потребление) определяется из соотношения . Получим (см. прил.):

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

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

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

Требуется:

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

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

3. Построить адаптивную линейную модель Брауна.

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

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

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

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

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

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

,

где -- стандартное отклонение уровней ряда.

Стандартное отклонение определяется с помощью встроенной функции EXCEL «СТАНДОТКЛОН»: S_y6,73 млн. руб. (прил. 1). Расчет значений ?_t для всех уровней ряда, начиная со второго, приведен в прил. 1. Табличное значение критерия Ирвина для уровня значимости =0,05 и длины временного ряда n=9 составляет =1,5. Видно, что ни одно из значений _t не превышает критического значения, что свидетельствует об отсутствии аномальных наблюдений.

2. Линейную трендовую модель строим с помощью надстройки EXCEL «Анализ данных… Регрессия» (меню «Сервис»):

Уравнение линейного тренда имеет вид:

.

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

Коэффициент детерминации уравнения R²0,967 (см. «R-квадрат» в прил. 1) превышает критическое значение для =0,05 и n=9, что свидетельствует о статистической значимости линейной модели и наличии устойчивого линейного тренда во временном ряду. Само значение R² показывает, что изменение спроса во времени на 96,7 % описывается линейной моделью.

4. Оценим адекватность линейной модели. Рассчитанные по модели значения спроса , остатки и их график были получены в EXCEL одновременно с построением модели.

Случайность остаточной компоненты проверим по критерию поворотных точек. Для этого каждый уровень ряда остатков сравниваем с двумя соседними -- предыдущим и последующим. Если этот уровень одновременно больше или одновременно меньше обоих соседних уровней, то точка считается поворотной (на графике остатков такие уровни выглядят как «пики» и «впадины»). В нашем случае общее число поворотных точек в ряду остатков составляет p=5.

Критическое число поворотных точек для =0,05 и n=9 определяется по формуле

Так как , остатки признаются случайными.

Проверим независимость остатков с помощью критерия Дарбина-Уотсона. Для расчета d_статистики используется выражение, составленное из встроенных функций EXCEL:

=СУММКВРАЗН(«Остатки 2, …, n»; «Остатки 1, …, n-1»)/СУММКВ(«Остатки 1, …,n»)

d_статистика имеет значение:

.

Критические значения d_статистики для =0,05 и n=9 составляют: d₁=0,82; d₂=1,32. Так как выполняется условие

,

остатки признаются независимыми (автокорреляция остатков не выявлена).

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

.

Для расчета коэффициента автокорреляции использовалось выражение, составленное из встроенных функций EXCEL:

=СУММПРОИЗВ(«Остатки 2, …, n»; «Остатки 1, …, n-1»)/СУММКВ(«Остатки 1, …,n»)

Критическое значение коэффициента автокорреляции для =0,05 и n=9 составляет 0,666. Так как коэффициент автокорреляции не превышает по абсолютной величине критическое значение, то это еще раз указывает на отсутствие автокорреляции в остатках.

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

(определено с помощью встроенной функции «СРЗНАЧ». Поэтому гипотеза о равенстве математического ожидания значений остаточного ряда нулю не отклоняется.

Нормальный закон распределения остатков проверяем с помощью R/S-критерия, определяемого по формуле

,

где e_max=0,98; e_min=(-0,82) -- наибольший и наименьший остатки соответственно (определялись с помощью встроенных функций «МАКС» и «МИН»);

-- стандартное отклонение ряда остатков (определено с помощью встроенной функции «СТАНДОТКЛОН».

Критические границы R/S-критерия для =0,05 и n=9 заданы условием имеют табулированные границы: (R/S)₁=2,7 и (R/S)₂=3,7. Так как R/S-критерий попадает в интервал между критическими границами, то ряд остатков признается соответствующим нормальному закону распределения вероятностей.

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

5. Оценим точность линейной модели. Стандартная ошибка модели S_мод была определена одновременно с ее построением (см. «Стандартная ошибка» в прил. 1):

млн. руб.

Среднюю относительную ошибку аппроксимации находим по приближенной формуле:

%,

где млн. руб. -- средний уровень временного ряда (определен с помощью встроенной функции «СРЗНАЧ»; см. прил. 1).

Значение E_отн показывает, что предсказанные моделью значения спроса на кредитные ресурсы отличаются от фактических значений в среднем на 1,19 %. Модель имеет высокую точность.

6. Строим точечный и интервальный прогнозы спроса на 1 и 2 недели вперед.

Прогноз на 1 неделю вперед (период упреждения k=1):

1) Точечный прогноз :

млн. руб.

Среднее прогнозируемое значение спроса равно 15,23 млн. руб.

2) Интервальный прогноз с надежностью (доверительной вероятностью) =0,7:

млн. руб.,

где t_таб=1,12 -- табличное значение t-критерия Стьюдента для доверительной вероятности =0,7 и числа степеней свободы ; K_пр=1,24 -- коэффициент интервального прогноза для n=9 и k=1.

С вероятностью 70 % фактическое значение спроса на кредитные ресурсы будет находиться в интервале от 14,49 до 15,97 млн. руб.

Прогноз на 2 недели вперед (период упреждения k=2):

1) Точечный прогноз:

млн. руб.

Среднее прогнозируемое значение спроса равно 14,83 млн. руб.

2) Интервальный прогноз с надежностью =0,7:

млн. руб.,

где K_пр=1,31 -- коэффициент интервального прогноза для n=9 и k=2.

С вероятностью 70 % фактическое значение спроса на кредитные ресурсы будет находиться в интервале от 14,05 до 15,61 млн. руб.

7. График временного ряда спроса строим с помощью надстройки «Диаграмма» EXCEL. Предварительно выделяется блок ячеек «t» и «y_t» вместе с заголовками, а затем выбирается пункт меню «Вставка» «Диаграмма…»:

Далее строим линию линейного тренда (меню «Диаграмма» «Добавить линию тренда…» «Линейная»), и устанавливаем «Прогноз» вперед на 2 единицы и назад на 1 единицу, а также вывод на диаграмме уравнения тренда и коэффициента детерминации R²:

Точки точечного и интервального прогнозов наносим на график вручную.

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