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

4 5 6 7 8 9 10

Симплексный метод, или метод последовательного улучшения решения, универсален, им можно решить любую ЗЛП.

Пусть ЗЛП задана в канонической форме:

(1)

(2)

(3)

Разрешим систему уравнений (2) относительно неотрицательного базиса. Пусть система (2) при этом примет вид

(4)

Получено опорное решение .

. (5)

Исключим базисные переменные х ₁, х ₂, …, х_r из целевой функции, для этого умножим первое уравнение системы (4) на с ₁, второе на с ₂ и т.д., r -е уравнение умножим на с_r и все это прибавим к целевой функции. Получим:

(6)

Определение 1. Выражение (6) называется приведенным выражением для целевой функции, коэффициенты при свободных переменных х_r₊ ₁, …, х_j, …, х_n называются оценками и обозначаются D.

. (7)

Правая часть уравнения (6)

так как .

Тогда уравнение (6) примет вид

. (8)

Запишем систему (5) и выражение (8) в виде одной системы и перейдем ко второму опорному решению:

(9)

Допустим, что вместо x_i в базис вводится свободная переменная x_j. По правилу прямоугольника найдем значение целевой функции от второго опорного решения.

(10)

Сравним и , так как f_i ³0, h_ij > 0, то знак дроби зависит от знака оценки D_j.

1) Если D _j > 0, то .

2) Если D _j < 0, то .

3) Если D _j = 0, то .

Отсюда получаем критерий оптимальности для ЗЛП на максимум:

1) если все оценки D _j > 0, то найденное решение оптимальное;

2) если среди оценок имеется хотя бы одно отрицательное число, то найденное решение не оптимально.

Пусть D_j < 0, тогда если среди коэффициентов при х_j есть хотя бы одно положительное число, х_j можно ввести в базис и .

Если D _j < 0 и все коэффициенты при х_j h_ij < 0, то х_j в базис ввести нельзя. Покажем, что в этом случае равен бесконечности, для этого из системы (9) выпишем общее решение, всем свободным переменным, кроме х_j, придадим значение, равное 0, получим

(11)

. (12)

Отсюда видно, что если х_j придавать сколь угодно большие числовые значения, то решение, полученное из системы (11), будет допустимым, а значение целевой функции (12) будет неограниченно расти, т.е. при х → ∞ ;

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

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

Алгоритм симплексного метода

Решение задач линейного программирования симплексным методом предполагает следующие этапы:

1) привести задачу к каноническому виду;

2) найти неотрицательное базисное решение системы ограничений;

3) найти оценки свободных переменных по формуле

и записать полученные оценки в симплексную таблицу;

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

а) если все оценки D_j > 0, то найденное решение оптимально и задача решена;

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

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

4) если выполняется случай в), то нужно перейти к следующему опорному решению;

5) перейти к п. 3.

Замечание 1. Критерием оптимальности для ЗЛП на минимум является неположительность оценок, т.е. все D _j < 0, .

Замечание 2. В ЗЛП максимум и минимум целевой функции понимаются как глобальные.

Пример 3. Найти наибольшее значение функции

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

х ₁-2х₂ - 2х₃ + х ₄- х ₅ = 1,

-2 х ₂- х ₃+3х₄+ х ₅= 5,

х₂ + 8 х ₃+ х ₄+3 х ₅= 20,

Задача задана в каноническом виде. Найдем исходное опорное решение.

№ п/п	Б.п.	х ₁	х ₂	х ₃	х ₄	х ₅	b _i
	x ₁		-2 -2 1	-2 -1		-1
	x ₁ x ₂					8
	x ₁ x ₅ x ₂			37/8 15/8 19/8	-1/8 5/8 -7/8		103/8 45/8 25/8

Проверим это решение на оптимальность.

№ п/п	с_j	Б.п.			-5			b_i
х ₁	х ₂	х ₃	х ₄	х ₅
		x ₁ x ₅ x ₂			37/8 15/8 19/8	-1/8 5/8 -7/8		103/8 45/8 25/8
D _j				111/8	-19/8		173/8

Найденное решение не оптимально, так как D₄ < 0. Введем в базис свободную переменную с отрицательной оценкой х ₄.

№ п/п	с_j	Б.п.			-5			b_i
х ₁	х ₂	х ₃	х ₄	х ₅
		x ₁ x ₄ x ₂					1/5 8/5 7/5
D _j						19/5

. Так как среди оценок нет отрицательных чисел, то второе опорное решение оптимально.

, .

Метод искусственного базиса

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

Дана задача: найти наибольшее значение функции

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

Составим расширенную задачу, которую назовем М-задачей.

Найти наибольшее значение функции

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

В каждое уравнение, в котором нет базисной переменной, вводим переменную , где , с коэффициентом 1, эти переменные называются искусственными, и они образуют искусственный базис. Искусственные переменные вводятся в целевую функцию с коэффициентами -М, если задача решается на максимум, и +М, если задача решается на минимум, где М сколь угодно большое положительное число. Система ограничений расширенной задачи совместна.