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

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

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

Пример 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 находится в базисе. В этом случае исходная задача не имеет решения по причине несовместности системы ограничений.

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

Пусть задача приведена к каноническому виду (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. Решаем полученную вспомогательную задачу с применением симплекс-таблиц:

Базис

С б

Своб. чл.

-3

-M

-M

q 2

q 3

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 6

-M

-1

min

x 4

-

x 7

-M

-1

-1

-2

-8

-2

-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 в старой таблице вычитаем новую первую. Получаем следующую, очередную, таблицу:

Базис

С б

Своб. чл.

-3

-M

-M

q 1

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 2

-1

-

x 4

x 7

-M

-1

-1

min

-4

-2

Так как 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:

Базис	С б	Своб. чл.	-3
x 1	x 2	x 3	x 4	x 5
x 2					3/2		-1/2
x 4					3/2		1/2
x 7	-3				-1/2		-1/2
D k	-2

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

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

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

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

Базис

С б

Своб. чл.

-3

M

M

q 2

q 3

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 6

M

-1

min

x 4

-

x 7

M

-1

-1

-2

-1

Критерий оптимальности нарушается для переменных 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:

Базис

С б

Своб. чл.

-3

-M

-M

q 1

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 2

-1

-

x 4

x 7

-M

-1

-1

min

-1

-1

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

Базис	С б	Своб. чл.	-3					q 3	q 5
x 1	x 2	x 3	x 4	x 5
x 2					3/2		-1/2	8/3	-
x 4					3/2		1/2	4/3
x 7	-3				-1/2		-1/2	-	-
D k	-2						-4/3	-4

Имеем 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 методом искусственного базиса.

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

Метод искусственного базиса (или метод “М”) может быть применен для решения задачи ЛП, если ее система ограничений, помимо неравенств смысла “≤” имеет неравенства смысла “≥” или строгие равенства. Рассмотрим задачу ЛП, заданную в самом общем виде.

Найти экстремум функции

Алгоритм метода «М».

1. От системы неравенств переходим к системе уравнений, вводя дополнительные неотрицательные переменные:

2. В ограничения, в которые дополнительные неотрицательные переменные вошли со знаком минус или вообще не вошли, вводятся так называемые искусственные переменные:

3. В линейную форму (1.26) вводится сумма искусственных переменных с коэффициентом M>0. Для того, чтобы искусственные переменные не содержались в оптимальном плане исходной задачи, коэффициенту М придается произвольно большое значение по сравнению с коэффициентами линейной формы (1.26). В этом случае при максимизации функции цели (1.26), берем (-М), при минимизации (+М).

4. Строим расширенную М – задачу ЛП:

найти экстремум линейной формы

при следующих ограничениях:

Найдем первоначальный опорный план М – задачи.

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

Тогда первоначальный опорный план будет иметь вид:

6. Для отыскания оптимального плана расширенной М – задачи составляют симплекс-таблицу, которая на одну строку больше, чем обычная. В эту (m+2) индексную строку записываются соответствующий коэффициенты при М, входящими в целевую функцию с противоположным знаком.

Проверяется признак оптимальности по (m+2)-й строке и определяется переменная, подлежащая включению в базис. Симплекс-процедуру по (m+2) индексной строке проводят до тех пор, пока по этой строке не будет выполнен признак оптимальности. Затем процесс отыскания оптимального плана продолжают по (m+1) индексной строке.

7. Анализируем оптимальный план М – задачи. Если в этом плане все искусственные переменные равны нулю, т.е. то план X(x 1 , x 2 , …, x n) является оптимальным планом исходной задачи. Если же в оптимальном плане М – задачи хотя бы одна искусственная переменная не равна нулю, т.е. то исходная задача решения не имеет.

Если в процессе решения М – задачи устанавливаем ее не разрешимость, то неразрешима и исходная задача.

Решение контрольного примера.

Найти минимум функции

при следующих ограничениях:

1. От системы неравенств переходим к системе уравнений, вводя в 1-е и во 2-е ограничения дополнительные неотрицательные переменные x 4 и x 5 . Третье уравнение переписываем без изменения:

2. Во 2-е и 3-е уравнения вводим искусственные переменные y 1 и y 2:

3. В линейную форму L(X) вводим сумму y 1 +y 2 с множителем М. Так как задача поставлена на минимум, то множитель М берем со знаком «+».

4. Строим М – задачу. Найти минимум линейной формы

при следующих ограничениях:

5. Решаем эту задачу симплекс-методом. Так как x 4 , y 1 , y 2 являются базисными переменными, то выражаем их через свободные и подставляем в функцию L(X):

6. Строим симплекс-таблицу, которая имеет две индексные строки: в первую, как обычно, записываются коэффициенты Cj, взятые с противоположным знаком, а во вторую – соответствующие коэффициенты при множителе М (тоже с обратным знаком, кроме свободного члена).

Проверяем признак оптимальности по (m+2) индексной строке. Так как задача на минимум, то признак не выполнен, поскольку в столбце x 2 находится положительный элемент 4. Отмечаем этот ключевой столбец стрелкой и , как обычно, выбираем ключевую строку. При выборе ключевой строки получили два одинаковых наименьших значения θ. Чтобы избежать зацикливания, применяем правило Креко. Строки x 1 и y 1 делим на соответствующие элементы ключевого столбца 2 и 4. Результаты от деления читаем слева направо, и ту строку, где первым встретится меньшее число, выбираем за ключевую, т.е.

Отмечаем строку y 1 стрелкой и находим генеральный элемент 4. Затем выполняем обычную симплекс-процедуру и получаем вторую таблицу (таблица 1.2.), в которой опять анализируем (m+2)-ю индексную строку и выбираем столбец x 3 за ключевой.

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

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

Для рассматриваемой задачи можно построить второе оптимальное решение с тем же самым значением L min =24 (таблица 1.2.). Следовательно, задача имеет множество оптимальных планов где

Таблица 1.2.

№ таблиц	Базисные переменные	Свободные члены	X 1	X 2	X 3	X 4	X 5	å	Q
	X 4				-4
Y 1		-1		-2		-1
Y 2								-
L(X)		-1	-2	-2			-5	Min
		4­			-1		-
	X 4		7/2		-3		1/2		-
X 2		-1/4		-1/4		-1/4		-
Y 2
L(X)		-3/2		-3		-1/2		Min
			2­
	X 3		1/2					15/2
X 2						-1/4	27/4	-
X 4						1/2	49/2	18/5
L(X)						-1/2	47/2	Min
	X 3	21/5			-1/10		-1/20	101/20
X 2						-1/4	27/4
X 4	18/5			1/5		-1/10	49/10
L(X)						-1/2	47/2	min

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

x 1

+x 2

+x 3

x 1

+x 2

+x 3

x 1

+x 2

+x 3

≤ = ≥

≤ = ≥

≤ = ≥

×

Предупреждение

Очистить все ячейки?

Закрыть Очистить

Инструкция ввода данных. Числа вводятся в виде целых чисел (примеры: 487, 5, -7623 и т.д.), десятичных чисел (напр. 67., 102.54 и т.д.) или дробей. Дробь нужно набирать в виде a/b, где a и b (b>0) целые или десятичные числа. Примеры 45/5, 6.6/76.4, -7/6.7 и т.д.

Симплекс метод

Примеры решения ЗЛП симплекс методом

Пример 1. Решить следующую задачу линейного программирования:

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

Запишем текущий опорный план:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-3), следовательно в базис входит вектор x при . min (40:6, 28:2)=20/3 соответствует строке 1. Из базиса выходит вектор x 3 . Сделаем исключение Гаусса для столбца x 2 , учитывая, что ведущий элемент соответствует строке 1. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 2, 3, 4 со строкой 1, умноженной на -1/3, 1/6, 1/2, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

