5.2. Симплексные таблицы и алгоритм решения задач

Рассмотрим алгоритм решения задач симплексным методом¹⁴.

1. Математическая модель задачи должна бать канонической. Если она неканоническая, то ее надо привести к каноническому виду.

2. Находим исходное опорное решение и проверяем его на оптимальность. Для этого заполняем симплекс-таблицу. Все строки таблицы 1-го шага, за исключением строки D_j (индексная строка), заполняем по данным системы ограничений и целевой функции.

Симплексная таблица имеет следующий вид:

сi	Базисная переменная (БП)	с1	с2	¼	сm	сm+1	¼	сn	f(`X)
		x1	x2	¼	xm	xm+1	¼	xn	b1
c1	x1	1	0	¼	0	h1, m+1	¼	h1n	l1
c2	x2	0	1	¼	0	h2, m+1	¼	h2n	l2
¼	¼	¼	¼	¼	¼	¼	¼	¼	¼
cm	xm	0	0	¼	1	hm, m+1	¼	hmn	lm
	Dj	0	0	¼	0	Dm+1	¼	Dn	f(`X1)

Индексная строка (D_j) для переменных находится по формуле

и для свободного члена по формуле

.

При этом возможны следующие случаи решения задачи на максимум:

- если все оценки D_j ³ 0, то найденное решение оптимальное;

- если хотя бы одна оценка D_j £ 0, но при соответствующей переменной нет ни одного положительного коэффициента, решение задачи прекращают, так как f(X) ® ¥, т.е. целевая функция не ограничена в области допустимых решений;

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

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

Пусть одна оценка D_k £ 0 или наибольшая по абсолютной величине D_k £ 0, тогда k-й столбец принимают за ключевой (разрешающий). За ключевую (разрешающую) строку принимают ту, которой соответствует минимальное отношение свободных членов (b_i) к положительным коэффициентам k-го столбца. Элемент, находящийся на пересечении ключевых строки и столбца, называют ключевым (разрешающим) элементом.

3. Заполнение симплексной таблицы 2-го шага:

- переписывается ключевая строка, разделив ее элементы на ключевой элемент;

- заполняют базисные столбцы;

- остальные коэффициенты таблицы находят по правилу «прямоугольника». Оценки можно считать по приведенным выше формулам или по правилу «прямоугольника». Получается новое опорное решение, которое проверяется на оптимальность и т.д.

Примечание. Если целевая функция f(X) требует нахождения минимального значения, то критерием оптимальности задачи является неположительность оценок D_j при всех .

Правило «прямоугольника» состоит в следующем. Пусть ключевым элементом 1-го шага является элемент 1-й строки (m+1)-го столбца h_{1, m+1}. Тогда элемент i-й строки (m+2)-го столбца 2-го шага, который обозначим , по правилу «прямоугольника» определяется по формуле

,

где h_{1, m+1}, h_{i, m+1}, h_{i, m+2} – элементы 1-го шага.

5.3. Применение симплексного метода в экономических задачах

Рассмотрим применение симплексного метода на примерах экономических задач¹⁵.

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

Производственный ресурс	Расход ресурсов за 1 месяц при работе		Общий ресурс
	по 1 способу	по 2 способу
Сырье	1	2	4
Оборудование	1	1	3
Электроэнергия	2	1	8

При первом способе производства предприятие выпускает за один месяц 3 тыс. изделий, при втором – 4 тыс. изделий.

Сколько месяцев должно работать предприятие по каждому из этих способов, чтобы при наличных ресурсах обеспечить максимальный выпуск продукции?

Решение. Обозначим: х₁ – время работы предприятия по первому способу; х₂ – время работы предприятия по второму способу. Экономико-математическая модель задачи:

при ограничениях:

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

при ограничениях:

Составляем симплексную таблицу 1-го шага:

сi	БП	3	4	0	0	0
		х1	х2	х3	х4	х5	bi
0	x3	1	2	1	0	0	4
0	x4	1	1	0	1	0	3
0	x5	2	1	0	0	1	8
Dj		-3	-4	0	0	0	0

= (0, 0, 4, 3, 8), = 0.

В индексной строке D_j имеются две отрицательные оценки, значит найденное решение не является оптимальным и его можно улучшить. В качестве ключевого столбца следует принять столбец базисной переменной х₂, а за ключевую строку – строку переменной х₃, где min (4/2, 3/1, 8/1) = min (2, 1, 8) = 2.

Ключевым элементом является «2». Вводим в столбец БП переменную х₂, выводим х₃. Составляем симплексную таблицу 2-го шага:

сi	БП	3	4	0	0	0
		х1	х2	х3	х4	х5	bi
4	x2	1/2	1	1/2	0	0	2
0	x4	1/2	0	-1/2	1	0	1
0	x5	3/2	0	-1/2	0	1	6
Dj		-1	0	2	0	0	8

= (0, 2, 0, 1, 6), =8.

В индексной строке имеется одна отрицательная оценка. Полученное решение можно улучшить. Ключевым элементом является «1/2». Составим симплексную таблицу 3-го шага:

сi	БП	3	4	0	0	0
		х1	х2	х3	х4	х5	bi
4	x2	0	1	1	-1	0	1
3	x1	1	0	-1	2	0	2
0	x5	0	0	1	-3	1	3
Dj		0	0	1	2	0	10

Все оценки свободных переменных D_j ³ 0, следовательно, найденное опорное решение является оптимальным:

= (2, 1, 0, 0, 3), = 10.

Ответ: максимальный выпуск продукции составит 10 тыс. ед., при этом по первому способу предприятие должно работать два месяца, по второму – один месяц.