Графический метод и симплекс-метод решения задач линейного программирования

Графический метод решения ЗЛП

Графическим методом можно решать задачи, заданные в неканоническом виде с двумя переменными или сводящиеся к ним. Рассмотрим задачу следующего вида: найти экстремум функции

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

х₁>0, х₂>0.

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

1) область допустимых решений - пустое множество;

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

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

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

В первом случае ЗЛП не имеет оптимального решения из-за несовместности системы ограничений.

Во втором случае - это единственное решение и будет оптимальным решением.

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

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

Пусть с₀ - некоторое число. Прямая является линией уровня целевой функции. В каждой точке этой прямой целевая функция принимает одно и то же значение, равное с₀. Вектор - градиент целевой функции

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

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

, .

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

Пример 1. Решить графически следующую задачу:

,

х₁ >0, х₂ >0.

Построим область допустимых решений системы ограничений:

Х₂

30 А

В

С

D Х₁

40 50 80

l₂ l₁

l₃

Областью допустимых решений системы ограничений является выпуклый пятиугольник ОАВCD.

Построим вектор и линию уровня, перпендикулярную вектору . Наибольшее значение целевая функция достигает в угловой точке В. Найдем координаты точки В, для этого решим систему из уравнений первой и второй прямой.

Решая систему, получим: , .

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

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

х₁+х₂ > 8,

-5х₁+2х₂ < 10,

х₁-3х₂ < 0,

х₁ >0, х₂ >0

Построим ОДР.

Областью допустимых решений системы ограничений является выпуклая многоугольная неограниченная область. Наименьшее значение целевой функции достигается в угловой точке А, а наибольшее значение функции найти нельзя, так как функция не ограничена сверху, т.е. max L = ∞.

Найдем координаты точки А, для этого решим систему из уравнений первой и третьей прямой:

х₁+х₂ = 8,

х₁-3х₂ =0

х₁ = 6,

х₂ = 2.

т.е. .

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

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

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

(1)

(2)

(3)

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

(4)

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

. (5)

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

(6)

Определение 1. Выражение (6) называется приведенным выражением для целевой функции, коэффициенты при свободных переменных х_r+1, …, х_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,

.

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

№ п/п	Б.п.	х1	х2	х3	х4	х5	bi
	x1		-2 -2 1	-2 -1		-1
	x1   x2					8
	x1 x5 x2			37/8 15/8 19/8	-1/8 5/8 -7/8		103/8 45/8 25/8

.

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

№ п/п	сj	Б.п.			-5			bi
х1	х2	х3	х4	х5
		x1 x5 x2			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			bi
х1	х2	х3	х4	х5
		x1 x4 x2					1/5 8/5 7/5
D j						19/5

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

, .

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

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

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

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

.

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

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

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

.

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

Исходное опорное решение где , .

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

.

Эти решения называются соответствующими.

Теорема.

1. Если в оптимальном решении М-задачи все искусственные переменные равны 0, то соответствующее ему решение является оптимальным решением исходной задачи.

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

3. Если М-задача не имеет оптимального решения, то и исходная задача также не имеет оптимального решения.

Алгоритм метода искусственного базиса

1. Задачу линейного программирования привести к каноническому виду.

2. Построить М-задачу.

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

4. Применяя теорему о связи между оптимальными решениями М-задачи и исходной задачи, даем ответ исходной задачи:

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

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

в) если М-задача не имеет оптимального решения, то исходная задача также не имеет оптимального решения.