Графический способ решения ЗЛП

Графический способ решения применим к ЗЛП в следующей постанвке: 1) целевая функция f→ max(min); 2) ограничения должны быть записаны в виде неравенств, не обязательно одного знака; 3) число переменных n≤ 3.

Для простоты изложения рассмотрим случай n=2.

Выясним геометрический смысл неравенств, их решений и решений систем неравенств, то есть геометрический смысл системы ограничений.

Доказана теорема: множество решений неравенства с двумя переменными

является одной из двух полуплоскостей, на которые вся плоскость делится прямой

,

включая и эту прямую, а другая половина плоскости с той же прямой есть множество решений неравенства

Пример. Построить множество решений неравенства:

а) , б) .

Решение. В соответствии с теоремой множество решений неравенства есть полуплоскость.

а) Построим границу полуплоскости – прямую , найдя точки её пересечения с осями координат A(5, 0) и B(0, -1) (рис.1).

Для определения искомой полуплоскости (верхней или нижней) рекомендуется задать произвольную контрольную точку, не лежащую на её границе – построенной прямой. Если неравенство выполняется в контрольной точке, то оно выполняется во всех точках полуплоскости, содержащей контрольную точку, и не выполняется во всех точках другой полуплоскости. И наоборот, в случае невыполнения неравенства в контрольной точке оно не выполняется во всех точках полуплоскости, содержащей контрольную точку, и выполняется во всех точках другой полуплоскости.

В качестве контрольной точки удобно взять начало координат
0(0, 0), не лежащее на построенной прямой. Координаты точки 0
удовлетворяют неравенству 1*0-5*0≤ 5. Это неравенство - верное. Следовательно. решением данного неравенства является полуплоскость, содержащая точку 0. Искомая полуплоскость выделена штриховкой.

б)Построим границу полуплоскости — прямую 3х₁-2х₂=0 по двум точкам (рис. 2). Одной из этих точек является начало коорди-
нат, другую точку берем на прямой произвольно, например, А(2, 3). В качестве контрольной точки здесь брать " самую простую" 0(0, 0)
не следует, так как она лежит на прямой. Возьмем, например, точку
В(0.1). Так как координаты контрольной точки не удовлетворяют неравенству, т.е. неравенство 3*0-2*1≥ 0 не является верным, то решением данного неравенства является полуплоскость, не содержащая точку В(0, 1). Искомая полуплоскость выделена штриховкой. Доказана теорема: множество решений совместной системы линейных неравенств с двумя переменными является выпуклым многоугольником (или выпуклой многоугольной областью).

Пример, Построить множество решений системы неравенств

Для каждой прямой (границы полуплоскости) находим точки пересечения с осями координат и определяем соответствующую полуплоскость:

1) х1–5x2 =5,	X1 0 5 X2 -1 0	1*0 - 5*0 ≤ 5, 0< 5;
2) х1–x2< -4,	X1 0 -4 X2 4 0	1*0 –1*0 ≥ -4 0> -4;
3) х1+х2< 8	X1 0 8 X2 8 0	1*0+1*0 < 8.

Множеством всех решений системы неравенств – пересечение соответствующих полуплоскостей – треугольник АВС (рис. 3).

(рис. 3 )

Если учесть условия неотрицательности

х₁ > о; х₂> 0,

то областью допустимых решений будет та часть треугольника АВС, которая находится в первой четверти, т.е. ОДВСЕ — многоугольник
допустимых решений, в дальнейшем — многоугольник решений.
При построении многоугольника решений возможны следующие частные случаи: многоугольная область (рис. 4); прямая линия (рис. 5): точка (рис. 6); множество. не содержащее допустимых решений (рис. 7); пустое множество, если система ограничений несовместна (рис. 8).  

 

 

Итак, в общем случае множество всех допустимых решений системы ограничений ЗЛП при n = 2 — многоугольник решений — является выпуклым многоугольником (рис. З) или, в частности, выпуклой многоугольной областью (рис. 4).

