1 Этапы построения математической модели

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

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

Наконец, составляется целевая функция, которая в математической форме отражает критерий выбора лучшего варианта.

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

2 Геометрическая интерпретация задачи ЛП

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

1. Основной случай - получающаяся область имеет вид ограниченного выпуклого многоугольника ( см. рис. 6).

2. Неосновной случай  получается неограниченный выпуклый многоугольник, имеющий вид, подобный изображенному на рис. 7. Подобная ситуация, например, получится, если в рассмотренном выше примере убрать ограничение . Оставшаяся часть будет неограниченным выпуклым многоугольником.

3. Наконец, возможен случай, когда неравенства (1.22) противоречат друг другу, и допустимая область вообще пуста.

3 Геометрическая интерпретация задачи ЛП по целевой функции

Строим прямую на плоскости по уравнению целевой функции и указываем её направление (max, min), передвигает прямую параллельно себе в границе допустимой области в направлении функции.

Возможны варианты

- функция выйдет за пределы допустимой области на пересечении 2 прямых из ограничений(тогда точка пересечения будет являться оптимальным значением целевой функции )

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

- если область допустимых значений неограниченна то значение целевой функции тоже будет неограниченно

4 Векторный вид канонической формы задачи ЛП

Каноничная форма ЗЛП

В векторной форме:

В матричной форме:

Во всех этих задачах функцию  называют целевой функцией. Вектор  называют вектором коэффициентовлинейной формы, вектор   вектором ограничений.

Матрицу

называют матрицей коэффициентов.

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

---

5 Скалярный вид задачи ЛП

Первая форма	Вторая форма	Каноническая форма

6 Специальная форма ЛП (Симплекс метод)

7 Базисное решение

Записанная в стандартной форме задача линейного программирования содержит m линейных равенств и n неизвестных переменных, причем m < n. Разделим эти переменные на два множества: n − m равных нулю и m, определенных как решение соответствующей системы. Если это решение единственное – назовем эти переменные базисными, а остальные – небазисными. В этом случае получившееся решение называется базисным решением. Если при этом все переменные неотрицательны, то такое решение называем допустимым, а в противном случае – недопустимым. //т. e. грубо говоря вектор который мы получаем когда получаем допустимое решение в симплекс таблице

7* Базисное допустимое решение

Базисное решение - свободные переменные равны нулю

Базисное решение называется допустимым базисным решением или опорным решением, если в нем значения переменных неотрицательны.

7* базисное недопустимое решение

Базисное решение называется недопустимым базисным решением,  если в нем значение хотя бы одной переменной меньше нуля.

8 Вырожденное базисное решение

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

Особые случаи:

Вырожденность Вырожденный случай – случай, в котором одна из базисных переменных имеет нулевое значение. Что означает, что в исходной задаче присутствует избыточное ограничение. •

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

Неограниченные решения Иногда, обычно в случае некорректной постановки задачи (не учтен некоторые параметры) решение может неограниченно возрастать (убывать – в случае минимизации). Если на некоторой итерации коэффициенты в ограничениях для небазисной переменной не положительны, а коэффициент в z-строке отрицателен, то значение целевой функции неограничено (в случае задачи максимизации).

Отсутствие допустимых решений Возможны также случаи, когда допустимых решений нет. То есть области заданные неравенствами имеют пустое пересечение. Это означает, что задача плохо сформулирована (или действительно не имеет решений).

8* невырожденное базисное решение

Базисное решение называется невырожденным, если базисные переменные не равны нулю.

9 Оптимальная симплекс таблица

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

---

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

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

10 Неразрешимость задачи ЛП

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

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

11 Правила построения отсечения в методе Гоммори

Среди дробных компонент таблицы выбираем элемент с максимальной дробной частью и по строке i составляем дополнительное ограничение:

Здесь - целая часть числа (наибольшее целое число, не превышающее число ).

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

12 Свойства отсечений в методе Гоммори

- оно должно быть линейным;

- должно отсекать найденный оптимальный нецелочисленный план;

- не должно отсекать ни одного целочисленного плана.

13 Ситуации, когда ЦЛП не имеет решений

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

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

14 Транспортная задача открытого типа

Транспортной задачей называется разновидность задач линейного программирования, общая постановка которой такова.

Имеется m пунктов производства однородного продукта с объемами производства  и n пунктов потребления с объемами потребления . Известна стоимость перевозки единицы продукта от каждого пункта производства до каждого пункта потребления: , 

Транспортной задачей открытого типа называется задача в которой суммарное количество запасов и суммарное количество потребления не равны.

15 Транспортная задача закрытого типа

Различают два типа транспортных задач. Если суммарные запасы продукта поставщиков равны суммарным объемам потребления

,

то это задача закрытого типа. В противном случае задачу называют задачей открытого типа.

16 Балансовое равенство

Сумма всех запасов равна сумме всех потребностей

17 Условие дополняющей нежесткости

---

Пара двойственных задач

L=cx → max <-> L=bu→min

Ax ≤ b <-> u ≥ 0

x ≥ 0 <-> A^Tu >= c

пара задач для канонической задачи на макс

L=cx -> max <-> L=bu -> min

Ax=b <-> u - произвольные

x ≥ 0 <-> A^Tu ≥ c

пара задач для канонической задачи на мин

L=cx -> min <-> L=bu-> max

Ax=b <-> u - произвольные

x ≥ 0 <-> A^Tu ≤ c

Условие дополняющей нежесткости

В паре сопряженных задач

a ≤ b <-> b ≤ c

1 a = b ==> b < c

2 b < c ==> a=b

3 если AiX1+ …..+ AinXn< Bi тогда Ui=0

4 если Ui>0 то AiX1+ …..+ AinXn= Bi

