14

Билет 14.

Симплексный метод решения задачи линейного программирования. Теорема о возможности «улучшить» решение.

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

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

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

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

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

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

Теорема о возможности «улучшить» решение: 1) Сущ-т δ_s < 0 и а_is > 0 – в столбце над каждой отрицательной оценкой есть положительные элементы, то решение можно улучшить, т.е. перейти к другому опорному решению, у которого значение функции будет больше.

Док-во. Выполним замещение с разрешающим элементом а_ks :

1. S-ый столбец – разрешающий

2. К-ая строчка: = min {}, a_is > 0

К-ая строчка -----b_k------a_ks

Оценочная строчка -----δ₀-------δ_s

δ^’₀= δ₀ - δ_s(<0) > δ₀ = f(x₀)

δ^’₀ = f(x₁); Δf = f(x₁) – f(x₀) = δ^’₀ - δ₀ = δ₀ – δ_s - δ₀ = - δ_s >0