Данный опорный план не является оптимальным, так как в последней строке есть отрицательный элемент (-3), следовательно в базис входит вектор x 1 . Определяем, какой вектор выходит из базиса. Для этого вычисляем при . min(44/3:11/3, 62/3:5/3)=4 соответствует строке 2. Из базиса выходит вектор x 4 . Сделаем исключение Гаусса для столбца x 1 , учитывая, что ведущий элемент соответствует строке 2. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 1, 3, 4 со строкой 2, умноженной на 1/11, -5/11, 9/11, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

Симплекс таблица примет следующий вид:

Текущий опорный план является оптимальным, так как в строках 4 под переменными нет отрицательных элементов.

Решение можно записать так: .

Значение целевой функции в данной точке: F (X )=.

Пример 2. Найти максимум функции

Р е ш е н и е.

Базисные векторы x 4 , x 3 , следовательно, все элементы в столбцах x 4 , x 3 , ниже горизонтальной линии должны быть нулевыми.

Обнулим все элементы столбца x 4 , кроме ведущего элемента. Для этого сложим строку 3 со строкой 1, умноженной на 4. Обнулим все элементы столбца x 3 , кроме ведущего элемента. Для этого сложим строку 3 со строкой 2, умноженной на 1.

Симплекс таблица примет вид:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательный элемент (-11), следовательно в базис входит вектор x 2 . Определяем, какой вектор выходит из базиса. Для этого вычисляем при . Все следовательно целевая функция неограничена сверху. Т.е. задача линейного программирования неразрешима.

