Решение ЗЛП табличным симплекс-методом

ЗАНЯТИЕ 7 Тема: 1) двойственная пара ЗЛП 2) решение ЗЛП табличным симплекс-методом Каждой ЗЛП можно поставить в соответствие другую ЗЛП, которая называется двойственной по отношению к исходной, прямой или основной ЗЛП, предварительно представленной в симметричной форме: Прямая ЗЛП:    f ( x )  c T x  max; (1)   Ax  b ,  (2)  x  0,    n m c, x  R , b  R . Двойственная ЗЛП:    g ( y)  b T y  min; (3)     AT y  c ,   y  0, (4)   m  n b, y  R , c  R . Нетрудно видеть, что если задачу (3)-( 4) взять за прямую, то двойственной по отношению к ней будет задача (1)-(2). В связи с эти говорят, что задачи (1)-(2) и (3)-(4) образуют так называемую двойственную пару ЗЛП. Для сформулированных ниже задач выполнить следующие действия: 1) написать двойственную задачу линейного программирования по отношению к заданной; 2) решить заданную задачу табличным симплекс-методом, определив при этом двойственные оценки. Сделать проверку, используя 1-ю теорему двойственности. Задача 1. f ( x )  2 x1  5 x2  max;  x1  x2  6,  2 x  x  4,  1 2  2 x  x  1 2 4  x1  0 x2  0. 1) двойственная ЗЛП: g ( y )  6 y1  4 y2  4 y3  min;  y1  2 y2  2 y3  2,   y1  y2  y3  5,  y  0.  для сопоставления приведем графическое решение задачи (см. рис. 1 ниже); оптимальный план и значение T целевой функции на данном плане равны xmax  (2 / 3; 16 / 3) ; f max  28 . Рис. 1. Графическое решение задачи 1 2) Для реализации симплекс-метода задачу необходимо представить в канонической форме. Каноническая форма задачи: F ( x )  2 x1  5 x2  max;  x1  x2  x3  6,  2 x  x  x  4,  1 2 4  2 x1  x2  x5  4,  x  0. Расширенная матрица уравнений-ограничений задачи:  x1 x2 x3   1 1 1  2 1 0   2 1 0 P P P 2 3  1 x4 1 P4 x5 1 P5 b  6 4  4 P0  Матрица представляет собой решенную относительно базисных переменных x3 , x4 , x5 систему линейных уравнений, причем правая часть системы состоит из неотрицательных чисел. Полагая свободные переменные равными нулю, получаем первый опорный план x T (1)  (0; 0; 6; 4; 4) . Реализацию табличного метода представим последовательностью симплекс-таблиц. Число переменных n в данной задаче равно 5; число уравнений m равно 3. Симплекс-таблица имеет (n + 3 = 8) столбцов и (m + 3 = 6) строк. Разрешающий столбец показан стрелкой. Разрешающие элементы заключены в скобки. Таб.1 б Cб P0 x3 6 4 4 x4 x5 f 2 P1 1 –2 2 –2 5 P2 1 (1) –1 –5 ↑ P3 1 P4 1 P5 1 б Cб P0 x3 5 2 4 8 20 x2 x5 f б Cб P0 x1 2/3 x2 5 16/3 8 28 x5 f 2 P1 (3) –2 –12 ↑ 5 P2 1 P3 1 P4 –1 1 1 5 Таб.2 P5 1 2 P1 1 5 P2 P3 1 P4 –1 Таб.3 P5 ↑ 1 2/3 4 y1 1/3 1 1 y2 1 y3 В таб.3 нет отрицательных среди ∆j в нижней строке, значит, она соответствует оптимальному плану. Компоненты оптимального плана содержатся в столбце P0 . Ответ: x *T   2 / 3; 16 / 3; 0; 0; 8 . f *  f ( x * )  28 . Двойственные оценки находим в последней, 3-й таблице (желтые клетки). Имеем: y1  4 ; y2  1 ; y3  0 . Проверка: g ( y )  6  4  4 1  4  0  28  f ( x  ) . Верно. Задача 2. F ( x )  3x1  5 x2  max; 4 x1  3x2  12,   2 x1  5 x2  10,  x  0 x  0.  1 2 1) двойственная ЗЛП: g ( y )  12 y1  10 y2  min; 4 y1  2 y2  3,  3 y1  5 y2  5,  y  0.  2) Для реализации симплекс-метода задачу необходимо представить в канонической форме. Каноническая форма задачи: F ( x )  3x1  5 x2  max;  4 x1  3x2  x3  12,  2 x1  5 x2  x4  10,  x  0.  Расширенная матрица уравнений-ограничений задачи:  x1  4 2   P1 x2 3 5 P2 x3 1 P3 x4 1 P4 b  12  10   P0  Матрица представляет собой решенную относительно базисных переменных x3 , x4 систему линейных уравнений, причем правая часть системы состоит из неотрицательных чисел. Полагая свободные переменные равными нулю, получаем первый опорный план x T (1)  (0; 0; 12; 10) . Реализацию табличного метода представим последовательностью симплекс-таблиц. Число переменных n в данной задаче равно 4; число уравнений m равно 2. Симплекс-таблица имеет (n + 3 = 7) столбцов и (m + 3 = 5) строк. Разрешающий столбец показан стрелкой. Разрешающие элементы заключены в скобки. Таб.1 б Cб P0 x3 12 10 x4 f 3 P1 4 2 –3 5 P2 3 (5) –5 ↑ P3 1 3 P1 (14/5) 2/5 –1 ↑ 5 P2 1 P3 1 3 P1 1 ↑ 5 P2 1 P3 5/14 –2/14 5/14 y1 P4 1 Таб.2 б Cб P0 x3 x2 f 5 6 2 10 P4 –3/5 1/5 1 Таб.3 б Cб P0 x1 x2 f 5 30/14 16/14 170/14 P4 –3/14 4/14 11/14 y2 В таб.3 нет отрицательных среди ∆j в нижней строке, значит, она соответствует оптимальному плану. Компоненты оптимального плана содержатся в столбце P0 . Ответ: x *T   30 /14; 16 /14 0; 0  . f *  f ( x * )  170 /14 . Двойственные оценки находим в последней, 3-й таблице (желтые клетки). Имеем: y1  5 / 14 ; y2  11/ 14 . Проверка: g ( y )  12  (5 /14)  10  (11/14)  170 /14  85 / 7  f ( x  ) . Верно. Задача 3. F ( x )  3x1  2 x2  max;  x1  3x2  9, 5 x  3x  15,  1 2   x1  x2  2  x1  0 x2  0. 1) двойственная ЗЛП: g ( y )  9 y1  15 y2  2 y3  min;  y1  5 y2  y3  3,  3 y1  3 y2  y3  2,  y  0.  2) для реализации симплекс-метода задачу необходимо представить в канонической форме. Каноническая форма задачи: F ( x )  3x1  2 x2  max;  x1  3x2  x3  9, 5 x  3x  x  15,  1 2 4   x1  x2  x5  2,  x  0. Расширенная матрица уравнений-ограничений задачи:  x1  1 5  1 P  1 x2 x3 3 1 3 0 1 0 P2 P3 x4 1 P4 x5 1 P5 b  9 15   2 P0  Матрица представляет собой решенную относительно базисных переменных x3 , x4 , x5 систему линейных уравнений, причем правая часть системы состоит из неотрицательных чисел. Полагая свободные переменные равными нулю, получаем первый опорный план x T (1)  (0; 0; 9; 15; 2) . Реализацию табличного метода представим последовательностью симплекс-таблиц. Число переменных n в данной задаче равно 5; число уравнений m равно 3. Симплекс-таблица имеет (n + 3 = 8) столбцов и (m + 3 = 6) строк. Разрешающий столбец показан стрелкой. Разрешающие элементы заключены в скобки. Таб.1 б Cб P0 x3 9 15 2 x4 x5 f б Cб P0 x2 x4 2 5 3 6 5 6 x5 f –3 P1 1 5 1 3 2 P1 1/3 4 4/3 11/3 2 P2 (3) 3 –1 –2 ↑ 5 P2 1 P3 1 P3 1/3 –1 1/3 2/3 y1 P4 1 P4 1 y2 P5 1 Таб.2 P5 1 y3 В таб.2 нет отрицательных среди ∆j в нижней строке, значит, она соответствует оптимальному плану. Компоненты оптимального плана содержатся в столбце P0 . Ответ: x *T   0; 3; 0; 6; 5 . f *  f ( x * )  6 . Двойственные оценки находим в последней, 2-й таблице (желтые клетки). Имеем: y1  2 / 3 ; y2  0 ; y3  0 . Проверка: g ( y )  9  (2 / 3)  15  0  2  0  6  f ( x  ) . Верно. ДОМАШНЕЕ ЗАДАНИЕ Прочитать лекционный материал по транспортной задаче (лекция 8). Знать методы северо-западного угла и минимальных тарифов, а также метод потенциалов. Для сформулированных ниже задач выполнить следующие действия: 1) написать двойственную задачу линейного программирования по отношению к заданной; 2) решить заданную задачу табличным симплекс-методом, определив при этом двойственные оценки. Сделать проверку, используя 1-ю теорему двойственности. (пытайтесь решить задачи самостоятельно, но если не получается, смотрите приведенные решения) Задача 4. F = х1 +4х2  max;  x1  x2  7,  2 x  x  0, 1 2  x  x  0, 1 2  x  .  1) двойственная ЗЛП: g ( y )  7 y1  min;  y1  2 y2  y3  1,   y1  y2  y3  4,  y  0.  2) для реализации симплекс-метода задачу необходимо представить в канонической форме. Каноническая форма задачи: F ( x )  x1  4 x2  max;  x1  x2  x3  7,  2 x  x  x  0,  1 2 4   x1  x2  x5  0,  x  0. Расширенная матрица уравнений-ограничений задачи:  x1 x2 x3   1 1 1  2 1 0   1 1 0 P P P 2 3  1 x4 1 P4 x5 1 P5 b  7 0  0 P0  Матрица представляет собой решенную относительно базисных переменных x3 , x4 , x5 систему линейных уравнений, причем правая часть системы состоит из неотрицательных чисел. Полагая свободные переменные равными нулю, получаем первый опорный план x T (1)  (0; 0; 7; 0; 0) . Реализацию табличного метода представим последовательностью симплекс-таблиц. Число переменных n в данной задаче равно 5; число уравнений m равно 3. Симплекс-таблица имеет (n + 3 = 8) столбцов и (m + 3 = 6) строк. Разрешающий столбец показан стрелкой. Разрешающие элементы заключены в скобки. Таб.1 б Cб P0 x3 7 x4 x5 f 1 P1 1 –2 1 –1 4 P2 1 (1) –1 –4 ↑ P3 1 P4 1 P5 1 Таб.2 б Cб P0 x3 1 4 7 x2 x5 f 1 P1 (3) –2 –1 –9 ↑ 4 P2 1 P3 1 P4 –1 1 1 4 P5 1 Таб.3 б Cб P0 x1 x2 4 7/3 14/3 7/3 21 x5 f 1 P1 1 4 P2 1 P3 1/3 2/3 1/3 3 y1 P4 –1/3 1/3 2/3 1 y2 P5 1 y3 В таб.3 нет отрицательных среди ∆j в нижней строке, значит, она соответствует оптимальному плану. Компоненты оптимального плана содержатся в столбце P0 . Ответ: x *T   7 / 3; 14 / 3; 0; 0; 7 / 3 . f *  f ( x * )  21 . Двойственные оценки находим в последней, 2-й таблице (желтые клетки). Имеем: y1  3 ; y2  1 ; y3  3 . Проверка: g ( y )  7  3  0 1  0  0  21  f ( x  ) . Верно. Задача 5. F = х1 +4х2  max;  x1  x2  7,  2 x  x  0, 1 2   x  x  1 2  0,  x  0. 1) двойственная ЗЛП: g ( y )  7 y1  min;  y1  2 y2  y3  1,   y1  y2  y3  4,  y  0.  2) для реализации симплекс-метода задачу необходимо представить в канонической форме. Каноническая форма задачи: F ( x )  x1  4 x2  max;  x1  x2  x3  7, 2 x  x  x  0,  1 2 4   x  x  x 5  0,  1 2  x  0. Расширенная матрица уравнений-ограничений задачи:  x1 x2 x3  1 1 1  2 1 0   1 1 0 P P P 2 3  1 x4 1 P4 x5 1 P5 b  7 0  0 P0  Матрица представляет собой решенную относительно базисных переменных x3 , x4 , x5 систему линейных уравнений. Первый опорный план: x T (1)  (0; 0; 7; 0; 0) . Реализацию табличного метода представим последовательностью симплекс-таблиц. Разрешающий столбец показан стрелкой. Разрешающие элементы заключены в скобки. Таб.1 б Cб P0 x3 7 x4 x5 f 1 P1 1 2 –1 –1 4 P2 1 –1 (1) –4 ↑ P3 1 P4 1 P5 1 1 P1 2 (1) –1 –5 ↑ 4 P2 1 P3 1 P4 1 4 P2 P3 1 P4 –2 1 P5 1 y1 1 5 y2 1 y3 Таб.2 б Cб P0 x3 4 7 x4 x2 f P5 1 Таб.3 б Cб P0 x3 1 7 1 P1 1 4 x1 x2 f В таб.3 нет отрицательных среди ∆j в нижней строке, значит, она соответствует оптимальному плану. Компоненты оптимального плана содержатся в столбце P0 . Ответ: x *T   0; 0; 7; 0; 0  . f *  f ( x * )  0 . Двойственные оценки находим в последней, 2-й таблице (желтые клетки). Имеем: y1  3 ; y2  5 ; y3  3 . Проверка: g ( y )  7  0  0  5  0  0  0  f ( x  ) . Верно. Задача 6. F ( x )  x1  x2  max;   x1  x2  1,   x1  2 x2  2,  x  0 x  0.  1 2 1) двойственная ЗЛП: g ( y )  y1  2 y2  min;   y1  y2  1,   y1  2 y2  1,  y  0.  2) Для реализации симплекс-метода задачу необходимо представить в канонической форме. Каноническая форма задачи: F ( x )  x1  x2  max;   x1  x2  x3  1,   x1  2 x2  x4  2,  x  0.  Расширенная матрица уравнений-ограничений задачи:  x1 x2 x3   1 1 1  1 2 0   P1 P2 P3 x4 1 P4 b  1 2  P0  Матрица представляет собой решенную относительно базисных переменных x3 , x4 систему линейных уравнений, причем правая часть системы состоит из неотрицательных чисел. Полагая свободные переменные равными нулю, получаем первый опорный план x T (1)  (0; 0; 1; 2) . Реализацию табличного метода представим последовательностью симплекс-таблиц. Число переменных n в данной задаче равно 4; число уравнений m равно 2. Симплекс-таблица имеет (n + 3 = 7) столбцов и (m + 3 = 5) строк. Разрешающий столбец показан стрелкой. Разрешающие элементы заключены в скобки. Таб.1 б Cб P0 x3 1 2 x4 f 1 P1 –1 1 –1 1 P2 (1) –2 –1 ↑ P3 1 P4 1 1 P1 –1 1 P2 1 P3 1 P4 –1 –2 ↑ 2 1 1 Таб.2 б Cб P0 x2 1 1 x4 f 4 1 В таб. 2 величина ∆1 = –2 в нижней клетке столбца P1 дает возможность увеличения значения целевой функции за счет увеличения переменной x1 . Однако среди компонент столбца P1 нет положительных. Это означает, что пере- менную x1 можно увеличивать до бесконечности; при этом целевая функция растет беспредельно. Решения задачи нет – целевая функция не ограничена сверху. Этот вывод можно было бы сделать и без вычерчивания и пересчета симплекс-таблиц – достаточно воспользоваться 1-й теоремой двойственности: Если одна задача двойственной пары ЗЛП имеет оптимальный план, то и вторая тоже имеет оптимальный план, причем значения целевых функций этих задач на оптимальных планах равны. Если целевая функция одной из задач двойственной пары не ограничена, то множество допустимых решений второй пусто и наоборот. В самом деле, в нашем случае двойственная задача g ( y )  y1  2 y2  min;   y1  y2  1,   y1  2 y2  1,  y  0.  имеет пустую область ограничений. Это сразу следует из сложения неравенств системы ограничений, после которого получаем  y2  0 , что противоречит условию y  0 . Значит, целевая функция прямой задачи неограничена. Задача 7. F = х1 +4х2 max;  x1  x2  7,  3  x1  x 2  7,   x  x  3,  1 2 x  5,    2 x  5,  2   x  0.  x  0.  1) двойственная ЗЛП: g ( y )  7 y1  3 y2  5 y3  min;  y1  y2  1,   y1  y2  y3  4,  y  0.  3) для реализации симплекс-метода задачу необходимо представить в канонической форме. Каноническая форма задачи: F ( x )  x1  4 x2  max;  x1  x2  x3  7,   x  x  x  3,  1 2 4  x  x  5, 5  2  x  0. Расширенная матрица уравнений-ограничений задачи:  x1 x2 x3  1 1 1  1 1 0  0 1 0 P P P 2 3  1 x4 1 P4 x5 1 P5 b   7 3   5 P0  Матрица представляет собой решенную относительно базисных переменных x3 , x4 , x5 систему линейных уравнений, однако вторая компонента правой части системы отрицательна. Это означает, что присвоение нулевых значений свободным переменным x1 , x2 уведет базисную переменную x4 в отрицательную область, что несовместимо с требованием x  0 . Систему уравнений-ограничений необходимо перерешать, убрав x4 из базиса. С этой целью прибавим второе уравнение системы к первому, исключив переменную x4 из всех уравнений, кроме второго. Таким образом, переменная x4 станогвится базисной и мы получаем следующую расширенную матрицу:  x1 x2 x3  0 0 1  1 1 0  0 1 0 P P P 2 3  1 x4 1 1 P4 x5 1 P5 b   4 3   5 P0  Умножив вторую строку матрицы на –1, получим желаемое решение системы:  x1  0 1  0 P  1 x2 1 1 P2 x3 1 P3 x4 x5 1 0 1 0 0 1 P4 P5 b  4 3  5 P0  Теперь все хорошо : матрица представляет собой решенную относительно базисных переменных x3 , x1 , x5 систему линейных уравнений, причем правая часть системы состоит из неотрицательных чисел. Полагая свободные переменные x2 , x4 равными нулю, получаем первый опорный план x T (1)  (3; 0; 4; 0; 5) . Реализацию табличного метода представим последовательностью симплекс-таблиц. Число переменных в данной задаче равно 5; число уравнений m равно 3. Симплекс-таблица имеет (n + 3 = 8) столбцов и (m + 3 = 6) строк. Разрешающий столбец показан стрелкой. Разрешающие элементы заключены в скобки. Таб.1 б Cб P0 x3 1 4 3 5 3 x1 x5 f 1 P1 1 4 P2 (1) 1 –3 ↑ P3 1 P4 1 –1 –1 P5 1 1 P1 1 –1 3 4 P2 1 P3 1 P4 1 –1 (1) –4 ↑ 1 P1 (1) –1 –1 ↑ 4 P2 1 P3 1 P4 1 1 P1 1 4 P2 1 P3 1 P4 P5 –1 1 y2 1 1 y1 1 3 y3 Таб.2 б Cб P0 x3 4 4 3 2 12 x2 x5 f P5 1 Таб.3 б Cб P0 x3 4 2 5 2 20 x2 x4 f P5 –1 1 1 4 Таб.4 б Cб P0 x1 x2 4 2 5 x4 f 4 22 В таб.4 нет отрицательных среди ∆j в нижней строке, значит, она соответствует оптимальному плану. Компоненты оптимального плана содержатся в столбце P0 . Ответ: x *T   2; 5; 0; 4; 0 . f *  f ( x * )  22 . Двойственные оценки находим в последней, 2-й таблице (желтые клетки). Имеем: y1  1 ; y2  0 ; y3  3 . Проверка: g ( y )  7  (1)  3  0  5  3  22  f ( x  ) . Верно.