Москвин Б.В. Теория принятия решений

Подождите немного. Документ загружается.

3.4. Основные элементы алгоритмов линейного

программирования

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

ноническом виде:

L = c

x → max c

+ … + c

→ max

+ … + a

= b

A x = b или . . . . . . . . . . . . . . . . . .

+ … + a

= b

x ≥ 0 x

≥ 0, j = 1,…, n

или

║c

,….., c

║x → max

,…, a

. . . . . . . . . . .

…= …

,…, a

Матрицу условий можно представить в виде совокупности векто-

ров условий

A = ║a

,….., a

║.

Здесь a

, j=1,...,n - векторы условий задачи линейного программи-

рования.

Пусть J = {1,..., n } - множество номеров векторов условий.

Тогда можно выделить J

= {s1,...,sm} ⊂ J, такое, что множество

векторов условий {a

, a

,..., a

} образуют базис матрицы А (мак-

симальную линейно независимую систему векторов).

S = ║a

,….., a

║ = ║a

, j∈J

║ - матрица базиса.

Если x

= S

-1

b, такое, что x

≥ 0, то

S называется матрицей о п о р н о г о базиса, а

называется о п о р н ы м решением.

Опорное решение соответствует вершине многогранника реше-

ний задачи линейного программирования.

Множество J

= J \ J

- множество номеров небазисных

(свободных) переменных. Тогда x = ║x

║

, где x

- базисные

переменные; x

- небазисные (свободные) переменные;

≥ 0; │x

│= m; x

= 0; │x

│= n - m.

Тогда матрицу А можно представить в виде

A = ║S Q║,

где S = ║a

, j∈J

║; Q = ║a

, j∈J

= J \ J

║.

Решение x

= S

-1

b - опорное решение; c

= ║c

, j∈J

║ - компонен-

ты вектора коэффициентов целевой функции, соответствующие

опорному решению, L(x

) = c

Рассмотрим основные элементы, составляющие формаль-

ную основу различных алгоритмов линейного программирования

(в частности, симплекс-метода).

1. Признак оптимальности опорного решения (плана)

Признаком оптимальности опорного решения выступает

следующее условие

A - c

≥ 0 или π

- c

≥ 0, j = 1,.., n (3.10)

где

= c

-1

(3.11)

Здесь π - вектор двойственных оценок векторов условий относи-

тельно текущего базиса (разрешающий вектор).

Покажем, что если выполняется данный признак, то опор-

ное решение оптимально. Действительно,

A - c

≥ 0, откуда π

A x ≥ c

x = L(x), ∀x∈∆

В то же время левая часть последнего неравенства

A x = c

-1

A x = c

-1

b = c

= L(x

)

Т.е. L(x

) ≥ L(x), ∀x ∈ Δ, следовательно, x

- оптимально (x

= x

С другой стороны, если ∃k∈J│π

- c

< 0, то ∃x∈Δ│L(x) ≥

L(x

), т.е. существует другая вершина многогранника условий с

большим значением целевой функции.

2). Приращение целевой функции

Итак, если признак оптимальности не выполняется, то су-

ществует другое опорное решение, позволяющее увеличить зна-

чение целевой функции. Здесь можно сформулировать два во-

проса:

- на какую величину возрастет значение целевой функции;

- каким образом этого увеличения достичь.

Если признак оптимальности не выполняется, следова-

тельно, хотя бы одну из небазисных переменных целесообразно

ввести в базис, т.е. она должна принять значение большее 0.

Пусть это будет k-я переменная x

, и она примет значение θ, т.е.

= θ > 0.

Тогда, если

S x

= b,

то S x

- a

+ a

= b,

или S x

- θ a

+ θ a

= b,

или S(x

- θ S

-1

) + θ a

= b,

или, обозначая æ

= S

-1

S(x

- θæ

) + θ a

= b.

Обозначим x

(θ) = x

- θæ

тогда S x

(θ) + θ a

= b.

Значение целевой функции, вычисленное для x

(θ)

L(x

(θ)) = c

(θ) + c

θ =

= c

- θ æ

) + c

θ =

= c

- c

θ æ

+ c

θ =... т.к. æ

= S

-1

= c

- θ ( c

-1

- c

) =

= L(x

) - θ δ

где δ

= c

-1

- c

= π

- c

Тогда приращение значения целевой функции

ΔL = L(x

(θ)) - L(x

) = - θ δ

(3.12)

