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

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

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

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

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

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

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

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

при условиях:

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

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

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

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

Чтобы определить, какую именно полуплоскость определяет данное неравенство, достаточно взять произвольную точку плоскости (Графическое решение задач линейного программирования) (например, начало координат) и подставить в неравенство числа Графическое решение задач линейного программирования. Если оно удовлетворится, то полуплоскость, в которой лежит данная точка — искомая. В противном случае нужная полуплоскость лежит по другую сторону прямой Графическое решение задач линейного программирования [26].

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

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

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

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

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

Рассмотрим целевую функцию

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

Уравнение

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

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

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

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

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

Таким образом, можно определить алгоритм геометрического (графического) решения задач линейного программирования:

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

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

  1. Построение пространства допустимых решений, удовлетворяющих всем ограничениям модели.
  2. Поиск оптимального решения среди всех точек пространства допустимых решений.

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

Пример решения задачи №1:

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

Задана стандартная математическая модель задачи с двумя неизвестными:

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

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

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

При геометрической интерпретации задач ЛП могут встретиться случаи, изображенные на рис. 2.1. — 2.4.

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

Рис. 2.2. Задача ЛП имеет бесчисленное множество решений, т.к. целевая функция достигает максимума на отрезке Графическое решение задач линейного программирования.

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

Рис. 2.3. Задача ЛП не имеет решения, т.к. функция неограниченна сверху.
Рис. 2.4. Задача ЛП не имеет решения, т.к. система (2.1) несовместна.

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

Пример решения задачи №2:

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

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

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

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

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

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

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

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

Итак, мы получили стандартную модель с двумя переменными.

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

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

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

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

Наибольшая прибыль будет равна 1080 (у.е).

Пример решения задачи №3:

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

Минимизировать функцию

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

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

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

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

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

Минимальное значение функции Графическое решение задач линейного программирования = — 68 и достигается в точке Графическое решение задач линейного программирования = (12,8). Заметим, что, как и в примере разд. 1.1, минимум достигается в вершине допустимой области. Оптимальным решением задачи является точках Графическое решение задач линейного программирования = 2, Графическое решение задач линейного программирования = 8 с минимальным значением функции Графическое решение задач линейного программирования = — 68.

Иногда задача имеет более чем одно оптимальное решение.

Пример решения задачи №4:

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

Минимизировать функцию

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

при ограничениях

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

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

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

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

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

где

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

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

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

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

Иногда решение задачи не ограничено.

Пример решения задачи №5:

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

Максимизировать функцию

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

при ограничениях

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

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

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

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

Пример решения задачи №6:

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

Минимизировать функцию

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

при ограничениях

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

Ограничения задачи противоречивы, поэтому нет допустимых решений (рис. 1.5).

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

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

Пример решения задачи №7:

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

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

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

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

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

Пример решения задачи №8:

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

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

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

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

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

Пример решения задачи 9:

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

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

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

Всем неравенствам системы ограничений удовлетворяют точки треугольника Графическое решение задач линейного программирования, который и является областью решений (рис. 5). Максимальное значение Графическое решение задач линейного программирования. При построении треугольника Графическое решение задач линейного программирования не использовали прямые Графическое решение задач линейного программирования, хотя все точки этого треугольника удовлетворяют неравенствам Графическое решение задач линейного программирования. Таким образом, эти неравенства лишние в системе ограничений.

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

Пример решения задачи №10:

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

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

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

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

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

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

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

т.е.

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

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

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

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

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

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

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

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