Табличная реализация простого симплекс-метода

 

Табличную реализацию продемонстрируем на том же примере (2.2)–(2.5).

Шаг 0. Решение начинается с построения начальной симплекс-таблицы. Сначала заполняется правая часть таблицы с третьей колонки. В двух верхних строках записываются имена переменных задачи (x_1,...,x₄) и коэффициенты целевой функции при этих переменных. Ниже записываются коэффициенты уравнений – элементы матрицы условий А, так что под переменной x₁располагаетсястолбец A₁, под переменной x₂– столбец A₂и т.д. В правый столбец заносятся правые части ограничений (числа b_i > 0).

Затем находим столбцы матрицы условий, образующие единичный базис – в нашем примере это A₃ и A₄ – и соответствующие им базисные переменные x_3, x₄записываем во вторую колонку. Наконец, в первом столбце записываем коэффициенты целевой функции при базисных переменных.

Таблица 1 - Начальная симплекс-таблица

СБ	Базисные переменные	с1=1	с2=2	с3=0	с4=0	Значения базисных перем. (x Б = b)
		x1	x2	x3	x 4
c3=0	x3	a11=-1	a12=2	a13=1	a14=0	b1=4
c4=0	x4	a21=3	a22=2	a23=0	a24=1	b2=12
Строка оценок j		 1 = -1	 2 = -2	 3 = 0	 4 = 0	f(x)= 0

 

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

x^o = (0, 0, x₃, x₄₎ = (0, 0, 4, 12).

Шаг 1. Для проверки плана x^oна оптимальность подсчитаем симплексные оценки для небазисных переменных x₁и x₂по формуле

 _j =< c_Б , A_j > – c_j.

₁ = < c_Б , A₁ > – c₁ = 0 ·(–1) + 0 ·3 – 1 = –1.

 

При табличной реализации для подсчета оценки ₁ надо найти сумму произведений элементов первого столбца (c_Б) на соответствующие элементы столбца A₁при небазисной переменной x₁. Аналогично подсчитывается оценка ₂, как скалярное произведение первого столбца (c_Б) на столбец при переменной x₂.

₂ = < c_Б, A₂ > – c₂ = 0 ·2 + 0 · 2 – 2 = –2.

 

Симплексные оценки записываются в последней строке симплекс-таблицы, которая называется дельта-строкой. При этом заполняются не только клетки при небазисных переменных, но и базисные клетки. Легко проверить, что для базисных единичных столбцов матрицы условий симплексные оценки равны нулю. В последней клетке строки оценок записываем значение целевой функции в точке x^o_. Заметим, что, так как небазисные координаты базисного плана равны нулю, то подсчет целевой функции удобно производить по формуле

f(x)= < c_Б, x_Б >,

 

перемножая скалярно первый и последний столбцы таблицы.

Так как среди оценок _j естьотрицательные, то план x^o – не оптимальный, и надо найти новый базисный план, заменив одну из базисных переменных на новую из числа небазисных.

Шаг 2. Поскольку обе оценки ₁и ₂ < 0,то в базис можно включить любую из переменных x_1, x₂. Введем в базис переменную с наибольшей по модулю отрицательной оценкой, то есть x₂.

Столбец симплекс-таблицы, в котором находится вводимая в базис переменная называется ведущим столбцом.

В примере ведущим будет столбец при x₂.

Шаг 3. Если в ведущем столбце все элементы отрицательны, то решения задачи не существует и max f(x) . В примере все элементы ведущего столбца положительны, следовательно, можно найти максимальное значение x₂, при котором одна из старых базисных переменных обратится в ноль. Напомним, что максимальное значение x₂ = min{4/2, 12/2}=2.

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

Наименьшее отношение находится в строке с базисной переменной x_3. Значит переменная x₃ исключается из состава базисных переменных (x₃ = 0).

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

В примере ведущей строкой будет первая строка.

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

В нашем случае ведущий элемент a₁₂ = 2.

 

Табл. 2 - Начальная симплекс-таблица с ведущими строкой и столбцом

cБ	Базисные перемен.	с1=1	с2=2	с3=0	С4=0	Значения базисных перем.	Уравнения
		x1	x2	x3	x 4
c3=0	x 3	–1	2	1	0	4	p1
c4=0	x4	3	2	0	1	12	p2
Строка оценок j		 1 = –1	2 = –2	 3 = 0	 4 = 0	f(x)= 0

 

Шаг 4. Для получения нового базисного плана приведем задачу к новому предпочтительному виду относительно новых базисных переменных.

Для этого построим новую симплекс-таблицу, во втором столбце которой вместо исключаемой переменной x₃ запишем новую базисную переменную x₂, а в первом столбце (с_Б) вместо с₃ запишем коэффициент целевой функции при x₂ : c₂=2. В новой симплекс таблице столбец при x₂ долженстать единичным (ведущий элемент должен равняться единице, а все остальные элементы должны обратиться в ноль). Это достигается следующими преобразованиями строк таблицы.

a. Все элементы ведущей строки делим на ведущий элемент и записываем в той же строке новой симплекс- таблицы.

Полученную строку p₁' назовем разрешающей.

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

p₂' = p₂ + (- 2) p₁' = p₂ - p_1.

c. Заполним последнюю строку, вычислив оценки _j' = < c_Б', A_j' > - - c_j,где c_Б', A_j' - соответствующие столбцы новой симплекс-таблицы, и значение целевой функции f(x)= < c_Б', x_Б' >.

Получим вторую симплекс-таблицу с новым базисом.

 

Таблица 3 - Результат первой итерации

cБ'	Базисные перемен.	с1=1	с2=2	с3=0	с4=0	Значения базисных перем.	Уравнения
		x1	x2	x3	x 4
c2=2	x 2	–1/2	1	1/2	0	2	p1' =p1/2
c4=0	x4	4	0	-1	1	8	p2' =p2 - p1
оценки j'		–2	0	1	0	f(x')=4

 

