Методические указания к исследовательской лабораторной работе по дисциплине “Математические основы кибернетики” Тема: Симплекс-алгоритм решения задачи линейного программирования (ЛП)

Методические указания

к исследовательской лабораторной работе по дисциплине

“Математические основы кибернетики”

Тема: Симплекс-алгоритм решения задачи линейного программирования (ЛП).

Вопросы для исследования:

1. Освоить симплекс-алгоритм решения задачи ЛП.

2. Рассмотреть шаги симплекс - алгоритма, проанализировать его свойства, освоить правила остановки алгоритма и признаки неограниченности решения задачи ЛП.

3. Рассмотреть примеры решения задачи ЛП с помощью симплекс - алгоритма.

1. Необходимые теоретические сведения

1.1. Постановка задачи

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

Пусть задача состоит в нахождении неотрицательного n-мерного вектора x = [x1, x2, ...,xn]т доставляющего экстремум (для конкретности - максимум) линейному критерию:

I = с0 + cтx =c1 x1 +c2 x2 + ... +cn xn (1)

на линейной системе ограничений:

AТx = B (2)

x ³ 0 (3)

Здесь c = [c1, c2, ...,cn]т - n- мерный вектор коэффициентов критерия;

с0 - скаляр;

A - матрица размерности r*n , элементами которой являются коэффициенты, входящие в систему ограничений;

B - вектор с неотрицательными элементами (правая часть ограничений размерности r).

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

НЕ нашли? Не то? Что вы ищете?

В скалярной форме ограничения (2)...(3) имеют вид:

a 11 x1 + a 12 x2 + ... +a 1nx n = b 1

a r1 x1 + a r2 x2 + ... +a r nx n =b r

xi ³ 0 " i=1...n (4)

В системе равенств (4) число переменных (n) всегда больше числа равенств (r), и поэтому имеется (k=n-r) свободных переменных, которые могут принимать любые значения. Ранг (4) равен r (по постановке задачи предполагается, что допустимое решение задачи существует). Из бесконечного числа решений системы (4) выделим т. н. базисное, т. е. такое, в котором все свободные переменные равны нулю.

Базисом для (4) называется набор несвободных переменных.

Упорядочим все переменные (элементы вектора x) таким образом, чтобы сначала были перечислены все свободные переменные:

x1, x 2, . . . , x k, x k+1, x k+2, ... , x n

k – число свободных переменных;

r – число базисных переменных;

k + r = n – общее число переменных.

Пусть базисное решение (4) (т. е. такое, в котором x1, x 2, . . . , x k равны нулю) легко найти. Так получается, если ограничения в задаче распределения ресурсов преобразуются в равенства введением дополнительных переменных по одному в каждое из исходных ограничений-неравенств - например:

a 11 x1 + a 12 x2 + ... +a 1 kx k + 1×x k+1 +0×x k++0× x n = b 1

a 21 x1 + a 22 x2 + ... +a 2 kx k + 0×x k+1 +1×x k++0× x n = b 2

a r1 x1 + a r2 x2 + ... +a r nx n + 0×x k+1 +0×x k++1× x n = br (5)

Мы видим, что если положить x1, x 2, . . . , x k нулевыми, то элементарно находятся x k+1= b 1, x k+2= b 2, ... , x n= b r.

Обратите внимание: если бы Вы переписали систему (5) в векторно-матричной форме, то “сомножителем” перед искомым базисным вектором xБ Т = [x1, x 2, . . . , x k]т служила бы единичная матрица E r, r размерности r*r:

E*xБ =B, откуда xБ =B.

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

1. на каждом шаге работы алгоритма заменялась только одна из переменных базиса на небазисную (свободную) переменную. Эта позиция позволит сохранить простоту нахождения базисного решения (оно по-прежнему должно быть очевидным);

2. смена базиса должна быть целенаправленной: такой, чтобы на каждом шаге работы алгоритма критерий оптимальности (1) обязательно возрастал;

3. на каждом шаге работы алгоритма должно быть видно, достигнуто ли оптимальное решение;

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

Данная задача решается с помощью симплекс - алгоритма, разработанного американским математиком Дж. Данцигом.

1.2. Схема симплекс - алгоритма

1. Выразим из (4) базисные переменные через небазисные:

a 1, k+1 xk+1 + a 1, k+2 x k+2 + ... +a 1 nx n = b 1 - a 11 x1 - a 12 x2 - ...-a 1 kx k

