![]()
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Симплексный метод решения задач линейного программированияСимплексный метод решения задач линейного программирования Данные метод состоит в целенаправленном переборе опорных решений задачи линейного программирования. Он позволяет за конечное число шагов расчёта либо найти оптимальное решение, либо установить его отсутствие.
Симплексные таблицы Систему ограничений сведем к единичному базису: и линейную форму L – к виду
В виде таблицы эти данные можно представить так:
Равенство (**) будем называть приведённым (к свободным переменным) выражением для функции L, а коэффициенты γj - оценками (индексами) соответствующих свободных переменных xj. 1) Выбирается разрешающий столбец ap из условия: оценка γp<0 и хотя бы один элемент aip>0. 2) Выбирается q-я разрешающая строка из условия
3) Производится пересчёт элементов разрешающей q-й строки по формуле
4) Вычисляются элементы всех остальных строк (при k ≠ p) по формуле
Теорема. Если после выполнения очередной итерации: 1) найдется хотя бы одна отрицательная оценка и в каждом столбце с такой оценкой будет хотя бы один положительный элемент, т.е. γk<0 для некоторых k, и aik>0 для тех же k и некоторого i, то можно улучшить решение, выполнив следующую итерацию: 2) найдётся хотя бы одна отрицательная оценка, столбец которой не содержит положительных элементов, т.е. для какого-то k и всех i, то функция L не ограничена в области допустимых решений ( 3) все оценки окажутся неотрицательными, т.е.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|