Ответ на вопрос. В какой точке многоугольника решений возможно оптимальное решение ЗЛП, дается следующей Фундаментальной
теоремой: если ЗЛП имеет единственное оптимальное решение, то линейная функция принимает максимальное (минимальное) значение в одной из угловых точек многоугольника решений. Если линейная Функция принимает максимальное (минимальное) значение более чем в одной угловой точке. то она принимает его в бесчисленном множестве точек, являющихся отрезком — частью границы многоугольника решений.

 Рассмотрим целевую функцию F(х₁, х₂)= с₁х₁+с₂х₂. Она является линейной функцией двух переменных х₁, х₂. В математическом анализе функций нескольких переменных вводятся понятия линии уровня функции нескольких переменных и градиента функции нескольких переменных.

Линией уровня функции двух переменных называется множество точек плоскости, в которых функция сохраняет одно и то же значение, т. е. f(х₁, х₂)= d или

 f(х₁, x₂)= с₁х₁+ с₂х₂=d,   d=const.

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

Он обладает следующими свойствами:

1)  перпендикулярен линиям уровня функции ;

2)  показывает направление наискорейшего возрастания функции .

Если функция  — линейная функция, то ее линии уровня образуют семейство параллельных прямых, а вектором-градиентом является вектор

перпендикулярный линиям уровня.

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

Используя все вышеизложенное, сформулируем порядок решения ЗЛП графическим способом.

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

2. Построить многоугольник решений.

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

4. Решив соответствующую систему уравнений, найти координаты оптимального решения (плана).

5. Вычислить максимальное (минимальное) значение целевой функции и записать ответ.

Пример. Решить графически: f = -2x₁ – 3x₂ → min,

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

x₁ – 5x₂ ≤ 5,

x₁ – x₂ ≥ -4,

x₁ + x₂ ≤ 8,

x₁ ≥ 0, x₂ ≥ 0.

Решение.

1. Задача поставлена в симметричной форме.

2. Многоугольник решений представлен на рис. 3.

3. Восстановим рис. 3 и из начала координат построим вектор c (-2, -3). Перпендикулярно ему проведём линию уровня, проходящую через начало координат. Перемещаем линию уровня в направлении вектора –с до тех пор, пока она имеет общие точки с многоугольником решений. Минимальное значение целевая функция принимает в точке B.

4. найдём координаты точки B. Для этого решим систему линейных алгебраических уравнений:

 

5. Вычислим значение целевой функции при x₁=2, x₂=6:

f=-2*2-3*6=-22

Ответ: fmin=-22, x_опт=(2, 6).

Рисунок, иллюстрирующий решение задачи:

рис. 9

Частный случай 1. Решить графически задачу:

f=x₁+x₂→ max;

Решение

1) –2x1+3x2=9,	X1 0 -4.5 X2 3 0
2) x1-2x2=2,	X1 0 2 X2 -1 0

Рисунок, иллюстрирующий решение задачи:

Многоугольник решений – многоугольная выпуклая область. Оптимальных решений нет, f_max→ ~.

Ответ: f_max→ ~; оптимальных решений нет.

 

Частный случай 2. Решить графически задачу:

F=x₁-x₂→ max;

Решение

1) –2x1+3x2=9	X1 0 -4.5 X2 3 0
2) x1-x2=2	X1 0 2 X2 -2 0
3)x1+x2=8	X1 0 8 X2 8 0

Рисунок, иллюстрирующий решение задачи:

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

Координаты точки С находим, решая систему:

Координаты точки Д находим, решая систему:

   Д(2, 0)

 

Значение целевой функции

f(C)=5-3=2; f(Д)=2-0=2; f_max=f(C)=f(Д)

Ответ:

f_max=2,

Пример. Решить графически:

f=9x₁+3x₂-5x₃+5x₄→ max;

 

Решить пример самостоятельно.

Ответ: f_max=2, x_опт=(2, 0, 0, 2)

 Симплекс-метод решения ЗЛП.

В основе геометрической интерпретации решения системы m линейных уравнений с n неизвестными (m< n) лежит теорема: каждому допустимому базисному решению системы ограничений ЗЛП соответствует угловая точка многоугольника решений. Справедлива и обратная теорема: каждой угловой точке множества допустимых решений системы ограничений (многоугольника решений) соответствует допустимое базисное решение. Обобщая упомянутые в этом параграфе теоремы можно сформулировать следствия: если существуют, и при том единственное оптимальное решение задачи линейного программирования, то оно совпадает с одним из допустимых базисных решений системы ограничений.

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

