Книгопоиск: поисковая система книг. Корнеенко методы оптимизации


Методы оптимизации - Стр 12

109

приоритетами.

Пример 7.3

Решим методом приоритетов задачу из примера 7.2. Предположим, что наибольший приоритет имеет частная целевая функция, соответствующая условию, накладываемому на объем рекламной аудитории.

Шаг 0. G1 > G2.

G1: минимизироватьs1+ (условие по рекламной аудитории),G2: минимизироватьs2 (условие по бюджету).

Шаг 1. Решаем первую задачу ЛП.

Минимизировать G1 =s1+ при выполнении ограничений

4x1 + 8х2 +s1+ s1 = 45 (условие по рекламной аудитории), 8x1 + 24x2 +s2+ s2 = 100 (условие по бюджету),

x1 + 2x2 ≤ 10 (ограничение по рекламным агентам),

x 1 ≤ 6 (ограничение на рекламу по радио),

x1,x2,s1+,s1 ,s2+,s2 ≥ 0.

Оптимальное решение этой задачи составляет х1= 5 мин,х2 = 2,5 мин,s1+ = 5 млн человек, остальные переменные равны нулю. Решение показывает, что условие по объему рекламной аудитории не выполняется с дефицитом в 5 млн человек. В этой задаче мы имеемр1 =s1+. Поэтому в следующей задаче добавим ограничениеs1+ = 5.

Шаг 2. Теперь необходимо решить вторую задачу ЛП. Минимизировать G2 =s2 при выполнении тех же ограничений, что и в

предыдущей задаче, плюс дополнительное ограничение s1+ = 5.

В данном случае в решении второй задачи нет необходимости, поскольку уже в решении первой имеем s2 = 0. Следовательно, решение первой задачи автоматически является оптимальным решением второй. Решениеs2 = 0 показывает, что ограничение, касающееся бюджета рекламной компании, выполняется.

Дополнительное ограничение s1+ = 5 можно также учесть путем подстановки значения 5 вместо переменнойs1+ в первое ограничение. В результате правая часть этого неравенства изменится со значения 45 на 40. Получим следующую задачу ЛП.

Минимизировать G2 =s2 при ограничениях

4x1 + 8x2 s1 = 40, 8x1 + 24x2 +s2+ s2 = 100,

110

x1 + 2x2 ≤ 10,

x1 ≤ 6,

х1,х2,s1+,s1 ,s2+,s2 ≥ 0.

В новой формулировке этой задачи на одну переменную меньше, чем в первой задаче.

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

Пример 7.4

Цели, поставленные в задаче из примера 7.2, можно переформулировать следующим образом.

Цель 1. Максимизировать объем рекламной аудитории (P1). Цель 2. Минимизировать стоимость рекламной кампании (Р2).

Математически эти цели можно выразить с помощью следующих целевых функций.

Максимизировать Р1 = 4x1 + 8х2. МинимизироватьР2 = 8x1 + 24x2.

Отдельные ограничения на желаемый объем рекламной аудитории и стоимость рекламной кампании, которые использовались в примерах 7.2 и 7.3, в данном случае излишни, поскольку для этих величин мы получим границы после решения соответствующих задач.

Получили новую задачу: Максимизировать P1 = 4x1 + 8х2 МинимизироватьР2 = 8x1 + 24х2

при ограничениях

x1 + 2x2 10,x1 6,

x1,x2 0.

Сначала решим эту задачу с помощью процедуры, описанной в примере

7.3.

Шаг 1. Решаем первую задачу ЛП. МаксимизироватьР1 = 4x1 + 8х2 при ограничениях

111

x1+ 2x210, x16,

x1,x2 0.

Оптимальное решение этой задачи составляет x1 = 0,х2 = 5 иР1 = 40. Отсюда видно, что объем рекламной аудитории не может превысить 40 миллионов человек.

