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

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

Рассмотрим третий случай построения начального опорного плана (первый и второй описаны в пункте 2.1).

Пусть система ограничений имеет вид

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

.

Теперь система ограничений не имеет предпочтительного вида, так как дополнительные переменные x n + i входят в левую часть (приb i 0) с коэффициентами, равными –1. В этом случае вводится так называемыйискусственный базис путем перехода кМ-задаче.

К левым частям ограничений-равенств, не имеющих предпочтительного вида, добавляют искусственные переменные w i . В целевую функцию переменныеw i вводят с коэффициентомM в случае решения задачи на минимум и с коэффициентом –M – для задачи на максимум, гдеM – большое положительное число. Полученная задача называетсяМ-задачей , соответствующей исходной. Она всегда имеет предпочтительный вид.

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

;
;

При этом ни одно из ограничений не имеет предпочтительной переменной. М-задача будет записываться следующим образом:

;

При этом знак “–” в функции (10) относится к задаче на максимум. Задача (10)–(12) имеет предпочтительный вид. Ее начальный опорный план имеет вид

.

Если некоторые из уравнений (8) имеют предпочтительный вид, то в них не следует вводить искусственные переменные.

Теорема 5. Если в оптимальном планех опт 

М -задачи (10)–(12) все искусственные переменные
, то план
является оптимальным планом исходной задачи (7)–(9).

Теорема 6 (признак несовместности системы ограничений ) . Если в оптимальном планеМ -задачи хотя бы одна из искусственных переменных отлична от нуля, то система ограничений исходной задачи несовместна.

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

Пример 4. Решить с использованием искусственного базиса задачу линейного программирования

Первое ограничение имеет предпочтительную переменную х 3 , а второе – нет. Поэтому вводим в него искусственную переменнуюw 1 . Приходим кМ- задаче

Занесем условие М- задачи в симплексную табл. 5. Начальный опорный план имеет видx 0 = (x 1 ;x 2 ;x 3 ;x 4 ;w 1) = (0; 0; 2; 0; 12),z (x 0) = 0 – 12M .

Таблица 5

	с Б
z j – c j

Сделаем необходимые пояснения.

Индексную строку удобно разбить на две. В первой из них записываются свободные члены выражений  0 =c Б А 0 и j =c Б A j –c j , а во второй – коэффициенты, содержащиеM . Например, для табл. 5:

Признак оптимальности проверяем сначала по второй строке индексной строки. Так как в ней существуют отрицательные оценки, то план x 0 не является оптимальным.

Переходим к новой табл. 6.

Разрешающий столбец находим по max{|–3M |; |–4M |} = 4M , разрешающая строка определяется по
. Следовательно, 1 – разрешающий элемент.

Таблица 6

	с Б
z j – c j

В индексной строке нет отрицательных оценок. Следовательно, по признаку оптимальности опорный план (0; 2; 0; 0; 4) оптимален. Но так как в оптимальном плане искусственная переменная w 1 не равна 0, то по теореме 6 система ограничений исходной задачи несовместна. Задача решения не имеет.

Ответ: нет решения.

Пример 5. Решить с использованием искусственного базиса задачу

Упорядочим запись исходной задачи. Умножим второе неравенство на –1:

Сведем задачу к каноническому виду. Получим

Первое и четвертое ограничения имеют предпочтительные переменные, а второе и третье – нет. Поэтому вводим в них искусственные переменные w 1 иw 2 . Приходим кМ- задаче

Занесем условие М- задачи в симплексную табл. 7. Начальный опорный план имеет видx 0 = (0; 0; 10; 0; 0; 4; 3; 9),z (x 0) = 0 + 12M .

Таблица 7

	с Б
z j – c j

Мы решаем задачу на минимум. Признак оптимальности проверяем сначала по второй строке индексной строки. Так как в ней существует положительная оценка, то план x 0 не является оптимальным. Переходим к новой табл. 8.

Таблица 8

		с Б

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

При решении таких задач был введен метод искусственного базиса . Он особенно удобен, когда число переменных значительно превосходит число уравнений.

Алгоритм решения задачи симплексным методом с искусственным базисом рассмотрим на примере.

Пример 1

Найти максимум Z=4X1+2X2+X3

3Х1+2Х2+Х3=15

Хj³0, j=1,...,3

Переходим к канонической форме:

Х1+Х2+Х3-Х4=8

2Х1+Х2+Х3+Х5=8