a 2, k+1 xk+1 + a 2, k+2 x k+2 + ... +a 2nx n = b 2 - a 21 x1 - a 22 x2 - ...-a 2 kx k

a r, k+1 xk+1 + a r, k+2 x k+2 + ... +a r nx n = b r - a r1 x1 - a r2 x2 - ...-a r kx k (6)

2. В векторной форме (1.6.6) можно записать так:

AБ xБ = B - AНБ xНБ (7)

где xБ – базисный r-мерный вектор с элементами x k+1, x k+2, ... , x n ;

AБ - матрица коэффициентов размерности r*r при базисных переменных с элементами ai, k+v, i=1,...,r; v=1,...,n-k;

xНБ - k-мерный вектор свободных переменных с элементами x1,x2,...,xk;

AНБ - матрица коэффициентов размерности r*k при базисных переменных с элементами ai, j, i=1,...,r; j=1,...,k;

B - r-мерный вектор с элементами b 1, b 2, ... , b r.

Из (7), умножая слева на АБ-1, которая обязательно существует, поскольку по постановке задачи предполагается наличие допустимого решения, найдем формулу, выражающую базис через свободные переменные:

xБ = АБ-1 B - АБ-1 AНБ xНБ (8)

3. Представим себе, что вычисления в (8) выполнены. Тогда запишем в скалярной форме:

xk+1 = b1 -(a11 x1 +a 12 x2 + ...+ a 1 kx k)

xk+2 = b2 -(a21 x1 +a 22 x2 + ...+ a 2 kx k)

xn = br -(a r1 x1 +a r 2 x2 + ...+ a r kx k) (9)

4. Из (9) сразу видно, чему равны переменные базиса в базисном решении, в котором по определению x1, x2, ... , x k - нулевые:

xk+1 = b1

xk+2 = b2

xn = br (10)

Поэтому, если бы нам было известно, что оптимальное решение найдено (и дальнейшая корректировка состава базисных переменных нецелесообразна), мы сразу же “прочли” бы значения оптимального базиса из (10).

5. Для установления целесообразности смены базиса выразим критерий оптимальности (1) также через свободные переменные. Из формулы будет видно, станет ли увеличиваться (улучшаться) критерий, если свободные переменные будут ненулевыми (естественно, положительными по постановке задачи ЛП).

Выделим в формуле для критерия группы слагаемых с базисными и свободными переменными:

I = (c0 + c1 x1 + c2 x2 + . . . + c k x k ) + (c k+1 x k+1 + c k+2 x k+2 + . . . +cn xn) =

(свободные переменные) (базисные переменные)

= c0 + cНБТ*xНБ + cБТ *xБ (11)

где cНБТ - строка 1*k, элементами которой являются c1 ,c2 , . . . , c k;

cБТ - строка 1*r, элементами которой являются c k+1, c k+2, . . .,cn.

Подставляя (8) в (11), найдем:

I = c0 + cНБТ xНБ + cБТ (АБ-1 B - АБ-1 AНБ xНБ) =

= (c0+ cБТ АБ-1 B )+( cНБТ - cБТ АБ-1 AНБ) xНБ (12)

Выполнив вычисления в (12), выразим критерий через свободные переменные: g

I = g 0 + g1 x1 + g 2 x2 + . . . + g k x k (13)

Из (13) видно:

a) если имеется хотя бы один коэффициент gi, i Î[1,...,k], то введение свободной переменной (с этим же индексом) xi в базис целесообразно: поскольку при этом переменная xi станет больше нуля, произойдет увеличение (улучшение) критерия оптимальности;

b) если договориться, что на каждом шаге работы алгоритма вводу в базис подлежит только одна из свободных переменных, то можно заметить, что локальное (т. е. на данном шаге работы алгоритма) улучшение критерия будет наибольшим, если мы введем в базис переменную, которая входит в (13) с наибольшим положительным коэффициентом;

c) если же все коэффициенты gi, i Î[1,...,k], неположительные, то изменение состава базиса Нецелесообразно: положительные значения свободных переменных приведут к уменьшению (ухудшению, или, по крайней мере, к сохранению уже достигнутого при “старом” базисе) значения критерия.

Перечисленные положения определяют:

