Тема 3. Анализ оптимального плана 1. Эффективные и неэффективные ограничения в оптимальном плане. Эффективные и неэффективные ограничения в оптимальном. - презентация

1 Тема 3. Анализ оптимального плана 1. Эффективные и неэффективные ограничения в оптимальном плане. Эффективные и неэффективные ограничения в оптимальном плане Эффективные и неэффективные ограничения в оптимальном плане 2. Двойственные оценки и их анализ. Двойственные оценки и их анализ Двойственные оценки и их анализ 3. Анализ устойчивости оптимального плана. Анализ устойчивости оптимального плана Анализ устойчивости оптимального плана 4. Техника отладки оптимизационных моделей. Техника отладки оптимизационных моделей Техника отладки оптимизационных моделей © Н.М. Светлов, 2005Н.М. Светлов

2 Анализ оптимального плана / 9 0 (эфф.) / 3 0 (эфф.) 63,272 0 (неэфф.) 3, ,907 -5, / 9 0 (эфф.) (неэфф.) 8 1. Эффективные и неэффективные ограничения max 800·x ·x ·x 3 (руб./сут.) 1,01·x 1 + 1,01·x 2 + 9,45·x (ц/сут.) (1/5)·x 1 + (1/6)·x 2 21 (ч/сут.) (1/0,3)·x 3 16 (ч/сут.) x 1 90 (ц/сут.) x 2 10 (ц/сут.) x 3 0 (ц/сут.) x 1 = 90 x 2 = 18 x 3 = 3,272 ОграничениеСуммаОценкаОтклонение

3 Анализ оптимального плана3 1. Эффективные и неэффективные ограничения: экономические резервы Разница между свободным членом и суммой ограничения отражает величину экономических резервов соответствующего ресурса Разница между свободным членом и суммой ограничения отражает величину экономических резервов соответствующего ресурса Пример: ограничение 3 (1/0,3)·x 3 16 (ч/сут.) – 10, = 5,093 (ч/сут.) неиспользуемая мощность (резерв) В рамках описываемых моделью технологических возможностей использовать эти мощности экономически эффективным способом невозможно

4 Анализ оптимального плана4 1. Эффективные и неэффективные ограничения: экономические резервы Разница между свободным членом и суммой ограничения отражает величину экономических резервов соответствующего ресурса Разница между свободным членом и суммой ограничения отражает величину экономических резервов соответствующего ресурса Резерв не может быть использован в оптимальном плане, но указывает на возможность изменений в объекте моделирования (например, резерв ресурса можно продать или сдать в аренду) Резерв не может быть использован в оптимальном плане, но указывает на возможность изменений в объекте моделирования (например, резерв ресурса можно продать или сдать в аренду) Предполагаемые изменения в объекте моделирования можно отразить в модели, соответствующим образом изменив её. Предполагаемые изменения в объекте моделирования можно отразить в модели, соответствующим образом изменив её.

5 Анализ оптимального плана5 1. Эффективные и неэффективные ограничения: оценка адекватности модели Действительно ли избыточные ресурсы не могут быть использованы эффективно и с пользой? Действительно ли избыточные ресурсы не могут быть использованы эффективно и с пользой? Существует ли объяснение тому, что на самом деле избыточны другие ресурсы? Не следует ли отразить это объяснение в модели? Существует ли объяснение тому, что на самом деле избыточны другие ресурсы? Не следует ли отразить это объяснение в модели? Почему модель показывает такие большие резервы? Почему модель показывает такие большие резервы? С наличием резервов связаны инвестиционные возможности. Заметил ли их кто-нибудь, кроме разработчика модели? Если нет, почему? С наличием резервов связаны инвестиционные возможности. Заметил ли их кто-нибудь, кроме разработчика модели? Если нет, почему?

6 Анализ оптимального плана6 2. Двойственные оценки Рассмотрим задачу с точки зрения возможного изменения её параметров A, c и b Вектора x здесь нет

7 Анализ оптимального плана7 2. Двойственные оценки Для эффективного ограничения отлична от нуля Для неэффективного ограничения равна нулю

8 Анализ оптимального плана8 2. Двойственные оценки Двойственная оценка (д.о.) ограничения i показывает, на сколько изменится целевая функция при единичном изменении объёма ограничения, т.е величины b i. Двойственная оценка (д.о.) ограничения i показывает, на сколько изменится целевая функция при единичном изменении объёма ограничения, т.е величины b i. Изменение целевой функции будет соответствовать д.о. по крайней мере при достаточно малом изменении величины b i (изменение на единицу может оказаться слишком большим). Изменение целевой функции будет соответствовать д.о. по крайней мере при достаточно малом изменении величины b i (изменение на единицу может оказаться слишком большим). Изменение целевой функции может соответствовать д.о. при изменении b i только в одну сторону. Изменение целевой функции может соответствовать д.о. при изменении b i только в одну сторону. Единица измерения двойственной оценки – Единица измерения двойственной оценки – [единица измерения целевой функции] [единица измерения ограничения i]

