Метод искусственного базиса.

Лекция 3. Метод искусственного базиса. Известно, что для решения задачи линейного программирования симплексным методом необходимо, чтобы она была задана в канонической форме, т.е. система условий задачи должна удовлетворять следующим трем требованиям: 1. все ограничения должны быть заданы в виде уравнений; 2. свободные члены должны быть неотрицательными; 3. система ограничений должна содержать единичный базис (т.е. систему из m единичных линейно независимых векторов, где m – количество ограничений задачи). Если выполнены эти условия, то тем самым определен первоначальный опорный план, исходя из которого с помощью симплексного метода находится оптимальный план. Требование 1. (как было показано выше) можно выполнить всегда с помощью введения дополнительных переменных. С другой стороны, большинство задач линейного программирования таково, что выполнить одновременно требования 2. и 3. невозможно, в то же время можно выполнить какое – либо одно из этих требований. Если задача линейного программирования такова, что ее система ограничений удовлетворяет требованиям 1. и 2., но не содержит единичного базиса (т.е. не выполнено требование 3.), то для ее решения применяется метод искусственного базиса. Рассмотрим задачу линейного программирования: Z  c1 x1  c2 x2  ...  cn xn  extr (3.1)  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 (3.2) где 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 (3.3) (3.4) Величина М предполагается достаточно большим положительным числом. Знак перед числом М выбирается из соображений штрафа за нарушение ограничений. Искусственные переменные xn+i (i =1, 2,…, m) нарушают ограничения задачи, так как система ограничений (3.4) отличается от системы (3.2). Если хотя бы одна искусственная переменная отлична от нуля (а в силу условий неотрицательности переменных, это означает, что она больше нуля), то данное ограничение системы (3.4) отличается от соответствующего ограничения системы (3.2). Точнее, левая часть этого ограничения в (3.4) превосходит левую часть в (3.2) на значение искусственной переменной. Как только это происходит, на функцию цели в расширенной задаче накладывается штраф. Если задача решается на минимум, то за нарушение ограничений добавляется штрафная функция +М(xn+1 + xn+2 + … + xn+m) и значение исходной функции цели (3.1) неизмеримо возрастает; при решении задачи на максимум штрафная функция имеет вид: – М(xn+1 + xn+2 + … + xn+m) и при нарушении ограничений функция (3.1) неизмеримо убывает. Задача (3.3) – (3.4) совпадает с задачей (3.1) – (3.2) в том и только в том случае, когда все искусственные переменные равны нулю. Для отыскания оптимального плана исходной задачи пользуются следующей теоремой. Теорема Если в оптимальном плане X = (х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) – й строки полученную задачу решают по алгоритму симплексного метода). Пример 1. Решить задачу линейного программирования: 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). Строим первую симплексную таблицу. Таблица 3.1 С i Базис 1 A5 М 2 A6 М базиса 10 8 М М A1 A2 A3 A4 A5 A6 5 1 2 –1 1 2 2 1 –1 1 B m+1 Zj – Cj –10 –8 m+2 Zj – Cj 7 3 3 –1 –1 Таблица 3.1. составлена по обычным правилам симплексного метода. В (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.1. имеются два «нарушителя»: это число 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.2. оформляем без столбца А6. Таблица 3.2 С i Базис 1 A5 М 2 A2 8 10 8 М A1 A2 A3 A4 A5 1 –3 –1 2 1 2 2 1 –1 B базиса m+1 Zj – Cj 16 6 –8 m+2 Zj – Cj 1 –3 –1 2 Переход от таблицы 3.1. к таблице 3.2. выполнен в соответствии с алгоритмом симплексного метода. В полученной таблице вновь не выполнено условие оптимальности по (m + 2) – й строке: в ней содержится положительный элемент 2. Это означает, что вектор А4 должен быть введен в базис. Составляем симплексные отношения: 1 = 1/2. Других симплексных отношений нет, так как элемент – 1, стоящий в столбце А4, является отрицательным. Следовательно, из базиса будет выведен вектор А5. Таким образом, из базиса выведены все искусственные векторы. В следующей таблице исключаем (m + 2) – ю строку и столбец А5. Таблица 3.3 С i Базис 1 A4 2 A2 8 m+1 базиса Zj – Cj 10 8 A1 A2 A3 A4 1/2 –3/2 –1/2 1 5/2 1/2 1 –1/2 20 –6 –4 B В таблице 3.3. получен оптимальный план, так как все оценки (m + 1) –й строки не положительны. Zmin = 20; x1 = 0; x2 = 5/2; x3 = 0; x4 = 1/2. Если задача линейного программирования не имеет решения из – за пустоты области допустимых решений, то метод искусственного базиса позволяет это обнаружить. В этом случае встретится симплексная таблица, содержащая (m + 2) – ю строку (в базисе содержатся искусственные векторы), удовлетворяющую условиям оптимальности. Следовательно, возникает ситуация, когда невозможно осуществить оптимизацию по (m + 2) – й строке (ввиду отсутствия в ней нарушений условий оптимальности) и в тоже время базис содержит искусственные векторы. Это означает, что искусственные векторы не могут быть выведены из базиса, т.е. система ограничений исходной задачи без привлечения искусственных переменных невыполнима, иначе говоря, область допустимых решений пуста. Пример 2. Решить методом искусственного базиса задачу линейного программирования: 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). Строим первую симплексную таблицу. Таблица 3.4 i Базис 1 A3 С базиса B 12 2 –5 –M A1 A2 A3 A4 A5 4 3 1 2 A5 –M 24 3 4 –1 1 m+1 Zj – Cj –2 5 m+2 Zj – Cj –24 –3 –4 1 Оптимизацию ведем по (m + 2) – й строке. На первом этапе вводим в базис вектор А2 и выводим вектор А3. Таблица 3.5 С i Базис 1 A2 –5 2 A5 –M базиса 2 –5 –M A1 A2 A3 A4 A5 4 4/3 1 1/3 8 –7/3 –4/3 –1 1 B m+1 Zj – Cj –20 –26/3 –5/3 m+2 Zj – Cj –8 7/3 4/3 1 В полученной таблице (m + 2) – я строка удовлетворяет условиям оптимальности (все оценки этой строки являются неотрицательными). В то же время в базисе содержится искусственный вектор А5. Таким образом, задача не имеет решения из-за пустоты области допустимых решений.