Число перебираемых допустимых базисных решений можно значительно сократить, если производить перебор не беспорядочно, а с учетом изменения целевой функции, добиваясь, чтобы каждое следующее решение было «лучше» или, по крайней мере «не хуже», чем предыдущее, то есть увеличивалось при отыскании максимума, и уменьшалось при отыскании минимума. Идея последовательного улучшения легла в основу универсального метода решения ЗЛП – симплекс-метода.

Впервые симлексный метод решения был предложен американским ученым Дж.Данцигом в 1949 году, хотя еще в 1939 году его идеи были разработаны советским ученым Л.В. Канторовичем. На основе симплекс метода создан пакет прикладных программ 1рх88, обладающий достаточно большими вычислительными возможностями. Однако, студентом необходимо ознакомиться с сутью этого метода, которую мы изложим на примере.

Симплекс-метод изложим для ЗЛП, поставленной в канонической форме: f→ min, ограничения в виде системы уравнений, число переменных любое.

Пример. Решить симплекс-методом задачу:

F=4-x₂+x₅→ min;

 

1. Проверим, является ли система уравнений совместной. Для этого найдем ранг матрицы и ранг расширенной матрицы:

; r( )=r( )=3.

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

1 этап: х₁, х₃, х₄ – базисные, х₂, х₅ – свободные;

Проверим, является ли построенное базисное решение допустимым, то есть выполняются ли неравенства X_j≥ 0. Если решения не является допустимым, в качестве базисных выбираем три другие переменные, при которых определитель не равен нулю.

3. Поставим вопрос – можно ли каким либо образом «улучшить» решение? Легко понять, что функцию можно уменьшить за счёт увеличения любой свободной переменной, входящей в выражение целевой функции с отрицательным коэффициентом. Это можно осуществить, перейдя к такому новому допустимому базисному решению, в котором эта переменная станет базисной и примет не нулевое, а положительное значение. Формальным признаком выбором такой переменной является знак «минус» перед свободной переменной в выражении целевой функции. В нашем случае это переменная х_2.

Однако, базисных переменных должно быть на каждом этапе решения задачи ровно 3, т.к. r=3. Чем больше будет значение переменной, тем меньше будет значение целевой функции, но система ограничений накладывает условия на рост переменной x₂.

Поскольку необходимо сохранить допустимость решений, т.е. все переменные должны остаться неотрицательными, то должны выполняться следующие неравенства (x₅=0 как свободная переменная):

Формально оценочные отношения для x₂ можно получить, составляя для каждого уравнения системы ограничения отношение свободного члена к коэффициенту при меняемой переменной, если меняемая переменная входит в выражение целевой функции со знаком « - »; если меняемая переменная не входит в уравнение или входит с положительным кооэффициентом, то это отношение заменяем символом ~. Очевидно, что сохранение неотрицательности всех переменных решения возможно, если не нарушается ни одна из полученных во всех уравнениях границ. В данном примере наибольшее возможное значение для переменной x₂ определяется как x₂=min{5, ~, 3}=3. При x₂= 3 переменная x₄ обращается в нуль и переходит в свободные.

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

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

2 этап: X₁, х₂, х₃ - базисные, х₄, х₅ - свободные;

Проверяем можно ли " улучшить" решение, т.е. имеются ли в выраже­нии целевой функции свободные переменные с отрицательными коэффициентами. В нашем случае таковых нет. Задача решена, построенное решение оптимально.

Ответ: f_min = 1, .

Блок-схема симплекс-метода.

1. Постановка задачи в канонической форме. Построение исходного допустимого базисного решения.

2. Проверка критерия оптимальности. Если все свободные пере­менные входят в выражение целевой функции с положительными коэф­фициентами, то построенное решение оптимально, переходим к пункту
5; если критерий оптимальности не выполнен, то переходим к пункту
4.

3. Построение нового допустимого базисного решения.

4. Конец.

Доказано, что за конечное число шагов можно получить оптимальное решение.

 

Частный случай 1. Если на каком-то этапе решения ЗЛП в выра­жении целевой функции имеется свободная переменная с отрицатель­ным коэффициентом, а во все уравнения системы ограничений она ли­бо не входит, либо входит с положительным коэффициентом, то целевая функция не ограничена при данной системе ограничений. Опти­мального решения нет.

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

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

⇐ Предыдущая123456Следующая ⇒

Поделиться: