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

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

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

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

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

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

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

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

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

(5.1)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Если в оптимальном решении М-задачи нет искусственных переменных, это решение есть оптимальное решение исходной задачи. Если же в оптимальном решении M-задачи хоть одна из искусственных переменных будет отлична от нуля, то система ограничений исходной задачи несовместна и исходная задача неразрешима.

Симплекс-таблица, которая составляется в процессе решения, используя метод искусственного базиса, называется расширенной . Она отличается от обычной тем, что содержит две строки для функции цели: одна – для составляющей F, а другая – для составляющей M. При составлении симплекс таблицы полагают что исходные переменные являются небазисными, а дополнительные (x n+m) и искусственные (R i)- базисными.

Исходная таблица для "Метода искусственного базиса" имеет следующий вид:

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

Алгоритм метода искусственного базиса.

Подготовительный этап

Приводим задачу ЛП к каноническому виду

F=a 0,1 x 1 +a 0,2 x 2 +...a 0,n x n +b 0 → max

a 1,1 x 1 +a 1,2 x 2 +...a 1,n x n +x n+1 =b 1

a 2,1 x 1 +a 2,2 x 2 +...a 2,n x n +x n+2 =b 2

.........................................

a i,1 x 1 +a i,2 x 2 +...a i,n x n +R i =b i

.......................................

a m,1 x 1 +a m,2 x 2 +...a m,n x n +x n+m =b m

В случае если в исходной задаче необходимо найти минимум - знаки коэффициентов целевой функции F меняются на противоположные a 0,n =-a 0,n . Знаки коэффициентов ограничивающих условий со знаком "≥" так же меняются на противоположные. В случае если условие содержит знак "≤" или "=" - коэффициенты запишутся без изменений. К каждому условияю-неравенству, при переходе к каноническому виду добавляем дополнительную переменную, x n+m , к каждому i-му условию-равенству добавляем искусственную переменную R i .

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

Шаг 1. Проверка на допустимость.

Проверяем на положительность элементы столбца b (свободные члены), если среди них нет отрицательных то найдено допустимое решение (решение соответствующее одной из вершин многогранника условий) и мы переходим к шагу 2. Если в столбце свободных членов имеются отрицательные элементы то выбираем среди них максимальный по модулю - он задает ведущую строку k. В этой строке так же находим максимальный по модулю отрицательный элемент a k,l - он задает ведущий столбец - l и является ведущим элементом. Переменная, соответствующая ведущей строке исключается из базиса, переменная соответствующая ведущему столбцу включается в базис. Пересчитываем симплекс-таблицу согласно .

Если же среди свободных членов есть отрицательные элементы - а в соответствующей строке - нет то условия задачи несовместны и решений у нее нет.

Если после перерасчета в столбце свободных членов остались отрицаетельные элементы, то переходим к первому шагу, если таких нет, то ко второму.

Шаг 2. Проверка на оптимальность.

На предыдущем этапе найдено допустимое решение. Проверим его на оптимальность Если среди элементов симплексной таблицы, находщихся в строках M и F(не беря в расчет элемент b 0 - текущее значение целевой функции и элемент -∑b i) нет отрицательных, то найдено оптимальное решение.

2.1 Положительность строки M

Если в строке M есть отрицательные элементы то решение требует улучшения. Выбираем среди отрицательных элементов строки M максимальный по модулю (исключая -∑b i)

При a i,l >0, b i >0

Пересчитываем симплекс-таблицу по . Если в новой таблице после перерасчета в строке M остались отрицательные элементы переходим к шагу 2

Если в строке M и в столбце свободных членов все элементы положительные, то переходим к шагу 2.2 .

2.2 Положительность строки F

Проверяем на положительность элементы строки F. Если имеются отрицательные элементы (не считая b 0), выбираем среди отрицательных элементов строки F максимальный по модулю.

-a 0,l =min{-a 0,i }

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

b k /a k,l =min {b i /a i,l } при a i,l >0, b i >0

k - cтрока, для которой это отношение минимально - ведущая. Элемент a k,l - ведущий (разрешающий). Переменная, соответствующая ведущей строке (x k) исключается из базиса, переменная соответствующая ведущему столбцу (x l) включается в базис.

Пересчитываем симплекс-таблицу по . Если в новой таблице после перерасчета в строке F остались отрицательные элементы переходим к шагу 2.2

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

Если в строке F и в столбце свободных членов все элементы положительные, то найдено оптимальное решение.

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

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

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

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

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

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