Задача линейного программирования

163 Раздел V. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ. ЛЕКЦИЯ 19. ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. Линейные задачи оптимизации. Целевая функция. Классический пример задачи Линейного Программирования, - Задача о Диете. Стандартная и Каноническая формы задачи Линейного Программирования. Так называемые оптимизационные экономико-математические модели содержат один или несколько критериев оптимальности и некоторые ограничения, - условия, вытекающие из содержательной части постановки задачи. Если ограничения сформулированы в виде системы уравнений или неравенств относительно переменных x1, x2 , ..., xn и добавлены требования неотрицательности переменных x1  0 , x2  0 ,…, xn  0 , то получим задачу Математического программирования. Она включает в себя: 1) целевую функцию: f x1, x2 ,..., xn   max min  2) специальные ограничения:  gi  x1, x2 ,...,xn   0, i  1,, k h  x , x ,...,x   0, j  k  1,, m n  j 1 2 3) ограничения общего вида: x1  0 , x2  0 ,… , xn  0 Задача математического программирования состоит в определении   T вектора x *  x1* , x2* , ..., xn* , который является решением задачи: f x1, x2 ,...,xn   maxmin   g i  x1 , x2 ,...,xn   0, i  1,, k  h j  x1 , x2 ,...,xn   0, j  k  1,, m   x1  0, x2  0, , xn  0 Математически это – задача на условный экстремум. Задача Линейного программирования (точнее было бы использовать термины «линейное планирование», «математическое планирование», но эти сочетания уже закрепились и широко используются в литературе) – частный случай задачи математического программирования, в котором целевая функция и 164 все функции ограничений - линейны. Именно этот класс оптимизационных моделей широко применяется в экономике и управлении. Исторически «Задача о диете» является одним из первых примеров классической задачи Линейного программирования – так называемой «Задачи о смесях». Кроме того типичные экономические задачи, такие, как задача о планировании производства и оптимальном использовании ресурсов, задача о формировании потребительской корзины, задача о перевозках (транспортная задача) так же являются классическими задачами Линейного программирования. Пример 1. [2] «Задача о диете» Дама, просто приятная, решила похудеть и как это часто бывает, обратилась за советом к подруге. Подруга, дама приятная во всех отношениях, посоветовала ей перейти на рациональное питание, состоящее исключительно из новомодных продуктов P и Q. Дневное питание этими новинками должно давать не более 14 единиц жира (чтобы похудеть), но не менее 300 калорий(чтобы не сойти с дистанции раньше). На банке с продуктом P написано, что в Одном килограмме содержится 15 единиц жира и 150 калорий, а на банке с продуктом Q – 4 единицы жира и 200 калорий соответственно. При этом цена 1 кг продукта P равна 15 рублей, а 1 кг продукта Q - 25 рублей. Так как дама, просто приятная, в это время была весьма стеснена в средствах, то ее очень интересовал ответ на вопрос: в какой пропорции нужно брать эти удивительные продукты P и Q, чтобы выдержать условия диеты и потратить как можно меньше средств? Итак, запишем все условия задачи в таблицу: P Q Жир Калории Цена 15 150 15 4 200 25 Для того, чтобы математически «поставить» задачу, обозначим искомое количество продукта P - за x, искомое количество продукта Q - за y. 165 Поскольку стоимость суммарного продукта получим целевую функцию: 15x  25 y  min - z  15x  25 y , то 15x  4 y  14 150x  200 y  300  и ограничения:  x  0  y  0 Рис. 19.1 Будем искать решение этой совсем не геометрической задачи графически. В Декартовой системе координат Oxy построим две прямые l1 и l2 . l1 : 15x  4 y  14 и l2 : 150x  200 y  300 . Найдем точки их пересечения с осями Ox и Oy. Для прямой l1 , - тт. A 14   7  ,0  , B 0,  .  15   2  Для прямой l2 , - тт.  3 C 2,0, D 0,  .  2 Прямая l1 делит плоскость на 2 полуплоскости: очевидно, что в одной 15x  4 y  14 , в другой - 15x  4 y  14 . В какой из полуплоскостей 166 выполняется нужное неравенство 15x  4 y  14 ? Рассмотрим т.О(0,0): 15  0  4  0  0  14 , - таким образом, т.О лежит в искомой полуплоскости(слева). Аналогично можно найти на плоскости множество точек, координаты которых удовлетворяют неравенству 150x  200 y  300 . Заметим, что 150  0  200  0  300 , то есть искомая полуплоскость не содержит т.О(0,0), и, значит, она лежит выше прямой, проходящей через т.С и т.D. Прибавив условие x  0, y  0 , получаем  BDE, в котором выполняются и специальные ограничения и ограничения общего вида. То есть, в данной задаче  BDE – это область допустимых решений. Здесь т.E – точка пересечения прямых и находится, как решение 15x  4 y  14 150x  200 y  300 системы уравнений:  Решая систему методом Гаусса, находим x  , y  1 . Итак, точка пересечения прямых E  , 1 . 2 3 2 3  Графически линейная функция z  15x  25 y является уравнением плоскости. Нас интересует только та часть плоскости, которая лежит над  BDE. Чтобы построить ее, мы можем провести из всех трех вершин  BDE линии, параллельные оси OZ, - пересечением их с плоскостью z  15x  25 y будет другой треугольник. Так называемый плоский срез призматической поверхности обладает следующим свойством: как самая высокая, так и самая низкая его точки располагаются непосредственно над вершинами  BDE. Вычислим z  15x  25 y в этих трех вершинах : z B  87,5 , z D  37,5 , 2 z E  35 . Целевая функция минимальна в т.E, то есть x  , y  1 и 3 x 2  . искомая пропорция: y 3 Ответ на вопрос, волновавший даму просто приятную, получен: для того, чтобы выдержать условия диеты и потратить как можно меньше денег нужно брать рекомендованные продукты в соотношении два к трем Воспользовалась ли она этими рекомендациями – неизвестно. Заметим, что оптимальное решение найдено так называемым методом перебора. 167 Определение 1. Задача Линейного Программирования (ЗЛП) с n переменными x1, x2 , ..., xn и m ограничениями в стандартной форме имеет вид: f x   c1x1  c2 x2  ...  cn xn  max a11 x1  a12 x2  ...  a1n xn  b1 a x  a x  ...  a x  b c , x   max 2n n 2  21 1 22 2 (1) ... или коротко: (2) Ax  b , где a x  a x  ...  a x  b x0 mn n m  m1 1 m 2 2  x1  0, x2  0, ... xn  0  a11 a12 ... a1n    a a ... a  21 22 2n  , c  c1, c2 ,...,cn  , A  aij nm , или подробно A   ... ... ... ...    a a ... a m2 mn   m1  x1   b1      x b    x   2 , b   2 . ... ...      bm   xn    Подчеркнем, что выражение Ax  b из ЗЛП (2) является просто компактной записью системы линейных уравнений из ЗЛП (1). Согласно Определению 6 Лекции 13, здесь и далее подразумевается не сравнение векторов в целом (что невозможно, учитывая, что вектор кроме координат имеет еще и направление), а выполнение соответствующего неравенства для каждой компоненты. Аналогично запись x  0 является компактной записью набора ограничений x1  0, x2  0, ..., xn  0 по Определению 6 Лекции 13. Заметим, что несложно привести все ограничения к одному виду: исходное неравенство со знаком  нужно умножить на (-1). Определение 2. Оптимальным решением задачи (1) называется   T такое допустимое решение x *  x1* , x2* , ..., xn* , которое обращает в максимум целевую функцию:   f *  f x1* , x2* , ..., xn*  max f x1 , x2 ,..., xn  . x  ОДР 168 Величина f * является оптимальным значением целевой функции задачи (1). Общая задача линейного программирования отличается от стандартной тем, что некоторые ограничения имеет форму равенств: c , x   max  n   aij x j  bi ,  j 1   n   aij x j  bi ,  j 1   x j  0,   i  1,..., k i  k  1,..., m , j  1,..., n Здесь ограничения сокращенно записаны с использованием знака суммирования  . Иногда полезно использовать Канонический вид задачи линейного программирования: f x   c1x1  c2 x2  ...  cn xn  maxmin  a11 x1  a12 x2  ...  a1n xn  b1 a x  a x  . ..  a x  b 22 2 2n n 2  21 1 ... a x  a x  ...  a x  b mn n m  m1 1 m 2 2  x1  0, x2  0, ... , xn  0 Переход от задачи линейного программирования в стандартной форме (1) к каноническому виду осуществляется путем добавления новых m переменных xn 1, xn  2 , ..., xn  m : f x   c1x1  c2 x2  ...  cn xn  max a11 x1  a12 x2  ...  a1n xn  xn 1  b1 a x  a x  ...  a x  0  x 22 2 2n n n 1  xn  2  b2  21 1 ... a x  a x  ...  a x  0  x m2 2 mn n n 1  ...  xn  m  bm  m1 1  x1  0, x2  0, ..., xn  0, xn 1  0, xn  2  0, ..., xn  m  0 169      a11 a12 ... a1n 1 0 ... 0  a 22 ... a 2n 0 1 ... 0  ~ a ~ nm A   21  , A  aij m . Очевидно, что ... ... ... ... ... ... ...  ...  a m1 a m 2 ... a mn 0 0 ... 1      m   ~ rang A  m , так как матрица, составленная из m строк и последних m     столбцов является единичной матрицей, которая может быть выбрана в качестве базисного минора. В этом случае базисными переменными будут xn 1 , … xn  m и можно найти так называемое первое базисное решение ЗЛП, используя методы решения систем линейных уравнений. «Платой» за использование известных методов линейной алгебры является увеличение количества переменных: от n - к n  m . Согласно Определению 4 Лекции 8, частное решение системы, в котором все свободные переменные равны нулю, называется базисным решением (относительно данного базисного минора). Определение 3. Опорным (базисным) решением задачи линейного программирования в канонической форме с (n+m) переменными и m уравнениями называется решение, в котором все n свободных переменных равны нулю, а m базисных переменных неотрицательны. 170 ЛЕКЦИЯ 20. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. Графический метод решения задач Линейного Программирования. Свойства решений задач Линейного Программирования. Графический метод решения ЗЛП достаточно прост и имеет наглядный геометрический смысл для случая двух и трех переменных (n=2, n=3). Запишем Задачу Линейного Программирования с двумя переменными x1, x2 (n=2) и m ограничениями в стандартной форме: f ( x1, x2 )  c1x1  c2 x2  max a11 x1  a12 x2  b1 a x  a x  b 21 1 22 2 2   ... a x  a x  b m2 2 m  m1 1   x1  0, x2  0. Заметим, что целевая функция в данном случае – это функция двух переменных и ее линии уровня – прямые линии. Для каждого неравенства ai1x1  ai 2 x2  bi из системы специальных ограничений можно построить соответствующую прямую li : ai1x1  ai 2 x2  bi , которая делит плоскость на две полуплоскости. Очевидно, что в одной из них выполняется условие: ai1x1  ai 2 x2  bi , в другой: ai1x1  ai 2 x2  bi . Отметим штриховкой ту из полуплоскостей, в которой выполняется нужное неравенство. Добавив условие x1  0, x2  0 , получим область допустимых решений ЗЛП для случая, когда в специальных ограничениях только одно это неравенство. Если неравенств несколько, нужно для каждой прямой выделить полуплоскость, в которой выполняется нужное неравенство. Область, в которой выполняются одновременно все специальные ограничения и ограничения общего вида будет искомой Областью допустимых решений (ОДР) Задачи Линейного Программирования. 171 Рис. 20.1 Если неравенств несколько, нужно для каждой прямой выделить полуплоскость, в которой выполняется нужное неравенство. Область, в которой выполняются одновременно все специальные ограничения и ограничения общего вида будет искомой Областью допустимых решений (ОДР) Задачи Линейного Программирования. Возможные варианты Области допустимых решений: I.[3]  x1  x 2  1   x1  x 2  1 т. А0,1 – допустимое решение.  x  0, x  0  2 172 Рис. 20.2 Область допустимых решений в данном случае состоит из одной точки. II.[3]  x1  x2  3   x1  x2  4  x  0, x  0  2 Рис. 20.3 Допустимых решений нет. 173 Область допустимых решений в данном случае состоит из пустого множества. III.  x1  2 x 2  4  x x 6  1 2   x1  x2  4  x  0, x 2  0 Рис. 20.4 Область допустимых решений в данном случае – ограниченное выпуклое множество. IV.  x1  x 2  2  x x 4  1 2   2 x1  x 2  4  x  0, x 2  0 174 Рис. 20.5 Область допустимых решений в этом случае – неограниченное выпуклое множество. Заметим, что для случая, когда n=3, принципиально алгоритм поиска Области допустимых решений не меняется: вместо прямых мы имеем дело с пересечением плоскостей и ищем область в пространстве, где выполняются все специальные ограничения и ограничения общего вида. Конечно, это существенно более громоздкая процедура, чем для n=2. Алгоритм решения задач графическим методом (n=2): линейного программирования 1. Поиск области допустимых решений. Возможны 4 варианта: а) пустое множество б) множество, состоящее из одной точки в) выпуклое ограниченное множество г) выпуклое неограниченное множество 2. Поиск оптимального значения целевой функции: а) перебором б) с помощью вектора-градиента. 175 Определение 1. Вектор-градиент f ( x1, x2 )  c1x1  c2 x2  max(min) целевой функции  f f    c1, c2  c  g r a df ( x1, x2 )   ,  x  x  1 2 перпендикулярен к линиям уровня целевой функции и показывает направление, в котором линии уровня возрастают. Пример 1. Пусть целевая функция имеет вид: f  2 x1  3x2  max . Тогда вектор-градиент c  2,3 . Рис. 20.6 1) Рассмотрим линию уровня функции двух переменных, где значение целевой функции равно нулю, то есть L  0 . Тогда имеем уравнение прямой: 2 x1  3x2  0 . Из этого уравнения следует, что скалярное произведение векторов равно нулю: c , x   0 . Следовательно, вектор 2,3  x1, x2  . Из уравнения прямой линии получаем 2 x2   x1 , то 3 2 k1   . Очевидно, что вектор 3 3 k2  . оси ОХ Условие c имеет тангенс угла наклона к 2 ортогональности векторов k1  k2  1 - выполнено. есть коэффициент этой прямой 176 2) Рассмотрим линию уровня, когда L  3  2 x1  3x2  3 , или 2 3 x2   x1  3 3 3) Рассмотрим линию уровня, когда L  3  2 x1  3x2  3 , или 2 3 x2   x1  и т.д. 3 3 Таким образом, все линии уровня параллельны между собой и ортогональны вектору-градиенту. Очевидно, что линии уровня возрастают в направлении вектора-градиента. Найдем теперь оптимальное значение функции f  2 x1  3x2 в области допустимых решений из пункта III (см. рис. 20.4, рис. 20.6, рис. 20.7). Очевидно, что через т. N , граничную точку ОДР, пройдет линия уровня, имеющая максимальное значение и тогда f *  f N . Найдем     f *  f x1* , x2* . Определим координаты т. N , решив  x x 6 систему уравнений методом Гаусса:  1 2  x1  2 x2  4 I  II 2  x1  2  x  x  6  1 2  3 .   1  3x2  10  x2  3  3 8 10 1 2 1 Таким образом, x *   2 , 3  , f *  2   3   15 . 3 3 3  3 3 x *  x1* , x2* Вернемся и к общему случаю: целевая функция имеет вид вектор-градиент f ( x1, x2 )  c1x1  c2 x2  max(min) , c  c1,c2  . Уравнение линии уровня c1x1  c2 x2  L , - это общее уравнение прямой. Тогда уравнение с угловым коэффициентом для этой c c L прямой: x2   1 x1  и k1   1 . c2 наклона к оси ОХ c2 c k2  2 и c1 c2 Вектор c имеет тангенс угла k1  k 2  1 . Очевидно, что вектор- градиент ортогонален линиям уровня и показывает направление их роста. 177 В Примере 1. был рассмотрен случай, когда ЗЛП имеет единственное решение. При этом оптимальное решение достигается в одной из вершин области допустимых решений. Пример 2. Найдем теперь оптимальное значение целевой функции f  3x1  3x2  max в той же области допустимых решений из Примера 1. Здесь вектор-градиент c  3,3 . Заметим, что линии уровня параллельны ребру NM . Убедимся в этом: так же, как Примере 1, определим координаты т. M и найдем значения целевой 2 1 функции в т. N  2 ,3  и т. M 5,1 .  3 3 Получаем f *  f N  f M  18 (см. рис. 20.7). Рис. 20.7 В Примере 2. рассмотрен случай, когда ЗЛП имеет множество решений: если в двух крайних точках отрезка целевая функция принимает оптимальное решение, то она принимает оптимальное решение во всех точках отрезка. 178 Это так называемый «альтернативный оптимум». В этом случае оптимальное решение достигается в двух вершинах области допустимых решений, а также во всех внутренних точках соответствующего ребра области допустимых решений. Заметим, что, с одной стороны, - если Задачу Линейного Программирования в стандартной форме с двумя переменными x1, x2 (n=2) привести к каноническому виду, то у общего решения соответствующей системы линейных уравнений всегда будет две свободные переменные. С другой стороны, любая вершина области допустимых решений есть точка пересечения двух прямых, то есть как минимум две из переменных, составляющие решение ЗЛП в каноническом виде равны нулю. Согласно Определению 3 Лекции 19, получаем, что всякая вершина области допустимых решений совпадает с одним из опорных решений системы специальных ограничений в каноническом виде. Для случая, когда область допустимых решений ЗЛП – неограниченное выпуклое множество, существование оптимального решения зависит от вектора-градиента целевой функции. Суммируя все вышесказанное, сформулируем несколько утверждений. Утверждение 1. Если задача линейного программирования имеет оптимальное решение, то целевая функция принимает максимальное (минимальное) значение в одной из вершин (угловых точек) области допустимых решений. Утверждение 2. Если линейная функция принимает максимальное (минимальное) значение в 2-х угловых точках (т.А и т.В) области допустимых решений, то она принимает его в любой точке отрезка АВ. Объединяя Утверждение 1 и Утверждение 2 получаем: Если область допустимых решений ограничена, то оптимальное решение задачи линейного программирования существует (одно или множество). 179 Утверждение 3. Если ОДР не ограничена, то оптимальное решение существует тогда, когда линейная функция ограничена сверху для задачи на поиск максимума или снизу для задачи на поиск минимума. Объединяя Утверждение 1, 2,3 и Определение 3 Лекции 19 получаем: Утверждение 4. Если задача линейного программирования имеет оптимальное решение (в ограниченной области – всегда, в неограниченной – в зависимости от ограниченности линейной функции), то оно совпадает, по крайней мере, с одним из опорных решений системы специальных ограничений задачи линейного программирования в канонической форме. 180 ЛЕКЦИЯ 21. ТРАНСПОРТНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Постановка Транспортной задачи. Графический метод решения простейших Транспортных задач. Примеры задач, сводящихся к транспортной: задача о формировании штата фирмы; задача о назначениях. Рассмотрим еще один классический пример задачи Линейного программирования, - задачу о перевозках (транспортную задачу). Транспортная задача Здесь рассмотрим так называемую сбалансированную задачу, то есть задачу о перевозках, в которых общий объем товаров, готовых к отправлению, в точности равен объему товаров, который готовы принять в пунктах назначения. В общем виде сбалансированная транспортная задача состоит в том, что существует m пунктов отправления A1, A2 ,, Am , n пунктов назначения B1, B2 ,, Bn ; в каждом пункте отправления Ai находится ai единиц товара, запрос пункта назначения B j - b j единиц товара. Дана матрица C  cij  nm , где cij – стоимость доставки единицы продукции из i-го пункта отправления в j-ый пункта назначения. В частности, c12 – стоимость доставки единицы продукции из 1-го пункта отправления во 2-ой пункта назначения. xij – искомое число единицы продукции, перевезенное из i-го пункта отправления в j-ый пункта назначения. Рис.21.1 181 Стоимость перевозки xij единиц продукции из i-го пункта отправления в j-ый пункта назначения составляет: cij  xij . Тогда общая стоимость всех перевозок составляет: c11 x11  c12 x12  ...  cmn xmn  отправления вывезено m n   cij xij  F . При этом из i-го пункта i 1 j 1 xi1  xi 2    xin  n  xij  ai единиц товара. В j 1 j-ый пункт назначения привезут x1 j  x2 j    xmj  товара. m Выполнено условие :  ai  i 1  xij  b j единиц i 1 n b j . j 1 Итак, сбалансированная транспортная программирования имеет вид: F m задача Линейного m n   cij xij  min i 1 j 1 n  xij  ai , i  1,, m j 1 m (1)  xij  b j , j  1,, n xij  0, i, j i 1 n  ai  i 1 m b j j 1 Пример 1. Пусть m  2 – количество складов, n  3 – количество магазинов. Задана матрица стоимостей перевозки единиц товара    c11 c12 c13   . C  cij 32   c c c  21 22 23  Тогда, согласно условиям задачи ограничения, связанные с возможностями каждого из выглядят так: (1), складов x11  x12  x13  a1 x21  x22  x23  a2 Ограничения, соответствующие поступлениям в каждый магазин выглядят так: 182 x11  x21  b1 x12  x22  b2 x13  x23  b3 , x11  0, x 12  0, x13  0, x21  0, x22  0, x23  0 , при этом Целевая функция имеет вид: F  2 3 i 1 j 1  ai   b j . 2 3   cij xij  min , так как общую i 1 j 1 стоимость всех перевозок нужно минимизировать. Требуется найти оптимальное решение сбалансированной транспортной задачи Линейного программирования, - матрицу перевозок    x* x* x*  11 12 13  * 3 , для которой значение целевой X  xij 2    * * *   x21 x22 x23  функции F минимально. Существуют различные транспортной задачи. методы решения сбалансированной Несбалансированные задачи сводятся к сбалансированной задаче двумя способами. I. Если выполняется условие «фиктивный потребитель». m n i 1 j 1  ai   b j , вводится так называемый Количество пунктов увеличивается на единицу, при этом считается, что bn 1  назначения m  ai  i 1 n b j . j 1 Размер матрицы стоимостей перевозки единиц товара меняется, добавляется лишний столбец. Теперь матрицы стоимостей перевозки единиц товара имеет вид C  cij  nm1 , где ci,n 1  0 , i  1, , m . Заметим, что целевые функции исходной задачи: F  c11 x11  c12 x12  ... cmn xmn  m n   cij xij и модифицированной: i 1 j 1 F  c11 x11  c12 x12  ... cmn xmn  0  x1 n 1   0  xm n 1  совпадают. m n 1   cij xij , i 1 j 1 - 183 II. Если выполняется условие m  ai  i 1 «фиктивный поставщик». n  b j , вводится так называемый j 1 Количество пунктов отправления увеличивается на единицу, при этом считается, что am 1  n m j 1 i 1  b j -  ai . Размер матрицы стоимостей перевозки единиц товара меняется, добавляется лишняя строка. Теперь матрицы стоимостей перевозки единиц товара имеет вид C  cij  n , где cm 1, j  0 , j  1, , n . Целевые функции F  c11 x11  c12 x12  ... cmn xmn  m 1 исходной задачи: m n   cij xij и модифицированной: i 1 j 1 F  c11 x11  c12 x12  ... cmn xmn  0  xm 1,1   0  xm 1,n  m 1 n   cij xij также i 1 j 1 совпадают. Покажем, что в некоторых случаях транспортную задачу можно решить графически. Пример 2. [2] Пусть m  2 – количество складов, n  2 – количество магазинов. Задана матрица стоимостей перевозки единиц товара C  cij  22   1 2   . 2 1   На складе A1 находится a1  20 единиц товара, на складе A2 находится a2  10 единиц товара. Запрос магазина B1 : b1  16 единиц товара, запрос магазина B2 : b2  14 единиц товара. Обычно эти данные задачи представлены в табличном виде: п о т р е б н о с т и м а г а A1 A2 B1 B2 1 2 16 2 1 14 20 10 н а с к л а 184 Поскольку общую стоимость всех перевозок необходимо минимизировать, получаем целевую функцию транспортной задачи: F  1  x11  2  x12  2  x21  1  x22  min  x11  x12  20  x  x  10  21 22 и ограничения:  x11  x21  16 .  x  x  14 22  12  x11  0, x 12  0, x21  0, x22  0 Легко видеть: 20  10  2  ai  i 1 Требуется найти 2  b j  16  14  30 . j 1 оптимальное решение сбалансированной    x* x* * 2 транспортной задачи - матрицу перевозок X  xij 2   11 12  * *  x21 x22 которой значение целевой функции F минимально. Введя новую переменную  x11  t  x  20  t  получим:  12  x21  16  t  x22  10  x21  t  6 Поскольку все   , для   x11  t  0 , переменные t  0 t  20  неотрицательны, получаем:  и результирующее ограничение: t  16  t  6 6  t  16 . Преобразуем целевую функцию, чтобы она стала функцией одной переменной t : Построим прямую, F  t  220  t   216  t   t  6  66  2t . соответствующую этому уравнению. Отрезок АВ – это множество возможных значений целевой функции. Очевидно, что минимальное значение целевая функция достигнет (рис.21.2) при максимально возможном значении аргумента, - t  16 . Таким образом, получаем *  16 , x*  4 , x11 оптимальное решение задачи: F *  66  2t  34 , 12 *  0 , x *  10 . x21 22 185 Рис. 21.2 Пример 3. [2]. Пусть, так же, как в Примере 1, m  2 – количество складов, n  3 – количество магазинов. Конкретные числовые данные для подобных задач удобно представить в табличном виде: A1 A2 B1 B2 B3 6 9 70 5 4 140 8 6 90 120 180 Здесь C  cij  32   6 5 8   . Запишем математическую постановку этой  9 4 6 транспортной задачи: F  6 x11  5x12  8x13  9 x21  4 x22  6 x23  min  x11  x12  x13  120  x  x  x  180 23  21 22  x11  x21  70   x12  x22  140  x13  x23  90   x11  0, x 12  0, x13  0, x21  0, x22  0, x23  0 186 Требуется найти оптимальное решение сбалансированной   * x* x*  3  x11 12 13  * * транспортной задачи - матрицу перевозок X  xij  , 2  * * *   x21 x22 x23  для которой значение целевой функции F минимально. Введя две новые переменные: x11  u , x12  v , выразим остальные исходные переменные через новые переменные u, v . Получим: x21  70  u , x22  140  v , x13  120  u  v , Поскольку все переменные x23  90  120  u  v   u  v  30 . неотрицательны, в данном случае можно свести транспортную задачу к задаче Линейного программирования. Преобразовав соответствующим образом целевую функцию получаем: F  6u  5v  8120  u  v   970  u   4140  v   6u  v  30   5u  v  1970  min u  v  120 u  70  v  140 u  v  30  u  0, v  0 Рис. 21.3 187 Вектор-градиент целевой функции c   5,1 . На рис.21.3 для удобства построен коллинеарный ему вектор c    75,15. Очевидно, что минимальное значение целевой функции достигается в т. N 70, 50 . Таким образом, получаем оптимальное решение задачи: F *  1970  5  70  50  1570, *  70 , x*  50 , x*  0 , x*  0 , x*  90 , x11 12 22 13 21 *  90 . x23 Задачи, сводящиеся к транспортной. Известно довольно много задач, решение которых находится так же, как в транспортной задаче, при этом содержательная часть задачи никак не связана ни с каким видом транспорта. Например, это задача о формировании штата фирмы; задача о назначениях. Пример Задачи о формировании штата фирмы. В 80-е годы прошлого века советские консульства за рубежом предпочитали использовать труд членов семей дипломатических работников на таких должностях, как секретарь-референт, работники бухгалтерии, визовой службы, отдела технического обслуживания. Обучать потенциальных работников нужно было языку (английскому, или страны пребывания), математическому обеспечению персональных компьютеров и инженерному обслуживанию компьютерных сетей. По результатам тестирования было сформировано 3 группы (7, 5 и 6 человек в каждой) по обучению предполагаемых работников для занятия должностей 4 видов (известно, что есть 5 вакансий секретарей-референтов, 3 – в отделе выдачи виз, 6 вакансий работников бухгалтерии, 4 вакансии в отделе технического обслуживания. Известно, что на обучение кандидата из i-го группы для занятия должности j-ого вида вакансий тратится cij средств. Задана матрица  c11 c12 c13 c14  120 150 185 210      4 C  cij 3   c21 c22 c23 c24    95 135 150 180 .  c c c c   80 95 140 165    31 32 33 34     Все данные задачи сведены в таблицу: 188 Секретарь Language Hardware Software Вакансии 120 95 80 5 Визов. Бухгалтер Отдел 150 185 135 150 95 140 3 6 Техн. Отдел 210 180 165 4 bj Группы ai 7 человек 5 человек 6 человек 3 4 i 1 j 1  ai   b j Как минимизировать общие затраты на обучение потенциальных работников? Математическая постановка этой задачи выглядит так: F 3 4   cij xij  min i 1 j 1  x11  x12  x13  x14  7 x  x  x  x  5 23 24  21 22  x31  x32  x33  x34  6   x11  x21  x31  5 x  x  x  3 22 32  12  x13  x23  x33  6   x14  x24  x34  4  xij  0, xij  целое  Требуется так же, как для сбалансированной транспортной задачи,  x* x* x* x*   11 12 13 14   * * * *  найти оптимальное решение, - матрицу X  xij* 34   x21 x22 x23 x24  ,  * * * *   x31 x32 x33 x34    для которой значение целевой функции F будет минимальным.   Пример задачи о назначениях. В задаче о назначениях известно, что есть одинаковое количество работников и работ, которые нужно выполнить, причем каждый работник будет выполнять только одну работу и, соответственно, каждая работа будет выполняться только одним работником. 189 Известно, какое время тратит каждый работник на выполнение определенной работы. В задаче о назначениях искомые переменные – бинарные, то есть те, которые принимают только значения 0 и 1. Нужно так распределить работы между работниками, чтобы общее время выполнения всех работ было минимальным. F n n   cij xij  min , i 1 j 1 1, если i  й работник выполняет j  ю работу . xij   0, в противном случае Пусть n  4 и известно время в одинаковых единицах, которое тратит каждый работник на выполнение определенной работы: Имя\Работа Геракл Емеля Сизиф Папа Карло 1 2 3 7 5 2 5 4 3 7 3 1 4 5 3 4 3 5 8 5 Математическая постановка задачи о назначениях выглядит так: F 4 4   cij xij  2  x11  5  x12  1  x13  3  x14  3  x21  4  x22  4  x23  i 1 j 1 5  x24  7  x31  3  x32  5  x33  8  x34  5  x41  7  x42  3  x43  5  x44  min  x11  x12  x13  x14  1   x21  x22  x23  x24  1  x31  x32  x33  x34  1   x41  x42  x43  x44  1  , поскольку матрица временных затрат  x11  x21  x11  x41  1 x  x  x  x  1 22 32 42  12  x13  x23  x33  x43  1 x  x  x  x  1 24 34 44  14  xij  двоичная переменная 190 2 51 3     3 4 4 5 4 известна. Для данного примера одним из методов C  сij 4   7 358   5 7 3 5    решения транспортной задачи найдено оптимальное решение  x* x* x* x*   11 12 13 14   0 0 1 0    * * * *   x x x x 1   21 22 23 24  матрица X  xij* 44   , для которой значение  * * * *   0 1 0 0   x31 x32 x33 x34   1   * * * *    x41 x42 x43 x44    целевой функции F минимально, F *  12 единиц времени. Таким образом, за минимально возможное время будут выполнены все работы, при этом, Геракл возьмется за третью работу, Емеля – за первую, Сизифу достанется вторая работа, а четвертая работа останется для Папы Карло. 191 ЛЕКЦИЯ 22. СИМПЛЕКС-МЕТОД. Симплекс - метод решения задач Линейного Программирования. Опорное решение. Алгоритм Симплекс - метода. Пример нахождения решения задачи Линейного программирования Симплекс - методом. В Лекции 20 был рассмотрен Графический метод решения Задачи Линейного Программирования. Он позволяет построить область допустимых решений и нагляден для случая двух и трех переменных (n=2, n=3). n=2: F x   c1x1  c2 x2  max Вектор - градиент c  c1,c2  . Рис. 22.1 n=3: F x   c1x1  c2 x2  c3 x3  max Рис. 22.2 Вектор - градиент c  c1, c2 , c3  . 192 Оптимальное решение ЗЛП, если оно существует, будет находиться в вершинах (угловых точках) области допустимых решений и его легко можно найти с помощью вектора- градиента. В случае « альтернативного оптимума» оптимальное решение ЗЛП достигается в двух соседних вершинах (и во всех внутренних точках соответствующего отрезка). Оптимальное решение ЗЛП для случая более, чем трех переменных можно найти с помощью метода перебора вершин области допустимых решений. Как уже говорилось в Лекции 20, если задача линейного программирования имеет оптимальное решение, то оно совпадает, по крайней мере, с одним из опорных решений системы специальных ограничений задачи линейного программирования в канонической форме. Таким образом, перебор всех опорных решений, то есть угловых точек области допустимых решений, приведет к оптимальному решению, так как множество угловых точек конечно. Но существуют чисто вычислительные трудности простого перебора, когда у области допустимых решений очень много вершин. Метод направленного перебора вершин для решения Задачи Линейного Программирования является фундаментом универсального метода решения ЗЛП, известного, как Симплексметод. Пример 1.[4] Рассмотрим систему ограничений конкретной Задачи Линейного Программирования в канонической форме.  x1  2 x3  5 x 4  7  x2  3x3  4 x4  15   x  0, j  1, ...,4  j Система имеет два уравнения (m=2) и четыре неизвестных (n=4). Можно ввести векторную запись этой системы: x1 A1  x2 A2  x3 A3  x4 A4  B , где  1   2  0  5 7 A1    , A2    , A3    , A4    , B    . Векторы A1 , A2 , A3 , A4  0  3  1  4 15 - векторы условий. Система линейных уравнений имеет бесконечное множество решений, так как m  n . Ранг матрицы системы 193 r  min2;4=2. Если выбрать базисный минор: 1 0  0 , то тогда x1, x2 0 1 базисные переменные, а x3 , x4 - свободные переменные. Векторы условий, соответствующие базисным переменным – линейно независимы. Приведем несколько примеров частных решений данной системы линейных уравнений: x 1  4,8,1,1 , x 2  9,12,1,0, x 3  7,15,0,0. Последний пример, - это базисное решение (относительно данного базисного минора), так как обе свободные переменные равны нулю. В данном случае базисное решение является и опорным, так как базисные переменные неотрицательны. В общем случае, когда матрица системы линейных уравнений с n переменными имеет ранг r, базисное решение имеет не больше r ненулевых координат. В дополнение к Определению 3 Лекции 19, дадим другой вариант определения опорного решения ЗЛП. Определение 1. Опорным решением задачи линейного программирования с n переменными называется такое допустимое решение    0 0 0  x   x1 , x2 ...x r ,0,0, ... ,0  , для которого векторы условий,    n   соответствующие положительным координатам ( x10  A1 , x20  A2 ,…, x r0  Ar ), - линейно независимы, так как соответствуют базисному минору. Если в опорном решении x число отличных от нуля координат равно r, то оно называется невырожденным (если число отличных от нуля координат меньше r, то опорное решение будет называться вырожденным). Как уже отмечалось, всякая вершина области допустимых решений ЗЛП совпадает с одним из опорных решений. Симплекс - метод, или метод направленного перебора опорных решений, метод последовательного улучшения решения, - универсален: он позволяет за конечное число шагов найти оптимальное решение, если оно существует. 194 Алгоритм Симплекс - метода: 1. Определить какое-либо первоначальное допустимое решение задачи линейного программирования. 2. Найти условие перехода к следующему решению, которое не хуже предыдущего. 3. Проверить полученное решение с помощью критерия оптимальности. Если условия критерия оптимальности выполнены, найденное решение оптимально. Пусть дана Задача Линейного Программирования (ЗЛП) с n переменными x1, x2 , ..., xn и m ограничениями в стандартной форме (см. Лекцию 19): f x   c1x1  c2 x2  ...  cn xn  max a11 x1  a12 x2  ...  a1n xn  b1 a x  a x  ...  a x  b c , x   max 2n n 2  21 1 22 2 1) ... или коротко: (2) Ax  b , где a x  a x  ...  a x  b x0 mn n m  m1 1 m 2 2  x1  0, x2  0, ... , xn  0  a11 a12   a 21 a 22 n A  aij m , или подробно A   ... ...   a m1 a m 2   ... a1n   ... a 2n  ... ...   ... a mn  Осуществим переход от задачи линейного программирования в стандартной форме (1) к каноническому виду путем добавления новых m переменных xn 1, xn  2 , ..., xn  m : F x   c1x1  c2 x2  ...  cn xn  max a11 x1  a12 x 2  ...a1n x n  x n 1  b1   b2 a 21 x1  a 22 x 2  ...a 2n x n  x n  2  . ... a x  a x  ...a x  x n  m  bm m2 2 mn n  m1 1  x j  0, j  1, ..., n  m 195 Здесь матрица системы линейных уравнений:  a11 a12  ~ ~ n  m  a 21 a 22 A  aij  m ... ...   a m1 a m2   ... a1n ... a 2n ... ... ... a mn 1 ... 1 ... ... ... ... ... 0  0 . ...  1  Поскольку r  minm, n  m , - r A  m , так как естественно взять за базисный минор последние m столбцов матрицы. Мы получим единичную матрицу m-го порядка. Следовательно xn 1,  , xn  m – базисные переменные, а x1, ..., xn – свободные переменные. Базисные переменные выразим через свободные: ~ n   x n 1  b1   a1 j x j  j 1  n  x  b  2  a2 j x j  n2 j 1   ...  n x  bm   a mj x j  nm j 1   x1 , ... , x n  m  0    1.Таким образом, на первом этапе дополнительные переменные являются базисными, а основные переменные – свободными. Возьмем все свободные переменные равными нулю.    X I  0 ,0...0, b , b ...b  – первое опорное решение (в задаче на   1 2 m   n  b  0 , базисное решение всегда будет максимум, при условии опорным решением, то есть X I  ODP ). FI  F X I   0 – значение целевой функции для первого опорного решения. 196 2. Первое опорное решение, когда FI  0 , явно может быть улучшено. В п.2 попадаем, так же, если проверка опорного решения предыдущего этапа на критерий оптимальности показала, что оптимальное решение пока не найдено. На данном этапе прежде всего находим наибольший положительный коэффициент целевой функции, выраженной через свободные переменные: c 0j  max c j , j  1, ... , n . Переменную xi0 сделаем базисной переменной, - так быстрее будет осуществляться рост целевой функции. Понятно, что какая-то базисная переменная предыдущего этапа должна перейти в свободные переменные текущего этапа. Очевидно, что все базисные переменные предыдущего этапа неотрицательны. Поскольку базисные переменные выражаются через свободные и, в частности, через xi0 , из условий неотрицательности находятся возможные границы изменения переменной xi0 . Та базисная переменная, которая раньше всех остальных при росте xi0 обращается в нуль, и будет переведена из базисных переменных в свободные. Из выражения для старой базисной переменной и будет получено выражение для новой базисной переменной xi0 . Далее находятся выражения для всех остальных базисных переменных текущего этапа через свободные переменные этого этапа. Принимая все свободные переменные равными нулю находим вначале второе опорное решение X II и FII  F X II  – значение целевой функции для второго опорного решения, затем, аналогично, все последующие. Процесс нахождения очередного опорного решения продолжается до тех пор, пока не будет выполнен критерий оптимальности. 3. Проверка критерия оптимальности состоит в следующем: а) целевая функция выражается через свободные переменные в) если все коэффициенты целевой функции в задаче на максимум отрицательны (все коэффициенты целевой функции в задаче на минимум положительны) то оптимальное решение найдено. Если критерий оптимальности не выполнен, то возвращаемся к п.2 , меняем одну из базисных переменных и ищем очередное опорное решение. 197 Пример 2. Пусть дана Задача Линейного Программирования (ЗЛП) с двумя переменными x1, x2 и тремя ограничениями в стандартной форме. Рис.22.3 Вначале решим задачу Графическим методом: F  2 x1  4 x2  max  x1  x 2  5  x  x  3  1 2  2 x1  x 2  8  x1  0, x 2  0  1 1   A    1 1  2 1   Построим ОДР: l1 : A0,5, B5,0 l2 : С 0,3, D 3,0 l3 : K 0,8, L4,0 Поскольку вектор-градиент c  2,4  2 1, 2 , оптимальное решение ЗЛП будет достигаться в т. M 1,4. F *  2 1  4  4  18 x *  x1* , x2*  1,4 .   198 Для решения этой же задачи Симплекс–методом перейдем к каноническому виду ЗЛП. I. F  2 x1  4 x2  max    1 1 ~  A  1 1   2 1   5  x1  x2  x3  x  x  x4 3  1 2   x5  8  2 x1  x2  x1 , ... , x5  0   1 0 0 0 1 0  0 0 1        ~ r A  3 , так как 3 последних столбца составляют базисный минор. Следовательно x3 , x 4 , x5 – базисные переменные; x1 , x 2 – свободные переменные. Выразим базисные переменные через свободные:  x3  5  x1  x2  0   x4  3  x1  x2  0 x  8  2x  x  0 1 2  5 Возьмем все свободные переменные равными нулю. Получим первое опорное решение: X I  0, 0, 5, 3, 8. Целевая функция выражена через свободные переменные: F  2 x1  4 x2 . Таким образом F X I   0 . II. Целевая функция F  2 x1  4 x2 выражена через свободные переменные. Максимальный коэффициент равен 4, таким образом, имеет смысл переменную x2 перевести в базисные. Из условий неотрицательности всех базисных переменных п. I. находятся три возможные границы изменения переменной x2 , x1 . Когда свободная переменная x1  0 получаем три неравенства:  x2  5   x 2  3 . Легко видеть, что раньше всего условие неотрицательности x  8  2 нарушается во втором неравенстве, для переменной x4 , так как min5,3,8  3 . Таким образом, x 4 нужно перевести в свободные переменные. Итак x3 , x2 , x5 – новые базисные переменные. Выпишем выражения свободные: для всех базисных переменных через 199  x2  3  x1  x4  0   x3  5  x1  3  x1  x4   2  2 x1  x4  0  x  8  2 x  3  x  x   5  3x  x  0  5 1 1 4 1 4 Целевая функция переменные: должна быть выражена через свободные F  2 x1  43  x1  x4   12  6 x1  4 x4 Возьмем все свободные переменные равными нулю, получим второе опорное решение: X II  0, 3, 2, 0, 5 . FII  F X II   12 . Критерий оптимальности не выполнен, так как есть положительный коэффициент в новом выражении целевой функции. Нужно опять менять одну из базисных переменных и искать очередное опорное решение. III. Очевидно, что нужно сделать x1 – базисной переменной. Из условий неотрицательности всех базисных переменных п. II. находятся три возможные границы изменения переменной x1 . При x4  0 получаем   x1  3  три неравенства:  x1  1 . Легко видеть, что раньше всего условие  5  x1   3 неотрицательности нарушается во втором неравенстве, для 5 переменной x3 , так как min , 1,   1 . Таким образом, x3 нужно 3   перевести в свободные переменные. Окончательно получаем: x4 , x3 – свободные переменные, x1 , x2 , x5 –базисные переменные. Выпишем выражения для всех базисных переменных через свободные:  2  x3  x 4 x x  1 3  4  x1  2 2 2  x3 x 4 x x    x4  4  3  4  x2  3  1  2 2 2 2   3 1  x3 x 4   x5  5  31  2  2   x4  2  2 x3  2 x4    Целевая функция переменные: должна быть выражена через свободные 200 x   x F  12  61  3  4   4 x4  12  6  3x1  x4  18  3x1  x4 2 2   Возьмем все свободные переменные равными нулю, получим третье опорное решение: X III  1, 4, 0, 0, 2 . FIII  F X III   18 . Критерий оптимальности выполнен, так как все коэффициенты целевой функции в задаче на максимум отрицательны. Это означает, что F *  18 , x *  x1* , x2*  1,4 .   Видим, что оптимальное решение Задачи Линейного Программирования, найденное Симплекс – методом совпадает с оптимальным решением задачи, найденным графическим методом. Алгоритм Симплекс – метода достаточно прост при решении задач на максимум для случаев, когда область допустимых решений содержит нулевую точку. Заметим, что, есть особенности получения первоначального допустимого решения задачи линейного программирования для случая, когда область допустимых решений не содержит т.О(0,0), а также при решении задач на минимум. В любом случае, на этапе поиска первого опорного решения (п. 1.) возможен просто перебор базисных миноров. Если ненулевые компоненты базисного решения, соответствующего определенному базисному минору, положительны, то это базисное решение может быть выбрано в качестве первого опорного решения ЗЛП. 201 ЛЕКЦИЯ 23. ДВОЙСТВЕННАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. Построение двойственной задачи Линейного программирования. Существование оптимальных решений взаимодвойственных задач. Связь основных и дополнительных переменных прямой и двойственной задач Линейного программирования. Теоремы Двойственности. Экономический смысл Теории Двойственности. Любой задаче линейного программирования, назовем ее исходной, прямой, можно поставить в соответствие другую задачу, которая называется двойственной, сопряженной. Обе эти задачи образуют пару взаимодвойственных задач линейного программирования, каждая из которых является двойственной к другой задаче. Вспомним – стандартную задачу линейного программирования: F x   c1x1  c2 x2  ...  cn xn  max a11 x1  a12 x2  ...  a1n xn  b1 a x  a x  ...  a x  b 2n n 2  21 1 22 2 (1) ... , где a x  a x  ...  a x  b mn n m  m1 1 m 2 2  x1  0, x2  0, ... , xn  0  a11 a12  a 22 a A  aij nm   21 ... ...   a m1 a m2   ... a1n   x1   b1       ... a 2n   b2   x2  b  x  , ,  ...  , c  c1, c2 , ... , cn  .  ...  ... ...       ... a mn  x  bm   n c , x   max Короткая запись: (1') Ax  b . x 0 Экономический смысл этой задачи – найти оптимальный план выпуска продукции I -м производителем, обеспечивающий максимальную прибыль. Предположим, что II-й производитель хочет перекупить сырье [3,4]. Составим двойственную задачу, решение которой позволит определить приемлемые условия продажи сырья. 202  y1     y2  Введем вектор оценок (цен) видов сырья: y    . ...    ym  В данном случае под оценками (ценами) подразумеваются объективно обусловленные оценки (понятие впервые введено русским ученым Л.В.Канторовичем в 30-е годы ХХ в.), которые, в отличие от цен, задаются не извне, а определяются самим предприятием для внутреннего пользования. Очевидно, что затраты на приобретение i -го вида сырья в количестве bi - bi  yi . II-му производителю выгодно минимизировать суммарные затраты на приобретение всех видов сырья, таким образом, целевая функция в Двойственной задаче имеет вид: Z  y   b1 y1  b2 y2  ...  bm ym  min . I-му производителю, в свою очередь, не выгодно продавать сырье, если суммарная стоимость всех видов сырья, расходуемое на каждое изделие j -го вида продукции, то есть a1 j y1  a2 j y2  ...  amj ym была меньше величины c j , получаемой от реализации изделия j -го вида. Аналогично получим общую систему специальных ограничений задачи и очевидных общих ограничений. Объединяя систему ограничений с целевой функцией получим Двойственную задачу, соответствующую прямой ЗЛП (1) : Z  y   b1 y1  b2 y2  ...  bm ym  min a11 y1  a 21 y 2  ...  a m1 y m  c1 a y  a y  ...  a y  c m2 m 2  12 1 22 2 (2) ... Короткая запись:(2') a y  a y  ...  a y  c mn m n  1n 1 2n 2  y1  0, y 2  0, ... , y m  0 b , y   min AT y  c , y0 где  y1     y2  y , ...    y  m  a11  a AT   12 ...   a1n a 21 a 22 ... a 2n ... a m1   b1     ... a m 2   b2  b    , , c  c , c , ... , c 1 2 n  ...  . ... ...     ... a mn   bm  Легко видеть, что и в прямой, и в двойственной задаче ищется экстремум целевой функции. При этом, если в прямой задаче 203 линейного программирования мы ищем максимум, то в соответствующей двойственной задаче – минимум. В обеих задачах переменные должны удовлетворять системе специальных и общих ограничений задачи. Коэффициенты c j , j  1,..., n целевой функции прямой задачи являются свободными членами системы ограничений двойственной задачи. И наоборот, свободные члены системы ограничений прямой задачи bi , i  1,..., m являются коэффициентами целевой функции двойственной задачи. Матрица коэффициентов системы ограничений двойственной задачи является транспонированной матрицей коэффициентов системы ограничений исходной задачи. Заметим, что отмеченные правила построения справедливы, если в прямой задаче на максимум все специальные ограничения приведены к одному знаку «  ». В двойственной задаче на минимум все специальные ограничения так же должны иметь один знак, - «  ». Пример 1. Построим двойственную задачу линейного программирования по заданной прямой ЗЛП: F x   2 x1  x2  max  x1  x 2  5 1  1 x  x  2   1 2   1 1   A  3x1  x 2  6  , тогда 3  1   2 x  x  2   1 2   2  1    x1  0, x 2  0 1  1 3  2  AT    . 1 1  1  1   Соответствующая двойственная задача будет иметь вид: Z  y   5 y1  2 y2  6 y3  2 y4  min  y1  y 2  3 y3  2 y 4  2   y1  y 2  y3  y 4  1  y  0, y  0, y  0, y  0.  1 2 3 4 Сформулируем еще раз все Правила формирования задачи линейного программирования, двойственной к исходной задаче: 1. Число переменных в двойственной задаче равно количеству специальных ограничений прямой задачи. 204 2. Если в прямой задаче ищется максимум, то в двойственной задаче ищется минимум (и наоборот). 3. В задаче на максимум все специальные ограничения должны иметь один знак: «  », а в задаче на минимум все специальные ограничения должны иметь один знак: - «  ». 4. Компоненты вектора специальных ограничений b в прямой задаче становятся коэффициентами целевой функции в двойственной задаче. 5. Матрица коэффициентов при переменных в системе специальных ограничений в двойственной задаче получается путем транспонирования соответствующей матрицы исходной задачи. 6. Знак неравенства специальных ограничений в прямой задаче меняется на противоположный в двойственной задаче. 7. Коэффициенты целевой функции в прямой задаче становятся компонентами вектора ограничений c в двойственной задаче. Основные теоремы двойственности: Основное неравенство.  x1   y1      x y Для любых допустимых решений x   2  и y   2  , - соответственно ... ...     x y  n  m решений прямой (1) и двойственной (2) программирования, справедливо неравенство: F x   Z  y  – основное неравенство. Возможны другие записи: c , x   b , y  или n задач c j x j  j 1 линейного m  bi y j . i 1 Приведем без доказательства формулировки некоторых Теорем теории двойственности. Теорема. (Достаточный признак оптимальности) * T – допустимые решения Если x *  x1* , x2* , ..., xn* T и y *  y1* , y2* , ..., ym взаимодвойственных задач (1) и (2), для которых выполняется равенство: F x *  Z y * , то x * – оптимальное решение прямой         задачи (1), а y * – оптимальное решение двойственной задачи (2). Теорема 1. Первая (основная) теорема двойственности 205 Либо взаимодвойственные задачи линейного программирования одновременно имеют оптимальные решения и тогда F x *  Z y * , либо ни одна из них не имеет решения.     Замечание 1: Если линейная функция одной из задач не ограничена (не достигает оптимального решения), то условия двойственной задачи противоречивы (нет множества допустимых значений). Замечание 2: утверждение, обратное замечанию 1, в общем случае не верно. Пример 2. [3] Прямая задача: F  5x1  9 x2  max  2 x1  3x 2  12   2 x1  x 2  4  x  0, x  0  1 2 3  2 A     2  1 Рис. 23.1 Двойственная задача:  Z  12 y1  4 y2  min  2 y1  2 y 2  5   3 y1  y 2  9  y  0, y  0  1 2   2 2  AT    3  1 206 Рис. 23.2 Существует оптимальное решение прямой и двойственной задач:   y *  y1*  5,75, y2*  8,25, Z *  12  5.75  4  8.25  102 x *  x1*  6, x2*  8 , F *  5  6  9  8  102 Пример 3. [3] Иллюстрация Замечания 1 Прямая задача: Двойственная задача: F  3x1  5x2  max 2 x1  3x 2  6   2 x1  x 2  4  x  0, x  0  1 2 Z  6 y1  4 y2  min 2 y1  2 y 2  3   3 y1  y 2  5  y  0, y  0  1 2  2  3 A    1  2   2  2 AT    1  3 207 Рис. 23.3 Рис. 23.4 Легко видеть, что не существует оптимального решения прямой задачи и условия двойственной задачи противоречивы (нет множества допустимых значений). 208 Экономический смысл Теоремы 1 состоит в том, что предприятие имеет два равновыгодных для него варианта: а)производство продукции в соответствии с оптимальным планом и получение максимально возможной выручки за произведенную продукцию; б) предприятие может получить ту же самую сумму средств за счет продажи имеющихся у предприятия ресурсов. Запишем прямую задачу линейного программирования (1) в каноническом виде: F x   c1x1  c2 x2  ...  cn xn  max a11 x1  a12 x2  ...  a1n xn  xn 1  b1 a x  a x  ...  a x  0  x 22 2 2n n n 1  xn  2  b2  21 1 (3) ... a x  a x  ...  a x  0  x m2 2 mn n n 1  ...  xn  m  bm  m1 1  x1  0, x2  0, ..., xn  0, xn 1  0, xn  2  0, ..., xn  m  0 n переменных  n+m Запишем двойственную задачу линейного программирования (2) в каноническом виде: Z  y   b1 y1  b2 y2  ...  bm ym  min  c1 a11 y1  a 21 y 2  ...  a m1 y m  y n 1 a y  a y  ...  a y  yn  2  c2 m2 m  12 1 22 2 (4) ... a y  a y  ...  a y  y m  n  cn mn m  1n 1 2n 2  y1  0, y 2  0, ..., y m  0, y m 1  0, y m  2  0, ..., y m  n  0 m переменных  m+n Выпишем Таблицу соответствия основных и дополнительных переменных (они здесь и далее отделены двойной чертой) прямой и двойственной задач (3) и (4): Прямая ... ... x xn 1 xn x1 nm задача Двойственн ая задача y m 1 ... ym  n y1 ... ym 209 Теорема 2. Вторая теорема двойственности: Пусть есть пара взаимодвойственных задач (1) и (2). Для того, чтобы,  x1   y1       x2   y2  допустимые решения x    и y    являлись оптимальными ... ...      xn   ym  решениями пары двойственных задач, Необходимо и Достаточно следующее:   n  1)  yi bi   aij x j   0   i 1  j 1  m    x c  a y  j  j  ij j   0 . j 1  i 1  n m 2) Теорему 2 можно сформулировать короче, используя Таблицу соответствия переменных прямой и двойственной задач (3) и (4). Заметим, что условию 1) для оптимального решения эквивалентна m более короткая запись:  yi xn i  0 ; условию 2) эквивалентна запись: i 1 n  x j ym  j  0 . Поскольку все переменные взаимодвойственных задач j 1 неотрицательны, каждое слагаемое из первой и второй суммы должно быть равно нулю, то есть каждое попарное произведение должно быть равно нулю. Теорема 2. (другая формулировка) Положительным компонентам переменных оптимального решения одной из взаимодвойственных задач соответствуют нулевые компоненты оптимального решения другой задачи. Может быть, самое простое - записать Таблицу соответствия основных и дополнительных переменных прямой и двойственной задач для оптимального решения: Прямая ... ... x * x1* xn* xn* 1 nm задача Двойственн ая задача * ym 1 ... * ym n y1* ... * ym 210 Утверждение Теоремы 2 состоит в том, что произведение элементов в каждом столбце таблицы равно нулю. Более традиционно символически это можно записать так: 1) если xn* i  0 , то yi*  0 , i  1,  , m * 2) если x*j  0 , то ym  j  0 , j  1,  , n . Первое условие можно пояснить подробнее: Если при подстановке оптимального решения в систему ограничений i -е ограничение исходной задачи (1) выполняется как строгое неравенство, то i –я компонента оптимального решения двойственной задачи равна нулю. И наоборот, - если i–я компонента оптимального решения двойственной задачи отлична от нуля, то i-е ограничение исходной задачи (1) удовлетворяется оптимальным решением как равенство. Для пояснения второго условия, аналогично можно связать j –ю компоненту оптимального решения исходной задачи (1) и j –е ограничение двойственной задачи (2). Экономический смысл Теоремы 2 состоит в том, что объективно обусловленные оценки определяют степень дефицитности ресурсов. Дефицитными оказываются те ресурсы, которые в соответствии с оптимальным планом производства используются полностью и тогда имеют ненулевые объективно обусловленные оценки, а недефицитные – нулевые оценки. Также очевидно, что в оптимальный план производства могут попасть только те виды продукции, рыночные цены которых в точности равны затратам на используемые при их производстве ресурсы. Если рыночные цены меньше всех затрат на производство, то такая продукция не должна производиться. Пример 3. Убедимся, на Примере 3, что утверждение Теоремы 2 справедливо. Составим Таблицу соответствия основных и дополнительных переменных прямой и двойственной задач для оптимального решения. 211 Прямая задача: F  5x1  9 x2  max  2 x1  3x2  12   2 x1  x2  4  x  0, x  0  1 2 Двойственная задача: Z  12 y1  4 y2  min  2 y1  2 y 2  5   3 y1  y 2  9  y  0, y  0  1 2  Запишем ограничения обеих задач в каноническом виде:  2 x1  3x2  x3  12   2 x1  x2  x4  4  x  0, x  0, x  0, x  0 2 3 4  1  2 y1  2 y 2  y3  5   3 y1  y 2  y 4  9  y  0, y  0, y  0, y  0 2 3 4  1   Зная оптимальное решение обеих задач: x *  x1*  6, x2*  8 , y *  y1*  5,75, y2*  8,25 , найдем дополнительные переменные. x3  12  2  6  3  8  0 , x4  4  2  6  8  0 , y3  5  2  5,75  2  8,25  0, y4  9  3  5,75  8,25  0 .   Из Таблицы соответствия переменных видно, что утверждение Теоремы 2 верно. Прямая задача Двойственн ая задача x1* x 2* x3* x 4* 6 8 5,7 5 8,25 y3* y 4* y1* y 2* Как можно использовать теорию двойственности для решения исходной (прямой) задачи линейного программирования? Если, например, в прямой задаче много переменных и всего два специальных ограничения, можно поставить ей в соответствие двойственную задачу, в которой только две переменные и много ограничений. Лучше вначале найти решение именно двойственной задачи, что легко сделать графическим методом. 212 Затем нужно записать ограничения обеих задач в каноническом виде, составить Таблицу соответствия основных и дополнительных переменных прямой и двойственной задач для оптимального решения. Из Таблицы будет следовать, что в оптимальном решении довольно много переменных прямой задачи равны нулю. В итоге в прямой задаче окажется не более двух ненулевых переменных, которые можно будет легко найти из системы специальных ограничений. В заключение заметим, что если в реальности существуют приемлемые для II-го производителя условия продажи ему сырья I-м производителем, то это значит, что он рассчитывает в процессе производства продукции получить прибыль. То, что I-му производителю выгоднее продавать сырье, а не производить продукцию, означает, что технологический процесс у I-го производителя организован очень не эффективно. 213 ЛЕКЦИЯ 24. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ. Основные понятия Динамического программирования. Пример задачи Динамического программирования: выбор оптимального пути в транспортной сети. Динамическое программирование (точнее было бы использовать термин «динамическое планирование») – это известный метод нахождения оптимального решения задачи, которую можно считать «многоэтапной», или «многошаговой» операцией. Динамическое программирование – математический аппарат, позволяющий оптимизировать решение в случае, когда изучаемая ситуация не содержит факторов неопределенности, но наилучшее решение надо выбрать из множества возможных. При этом планирование каждого шага должно производиться с учетом конечной выгоды, получаемой только при окончании всего анализируемого процесса. Выигрыш за всю операцию складывается из выигрыша на отдельных шагах. Динамическое программирование применяется в задачах, которые можно рассматривать, как операции, распадающиеся на m шагов, например, - деятельность промышленного предприятия в течение ряда лет; - составление календарных планов ремонта и замены оборудования; - распределение на несколько лет вперед дефицитных ресурсов между новыми направлениями их использования; - поиск кратчайшего маршрута в транспортной сети и т.д. Пусть операция Q состоит из m шагов. Эффективность всей W , а показатели операции характеризуется «выигрышем» эффективности на отдельных шагах - wi , i  1,...,m . Если выполнено W  критерий. m  wi , тогда говорят, что i 1 W- аддитивный 214 Определение 1. Динамическое программирование – это метод оптимизации многошаговых или поэтапных процессов, критерий эффективности которых обладает свойством аддитивности. Определение 2. Пусть операция Q - управляемый процесс. xi - параметр, влияющий на ход операции, называют шаговым управлением. x  x1, x2 ,  , xm  - вектор шаговых управлений. Заметим, что компоненты вектора x могут являться числами, векторами, функциями и т.д. Множество векторов x составляет множество возможных управлений X . Определение 3.   * - это значение управления Оптимальное управление x *  x1* , x2* , ..., xm W является максимальным: x , при котором выигрыш * * W  W ( x )  max W x . x X Процесс динамического программирования обычно разворачивается от конца к началу и этот этап называется условная оптимизация. Затем, от начала к концу идет процесс безусловной оптимизации, когда используются рекомендации этапа условной оптимизации и *. находятся оптимальные шаговые управления x1* , x2* , ..., xm Для постановки задачи Динамического программирования в общем случае нужно: 1) определить множество Si возможных состояний системы s перед каждым i -м шагом: s  Si , i  1,  , m ; 2) определить для каждого i -го шага набор возможных шаговых управлений X i , xi  X i . (Смотрите, в качестве примера возможных шаговых управлений пункт I. 2) Примера 1.); 3) определить, какой выигрыш на i –м шаге приносит управление xi , если система перед этим находилась в состоянии s: wi  i s, xi  . То есть нужно определить функции  i ; 215 4) определить, как изменится состояние системы s на i –м шаге при применении шагового управления xi : s  f i s, xi  . То есть нужно определить функции f i ; 5) определить основное рекуррентное соотношение ( функция Беллмана): (*)     Wi s   max i s , xi  Wi 1 fi s, xi  Xi – оно выражает условный оптимальный выигрыш для данного состояния системы s с i –го шага и до конца процесса через уже известный условный оптимальный выигрыш с i+1– го шага и до конца процесса. 6) составить уравнение, определяющее условный оптимальный выигрыш на последнем шаге для состояния системы s : Wm s   max m s, xm   maxwm s, xm  Xm Xm 7)составить уравнение, определяющее на основании соотношения (*) из п. 5) условный оптимальный выигрыш на предпоследнем шаге для состояния системы s Wm 1 s   max  m 1 s, xm 1   Wm  f m 1 s, xm 1  X m 1 Пусть sˆ  f m 1 s, xm 1  , - подставляя в известную функцию Wm s  значение ŝ получим функцию Wm1s  . Дойдя таким образом до 1-го шага, определим функцию W1 s  . Таким образом, получаем набор «рекомендаций» на каждом шаге, в зависимости от состояния системы s. 8)Поскольку состояние s1 перед 1-м шагом известно, найдем из формулы (*) п. 5) для i  1 оптимальное управление на 1-м шаге : x1*  x1 ( s1 ) и оптимальный выигрыш W1 s1  .   Это и есть оптимальный выигрыш всей задачи W *  W x1* . Более подробно:       W x1*  W *  W1s1   max1s1, x1   W2  f1s1, x1   1 s1, x1*  W2 f1 s1, x1* X1 На этом этапе условная оптимизация закончена. 216 9) Для проведения безусловной оптимизации управления, необходимо на каждом шаге «читать» соответствующие рекомендации. Найденное на 1-м шаге оптимальное управление x1*  x1 ( s1 ) использовать для нахождения состояния системы перед 2-м шагом: s2  f1 s1, x1* . Для измененного состояния системы найдем оптимальное управление на 2-м шаге x2*  x2 ( s2 ) :        W2 s2   max 2 s2 , x2   W3  f 2 s2 , x2    2 s2 , x2*  W3 f 2 s2 , x2* . X2   Зная x2*  x2 ( s2 ) , найдем s3  f 2 s2 , x2* . Далее, аналогично, найдем всю цепочку оптимальных шаговых *. управлений: x3* , . . . , xm Таким образом, мы нашли оптимальное решение задачи:     * и W x *  W *. x *  x1* , x2* , ..., xm 1 Пример 1. [5] Выбор кратчайшего маршрута в транспортной сети. Пусть в транспортной сети n = 10 узлов (городов). Возможное направление проезда и время – указаны на рисунке. Найти оптимальный маршрут проезда из 1-го города в 10 -й. Найти минимальное время проезда. Рис.24.1 Конфигурация данной транспортной сети позволяет разбить ее на пояса. 217 Считаем, что номера городов k -го пояса – это возможные состояния системы S перед k-м шагом. Движение организовано только слева направо. Постановим задачу Динамического программирования: Разобьем ее на пояса и определим шагом: I пояс, k  1 S  1 – S  2,3,4 – II пояс, k  2 S  5,6 – III пояс, k  3 S  7,8,9 – IV пояс, k  4 S  10  – V пояс, k  5 состояния системы перед k-м Если J  - возможные города k+1–го пояса (то есть состояния системы перед k+1 -м шагом), то определим через t SJ - время проезда из города S ( k-го пояса) до города J (k+1-го пояса). Набор возможных шаговых управлений для каждого k -го шага состоит в выборе номера города J ( k  1 –го пояса), куда возможен переезд из города S ( k-го пояса) с конкретным номером. Тогда основное рекуррентное соотношение будет иметь вид: Wk S   mint SJ  Wk 1 J  J I. Сначала будем проводить этап условной оптимизации процесса. Набор возможных шаговых управлений на i –м шаге xi и выигрыш, который приносит на i –м шаге управление xi представим в виде таблиц. 1) k  4 W4 S   min t SJ  0 J S J  10 W4 S  J* 7 8 9 9 3 11 10 10 10 9 3 11 218 2) k  3 W3 S   min t SJ  W4 J  S J J 7 J 8 J  9 W3 S  J* 5 6 7+9 8+9 7+3 4+3 – 10 5+11 7 8 8 Заметим, что набор возможных шаговых управлений для 3 - го шага состоит в выборе номеров городов 4 – го пояса, куда возможен переезд из города с конкретным номером 3-го пояса: так для S  5 , - J  7, 8 , для S  6 , - J  7, 8, 9 . 3) k  2 W2 S   mint SJ  W3 J  J J  6 W2 S  S J 5 2 3 4 6+10 – 7+10 – – 8+7 16 17 15 J* 5 5 6 4) k  1 W1 S   min t SJ  W2 J  S J J 2 1 8+16 8+17 8+15 23 W1 1  23 .   J 3 J 4 W1 S  J* 4 Это и есть оптимальный «выигрыш» всей задачи W *  W x1* . В данной задаче оптимальное управление x1* - это проезд на 1-м шаге из города 1 в город 4. I I. Безусловная оптимизация: Уже найдено из последней таблицы минимальное время проезда из города 1 в город 10: W *  W1 1  23. 219 Так же уже определено оптимальное управление на 1-м шаге x1* : это - проезд из города 1 в город 4. Далее необходимо найти оптимальное управление на 2-м шаге x2* . Из предпоследней таблицы видно, что это - проезд из города 4 в город 6. Заметим, что x2* оптимальное управление и в данной задаче – единственное управление на 2-м шаге. Аналогично находим оптимальное управление на 3-м шаге x3* : проезд из города 6 в город 8, что легко видеть из таблицы для k  3 . Таким образом, оптимальный маршрут будет выглядеть так: 1  4  6  8  10 . Заметим, что этап условной оптимизации сложнее и длительнее этапа безусловной оптимизации, который почти не требует дополнительных вычислений. Как уже отмечалось выше, на этапе безусловной оптимизации используются рекомендации этапа условной оптимизации и находятся оптимальные шаговые управления. 220 СПИСОК ЛИТЕРАТУРЫ Учебники и учебные пособия 1. Идельсон А.В., Блюмкина И.А. Аналитическая геометрия. Линейная алгебра. Математика для экономистов. Том 1. Учебное пособие. - М.: ИНФРА-М, 2000 – 153 с. 2. Шикин Е.В., Чхартишвили А.Г. Математические методы и модели в управлении. Учебное пособие. Серия: Классический университетский учебник. - М.: Дело, 2004 – 440 с. 3. Лепе Н.Л., Манаенкова Н. И. Лекции по линейной алгебре : учебное пособие; Федер. гос. бюджетное образоват. учреждение высш. проф. образования "Рос. гос. гуманитарный ун-т" (РГГУ). - Москва: Тровант, 2016. - 247 с. 4. Пинегина М.В. Математические методы и модели в экономике. Учебное пособие. - М.: Экзамен, 2004 - 128 с. 5. Невежин В.П., Кружилов С.И. Сборник задач по курсу «Экономико-математическое моделирование». – М.: ОАО «Издательский Дом «Городец», 2005. - 320 c. 6. Манаенкова Н.И. Линейная алгебра. Учебно-методический комплекс. Учебное издание. М.: РГГУ, 2012 г. 40 с. 7. Манаенкова Н.И. Аналитическая геометрия. Учебно-методический комплекс. Учебное издание. М.: РГГУ, 2012 г. 34 с. Адреса ресурсов Интернет 8. Аналитическая геометрия [Электронный ресурс] : учеб.-метод. комплекс : для бакалавриата по направлению 080200 Менеджмент / М-во образования и науки Рос. Федерации, Федер. гос. бюджет. образоват. учреждение высш. проф. образования "Рос. гос. гуманитарный ун-т", Ин-т экономики, упр. и права, Фак. упр., Каф. моделирования в экономике и упр. ; [сост. Н. И. Манаенкова ; отв. ред. Н. Л. Лепе]. - М. : РГГУ, 2012. - 34 с. ; 20 см. - Режим доступа : http://elib.lib.rsuh.ru/elib/000005265. - Загл. с экрана. Библиогр.: с. 20-21. 221 9. Линейная алгебра [Электронный ресурс] : учеб.-метод. комплекс : для бакалавриата по направлению 080200 - Менеджмент / М-во образования и науки Рос. Федерации, Федер. гос. бюджет. образоват. учреждение высш. проф. образования "Рос. гос. гуманитарный ун-т", Ин-т экономики, упр. и права, Фак. упр., Каф. моделирования в экономике и упр. ; [сост. Н. И. Манаенкова ; отв. ред. Н. Л. Лепе]. - М. : РГГУ, 2012. - 40 с. ; 20 см. - Режим доступа : http://elib.lib.rsuh.ru/elib/000005266.pdf. - Загл. с экрана. - Библиогр.: с. 21-22. 10. Лекции по линейной алгебре [Электронный ресурс] : учебное пособие для бакалавриата по направлению № 080200 – Менеджмент, № 080400 – Управление персоналом / Минобрнауки России, Федер. гос. бюджетное образоват. учреждение высш. проф. образования "Рос. гос. гуманитарный ун-т" (РГГУ), Ин-т экономики, упр. и права, Фак. упр., Каф. моделирования в экономике и упр., [сост.: Н. Л. Лепе, Н. И. Манаенкова ; отв. ред. В. В. Кульба]. - Москва : РГГУ, 2014. - 202 с. - Режим доступа: http://elib.lib.rsuh.ru/elib/000009509. - Загл. с экрана. - ISBN 978-57281-1699-8. Справочные и информационные издания 11. Воеводин В.В., Воеводин Вл.В. Энциклопедия линейной алгебры. Электронная система ЛИНЕАЛ – СПб.: БХВ-Петербург, 2006. – 544 с.