Шаг 2. Добавим ограничение 4x1 + 8х2 ≥ 40 которое гарантирует, что решение, полученное на предыдущем шаге, не будет ухудшено, и решаем следующую задачу ЛП.

Минимизировать Р2 = 8x1 + 24х2 при ограниченияхx1 + 2x2 10,

x16,

4x1 + 8x2 40,x1,x2 0.

Решение задачи дает следующее оптимальное решение: Р2 = 96 000 руб,x1 = 6 мин их2 = 2 мин. Мы получили тот же объем рекламной аудитории (P1 = 40 млн чел.), но за меньшую стоимость. Это результат того, что здесь мы искали оптимальные значения соответствующих величин, а не просто удовлетворяли ограничениям, как в примере 7.3.

Теперь решим ту же задачу, используя правило исключения столбцов. Это правило применяется последовательно к строкам симплекс таблицы, соответствующим частным целевым функциям.

Первая задача ЛП (Максимизация объема рекламной аудитории). При решении этой задачи симплекс таблица содержит строки, соответствующие как целевой функции P1, так и целевой функции Р2. Строка целевой функции Р2 пока играет пассивную роль, но будет изменена перед решением второй задачи ЛП.

Первая задача решается за две симплексные итерации, как показано в следующей таблице.

Нижняя часть этой таблицы показывает оптимальное решение x1 = 0,х2 = 5 иP1 = 40 первой задачи.

Правило исключения столбцов применяется перед решением второй задачи для удаления из симплекс таблицы с оптимальным решением первой задачи небазисной переменнойхj, для которойzj –cj 0. Такие переменные, приняв положительные значения в задаче с более низким приоритетом,

112

ухудшают решение задач с более высоким приоритетом.

Базис

x1

x2

s1

s2

Решение

 

 

 

 

 

 

P1

4

8

0

0

0

 

 

 

 

 

 

P2

8

24

0

0

0

 

 

 

 

 

 

s1

1

2

1

0

10

s2

1

0

0

1

6

P1

0

0

4

0

40

P2

4

0

12

0

120

x2

1/2

1

1/2

0

5

s2

1

0

0

1

6

Вторая задача ЛП (Минимизация стоимости рекламной кампании).

Правило исключения столбцов удаляет переменную s1, для которойz1 –c2 = 4. ИзР2 строки приведенной выше симплекс таблицы видно, что если не удалить переменнуюs1, то на первой итерации решения второй задачи она должна войти в базис, при этом из базиса будет исключена переменнаях2. После этого будет получено оптимальное решение второй задачи (в этом решенииx1 =х2 = 0), которое ухудшает оптимальное решение первой, поскольку теперьP1 = 0 вместоP1 = 40, как было ранее.

В данном случае вторая задача ЛП является задачей минимизации. После удаления переменной s1 в базис вводится небазисная переменнаях1, со значением разностиzj cj, равным 4 (> 0), что может улучшить значение целевой функцииР2. В следующей симплекс таблице показаны две итерации решения второй задачи ЛП.Р1 строку можно удалить из этой таблицы, так как она не участвует в процессе нахождения оптимального решения задачи с целевой функциейР2.

Полученное здесь оптимальное решение (х1 = 6,х2 = 2) со значениями целевых функцийР1 = 40 иР2 = 96 такое же, как и полученное ранее.

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

113

Итерация

Базис

x1

x2

s1

s2

Решение

 

Р1

 

 

 

 

40

1

P2

4

0

 

0

120

x2

1/2

1

 

0

5

 

 

 

s2

1

0

 

1

6

 

Р1

 

 

 

 

40

2

P2

0

0

 

4

96

 

 

 

 

 

 

x2

0

1

 

1/2

2

 

 

 

x1

1

0

 

1

6

 

 

 

 

 

 

 

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

114

Список литературы

1.Таха X. Введение в исследование операций. Учебное пособие. - М.: Издательский дом «Вильямс», 2007.