3Х1+2Х2+Х3=15

Хj³0, j=1,...,5

Zmax=4X1+2X2+X3+0×X4+0×X5

Данная система ограничений не имеет единичного базиса, так как дополнительная переменная Х4 имеет коэффициент минус единица, а третье ограничение было представлено уравнением и в нем отсутствует базисная переменная. Для того, чтобы был единичный базис вводим в соответствующие ограничения искусственные переменные y1 и y2 с положительными коэффициентами (+1).

Следует отметить, что искусственные переменные вводятся только для математической формализации задачи. Поэтому схема вычислений должна быть такой, чтобы искусственные пременные не могли попасть в окончательное решение в числе базисных переменных. С этой целью для искусственных переменных в целевой функции вводят коэффициент М, обозначающий очень большое число. На практике (особенно при решении задачи на ЭВМ) вместо М берут конкретное большое число, например, 10000. Причем, при решении задачи на максимум этот коэффициент вводится в целевую функцию со знаком минус, а при решении на минимум – со знаком плюс. Теперь будем решать Т (М)-задачу, целевая функция которой содержит целевую функцию Z–задачи и искусственные переменные с коэффициентом ±М, т.е.

T=Z-M S yi, при решении на максимум целевой функции и

T=Z+M S y, при решении на минимум целевой функции

В нашем случае:

Х1+Х2+Х3-Х4+y1=8

2Х1+Х2+Х3+Х5=8

3Х1+2Х2+Х3+y2=15

Хj³0, j=1,...,5

Тmax= 4X1+2X2+X3+0×X4+0×X5 - M(y1+y2)

Эта задача решается в симплексных таблицах, но для удобства целевую функцию разбивают на 2 строки:

В первую строку записываем оценки, которые не содержат коэффициент М;

Во вторую строку- оценки по каждой свободной переменной, содержащие коффициент М.

Расчет элементов (оценок) этих двух строк производится по формуле (2). Только отличие:

При расчете оценок Z -строки должны быть учтены коэффициенты Cj , входящие в функцию Z ;

При расчете оценок М-строки этот коэффициент во внимание не берется, а М -выносится как общий множитель.

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

Лишь после того, как все y i станут равны нулю, дальнейший расчет будет вестись по первой индексной строке, т.е. -обычная Z-задача.

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

Между оптимальными решениями М-задачи и Z-задачи существует связь, устанавливаемая следующей теоремой:

1. Если в оптимальном решении М-задачи все искусственные переменные (y i) равны нулю, то это решение будет являться оптимальным решением Z-задачи.

2. Если в оптимальном решении М-задачи, хотя бы одна из искусственных переменных отлична от нуля, то Z-задача не имеет решения по причине несовместности системы ограничений.

3. Если М-задача оказалась неразрешимой (Т®+¥ или-¥), то исходная задача также неразрешима либо по причине несовместности системы ограничений, либо по причине неограниченности функции Z.

Составим первую симплексную таблицу. При решении М-методом разрешающий столбец можно выбирать в М-строке не по наибольшей по абсолютной величине отрицательной оценке (при решении на максимум) и не по наибольшей положительной оценке (при решении на минимум), а по той из них, которая быстрее выводит У из базиса. В данном примере разрешающим столбцом будет столбец свободной переменной X2 с оценкой (-3).

Таблица 3.1.

Первая симплексная таблица

Заполнение Z- строки осуществляется по формуле (2):

а00 = 0 × 8– 0 = 0

а01 =0 × 2– 4 = -4

а02 =0 × 1– 2 = -2

а03 =0 × 1– 1 = -1

а02 =0 × 0– 0 = 0

Заполнение М- строки:

а¢00 = -М × 8 + (–М) × 15 = -23М

а¢01 = -М × 1 + (–М) × 3= -4М

а¢02 = -М × 1 + (–М) × 2= -3М

а¢03 = -М × 1+ (–М) × 1 = -2М

а¢04 = -М ×(-1)+ (–М) × 0 = 1М

М выносим как общий множитель.

В последнем столбце в разрешающей строке стоит 0, поэтому столбец свободной переменной X4 переносим без изменений.

Таблица 3.2.

Вторая симплексная таблица

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

Таблица 3.3.

Третья симплексная таблица

Теперь решаем обычным симплексным методом.

Таблица 3.4.

Четвертая симплексная таблица

Св.П	Cj
Б.П.	Ci	ai0	X5	X4
Х3				-1
X1
Х2			-2	-1
Z

В оценочной строке все элементы являются неотрицательными величинами, следовательно получено оптимальное решение:

Zmax=15 Xopt(0,7,1,0,0)

Пример2

Задача решалась на минимум (Z®min) целевой функции. На последней итерации получили следующую таблицу:

Таблица 3.5.

Последняя симплексная таблица

Св.П	Cj
Б.П.	Ci	ai0	X1	X3	X4
У1	М	-1/2	-1/2	-1/2	-1
X5		1/2	1/2	1/2
Х2		15/2	3/2	1/2
Z			-1
	М	-1/2	-1/2	-1/2	-1

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

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

• система должна иметь каноническую (ступенчатую) структуру;
• присутствуют только ограничения-равенства;
• правые части ограничений положительны;
• переменные задачи положительны.

Без этих условий нельзя получить опорный план. Однако в реальных задачах далеко не всегда выполняются перечисленные условия.

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

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

Пусть все /? > 0, но часть или все базисные переменные отрицательны, X; 0. Следовательно, опорного плана нет.

Дополним уравнения-ограничения искусственными переменными (предполагаем, что все x j j - 1, п ).

Введем т переменных (по количеству уравнений): х лМ т, которые в новой системе будут базисными, а отрицательные х-

В результате получим следующую эквивалентную задачу.

Здесь переменные x n+i не имеют никакого отношения к исходной задаче линейного программирования. Они служат лишь для получения опорного плана и называются искусственными переменными. А новая

целевая функция /(.т) сформирована для полноты задачи.

В оптимальном опорном плане искусственные переменные должны быть равны нулю. В противном случае нарушится условие первоначальной задачи.

В начальном опорном плане искусственные переменные являются базисными, то есть не равны нулю, а в оптимальном плане искусственные переменные должны быть равны нулю. Значит, искусственные переменные должны стать в оптимальном плане свободными. В этом переводе и состоит основная идея метода: перевод искусственных переменных из базисных переменных в свободные. Рассмотрим механизм такого перевода на примере.

Перепишем ЗЛП в стандартной форме. Для этого введем дополнительные переменные х } , х А, х 5 , х 6 и запишем задачу в канонической форме.

Свободные переменные х, х 2 = 0, при этом базисные переменные примут значения х 3 =-5, х 4 = -5, х 5 = 7, х 6 =9. Так как часть базисных переменных отрицательны, следовательно опорного плана нет. Для получения начального опорного плана введем переменные х 7 , х 8 в двух первых уравнениях-ограничениях и сформулируем вспомогательную задачу:

Таким образом, начальным базисом является

Симплекс-таблица с искусственным базисом

	Х 4

Запишем последовательности опорных планов.

Для первых трех шагов приращения А к вычисляются только по искусственным переменным, которые входят в искусственную целевую функцию /(х) = х 7 + х 8 с коэффициентом с, = 1.

На третьем шаге искусственные переменные исключены, так как все А к положительны.

Итак, симплекс-метод с введением искусственных переменных включает два этапа.

Формирование и решение вспомогательной задачи ЛП с введением искусственных переменных. Искусственные переменные в начальном опорном плане являются базисными. Искусственная целевая функция включает только искусственные переменные. При получении смежных опорных планов искусственные переменные из базисных переводим в свободные. В результате получен оптимальный опорный план для вспомогательной задачи /(х) = 0.

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

Замечания

• 1. Введение искусственных переменных требуется в двух случаях:
  • ряд базисных переменных х, в канонической форме отрицательны;
  • если трудно свести к канонической форме, то просто в любое уравнение-ограничение добавляем искусственную переменную.
• 2. Встречающиеся в практике автоматического управления задачи линейного программирования содержат от 500 до 1500 ограничений и более 1000 переменных. Ясно, что задачи такой размерности можно решать лишь с помощью ЭВМ и специального программного обеспечения. Сложность алгоритма заключается в том, что:
  • ППП требует канонического вида;
  • ППП для задач такой размерности требует использования больших ЭВМ (и параллельных вычислений), так как симплекс-метод хранит всю таблицу.
• 3. Вычислительную эффективность симплекс-метода можно оценить следующими показателями:
  • число шагов (смежных опорных планов);
  • затраты машинного времени.

Существуют такие теоретические оценки для стандартной задачи линейного программирования с т ограничений и «"переменных:

• среднее число шагов * 2 т и лежит в диапазоне }