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

Рассмотрим третий случай построения начального опорного плана (первый и второй описаны в пункте 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

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

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

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

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

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

Таблица 6

В индексной строке нет отрицательных оценок. Следовательно, по признаку оптимальности опорный план (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

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

Таблица 8

Метод искусственного базиса (Симплекс-метод) - Пример 1

Целевая функция:

1X 1 +5X 2 +4X 3 -3X 4 →max

2X 1 +7X 2 +1X 3 +0X 4 ≤5
1X 1 +4X 2 +2X 3 +8X 4 =6
-1X 1 +0X 2 +2X 3 +5X 4 =9

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

2X 1 +7X 2 +1X 3 +0X 4 +X5=5
1X 1 +4X 2 +2X 3 +8X 4 +R1=6
-1X 1 +0X 2 +2X 3 +5X 4 +R2=9
Переходим к формированию исходной симплекс таблицы. В строку F таблицы заносятся коэффициенты целевой функции. Так как нам необходимо найти максимум целевой функции, то в таблицу заносятся коэффициенты с противоположным знаком

Так как среди исходного набора условий были равенства, мы ввели искуственные переменные R. Это значит, что в симплекс таблицу нам необходимо добавить дополнительную строку M, элементы которой расчитываются как сумма соответствующих элементов условий-равенств (тех которые после приведения к каноническому виду содержат искусственные переменные R) взятая с противоположным знаком.

Из данных задачи составляем исходную симплекс таблицу.

	X1	X2	X3	X4	Своб член
F	-1	-5	-4	3	0
X5	2	7	1	0	5
R1	1	4	2	8	6
R2	-1	0	2	5	9
M	0	-4	-4	-13	-15

Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение.В строке M имеются отрицательные элементы, это означает что полученое решение не оптимально. Определим ведущий столбец. Для этого найдем в строке M максимальный по модулю отрицательный элемент - это -13 Ведущей строкой будет та для которой отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является R1, а ведущий элемент: 8.

	X1	X2	X3	Своб член
F	-1.375	-6.5	-4.75	-2.25
X5	2	7	1	5
X4	0.125	0.5	0.25	0.75
R2	-1.625	-2.5	0.75	5.25
M	1.625	2.5	-0.75	-5.25

В строке M имеются отрицательные элементы, это означает что полученое решение не оптимально. Определим ведущий столбец. Для этого найдем в строке M максимальный по модулю отрицательный элемент - это -0.75 Ведущей строкой будет та для которой отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является X4, а ведущий элемент: 0.25.

	X1	X2	X4	Своб член
F	1	3	19	12
X5	1.5	5	-4	2
X3	0.5	2	4	3
R2	-2	-4	-3	3
M	2	4	3	-3

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

Когда в условии присутствуют ограничения типа равенств. Рассмотрим задачу:

max{F(x)=∑c i x i |∑a ji x i =b j , j=1,m ; x i ≥0}.

В ограничения и в функцию цели вводят так называемые «искусственные переменные» R j следующим образом:

∑a ji x+R j =b j , j=1,m ;F(x)=∑c i x i -M∑R j

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

Симплекс-таблица, которая составляется в процессе решения, используя метод искусственного базиса, называется расширенной. Она отличается от обычной тем, что содержит две строки для функции цели: одна – для составляющей F = ∑c i x i , а другая – для составляющей M ∑R j Рассмотрим процедуру решения задачи на конкретном примере.

Пример 1. Найти максимум функции F(x) = -x 1 + 2x 2 - x 3 при ограничениях:

2x 1 +3x 2 +x 3 =3,

x 1 ≥0, x 2 ≥0, x 3 ≥0 .

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

2x 1 + 3x 2 + x 3 + R 1 = 3;

x 1 + 3x 3 + R 2 = 2 ;

Функция цели F(x)-M ∑R j = -x 1 + 2x 2 - x 3 - M(R 1 +R 2).

Выразим сумму R 1 + R 2 из системы ограничений: R 1 + R 2 = 5 - 3x 1 - 3x 2 - 4x 3 , тогда F(x) = -x 1 + 2x 2 - x 3 - M(5 - 3x 1 - 3x 2 - 4x 3) .

При составлении первой симплекс-таблицы (табл. 1) будем полагать, что исходные переменные x 1 , x 2 , x 3 являются небазисными, а введенные искусственные переменные – базисными. В задачах максимизации знак коэффициентов при небазисных переменных в F- и M-строках изменяется на противоположный. Знак постоянной величины в M-строке не изменяется. Оптимизация проводится сначала по M-строке. Выбор ведущих столбца и строки, все симплексные преобразования при испльзовании метода искусственного базиса осуществляются как в обычном симплекс-методе.

Максимальный по абсолютному значению отрицательный коэффициент (-4) определяет ведущий столбец и переменную x 3 , которая перейдет в базис. Минимальное симплексное отношение (2/3) соответствует второй строке таблицы, следовательно, переменная R 2 должна быть из базиса исключена. Ведущий элемент обведен контуром.

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

x 1 =0; x 2 =7/9; F max =8/9.

Если при устранении M-строки решение не является оптимальным, то процедура оптимизации продолжается и выполняется обычным симплекс-методом. Рассмотрим пример, в котором присутствуют ограничения всех типов:≤,=,≥

Пример 2 . Найти минимальное значение функции F(x) = 2x 1 + 3x 2 - x 3 при следующих ограничениях

2x 1 +x 2 -3x 3 ≥6,

x 1 -x 2 +2x 3 =4,

x 1 +x 2 +x 3 ≤5,

x 1 ≥0, x 2 ≥0, x 3 ≥0 .

Домножим первое из ограничений на (-1) и введем в ограничения дополнительные переменные x 4 , x 5 и искусственную переменную R следующим образом:

2x 1 -x 2 +3x 3 +x 4 =-6,

x 1 -x 2 +2x 3 +R=4,

x 1 +x 2 +x 3 +x 5 =5,

Пусть x 4 , R и x 5 – базисные переменные, а x 1 , x 2 , x 3 – небазисные. Функция цели F(x)=F(x)+M∑R=2x 1 +3x 2 -x 3 +M(4-x 1 +x 2 -2x 3).

В первой (табл. 4.) коэффициенты при небазисных переменных в F-строке и M-строках знака не меняют, так как осуществляется минимизация функции. Свободный член в методе искусственного базиса в M-строке берется с противоположным знаком. Решение, соответствующее табл. 4, не является допустимым, так как есть отрицательный свободный член.

Выберем ведущий столбец и строку в соответствии с шагом 2 алгоритма решения. После пересчета получим табл. 5. Оптимизация решения в методе искусственного базиса (шаг 5 алгоритма) осуществляется вначале по M-строке. В результате x 3 введем в базис, а переменную R исключим из рассмотрения, сократив количество столбцов. После пересчета получим табл. 6, которая соответствует оптимальному решению задачи.

Таблица 4

Таблица 5

Таблица 6

Искомый минимум функции F(x) равен свободному члену F-строки табл. 6, взятому с обратным знаком, так как min F(x) = -max(-F(x)); x 4 = x 2 = 0;

x 1 =24/7; x 3 =2/7; x 5 =9/7; F min =46/7;

В случаях, когда сразу не выделяются базисные переменные (а они сразу выделяются только после приведения к каноническому виду задачи, в которой имеются только неравенства типа «≤» при неотрицательных правых частях) можно применять так называемый метод искусственного базиса , который является по сути разновидностью симплекс-метода.

Пусть задача приведена к каноническому виду (1.6), в котором в некоторых уравнениях, скажем в i 1 -м, i 2 -м, …, i s -м, явно не выделяются базисные переменные. Добавим в эти уравнения искусственные переменныеx m +1 , x m +2 , …, x m + s , а в целевую функцию - слагаемые ±Mx m +1 , ±Mx m +2 , …, ±Mx m + s , где M >>1 (M - достаточно большое положительное число) причём «±» - это «+», если решается задача на min, и «±» - это «-», если решается задача на max. Получается новая задача, которая называется дополнительной или вспомогательной .

Например, вспомогательная (дополнительная) задача с искусственными переменными для задачи (1.5) будет иметь вид

c 1 x 1 +c 2 x 2 +…+c n x n +Mx n + m +1 +Mx n + m +2 +…+Mx n +2 m ®min

Аналогично, если задача (2.1) решается на max и придётся вводить искусственные переменные во все ограничения, то получаем следующую вспомогательную задачу:

c 1 x 1 +c 2 x 2 +…+c n x n -Mx n +1 -Mx n +2 -…-Mx n + m ®max

(5.1)

5.1.1. Если ( , , …, , , …, ) оптимальное решение вспомогательной задачи , где , …, - значения искусственных переменных , , , …, - значения переменных в исходной задаче в канонической форме , то =…= =0 и ( , , …, ) - оптимальное решение исходной задачи . При этом значения целевой функции исходной и вспомогательной задач совпадают .

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

1. Привести задачу к каноническому виду.

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

3. Решить вспомогательную задачу, и если ( , , …, , , …, ) - оптимальное решение вспомогательной задачи, где x 1 , x 2 , …, x m - основные и дополнительные переменные (из задачи в каноническом виде), x m +1 , x m +2 , …, x m + s - искусственные переменные то ( , , …, ) - решение задачи в каноническом виде. Оптимальное значение целевой функции вспомогательной задачи равно оптимальному значению исходной задачи.

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

1. Так как целевая функция вспомогательной задачи имеет слагаемые с коэффициентами ±M , то оценки D k имеют вид ± M , причём M - достаточно большое число. Поэтому при ≠0 знак D k фактически определяется знаком при . В связи с этим в симплекс-таблице на начальном этапе (пока в базис входят искусственные переменные) вместо одной строки D k записывают две строки и , и при применении критерия оптимальности ориентируются только на строку .

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

3. После того, как все искусственные переменные будут выведены из базиса, коэффициенты D k при M будут равны нулю, в таблице остаётся только строка =D k .

Пример. Решить пример из предыдущего параграфа методом искусственного базиса.

Решение. Напоминаем задачу:

3x 1 +x 2 +2x 3 ® max(min)

1. Приведём задачу к каноническому виду:

3x 1 +x 2 +2x 3 ® max(min)

2. В базис в виде единичного вектора входит только вектор при x 4 , то есть переменная во втором уравнении. В первое и третье уравнения системы ограничений вводим искусственные переменные x 6 и x 7:

В целевую функцию они войдут с коэффициентами M или -M в зависимости от того, решается задача на min или на max.

Решим задачу на максимум. Тогда вспомогательная задача - следующая:

3x 1 +x 2 +2x 3 -Mx 6 -Mx 7 ® max

3. Решаем полученную вспомогательную задачу с применением симплекс-таблиц:

Здесь D 2 =-2M -1, D 3 =-3M -2. Коэффициенты при M записаны в строке . Имеем, что D 2 <0 и D 3 <0, то есть для переменных x 2 и x 3 нарушается критерий оптимальности. Поэтому в базис будем вводить x 2 или x 3 . Какую именно из этих переменных, и вместо какой из искусственных (вместо x 6 или вместо x 7), определяем с помощью столбцов q 2 и q 3 . На пересечении столбца q 2 и строк и числа соответственно 2 и 4 означают, что в случае включения в базис x 2 значение функции возрастёт на -q 2 D 2 =4M +2, а в случае включения в базис x 3 значение функции возрастёт на -q 3 D 3 =3M +2<-q 2 D 2 . Поэтому в базис включаем x 2 (что обеспечивает большее возрастание функции и в конечном итоге ускоряет процесс решения задачи). Так как min =2 достигается в строке x 6 , то из базиса исключаем x 6 . Строим новую симплекс-таблицу, в который уже столбец с искусственной переменной x 6 отсутствует (вычеркнут), так как искусственная переменная x 6 из дальнейшего процесса исключается. В новой таблице коэффициент при x 2 в первой строке (которая теперь соответствует новой базисной переменной x 2) равен 1, а во второй равен нулю. Поэтому первые две строки в новую таблицу переписываем из старой. Для того, чтобы в строке x 7 при x 2 получить 0, из строки x 7 в старой таблице вычитаем новую первую. Получаем следующую, очередную, таблицу:

Так как D k <0 только для одного значения k =1, а именно, D 1 =-2M +2<0 (напоминаем, что M - достаточно большое число, так что -2M <2 и D 1 <0), то ищем только отношения q 1 . Минимум этих отношений достигается в строке x 7: min =2. Поэтому искусственная переменная исключается из базиса, а вместо неё в базис включается x 1 .

Искусственные переменные теперь исключены из базиса. Поэтому дальше работаем с обычной симплекс-таблицей, в которой новая третья строка (соответствующая переменной x 1) получается делением старой третьей строки на 2. Затем эту новую третью прибавляем к старой первой и вычитаем из старой второй. В результате в новой таблице в столбце x 1 появятся соответственно 0, 0 и 1:

В полученной таблице D k ³0 для всех k X 0 =(2; 4; 0) является оптимальным решением, при котором значение целевой функции равно -2 (x 4 в окончательном ответе не учитывается, так как она является дополнительной переменной, и не входит в первоначальную задачу).

Решим задачу на минимум (min). Тогда вспомогательная задача - следующая:

3x 1 +x 2 +2x 3 -Mx 6 -Mx 7 ® max

Как и выше, решаем полученную вспомогательную задачу с применением симплекс-таблицы:

Критерий оптимальности нарушается для переменных x 2 и x 3: D 2 =2M -1>0, D 3 =3M -2>0. Так как -q 2 D 2 =-4M +2 по абсолютной величине превосходит -q 3 D 3 =-3M +2, то в базис включаем x 2 . При этом min =2 достигается в строке x 6 , и из базиса исключаем x 6 . Переход к новой таблице аналогичен переходу при решении задачи на max:

Теперь D 1 >0. Поэтому переход к новой таблице аналогичен соответствующему переходу при решении задачи на max: в базис вводится x 1 вместо x 7:

Имеем D 3 =1>0 и D 5 =1>0. Так как |-q 5 D 5 |=|-q 3 D 3 |, то вводим в базис x 5 (вместо x 4): сначала умножаем 2-ю строку на 2, а затем новую вторую строку, умноженную на ½, прибавляем к первой и третьей (фактически вторую старую прибавляем к первой и третьей):

В полученной таблице D k £0 для всех k =1, 2, …, 5, то есть критерий оптимальности выполнен. Поэтому X 0 =(4; 6; 0) является оптимальным решением, при котором значение целевой функции равно -6.

Ответ: F min =-6, минимум достигается в точке X 2 =(4; 6; 0);

F max =-2, максимум достигается в точке X 1 =(2; 4; 0).

5.2. Упражнение. Решить соответствующие задачи линейного программирования из Упражнения 1.3 методом искусственного базиса.

Теория двойственности