2.Аттетков А.В. Методы оптимизации. Учебник для студ. втузов. /Под ред. Зарубина В.С., Крищенко А.П. - М.: МГТУ им. Н.Э. Баумана, 2003.

3.Корнеенко В.П. Методы оптимизации. Учебник. – М.: Высшая школа,

2007.

4.Минько Э.В., Минько А.Э. Методы прогнозирования и исследования операций: учеб. Пособие. – М.: Финансы и статистика; ИНФРА-М,2010.

5.Вентцель Е.С. Исследование операций: задачи, принципы, методология. Учебное пособие. - М.: Кнорус, 2010.

6.Гончаров В.А.. Методы оптимизации: учеб. пособие для студ. ВУЗов.

–М.: Юрайт, Высшее образование, 2010.

7.Пантелеев А.В. Методы оптимизации в примерах и задачах: учеб. пособие для студ. втузов. – М.: Высшая школа, 2005.

8.Давыдов Э.Г. Элементы исследования операций: учеб. пособие для студ. вузов - М.: Кнорус, 2010.

115

 

ОГЛАВЛЕНИЕ

 

1. Задачи оптимизации ........................................................................................

3

1.1. Основные понятия ........................................................................................

3

1.2. Примеры задач оптимизации ......................................................................

5

1.3. Задачи оптимального проектирования.......................................................

7

1.4. Задачи оптимального планирования ..........................................................

9

1.5. Классы задач оптимизации ........................................................................

13

2. Методы решения задач линейного программирования ........................

18

2.1. Введение ......................................................................................................

18

2.2. Ограничения в модели линейного программирования ..........................

18

2.3. Графическое решение задачи линейного программирования ...............

21

2.4. Дополнительные переменные ...................................................................

25

3. Симплекс метод .............................................................................................

28

3.1. Стандартная форма задачи ЛП и ее базисные решения .........................

28

3.1.1. Стандартная форма задачи ЛП.........................................................

28

3.1.2. Определение базисных решений ..........................................................

30

3.1.3. Свободные переменные и базисные решения.....................................

32

3.2. Алгоритм симплекс метода ......................................................................

32

3.3. Искусственное начальное решение ..........................................................

40

3.3.1. М метод ................................................................................................

40

3.3.2. Двухэтапный метод .............................................................................

43

4. Двойственная задача линейного программирования ............................

47

4.1. Определение двойственной задачи...........................................................

47

4.2. Соотношения между оптимальными решениями прямой и

 

двойственной задач ...........................................................................................

50

4.3. Двойственный симплекс метод................................................................

53

5. Транспортные модели ...................................................................................

57

5.1. Определение транспортной модели..........................................................

57

5.2. Решение транспортной задачи ..................................................................

58

5.2.1. Определение начального решения .......................................................

59

5.2.2. Итерационный алгоритм решения транспортной задачи..............

64

5.2.3. Интерпретация метода потенциалов как симплекс метода ........

69

5.3. Задача о назначениях..................................................................................

70

5.3.1. Венгерский метод .................................................................................

71

5.3.2. Интерпретация венгерского метода как симплекс метода ..........

74

116

 

5.4. Транспортная модель с промежуточными пунктами .............................

75

6. Целочисленное линейное программирование .........................................

78

6.1. Примеры задач целочисленного программирования .............................

78

6.2. Методы решения задач целочисленного программирования................

79

6.2.1. Метод ветвей и границ........................................................................

80

6.2.2. Аддитивный алгоритм для задач с двоичными переменными ........

87

6.2.3. Метод отсекающих плоскостей ........................................................

94

6.4. Выводы ......................................................................................................

100

7. Целевое программирование.......................................................................

102

7.1. Несколько целевых функций ..................................................................

102

7.2. Формулировка задачи целевого программирования ............................

102

7.3. Алгоритмы целевого программирования ..............................................

104

7.3.1. Метод весовых коэффициентов .......................................................

105

7.3.2. Метод приоритетов ..........................................................................

107

Список литературы ............................................................................................

114

