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

Пусть решаем ЗЛП в виде

В этом случае общая схема симплекс-метода претерпевает некоторые изменения. А именно:

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

2) Если все относительные оценки (нижняя строка этой таблицы) неотрицательны, то построено оптимальное опорное решение.

3) Если существует отрицательная оценка и соответствующий ей столбец (разрешающий) состоит из неположительных элементов, то имеет место неразрешимость целевой функции Z (X ), то есть max Z (X ) ®+¥.

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

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

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

Пусть задана задача ЛП в канонической форме, то есть имеет вид (2.1.1), и в ней отсутствует единичный базис. К этой задаче строим вспомогательную задачу (ВЗ):

Здесь w 1 , w 2 ,…, w m – искусственные переменные. Запишем ограничения в векторном виде: A 1 x 1 +A 2 x 2 +…+A n x n +A n +1 w 1 +…+A n + m w m =B , где , , …, , , , …, , . Таким образом, вектора , , …, образуют единичный базис в R m , и все искусственные переменные соответствующие этим векторам будут базисными. Далее строится обычная симплекс-таблица. Если ВЗ не имеет решения в силу неограниченности целевой функции, то исходная задача также не имеет решения по той же причине. Пусть в результате знакомых по симплекс-методу необходимых преобразований получили оптимальную симплекс-таблицу к ВЗ. Очевидно, что максимальное значение целевой функции ВЗ равно 0, то есть max F =0. Если же maxF <0, то исходная задача ЛП не имеет решения в силу несовместности системы ограничений. Предположим, что max F =0. Тогда возможны такие ситуации:

1) все искусственные переменные стали свободными и были исключены из таблицы. В этом случае вычеркиваем столбцы, соответствующие искусственным переменным и последнюю строку. Вместо неё приписываем новую строку оценок, но с использованием исходной целевой функции Z (X ). Тем самым получена начальная симплекс-таблица для исходной задачи ЛП, к которой применяем симплекс-метод;

2) в оптимальном решении ВЗ хотя бы одна искусственная переменная осталась базисной. Тогда:

а) либо все числа в строках, соответствующих оставшимся базисным искусственным переменным, равны 0;

б) либо есть хоть одно отличное от 0.

В первом случае, поступаем также как и пункте 1). Во втором, выбираем любой ненулевой элемент в качестве ведущего и делаем шаг жордановых исключений. Через конечное число шагов мы придем или к пункту 1), или к пункту 2)а).

Заметим, что если среди векторов A j , j =1,2,…,n , были вектора, которые могли бы войти в базис, то искусственные переменные вводят только в те уравнения системы ограничений, в которых отсутствует базисная переменная.

Пример. Максимизировать функцию Z =x 1 +2x 2 -2x 3 при ограничениях

