Оптимизация дохода с учетом охраны окружающей среды

Для выпуска двух видов продукции используется 4 вида ресурсов, запасы которых соответственно равны 48, 36, 35 и 11,2 единицы.

Затраты ресурсов на производство единицы каждой продукции заданы в таблице

3,5
	1,4

Доходы от реализации продукции равны С₁ и С₂. Производство единицы продукции i-го вида связано с выбросом вредных веществ в объеме H_i единиц загрязнения (i=1,2). Минимально допустимый суммарный объем производства – 6 единиц.

Параметры С₁ и С₂, H₁ H₂ заданы индивидуально.

 

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

1. Постройте множество допустимых решений Х.

2. Используя линейные функции свертки, найдите все Парето-оптимальные планы производства. Вычислите «характерные» значения весов α и 1-α (при которых решения неединственны)

3. Постройте множество оценок Y(X) в пространстве двух критериев (по точкам, в которые переходят вершины Х).

4. Найдите все Парето-оптимальные оценки, а по ним – соответствующие Парето-оптимальные решения. Убедитесь в совпадении с результатами п. 2.

8.2 Вопросы для оценки качества освоения дисциплины

 

• Почему симплекс-метод находит точное решение задачи ЛП за КОНЕЧНОЕ число шагов?
• Какова верхняя оценка максимального числа шагов до достижения решения?
• Почему реальное число шагов гораздо меньше этой оценки?
• Каковы две возможные причины отсутствия решений в задачах линейного программирования?
• Может ли достигаться максимум или минимум линейной целевой функции во внутренней точке множества допустимых решений?
• Может ли задача ЛП иметь ровно три оптимальных решения?
• Может ли задача ЛП иметь ровно три оптимальных базисных решения?
• Может ли оптимальное решение замкнутой транспортной задачи с целочисленными условиями (запасами и запросами) быть нецелочисленным?
• Дайте определение выпуклого множества. Докажите, что пересечение двух выпуклых множеств выпукло.
• Докажите «в лоб», исходя из определения выпуклости, что множество решений системы линейных неравенств Ax≤ выпукло.
• То же для множества решений СЛУ Ax=b
• Докажите, что локальный экстремум выпуклой функции на выпуклом множестве является и глобальным экстремумом.
• Докажите, что строго выпуклая функция имеет на выпуклом множестве не более одной точки экстремума.
• Может ли выпуклая функция иметь на выпуклом множестве ровно три точки максимума?
• Может ли выпуклая функция иметь на выпуклом множестве ровно три точки минимума?
• Справедливо ли утверждение: «выпуклая функция на выпуклом множестве имеет экстремум»?
• Справедливо ли утверждение: «выпуклая функция на выпуклом множестве имеет не более одного экстремума»?

• Сформулируйте двойственную задачу ЛП (для стандартной формы - с неравенствами). В каком случае двойственная задача совпадает с прямой задачей?
• Докажите, что задача ЛП, двойственная к двойственной, совпадает с исходной (для канонической формы).
• Сформулируйте 2-ю теорему двойственности в задаче ЛП (условия дополняющей нежесткости).
• Как найти оптимальное решение прямой задачи линейного программирования, если найдено оптимальное решение ее двойственной задачи?
• Сформулируйте необходимые и достаточные условия выпуклости и строгой выпуклости дважды дифференцируемой функции нескольких переменных (в терминах Гессиана).
• Сформулируйте теорему Куна-Таккера для задачи выпуклого программирования в дифференциальной форме.
• Сформулируйте достаточное условие существования глобального экстремума (теорема Вейерштрасса). Назовите возможные причины отсутствия оптимального решения, приведите примеры.
• Чем вызвана необходимость разработки и применения численных методов?
• Как выбирается длина шага в градиентном методе с полным шагом?
• В каких случаях градиентный метод медленно сходится?
• Сформулируйте и докажите достаточные условия оптимальности по Парето в форме линейной свертки (теорема 1).
• Может ли оптимальная по Парето оценка быть внутренней точкой множества достижимых оценок?
• Может ли оптимальное по Парето решение быть внутренней точкой множества лопустимых решений?
• Почему Парето-оптимальное решение оптимально по Слейтеру?
• Сформулируйте необходимые и достаточные условия оптимальности по Парето в многокритериальной задаче линейного программирования.
• Изложите метод последовательных уступок.