Следовательно, для того чтобы приращения целевой функ-

ции были по возможности большими δ

необходимо выбирать из

условия

= min (π

- c

), j∈J

(3.13)

3). Замена векторов базиса

Значение переменной x

, которая становится базисной

(вводится в базис) равно x

= θ. Однако в опорном решении может

быть только m отличных от 0 переменных, и если x

становится

равной θ, то одна из базисных переменных должна стать равной

0, или некоторый r-ый вектор базиса S должен быть выведен из

него. Возникает вопрос - какой из векторов базиса следует вывес-

ти из базиса для того, чтобы на его место ввести вектор a

Пусть из базиса выводится некоторый r-ый вектор, r = 1,...,

m. Следовательно, r-я компонента вектора x

(θ) должна стать

равной 0.

В целом новое опорное решение определяется как

′

= x

- θ æ

, i = 1,..,m, i ≠ r,

(θ) = (3.14)

′

= θ

⎪

⎩

⎪

⎨

⎧

Отметим, что если ∀æ

< 0, то θ, а, следовательно, и зна-

чение целевой функции L и компоненты x

могут принимать лю-

бые сколь угодно большие значения. Таким образом, если все

< 0, то целевая функция может неограниченно возрастать на

множестве допустимых решений задачи линейного программиро-

вания. Следовательно, оптимального решения не существует.

Все компоненты x

должны быть больше 0, т.е.

′

= x

- θ æ

> 0, i = 1,..,m,

Это выполняется, если выбирать θ из условия

θ = m i n ⎯ , i = 1,..,m,

>0 æ

причем по тем компонентам æ

, которые больше 0; æ

> 0.

Тогда из базиса выводится вектор с номером r, который

определяется из условия:

= m i n ⎯ , i = 1,..,m. (3.15)

>0 æ

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

′

= J

∪ {k} \ J

(r) (3.16)

Здесь J

(r) - номер переменной находящейся на r-ой позиции в

базисе.

3.5. Алгоритмы линейного программирования.

Симплекс-метод

Алгоритмы решения задачи линейного программирования

можно разбить на два класса. Алгоритмы первого класса основы-

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

за конечное число шагов. Алгоритмы второго класса основывают-

ся на итеративных методах, позволяющих получить приближен-

ное решение задачи и связанных с проведением достаточно

большого числа итераций. При этом качество

приближения суще-

ственно зависит от числа проведенных итераций.

Конечные методы решения задач линейного программиро-

вания можно разделить на следующие три группы [87]:

1. Методы последовательного улучшения решений, обес-

печивающие получение оптимального решения задачи при дви-

жении по планам прямой задачи.

2. Методы последовательного уточнения оценок, в которых

оптимальное решение достигается при движении по планам

двойственной (сопряженной) задачи.

3. Методы последовательного сокращения невязок, в кото-

рых используются обе задачи двойственной пары.

В настоящее время методы второй и третьей группы ис-

пользуются в специальных приложениях (целочисленное про-

граммирование, приближенное решение задач и др.), в

то время

как практические алгоритмы решения общей задачи линейного

программирования строятся на основе методов первой группы,

причем в методах первой группы различают: табличный метод и

метод обратной матрицы. Различают модификации метода об-

ратной матрицы: метод с мультипликативным представлением

обратной матрицы (мультипликативный алгоритм) и метод с тре-

угольным (верхним и нижним)

разложением обратной матрицы.

Первоначально симплекс-методом назывался именно таб-

личный метод, в то время как метод обратной матрицы называл-

ся модифицированным симплекс-методом или вторым алгорит-

мом симплекс-метода. Вместе с тем метод обратной матрицы по

сравнению с табличным характеризуется меньшим объемом вы-

числений, более компактным представлением необходимых для

решения задачи

данных, возможностью получения наряду с ре-

шением прямой задачи решения двойственной задачи. Именно

поэтому реальные алгоритмы линейного программирования

строятся на основе этого метода, и он обладает большим числом

различных модификаций. В дальнейшем, говоря о симплекс-

методе, будем иметь в виду именно метод обратной матрицы.

Так как решение задачи линейного программирования

со-

ответствует вершине многогранника, оно определяется опорным

базисом J

и соответствующей ему матрицей опорного базиса S.

Тогда оптимальное решение может быть найдено перебором

различных квадратных подматриц S матрицы А и проверкой ус-

ловий, которым должна удовлетворять матрица опорного базиса:

- det S ≠ 0;

- x

= S

-1

b ≥ 0.

Всего количество таких матриц S, которые таким образом

можно составить, не превышает числа сочетаний C

(здесь m и n

размерность матрицы условий A). Каждой матрице S соответст-

вует свое решение x

и значение целевой функции L(x

). Сравни-

вая значения L(x

), можно выявить решение x

с наибольшим

значением целевой функции L(x

Симплекс-метод осуществляет направленный перебор та-

ких матриц S, соответствующих вершинам многогранника реше-

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

значения целевой функции. Так как число вершин многогранника

решений конечно, то за конечное число шагов достигается опти-

мальное решение x

(L(x

) = max) или устанавливается неразре-

шимость задачи.

Алгоритм симплекс-метода

Алгоритм представляет собой определенную итеративную

последовательность действий, связанную с нахождением опти-

мального решения. В соответствии с этим на каждой итерации

выполняется три шага:

♦ анализ оптимальности текущего решения; нахождение век-

тора, вводимого в базис;

♦ установление неразрешимости задачи; нахождение вектора,

выводимого из базиса;

♦ преобразование базиса.

Все данные, необходимые для проведения

расчетов на ка-

ждой итерации, целесообразно представлять в форме таблицы

следующего вида:

Таблица 1.

..…… π

s1 x

…… s

s2 x

…… s

…. …. ……………… …. ….

…. …. S

-1

…. ….

…. …. ……………… …. ….

sm x

..… s

Часть таблицы, обведенную двойной линией, называют

о с н о в н о й ч а с т ь ю таблицы 1.

Предположение.

Пусть имеется некоторое опорное решение. Тогда известны

- J

= {s1, s2,..., sm} множество номеров векторов условий ба-

зиса;

- S = ║a

,….., a

║ = ║a

, j∈J

║ - матрица базиса; соот-

ветственно известны элементы матрицы S

-1

= ║s

║;

- x

= S

-1

b, такое, что x

≥ 0;

- π

= c

-1

;

- L(x

) = c

Таким образом, если известно опорное решение, то можно за-

полнить основную часть таблицы 1.

1. Анализ оптимальности текущего решения; нахож-

дение вектора, вводимого в базис

В соответствии с (3.13) рассчитывается оценка

= min ( π

- c

), j = 1,...,m.

Если δ

≥ 0 - счет окончен. Текущее опорное решение оптималь-

но.

Если δ

< 0 - вектор условий a

целесообразно ввести в базис -

производится заполнение крайнего правого столб-

ца таблицы 1.

2. Установление неразрешимости задачи; нахождение

вектора, выводимого из базиса

Вектор a

приводится к текущему базису - находится вектор

= S

-1

. Заполняется второй справа столбец таблицы 1.

Если æ

≤ 0, i=1,...,m - задача не имеет решений (целевая

функция может неограниченно возрастать множестве допустимых

решений). Счет окончен.

Если ∃æ

> 0, i=1,...,m , то производится вычисление оценки

по формуле (3.15):

= m i n ⎯ , i = 1,..,m.

>0 æ

Вектор условий, соответствующий r-ой позиции базиса сле-

дует вывести из базиса.

3. Преобразование базиса

Итак, r-ый вектор базиса меняется на k-ый вектор условий.

Тогда новый базис J

′

= J

∪ {k} \ J

(r), изменяется крайний слева

столбец таблицы 1.

Неизменной осталась основная часть таблицы, (обведен-

ная двойной линией) она изменяется в соответствии с формула-

ми:

s′

= ⎯ , j = 0,…, m, (3.16)

s′

= s

- s′

, i = 0,…, m, j = 0,…, m, (3.17)

Таким образом, вначале преобразуется r-я строка основной

таблицы, а затем все остальные. За конечное число шагов, за-

ключающихся в выполнении пунктов 1-3, находится оптимальное

решение или устанавливается неразрешимость задачи (неогра-

ниченность целевой функции на множестве допустимых реше-

ний).

Отметим, что алгоритм рассматривался в предположении,

что существует некоторое исходное опорное решение, и

оно из-

вестно (следовательно, Δ ≠ ∅)

3.6. Построение исходного опорного решения

При рассмотрении алгоритма симплекс-метода вводилось

предположение о том, что известно некоторое опорное решение.

Вместе с тем задача поиска такого решения является достаточно

не тривиальной. Рассмотрим несколько способов построения ис-

ходного опорного решения.

Задачи с "очевидным" исходным опорным решением

В ряде случаев задача линейного программирования обла-

дает такими особенностями, что исходное опорное решение мо-

жет быть найдено, вследствие предварительного анализа задачи.

Напомним, что к опорному решению и опорному базису (в том

числе и к исходному) предъявляется два требования:

1. Матрица S, составленная из векторов базиса S = ║a

,..., a

║ = ║a

, j∈J

║ является неособенной (det S ≠ 0).

2. Компоненты вектора базисных переменных больше 0; x

≥.0,

= S

-1

b).

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

