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

1. Общая постановка задачи линейного программирования. Графическое решение злп. Каноническая форма. Базисное решение

Система неравенств (1.1.1) называется системой ограничений задачи.

Неравенства (1.1.2) – условие не отрицательности переменных. Функция (1.1.3) – функция цели (целевая функция).

Вектор , удовлетворяющий неравенствам (1.1.1) и (1.1.2), называется планом задачи линейного программирования или допустимым вектором, или допустимым решением.

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

Вектор называется оптимальным решением или оптимальным планом, если для всех ( ).

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

Причины, по которым не может быть найдено оптимальное решение:

1. Функция на допустимом множестве G неограниченна. Эта задача называется неразрешимой из-за неограниченности целевой функции.

2. Допустимое множество G пусто ( ), то есть не существует допустимых решений.

Такая задача называется несовместимой.

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

Если задача линейного программирования имеет две переменные x₁ и x₂, то ее можно решить графически.

Решение задачи происходит в два этапа.

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

Этап 1. Построение допустимого множества

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

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

Если правая часть не равна нулю, то в качестве пробной точки удобнее всего выбрать начало координат (0,0).

Алгоритм выполнения первого этапа

Шаг 1: Выделение первого координатного угла.

Шаг 3: i-е неравенство записывается как уравнение.

Шаг 4: Полагаем, находим из уравнения.

Шаг 5: Полагаем, находим из уравнения.

Шаг 6: Через точку и проводится прямая.

Шаг 7: В левую часть неравенства подставляется точка с координатами . Если неравенство выполнено, то выбирается полуплоскость, содержащая начало координат, в противном случае — противоположная полуплоскость.

Шаг 8: Если , то , переходим к Шагу 3, иначе Шаг 9.

Шаг 9: Допустимое множество получено. Если оно пустое ( ), то выписывается ответ: «Задача несовместна», иначе переход к Этапу 2.

Этап 2: Поиск оптимальной точки

Рассмотрим градиент функции . Так как функция линейна, то ее градиент есть постоянный вектор с координатами .

Известно, что движение в направлении градиента увеличивает значение функции.

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

Алгоритм выполнения второго этапа

Шаг 1: Строится вектор градиент .

Шаг 2: Кладется линейка перпендикулярно вектору–градиенту.

Шаг 3: Линейка сдвигается параллельно самой себе по направлению вектора-градиента, пока хотя бы одна точка соответствующей прямой принадлежит допустимому множеству.

Шаг 4: Если при любом положении линейки перпендикулярно вектору-градиенту имеются точки допустимого множества, то выписывается ответ: «Задача неразрешима из-за неограниченности целевой функции» и переход к Шагу 10. Иначе Шаг 5.

Шаг 5: Находится последняя точка допустимого множества, лежащая на соответствующей линии уровня.

Шаг 6: Если эта точка неединственная, то выбирается точка, которая является пересечением двух прямых, ограничивающих допустимое множество.

Шаг 7: Выписывается система двух уравнений с двумя неизвестными.

Шаг 8: Из системы уравнений находится оптимальная точка .

Шаг 9: Находится оптимальное значение целевой функции .

Пример 1.1. Решить задачу линейного программирования графически.

Решение. Строим допустимое множество в соответствии с первым этапом алгоритма. В результате получаем ограниченную многогранную область (рис. 1.1).

В табл. 1.1 заданы точки, по которым строятся прямые (1.2.1)-(1.2.3).

Источник

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

Графический метод решения ЗЛП основан на утверждениях, приведенных в пункте 2.1. Согласно теореме 2, оптимальное решение находится в вершине области допустимых решений и поэтому решить ЗЛП – найти вершину области допустимых решений, координаты которой дают оптимальное значение целевой функции.

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

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

1. Построить прямые линии, уравнения которых получаем заменой в системе ограничений (2.1.2) знаков неравенств на знаки равенств.
2. Определить полуплоскости, соответствующие каждому неравенстве задачи.
3. Найти многоугольник решений ЗЛП, учитывая, что .
4. Построить вектор направлений =(с₁,с₂), который указывает направление наибольшего возрастания целевой функции ЗЛП (2.1.1).
5. Построить прямую z, которая проходит через область допустимых решений, перпендикулярно к вектору :. Это линия уровня.
6. Переместить прямую в направлении векторав случае максимизации целевой функции (или в противоположном направлении в случае минимизации целевой функции), найти вершину многоугольника решений ЗЛП, в которой целевая функция достигает экстремального значения.
7. Определить координаты точки, в которой целевая функция достигает оптимальное значения, и вычислить экстремальное значение целевой функции в этой точке.

Реализацию графического метода решения ЗЛП рассмотрим на примерах. Пример 2.2.1. Решить ЗЛП графическим методом: (2.2.1) max z=x₁+ 4x₂(2.2.2) Решение. Для построения области допустимых решений, которая состоит из пересечения полуплоскостей, соответствующих каждому неравенству системы ограничений (2.2.1), запишем уравнения граничных прямых: l₁: x₁ + 5x₂ = 5; l₂: x₁ + x₂ = 6; l₃: 7x₁ + x₂ = 7.

Замечание.	Для удобства построения прямой линии, ее уравнение можно привести к виду в отрезках на осях , (2.2.3) где параметры а,b– длины отрезков, отсекаемых прямой на соответствующих осяхОх1,Ох2 .
Замечание.	Если уравнение прямой линии имеет вид: , то она проходит через точку с координатами (0;0). Для ее построения следует выразитьx2 через x1, и найти еще одну точку.

