Симплекс-метод — различия между версиями
Ws (обсуждение | вклад) (Восстановление статей Logic-samara) |
|||
Строка 1: | Строка 1: | ||
[[файл:СМ01.JPG|thumb|300|[[Математическая модель]] КЗ]] | [[файл:СМ01.JPG|thumb|300|[[Математическая модель]] КЗ]] | ||
− | |||
'''Симплекс-метод''' — метод для решения задач линейного программирования канонического вида, т.е. задач с ограничениями в форме равенств. | '''Симплекс-метод''' — метод для решения задач линейного программирования канонического вида, т.е. задач с ограничениями в форме равенств. | ||
− | + | == Описание метода == | |
Суть симплекс-метода состоит в переходе от одной угловой точки (одного базиса) многогранника допустимых решений к другой (другому базису) с целью оптимизации целевой функции. При этом симплекс-таблица в каждом базисе новая. Целевая функция соответствует гиперплоскости (в заданном базисе), которая проходит через угловую точку. Оценки оптимальности соответствуют отклонениям относительно гиперплоскости. Когда все оценки оптимальности положительны, тогда целевая функция достигает максимума, когда все оценки оптимальности отрицательны, тогда целевая функция достигает минимума. | Суть симплекс-метода состоит в переходе от одной угловой точки (одного базиса) многогранника допустимых решений к другой (другому базису) с целью оптимизации целевой функции. При этом симплекс-таблица в каждом базисе новая. Целевая функция соответствует гиперплоскости (в заданном базисе), которая проходит через угловую точку. Оценки оптимальности соответствуют отклонениям относительно гиперплоскости. Когда все оценки оптимальности положительны, тогда целевая функция достигает максимума, когда все оценки оптимальности отрицательны, тогда целевая функция достигает минимума. | ||
− | |||
== [[Каноническая задача]] == | == [[Каноническая задача]] == | ||
Математическая модель канонической задачи имеет следующий вид: | Математическая модель канонической задачи имеет следующий вид: | ||
Строка 15: | Строка 13: | ||
В каждой угловой точке многогранника допустимых решений число базисных элементов совпадает с числом (независимых) уравнений. Симплекс-таблица для базисных элементов имеет единичные вектор-столбцы. | В каждой угловой точке многогранника допустимых решений число базисных элементов совпадает с числом (независимых) уравнений. Симплекс-таблица для базисных элементов имеет единичные вектор-столбцы. | ||
− | |||
== Расширенная матрица == | == Расширенная матрица == | ||
Для построения симплекс-таблицы, необходимо выбрать базисные элементы, построить из базисных вектор-столбцов матрицы коэффициентов '''A''' базисную матрицу '''B'''. Затем рассчитать матрицу коэффициентов '''A’''' по формулам и построить расширенную матрицу. | Для построения симплекс-таблицы, необходимо выбрать базисные элементы, построить из базисных вектор-столбцов матрицы коэффициентов '''A''' базисную матрицу '''B'''. Затем рассчитать матрицу коэффициентов '''A’''' по формулам и построить расширенную матрицу. | ||
Строка 24: | Строка 21: | ||
[[файл:СМ04.JPG]] | [[файл:СМ04.JPG]] | ||
− | |||
== Симплекс-таблица == | == Симплекс-таблица == | ||
Исходная симплекс-таблица имеет вид: | Исходная симплекс-таблица имеет вид: | ||
Строка 50: | Строка 46: | ||
Далее переходят к выбору новых переменных для ввода в базис и для вывода из базиса. | Далее переходят к выбору новых переменных для ввода в базис и для вывода из базиса. | ||
− | |||
* Заметим, что при решении задачи максимизации при выборе новой переменной выбирают минимальную оценку '''Δ<sub>j</sub>''', чтобы избавиться от всех отрицательных оценок '''Δ<sub>j</sub>'''. При решении задачи минимизации при выборе новой переменной надо выбирать максимальную оценку '''Δ<sub>j</sub>''', чтобы избавиться от всех положительных оценок '''Δ<sub>j</sub>'''. Оценки '''Δ<sub>j</sub>''' называются критериями оптимальности. | * Заметим, что при решении задачи максимизации при выборе новой переменной выбирают минимальную оценку '''Δ<sub>j</sub>''', чтобы избавиться от всех отрицательных оценок '''Δ<sub>j</sub>'''. При решении задачи минимизации при выборе новой переменной надо выбирать максимальную оценку '''Δ<sub>j</sub>''', чтобы избавиться от всех положительных оценок '''Δ<sub>j</sub>'''. Оценки '''Δ<sub>j</sub>''' называются критериями оптимальности. | ||
− | |||
== Другие методы: == | == Другие методы: == | ||
*[[Метод искусственного базиса]]; | *[[Метод искусственного базиса]]; | ||
*[[М-метод]]. | *[[М-метод]]. | ||
− | |||
== Ссылки == | == Ссылки == | ||
* Юдин Д. Б., Гольштейн Е. Г. Линейное программирование., М.,1963. | * Юдин Д. Б., Гольштейн Е. Г. Линейное программирование., М.,1963. | ||
* [[Участник:Logic-samara]] | * [[Участник:Logic-samara]] | ||
[[Категория:Линейное программирование]] | [[Категория:Линейное программирование]] |
Версия 05:42, 14 января 2016
Симплекс-метод — метод для решения задач линейного программирования канонического вида, т.е. задач с ограничениями в форме равенств.
Содержание
Описание метода
Суть симплекс-метода состоит в переходе от одной угловой точки (одного базиса) многогранника допустимых решений к другой (другому базису) с целью оптимизации целевой функции. При этом симплекс-таблица в каждом базисе новая. Целевая функция соответствует гиперплоскости (в заданном базисе), которая проходит через угловую точку. Оценки оптимальности соответствуют отклонениям относительно гиперплоскости. Когда все оценки оптимальности положительны, тогда целевая функция достигает максимума, когда все оценки оптимальности отрицательны, тогда целевая функция достигает минимума.
Каноническая задача
Математическая модель канонической задачи имеет следующий вид:
или
В каждой угловой точке многогранника допустимых решений число базисных элементов совпадает с числом (независимых) уравнений. Симплекс-таблица для базисных элементов имеет единичные вектор-столбцы.
Расширенная матрица
Для построения симплекс-таблицы, необходимо выбрать базисные элементы, построить из базисных вектор-столбцов матрицы коэффициентов A базисную матрицу B. Затем рассчитать матрицу коэффициентов A’ по формулам и построить расширенную матрицу.
Расширенная матрица исходной симплекс-таблицы имеет вид:
Симплекс-таблица
Исходная симплекс-таблица имеет вид:
Формулы выбора переменных для ввода в базис и для вывода из базиса
В случае когда Δ=0, опорное решение X - оптимальное и завершение итераций, иначе строится новая симплекс-таблица с новым опорным решением.
Формулы перехода к новой симплекс-таблице имеют вид:
Расширенная матрица новой симплекс-таблицы имеет вид:
Новая симплекс-таблица имеет вид:
Далее переходят к выбору новых переменных для ввода в базис и для вывода из базиса.
- Заметим, что при решении задачи максимизации при выборе новой переменной выбирают минимальную оценку Δj, чтобы избавиться от всех отрицательных оценок Δj. При решении задачи минимизации при выборе новой переменной надо выбирать максимальную оценку Δj, чтобы избавиться от всех положительных оценок Δj. Оценки Δj называются критериями оптимальности.
Другие методы:
Ссылки
- Юдин Д. Б., Гольштейн Е. Г. Линейное программирование., М.,1963.
- Участник:Logic-samara