Симплексный метод

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

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

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

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

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

Алгоритм решения задач симплексным методом:

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

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

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

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

сi	Базисная переменная (БП)	c1	c2	…	cm	cm+1	…	cn	L(x)
x1	x2	…	xm	xm+1	…	xn	bi
c1	x1			…		h1,m+1	…	h1n	f1
c2	x2			…		h2,m+1	…	h2n	f2
…	…	…	…	…	…	…	…	…	…
cm	xm			…		hm,m+1	…	hmn	fm
	∆j			…		∆m+1	…	∆n	L(x1)

 

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

 

 

и по формуле

 

 

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

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

- если хотя бы одна оценка ∆_j 0, но при соответствующей переменной нет ни одного положительного коэффициента, то решение задачи завершается, так как L(x) , т.е. целевая функция не ограничена в области допустимых решений;

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

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

3. Симплексная таблица 2-го шага заполняется следующим образом:

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

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

- остальные коэффициенты таблицы находим по правилу

“прямоугольника”. Оценки можно считать по приведенным выше формулам или по правилу “прямоугольника”. Получаем новое опорное решение, которое проверяем на оптимальность и т.д.

Примечание:

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

1. Правило “прямоугольника”: пусть ключевым элементом 1-го шага является элемент 1-й строки (m+1)-го столбца – элемент h_1,m+1. Тогда элемент i-й строки (m+2)-го столбца 2-го шага, который обозначим = (h_1,m+1 ) / h_1,m+1,

где h_1,m+1, h_i,m+1, h_i,m+2 – элементы 1-го шага.

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

 

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

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

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

Решение. Пусть x₁ – время работы предприятия по первому способу;

x₂ – время работы предприятия по второму способу.

Математическая модель задачи примет вид:

L(x) = 3 x₁ + 4 x₂ max

x₁ + 2 x₂

x₁ + x₂ 3,

2 x₁ + x₂ 8,

x₁ , x₂ .

 

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

L(x) = 3 x₁ + 4 x₂ max

x₁ + 2 x₂x₃

x₁ + x₂ 3,

2 x₁ + x₂ 8,

x_j , j= 1;2;3;4;5.

 

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

ci	БП						L(x)
x1	x2	x3	x4	x5	bi
	x3
	x4
	x5
	-3	-4

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

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

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

ci	БП						L(x)
x1	x2	x3	x4	x5	bi
	x2	1/2		1/2
	x4	1/2		-1/2
	x5	3/2		-1/2
	-1

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

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

 

ci	БП						L(x)
x1	x2	x3	x4	x5	bi
	x2				-1
	x1			-1
	x5				-3

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

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

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