16

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

Симплексный метод включает 3 основных элемента:

1. Нахождение исходного опорного решения

2. Правило перехода к «лучшему» опорному решению

3. Критерии, которые позволяют установить, является ли данное опорное решение оптимальным или его следует улучшить, или З.Л.П. не имеет решений.

Говорят, что З.Л.П. имеет симплексную форму, если система ограниченных уравнений (1) разрешена относительно базисных неизвестных, свободные члены уравнений системы больше 0, а линейная функция выражена через свободные неизвестные.

Отыскав исходное опорное решение и получив приведенное выражение для линейной функции f, мы тем самым привели З.Л.П. к симплексной форме.

Если все _, тогда З.Л.П. не имеет решения в виду неограниченности целевой функции в ОДР

Док-во.

Пусть З.Л.П. записана в симплексной форме

(1¹)

Построим какое-либо допустимое (неотрицательное) решение системы (1¹). Для этого в качестве свободных переменных возьмем

Из системы (1¹) найдем значение базисных неизвестных

X=(

Подсчитаем значение линейной функции

Из равенства (5) найдем значение функции на векторе X

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