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

Описание метода

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

Рассмотрим задачу линейного программирования с двумя переменными и :
(1.1) ;
(1.2)
Здесь , есть произвольные числа. Задача может быть как на нахождение максимума (max), так и на нахождение минимума (min). В системе ограничений могут присутствовать как знаки , так и знаки .

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

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

Так, первое неравенство
(1.2.1)
определяет полуплоскость, ограниченную прямой . С одной стороны от этой прямой , а с другой стороны . На самой прямой . Чтобы узнать, с какой стороны выполняется неравенство (1.2.1), мы выбираем произвольную точку, не лежащую на прямой. Далее подставляем координаты этой точки в (1.2.1). Если неравенство выполняется, то полуплоскость содержит выбранную точку. Если неравенство не выполняется, то полуплоскость расположена с другой стороны (не содержит выбранную точку). Заштриховываем полуплоскость, для которой выполняется неравенство (1.2.1).

Тоже самое выполняем для остальных неравенств системы (1.2). Так мы получим заштрихованных полуплоскостей. Точки области допустимых решений удовлетворяют всем неравенствам (1.2). Поэтому, графически, область допустимых решений (ОДР) является пересечением всех построенных полуплоскостей. Заштриховываем ОДР. Она представляет собой выпуклый многоугольник, грани которого принадлежат построенным прямым. Также ОДР может быть неограниченной выпуклой фигурой, отрезком, лучом или прямой.

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

Можно упростить метод. Можно не заштриховывать каждую полуплоскость, а вначале построить все прямые
(2)
Далее выбрать произвольную точку, не принадлежащую ни одной из этих прямых. Подставить координаты этой точки в систему неравенств (1.2). Если все неравенства выполняются, то область допустимых решений ограничена построенными прямыми и включает в себя выбранную точку. Заштриховываем область допустимых решений по границам прямых так, чтобы оно включало в себя выбранную точку.

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

Нахождение экстремума целевой функции

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

Теперь мы можем искать экстремум целевой функции
(1.1) .

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

Таким образом, чтобы найти максимальное значение целевой функции, надо провести прямую, параллельную прямой (3), максимально удаленную от нее в сторону возрастания значений , и проходящую хотя бы через одну точку ОДР. Чтобы найти минимальное значение целевой функции, надо провести прямую, параллельную прямой (3) и максимально удаленную от нее в сторону убывания значений , и проходящую хотя бы через одну точку ОДР.

Если ОДР неограниченна, то может возникнуть случай, когда такую прямую провести нельзя. То есть как бы мы ни удаляли прямую от линии уровня (3) в сторону возрастания (убывания) , то прямая всегда будет проходить через ОДР. В этом случае может быть сколь угодно большим (малым). Поэтому максимального (минимального) значения нет. Задача решений не имеет.

Рассмотрим случай, когда крайняя прямая, параллельная произвольной прямой вида (3), проходит через одну вершину многоугольника ОДР. Из графика определяем координаты этой вершины. Тогда максимальное (минимальное) значение целевой функции определяется по формуле:
.
Решением задачи является
.

Также может встретиться случай, когда прямая параллельна одной из граней ОДР. Тогда прямая проходит через две вершины многоугольника ОДР. Определяем координаты и этих вершин. Для определения максимального (минимального) значения целевой функции, можно использовать координаты любой из этих вершин:
.
Задача имеет бесконечно много решений. Решением является любая точка, расположенная на отрезке между точками и , включая сами точки и .

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

Фирма выпускает платья двух моделей А и В. При этом используется ткань трех видов. На изготовление одного платья модели А требуется 2 м ткани первого вида, 1 м ткани второго вида, 2 м ткани третьего вида. На изготовление одного платья модели В требуется 3 м ткани первого вида, 1 м ткани второго вида, 2 м ткани третьего вида. Запасы ткани первого вида составляют 21 м, второго вида — 10 м, третьего вида — 16 м. Выпуск одного изделия типа А приносит доход 400 ден. ед., одного изделия типа В — 300 ден. ед.

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

Пусть переменные и означают количество произведенных платьев моделей А и В, соответственно. Тогда количество израсходованной ткани первого вида составит:
(м)
Количество израсходованной ткани второго вида составит:
(м)
Количество израсходованной ткани третьего вида составит:
(м)
Поскольку произведенное количество платьев не может быть отрицательным, то
и .
Доход от произведенных платьев составит:
(ден. ед.)

Тогда экономико-математическая модель задачи имеет вид:

Решаем графическим методом.
Проводим оси координат и .

Строим прямую .
При .
При .
Проводим прямую через точки (0; 7) и (10,5; 0).

Строим прямую .
При .
При .
Проводим прямую через точки (0; 10) и (10; 0).

Строим прямую .
При .
При .
Проводим прямую через точки (0; 8) и (8; 0).

Прямые и являются осями координат.

Область допустимых решений (ОДР) ограничена построенными прямыми и осями координат. Чтобы узнать, с какой стороны, замечаем, что точка принадлежит ОДР, поскольку удовлетворяет системе неравенств:

