Решение двойственных задач

Требуется:

1) Сформулировать

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

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

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

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

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

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

- оценить целесообразность включения в план изделия четвертого вида ценой 11ед., если нормы затрат ресурсов 8, 4, 20 и 6 ед.

Решение:

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

Введем условные обозначения:

х1 - норма расхода ресурсов на одно изделие I вида

х2 - норма расхода ресурсов на одно изделие II вида

х3 - норма расхода ресурсов на одно изделие III вида

Целевая функция имеет вид:

F =

Ограничения задачи имеют вид:

3 х1 + 6 х2 + 4 х3 2000

20 х1 + 15 х2 + 20 х3 15000

10 х1 + 15 х2 + 20 х3 7400

3 х2 +5 х3 1500

х1,2,3 0

Оптимальный план найдем через поиск решения в надстройках Microsoft Excel (рис. 1 и рис. 2)

Полученное решение означает, что максимальную выручку от реализации готовой продукции (4110 ед.) предприятие может получить при выпуске 520 единиц продукции I вида и 110 единиц продукции II вида.

Рис. 1 - Поиск оптимального плане

Рис. 2 - Поиск оптимального плана.

При этом трудовые ресурсы и сырье второго вида будут использованы полностью, тогда как из 15 000 единиц сырья первого вида будет использовано только 12 600 единиц, а из 1500 единиц оборудования будет задействовано только 550 единиц.Excel позволяет представить результаты поиска решения в форме отчета (рис.3).

Рис. 3 - Отчёт по результатам поиска оптимального плана

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

Число переменных в двойственной задаче равно числу функциональных ограничений в исходной задаче. Исходная задача содержит 4 функциональных ограничения: труд, сырье 1, сырье 2, оборудование. Следовательно, в двойственной задаче 4 неизвестных:

y1 - двойственная оценка ресурса «Труд»

y2 - двойственная оценка ресурса «Сырье 1»

y3 - двойственная оценка ресурса «Сырье 2»

y4 - двойственная оценка ресурса «Оборудования»

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

min g(y) = 2000 y1+15000 y2+7400 y3+1500 y4.

Необходимо найти такие «цены» на типы ресурсов (yi), чтобы общая стоимость используемых ресурсов была минимальной.

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

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

Каждое ограничение соответствует определенной норме использования ресурса на единицу продукции:

3 y1 + 20 y2 +10 y3 6;

6 y1 + 15 y2 + 15 y3 + 3 y410;

4 y1 + 20 y2 + 20 y3 + 5 y49.

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

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

= 0, тогда

y1(3 х1+ 6 х2+4 х3 - 2000) = 0;

y2(20 х1 + 15 х2 + 20 х3 - 15000) = 0;

y3(10 х1 + 15 х2 + 20 х3 - 7400) = 0;

y4(3 х2 + 5 х3 - 1500) = 0.

()* = (520;0;110)

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

y1(3*520+ 6*0+4*110 - 2000) = 0;

y2(20*520 + 15*0 + 20*110 - 15000) = 0;

y3(10*520 + 15*0 + 20 *110 - 7400) = 0;

y4(3 *0 + 5*110 - 1500) = 0.

Отсюда получим:

y1(2 000- 2 000) = 0;

y2 (12 600 - 15 000) = 0, т.к. 12 600 < 15 000, то y2 = 0;

y3 (7400-7400) = 0;

y4 (550-1500) = 0, т.к. 550 < 1500, то y4 = 0.

Далее воспользуемся вторым соотношением второй теоремы двойственности

, если >0, то

В нашей задаче х1=520 > 0 и х3 = 110 > 0, поэтому первое и третье ограничения двойственной задачи обращаются в равенства

х1(3 y1 + 20 y2 +10 y3 - 6) = 0;

х2(6 y1 + 15 y2 + 15 y3 + 3 y4 -10) = 0;

х3 (4 y1 + 20 y2 + 20 y3 + 5 y4 -9) = 0.

Решая систему уравнений

3*у1 + 20*у2+10у3-6=0

у2 = 0

4*у1 + 20*у2 + 20 у3 + 5*у4-9=0

у4 = 0,

получим у1 = 1,5, у2 = 0, у3 = 0,15, у4 = 0.

Необходимо проверить выполнение первой теоремы двойственности

g(y) = 2000 y1+15000 y2+7400 y3+1500 y4 = 2 000*1,5 + 7400 *0,15 = 4 110

f(x) = 6 х1 + 10 х2 + 9 х3 = 6*520+9*110 = 4 110.

Это означает, что оптимальный план двойственности определен верно.

Решение двойственной задачи можно найти, выбрав команду Поиск решения - Отчет по устойчивости в Excel (рис. 4).

Рис. 4 - Отчёт по устойчивости

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

2.1 Задание № 2.10

