Езу9у. Учебное пособие Рекомендовано методическим советом Уральского федерального университета в качестве учебного пособия для студентов вуза, обучающихся по направлениям подготовки
 Скачать 5.85 Mb.
|
|
3. ГРАФИЧЕСКОЕ РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 3.1. Геометрическая интерпретация задачи Задача линейного программирования с двумя переменными легко решается графически. В случае трех переменных (соответственно, в трехмерном пространст- ве) графическое решение в принципе еще возможно, хотя и теряет преимущества наглядности; когда переменных больше, чем три, графический метод неприменим. Иногда количество переменных в задаче можно уменьшить (см. пример 3.5). Казалось бы, случай двух переменных, возможный лишь в учебных задачах или как результат резкого огрубления реальных задач, не должен представлять интереса. В действительности его рассмотрение очень важно, поскольку позво- ляет уяснить свойства общей задачи линейного программирования и принципы ее решения. Пусть дана задача: 1 ( ) max, n j j j Z X c x = = → ∑ (3.1) ( ) 1 1, , n ij j i j a x b i m = ≤ = ∑ (3.2) ( ) 0 1, . j x j n ≥ = (3.3) Если количество переменных n = 2, то (3.2)–(3.3) можно рассматривать как систему неравенств 11 1 12 2 1 21 1 22 2 2 1 1 2 2 1 2 , , , 0, 0 m m m a x a x b a x a x b a x a x b x x + ≤ + ≤ + ≤ ≥ ≥ (3.4) на плоскости Ox 1 x 2 75 Каждое неравенство здесь определяет одну из двух полуплоскостей, на ко- торые плоскость делится соответствующей прямой a i1 x 1 + a i2 x 2 = b i1 ( 1, ), i m = включая и саму прямую — границу полуплоскости. Если система (3.4) сов- местна, то пересечением полуплоскостей является выпуклый * многоугольник решений, заштрихованный на рис. 3.1 (для случая m = 4). Если в системе ограничений (3.2)–(3.3) количество переменных n = 3, то каж дое неравенство системы определяет полупространство трехмерного про- странства с соответствующей граничной полуплоскостью a i1 x 1 + a i2 x 2 + a i3 x 3 = b i ( 1, ). i m = Если система ограничений совместна, то полученные полупространства образуют в трехмерном пространстве выпуклую общую часть — многогранник решений, представляющий собой совокупность точек, координаты которых удовлетворяют системе (3.2)–(3.3). При n > 3 каждое неравенство системы (3.2)–(3.3) описывает полупростран- ство n-мерного пространства с соответствующей граничной гиперплоскостью * Напомним, что множество называется выпуклым, если вместе с любыми двумя его точ- ками оно содержит и соединяющий их отрезок. Пустое и одноточечные множества выпуклы по определению. Пересечение выпуклых множеств есть выпуклое множество. Рис. 3.1. Случай двух переменных с областью допустимых решений — выпуклый многоугольник. Стрелками по концам сегмента прямой здесь и ниже будем отмечать направление штриховки O x 1 x 2 (1) (2) (3) (4) 76 a i1 x 1 + a i2 x 2 + … + a in x n = b i ( 1, ). i m = Если система ограничений совместна, то пере- сечением полупространств является выпуклый n-мерный многогранник решений. Геометрически задача линейного программирования состоит в нахождении той точки n-мерного многогранника решений, координаты которой доставляют целевой функции оптимальное значение; при этом допустимыми решениями являются все точки многогранника решений. Свойства решений задачи линейного программирования Поскольку любая задача линейного программирования приводится к ка- нонической форме: Z 1 ( ) max, n j j j X c x = = → ∑ (3.5) ( ) 1 1, , n ij j i j a x b i m = = = ∑ (3.6) ( ) 0 1, , j x j n ≥ = (3.7) ограничимся рассмотрением свойств допустимых решений задачи в канони- ческой форме: 1. Область допустимых решений задачи линейного программирования выпукла. 2. Поскольку линейная функция не имеет экстремумов, целевая функция задачи линейного программирования достигает наибольшего значения на гра- нице области, а именно в угловой точке области допустимых решений. Если наибольшее значение целевой функции достигается более чем в одной угловой точке, то это же значение достигается и в любой линейной комбинации этих угловых точек. 3. Каждому допустимому базисному решению задачи (3.5)–(3.7) соответст- вует угловая точка многогранника решений и, наоборот, каждой угловой точке многогранника соответствует допустимое базисное решение. Следствие из свойств 2 и 3: если задача линейного программирования имеет оптимальное решение, то оно совпадает, по меньшей мере, с одним из ее допустимых базисных решений, т. е. с одной из угловых точек (вершин) мно- гогранника решений, а это означает, что оптимальное решение задачи нужно искать среди конечного числа допустимых базисных решений. 77 3.2. Реализация графического метода решения Графический способ решения задачи линейного программирования можно использовать: • для решения задачи с двумя неизвестными, когда ограничения выражены неравенствами; • для решения задачи со многими неизвестными при условии, что в кано- нической форме она содержит две свободных неизвестных. Запишем задачу линейного программирования с двумя неизвестными: ( ) 1 1 2 2 ( ) max min , Z X c x c x = + → (3.8) 11 1 12 2 1 21 1 22 2 2 1 1 2 2 , , ; m m m a x a x b a x a x b a x a x b + ≤ + ≤ + ≥ (3.9) 1 2 0, 0. x x ≥ ≥ (3.10) Каждое неравенство в (3.9)–(3.10) геометрически определяет полуплоскость с граничной прямой соответственно a i1 x 1 + a i2 x 2 = b i ( 1, ), i m = x 1 = 0 и x 2 = 0. Если система (3.9)–(3.10) совместна, то область ее допустимых решений — это общая часть указанных полуплоскостей, называемая многоугольником решений. Об- ластью допустимых решений системы (3.9)–(3.10) может быть: • выпуклый многоугольник; • выпуклая неограниченная многоугольная область; • луч; • отрезок; • точка; • пустая область. Целевая функция Z(X) = c 1 x 1 + c 2 x 2 определяет на плоскости семейство ли- ний уровня — прямых, на каждой из которых функция принимает постоянное значение Z(X) = c 1 x 1 + c 2 x 2 = const. Градиент c = (c 1 ; c 2 ) целевой функции — это вектор, перпендикулярный ее линиям уровня и указывающий направление наискорейшего возрастания Z(X) (противоположный вектор –c указывает направление наискорейшего убывания целевой функции). Отыскание наибольшего (наименьшего) целевой функции сводится к нахождению в допустимой области решений точки 0 0 0 1 2 ( ; ), X x x = через которую проходит линия уровня с экстремальным значением целевой функции. 78 3.3. Примеры графического решения задач линейного программирования Для решения задач линейного программирования применяется следующий а л г о р и т м: 1. Записать математическую модель (3.8)–(3.10) задачи. 2. Построить в системе координат Ox 1 x 2 прямые, уравнения которых полу- чаются заменой неравенств равенствами в ограничениях (3.9)–(3.10). 3. Заштриховать полуплоскости, определяемые каждым из неравенств (3.9)–(3.10) (границами полуплоскостей являются построенные прямые). 4. Выделить область допустимых решений (в ней накладываются все штри- ховки). 5. Построить градиент c = (c 1 ; c 2 ). 6. Построить прямую уровня c 1 x 1 + c 2 x 2 = 0 (убедиться в том, что она пер- пендикулярна градиенту). 7. При решении задачи на max (min) совершать параллельный перенос пря- мой c 1 x 1 + c 2 x 2 = 0 в направлении градиента (в противоположном направлении); в итоге либо найдется точка, в которой целевая функция принимает наибольшее (наименьшее) значение, либо обнаружится неограниченность функции сверху (снизу) на области допустимых решений. 8. Найти координаты точки максимума (минимума) целевой функции и значение функции в этой точке. Пример 3.1. Предприятие производит продукцию видов Р 1 и Р 2 по цене 3 и 7 у. е. соответственно. При этом используются два вида сырья А и В. Суточные запасы и расход сырья каждого вида на единицу продукции Р 1 и Р 2 указаны в таблице. Вид сырья Запас сырья Расход сырья на единицу продукции Р 1 Р 2 А 9 2 3 В 7 1 2 Суточный спрос на продукцию Р 1 превышает спрос на продукцию Р 2 не бо- лее чем на две единицы, а спрос на продукцию Р 2 не бывает более двух единиц в сутки. Какое количество продукции каждого вида в сутки должно выпускать предприятие, чтобы получить максимальный доход от реализации продукции? Решение. Пусть х 1 и х 2 — количество единиц продукции Р 1 и Р 2 соответст- венно, производимой в сутки. Математическая постановка задачи: 1 2 ( ) 3 7 max, Z X x x = + → 79 1 2 1 2 1 2 2 2 3 9, 2 7, 2, 2; x x x x x x x + ≤ + ≤ ≤ + ≤ 1 2 0, 0. x x ≥ ≥ На координатной плоскости покажем область допустимых решений, ог- раниченную осями координат и прямыми, соответствующими уравнениям: (1) (2) (3) 1 2 1 2 1 2 2 2 3 9 , 2 7 , 2 , 2 (4). x x x x x x x + = + = = + = Область допустимых решений — пятиугольник, заштрихованный на рис. 3.2. Покажем вектор v, сонаправленный градиенту * c = (3; 7) и исходящий из на- чала координат. Проведем через ту же точку перпендикулярно градиенту ли- нию уровня (рис. 3.3). При параллельном переносе этой линии в направлении вектора v значение целевой функции возрастает. Мы хотим найти, в какой точке линия уровня покидает область допустимых решений. Судя по рис. 3.3, * Сам градиент не уместится на рисунке в выбранном масштабе. Рис. 3.2. Область допустимых решений для примера 3.1 2 3 1 O 1 2 3 x 1 (1) (2) (3) (4) x 2 A B C D 80 это точка В. Следовательно, именно в ней целевая функция примет наибольшее значение. Точка В является точкой пересечения прямых (1) и (4) (см. рис. 3.2), поэтому ее координаты удовлетворяют системе 1 2 2 2 3 9, 2, x x x + = = решая которую, находим x 1 = 1,5 и x 2 = 2. Целевая функция Z в точке B (1,5; 2) принимает значение: ( ) ( ) 1 2 1 2 1,5 2 max 3 7 3 1,5 7 2 18,5. x B x Z X Z x x = = = = + = ⋅ + ⋅ = Итак, найдено оптимальное решение X = (1,5; 2), для которого max Z(X) = 18,5. Пример 3.2. Решить графически задачу: 1 2 ( ) 4 6 max, Z X x x = + → Рис. 3.3. Случай отыскания точки, в которой прямая, соответствующая целевой функции, покидает область допустимых решений 2 1 O 1 2 3 x 1 x 2 A B (1,5; 2) C D v 3x 1 + 7x 2 = 0 81 1 2 1 2 1 2 2 2 3 9, 2 7, 2, 2; x x x x x x x + ≤ + ≤ ≤ + ≤ 1 2 0, 0. x x ≥ ≥ Решение. Заметим, что эта задача отличается от предыдущей лишь тем, что иначе определена целевая функция. Поэтому область допустимых решений по-прежнему будет такой, как показано на рис. 3.3. Надо лишь по-другому построить вектор, указывающий направление градиента c = (4; 6) и перпенди- кулярные ему линии уровня (рис. 3.4). Теперь линия уровня при параллельном переносе в направлении градиента покидает область допустимых решений не в точке В, а по отрезку ВС. Поэтому координаты любой точки отрезка ВС будут определять оптимальное решение исходной задачи. Выразим из уравнения 1 2 2 3 9 x x + = прямой ВС переменную х 2 : 1 2 9 2 3 x x − = 2 1 O 1 2 3 x 1 x 2 A B (1,5; 2) C (3; 1) D v 4x 1 + 6x 2 = 0 Рис. 3.4. Случай, когда целевая функция покидает область допустимых решений по отрезку — задача имеет бесконечно много решений 82 Тогда оптимальное решение есть ( ) 1 1 1 3 , (9 2 ) , X x x = − где х 1 — любое зна- чение из отрезка [1,5; 3], при этом ( ) ( ) 1 2 1 2 1,5 2 max 4 6 4 1,5 6 2 18. x B x Z X Z x x = = = = + = ⋅ + ⋅ = Проверьте, что при подстановке в целевую функцию координат точки С (3; 1) получается то же оптимальное значение. Пример 3.3. Решить задачу: 1 2 ( ) min, Z X x x = − → 1 2 1 2 1 2 1,5 3, 2 4, 2 4; x x x x x x − ≤ + ≥ + ≥ 1 2 0, 0. x x ≥ ≥ Решение. Построим область допустимых решений, ограниченную осями координат и прямыми, соответствующими уравнениям (рис. 3.5): 1 2 1 2 1 2 1,5 3 (1), 2 4 (2), 2 4 (3). x x x x x x − = + = + = Заметим, что область не ограничена сверху. Построим вектор градиента c = (1, −1), исходящий из начала координат, и проведем линии уровня в направлении, противоположном c, так как именно в этом направлении значение целевой функции Z(X) убывает (рис. 3.5). Чем выше располагается линия уровня, тем меньше значение целевой функции на ней. В силу неограниченности области допустимых решений Z(X) → −∞ на этой области, и исходная задача не имеет решения. Пример 3.4. Решить задачу: 1 2 ( ) min, Z X x x = − → 1 2 1 2 1 2 1,5 3, 2 4, 2 4; x x x x x x − ≥ + ≤ + ≥ 1 2 0, 0. x x ≥ ≥ Решение. По сравнению с предыдущей задачей здесь изменен знак первых двух ограничений; это означает, что в обоих случаях штриховать придется 83 полуплоскость по другую сторону от соответствующей прямой. Сейчас систе- ма ограничений противоречива: нет таких точек, которые удовлетворяли бы всем ограничениям сразу (рис. 3.6). И эта задача линейного программирования не имеет решения, но по другой причине, нежели предыдущая задача. Итак, рассмотрены ситуации, встречающиеся при графическом решении задачи линейного программирования: оптимальное решение существует и един- ственно (пример 3.1); существует, но не единственно (бесконечное множество решений доставляют целевой функции одно и то же оптимальное значение — пример 3.2); оптимальное решение не существует — по причине неограничен- ности целевой функции в области допустимых решений (пример 3.3) или в силу несовместности ограничений задачи (пример 3.4). Наконец, рассмотрим задачу, которая, на первый взгляд, вообще не до- пускает графического решения, поскольку содержит более двух переменных. В действительности, выражая одни переменные через другие, можно уменьшить количество переменных до двух. 4 3 1 1 3 4 O (1) (2) (3) C x 1 x 2 –1 Рис. 3.5. Случай, когда область допустимых решений не ограничена — задача может не иметь решения 84 Пример 3.5. Привести задачу линейного программирования 1 2 3 4 ( ) 4 3 max, Z X x x x x = − + − → 1 2 3 4 1 2 3 4 4 2 1, 3 4 3; x x x x x x x x − + − = + − + = ( ) 0 1, 4 j x j ≥ = к виду, допускающему графическое решение. Решение. Составим расширенную матрицу системы ограничений и вы- берем базисный минор, например, так, чтобы неизвестные х 1 и х 2 оказались базисными, а х 3 и х 4 — свободными * . Выполняя элементарные преобразования строк матрицы, выразим базисные переменные через свободные: 3 1 4 2 13 5 4 2 1 1 4 2 1 1 0 1 , 3 1 1 4 3 0 1 0 − − − − * В силу неоднозначности отнесения переменных к базисным и свободным можно по- разному привести исходную задачу к виду, допускающему графическое решение. Векторы оптимального решения при этом, естественно, будут различаться, но они доставляют своим Рис. 3.6. Случай, когда система ограничений несовместна — задача не имеет решения 3 1 1 3 4 O (1) (2) (3) x 1 x 2 –1 85 откуда 3 13 5 1 1 3 4 2 3 4 4 2 4 2 1 , x x x x x x = − − = − Подставим эти выражения в целевую функцию; учтем также, что на х 1 и х 2 действовали естественные ограничения. В итоге получим стандартную задачу, допускающую графическое решение: 47 9 3 4 4 2 ( ) 4 max, Z X x x = − + → 3 1 3 4 4 2 13 5 3 4 4 2 1 0, 0; x x x x − − ≥ − ≥ 3 4 0, 0. x x ≥ ≥ |