• Что такое среднеквадратическое решение? К какой задаче Математического Программирования сводится его вычисление в многокритериальной задаче ЛП?
• Что такое арбитражное решение Нэша, почему оно оптимально по Парето?
• Что такое лексикографическая оптимизация?
• В чем сущность метода целевого программирования? При каком определении расстояния в критериальном пространстве возможно решение задачи целевого программирования методами линейного программирования?
• Сформулируйте необходимые и достаточные условия оптимальности по Слейтеру (теорема Гермейера).
• В задаче многокритериальной оптимизации найдено решение, оптимальное по одному из критериев. В каком случае оно будет оптимальным по Слейтеру? По Парето?
• Как можно классифицировать виды неопределенности по типу доступной информации?
• Каковы основные принципы оптимальности (критерии выбора решений) в случае полной неопределенности?
• Особенности и недостатки критерия максиминного критерия Вальда.
• Каков смысл весового коэффициента в критерии Гурвица?
• Критерий минимаксного сожаления Сэвиджа.
• Принцип гарантированного результата в задачах линейного программирования.

 

 

Примеры заданий итогового контроля

Типовой вариант экзаменационной контрольной работы

Задача 1. Рассматривается задача математического программирования

 

 

0) Можно ли понизить размерность этой задачи? Если да, сделайте это и проведите обоснование.

1) Проверьте выполнение условий теоремы Вейерштрасса, сделайте вывод о существовании глобального минимума.

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

3) Проверьте выполнение условия Слейтера, поясните, зачем это нужно.

4) Найдите решение x* графическим методом.

5) Выпишите условия Куна-Таккера в дифференциальной форме в общем виде.

6) Проверьте выполнение этих условий в найденной в п. 4 точке x*, сделайте соответствующие выводы.

 

Задача 2. Дана функция .

1) Исследуйте функцию на экстремумы. Найдите точку минимума аналитически. Не забудьте доказать, что это именно минимум.

2) Если начальная точка имеет координаты (8;5), то сколько шагов потребуется сделать градиентным методом с наилучшим фиксированным шагом, чтобы расстояние от текущего приближения до точного решения было не больше 0,0001? В ответе можно «оставить логарифм без вычисления»

 

Задача 3. Шесть конкурсных проектов оценивались по четырем критериям (каждый критерий желательно максимизировать). Результаты представлены в таблице ниже.

а) Найдите все проекты, чьи оценки оптимальны по Парето.

б) Найдите все проекты, чьи оценки оптимальны по Слейтеру.

в) Какой проект следует выбрать, если коэффициенты важности критериев считать одинаковыми?

Таблица оценки проектов по четырем критериям

Критерий\проект	ФA	ИB	СC	ВD	УE	АF	Идеальная точка
Критерий 1
Критерий 2
Критерий 3
Критерий 4
Функция свертки

 

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

Используйте для расчетов «расстояний» до идеальной точки табличку ниже:

 

Критерий\проект	ФA	ИB	СC	УD	УE	FF
Критерий 1
Критерий 2
Критерий 3
Критерий 4
Maximum

Задача 4.

Вы можете использовать имеющиеся у Вас 100 тыс. руб. тремя альтернативными способами – срочный вклад в банк, вложение в инвестиционный фонд (ИФ) или приобретение акций. Доход от этих действий, однако, не во всех случаях известен заранее, поскольку зависит от мировой цены на нефть. Банк гарантирует 5% годовых при любых ценах на нефть. Доход от вложений в ИФ зависит от этих цен: при высоких, средних и низких ценах 25%, 15% и 10% соответственно от вложенной суммы за год. Предполагается, что доходы от акций составят соответственно 40%, 1% и -20% (потери). Найти максимальную гарантированную оценку прибыли и гарантирующее решение, решения по критериям Бернулли-Лапласа, Гурвича, Сэвиджа.

Сформулируйте указанные критерии и покажите, как они работают в данной задаче.

Задача 5.

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

Удельные затраты сырья и цены известны неточно, прогнозно, с точностью до заданного диапазона. Точно известны объемы запасов сырья. Все данные приведены в таблице.

 

Вид продукции	X1	X2	X3	Запасы сырья
Уд. расход сырья 1	1,89-2	4-5	0-0
Уд. расход сырья 2	2,1-3	3,01-4	43-50
Цены на продукцию	19-21	30-35	45-50

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

Требуется найти наилучший гарантированный план производства X₁*, X₂*, X₃*, который будет заведомо выполним и обеспечит максимум гарантированной оценки прибыли.

Указание. Задачу решить с использованием двойственной задачи.

1. Дайте формальное описание задачи (введя необходимые обозначения).