Заштриховываем область, чтобы точка (2; 2) попала в заштрихованную часть. Получаем четырехугольник OABC.

Строим произвольную линию уровня целевой функции, например,
(П1.1) .
При .
При .
Проводим прямую через точки (0; 4) и (3; 0).

Далее замечаем, что поскольку коэффициенты при и целевой функции положительны (400 и 300), то она возрастает при увеличении и . Проводим прямую, параллельную прямой (П1.1), максимально удаленную от нее в сторону возрастания , и проходящую хотя бы через одну точку четырехугольника OABC. Такая прямая проходит через точку C. Из построения определяем ее координаты.
.

.
То есть, для получения наибольшего дохода, необходимо изготовить 8 платьев модели А. Доход при этом составит 3200 ден. ед.

Пример 2

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

Решаем графическим методом.
Проводим оси координат и .

Строим прямую .
При .
При .
Проводим прямую через точки (0; 6) и (6; 0).

Строим прямую .
Отсюда .
При .
При .
Проводим прямую через точки (3; 0) и (7; 2).

Строим прямую .
Строим прямую (ось абсцисс).

Область допустимых решений (ОДР) ограничена построенными прямыми. Чтобы узнать, с какой стороны, замечаем, что точка принадлежит ОДР, поскольку удовлетворяет системе неравенств:

Заштриховываем область по границам построенных прямых, чтобы точка (4; 1) попала в заштрихованную часть. Получаем треугольник ABC.

Строим произвольную линию уровня целевой функции, например,
.
При .
При .
Проводим прямую линию уровня через точки (0; 6) и (4; 0).
Поскольку целевая функция увеличивается при увеличении и , то проводим прямую, параллельную линии уровня и максимально удаленную от нее в сторону возрастания , и проходящую хотя бы через одну точку треугольника АВC. Такая прямая проходит через точку C. Из построения определяем ее координаты.
.

Пример отсутствия решения

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

Решаем задачу графическим методом.
Проводим оси координат и .

Строим прямую .
При .
При .
Проводим прямую через точки (0; 8) и (2,667; 0).

Строим прямую .
При .
При .
Проводим прямую через точки (0; 3) и (6; 0).

Строим прямую .
При .
При .
Проводим прямую через точки (3; 0) и (6; 3).

Прямые и являются осями координат.

Область допустимых решений (ОДР) ограничена построенными прямыми и осями координат. Чтобы узнать, с какой стороны, замечаем, что точка принадлежит ОДР, поскольку удовлетворяет системе неравенств:

Заштриховываем область, чтобы точка (3; 3) попала в заштрихованную часть. Получаем неограниченную область, ограниченную ломаной ABCDE.

Строим произвольную линию уровня целевой функции, например,
(П3.1) .
При .
При .
Проводим прямую через точки (0; 7) и (7; 0).
Поскольку коэффициенты при и положительны, то возрастает при увеличении и .

Чтобы найти максимум, нужно провести параллельную прямую, максимально удаленную в сторону возрастания , и проходящую хотя бы через одну точку области ABCDE. Однако, поскольку область неограниченна со стороны больших значений и , то такую прямую провести нельзя. Какую бы прямую мы не провели, всегда найдутся точки области, более удаленные в сторону увеличения и . Поэтому максимума не существует. можно сделать сколь угодно большой.

Ищем минимум. Проводим прямую, параллельную прямой (П3.1) и максимально удаленную от нее в сторону убывания , и проходящую хотя бы через одну точку области ABCDE. Такая прямая проходит через точку C. Из построения определяем ее координаты.
.
Минимальное значение целевой функции:

Максимального значения не существует.
Минимальное значение
.

Автор: Олег Одинцов . Опубликовано: 08-08-2016

Источник

Графический способ решения производственной задачи

Условие

Сначала запишем условие производственной задачи из предыдущей главы:

Ресурс	Изделие A	Изделие B	Сколько ресурса на складах
R1	1	3	15
R2	2	1	20
R3	3	2	35
Прибыль	5	10

У нас получилась система ограничений и целевая функция следующего вида:

Строим область допустимых решений

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

Мы получили пять уравнений с двумя переменными, следовательно, мы можем построить их графики. Например, мы можем направить ось с переменной $x_A$ вправо (где обычно у нас ось абсцисс) и ось с переменной $x_B$ вверх (где обычно у нас ось ординат). Для построения графиков нужно лишь выразить из этих уравнений $x_B$. Сделаем это:

Прежде чем строить графики, разберемся с последними двумя уравнениями, $x_A=0$ и $x_B=0$. Эти уравнения выражают сами оси — абсцисс и ординат. А так как в исходных ограничениях были неравенства $x_A\geq0$ и $x_B\geq0$, то точка нашего решения должна быть правее и выше, чем эти оси — то есть, находиться в первой четверти. Поэтому эти две линии можно не строить, а просто учитывать, что решение в первой четверти.

