Алгоритм решения з.Л.П. С использованием симплекс – таблицы

1 шаг: привести целевую функцию f (x) = с₁x₁+с₂x₂ +с₃x₃+…+с_nx_n к виду: f (x) -с₁x₁-с₂x₂ -с₃x₃-…-с_nx_n = 0.

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

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

4 шаг: заполнить симплекс-таблицу (предположим, что первые m переменные – базисные):

Базис	Свободные члены	Переменные					Разрешающий коэффициент
		x1	x2	x3	…	xn
x1	b1	a11	a12	a13	…	a1n	ri = , для aij > 0
x2	b2	a21	a22	a23	…	a2n
…	…	…	…	…	…	…
xm	bm	am1	am2	am3	…	amn
f (x)	0	с1	с2	с3	…	сn

5 шаг: пользуясь Теоремой 1*, проверить базисное решение на оптимальность:

• если все коэффициенты целевой функции при небазисных переменных положительные, а при базисных равны нулю, то критерий оптимальности выполнен. Далее перейти к 6-му шагу алгоритма.

• если в целевой функции найдется хотя бы один отрицательный коэффициент с_j перед небазисной переменной x_j, то найденное базисное решение не является оптимальным. В этом случае, пользуясь теоремой 3*, исследуют возможность перехода к новому базисному решению. Если получили, что такой переход возможен, то необходимо осуществить смену одной базисной переменной по схеме 1*.

Схема 1*

- Пусть в целевой функции при небазисной переменной x_j коэффициент с_j < 0. Тогда для всех положительных коэффициентов a_ik, стоящих в столбце “x_j” симлекс-таблицы, вычисляют разрешающий коэффициент по формуле:

r_{i =} , где b_i - свободный член в i-ой строке таблицы.

- Среди всех разрешающих коэффициентов находят минимальный. Пусть r_p=min ( r_i ). Тогда в p-ой строке таблицы производят замену исходной базисной переменной на переменную x_j.

• После смены одной базисной переменной необходимо путем эквивалентных преобразований привести симплекс-таблицу к следующему виду:

Базис	Свободные члены	Переменные							Разрешающий коэффициент
		x1	x2	x3	…	xj	…	xn
x1	b1’	a11’	a12’	a13’	…	0	…	a1n’	ri = , для aij’ > 0
x2	b2’	a21’	a22’	a23’	…	0	…	a2n’
…	…	…	…	…	…	0	…	…
xp xj					…	1	…
…	…	…	…	…	…	0	…	…
xm	bm’	am1’	am2’	am3’	…	0	…	amn’
f (x)	c	с1’	с2’	с3’	…	0	…	сn’

-Теперь переменная x_j будет являться базисной. Получили новое базисное решение. Его необходимо проверить на оптимальность по теореме 1*. Если найденное базисное решение является оптимальным, то перейти к 6 шагу алгоритма. В противном случае необходимо произвести смену одной базисной переменной по схеме 1*.

6 шаг: сформулировать выводы по результатам решения З.Л.П.

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

f (x) = х₁ + х₂ – х₃  max

х₁ 0, х₂ 0, х₃ 0

1 шаг алгоритма: приведем целевую функцию f (x) = х₁+ х₂ – х₃

к виду: f (x) - х₁ - х₂ + х₃ = 0.

2 шаг алгоритма: сведем систему ограничений к системе линейных уравнений путем добавления дополнительных переменных х₄ и х₅:

х₁ 0, х₂ 0, х₃ 0, х₄ 0, х₅ 0

3 шаг алгоритма: в данном случае, после ввода дополнительных переменных, в каждой из двух уравнений системы уже присутствует выделенная переменная ( х₄ - в первом уравнении и х₅ – во втором).

4 шаг алгоритма: заполним симплекс-таблицу (Табл.1):

Таблица 1

Базис	Свободные члены	Переменные					Разрешающий коэффициент
		х1	х2	х3	х4	х5
х4	2	1	1	4	1	0	2/1=2
х5	1	1	-1	2	0	1	1/1=1min
f(x)	0	-1	-1	1	0	0

Базисное решение имеет вид: (х₁,х₂,х₃,х₄,х₅)=(0,0,0,2,1). Найденное базисное решение не является оптимальным, так как не все коэффициенты целевой функции неотрицательные. Следовательно, необходимо осуществить смену одной базисной переменной. Для этого выберем одну из переменных, при которой в целевой функции стоит отрицательный коэффициент (например, переменную х₁) и произведем для этой переменной расчет разрешающих коэффициентов (Табл. 1).

Поскольку наименьший из разрешающих коэффициентов стоит во второй строке таблицы, то необходимо заменить базисную переменную х₅ на переменную х₁. Так как теперь х₁ является базисной переменной, то необходимо путем эквивалентных преобразований получить а₁₁=0, с₁=0 и а₂₁=1.

В данном случае, чтобы получить:

а₂₁=1, необходимо разделить вторую строку таблицы на разрешающий коэффициент;

а₁₁=0, необходимо вычесть из элементов первой строки соответствующие элементы второй;

с₁=0, необходимо сложить вторую и третью строку таблицы.

После указанных преобразований получим таблицу 2 (стр.28).

Получили новое базисное решение (х₁,х₂,х₃,х₄,х₅)=(1,0,0,1,0). Выделенное базисное решение не доставляет максимума целевой функции (не является оптимальным), так как не все коэффициенты целевой функции являются неотрицательными числами.

Таблица 2

Базис	Свободные члены	Переменные
		х1	х2	х3	х4	х5
х4	1	0	2	2	1	-1
х1	1	1	-1	2	0	1
f(x)	1	0	-2	3	0	1

Так перед переменной х₂ в целевой функции стоит коэффициент с₂ = -2. Следовательно, необходимо произвести смену одной базисной переменной. Но, поскольку в столбце «х₂» (Табл. 2) присутствует только один положительный коэффициент а₁₂ = 2, стоящий в первой стоке таблицы, то нет необходимости в расчете разрешающих коэффициентов. Можно сразу сделать вывод, что базисную переменную х₄ необходимо заменить на переменную х₂. Так как теперь х₂ является базисной переменной, то необходимо путем эквивалентных преобразований получить а₁₂=1, с₂=0 и а₂₂=0.

В данном случае, чтобы получить:

с₁=0, необходимо сложить вторую и третью строку таблицы;

а₁₂=1, необходимо разделить вторую строку таблицы на 2;

а₂₂=0, необходимо прибавить к элементам второй строки соответствующие элементы первой, полученные после умножения на 2;

Внесем все преобразования в таблицу 3.

Таблица 3

Базис	Свободные члены	Переменные					Разрешающий коэффициент
		х1	х2	х3	х4	х5
х2	1/2	0	1	1	1/2	-1/2
х1	3/2	1	0	3	1/2	1/2
f(x)	2	0	0	5	1	0

По таблице 3 составим новое базисное решение, приравнивая базисные переменные к свободным членам, небазисные – к нулю: (х₁,х₂,х₃,х₄,х₅) = (3/2,1/2,0,0,0). Данное базисное решение является оптимальным (по теореме 1*), так как все коэффициенты целевой функции есть неотрицательные числа. Следовательно, найденный базис будет доставлять максимальное значение целевой функции: f (x) = х₁ + х₂ – х₃ . Таким образом, max (f (x)) = 2 + 5х₃ + х₄ = 2. Поставленная З.Л.П решена.