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

ЗАНЯТИЕ 6 Тема: 1) решение задач линейного программирования графическим методом; 2) решение ЗЛП с помощью симплекс-таблиц (начало) Предположим, что задача линейного программирования (ЛП) представлена в общей форме записи:   F x   c T x  extr ;  n  a ij x j  bi , i  1, m,  j 1  n   a ij x j  bi , i  m  1, k ,  j 1  x j  0 j  1, n.    Метод графического (геометрического) решения задачи включает выполнение последовательности шагов: 1 шаг. Строится область определения задачи ЛП. При этом возможны варианты: a) область определения пуста; b) область определения – ограниченное множество (выпуклый многогранник); c) область определения – неограниченное множество.   2 шаг. Строится направляющий вектор c , составленный из коэффициентов целевой функции F (x ) . Направляющий вектор является градиентом целевой функции. Он указывает направление максимального роста целевой функции. 3 шаг. Строится прямая (плоскость в трехмерном случае), ортогональная (перпендикулярная) этому вектору. Во всех точках такой прямой (плоскости) целевая функция имеет одинаковые значения.  4 шаг. Перпендикулярная направляющему вектору c прямая (плоскость) перемещается в направлении, указан ном вектором c (или в противоположном направлении при поиске минимума), с сохранением параллельности первоначальной прямой (плоскости), пока при этом имеются ее точки пересечения с областью определения задачи ЛП. Последняя точка касания (точка отрыва) прямой с областью определения задачи ЛП является ее решением – оптимальным планом. 5 шаг. Находятся точные значения компонент оптимального плана. Для этого решается система, составленная из тех линейных уравнений, которые задают прямые (плоскости), пересечение которых и определяет точку оптимального плана. В случае, когда область определения не ограничена, применение графического метода решения задачи ЛП может не привести к достижению оптимального плана; такой точки может и не быть; в этом случае задача ЛП неразрешима. Результаты графического рассмотрения данной задачи иллюстративного характера можно резюмировать следующим образом: 1. Если множество решений является непустым, то оно выпукло и может быть либо ограниченным, либо неограниченным. 2. Если множество решений является непустым, то оптимальное значение целевой функции может быть либо конечным, либо неограниченным. В случае, когда оптимальное значение целевой функции конечно, оно соответствует оптимальному плану. Задача 1. F ( x )  3x1  5 x2  extr; 4 x1  3x2  12,   2 x1  5 x2  10,  x  0 x  0.  1 2 Решение. Реализуем алгоритм геометрического решения задачи по шагам. Шаг 1. Строится область определения поставленной задачи ЛП. Она представляет собой пересечение двух полупространств-полуплоскостей, порождаемых двумя неравенствами системы ограничений-неравенств исходной задачи. Для того чтобы определить эти полупространства-полуплоскости, решаем каждое из неравенств в отдельности. Первое неравенство определяет «критическую» прямую 4 x1  3x2  12 , которая получается из неравенства путем замены знака неравенства на знак равенства. Эта прямая разделяет всю плоскость на две полуплоскости; точки одной из них удовлетворяют неравенству, а точки другой – нет. Для того чтобы определить, точки какой из полуплоскостей удовлетворяют неравенству, можно взять координаты любой точки плоскости, не лежащей на «критической» прямой и проверить, удовлетворяется ли для этой точки неравенство. Если неравенство удовлетворяется, то та полуплоскость, которой принадлежит взятая точка, является решением неравенства. В противном случае решение неравенства будет та полуплоскость, которой взятая точка не принадлежит. Для нашей задачи взяв в качестве проверочной точки точку начала координат, мы простой подстановкой x1  0, x2  0 убедимся, что точка начала координат удовлетворяет обоим неравенствам системы ограничений. Отсюда следует, что полуплоскости, являющиеся решениями неравенств, лежат ниже «критических» прямых. С учетом того, что x1  0, x2  0 , получаем, что область определения ЗЛП – внутренность заштрихованного четырехугольника ABCD.   Шаг 2. Строится направляющий вектор c , составленный из коэффициентов целевой функции F ( x )  3x1  5x2 Шаг 3. и прямая ss , перпендикулярная этому вектору. На рисунке эта прямая проведена пунктирной линией. Шаг 4. Прямая ss перемещается параллельно самой себе в направлении, указанном  вектором c , пока при этом имеются точки пересечения с областью решения задачи ЛП. Последняя точка касания перемещаемой прямой ( на рисунке – прямая s s  ) с областью решения задачи ЛП (точка C ) является оптимальным планом. Шаг 5. Для того чтобы определить координаты точки C , требуется решить систему уравнений 4 x1  3x 2  12,  2 x1  5 x 2  10. Решив систему, получаем ответ: максимальное значение F * целевая функция получает в точке x1*  15 / 7; x 2*  8 / 7 , при этом F *  c1 x1*  c 2 x 2*  3  (15 / 7)  5  (8 / 7)  85/7. Минимальное значение целевая функция получает в точке x1*  0; x2*  0 , при этом F *  0 . Задача 2. F ( x )  3x1  2 x2  extr;  x1  3x2  9, 5 x  3x  15,  1 2   x1  x2  2  x1  0 x2  0. Решение. Реализуем алгоритм геометрического решения задачи по шагам аналогично решению задачи 2. Построенный чертеж с областью ограничений OPQRS, направляющим вектором c T  ( 3; 2) и перпендикулярными направляющему вектору прямыми ss, s’s’, s”s” представлен на рисунке При поиске максимума точкой отрыва перемещаемой прямой ss является точка P, имеющкая координаты * x1*  0; x2*  3 . Максимум целевой функции равен Fmax  c1 x1*  c2 x2*  3  (0)  2  (3)  6. При поиске минимума точкой отрыва является точка R (прямая ss перемещается в противоположном градиенту направлении). Для определения координат точки R нужно решить систему уравнений 5 x1  3x2  15,   x1  x2  2. Решая эту систему, получаем значения аргументов, приносящие минимум целевой функции: * x1*  21/ 8; x2*  25 / 8 . При этом Fmin  c1 x1*  c2 x2*  3  (21/ 8)  2  (25 / 8)  11/ 8. Задача 3. F = х1 +4х2  extr;  3  x1  x 2  7,  x  5,  2  x  0.  T T Ответ: xmax  (2; 5) ; Fmax  22 ; xmin  (3; 0) ; Fmin  3 . Задача 4. F = х1 +4х2  extr;  x1  x2  7,  2 x  x  0, 1 2  x  x  1 2  0, x  0.  T T  (7 / 3; 14 / 3) ; Fmax  21 ; xmin  (0; 0) ; Fmin  0 . Ответ: xmax Задача 5. F = х1 +4х2  extr;  x1  x2  7,  2 x  x  0, 1 2   x  x  1 2  0,  x  0. T T  (0; 0) ; Fmax  0 ; xmin  (0; 0) ; Fmin  0 . Ответ: xmax Задача 6. 1. Решить графическим методом. 2. представить задачу в канонической форме. 3. Выписать расширенную матрицу уравнений-ограничений канонической задачи. 4. Найти опорный план. 5. Начертить и заполнить начальную симплекс-таблицу F ( x )  2 x1  5 x2  max; T Решение. 1. Графическое решение: xmax 2.  x1  x2  6,  2 x  x  4,  1 2  2 x1  x2  4  x1  0 x2  0.  (2 / 3; 16 / 3) ; Fmax  28 . Каноническая форма задачи: F ( x )  2 x1  5 x2  max;  x1  x2  x3  6,  2 x  x  x  4,  1 2 4  2 x  x  x 5  4,  1 2  x1  0 x2  0. 3.Расширенная матрица уравнений-ограничений задачи:  x1 x2 x3   1 1 1  2 1 0   2 1 0 P P P 2 3  1 4. Опорный план: x T (1)  (0; 0; 6; 4; 4) . 5.Симплекс-таблица (n + 3 = 8 столбцов; m + 3 = 6 строк): 2 5 Б СБ Р0 Р 1 Р2 x3 0 6 1 1 x4 0 4 –2 1 x5 0 4 2 –1 f –2 –5 x4 1 P4 x5 1 P5 Р3 1 b  6 4  4 P0  Р4 1 Р5 1 ДОМАШНЕЕ ЗАДАНИЕ: Прочитать лекционный материал по двойственным задачам линейного программирования и по симплекс-методу. Знать 1-ю, 2-ю и 3-ю теоремы двойственности. Уметь строить симплекс – таблицы. Решить графическим способом следующие задачи: 1. Задача 1. F( x ) = 2х1 + 3х2  mах  3x1  2 x 2  12,   x1  4 x 2  14,   x0   T Ответ: x   (2; 3) ; F   13 . Задача 2. F = х1 + 3х2  mах  x1  4 x 2  12   3x1  x 2  14   x0  T Ответ: x   (4; 2) ; F   10 . Задача 3. F  2 x1  x2  max;  x1  x2  3,  2 x  x  1,  1 2  2 x  x  1  2  2,  x  0.  Ответ:; x T  (5 / 3; 4 / 3) ; F   14 / 3 . Задача 4. F  3x1  2 x2  max;  3 x1  4 x2  36, 3 x  4 x  24,  1 2   x  2 x 2  8,  1  x1 , x2  0. Ответ: x T  (10; 3 / 2) ; F   33 . Задача 5. Предприниматель, занимающийся изготовлением бюстов известных деятелей, решает задачу определения оптимального плана производства бюстов предендентов на пост президента США: республиканца Трампа и демократа Байдена. Проекты бюстов данных деятелей разработаны и утверждены к производству. На изготовление бюстов требуется серебро и бронза. Нормы расхода металлов на один бюст, общие запасы металлов у предпринимателя и прибыли, получаемые от реализации каждого бюста, указаны в таблице: Бронза (кг) Серебро (кг) Прибыль (тыс. руб) Бюст Байдена 4 2 30 Бюст Трампа 3 5 50 Общие запасы (кг) 240 260 Решение. Формализуем задачу. Для этого введем в рассмотрение переменные x1 и x 2 соответственно, которые будут означать искомые количества производимых бюстов Байдена и Трампа соответственно. Тогда задача определения оптимального плана производства сводится (с учетом табличных данных) к следующей задаче ЛП:  F ( x )  30 x1  50 x 2  max; 4 x1  3x 2  354,  2 x1  5 x 2  380,  x  0 x  0. 2  1 Реализуем алгоритм геометрического решения задачи по шагам. 1 шаг. Строится область определения поставленной задачи ЛП. Она представляет собой пересечение двух полупространств-полуплоскостей, порождаемых двумя неравенствами системы ограничений-неравенств исходной задачи. Для того чтобы определить эти полупространства-полуплоскости, решаем каждое из неравенств в отдельности. Первое неравенство определяет «критическую» прямую 4 x1  3x2  12 , которая получается из неравенства путем замены знака неравенства на знак равенства. Эта прямая разделяет всю плоскость на две полуплоскости; точки одной из них удовлетворяют неравенству, а точки другой – нет. Для того чтобы определить, точки какой из полуплоскостей удовлетворяют неравенству, можно взять координаты любой точки плоскости, не лежащей на «критической» прямой и проверить, удовлетворяется ли для этой точки неравенство. Если неравенство удовлетворяется, то та полуплоскость, которой принадлежит взятая точка, является решением неравенства. В противном случае решение неравенства будет та полуплоскость, которой взятая точка не принадлежит. Для нашей задачи, взяв в качестве проверочной точки точку начала координат, мы простой подстановкой x1  0, x2  0 убедимся, что точка начала координат удовлетворяет обоим неравенствам системы ограничений. Отсюда следует, что полуплоскости, являющиеся решениями неравенств, лежат ниже «критических» прямых. С учетом того, что x1  0, x2  0 , получаем, что область определения задачи ЛП – внутренность заштрихованного четырехугольника ABCD.   2 шаг. Строится направляющий вектор c , составленный из коэффициентов целевой функции F ( x )  30 x1  50 x 2 x2 80 4 x1  3 x 2  240 52 S’ .  c Направляющий вектор Точка оптимального плана Ортогональная направляющая вектору прямая 30 S’ 60 2x1  5x2  260 130 x1 3 шаг. Строится прямая, перпендикулярная этому вектору. На рисунке эта прямая проведена пунктирной линией  s s  . Прямая s s  перемещается параллельно самой себе в направлении, указанном вектором c , пока при этом имеются точки пересечения с областью решения задачи ЛП. Последняя точка касания перемещаемой прямой (на рисунке – прямая s s  ) с областью решения задачи ЛП является оптимальным планом. Для того чтобы определить координаты точки оптимального плана, требуется решить систему уравнений 4 x1  3x 2  240,  2 x1  5 x 2  260. Решив систему, получаем ответ: максимальное значение F * целевая функция получает в точке x1*  30; x 2*  40 , при этом F *  c1 x1*  c2 x2*  30  (30)  50  40)  2900. * Ответ: x *T  (30; 40) . F  2900 .