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

Введение

К оглавлению…

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

Возможно эта страница вам будет полезна:

Предмет математическое программирование

Задача линейного программирования в стандартной форме с двумя переменными имеет вид:

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

Эти задачи допускают простое геометрическое истолкование.

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

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

Рассмотрим прямую на плоскости с уравнением:

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

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

При решении двумерных задач линейного программирования возможны следующие ситуации (ОДР — область допустимых решений):

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

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

Отметим, что при нахождении решения задачи (5.1)-(5.3) могут встретиться случаи, изображенные на рис. 5.2- 5.5. Рис.5.2 характеризует такой случай, когда целевая функция принимает максимальное значение в единственной точке Графический метод решения задач линейного программирования. Из рис. 5.3 видно, что максимальное значение целевая функция принимает в любой точке отрезка Графический метод решения задач линейного программирования. На рис.5.4 изображен случай, когда целевая функция неограничена сверху на множестве допустимых решений, а на рис.5.5 — случай, когда система ограничений задачи несовместна, т. е. если система неравенств (5.1) при условии (5.2) не имеет решений.

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

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

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

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

К оглавлению…

  1. Построить область допустимых решений.
  2. Если область допустимых решений является пустым множеством, то задача не имеет решения ввиду несовместности системы ограничений.
  3. Если область допустимых решений является непустым множеством, построить нормаль линий уровня Графический метод решения задач линейного программирования и одну из линий уровня, имеющую общие точки с этой областью.
  4. Линию уровня переместить до опорной прямой в задаче на максимум в направлении нормали, в задаче на минимум — в противоположном направлении.
  5. Если при перемещении линии уровня по области допустимых решений в направлении, соответствующем приближению к экстремуму целевой функции, линия уровня уходит в бесконечность, то задача не имеет решения ввиду неограниченности целевой функции.
  6. Если задача линейного программирования имеет оптимальное решение, то для его нахождения решить совместно уравнения прямых, ограничивающих область допустимых решений и имеющих общие точки с соответствующей опорной прямой. Если целевая функция задачи достигает экстремума в двух угловых точках, то задача имеет бесконечное множество решений. Оптимальным решением является любая выпуклая линейная комбинация этих точек. После нахождения оптимальных решений вычислить значение целевой функции на этих решениях.

Пример задачи №1

К оглавлению…

Пусть имеется два станка Графический метод решения задач линейного программирования, на каждом из которых можно производить два вида продукции Графический метод решения задач линейного программирования. Станок Графический метод решения задач линейного программирования производит единицу продукции Графический метод решения задач линейного программирования за 1 час, а единицу продукции Графический метод решения задач линейного программирования — за 2 часа. Станок Графический метод решения задач линейного программирования затрачивает на единицу продукции Графический метод решения задач линейного программирования — 2 часа, а на единицу продукции Графический метод решения задач линейного программирования — 1 час. Станок Графический метод решения задач линейного программирования может работать в сутки не более 10 ч., а станок Графический метод решения задач линейного программирования — не более 8 ч. Стоимость единицы продукции Графический метод решения задач линейного программирования составляет Графический метод решения задач линейного программирования руб., а стоимость единицы продукции Графический метод решения задач линейного программированияГрафический метод решения задач линейного программирования руб. Требуется определить такие объемы выпуска продукции Графический метод решения задач линейного программирования и Графический метод решения задач линейного программирования на станок, чтобы выручка от реализации производственной продукции была максимальной.

Решение:

Для наглядности сведем условие задачи в таблицу 5.1.

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

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

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

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

Аналогично можно получить неравенство для станка Графический метод решения задач линейного программирования. Кроме того, величины Графический метод решения задач линейного программирования и Графический метод решения задач линейного программирования не могут быть отрицательными:

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

по смыслу задачи. Такие задачи кратко записываются следующим образом:

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

Итак, математическая модель задачи: найти такой план выпуска продукции Графический метод решения задач линейного программирования, удовлетворяющий системе (5.4) и условию (5.5), при котором функция (5.6) принимает максимальное значение.

Решения, удовлетворяющие системе ограничений (5.4) и требованиям неотрицательности (5.5), являются допустимыми, а решения, удовлетворяющие одновременно и требованию (5.6) — оптимальными.

Рассмотрим геометрическое истолкование задачи:

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

Математическая модель задачи:

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

Построение области допустимых решений целевой функции Графический метод решения задач линейного программирования:

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

Рассмотрим первое ограничение:

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

Рассмотрим второе ограничение:

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

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

  • Построим нормаль линий уровня Графический метод решения задач линейного программирования.
  • Линию уровня Fпереместим до опорной прямой в направлении нормали, т.к. в задаче необходимо определить максимум целевой функции.
  • Точкой максимума здесь является точка Графический метод решения задач линейного программирования, координаты которой определяются из системы уравнений (5.4), решая которую, получаем точку максимума Графический метод решения задач линейного программирования.(см. рис.5.6)
Графический метод решения задач линейного программирования

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

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

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

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

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

К оглавлению…

Множество решений системы ограничений задачи ЛП образует область допустимых решений (ОДР).

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

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

I. Одномерное пространство переменных

К оглавлению…

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

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

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