9 Анализ оптимального плана9 2. Двойственные оценки Примеры: при увеличении объёма переработки молока в смену со 140 до 141 ц/сут. целевая функция увеличится на p 1 =444,4 руб. и составит ,2+444,4=103286,7 руб. при увеличении объёма переработки молока в смену со 140 до 141 ц/сут. целевая функция увеличится на p 1 =444,4 руб. и составит ,2+444,4=103286,7 руб. при увеличении времени использования оборудования для фасовки молока и кефира с 21 до 22 ч/сут. целевая функция увеличится на p 2 =3006,7 руб. и составит ,2+3006,7=105898,9 руб. при увеличении времени использования оборудования для фасовки молока и кефира с 21 до 22 ч/сут. целевая функция увеличится на p 2 =3006,7 руб. и составит ,2+3006,7=105898,9 руб. увеличение времени использования оборудования для фасовки сметаны не повлияет на целевую функцию (p 3 =0): в самом деле, и без того из 16 возможных часов его работы используются только 9 ч. 54 мин. увеличение времени использования оборудования для фасовки сметаны не повлияет на целевую функцию (p 3 =0): в самом деле, и без того из 16 возможных часов его работы используются только 9 ч. 54 мин.

10 Анализ оптимального плана10 2. Двойственные оценки Примеры: включение в модель новой переменной «сметана диетическая» в предположении, что на производство 1 ц сметаны обезжиренной требуется 6 ц молока, производительность при фасовке такая же, что и для обычной сметаны, а цена реализации составляет 3200 руб./ц, приведёт к изменению целевой функции (в расчёте на 1 ц): включение в модель новой переменной «сметана диетическая» в предположении, что на производство 1 ц сметаны обезжиренной требуется 6 ц молока, производительность при фасовке такая же, что и для обычной сметаны, а цена реализации составляет 3200 руб./ц, приведёт к изменению целевой функции (в расчёте на 1 ц): –6 ц мол./ц см. · 444,4 руб./ц мол. = –2666,4 руб./ц см. – за счёт изменения плана использования молочного сырья ; –6 ц мол./ц см. · 444,4 руб./ц мол. = –2666,4 руб./ц см. – за счёт изменения плана использования молочного сырья ; – (1/0,3ц см./ч) · 0 руб./ч = 0 руб./ц см. – за счёт изменения плана использования оборудования для фасовки сметаны ; – (1/0,3ц см./ч) · 0 руб./ч = 0 руб./ц см. – за счёт изменения плана использования оборудования для фасовки сметаны ; руб./ц см. – за счёт выручки от реализации ; руб./ц см. – за счёт выручки от реализации ; итого +533,6 руб./ц сметаны. итого +533,6 руб./ц сметаны. Итак, освоение производства диетической сметаны – выгодное предприятие. Итак, освоение производства диетической сметаны – выгодное предприятие.

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

12 Анализ оптимального плана12 3. Анализ устойчивости оптимального плана Цель анализа – определить возможные изменения модели, при которых не меняется набор ненулевых (базисных) переменных и эффективных ограничений. Цель анализа – определить возможные изменения модели, при которых не меняется набор ненулевых (базисных) переменных и эффективных ограничений. Значение целевой функции, а в ряде случаев – базисных переменных или ненулевых двойственных оценок при таких изменениях может меняться. Смысл анализа – выявить границы изменений в моделируемом объекте, которые не повлекут за собой сложных организационно-экономических мероприятий по освоению новых видов деятельности (не ограничиваясь изменением размеров имеющихся) и изысканию новых каналов снабжения ресурсами. Смысл анализа – выявить границы изменений в моделируемом объекте, которые не повлекут за собой сложных организационно-экономических мероприятий по освоению новых видов деятельности (не ограничиваясь изменением размеров имеющихся) и изысканию новых каналов снабжения ресурсами.

13 Анализ оптимального плана13 3. Cимплексные таблицы Решаем…

14 3. Последняя симплексная таблица Мо- локо Ке- фир Сме- тана Откл. бал. мол. Откл. фас. мол. Откл. фас. смет. Откл. мин. мол. Откл. мин. кеф. Иск. мин. мол. Иск. мин. кеф. Своб. чл. / u i / знач. пер. Баланс молока v 1j 61,21-1,28 Время фасовки молока+кефира - 0,35 2,1410,07 - 0,07 5,093 Время фасовки сметаны v 3j 10,11 - 0,64 - 0,02 0,023,272 Минимум пастер. молока 1190 Минимум кефира v 5j 161,2-1,218 Целевая функция / w j / оценки Д.о. p i Строка i (2) Пер. x j Столбец j (3)