a. правило остановки алгоритма (признак оптимальности - все коэффициенты gi, i Î[1,...,k] при свободных переменных должны быть неположительными;

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

6. Традиционно симплекс-алгоритм интерпретируется симплекс - таблицей. Исходная симплекс-таблица представлена в табл.1. Данные, подлежащие вводу в таблицу в качестве исходных, помещены в верхних левых углах клеток. Нижние правые углы заполняются по мере корректировки базиса; пока не обращайте на них внимания (как и на цифры в верхнем правом углу, и на выделенные столбцы, строки и клетку) - они будут пояснены ниже.

Правила заполнения симплекс-таблицы:

1. в верхней строке записывается перечень свободных переменных;

2. в левом столбце во второй клетке записывается наименование “Критерий”;

3. в левом столбце, начиная с третьей клетки, записывается перечень базисных переменных;

4. в столбце, втором слева, во второй клетке записывается постоянная часть критерия (значение, достигнутое к данному шагу работы алгоритма: g0);

5. в этом же столбце, начиная с третьей клетки, записываются значения базисных переменных, которые они приняли на данном такте в базисном решении (т. е. таком, в котором все свободные переменные равны нулю): b1,..., b r;

6. во второй строке в клетках, начиная с третьей, записываются коэффициенты, с которыми свободные переменные входят в формулу критерия (13): g1,..., g k;

7. в третьем и всех последующих столбцах, начиная с третьей строки, записываются значения коэффициентов ai s, i=1, ... , n-k; s=1, ... , k, с помощью которых базисная переменная x k+ i выражается через свободные x s.

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

Правила чтения симплекс-таблицы:

a) на данном шаге работы алгоритма достигнуто значение критерия, указанное во второй клетке второго столбца (g0);

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

(xk+i = b i );

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

7. Изменения содержимого клеток таблицы при переходе к следующему шагу симплекс - алгоритма.

a) Пусть наибольший положительный коэффициент в строке критерия (вторая строка табл.1, начиная с третьей клетки) равен gj. Соответственно xj -претендент на ввод в новый состав базисных переменных. Столбец симплекс-таблицы, относящийся к переменной-претенденту, называют разрешающим столбцом (в табл. 1 выделен).

b) При увеличении xj (благодаря положительности gj) критерий будет улучшаться. Но рост xj ограничивается требованием сохранения неотрицательности всех “старых” базисных переменных. Из (1.6.9) получим (помня, что все “старые” небазисные переменные, кроме xj, по-прежнему равны нулю при переходе к новому базису) r вариантов предельно больших значений xj:

xk+1 = b1 -a1j xj (1) = 0 ® xj (1) = b1 / a1 j

xk+2 = b2 -a2j xj (2) = 0 ® xj (2) = b2 / a2 j

...

xn = br -a r j xj (r ) = 0 ® xj (r) = br / ar j (14)

Таблица 1. Форма исходной симплекс-таблицы.

Свободные Базисные переменные		x1	…	xs	…	xj ® xk+i	…	xk
Критерий I	g0 5 +gj / a i j*bi	g1 6 -gj / a i j *a i 1	…	gs 6	…	gj 3	…	gk 6
x k+1	b1 4 -a1 j / a i j *b i	a11 4 -a1j / a i j * a i1	…	a1s 4	…	a1j 3	…	a1k 4
…	…	…	…	…	…	…	…	…
x k+l	bl 4 -a l j /a i j *bi	al1 4 -a l j /a i j *a i 1	…	a1s	…	a l j 3 -a l j / a i j	…	al k 4
…	…	…	…	…	…	…	…	…
x k+i xj	bi 2 bi / a i j	ai1 2 -a i1/ a i j	…	2 - a i s/ a i j		aij 1 1/ aij	…	2 -a i k / a i j
…	…	…	…	…	…	…	…	…
x n	br 4 -a r j /a i j *b i	ar1 4 -a r j / ai j *a i 1	…	ars 4	…	arj 3	…	ar k 4

Соотношения типа (14) можно записать только в том случае, если al j положительны - иначе неотрицательность переменных в левой части (14) не нарушится даже при xj ® ¥. Поэтому:

1. если на некотором шаге работы симплекс - алгоритма получится, что все al i неположительны (al i £ 0 " lÎ [1, r]), то критерий в задаче неограничен, вводимая в базис переменная стремится к бесконечности, что свидетельствует о просчетах разработчика на этапе постановки задачи;

2. в противном случае предельно большим значением переменной xj, вводимой в базис, является

bi /ai j= min (b1 / a1j, ... , bl / al j, . . . , br / ar j ) (15)

lÎJ++

где J++ - множество индексов положительных коэффициентов al j.

c) Индекс i в соотношении (15) идентифицирует переменную xk+i, препятствующую росту xj (и, следовательно, росту критерия). Эту переменную целесообразно вывести из базиса и заменить на xj.

