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

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

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

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

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

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

х1>0, х2>0.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

х1 >0, х2 >0.

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

Х2

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

30 А

В

С

D Х1

40 50 80

l2 l1

l3

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

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

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

Решая систему, получим: Графический метод и симплекс-метод решения задач линейного программирования - student2.ru , Графический метод и симплекс-метод решения задач линейного программирования - student2.ru .

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

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

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

Графический метод и симплекс-метод решения задач линейного программирования - student2.ru х12 > 8,

-5х1+2х2 < 10,

х1-3х2 < 0,

х1 >0, х2 >0

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

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

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

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

х12 = 8,

х1-3х2 =0

х1 = 6, Графический метод и симплекс-метод решения задач линейного программирования - student2.ru

х2 = 2.

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

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

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

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

Графический метод и симплекс-метод решения задач линейного программирования - student2.ru (1)

Графический метод и симплекс-метод решения задач линейного программирования - student2.ru (2)

Графический метод и симплекс-метод решения задач линейного программирования - student2.ru (3)

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

Графический метод и симплекс-метод решения задач линейного программирования - student2.ru Графический метод и симплекс-метод решения задач линейного программирования - student2.ru Графический метод и симплекс-метод решения задач линейного программирования - student2.ru (4)

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

Графический метод и симплекс-метод решения задач линейного программирования - student2.ru . (5)

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

Графический метод и симплекс-метод решения задач линейного программирования - student2.ru (6)

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

Графический метод и симплекс-метод решения задач линейного программирования - student2.ru . (7)

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

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

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

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

Графический метод и симплекс-метод решения задач линейного программирования - student2.ru . (8)

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

Графический метод и симплекс-метод решения задач линейного программирования - student2.ru Графический метод и симплекс-метод решения задач линейного программирования - student2.ru (9)

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

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

Графический метод и симплекс-метод решения задач линейного программирования - student2.ru (10)

Сравним Графический метод и симплекс-метод решения задач линейного программирования - student2.ru и Графический метод и симплекс-метод решения задач линейного программирования - student2.ru , так как fi ³0, hij > 0, то знак дроби Графический метод и симплекс-метод решения задач линейного программирования - student2.ru зависит от знака оценки Dj.

1) Если Dj > 0, то Графический метод и симплекс-метод решения задач линейного программирования - student2.ru .

2) Если Dj < 0, то Графический метод и симплекс-метод решения задач линейного программирования - student2.ru .

3) Если Dj = 0, то Графический метод и симплекс-метод решения задач линейного программирования - student2.ru .

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

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

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

Пусть Dj < 0, тогда если среди коэффициентов при хj есть хотя бы одно положительное число, хj можно ввести в базис и Графический метод и симплекс-метод решения задач линейного программирования - student2.ru .

Если Dj < 0 и все коэффициенты при хj hij < 0, то хj в базис ввести нельзя. Покажем, что Графический метод и симплекс-метод решения задач линейного программирования - student2.ru в этом случае равен бесконечности, для этого из системы (9) выпишем общее решение, всем свободным переменным, кроме хj, придадим значение, равное 0, получим

Графический метод и симплекс-метод решения задач линейного программирования - student2.ru Графический метод и симплекс-метод решения задач линейного программирования - student2.ru (11)

Графический метод и симплекс-метод решения задач линейного программирования - student2.ru . (12)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Замечание 1. Критерием оптимальности для ЗЛП на минимум является неположительность оценок, т.е. все Dj < 0, Графический метод и симплекс-метод решения задач линейного программирования - student2.ru .

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

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

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

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

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

х1-2х2 - 2х34 - х5 = 1,

-2х2 - х3 +3х4 + х5 = 5,

х2 + 8х3+ х4 +3х5 = 20,

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

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


№ п/п Б.п. х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

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

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

№ п/п с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 Графический метод и симплекс-метод решения задач линейного программирования - student2.ru 111/8 -19/8 173/8

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

№ п/п сj Б.п. -5 bi
х1 х2 х3 х4 х5
x1 x4 x2 1/5 8/5 7/5
D j Графический метод и симплекс-метод решения задач линейного программирования - student2.ru 19/5

Графический метод и симплекс-метод решения задач линейного программирования - student2.ru . Так как среди оценок нет отрицательных чисел, то второе опорное решение оптимально.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Исходное опорное решение Графический метод и симплекс-метод решения задач линейного программирования - student2.ru где Графический метод и симплекс-метод решения задач линейного программирования - student2.ru , Графический метод и симплекс-метод решения задач линейного программирования - student2.ru .

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

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

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

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

Теорема.

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

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

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

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

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

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

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

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

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

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

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

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

Наши рекомендации