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

1) умение находить начальный опорный план;

2) наличие признака оптимальности опорного плана;

3) умение переходит к нехудшему опорному плану.

Алгоритм:

1) Математическая модель задачи должна иметь каноническую форму. В противном случаи её приводят к каноническому виду.

2) Находят начальное опорное решение задачи. Им является вектор, состоящий из тех переменных, которые входят только в одно уравнение в системе ограничений. Если начальное решение сразу не найти то используют метод Гаусса.

Количество переменных решения равно количеству уравнений системы. Заполняют симплексную таблицу по системе ограничений и целевой функции.

Макет симплексной таблицы:

Б							…
							…
							…
							…
…	…	…	…	…	…	…	…	…	…

Первый столбец – коэффициенты в целевой функции при базисных переменных.

Второй столбец – базисные переменные.

Третий столбец – свободные члены.

Самая верхняя строка – коэффициенты при целевой функции.

Вторая верхняя строка – сами переменные, входящие в целевую функцию и в систему ограничений.

Основное поле симплекс метода – система коэффициентов из уравнения.

Последняя строка – служит для того, чтобы ответить на вопрос: “оптимален план или нет ”.

Индексная строка позволяет нам судить об оптимальности плана.

3) Проверяют опорное решение, на оптимальность, вычисляя коэффициенты индексной строки по форме:

При решении задачи возможны два случая:

- При решении задачи на максимум:

а) все оценки следует, что решение оптимальное

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

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

- При решении задачи на минимум:

а) все оценки следует, что решение оптимальное

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

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

4) Новое опорное решение находится с помощью ключевого столбца, ключевой строки и ключевого элемента.

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

Ключевая строка указывает на переменную, которую надо вывести из числа базисных для улучшения решения.

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

Их нахождения зависит от цели задачи.

- При решении задачи на максимум:

а) ключевой столбец – это столбец с отрицательной наименьшей оценкой  в индексной строке.

б) ключевая строка – это строка с наименьшим отношением свободных членов к положительным коэффициентам ключевого столбца:

min  =

в) ключевой элемент – это число расположенное на пересечении ключевых столбца и строки(не может быть равен нулю).

- При решении задач на минимум:

а) ключевой столбец – это столбец с положительной наименьшей оценкой  в индексной строке.

б) ключевая строка – это строка с наибольшим отношением свободных членов к положительным коэффициентам ключевого столбца:

mах  =

в) ключевой элемент – это число расположено на пересечении ключевых столбца и строки.

5) Заполняют первую симплексную таблицу следующим образом:

а) ключевую строку делят на ключевой элемент и записывают на том же месте в новой таблице.

б) заполняют базисные столбцы.

в) остальные элементы пересчитывают по правилу “прямоугольника”:

НЭ = СТЭ –

где НЭ – новый элемент

СТЭ – элемент старого плана

РЭ – разрешающей элемент

А и Б – элементы старого плана

6)  Возвращаются ко второму этапу алгоритма – проверка плана на оптимальность.