- •1.Проблемные ситуации и их классификация
- •6. Задача о наилучшем использовании ресурсов
- •7.Задача о распределения персонала (о назначения)
- •8. Транспортная задача открытого и закрытого типа
- •9. Задача о движении автобусов
- •10. Математическая модель задачи линейного программирования
- •11.Формы записи задачи линейного программирования
- •12.Линейное векторное пространство. Линейная зависимость векторов. Ранг.
- •13.Понятие базиса системы. Базисное и опорное решение системы.
- •14.Отыскание исходного опорного базиса
- •15.Переход от одного опорного решения к другому
- •16.Каноническая форма задачи линейного программирования
- •17. Приведение задачи линейного программирования к канонической форме
- •18. Геометрический смысл задачи линейного программирования
- •19. Свойства решений задачи линейного программирования (без док)
- •24. Основная идея симплекс-метода решения злп и ее теоретическое обоснование
- •25. Теорема о возможности улучшения опорного решения задачи лп
- •26. Условие применимости симплекс-метода и теорема о неограниченности целевой функции на одз
- •27. Структура симплекс таблицы
- •28. Алгоритм симплексного метода решения злп
- •29. Контроль за правильностью решения злп симплекс-методом
- •30. Понятие о вырождении. Причины зацикливания в симплекс-методе
- •31. Понятие двойственности в линейном программировании. Правила построения двойственных задач
- •32.Леммы и теоремы двойственности (без док)
- •33. Применение двойственных задач
- •34. Связь между решениями прямой и двойственной задачи на примере пары симметричных задач
- •35.Экономическая интерпретация двойственных задач (на примере). Экономический смысл 1-ой теоремы двойственности
- •36. Оптимальные двойственные оценки и их смысл в задаче об использовании ресурсов.
- •37. Анализ моделей на устойчивость и чувствительность
- •38. Метод искусственного базиса
- •39. Основные понятия теории игр
- •40. Антагонистические игры, седловая точка
- •41. Чистые и смешанные стратегии матричных игр с нулевой суммой, платежная функция
- •42. Теорема о необходимом и достаточном условии существования решения антагонистической игры
- •43. Правила упрощения матричной игры
- •44. Решение матричной игры 2x2
- •45. Геометрическое решение матричной игры Mx2, 2xN
- •46. Приведение матричной игры к задаче линейного программирования
- •47. Статистические игры. Критерии для принятия решений
- •48.Общая постановка задачи нелинейного программирования
- •49. Геометрическая интерпретация задачи нелинейного программирования
- •50. Геометрический способ решения задачи нелинейного программирования
- •51.Глобальный (абсолютный) и локальный экстремум функции
- •52.Условный экстремум функции
- •53. Метод неопределенных множителей Лагранжа.
- •54. Определение выпуклой и вогнутой функции
- •55. Общая постановка задачи выпуклого программирования. Теорема о существовании решения задачи вп (формулировка)
- •56. Седловая точка функции Лагранжа
- •57. Теорема Куна-Таккера
- •58.Основная идея градиентных методов решения знлп
- •59.Метод Франка –Вульфа
- •60. Метод штрафных функций
- •61. Метод наискорейшего спуска
- •62. Определение сепарабельной функции
- •63. Кусочно-линейная аппроксимация
- •64. Задача целочисленного программирования, методы ее решения
- •65. Задача дробно-линейного программирования, геометрическая интерпретация и метод решения
- •66. Постановка задачи параметрического программирования и принципы ее решения
- •67. Постановка задачи динамического программирования
- •68. Задачи, приводящие к задаче динамического программирования
- •69. Принцип оптимальности Беллмана
- •70. Связь проблемы выбора с задачами лп, нлп, игр
24. Основная идея симплекс-метода решения злп и ее теоретическое обоснование
геометрическим методом решение- наглядное 2.3.перем. если больше то нельзя.
методом простого перебора- можно но долго
Если известны какая-нибудь крайняя точка и значение целевой функции, то все крайние точки, в которых целевая функция принимает худшее значение, заведмо не нужны. Отсюда естественно стремление найти способ перехода от данной крайней точки к смежной по ребру лучшей, от нее к еще лучшей (не худшей). Для этого нужно иметь признак того, что лучших крайних точек, чем данная крайняя точка, вообще нет. В этом и состоит общая идея (рационального перебора). симплексного метода ( метода последовательного улучшения плана) для решения ЗЛП. Итак, симп. м. предполагает : 1) умение находить начальный опорный план; 2) наличие признака оптимальности опорного плана; 3) умение переходить к нехудшему опорному плану.
25. Теорема о возможности улучшения опорного решения задачи лп
Т . Если опорный план Х ЗЛП не вырожден и k<0, но среди чисел aik есть положительные ( не все aik<0), то существует опорный план X’ такой, что Z(X’)>Z(X), где Х исходное опорные решения.
26. Условие применимости симплекс-метода и теорема о неограниченности целевой функции на одз
Т . Если k<0 для некоторого j=k и среди чисел aik ( )нет положительных, то целевая функция ЗЛП не ограничена на множестве ее планов.
27. Структура симплекс таблицы
|
с1 |
с2 |
... |
сi |
... |
сm |
cm+1 |
... |
cj |
... |
cn |
||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Базис |
Сб |
А0 |
A1 |
A2 |
... |
Ai |
... |
Am |
Am+1 |
... |
Aj |
... |
An |
||
A1 |
с1 |
b1 |
1 |
0 |
... |
0 |
... |
0 |
a1,m+1 |
... |
a1,j |
... |
a1,n |
||
A2 |
с2 |
b2 |
0 |
1 |
... |
0 |
... |
0 |
a2,m+1 |
... |
a2,j |
... |
a2,n |
||
... |
... |
... |
... |
... |
... |
... |
... |
... |
... |
... |
... |
... |
... |
||
Ai |
сi |
bi |
0 |
0 |
... |
1 |
... |
0 |
ai,m+1 |
... |
ai,j |
... |
ai,n |
||
... |
... |
... |
... |
... |
... |
... |
... |
... |
... |
... |
... |
... |
... |
||
Am |
сm |
bm |
0 |
0 |
... |
|
... |
1 |
am,m+1 |
... |
am,j |
... |
am,n |
||
Zj-cj |
0 |
0 |
0 |
... |
0 |
... |
0 |
m+1 |
... |
j |
... |
n |
|||
28. Алгоритм симплексного метода решения злп
1. Находят опорный план.
2. Составляют симплекс-таблицу.
3. Выясняют, имеется ли хотя бы одно положительное число j . Если нет, то найденный план оптимален. Если же среди чисел j имеются положительные, то либо устанавливают неразрешимость задачи, либо переходят к новому опорному плану.
4. Находят разрешающие столбец и строку. Разрешающий столбец определяется наибольшим по абсолютной величине положительным числом j , а разрешающая строка — минимальным из отношений компонент столбца вектора А0 к положительным компонентам разрешающего столбца.
5. Определяют положительные компоненты нового опорного плана, коэффициенты разложения векторов Аi по векторам нового базиса и числа 0 и j.Все эти числа записываются в новой симплекс-таблице.
6. Проверяют найденный опорный план на оптимальность. Если план не оптимален и необходимо перейти к новому опорному плану, то возвращаются к этапу 4, а в случае получения оптимального плана или установления неразрешимости процесс решения задачи заканчивают.