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

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

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

Сначала на координатной плоскости x₁Ox₂ строится допустимая многоугольная область (область допустимых решений, область определения), соответствующая ограничениям.

При этом могут быть получены следующие области:

1. Основной случай – получающаяся область имеет вид ограниченного выпуклого многоугольника (рис. 2.2, а).
2. Неосновной случай – получается неограниченный выпуклый многоугольник, имеющий вид, подобный изображенному на рис. 2.2, б.
3. Возможен случай, когда неравенства противоречат друг другу и допустимая область вообще пуста.

Рис. 2.2. Области определения решения:

а – основной случай, б – неосновной случай

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

Приравняем целевую функцию постоянной величине “a”. Меняя значение “a”, получим семейство параллельных прямых, каждая из которых является линией уровня.

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

При поиске максимума ЦФ необходимо передвигать целевую прямую в направлении вектора , при поиске минимума ЦФ – против направления вектора . Последняя по ходу движения вершина ОДР будет точкой максимума или минимума ЦФ.

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

Если такой точки (точек) не существует, то можно сделать вывод о неограниченности ЦФ на множестве планов сверху (при поиске максимума) или снизу (при поиске минимум).

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

Вернемся к целевой функции: . Допустим, значение функции L = 1 (абсолютно произвольно выбранное число), тогда . Данное уравнение является уравнением прямой на плоскости. Известно, что данная прямая перпендикулярна вектору, координатами которого являются коэффициенты функции, а именно вектору .

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

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

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

Решая совместно эти два уравнения, получим координаты этой точки x₁ = 1; x₂ = 2. При этом значение целевой функции , что и дает ее максимальное значение.

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

Подводя итог, можно сформулировать следующие положения:

1. Допустимая область – это выпуклый многоугольник.
2. Оптимум достигается в вершине допустимой области (если допустимая область ограничена и не пуста).
3. Ограниченность целевой функции в допустимой области является необходимым и достаточным условием разрешимости задачи.

Источник

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

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

Рисунок 2.3.8.

Построение области допустимых решений целевой функции F.

Первое ограничение:

Второе ограничение:

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

Рисунок 2.3.9.

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

1. Область допустимых решений ограниченна со всех сторон (примеры №1,2);

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

Примечание — Область допустимых решений всегда является выпуклым множеством. Множество S называется выпуклым, если для любых двух точек M и N этого множества весь отрезок MN содержится в множестве S. На рисунках изображены примеры выпуклых (рис. 1) и невыпуклых множеств (рис. 2).

Рисунок 2.3.10.

Рисунок 2.3.11.

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

Рассмотрим этот случай на примере.

Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:

Источник

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

Существуют два наиболее распространенных способа решения задач линейного программирования (ЗЛП): графический метод и симплекс-метод. Графический метод существенно нагляднее и обычно проще для понимания и решения (хотя занимает много времени, так как требует тщательного построения чертежа). Также этот метод позволяет практически одновременно найти решение на минимум и максимум, тогда как симплекс-методом придется делать «два подхода».

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

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

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

Задача 1. Колхоз имеет возможность приобрести не более 19 трехтонных автомашин и не более 17 пятитонных. Отпускная цена трехтонного грузовика — 4000 руб., пятитонного — 5000 руб. Колхоз может выделить для приобретения автомашин 141 тысяч рублей. Сколько нужно приобрести автомашин, чтобы их суммарная грузоподъемность была максимальной?
Задачу решить графическими и аналитическими методами.

Задача 2. Решить задачу графическим методом на минимум и на максимум

Задача 3. Решить задачу графическим методом на минимум и на максимум

Задача 4. Среди чисел x и y, удовлетворяющих условиям

найти такие, при которых разность этих чисел y-x принимает наибольшее значение.

Задача 5. Решить графическим методом ЗЛП, заданную указанной математической моделью.

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

Задача 7. Решить графическим методом

Источник

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

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

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

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

Рассмотрим для определенности задачу максимизации для целевой функции, зависящей от двух переменных:

,

(1.12)

Шаг 1. Построение множества допустимых планов.

Каждое -тое ограничение задачи записывается как равенство. Геометрически полученное уравнение определяет прямую линию, которая делит плоскость на две полуплоскости, в одной из которых выполняется условие , в другой. Полуплоскость, для точек которой выполняется требуемое ограничение, назовем допустимой полуплоскостью.

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

Шаг 2. Нахождение оптимального плана.

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

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

Для нахождения оптимальной точки рассмотрим целевую функцию задачи . Запишем ее в виде:

, где .

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

Вектор нормали к прямой к линии уровня целевой функции называется градиентом.Градиент указывает направление возрастания целевой функции.

Для нахождения точки экстремума графическим методом, необходимо сначала построить линию уровня для некоторого произвольного значения целевой функции. Затем осуществить ее параллельное передвижение в направлении градиента, если решается задача максимизации, и в обратном направлении, при решении задачи минимизации. Смещение производится до тех пор, пока не будет достигнута «последняя» точка области допустимых планов . Для задач максимизации (минимизации) такой точке области D соответствует наибольшее из возможных значений линии уровня. Последнее означает, что для нахождения точки экстремума в задаче линейного программирования мы должны сначала построить линию уровня для некоторого произвольного значения целевой функции. Затем необходимо осуществлять ее параллельное передвижение (так, чтобы она оставалась перпендикулярной векторус ) до тех пор, пока не достигнем такой точки области допустимых планов D , из которой смещение в направлении вектора с было бы невоз­можно. Такой метод решения получил название графического . Заметим, что решение задачи поиска минимума линейной функ­ции осуществляется аналогично, с той лишь разницей, что дви­жение по линиям уровня должно производиться в направлении, обратном градиенту целевой функции, т. е. по вектору (-с ).

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

Шаг 3. Нахождение максимального значения функции .

Аналитически оптимальная точка с координатами находится как точка пересечение двух прямых. Векторявляется оптимальным планом задачи. Затем вычисляется значение целевой функции в оптимальной точке.

Задача. При производстве товаров А и В используются три вида ресурсов: R1, R2, R3. Сведения о количестве ресурсов, необходимых для производства единицы каждого товара, запасе ресурсов и ценах, по которым товары продаются, приведены в табл. 1.3. Найдите оптимальный план, максимизурующий доход.

Источник