МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное образовательное учреждение
высшего профессионального образования
«Дальневосточный федеральный университет»
(ДВФУ)
ШКОЛА ЕСТЕСТВЕННЫХ НАУК
УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС ДИСЦИПЛИНЫ
Теория принятия решений
Специальность - 230102.65 «Автоматизированные системы обработки информации и управления»
Форма подготовки - очная
Школа естественных наук
Кафедра «Информационные системы управления»
курс 3 семестр 5/6
лекции 18/32 час.
практические занятия – 18/16 час.
консультации 1 раз в неделю
всего часов аудиторной нагрузки 84 час.
самостоятельная работа 86 час.
Курсовая работа - 6 семестр
всего 170 час.
контрольные работы 5
экзамен:6 семестр;
зачет 5 семестр
Учебно-методический комплекс составлен
в соответствии с требованиями государственного
образовательного стандарта высшего профессионального образования №224 тех/дс от 27 марта 2000 г.
Учебно-методический комплекс дисциплины обсужден на заседании кафедры «Информационные
системы управления», протокол № 1 от 01сентября 2011 г.
Заведующий кафедрой ____________ Сухомлинов А.И.
Составитель: С.П. Брязгина, ст. преподаватель
2
Структура учебно-методического комплекса дисциплины
1. Аннотация
2. Рабочая программа дисциплины
3. Материалы для практических и семинарских занятий
4. Материалы для организации самостоятельной работы студентов
5. Контрольно-измерительные материалы
6. Список литературы
7. Глоссарий
Аннотация
Учебно-методический комплекс дисциплины «Теория принятия решений» является
составной частью образовательной программы подготовки специалистовпо направлению
«Информатика и вычислительная техника», используемой в процессе преподавания и изучения этой дисциплины.
УМК дисциплины «Теория принятия решений» состоит из организационнометодических документов и учебно-методических материалов, обеспечивающих учебный
процесс по данной дисциплине и способствующих эффективному и результативному освоению студентами учебного материала дисциплины.
Основными целями данного УМК являются повышение качества учебного процесса и активизация самостоятельной деятельности студентов.
УМК дисциплины «Теория принятия решений» предназначендля студентов3 курсаподготовки специалистовпо образовательной программе «Автоматизированные системы
обработки информации и управления».
3
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное образовательное учреждение
высшего профессионального образования
«Дальневосточный федеральный университет»
(ДВФУ)
ШКОЛА ЕСТЕСТВЕННЫХ НАУК
РАБОЧАЯ ПРОГРАММА УЧЕБНОЙ ДИСЦИПЛИНЫ (РПУД)
«Т е о р и я п р и н я т и я р е ш е н и й »
Специальность - 230102.65 «Автоматизированные системы обработки информации и
управления»
Форма подготовки - очная
Школа естественных наук
Кафедра «Информационные системы управления»
курс 3 семестр 5/6
лекции 18/32 час.
практические занятия – 18/16 час.
консультации 1 раз в неделю
всего часов аудиторной нагрузки 84 час.
самостоятельная работа 86 час.
Курсовая работа - 6 семестр
всего 170 час.
контрольные работы 5
экзамен:6 семестр;
зачет 5 семестр
Рабочая программа составлена в в соответствии с требованиями государственного образовательного
стандарта высшего профессионального образования №224 тех/дс от 27 марта 2000 г.
Рабочая программа обсуждена на заседании кафедры «Информационные системы управления»
протокол № 10 от «29» июня 2011 г.
Заведующий кафедрой ____________
Составитель: С.П. Брязгина, ст. преподаватель
4
I. Рабочая программа пересмотрена на заседании кафедры:
Протокол от «_____» _________________ 201 г. № ______
Заведующий кафедрой _______________________ __________________
(подпись)
(И.О. Фамилия)
II. Рабочая программа пересмотрена на заседании кафедры:
Протокол от «_____» _________________ 201
г. № ______
Заведующий кафедрой _______________________ __________________
(подпись)
(И.О. Фамилия)
5
1. Цели и задачи дисциплины
В соответствии с Государственным образовательным стандартом по
специальности 230102 "Автоматизированные системы обработки информации
и управления" (АСОИУ) одной из основных задач деятельности инженера является создание, анализ и развитие моделей, используемых в разработках современных систем автоматизации.
Исходя из вышесказанного, целью дисциплины является математическая подготовка студентов в области теории принятия решений, системного
анализа и исследований операций. В результате изучения дисциплины студенты должны знать основные положения теории принятия решений; принципы системного подхода; методы решения задач скалярной оптимизации: линейное программирование, нелинейное (условное и безусловное) программирование, дискретные программирование; методы решения динамических задач, методы принятия решений в условиях неопределенности.
В результате изучения дисциплины студенты должны уметь формулировать и решать задачи оптимального проектирования с использованием методов теории принятия решений; а так же использовать пакеты и библиотеки
программ при принятии оптимальных решений.
2.
Место дисциплины в структуре ООП специалитета
Дисциплина «Теория принятия решений» строится на знаниях, полученных студентами при изучении дисциплин «Алгебра и геометрия», «Дискретная математика» и «Математический анализ» в объеме, предусмотренном
учебным планом специальности. Дисциплина связана с предшествующими ей
дисциплинами «Введение в специальность», «Высшая математика», «Математические модели информационных процессов и управления» и со всеми последующими дисциплинами специальной подготовки.
3. Компетенции обучающегося, формируемые в результате освоения
дисциплины
В результате теоретического изучения дисциплины студент долженЗнать:
6
- основные закономерности функционирования систем и возможности
их системного анализа;
- методы системного анализа объектов и процессов, исследования операций и принятия решений;
- математические модели процессов в естествознании и технике.
В результате практического изучения дисциплины студент должен
Уметь:
- использовать математическую символику для выражения количественных и качественных отношений объектов;
- использовать методы оптимизации при решении практических задач.
4. Структура и содержание теоретической части курса
4.1. Распределение часов курса по темам и видам работ представлено в
таблице 1.
Т а б л и ц а 1 Распределение учебного материала по разделам и видам учебной работы
№
Раздел дисциплины
Виды учебной
работы и трудоемкость
(в часах)
ЛЕК
ПЗ
СР
Формы текущего контроля успеваемости
1.
Введение.
2
2
7
2.
Теоретические основы линейного программирования.
12
10
18
КР №1
3.
Теория двойственности.
10
4
15
КР №2
4.
Специальные задачи линейного программирования и методы их решения.
12
10
15
КР №3
КР №4,
5.
Нелинейное программирование.
6
4
13
КР №5
6.
Динамическое программирование.
4
2
9
7.
Принятие решений в условиях неопределенности.
4
2
9
Итого:
50
34
86
7
4.2. Содержание лекционного курса
Введение.
Предмет курса, его цели и задачи. Классифиция задач математического
программирования.Моделирование как метод исследования, проектирования и
эксплуатации АСОИУ. Задачи разработки АСОИУ на базе современных математических методов, реализуемых с помощью ЭВМ.
Теоретические основы линейного программирования.
Построение математической модели задачи линейного программирования. Различные способы записи математических моделей. Графическое решение задачи линейного программирования при двух переменных.
Основные свойства задачи линейного программирования. Выпуклость
допустимого множества и множества оптимальных точек. Случаи существования оптимального решения.
Теоретическое обоснование симплекс метода для невырожденной задачи линейного программирования. Понятие опорного решения.
Основные
формулы симплекс-метода. Алгоритм симплекс-метода. Нахождение начального опорного решения. Метод искусственных переменных.
Теория двойственности.
Теоретическое обоснование понятия двойственности в линейном программировании. Симметричные и несимметричные двойственные задачи.
Двойственный симплекс-метод. Анализ задачи на чувствительность
Специальные задачи линейного программирования и методы их
решения.
Транспортная задача линейного программирования и метод потенциалов. Задача о назначениях.
Параметрическое линейное программирование. Решение задач с параметром в целевой функции.
Целочисленное программирование и методы их решения. Понятие о
комбинаторных задачах линейного программирования.
8
Целевое программирование.
Нелинейное программирование.
Основные понятия нелинейного программирования. Классический метод поиска экстремума: метод множителей Лагранжа. Выпуклое программирование. Численные методы решения задачи выпуклого программирования.
Методы штрафных и барьерных функций. Понятие о квадратичном, программировании.
Динамическое программирование. Общая постановка задачи. Функция
состояния. Принцип оптимальности Беллмана. Методы решения задач последовательного принятия решения на примере планирования.
Принятие решений в условиях неопределенности.
Основные понятия теории игр. Применение теория игр при принятии
решений. Решение игры 2x2. Графическое решение игр. Сведение матричной
игры к задаче линейного программирования. Игры с природой.
9
5.
Структура и содержание практической части курса
5.1Содержание практических занятий
№ пп
1
Номер
раздела
1
2
2
3
2
4
2
5
2
6
2
7
8
9
10
11
12
13
14
15
16
17
3
3
4
4
4
4
4
5
5
6
7
Наименование лабораторной работы (практического занятия)
Построение математических моделей для задач теории принятия решений
Построение моделей задачи линейного программирования и ее графическое решение для случая двух переменных.
Приведение задачи линейного программирования к каноническому виду. Опорное решение.
Основной алгоритм задачи линейного программирования: симплексметод.
Основной алгоритм задачи линейного программирования: симплексметод.
Метод искусственных переменных при решении задачи симплексметодом.
Теория двойственности. Анализ решения на чувствительность.
Двойственный симплекс-метод.
Транспортные задачи.
Венгерский алгоритм решения задачи о назначении.
Параметрическое линейное программирование.
Целочисленные задачи линейного программирования. Метод Гомори.
Решение комбинаторных задач
Нелинейное программирование.
Методы штрафных и барьерных функций
Динамическое программирование
Принятие решений в условиях неопределенности. Теория игр.
6. Контроль достижения целей курса
6.1
Формы и методы для текущего контроля успеваемости
Текущий контроль проводится в течение всего периода изучения курса.
В 5, 6 семестрах контроль осуществляется на лекционных и практических занятиях. На лекционных занятиях проводятся тесты по основным разделам курса. Цель проведения тестов - определить уровень усвоения студентами
и оценить качество их теоретических знаний по данным темам.
На практических занятиях контроль осуществляется при проверке индивидуальных заданий. В 6 семестре во время работы над курсовым проектом
контроль осуществляется на консультациях.
10
Выполнение указанных видов работ является обязательным для всех
студентов, по результатам текущего контроля выставляется аттестация.
6.2. Темы контрольных работ и тестов
1. Тест «Линейное программирование».
2. Тест «Симплекс-метод».
1. КР «Математические модели задач линейного программирования».
2. КР «Симплекс-метод».
3. КР «Транспортная задача».
4. КР «Специальные задачи линейного программирования».
5. КР «Метод Лагранжа»
6.2
Курсовое проектирование (Цель, типовая тематика)
Курсовая работа является одним из видов самостоятельной работы
студентов. В соответствии с рабочим учебным планом специальности выполняется в 6 (весеннем) семестре.
Целью курсовой работы является углубленное изучение оптимизационных методов и программирование алгоритмов этих методов.
КЛАССИФИКАЦИЯ ТЕМ КУРСОВЫХ РАБОТ
Курсовая работа предполагает самостоятельную работу по решению
различных задач теории принятия решений.
Возможные классы работ:
1)
Создание программ, реализующих какой-либо метод решения
задач теории принятия решений.
2)
Разработка обучающих программ по различным разделам курса
теории принятия решений.
3)
шений.
Графическая иллюстрация решения задач теории принятия ре-
11
4)
Анализ задач теории принятия решений.
5)
Решение конкретной задачи теории принятия решений.
ТРЕБОВАНИЯ К ПРОГРАММЕ
1. Возможность работы в диалоговом режиме.
2. Удобный ввод и вывод данных на экране дисплея с возможностью их
вывода на печать.
3. Сохранение промежуточных результатов и возможность их просмотра.
4. Возможность получения “справки” (инструкции по работе с программой, описание метода решения задачи).
5. При необходимости - вывод на экран таблиц, графиков.
ГРАФИК ВЫПОЛНЕНИЯ КУРСОВОЙ РАБОТЫ
1. Выдача задания по курсовой работе – 1 неделя (В).
2. Поиск литературы – 2-3 недели (ПЛ).
3. Изучение литературы и оформление теоретической части – 4-5 недели (ТЧ).
4. Подбор и решение тестовых примеров – 6-7 недели (ТП).
5. Написание и отладка программы – 8-12 недели (П).
6. Защита курсовой работы – 13-15 недели (З).
К работе оформляется отчет (описание / пояснительная записка). Отчет должен иметь объем не менее 15 страниц текста, выполнен в соответствии
с ГОСТом.
6.3
Итоговый контроль
В соответствии с учебным планом дисциплины предусмотрены формы
промежуточной аттестации:
5 семестр – зачет;
6 семестр - экзамен;
6.4
Перечень типовых экзаменационных вопросов
12
1.
Математическая модель задачи линейного программирования.
2.
Графическое решение задачи линейного программирования.
3.
Область допустимых решений задачи линейного программирования.
4.
Каноническая запись задачи линейного программирования.
5.
Симплекс-метод решения задачи линейного программирования.
6.
Метод искусственных переменных.
7.
Двойственность в линейном программировании.
8.
Анализ на чувствительность задачи линейного программирования.
9.
Транспортная задача.
10.
Задача о назначениях.
11.
Задачи целочисленного программирования.
12.
Метод ветвей и границ.
13.
Метод множителей Лагранжа.
14.
Квадратичное программирование.
15.
Методы решения задач динамического программирования.
16.
Теория игр.
17.
Принцип минимакса. Решение игры 2х2.
ПРИМЕР ЭКЗАМЕНАЦИОННЫХ БИЛЕТОВ.
Вариант 1.
Вопрос 1. Запишите математическую постановку задачи о назначении.
Вопрос 2. Как определяется статус ресурса в ЗЛП?
Вопрос 3. Какое решение ЗЛП называется вырожденным?
Вопрос 4. Чем метод больших штрафов отличается от двухэтапного
метода?
Вопрос 5. Какие задачи решаются методами динамического программирования?
Вопрос 6. Какие изменения ЗЛП могут привести к неоптимальностирешения?
Вопрос 7. Какая связь между оптимальными решениями прямой и
двойственной задач?
13
Вопрос 8. Как определить верхнюю и нижнюю цену игры? Седловая точка.
Вопрос 9. Дана транспортная задача. Найдите
опорное решение методом Фогеля и определите,
2
6
4
2
20
1
4
6
1
30
5
3
2
2
10
15
15
10
20
является оно оптимальным.
Вопрос 10. Монополист планирует программу производства и реализации
продукции на некоторый период. Цены на продукт 1: p1=14-0,25x1,
на про-
дукт 2: p2=14-0,5x2 , где x1 и x2 – объемы реализации продуктов. Предположим, что вся продукция реализуется. Максимальный суммарный объём сбыта
– 57. Каков оптимальный выпуск продуктов?
Вариант 2.
Вопрос 1. Классификация моделей ИСО
Вопрос 2. Дайте определение области допустимых решений.
Вопрос 3. Поясните суть симплекс-метода.
Вопрос 4. Как привести ЗЛП к стандартному виду.
Вопрос 5. Принцип оптимальности Беллмана.
Вопрос 6. Условие оптимальности двойственного симплекс-метода
Вопрос 7. Как связаны прямая и двойственная задачи ЛП?
Вопрос 8. Запишите математическую постановку транспортной задачи.
Вопрос 9. Дана матрица игры. Определите верхнюю и нижнюю цену игры. Есть ли у этой игры седловая точка?
a1
a2
a3
b1
10
17
23
b2
40
16
40
8
1
b3
12
10
13
b4
9
14
25
9
7
14
Вопрос 10.На трех хлебокомбинатах ежедневно произво-
4
6
2
12
дится 110, 90 и 90 т. муки. Эта мука потребляется четырьмя
3
5
8
9
хлебозаводами, ежедневные потребности которых равны соответственно 80,
60, 70 и 80 т. Тарифы перевозок 1 т. муки с хлебокомбинатов к каждому хлебозаводов заданы матрицей стоимости перевозок (условных единиц)
Составить такой план доставки муки, при котором общая стоимость перевозок является минимальной.
7. Учебно-методическое и информационное обеспечение дисциплины
7.1. Основная литература
1. Таха, Хэмди, А. Введение в исследование операций, 6-е издание.: Пер. с
англ. – М.: Издательский дом «Вильямс», 2001.
2. ЭддоузМ., Стенсфилд Р. Методы принятия решений/ Пер. с англ. под
ред. член-кор. РАН И.И. Елисеевой. – М.: Аудит, ЮНИТИ, 1997.
7.2 Дополнительная литература
1. Г. Вагнер Основы исследования операций, в 3-х томах: Пер. с англ. –
М.:Мир, 1973.
2. Калихман И.Л. Сборник задач по математическому программированию.
М., «Высшая школа», 1975.
3. Кудрявцев Е.М. Исследование операций в задачах, алгоритмах и программах. М., Радио и связь, 1984.
4. Брязгина С.П. Теория принятия решений. Методические указания по самостоятельной работе студентов.электр. версия. 2010г.
5. Брязгина С.П. Теория принятия решений. Методические указания к курсовой работе для студентов специальности 220200 –Автоматизированные системы обработки информации и управления.электр. версия. 2010г.
15
Полный список литературы -
в разделе УМКД “ЛИТЕРАТУРА ПО
ДИСЦИПЛИНЕ «Теория принятия решений»”.
7.3 Интернет ресурс:
1. http://e.lanbook.com/books/element.php?pl1_cid=25&pl1_id=3506 Федунец
Н.И. Куприянов В.В. Теория принятия решений: учебное пособие для
вузов – М.: Издательство Московского государственного горного университета, 2005. – 218 с.
2. http://www.aup.ru/books/m157/ Орлов А.И. Теория принятия решений.
Учебное пособие. - М.: Издательство "Март", 2004. - 656 с.
3. http://window.edu.ru/resource/960/44960 Павлов А.Н., Соколов Б.В. Принятие решений в условиях нечеткой информации: Учебное пособие. СПб.: ГУАП, 2006. - 72 с.
7.4 Программное обеспечение
При выполнении курсовых проектов могут использоваться пакеты программ:
MathCad, MatLabMathematica, программа TORA и другие.
8. Рейтинговая оценка по дисциплине.
Распределение баллов по видам учебных работ.
№
Наименование работ
Распределение баллов
п/п
1
Теоретический материал
2
Лабораторные работы
3
Практические занятия
10
20
16
4
Курсовое проектирование
5
Индивидуальные
домашние
задания
10
(РГЗ, рефераты и т. д.)
6
Контрольные работы
7
Посещаемость
8
Экзамен/ Зачет
30
30
Итого
100
Посещаемость занятий учитывается поправочным коэффициентом, равным отношению количества часов посещенных занятий к плановым.
ПЕРЕВОД БАЛЛОВ В ПЯТИБАЛЬНУЮ ШКАЛУ
Отлично
85-100
Хорошо
71-84
Удовлетворительно
60-70
Неудовлетворительно
Менее 60
Примечание: при набранной общей суммы баллов менее 40 по результатам
третьей аттестации студент не допускается к итоговой аттестации по дисциплине.
17
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное образовательное учреждение
высшего профессионального образования
«Дальневосточный федеральный университет»
(ДВФУ)
ШКОЛА ЕСТЕСТВЕННЫХ НАУК
КОНСПЕКТЫ ЛЕКЦИЙ
по дисциплине «Теория принятия рений»
Специальность - 230102.65 «Автоматизированные системы обработки информации и управления»
Форма подготовки - очная
г. Владивосток
2011
18
5семестр, 3 курс
Лекция 1
Название темы: ВВЕДЕНИЕ В ТЕОРИЮ ПРИНЯТИЯ РЕШЕНИЙ.
Цели:
Рассмотреть широкий круг задач оптимизации. Описать этапы решения
прикладных задач оптимизации. Классифицировать задачи математического
программирования по методам решения.
Учебная информация:
Решение конкретной задачи оптимизации требует комплексного подхода. На практике реализация методов оптимизации должна включать следующие этапы:
Формализация исходной проблемы.
Построение математической модели.
Решение модели.
Проверка адекватности модели.
Реализация решения.
Исследователь прежде всего должен выбрать математический метод, который приводил бы к конечным результатам с наименьшими затратами на вычисления или же давал возможность получить наибольший объем информации
об искомом решении. Выбор того или иного метода в значительной степени
определяется постановкой оптимальной задачи, а также используемой математической моделью объекта оптимизации.
В настоящее время для решения оптимальных задач применяют в основном следующие методы:
методы исследования функций классического анализа;
методы, основанные на использовании неопределенных множителей
Лагранжа;
вариационное исчисление;
динамическое программирование;
19
принцип максимума;
линейное программирование;
нелинейное программирование.
В последнее время разработан и успешно применяется для решения
определенного класса задач метод геометрического программирования.
Нельзя рекомендовать какой-либо один метод, который можно использовать для решения всех без исключения задач, возникающих на практике.
Одни методы в этом отношении являются более общими, другие - менее общими. Целую группу методов (методы исследования функций классического
анализа, метод множителей Лагранжа, методы нелинейного программирования) на определенных этапах решения оптимальной задачи можно применять
в сочетании с другими методами, например динамическим программированием или принципом максимума.
Некоторые методы специально разработаны или наилучшим образом
подходят для решения оптимальных задач с математическими моделями определенного вида. Так, математический аппарат линейного программирования,
специально создан для решения задач с линейными критериями оптимальности и линейными ограничениями на переменные и позволяет решать большинство задач, сформулированных в такой постановке. Так же и геометрическое
программирование предназначено для решения оптимальных задач, в которых
критерий оптимальности и ограничения представляются специального вида
функциями позиномами.
Динамическое программирование хорошо приспособлено для решения
задач оптимизации многостадийных процессов, особенно тех, в которых состояние каждой стадии характеризуется относительно небольшим числом переменных состояния. Однако при наличии значительного числа этих переменных, т. е. при высокой размерности каждой стадии, применение метода динамического программирования затруднительно вследствие ограниченных быстродействия и объема памяти вычислительных машин.
20
Наилучшим путем при выборе метода оптимизации, наиболее пригодного для решения соответствующей задачи, можно признать исследование возможностей и опыта применения различных методов оптимизации. Рассмотрим
основные математические методы решения оптимальных задач и примеры их
использования.
Линейное программирование представляет собой математический аппарат, разработанный для решения оптимальных задач с линейными выражениями для критерия оптимальности и линейными ограничениями на область
изменения переменных. Такие задачи обычно встречаются при решении вопросов оптимального планирования производства с ограниченным количеством ресурсов, при определении оптимального плана перевозок (транспортные задачи) и т. д.
Для решения большого круга задач линейного программирования имеется практически универсальный алгоритм -симплексный метод, позволяющий
за конечное число итераций находить оптимальное решение подавляющего
большинства задач. Тип используемых ограничений (равенства или неравенства) не сказывается на возможности применения указанного алгоритма. Дополнительной проверки на оптимальность для получаемых решений не требуется. Как правило, практические задачи линейного программирования отличаются весьма значительным числом независимых переменных. Поэтому для
их решения обычно используют вычислительные машины, необходимая мощность которых определяется размерностью решаемой задачи.
Методы нелинейного программирования применяют для решения оптимальных задач с нелинейными функциями цели. На независимые переменные могут быть наложены ограничения также в виде нелинейных соотношений, имеющих вид равенств или неравенств. По существу методы нелинейного
программирования используют, если ни один из перечисленных выше методов
не позволяет сколько-нибудь продвинуться в решении оптимальной задачи.
Поэтому указанные методы иногда называют также прямыми методами решения оптимальных задач.
21
Для получения численных результатов важное место отводится нелинейному программированию и в решении оптимальных задач такими методами, как динамическое программирование, принцип максимума и т. п. на определенных этапах их применения.
Названием “методы нелинейного программирования” объединяется
большая группа численных методов, многие из которых приспособлены для
решения оптимальных задач соответствующего класса. Выбор того или иного
метода обусловлен сложностью вычисления критерия оптимальности и сложностью ограничивающих условий, необходимой точностью решения, мощностью имеющейся вычислительной машины и т.д. Ряд методов нелинейного
программирования практически постоянно используется в сочетании с другими методами оптимизации, как, например, метод сканирования в динамическом программировании. Кроме того, эти методы служат основой построения
систем автоматической оптимизации - оптимизаторов, непосредственно применяющихся для управления производственными процессами.
Методы
исследования
функций
классического
анали-
за представляют собой наиболее известные методы решения несложных оптимальных задач, которые известны из курса математического анализа. Обычной
областью использования данных методов являются задачи с известным аналитическим выражением критерия оптимальности, что позволяет найти не очень
сложное, также аналитическое выражение для производных. Полученные приравниванием нулю производных уравнения, определяющие экстремальные
решения оптимальной задачи, крайне редко удается решить аналитическим
путем, поэтому, как, правило, применяют вычислительные машины. При этом
надо решить систему конечных уравнений, чаще всего нелинейных, для чего
приходится использовать численные методы, аналогичные методам нелинейного программирования.
Дополнительные трудности при решении оптимальной задачи методами
исследования функций классического анализа возникают вследствие того, что
система уравнений, получаемая в результате их применения, обеспечивает
22
лишь необходимые условия оптимальности. Поэтому все решения данной системы (а их может быть и несколько) должны быть проверены на достаточность. В результате такой проверки сначала отбрасывают решения, которые не
определяют экстремальные значения критерия оптимальности, а затем среди
остающихся экстремальных решений выбирают решение, удовлетворяющее
условиям оптимальной задачи, т. е. наибольшему или наименьшему значению
критерия оптимальности в зависимости от постановки задачи.
Методы исследования при наличии ограничений на область изменения
независимых переменных можно использовать только для отыскания экстремальных значений внутри указанной области. В особенности это относится к
задачам с большим числом независимых переменных (практически больше
двух), в которых анализ значений критерия оптимальности на границе допустимой области изменения переменных становится весьма сложным.
Метод множителей Лагранжа применяют для решения задач такого же
класса сложности, как и при использовании обычных методов исследования
функций, но при наличии ограничений типа равенств на независимые переменные. К требованию возможности получения аналитических выражений для
производных от критерия оптимальности при этом добавляется аналогичное
требование относительно аналитического вида уравнений ограничений.
В основном при использовании метода множителей Лагранжа приходится решать те же задачи, что и без ограничений. Некоторое усложнение в данном случае возникает лишь от введения дополнительных неопределенных
множителей, вследствие чего порядок системы уравнений, решаемой для
нахождения экстремумов критерия оптимальности, соответственно повышается на число ограничений. В остальном, процедура поиска решений и проверки
их на оптимальность отвечает процедуре решения задач без ограничений.
Множители Лагранжа можно применять для решения задач оптимизации объектов на основе уравнений с частными производными и задач динамической оптимизации. При этом вместо решения системы конечных уравнений
23
для отыскания оптимума необходимо интегрировать систему дифференциальных уравнений.
Множители Лагранжа используют также в качестве вспомогательного
средства и при решении специальными методами задач других классов с ограничениями типа равенств, например, в вариационном исчислении и динамическом программировании. Особенно эффективно применение множителей Лагранжа в методе динамического программирования, где с их помощью иногда
удается снизить размерность решаемой задачи.
Методы вариационного исчисления обычно используют для решения
задач, в которых критерии оптимальности представляются в виде функционалов и решениями которых служат неизвестные функции. Такие задачи возникают обычно при статической оптимизации процессов с распределенными параметрами или в задачах динамической
Динамическое программирование служит эффективным методом решения задач оптимизации дискретных многостадийных процессов, для которых критерий оптимальности задается как аддитивная функция критериев оптимальности отдельных стадий. Этот метод можно распространить и на случай, когда критерий оптимальности задан в другой форме, однако при этом
обычно увеличивается размерность отдельных стадий.
По существу метод динамического программирования представляет собой алгоритм определения оптимальной стратегии управления на всех стадиях
процесса. При этом закон управления на каждой стадии находят путем решения частных задач оптимизации последовательно для всех стадий процесса с
помощью методов исследования функций классического анализа или методов
нелинейного программирования. Результаты решения обычно получаются в
виде таблиц.
При решении задач методом динамического программирования, как
правило, используют вычислительные машины, обладающие достаточным
объемом памяти для хранения промежуточных результатов решения, которые
обычно получаются в табличной форме.
24
Вопросы для самопроверки:
1. Перечислите этапы решения оптимизационных задач.
2. Какие основные методы применяют для решения оптимальных задач?
3. Что представляет собой линейное программирование?
4. Что представляет собойнелинейное программирование?
5. Что представляет собойдинамическое программирование?
6. Перечислите наиболее важные характеристики любой оптимальной задачи
Список литературы и ссылки на интернет-ресурсы по теме:
1.
Струченков И. В. Методы оптимизации в прикладных задачах. –
М.:СОЛОН-ПРЕСС, 2009.
2.
Федоров В.В., Сухарев А.Г., Тимохов А.В., Курс методов оптимизации:
учебное пособие, М.: ФИЗМАТЛИТ, 2011 г.
3.
А.Г.Трифонов. "Постановка задачи оптимизации и численные методы ее
решения"
/
А.Г.Трифонов
[Электронный
ресурс].
http://matlab.exponenta.ru/optimiz/book_2/1.php)
Интернет ресурс:
1. http://e.lanbook.com/books/element.php?pl1_cid=25&pl1_id=3506
Феду-
нец Н.И. Куприянов В.В. Теория принятия решений: учебное пособие
для вузов – М.: Издательство Московского государственного горного
университета, 2005. – 218 с.
2. http://www.aup.ru/books/m157/ Орлов А.И. Теория принятия решений.
Учебное пособие. - М.: Издательство "Март", 2004. - 656 с.
3. http://window.edu.ru/resource/960/44960 Павлов А.Н., Соколов Б.В. Принятие решений в условиях нечеткой информации: Учебное пособие. СПб.: ГУАП, 2006. - 72 с.
25
Лекции 2-7
Название темы:ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.
Цели:
Рассмотреть:
Типичные задачи линейного программирования.
Математическая постановка задач линейного программирования
Общие свойства линейных задач.
Область допустимых решений задач линейного программирования.
Геометрический смыслзадачи линейного программирования.
Стандартная форма задачи линейного программирования.
Решение задачи линейного программированиясимплекс-методом
Решение задачи линейного программирования методом искусственного
базиса.
Особые случаи решения задач линейного программирования.
Анализ чувствительности решения задач линейного программирования.
Учебная информация:
Примерытипичных задачи линейного программирования:
1. Задача о пищевом рационе.
Пищевой рацион составляется из набора продуктов питанияР 1, Р2,...,
PNстоимостью с1, с2,..., CNза 1 кг соответственно. Пусть 1 кгпродукта каждого
вида содержит ai1г белка, аi2г жиров, аi3г углеводов, аi4 г микроэлементов, аi5 г
витамина С, а также обладает энергетической ценностью аi6 килокалорий
(i=1,2,...,N). Необходимо закупить такое количество продуктов, чтобы их стоимость быламинимальна и составленный из них рацион в расчете на одного
человека содержал не менее b1г белков, не менее b2 г жиров, не менееb3г угле-
26
водов, не менее b4 г микроэлементов, не менее b5г витаминаС и не более
b6килокалорий.
2. Задача о планировании производства.
Предприятие производит изделия трех видов: U1, U2, U3. По каждому виду изделия у предприятия есть заказ, по которому оно обязано выпустить не
менее b1, единиц изделияU1, не менее b2 единиц изделия U2 и не менее b3 единиц изделия U3. Заказ может быть перевыполнен, но в определенных границах;
условия спроса ограничивают количества произведенных единиц изделий
каждого типа: не более, соответственно k1, k2, k3 единиц. На изготовление изделий идет какое-то сырье; всего имеется четыре вида сырья: s1, s2, s3, s4, причем запасы ограничены числами f1, f2, f3,f4 единиц каждого вида сырья. Обозначим аij количество единиц сырья вида si (i =1, 2, 3, 4), потребное на изготовление одной единицы изделия Uj, (j= 1, 2, 3). Первый индекс у числа аij — вид
изделия, второй — вид сырья.
При реализации одно изделие U1 приносит предприятию прибыль c1, U2
— прибыль c2, U3— прибыль с3. Требуется так спланировать производство
(сколько каких изделий производить), чтобы план был выполнен или перевыполнен (но при отсутствии «затоваривания»), а суммарная прибыль обращалась в максимум.
3. Задача о загрузке оборудования.
Ткацкая фабрика располагает двумя видами станков, из них N1 станков
типа 1 и N2 станков типа 2. Станки могут производить три вида тканей: Т 1, Т2,
Т3, но с разной производительностью. aij-производительность станков (первый
индекс — тип станка, второй — вид ткани).
Каждый метр ткани вида Т1 приносит фабрике доход c1, вида Т2 — доход
c2, Т3— доход с3.
Фабрике предписан план, согласно которому она должна производить в
месяц не менее b1 метров ткани Т1, b2 метров ткани Т2, b3 метров ткани Т3; количество метров каждого вида ткани не должно превышать соответственно k1,
k2, k3 метров. Кроме того, все без исключения станки должны быть загружены.
27
Требуется так распределить загрузку станков производством тканей Т1, Т2, Т3,
чтобы суммарный месячный доход был максимален.
4. Задача о раскрое.
В качестве примера рассмотрим проблему раскроя листа металла шириной S и длиной 25 м на три куска длиной по 10, 8 и 5 м такой же ширины.
Технология резки металла такова, что лист металла можно сразу резать на три
части по схеме А, Б или В. Схема А: 8, 10 и 5 м соответственно. Схема Б: 8, 5 и
5 м. Схема В: 10, 5 и 5 м. Требуется из данных листов металла нарезать 400,
300 и 200 кусков по 10, 8 и 5 м соответственно. Вопрос: сколько для этого потребуется листов металла и как это сделать при минимальном количестве отходов?
Математические модели этих задач могут быть представлены как модели
линейного программирования.
Задача, в которой требуется минимизировать (максимизировать) линейную
функцию
n
c x min (max)
i
i
i 1
при условии, что
n
a x b , j 1, m ,
ij
i
j
j 1
или
a x b , j m 1, p ,
n
ij
i 1
i
j
или
n
a x b , j p 1, k ,
i 1
и
ij
i
j
28
xi 0 , i 1, n ,
называется задачей линейного программирования в произвольной форме записи.
Такая задача линейного программирования обладает свойствами аддитивности и пропорциональности.
Область допустимых решений такой задачи если не пуста, то всегда выпукла.
Для задачи с двумя переменными всегда можно получить решение графически.
При большем числе переменных необходимо применение алгебраического аппарата. Рассмотрим общий метод решения задач ЛП, называемый симплекс-методом.
Информация, которую можно получить с помощью симплекс-метода, не
ограничивается лишь оптимальными значениями переменных. Симплексметод фактически позволяет дать экономическую интерпретацию полученного
решения и провести анализ модели на чувствительность.
Процесс решения задачи линейного программирования симплексметодом носит итерационный характер: однотипные вычислительные процедуры в определенной последовательности повторяются до тех пор, пока не будет получено оптимальное решение. Процедуры, реализуемые в рамках симплекс-метода, требуют применения вычислительных машин — мощного средства решения задач линейного программирования.
Симплекс-метод — это характерный пример итерационных вычислений,
используемых при решении большинства оптимизационных задач.
Для построения общего метода решения задач ЛП соответствующие модели
должны быть представлены в некоторой форме, которую назовем стандартной
формой линейных оптимизационных моделей. При стандартной форме линейной модели
29
все ограничения записываются в виде равенств с неотрицатель-
1)
ной правой частью,
2)
значения всех переменных модели неотрицательны;
3)
целевая функция подлежит максимизации или минимизации.
Любую линейную модель можно привести к стандартной.
При анализе графического метода решения задач ЛП было отмечено, что
оптимальному решению всегда соответствует одна из угловых (или экстремальных) точек пространства решений. Именно этот результат и положен в
основу построения симплекс-метода.
В вычислительной схеме симплекс-метода реализуется упорядоченный
процесс, при котором, начиная с некоторой исходной допустимой угловой
точки (обычно начала координат), осуществляются последовательные переходы от одной допустимой экстремальной точки к другой до тех нор, пока не будет найдена точка, соответствующая оптимальному решению.
Исходной точкой алгоритма обычно является начало координат. Решение, соответствующее этой точке, обычно называют начальным решением. От
исходной точки осуществляется переход к некоторой смежной угловой точке.
Выбор точки зависит от коэффициентов целевой функции. После этого указанный процесс повторяется, чтобы выяснить, существует ли другая экстремальная точка, соответствующая лучшему допустимому решению. Используя,
как и ранее, информацию о целевой функции, можно определить, имеется ли
на данном шаге алгоритма такая точка. В результате такой итеративный процесс позволяет найти оптимальную угловую точку.
Выбор каждой последующей экстремальной точки при использовании
симплекс-метода определяется следующими двумя правилами.
1.
Каждая последующая угловая точка должна быть смежнойс
предыдущей.
2.
Обратный переход к предшествующей экстремальной точке не
может производиться.
30
Чтобы описать рассмотренные процедуры формальными средствами,
необходимо определить пространство решений и угловые точки алгебраически.
Определить экстремальные точки алгебраическим способом можно путем приравнивания нулю такого количества переменных, которое равно разности между количеством неизвестных и числом уравнений. В этом состоит
сущность свойства однозначности экстремальных точек. Каждой неэкстремальной точке соответствует не более одной нулевой переменной. А любая
точка внутренней области пространства решений вообще не имеет ни одной
пулевой переменной, а любая неэкстремальная точка, лежащая на границе,
всегда имеет лишь одну нулевую переменную.
Свойство однозначности экстремальных точек позволяет определить их
алгебраическим методом. Будем считать, что линейная модель стандартной
формы содержит т уравнений и n (т≤n) неизвестных (правые части ограничений — неотрицательные). Тогда все допустимые экстремальные точки определяются как все однозначные неотрицательные решения системы т уравнений,
в которых п—т переменных равны нулю.
Однозначные решения такой системы уравнений, получаемые путем
приравнивания к нулю (п — т) переменных, называются базисными решениями. Если базисное решение удовлетворяет требованию неотрицательности
правых частей, оно называется допустимым базисным решением. Переменные, имеющие нулевое значение, называются небазисными переменными,
остальные — базисными переменными.
Из вышеизложенного следует, что при реализации симплекс-метода алгебраическое определение базисных решений соответствует идентификации
экстремальных точек, осуществляемой при геометрическом представлении
пространства решений. Таким образом, максимальное число итераций при использовании симплекс-метода равно максимальному числу базисных решений
задачи ЛП, представленной в стандартной форме. Это означает, что количество итерационных процедур симплекс-метода не превышает
31
Сnm=п!(п-т)!т!.
Так как смежные экстремальные точки отличаются только одной переменной, можно определить каждую последующую (смежную) экстремальную
точку путем замены одной из текущих небазисных (нулевых) переменных текущей базисной переменной.
Процесс взаимной замены переменных приводит к необходимости введения двух новых терминов. Включаемой переменной называется небазисная
в данный момент переменная, которая будет включена в множество базисных
переменных на следующей итерации (при переходе к смежной экстремальной
точке). Исключаемая переменная — это та базисная переменная, которая на
следующей итерации подлежит исключению из множества базисных переменных.
Симплекс-алгоритм состоит из следующих шагов.
Шаг 0. Используя линейную модель стандартной формы, определяют
начальное допустимое базисное решение путем приравнивания к нулю п—т
(небазисиых) переменных.
Шаг 1. Из числа текущих небазисных (равных нулю) переменных выбирается включаемая в новый базис переменная, увеличение которой обеспечивает улучшение значения целевой функции. Если такой переменной нет, вычисления прекращаются, так как текущее базисное решение оптимально. В
противном случае осуществляется переход к шагу 2.
Шаг 2. Из числа переменных текущего базиса выбирается исключаемая
переменная, которая должна принять нулевое значение (стать небазисной) при
введении в состав базисных новой переменной.
Шаг 3. Находится новое базисное решение, соответствующее новым составам небазисных и базисных переменных. Осуществляется переход к шагу 1.
Для задачи максимизировать Z=5x1+4x2+0s1+0s2+0s3+0s4
при ограничениях
6x1+4x2+0s1
=24
32
x1+2x2
+0s2
=6
-x1 + x2
+0s3
x2+ 2
+0s4=2
=1
x1, x2, s1, s2, s3, s4 0,
в качестве начального пробного решения используется решение системы
уравнений, в которой две переменные принимаются равными нулю. Это обеспечивает единственность и допустимость получаемого решения. Подстановка x1=x2=0 сразу же приводит к начальному допустимому решению. Величина
Z в этой точке равна нулю. Полученные результаты удобно представить в виде
симплекс-таблицы:
Базис-
x1
x2
s1
s2
s3
s4
ные пе-
решен
ие
ременные.
s1,
6
4
1
0
0
0
24
s2,
1
2
0
1
0
0
6
s3
-1
1
0
0
1
0
1
s4
0
1
0
0
0
1
2
z
-5
-4
0
0
0
0
0
Анализируя уравнениецелевой функции Z, нетрудно заметить, что обе
небазисные переменные равные нулю, имеют отрицательные коэффициенты.
Это эквивалентно наличию положительных коэффициентов при этих переменных в исходной целевой функции. Так как мы имеем дело с задачей максимизации, значение Zможет быть улучшено при увеличении как x1 так и x2.
Однако всегда выбирается переменная с большим абсолютным значением отрицательного коэффициента (в целевой функции), так как практический опыт
вычислений показывает, что в этом случае оптимум достигается быстрее.
33
Условие оптимальности: если в задаче максимизации все небазисные
переменные в z -уравнении имеют неотрицательные коэффициенты, полученное пробное решение является оптимальным. В противном случае в качестве новой базисной переменной следует выбрать ту, которая имеет наибольший по абсолютной величине отрицательный коэффициент.
По условию оптимальности выберем в качестве переменной, включаемой
в базис, переменную Х1. Исключаемая переменная должна быть выбрана из
совокупности базисных переменных. Процедура выбора исключаемой переменной предполагает проверку условия допустимости: в задачах максимизации и минимизации в качестве исключаемой переменной выбирается та базисная переменная, для которой отношение постоянной в правой части соответствующего ограничения к положительному коэффициенту ведущего столбца
минимально. В случае равенства этого отношения для нескольких базисных
переменных выбор делается произвольно. В качестве исключаемой переменной будет выбираться та из переменных текущего базиса, которая первой обращается и нуль при увеличении включаемой переменной X1. вплоть до значения, соответствующего смежной экстремальной точке.
Для удобства описания вычислительных процедур, осуществляемых на
следующей итерации, введем ряд необходимых определений. Столбец симплекс-таблицы, ассоциированный с вводимой переменной, будем называть ведущим столбцом. Строку, соответствующую исключаемой переменной, назовем ведущей строкой (уравнением), а элемент таблицы, находящийся на пересечении ведущего столбца и ведущей строки, будем называть ведущим элементом.
После того как определены включаемая и исключаемая переменные (с
использованием условий оптимальности и допустимости), следующая итерация (поиск нового базисного решения) осуществляется методом исключения
переменных, или методом Жордана—Гаусса. Этот процесс изменения базиса
включает вычислительные процедуры двух типов.
Тип 1 (формирование ведущего уравнения),
34
Новая ведущая строка = Предыдущая ведущая строка/ Ведущий элемент
Тип 2 (формирование всех остальных уравнений, включая г-уравнение).
Новое уравнение =Предыдущее уравнение—(коэффициент ведущего
столбца предыдущего уравнения)*(Новая ведущая строка).
Выполнение процедуры типа 1 приводит к тому, что в новом ведущем
уравнении ведущий элемент становится равным единице. В результате осуществления процедуры типа 2 все остальные коэффициенты, фигурирующие в
ведущем столбце, становятся равными нулю. Это эквивалентно получению базисного решения путем исключения вводимой переменной из всех уравнений,
кроме ведущего.
Базисные
x1
x2
s1
s2
s3
s4
перемен-
решен
ие
ные
x1
0
23
1/6
0
0
0
4
s2
1
43
-1/6
1
0
0
2
s3
0
53
1/6
0
1
0
5
s4
0
1
0
0
0
1
2
z
0
-23
5/6
0
0
0
20
В новом решении значение Zвозросло с 0 до 20. Это увеличение обусловлено тем, что прирост x1 на единицу обеспечивает увеличение Z на 5 единиц; таким образом, прирост целевой функции Z составляет: 5*4=20.
Заметим, что новая симплекс-таблица обладает такими же Характеристиками, как и предыдущая: только небазисные переменные x2 и s1 равны нулю, а
значения базисных переменных, как и раньше, представлены в столбце «Решение». Это в точности соответствует результатам, получаемым при использовании метода Жордана—Гаусса.
В результате дальнейших преобразований получим следующую симплекс-таблицу.
35
Базисные
x1
x2
s1
s2
s3
s4
перемен-
решен
ие
ные
x1
1
0
14
-12
0
0
3
x2
0
1
-18
34
0
0
3/2
s3
0
0
3/8
-54
1
0
5/2
s4
0
0
1/8
-34
0
1
1/2
z
0
0
3/4
1/2
0
0
21
Последняя симплекс-таблица соответствует оптимальному решению задачи, так как в Z-уравнении ни одна из небазисных переменных не фигурирует
с отрицательным коэффициентом. Получением этой результирующей таблицы
и завершаются вычислительные процедуры симплекс-метода.
В случае минимизации целевой функции в этом алгоритме необходимо
изменить только условие оптимальности: в качестве новой базисной переменной следует выбирать ту переменную, которая в Z -уравнении имеет наибольший положительный коэффициент. Условия допустимости в обоих случаях
(максимизации и минимизации) одинаковы.
Если исходное ограничение в задаче ЛП записано в виде равенства или
имеет знак , нельзя сразу же получить допустимое начальное базисное решение.
Например:минимизироватьZ=4xl+x2
при ограничениях3xl+x2 =З,
4xl+3x26,
xl+2x2<=4,
Для решения таких задач используется метод искусственных. Метод
предполагает включение неотрицательных переменных в левую часть каждого
из уравнений, не содержащих «очевидных» начальных, базисных переменных.
36
Однако, поскольку такие искусственные переменные не имеют отношения к
содержанию поставленной задачи (отсюда и их название «искусственные»), их
введение допустимо только в том случае, если соответствующая схема вычислений будет обеспечивать получение оптимального решения, в котором все
искусственные переменные окажутся равными нулю. Другими словами, эти
переменные следует использовать только для получения «стартовой» точки,
причем итеративный процесс оптимизации должен «вынуждать» эти переменные принимать нулевые значения в конечном оптимальном решении, обеспечивая допустимость оптимума.
Добиться желаемого результата позволяет использование в итерационном процессе обратной связи, обеспечивающей в конечном итоге получение
оптимального решения при нулевых значениях искусственных переменных
(при условии, что допустимое оптимальное решение задачи существует). Для
построения требуемой схемы вычислений можно применить следующий прием: наложить «штраф» за использование искусственных переменных, вводимых и целевую функцию. Затем полученную задачу решают симплекс методом.
Вопросы для самопроверки:
1. Перечислите основные свойства задач ЛП.
2. Какие основные методы применяют для решения задач ЛП?
3. Дайте определение базисного решения?
4. Дайте определение допустимого базисного решения?
5. Как формируется симплекс-таблица?
6. Какие задачи решаются методом искусственного базиса
7. Перечислите правила построения двойственной задачи линейного программирования.
Список литературы и ссылки на интернет-ресурсы по теме:
37
1. ХэмдиА.Таха, Введение в исследование операций, 7-е издание.: Пер. с
англ. – М.: Издательский дом «Вильямс», 2007.
2. Струченков И. В. Методы оптимизации в прикладных задачах. –
М.:СОЛОН-ПРЕСС, 2009.
3. Просветов Г.И. Методы оптимизации: задачи и решения. Учебнопрактическое пособие. – М., Альфа-Пресс, 2009.
4. Акулич И.Д. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1993.
Лекции 8-12
Название темы:ТЕОРИЯ ДВОЙСТВЕННОСТИ.
Цели:
Рассмотреть:
Понятие двойственной задачи.
Построение двойственной задачи
Двойственные цены
Двойственный симплекс-метод
Экономический смысл двойственной задачи.
Связь решения двойственной и прямой задачи
Учебная информация:
Двойственная задача - это вспомогательная задача ЛП, формулируемая с и
не требует знания деталей различных формулировок двойственной задачи.
Дадим обобщенную формулировку двойственной задачи ЛП, которая применима к любой форме представления прямой задачи. В основу такой формулировки положен тот факт, что использование симплекс-метода требует приведения любой задачи ЛП к стандартной форме.
38
Двойственная задача получается путем симметричного структурного преобразования условий прямой задачи в соответствии со следующими правилами:
1) каждому ограничению прямой задачи соответствует переменная двойственной задачи;
2) каждой переменной прямой задачи соответствует ограничение двойственной задачи;
3) коэффициенты при некоторой переменной, фигурирующие в ограничениях прямой задачи, становятся коэффициентами левой части соответствующего ограничения двойственной задачи. А коэффициент, фигурирующий при
той же переменной в выражении для целевой функции прямой задачи, становится постоянной правой части этого же ограничения двойственной задачи.
4) Правые части ограничений прямой задачи становятся коэффициентами
целевой функции двойственной задачи.
Из указанных правил построения двойственной задачи следует, что она
имеет т переменных (y1,y2,…., ym) и п ограничений (соответствующих п переменным прямой задачи (х1,..xn).
Остальные условия двойственной задачи формируются:
прямая задача
в стандартной
форме. Целевая
двойственная задача
Целевая
функция.
Ограниче-
Переменные
ния
функция.
Максимизация
Минимизация
Минимизация
Не ограничены в
знаке
Максимизация
Не ограничены в
знаке
Пример :. Прямая задача:
максимизировать z=5х1+12х2+4х3 при ограничениях
1х1+2х2+1х310,
39
2х1-х2+3х3=8,
х1,х2,х30
Прямая задача в стандартной форме:
максимизировать z=5х1+12х2+4х3+0х4 при ограничениях
1х1+2х2+1х3+ х410,
2х1-х2+3х3+0х4=8,
х1,х2,х3, х40
Заметим, что х4 - остаточная переменная, введенная в первое ограничение.
Поэтому коэффициенты, фигурирующие при этой переменной в целевой
функции и во втором ограничении, равны нулю.
Двойственная задача:
минимизировать w=10y1+8y2 при ограничениях
х1: y1+2 y25,
х2: 2y1- y212,
х3: y1+3 y24,
х4: y1+0 y20, (означает, что y10),
y1, y2 не ограничены в знаке.
На принципах двойственности построен двойственный симплекс-метод.
Соотношения двойственности
Между прямой и двойственной задачами существует тесная взаимосвязь.
Фактически оптимальное решение одной из этих задач непосредственно (без
каких-либо дополнительных вычислений) можно получить из данных симплекс-таблицы для оптимального решения другой задачи. Кроме того, будут
представлены некоторые вычислительные процедуры, использующие соотношения двойственности и позволяющие выявить изменения оптимального решения прямой задачи, обусловленные изменениями исходной модели. Это облегчит изучение материала в разделе, посвященном методам анализа моделей
на чувствительность.
40
Заинтересованность в определении оптимального решения прямой задачи
путем решения двойственной к ней задачи обусловлена тем, что вычисления,
необходимые для решения двойственной задачи, могут оказаться менее сложными, чем решение прямой задачи.
Вопросы для самопроверки:
1. Перечислите правила построения двойственной задачи линейного программирования.
2.
Лекции13-17
Название темы:
СПЕЦИАЛЬНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ И МЕТОДЫ ИХ РЕШЕНИЯ.
Цели:
Рассмотреть:
Транспортная задача, ее свойства, модификации.
Метод потенциалов решения транспортной задачи.
Задача о назначении.
Задачи целочисленного линейного программирования, постановка и методы решения.
Методы отсечения.
Метод ветвей и границ.
Задача о коммивояжере.
Учебная информация:
41
Транспортная задача линейного программирования формулируется следующим образом. Необходимо минимизировать транспортные расходы
Q X
m
n
c x min
ij
ij
i 1 j 1
при ограничениях
j 1, n,
i 1
n
x
a
,
i
1
,
m
,
,
ij
i
j 1
xij 0, i 1, m, j 1, n,
m
x b ,
ij
j
где cij - стоимость перевозки единицы продукции из пункта i в пункт j;
xij – планируемая величина перевозок из пункта i в пункт j (план перевозок X
– матрица размерности m n ); b j - потребности в продукте в пункте j; ai - запасы в пункте i.
n
Предполагается, что модель закрытого типа, то есть
m
b a .
j
i
j 1
i 1
m
n
Если модель открытого типа b j
a
i , то ее всегда можно приве
i 1
j 1
сти к закрытому типу введением фиктивного пункта производства или фиктивного пункта потребления:
n
Если
m
b a , то b
j
n 1
i
j 1
i 1
m
n 1
n
m
a b , тогда b a ,
i
j
i 1
j
j 1
i
j 1
i 1
причем ci ,n 1 0 i .
n
Если
b a , то a
j
j 1
cm1, j 0 j .
m
i
i 1
m 1
n
m
m 1
n
b a , b a
j
j 1
i
i 1
j
j 1
i 1
i
и
42
Транспортная задача представляет собой задачу линейного программирования и, естественно, ее можно решить с использованием симплекс-метода.
В этом случае основная трудность бывает связана с числом переменных задачи (mn) и числом ограничений (m+n). Поэтому специальные алгоритмы оказываются более эффективными. К таким алгоритмам относятся метод потенциалов и венгерский метод.
Алгоритм метода потенциалов, его называют еще модифицированным
распределительным алгоритмом, начинает работу с некоторого опорного плана транспортной задачи (допустимого плана перевозок). Для построения опорного плана обычно используется один из трех методов: метод северозападного угла,метод минимального элемента илиметод Фогеля.
К транспортной модели может привести задача, по своему содержанию
никак не связанная с транспортом, с планированием перевозок. В таких случаях говорят, что данная задача может быть сформулирована в терминах транспортной задачи. Поскольку для решения простейшей транспортной задачи
имеются достаточно эффективные алгоритмы,
всегда
полезно пытаться
сформулировать задачу в терминах транспортной задачи, если конечно не
ясно, что это заведомо невозможно.
Многие практические задачи, связанные с планированием перевозок, не
укладываются в рамки рассмотренной транспортной задачи, так как осложнены теми или иными дополнительными ограничениями, или вообще существенно более сложны по постановке.
Многие практические задачи приводят к модели, по отношению к которой обычная транспортная задача является частным случаем.
Как и в транспортной задаче, ограничения здесь делятся на две группы,
такие что каждая переменная входит явно лишь в одно из ограничений каждой
группы, т. е. сохраняется одна из основных особенностей транспортной задачи. Однако в отличие от нее в одной из групп ограничений допускаются произвольные, не обязательно единичные, ненулевые коэффициенты при входящих в ограничение переменных.
43
Рассмотрим один пример такой задачи. Имеется m пунктов производства
(или хранения) различных видов энергетического топлива: Р 1 Р2, ... Рm с объемами производства аi весовых единиц, соответственно, и n потребителей этого
топлива с потребностями b1b2 ... , bn, выраженными, например, в калориях тепла, обеспечиваемого им. Одна весовая единица топлива i-го вида, использованная в условиях j-го потребителя, обеспечивает аij калорий тепла; транспортные расходы, связанные с доставкой одной весовой единицы топлива из
пункта i j-му потребителю равны сij денежных единиц. Требуется так распределить топливо между потребителями, чтобы суммарные транспортные расходы были минимальными.
Задачи такого вида называют распределительными задачами. Для них
разработаны различные алгоритмы решения, хотя и более сложные, чем для
транспортной задачи, однако значительно более простые, чем общие методы
линейного Можно привести еще много различных «усложнений» транспортной задачи, ее обобщений в различных направлениях. Для некоторых из них
имеются специальные методы решения. Рассмотрим, напротив, один частный
случай транспортной задачи, для которого имеется алгоритм решения, более
простой, чем метод потенциалов. Это так называемая задача о назначениях
или задача выбора. Эта задача относится к задачам целочисленного программирования.
Целочисленное программирование ориентировано на решение задач, в
которых все или некоторые переменные должны принимать только целые значения. Различают полностью и частично целочисленные задачи.
Разработан ряд методов решения целочисленных задач, но ни один из
них не обеспечивает желаемой эффективности соответствующих процедур,
что особенно проявляется при увеличении размерности задачи.
Принципиальная сложность ЗЦП состоит в том, что в значительном количестве случаев невозможно заменить дискретную задачу ее непрерывным
аналогом и, найдя соответствующее решение, округлить его до ближайших
целых значений.
44
Выделяют следующие классы дискретных оптимизационных задач:
задачи с неделимостями;
экстремальные комбинаторные задачи;
задачи с разрывными ЦФ;
задачи на несвязных и невыпуклых областях и др.
В большинстве случаев наличие условий неделимости определяется физическими свойствами моделируемых объектов.
Классическая задача – задача о ранце. Солдат (турист), собирающийся в
поход, может нести груз весом не более W кг. Этот груз может состоять из
набора предметовn типов, каждый предмет типа j весит wjкг и характеризуется
некоторой полезностьюuj, j1:n.
Сколько предметов каждого вида нужно взять, чтобы полезность ранца
была максимальной.
Комбинаторные задачи – это задачи оптимизации функции, заданной на
конечном множестве, элементами которого служат выборки из n объектов.
Классический представитель – задача о коммивояжере. К аналогичной модели
приведет задача о разработке графика переналадки оборудования, которое
может выпускать разные типы изделий, но требует определенных затрат (временных или материальных) при переходе с одного технологического режима
на другой.
Задачи с разрывными ЦФ. Многие экономические системы характеризуются наличием так называемых постоянных затрат, которые не зависят от объема производства. Учет в моделях этих и подобных факторов приводит к появлению в них ЦФ, не обладающих свойствами непрерывности.
Метод отсекающих плоскостей, как и метод ветвей и границ, начинает
работу с оптимального решения "обычной" (непрерывной) задачи линейного
программирования. Однако вместо ветвления и построения границ этот метод
видоизменяет пространство допустимых решений, последовательно прибавляя
специальным образом построенные ограничения (именуемые отсечениями).
В общем случае может потребоваться любое (конечное) число отсечений
45
для достижения полностью целочисленной экстремальной точки. В действительности количество необходимых для этого отсечений не зависит от размерности.
Вопросы для самопроверки:
1. Какие задачи относятся к транспортным?
2. Какие основные методы применяют для поиска начального опорного
плана транспортной задачи?
3. Какие методы используют для решения транспортной задачи?
4. Математическая постановка задачи о назначении.
5. Что представляет собой решение, оптимальное по Парето?
6. Какие задачи относятся к задачам целочисленного программирования
7. Для каких задач используется метод приоритетов?
Список литературы и ссылки на интернет-ресурсы по теме:
1. ХэмдиА.Таха, Введение в исследование операций, 7-е издание.: Пер. с
англ. – М.: Издательский дом «Вильямс», 2007.
2. Струченков И. В. Методы оптимизации в прикладных задачах. –
М.:СОЛОН-ПРЕСС, 2009.
3. Просветов Г.И. Методы оптимизации: задачи и решения. Учебнопрактическое пособие. – М., Альфа-Пресс, 2009.
4. Акулич И.Д. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1993.
Интернет ресурс:
1. http://e.lanbook.com/books/element.php?pl1_cid=25&pl1_id=3506
Феду-
нец Н.И. Куприянов В.В. Теория принятия решений: учебное пособие
для вузов – М.: Издательство Московского государственного горного
университета, 2005. – 218 с.
46
2. http://www.aup.ru/books/m157/ Орлов А.И. Теория принятия решений.
Учебное пособие. - М.: Издательство "Март", 2004. - 656 с.
3. http://window.edu.ru/resource/960/44960 Павлов А.Н., Соколов Б.В.
Принятие решений в условиях нечеткой информации: Учебное пособие. - СПб.: ГУАП, 2006. - 72 с.
6 семестр, 3 курс
Лекция 18
Название темы: МНОГОКРИТЕРИАЛЬНЫЕ ЗАДАЧИ.
Цели:
Рассмотреть:
Парето-оптимальность.
Методы решения многокритериальных задач.
Метод уступок.
Метод весовых коэффициентов.
Метод приоритетов
Учебная информация:
Возможны ситуации, когда в модели присутствует несколько (возможно,
конфликтующих между собой) целевых функций. В таких ситуациях иногда
невозможно найти единственное решение, оптимизирующее все конфликтующие целевые функции. Поэтому нужно искать компромиссное решение, учитывающее "важность" каждой целевой функции.
Рассмотрим методы целевого программирования (многокритериальной
оптимизации) для решения задач линейного программирования с несколькими
целевыми функциями. Основное назначение этих методов — преобразование
исходной, задачи с несколькими целевыми функциями в задачу ЛП с одной
47
целевой функцией. После решения преобразованной задачи получаем так
называемое эффективное решение, поскольку может не существовать оптимального решения, доставляющего оптимум частным целевым функциям исходной задачи.
Некоторые частные критерии могут противоречить друг другу. Другие
действуют в одном направлении, третьи — индифферентны, безразличны друг
к другу. Поэтому процесс решения многокритериальных задач неизбежно связан с экспертными оценками как самих критериев, так и взаимоотношений
между ними. Известен ряд методов решения задач многокритериальной оптимизации:
• оптимизация одного признанного наиболее важным критерия, остальные критерии при этом играют роль дополнительных ограничений;
• упорядочение заданного множества критериев и последовательная оптимизация по каждому из них;
• сведение многих критериев к одному введением экспертных весовых
коэффициентов для каждого из критериев, таким образом, что более важный
критерий получает более высокий вес.
Возвращаясь к задаче многокритериальной оптимизации в общей постановке, отметим, что в идеальном случае можно вести поиск такого решения, которое принадлежит пересечению множеств оптимальных решений всех
однокритериальных задач. Однако такое пересечение обычно оказывается пустым множеством, поэтому приходится рассматривать так называемое «переговорное» множество эффективных решений (оптимальных по Парето). Критерий оптимальности итальянского экономиста В. Парето применяется при
решении таких задач, когда оптимизация означает улучшение одних показателей при условии, чтобы другие не ухудшались.
Рассмотрим методы целевого программирования (многокритериальной оптимизации) для решения задач линейного программирования с несколькими
целевыми функциями. Основное назначение этих методов — преобразование
исходной, задачи с несколькими целевыми функциями в задачу ЛП с одной
48
целевой функцией. После решения преобразованной задачи получаем так
называемое эффективное решение, поскольку может не существовать оптимального решения, доставляющего оптимум частным целевым функциям исходной задачи.
В методе весовых коэффициентов единственная целевая функция формируется как взвешенная сумма исходных частных целевых функций. В методе приоритетов на частные цели устанавливаются приоритеты в порядке их важности.
Исходная задача решается путем последовательного решения ряда задач ЛП с
одной целевой функцией таким образом, что решение задачи с низкоприоритетной целью не может "испортить" оптимального значения целевой функции
с более высоким приоритетом.
Эти методы различны по своей природе и в общем случае дают оптимальные решения, не совпадающие между собой. Вместе с тем нельзя сказать, что
один из этих методов лучше другого; в сущности, они предназначены для решения задач с разными прочтениями в процессе принятия решений.
Метод весовых коэффициентов
Предположим, что модель целевого программирования имеет n целей,
каждая из которых имеет следующий вид.
Минимизировать Gi , i=1,2,.,.,n.
В методе весовых коэффициентов обобщенная целевая функция определяется дующим образом.
Минимизировать z = w1G1 + w2G2 + ... + wnGn.
Здесь wi , (i= 1, 2, n) — положительные весовые коэффициенты, которые
отображают предпочтения, отдаваемые каждой цели. Например, случай wi = 1
для всех i говорит о равнозначности всех целей. Задание значений весовым коэффициентам очень субъективно. В настоящее время разработаны различные
методы, которые уменьшают субъективный фактор при определении весовых
коэффициентов.
Пример
49
Новое рекламное агентство, в составе которого 10 рекламных агентов,
получило контракт на рекламу нового продукта. Агентство может провести
рекламную акцию на радио и телевидении. В таблице приведены данные о количестве людей, охватываемых тем или иным видом рекламы, стоимость этой
рекламы и количество необходимых рекламных агентов. Все эти данные отнесены к одной минуте рекламного времени.
Радио
Телевидение
Рекламная аудитория (млн чел.)
4
8
Стоимость (в тыс. долларов)
8
24
Количество рекламных агентов
1
2
Реклама на радио и телевидении должна охватить не менее 45 миллионов
человек (так называемая рекламная аудитория), но контракт запрещает использовать более 6 минут рекламы на радио. Рекламное агентство может выделить на этот проект бюджет, не превышающий $100 000. Сколько минут рекламного времени агентство должно купить на радио и сколько на телевидении?
Обозначим через х1, и х2 количество минут рекламного времени, закупленного соответственно на радио и телевидении. Для данной задачи целевого программирования можно задать следующие частные целевые функции.
Минимизировать G1 = s1+ (для выполнения условия по рекламной аудитории), Минимизировать G2 = s2- (для выполнения условия по бюджету)
при выполнении ограничений
4 х1 + 8 х2+ S1+ - S1- = 45 (условие по рекламной аудитории),
8 х1+ 24x2+ S2+ - S2- = 100 (условия по бюджету),
х1 + 2х2 10 (ограничение по рекламным агентам),
х1 6 (ограничение на рекламу по радио),
все переменные неотрицательны.
Менеджеры рекламного агентства считают, что выполнение условия по
объему рекламной аудитории в два раза важнее, чем выполнение условия по
50
бюджету. Поэтому обобщенная целевая функция будет записана следующим
образом.
Минимизировать z= 2G1 + G2 = 2 S1+ + S2- ,
Оптимальное решение этой задачи, полученное с помощью программы
TORA, следующее: z = 10, х1= 5 минут, х2 = 2,5 минуты, . S1+ =5 миллионов
человек. Остальные переменные равны нулю.
Тот факт, что оптимальное значение целевой функции не равно нулю, указывает, что, по крайней мере, одна из исходных целевых функций не достигла
своего оптимального значения. Действительно, так как S1+ = 5, значит, объем
рекламной аудитории меньше запланированного на 5 миллионов. При этом
условие по бюджету выполнено, поскольку S2- = 0.
Еще раз повторим, что методы целевого программирования позволяют
получить только эффективное решение задачи, которое не всегда будет оптимальным. Например, решение х1= 6 и х2=2 дает такой же объем рекламной
аудитории (4х6+ 8x2= 40 миллионов человек), но при меньшей стоимости рекламной кампании (8 х 6 + 24 х 2 = $96 000). Существенно, что методы целевого программирования в общем случае не находят оптимум каждой целевой
функции исходной модели. Этот "дефект" методов целевого программирования поднимает общий вопрос о "жизнеспособности" целевого программирования в качестве технологии оптимизации.
Метод приоритетов
В методе приоритетов n частных целевых функций ранжируются в порядке их важности, так как их оценивает специалист по принятию решений, т.е
Минимизировать Gi = р1 (наивысший приоритет) …
Минимизировать Сn = рn (наинизший приоритет).
Переменные рi— это компоненты отклоняющих переменных, т.е. Si+ или
Si- , которые определяют i-ю целевую функцию. Например, в задаче о рекламе р1 = Si+ и р2 = S2- .
51
В методе приоритетов поочередно решаются задачи с одной целевой
функцией, начиная с задачи с целевой функцией, имеющей наивысший приоритет, и заканчивая задачей с целевой функцией, имеющей наинизший приоритет. В процессе решения последовательных задач решение задачи с целевой
функцией, имеющей более низкий приоритет, не может ухудшить полученные
ранее решения задач с целевой функцией, имеющих более высокий приоритет.
Это означает, что если z(Gi)— оптимальное значение целевой функции Gi, то
для всех i >1 оптимизация любой целевой функции Gj (j > I) с меньшим приоритетом не может ухудшить значение z(Gi).
Вопросы для самопроверки:
1. Что представляет собой решение, оптимальное по Парето?
2. Какие задачи относятся к задачам целочисленного программирования
3. Для каких задач используется метод приоритетов?
Список литературы и ссылки на интернет-ресурсы по теме:
1. ХэмдиА.Таха, Введение в исследование операций, 7-е издание.: Пер. с
англ. – М.: Издательский дом «Вильямс», 2007.
2. Струченков И. В. Методы оптимизации в прикладных задачах. –
М.:СОЛОН-ПРЕСС, 2009.
3. Просветов Г.И. Методы оптимизации: задачи и решения. Учебнопрактическое пособие. – М., Альфа-Пресс, 2009.
4. Акулич И.Д. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1993.
Интернет ресурс:
1. http://e.lanbook.com/books/element.php?pl1_cid=25&pl1_id=3506 Федунец
Н.И. Куприянов В.В. Теория принятия решений: учебное пособие для
вузов – М.: Издательство Московского государственного горного университета, 2005. – 218 с.
52
2. http://www.aup.ru/books/m157/ Орлов А.И. Теория принятия решений.
Учебное пособие. - М.: Издательство "Март", 2004. - 656 с.
3. http://window.edu.ru/resource/960/44960 Павлов А.Н., Соколов Б.В. Принятие решений в условиях нечеткой информации: Учебное пособие. СПб.: ГУАП, 2006. - 72 с.
Лекции19-20
Название темы:ЗАДАЧИ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. ОПТИМИЗАЦИОННЫЕ ЗАДАЧИ С ОГРАНИЧЕНИЯМИ.
Цели:
Рассмотреть:
Экстремумы функции одной переменной.
Необходимые и достаточные условия оптимальности.
Экстремумы функции многих переменных.
Матрица Гессе, ее связь с необходимым и достаточным условиями оптимальности.
Задачи на условный экстремум.
Решение задач с ограничениями типа равенств.
Метод множителей Лагранжа.
Функция Лагранжа.
Градиентные методы.
.
Учебная информация:
Классическая теория оптимизации основана на использовании дифференциального исчисления для нахождения точек максимумов и минимумов
(экстремумов) функций в условиях отсутствия и наличия ограничений.
Задача нелинейного программирования в общем виде формулируется так:
Максимизировать f(x1, x2, …,xn)
53
при ограничениях
g1(x1, x2, …,xn)≥0
g2(x1, x2, …,xn)≥0
………………
gm(x1, x2, …,xn)≥0
где функции f(x1, x2, …,xn), g2(x1, x2, …,xn)≥0, i=1, m нелинейны.
В отличие от задачи линейного программирования для задач нелинейного программирования нет универсального метода решения.
В задаче линейного программирования допустимое множество R всегда
является выпуклым с конечным числом крайних точек. Поэтому воспользовавшись симплекс-методом и перебрав только крайние точки, можно за конечное число шагов найти оптимальное решение. В задачах нелинейного программирования, наоборот, выпуклость допустимого множества и конечность
числа его крайних точек совсем необязательны. Это и служит причиной основной трудности решения задач нелинейного программирования.
Для определения условного экстремума (то есть экстремума при ограничениях) можно воспользоваться методами дифференциального исчисления,
когда функция f(x1, x2, …,xn), имеет не ниже второй производной. Рассмотрим
некоторые важные понятия и теоремы классического анализа, которые лежат в
основе классических методов поиска условного экстремума .
Вопросы для самопроверки:
1. Постановка задачи нелинейного программирования.
2. В чем заключается метод Лагранжа?
3. Необходимое и достаточное условие оптимальности.
4. Как строится функция Лагранжа?
Список литературы и ссылки на интернет-ресурсы по теме:
54
1. ХэмдиА.Таха, Введение в исследование операций, 7-е издание.: Пер. с
англ. – М.: Издательский дом «Вильямс», 2007.
2. Федоров В.В., Сухарев А.Г., Тимохов А.В., Курс методов оптимизации: учебное пособие, М.: ФИЗМАТЛИТ, 2011 г.
3. Пантелеев А.В. Методы оптимизации в примерах и задачах: Учебное
пособие для втузов. - М.: Высшая школа, 2002.
4. Струченков И. В. Методы оптимизации в прикладных задачах. –
М.:СОЛОН-ПРЕСС, 2009.
5. Просветов Г.И. Методы оптимизации: задачи и решения. Учебнопрактическое пособие. – М., Альфа-Пресс, 2009.
6. Васильев Ф.П. Численные методы решения экстремальных задач. – М.:
Наука, 1988.
7. Химмельблау Д. Прикладное нелинейное программирование М.:Мир,
1989
Интернет ресурс:
1. http://e.lanbook.com/books/element.php?pl1_cid=25&pl1_id=3506 Федунец
Н.И. Куприянов В.В. Теория принятия решений: учебное пособие для
вузов – М.: Издательство Московского государственного горного университета, 2005. – 218 с.
2. http://www.aup.ru/books/m157/ Орлов А.И. Теория принятия решений.
Учебное пособие. - М.: Издательство "Март", 2004. - 656 с.
3. http://window.edu.ru/resource/960/44960 Павлов А.Н., Соколов Б.В. Принятие решений в условиях нечеткой информации: Учебное пособие. СПб.: ГУАП, 2006. - 72 с.
Лекция 21
55
Название темы: ЧИСЛЕННЫЕ МЕТОДЫ ОПТИМИЗАЦИИ.
Цели:
Рассмотреть:
Задачи одномерной оптимизации.
Методы дихотомии, Фибоначчи, «золотого сечения».
Учебная информация:
Метод дихотомии (половинного деления) является одним из методов одномерной безусловной оптимизации унимодальной целевой функции. Алгоритм метода основывается на выборе исходного отрезка поиска решения [a, b]
и последующем делении текущего отрезка пополам:
1) xc=(b+a)/2;
2) x1 = xc- /2; x2= x2+/2 где – точность поиска экстремума;
3) если при минимизации f(x1) < f(x2), то b = xс, иначе a = xс;
4) при b - a <, xопт = ( b + a)/2 и решение получено, иначе на п. 1.
Метод золотого сечения основан на делении отрезка [a,b] по правилу
"золотого" сечения, когда отношение большего отрезка к меньшему const. Такое отношение определяется выражением ( 5 -1)/2 ≈ 0.62. При этом методе в
отличие от метода дихотомии на каждой итерации требуется расчет только
одного значения целевой функции. В результате находится решение xn и соответствующее ему значение целевой функции Zn
Метод Фибоначчи основан на делении отрезка [a, b] с использованием
чисел Фибоначчи, представляющих ряд, у которого последующее число равно
сумме двух предыдущих (1,1,2,3,5,8 и т.д.).
Шаговые методы основаны на том, что текущему приближению к решению xn на каждом новом шаге дается приращение h как xn=xn+h и вычисляется
f(xn). Если новое значение целевой функции "лучше" предыдущего, то пере-
56
менной x дается новое приращение. Если функция "ухудшилась", то поиск в
данном направлении завершен.
Имеется ряд разновидностей шагового метода поиска экстремума целевых функций (прямой поиск, поразрядного приближения, Зейделя и др.), которые широко применяются при решении задач одномерной оптимизации.
Вопросы для самопроверки:
Список литературы и ссылки на интернет-ресурсы по теме:
1. ХэмдиА.Таха, Введение в исследование операций, 7-е издание.: Пер. с
англ. – М.: Издательский дом «Вильямс», 2007.
2. Федоров В.В., Сухарев А.Г., Тимохов А.В., Курс методов оптимизации: учебное пособие, М.: ФИЗМАТЛИТ, 2011 г.
3. Пантелеев А.В. Методы оптимизации в примерах и задачах: Учебное
пособие для втузов. - М.: Высшая школа, 2002.
4. Струченков И. В. Методы оптимизации в прикладных задачах. –
М.:СОЛОН-ПРЕСС, 2009.
5. Просветов Г.И. Методы оптимизации: задачи и решения. Учебнопрактическое пособие. – М., Альфа-Пресс, 2009.
6. Васильев Ф.П. Численные методы решения экстремальных задач. – М.:
Наука, 1988.
7. Химмельблау Д. Прикладное нелинейное программирование М.:Мир,
1989
Интернет ресурс:
1. http://e.lanbook.com/books/element.php?pl1_cid=25&pl1_id=3506 Федунец
Н.И. Куприянов В.В. Теория принятия решений: учебное пособие для
вузов – М.: Издательство Московского государственного горного университета, 2005. – 218 с.
57
2. http://www.aup.ru/books/m157/ Орлов А.И. Теория принятия решений.
Учебное пособие. - М.: Издательство "Март", 2004. - 656 с.
3. http://window.edu.ru/resource/960/44960 Павлов А.Н., Соколов Б.В. Принятие решений в условиях нечеткой информации: Учебное пособие. СПб.: ГУАП, 2006. - 72 с.
Лекции22-23
Название темы: ЗАДАЧИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ.
Цели:
Рассмотреть:
Общая постановказадачи динамического программирования.
Принцип оптимальности и уравнение Беллмана.
Рекуррентная природа вычислений в динамическом программировании.
Примеры содержательных динамических задач и способы их решения.
Учебная информация:
Элементы динамики и учет времени играют важнейшую роль в некоторых
задачах линейного программирования. Например, в общей задаче планирования производственной программы. Основное внимание мы уделяли рассмотрению алгоритмов, которые позволяют находить решение системы, включающей большое число ограничений. В динамическом программировании решающее значение по прежнему имеет одновременный учет всех ограничений системы, однако излагаемый здесь материал в основном посвящен динамическим структурным зависимостям оптимизационных моделей.
Модели ЛП в большинстве случаев используются в промышленности для
принятия крупномасштабных плановых решений в сложных ситуациях. Моде-
58
ли динамического программирования обычно применяются при решении задач
значительно меньшего масштаба.
Области применения моделей динамического программирования при принятии решений:
Разработка правил управления запасами, устанавливающих момент
пополнения запасов и размер пополняющего запаса
Разработка принципов календарного планирования производства и
выравнивания занятости в условиях колеблющегося спроса на продукцию.
Определение необходимого объема запасных частей, гарантирующего
эффективное использование дорогостоящего оборудования.
Распределение дефицитных капитальных вложений между возможными новыми направлениями их использования.
Выбор методов проведения рекламной кампании, знакомящей покупателя с продукцией фирмы.
Систематизация методов поиска ценного вида ресурсов.
Составление календарных планов текущего и капитального ремонта
сложного оборудования.
Разработка долгосрочных правил замены выбывающих из эксплуатации основных фондов.
Модели динамического программирования ценны тем, что позволяют
принимать множество решений на основе стандартного подхода при минимальном вмешательстве человека. Рассмотрим задачу о дилижансе.
Мистер М. отправляется с Востока на Запад. Любой вариант пути включает 4 дилижансовых маршрута – или 4 «шага». Обозначим через Cij стоимость страхового полиса для переезда из штата i в штат j. Цель мистера М. –
выбрать такой маршрут то штата 1 до штата 10, для которого стоимость страхования бала бы минимальной.
Принцип оптимальности. Оптимальная стратегия обладает тем свойством, что, каков бы ни был путь достижения некоторого штата (или состоя-
59
ния), последующие решения должны принадлежать оптимальной стратегии
для части пути, начинающейся с этого состояния.
Задача календарного планирования трудовых ресурсов.
Предпринимателю необходимо составить план регулирования численности рабочих на последующие пять недель. Он оценивает минимальные потребности в рабочей силе biна каждую из пяти недель следующим образом: 5, 7, 8, 4 и 6 рабочих для i=l, 2, 3, и 5 соответственно.
Предприниматель имеет возможность регулировать количество имеющихся в наличии рабочих путем найма и увольнения. При найме рабочих
предприниматель терпит убытки в виде накладных расходов по найму. С
другой стороны, сохранение в течение какой-либо недели количества рабочих, которое превышает минимальную потребность, приводит к убыткам, связанным с простоями рабочих на этой неделе.
Пусть yj— количество рабочих, имеющихся в наличии на j-неделе.
Определим С1(уj—bj,) как величину убытков, связанных с тем, yjпревышает заданное значение bj, а С2(уj—yj-1) — как величину накладных расходов по
найму новых рабочих (уj>yj-1).Предприниматель располагает следующими
данными:
С1(уj—bj,) =3(уj—bj,), j=1, 2…,5,
С2(уj—yj-1)= 4+2(уj—yj-1), уj>yj-1,
0,
уjyj-1
из определения С2 следует, что увольнение,
уjyj-1не требует наклад-
ных расходов.
Необходимо составить оптимальный план регулирования численности
рабочих для 5-недельного периода планирования при условии, что исходное количество y0 рабочих, имеющихся в наличии началу первой недели, составляет пять человек. В данном примере этапы определяются очевидным
образом: каждой неделе соответствует некоторый этап. Иначе обстоит дело
с определением состояния. В рассмотренных выше примерах различия в опре-
60
делениях состояний незначительны, так как все соответствующие задачи
принадлежат классу задач распределения, в которых единственный ресурс
поэтапно распределяется некоторым оптимальным способом. Задача настоящего примера не относится указанному классу и поэтому требует другого
определения состояния.
Вспомним, что состояние должно нести информацию, которая является
достаточной для принятия «будущих» оптимальных и допустимых решений
без обращения к решениям, принятым ранее. В данном случае информация о
количестве рабочих, имеющихся к концу текущей недели, оказывается достаточной для принятия допустимых решений в течение оставшихся недель. Следовательно, состояние на этапе j можно определить как yj-1.
Еще одним элементом модели ДП служит совокупность вариантов решения на этапе j, которая описывается переменной уj. Величина уjвыражает количество рабочих, имеющихся на этапе j.
Таким образом, определены все основные элементы модели ДП.
1. Этап jставится в соответствие j-й неделе.
2. Состояние yj-1 на этапе j выражает количество рабочих, имеющихся к
концу этапа j—1.
3. Варианты решения yjописываются количеством рабочих, имеющихся
на этапе j.
Обозначим через fj(yj-1) минимальную величину расходов, осуществленных в течение периодов времени (недель) j, j+1,..., 5, при заданном yj-1. Рекуррентное соотношение записывается в следующем виде:
F5(y4) = min { С1(у5—b5,) +С2(у5—y4)},
у5=b5
Fj(yj-1) = min { С1(уj—bj,) +С2(уj—yj-1)},
Уj>=bj
j=1,2,3,4.
Перед тем как приступить к вычислениям с использованием таблиц,
необходимо определить границы для значений переменных у1, у2, у3, у4, и у5.
61
Так как j=5 соответствует последнему периоду времени, а увольнение не требует накладных расходов, то значение у5, должно равняться минимальной потребности в рабочей силе b5, т. е. у5,=b5=6. С другой стороны, поскольку
b4(=4)<b5(=6), предприниматель может рассматривать ситуации y4=4, 5 или 6 в
поисках варианта с минимальными расходами. Аналогичные рассуждения
приводят к заключению, что у3=8, у2=7 или 8 и y1=5, 6, 7 или 8. Из условий задачи следует, что исходное количество рабочих y0 равно 5.
Оптимальное
решение задачи
находится
последовательно:
y0=5
y1*=5 y2*=8 y3*=8 y4*=6y5*=6
Вопросы для самопроверки:
1. Постановка задачи динамического программирования.
2. Какие задачи могут быть решены методами динамического программирования?
3. Отличаются ли решения полученные методами прямой и обратной
прогонки?
Список литературы и ссылки на интернет-ресурсы по теме:
1. Калихман И.Л., Войтенко М.А. Динамическое программирование в
примерах и задачах. – М.: Высшая школа, 1979.
2. Карманов В.Г. Математическое программирование, "Наука", М., 1986.
3. Акулич И.Д. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1993.
4. ХэмдиА.Таха, Введение в исследование операций, 7-е издание.: Пер. с
англ. – М.: Издательский дом «Вильямс», 2007.
5. Федоров В.В., Сухарев А.Г., Тимохов А.В., Курс методов оптимизации: учебное пособие, М.: ФИЗМАТЛИТ, 2011 г.
6. Пантелеев А.В. Методы оптимизации в примерах и задачах: Учебное
пособие для втузов. - М.: Высшая школа, 2002.
62
Интернет ресурс:
1. http://e.lanbook.com/books/element.php?pl1_cid=25&pl1_id=3506 Федунец
Н.И. Куприянов В.В. Теория принятия решений: учебное пособие для
вузов – М.: Издательство Московского государственного горного университета, 2005. – 218 с.
2. http://www.aup.ru/books/m157/ Орлов А.И. Теория принятия решений.
Учебное пособие. - М.: Издательство "Март", 2004. - 656 с.
3. http://window.edu.ru/resource/960/44960 Павлов А.Н., Соколов Б.В. Принятие решений в условиях нечеткой информации: Учебное пособие. СПб.: ГУАП, 2006. - 72 с.
Лекции 24-25
Название темы: ПРИНЯТИЕ РЕШЕНИЙ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ.
Цели:
Рассмотреть:
Общая постановка задачи динамического программирования.
Принцип оптимальности и уравнение Беллмана.
Рекуррентная природа вычислений в динамическом программировании.
Примеры содержательных динамических задач и способы их решения.
Учебная информация:
Ранее все задачи принятия решений формулировались и решались в предположении наличия полной информации. Их можно отнести к совокупности
задач принятия решений в условиях определенности. Например, в задаче выбора ассортимента изделий доход Cjот изделия j считался фиксированной величиной. Если Xj— выбранное значение переменной, определяющее уровень
63
выпуска изделия j, то общий вклад в доход от изделия jравен сjхj, являющейся
также фиксированной величиной при заданном значении Xj.
Ограниченность или неточность информации о задаче приводит к двум
новым типам ситуаций, в которых приходится принимать решения:
1) принятие решений в условиях риска;
2) принятие решений при наличии неопределенности.
В первом случае степень неполноты данных выражается через функцию
распределения вероятностей; во втором случае существование подобных
функций не гарантируется. Другими словами, с точки зрения наличия исходных данных определенность и неопределенность представляют два крайних
случая, а риск определяет промежуточную ситуацию.
Проиллюстрируем различие между ситуациями, когда приходится принимать решения в условиях риска и неопределенности, рассмотрим вышеупомянутую задачу выбора ассортимента изделий. В условиях риска доход Cjуже
не является фиксированным. Напротив, это случайная величина, точное числовое значение которой не известно, но описывается с помощью функции распределения f(Cj). Таким образом, нет никакого смысла говорить о величине Cj,
не связывая ее с вероятностями, с которыми она принимает то или иное значение. Часть прибыли, CjXj, определяемая изделием j, также случайная величина, точное значение которой неизвестно, даже если значение Xjзадано.
В условиях неопределенности функция распределения f(cj) либо неизвестна, либо не может быть определена. В действительности неопределенность не означает полного отсутствия информации о задаче. Например, лицо,
принимающее решение, может располагать сведениями, что с}принимает одно
из трех значений: сj, сj, с"j.Пока не известны вероятности этих значений, ситуация рассматривается как принятие решений в условиях неопределенности.
Степень неинформированности о данных непосредственно определяет,
каким образом задача формализуется и решается. Например, предположим,
что в задаче выбора ассортимента общее число изделий n. В условиях полной
определенности имеет смысл использовать z=clx1+c2x2+...+cnxn в качестве кри-
64
терия, подлежащего максимизации при надлежащих ограничениях. Конечно, в
условиях риска тот же критерий будет малозначимым без некоторых вероятностных предположений, так как в действительности является случайной величиной. Указанный критерий становится совершенно неадекватным в условиях неопределенности, так как значения величин Cj не известны. Этот простой пример показывает, что неполнота данных усложняет задачу принятия
решений и неизбежно приводит к менее удовлетворительным результатам.
К сожалению, из-за недостаточности данных часто используются противоречащие друг другу подходы к задачам принятия решений и оценке их результатов. При полной определенности критерий максимума прибыли (или
минимума затрат) является почти универсальным. Напротив, для ситуаций с
риском или неопределенностью существует ряд возможных критериев.
Например, в условиях риска иногда целесообразна максимизация ожидаемой
прибыли, но встречаются случаи, когда это неверно. Другие критерии образуют целый спектр от максимально «пессимистичных» до максимально «оптимистичных». Положение усложняется в условиях неопределенности.
В большинстве задач принятия решений требуется выбирать наилучший
способ (или способы) действия из некоторого множества (возможно, бесконечного) допустимых альтернатив. Ни в одном из рассмотренных случаев не
предполагалось, что решения принимаются в условиях, когда сама система
стремится «помешать» лицу, принимающему решение. Для пояснения предположим, что некоторое лицо принимает решение в зависимости от того, будет
дождь или нет. В этом случае природа не будет восприниматься как недоброжелательный противник.
В процессах принятия решений при наличии неопределенности существуют ситуации конкуренции, когда два (или более) участника находятся в
конфликте и каждый стремится как можно больше выиграть у другого (других). Эти ситуации отличаются от обычных процессов принятия решений в
условиях неопределенности тем, что принимающему решение противостоит
65
мыслящий противник. Теория, в которой рассматриваются подобные задачи
принятия решений, известна как теория игр.
Теория игр - теория математических моделей, интересы участников которой различны, причем цели они достигают различными путями.
Рассмотрим решения в условиях неопределенности, принимаемые двумя
или более «разумными» противниками, каждый из которых стремится оптимизировать свои решения за счет других. К числу типичных примеров подобных
ситуаций относятся рекламирование конкурирующих товаров и тактическое
планирование противоборствующих армий.
В теории игр противников принято называть игроками.
Исход конфликта – выигрыш.
Каждый игрок имеет некоторое множество (конечное или бесконечное)
возможных выборов, называемых стратегиями.
Результаты или платежи в игре задаются функциями, зависящими от
стратегий каждого из игроков. Игры с двумя игроками, в которых выигрыш
одного из них равен проигрышу другого, известны как игры двух лиц с нулевой суммой. В такой игре достаточно задать результаты в виде платежей для
одного из игроков.
В зависимости от количества стратегий игры бывают конечные и бесконечные.
Простейший вид стратегической игры - игра двух с нулевой суммой (антагонистические игры).
Для иллюстрации определений игры двух лиц с нулевой суммой рассмотрим игру на совпадение сторон монеты, в которой два игрока А и В выбирают
герб (Г) или решетку (Р). Если результаты совпадают (т. е. Г и Г или Р и Р), то
игрок А получает 1 долл. от игрока В. В противном случае игрок А платит 1
долл. игроку В.
В этой игре каждый из игроков имеет две стратегии (Г или Р), которые
составляют матрицу игры размерами 2x2, представляющую выигрыш игрока
А.
66
Игрок В
Игрок А
Г
Р
Г
1
-1
Р
-1
1
«Оптимальное» решение в такой игре может потребовать от игроков выбора чистых стратегий либо какой-нибудь комбинации чистых стратегий –
решение в смешанных стратегиях.
Обычно выбор критерия в задачах принятия решений в значительной мере определяется имеющейся информацией. Игры представляют собой предельный случай полного отсутствия информации, когда разумные противники
находятся в состоянии конфликта. В силу этого для решения игры двух лиц с
нулевой суммой обычно предлагается очень «пессимистичный» критерий, так
называемый критерий минимакса-максимина. В теории игр каждый игрок
действует разумно и, следовательно, пытается активно помешать своему противнику.
Чтобы учесть, что каждый из игроков действует против другого, критерий
минимакса выделяет из всех стратегий (чистых или смешанных) те, которые
дают наилучшие или наихудшие возможные результаты. Говорят, что оптимальное решение достигнуто, если ни одному из игроков невыгодно изменить
свою стратегию. В этом случае игра считается стабильной или находящейся в
состоянии равновесия.
Так как обычно матрица игры представляет выигрыши игрока А (стратегии которого определяются строками), критерий предписывает игроку А выбрать такую стратегию (чистую или смешанную), которая максимизирует его
минимальный выигрыш, причем минимум берется по всем стратегиям игрока
В. Точно так же игрок В выбирает стратегию, которая минимизирует его максимальный проигрыш. Максимум теперь берется по стратегиям игрока А.
Если Аi – это i- я стратегия игрока А, I=1,..n, выбранная из множества его
стратегий, Вj– стратегия игрока В, j=1,…m, то функция выигрыша:
1(Аi, Вj) + 2(Аi, Вj)0, где
67
1 – выигрыш первого игрока,
2 – выигрыш второго игрока.
Платежная матрица А
а11
а12
…
а1n
a21
a22
…
a2n
…
…
…
…
am1
am2
…
amn
aij – тот выигрыш, который получит игрок А, если он выберет стратегию i,
а игрок В выберет стратегию j.
Пример показывает, каким образом подсчитываются минимаксное и максиминное значения игры.
Рассмотрим платежную матрицу
Игрок В
1
2
3
43
Минимумы в
строках
Игрок А
Максимумы
1
8
2
9
5
2
2
6
5
7
18
5максимин
3
7
3
-4
10
-4
8
5
9
11
в столбцах
минимакс
Если игрок А выбирает первую стратегию, он может получить 8, 2, 9 или
5 в зависимости от стратегии, выбранной игроком В. Его выигрыш будет не
меньше min{8, 2, 9, 5}=2 независимо от поведения игрока В. Аналогично при
выборе игроком А второй стратегии гарантированный выигрыш будет равен
min{6, 5, 7, 18}=5, и, наконец, если он выбирает третью стратегию, гарантированный выигрыш будет равен min {7, 3,-4, 10}= - 4. Таким образом, минимальные значения в каждой строке определяют минимально гарантированный
выигрыш для игрока А, если он выбирает соответствующую стратегию. Эти
68
значения указаны в столбце «Минимумы в строках». Теперь игрок А, выбирая
вторую стратегию, максимизирует свой минимальный выигрыш. Его значение
равно max {2, 5, -4}=5. Выбранная игроком А стратегия называется максиминной стратегией, а соответствующее ей значение выигрыша — максиминным
(нижним) значением игры.
Игрок В хочет минимизировать свой проигрыш. Выбрав первую стратегию, он может проиграть не более чем тах{8, 6, 7}=8 независимо от выбора
своего противника. Подобные рассуждения можно продолжить для остальных
трех стратегий. Соответствующие результаты указаны выше в строке «Максимумы в столбцах». Игрок В выберет стратегию, которая минимизирует его
максимальные проигрыши. Такой стратегией будет вторая, для которой проигрыш игрока В составит min{8, 5, 9, 18}=5. Эта стратегия называется минимаксной, а соответствующее ей значение проигрыша игрока В, — минимаксным (или верхним) значением игры.
Из условий, определяющих критерий минимакса, следует, что минимаксное (верхнее) значение всегда больше, чем максиминное (нижнее) значение,
или равно ему. В случае когда имеет место равенство, т. е. минимаксное значение равно максиминному, соответствующие чистые стратегии называются
оптимальными, а про игру говорят, что она имеет седловую точку. Значение
игры, определяемое парой оптимальных чистых стратегий, равно минимаксному и максиминному значениям. «Оптимальность» здесь означает, что ни
один игрок не стремится изменить свою стратегию, так как его противник может на это ответить выбором другой стратегии, дающей худший для первого
игрока результат. Вообще значение игры должно удовлетворять неравенствам:
Максиминное (нижнее ) значение Значение игры Минимаксное
(верхнее ) значение.
В вышеприведенном примере максиминное значение равно минимаксному значению (=5). Это означает, что игра имеет седловую точку, задаваемую
элементом матрицы (2, 2). Значение игры, таким образом, равно 5. Отметим,
69
что ни один из игроков не может улучшить свою позицию выбором какойнибудь другой стратегии.
Смешанные стратегии
В предыдущем подразделе показано, что из существования седловой точки непосредственно следует существование оптимальных чистых стратегий в
игре. Однако некоторые игры могут не иметь седловых точек.
Поскольку, пользуясь чистыми максиминно-минимаксными стратегиями,
в общем случае невозможно получить оптимальные решения игры, появилась
идея использования смешанных стратегий. Каждый игрок вместо выбора одной из чистых стратегий может выбирать любую из них с заранее заданными
вероятностями. Пусть x=(x1, хг, ..., хт) и y=(y1, уг, • ••, yп) — наборы вероятностей, с которыми игроки А и В соответственно выбирают свои чистые стратегии. Тогда
m
n
i 1
j 1
xi y j 1
xi ,yj0 для всех i и j.
Подход к определению решения игры при смешанных стратегиях также
основывается на критерии минимакса. Единственная разница заключается в
том, что игрок А выбирает хi так, чтобы максимизировать наименьший ожидаемый выигрыш по столбцам, тогда как игрок В выбирает yj с целью минимизировать наибольший ожидаемый проигрыш по строкам. Математически
критерий минимакса при смешанных стратегиях может быть описан следуюm
x 1
щим образом. Игрок А выбирает стратегию хi (хi 0, i 1
i
m
m
m
min ai1 xi , ai 2 xi ,... ain xi ,
max
xi
i 1
i 1
i 1
n
Игрок А выбирает стратегию YJ (YJ0, y j 1 ), дающую
j 1
), дающую
70
n
n
n
max a1 j y j , a 2 j y j ,... amj y j .
min
yj
j 1
j 1
j 1
Эти величины определяются соответственно как ожидаемые максиминные и минимаксные платежи.
Как и в случае чистых стратегий, выполняется соотношение
Минимаксный ожидаемый проигрыш Максиминный ожидаемый выигрыш.
Когда xi и уj соответствуют оптимальным решениям, выполняется строгое равенство, и результирующее значение равно ожидаемому (оптимальному)
значению игры. Это утверждение следует из теоремы о минимаксе. Если хi* и
уj* — оптимальные решения для обоих игроков, каждому элементу платежной
матрицы аij соответствует вероятность хi*уj*. Следовательно, оптимальное
ожидаемое значение игры
m
n
v * aij xi* y *j .
i 1 j 1
Вопросы для самопроверки:
1. Дайте определение стратегической игры.
2. Что значит игра с седловой точкой?
3. Почему принцип минимакса называют пессимистическим?
4. Как определяется максиминный ожидаемый выигрыш?
5. Что значит решение в смешенных стратегиях?
Список литературы и ссылки на интернет-ресурсы по теме:
1. Карманов В.Г. Математическое программирование, "Наука", М., 1986.
2. Акулич И.Д. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1993.
71
3. ХэмдиА.Таха, Введение в исследование операций, 7-е издание.: Пер. с
англ. – М.: Издательский дом «Вильямс», 2007.
4. Федоров В.В., Сухарев А.Г., Тимохов А.В., Курс методов оптимизации: учебное пособие, М.: ФИЗМАТЛИТ, 2011 г.
5. Пантелеев А.В. Методы оптимизации в примерах и задачах: Учебное
пособие для втузов. - М.: Высшая школа, 2002.
Интернет ресурс:
1. http://e.lanbook.com/books/element.php?pl1_cid=25&pl1_id=3506 Федунец
Н.И. Куприянов В.В. Теория принятия решений: учебное пособие для
вузов – М.: Издательство Московского государственного горного университета, 2005. – 218 с.
2. http://www.aup.ru/books/m157/ Орлов А.И. Теория принятия решений.
Учебное пособие. - М.: Издательство "Март", 2004. - 656 с.
3. http://window.edu.ru/resource/960/44960 Павлов А.Н., Соколов Б.В. Принятие решений в условиях нечеткой информации: Учебное пособие. СПб.: ГУАП, 2006. - 72 с.
72
МИНИСТЕРСТВООБРАЗОВАНИЯИНАУКИРОССИЙСКОЙФЕДЕРАЦИИ
Федеральноегосударственноеавтономноеобразовательное учреждение
высшего профессионального образования
«Дальневосточный федеральный университет»
(ДВФУ)
ШКОЛА ЕСТЕСТВЕННЫХ НАУК
МАТЕРИАЛЫ ПРАКТИЧЕСКИХ ЗАНЯТИЙ
по дисциплине «Теория принятия решений»
Специальность - 230102.65 «Автоматизированные системы обработки информации и управления»
Форма подготовки - очная
г. Владивосток
2011
73
5 семестр, 3 курс
Тема.Задачи линейного программирования
Практическое занятие 1. Построение моделей задачи линейного программирования и ее графическое решение для случая двух переменных. Канонический вид ЗЛП. Опорное решение
Задачи для решения:
1. Крупная свиноферма (условно назовем ее «Суперрацион») имеет возможность покупать от одного до трех различных видов зерна и приготавливать
различные виды смесей (комбикормов). Различные зерновые культуры содержат разное количество питательных компонентов (ингредиентов). Допустим,
что принимаются в расчет четыре компонента. (Все данные приведены в таблице) Управляющим свинофермой установлено, что комбикорм для свиней
должен удовлетворять по крайней мере некоторым минимальным требованиям
с точки зрения питательности; он стремится определить, какая из всех возможных смесей является самой дешевой.
Минимальные
Единица веса
Зерна
Зерна 2
1
Зерна
суммарные
3
потребности
ИнгредиентА
2
3
7
1250
ИнгредиентВ
1
1
0
250
ИнгредиентС
5
3
0
900
ИнгредиентД
0,6
0,25
1
232,2
Затраты в расчете 41
на единицу веса
35
96
минимизировать
(цена),долл.
2. Фирмой «Супертранзистор» выпускаются радиоприемники трех различных
моделей: модельА, модель В и модель С. Каждое изделие указанных моделей
74
приносит доход в размере 8, 15 и 25 соответственно. Необходимо, чтобы фирма выпускала за неделю не менее 100 приемников модели А, 150 приемников
модели В и 75 приемников модели С.
Каждая модель характеризуется определенным временем, необходимым для
изготовления соответствующих деталей, сборки изделия и его упаковки. В
расчете на 10 приемников модели А требуется 3 часа для изготовления соответствующих деталей, 4 ч. на сборку и 1 ч на упаковку. Соответствующие показатели в расчете на 10 приемников модели В равняются 3,5, 5 и 1,5 ч, а на 10
приемников модели С — 5, 8 и 3. В течение ближайшей недели фирма может
израсходовать на производство радиодеталей 150 ч, на сборку 200 ч и на упаковку 60 часов.
3. Фирмой «Радость» выпускаются игрушечные машины трех различных моделей: модельА, модель В и модель С. Каждое изделие указанных моделей
приносит доход в размере 9, 13 и 21 рублей соответственно. Необходимо, чтобы фирма выпускала за неделю не менее 120 игрушек модели А, 140 игрушек
модели В и 90 игрушек модели С.
Каждая модель характеризуется определенным временем, необходимым для
изготовления соответствующих деталей, сборки машинки и ее упаковки. В
расчете на 10 игрушек модели А требуется 4часа для изготовления соответствующих деталей, 2 ч. на сборку и 0,5 ч на упаковку. Соответствующие показатели в расчете на 10 игрушек модели В равняются 4, 3 и 0,3 ч, а на 10 игрушек модели С — 6, 3 и 0,5. В течение ближайшей недели фирма может израсходовать на производство игрушек 250 ч, на сборку 150 ч и на упаковку 20 часов.
Построить математическую модель задачи.
4. Фирма производит два вида продукции — А и В. Объем сбыта продукции
вида А составляет не менее 60% общего объема реализации продукции обоих
видов. Для изготовления продукции А и В используется одно и то же сырье,
суточный запас которого ограничен величиной 100 фунтов. Расход сырья на
75
единицу продукции А составляет 2 фунта, а на единицу продукции В — 4
фунта. Цены продукции А и В равны 20 и 40 долл. соответственно. Определите оптимальное распределение сырья для изготовления продукции А и В.
5. Фирма выпускает ковбойские шляпы двух фасонов. Трудоемкость изготовления шляпы фасона 1 вдвое выше трудоемкости изготовления шляпы фасона
2. Если бы фирма выпускала только шляпы фасона 1, суточный объем производства мог бы составить 500 шляп. Суточный объем сбыта шляп обоих фасонов ограничен диапазоном от 150 до 200 штук. Прибыль от продажи шляпы
фасона 1 равна 8 долл., а фасона 2—5 долл. Определите, какое количество
шляп каждого фасона следует изготавливать, чтобы максимизировать прибыль.
Построить математическую модель задачи.
6. Фирма выпускает спортивные костюмы двух фасонов. Трудоемкость изготовления костюма фасона 1 вдвое выше трудоемкости изготовления костюма
фасона 2. Если бы фирма выпускала только костюмы фасона 1, суточный объем производства мог бы составить 1000 костюмов. Объем сбыта костюмов
обоих фасонов ограничен диапазоном от 1300 до 2000 штук. Прибыль от продажи костюма фасона 1 равна 16 долл., а фасона 2—11 долл. Определите, какое количество костюмов каждого фасона следует изготавливать, чтобы максимизировать прибыль.
7. Для изготовления различных видов изделий А, В, С предприятие использует три различных вида сырья. Нормы расхода сырья на производство одного
изделия каждого вида, цена одного изделия каждого вида, а также общее количество сырья каждого вида, которое может быть использовано предприятием, приведены в таблице:
Вид сырья
Нормы затрат сырья (кг) на одно из- Общее
личество
делие
А
1
В
18
сырья
С
15
12
1360
ко-
76
2
6
6
8
592
3
5
3
3
680
Цена одно-
9
10
16
максимизи-
го
изделия
ровать
(руб.)
Составить план производства изделий, при котором общая стоимость изделий
будет максимальной.
8. Для изготовления трех видов изделийА, В и С используется токарное, фрезерное, сварочное и шлифовальное оборудование. Затраты времени на обработку одного изделия для каждого из типов оборудования указаны в таблице.
В ней же указан общий фонд рабочего времени каждого из типов используемого оборудования, а также прибыль от реализации одного изделия данного
вида.
Тип
Затраты времени (станко-ч) Общий фонд ра-
оборудова-
на обработку одного изде- бочего
ния
лия вида
времени
оборудован
А
В
С
Фрезерное
2
6
3
230
Токарное
1
4
4
340
Сварочное
8
3
7
455
Шлифоваль-
5
9
4
370
12
15
10
максимизировать
ное
Прибыль
Требуется определить, сколько изделий и какого вида следует изготовить
предприятию, чтобы прибыль от их реализации была максимальной. Составить математическую модель задачи.
9. Кондитерская фабрика для производства трех видов карамелиА, В и С использует три вида основного сырья: сахарный песок, патоку и фруктовое пюре. Нормы расхода сырья на производство 1т. карамели и прибыль от реализации 1 т. карамели приведены в таблице.
77
вид сырья
Нормы расхода сырья (т.)
Общее
на 1т.
личество
карамели
сырья (т.)
ко-
А
В
С
сахарный
0,8
0,5
0,6
800
песок
0,4
0,4
0,3
640
патока
-
0,1
0,2
124
102
115
126
максимизи-
фруктовое
пюре
Прибыль
ровать
Найти план производства карамели, обеспечивающий максимальную прибыль
от ее реализации.
10. Фирма производит два вида продукции — тапочки и туфли. Объем сбыта
туфель составляет не менее 70% общего объема реализации продукции обоих
видов. Для изготовления тапочек и туфель используется одно и то же сырье,
суточный запас которого ограничен величиной 200 единиц. Расход сырья на
тапочки составляет 2 единицы, а на туфли — 4 единицы. Цены на тапочки и
туфли равны 40 и 90 рублей соответственно. Определите план производства из
условия максимальной прибыли.
Построить математическую модель задачи.
11. Нефтеперерабатывающий завод получает 4 полуфабриката: 400 тыс. л. алкилата, 250 тыс. л. крекинг-бензина, 350 тыс. л. бензина прямой перегонки и
100 тыс. л. изо-пентана.
В результате смешивания этих четырех компонентов в разных пропорциях образуются три сорта бензина: бензин А(3:4:2:1), бензин В(2:4:1:3) и бензин
С(3:4:2:1). Стоимость 1 тыс. л. бензина каждого сорта равна 320 руб., 200 руб.
и 250 руб.
Определить выпуск продукции, исходя из условия максимальной стоимости.
78
12. В аптеке получают лекарственные микстуры путем смешивания пяти основных компонентов. Запасы которых составляют: компонент А – 5 литров,
компонент В – 3,5 литров,
компонент С – 6 литров,
компонент Д – 3,3 литров,
компонент Е – 12 литров.
В результате смешивания этих пяти компонентов в разных пропорциях образуются три микстуры: микстура 1(3:4:2:1:6), микстура 2 (2:4:1:1:3) и микстура
3 (3:4:2:1:5).
Определить выпуск продукции, исходя из условия максимального использования компонентов.
13. На предприятие поступили две партии фанеры, причем первая партия содержит 200 листов, а вторая — 350 листов фанеры. Из них изготовляются
комплекты, включающие 3 детали 1-го типа, 2 детали 2-го типа и 4 детали 3-го
типа. Один лист фанеры каждой партии может раскраиваться двумя способами
Количество деталей каждого типа, которое получается при раскрое одного листа по тому или иному способу, представлено в таблице.
Тип
Количество деталей
Первая партия
Вторая партия
детаСпособ 1 . Способ 2 Способ Способ 2
ли
1
1
4
8
1
8
2
6
4
7
3
3
9
6
4
6
Требуется раскроить материал так, чтобы обеспечить изготовление максимального числа комплектов.
14. Механический завод при изготовлении трех разных деталей I, II, III использует токарные, фрезерные и строгальные станки. Обработку каждой детали можно вести тремя различными технологическими способами Т1, Т2 и Т3.
В таблице указаны нормы времени обработки детали на соответствующем
79
станке каждым технологическим способом, а также ресурсы (станко-часы)
каждой группы станков.
Тип стан- Нормы времени на обработку Ресурс
I
II
III
ка
деталей, ч
времени
Т2 1,
Т 0,9
Т1 Т2
Токарный Т1
1 0,9
0, Т3
0, Т1
- Т2
- Т3
-
200
Фрезер-
450
0, 0,8 3
3 0,7 5 8 1, 0, -
ный
0,7 1, каждого
1,0 1, 0,вида
3 деталей
8 - составляет
340
Прибыль
от 8продажи
соответственно 22, 18 и
строгаль30
руб.
-
1
5 8 1, 0,
ный
1,
- - загрузки
6 6 станков, обеспечивающий максимальСоставить
оптимальный
план
2 что количество выпускаемых деталей удовлетворяет соную прибыль, считая,
отношению комплектности 1 : 2 : 1.
Литература:
1. ХэмдиА.Таха, Введение в исследование операций, 7-е издание.: Пер. с
англ. – М.: Издательский дом «Вильямс», 2007.
2. Федоров В.В., Сухарев А.Г., Тимохов А.В., Курс методов оптимизации:
учебное пособие, М.: ФИЗМАТЛИТ, 2011 г.
3. Пантелеев А.В. Методы оптимизации в примерах и задачах: Учебное пособие для втузов. - М.: Высшая школа, 2002.
Практические занятия 2-5.
Основной алгоритм задачи линейного программирования: симплексметод. М-метод.
Двойственный симплекс-метод. . Анализ решения на чувствительность.
Задачи для решения:
80
1. F=2x1+8x2+3x3 min
2. F=2x1+5x2+4x3 min
6x1+2x2+3x312
3x1-x2+x36
4x1+3x2+4x36
x1+3x2+5x315
3x1+2x2+x38
3x1+2x2-2x36
x1, x2, x30
x1, x2, x30
3. F=x1+2x2+3x3 min
4. F=3x1+2x2+7x3 max
4x1+2x2+3x312
3x1-3x2+4x312
2x1-4x2+4x38
2x1+x2+3x33
3x1+2x2+x36
x1+2x2+x31
x1, x2, x30
x1, x2, x30
5.
F=3x1+5x2+3x3 min
6. F=4x1+10x2+8x3 min
3x1+x2+3x312
3x1-x2+x36
4x1+3x2+4x36
x1+3x2+5x315
3x1+2x2+x38
3x1+2x2-2x36
x1, x2, x30
x1, x2, x30
7. F=4x1+2x2+5x3 min
8. F=6x1+4x2+10x3 min
3x1+x2+3x312
3x1+x2+3x312
4x1+3x2+4x36
4x1+3x2+4x36
3x1+2x2-x38
3x1+2x2-x38
x1, x2, x30
x1, x2, x30
81
9. F=5x1+2x2+3x3 min
10. F=10x1+4x2+6x3 min
4x1+2x2+3x312
4x1+2x2+3x312
2x1-4x2+4x38
1x1-2x2+2x34
3x1+2x2+x36
3x1+2x2+x36
x1, x2, x30
x1, x2, x30
Литература:
1. ХэмдиА.Таха, Введение в исследование операций, 7-е издание.: Пер. с
англ. – М.: Издательский дом «Вильямс», 2007.
2. Федоров В.В., Сухарев А.Г., Тимохов А.В., Курс методов оптимизации: учебное пособие, М.: ФИЗМАТЛИТ, 2011 г.
3. Пантелеев А.В. Методы оптимизации в примерах и задачах: Учебное
пособие для втузов. - М.: Высшая школа, 2002.
Интернет ресурс:
1. http://e.lanbook.com/books/element.php?pl1_cid=25&pl1_id=3506 Федунец
Н.И. Куприянов В.В. Теория принятия решений: учебное пособие для
вузов – М.: Издательство Московского государственного горного университета, 2005. – 218 с.
2. http://www.aup.ru/books/m157/ Орлов А.И. Теория принятия решений.
Учебное пособие. - М.: Издательство "Март", 2004. - 656 с.
3. http://window.edu.ru/resource/960/44960 Павлов А.Н., Соколов Б.В. Принятие решений в условиях нечеткой информации: Учебное пособие. СПб.: ГУАП, 2006. - 72 с.
82
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное образовательное учреждение
высшего профессионального образования
«Дальневосточный федеральный университет»
(ДВФУ)
ШКОЛА ЕСТЕСТВЕННЫХ НАУК
МАТЕРИАЛЫ ДЛЯ ОРГАНИЗАЦИИ САМОСТОЯТЕЛЬНОЙ РАБОТЫ СТУДЕНТОВ
по дисциплине «Теория принятия решений»
Направление - 230100 «Информатика и вычислительная техника»
Специальность - 230102 «Автоматизированные системы обработки информации и управления»
Форма подготовки - очная
г. Владивосток
2011
83
Объем дисциплины и виды учебной работы
Вид учебной работы
Всего
часов
Общая трудоемкость дисциплины
108
Лекции
18
Практические занятия
36
Всего самостоятельная работа
54
Подготовка к аудиторным за-
36
нятиям
Подготовка к экзаменам
18
Вид итогового контроля
экзамен
Подробное содержание дисциплины приводится в рабочей программе учебной
дисциплины (имеется у лектора и на кафедре ИСУ) и отражено в контрольноизмерительных материалах.
Лекции и практические занятия
Принятая в рабочей программе учебной дисциплины "Методы оптимизации" технология освоения теоретического и практического материала предусматривает проведения студентом самостоятельного изучения положений
дисциплины по учебной литературе в рамках часов отведенных для самостоятельной работы. Магистрант должен до посещения практического занятия
ознакомиться с материалом по изучаемой теме и ответить на вопросы, соответствующие теме занятия в письменной форме. По итогам практических занятий магистрант должен выполнить решение предложенных задач. Все затруднения в освоении материала фиксируются студентом в конспекте для
устранения неясности с помощью преподавателя на аудиторном занятии.
84
Консультации
Консультации проводятся по расписанию, размещенному на стенде кафедры.
Перечень вопросовпромежуточного и итогового контроля представлен в контрольно-измерительных материалах
Аттестационные оценки промежуточной аттестации и итоговой аттестации
выставляются
согласно
методике,
представленной
измерительных материалах по дисциплине.
в
контрольно-
85
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное образовательное учреждение
высшего профессионального образования
«Дальневосточный федеральный университет»
(ДВФУ)
ШКОЛА ЕСТЕСТВЕННЫХ НАУК
КОНТРОЛЬНО-ИЗМЕРИТЕЛЬНЫЕ МАТЕРИАЛЫ
по дисциплине «Теория принятия решений»
Специальность - 230102 «Автоматизированные системы обработки информации и управления»
Форма подготовки - очная
г. Владивосток
2011
86
АННОТАЦИЯ
Комплект педагогических измерительных материалов дисциплины «Методы оптимизации» предназначен для проведения промежуточного контроля и
итогового экзамена. Приводится развернутое содержание дисциплины, наборы заданий по разделам, структура и пример билета, шкала и правила оценки.
Нормативное время выполнения заданий билета - 60 минут.
Материалы предназначены для магистрантов образовательных программ«Информационные системы предприятий" и «Методы анализа и синтеза
проектных решений»направления 230100 "Информатика и вычислительная
техника".
СОДЕРЖАНИЕ
1.
2.
Общие положения
1.1.
Цель материалов
1.2.
Условия применения
1.3.
Содержание материалов
1.4.
Структура
1.5.
Время выполнения
1.6.
Шкала и правила оценки
Набор заданий
Приложение 1.
Развернутое содержание дисциплины "Методы
87
оптимизации"
Приложение 2. Образец бланка билета
88
1. ОБЩИЕ ПОЛОЖЕНИЯ
1.1. Цель материалов
Повышение качества освоения студентами дисциплины "Методы оптимизации", изучаемой в рамках рабочей учебной программы, за счет применения
ими структурированных и взаимно согласованных обучающих и контролирующих материалов.
1.2. Условия применения
Педагогические измерительные материалы предназначены для магистрантов 1-го курса образовательных программ «Информационные системы
предприятий" и «Методы анализа и синтеза проектных решений» направления 230100 "Информатика и вычислительная техника". Материалы применяются на этапах изучения дисциплины, подготовки студентов к итоговой аттестации по дисциплине и в период проведения итоговой аттестации.
1.3. Содержание материалов
Содержание педагогических измерительных материалов определяется рабочей учебной программой и состоит их следующих разделов:
1. ВВЕДЕНИЕ В Методы оптимизации.
2. Задачилинейного программирования. Теориядвойственности.
3. Специальныезадачи линейного программирования и методы их решения.
4. Многокритериальные задачи.
5. Задачинелинейного программирования. Методы одномерной и многомерной оптимизации.
6. Оптимизационные задачи с ограничениями.
7. Численные методы оптимизации.
8. Задачи динамического программирования.
89
1.4. Структура
Работа, выполняемая студентом, имеет форму билета, заполняемого магистрантом в свободной форме письменно. Билет состоит из вопросов равного
уровня сложности. Структура тест-билета зависит от цели применения. Для
осуществления промежуточного контроля содержание вопросов, включаемых
в билет, должно соответствовать изученному разделу курса. При проведении
итогового контроля знаний по дисциплине вопросы должныохватывать все
изученные разделы дисциплины.Экзаменационный билет содержит 2 теоретических вопроса и одну практическую задачу. Образец билета приведен в прил.
2.
1.5. Время выполнения
На выполнение экзаменационной работы отводится 60 минут.
1.6. Шкала и правила оценки
Оценивание ответа на билет производится в два этапа:
оценивание ответов на каждое из заданий билета;
определение интегрированной оценки за тест.
Ответ на каждое задание оценивается по четырехбалльной системе (5, 4,
3, 2). При этом каждой из возможных оценок соответствуют следующая характеристика ответа:
"5" - студент показал глубокие знания теории, свободное владение материалом, умение соотносить понятийный аппарат с реальными фактами и
явлениями, умение анализировать и творчески использовать теоретические положения для решения практических задач. Ответ по форме логичен, содержателен и обоснован.
"4" - студент показал достаточные знания теории, хорошее осмысление
основных вопросов анализируемой проблемы, однако в меньшей степе-
90
ни проявил умение свободно оперировать категориальными понятиями,
умение применять теоретические понятия на практическом материале.
Ответ по форме логичен, содержателен, но недостаточно полон и аргументирован.
"3" - студент показал знание основных теоретических положений, но допустил существенные пробелы в теоретической подготовке, а также
проявил определенные затруднения и неточности.
"2" - студент не владеет программным материалом в объеме, необходимом для профессиональной деятельности.
Интегрированная оценка билета производится по сумме баллов, полученных
за выполнение всех заданий. При этом оценка "отлично" проставляется при
сумме баллов, превышающей 90% от ее возможного максимального значения;
оценка "хорошо" - при сумме баллов, попадающей в интервал 89-72%; оценка
"удовлетворительно" - при сумме баллов, попадающей в интервал 71-52%.
2. НАБОР ЗАДАНИЙ
Раздел 1. Теоретические вопросы
1.
Математическое моделирование. Переход от реальной системы к математической модели задачи организационного управления.
2.
Классификация моделей ИСО.
3.
Имитационные и эвристические модели реальных систем.
4.
Задачи ЛП. Построение математической модели. Основные свойства линейной математической модели.
5.
Задачи ЛП. Задача о смесях.
6.
Задачи ЛП. Задача о раскрое (минимизация обрезков).
7.
Задачи ЛП. Задача о загрузке оборудования
8.
Задачи ЛП. Задача о работе автопарка.
9.
Графическое решение задачи линейного программирования
91
Анализ моделей после нахождения оптимального решения. Задачи анализа
10.
на чувствительность (на примере графического решения задачи).
11.
Стандартная форма линейных оптимизационных моделей
12.
Симплекс-метод решения задачи линейного программирования.
13.
Представление пространства решений стандартной задачи линейного программирования.
14.
Вычислительные процедуры симплекс-метода.
15.
Искусственное начальное решение. Метод больших штрафов.
16.
Искусственное начальное решение. Двухэтапный метод.
17.
Особые случаи применения симплекс-метода. Вырожденность.
18.
Особые случаи применения симплекс-метода. Альтернативные оптимальные решения.
19.
Особые случаи применения симплекс-метода. Неограниченные решения.
20.
Особые случаи применения симплекс-метода. Отсутствие допустимых
решений.
Анализ модели на чувствительность по симплекс-таблице. Оптимальное
21.
решение и статус ресурсов.
Анализ модели на чувствительность по симплекс-таблице. Ценность ресур-
22.
са.
23.
Анализ модели на чувствительность по симплекс-таблице. Максимальное
изменение запаса ресурса.
24.
Анализ модели на чувствительность по симплекс-таблице. Максимальное
изменение коэффициентов удельной прибыли (стоимости).
25.
Определение двойственной задачи линейного программирования.
26.
Соотношения двойственности. Получение оптимального решения двойственной задачи с помощью симплекс-таблиц.
27.
Двойственный симплекс-метод.
28.
Вычислительные процедуры, основанные на соотношениях двойственности. Понятие обратной матрицы.
92
29.
Экономическая интерпретация двойственности. Переменные двойственной
задачи.
30.
Экономическая интерпретация двойственности. Ограничения двойственной
задачи
31.
Анализ на чувствительность (с применением теории двойственности)
32.
Анализ на чувствительность. Изменение условий задачи, влияющие на
допустимость решения.
33.
Анализ на чувствительность. Изменение условий задачи, влияющие на
оптимальность решения.
34.
Транспортная задача. Постановка транспортной задачи.
35.
Определение начального решения транспортной задачи. Методы поиска
начального решения ТЗ.
36.
Решение транспортной задачи методом потенциалов.
37.
Задача о назначении.
38.
Целочисленное линейное программирование. Методы решения задач целочисленного линейного программирования.
39.
Метод ветвей и границ. Решение задачи о коммивояжере.
40.
Метод отсекающих плоскостей.
41.
Задачи целевого программирования. Решение многокритериальных задач
методом весовых коэффициентов.
42.
Задачи целевого программирования. Решение многокритериальных задач
методом приорететов.
43.
Динамическое программирование. Принцип оптимальности Беллмана.
44.
Рекуррентная природа вычислений в динамическом программировании.
Рекуррентные алгоритмы прямой и обратной прогонки.
45.
Задача о дилижансе.
46.
Задача планирования рабочей силы.
47.
Классическая теория оптимизации. Задачи на экстремум при наличии
ограничений.
48.
Метод множителей Лагранжа.
93
Задачи одномерной оптимизации. Метод Фибоначчи.
49.
Раздел 2. Практические задачи
1.
Фармацевтическая фирма Здоровье ежедневно производит не менее 800
килограммовнекой пищевой добавки, которая состоит из смеси кукурузной и
соевой муки, состав которой представлен в следующей таблице.
Мука
Белок
Клетчатка
Стоимость
(в $ за кг)
(в кг на кг муки)
Кукурузная
0,09
0,02
0,3
Соевая
0,6
0,06
0,9
Диетологи требуют, чтобы в пищевой добавке было не менее 30% белка и не
более 5% клетчатки. Фирма Здоровье хочет определить рецептуру смеси
наименьшей стоимости с учетом требований диетологов.
Решить задачу графически.
2. Для изготовления напитков «Люкс» и «Бодрость» предприятие использует
два различных вида сырья. Нормы расхода сырья на производство одной тонны напитка каждого вида, цена одной тонны напитка каждого вида, а также
общее количество сырья каждого вида, которое может быть использовано
предприятием, приведены в таблице:
Вид сырья
Расход сырья (в тоннах) Максина тонну изделие
мально
Люкс
возможный
Бодрость
ежедневный
расход сырья
1
2
6
1
4
24
2
6
94
Цена одной
5
4
тонны
напитка
(
тыс. руб.)
Изучение рынка сбыта показало, что спрос на напиток Бодрость никогда не
превышает спроса на Люкс более чем на 1 тонну. Кроме того установлено, что
спрос на изделие Бодрость никогда не превышает 2 тонн.
Какое количество напитков каждого вида должно производить предприятие,
чтобы доход от реализации был максимальным.
Решить задачу симплекс-методом.
3. Консервный завод перерабатывает за смену 60000 кг спелых помидоров (0,7 рублей за кг.) в томатный сок и пасту. Готовая продукция пакетируется в упаковки по 24 банки. Производство одной банки сока требует 1 кг спелых помидоров, а одной банки пасты – одной трети кг. Заводской склад может
принять за смену только 2000 упаковок сока и 6000 упаковок пасты. Оптовая
цена одной упаковки томатного сока составляет 180 рублей, одной упаковки
томатной пасты – 90 рублей. Найти оптимальную структуру производства
консервного завода. Решить симплекс-методом.
4. Собственные средства банка вместе с депозитами составляют 100
млнден. ед. Не менее 35 млн ден. ед. этих средств должно быть размещено в
кредитах, доходность которых составляет 15%. Кредиты являются неликвидными активами банка, так как в случае непредвиденной потребности в наличности обратить их в деньги без существенных потерь невозможно. Другое дело ценные бумаги, особенно государственные. Их можно в; любой момент
продать, получив некоторую прибыль или во всяком случае без большого
убытка. Поэтому существует правило, согласно которому коммерческие банки
должны покупать в определенной пропорции ликвидные активы — ценные
бумаги, чтобы компенсировать неликвидность кредитов. Пусть в данном случае ценные бумаги должны составлять не менее 30% средств, размещенных в
95
кредитах и ценных бумагах, а их доходность оставляет 10%. Требуется сформировать оптимальный пакет активов, максимизирующий прибыль банка.
5. Транспортная компания занимается перевозкой зерна специальными
зерновозами от трех элеваторов к четырем мельницам. В таблице показаны
возможности отгрузки зерна (предложения) элеваторами (в зерновозах) и потребности (спрос) мельниц (также в зерновозах), а также стоимость перевозки
зерна одним зерновозом от элеваторов к мельницам. Стоимость перевозок
приведена в тысячах рублей.
Мельницы
Элеваторы
Предложение
1
2
4
4
1
10
2
20
11
15
2
12
7
9
20
25
3
4
14
16
18
10
спрос
5
15
15
15
Требуется определить структуру перевозок между элеваторами и мельницами с минимальной стоимостью. Для этого необходимо найти объемы перевозок Xijмежду i-м элеватором и j-й мельницей.
6.
Некоторая компания имеет четыре сбытовые базы и четыре заказа,
которые необходимо доставить различным потребителям. Складские помещения каждой базы вполне достаточны для того, чтобы вместить один из этих
заказов. В таблице содержится информация о расстоянии между каждой базой
и каждым потребителем. Как следует распределить заказы по сбытовым базам,
чтобы общая дальность транспортировки была минимальной?
Расстояние от сбытовых баз до потребителей
Сбы-
Расстояние, км
товая
база
Потребители
1
2
3
4
96
А
68
72
75
83
В
56
60
58
63
С
38
40
35
45
Д
47
42
40
45
97
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное образовательное учреждение
высшего профессионального образования
«Дальневосточный федеральный университет»
(ДВФУ)
ШКОЛА ЕСТЕСТВЕННЫХ НАУК
СПИСОК ЛИТЕРАТУРЫ
по дисциплине «Теория принятия решений»
Специальность - 230102 «Автоматизированные системы обработки информации и управления»
Форма подготовки - очная
г. Владивосток
2011
98
Основная литература
4. ХэмдиА.Таха, Введение в исследование операций, 7-е издание.: Пер. с
англ. – М.: Издательский дом «Вильямс», 2007.
5. Федоров В.В., Сухарев А.Г., Тимохов А.В., Курс методов оптимизации:
учебное пособие, М.: ФИЗМАТЛИТ, 2011 г.
6. Пантелеев А.В. Методы оптимизации в примерах и задачах: Учебное пособие для втузов. - М.: Высшая школа, 2002.
Дополнительная литература
1. Струченков И. В. Методы оптимизации в прикладных задачах. –
М.:СОЛОН-ПРЕСС, 2009.
2. Калихман И.Л. Сборник задач по математическому программированию.
М., «Высшая школа», 1975.
3. Просветов Г.И. Методы оптимизации: задачи и решения. Учебнопрактическое пособие. – М., Альфа-Пресс, 2009.
4. Кощлов В.Н. Системный анализ, оптимизация и принятие решений.
Учебное пособи. - М.: Проспект, 2010
5. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. –
М.: Наука, 1986.
6. Васильев Ф.П. Численные методы решения экстремальных задач. – М.:
Наука, 1988.
7. Поляк Б.Т. Введение в оптимизацию. – М.: Наука, 1983.
8. Моисеев Н.Н., Иванилов Ю.П., Столярова Е.М. Методы оптимизации. –
М.: Наука, 1978.
9. Лесин В.В., Лисовец Ю.П. Основы методов оптимизации. – М.: МАИ,
1998.
10. Химмельблау Д. Прикладное нелинейное программирование М.:Мир,
1989
99
11. Акулич И.Д. Математическое программирование в примерах и задачах.
– М.: Высшая школа, 1993.
12. Алексеев В.М., Галеев Э.М., Тихомиров В.М. Сборник задач по оптимизации. Теория. Примеры. Задачи. – М.: Наука, 1984.
13. Калихман И.Л., Войтенко М.А. Динамическое программирование в примерах и задачах. – М.: Высшая школа, 1979.
14. Карманов В.Г. Математическое программирование, "Наука", М., 1986.
15. Мину М. Математическое погаммиование, "Наука", М., 1990.
16. Моисеев Н.Н., Иванилов Ю.П., Столяров Е.М. Методы оптимизации, "Наука", М., 1978.
17. Полак Э. Численные методы оптимизации, "Наука", М., 1974.
18. Пшеничный Б.Н., Данилин Ю.М. Численные методы в экстремальных
задачах, "Наука", М., 1975.
Интернет ресурс:
1. http://e.lanbook.com/books/element.php?pl1_cid=25&pl1_id=3506 Федунец
Н.И. Куприянов В.В. Теория принятия решений: учебное пособие для
вузов – М.: Издательство Московского государственного горного университета, 2005. – 218 с.
2. http://www.aup.ru/books/m157/ Орлов А.И. Теория принятия решений.
Учебное пособие. - М.: Издательство "Март", 2004. - 656 с.
3. http://window.edu.ru/resource/960/44960 Павлов А.Н., Соколов Б.В. Принятие решений в условиях нечеткой информации: Учебное пособие. СПб.: ГУАП, 2006. - 72 с.
100
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное образовательное учреждение
высшего профессионального образования
«Дальневосточный федеральный университет»
(ДВФУ)
ШКОЛА ЕСТЕСТВЕННЫХ НАУК
ГЛОССАРИЙ
по дисциплине «Теория принятия решений»
Специальность - 230102 «Автоматизированные системы обработки информации и управления»
Форма подготовки - очная
г. Владивосток
2011
101
Аддитивность – (лат. additivus — прибавляемый) — свойство величин, состоящее в том, что значение величины, соответствующее целому объекту, равно
сумме значений величин, соответствующих его частям, при любом разбиений
объекта на части.
Адекватность
модели
–
это
совпадение
свойств
(функ-
ций/параметров/характеристик и т.п.)моделии соответствующих свойств моделируемого объекта.Адекватностьюназывается совпадение модели моделируемой системы в отношении цели моделирования.
Аппроксимация – это приближенное решение сложной функции с помощью
более простых, что резко ускоряет и упрощает решение задач.
Беллмана принцип оптимальности- важнейшее положение динамического
программирования, которое гласит: оптимальное поведение в задачах динамического программирования обладает тем свойством, что каковы бы ни были
первоначальное состояние и решение (т. е. “управление”), последующие решения должны составлять оптимальное поведение относительно состояния,
получающегося в результате первого решения. Этот принцип можно выразить
и рассуждая от противного: если не использовать наилучшим образом то, чем
мы располагаем сейчас, то и в дальнейшем не удастся наилучшим образом
распорядиться тем, что мы могли бы иметь. Следовательно, если имеется оптимальная траектория, то и любой ее участок представляет собой оптимальную траекторию. Этот принцип позволяет сформулировать эффективный метод решения широкого класса многошаговых задач. (Подробнее см. Динамическое программирование.) Принцип назван по имени крупного американского математика Р. Беллмана, одного из основоположников динамического программирования.
Векторная
оптимизация
–
это
комплекс
методов
решения
за-
дач математического программирования, в которых критерий оптимальности представляет собой вектор, компонентами которого являются, в свою оче-
102
редь, несводимые друг к другу скалярные критерии оптимальности подсистем,
входящих в данную систему (напр., критерии роста благосостояния разных
социальных групп в социально-экономическомпланировании). .
Выпуклое программирование – разделматематического программирования,посвященный теории и методам решения задач минимизации выпуклых
функций на выпуклых множествах, задаваемых системами неравенств и равенств..
Глобальный критерий оптимальности – элемент оптимизационной модели,
обобщенный критерий оптимальностираспределения наличных (ограниченных) ресурсов, отыскиваемого с помощью этой модели. Чаще всего определение “глобальный” применяется либо к критерию одноуровневой модели
народного хозяйства в целом, либо к критерию “верхней” модели соответствующей многоуровневой системы моделей; в последнем случае наряду с
Г. к., выражающим интересы общества в целом, фигурируют локальные критерии моделей нижних уровней, отражающие интересы отдельных хозяйственных звеньев и социальных групп.
Градиент– вектор, своим направлением указывающий направление наискорейшего возрастания некоторой величины , значение которой меняется от
одной точки пространства к другой (скалярного поля), а по величине (модулю)
равный быстроте роста этой величины в этом направлении.
Градиентные методы – методы решения задачматематического программирования(вычислительныеалгоритмы),
основанные
на
поис-
кеэкстремума(максимумаилиминимума)функциипутем последовательного перехода к нему с помощьюградиентаэтой функции..
Двойственная задача–одно из фундаментальных понятий теории линейного
программирования; инструмент, позволяющий установить, оптимально ли
данное допустимое решение задачи ЛП, без непосредственного сравнения его
со всеми остальными допустимыми решениями.
103
Дерево решений – схематическое представление сложного процесса принятия
решений по какой-либо задаче.
Дерево целей - в программно-целевых методах планирования и управления граф — схема, показывающая членение общих (генеральных) целей плана или программы на подцели (затем последних — на подцели следующего
уровня и т. д.). Дерево — это связный граф, выражающий соподчинение и взаимосвязи элементов; в данном случае такими элементами являются цели и
подцели.
Динамическая система - всякая система, которая изменяется во времени (в
отличие от статической системы). Математически это принято выражать через переменные (координаты).
Процесс
их
изменения
характеризует-
ся траекторией:
Динамическое программирование–раздел математики, посвященный теории
и методам решения многошаговых задач оптимального управления.
Дискретное программирование – раздел оптимального программирования,
изучающий экстремальные
задачи,
в
которых
на
иско-
мые переменные накладывается условие целочисленности, а область допустимых решений конечна. Таким образом, здесь используется модель общей задачи
математического
программирования с
дополнитель-
ным ограничением: x1, x2, ..., xn — целочисленны.
Квадратичное программирование – раздел выпуклого программирования, посвященный теории и методам решения задач минимизации выпуклых
квадратичных функций на множествах, задаваемых системами линейных неравенств и равенств. Существует законченная теория К. п., и разработаны численные методы решения задач К. п., в том числе методы типа симплексного
метода,приводящие к решению за конечное число шагов (итераций).
Критерий–
признак,
ся оценка, классификация.
на
основании
которого
производят-
104
Критерий оптимальности – характерный показатель решения задачи, по значению которого оценивается оптимальность найденного решения, то есть максимальное удовлетворение поставленным требованиям. В одной задаче может
быть установлено несколько критериев оптимальности.
Линейное программирование– область математического программирования,
посвященная теории и методам решенияэкстремальных задач, характеризующихся линейной зависимостью между переменными.
Математическое программирование– математическая дисциплина, посвященная теории и методам решения задач о нахождении экстремумов функций
на множествах конечномерного векторного пространства, определяемых линейными и нелинейными ограничениями (равенствами и неравенствами). М.
п.- раздел науки обисследовании операций,охватывающий широкий класс задач управления, математическими моделями которых являются конечномерные экстремальные задачи. Задачи М. п. находят применение в различных областях человеческой деятельности, где необходим выбор одного из возможных
образов действий, напр, при решении многочисленных проблем управления и
планирования производственных процессов, ,в задачах проектирования и перспективного планирования. Наименование "М. п." связано с тем, что целью
решения задач является выбор программы действий.
Методы ветвей и границ– общий алгоритмический метод для нахождения
оптимальных решений различных задач оптимизации, особенно дискретной
и комбинаторной оптимизации.
Многокритериальные задачи– математические модели принятия оптимального решения одновременно по нескольким критериям. Эти критерии могут
отражать оценки различных качеств объекта (или процесса), по поводу которых принимается решение, или оценки одной и той же его характеристики, но
с различных точек зрения. Теория М. з. относится к числу математических методов исследования операций.
105
Множители
Лагранжа– дополнительные
множители,
преобразую-
щие целевую функцию экстремальной задачи выпуклого программирования (в
частности, линейного программирования) при ее решении одним из классических методов — методом разрешающих множителей (методом Лагранжа). Полученная функция носит название лагранжиан, или функция Лагранжа.
Нелинейное программирование– разделматематического программирования,посвященный теории и методам решения задач оптимизации нелинейных
функций на множествах, задаваемых нелинейными ограничениями (равенствами и неравенствами).
Оптимальность по Парето – такое состояние системы, при котором значение
каждого частного показателя, характеризующего систему, не может быть
улучшено без ухудшения других.Таким образом, по словам самого Парето:
«Всякое изменение, которое никому не приносит убытков, а некоторым людям
приносит пользу (по их собственной оценке), является улучшением». Значит,
признаётся право на все изменения, которые не приносят никому дополнительного вреда.
Множество состояний системы, оптимальных по Парето, называют «множеством Парето», «множеством альтернатив, оптимальных в смысле Парето»,
либо «множеством Парето-оптимальных альтернатив».Ситуация, когда достигнута эффективность по Парето — это ситуация, когда все выгоды от обмена исчерпаны.
Распределительная задача – класс экономико-математических задач, связанных с распределением ресурсов по работам, которые необходимо выполнить.
Если ресурсов достаточно, чтобы каждую работу выполнить наиболее эффективно, задача не возникает. В обратном же случае переброска, передача ресурсов
с
одной
работы
на
другую
приводит
к
изменению
об-
щей эффективности всех работ, вместе взятых. Поэтому Р. з. заключается в
отыскании наилучшего распределения ресурсов, при котором либо максими-
106
зируется общий доход или результат, выраженный в какой-либо другой форме, либо минимизируются затраты.
Седловая
точка– в математическом
программировании — точка,
где функция Лагранжа достигаетмаксимумапо исходнымпеременным(прямой
задачи) иминимумапомножителям Лагранжа.
Экстремум
функции
–
тия максимума и минимума функции.
термин,
объединяющий
поня-
