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

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

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

Сначала на координатной плоскости 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. Ограниченность целевой функции в допустимой области является необходимым и достаточным условием разрешимости задачи.

Источник

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник

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

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

1. На плоскости X₁0X₂ строят прямые.
2. Определяются полуплоскости.
3. Определяют многоугольник решений;
4. Строят вектор N(c₁,c₂), который указывает направление целевой функции;
5. Передвигают прямую целевую функцию c₁x₂+ c₂x₂ = 0 в направлении вектора N до крайней точки многоугольника решений.

Вычисляют координаты точки и значение целевой функции в этой точке.

Алгоритмический метод.

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

Рассмотренные выше методы служат для сбора информации о субъекте труда или профессиональной среде. Вместе с тем существует ряд методов упорядочения полученной информации. Одним из таких методов является алгоритмический анализ. Алгоритм — строгая последовательность действий, которая неизбежно приводит к решению задачи определенного класса. Эта последовательность действий может иметь словесное описание, в котором представлены все элементарные действия и логические условия, определяющие порядок этих действий, а может быть описана в символической форме или в виде графика. Метод дает возможность представить совокупность действий в компактной форме и понять их закономерные связи. Благодаря своей полноценности, конкретности и систематичности алгоритмы позволяют постепенно проследить характер операций, выполняемых работниками, и установить те звенья процесса, в которых наиболее часты аварии и брак и которые необходимо рационализировать или автоматизировать в первую очередь, либо функции, требующие перераспределения или изменения.

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

Введение в симплексный алгоритм.

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

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

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

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

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

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

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

Обратимся вначале к одной простой задаче, не имеющей никаких «аномалий», и попытаемся с ее помощью получить общее представ­ление о симплексном методе. К более подробному анализу данного метода вернемся несколько позже.

Источник