Гладков Леонид Анатольевич Гладкова Надежда Викторовна

Методы оптимизации

Часть 1 Конспект лекций

Ответственный за выпуск

Гладков Л.А.

Редактор

Проценко И.А.

Корректор

Надточий З.И.

ЛР № 020565 от 23.06.1997 г.

Подписано к печати

Формат 60 х 84 1/16.

Бумага офсетная

Печать офсетная.

Усл.п.л. – 7,0. Уч. изд.л. – 6,8.

Заказ №

Тираж 300 экз.

«С»

Издательство ЮФУ Таганрог, Некрасовский, 44

Типография ЮФУ Таганрог, Некрасовский, 44

studfiles.net

Корнеенко, Виктор Павлович - Методы оптимизации : учебник для студентов высших учебных заведений, обучающихся по специальности "Прикладная математика и информатика" и по направлению подготовки магистров "Прикладная математика и информатика"

Поиск по определенным полям
Чтобы сузить результаты поисковой выдачи, можно уточнить запрос, указав поля, по которым производить поиск. Список полей представлен выше. Например:

author:иванов

Можно искать по нескольким полям одновременно:

author:иванов title:исследование

Логически операторы
По умолчанию используется оператор AND. Оператор AND означает, что документ должен соответствовать всем элементам в группе:

исследование разработка

author:иванов title:разработка

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

исследование OR разработка

author:иванов OR title:разработка

оператор NOT исключает документы, содержащие данный элемент:

исследование NOT разработка

author:иванов NOT title:разработка

Тип поиска
При написании запроса можно указывать способ, по которому фраза будет искаться. Поддерживается четыре метода: поиск с учетом морфологии, без морфологии, поиск префикса, поиск фразы. По-умолчанию, поиск производится с учетом морфологии. Для поиска без морфологии, перед словами в фразе достаточно поставить знак "доллар":

$исследование $развития

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

исследование*

Для поиска фразы нужно заключить запрос в двойные кавычки:

"исследование и разработка"

Поиск по синонимам
Для включения в результаты поиска синонимов слова нужно поставить решётку "#" перед словом или перед выражением в скобках. В применении к одному слову для него будет найдено до трёх синонимов. В применении к выражению в скобках к каждому слову будет добавлен синоним, если он был найден. Не сочетается с поиском без морфологии, поиском по префиксу или поиском по фразе.

#исследование

Группировка
Для того, чтобы сгруппировать поисковые фразы нужно использовать скобки. Это позволяет управлять булевой логикой запроса. Например, нужно составить запрос: найти документы у которых автор Иванов или Петров, и заглавие содержит слова исследование или разработка:

author:(иванов OR петров) title:(исследование OR разработка)

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

бром~

При поиске будут найдены такие слова, как "бром", "ром", "пром" и т.д. Можно дополнительно указать максимальное количество возможных правок: 0, 1 или 2. Например:

бром~1

По умолчанию допускается 2 правки.
Критерий близости
Для поиска по критерию близости, нужно поставить тильду "~" в конце фразы. Например, для того, чтобы найти документы со словами исследование и разработка в пределах 2 слов, используйте следующий запрос:

"исследование разработка"~2

Релевантность выражений
Для изменения релевантности отдельных выражений в поиске используйте знак "^" в конце выражения, после чего укажите уровень релевантности этого выражения по отношению к остальным. Чем выше уровень, тем более релевантно данное выражение. Например, в данном выражении слово "исследование" в четыре раза релевантнее слова "разработка":

исследование^4 разработка

По умолчанию, уровень равен 1. Допустимые значения - положительное вещественное число.
Поиск в интервале
Для указания интервала, в котором должно находиться значение какого-то поля, следует указать в скобках граничные значения, разделенные оператором TO. Будет произведена лексикографическая сортировка.

author:[Иванов TO Петров]

Будут возвращены результаты с автором, начиная от Иванова и заканчивая Петровым, Иванов и Петров будут включены в результат.