5 если Xj>0 то AijU1+ ……+AmjXm=Cj

6 если AijU1+ ……+AmjXm>Cj то Xj=0

18 Условие дополняющей нежесткости для транспортной задачи

1) если i-й ресурс расходует не весь (с остатком) ==> оценка i-ресурса ≥0 (a₁₁x₁+ …+a_1nx_n<b₁)

2) если оценка > 0 ==> ресурс тратится весь

3) если x_j^*>0 , тогда оценка всех ресурсов = цене реализации

A₁₁U₁+….+A_m1U_m=C₁

4) если суммарная оценка вложенных ресурсов > цены реализации, то x_j=0 производство невыгодно.

19 Условия при которых задача относится к динамическому программированию

1 сепарабельность (разделимость)

Мультипликативная (функция зависит он n элементов) f(x₁…x_n)=f₁(x₁)*f₂(x₂)…….*f_n(x_n)

Аддитивная (функция зависит он n элементов) f(x₁…x_n)= f₁(x₁)+……+f_n(x_n)

2 Структурные ограничения простые, их количество не большое (1,2)

20 Уравнение состояния Беллмана

принципа оптимальности Беллмана: каково бы ни было состояние системы перед очередным шагом, необходимо выбирать управление на этом шаге так, чтобы доход на данном шаге вместе с оптимальным доходом на всех последующих шагах был максимальным.

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

21 Общий вид Уравнения Бэллмана

22 Уравнение состояния Беллмана

С остояние на определенном шаге будет зависеть от состояния системы в предыдущий момент времени и выбранного управления X_k

23 Уравнение Бэллмана для задачи распределение ресурсов

N – количество потребителей

Q – начальное количество ресурсов распред между n потребителями, каждый дает эффективность Fk в зависимости от выделенных средств Xk

Распределить средства с максимальной эффективностью

24 Уравнение Бэллмана для задачи о рюкзаке

N – предметов

Q – вместимость рюкзака

d_i – вес предмета i-го типа

c_i – эффективность предмета i-го типа

i=1….n

x_i – количество экземпляров i-го вида

альтернатив модель x=1 ,берем x=0 не берем

L= c₁x₁+…..+ c_nx_n → max

d₁x₁+….+d_nx_n ≤ Q

x_i≥0 , целые

X_k- количество предметов к-го типа

25 Уравнение Бэллмана для задачи о пожаре

N – предметов

c_i – эффективность(ценность) предмета i-го типа

i=1….n

x_i –i-й предмет

x=1 ,берем

x = 0 не берем

L= c1x1+…..+ cnxn -> max

x₁+….+x_n ≤N

x_i≥0 , целые

27 Уравнение Бэллмана для задачи о замене оборудования

N – периодов эксплуатации оборудования

R_i – затрата на эксплуатации оборудования возраста i

---

C_i – эффективность оборудования возраста i

P₀ – стоимость нового оборудования

Ѱ_i – ликвидная стоимость оборудования возраста i

i=1….n

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

Решение о замене принимается в начале К этапа

В начала эксплуатации оборудование новоге (t=0)

28 Определение смешанной стратегии (чистой стратегии) при решении матричной игры

Седловая точка должна отсутствовать.

Седловая точка – это пара оптимальных стратегий (A_i, B_j). В этом случае число a=b называется (чистой) ценой игры (нижняя и верхняя цена игры совпадают). Это означает, что матрица содержит такой элемент, который является минимальным в своей строке и одновременно максимальным в своем столбце.

Вкратце: Смешанной стратегией игрока называются случайные величины, возможные значения которых являются чистые стратегии.

Смешанная стратегия состоит из чистых стратегий и соответствующих им вероятностей. Сумма вероятностей для игрока равна 1. Применение игроком чистой стратегии – частный случай смешанной стратегии.

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

• игроки используют случайную смесь чистых стратегий с заданными вероятностями;

• игра многократно повторяется в сходных условиях;

• при каждом из ходов ни один игрок не информирован о выборе стратегии другим игроком;

• допускается осреднение результатов игр.

29 Задача ЛП для первого игрока матричной игры

30 Задача ЛП для второго игрока матричной игры

31 Общий вид задачи нелинейной оптимизации

32Критерий остановки итерационного алгоритма

33 Линия уровня в задаче оптимизации

Линия уровня – геометрическое место точек в пространстве в которой значение целевой функции

34 Определение точки минимума в задачи оптимизации

35 Определение точки максимума в задачи оптимизации

Аналитическая форма условия выбора направления

Г радиент – возрастает. Антиградиент – убывает.

S^k должен образовывать угол более 90 градусов со всеми ограничениями в этой точке.

(f_i(x^k) , S^k) < 0 (Z,p) = ||z|| * ||p||*cos(α)

(f_j(x^k) , S^k) < 0

36 Аналитическая форма для сохранения допустимости

((x^k) , S^k) ≤ 0, i ∈ I(x^k)

37 Аналитическая форма для обеспечения убывания

Н аправление должен образовывать угол больше 90 градусов с касательной в x^k

( (x^k) | S^k) < 0

38 Активное ограничение (Множество активных ограничение)

39 Задача ЛП для выбора направление S^k в выборе условных направлений

40 Выбор S^k в методе наискорейшего спуска

41 Выбор S^k в координатном спуске

42 Выбор величины шага в методе наискорейшего спуска

43 Выбор S^k в методе спуска (Матрице Гессце)

---

Смотрите также файлы

• Зачет, АП, 1-66 вопросы.docx

• iogpgp.docx

• Diplom_Tipografia.docx

• summaries 4&5 units.pdf

• Rukovodstvo po radiosvyazi MCHS Rossii 2006.pdf