Фирма производит два безалкогольных напитка -- «Лимонад» и «Тоник». Однако объем производства ограничен количеством основного ингредиента и производственной мощностью имеющегося оборудования. Для производства 1 л «Лимонада» требуется 0,02 ч работы оборудования, а для производства 1 л «Тоника» -- 0,04 ч. Расход специального ингредиента составляет 0,01 кг и 0,04 кг на 1 л «Лимонада» и «Тоника» соответственно. Ежедневно в распоряжении фирмы имеется 24 ч времени работы оборудования и 16 кг специального ингредиента. Прибыль фирмы составляет 0,10 ден. ед. за 1 л «Лимонада» и 0,30 ден. ед. за 1 л «Тоника». Сколько продукции каждого вида следует производить ежедневно, если цель фирмы состоит в максимизации ежедневной прибыли? Построить экономико - математическую модель задачи, дать необходимые комментарии к ее элементам и получить решение графическим методом. Что произойдет, если решать задачу на минимум и почему?

Решение:

Введем следующие обозначения:

х1 - количество первого напитка («Лимонад»)

х2 - количество второго напитка («Тоник»)

Цена 1 л «Лимонада» таким образом составляет 0,1 х1 (ден. ед.), а цена 1 л «Тоника» составляет 0,3 х2 (ден. ед.). Т.к. нам необходимо максимизировать прибыль, получаем целевую функцию:

F = 0,1 х1 + 0,3 х2 max

Ограничения задачи имеют вид:

0,02х1 + 0,04 х2 24;

0,01х1 + 0,04 х2 16;

х1,2 0.

Построим прямые, соответствующие ограничениям задачи: первая прямая имеет вид 0,02х1 + 0,04 х2 = 24, решением ее служат точки (1200;0)

и (0;400); вторая прямая имеет вид 0,01х1 + 0,04 х2 = 16, решением ее служат точки (1600;0) и (0;600).

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

Рис. 5 - Область допустимых решений

На рисунке 5 серым цветом обозначена область допустимых значений. Для определения движения к оптимуму построим вектор-градиент. При максимизации функции движемся в направлении вектора-градиента.

Решая систему уравнений

0,02х1 + 0,04 х2 = 24;

0,01х1 + 0,04 х2 = 16.

Находим, что х1 = 800, х2 = 200.

max f(х1,х2) = 0,1 800 + 0,3 200 = 140 (ден. ед.)

Ответ: Прибыль будет максимальной, если производить 800 л. «Лимонада» и 200 л. «Тоника» ежедневно (х1 = 800, х2 = 200). Если задачу решать на min, то f(min)= ?, т.е. не имеет конечного оптимума, т.к. область допустимых значений не ограничена снизу.

2.2 Задание № 3.10

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

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

Табл. 2 - Временной ряд

Требуется:

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

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

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

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

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

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

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

Решение:

1) Используя метод Ирвина проверим наличие аномальных наблюдений:

, где - среднеквадратическое отклонение

Выполним все вычисления, используя MS Excel (рис. 6)

Рис. 6 - Вычисление

В результате получаем (рис. 7):

Рис. 7 - Результат вычисления

Так как по всем уровням t значение  не превосходит табличное 1,6, то аномальных наблюдений нет.

2) Построим линейную модель вида Y(t) = a0+a1t по методу наименьших квадратов.

Коэффициенты а0 и а1 линейной модели найдем по следующим формулам.

;

Построим следующую таблицу, используя MS Excel:

Рис. 8 - Вычисление

В результате получаем:

Рис. 9 - Результат вычисления

Уравнение регрессии зависимости Yt от tt имеет вид:

Y(t) = 31,3 + 2,4t

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

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

Рис. 11 - Получение коэффициента регрессии

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

Рис. 12 - Вывод итогов

Средствами MS Excel получены коэффициенты уравнения регрессии а0=31,3, а1=2,4

Уравнение регрессии имеет вид: Y(t) = 31,3+ 2,4t

Рис. 13 - График подбора

3) Для построения адаптивной модели Брауна воспользуемся схемой адаптивного прогнозирования.

Начальные оценки параметров получим по первым пяти точкам с помощью метода наименьших квадратов.

Рис. 14 - Начальные оценки параметров

;

;

а)

;

Рис. 15 - Расчет

б)

;

Рис. 16 - Расчет

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

При б = 0,4

При б = 0,7

Т.к. 38,67 < 65,82, то значение б= 0,4 лучше.

Строим модели:

Рис. 17 - Модели

4) Используя свойство случайности остаточной компоненты (по критерию пиков - поворотных точек) оценим адекватность моделей.

Рис. 18 - Оценка адекватности моделей

Количество поворотных точек сравнивается с величиной в квадратных скобках:

P >

P >

P > 2

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

Для оценки адекватности моделей используем свойство независимости остаточной компоненты.

Применим метод Дарбина - Уотсона. Критерий рассчитывается по формуле:

Рис. 19 - Вычисление

Получим:

Рис. 20 - Результат вычисления

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

Для модели Брауна с б = 0,4:

Для модели Брауна с б = 0,7:

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