author:{Иванов TO Петров}

Такой запрос вернёт результаты с автором, начиная от Иванова и заканчивая Петровым, но Иванов и Петров не будут включены в результат. Для того, чтобы включить значение в интервал, используйте квадратные скобки. Для исключения значения используйте фигурные скобки.

search.rsl.ru

Корнеенко В.П. - Методы оптимизации, 978-5-06-005531-3

Главная  » Учебники и учебные пособия. Педагогика » Литература для ВУЗов и ССУЗов » Математика. Физика » Методы оптимизации серия: Для высших учебных заведений Высшая школа, 2007 г., 664 стр., 978-5-06-005531-3 , 217*148*33 мм., тираж: 5000

Описание книги

Рассматриваются численные методы решения экстремальных нецелочисленных задач, методы и алгоритмы оптимизации на дискретных моделях и методы решения многокритериальных задач на основе паретовского подхода. Учебник подготовлен в соответствии с требованиями Государственного образовательного стандарта, охватывает все темы, включая и дополнительные, по курсу "Методы оптимизации". Приведены доказательства практически всех сформулированных утверждений. Для студентов математических факультетов университетов, а также для магистрантов, аспирантов и научных работников, занимающихся решением оптимизационных задач.

Рекомендации

Допущено Учебно-методическим советом по прикладной математике и информатике УМО по классическому университетскому образованию.

Поделиться ссылкой на книгу

Об авторе

Корнеенко В.П.

Последние поступления в рубрике "Математика. Физика"

Макроскопическая электродинамика Власов А.Е.

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

Термодинамика и статистическая физика. Теория равновесных систем. Термодинамика. Том 1 Квасников И.А.

В основу настоящего учебного пособия, написанного в соответствии с программой по теоретической физике, положен курс лекций, читаемый автором на физическом факультете МГУ. Первый том включает в себя материал по аксиоматике макроскопической термодинамики, общим проблемам теории и основным прикладным вопросам....

Основы инерциальной навигации Чуб В.В.

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

Если Вы задавались вопросами "где найти книгу в интернете?", "где купить книгу?" и "в каком книжном интернет-магазине нужная книга стоит дешевле?", то наш сайт именно для Вас. На сайте книжной поисковой системы Книгопоиск Вы можете узнать наличие книги Корнеенко В.П., Методы оптимизации в интернет-магазинах. Также Вы можете перейти на страницу понравившегося интернет-магазина и купить книгу на сайте магазина. Учтите, что стоимость товара и его наличие в нашей поисковой системе и на сайте интернет-магазина книг может отличаться, в виду задержки обновления информации.

www.knigo-poisk.ru

Методы оптимизации

Методы оптимизации Автор программы: доктор физ.-мат. наук, профессор Югай Л.П.

Лектор 2010/11 уч. года:

МЕТОДЫ ОПТИМИЗАЦИИ

Введение. Математические модели и моделирование. Задачи оптимизации и их роль в математическом моделировании. Структура курса.

Линейное программирование (ЛП). Постановки задач в линейном программировании (основная, двойственная и каноническая задачи ЛП). Графический метод решения задачи ЛП.

Теоретические основы линейного программирования: оптимальные решения и их связь с седловыми точками, теоремы двойственности, теорема Фаркаша, оптимальные решения и угловые точки, грубый алгоритм решения задач ЛП. Симплекс-метод решения задач линейного программирования. Антициклин. Методы отыскания начального опорного плана(угловой точки). Решение задач ЛП методом искусственного базиса и М-методом.

Специальные задачи линейного программирования. Транспортная задача (ТЗ). Транспортные задачи и линейное программирование. Существование оптимального решения ТЗ. Построение начального опорного плана перевозок (методы северо-западного угла, минимальной стоимости и Фогеля). Метод потенциалов решения ТЗ. Экономический смысл потенциалов. Многопродуктовые ТЗ. Приложения ТЗ(задача о загрузке обрабатывающих устройств, задача о назначениях и др.). Целочисленное программирование.