2. Опишите множество гарантированно допустимых планов.

3. Чему равна гарантированная оценка f прибыли при заданном плане?

4. Найдите максимальную гарантированную прибыль f* и оптимальный гарантирующий план X*, решив соответствующую задачу ЛП с использованием двойственной задачи и условий дополняющей нежесткости.

Теоретический вопрос.

В чем сущность метода целевого программирования? При каком определении расстояния в критериальном пространстве возможно решение задачи целевого программирования методами линейного программирования? Как формируется соответствующая задача?

9 Порядок формирования оценок по дисциплине

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

- письменная аудиторная контрольная работа (третий модуль, 70 мин),

- домашнее контрольное задание (четвертый модуль, неделя на исполнение)

- письменный экзамен (четвертый модуль, 90 мин).

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

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

О_{накопленная} = 0,2•О_{аудиторная} + 0,4•О_контр +0,4•О _{дом.задание}

 

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

Итоговая десятибалльная оценка успеваемости студента по дисциплине в целом определяется по формуле

О_{итоговая} = 0,5•О_{накопленная} + 0,5•О_{экзамен/зачет}

Перевод итоговой десятибалльной оценки в пятибалльную осуществляется по общепринятому в НИУ ВШЭ правилу:

не больше 3 – неудовлетворительно, 4,5 – удовлетворительно, 6, 7 – хорошо, 8,9,10 – отлично.

10 Учебно-методическое и информационное обеспечение дисциплины

Базовый учебник

1. А.В. Соколов, В.В. Токарев. Методы оптимальных решений. Т.1. Общие положения. Математическое программирование. Москва: ФИЗМАТЛИТ, 2010, 2011.
2. В.В. Токарев. Методы оптимальных решений. Т.2. Многокритериальность. Динамика. Неопределенность. Москва: ФИЗМАТЛИТ, 2010, 2011
3. Исследование операций в экономике. Под ред. Кремера Н.Ш. М.: ЮНИТИ, 2005.
4. Интрилигатор М. Математические методы оптимизации и экономическая теория. М.: Айрис-Пресс, 2002.

10.2 Основная литература

1. Ф.П. Васильев, А.Ю. Иваницкий. Линейное программирование. М. Факториал Пресс, 2008.
2. Ф.П. Васильев. Методы оптимизации. М. Факториал Пресс, 2005.
3. Ногин В.Д. Методы оптимальных решений. СПб, СПб филиал ГУ – ВШЭ, 2006.
4. Гольштейн Е.Г., Юдин Д.Б. Задачи линейного программирования транспортного типа. М.: Наука, 1969.
5. Вентцель Е.С. Исследование операций. Задачи, принципы, методология. М.: ВШ, 2001.
6. Подиновский В.И., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. М.: Физматлит, 2007.
7. Курицкий Б.Я. Поиск оптимальных решений средствами Excel 7.0. СПб., BHV, 1997.

10.3 Дополнительная литература

1. Ларичев О.И. Теория и методы принятия решений. / Учебник. М.: Логос, 2002.
2. Петров А.А., Поспелов И.Г., Шананин А.А. Опыт математического моделирования экономики. М., Энергоатомиздат, 1996.
3. Л.В. Канторович, А.Б. Горстко. Математическое оптимальное программирование в экономике. М.: Знание, 1968.
4. Дж. Данциг. Линейное программирование, его обобщения и применение. М.: Прогресс, 1966.
5. Подиновский В.В. Введение в теорию важности критериев в многокритериальных задачах принятия решений. М.: Физматлит, 2007.
6. Математические методы принятия решений в экономике. /Учебник. Под ред. Колемаева В.А. М.: Финстатинформ, 1999.
7. Лотов А.В. Введение в экономико-математическое моделирование / Учебное пособие. М.: Наука, Физматлит, 1984.
8. Хрестоматия по учебной дисциплине «Теория и методы принятия многокритериальных решений». Составитель В.В. Подиновский. М.: ГУ – ВШЭ, 2005.
9. Хазанова Л.Э. Математические методы в экономике: Учебное пособие. – М.:,БЕК, 2002.
10. Жуковский В.И., Молоствов В.С. Многокритериальное принятие решений в условиях неопределенности. М.: Международный НИИ проблем управления, 1988.
11. Дуброва А.М. и др. Моделирование рисковых ситуаций в экономике и бизнесе. М.: «Финансы и статистика», 2001.

 

Автор программы В.С.Молоствов

 

© В.С.Молоствов