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

3. Графический метод решения задач линейного программирования 1 3. Графический метод решения ЗЛП Этот метод можно применять, если количество неизвестных в задаче равно двум. В общем виде ЗЛП с двумя переменными будет иметь вид. Z ( X ) = c0 + c1 x1 + c2 x2 → max(min) a11 x1 + a12 x2 {, }b1 , a x + a x {, }b ,  21 1 22 2 2  .......... .......... .......  am1 x1 + am 2 x2{, }bm , x1 , x2  0. 2 3. Графический метод решения ЗЛП Область допустимых решений системы ограничений (ОДР) имеет вид выпуклого многоугольника (или неограниченной выпуклой многоугольной области), что позволяет легко построить данное множество на плоскости. Стороны такого многоугольника лежат получаемых из системы ограничений задачи: 𝑎𝑖1 𝑥1 + 𝑎𝑖2 𝑥2 = 𝑏𝑖 , на прямых, 𝑖 = 1, … , 𝑚 Экстремальные значения целевой функции следует искать среди угловых точек (вершин) ОДР. 3 3.1. Алгоритм графического метода решения ЗЛП 1. Построить область допустимых решений (ОДР). 2. Построить вектор градиента gradZ=(c1,c2) целевой функции. 3. Построить линии уровня целевой функции, перпендикулярные вектору градиента (графический поиск экстремальных точек). 4. Определить аналитически координаты экстремальных точек и вычислить значение целевой функции в них. 4 3.2. Пример решения ЗЛП графическим методом Z ( X ) = 5 x1 + x2 → max(min) 3x1 + 2 x2  12, (1)   x1 + 2 x2  4, (2) 2 x − x  1, (3)  1 2 x1, x2  0 5 3.2.1. Построение ОДР Z ( X ) = 5 x1 + x2 → max(min) (1) 3x1 + 2 x2  12, (1)   x1 + 2 x2  4, (2) 2 x − x  1, (3)  1 2 3x1 + 2 x2 = 12 Прямая (2) x1 + 2 x2 = 4 Прямая (3) 2 x1 − x2 = 1 (3) 6 x1, x2  0 Прямая (1) X2 5 x1 4 x2 6 x1 4 x2 2 4 3 (2) x1 3 1 x2 5 1 2 1 1 2 3 4 5 X1 6 3.2.2. Построение вектора градиента целевой функции. Z ( X ) = 5 x1 + x2 → max(min) (1) 3x1 + 2 x2  12, (1)   x1 + 2 x2  4, (2) 2 x − x  1, (3)  1 2 x1, x2  0 5 целевой 4 gradZ = (5;1). его (3) 6 Вектор градиента функции имеет вид Помещаем координат. X2 3 в начало (2) 2 1 gradZ 1 2 3 4 5 X1 7 3.2.3. Построение линий уровня и графический поиск экстремальных точек Z ( X ) = 5 x1 + x2 → max(min) (1) 3x1 + 2 x2  12, (1)   x1 + 2 x2  4, (2) 2 x − x  1, (3)  1 2 x1, x2  0 (3) 6 5 Линия уровня целевой функции перпендикулярна вектору градиента и имеет вид 4 5x1 + x2 = d Первая точка встречи линии уровня с ОДР (при движении в направлении вектора градиента) является точкой минимума, последняя – точкой максимума. X2 3 Xmax (2) Xmin 2 1 gradZ 1 2 3 4 5 X1 8 3.2.4. Аналитический поиск экстремальных точек Если ЗЛП имеет решение, то оно достигается хотя бы в одной угловой точке. Для нахождения угловой точки ОДР необходимо решить систему из двух линейных уравнений, задающих прямые, при пересечении которых и получается выбранная угловая точка 9 3.2.4. Аналитический поиск экстремальных точек В нашем случае точка Xmin образована пересечением прямой (2) и осью ординат и по построению очевидно, что X min = (0;2), Zmin = 5 * 0 + 1* 2 = 2. Точка Xmax образована пересечением прямых (1) и (3) и для ее нахождения решим систему 3x1 + 2 x2 = 12,  2 x1 − x2 = 1 Используя для решения системы стандартные приемы получим, что x1=2, x2=3. Таким, образом, X max = (2;3), Zmax = 5 * 2 + 1* 3 = 13. 10 3.3. Различные случаи конфигурации ОДР В зависимости от вида области допустимых решений в ЗЛП может встретиться только один из следующих случаев: Ровно одно решение (рассмотрено в п. 3.2.) Бесконечное множество решений (п. 3.3.1.) Решения отсутствуют, так как целевая функция неограничена (п. 3.3.2.) Решения отстутствуют, так как система ограничений противоречива (п.3.3.3.) 11 3.3.1 Случай бесконечного множества решений Z ( X ) = 3 x1 + 2 x2 → max (1) 3 x1 + 2 x2  12, (1)   x1 + 2 x2  4, (2) 2 x − x  1, (3)  1 2 x1 , x2  0 Xmax2 6 (3) 5 В качестве оптимального решения можно выбрать любую из точек лежащих на отрезке между точками Xmax1=(0;6) и Xmax2 =(2;3). Общее решение можно записать в виде X max = t * X max 1 + (1 − t ) * X max 2 , X2 (2) 4 Xmax1 3 2 t  [0;1], Z max = 12 1 gradZ 1 2 3 4 5 X1 12 3.3.2. Отсутствие решений вследствие неограниченности функции X2 Z ( X ) = 5 x1 + x2 → max  x1 + 2 x2  4, (2)  2 x1 − x2  1, (3) x1, x2  0 Очевидно, что при сдвиге линии уровня в направлении вектора градиента, она всегда будет иметь общие точки с ОДР. Соответственно функция будет неограниченно возрастать. (2) Подумайте, имеет ли данная задача точку минимума? (3) 6 5 4 3 2 1 gradZ 1 2 3 4 5 X1 13 3.3.3. Отсутствие решений вследствие противоречивости системы ограничений Z ( X ) = 5 x1 + x2 → max (1) 3x1 + 2 x2  12 , (1)  x + 2 x  4, (2)  1 2  2 x1 − x2  1, (3) 2 x1 − 3x2  2, (4) x1 , x2  0 X2 (3) 6 5 4 Очевидно, что условия (3) и (4) задают множества, не имеющие общих точек при неотрицательных значениях переменных. Поэтому ОДР представляет собой пустое (2) множество и задачи поиска оптимального решения теряет смысл. 3 (4) 2 1 14 1 2 3 4 5 X1