Программа дисциплины (syllabus) (стр. 11 )

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

Тема 3 Нелинейное программирование.

Метод деления пополам

На каждой итерации исключается половина интервала.

1. Найти  и . Вычислить .

2. Найти  и . Вычислить  и .

3. Если , то исключается интервал , при этом ; перейти к п. 5.  Иначе перейти к п. 4.

4. Если , то исключается интервал , при этом ; перейти к п. 5.  Иначе исключить интервалы и , то есть ; перейти к п. 4.

5. Вычислить . Если , то закончить поиск. Иначе перейти к п. 2.

Достоинства метода:

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

2. После  вычислений длина интервала равна  длинны исходного интервала.

Тема 4 Численные методы оптимизации

Метод золотого сечения

Требуется минимизировать:f(x)=(100-x)2 в интервале 60<=х<=150

Решение: Для того, чтобы перейти к интервалу единичной длины, проведем заметку переменной, положив Z = (x-60)/90. Таким образом, задача принимает следующий вид:

·  минимизировать f(Z) = (40-90Z)2;

·  при ограничении 0<=Z<=1.

Итерация 1. Интервал: I1=(0,1); L1=1. Проведем два первых вычислений функции: Z1=q=0.618, f(Z1)=244.0 Z2=1-q=q2=0.382, f(Z2)=31.6. Т. к. f(Z2)<f(Z1) и Z2<Z1, интервал Z>=Z1 исключается.

Итерация 2. I2=(0, 0.618); L=0.618=q. Следующее вычисление значения функции проводится в точке. Z3=q-q2=q(1-q)=q3=0.236, f(Z3)=352. Т. к. f(Z3)>f(Z2) и Z3<Z2, интервал Z<=Z3 исключается.

Итерация 3. I3=(0.236, 0.618); L=0.382=q2. Следующее вычисление функции проводится в точке, расположенной на расстоянии q*(длина полученного интервала), или на расстоянии (1-q)*(длина интервала) от правой граничной точки. Таким образом: Z4=0.618 - (1-q)L3=0.618 - q2L3=0.618 -q2(q2)=0.618 - q4=0.472;f(Z4)=6.15. Т. к. f(Z4)<f(Z2) и Z4>Z2, интервал Z<=Z2 исключается.

В результате получен следующий интервал неопределенности: 0.382<=Z<=0.618 для переменной Z, или 94.4<=x<=115.6 для переменной x.

Тема 5 Вариационное исчисление

Тема 6 Метод динамического программирования Беллмана.

Задача (Задача о загрузке, или задача о рюкзаке (ранце)). Самолет загружается предметами n различных типов. Каждый предмет типа i имеет вес  и стоимость . Максимальная грузоподъемность самолета равна W.  Требуется определить максимальную стоимость груза, вес которого не должен превышать максимальной грузоподъемности самолета.

Обозначим количество предметов типа i через . Составим математическую модель задачи

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

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

Этап j ставится в соответствие типу j, . Состояние  на этапе j выражает суммарный вес предметов, решения о погрузке которых приняты на этапах ; при этом  и  при . Варианты решения  на  этапе j  описываются  количеством предметов типа j. Значение  заключено в пределах от нуля до . Пусть  – максимальная суммарная стоимость предметов, решения о погрузке которых приняты на этапах  при заданном состоянии . Рекуррентное соотношение (для процедуры обратной прогонки) имеет следующий вид:

Тема 7 Исследование операций.

Пример. Решить игру

.

Прежде всего проверим наличие седловой точки (в чистых стратегиях). Имеем

и, следовательно, седловых точек нет. Перейдем к нахождению оптимальных смешанных стратегий и значения игры. Используя формулы (17.22), получим:

Таким образом, .

Пример. Используя доминирование, мы свели игру к эквивалентной игре с матрицей выигрышей

.

Так как, , седловых точек в чистых стратегиях нет.

Перейдем к нахождению решения в смешанных стратегиях. По формулам имеем:

и, следовательно, .

Тема 8 Линейные и нелинейные модели.

С помощью симплекс-метода решить каноническую задачу линейного программирования: найти минимум целевой функции  

Решение

В первоначальное оптимальное решение добавим переменные , , , т. к. они встречается только в одном неравенстве. В качестве основных переменных выберем , ,