Для приведения уравнения прямой l₁ к виду (2.2.3.) разделим обе его части на 5: . Таким образом, прямаяl₁ отсекает на оси Ох₁ 5 единиц, на оси Ох₂ 1 единицу. Аналогично имеем для l₂: иl₃: . Для определения полуплоскостей, которые отвечают ограничениям системы (2.2.1), в ограничения нужно подставить координаты какой-либо точки, не лежащей на граничной прямой. Если получим верное неравенство, то все точки из этой полуплоскости являются решениями данного неравенства. В противном случае выбирают другую полуплоскость.

Замечание.

В качестве точки сравнения целесообразно выбирать, если это возможно, точку О(0,0).

Таким образом, первая и вторая искомые полуплоскости расположены в противоположную сторону от начала координат (0 – 5·0– 5; 7·0 + 07), а вторая – в сторону начала координат (0 + 06). Область допустимых решений на рисунке 2.2.1 заштрихована.

Замечание.

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

Рисунок 2.2.1 – Область допустимых решений Для нахождения оптимального плана, который будет находиться в вершине многоугольника решений, нужно построить вектор направлений =(с₁,с₂), который указывает направление наибольшего возрастания целевой функцииz=с₁х₁+с₂х₂. В данной задаче вектор направлений = (1, 4): он начинается в точкеО(0,0) и заканчивается в точкеN(1, 4). Далее строим прямую, которая проходит через область допустимых решений, перпендикулярно к вектору , и называетсялинией уровня целевойфункции.Передвигаем линию уровня в направлении векторав случае максимизации целевой функцииzи в направлении противоположном, в случае минимизацииz, до последнего пересечения с областью допустимых решений. В результате определяется точка или точки, где целевая функция достигает экстремального значения, или устанавливается неограниченность целевой функцииzна множестве решений задачи. Таким образом, точкой максимума целевой функции zявляется точкаАпересечения прямыхl₂иl₃. Для вычисления оптимального значения целевой функции z найдем координаты точки А. Поскольку точка А – это точка пересечения прямых l₂ и l₃, то ее координаты удовлетворяют системе уравнений, составленной из уравнений соответствующих граничных прямых:Таким образом, точка А имеет координаты x₁ =1/6, x₂ = 35/6.Для вычисления оптимального значения целевой функции нужно подставить в нее координаты точки А.Подставив координаты точки А в целевую функцию (2.4), получимmax z = 1/6 + 4·(35/6) = 47/2.Пример 2.2.2. Построить на плоскости область допустимых решений системы линейных неравенств (2.2.4) и найти наибольшее и наименьшее значения целевой функции (2.2.5):(2.2.4) z= –2x₁–x₂(2.2.5) Решение. Для построения области допустимых решений, которая состоит из пересечения полуплоскостей, соответствующих каждому неравенству системы ограничений (2.2.4), запишем уравнения граничных прямых: l₁: 4x₁ – x₂ = 0; l₂: x₁ + 3x₂ = 6; l₃: x₁ – 3x₂ = 6; l₄: x₂ = 1. Прямая l₁ проходит через точку с координатами (0;0). Для ее построения выразим x₂ через x₁: x₂ = 4x₁. Найдем еще одну точку, через которую проходит прямая l₁ , например (1;4). Через точку с координатами (0;0) и точку с координатами (1;4) проведем прямую l₁ . Для приведения уравнения прямой l₂ к виду в отрезках на осях (2.2.3) разделим обе его части на 6: . Таким образом, прямаяl₂ отсекает на оси Ох₁ 6 единиц, на оси Ох₂ — 2 единицы. Аналогично имеем для l₃: и Прямаяl₄ параллельна оси Ох₁ и проходит через точку с координатами (0;1) . Для определения полуплоскостей, которые отвечают ограничениям системы (2.2.4) в ограничения нужно подставить координаты какой-либо точки, не лежащей на граничной прямой. В силу ограниченийх₁0,х₂0, область допустимых решений ЗЛП лежит в первой четверти координатной плоскости.Область допустимых решений на рисунке 2.2.2 заштрихована. Рисунок 2.2.2 – Область допустимых решений Построим вектор направлений = (–2,–1). Далее строим линию уровня, перпендикулярно к вектору. Для нахождения наибольшего значения целевой функции передвигаем линию уровня в направлении вектора до последнего пересечения с областью допустимых решений. Таким образом, точкой максимума целевой функцииzявляется точкаА(пересечение прямыхl₁иl₂). Для вычисления оптимального значения целевой функции zнайдем координаты точкиА. Поскольку точкаА– это точка пересечения прямыхl₁иl₂, то ее координаты удовлетворяют системе уравнений, составленной из уравнений соответствующих граничных прямых: Таким образом, точка А имеет координаты x₁ =6/13, x₂ = 24/13.Подставив координаты точки А в целевую функцию (2.2.5), получим оптимальное значение целевой функции max z= – 2·(6/13) – (24/13) = – 36/13. Для нахождения наименьшего значения целевой функции передвигаем линию уровня в направлении, противоположном вектору до последнего пересечения с областью допустимых решений. В этом случае целевая функция неограниченна в области допустимых решений, т.е. ЗЛП минимума не имеет. В результате решения ЗЛП возможны следующие случаи:

• Целевая функция достигает оптимального значения в единственной вершине многоугольника решений;
• Целевая функция достигает оптимальное значение в любой точке ребра многоугольника решений (ЗЛП имеет альтернативные опорные планы с одинаковыми значениями z);
• ЗЛП не имеет оптимальных планов;
• ЗЛП имеет оптимальный план в случае неограниченной области допустимых решений.

Источник