d) Строка симплекс-таблицы, соответствующая x k+i, называется разрешающей строкой (выделена в табл. 1).

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

f) Для вывода соотношений, позволяющих предложить правила трансформации симплекс-таблицы при последовательных шагах алгоритма, основаны на технике Жордановских исключений [1]:

1) состав базиса корректируется на каждом шаге только по одной переменной;

2) выразим “новую” базисную переменную xj через “новый” состав свободных переменных, в котором сохранены все “старые” переменные, кроме xj (которая заменяется на xk+i ); используем i-ю строку (9):

xk+i = bi -(ai 1 x1 + ... +a i, j -1 xj -1 + a i j xj + a i, j +1 xj +1...+ a i kx k)

Отсюда получим:

xj = bi /a i j - ([ai 1 /a i j]× x1+ ... +[ai, j -1 /a i, j - 1]× xj -1 + [1/a i j]× x k + i + ...+

+ [ai, j +1 /a i, j + 1] × xj + 1 + ... + [ai k /a i j]× x k) (16)

Формула (16) будет использована для формирования правил 1 и 2 трансформации симплекс-таблицы, см. ниже.

3) выразим остальные “старые” базисные переменные xk+l "lÎ [1,r; l¹i] через новый состав свободных переменных.

xk+i = bi -(ai 1 x1 + ... +a i, j -1 xj -1 + a i j xj + a i, j +1 xj +1...+ a i kx k)

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

xk+l =[bl + {- al j / a i j }×bi ] - ([a l 1 + {- al j / a i j }×a i1 ] × x1 + ... +

+[a l, j -1 + {- al j / a i j }×a i, j - 1] × xj - 1 + {- al j / a i j } × x k + i + ... +

+ [a l, j +1 + {- al j / a i j }×a i, j + 1] ×xj +1 +…+

+[a l k + {- al j / a i k}×a i k ] × xk) (17)

4) Аналогично записывается формула, связывающая значение критерия, выраженного через “новые” свободные переменные (технология выкладок – такая же, как и для формулы (17)). Из исходной формулы (13)

I = g 0 + g1 x1 + ... + g j-1 xj -1 + g j xj + g j +1 xj +1 + . . . + g k x k

после подстановки (16) вместо xj получим:

I = (g 0 - {- g j /a i j }× bi ) + (g 1 + {- g j /a i j }× ai 1 ) × x 1+ ... +

+ (g j -1 + {- g j /a i j }× ai, j -1 ) × x j - 1 + { - g j /a i j } × x k + i + .... +

+ (g j +1 + {- g j /a i j }× ai, j +1 ) ×x j + 1 + ... +(g k + {- g j /a i j }× ai k ) × x (18)

Выноска 2: Трансформация коэффи-циентов в других столбцах (кроме разрешающего)

g) Формулы (позволяют установить правила

трансформация симплекс-таблицы для перехода к следующему

шагу алгоритма, которые включают последовательные фазы

(их номера указаны в табл.1 в верхних правых углах клеток):

1) фаза 1: трансформация генерального элемента по

правилу 1:

[новый генеральный элемент] = 1 / [старый генеральный элемент]

2) фаза 2: трансформация элементов разрешающей строки по

правилу 2

[новый элемент строки, кроме генерального] = [старый элемент строки] / [старый генеральный элемент]

3) фаза 3: трансформация элементов разрешающего столбца по правилу 3:

[новый элемент столбца, кроме генерального] = (минус) [старый элемент строки] / [старый генеральный элемент]

4) фаза 4: трансформация элементов строк системы ограничений - начиная с третьей - по правилу 4:

[новый элемент клетки, кроме клеток разрешающих строки и столбца] = [старый элемент клетки]+[элемент в НОВОМ разрешающем столбце в той же строке, что и рассматриваемая клетка]*[элемент в СТАРОЙ разрешающей строке в том же столбце, что и рассматриваемая клетка]

5) фаза 5: трансформация коэффициента критерия в зависимости от новой свободной переменной (в клетке второй строки в разрешающем столбце) по правилу 5:

Правило 5 полностью совпадает с Правилом 3, поэтому фазу 5 можно выполнять с цикле с фазой 3.

[новый элемент клетки] = (минус)[старый элемент клетки] / [старый генеральный элемент]

6) фаза 6: трансформация значения критерия, достигнутого к текущему шагу (в клетке второй строки второго столбца) - по правилу 6:

[новый элемент клетки второй строки второго столбца] =

= [старый элемент клетки]+[элемент в НОВОМ разрешающем столбце во второй строке]*[элемент в СТАРОЙ разрешающей строке во втором столбце]

7) фаза 7: трансформация значения коэффициентов зависимости критерия от свободных переменных (в клетках второй строки, начиная с третьего столбца) - по правилу 7:

Правило 7 по форме НЕ отлиается от Правила 4, поэтому вычисления можно выполнять с цикле с фазой 4.

[новый элемент клетки второй строки, начиная с третьего столбца]=

= [старый элемент клетки]-[элемент в НОВОМ разрешающем столбце во второй строке] *[ элемент в СТАРОЙ разрешающей строке в том же столбце, что и рассматриваемая клетка]

1.3. Метод нахождения допустимого решения с помощью симплекс– алгоритма. Метод искусственного базиса

Алгоритм и правила, изложенные в п. 1.2, применимы только тогда, когда известно одно из допустимых (не обязательно оптимальных) решений. Имеется большое число прикладных задач, в которых допустимое решение не является очевидным (и вообще может не существовать из-за несовместности ограничений). Формально такие задачи имеют (наравне с ограничениями типа “£” при условии неотрицательности правой части) ограничения типа “³” также при неотрицательной правой части: в отличие от системы ограничений (2) требуется найти вектор x = [x1, x2, ...,xn]т, доставляющий максимум критерию (1) на системе ограничений общего вида:

A1 Тx ³ B1 (19а)

A2 Тx £ B2 (19б)

x ³ 0

где A1, A2 – матрицы размерности m1 и m2 соответственно;

B1, B2 – m1 и m2 – мерные векторы с неотрицательными элементами.

Попытка преобразовать систему (19) в равенства введением вспомогательных переменных x(1) и x(2) соответственно не помогает найти очевидное решение:

A1 Тx - x(1) = B1

A2 Тx + x(2) = B2 (20)

видно что очевидный базис{ x(1) , x(2) } недопустим, т. к. x(1) = - B1 имеет отрицательные (недопустимые по постановке задачи) значения.

Эффектным приемом, который лежит в основе метода искусственного базиса, задача с ограничениями (19) подменяется “искусственной” задачей, характерными особенностями которой являются:

1. задача всегда имеет решение;

2. одно из решений является очевидным, поэтому оптимальное решение может быть найдено симплекс – алгоритмом;

3. задача устроена таким образом, чтобы по самой своей постановке “препятствовать” ее отличиям от исходной. Тогда:

a) если в точке оптимума отличия отсутствуют, то решение “искусственной” задачи - такое же, как было бы у исходной задачи (если бы мы искали оптимум исходя из ее допустимого решения);

b) если же в точке оптимума различия между искусственной и исходной задачами сохраняются, то это свидетельствует о том, что решение исходной задачи отсутствует.

Применительно к задаче оптимизации критерия (1) на системе ограничений (20) данный прием имеет следующую форму:

a) В систему ограничений вводятся “искусственные” переменные – неотрицательный вектор y=[y1, y2,…,ym1]T размерности m1 – по числу ограничений типа “³”. Ввод этих переменных не изменяет ранга системы ограничений (20) (т. к. общее число ограничений – равенств не изменилось). Система ограничений примет вид:

A1 Тx - x(1) + y = B1

A2 Тx + x(2) = B2 (21)

b) Эта система имеет очевидный базис y = B1 и x(2) = B2, который в отличие от (20), является допустимым: y³0 и x(2) ³0 при выполнении функциональных ограничений (21).

c) Модифицируем критерий оптимальности (1) так, чтобы оптимизационная задача “не хотела” никаких других значений “искусственных” переменных y, кроме нулевых. Мы видим, что при y=[0] системы ограничений (20) и (21) совпадают. Модификаций критерия сводится к введению штрафа за ненулевые значения “искусственных” переменных y – такого, чтобы, во-первых, критерий остался бы линейным (иначе нельзя будет рассматривать “искусственную” задачу как задачу ЛП) и, во-вторых, чтобы, при нулевых значениях “искусственных” переменных y модифицированный критерий совпадал бы с критерием (1) исходной задачи. Исходя из этого, выберем модифицированный критерий Im в форме:

Im = {Критерий (1) исходной задачи} - {штраф за ненулевые yi }

Im = I - M× (y1 + y1 + ... + ym

где M>> 0 –произвольная большая положительная константа.

d) Мы видим, что (поскольку ставится задача максимизации (22), то если не принимать во внимание ограничения) самыми лучшими значениями yi являются нулевые (и именно при этом “искусственная” и исходная задачи тождественны).

