Геометрическая интерпретация симплексного метода

На основании материала, рассмотренного выше, сделаем следующие выводы.

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

2) Существует такая угловая точка многогранника решений, в которой линейная функция достигает своего наименьшего (наибольшего) значения.

3) Каждой угловой точке многогранника решений соответствует опорный план, каждый из которых определяется системой m линейно независимых векторов, содержащихся в данной системе из n векторов A₁,A₂,...,A_n.

Напомню, что опорным планом называется допустимое (если оно содержит лишь неотрицательные компоненты) базисное решение, т.е. если векторы A_i (i=1,2,..., m), входящие в разложение A₁x₁+A₂x₂+…+A_nx_n = B с положительными коэффициентами x_i, являются линейно независимыми.

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

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

Такой перебор позволяет сократить число шагов при отыскании оптимума. Поясним это на графическом примере. Пусть область допустимых решений изображается многоуголь­ником ABCDEGH. Предположим, что его угловая точка А соответствует исходному допустимому базисному решению. При беспорядочном переборе пришлось бы испытать 7 допустимых базисных решений, соответствующих семи угловым точкам мно­гоугольника. Однако из чертежа видно, что после вершины А выгодно перейти к вершине В, а затем - к оптимальной точке С, т.е. перебрать только три вершины.

Схема, позволяющая осуществлять упорядоченный переход от одного опорного плана к другому, т.е. исходя из известного опорного плана задачи, за конечное число шагов получить ее оптимальный план, легла в основу универсального метода решения ЗЛП —симплексного метода. Если исходная задача не имеет такого плана или ее линейная функция не ограничена на многограннике решений, то симплексный метод позволяет установить это в процессе решения. Название метода произошло от понятия ''симплекс" (лат. simplex - простой) - простейший выпуклый много­гранник в n-мерном пространстве с n+1 вершиной (например, тетраэдр в 3-мерном пространстве).

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

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

• способ определения какого-либо первоначального опорного плана задачи;

• правило перехода от одного опорного плана к другому, на котором значение целевой функции ближе к оптимальному;

• критерий проверки оптимальности найденного плана, позволяющий своевременно прекратить перебор решений на оптимальном решении или сделать заключение об отсутствии решения.

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

Рассмотрим следующую ЗЛП.

Найти максимум целевой функции L=С₀+ ® max

при ограничениях где x_j ³ 0 (j=1,2,…,n), b_i ³ 0 (i=1,2,…m; m£n).

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

Предположим, для определенности, что система ограничений задачи содержит т единичных векторов, причем без ограничения общности можно по­ложить, что единичными являются первые т векторов, и, следовательно, переменные, которые выражены через остальные, - это x₁,x₂,...,x_m, т.е. система ограничений имеет вид:

(1)

где x₁ ³ 0, x₂ ³ 0, ... , x_n ³ 0. (2)

Далее приведем систему к следующему виду

(3),

где все свободные члены b_i ³ 0, (i=1,2,...,m).

Переменные x₁,x₂,...,x_m, находящиеся в левой части системы (3), называются базисными, а весь набор {x₁,x₂,...,x_m} - базисом; остальные переменные называются небазисными или свободными. Т.о. мы выразили базисные переменные через свободные.

2. Выражаем целевую функцию L через свободные переменные x_m+1,..., x_n, подставляя в L вместо базисных переменных их выражения через свободные из (3), и получаем первоначальный опорный план. Получим:

L=C₀’ + C¢_m+1x_m+1 + ... + C¢_nx_n. (4)

Т.к. все величины х_i (i=1,2,…,n) должны быть неотрицательны, то наименьшие возможные значения свободных переменных - это значения, равные нулю. Положим все свободные переменные равными нулю: x_m+1 = 0, ... , x_n = 0

и найдем из системы (3) значения базисных переменных:

x₁ = b₁, x₂ = b₂, ... , x_m = b_m.

Получим первоначальное базисное решение (опорный план) системы, отвечающее базису x₁,x₂,...,x_m:

X = (b₁, b₂,..., b_m,0, ... , 0).

Оно будет вследствие (2) допустимым, а т.к. векторы, соответствующие базисным переменным, линейно независимы, то и опорным. Т. е. получим первоначальный опорный план. Геометрически данный план соответствует первоначальной угловой точке.

Подставим в максимизируемую целевую функцию L из (4) значения свободных переменных. Т.к. x_m+1 = 0, ... , x_n = 0, то L_б = C₀.

Посмотрим, можем ли мы улучшить решение, т.е. увеличить целевую функцию L, увеличивая какие-нибудь из переменных x_m+1, ... , x_n (уменьшать их мы не можем, т.к. они все равны нулю, а отрицательные значения переменных недопустимы). Это можно осуществить, перейдя к такому новому допустимому решению, в котором эта переменная будет базисной, а не равняться 0 как свободная.

Если оказалось, что все коэффициенты C¢_m+1,...,C¢_n в (4) отрицательны, то, увеличивая какие-то из переменных x_m+1,..., x_n сверх нуля, мы не можем увеличить L; значит, найденное нами базисное решение X=(b₁,b₂,..., b_m,0,...,0) оптимально.

3. Пусть среди коэффициентов, упомянутых в предыдущем пункте, т.е. среди чисел C¢_m+1,..., C¢_n имеются положительные, то увеличивая те из переменных x_m+1, ... , x_n, коэффициенты при которых положительны, мы можем улучшить решение, т.е. увеличить L.

Для определенности в такой ситуации будем выбирать переменную, имеющую больший коэффициент. Пусть, например, это будет коэффициент C¢_m+1 в формуле (4) при x_m+1. Значит есть смысл увеличивать x_m+1, т.е. перейти от данного опорного решения к другому, где переменная x_m+1 ¹ 0, а вместо нее равна нулю какая-то другая. При таком переходе геометрически произойдет переход к соседней вершине многоугольника, где значение линейной функции лучше.

Однако увеличивать x_m+1 надо осторожно, так чтобы не стали отрицательными другие переменные x₁,x₂,...,x_m, выраженные через свободные переменные, в частности через x_m+1 формулами (3). Таким образом, должны выполняться следующие неравенства (при этом х_m+2=0, х_m+3=0,…, х_n=0, как свободные переменные):

(5) откуда

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

Очевидно, что сохранение неотрицательности всех переменных (допустимость решения) возможно, если не нарушается ни одна из полученных во всех уравнениях границ. Ясно, что если мы оставим остальные свободные переменные x_m+2=0,...,x_n=0, то x _m+1 мы можем увеличивать только до значения, равного b¢_i/ a¢_i,m+1(i=1,2,…,m), а при дальнейшем увеличении x_m+1 переменная x_j станет отрицательной.

Каждое уравнение системы ограничений определяет конечное или бесконечное наибольшее возможное значение этой переменной – оценочное отношение.

Уравнение, где достигается наибольшее возможное значение переменной, переводимой в базисные (т.е. где оценка минимальна), называется разрешающим. Его выделяем рамкой.

Встречаются различные случаи оценки роста свободной переменной, которые зависят от знаков и значений свободного члена и коэффициента при свободной переменной x_i (i=1,2,…,m). Сформулируем все возможные случаи. Обозначим: x_m+1 – переводимая свободная переменная, b’_i - свободный член, a’_im+1 – коэффициент при x_m+1. В общем виде уравнение x_i = a¢_i,m+1x_m+1 + …+a¢_i,nx_n + b¢_i определяет наибольшее возможное значение x_m+1 по следующим правилам.

Здесь, в свою очередь, могут представиться следующие случаи.

1) x_m+1=|b¢_i/a¢_im+1|, если b¢_i и a¢_im+1 разного знака и b¢_I ¹ 0 и a¢_im+1 ¹ 0.

x_m+1 мы можем увеличивать только до значения, равного b¢_i/ a¢_{i m+1}, а при дальнейшем увеличении x_m+1 переменная x_j станет отрицательной.

Например: x₃ = 8-2x₂ + ...; x₂ = 8/2=4 или x₃ = -8+2x₂ + ...; x₂ =8/2=4.

2) x_m+1=µ, если b¢_i и a¢_{i m+1} одного знака и неравны 0.

Например: x₃ = 8+2x₂ + ...; x₂ = µ.

3) x_m+1=0, если b¢_i =0 и a¢_{i m+1}<0.

Например: x₃ = 0-2x₂ + ...; x₂ = 0.

4) x_m+1=µ, если b¢_i =0 и a¢_{i m+1}>0.

Например: x₃ = 0+2x₂ + ...; x₂ = µ.

5) x_m+1=µ, если a¢_{i m+1}=0.

Например: x₃ = 5+0x₂ + ...; x₂ = µ или x₃ = -5+0x₂ + ...; x₂ = µ .

Если во всех уравнениях (5) оценочное отношение x_m+1=µ, то max L = ¥ - задача решения не имеет.