Выпуклое программирование. Постановка задач оптимизации в выпуклом программировании. Элементы выпуклого анализа. Экстремальные свойства на выпуклых множествах. Метод множителей Лагранжа. Теоремы Куна-Таккера.

Нелинейное программирование. Постановка задач оптимизации в нелинейном программировании.

Методы оптимизации функции одной переменной( классический метод, деления отрезка пополам, золотого сечения и др.).

Методы оптимизации функций многих переменных. Правило множителей Лагранжа (обобщенное и классическое), необходимые и достаточные условия экстремума.

Численные методы решения задач нелинейного программирования (градиентные методы, возможных направлений, штрафных функций и др.).

Вариационное исчисление и оптимальное управление

Постановка оптимизационных задач вариационного исчисления. Основные леммы. Уравнение Эйлера. Достаточные условия экстремума функционалов.

Постановка задач оптимального управления. Формулировка Принципа максимума Л.С. Понтрягина. Доказательство Принципа максимума для простейшей задачи оптимального управления.

Связь между принципом максимума и вариационным исчислением.

Динамическое программирование

Динамическое программирование в дискретных системах. Задача о распределении ресурсов. Принцип оптимальности и уравнение Беллмана. Задачи

о «загрузке станков», «поиске пути минимальной длины», «загрузке самолета» и др. Динамическое программирование в непрерывных системах.

Литература 1. Карманов В.Г. Математическое программирование. –М.: Наука, 1986. -288с.

2. Васильев Ф.П. Численные методы решения экстремальных задач.

–М.: Наука,2002. – 552 с.

3. Корнеенко В.П. Методы оптимизации. -М.: ВШ, 2007.- 664с.

4.Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. - М.: ВШ, 1980. -304с.

5. Габасов Р., Кириллова Ф.М. Методы оптимизации. -Минск: ВШ, 1980.-280с.

6. Интрилигатор М. Математические методы оптимизации и экономическая

теория.- М.: Айрис-пресс, 2002. – 576с.

7. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и примерах.

- М.: Наука, 1991.-448с.

8. Заславский Ю.Л. Сборник задач по линейному программированию. –М., Наука,

1969, 256с.

9. Кузнецов А.В., Холод Н.И., Костевич Л.С. Руководство к решению задач по

математическому программированию. Минск, ВШ, 1978, -256с.

10. Капустин В.Ф. Практические занятия по курсу математического

программирования. Изд. ЛГУ, 1976. –192с.

11. Избранные труды Л.С. Понтрягина (сер. «Выдающиеся ученые МГУ»).

– М.: МАКС Пресс, 2004.-552с.

12. Основы теории оптимального управления (под ред. В.Ф. Кротова) – М., ВШ,

1990, - 430с.

13. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир. 1982.

14. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. М.: Мир. 1985.

15. Хачиян Л.Г. Сложность задач линейного программирования. М.: Знание. 1987. № 10.

16. Карманов В.Г. Математическое программирование. М.: Наука. 1986.

17. Сухарев А..Г., Тимохов А..В., Федоров В.В. Курс методов оптимизации. М.: Наука. 1985.

18. Мину М. Математическое программирование. М.: Наука. 1990.

www.vmest.ru

Методы оптимизации

Методы оптимизации Автор программы: доктор физ.-мат. наук, профессор Югай Л.П.

Лектор 2010/11 уч. года:

МЕТОДЫ ОПТИМИЗАЦИИ

Введение. Математические модели и моделирование. Задачи оптимизации и их роль в математическом моделировании. Структура курса.

Линейное программирование (ЛП). Постановки задач в линейном программировании (основная, двойственная и каноническая задачи ЛП). Графический метод решения задачи ЛП.

Теоретические основы линейного программирования: оптимальные решения и их связь с седловыми точками, теоремы двойственности, теорема Фаркаша, оптимальные решения и угловые точки, грубый алгоритм решения задач ЛП. Симплекс-метод решения задач линейного программирования. Антициклин. Методы отыскания начального опорного плана(угловой точки). Решение задач ЛП методом искусственного базиса и М-методом.