Примеры решения ЗЛП методом искусственного базиса

Пример 1. Найти максимум функции

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

Матрица коэффициентов системы уравнений имеет вид:

Базисные векторы следовательно, все элементы в столбцах ниже горизонтальной линии должны быть нулевыми.

Обнулим все элементы столбца кроме ведущего элемента. Для этого сложим строку 5 со строкой 3, умноженной на -1.

Симплекс таблица примет вид:

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

Симплекс таблица примет следующий вид:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-3), следовательно в базис входит вектор Определяем, какой вектор выходит из базиса. Для этого вычисляем при соответствует строке 1. Из базиса выходит вектор x 2 . Сделаем исключение Гаусса для столбца x 1 , учитывая, что ведущий элемент соответствует строке 1. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 2, 3, 4 со строкой 1, умноженной на 3/2, -1/10, 3/2, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

Симплекс таблица примет следующий вид:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-13/2), следовательно в базис входит вектор x 3 . Определяем, какой вектор выходит из базиса. Для этого вычисляем при соответствует строке 3. Из базиса выходит вектор x 5 . Сделаем исключение Гаусса для столбца x 3 , учитывая, что ведущий элемент соответствует строке 3. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 1, 2, 4 со строкой 3, умноженной на 5/3, 25/9, 65/9, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

Симплекс таблица примет следующий вид:

Текущий опорный план является оптимальным, так как в строках 4−5 под переменными нет отрицательных элементов.

Решение исходной задачи можно записать так:

Пример 2. Найти оптимальный план задачи линейного программирования:

Матрица коэффициентов системы уравнений имеет вид:

Базисные векторы x 4 , x 5 , x 6 , следовательно, все элементы в столбцах x 4 , x 5 , x 6 , ниже горизонтальной линии должны быть нулевыми.

Обнулим все элементы столбца x 4 , кроме ведущего элемента. Для этого сложим строку 4 со строкой 1, умноженной на -1. Обнулим все элементы столбца x 5 , кроме ведущего элемента. Для этого сложим строку 5 со строкой 2, умноженной на -1. Обнулим все элементы столбца x 6 , кроме ведущего элемента. Для этого сложим строку 5 со строкой 3, умноженной на -1.

Симплекс таблица примет вид:

В строке 5 элементы, соответствующие переменным x 1 , x 2 , x 3 , x 4 , x 5 , x 6 неотрицательны, а число находящийся в пересечении данной строки и столбца x 0 отрицательнo. Тогда исходная задача не имеет опорного плана. Следовательно она неразрешима.