Очевидно, что сохранение неотрицательности всех переменных (допустимость решения) возможно, если не нарушается ни одна из полученных во всех уравнениях границ. Поэтому выберем ту из переменных x₁,x₂,...,x_m, которая раньше всех обратится в нуль при увеличении x_m+1, т.е. ту, для которой величина b¢_i/ a¢_i,m+1 меньше всего.

Для этого найдем среди всех отношений (i=1,2,…,m) наименьшее; пусть это будет , k£m. Т. о., = min по всем i. Число a_k,m+1 называется разрешающим элементом. Обозначим указанный минимум через r= . Если он достигается сразу при нескольких значениях i, то в качестве k берем любое из них. Очевидно,r ³ 0. Ясно, что теперь x_m+1 можно увеличить до r (и не более, иначе x_i станет < 0). Пусть такая «наиболее угрожаемая» переменная будет x_k. Тогда имеет смысл «переразрешить» систему уравнений (3) относительно других базисных переменных, выведя из числа свободных переменных x_m+1 и переведя вместо нее в группу свободных переменных x_k.

Т.о., на каждом шаге симплексного метода какая-либо свободная переменная переводится в базисные, при этом каждое уравнение системы ограничений определяет конечное или бесконечное наибольшее возможное значение этой переменной – оценочное отношение.

4. Переходим к новому базису, исключая из старого базиса x_m+1 и вводя вместо него x_k. Новыми базисными переменными при этом будут x₁,x₂,...,x_k-1,x_k+1,...,x_m,x_m+1; новые свободные переменные x_k,x_m+2,..., x_n.

Первое опорное решение мы получили, положив равными нулю все прежние свободные переменные x_m+1, ... , x_n; второе мы получим, если обратим в нуль все новые свободные переменные x_k, x_m+2 ,..., x_n.

Нам остается лишь переписать систему (3) и целевую функцию (4) применительно к новому базису.

Выразим новые базисные переменные через новые свободные, начиная с разрешающего уравнения. Для этой цели уравнение, содержащее x_k, разрешаем относительно x_m+1 (пользуясь тем, что a_im+1 ¹ 0) и полученное таким путем выражение для x_m+1 подставляем во все остальные уравнения системы ограничений.

Из выражения для x_k (новой свободной переменной) в системе (3) находим x_m+1 (новое базисное неизвестное):

x_{m+1 =} - ( x_k + x_m+2 + ... + x_n)

и подставляем это выражение вместо x_m+1 в остальные уравнения. В результате система окажется разрешенной относительно нового базиса:

(6)

Полагая x_k =0, x_m+2 = 0, ..., x_n = 0, (7)

найдем значения остальных переменных: (8) .

Теперь новый базис Б¢ состоит из неизвестных x₁,..., x_k-1, x_k+1,..., x_m, x_m+1; соответствующее базисное решение (опорный план) есть (7), (8). Следовательно, в геометрической интерпретации перешли к новой вершине.

Наконец, к системе (6) добавляем новое выражение для целевой функции L (запись L через новые небазисные переменные):

L_Б¢ = C’’₀ - (C’’_kx_k +C’’_m+1x_m+1 + ... + C’’_nx_n) ³ L_Б. (9)

На этом заканчивается первый шаг процесса.

5. Далее возвращаемся к выполнению пункта 3 (но уже в новом базисе).

Затем все рассуждения повторяются. Именно, если все коэффициенты при переменных в этой функции отрицательны, т.е. коэффициенты C’’_k, C’’_m+1, ... , C’’_n в (9) отрицательны, то нашли оптимальное решение: оно получится, если все свободные переменные положить равными нулю. Полученное базисное решение (7), (8) является оптимальным, и задача решена.

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

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

При определении минимума линейной функции Z возможны два пути:

1) отыскать максимум функции F, полагая F= -Z и учитывая, что Z_min=-F_max;

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

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

Можно сказать, что изложенный выше метод решения ЗЛП заключается в переходе от одного допустимого базисного решения (опорного плана) к другому. Однако каждый такой переход совершается не произвольно, а сопровождается увеличением (или уменьшением) максимизируемой (минимизируемой) формы. В этом приеме и состоит суть симплекс-метода. Сформулируем теперь теорему, оправдывающую применение симплекс-метода.

Теорема. Пусть дана некоторая ЗЛП в канонической форме. Предположим, что эта ЗЛП имеет оптимальное решение. Тогда существует по крайней мере одно оптимальное базисное решение, которое может быть получено симплекс-процессом из любого базисного решения.