Специальные задачи линейного программирования. Транспортная задача (ТЗ). Транспортные задачи и линейное программирование. Существование оптимального решения ТЗ. Построение начального опорного плана перевозок (методы северо-западного угла, минимальной стоимости и Фогеля). Метод потенциалов решения ТЗ. Экономический смысл потенциалов. Многопродуктовые ТЗ. Приложения ТЗ(задача о загрузке обрабатывающих устройств, задача о назначениях и др.). Целочисленное программирование.

Выпуклое программирование. Постановка задач оптимизации в выпуклом программировании. Элементы выпуклого анализа. Экстремальные свойства на выпуклых множествах. Метод множителей Лагранжа. Теоремы Куна-Таккера.

Нелинейное программирование. Постановка задач оптимизации в нелинейном программировании.

Методы оптимизации функции одной переменной( классический метод, деления отрезка пополам, золотого сечения и др.).

Методы оптимизации функций многих переменных. Правило множителей Лагранжа (обобщенное и классическое), необходимые и достаточные условия экстремума.

Численные методы решения задач нелинейного программирования (градиентные методы, возможных направлений, штрафных функций и др.).

Вариационное исчисление и оптимальное управление

Постановка оптимизационных задач вариационного исчисления. Основные леммы. Уравнение Эйлера. Достаточные условия экстремума функционалов.

Постановка задач оптимального управления. Формулировка Принципа максимума Л.С. Понтрягина. Доказательство Принципа максимума для простейшей задачи оптимального управления.

Связь между принципом максимума и вариационным исчислением.

Динамическое программирование

Динамическое программирование в дискретных системах. Задача о распределении ресурсов. Принцип оптимальности и уравнение Беллмана. Задачи

о «загрузке станков», «поиске пути минимальной длины», «загрузке самолета» и др. Динамическое программирование в непрерывных системах.

Литература 1. Карманов В.Г. Математическое программирование. –М.: Наука, 1986. -288с.

2. Васильев Ф.П. Численные методы решения экстремальных задач.

–М.: Наука,2002. – 552 с.

3. Корнеенко В.П. Методы оптимизации. -М.: ВШ, 2007.- 664с.

4.Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. - М.: ВШ, 1980. -304с.

5. Габасов Р., Кириллова Ф.М. Методы оптимизации. -Минск: ВШ, 1980.-280с.

6. Интрилигатор М. Математические методы оптимизации и экономическая

теория.- М.: Айрис-пресс, 2002. – 576с.

7. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и примерах.

- М.: Наука, 1991.-448с.

8. Заславский Ю.Л. Сборник задач по линейному программированию. –М., Наука,

1969, 256с.

9. Кузнецов А.В., Холод Н.И., Костевич Л.С. Руководство к решению задач по

математическому программированию. Минск, ВШ, 1978, -256с.

10. Капустин В.Ф. Практические занятия по курсу математического

программирования. Изд. ЛГУ, 1976. –192с.

11. Избранные труды Л.С. Понтрягина (сер. «Выдающиеся ученые МГУ»).

– М.: МАКС Пресс, 2004.-552с.

12. Основы теории оптимального управления (под ред. В.Ф. Кротова) – М., ВШ,

1990, - 430с.

13. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир. 1982.

14. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. М.: Мир. 1985.

15. Хачиян Л.Г. Сложность задач линейного программирования. М.: Знание. 1987. № 10.

16. Карманов В.Г. Математическое программирование. М.: Наука. 1986.

17. Сухарев А..Г., Тимохов А..В., Федоров В.В. Курс методов оптимизации. М.: Наука. 1985.

18. Мину М. Математическое программирование. М.: Наука. 1990.

vmest.ru


Prostoy-Site | Все права защищены © 2018 | Карта сайта