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

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

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

Для многих задач линейного програм­мирования, записанных в форме основной задачи и имеющих опорные планы, среди векторов 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).

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

Примечание

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

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

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

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

Метод искусственного базиса (Симплекс-метод) - Пример 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) Пусть дан базис некоторого опорного решения и соответствующая ему симплекс-таблица . В верхней строке этой таблицы (заголовки столбцов) располагаются свободные переменные, в крайнем левом столбце – базисные переменные; крайний правый столбец – это столбец свободных членов, а самая нижняя строка является строкой целевой функции и называется вектором относительных оценок. Остальное содержимое таблицы - столбцы матрицы ограничений, отвечающие соответствующим столбцам свободных переменных. Координаты вектора относительных оценок находят по правилу: вектор из коэффициентов при базисных переменных в целевой функции скалярно умножить на 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. Строим симплекс-таблицу, соответствующую начальному опорному плану:

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

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

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

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

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

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

Проводя преобразования по методу Жордана-Гаусса, на втором шаге будем иметь оптимальную симплекс-таблицу ВЗ (5.2.2). Вычеркивая столбцы, соответствующие искусственным переменным и последнюю строку, и приписывая новую строку оценок с использованием целевой функции Z 1 (X ), получим начальную симплекс-таблицу для задачи (5.2.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 в двух первых уравнениях-ограничениях и сформулируем вспомогательную задачу:

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

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

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

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

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

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

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

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

Замечания

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

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

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