15 Анализ оптимального плана15 3. Оптимальный план остаётся неизменным, если: коэффициент целевой функции при небазисной переменной меняется в пределах от – до –w j ; коэффициент целевой функции при небазисной переменной меняется в пределах от – до –w j ; коэффициент целевой функции при базисной переменной меняется в пределах коэффициент целевой функции при базисной переменной меняется в пределах Базисная переменная, соответствующая i-й строке последней симплексной таблицы Остальные обозначения - на предыдущем слайде

16 3. Анализ устойчивости оптимального плана: базисный коэффициент ЦФ Мо- локо Ке- фир Сме- тана Откл. бал. мол. Откл. фас. мол. Откл. фас. смет. Откл. мин. мол. Откл. мин. кеф. Иск. мин. мол. Иск. мин. кеф. Своб. чл./зна ч. пер. Баланс молока 61,21-1,28 Время фасовки молока+кефира - 0,35 2,1410,07 - 0,07 5,093 Время фасовки сметаны 10,11 - 0,64 - 0,02 0,023,272 Минимум пастер. молока 1190 Минимум кефира 161,2-1,218 Целевая функ- ция / оценки max –4 200 min 4 688,6 min max -

17 Анализ оптимального плана17 3. Оценки оптимального плана остаются неизменными, если: свободный член эффективного ограничения типа «меньше либо равно», меняется в пределах свободный член эффективного ограничения типа «меньше либо равно», меняется в пределах Эффективное ограничение, отклонение по которому соответствует j-му столбцу последней симплексной таблицы Остальные обозначения – слайд 15 Для типа «больше либо равно» минус заменить на плюс

18 3. Анализ устойчивости оптимального плана: свободный член ограничения Мо- локо Ке- фир Сме- тана Откл. бал. мол. Откл. фас. мол. Откл. фас. смет. Откл мин. мол. Откл. мин. кеф. Иск. мин. мол. Иск. мин. кеф. Своб. чл./зна ч. пер. Баланс молока 61,21-1,28 Время фасовки молока+кефира - 0,35 2,1410,07 - 0,07 5,093 Время фасовки сметаны 10,11 - 0,64 - 0,02 0,023,272 Минимум пастер. молока 1190 Минимум кефира 161,2-1,218 Целевая функ- ция / оценки min6,667min72,757 max–109,1 max –90 min15 4-я дополнительная4-е ограничение

19 Анализ оптимального плана19 3. Анализ устойчивости оптимального плана может также проводиться по отношению к: Пределу введения в базис небазисной переменной при неизменных оценках и соответствующему изменению значений базисных переменных Пределу введения в базис небазисной переменной при неизменных оценках и соответствующему изменению значений базисных переменных Границам изменения технико-экономического коэффициента при небазисной переменной, не влияющего на значения переменных и двойственных оценок Границам изменения технико-экономического коэффициента при небазисной переменной, не влияющего на значения переменных и двойственных оценок Введению в оптимальный план новых переменных и ограничений (для этой цели достаточно исходной симплексной таблицы) Введению в оптимальный план новых переменных и ограничений (для этой цели достаточно исходной симплексной таблицы) (см. рекомендуемую литературу)

20 Анализ оптимального плана20 Все ли коэффициен- ты при этой переменной на месте?! Достаточно ли имеющихся ограничений? 4. Техника отладки моделей: поиск причины неограниченности целевой функции Причины: Причины: Некоторые коэффициенты пропущены либо приписаны не той переменной, которой они должны соответстововать Некоторые коэффициенты пропущены либо приписаны не той переменной, которой они должны соответстововать Ошибочные знаки некоторых ограничений Ошибочные знаки некоторых ограничений Неправильно задана целевая функция (в т.ч. min вместо max и наоборот) Неправильно задана целевая функция (в т.ч. min вместо max и наоборот) Поиск: Поиск: Иногда переменная, в коэффициентах при которой имеется ошибка, выдаёт себя чрезмерно большим значением Иногда переменная, в коэффициентах при которой имеется ошибка, выдаёт себя чрезмерно большим значением В противном случае: В противном случае: 1.Ограничиваем все переменные модели сверху значением, заведомо превышающим их ожидаемые значения в оптимальном плане 1.Ограничиваем все переменные модели сверху значением, заведомо превышающим их ожидаемые значения в оптимальном плане 2.Проверяем, существует ли ограничение, лимитирующее данную переменную 2.Проверяем, существует ли ограничение, лимитирующее данную переменную 3.Если нет – исправляем ошибку; в противном случае снимаем с этой переменной отладочное ограничение и переходим к п.1. В предположении, что переменные неотрицательны

