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

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

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

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

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

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

Пример 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.

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

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

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

Пример2

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

Таблица 3.5.

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

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

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

Как осуществляется переход от одного базиса к другому?
Запись решения удобнее вести в виде таблиц. Каждая строка эквивалентна уравнению системы. Выделенная строка состоит из коэффициентов функции (сравните сами). Это позволяет не переписывать переменные каждый раз, что существенно экономит время.
B выделенной строке выбираем наименьший отрицательный коэффициент. Это необходимо для того, чтобы получить значение функции, как минимум, не больше имеющегося.
Выбран столбец.
Для положительных коэффициентов выбранного столбца считаем отношение Θ и выбираем наименьшее значение. Это необходимо для того, чтобы после преобразования столбец свободных членов остался положительным.
Выбрана строка.
Следовательно, определен элемент, который будет базисным. Далее считаем.

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

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;