Симплекс-метод - История изменений

Logic-samara в 18:11, 17 октября 2020

2020-10-17T18:11:57Z

: Содержимое страницы заменено на «Хуита»

2020-10-17T17:26:24Z

Содержимое страницы заменено на «Хуита»

Logic-samara в 18:29, 2 февраля 2016

2016-02-02T18:29:59Z

Logic-samara в 05:43, 14 января 2016

2016-01-14T05:43:48Z

Logic-samara в 05:43, 14 января 2016

2016-01-14T05:43:07Z

Logic-samara в 05:42, 14 января 2016

2016-01-14T05:42:08Z

Ws: Восстановление статей Logic-samara

2015-11-15T15:05:52Z

Восстановление статей Logic-samara

Новая страница

[[файл:СМ01.JPG|thumb|300|[[Математическая модель]] КЗ]]
== Определение ==
'''Симплекс-метод''' — метод для решения задач линейного программирования канонического вида, т.е. задач с ограничениями в форме равенств.

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

== [[Каноническая задача]] ==
Математическая модель канонической задачи имеет следующий вид:

[[файл:СМ01.JPG]]

или

[[файл:СМ02.JPG]]

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

== Расширенная матрица ==
Для построения симплекс-таблицы, необходимо выбрать базисные элементы, построить из базисных вектор-столбцов матрицы коэффициентов '''A''' базисную матрицу '''B'''. Затем рассчитать матрицу коэффициентов '''A’''' по формулам и построить расширенную матрицу.

[[файл: СМ03.JPG]].

Расширенная матрица исходной симплекс-таблицы имеет вид:

[[файл:СМ04.JPG]]

== Симплекс-таблица ==
Исходная симплекс-таблица имеет вид:

[[файл:СМ041.JPG]]

Формулы выбора переменных для ввода в базис и для вывода из базиса

[[файл:СМ05.JPG]]

В случае когда '''Δ=0''', опорное решение '''X''' - оптимальное и завершение итераций,
иначе строится новая симплекс-таблица с новым опорным решением.

Формулы перехода к новой симплекс-таблице имеют вид:

[[файл:СМ06.JPG]]

Расширенная матрица новой симплекс-таблицы имеет вид:

[[файл:СМ07.JPG]]

Новая симплекс-таблица имеет вид:

[[файл:СМ071.JPG]]

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

* Заметим, что при решении задачи максимизации при выборе новой переменной выбирают минимальную оценку '''Δj''', чтобы избавиться от всех отрицательных оценок '''Δj'''. При решении задачи минимизации при выборе новой переменной надо выбирать максимальную оценку '''Δj''', чтобы избавиться от всех положительных оценок '''Δj'''. Оценки '''Δj''' называются критериями оптимальности.

== Другие методы: ==
*[[Метод искусственного базиса]];
*[[М-метод]].

== Ссылки ==
* Юдин Д. Б., Гольштейн Е. Г. Линейное программирование., М.,1963.
* [[Участник:Logic-samara]]
[[Категория:Линейное программирование]]

@@ Строка 1: / Строка 1: @@
 [[файл:СМ01.JPG|thumb|300|[[Математическая модель]] КЗ]]
-'''Симплекс-метод''' — это метод для решения задач линейного программирования канонического вида, т.е. задач с ограничениями в форме равенств.
+'''Симплекс-метод''' — это метод для решения задач линейного программирования.
 == Описание метода ==
 Суть симплекс-метода состоит в переходе от одной угловой точки (одного базиса) многогранника допустимых решений к другой (другому базису) с целью оптимизации целевой функции. При этом симплекс-таблица в каждом базисе новая. Целевая функция соответствует гиперплоскости (в заданном базисе), которая проходит через угловую точку. Оценки оптимальности соответствуют отклонениям относительно гиперплоскости. Когда все оценки оптимальности положительны, тогда целевая функция достигает максимума, когда все оценки оптимальности отрицательны, тогда целевая функция достигает минимума.

← Предыдущая		Версия 18:11, 17 октября 2020
Строка 1:		Строка 1:
−	~~Хуита~~	+	[[файл:СМ01.JPG\|thumb\|300\|[[Математическая модель]] КЗ]]
		+	'''Симплекс-метод''' — это метод для решения задач линейного программирования.
		+	== Описание метода ==
		+	Суть симплекс-метода состоит в переходе от одной угловой точки (одного базиса) многогранника допустимых решений к другой (другому базису) с целью оптимизации целевой функции. При этом симплекс-таблица в каждом базисе новая. Целевая функция соответствует гиперплоскости (в заданном базисе), которая проходит через угловую точку. Оценки оптимальности соответствуют отклонениям относительно гиперплоскости. Когда все оценки оптимальности положительны, тогда целевая функция достигает максимума, когда все оценки оптимальности отрицательны, тогда целевая функция достигает минимума.
		+	== [[Каноническая задача]] ==
		+	Математическая модель канонической задачи имеет следующий вид:
		+
		+	[[файл:СМ01.JPG]]
		+
		+	или
		+
		+	[[файл:СМ02.JPG]]
		+
		+	В каждой угловой точке многогранника допустимых решений число базисных элементов совпадает с числом (независимых) уравнений. Симплекс-таблица для базисных элементов имеет единичные вектор-столбцы.
		+	== Расширенная матрица ==
		+	Для построения симплекс-таблицы, необходимо выбрать базисные элементы, построить из базисных вектор-столбцов матрицы коэффициентов '''A''' базисную матрицу '''B'''. Затем рассчитать матрицу коэффициентов '''A’''' по формулам и построить расширенную матрицу.
		+
		+	[[файл: СМ03.JPG]].
		+
		+	Расширенная матрица исходной симплекс-таблицы имеет вид:
		+
		+	[[файл:СМ04.JPG]]
		+	== Симплекс-таблица ==
		+	Исходная симплекс-таблица имеет вид:
		+
		+	[[файл:СМ041.JPG]]
		+
		+	Формулы выбора переменных для ввода в базис и для вывода из базиса
		+
		+	[[файл:СМ05.JPG]]
		+
		+	В случае когда '''Δ=0''', опорное решение '''X''' - оптимальное и завершение итераций,
		+	иначе строится новая симплекс-таблица с новым опорным решением.
		+
		+	Формулы перехода к новой симплекс-таблице имеют вид:
		+
		+	[[файл:СМ06.JPG]]
		+
		+	Расширенная матрица новой симплекс-таблицы имеет вид:
		+
		+	[[файл:СМ07.JPG]]
		+
		+	Новая симплекс-таблица имеет вид:
		+
		+	[[файл:СМ071.JPG]]
		+
		+	Далее переходят к выбору новых переменных для ввода в базис и для вывода из базиса.
		+	* Заметим, что при решении задачи максимизации при выборе новой переменной выбирают минимальную оценку '''Δ<sub>j</sub>''', чтобы избавиться от всех отрицательных оценок '''Δ<sub>j</sub>'''. При решении задачи минимизации при выборе новой переменной надо выбирать максимальную оценку '''Δ<sub>j</sub>''', чтобы избавиться от всех положительных оценок '''Δ<sub>j</sub>'''. Оценки '''Δ<sub>j</sub>''' называются критериями оптимальности.
		+	== Другие методы: ==
		+	*[[симплекс-метод]];
		+	*[[метод искусственного базиса]];
		+	*[[М-метод]].
		+	== Ссылки ==
		+	* Юдин Д. Б., Гольштейн Е. Г. Линейное программирование., М.,1963.
		+	* [[Участник:Logic-samara]]
		+	[[Категория:Линейное программирование]]

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