21 Анализ оптимального плана21 4. Техника отладки моделей: причины несовместности системы ограничений Отрицательный результат эксперимента на модели (ошибкой не является) Отрицательный результат эксперимента на модели (ошибкой не является) Ошибка при расчёте значений коэффициентов или свободных членов модели Ошибка при расчёте значений коэффициентов или свободных членов модели Некоторые коэффициенты пропущены либо приписаны не той переменной, которой они должны соответствовать Некоторые коэффициенты пропущены либо приписаны не той переменной, которой они должны соответствовать Ошибочные знаки некоторых ограничений Ошибочные знаки некоторых ограничений

22 Анализ оптимального плана22 4. Техника отладки моделей: поиск причин несовместности системы ограничений Если эффективных ограничений мало – проверяем каждое из них на наличие вышеуказанных причин Если эффективных ограничений мало – проверяем каждое из них на наличие вышеуказанных причин В противном случае: В противном случае: 1. Проверяем на отсутствие типовых ошибок для модели данного вида 2. Обращаем внимание на группы связанных переменных, не вошедшие в базис 3. Освобождаем наиболее «подозрительное» из эффективных ограничений: Если решение оптимальное, ошибка в этом ограничении или в эффективных ограничениях, связывающих входящие в него переменные; Если решение оптимальное, ошибка в этом ограничении или в эффективных ограничениях, связывающих входящие в него переменные; Если нет – повторяем п.3. Если нет – повторяем п.3. Для многих моделей существуют характерные картины распределения значений переменных и двойственных оценок, типичные для определённой часто встречающейся ошибки Как правило, в этом случае ошибка – в ограничениях, связывающих эти переменные

23 Анализ оптимального плана23 4. Техника отладки моделей Несовместность никогда не может быть вызвана: Несовместность никогда не может быть вызвана: ошибкой в целевой функции; ошибкой в целевой функции; ошибкой в неэффективном ограничении ошибкой в неэффективном ограничении Неограниченность никогда не может быть вызвана ошибкой в величине свободных членов Неограниченность никогда не может быть вызвана ошибкой в величине свободных членов

24 Анализ оптимального плана24 4. Техника отладки моделей: неадекватное оптимальное решение Причины те же, что и при несовместности/неограниченности Причины те же, что и при несовместности/неограниченности Поиск ошибок: сравнение оптимального решения ( значения переменных, объёмы использования ресурсов и их эффективность ) с фактическим состоянием моделируемой системы и объяснение причин наблюдаемых различий Поиск ошибок: сравнение оптимального решения ( значения переменных, объёмы использования ресурсов и их эффективность ) с фактическим состоянием моделируемой системы и объяснение причин наблюдаемых различий В моделируемой системе должны существовать реальные возможности освоить оптимальный план В моделируемой системе должны существовать реальные возможности освоить оптимальный план Сопоставление модели с реальностью может указать на ограничения, в реальности препятствующие освоению оптимального плана, но не отражённые в модели. Сопоставление модели с реальностью может указать на ограничения, в реальности препятствующие освоению оптимального плана, но не отражённые в модели.

25 Литература Основная Основная Математическое моделирование экономических процессов в сельском хозяйстве / Гатаулин А.М., Гаврилов Г.В. и др. М.: Агропромиздат, глава 5. Математическое моделирование экономических процессов в сельском хозяйстве / Гатаулин А.М., Гаврилов Г.В. и др. М.: Агропромиздат, глава 5. Презентация: Презентация: Дополнительная Дополнительная Практикум по математическому моделированию экономических процессов в сельском хозяйстве / А.Ф. Карпенко, В.А. Кардаш, Н.С. Низова и др.: 2-е изд. М.: Агропромиздат, Практикум по математическому моделированию экономических процессов в сельском хозяйстве / А.Ф. Карпенко, В.А. Кардаш, Н.С. Низова и др.: 2-е изд. М.: Агропромиздат, Вентцель Е.С. Исследование операций: Задачи, принципы, методология. М.: Высшая школа, Вентцель Е.С. Исследование операций: Задачи, принципы, методология. М.: Высшая школа, Воркуев Б.Л. Анализ решений экономико-математических моделей. М.: Изд-во МГУ, Воркуев Б.Л. Анализ решений экономико-математических моделей. М.: Изд-во МГУ, 1987.