Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Задача с двумя переменными

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

Задача линейного программирования с двумя переменными должна иметь систему ограничений, представляющую собой систему неравенств. Неравенства могут быть как вида " £ ", так и " ³ ". Условия неотрицательности могут отсутствовать. Математическая модель должна иметь вид

Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru (2.1)

Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru (2.2)

Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru .

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

Теорема 2.1. О виде области решений линейного неравенства. Областью решений линейного неравенства Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru является одна из двух полуплоскостей, на которые разбивает всю координатную плоскость Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru прямая Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru , соответствующая этому неравенству.

Доказательство. В системе координат О Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru построим прямую Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru (L) и ее нормаль Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru (рис. 2.1).

Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru

Рис. 2.1

Прямая (L) разбивает плоскость О Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru на две полуплоскости: верхнюю ( Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru ), соответствующую направлению нормали Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru , и нижнюю ( Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru ). Пусть произвольно выбранная точка М( Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru ) принадлежит ( Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru ), ее проекцией на прямую (L) является точка Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru . Вектор Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru . Координаты векторов Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru и Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru совпадают с координатами точек М и А, т. е. Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru = ( Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru ), Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru . Вектор Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru коллинеарен вектору Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru , поэтому Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru = Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru ×l, где l некоторое число. Найдем скалярное произведение Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru . Запишем это равенство через координаты векторов Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru . Так как точка А принадлежит прямой (L), то Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru , получаем Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru .

Отсюда следует, что если l>0, т. е. M Î( Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru ), то Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru и тогда Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru . Если же l<0, M Î( Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru ), то Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru и Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru .

Пример 2.1. Найти область решений неравенства Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru .

Решение. Строим прямую Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru (рис. 2.2).

Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru
Рис. 2.2

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

В рассматриваемом примере в качестве "пробной" точки возьмем О(0, 0). Подставляем координаты этой точки в неравенство, получаем 2 × 0 + 3 × 0 £ 6 Û 0 £ 6, следовательно, областью решений является полуплоскость, содержащая начало координат. Этот факт отмечаем на рисунке стрелками.

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

Линией уровня называется прямая, в точках которой целевая функция постоянна Z(X) = Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru . Уравнение линий уровня

Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru , с = const.

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

Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru

Рис. 2.3

Доказательство. Пусть целевая функция задачи линейного программирования имеет вид Z(X) = Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru . В системе координат О Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru построим две линии уровня (L Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru ) и (L Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru ) (рис. 2.3). Их общая нормаль Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru . Пусть точка М( Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru ) Î (L Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru ), а точка Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru Î(L Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru ) является проекцией М на (L Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru ). Вектор Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru , Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru = ( Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru ), Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru . Так как Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru коллинеарен вектору Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru , то вектор Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru = Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru ×l, где l число. Скалярное произведение Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru . Используя координаты векторов Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru и Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru , можно записать Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru . Так как Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru , Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru , то Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru .

Отсюда получаем следующие выводы: 1) если линия уровня перемещается в направлении нормали Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru из положения (L Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru ) к (L Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru ), то l > 0 и, следовательно, Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru ; 2) если же линия уровня перемещается в направлении противоположном направлению нормали Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru из положения (L Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru ) к (L Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru ), то l < 0 и, следовательно, Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru .

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

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

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

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

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

3. Если область допустимых решений – это непустое множество, то строится нормаль линий уровня Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru и одна из линий уровня, имеющая общие точки с этой областью.

4. Линия уровня перемещается до опорной прямой в задаче на максимум в направлении нормали, в задаче на минимум – в противоположном.

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

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

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

Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru

Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru

Рис. 2.4

Решение. Изобразим на плоскости систему координат Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru (рис. 2.4) и построим граничные прямые области допустимых решений.

Прямые, ограничивающие ОДР:

Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru

Область допустимых решений определяется многоугольником ОАВСD. Для линий уровня Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru (с = const) строим нормальный вектор Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru . Перпендикулярно вектору Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru построим одну из линий уровня (на рисунке она проходит через начало координат). Так как задача на максимум, то перемещаем ее в направлении вектора Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru до опорной прямой. На рисунке видно, что опорная прямая проходит через точку B, являющуюся точкой пересечения первой и второй граничных прямых, Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru . Для определения координат точки В решаем систему уравнений

Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru

Получаем Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru = 3, Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru = 6. Данному оптимальному решению
X = (3; 6) соответствует максимальное значение целевой функции
max Z(X) = 2 × 3 + 4 × 6 =30.

Ответ: max Z(X) = 30 при X = (3; 6).

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

Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru

Рис. 2.5

Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru

Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru

Решение. Строим область допустимых решений, нормаль линий уровня Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru и одну из линий уровня, имеющую общие точки с этой областью (рис. 2.5). Перемещаем линию уровня в направлении противоположном направлению нормали Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru , так как решается задача на отыскание минимума функции. Нормаль линии уровня Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru и нормаль Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru = (2; 1) второй граничной прямой, в направлении которой перемещаются линии уровня, параллельны, так как их координаты пропорциональны 4/2 = 2/1. Следовательно, опорная прямая совпадает со второй граничной прямой области допустимых решений, проходит через две угловые точки этой области Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru и Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru . Задача имеет бесконечное множество оптимальных решений, являющихся точками отрезка Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru . Находим точки Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru , Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru , решая соответствующие системы уравнений.

Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru

Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru

Вычисляем Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru

Ответ: Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru при Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru

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

Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru

Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru

Рис. 2.6

Прямые, ограничивающие ОДР:

Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru

Решение. Строим область допустимых решений, нормаль Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru и одну из линий уровня (рис. 2.6). В данной задаче необходимо найти максимум целевой функции, поэтому линию уровня перемещаем в направлении нормали. Ввиду того, что в этом направлении область допустимых решений не ограничена, линия уровня уходит в бесконечность. Задача не имеет решения по причине неограниченности целевой функции.

Ответ: Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru .

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

Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru

Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru

Рис. 2.7

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

Ответ: система ограничений несовместна.

Лекция №3 ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Графический метод решения задач линейного
программирования с n переменными

Данным методом решаются задачи линейного программирования, имеющие каноническую форму и удовлетворяющие условию Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru , где n – число неизвестных системы, r – ранг системы векторов-условий (число линейно независимых уравнений системы). Если уравнения системы ограничений линейно независимые, то r = m.

Рассмотрим алгоритм метода на конкретном примере.

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

Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru ,

Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru

Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru .

Решение.

1. Проверяем условие применимости графического метода. Нетрудно видеть, что любые два из векторов-столбцов системы ограничений, например, Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru , Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru являются линейно независимыми, так как их координаты непропорциональны, поэтому ранг системы векторов-условий r = 2. Находим n - r = 4 - 2 =2 £ 2. Следовательно, метод применим.

2. Приведем систему ограничений-уравнений к равносильной, разрешенной с помощью метода Жордана – Гаусса. Одновременно исключим разрешенные неизвестные из целевой функции. Для этого

Т а б л и ц а 2.1

Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru b
–5
–1
–5

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

Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru

3. Отбросим в уравнениях-ограничениях неотрицательные разрешенные неизвестные Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru и Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru и заменим знаки равенства знаками " Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru ", получим эквивалентную задачу линейного программирования с двумя переменными

Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru

Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru

которая решается графическим методом (рис. 2.8).

Рис. 2.8

Оптимальное решение Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru ; Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru = (2; 0). Значение целевой функции Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru = 4 × 2 + 0 + 5 = 13.

4. Используем систему ограничений исходной задачи, приведенную к каноническому виду,

Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru

и оптимальное решение задачи с двумя переменными Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru = (2; 0) для нахождения оптимального решения исходной задачи

Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru ;

Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru .

Записываем оптимальное решение исходной задачи
Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru = (3; 0; 2; 0). Значение целевой функции на оптимальном решении совпадает со значением целевой функции для вспомогательной задачи Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru = 1 × 3 + 2 × 0 + 5 × 2 + 3 × 0 = 13.

Ответ: max Z(X) = 13 при Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru = (3; 0; 2; 0).

Задания для самостоятельного решения

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

Пример 2.7. Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru ,

Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru

Пример 2.8. Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru ,

Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru

Пример 2.9. Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru ,

Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru

Пример 2.10. Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru ,

Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru

Пример 2.11. Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru ,

Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru

Пример 2.12. Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru ,

Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ - student2.ru

Лекция№4. СВОЙСТВА РЕШЕНИЙ ЗАДАЧ ЛИНЕЙНОГО
ПРОГРАММИРОВАНИЯ

Наши рекомендации