Математические основы теории систем (стр. 13 из 13)

Рассмотрим векторы: х_к=х_к(ℷ)= x_в-ℷb_ak^-1 ______

ℷ k=(m+1,n)

0

где ℷ является к - й компонентой вектора х.

Если х_в>0, то при малых ℷ>0; х_k≥0, т.к. Ах_k=в, то х_k∈R_○ при малых ℷ>0. Кроме того:

<C₁ x_k>=<C₁ x>-ℷ[<C_в, B^-1_ak>-C_k]=<C, x>-ℷ∆k

∆к - определитель для любого к=1,n, причем при к=1,m;

∆к=<C_в, B^-1_ak>-C_k=<C_в, C_к>C_к=C_к-C_к=0

Окончательно; <C₁ x_к>=<C₁x>-ℷ∆x (k=1,n)

3)Выбор столбца для ввода из базиса.

В зависимости от значков величины ∆к и (В^-1_ak); возникает 3 случая. ___

a)Если для любого к=1,n будет ∆к=0, то точка х - оптимальная. _____

б) Если найдется номер к≥m+1 такой, что ∆к>0 и В^-1_ak≤0, то множество R₀ неограниченно и функция <С₁х> неограниченна снизу на R₀.

в) Пусть найдутся такие к≥m+1 и i≤m, что ∆к>0 и (В^-1_akа )>0.

4)Конечность метода.

х_k - новая угловая точка, причем <C₁k>=<C₁x>-ℷ₀ ∆k < <C₁ x>. Из этого следует, что итерационный шаг симплексного метода состоит в таком переходе от базиса а₁, а₂,..., а_s, а_s+1, a_m к базису a₁, a₂,..., a_s-1, a_s+1,..., a_m, a_k при котором целевая функция убывает, а значит, симплексный метод приводит к угловой точке х*, в которой достигает минимума за конечное число итераций.

Стр: 19
[ВЮЮ1]

Стр: 19
[ВЮЮ2]

Стр: 29
[ВЮЮ3]

Стр: 1
[ВЮЮ4]