Решение. Преобразуем исходную задачу линейного программирования к канонической (см. (2.1.1). Для этого введём в ограничения дополнительные неотрицательные переменные. А именно, в первое неравенство – переменную x 4 со знаком «+», во второе – x 5 со знаком «-» (см. §2.2). Система ограничений примет вид:

Эту систему запишем в векторной форме: A 1 x 1 +A 2 x 2 +A 3 x 3 +A 4 x 4 +A 5 x 5 =B , где

Очевидно, что в данной системе ограничений отсутствует единичный базис. Это означает, что среди векторов A j нет трёх необходимых единичных векторов, которые должны образовывать базис в R 3 . Однако заметим, что вектор A 4 является частью базиса. Ему соответствует базисная переменная x 4 . Необходимо найти ещё два единичных вектора. Для этого применим метод искусственного базиса. Введём искусственные переменные в те уравнения ограничений, в которых не присутствует базисная переменная x 4 и построим следующую вспомогательную задачу (ВЗ):

F =-w 1 -w 2 ®max

где w 1 , w 2 – искусственные переменные. Система ограничений ВЗ в векторном виде имеет вид: A 1 x 1 +A 2 x 2 +A 3 x 3 +A 4 x 4 +A 5 x 5 +A 6 w 1 +A 7 w 2 =B , где вектора A j , j =1,2,3,4,5 определяются также, как и выше, а и . Таким образом, вектора A 4 , A 6 , A 7 образуют базис в R 3 и им соответствуют базисные переменные (БП) – x 4 , w 1 , w 2 . Все остальные переменные, а именно x 1 , x 2 , x 3 , x 5 объявляются свободными (СП). Далее к ВЗ применяем обычный симплекс-метод. Как и раньше, см. §5.1, начальный опорный план получается, если присвоить свободным переменным значения, равные нулю. При этом базисные переменные принимают значения, равные числам в соответствующей строке столбца свободных коэффициентов В , то есть x 1 =x 2 =x 3 =x 5 =0¸ а x 4 =8, w 1 =4, w 2 =12. Строим симплекс-таблицу, соответствующую начальному опорному плану:

СП БП.	x 1	x 2	x 3	x 5	B
x 4		-3
w 1				-1
w 2		-2
F	-4		-3		-16

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

СП БП.	w 1	x 2	x 3	w 2	B
x 4	-0,5	-3	-0,5	-0,5
x 1	0,25		0,75	0,25
x 5	-0,75	-2
F

Эта таблица будет оптимальной для ВЗ. При этом все искусственные переменные стали свободными и max F =0. Вычеркивая столбцы, соответствующие искусственным переменным и последнюю строку, и приписывая новую строку оценок с использованием исходной целевой функции Z (X ), получим начальную симплекс-таблицу для исходной задачи ЛП:

СП БП.	x 2	x 3	B
x 4	-3	-0,5
x 1		0,75
x 5	-2
Z	-2	2,75

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

Пример. Минимизировать функцию при ограничениях

Если ввести дополнительные неотрицательные переменные , , , , и перейти к задаче на нахождение максимума целевой функции, исходная задача примет вид:

Базисное решение (допустимый план) будет иметь вид: , а , , w 1 =10, w 2 =5. Строим симплекс-таблицу к ВЗ, соответствующую начальному опорному плану:

СП БП.	x 1	x 2	x 3	x 4	B
w 1			-1
w 2				-1
x 5
x 6	-1
F	-1	-1			-15

Проводя преобразования по методу Жордана-Гаусса, на втором шаге будем иметь оптимальную симплекс-таблицу ВЗ (5.2.2). Вычеркивая столбцы, соответствующие искусственным переменным и последнюю строку, и приписывая новую строку оценок с использованием целевой функции Z 1 (X ), получим начальную симплекс-таблицу для задачи (5.2.1).

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

Для многих задач линейного програм­мирования, записанных в форме основной задачи и имеющих опорные планы, среди векторов P j не всегда есть m единичных.

Рассмотрим такую задачу:

Пусть требуется найти максимум функции

F = c 1 x 1 + c 2 x 2 + ……+ c n x n (1)

при условиях

……………………………………… (2)

где b i  0 (i =l, m), m <.>n и среди векторов P 1 , P 2 , …, P n нет m единичных.

Определение . Задача, состоящая в определении максимального значения функции

F = c 1 x 1 + c 2 x 2 + ……+ c n x n -М x n +1 - …- М x n + m (3)

при условиях

……………………………………… (4)

где M - некоторое достаточно большое положительное число, конкретное значение которого обычно не задается, называется расширенной задачей (М-задачей) по отношению к задаче (1) - (2).

Расширенная задача имеет опорный план

Х=(0; 0; ...; 0; b 1 ; b 2 ; ...;b m).

определяемых системой единичных векторов P n +1 ; Р п+2 , … Р п+т , образующих базис m-ro векторного пространства, который назы­вается искусственным. Сами векторы, так же как и переменные x n + i (i =l, m ), называются искусственными. Так как расширенная задача имеет опорный план, то ее решение может быть найдено симплексным методом.

Теорема Если в оптимальном плане X*=(x* 1 , x * 2 , ...; x * n , x * n +1 ; ...; x * n + m) расширенной задачи (3) - (4) значения ис­кусственных переменных x * n + i =0 (i =1, m ), то X*=(x* 1 , x * 2 , ...; x * n) является оптимальным планом задачи (1) - (2).

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

Значения индексной строки ∆ 0 , ∆ 1 , …, ∆ n состоят из двух частей, одна из кото­рых зависит от M, а другая - нет. Заполняют симплекс - таблицу, которая содер­жит на одну строку больше, чем обычная симплексная табли­ца. При этом в (m+2)-ю строку помещают коэффициенты при M, а в (m+1)-ю – слагаемые, не содержащие M. При переходе от одного опорного плана к другому в базис вводят вектор, соответствующий наибольшему по абсолютной величине отрицательному числу (m+2)-й строки. Искусствен­ный вектор, исключенный из базиса, в следующую симплекс-таблицу не записывают. Пересчет симплекс-таблиц при переходе от одного опорного плана к другому производят по общим правилам симплексного метода.

Итерационный процесс по (m+2) -и строке ведут до тех пор, пока:

либо все искусственные векторы не будут исключены из базиса;

либо не все искусственные векторы исключены, но (m+2)-я строка не содержит больше отрицательных элементов в индексах ∆ 1 , …, ∆ n .

В первом случае базис отвечает некоторому опорному пла­ну исходной задачи и определение ее оптимального плана про­должают по (m+1)-й строке.

Во втором случае, если значение ∆ 0 отрицательное, исходная задача не имеет решения; если же ∆ 0 =0, то найденный опорный план исходной задачи является вырожденным и базис содержит по крайней мере один из векторов искусственного базиса.

Этапы нахождения решения задачи (1) - (2)

методом искусственного базиса:

Составляют расширенную задачу (3) - (4).

Находят опорный план расширенной задачи.

С помощью обычных вычислений симплекс-метода исклю­чают искусственные переменные из базиса. В результате либо на­ходят опорный план исходной задачи (1) - (2), либо уста­навливают ее неразрешимость.

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

Пример.

Найти минимум функции F = - 2x 1 + 3x 2 - 6x 3 - x 4

при ограничениях:

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

x 1 +2x 2 +4x 3 ≤22

x 1 -x 2 +2x 3 ≥10

x i ≥0, i =1,4

Решение.

Запишем данную задачу в форме основной задачи: найти максимум функции F = 2x 1 - 3x 2 + 6x 3 + x 4

при ограничениях:

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

x 1 +2x 2 +4x 3 +x 5 =22

x 1 -x 2 +2x 3 - x 6= 10

x i ≥0, i =1, 6

В системе уравнений последней задачи рассмотрим векторы из коэффициентов при неизвестных:

Среди векторов P 1 , Р 2 , … P 6 только два единичных (P 4 и P 5). Поэтому в левую часть третьего уравнения системы ограничений задачи добавим дополнительную неотрицательную переменную х 7 и рассмотрим расширенную задачу, состоящую в максимизации функции

F = 2x 1 - 3x 2 + 6x 3 + x 4 - Мх7

при ограничениях:

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

x 1 +2x 2 +4x 3 +x 5 =22

x 1 -x 2 +2x 3 - x 6 +x 7= 10

Расширенная задача имеет опорный план Х=(0; 0; 0; 24; 22; 0; 10), определяемый системой трех единичных векторов: P 4 , P 5 , Р 7 .

Понятие двойственной (соапряженной) задачи линейного программирования.

Правила построения двойственной задачи.

С каждой задачей линейного программирования (ЗЛП), которая называется двойственной задачей (или сопряженной) по отношению к исходной задаче, которая называется прямой.

Двойственная задача строится по отношению к прямой задаче, записанной в стандартной форме:

F=c 1 x 1 +c 2 x 2 +…+c n x n  max (3.6)

a 11 x 1 +a 12 x 2 +…+a 1n x n ≤ b 1 ,

a 21 x 1 +a 22 x 2 +…+a 2n x n ≤ b 2 ,

………………………………

a k1 x 1 +a k2 x 2 +…+a kn x n ≤ =b k , (3.7)

a k+1,1 x 1 +a k+1,2 x 2 +…+a k+1,n x n =b k+1 ,

………………………………

a m1 x 1 +a m2 x 2 +…+a mn x n =b m ,

x j ≥ 0, , l ≤ n (3.8)

Задача, состоящая в нахождении минимального значения функции

L = b 1 y 1 + b 2 y 2 + … + b m y m (3.9)

при условиях

a 11 y 1 + a 12 y 2 +…+ a m1 y m ≥ c 1

a 21 y 1 + a 22 y 2 +…+ a m2 y m ≥ c 2

………………………………

a 1 l y 1 + a 2 l y 2 +…+ a m l y m ≥ c l (3.10)

a l +1,1 y 1 + a l +1,2 y 2 +…+ a l +1,m y m = c l+1

………………………………

a m1 y 1 + a m2 y 2 +…+ a mn y m = c m

y i ≥ 0, , k ≤ m (3.11)

называется двойственной по отношению к задаче (3.6) – (3.8).

Правила построения двойственной задачи приведены в таблице:

Структурные характеристики ЗЛП	Задача линейного программирования
		Двойственная
1. Целевая функция	Максимизация (max)	Минимизация (min)
2. Количество переменных	n переменных	Равно количеству ограничений прямой задачи (3.7), y i , т.е. m
3. Количество ограничений	m ограничений	Равно количеству переменных прямой задачи x j , , т.е n
4. Матрица коэффициентов в системе ограничений
5. Коэффициенты при переменных в целевой функции	c 1 ,c 2, …,c n	b 1 ,b 2, …,b m
6. Правая часть системы ограничений	b 1 ,b 2, …,b m	c 1 ,c 2, …,c n
7. Знаки в системе ограничений	а) x j ≥ 0- условие неотрицательности	j-е ограничение имеет знак «≥»
	б) на переменную x j не наложено условие неотрицательности	j-е ограничение имеет знак «=»
	в) i-е ограничение имеет знак «≤»	переменная y i ≥0
	г) i-е ограничение имеет знак «=»	на переменную y i не наложено условие неотрицательности

Примечание

Прямая задача на максимум и двойственная на минимум являются взаимодвойственными задачами. Поэтому можно считать задачу (3.9) – (3.11) прямой ЗЛП, а задачу (3.6) – (3.8) – двойственной к ней задачей. При этом правила построения двойственной ЗЛП сохраняются, лишь с тем изменением, что исходной считается задача на минимум.

Если исходная задача решается на max (min), а в системе ограничений) i -е (j -е) ограничение имеет знак «≤» («≥»), то для построения двойственной задачи необходимо:

а) либо домножить обе части i -го (j -го) неравенства на (-1) и поменять знак на «≤» («≥»)

б) либо привести i -е (j -е) ограничение к равенству путем введения дополнительной переменной x n+ i ≥0

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

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

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

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

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

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

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

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

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

Пусть все /? > 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 т и лежит в диапазоне }