Остальные линии мы построим на графике, и получим следующую картину (естественно, на нормальном графике не нужно рисовать такие стрелки, они лишь для наглядности, чтобы не перепутать линии друг с другом):

Каждая из этих линий разбивает область допустимых решений на две — одна находится правее и выше каждой из этих линий, вторая — левее и ниже. Какая из них нужна нам? Та, которая левее и ниже. Во-первых, в исходных неравенствах у нас был знак «меньше или равно», а левее и ниже как раз более маленькие значения переменных. А во-вторых, как мы говорили в предыдущем пункте, решение (0,0) вполне удовлетворяет условию задачи, хоть и не является оптимальным. А точка (0,0) — начало координат — расположена как раз левее и ниже каждой из прямых.

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

Эта область, во-первых, расположена в первой четверти, как и должно быть, во-вторых, левее и ниже прямых $x_B=5-\frac<1><3>x_A$ и $x_B=20-2x_A$. Прямая $x_B=17,5-1,5x_A$ оказалась не участвующей в решении, так иногда бывает, это не страшно.

Далее задачу можно решать двумя способами.

Основной способ

Рассмотрим первый из них. Для него нужно нарисовать линию нулевого дохода, то есть, линию, при которой целевая функция равна нулю: $5x_A+10x_B=0$. Если упростить данное выражение, получим $x_B=-0,5x_A$. Построим эту функцию красным цветом, и уберем подписи. Она будет расположена не в первой четверти, это нормально.

Эта линия состоит из точек, каждая из которых является решением, применяя которое, мы получим нулевой доход. Однако с тем условием, что $x_A,x_B\geq0$, такое решение мы получаем всего одно — в точке (0,0) — остальные точки лежат во второй и четвертой четверти.

Что будет, если эту линию поднимать выше (параллельным переносом)? Мы получим линии, которые будут давать больший, чем 0 доход. Получается, чем выше мы поднимем данную линию, тем лучше. Однако совсем до бесконечности поднимать ее не получится, ведь она должна хотя бы касаться разрешенной области, обозначенной серым цветом (сейчас она касается только в точке (0,0)). Попробуем провести (пока на глаз) линии, параллельные данной, через оставшиеся три точки многоугольника:

Мы нарисовали еще две линии, параллельные линии нулевого дохода, но расположенные выше. Средняя из них проходит через две точки нашего многоугольника с решениями, а самая высокая — через еще одну точку многоугольника. Кроме того, она вообще пересекает наш многоугольник в одной-единственной точке. И еще выше данную линию поднять нельзя — она вообще перестанет пересекать наш многоугольник. Следовательно, эта линия и есть «линия максимального дохода», а наше решение находится, как раз, в той точке, в которой эта линия пересекает нашу область допустимых решений — в точке пересечения линий $x_B=5-\frac<1><3>x_A$ и $x_B=20-2x_A$. Найдем координаты данной точки. Для этого приравняем эти два значения для $x_B$:

$$5-\frac<1><3>x_A=20-2x_A$$ $$-\frac<1><3>x_A+2x_A=20-5$$ $$\frac<5><3>x_A=15$$ $$5x_A=45$$ $$x_A=9$$ $$x_B=20-2\cdot9=20-18=2$$

Итак, наше решение находится в точке (9,2). Это означает, что необходимо производить 9 единиц изделия A и 2 единицы изделия B. При этом мы получим прибыль

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

Другой способ

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

Найдем координаты каждой из них. Координаты точки O мы знаем — (0,0). Координаты точки B мы нашли выше (по первому способу) — (9,2). Точка A — это точка на прямой $x_B=5-\frac<1><3>x_A$, причем $x_A=0$. Следовательно $x_B=5$. То есть, ее координаты (0,5). Точка C — это точка на прямой $x_B=20-2x_A$, причем $x_B=0$. То есть, $20-2x_A=0$, $2x_A=20$, $x_A=10$. Следовательно, ее координаты (10,0).

Теперь найдем значение целевой функции в каждой из данных точек:

$$F(O)=F(0,0)=5\cdot0+10\cdot0=0+0=0$$ $$F(A)=F(0,5)=5\cdot0+10\cdot5=0+50=50$$ $$F(B)=F(9,2)=5\cdot9+10\cdot2=45+20=65$$ $$F(C)=F(10,0)=5\cdot10+10\cdot0=50+0=50$$

Действительно, в точке B наша функция принимает максимальное значение, равное 65. Это и есть максимальная прибыль, которую можно получить в данном случае.

А если товаров больше?

Как говорилось в предыдущем разделе, графическим способом можно решать только задачу для двух производимых товаров. Это потому, что если товаров будет больше двух, то и переменных будет больше двух, например, три — $x_A, x_B, x_C$. И тогда придется строить трехмерный график, в котором запросто можно запутаться. А если переменных больше трех, то график не построить вообще. Однако специально для этих случаев был разработан еще один метод решения задач линейного программирования, и, в частности, производственной задачи — симплекс-метод, который мы рассмотрим в следующей главе.

Источник