Новости    Библиотека    Байки    Ссылки    О сайте


предыдущая главасодержаниеследующая глава

5.1. Симплексный метод

(Симплексный метод часто называют "методом последователь-юго улучшения плана". )

По существу, симплексный метод представляет собой последовательный перебор угловых точек, при котором значение целевой функции убывает от итерации к итерации (от одной угловой точки - к другой).

Будем рассматривать каноническую задачу линейного программирования

(5.1)

Предполагается, что задача (5.1)-невырожденная, то есть не вырождена каждая угловая точка множества R0.

Итерационный шаг метода состоит в переходе от угловой точки х к угловой точке х', при котором значение целевой функции убывает:

<с, х'> < <с, х>.

Пусть известна угловая точка х. Не ограничивая общности, можно считать, что базис В этой угловой точки образуют первые т столбцов матрицы А. Будем записывать матрицу А следующим образом:

А = [В, D],

где


Соответствующим образом запишутся векторы х и с:


Компоненты вектора хв иногда называют базисными, а вектора xD-внебазисными.

Заметим, что если хоть одна компонента вектора хв-нулевая, то угловая точка х - вырожденная. В самом деле, если, например, хm=0, то, вычеркивая из матрицы В последние строку и столбец, получаем, что х удовлетворяет квадратной не особенной системе уравнений порядка m-1, то есть угловая точка х будет вырожденной.

Итак, известна угловая точка х. При этом.

хв>0, xD>0, detB≠0, BxB = b.

Рассмотрим векторы

(5.2)

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

Во-первых, заметим, что поскольку хв > 0, то при малых λ>0 будет хk≥0. Далее, так как

(5.3)

то xk∈R0 при малых λ > 0. Кроме того,


Обозначим

Δk = <cB, B-1ak> (5.4)

Заметим, что величина Δk определена для любого k = 1,..., n, причем при k = 1, ...., m, поскольку В-1ak=ek (ek - k-й координатный вектор), имеем

Δk = <cB, B-1ak> - ck = <cB, ek> - ck = ck - ck = 0

Окончательно получаем соотношение

<c, xk> = <c, x> - λΔk (k = 1,...,n)(5.5)

В зависимости от знаков величин Δk и (В-1ak)i возникают три случая.

I. Если для любого k = 1, 2, ..., n будет Δk≤0, то точка х - оптимальная.

Действительно, обозначим

ȳ=(B-1ak)i

Тогда условие Δk≤0 запишется так:


или, что то же самое,

ATȳ≤c

Поскольку двойственной к задаче (5.1) является задача

(5.6)

то ȳ ∈ Q0. И так как

<c, x> = <св, хв> = <св, B-1b> = <(B>-1)TcB, b>= <ȳ, b>

то из теоремы 4.4 следует оптимальность точки х. II. Если найдется номер k≥m+1 такой, что

Δk>0 и В-1аk≤0,

то множество R0 не ограничено и функция <с, х> не ограничена снизу на R0.

Действительно, из (5.2) следует, что при любом λ>0 будет

хk = хk(λ)≥0.

Отсюда и из (5.3) получаем, что xk(λ)∈R0. А из (5.5) следует, что

<c, xk(λ)>→-∞

при λ→+∞.

III. Пусть найдутся такие k≥m+1 и i≤m, что

Δk>0 и (B-1ak)>0*.

В этом случае делается итерационный шаг. Обозначим


и выберем

Заметим, что λ0 > 0, поскольку


* (Напомним, что запись (B-1ak)i означает i-ю компоненту вектора В-1аk.)

При таком выборе величины 0 точка хk = хk0) становится допустимой точкой множества R0 (см. (5.2) и (5.3)). Номер s, для которого достигается минимум в (5.7), единствен, ввиду не вырожденности задачи (5.1). В самом деле, если бы минимум достигался более чем для одного номера, то из (5.3) видно, что вектор b выражался бы линейно с положительными коэффициентами менее чем через m векторов аi матрицы A, то - есть точка хk удовлетворяла бы системе уравнений размерности меньшей m и, следовательно, точка хk была бы вырожденной угловой точкой. А это противоречит I предположению о не вырожденности. То, что хk - угловая точка, проверить нетрудно. Для этого достаточно показать, что система векторов а1, а,2 ..., as-1, as+1 , ..., am, аk линейно-независима. Предположим противное, то есть что найдутся такие числа β1, β2, ..., βs-1, βs+1 ,....,βm, βk, не все равные нулю, что

(5.8)

Обозначим

(5.9)

Тогда тождество ВВ-1хаkk≡0 запишется так:


Умножая это тождество на βk и складывая с (5.8), получаем


Так как det В≠0, то это равенство возможно лишь при всех нулевых коэффициентах:

βi + βkzik = 0 (i=1,...,m, t≠s), βkzsk=0.

Но

zsk=(B-1ak)s>0

поскольку s∈Ik, и, следовательно, βk = 0, а тогда и все βi = 0, что противоречит предположению о числах β1, β2,.....,bs-1, βs+1,...,βm, βk.

Итак, хk - новая угловая точка, причем

<с, хk> = <c, x> - λ6Δk < <c, x> (5.10)

"Из изложенного выше следует, что итерационный шаг симплексного метода состоит в таком переходе от базиса а1, а2, ..., as-1, as, аs+1, ..., аm к базису а1, а2, ..., as-1, аs+1, ..., аm при котором целевая функция убывает, а значит, симплексный метод приводит к угловой точке x*, в которой достигается минимум, за конечное число итераций.

предыдущая главасодержаниеследующая глава





Пользовательский поиск


Диски от INNOBI.RU




© Злыгостев Алексей Сергеевич, подборка материалов, оцифровка, статьи, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить активную ссылку на страницу источник:
http://informaticslib.ru/ "InformaticsLib.ru: Информатика"