дартной постановке

x → max,

A x ≤ b,

x ≥ 0.

При сведении такой задачи к канонической форме вводятся

дополнительные переменные, и задача приобретает вид

x + 0

→ max,

A x + E x

= b,

x ≥ 0, x

≥ 0.

Здесь x

- дополнительные переменные; E - единичная

матрица.

В качестве исходного опорного решения такой задачи мож-

но выбрать дополнительные переменные, т.е.

- J

={s1, s2,..., sm}= {n+1, n+2,..., n+m};

- S = ║e

,…, e

║, здесь e

- j-ый вектор матрицы E;

- x

= x

= S

-1

b = b;

- π

= 0

-1

= 0

;

- L(x

) = 0

= 0.

Говорят, что задача линейного программирования в стан-

дартной постановке имеет о ч е в и д н о е опорное решение.

Построение исходного опорного решения на основе

вспомогательной задачи

Более общей формой задач линейного программирования

является каноническая форма. Здесь для нахождения исходного

опорного решения может быть использована вспомогательная

задача, которая ставится в виде

-1

→ max, (3.18)

A x + E x

= b, (3.19)

x ≥ 0, x

≥ 0. (3.20)

или

- x

n+1

- ,…., - x

n+m

→ max

+ … + a

+ x

n+1

= b

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

+ … + a

+ . . . . . . . + x

n+m

= b

≥ 0, j = 1,…, n+m

Такая задача имеет очевидное исходное опорное решение:

- J

= {n+1, n+2,..., n+m };

- S = ║e

,…, e

║ = E;

- x

= S

-1

b = b;

- π

= -1

-1

= -1

= (-1,...,-1);

- L(x

) = -1

= - Σb

Поскольку целевая функция ограничена сверху на множе-

стве решений такой вспомогательной задачи (L(x) ≤ 0), то итера-

тивный процесс симплекс-метода через конечное число шагов

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

возможны два случая:

1) оптимальное значение целевой функции L

< 0;

2) оптимальное значение целевой функции L

= 0.

Рассмотрим эти случаи.

Случай 1. При L* < 0 исходная задача линейного програм-

мирования не имеет ни одного допустимого решения, то есть сис-

тема ограничений исходной задачи несовместна (Δ = ∅).

Если допустить противное и принять, что исходная задача

имеет хотя бы одно допустимое решение, то вспомогательная

задача будет иметь решение, у которого первые (n) переменных

(основных переменных) совпадают с

решением исходной задачи,

а остальные (m) переменных (дополнительных переменных) рав-

ны 0. Следовательно, оптимальное значение целевой функции

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

дополнительные переменные (см. 3.18) L

= 0, а это противоречит

исходному предположению случая 1, по которому L

< 0.

Случай 2. (L

= 0). Здесь оптимальное решение вспомога-

тельной задачи является опорным решением исходной задачи.

Возможны ситуации, когда полученное опорное решение

содержит дополнительные переменные вспомогательной задачи

(значения этих переменных, естественно, равны 0).

Рассмотрим эти ситуации более подробно.

Известно, что ранг матрицы условий задачи линейного про-

граммирования не превышает числа ограничений. Т.е. возможны

две ситуации

а) r = rang A = m;

б) r = rang A < m.

В ситуации а) дополнительные переменные вспомогательной

задачи можно заменить на основные переменные.

В ситуации б) (m-r) ограничений задачи линейного программи-

рования являются линейной комбинацией остальных r ограниче-

ний и, следовательно, эти (m-r) ограничений можно исключить,

сократив, таким образом, размерность задачи.

Квалифицировать ситуацию (а или б) можно следующим

образом.

1). Определяются компоненты разложения

векторов усло-

вий исходной задачи по оптимальному базису вспомогательной

задачи, соответствующие дополнительным переменным. Пусть