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

Лекция 2. Симплексный метод решения задачи линейного программирования Если задача линейного программирования имеет решение, то существует такая угловая точка области допустимых решений, в которой функция цели принимает оптимальное значение. Каждой угловой точке области допустимых решений соответствует опорный план, который определяется системой m линейно независимых векторов, содержащихся в данной системе из n векторов А1, А2,…, Аn. Так как система ограничений задачи линейного программирования содержит m уравнений и n переменных, то количество угловых точек равно числу сочетаний Cnm=n!/[m!(n-m)!]. При больших m и n перебрать все угловые точки очень трудно. Поэтому необходимо иметь процедуру, позволяющую осуществлять направленный перебор угловых точек, т.е. такой перебор, при котором значение целевой функции в следующей угловой точке будет ближе к оптимальному, чем в предыдущей. Таким образом, на каждом шаге исключаются из рассмотрения те угловые точки, в которых не улучшается значение функции цели. Такой процедурой является симплексный метод, который позволяет, исходя из начального опорного плана задачи, за конечное число шагов получить оптимальный план. Для решения задачи линейного программирования симплексным методом необходимо: 1. наличие первоначального опорного плана; 2. знание процедуры (алгоритма) перехода от одного опорного плана к другому; 3. знание условий оптимальности, позволяющих ответить на вопрос: является ли данный опорный план оптимальным или необходимо перейти к следующему опорному плану. 2.1.Построение опорных планов задачи линейного программирования. Рассмотрим задачу линейного программирования, заданную в стандартной форме (2.1) – (2.3). Предположим, что система ограничений линейно независима. Тогда все допустимые угловые точки определяются как все однозначные неотрицательные решения системы m уравнений, в которых n-m переменных равны нулю. Будем считать, что свободные члены bi  0 (i = 1, 2,…, m) и система ограничений содержит m единичных векторов (т.е. содержит единичный базис). Без ограничения общности, будем считать, что единичными являются первые m векторов. Тогда задача линейного программирования принимает вид: Z = c1x1 + c2x2 + … + cnxn  extr (2.1) x1 + a1,m+1xm+1 + … + a1nxn = b1 x2 + a2,m+1xm+1 + … + a2nxn = b2 ………...…………………… (2.2) xm + am,m+1xm+1 + … + amnxn = bm xj  0; j = 1, 2,…, n (2.3) Переменные, коэффициенты при которых образуют в системе ограничений единичный базис, называются базисными (в нашем случае это переменные x1, x2,…, xm), остальные – небазисными. Задача (2.1) – (2.3) является задачей линейного программирования, заданной в канонической форме. Отметим, что каноническая форма записи отличается от стандартной тем, что в ней свободные члены неотрицательны (bi  0; i = 1, 2,…, m) и система ограничений содержит единичный базис (т.е. в каждом уравнении имеется переменная с коэффициентом 1 в этом уравнении и нулевыми коэффициентами во всех остальных уравнениях). Запишем систему ограничений (2.2) в векторной форме: x1A1 + x2A2 + … + xmAm + xm+1Am+1 + … + xnAn = B, (2.4)  a1, m 1  1 0 0  a1n   b1               a 2 , m 1   a2n   b2  0 1 0 где А1=   , А2=   ,…, Аm=   , Am+1=  ,…, A = , B = n      .                  a  b  0 0 1 a   mn   m        m , m 1  Векторы А1, А2,…, Аm – линейно независимые единичные векторы m-мерного векторного пространства. Они и образуют базис этого пространства. Выбирая за базисные неизвестные x1, x2,…, xm полагая свободные неизвестные xm+1, xm+2, …, xn равными нулю и учитывая, что bi  0; i = 1, 2, …, m, получаем первоначальный опорный план X0 = (x1 = b1; x2 = b2; xm = bm; xm+1 = 0, xn = 0) (2.5) Плану (2.5) соответствует разложение: x1A1 + x2A2 + … + xmAm = B (2.6) Итак, для того, чтобы задача линейного программирования имела первоначальный опорный план необходимо, чтобы ее система ограничений удовлетворяла следующим условиям: 1. она должна быть записана в виде уравнений; 2.содержать единичный базис; 3.свободные члены должны быть неотрицательными (bi  0; i = 1, 2,…, m). Рассмотрим теперь процедуру перехода от первоначального опорного плана (3.5) к следующему опорному плану. Векторы А1, А2,…, Аm образуют базис в m – мерном пространстве. Поэтому любой из n векторов, входящих в равенство (2.4) можно разложить по векторам базиса и притом единственным образом. Предположим, что для некоторого вектора Аj не входящего в базис, положителен хотя бы один из коэффициентов aij в разложении a1jA1 + a2jA2 + … + amjAm = Aj (2.7) Зададим некоторую (пока неизвестную) положительную величину  ( > 0), умножим на нее обе части равенства (2.7) и полученный результат вычтем почленно из равенства (2.6). В результате получим: (x1 – a1j)A1 + (x2 – a2j)A2 + … + (xm – amj)Am + Aj = B (2.8) Таким образом, вектор Х1 = (x1 – a1j; x2 – a2j;…, xm – amj; 0;…, ;…, 0) является планом, если его компоненты неотрицательны. Так как xi  0; (i = 1, 2,…, n),  > 0, то все величины (xi – aij), являющиеся компонентами вектора Х1, в которые входят неположительные коэффициенты aij, будут неотрицательными. Поэтому надо рассмотреть только компоненты, включающие положительные коэффициенты aij (i = 1, 2,…, m), т.е. необходимо определить такое  > 0, при котором для всех aij > 0 имеет место условие: xi – aij  0 (2.9) Из (2.9) имеем:   xi/aij для всех aij > 0. Возьмем 0 = min xi/aij; aij > 0 (2.10) Для того чтобы новый план был опорным, т.е. содержал ровно m положительных координат, необходимо положить  = 0, тогда одна из координат плана Х1 (для которой достигается минимум) будет обращена в нуль. Таким образом, для построения следующего опорного плана, необходимо любой вектор, не входящий в базис А1, А2,…, Аm разложить по векторам этого базиса (причем требуется, чтобы среди коэффициентов разложения были положительные). Затем, по формуле (3.10) определяется такое 0 > 0, при котором исключается один из векторов этого базиса. Заметим, что если вектор Аj подлежит включению в базис, а в его разложении (2.7) все коэффициенты aij  0, то нельзя выбрать такое  > 0, которое обнуляло бы одну из координат вектора Х1. В этом случае план Х1 будет содержать (m + 1) положительных компонент и он определяет не угловую, а внутреннюю точку области допустимых решений. Это означает, что гиперплоскость, соответствующая линейной функции цели, не может стать опорной к области допустимых решений, как бы далеко ее не перемещать в направлении градиента (при поиске максимума) или антиградиента (при поиске минимума), т.е. функция цели не ограничена на области допустимых решений. Итак: Если среди коэффициентов разложения вектора Аj, вводимого в базис отсутствуют положительные числа, то задача линейного программирования не имеет решения из-за неограниченности функции цели. 2.2. Отыскание оптимального плана задачи линейного программирования. Условия оптимальности. Зная теперь условия, которым должна удовлетворять задача линейного программирования, для того, чтобы она имела первоначальный опорный план и процедуру перехода от одного опорного плана к другому, остается выяснить условия оптимальности. Предположим, что область допустимых решений задачи линейного программирования (2.1) – (2.3) не пуста и каждый ее опорный план не вырожден. В этом случае для опорного плана (2.5) имеем: x1A1 + x2A2 + … + xmAm = B, (2.6) а соответствующее ему значение целевой функции определяется равенством: x1c1 + x2c2 + … + xmcm = Z(X0) (23.11) Единственному разложению (2.7) вектора Aj по векторам базиса соответствует единственное значение функции цели: a1jc1 + a2jc2 + … + amjcm = Zj (2.12) Zj – значение целевой функции, если в нее вместо неизвестных подставить соответствующие коэффициенты разложения вектора Aj по векторам базиса. Теорема (Условия оптимальности). Если задача линейного программирования решается на отыскание минимума, то план Х0 будет оптимальным, если выполнены условия: Zj – Cj  0; j = 1, 2,…, n. Если хотя бы одна оценка Zj – Cj > 0, то план не оптимален и его можно улучшить. Если же задача линейного программирования решается на отыскание максимума, то план Х0 будет оптимальным, если Zj – Cj  0;  j = 1, 2,…, n. Если хотя бы одна оценка Zj – Cj< 0, то план не оптимален, и его можно улучшить. Доказательство: Запишем равенство (2.8) (напомним, что оно было получено в результате вычитания из равенства (2.6) равенства (2.7), предварительно умноженного на величину  >0): (x1 – a1j)A1 + (x2 – a2j)A2 + … + (xm – amj)Am + Aj = B (2.8) Умножим теперь выражение (2.12) на  > 0 и вычтем полученный результат из (2.11): (x1 – a1j)c1 + (x2 – a2j)c2 + … + (xm – amj)cm = Z(X0) – Zj. Прибавив к обеим частям полученного равенства величину сj, получим: (x1 – a1j)c1 + (x2 – a2j)c2 + … + (xm – amj)cm + cj = Z(X0) – (Zj – Cj) (2.13) Как было показано ранее, выбирая  в соответствии с формулой (2.10), мы получаем новый опорный план X1 = (x1 – a1j; x2 – a2j;…, xm – amj; 0;…, ;…, 0), которому согласно равенству (2.13) соответствует значение функции цели Z (X1) = Z(X0) – (Zj – Cj) Если ищется минимум функции цели (2.14) (3.1) задачи линейного программирования (2.1) – (2.3), то при выполнении условий Zj – Cj  0; j = 1, 2, …, n, имеем: (Zj – Cj)  0 (т.к.  > 0) и на основе равенства (2.14) Z(X0) – Z(X1) = (Zj – Cj)  0, т.е. Z(X0)  Z(X1); X1 D, (2.15) где D – область допустимых решений. Действительно, разложение (2.7) имеет место для любого вектора Aj не входящего в базис. Перебрав все Aj, мы увидим, что условие (3.15) имеет место для любого плана X1D, а это и означает, что в точке Х0 целевая функция принимает минимальное значение. Если же для какого – либо j выполнено условие Zj – Cj > 0, то из (2.14) имеем: Z(X1) = Z(X0) – (Zj – Cj) < Z(X0), т.е. Х0 – не оптимальный план и его можно улучшить (по крайней мере, значение функции цели в точке Х 1 ближе к оптимальному, чем в точке Х0). Аналогично, если задача решается на максимум, то при выполнении условий Zj – Cj  0 (j = 1, 2,…, n) получим: (Zj – Cj)  0 и из (2.14) имеем: Z(X0) – Z(X1) = (Zj – Cj)  0, т.е. Z(X0)  Z(X1) для любого Х1D, (2.16) т.е. Х0 – оптимальный план. Если же для некоторого j выполнено условие Zj – Cj < 0, то из (2.14) имеем: Z(X1) = Z(X0) – (Zj – Cj) > Z(X0), т.е. Х0 не оптимальный план и его можно улучшить. Теорема доказана. Итак, если задача линейного программирования решается на минимум, то условиями оптимальности будут: Zj – Cj  0; j = 1, 2,…, n, (2.17) Если же – на максимум, то Zj – Cj  0; j = 1, 2,…, n (2.18) Значения Zj – Cj называются оценками плана. Таким образом, для того, чтобы план задачи линейного программирования на отыскание минимального значения функции цели был оптимальным, необходимо и достаточно, чтобы все его оценки были неположительными, а для того, чтобы план задачи линейного программирования на отыскание максимального значения функции цели был оптимальным, необходимо и достаточно, чтобы его оценки были неотрицательными. Как следует из равенства (2.12), для любого вектора Aj, входящего в базис, Zj = Cj и поэтому его оценка Zj – Cj = 0. 2.3. Алгоритм симплексного метода. Рассмотрим решение задачи линейного программирования (2.1)(2.3). Пусть первоначальный опорный план этой задачи X0 = (x1 = b1; x2 = b2;…, xm = bm; xm+1 = 0;…, xn=0) (2.5) определяется системой m – мерных векторов А1, А2,…, Аm. Для исследования этого плана на оптимальность следует векторы Аj (j = 1, 2,…, n) разложить по векторам базиса и вычислить значения оценок Zj – Cj. Базис является единичным, поэтому коэффициентами разложения вектора Aj по векторам базиса служат его координаты. Дальнейшие вычисления будем производить, используя симплексную таблицу (табл.2.1.). Таблица 2.1. i Базис С B базиса 1 A1 c1 b1 c1 c2 … cm cm+1 … cn A1 A2 … Am Am+1 … An 1 … … a1, a1,m+1 n 2 A2 c2 b2 1 … a2,m+1 … a2, n … … … m Am cm … bm … … … … … … … … 1 am,m+1 … am n m+1 Zj - Cj Z0 … qm+1 … qn Столбец «i» введен для нумерации ограничений. В столбце «базис» помещаем векторы, образующие единичный базис, а в столбце «C базиса» – коэффициенты функции цели, соответствующие базисным переменным. В столбце «B» записываем первоначальный опорный план Х0, в нем же в результате вычислений получаем оптимальный план. В столбцах «Аj» (j=1,2,…,n) записываем коэффициенты разложения вектора Аj по векторам базиса. В (m + 1) – й строке в столбце В записываем значение функции цели Z(X0), а в столбцах Аj – значения оценок Zj – Cj. Значения Z(X0) и Zj можно получить как скалярные произведения m m i 1 i 1 Z ( X 0 )  Cá  X 0   ci  xi ; Z j   ci  aij , где сi – коэффициенты функции цели, соответствующие векторам базиса. Обозначим через qj величину Zj – Cj, т.е. qj = Zj – Cj, а через J – множество тех индексов j, для которых не выполнено условие оптимальности. Для задачи линейного программирования, решаемой на максимум, J = {j: Zj – Cj < 0}; для задачи, решаемой на минимум J = {j: Zj – Cj > 0}. После составления таблицы 2.1. просматриваем (m+1) – ю строку. Если для всех j = 1, 2,…, n оценки qj = Zj – Cj удовлетворяют условиям оптимальности, то опорный план Х0 является оптимальным и оптимальное значение целевой функции равно Z(X0). Если хотя бы одна из оценок qj не удовлетворяет условиям оптимальности, то план Х0 не является оптимальным и его можно улучшить, вводя в базис вектор, соответствующий этой оценке. Если таких оценок несколько, то, как следует из (2.14), в базис должен быть включен вектор, которому соответствует max | jqj | для всех jJ. Это позволяет на данном шаге перейти к угловой точке, связанной с наилучшим изменением целевой функции (т.е. с наибольшим возрастанием в задаче, решаемой на максимум и наибольшим убыванием в задаче, решаемой на минимум). Если хотя бы для одной оценки qj = Zj – Cj, не удовлетворяющей условию оптимальности все коэффициенты разложения aij  0, то задача линейного программирования не имеет решения из-за неограниченности функции цели. Пусть max  j q j  l ql jJ Тогда в базис включается вектор Аl и исключается вектор, которому соответствует l = min {xi/ail} для всех ail > 0. Пусть l = min{xi/ail} = xi/akl достигается для вектора базиса, стоящего в k – й строке; тогда вектор Аk исключается из базиса. Элемент akl, называется разрешающим, строка и столбец, на пересечении которых находится akl, называются соответственно разрешающей строкой и разрешающим столбцом. Новому опорному плану соответствует базис, состоящий из векторов A1, A2,…, Ak1, Al, Ak+1,…, Am. Чтобы вычислить новый опорный план и проверить его на оптимальность, необходимо все векторы Aj (j = 1, 2,…, n) и В разложить по векторам нового базиса. Разложение вектора Al по векторам базиса A1, A2,…, Am имеет вид: Al = a1lA1 + a2lA2 + … + aklAk + … + amlAm, (2.19) Ak = 1/akl (Al – a1lA1 – a2lA2 – … – amlAm) (2.20) откуда Подставляя (2.20) в (2.6), получим: x1A1 + x2A2 + … + xk/akl(Al – a1lA1 – a2lA2 – … – amlAm) + … + xmAm = B или (x1 – xka1l/akl)A1 + (x2 – xka2l/akl)A2 + … + (xk/akl)Al + … + (xm – xkaml/akl)Am=B Таким образом, новый опорный план вычисляется по формулам:   xk  ail   xi  xi   ; i  k a   kl    x  xk . k  akl  (2.21) Подставляя (2.20) в (2.7), получаем разложение вектора Aj по векторам нового базиса: a1jA1 + a2jA2 + … + akj/akl(Al – a1lA1 – a2lA2 – … – amlAm) + … + amjAm = Aj или (a1j – akja1l/akl)A1+(a2j – akja2l/akl)A2 + … + akj/aklAl +… + (amj – akjaml/akl)Am=Aj, т.е.   akj  ail aij  aij     akl  a  akj .  kj a  kl  ; i  k  (2.22) Объединяя формулы (2.21) и (2.22) видим, что новый опорный план и коэффициенты разложения векторов в новом базисе, являются формулами полных исключений Жордана-Гаусса. Если в новой симплексной таблице все оценки qj = Zj – Cj удовлетворяют условиям оптимальности, то полученный план является оптимальным, если же среди оценок qj имеются «нарушители», то строят следующий опорный план. Процесс продолжают до получения оптимального плана, либо до установления неограниченности целевой функции. Если среди оценок qj = Zj – Cj оптимального плана нулевыми являются только оценки, соответствующие базисным векторам, то это свидетельствует о единственности оптимального решения. Если же нулевая оценка соответствует вектору Ai, не входящему в базис, то оптимальных планов бесконечно много. Действительно, если qi = Zi – Ci = 0, то, включая вектор Ai в базис, получим новый опорный план, которому согласно (2.14) соответствует то же значение функции цели, что и в предыдущем оптимальном плане, т.е. целевая функция достигает оптимума в двух угловых точках области допустимых решений. Это же оптимальное значение достигается в любой точке, являющейся выпуклой линейной комбинацией этих угловых точек. Таким образом, в этом случае задача линейного программирования имеет бесконечное множество решений (обладает бесконечным множеством оптимальных планов). Пример 1: Решить симплексным методом задачу линейного программирования: Z = x1 + 2x2 + 3x3  max x1 + 2x2 + 3x3  15 2x1 + x2 + 5x3  20 x1 + 2x2 + x3 + x4 = 10 xj  0; j = 1, 2, 3, 4. Введя дополнительные переменные х5 и х6, приведем систему ограничений данной задачи к уравнениям: Z = x1 + 2x2 + 3x3  max x1 + 2x2 + 3x3 + x5 = 15 2x1 + x2 + 5x3 + x6 = 20 x1 + 2x2 + x3 + x4 = 10 xj  0; j =1, 2,…, 6. Полученная задача линейного программирования записана в каноническом виде (система ограничений задана в виде уравнений, содержит единичный базис и свободные члены неотрицательны), поэтому ее можно решать симплексным методом. Запишем систему ограничений в векторной форме: x1A1 +x2A2 + x3A3 + x4A4 + x5A5 + x6A6 = B Напомним, что вектор Ai – вектор, составленный из коэффициентов системы ограничений при переменной xi, т.е. 1  2  3 0 1 0  15                А1=  2  , А2=  1  , А3=  5  , А4=  0  , А5=  0  , А6=  1  , В=  20  1  2 1 1 0 0  10                Единичные векторы А5, А6, А4 выбираем за базис первоначального опорного плана, свободные неизвестные х1, х2 и х3 приравниваем нулю. В результате получаем первоначальный опорный план Х0 = (х1 = 0, х2 = 0, х3 = 0, х4 = 10, х5 = 15, х6 = 20). Строим первую симплексную таблицу. Таблица 2.2. i Базис С базиса 1 2 3 A1 A2 А3 A4 A5 А6 B 1 A5 15 1 2 3 1 2 A6 20 2 1 5 1 3 А4 10 1 2 1 1 –1 –2 –3 m+1 Zj – Cj Величина Z0 рассчитывается как сумма произведений элементов, стоящих в столбце «C базиса» на соответствующие элементы столбца “B”: Z0 = 015+020+010 = 0. Величина Zj рассчитывается как сумма произведений элементов столбца «C базиса» на соответствующие элементы столбца «Aj»: Z1 – C1 = 01 + 02 + 01 – 1 = – 1; Z2 – C2 = 02 + 01 + 02 – 2 = – 2; Z3 – C3 = 03 + 05 + 01 – 3 = – 3. Для векторов базиса оценки qj = Zj – Cj = 0. Данная задача решается на максимум, следовательно, оптимальный план не должен содержать отрицательных оценок qj . Из таблицы 3.2. видно, что условия оптимальности не выполнены. Первоначальный план можно улучшить, включив в базис вектор, которому соответствует max |jqj | (jJ); j = min (xi/aij) для всех aij > 0. Поэтому: 1 = min (15/1; 20/2; 10/1) = 10; | 1q1 | = | 1(Z1 – C1) | = 10; 2 = min(15/2; 20/1; 10/2) = 5; | 2q2 | = |2(Z2 – C2) | = 10; 3 = min(15/3; 20/5; 10/1) = 4; | 3q3 | = |3(Z3 – C3) | = 12, max| jqj | = max (10; 10; 12) = 12. Следовательно, разрешающим элементом будет число 5, стоящее на пересечении второй строки и столбца А3. Таким образом, необходимо вектор А3 включить в базис, а вектор А6 – исключить из базиса. Составляем вторую симплексную таблицу. Элементы разрешающей (в данном случае, второй) строки находятся в результате деления элементов второй строки предыдущей таблицы на разрешающий элемент (т.е. на 5). С помощью полученной строки произведем одно полное исключение Жордана – Гаусса, т.е. вновь полученную строку умножим на – 3 и сложим с первой строкой; умножим на – 1 и сложим с третьей строкой; умножим на 3 и сложим с (m+1) – й строкой. В результате получим таблицу 2.3. Ранее было отмечено, что преобразования Жордана-Гаусса позволяют все элементы симплексной таблицы можно условно разбить на три класса: 1. вектор – столбцы, соответствующие базису (являются единичными векторами); 2. коэффициенты разрешающей строки новой таблицы (находятся в результате деления соответствующих коэффициентов предыдущей (вычисляются по таблицы на разрешающий элемент); 3. все остальные элементы методу прямоугольника). Таким образом: 1. вектор – столбцы, соответствующие базису: 1   А5 =   , А3 =   0   0   1  0  , А4 =   0   0   0 1 ;   0   2. коэффициенты разрешающей строки новой таблицы: b2 = 20/5 = 4; a21 = 2/5; a22 = 1/5; a23 = 1; a24 =a25 = 0; a26=1/5. 3. все остальные элементы: b1 = (155 – 203)/5 = 3; a11 = (15 – 23)/5 = – 1/5; a12 = (25 – 13)/5 = 7/5; a16 = (05 – 13)/5 = – 3/5; b3 = (105 – 201)/5 = 6; a31 = (15 – 21)/5 = 3/5; a32 = (25 – 11)/5 = 9/5; a36 = (05 – 11)/5 = – 1/5; Z(X) = (05+ 203))/5 = 12; q1 = (– 15 + 13)/5 = 1/5; q2 = (– 25 + 13)/5 = – 7/5; q6 = (05 + 13)/5 = 3/5. Таблица 2.3 i Базис С базиса 1 2 3 A1 A2 A3 A4 A5 A6 B 1 A5 3 –1/5 7/5 1 –3/5 2 A3 3 4 2/5 1/5 1 3 A4 6 3/5 9/5 1 0 –1/5 12 1/5 –7/5 m+1 Zj - Cj 1/5 3/5 В таблице 2.3. получен второй опорный план Х1 = (х1 = 0; x2 = 0; x3=4; x4 = 6; x5 = 3;x6 = 0), которому соответствует значение функции цели Z(X1) = 12. Полученный план не является оптимальным, так как q2 = Z2 – C2 = – 7/5 < 0. Следовательно, вектор А2 необходимо включить в базис. 4 6   3 ; ;  =15/7. 7 / 5 1/ 5 9 / 5  2 = min  Число 7/5, стоящее на пересечении первой строки и столбца А2 будет разрешающим элементом. Из базиса исключается вектор А5. Вновь используя преобразования Жордана-Гаусса, переходим к третьей симплексной таблице (табл. 2.4.). Таблица 2.4 i Базис С базиса 1 2 3 A1 A2 A3 A4 A5 A6 B 1 A2 2 15/7 –1/7 1 2 A3 3 25/7 3/7 1 5/7 –3/7 –1/7 2/7 3 m+1 A4 Zj – Cj 15/7 15 6/7 1 –9/7 1 4/7 Так как в (m + 1) – й строке таблицы 2.4. все оценки неотрицательны, то план Х2 = (х1 = 0; x2 = 15/7; x3 = 25/7; x4 = 15/7) – оптимальный и ему соответствует максимальное значение функции цели Z(X2) = 15. На основании оценок (m + 1) – й строки можно заключить, что оптимальный план для данной задачи не является единственным, так как нулевые оценки соответствуют векторам А1 и А6 не входящим в базис. Пример 2: Решить симплексным методом задачу линейного программирования: Z = x1 – 3x2 +2x3  min – x1 – x2 – 2x3  5 2x1 – 3x2 + x3  3 2x1 – 5x2 + 6x3  5 xj  0; j = 1, 2, 3. Сведя с помощью дополнительных переменных х4, х5 и х6 систему ограничений к уравнениям, получим задачу линейного программирования: Z = x1 – 3x2 + 2x3  min – x1 – x2 – 2x3 + x4 = 5 2x1 – 3x2 + x3 + x5 = 3 2x1 – 5x2 + 6x3 + x6 = 5 xj  0; j = 1, 2,…, 6. Полученная задача линейного программирования удовлетворяет всем условиям, позволяющим применить для ее решения алгоритм симплексного метода. Построим симплексную таблицу: Таблица 2.5 i Базис С базиса 1 –3 2 A1 A2 A3 A4 A5 A6 –1 –1 –2 1 B 1 A4 5 2 A5 3 2 –3 1 1 3 A6 5 2 –5 6 1 –2 m+1 Zj – Cj –1 3 Данная задача решается на минимум, следовательно, оптимальный план не должен содержать положительных оценок. Из таблицы 3.5. видно, что условия оптимальности не выполнены (q2 = Z2 – C2 > 0). Это означает, что вектор А2 следует ввести в базис. Все коэффициенты разложения вектора А2 по векторам базиса отрицательные, т.е. в соответствии с формулой (2.10) невозможно выбрать разрешающий элемент. Поэтому данная задача линейного программирования не имеет решения из-за неограниченности функции цели. 2.4. Метод искусственного базиса. Известно, что для решения задачи линейного программирования симплексным методом необходимо, чтобы она была задана в канонической форме, т.е. система условий задачи должна удовлетворять следующим трем требованиям: 1. все ограничения должны быть заданы в виде уравнений; 2. свободные члены должны быть неотрицательными; 3. система ограничений должна содержать единичный базис (т.е. систему из m единичных линейно независимых векторов, где m – количество ограничений задачи). Если выполнены эти условия, то тем самым определен первоначальный опорный план, исходя из которого с помощью симплексного метода находится оптимальный план. Требование 1. (как было показано выше) можно выполнить всегда с помощью введения дополнительных переменных. С другой стороны, большинство задач линейного программирования таково, что выполнить одновременно требования 2. и 3. невозможно, в то же время можно выполнить какое – либо одно из этих требований. Если задача линейного программирования такова, что ее система ограничений удовлетворяет требованиям 1. и 2., но не содержит единичного базиса (т.е. не выполнено требование 3.), то для ее решения применяется метод искусственного базиса. Рассмотрим задачу линейного программирования: Z  c1 x1  c2 x2  ...  cn xn  extr   a11 x1  a12 x2  ...  a1n xn  b1  a21 x1  a22 x2  ...  a2 n xn  b2  ...........................................  a x  a x  ...  a x  b mn n m  m1 1 m 2 2 _____   x j  0; j  1, n (2.23) (2.24) где bi  0 и система ограничений не содержит единичного базиса. Для его получения к каждому равенству прибавим по одной переменной xn+i (i = 1, 2,…, m), которые назовем искусственными, и рассмотрим расширенную задачу, связанную с отысканием экстремального значения линейной функции Z  c1 x1  c2 x2  ...  cn xn  M  xn 1  xn 2  ...  xn m   extr  a11 x1  a12 x2  ...  a1n xn  xn 1  b1 a21 x1  a22 x2  ...  a2 n xn  xn 2  b2  ........................................... a x  a x  ...  a x  x  b mn n nm m  m1 1 m 2 2 __________   x j  0; j  1, n  m (2.25) (2.26) Величина М предполагается достаточно большим положительным числом. Знак перед числом М выбирается из соображений штрафа за нарушение ограничений. Искусственные переменные xn+i (i =1, 2,…, m) нарушают ограничения задачи, так как система ограничений (2.26) отличается от системы (2.24). Если хотя бы одна искусственная переменная отлична от нуля (а в силу условий неотрицательности переменных, это означает, что она больше нуля), то данное ограничение системы (2.26) отличается от соответствующего ограничения системы (2.24). Точнее, левая часть этого ограничения в (2.26) превосходит левую часть в (2.24) на значение искусственной переменной. Как только это происходит, на функцию цели в расширенной задаче накладывается штраф. Если задача решается на минимум, то за нарушение ограничений добавляется штрафная функция +М(xn+1 + xn+2 + … + xn+m) и значение исходной функции цели (2.23) неизмеримо возрастает; при решении задачи на максимум штрафная функция имеет вид: – М(xn+1 + xn+2 + … + xn+m) и при нарушении ограничений функция (2.23) неизмеримо убывает. Задача (2.25) – (2.26) совпадает с задачей (2.23) – (2.24) в том и только в том случае, когда все искусственные переменные равны нулю. Для отыскания оптимального плана исходной задачи пользуются следующей теоремой. Теорема. Если в оптимальном плане Õ = (х1, х2,…, хn, 0, 0,…, 0) расширенной задачи все искусственные переменные xn+i = 0 (i =1, 2,…, m), то план Х = (х1, х2,…, xn) является оптимальным для исходной задачи. Доказательство: Если X – оптимальный план расширенной задачи, то Х – план исходной задачи, при этом Z ( X ) = Z(X) (т.к. план X отличается от плана Х только m последними компонентами, равными нулю). Для определенности положим, что исходная задача решается на максимум. Предположим, что Х не является оптимальным планом. Тогда существует оптимальный план Х*=(x1*, х2*,…, хn*) для которого Z(X*) > Z(X). Отсюда следует, что для вектора X *=(x1*, x2*,…,xn*, 0, 0,…, 0), являющегося планом расширенной задачи, получим: Z ( X *) = Z(X*) > Z(X) = Z ( X ) , т.е. Z ( X * )  Z ( X ) , что противоречит условию теоремы и доказывает ее. Аналогично доказывается теорема и для минимума целевой функции. Для отыскания оптимального плана расширенной задачи применяется симплексный метод с составлением симплексных таблиц, которые имеют на одну строку больше, чем обычные симплексные таблицы. По этой (m + 2) – й строке, содержащей числа, умноженные на величину М, определяют вектор, подлежащий включению в базис. Итерационный процесс по (m + 2) – й строке проводят до полного исключения всех искусственных векторов из базиса. Затем процесс отыскания оптимального плана продолжают по (m + 1) – й строке (т.е. после исключения (m + 2) – й строки полученную задачу решают по алгоритму симплексного метода). Пример 3. Решить задачу линейного программирования: Z = 10x1 + 8x2  min x1 + 2x2  5 2x1 + x2  2 x1  0; x2  0. Введя дополнительные переменные х3 и х4, приведем систему ограничений к уравнениям: Z = 10x1 + 8x2  min x1 + 2x2 – x3 = 5 2x1 + x2 – x4 = 2 xj  0; j = 1, 2, 3, 4. Полученная система ограничений не содержит единичного базиса. Введя искусственные переменные х5 и х6 и налагая штраф на функцию цели Z, получим расширенную задачу: Z = 10x1 + 8x2 +M(x5 + x6)  min x1 + 2x2 – x3 + x5 = 5 2x1 + x2 – x4 + x6 = 2 xj  0 ; j = 1, 2,…, 6. Теперь система ограничений содержит единичный базис (это векторы коэффициентов при искусственных переменных х5 и х6). Строим первую симплексную таблицу. Таблица 2.6 i Базис С базиса 10 8 М М A1 A2 A3 A4 A5 A6 B 1 A5 М 5 1 2 –1 1 2 A6 М 2 2 1 –1 1 –10 m+1 Zj – Cj –8 Zj – Cj m+2 7 3 –1 3 –1 Таблица 2.6. составлена по обычным правилам симплексного метода. В (m + 1) – й и (m + 2) – й строках помещены оценки Zj – Cj, причем в (m+2) – й строке – коэффициенты, содержащие множитель М. Например, столбец «B»: М5 + М2= 7М, т.е. в (m + 1) – ю строку помещаем 0 (коэффициент, не содержащий множитель М), в (m + 2) – ю строку помещаем 7 (коэффициент, содержащий множитель М). Столбец А1: М1 + М2 – 10 = – 10 + 3М. В (m + 1) – ю строку помещаем – 10 (коэффициент, не содержащий множителя М), в (m + 2) – ю строку записываем 3 (коэффициент, содержащий множитель М) и т.д. Оптимизацию ведем по (m + 2) – й строке. Задача решается на минимум, следовательно, нужно добиться того, чтобы в (m + 2) – й строке отсутствовали положительные оценки. В таблице 3.6. имеются два «нарушителя»: это число 3, стоящее в столбце А1 и число 3, стоящее в столбце А2. 1 = min {5/1; 2/2} = 1; | 1q1 | = | 1(Z1 – C1) | = 3; 2 = min {5/2; 2/1} = 2; | 2q2 | = | 2(Z2 – C2) | = 6. Выбираем столбец А2. Из базиса исключается вектор А6. Так как вектор А6 – искусственный, то при дальнейших расчетах он уже не может войти в базис и таблицу 3.7. оформляем без столбца А6. Таблица 2.7 i Базис С B базиса 1 A5 М 1 2 A2 8 2 10 8 М A1 A2 A3 A4 A5 –3 2 –1 2 1 1 –1 m+1 Zj – Cj 16 m+2 Zj – Cj 1 6 –3 –8 –1 2 Переход от таблицы 2.6. к таблице 2.7. выполнен в соответствии с алгоритмом симплексного метода. В полученной таблице вновь не выполнено условие оптимальности по (m + 2) – й строке: в ней содержится положительный элемент 2. Это означает, что вектор А4 должен быть введен в базис. Составляем симплексные отношения: 1 = 1/2. Других симплексных отношений нет, так как элемент – 1, стоящий в столбце А4, является отрицательным. Следовательно, из базиса будет выведен вектор А5. Таким образом, из базиса выведены все искусственные векторы. В следующей таблице исключаем (m + 2) – ю строку и столбец А5. Таблица 2.8 i Базис С базиса 10 8 A1 A2 A3 B A4 1 A4 1/2 –3/2 0 –1/2 1 2 A2 8 5/2 1/2 1 –1/2 m+1 Zj – Cj 20 –6 –4 В таблице 2.8. получен оптимальный план, так как все оценки (m + 1) –й строки неположительны. Zmin = 20; x1 = 0; x2 = 5/2; x3 = 0; x4 = 1/2. Если задача линейного программирования не имеет решения из – за пустоты области допустимых решений, то метод искусственного базиса позволяет это обнаружить. В этом случае встретится симплексная таблица, содержащая (m + 2) – ю строку (в базисе содержатся искусственные векторы), удовлетворяющую условиям оптимальности. Следовательно, возникает ситуация, когда невозможно осуществить оптимизацию по (m + 2) – й строке (ввиду отсутствия в ней нарушений условий оптимальности) и в тоже время базис содержит искусственные векторы. Это означает, что искусственные векторы не могут быть выведены из базиса, т.е. система ограничений исходной задачи без привлечения искусственных переменных невыполнима, иначе говоря, область допустимых решений пуста. Пример 4. Решить методом искусственного базиса задачу линейного программирования: Z = 2x1 – 5x2  max 4x1 + 3x2  12 3x1 + 4x2  24 x1  0; x2  0 Введя дополнительные переменные х3 и х4, приведем систему ограничений к уравнениям: Z = 2x1 – 5x2  max 4x1 + 3x2 + x3 = 12 3x1 + 4x2 – x4 = 24 xj  0; j = 1, 2,…, 4 Полученная система ограничений содержит только один единичный вектор (вектор коэффициентов при переменной х3). Введем во второе ограничение искусственную переменную х5 и, налагая штраф на функцию цели Z, получим расширенную задачу: Z = 2х1 – 5х2 – Мх5  max 4x1 + 3x2 + x3 = 12 3x1 + 4x2 – x4 +x5 = 24 xj  0; j = 1, 2,…, 5 Теперь система ограничений содержит единичный базис (это векторы коэффициентов при переменных х4 и х5). Строим первую симплексную таблицу. Таблица 2.9 i Базис С 2 –5 –M A1 A2 A3 A4 A5 B базиса 1 A3 12 4 3 1 2 A5 –M 24 3 4 –1 1 5 1 m+1 Zj – Cj m+2 Zj – Cj –2 –24 –3 –4 Оптимизацию ведем по (m + 2) – й строке. На первом этапе вводим в базис вектор А2 и выводим вектор А3. Таблица 2.10 i Базис С 2 –5 0 –M A1 A2 A3 A4 A5 B базиса 1 A2 –5 4 2 A5 –M 8 –7/3 m+1 Zj – Cj –20 m+2 Zj – Cj –8 4/3 –26/3 7/3 1 1/3 0 –4/3 –1 1 0 –5/3 0 4/3 1 В полученной таблице (m + 2) – я строка удовлетворяет условиям оптимальности (все оценки этой строки являются неотрицательными). В то же время в базисе содержится искусственный вектор А5. Таким образом, задача не имеет решения из-за пустоты области допустимых решений.