Для линейной модели и модели Брауна с б = 0,4 значения d попадают в интервал (dв; 4 - dв), т.е. (1,36 < d < 2,64), значит гипотеза о независимости остаточной компоненты принимается.

Значение d модели Брауна с б = 0,7 попадает в интервал (4 - dн < d < 4), т.е. (2,92 < d < 4), поэтому принимается альтернативная гипотеза об отрицательной автокорреляции.

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

Используем  - критерий, где

R = Emax - Emin - размах выборки

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

для линейной модели: Emax = 1,7; Emin = -3,1

R = 1,7 - (-3,1) = 4,8

S =

=  = 3,2

Расчетное значение  - критерия попадает в интервал [2,7; 3,7], значит гипотеза о нормальном распределении ряда остатков принимается.

Для модели Брауна с б = 0,4: Emax = 2,0; Emin = -5,2

R = 2,0 - (-5,2) = 7,2

S =

=  = 3,3

Гипотеза принимается.

Для модели Брауна с б = 0,7: Emax = 5,3; Emin = -4,7

R = 5,3 - (-4,7) = 10,0

S =

=  = 3,4

Гипотеза принимается.

5) Для оценки точности моделей применим среднюю относительную ошибку аппроксимации:

Рис. 21 - Расчет

Для линейной модели: Eотн =

Для модели Брауна с б = 0,4: Eотн =

Для модели Брауна с б = 0,7: Eотн =

Так как для всех моделей ошибка не превосходит 15%, то их точность считается приемлемой.

6) Доверительный интервал:

Прогноз на неделю вперед:

- линейная модель:

Точечный прогноз: y = 31,3 + 2,4·10 = 55,3

Интервальный прогноз: нижняя граница = 55,3 - 1,95 = 53,35

верхняя граница = 55,3 + 1,95 = 57,25

- модель Брауна с б = 0,4:

Точечный прогноз: y = 52,9 + 2,4·1 = 55,3

Интервальный прогноз: нижняя граница = 55,3 - 2,9 = 52,4

верхняя граница = 55,3 + 2,9 = 58,2

- модель Брауна с б = 0,7:

Точечный прогноз: y = 53,0 + 2,7·1 = 55,7

Интервальный прогноз: нижняя граница = 55,7 - 3,8 = 51,9

верхняя граница = 55,7 + 3,8 = 59,5

Прогноз на две недели вперед:

- линейная модель:

Точечный прогноз: y = 31,3 + 2,4·11 = 57,7

Интервальный прогноз: нижняя граница = 57,7 - 2,1 = 55,6

верхняя граница = 57,7 + 2,1 = 59,8

- модель Брауна с б = 0,4:

Точечный прогноз: y = 52,9 + 2,4·2 = 57,7

Интервальный прогноз: нижняя граница = 57,7 - 3,0 = 54,7

верхняя граница = 57,7 + 3,0 = 60,7

- модель Брауна с б = 0,7:

Точечный прогноз: y = 53,0 + 2,7·2 = 58,4

Интервальный прогноз: нижняя граница = 58,4 - 4,0 = 54,4

верхняя граница = 58,4 + 4,0 = 62,4

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

- для линейной модели:

Рис. 22 - График линейной модели

- для модели Брауна с б = 0,4:

Рис. 23 - График модели Брауна с б = 0,4

- для модели Брауна с б = 0,7:

Рис. 24 - График модели Брауна с б = 0,7

2.3 Задание № 4.10

Мебельный салон продает наборы мебели для кухни по цене 50 тыс. руб. Годовой спрос составляет 2000 кухонных гарнитуров. Издержки на один заказ равны 2500 руб. Годовые издержки хранения составляют 15% его цены. Каков оптимальный размер заказа? Салон работает 300 дней в году. Постройте график циклов изменения запаса товара.

Решение:

Введем обозначения:

М - 2000 кухонных гарнитуров в год

Т - 300 дней

К - 2500 рублей

h - 15% от 50000 рублей = 7500 рублей

Оптимальный размер заказа найдем по следующей формуле:

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

Для этого найдем пропорцию:

365х = 30000

х = 82,2%

100х = 82,2 * 37

х = 30,41 30

Следовательно, = 30

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

Q = M * T => T = T = = 0,015 года

Рис. 25 - График циклов изменения запаса товара

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

двойственная задача линейная модель

1. Экономико-математические методы и модели: компьютерное моделирование: Орлова И.В., Половников В.А. Учеб. пособие. - М.: Вузовский учебник, 2012. - 365 с.

2. Экономико-математические методы и прикладные модели: Учеб. пособие для вузов; Под ред. В.В. Федосеева. - М.: ЮНИТИ, 2001. - 391 с.

3. Экономико-математические методы и прикладные модели. Методические указания по выполнению контрольной работы, темы и задачи. - М.: ВЗФЭИ, 2002. - 104 с.

4. Экономико-математические методы и прикладные модели. Задания для выполнения контрольной и лабораторной работ. - М.: ВЗФЭИ, 2007. - 40 с.

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