В случае неограниченности ОДР задача ЛП может и не иметь оптимума.

II. Двумерное пространство переменных

К оглавлению…

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

Областью решений линейного неравенства

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

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

Решение системы ограничений есть пересечение полуплоскостей с граничными прямыми

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

многоугольник решений (ОДР).

Линией уровня называется прямая, на которой целевая функция задачи принимает постоянное значение. Уравнение

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

задаёт семейство линий уровня исследуемой целевой функции Графический метод решения задач линейного программирования — параллельные прямые с нормальным вектором Графический метод решения задач линейного программирования, который определяет направление роста функции Графический метод решения задач линейного программирования, т. к. является её градиентом.

Замечание.

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

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

• Прямая

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

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

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

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

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

Замечание. Если заданы ограничения неотрицательности переменных, то все построения проводятся в первой четверти.

Особые случаи

К оглавлению…

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

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

К оглавлению…

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

Пример задачи №2

К оглавлению…

Найти Графический метод решения задач линейного программирования, при котором функция достигает экстремума:

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

если имеются ограничения:

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

Решение:

Система ограничений определяет граничные прямые:

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

С учётом исходной системы неравенств строим ОДР.

Прямая

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

имеет вектор нормали Графический метод решения задач линейного программирования(5;4) и направляющий вектор Графический метод решения задач линейного программирования(-4;5). Опорное положение максимума линия уровня функции Графический метод решения задач линейного программирования занимает в точке Графический метод решения задач линейного программирования (направление роста вектора нормали); в точке Графический метод решения задач линейного программирования — опорное положение минимального значения линия уровня функции.

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

Т. о. имеем:

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

Тогда

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

Ответ:

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

Пример задачи №3

К оглавлению…

Найти план

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

при котором:

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

Решение:

Строим ОДР, проводим линии уровня Графический метод решения задач линейного программирования:

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

и вектор Графический метод решения задач линейного программирования = (4; 2). Т. к. решается задача на отыскание минимума функции, то фиксируем положение опорной прямой в направлении, противоположном вектору Графический метод решения задач линейного программирования. В результате опорная прямая совпадает с граничной прямой Графический метод решения задач линейного программирования и проходит через две угловые точки Графический метод решения задач линейного программирования и Графический метод решения задач линейного программирования. Задача имеет бесконечно много оптимальных решений, являющихся точками отрезка Графический метод решения задач линейного программирования.

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

Общее решение (выпуклая линейная комбинация точек отрезка Графический метод решения задач линейного программирования) имеет вид:

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

Вычисляем

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

Ответ:

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

Пример задачи №4

К оглавлению…

Найти план

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

при котором

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

Решение:

Строим ОДР, проводим линию уровня Графический метод решения задач линейного программирования:

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

и вектор Графический метод решения задач линейного программирования= (3;7). В данной задаче необходимо найти максимум целевой функции, поэтому линию уровня фиксируем в направлении нормального вектора. В виду того, что в направлении вектора нормали ОДР не ограничена, линия уровня уходит в бесконечность, т. е. max Графический метод решения задач линейного программирования

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

Пример задачи №5

К оглавлению…

Найти план

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

при котором

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

Решение:

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

III. Трёхмерное пространство переменных

К оглавлению…

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

Решение системы ограничений — многогранник решений (ОДР) — пересечение полупространств с граничными плоскостями

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

Уравнение

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

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

Плоскость

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

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

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

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

Основной случай: система ограничений содержит Графический метод решения задач линейного программирования переменных и Графический метод решения задач линейного программирования линейно независимых уравнения:

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

Расширенную матрицу системы с помощью элементарных преобразований строк можно привести к виду:

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

Тогда соответствующая система уравнений примет вид:

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

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

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

Подставляя полученные выражения для базисных неизвестных в целевую функцию, получим:

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

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

Найденное решение Графический метод решения задач линейного программирования подставляют в систему (*) и получают искомый оптимальный план

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

При этом оптимум:

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

Пример. Решить задачу ЛП:

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

Решение. Метод применим,так как Графический метод решения задач линейного программирования. Методом Жордана-Гаусса приведём систему уравнений ограничений задачи к равносильной путём выделения базисных и свободных переменных. Одновременно исключим базисные переменные из целевой функции.

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

Используя последнюю часть табл., запишем задачу ЛП в преобразованном виде:

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

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

Получим вспомогательную задачу ЛП с двумя переменными:

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

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

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

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

Вычисляем минимальное значение целевой функции

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

Находим оптимальное решение исходной задачи:

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

Т. о., получаем:

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

Возможно эти страницы вам будут полезны:

  1. Решение задач по математическому программированию
  2. Примеры решения задач по математическому программированию
  3. Заказать работу по математическому программированию
  4. Помощь по математическому программированию
  5. Задачи математического программирования
  6. Задача линейного программирования
  7. Примеры решения задач по линейному программированию
  8. Решение задач по линейному программированию
  9. Методы решения задач линейного программирования
  10. Графическое решение задач линейного программирования
  11. Заказать работу по линейному программированию
  12. Помощь по линейному программированию
  13. Контрольная работа по линейному программированию
  14. Линейное программирование в Excel
  15. Курсовая работа по линейному программированию