e) Если же в результате оптимизации (22) получится ненулевой вектор y, то это означает отсутствие решений у исходной задачи. Значения ненулевых элементов в векторе y показывает степень несовместности ограничений (и, если задача используется для прикладных целей, дает материал для поиска мероприятий, необходимых для “расшивки” несовместности).

1.4. Пример построения симплекс-таблицы и один шаг ее трансформации

Постановка задачи: найти x1, x2 , доставляющие максимум критерию

I = x1 +0.5 x2

при условиях:

x1 + x2 £ 5

2x1 + 5x2 £ 20

10x1 + 4x2 £ 40

x1, x2 ³ 0

Шаг 1: преобразование системы ограничений в строгие равенства путем введения дополнительных переменных, x4, x5 ³ 0:

x1 + x2 + 1× x3 + 0× x4 + 0× x5 = 5

2x1 + 5x2 + 0× x3 + 1× x4 + 0× x5 = 20

10x1 + 4x2 + 0× x3 + 0× x4 + 1× x5 = 40

xi, ³ 0 " i=[1, 5]

Шаг 2: выбор исходного (очевидного) базиса:

отсюда x3 = 5, x4 = 20, x5 = 40

Заполняем симплекс-таблицу:

Таблица 2а. Трансформации симплекс-таблицы

Свободные Базисные		x1	x2
Критерий I	0	1	0.5
x3	5	1	1
x4	20	2	5
X5	40	10	4

Вопрос: Как прочесть симплекс-таблицу?

Ответ:

1. значение критерия на данном такте расчетов I = 0 (2-я клетка 2-й строки);

2. формула зависимости критерия от свободных переменных I = 1×x1 +0.5 x2 (коэффициенты зависимости - во 2-й строке под обозначениями свободных переменных);

3. значения базисных переменных x3 = 5, x4 = 20, x5 = 40 (прочтём во 2-м столбце против обозначений базисных x3 , x4, x5 );

4. формулы зависимости базисных переменных от свободных:

a) x3 = 5 - 1×x1 -1× x2 (коэффициенты - в строке, соответствующей x3);

b) x4 =×x1 -5× x2 (коэффициенты - в строке, соответствующей x4);

c) x5 =×x1 -4× x2 (коэффициенты - в строке, соответствующей x5);

d) (знак “-” подразумевается и не записывается).

Вопрос: найдено ли оптимальное решение?

Ответ: не найдено: в строке критерия (2-я строка под обозначениями свободных переменных) имеются положительные значения.

Вопрос: Какую из свободных переменных введём в базис?

Ответ: Переменную x1, т. к. при ней в строке критерия стоит максимальный положительный коэффициент (max {1, 0.5}=1®выбираем x1 в качестве претендента для ввода в базис. Выделяем разрешающий столбец.

Таблица 2б. Трансформации симплекс-таблицы

Свободные Базисные		x1	x2
Критерий I	0	1	0.5
x3	5	1	1
x4	20	2	5
x5	40	10	4

Вопрос: Имеет ли место признак неограниченности решения?

Ответ: Нет. В разрешающем столбце против обозначений базисных переменных имеются положительные коэффициенты.

Вопрос: какую из “старых” базисных переменных вытеснит претендент на ввод в базис x1?

Ответ:

a) Выберем строки с положительными коэффициентами в разрешающем столбце, соответствующие базисным переменным (в данном случае - все строки, начиная с 3-й, т. к. все коэффициенты (1,2, 10) положительны);

b) рассчитаем частные от деления элементов второго столбца на элементы разрешающего столбца в выбранных строках, определим минимальное значение min(5/1, 20/2, 40/10) = 40/10 ® идентифицируется “старая” базисная переменная x5.

c) Выделяем разрешающую строку и изменяем обозначения “новых” базисной и свободной переменных.

Таблица 2в. Трансформации симплекс-таблицы

Свободные Базисные		x1	x2
Критерий I	0	1	0.5
x3	5	1	1
x4	20	2	5
x5	40	10	4

Вопрос: Как начать трансформацию симплекс-таблицы?

Ответ: Нужно выполнить фазу 1 и использовать правило 1: рассчитать новое значение в клетке с генеральным элементом. Получится:

Таблица 2г. Трансформации симплекс-таблицы

Свободные Базисные		x1	X2
Критерий I	0	1	0.5
x3	5	1	1
x4	20	2	5
X5	40	1/10=0.1	4