Новый базисный план x' = (0, x₂, 0, x₄₎ = (0, 2, 0, 8).

Поскольку оценка ₁= -2 < 0, то план x' не оптимален. Для перехода к новому базисному плану (соседней угловой точки) проведем еще одну итерацию симплекс - метода.

Так как ₁ < 0, то в базис вводится переменная x₁. Первый столбец, содержащий x₁ - ведущий.

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

Выделяем ведущий столбец и ведущую строку и на их пересечении находим ведущий элемент (= 4).

Строим новую (третью) симплекс-таблицу, заменяя в ней базисную переменную x₄ на x_1, и снова преобразуя строки таблицы таким образом, чтобы ведущий элемент стал равным единице, а остальные элементы ведущего столбца обратились в ноль. Для этого ведущую (вторую) строку делим на 4, а к первой строке прибавляем полученную вторую строку, деленную на 2. Последнюю строку вычисляем по формулам для симплексных оценок _j'' = < c_Б'', A_j'' > - c_j,где c_Б'', A_j'' - соответствующие столбцы новой симплекс-таблицы. Значение целевой функции на новом базисном плане находим по формуле f(x'')= < c_Б'', x_Б'' >.

 

Таблица 4 - Результат второй итерации

cБ''	Базисн. перемен.	с1=1	с2=2	с3=0	с4=0	Значения базисных перем.	уравнения
		x1	x2	x3	x 4
c2=2	x2	0	1	3/8	1/8	3	p1''=p1'+p2''/2
c1=1	x1	1	0	-1/4	1/4	2	p2'' = p2'/4
оценки j''		0	0	1/2	1/2	f(x'')= 8

 

Новый базисный план x'' = (x₁, x₂, 0, 0₎ = (2, 3, 0, 0). Поскольку все оценки неотрицательны, то план x'' - оптимальный план.

Таким образом, x* = (2, 3, 0, 0), f(x*) = 8.

ЗАКЛЮЧЕНИЕ

 

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

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

 

1. Ашманов С.А. Линейное программирование. – М.: Наука, 1981.

2. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. – М.: Высшая школа, 1980.

3. Калихман И.Л. Линейная алгебра и программирование. – М.: Высшая школа, 1967.

4. Нит И.В. Линейное программирование. – М.: Изд-во МГУ, 1978.

5. Юдин Д.Б., Гольштейн Е.Г. Линейное программирование. Теория и конечные методы. – М.: Физматиз, 1963.

6. Тарасенко Н.В. Математика-2. Линейное программирование: курс лекций. – Иркутск: изд-во БГУЭП, 2003.

7. Математическое программирование в примерах и задачах: Учеб. пособие. – 2-е изд., испр. и доп. – М.: Высш. шк., 1993. – 336 с.

8. www.yandex.ru

9. www.mathematica.ru

10. www.monax.ru