Алгоритмы и вычислительные методы оптимизации

М.Ю. Галкина Лекции по курсу «Алгоритмы и вычислительные методы оптимизации» Оглавление 1. Линейное программирование ........................................................................... 3 1.1. Пример задачи линейного программирования (задача использования сырья) ............................................................................................................................ 3 1.2. Векторы и матрицы............................................................................................ 3 1.3. Метод Жордана-Гаусса ..................................................................................... 7 1.4. Базисные и опорные решения систем линейных алгебраических уравнений ..................................................................................................................... 9 1.5. Генерирование сочетаний без повторений из n по k .................................... 14 1.6. Различные формы записи задачи линейного программирования. Переход от одной формы записи к другой ............................................................................. 16 1.7. Геометрическая интерпретация задачи линейного программирования .... 19 1.8. Графический способ метод решения ЗЛП, заданной в симметричной форме, в случае двух переменных ........................................................................... 23 1.9. Многомерные ЗЛП, заданные в канонической форме, решаемые графически ................................................................................................................. 29 1.10. Симплекс-метод ............................................................................................... 32 1.11. Вырожденные решения и правило устранения зацикливания .................... 43 1.12. Метод искусственного базиса (М-метод) ...................................................... 46 1.13. Двойственные задачи....................................................................................... 51 1.14. Двойственный симплекс-метод ...................................................................... 62 2. Специальные задачи линейного программирования ................................... 64 2.1. Целочисленные задачи линейного программирования. Метод Гомори .... 64 2.2. Транспортная задача ........................................................................................ 72 2.3. Задачи теории игр ............................................................................................ 84 3. Нелинейное программирование ................................................................... 103 3.1. Графическое решение задачи нелинейного программирования ............... 103 3.2. Метод множителей Лагранжа ....................................................................... 106 3.3. Решение задач выпуклого программирования ........................................... 106 3.4. Градиентные методы ..................................................................................... 113 4. Многоцелевые задачи .................................................................................... 119 4.1. Множество Парето ......................................................................................... 120 4.2. Метод идеальной точки ................................................................................. 121 2 1. Линейное программирование 1.1. Пример задачи линейного программирования (задача использования сырья) Пусть на мебельной фабрике могут выпускать стулья и кресла. Сведения о ресурсах, расходе материалов и прибыли от реализации каждого изделия приведены в таблице. Ресурсы Запасы Пиломатериалы (м3) Ткань (м2) Рабочее время (ч) Прибыль от ед. продукции (у.е.) 10 2000 1000 Расход на единицу продукции стул кресло 0.01 0.03 0.5 2 2 5 10 35 Найти план производства продукции максимизирующий прибыль предприятия. Для решения такой задачи строится математическая модель. Для этого выбирают переменные. Пусть x1 – количество выпущенных стульев, x2 – количество выпущенных кресел. Выпустив такое количество продукции, предприятие затратит ресурсы: пиломатериалов – 0.01x1 + 0.03x2 м3, ткани – 0.5x1 + 2 x2 м2, рабочего времени – 2 x1 + 5x2 ч. При этом, выпуск продукции ограничен имеющимися ресурсами. Получаем систему: 0.01x1 + 0.03x2  10 0.5 x1 + 2 x2  2000 . (1.1) 2 x + 5 x  1000 1 2 x , x  0  1 2 Полученная прибыль составит Z = 10 x1 + 35x2 . Ее надо максимизировать. (1.2) Z = 10x1 + 35x2 → max . (1.1), (1.2) образуют математическую модель задачи, (1.1) – система ограничений, (1.2) – целевая функция. Если система ограничений и целевая функция линейны, то построенная модель называется задачей линейного программирования. 1.2. Векторы и матрицы Упорядоченный набор n вещественных чисел x1, x2 , , xn будем называть nмерным вектором и обозначать x . Числа x1, x2 , , xn называются координатами вектора. Вектор, все компоненты которого равны 0, называется нулевым вектором: 0 = (0,0, ,0) . Два n-мерных вектора x = ( x1, x2 , , xn ) и y = ( y1, y2 , , yn ) равны, если их соответствующие координаты равны, т.е. если xi=yi для i = 1, 2, …, n. Определим над векторами две операции: 1. Умножение вектора x = ( x1, x2 , , xn ) на действительное число  3  x = ( x1, x2 , , xn ) . , xn ) и y = ( y1, y2 , , yn ) x + y = ( x1 + y1, x2 + y2 , , xn + yn ) . Множество всех n-мерных векторов c определенными над ними операциями сложения и умножения на скаляр, называется n-мерным векторным пространством и обозначается Rn. 2. Сложение векторов x = ( x1, x2 , Пример 1 R2={(x1,x2) | x1R, x2R} – двумерное векторное пространство (множество точек на плоскости). Линейной комбинацией векторов a1, a 2 , , a s называется вектор 1a1 +  2 a 2 + +  s a s , где i – скаляр (i =1, 2, …, s). Система векторов a1, a 2 , , a s называется линейно зависимой, если существуют числа 1,2 , , одновременно не равные 0, такие, что выполняется 1a1 +  2 a 2 + , s + s as = 0 . В противном случае, система векторов a1, a 2 , , a s называется линейно независимой. Для линейно независимой системы равенство 1a1 +  2 a 2 + +  s a s = 0 выполняется лишь при условии 1 = 2 = = s = 0 . Векторы, составляющие линейно независимую систему, называются линейно независимыми. Пример 2 Вектора a1=(5; 3; 2), a2=(1; 7; 3), a3=(2; 3; 2), , a4=(10; -6; 1) линейно зависимы, т.к. выполняется соотношение a1 − 3a 2 + 4a3 − a 4 = 0 . Базисом системы векторов a1, a 2 , , a s называется любая подсистема ai1 , ai2 , , air линейно независимых векторов этой системы, если любой вектор ai (i = 1, 2, …, s) из исходной системы представим в виде линейной комбинации векторов ai1 , ai2 , , air . Теорема 1 В пространстве Rn векторы e1 = (1,0, ,0) , e2 = (0,1, ,0) , …, en = (0,0, ,1) образуют базис. Доказательство: Покажем, что векторы e1, e2 , , e n – линейно независимы. Составим линейную комбинацию этих векторов и определим, при каких i (i = 1, 2, …, n) она равна 0. 1e1 +  2 e2 + +  n en = 1(1,0, ,0) +  2 (0,1, ,0) + +  n (0,0, ,1) = = (1, 2 , , n ) = 0  1 =  2 = =  n = 0 Следовательно, векторы e1, e2 , , e n - линейно независимы. 4 Возьмем любой вектор x = ( x1, x2 , x = x1e1 + x2 e2 + , xn ) из пространства Rn: + xn en = x1(1,0, ,0) + x2 (0,1, ,0) + + xn (0,0, ,1) = = ( x1, x2 , , xn ) . Следовательно, x представим в виде линейной комбинации e1, e2 , , e n . Теорема 2 Количество векторов в любом базисе одинаково. Рангом системы векторов называется число векторов в любом базисе этой системы. Прямоугольная таблица чисел, имеющая m строк и n столбцов, называется матрицей размера mn: a1n   a11 a12  a21 a22 a2n  A= . a amn   m1 am 2 Среди квадратных матриц выделяют матрицы специального вида: 0 1 0 0  - единичные матрицы размера nn. E =  0 1  0 0  1   Рангом матрицы будем называть ранг системы векторов, составленных из столбцов этой матрицы, т. е. системы a1 = (a11, a21, , am1), a 2 = (a12 , a22 , , am2 ), , a n = (a1n , a2n , , amn ) . Элементарными преобразованиями над строками матрицы будем называть следующие действия: 1. Перестановку строк. 2. Умножение всех элементов выбранной строки на число, отличное от 0. 3. Сложение соответствующих элементов двух строк. 4. Вычеркивание строк, состоящих из нулей. С помощью элементарных преобразований любую матрицу A размера mn (m  n) можно привести к виду: a1, n   0 a1, r +1 a1, r + 2 1 0  r +1 a2,  r +2  n  a2, 0 a2, (1.3) A  0 1  r , 0 0 1 ar ,r +1 ar ,r + 2 ar ,n    r где r  m и первые r столбцов могут занимать произвольные места в произвольном порядке. Очевидно, для матрицы (1.3) ранг равен r. Теорема 3 Элементарные преобразования не меняют ранга матрицы. На основании вышесказанного для определения r ранга матрицы A размера mn (m  n) с помощью элементарных преобразований будем приводить матрицу к виду (1.3), применяя следующий алгоритм (т.к. m  n, то ранг матрицы не может быть больше m). 5 1. Пусть r = m . 2. Вычеркиваем столбцы, состоящие из нулей. 3. Пусть k=1. 4. В k-ом столбце выберем элемент отличный от 0 среди элементов akk , ak +1,k , , am,k . Если такого элемента нет, то увеличиваем k на 1 и переходим к п.4. Не теряя общности, можно считать, что akk  0 (этого можно добиться перестановкой строк). Элемент akk называется разрешающим. Получаем новую матрицу, выполнив следующие преобразования: − разделим k-ю строку на разрешающий элемент akk ; − все элементы k-го столбца новой матрицы, кроме akk , равны 0; − для расчета aij – остальных элементов новой матрицы построим прямоугольники с вершинами в элементах aij и элементе akk : akk aik akj aij akj  aik и найдем новые элементы по правилу прямоугольников: aij = aij − . akk 5. Вычеркнем строки, состоящие из нулей, если такие образовалась. При вычеркивании каждой строки, r уменьшается на 1. 6. Если k меньше r, то увеличиваем k на 1 и переходим к п.4, иначе переходим к п.7. 7. Ранг исходной матрицы будет равен r – размеру выделенной единичной матрицы. Пример 3 Найти с помощью элементарных преобразований ранг матрицы  1 2 3 −4   2 −3 −2 3  .  4 1 4 −5    Решение: Ранг данной матрицы не может быть больше 3. Выполним преобразования согласно алгоритму (выделены разрешающие элементы на каждом шаге). 1 2 3 −4  Пересчет элементов новой матрицы по правилу  2 −3 −2 3 прямоугольников 4 1 4 −5   a a 22  = a22 − 12 21 = −3 − a22 = −7 a11 1 a a 3 2  = a23 − 13 21 = −2 − a23 = −8 a11 1 a a −4  2  = a24 − 14 21 = 3 − a24 = 11 a11 1 6 a a 24  = a32 − 12 31 = 1 − a32 = −7 a11 1 a a 3 4  = a33 − 13 31 = 4 − a33 = −8; a11 1 a a −4  4  = a34 − 14 31 = −5 − a23 = 11. a11 1 Новая матрица: 1 0 0  2 −7 −7 Пересчет элементов новой матрицы по правилу прямоугольников a a −8  2 5  = a13 − 23 12 = 3 − a13 = ; a22 −7 7 a a 11  2 6  = a14 − 24 12 = −4 − a14 =− ; a22 −7 7 a23  a32 −8  (−7)  = a33 − a33 = −8 − = 0; a22 −7 a a 11  (−7)  = a34 − 24 42 = 11 − a34 = 0. a22 −7 3 −4  −8 11  −8 11  Новая матрица: 1 0 0  ( 1 5 / 7 −6 / 7  8 / 7 −11 / 7  . 0  Вычеркиваем последнюю строку (она состоит из нулей). Новая матрица: 1 0 5 / 7 −6 / 7 . 0 1 8 / 7 −11 / 7 Из последней матрицы видно, что ранг матрицы A равен 2 (rang(A)=2). ) 1.3. Метод Жордана-Гаусса Рассмотрим систему из m линейных уравнений с n неизвестными: a11x1 + a12 x2 + + a1n xn = b1 a21x1 + a22 x2 + + a2n xn = b2 . (1.4)  a x + a x + + a x = b mn n m  m1 1 m 2 2 Обозначим через А матрицу системы ограничений, а через A - расширенную матрицу системы: a1n  a1n b1   a11 a12  a11 a12 a  a21 a22 a22 a2n  a2n b2  A =  21 , A= . a a amn  amn bm   m1 am 2  m1 am 2 Если ввести обозначения: 7  a11   a12   , a2 =  , a1 =  a  a   m1   m2  переписать в виде:  a1n   b1   , b =   , то систему (1.3) можно , an =  b  a   m  mn  x1a1 + x2 a 2 + + xn a n = b . (1.5) Тогда решить уравнение (1.5) – значит найти коэффициенты разложения вектора b по системе векторов a1, a 2 , , a n . Для решения системы (1.4) будем использовать метод полного исключения неизвестных или метод Жордана-Гаусса. Суть этого метода состоит в том, чтобы, выполнив элементарные преобразования над строками матрицы A , аналогично алгоритму нахождения ранга матрицы A, получить матрицу вида (1.3). Преобразования матрицы называются жордановыми исключениями. В процессе жордановых исключений возможны следующие случаи: 1. Получена строка, состоящая из нулей, кроме последнего коэффициента (правой части уравнения). В этом случае система не имеет решения. 2. Ранг матрицы А равен количеству уравнений m и числу неизвестных n (r = m = n). Тогда система имеет единственное решение. 3. Ранг матрицы А не превосходит количества уравнений m (r  m) и m < n. Тогда система имеет бесконечно много решений. Пусть имеет место третий случай и расширенная матрица системы приведена к виду (1.3): a1, n b1   0 a1, r +1 a1, r + 2 1 0  r +1 a2,  r +2  n b2   a2, 0 a2, A  0 1  r . 0 0 1 ar ,r +1 ar ,r + 2 ar ,n bn    r По преобразованной матрице составим систему:  x1 + a1, r +1xr +1 + + a1n xn = b1  x2 + a2,  r +1xr +1 + + a2 n xn = b2   x + a  xn = br r ,r +1xr +1 + + arn  r . (1.6) Система (1.6) называется приведенной к единичному базису. Переменные x1, x2 , , xr , соответствующие столбцам единичной матрицы, называются базисными, все остальные переменные xr +1, xr + 2 , , xn – свободными. Если выразить в (1.5) базисные переменные через свободные, то получим общее решение системы:  x1 = b1 − a1, r +1xr +1 − − a1n xn  x2 = b2 − a2,  r +1xr +1 − − a2 n xn . (1.7)   x = b − a  xn r ,r +1xr +1 − − arn  r r 8 Замечания: 1. При решении систем методом Жордана-Гаусса не возникает нулевых столбцов, поэтому п.2 алгоритма можно пропустить. 2. При решении систем программно может возникнуть деление на очень маленькое число (если диагональный элемент близок к нулю), поэтому используют методом Жордана-Гаусса с выбором главного элемента в столбце. Для этого в п. 3 алгоритма в качестве разрешающего выбирают максимальный по модулю элемент k-го столбца среди элементов akk , ak +1,k , , am,k и переставляют строки матрицы таким образом, чтобы он оказался на k-ой строке. Пример Решить систему методом Жордана-Гаусса с выбором главного элемента в столбце.  x1 + x2 + 2 x3 − 6 x4 = −3  x1 + x2 + x3 − 4 x4 = 0 .  x1 + x2 − 2 x4 = 3 Решение: Составим расширенную матрицу системы и выполним элементарные преобразования над ее строками.  1 1 2 −6 −3   1 1 2 −6 −3  A =  1 1 1 −4 0   0 0 −1 2 3 .   1 1 0 −2   0 0 −2 3 4 6    Во втором столбце нет отличных от 0 элементов ниже a22. Переходим к третьему столбцу. Поменяем местами вторую и третью строки, т.к. в третьем столбце max( −1 , −2 ) = 2 . 2 −6 −3   1 1 0 −2 3  1 1  0 0 −2 4 6   0 0 1 −2 −3  1 1 0 −2 3 .  0 0 1 −2 −3  0 0 −1 2  0 0 0 0 3     Ранг матрицы A равен 2, следовательно, система имеет бесконечно много решений. Из преобразованной матрицы определяем, что переменные x1, x3 – базисные, а x2 , x4 - свободные. Система, приведенная к единичному базису: x1 + x 2 −2 x4 = 3 . x3 − 2 x4 = −3 Выразим базисные переменные через свободные: x1 = 3 − x 2 +2 x4 – общее решение. x3 = −3 + 2 x4 ( )   1.4. Базисные и опорные решения систем линейных алгебраических уравнений Пусть имеется общее решение системы линейных уравнений: 9  x1 = b1 − a1, r +1xr +1 − − a1n xn  x2 = b2 − a2,  r +1xr +1 − − a2 n xn .   x = b − a  xn r ,r +1xr +1 − − arn  r r Положив значения свободных переменных равными нулю: получим базисное решение системы: xr +1 = xr +2 = = xn = 0 , X = (b1, b2 , , br ,0,0, ,0) . Базисное решение называется невырожденным, если оно содержит ровно r неотрицательных компонент, в противном случае оно называется вырожденным. Заметим, что для нахождения базисного решения можно не выписывать общее решение системы. Достаточно положить значения свободных переменных равными 0, а значения базисных переменных находятся в правой части матрицы системы, приведенной к единичному базису, в строках, соответствующих единицам единичной матрицы. Рассмотрим запись системы в векторном виде: x1a1 + x2 a 2 + + xn a n = b . Т.к. система векторов a1, a 2 , , a n в (1.2) может иметь несколько базисов (столбцы единичной матрицы можно получать на разных местах), то базисных n! решений может быть несколько, но не более, чем Сnr = ). r !(n − r )! Пример 1 Найдем все базисные решения для системы из последнего Примера предыдущей лекции.  x1 + x2 + 2 x3 − 6 x4 = −3  x1 + x2 + x3 − 4 x4 = 0  x1 + x2 − 2 x4 = −3 Решение: Была получена матрица, приведенная к единичному базису: 1 1 0 −2 3 0 0 1 −2 −3 В общем решении в матрице, приведенной к единичному базису, переменные x1, x3 – базисные, x2, x4 – свободные, поэтому, положив x2=0, x4=0, получаем первое базисное решение системы: X 1 = (3;0; −3;0) . Так как rang(A) = 2, n = 4, то базисных решений может быть не больше, чем 4! 4! С42 = = = 6 . Переберем все 6 возможных комбинаций базисных 2!(4 − 2)! 2! 2! переменных: x1, x2; x1, x3; x1, x4; x2, x3; x2, x4; x3, x4. Для каждой пары переменных преобразуем матрицу А с помощью элементарных преобразований таким образом, чтобы столбцы единичной матрицы получились на месте столбцов, соответствующих базисным переменным. Для преобразований можно ( ) 10 использовать любую наиболее удобную матрицу из предыдущих преобразований. Для того, чтобы переменные x1, x2 стали базисными, необходимо получить столбцы единичной матрицы на местах первого и третьего столбцов. Но из матрицы 1 1 0 −2 3 видно, что это сделать невозможно, т.к. эти 0 0 1 −2 −3 столбцы линейно зависимы. Следовательно, переменные x1 и x2 не могут быть одновременно базисными. Для того, чтобы переменные x1 и x4 стали базисными, необходимо получить столбцы единичной матрицы на местах первого и четвертого столбцов. Выполним преобразования матрицы.  1 1 0 −2 3 1 1 −1 0 6 .  0 0 1 −2 −3 − 1/ 2 1 3/ 2  ( ) )( ) Получаем второе базисное решение системы: X 2 = (6;0;0;3 / 2) . Для того, чтобы переменные x2 и x3 стали базисными, необходимо получить столбцы единичной матрицы на местах второго и третьего столбцов. Это уже сделано в матрице 1 1 0 −2 3 . 0 0 1 −2 −3 ( ) Получаем третье базисное решение системы: X 3 = (0;3; −3;0) . Для того, чтобы переменные x2 и x4 стали базисными, необходимо получить столбцы единичной матрицы на местах второго и четвертого столбцов. Это уже −1 0 6 сделано в матрице 1 1 0 0 −1 / 2 1 3 / 2 ( ) Получаем четвертое базисное решение системы: X 4 = (0;6;0;3 / 2) . Для того, чтобы переменные x3 и x4 стали базисными, необходимо получить столбцы единичной матрицы на местах третьего и четвертого столбцов. Выполним преобразования матрицы:  1 1 0 −2 3 −1 / 2 −1 / 2 0 1 −3 / 2 .  0 0 1 −2 −3 −1 −1 1 0 −6  )( ) Получаем пятое базисное решение системы: X 5 = (0;0; −6; −3 / 2) . Базисные решения, в которых все переменные неотрицательны, называются опорными решениями. В предыдущем примере из найденных пяти базисных решений опорными являются только два: X2 и X4. Опорные решения можно находить путем перебора базисных решений, но можно внести изменения в уже рассмотренный алгоритм поиска базисных решений для более быстрого нахождения опорных решений. При нахождении опорных решений будем считать, что правая часть исходной системы не содержит отрицательных коэффициентов. Этого можно всегда достичь, умножив нужные уравнения на –1. Далее при преобразованиях матрицы, необходимо следить за тем, чтобы правая часть сохраняла неотрицательность. 11 Рассмотрим дополнительные условия, которые будут накладываться на выбор разрешающего элемента при выполнении жордановых исключений. Пусть aij – разрешающий элемент j-го столбца (akj – элемент в j-ом столбце и k-ой строке (akj  0), на месте которого после элементарных преобразований будет получен 0. Рассмотрим один шаг жордановых исключений:      aij bi    1 bi     ,    bk  akj bk           bi  akj bk  aij − bi  akj b = где bi  0, bk  0 , bi = i , bk = bk − . aij aij aij Так как bi  0 и хотим сохранить неотрицательность правой части в этой b строке, то должно выполняться условие bi = i  0 , откуда aij  0 . Таким aij образом, разрешающий элемент должен быть положительным. Возможны 2 случая: akj < 0 и akj > 0. Рассмотрим их. 1) akj  0 Тогда, bk  aij − bi  akj  0 . Т.е. для отрицательных akj неотрицательность правой части после выполнения шага жордановых исключений сохранится. 2) akj  0 Тогда, должно выполняться неравенство bk  aij − bi  akj  0 . Преобразуем неравенство bk  aij  bi  akj . Т.к. akj  0 и aij  0 , то должно выполняться b b неравенство k  i . akj aij Следовательно, при поиске опорных решений на каждом шаге метода Жордана-Гаусса для включения в базис следует выбирать переменную с положительным коэффициентом aij , для которого в j-ом столбце достигается минимум отношения свободных членов к положительным элементам столбца: bi b (1.8) = min k . aij k ,akj 0 akj Если в процессе преобразования матрицы окажется, что в некоторой строке все коэффициенты при неизвестных неположительны, а правая часть – положительна, то система не имеет опорных решений. Если rang(A) = r и уже получено (r-s) столбцов единичной матрицы (1  s < r) и дальше не удается выделить положительный элемент матрицы, удовлетворяющий ограничению (1.8) для получения (r-s+1)-го столбца единичной матрицы, то включение в базис выбранных ранее переменных не дает опорного решения. 12 Пример 2 Найти все опорные решения системы.  2 x1 − x2 + x3 − x4 = 3 . 2 x1 − x2 + x4 = 2  3x1 − x3 − x4 = −1 Решение:  2 −1 1 −1 3   2 −1 1 −1 3  A =  2 −1 0 1 2   2 −1 0 1 2  .  3 0 −1 −1 −1  −3 0 1 1 1      Определим, какой положительный элемент следует выбрать в качестве разрешающего в первом столбце матрицы из соотношения (1.8). 3 2 min  ;  = 1 , следовательно, разрешающий элемент находится во второй 2 2 строке.  2 −1 1 −1 3   0 1 −2 1   2 −1 0 1 2   1 −1 / 2 0 1 / 2 1  .  −3 0 1 1 1   0 −3 2 5 8     Во втором столбце нельзя выбрать положительный разрешающий элемент. Откуда можно заключить, что x1 и x2 не могут быть базисными переменными опорного решения. Определим, какой положительный элемент следует выбрать в качестве разрешающего в третьем столбце матрицы. 1 8  min  ;  = 1 , следовательно, разрешающий элемент находится в первой строке. 1 2  0 1 −2 1  1 −2 1   0  1 −1 / 2 0 1 / 2 1   1 −1 / 2 0 1 / 2 1  . 0 −3 2 5 8   0 −3 0 9 6   Определим, какой положительный элемент следует выбрать в качестве разрешающего в четвертом столбце матрицы. 2 6 6 min  ;  = , следовательно, разрешающий элемент находится в третьей 1 9 9 строке. 0 1 −2 1   0 −2 / 3 1 0 7 / 3   1 −1 / 2 0 1 / 2 1   1 −1 / 3 0 0 2 / 3  .   0 −3 0 9 6   0 −1 / 3 0 1 2 / 3   Из последней матрицы находим опорное решение X 1 = (2 / 3;0;7 / 3;2 / 3) . Определим остальные опорные решения системы. Т. к. rang(A) = 3, n = 4, то 4! 4! 3 = = 4. базисных решений может быть не больше, чем С4 = 3!(4 − 3)! 3! 1! Переберем 4 возможные комбинации базисных переменных: x1, x2, x3; x1, x2, x4; x1, x3, x4; x2, x3, x4. Для каждой тройки переменных преобразуем матрицу 13 А с помощью жордановых исключений таким образом, чтобы столбцы единичной матрицы получились на месте столбцов, соответствующих базисным переменным. Случай, когда базисными переменными являются x1, x3, x4 уже рассмотрен. То, что x1 и x2 не могут быть базисными переменными опорного решения, было отмечено выше. Остался случай x2, x3, x4. Из последней матрицы x3, x4 уже базисные, но x2 нельзя включить в базис для получения опорного решения (во втором столбце нет положительных элементов). Поэтому, найденное опорное решение X = (2 / 3;0;7 / 3;2 / 3) является единственным опорным решением системы. 1.5. Генерирование сочетаний без повторений из n по k Без ограничения общности можно считать, что A = {1,2, , n} . Каждому kэлементному подмножеству взаимно однозначно соответствует возрастающая последовательность длины k с элементами из A. Сформулируем алгоритм, который позволяет генерировать все такие последовательности в лексикографическом порядке (p – номер элемента, с которого будут начинаться изменения в следующем сочетании): 1. Первая последовательность (1, , k ) , p = k. 2. Если последний элемент сгенерированной последовательности не равен n, то p = k, в новой последовательности меняется только последний элемент. Если последний элемент сгенерированной последовательности равен n, то уменьшаем p на 1 и новая сгенерированная последовательность (b1 , , bp , , bi , , bk ) будет отличаться от предыдущей (a1 , , a p , , ai , , ak ) , начиная с p-го элемента по следующему правилу: p-ый элемент увеличиваем на 1, а все последующие элементы на 1 больше предыдущего. Правило можно сформулировать по-другому: bi = a p + (i − p + 1), i = p, , k . Пояснение: bp = a p + 1, bp +1 = a p + 2, bk = a p + (k − p + 1) . (a1 , , a p , , ai , , ak ) (b1 , , bp , , bi , , bk ) i − p +1 Пункт 2 повторяем до тех пор, пока p не станет равным 0. Пример: Генерирование сочетаний из 5 по 3. Решение: (1, 2, 3), p = 3; (1, 2, 4), p = 3; (1, 2, 5), p = 2; (1, 3, 4), p = 3; (1, 3, 5), p = 2; (1, 4, 5), p = 1; 14 (2, 3, 4), p = 3; (2, 3, 5), p = 2; (2, 4, 5), p = 1; (3, 4, 5), p = 0. начало k, n i = 1, k, 1 ai = i p= k да ak = n p= p - 1 нет p= k p1 нет да i = k, p, -1 ai = ap + (i - p + 1) конец Рис. 1. Блок-схема генерирования сочетаний без повторений 15 1.6. Различные формы записи задачи линейного программирования. Переход от одной формы записи к другой Рассмотрим задачу линейного программирования (ЗЛП) в общем виде: n Z =  c j x j → max(min) (1.9) j =1  n   aij x j  bi (i = 1, , m1),  j =1  n    aij x j  bi (i = m1 + 1, , m2 ),  j =1  n    aij x j = bi (i = m2 + 1, , m),  j =1  x  0 ( j = 1, , k , k  n).  j (1.10) где aij , bi , c j – заданные постоянные величины и m1  m2  m . Функция (1.9) называется целевой функцией, а условия (1.10) – ограничениями задачи. Задача линейного программирования задана в канонической форме, если требуется максимизировать целевую функцию, все ограничения системы – уравнения, и на все переменные наложено условие неотрицательности ( m1 = m2 = 0, k = n ). Задача линейного программирования задана в симметричной форме, если требуется максимизировать целевую функцию, все ограничения системы – неравенства «» (или минимизировать целевую функцию, все ограничения системы – неравенства «») и на все переменные наложено условие неотрицательности. Набор чисел X = ( x1, x2 , , xn ) называется допустимым решением (планом), если он удовлетворяет системе ограничений (1.10). Множество всех допустимых решений называется областью допустимых решений (ОДР). Допустимое решение X * = ( x1*, x2* , , xn* ) , для которого достигается максимальное (минимальное) значение функции, называется оптимальным планом. Значение целевой функции при плане X будем обозначать Z ( X ) . Следовательно, если X* – оптимальный план задачи, то для любого X выполняется неравенство Z ( X )  Z ( X *) при нахождении максимума функции или Z ( X )  Z ( X *) при нахождении минимума функции. Термины «план» и «оптимальный план» возникли из экономических приложений. 16 Все три формы записи ЗЛП являются эквивалентными в том смысле, что имеются алгоритмы перехода от одной формы к другой. Таким образом, если имеется способ решения задачи в одной из форм, то всегда можно определить оптимальный план задачи, заданной в любой другой форме. Задача в симметричной форме решается графическим методом, а в канонической форме – симплекс–методом. Рассмотрим алгоритмы перехода от одной формы к другой. • Симметричная → каноническая. Переход осуществляется путем добавления в левую часть каждого неравенства дополнительной неотрицательной переменной. Если неравенство было «≤», то дополнительная переменная добавляется в левую часть неравенства со знаком «+». Если неравенство было «», то дополнительная переменная добавляется в левую часть неравенства со знаком «–». Вводимые дополнительные переменные называются балансовыми. Задачу минимизации функции Z заменяют на задачу максимизации функции (–Z) и используют, что min Z = –max (–Z). • Каноническая → симметричная. Для осуществления такого перехода находится общее решение системы уравнений – ограничений, целевая функция выражается через свободные переменные. Далее, воспользовавшись неотрицательностью базисных переменных, можно исключить их из задачи. Симметричная форма задачи будет содержать неравенства, связывающие только свободные переменные, и целевую функцию, зависящую только от свободных переменных. Значения базисных переменных находятся из общего решения исходной системы уравнений. • Общая → каноническая. Каждая переменная, на которую не было наложено условие неотрицательности, представляется в виде разности двух новых неотрицательных переменных. Неравенства преобразуются в уравнения путем введения в левую часть каждого неравенства балансовой переменной таким же образом, как это было описано при переходе от симметричной к канонической форме. Задачу минимизации функции Z заменяют на задачу максимизации функции (–Z) таким же образом, как это было описано при переходе от симметричной к канонической форме. Пример 1 Перейти от общей формы записи задачи линейного программирования к канонической форме. Z 3x1 2 x2 3x3 min 2 x1 x2 x3 2 3 x1 2 x2 4 x3 6 x1 x2 5 x3 4 x1 , x2 0 17 Решение: На переменную x3 не наложено условие неотрицательности, поэтому представим x3 в виде разности неотрицательных переменных: x3 x3 , где 0 . Тогда система ограничений будет иметь вид: x3 , x3 2 x1 x2 3x1 2 x2 x1 x3 x2 x3 x3 4 x3 5 x3 2 4 x3 6 5 x3 , 4 x1 , x2 , x3 , x3 а целевая функция преобразуется к виду: 3x1 2 x2 3x3 3x4 min . В неравенства введем дополнительные переменные, перейдем к задаче максимизации и получим каноническую форму записи задачи: Z Z 3x1 2 x1 x2 3x1 2 x2 x1 x2 2 x2 x3 3x3 x3 4 x3 5 x3 3x4 x4 4 x3 5 x3 x1 , x2 , x3 , x3 , x4 , x5 max 2 x5 6  4 Пример 2 Перейти от канонической формы программирования к симметричной форме. Z 2x1 x2 3x3 6x4 x5 max x1 3x2 x3 4 x4 x5 12 x1 2 x2 3x4 x5 6 3x1 3x2 16 x4 2 x5 26 x1 , x2 , x3 , x4 , x5 0 записи задачи Решение: Найдем общее решение системы методом Жордана-Гаусса. 1 4 −1 12   1 3 1 4 −1 12   1 3     A =  1 2 0 3 −1 6   0 −1 −1 −1 0 −6   3 3 0 16 −2 26   0 −6 −3 4 1 −10      18 линейного  1 0 2 1 −1 −6   1 0 0 23 / 3 −1 / 3 34 / 3       0 1 1 1 0 6   0 1 0 −7 / 3 −1 / 3 −10 / 3  .  0 0 3 10 1 −10   0 0 1 10 / 3 1 / 3 26 / 3      Ранг матрицы A равен 3, следовательно, система имеет бесконечно много решений. Из преобразованной матрицы определяем, что переменные x1, x2 , x3 базисные, а x4 , x5 - свободные. Система, приведенная к единичному базису:  x1 + 23 / 3x4 − 1 / 3 x5 = 34 / 3  x − 7 / 3 x − 1 / 3 x = −10 / 3  2 4 5   x3 + 10 / 3x4 + 1 / 3 x5 = 26 / 3  x1 , x2 , x3 , x4 , x5  0 Выразим базисные переменные через свободные:  x1 = 34 / 3 − 23 / 3 x4 + 1 / 3 x5  0  x = −10 / 3 + 7 / 3 x + 1 / 3 x  0  2 4 5 – общее решение системы  x = 26 / 3 − 10 / 3 x − 1 / 3 x  4 5  3  x4 , x5  0 Выразим целевую функцию через свободные переменные: Z 2(34 / 3 23 / 3x4 1/ 3x5 ) ( 10 / 3 7 / 3x4 1/ 3 x5 ) 3(26 / 3 10 / 3x4 1/ 3x5 ) 6 x4 x5 Задача в симметричной форме: Z 41/ 3x4 7 / 3x5  23 x4 − x5  34 7 x + x  10  4 5  10 x4 + x5  26  x4 , x5  0  1.7. 41/ 3x4 7 / 3x5 max Геометрическая интерпретация задачи линейного программирования Графический метод решения ЗЛП применяется для решения задач, заданных в симметричной форме. Этот метод наиболее эффективно применяется для решения задач с двумя переменными, т.к. требует графических построений. В случае трех переменных необходимы построения в R3, в случае четырех переменных необходимы построения в R4 и т.д. Множество точек называется выпуклым, если для любых двух точек множества оно содержит отрезок, их соединяющий. На рис. 2 представлены примеры выпуклых множеств. 19 Рис. 2. Выпуклые множества На рис. 3 представлены примеры множеств, которые не являются выпуклыми. Рис. 3. Невыпуклые множества Теорема 4 Пересечение любого количества выпуклых множеств является выпуклым множеством. Доказательство: Рассмотрим доказательство для случая двух множеств. Пусть имеются два множества точек A и B, которые являются выпуклыми. Пусть множество С - пересечение множеств A и B. Возьмем две произвольные точки P и Q, принадлежащие множеству С. Точки P и Q принадлежат С, поэтому они принадлежат A. Но A является выпуклым множеством, поэтому отрезок [PQ] принадлежит множеству A. Точки P и Q принадлежат С, поэтому они принадлежат B. Но B является выпуклым множеством, поэтому отрезок [PQ] принадлежит множеству B. Получили, что отрезок [PQ] принадлежит как множеству A, так и множеству B. Следовательно, отрезок [PQ] принадлежит пересечению A и B, т.е. множеству C. Следовательно, множество C с любыми двумя точками содержит отрезок, их соединяющий, поэтому, C – выпуклое множество. Теорема 5 Пусть имеются две произвольные точки P( p1, p2 , , pn ) и Q(q1, q2 , , qn ) в пространстве Rn. Тогда для любой точки X ( x1, x2 , , xn ) отрезка [PQ] должно выполняться: xi = qi + (1 −  ) pi (i = 1,2, , n), где 0    1 . Доказательство: Рассмотрим доказательство для случая на плоскости. Пусть имеются точки P(p1,p2) и Q(q1, q2) и точка X(x1, x2) лежит на отрезке [PQ]. PQ = (q1 − p1, q2 − p2 ), PX = ( x1 − p1, x2 − p2 ). Q P X С другой стороны, PX =   PQ , где 0    1 . Тогда, PX = ( x1 − p1, x2 − p2 ) =  (q1 − p1, q2 − p2 ). ( x1 − p1, x2 − p2 ) = ( (q1 − p1 ),  (q2 − p2 ))  x1 − p1 =  (q1 − p1), x2 − p2 =  (q2 − p2 ) . 20 Откуда получаем: x1 = p1 +  (q1 − p1 ) = q1 + (1 −  ) p1, x2 = p2 +  (q2 − p2 ) = q2 + (1 −  ) p2. Следовательно, xi = qi + (1 −  ) pi (i = 1,2, , n) , где 0    1. Гиперплоскостью в пространстве Rn называется множество точек, удовлетворяющее уравнению a1x1 + a2 x2 + + an xn = b , где ai (i = 1,2, n), b – константы. Заметим, что в двумерном случае гиперплоскостью является прямая. Полупространством называется множество точек, удовлетворяющее одному из неравенств a1x1 + a2 x2 + + an xn  b или a1x1 + a2 x2 + + an xn  b . Гиперплоскость делит точки пространства на два полупространства. В двумерном случае гиперплоскостью является полуплоскость. Теорема 6 Полупространство является выпуклым множеством. Доказательство: Рассмотрим доказательство для случая, когда полупространство задается неравенством a1x1 + a2 x2 + + an xn  b . Пусть точки и принадлежат Q(q1, q2 , , qn ) P( p1, p2 , , pn ) полупространству. Тогда, должны выполняться неравенства: a1 p1 + a2 p2 + + an pn  b и a1q1 + a2q2 + + anqn  b . Пусть X ( x1, x2 , , xn ) – некоторая точка отрезка [PQ]. Тогда по Теореме 5 должно выполняться xi = qi + (1 −  ) pi (i = 1,2, , n) , где 0    1 . Домножим первое неравенство на (1-), второе на  и сложим их. (1 −  )a1 p1 + (1 −  )a2 p2 + + (1 −  )an pn  b  a1q1 +  a2q2 +  anqn  b + a1((1 −  ) p1 +  q 1) + a2 ((1 −  ) p2 +  q 2 ) + + an ((1 −  ) pn +  q n )  b. Получаем, a1x1 + a2 x2 + + an xn  b . Следовательно, точка любая точка X отрезка [PQ] принадлежит полупространству, поэтому, полупространство – выпукло. Следствие Пересечение любого количества полупространств является выпуклым множеством. Многогранником называется пересечение одного или более полупространств. Многогранник в двумерном случае называется многоугольником. На рис. 4 приведены примеры многоугольников. 21 Ограниченное множество Единственная точка Неограниченное множество Пустое множество Рис. 4. Примеры многоугольников Точка выпуклого множества называется угловой, если она не лежит внутри никакого отрезка, соединяющего две другие точки данного множества. Угловыми точками треугольника являются его вершины (их три). Угловыми точками круга являются точки окружности, которая его ограничивает (их бесконечное число). Угловая точка многогранника называется его вершиной. Рассмотрим ЗЛП, заданную в симметричной форме. (1.11) Z = c1x1 + c2 x2 + + cn xn → max a 11 x1 + a12 x2 + + a1n xn  b1   (1.12)  a x + a x + + a x  b mn n m  m1 1 m 2 2  x1, x2 , , xn  0 Теорема 7 Если задача (1.11), (1.12) имеет оптимальное решение, то максимальное значение целевая функция принимает в одной из вершин многогранника решений. Если максимальное значение целевая функция принимает более, чем в одной вершине, то она принимает его во всякой точке, являющейся выпуклой комбинацией этих вершин (т.е. функция принимает максимальное значение в любой точке ребра или грани, которые определяются этими вершинами). 22 Доказательство: Наибольшее значение функция может принимать либо внутри многогранника, либо на его границе. Пусть наибольшее значение функция принимает внутри многогранника. Тогда для этой точки должно выполняться необходимое условие экстремума: Z Z Z = = = = 0  c1 = c2 = = cn = 0  Z  0, противоречие. x1 x2 xn Следовательно, наибольшее значение функция принимает на границе многоугольника. Предположим, что наибольшее значение функция принимает в граничной точке X * ( x1*, x2* , , xn* ) , которая не является вершиной. Значит, Z max = Z ( X * ) = c1 x1* + c2 x2* + + cn xn* = M и точка X* лежит внутри отрезка [PQ]. Следовательно, выполняется: Z ( P) = c1 p1 + c2 p2 + + cn pn  M , Z (Q) = c1q1 + c2q2 + + cnqn  M , xi* =  qi + (1 −  ) pi (i = 1,2, , n) , где 0    1 . Тогда, M = Z ( X * ) = c1x1* + c2 x2* + + cn xn* = c1 ( q1 + (1 −  ) p1 ) + c2 ( q2 + (1 −  ) p2 ) + + +cn ( qn + (1 −  ) pn ) =  (c1q1 + c2q2 + + cn qn ) + (1 −  )(c1 p1 + c2 p2 + + cn pn )    M + (1 −  ) M = M Получили, M  M – противоречие. Следовательно, наибольшее значение функция принимает в вершине многогранника. 1.8. Графический способ метод решения ЗЛП, заданной в симметричной форме, в случае двух переменных Пусть задача линейного программирования с двумя переменными задана в симметричной форме. (1.13) Z = c1x1 + c2 x2 → max a 11 x1 + a12 x2  b1 a x + a x  b  21 1 22 2 2 (1.14)  a x + a x  b  m1 1 m 2 2 m  x1, x2  0 Для решения этой задачи можно перебрать все вершины многоугольника, определяемого системой ограничений, и выбрать из них ту, в которой значение функции больше. Но можно не перебирать все вершины, а воспользоваться понятиями линии уровня и градиента. Линией уровня функции Z называется множество точек, удовлетворяющее уравнению Z = c , где c – произвольная константа. В двумерном случае, это уравнение определяет прямую. Линии уровня линейной функции образуют семейство параллельных прямых. 23  Z Z  , Вектор grad Z =   называется градиентом функции Z. Вектор  x1 x2  grad Z в каждой точке перпендикулярен линии уровня, проходящей через эту точку, и указывает направление наибольшего возрастания функции Z, grad Z = (c1, c2 ) . Таким образом, наибольшее значение Z достигается в вершине, через которую проходит линия уровня, соответствующая наибольшему значению Z. Для графического решения задачи ЗЛП используют следующий алгоритм: 1. Записывают уравнения граничных прямых ai1x1+ai2x2=bi (i = 1,…,m) и строят их на плоскости X1OX2 по двум точкам. 2. Отмечают полуплоскости, соответствующие ограничениям неравенствам. Для этого берут «пробную» точку, через которую не проходит граница полуплоскости (часто берут, если прямая не проходит через начало координат, точку (0,0)), и ее координаты подставляют в соответствующее ограничение-неравенство. Если полученное неравенство верное, то искомой будет полуплоскость, содержащая «пробную» точку; в противном случае, искомой будет полуплоскость, которой данная точка не принадлежит. 3. Заштриховывают многоугольник, определяемый системой ограничений. Для этого определяют общую часть ранее отмеченных m полуплоскостей, лежащую в первой четверти (следует из условий неотрицательности переменных). 4. Строят вектор grad Z = (c1, c2 ) и одну из прямых семейства Z = c (чаще всего Z = 0). Если выбранный для построения многоугольника масштаб не позволяет построить grad Z , то вместо него строят вектор N = k  grad Z grad Z (в случае, если длина grad Z слишком мала для построения) или N = (в k случае, если длина grad Z слишком велика для построения), где k  1 . 5. В случае необходимости параллельным переносом линию уровня следует расположить таким образом, чтобы многоугольник находился впереди линии уровня по направлению grad Z . 6. Определяют экстремальную точку, соответствующую вершине многоугольника, путем параллельного перемещения прямой Z = с в направлении вектора grad Z . Это будет наиболее удаленная вершина многоугольника, в которой линия уровня пересекается с многоугольником. 7. Вычисляют координаты оптимальной точки и значение функции Z в этой точке. Замечание: Если у функции требуется найти минимальное значение, то линию уровня Z = c перемещают в направлении вектора − grad Z (или перемещают в направлении grad Z , но находят первую вершину пересечения линии уровня с многоугольником). 24 В зависимости от особенностей области допустимых решений и взаимного расположения области и вектора grad Z при решении задачи линейного программирования возможны различные случаи. Рассмотрим их. 1. Если область допустимых решений – ограниченный многоугольник, то может быть либо единственное решение, либо бесконечно много решений – все точки отрезка, соединяющего две вершины многоугольника (альтернативный оптимум). В случае альтернативного оптимума оптимальный план представляется выражением координат произвольной точки отрезка через координаты ее концов. 2. Если область допустимых решений – неограниченный многоугольник, то в зависимости от направления grad Z задача может иметь или не иметь решения. В этом случае так же может оказаться альтернативный оптимум. На рис. 4 приведены примеры нахождения оптимальной точки. Рис. 5. Примеры нахождения минимумов и максимумов функции На рис. 5(а) функция достигает минимума в точке А, а максимума – в любой точке отрезка ВС (альтернативный оптимум); на рис. 5(б) максимум достигается в точке А, минимума функция не имеет; на рис. 5(в) функция не имеет ни минимума, ни максимума. Пример 1 Решить графически ЗЛП: Z = 50 x1 + 40 x2 → max 2 x1 + 5 x2  20 8 x + 5 x  40  1 2  5 x1 + 6 x2  30  x1, x2  0 Решение: Каждое неравенство полуплоскость. Запишем полуплоскостей. исходной системы ограничений уравнения граничных прямых 25 определяет для этих (1) 2х1 + 5х2 = 20 х1 10 x2 4 (2) 8х1 + 5х2 = 40 х1 5 x2 8 (3) 5х1 + 6х2 = 30 х1 6 x2 5 На рис. 6 демонстрируется процесс графического решения данной задачи. Сделаем пояснения. Построим прямые, ограничивающие полуплоскости, определяемые неравенствами системы. Каждая прямая разбивает плоскость на две полуплоскости. Для выбора полуплоскостей, определяемых каждым неравенством, подставим координаты «пробной» точки (0;0) в каждое неравенство. Получаем: 2  0 + 5  0  20 верно. Следовательно, отмечаем полуплоскость, содержащую «пробную» точку (0;0). 8  0 + 5  0  40 верно. Следовательно, отмечаем полуплоскость, содержащую «пробную» точку (0;0). 5  0 + 6  0  30 верно. Следовательно, отмечаем полуплоскость, содержащую «пробную» точку (0;0). Выбранные полуплоскости отметим стрелочками. Найдем пересечение отмеченных полуплоскостей с учетом условия: х1,х2  0. Заштрихуем полученный пятиугольник OABCD. Построим линию уровня Z = 0: 50х1 + 40х2 = 0 х1 x2 4 -5 Вектор grad Z = (50;40) определяет направление наибольшего возрастания grad Z функции Z. Построим из начала координат вектор N = = (5;4) . Этот 10 вектор также показывает направление наибольшего возрастания функции. Перемещая линию уровня параллельным переносом в направлении вектора N , находим последнюю точку пересечения линии уровня и заштрихованного пятиугольника – точку C. Эта точка является точкой максимума функции. 26 Рис. 6. Графическое решение задачи из примера 1 Точка C получается в результате пересечения прямых (2) и (3). Для нахождения ее координат решим систему: 8 x1 + 5 x2 = 40 5 − 5 x1 + 6 x2 = 30 8 − 23x2 = −40 40 920 − 200 40 40 − 5  x1 720 90 23 = 23 x2 =  x1 = = = = 23 8 8 8 23  8 23 90 40 4500 + 1600 6100  90 40  Z max = Z  ;  = 50  + 40  = = 23 23 23 23  23 23   90 40  6100 Ответ: Z max = Z  ;  = . 23  23 23  40 − 5  Пример 2 Решить графически задачу линейного программирования: Z ( x1, x2 ) = 120 x1 + 160 x2 → min  x1 + 3 x2  12 5 x + 4 x  31  1 2   2 x1 + 3 x2  18  x1, x2  0 Решение: Каждое неравенство исходной системы ограничений полуплоскость. Запишем уравнения граничных прямых полуплоскостей. 27 определяет для этих (1) х1 + 3х2 = 12 х1 12 x2 4 (2) 5х1 + 4х2 = 31 х1 6.2 x2 7.8 (3) 2х1 + 3х2 = 18 х1 9 x2 6 На рис. 6 демонстрируется процесс графического решения данной задачи. Построим прямые, ограничивающие полуплоскости, определяемые неравенствами системы. Каждая прямая разбивает плоскость на две полуплоскости. Для выбора полуплоскостей, определяемых каждым неравенством, подставим координаты «пробной» точки (0;0) в каждое неравенство. Получаем: 0 + 3  0  12 не верно. Следовательно, отмечаем полуплоскость, не содержащую «пробную» точку (0;0). 5  0 + 4  0  31 не верно. Следовательно, отмечаем полуплоскость, не содержащую «пробную» точку (0;0). 2  0 + 3  0  18 не верно. Следовательно, отмечаем полуплоскость, не содержащую «пробную» точку (0;0). Выбранные полуплоскости отметим стрелочками. Найдем пересечение отмеченных полуплоскостей с учетом условия: х1,х2  0. Заштрихуем полученный неограниченный четырехугольник ABCD. Построим линию уровня Z = 0: 120х1 + 160х2 = 0 х1 x2 4 -3 Вектор grad Z = (120;160) определяет направление наибольшего возрастания grad Z функции Z. Построим из начала координат вектор N = = (6;8) . Этот 20 вектор также показывает направление наибольшего возрастания функции. Перемещая линию уровня параллельным переносом в направлении вектора N , находим первую точку пересечения линии уровня и заштрихованного четырехугольника – точку B. Эта точка является точкой минимума функции. Рис. 7. Графическое решение задачи из примера 2 28 Точка B получается в результате пересечения прямых (2) и (3). Для нахождения ее координат решим систему: 5 x1 + 4 x2 = 31 3 − 2 x1 + 3x2 = 18 4 = 21 31 − 5  x1 31 − 5  3 16 x1 = 3  x2 = = = =4 4 4 4 Z min = Z ( 3;4 ) = 120  3 + 160  4 = 1000 7x1 Ответ: Z min = Z ( 3;4 ) = 1000 . 1.9. Многомерные ЗЛП, заданные в канонической форме, решаемые графически Графическим методом можно решить ЗЛП, заданную в канонической форме, если после приведения системы ограничений к виду (1.6) n − r  2 . В системе (1.7) переходят к неравенствам, воспользовавшись неотрицательностью базисных переменных. Далее решают графически задачу в эквивалентной симметричной форме и находят значения свободных переменных. Подставив найденные значения в (1.6), находят значения базисных переменных. Пример Решить графически задачу линейного программирования: Z = 4 x1 + 2 x2 + x4 → max 2 x1 + x2 + x3 = 14 x + x = 8 4  2  x1 + x2 − x5 = 4 2 x − 3x + x = 6 2 6  1  xi  0, i = 1,2, ,6 Решение: Составим расширенную матрицу системы:  2 1 1 0 0 0 14   2 1 1 0 0 0 14  0 1 0 1 0 0 8  0 1 0 1 0 0 8  1 1 0 0 −1 0 4  (−1)  −1 −1 0 0 1 0 −4   2 −3 0 0 0 1 6   2 −3 0 0 0 1 6      В матрице уже имеется выделенный базис, базисные переменные – x3, x4 , x5 , x6 . Выразим базисные переменные и целевую функцию через свободные переменные. 29  x3 = 14 − 2 x1 − x2  0 x = 8 − x  0 2  4  x5 = −4 + x1 + x2  0  x = 6 − 2 x + 3x  0 1 2  6  xi  0, i = 1,2 Z = 4x1 + 2x2 + 8 − x2 = 4x1 + x2 + 8 → max Получили эквивалентную задачу в симметричной форме. Z = 4x1 + x2 + 8 → max 2 x1 + x2  14 x  8  2  x1 + x2  4 2 x − 3x  6 2  1  xi  0, i = 1,2 Решим задачу графически. (1) х1 + х2 = 14 (2) х2 = 8 (3) х1 + х2 = 4 (4) 2х1 -3х2 = 6 х1 7 х1 0 1 х1 4 х1 3 x2 14 x2 8 8 x2 4 x2 -2 На рис. 8 демонстрируется процесс графического решения данной задачи. Построим прямые, ограничивающие полуплоскости, определяемые неравенствами системы. Каждая прямая разбивает плоскость на две полуплоскости. Для выбора полуплоскостей, определяемых каждым неравенством, подставим координаты «пробной» точки (0;0) в каждое неравенство. Получаем: 0 + 0 ≤ 14 верно. Следовательно, отмечаем полуплоскость, содержащую «пробную» точку (0;0). 0 ≤ 8 верно. Следовательно, отмечаем полуплоскость, содержащую «пробную» точку (0;0). 0 + 0 4 не верно. Следовательно, отмечаем полуплоскость, не содержащую «пробную» точку (0;0). 2  0 - 3  0 ≤ 6 верно. Следовательно, отмечаем полуплоскость, содержащую «пробную» точку (0;0). Выбранные полуплоскости отметим стрелочками. Найдем пересечение отмеченных полуплоскостей с учетом условия: х1,х2  0. Заштрихуем полученный четырехугольник ABCDE. Построим линию уровня Z = 8: 4х1 + х2 + 8 = 8  4х1 + х2 = 0. х1 x2 1 -4 30 Вектор grad Z = (4;1) определяет направление наибольшего возрастания функции Z. Построим из начала координат вектор N = 2  grad Z = (8;2) . Этот вектор также показывает направление наибольшего возрастания функции. Перемещая линию уровня параллельным переносом в направлении вектора N , находим последнюю точку пересечения линии уровня и заштрихованного пятиугольника – точку E. Эта точка является точкой максимума функции. Рис. 8. Графическое решение задачи из примера Точка E получается в результате пересечения прямых (1) и (4). Для нахождения ее координат решим систему: 2 x1 + x2 = 14 − 2 x1 − 3x2 = 6 4 x2 = 8  x2 = 2 14 − x2 14 − 2 x1 = = =6 2 2 Z max = Z ( 6;2 ) = 4  6 + 2 + 8 = 34 Для нахождения оптимального решения исходной задачи найдем значения базисных переменных. x3 = 14 − 2  6 − 2 = 0 x4 = 8 − 2 = 6 x5 = −4 + 6 + 2 = 4 x6 = 6 − 2  6 + 3  2 = 0 31 Оптимальное решение исходной задачи: Z max = Z ( 6;2;0;6;4;0 ) = 34 Ответ: Z max = Z ( 6;2;0;6;4;0 ) = 34 . 1.10. Симплекс-метод В предыдущих пунктах было рассмотрено графическое решение ЗЛП. Но, как мы видели, такой способ применим к достаточно узкому классу задач линейного программирования. Более универсальным является симплекс-метод (метод последовательного улучшения плана), который позволяет решить любую ЗЛП в каноническом виде. Его название связано с тем историческим обстоятельством, что ограничения одной из первых задач, решенных этим методом, задавали симплекс в пространстве соответствующей размерности (Симплекс – простейший многогранник данного числа измерений, например, треугольник в R2, тетраэдр – в R3 и т.д.) Пусть задача линейного программирования представлена в канонической форме: (1.15) Z = c1x1 + c2 x2 + + cn xn → max a 11 x1 + a12 x2 + + a1n xn = b1   (1.16)  a x + a x + + a x = b mn n m  m1 1 m 2 2  x1, x2 , , xn  0 Теорема 8 Каждому опорному решению системы (1.16) соответствует вершина многогранника планов эквивалентной симметричной задачи и наоборот. Из теоремы следует, что максимального значения функция достигает для одного из опорных решений системы (1.16). Симплекс-метод позволяет найти этот опорный план в результате упорядоченного перебора опорных планов. При этом упорядоченность понимается в том смысле, что переход от одного опорного решения к другому значения функции не убывают. Пусть система (1.16) приведена к единичному базису с неотрицательными правыми частями (bi  0, i = 1,2, , m) :  x1 + a1, r +1xr +1 + + a1 n xn = b1  x2 + a2,  r +1xr +1 + + a2 n xn = b2  , (1.17)   xn = br  xr + ar ,r +1xr +1 + + arn  xi  0, i = 1,2, , n Выразим целевую функцию через свободные переменные. (1.18) Z = c0 + c1 xr +1 + + cn xn → max Системе (1.17) соответствует опорное решение (b1, , br ,0, ,0) , при этом значение функции Z = c0 . Средством хранения информации о решаемой задаче линейного программирования являются симплекс-таблицы, начальная таблица составляется по (1.17), (1.18) и имеет следующий вид: 32 б.п. 1 x1 b1 x2 b2 x1 1 x2 1 xr xr +1 a1, r +1  r +1 a2, xn a1, n n a2, (1.19) xr br 0 0 1 ar ,r +1 ar ,n Z c0 0 0 0 −cr +1 −cn В крайнем левом столбце записаны базисные переменные и символ, обозначающий целевую функцию. Последнюю строку называют строкой целевой функции или Z-строкой. Столбец с заголовком 1 содержит правые части уравнений (1.17), свободный член целевой функции и называется столбцом свободных членов. Заголовками остальных столбцов являются переменные. Основную часть таблицы занимают коэффициенты при переменных в уравнениях и целевой функции. Таблице (1.19) соответствует опорное решение (b1, , br ,0, ,0) , при этом значение функции Z = c0 . Теорема 9 (признак оптимальности опорного решения) Если в таблице (1.19) коэффициенты cj  0 ( j = r + 1, , n) , то опорное решение X  = (b1 , , br ,0, ,0) является оптимальным и при этом Zmax = Z ( X ) = c0 . Теорема 10 (признак неограниченности функции) Если в таблице (1.19) существует хотя бы один коэффициент cj  0 такой, что среди элементов aij (i = 1,2, , r) нет положительных, то целевая функция (1.18) при ограничениях (1.17), не ограничена сверху. Теорема 11 (о возможности улучшения плана) Если в таблице (1.19) существует хотя бы один коэффициент cj  0 ( j = r + 1, , n) , а в каждом столбце с таким элементом среди aij (i = 1,2, , r ) есть хотя бы один положительный, то поменяв базис, можно перейти к другому опорному плану Z ( X )  Z ( X ) . X  такому, что Теорема 12 (признак альтернативного оптимума) Если в Z-строке симплексной таблицы (1.19), содержащей оптимальный план, среди чисел cj  0 ( j = r + 1, , n) есть равные 0, то множество оптимальных решений бесконечно. Сформулированные теоремы позволяют проверить, является ли найденное опорное решение оптимальным, и выявить целесообразность перехода к новому опорному решению, но не дают самого алгоритма перехода. Прежде, чем описать этот алгоритм, изложим идею симплекс-метода. Если в Z-строке есть отрицательные элементы, то введение в базис соответствующих свободных переменных позволит не уменьшить значение целевой функции. Так как количество переменных в базисе должно остаться неизменным, то одна из переменных должна быть выведена из базиса. Таким образом, на каждом шаге симплекс-метода осуществляется преобразование базиса: одна из свободных переменных вводится в базис, а одна из базисных – выводится. 33 Алгоритм симплексного преобразования 1. Для перехода к новому опорному решению в Z-строке среди отрицательных коэффициентов −cj ( j = r + 1, , n) выбирают наибольший по абсолютной величине, пусть это будет −cj0 . Тем самым выбрана свободная переменная x j0 , которая будет вводиться в базис. Столбец с заголовком x j0 называется разрешающим. 2. Для выбора базисной переменной, выводимой из базиса, находятся симплексные отношения – отношения элементов столбца свободных членов к положительным элементам разрешающего столбца. b Симплексные отношения i (aij 0  0) записываются справа от симплексaij 0 таблицы. Переменная, выводимая из базиса, определяется минимальным  b  симплексным соотношением min  i  , соответствующая ей строка   i =1, , r  aij 0   a  0 ij0 называется разрешающей. Пусть переменная xi0 будет выводиться из базиса. Элемент ai0 j0 , находящийся на пересечении разрешающей строки и разрешающего столбца, называется разрешающим элементом, выделим его. 3. Формируется новая симплексная таблица по следующим правилам: − в базис вместо переменной xi0 вводим переменную x j0 ; − элементы разрешающей строки делятся на разрешающий элемент ai0 j0 ; − на месте остальных элементов разрешающего столбца будут стоять нули; − столбцы таблицы с заголовками базисных переменных (кроме x j0 ), не изменяются; − все остальные элементы пересчитываются по правилу прямоугольника: ai j  aij 0 aij = aij − 0 (1.20) ai0 j0 (строим прямоугольник с диагональю в вершинах ai0 j0 и пересчитываемом элементе aij : ai0 j0 aij 0 ai0 j ). aij Заметим, что в соответствии с правилом прямоугольника, не заполненные ранее элементы столбца с заголовком xi0 будут равны элементам столбца с заголовком x j0 , деленным на противоположным знаком. 34 разрешающий элемент ai0 j0 , с Правила 3 распространяются на коэффициенты столбца свободных членов и Z-строки, cj ( j = 0, r + 1, r + 2, , n) . Симплексные преобразования проводят до тех пор, пока не будет получено оптимальное решение или установлена неразрешимость задачи (теоремы 9, 10). Замечания: 1. Если таблица (1.19) соответствует оптимальному решению, а среди чисел  c j ( j = r + 1, , n) имеется коэффициент c j0 равный нулю, то задача имеет бесконечно много решений (геометрически соответствует рис. 4 а). Вторую вершину, соответствующую оптимальному решению, можно найти, выбрав в качестве разрешающего столбец, содержащий c j0 . 2. Задачу минимизации Z можно формально заменить задачей максимизации функции (-Z). Но можно этого не делать. Признаком оптимальности опорного плана задачи минимизации является отсутствие положительных элементов в Zстроке таблицы (1.19). Для выбора разрешающего столбца выбирают максимальный среди положительных коэффициентов cj ( j = r + 1, , n) , а вся остальная вычислительная процедура остается прежней. Геометрически симплекс-метод можно проинтерпретировать следующим образом. Начальному опорному плану соответствует угловая точка многогранника решений (1.17). Шагу симплексного преобразования соответствует переход в соседнюю вершину таким образом, чтобы значение целевой функции не уменьшилось. Пример 1 Решить задачу симплекс-методом и дать геометрическую интерпретацию процесса поиска оптимального решения. Z = x1 + 2x2 → max 2 x1 + 3x2  6  x1  1  x − x  −1  x1  0,2i = 1,2  i Решение: Перейдем к равенствам в системе ограничений: 2 x1 + 3 x2 + x3 = 6  x1 + x4 = 1  x − x − x = −1  x1  0,2i = 1,5 ,5  i Составим расширенную матрицу системы ограничений: 2 3 1 0 0 6   2 3 1 0 0 6 A = 1 0 0 1 0 1   1 0 0 1 0 1.  1 −1 0 0 −1 −1  −1 1 0 0 1 1      В матрице уже имеется базис из столбцов, соответствующих переменным x3, x4 , x5 , переменные x1, x2 – свободные. Выражение для функции содержит 35 только свободные переменные. Из матрицы находим начальное опорное решение X 1 = (0;0;6;1;1), Z ( X 1) = 0 + 2  0 = 0 . Составляем первую симплексную таблицу. Таблица 1 б.п. 1 x1 x2 x3 x4 x5 CO x3 6 2 3 1 0 0 6 / 3 = 2 x4 1 1 0 0 1 0 − x5 1 −1 1 0 0 1 1 / 1 = 1  Z 0 −1 −2 0 0 0  Этой таблице соответствует начальный опорный план X 1 = (0;0;6;1;1), Z ( X 1) = 0 . Он не оптимален, т.к. в Z-строке имеются отрицательные элементы. В качестве разрешающего столбца выбираем столбец, соответствующий x2 , т.к. max(| −1|,| −2 |) = 2 . Отметим его вертикальной стрелкой. Для определения разрешающей строки в дополнительном столбце (заголовок CO) найдем симплексные отношения для положительных элементов разрешающего столбца, и выберем из них минимальное min ( 6 / 3;1 / 1) = min(2;1) = 1 . Откуда следует, что разрешающая строка – третья, отметим ее горизонтальной стрелкой. Выделим разрешающий элемент (он находится на пересечении разрешающей строки и разрешающего столбца). Переходим к новой таблице, выполнив шаг алгоритма симплекс-метода. Таблица 2 б.п. 1 x1 x2 x3 x4 x5 CO x3 3 5 0 1 0 −3 3 / 5 = 0.6  x4 1 1 0 0 1 0 1/1 =1 x2 1 −1 1 0 0 1 − Z 2 −3 0 0 0 2  Пояснение к вычислению элементов таблицы 2: Разрешающий элемент 1. Вместо базисной переменной x5 пишем x2 . Элементы разрешающей строки делим на 1. Остальные элементы столбца с заголовком x2 заполняем нулями (т.к. x2 стала базисной переменной). Столбцы, соответствующие базисным переменным x3, x4 , не изменяются. На месте не заполненных ранее элементов столбца с заголовком x5 пишем элементы столбца с заголовком x2 , деленные на разрешающий элемент, и взятые с противоположным знаком. Остальные элементы пересчитываем по правилу прямоугольников: 36 1 3 −1  3 =3 2→2− =5 1 1 1 0 −1  0 1→1− =1 1→1− =1 1 1 1  (−2) −1  (−2) 0→0− = 2 −1 → −1 − = −3 1 1 Таблице 2 соответствует опорное решение X 2 = (0;1;3;1;0), Z ( X 1) = 2 . Оно не оптимально, т.к. в Z-строке имеется отрицательный элемент. В качестве разрешающего столбца выбираем столбец, соответствующий x1 . Отметим его вертикальной стрелкой. Найдем симплексные отношения для положительных элементов разрешающего столбца, и выберем из них минимальное отношение min ( 3 / 5;1 / 1) = min(0.6;1) = 0.6 . Откуда следует, что разрешающая строка – первая. Выделим разрешающий элемент. Переходим к новой таблице, выполнив еще один шаг алгоритма симплекс-метода. Таблица 3 б.п. 1 x1 x2 x3 x4 x5 x1 3 / 5 1 0 1 / 5 0 −3 / 5 x4 2 / 5 0 0 −1 / 5 1 3 / 5 x2 8 / 5 0 1 1 / 5 0 2 / 5 Z 19 / 5 0 0 3 / 5 0 1 / 5 Пояснение к вычислению элементов таблицы 3: Разрешающий элемент 5. Вместо базисной переменной x3 пишем x1 . Элементы разрешающей строки делим на 5. Остальные элементы столбца с заголовком x1 заполняем нулями (т.к. x1 стала базисной переменной). Столбцы, соответствующие базисным переменным x2 , x4 , не изменяются. На месте не заполненных ранее элементов столбца с заголовком x3 пишем элементы столбца с заголовком x1 , деленные на разрешающий элемент 5, и взятые с противоположным знаком. 1→-1/5; -1→-(-1)/5=1/5; -3→-(-3)/5=3/5. Остальные элементы пересчитываем по правилу прямоугольников: 3 1 −3  1 1→1− =2/5 0→0− =3/5 5 5 3  (−1) −3  (−1) 1→1− =8/5 1→1− =2/5 5 5 3  (−3) −3  (−3) 2→2− = 19 / 5 2 → 2 − =1/ 5 5 5 Таблице 3 соответствует опорное решение X 3 = (3 / 5;8 / 5;0;2 / 5;0) , 6→6− Z ( X 1) = 19 / 5 . Оно оптимально, т.к. в Z-строке нет отрицательных элементов. Окончательно, Zmax = Z (3 / 5,8 / 5) = 19 / 5 . Решим исходную задачу графически. 37 (2) х1 = 1 х1 1 x2 (1) 2х1 + 3х2 = 6 х1 3 x2 2 (3) х1 - х2 = -1 х1 -1 x2 1 1 2 На рис. 9 демонстрируется процесс графического решения данной задачи. Построим прямые, ограничивающие полуплоскости, определяемые неравенствами системы. Каждая прямая разбивает плоскость на две полуплоскости. Для выбора полуплоскостей, определяемых каждым неравенством, подставим координаты «пробной» точки (0;0) в каждое неравенство. Получаем: 20 +3 0 ≤ 6 верно. Следовательно, отмечаем полуплоскость, содержащую «пробную» точку (0;0). 0 ≤ 1 верно. Следовательно, отмечаем полуплоскость, содержащую «пробную» точку (0;0). 0 – 0  -1 верно. Следовательно, отмечаем полуплоскость, не содержащую «пробную» точку (0;0). Выбранные полуплоскости отметим стрелочками. Найдем пересечение отмеченных полуплоскостей с учетом условия: х1,х2  0. Заштрихуем полученный четырехугольник ОABC. Построим линию уровня Z = 0: х1 + 2х2 = 0. х1 x2 Вектор 2 -1 grad Z = (1;2) определяет направление наибольшего возрастания функции Z. Построим из начала координат вектор N = grad Z = (1;2) . Перемещая линию уровня параллельным переносом в направлении вектора N , находим последнюю точку пересечения линии уровня и заштрихованного пятиугольника – точку B. Эта точка является точкой максимума функции. Рис. 9. Графическое решение задачи из примера 1 38 Точка B получается в результате пересечения прямых (1) и (3). Для нахождения ее координат решим систему: 2 x1 + 3x2 = 6 +  x1 − x2 = −1 3 5x1 = 3  x1 = 3 / 5 x2 = x1 + 1 = 3 / 5 + 1 = 8 / 5 Z max = Z ( 3 / 5;8 / 5 ) = 3 / 5 + 2  8 / 5 = 19 / 5 Сделаем сопоставление решения задачи симплекс-методом с графическим решением. Составим таблицу: Номер таблицы Опорное таблицы решение из Значение функции 1 X 1 = (0;0;6;1;1) 2 X 2 = (0;1;3;1;0) 2 A 3 X 3 = (3 / 5;8 / 5;0;2 / 5;0) 19/5 B Точка на графике O Из приведенной таблицы видно, что опорным решениям симплексных таблиц соответствуют вершины многогранника и при переходе от одной симплексной таблице к другой осуществляется переход по ребру в соседнюю вершину таким образом, что значение функции увеличивается.  Пример 2 Решить задачу симплекс-методом. Z = 25x1 − 16 x2 − 10 x3 + x4 + x5 → max −2 x1 + x2 + x3 = 4 3x1 − 8 x2 + x4 = 24 x + x + x = 9  x1  0,2i = 1,5 ,5  i Составим расширенную матрицу системы ограничений:  −2 1 1 0 0 4  A =  3 −8 0 1 0 24  . 1 1 0 0 1 9   В матрице уже имеется базис из столбцов, соответствующих переменным x3, x4 , x5 , переменные x1, x2 – свободные. В правой части нет отрицательных коэффициентов, следовательно, матрице соответствует опорное решение. Выражение для функции содержит не только свободные переменные, но и базисные. Выразим базисные переменные через свободные и подставим их в целевую функцию.  x3 = 4 + 2 x1 − x2  x4 = 24 − 3x1 + 8 x2 x = 9 − x − x 2  x5  0, i =11, ,5  i 39 Z = 25 x1 − 16 x2 − 10(4 + 2 x1 − x2 ) + 24 − 3x1 + 8 x2 + 9 − x1 − x2 = 25 x1 − 16 x2 − −40 − 20 x1 + 10 x2 + 24 − 3 x1 + 8 x2 + 9 − x1 − x2 = −7 + x1 + x2 Составляем первую симплексную таблицу. Таблица 1 б.п. 1 x1 x2 x3 x4 x5 CO x3 4 −2 1 1 0 0 − x4 24 3 −8 0 1 0 8  x5 9 1 1 0 0 1 9 Z −7 −1 −1 0 0 0  Этой таблице соответствует начальный опорный план X 1 = (0;0;4;24;9), Z ( X 1) = −7 . Он не оптимален, т.к. в Z-строке имеются отрицательные элементы. В качестве разрешающего столбца выбираем столбец, соответствующий x1 . Переходим к новой таблице с разрешающим элементом во второй строке. Таблица 2 б.п. 1 x1 x2 x3 x4 x5 CO x3 20 0 −13 / 3 1 2 / 3 0 − x1 8 1 −8 / 3 0 1 / 3 0 − x5 1 0 11 / 3 0 −1 / 3 1 3 / 11 Z 1 0 −11 / 3 0 1 / 3 0  Таблице 2 соответствует опорное решение X 2 = (8;0;20;0;1), Z ( X 1) = 1 . Оно не оптимально, т.к. в Z-строке имеется отрицательный элемент. В качестве разрешающего столбца выбираем столбец, соответствующий x2 . Таблица 3 б.п. 1 x1 x2 x3 233 / 11 0 0 x1 96 / 11 1 0 x2 3 / 11 0 1 Z 2 1 0 x3 x4 x5 CO 1 3 / 11 13 / 11 233 / 3  0 1 / 11 8 / 11 96 0 −1 / 11 3 / 11 − −11 / 3  Таблице 3 соответствует опорное решение X 3 = (96 / 11;3 / 11;233 / 11;0;0), Z ( X 3 ) = 2 . Оно оптимально. Но в Z-строке имеется нулевой элемент в столбце с заголовком свободной переменной x4 . Следовательно, задача имеет бесконечно много решений (альтернативный оптимум). В качестве разрешающего столбца выбираем столбец, соответствующий x4 . Тем самым будет найдена вторая вершина многогранника решений, соответствующая оптимальному решению. 40 Таблица 4 б.п. 1 x1 x2 x3 x4 x5 x4 233 / 3 0 0 11 / 3 1 13 / 3 x1 5/3 1 0 −1 / 3 0 1 / 3 x2 22 / 3 0 1 1 / 3 0 2 / 3 Z 2 1 0 1 Таблице 4 соответствует опорное решение X 4 = (5 / 3;22 / 3;0;233 / 3;0), Z ( X 4 ) = 2 . Оно также оптимально. Оптимальными будут все точки отрезка с концами X3 и X4. Координаты этих точек можно представить в виде  X 3 + (1 −  ) X 4 =  (96 / 11;3 / 11;233 / 11;0;0) + (1 −  )(5 / 3;22 / 3;0;233 / 3;0) = = (5 / 3 + (96 / 11 − 5 / 3);22 / 3 + (3 / 11 − 22 / 3);233 / 11;233 / 3 − 233 / 3 ) = = (5 / 3 + 233 / 33;22 / 3 − 233 / 33;233 / 11;233 / 3 − 233 / 3 ), 0    1. Zmax = Z (5 / 3 + 233 / 33;22 / 3 − 233 / 33;233 /11;233 / 3 − 233 / 3) = 2, 0    1.  Пример 3 Решить задачу симплекс-методом, используя в качестве начальной угловой точки опорное решение с базисными переменными x2 , x3, x4 , полученное методом жордановых исключений. Z = − x1 − x2 − x3 − x4 + 4x5 → min 3x1 + x2 + x3 − 6 x5 = 7 2 x1 + x2 + 3x3 + 3x4 − 7 x5 = 10 −3 x + x + x − 6 x = 1  x 10, i =2 1, 3,5 4  i Заведем новую функцию Z = − Z = x1 + x2 + x3 + x4 − 4 x5 → max . Выпишем расширенную матрицу системы.  3 1 1 0 −6 7  A =  2 1 3 3 −7 10  .  −3 1 1 −6 0 1    В матрице не выделен базис, поэтому необходимо выполнить жордановы преобразования для включения в базис переменных x2 , x3, x4 . Поскольку выражение для целевой функции содержит все переменные, а после нахождения опорного решения необходимо будет выразить ее через свободные переменные, то при преобразованиях матрицы методом жордановых исключений заведем строку для функции Z (коэффициенты при неизвестных будем записывать с противоположными знаками) и будем над ней также выполнять жордановы исключения. 3 1 1 0 −6 7 2 1 3 3 −7 10 −3 1 1 −6 0 1 −1 −1 −1 −1 4 0 41 Для включения переменной x2 в базис, необходимо выбрать разрешающий элемент во втором столбце. Находим min(7 / 1;10 / 1;1 / 1) = 1 , следовательно, разрешающий элемент находится в третьей строке. Выполним шаг жордановых преобразований. 6 0 0 6 −6 6 5 0 2 9 −7 9 −3 1 1 −6 0 1 −4 0 0 −7 4 1 Для включения в базис переменной x3 необходимо выбрать разрешающий элемент в третьем столбце. Находим min(9 / 2;1 / 1) = 1 , следовательно, разрешающий элемент находится в третьей строке, но у нас уже есть столбец единичной матрицы с единицей в третьей строке. Попробуем включить в базис переменную x4 . Для включения переменной x4 в базис, необходимо выбрать разрешающий элемент в четвертом столбце. Находим min(6 / 6;9 / 9) = 1 , следовательно, разрешающий элемент находится в первой строке. Выполним шаг жордановых преобразований. 1 0 0 1 −1 1 −4 0 2 0 2 0 3 1 1 0 −6 7 3 0 0 0 −3 8 Снова попробуем включить в базис переменную x3 , для этого необходимо выбрать разрешающий элемент в третьем столбце. Находим min(0 / 2;7 / 1) = 0 , следовательно, разрешающий элемент находится во второй строке. Выполним шаг жордановых преобразований. 1 0 0 1 −1 1 −2 0 1 0 1 0 5 1 0 0 −7 7 3 0 0 0 −3 8 Базис выделен. В правой части нет отрицательных коэффициентов, следовательно, матрице соответствует опорное решение, оно является вырожденным (базисная переменная x3 равна 0). Составляем симплексную таблицу. Таблица 1 б.п. 1 x1 x2 x3 x4 x5 CO x4 1 1 0 0 1 −1 − x3 0 −2 0 1 0 1 0  x2 7 5 1 0 0 −7 − Z 8 3 0 0 0 −3  Таблице 1 соответствует начальный опорный план X 1 = (0;7;0;1;0), Z ( X 1) = 8 . Он не оптимален, т.к. в Z-строке имеется отрицательный элемент. В качестве 42 разрешающего столбца выбираем столбец, соответствующий x5 . Переходим к новой таблице с разрешающим элементом во второй строке. Таблица 2 б.п. 1 x1 x2 x3 x4 x5 СО x4 1 −1 0 1 1 0 − x5 0 −2 0 1 0 1 − x2 7 −9 1 7 0 0 − Z 8 −3 0 3 0 0  Таблице 2 соответствует опорный план X 2 = (0;7;0;1;0), Z ( X 2 ) = 8 . Он не оптимален, т.к. в Z-строке имеется отрицательный элемент. В качестве разрешающего столбца выбираем столбец, соответствующий x1 . Но в этом столбце нет положительных элементов, откуда заключаем, что функция Z не ограничена сверху, следовательно, функция Z не ограничена снизу. 1.11. Вырожденные решения и правило устранения зацикливания При нахождении решения задачи линейного программирования мы предполагали, что задача имеет опорные планы и каждый такой план является невырожденным. Если задача имеет вырожденный опорный план, то на одной из итераций симплекс-метода одна или несколько базисных переменных опорного плана могут оказаться равными нулю. Появление вырожденного решения объясняется присутствием в задачи избыточного ограничения. В этом случае, при переходе от вырожденного опорного плана к другому опорному плану значение функции изменяться не будет, это значение функция может сохранять в течении нескольких итераций. Более того, может произойти возврат к ранее найденному базису. Такой возврат называется зацикливанием. Если количество базисных переменных, равных 0, в опорном решении небольшое количество (1-3), то зацикливаний не возникает. Если же таких переменных много, то можно избежать возникновение зацикливаний, если применять правило Креко. Правило заключается в следующем: если в выбранном разрешающем столбце есть несколько одинаковых минимальных симплексных отношений, то элементы этих строк делятся на предполагаемые разрешающие элементы, и за разрешающую строку принимается та строка, в которой раньше встретится наименьшее частное. Пример Решить задачу линейного программирования. Z = 2 x1 + 4 x2 → max −2 x1 + x2  6 − x1 + 3 / 2 x2  9 − x1 + 5 x2  30  x1 + x2  12  xi  0, i = 1,2 Перейдем к канонической форме записи задачи. 43 Z = 2 x1 + 4 x2 → max −2 x1 + x2 + x3 = 6 −  x1 + 3 / 2 x2 + x4 = 9 − x1 + 5 x2 + x5 = 30  x1 + x2 + x6 = 12  xi  0, i = 1, ,6 1 0 0 0 6   −2 1 − 1 3 / 2 0 1 0 0 9 .  Расширенная матрица системы: A =  −1 5 0 0 1 0 30  1 1 0 0 1 12   В матрице уже имеется базис из столбцов, соответствующих переменным x3, x4 , x5 , x6 , переменные x1, x2 – свободные. В правой части нет отрицательных коэффициентов, следовательно, матрице соответствует опорное решение. Составляем симплексную таблицу: Таблица 1 б.п. 1 x1 x2 x3 x4 x5 x6 CO x3 6 −2 1 1 0 0 0 6  x4 9 −1 3 / 2 0 1 0 0 6 x5 30 −1 5 0 0 1 0 6 x6 12 1 1 0 0 0 1 12 Z 0 −2 −4 0 0 0 0  Таблице 1 соответствует начальный опорный план X 1 = (0;0;3;6;9;12), Z ( X 1) = 0 . Он не оптимален, т.к. в Z-строке имеются отрицательные элементы. В качестве разрешающего столбца выбираем столбец, соответствующий x2 . Получили 3 одинаковых минимальных симплексных отношения. Применяем правило Креко. Находим min(−2; −2 / 3; −1 / 5) = −2 . Переходим к новой таблице с разрешающим элементом в первой строке. Таблица 2 б.п. 1 x1 x2 x3 x4 x5 x6 CO x2 6 −2 1 1 0 0 0 − x4 0 2 0 −3 / 2 1 0 0 0  x5 0 9 −5 0 1 0 x6 6 3 −1 0 0 1 2 Z 24 −10 0 4 0 0 0  Таблице 2 соответствует вырожденный опорный план X 2 = (0;6;0;0;0;6), Z ( X 2 ) = 24 . Он не оптимален, т.к. в Z-строке имеется отрицательный элемент. В качестве разрешающего столбца выбираем столбец, соответствующий x1 . Получили 2 одинаковых минимальных симплексных отношения. Применяем правило Креко. Находим min(−3 / 4; −5 / 9) = −3 / 4 . Переходим к новой таблице с разрешающим элементом во второй строке. 44 Таблица 3 б.п. 1 x1 x2 x2 6 0 1 x1 0 1 0 x5 0 0 0 x6 6 0 0 Z 24 0 0 x3 x4 x5 −1 / 2 1 −3 / 4 1 / 2 7 / 4 −9 / 2 1 5 / 4 −3 / 2 0 −7 / 2 5  x6 1 CO − − 0  24 / 5 Таблице 3 соответствует вырожденный опорный план X 3 = (0;6;0;0;0;6), Z ( X 3 ) = 24 . Он не оптимален, т.к. в Z-строке имеется отрицательный элемент. В качестве разрешающего столбца выбираем столбец, соответствующий x3 . Разрешающий элемент находится в третьей строке. Переходим к новой таблице с разрешающим элементом в третьей строке. Таблица 4 б.п. 1 x1 x2 x3 x4 x5 x6 CO x2 6 0 1 0 −2 / 7 2 / 7 0 − x1 0 1 0 0 −10 / 7 3 / 7 0 − x3 0 0 0 1 −18 / 7 4 / 7 0 − x6 6 0 0 0 12 / 7 −5 / 7 1 7 / 2  Z 24 0 0 0 −4 2  Таблице 4 соответствует вырожденный опорный план X 4 = (0;6;0;0;0;6), Z ( X 4 ) = 24 . Он не оптимален, т.к. в Z-строке имеется отрицательный элемент. В качестве разрешающего столбца выбираем столбец, соответствующий x4 . Разрешающий элемент находится в четвертой строке. Переходим к новой таблице с разрешающим элементом в четвертой строке. Таблица 5 б.п. 1 x1 x2 x3 x4 x5 x6 x2 7 0 1 0 0 1/ 6 1/ 6 x1 5 1 0 0 0 −1 / 6 5 / 6 x3 9 0 0 1 0 −1 / 2 3 / 2 x4 7 / 2 0 0 0 1 −5 / 12 7 / 12 Z 38 0 0 0 0 1/ 5 7/3 Таблице 5 соответствует оптимальное решение X 5 = (5;7;9;7 / 2;0;0), Z ( X 5 ) = 38 . Zmax = Z (5;7) = 38 . Рассмотрим геометрическую интерпретацию процесса решения. Из рис. 10 видно, что ограничения 1 и 2 избыточны. Именно это привело к тому, что трем шагам симплекс-метода (табл.2-4) соответствовала одна и та же точка (0;6). 45 Рис. 10. Графическая интерпретация решения из примера  1.12. Метод искусственного базиса (М-метод) В примере предыдущего пункта начальное опорное решение было найдено из матрицы исходной системы, т.к. она уже была приведена к единичному базису с неотрицательной правой частью. Рассмотрим, как получить начальный опорный план в общем случае. Пусть задача линейного программирования представлена в канонической форме (1.15), (1.16), все правые части уравнений (1.16) неотрицательны (bi  0, i = 1,2, , m) , и матрица системы ограничений не приведена к единичному базису или приведена частично. Неотрицательности правых частей уравнений можно добиться, умножив обе части уравнений, не удовлетворяющих этому условию, на -1. Базис будем создавать искусственным образом за счет введения в каждое уравнение новой (искусственной) переменной. Введение искусственных переменных приводит к появлению новой задачи, называемой расширенной задачей или М-задачей. Алгоритм построения М-задачи 1. В левую часть каждого ограничения добавляется своя искусственная неотрицательная переменная. Тогда каждое уравнение системы может быть разрешено относительно введенной искусственной переменной. При этом будет получен начальный опорный план, в котором все искусственные переменные будут базисными, а исходные переменные задачи – свободными. Система ограничений М-задачи будет иметь вид: a 11 x1 + a12 x2 + + a1n xn + xn +1 = b1   (1.21)  a x + a x + + a x + x = b mn n n+m m  m1 1 m 2 2  x1, x2 , , xn + m  0 46 2. В целевой функции М-задачи должен накладываться штраф за использование искусственных переменных, поэтому она будут иметь вид: (1.22) Z = c1x1 + c2 x2 + + cn xn − М ( xn +1 + + xn + m ) → max, где М – достаточно большое число. В этом случае, если хотя бы одна искусственная переменная будет отлична от 0, то значение целевой функции будет очень маленьким, поэтому в оптимальном решении должно выполняться xn+1 + + xn+m = 0 , откуда из условия неотрицательности искусственных переменных следует xn+1 = = xn+m = 0 . Задача (1.21), (1.22) называется М-задачей, для нее сразу находится начальный опорный план (0, ,0 , b1, , bm ) . Далее эту задачу можно решать n нулей симплекс-методом. Замечания: 1. Если какое-либо уравнение системы (1.16) может быть разрешено относительно «естественной» базисной переменной, то искусственная переменная в это уравнение не вводится. 2. Если в исходной задаче целевая функция минимизируется, то в М-задаче минимизируется функция, имеющая вид: Z = c1x1 + c2 x2 + + cn xn + М ( xn +1 + + xn + m ) → min, где М – большое положительное число. Получение оптимального опорного плана исходной задачи (М-метод) основано на следующих теоремах. Теорема 13 Если в оптимальном плане М-задачи искусственные переменные равны 0 (оптимальное решение имеет вид ( x1*, , xn* ,0, ,0) ), то план ( x1*, , xn* ) является оптимальным для исходной задачи. Теорема 14 Если в оптимальном плане М-задачи хотя бы одна из искусственных переменных xn+1, , xn+m положительна, то система ограничений (1.16) исходной задачи не совместна. Теорема 15 Если М-задача не имеет решения (функция не ограничена), то исходная задача не разрешима (либо не ограничена функция, либо система ограничений не совместна). Как уже было отмечено выше, М-задача решается симплекс-методом, но есть особенности в оформлении симплекс-таблиц. Рассмотрим эти особенности: 1. Целевой функции М-задачи соответствуют 2 строки: в первой из них хранятся коэффициенты функции Z (Z-строка), а во второй – коэффициенты при переменных, определяемые слагаемыми, содержащими множитель М (М-строка). 2. Признак оптимальности сначала проверяют по М-строке, игнорируя Z-строку. В случае неоптимальности опорного решения выбор разрешающего столбца также определяется по М-строке. 47 3. По мере исключения из базиса искусственных переменных, соответствующие им столбцы исключаются из дальнейшей работы (вычеркиваются), т.к. обратно в базис эти переменные возвращаться не будут. 4. Итерационный процесс по М-строке ведется до тех пор, пока: − либо все искусственные переменные будут исключены из базиса, при этом все элементы М-строки станут равны 0, и М-строку можно вычеркнуть, далее задача решается обычным симплекс-методом; − либо не все искусственные переменные будут исключены из базиса, при этом М-строка не содержит отрицательных элементов, тогда система ограничений исходной задачи не совместна. Пример 1 Решить задачу линейного программирования методом искусственного базиса. Z = −2x1 − 6x2 + 5x3 − x4 − 4x5 → max  x1 − 4 x2 + 2 x3 − 5 x4 + 9 x5 = 3  x2 − 3 x3 + 4 x4 − 5 x5 = 6 x − x + x − x = 1  x2  0,3i = 1,4 ,55  i Решение Составим расширенную матрицу системы ограничений:  1 −4 2 −5 9 3  A  0 1 −3 4 −5 6  .  0 1 −1 1 −1 1    В матрице первый столбец уже включен в базис, поэтому искусственные переменные будут вводиться только во второе и третье уравнение. Составим М-задачу. Z = −2 x1 − 6 x2 + 5 x3 − x4 − 4 x5 − М ( x6 + x7 ) → max  x1 − 4 x2 + 2 x3 − 5 x4 + 9 x5 = 3  x2 − 3 x3 + 4 x4 − 5 x5 + x6 = 6 x − x + x − x + x = 1  x2  0,3i = 1,4 ,75 7  i Выразим базисные переменные x1, x6 , x7 и целевую функцию через свободные x2 , x3, x4 , x5 и составим симплексную таблицу.  x1 = 3 + 4 x2 − 2 x3 + 5 x4 − 9 x5  x6 = 6 − x2 + 3 x3 − 4 x4 + 5 x5 x = 1 − x + x − x + x 3 4 5  x7  0, i =21, ,7  i Z = −2 x1 − 6 x2 + 5 x3 − x4 − 4 x5 − М ( x6 + x7 ) = −2(3 + 4 x2 − 2 x3 + 5 x4 − 9 x5 ) − −6 x2 + 5 x3 − x4 − 4 x5 − M (6 + x2 + 3x3 − 4 x4 + 5 x5 + 1 − x2 + x3 − x4 + x5 ) = = −6 − 14 x2 + 9 x3 − 11x4 + 14 x5 + M (−7 + 2 x2 − 4 x3 + 5 x4 − 6 x5 ) Симплексная таблица М-задачи: 48 б.п. 1 x1 x2 x3 x4 x5 x6 x7 CO x1 3 1 −4 2 −5 9 0 0 − x6 6 0 1 −3 4 −5 1 0 3 / 2 x7 1 0 1 −1 1 −1 0 1 1  Z −6 0 14 −9 11 −14 0 0 M −7 0 −2 4 −5 6 0 0  Таблице соответствует начальное опорное решение М-задачи (3;0;0;0;0;6;1) и значение функции Z = −6 − 7M . Решение не оптимально, т.к. в М-строке имеются отрицательные коэффициенты. Выберем в качестве разрешающего столбца – столбец с заголовком x4 и выполним симплексное преобразование таблицы. При этом искусственная переменная x7 исключается из базиса, поэтому столбец с заголовком x7 в новой таблице не пишем. б.п. 1 x1 x2 x3 x4 x5 x6 CO x1 8 1 1 −3 0 4 0 − x6 2 0 −3 1 0 −1 1 2  x4 1 0 1 −1 1 −1 0 − Z −17 0 3 2 0 −3 0 M −2 0 3 −1 0 1 0  Таблице соответствует опорное решение М-задачи (8;0;0;1;0;2;0) и значение функции Z = −17 − 2M . Решение не оптимально, т.к. в М-строке имеется отрицательный элемент. Выберем в качестве разрешающего столбца – столбец с заголовком x3 и выполним симплексное преобразование таблицы. При этом искусственная переменная x6 исключается из базиса, поэтому столбец с заголовком x6 в новой таблице не пишем. б.п. 1 x1 x2 x3 x4 x5 CO x1 14 1 −8 0 0 1 14  x3 2 0 −3 1 0 −1 x4 3 0 −2 0 1 −2 Z −21 0 9 0 0 −1 M 0 0 0 0 0  В базисе больше нет искусственных переменных, поэтому коэффициенты Мстроки равны 0, и ее можно вычеркнуть. Новой таблице соответствует начальное опорное решение исходной задачи (14;0;2;3;0) и значение функции Z = −21. Решение не оптимально, т.к. в Z-строке имеется отрицательный элемент. Выбираем разрешающий элемент в столбце с заголовком x5 и делаем еще одно симплексное преобразование. 49 б.п. 1 x1 x2 x3 x4 x5 x5 14 1 −8 0 0 1 x3 16 1 −11 1 0 0 x4 31 2 −18 0 1 0 Z −7 1 1 0 0 0 Новой таблице соответствует оптимальное опорное решение исходной задачи (0;0;16;31;14) и значение функции Zmax = Z (0;0;16;31;14) = −7 . Пример 2 Решить задачу линейного программирования методом искусственного базиса. Z = x1 + x2 → max  x1 + x2  1  x1 − x2  2  x1, x2  0 Решение Перейдем к равенствам в системе ограничений:  x1 + x2 + x3 = 1  x1 − x2 − x4 = 2  xi  0, i = 1, ,4 Составим расширенную матрицу системы ограничений: A= 1 1 1 0 1 1 −1 0 −1 2 В матрице третий столбец уже включен в базис, поэтому искусственная переменная будет вводиться только во второе уравнение. Составим М-задачу. Z = x1 + x2 − Mx5 → max   x1 + x2 + x3 = 1  x1 − x2 − x4 + x5 = 2   xi  0, i = 1, ,5 Выразим базисные переменные x3, x5 и целевую функцию через свободные x1, x2 , x4 и составим симплексную таблицу.   x3 = 1 − x1 − x2  x5 = 2 − x1 + x2 + x4   xi  0, i = 1, ,5 Z = x1 + x2 − Мx5 = x1 + x2 − M (2 − x1 + x2 + x4 ) = x1 + x2 + M (−2 + x1 − x2 − x4 ) → max ( ) 50 Симплексная таблица М-задачи: б.п. 1 x1 x2 x3 x4 x5 CO x3 1 1 1 1 0 0 1  x5 2 1 −1 0 −1 1 2 Z 0 −1 −1 0 0 0 M −2 −1 1 0 1 0  Таблице соответствует начальное опорное решение М-задачи (0;0;1;0;2) и значение функции Z = −2M . Решение не оптимально, т.к. в М-строке имеется отрицательный коэффициент. Выберем в качестве разрешающего столбца – столбец с заголовком x1 и выполним симплексное преобразование таблицы. При этом преобразовании искусственная переменная x5 остается в базисе. б.п. 1 x1 x2 x3 x4 x5 x1 1 1 1 1 0 0 x5 1 0 −2 −1 −1 1 Z 1 0 0 1 0 0 M −1 0 0 1 1 0 Таблице соответствует опорное решение М-задачи (1;0;0;0;1) и значение функции Z = 1 − M . Решение оптимально, т.к. в М-строке отсутствуют отрицательные коэффициенты. Т.к. искусственная переменная осталась в базисе, то исходная задача не имеет решения (система ограничений не совместна). Сделаем чертеж области допустимых решений исходной задачи. Рис. 11. Область допустимых решений примера пуста 1.13. Двойственные задачи Рассмотрим задачу использования сырья. Для изготовления двух видов продукции P1, P2 предприятие использует 4 вида сырья S1, S2, S3, S4. Запасы сырья и расходы на изготовление каждого вида продукции приведены в таблице. Составить план производства, при котором стоимость выпущенной продукции будет максимальной. 51 Сырье Запасы S1 S2 S3 S4 20 16 30 40 Расход на единицу продукции P1 P2 3 2 4 1 3 4 Стоимость единицы продукции (у.е.) 10 6 Для составления математической модели задачи введем две переменные: x1 – количество произведенной продукции P1 и x2 – количество произведенной продукции P2. По определению эти переменные должны быть неотрицательны. При производстве продукции предприятие израсходует 2x1+3x2 единиц сырья S1, 2x1+x2 единиц сырья S2, 3x2 единиц сырья S3 и 4x2 единиц сырья S4. Предприятие не может израсходовать сырья больше, чем у него имеется, поэтому получаем следующие ограничения на использование имеющегося сырья: 3x1 + 2 x2  20 4 x1 + x2  16 3x2  30 4 x1  40 От продажи выпущенной продукции предприятие получит 10x1+6x2 у.е. Получаем математическую модель задачи: Z ( x1, x2 ) = 10 x1 + 6 x2 → max 3 x1 + 2 x2  20 4 x + x  16  1 2 3 x2  30 4 x  40  1  x1, x2  0 Предположим, что по некоторым обстоятельствам потребитель отказался от заказа, и предприятие решило продать сырье, не выпуская продукцию. По каким ценам будет продаваться сырье? Составим математическую модель новой задачи. Введем три переменные: y1 − стоимость единицы сырья S1, y2 − стоимость единицы сырья S2, y3 − стоимость единицы сырья S3, y4 − стоимость единицы сырья S4. По определению эти переменные должны быть неотрицательны. Предприятию имеет смысл не выпускать продукцию только в случае, если выручка от продажи сырья не меньше, чем стоимость произведенной из этого сырья продукции. На производство одной единицы продукции P1 расходуется 3 единицы сырья S1, 4 единицы сырья S2 и 4 единицы сырья S4. Если не выпускать 52 продукцию P1, а продать все сырье, из которого его можно изготовить, то выручка от реализации этого сырья составит 3 y1 + 4 y2 + 4 y4 . Аналогично, выручка от реализации сырья, из которого можно изготовить продукцию P2, составит 2 y1 + y2 + 3 y3 . Выручка от продажи сырья должна быть не меньше стоимости единицы соответствующей продукции. Получаем ограничения: 3 y1 + 4 y2 + 4 y4  10 2 y1 + y2 + 3 y3  6 С другой стороны, покупатель сырья хочет купить это сырье как можно дешевле. На покупку сырья будет затрачено 20 y1 + 16 y2 + 30 y3 + 40 y4 у.е. Получаем математическую модель задачи: W ( y1, y2 , y3, y4 ) = 20 y1 + 16 y2 + 30 y3 + 40 y4 → min 3 y1 + 4 y2 + 4 y4  10  2 y1 + y2 + 3 y3  6 y , y , y , y  0  1 2 3 4 Составленная задача называется двойственной к исходной. Как видно из построенных моделей, кроме экономической связи между ними существует и математическая связь. Перечислим условия, связывающие построенные задачи. 1. Цели задач противоположны: в исходной задаче функция максимизируется, а в двойственной минимизируется. 2. Количество переменных двойственной задачи соответствует количеству ограничений исходной задачи. 3. Коэффициенты при неизвестных в целевой функции исходной задачи являются правыми частями в ограничениях двойственной задачи и, наоборот, правые части ограничений исходной задачи являются коэффициентами при неизвестных в целевой функции двойственной задачи. 4. Матрица коэффициентов при неизвестных в системе ограничений двойственной задачи является транспонированной матрицей коэффициентов при неизвестных в системе ограничений исходной задачи. 5. Знаки неравенств задач противоположны: все неравенства исходной задачи имеют знак «», а двойственной «». x1 x2 y1 y2 y3 y4  3 2 4 1  3 4 0 4   2 1 3 0  0 3      4 0 6. Переменные обеих задач неотрицательны. Рассмотрим правила построения двойственной задачи в общем случае. Пусть имеется задачи линейного программирования в общем виде: (1.23) Z = c1x1 + c2 x2 + + cn xn → max 53 a11x1 + a12 x2 + + a1n xn  b1 ..............................................  yk ak1x1 + ak 2 x2 + + akn xn  bk  (1.24) yk +1 ak +1,1x1 + ak +1,2 x2 + + ak +1, n xn = bk +1 ...................................................  ym am1x1 + am 2 x2 + + amn xn = bm   xi  0 ( i = 1, , l ; l  n ) Каждой такой задаче можно поставить в соответствие двойственную задачу: (1.25) W = b1y1 + b2 y2 + + bm ym → min. x1 a11 y1 + a21 y2 + + am1 ym  c1 ..............................................  xi a1l y1 + a2l y2 + + aml ym  cl  (1.26) xl +1 a1,l +1 y1 + a2,l +1 y2 + + am,l +1 ym = cl +1 ...................................................  xn a1n y1 + a2n y2 + + amn yn = cn  y  0 ( j = 1, , k , k  m ) ,  j y1 Алгоритм построения двойственной задачи 1. Сначала производится согласование цели исходной задачи и неравенств ее системы ограничений. Если целевая функция максимизируется, то все знаки неравенств должны быть «», если целевая функция минимизируется, то все знаки неравенств должны быть «». Если какое-нибудь неравенство не соответствует цели задачи, то его следует домножить на -1 для смены знака на противоположный. 2. Каждому i-му ограничению системы исходной задачи соответствует переменная yi двойственной задачи и, наоборот, каждому j-му ограничению системы двойственной задачи соответствует переменная xi исходной задачи. Подпишем эти соответствия слева от систем. 3. Коэффициенты при неизвестных в целевой функции двойственной задачи совпадают с правыми частями системы ограничений исходной задачи. 4. Цель двойственной задачи противоположна цели исходной задачи. 5. Матрица системы ограничений двойственной задачи получается транспонированием из матрицы системы ограничений исходной задачи; 6. Коэффициенты правых частей двойственной задачи – это коэффициенты при неизвестных в целевой функции исходной задачи. 7. Знаки ограничений двойственной задачи могут быть либо неравенствами, соответствующими цели двойственной задачи, либо равенствами. Неравенство ставится в случае, если на переменную исходной задачи, соответствующую ограничению двойственной задачи, наложено условие неотрицательности. Если 54 такого условия нет, то соответствующее ограничение двойственной задачи – уравнение. 8. На переменную yj двойственной задачи следует наложить условие неотрицательности лишь в том случае, если i-е ограничение исходной задачи – неравенство. Замечание: Если по алгоритму построить двойственную задачу к двойственной, то получим исходную задачу. Поэтому исходную и двойственную задачу называют парой взаимно двойственных задач. Пример 1 Построить двойственную для следующей задачи. Z = 5x1 + 4 x2 + 6 x3 → max  x1 + x2 + x3  6 2 x − x + 3x  9  1 2 3  3 x1 + x2 + 2 x3 = 11  x1, x3  0 Решение: Согласуем знаки неравенств с целью задачи. Целевая функция максимизируется, поэтому все неравенства должны быть «». Второе неравенство не согласовано с целью функции, умножим его обе части на -1.  x1 + x2 + x3  6 −2 x + x − 3x  −9  1 2 3  3 x1 + x2 + 2 x3 = 11  x1, x3  0 В системе имеется 3 ограничения, поэтому в двойственной задаче будет 3 переменные, подпишем эти переменные слева от ограничений. y1  x1 + x2 + x3  6 y2 −2 x1 + x2 − 3 x3  −9  y3 3 x1 + x2 + 2 x3 = 11  x1, x3  0 Матрица левой части системы ограничений исходной задачи: x1 x2 x3 1 1 1 A =  −2 1 −3   3 1 2   Матрица левой части системы ограничений двойственной задачи: 55 y1 y2 y3 T 1 1 1 1 −2 3   T  A =  −2 1 −3  = 1 1 1   3 1 2 1 −3 2      Двойственная задача: W = 6 y1 − 9 y2 + 11y3 → min x1  y1 − 2 y2 + 3 y3  5 x2  y1 + y2 + y3 = 4  x3  y1 − 3 y2 + 2 y3  6  y1, y2  0 Второе ограничение является уравнением, т.к. на переменную x2 не наложено условие неотрицательности. На переменную y3 не наложено условие неотрицательности, т.к. соответствующее y3 ограничение исходной задачи – уравнение.  В силу того, что все три формы записи задачи линейного программирования (общая, симметричная, каноническая) эквиваленты, далее будем рассматривать пару симметричных взаимно двойственных задач (1.27), (1.28) и (1.29), (1.30). (1.27) Z = c1x1 + c2 x2 + + cn xn → max a11x1 + a12 x2 + + a1n xn  b1 ..............................................  (1.28)  am1x1 + am 2 x2 + + amn xn  bm  xi  0 ( i = 1, , n ) W = b1y1 + b2 y2 + + bm ym → min a11 y1 + a21 y2 + + am1 ym  c1 ..................................................  a y + a y + + a y  c mn n n  1n 1 2n 2  y j  0 ( j = 1, , m ) Следующие теоремы двойственных задач. дают (1.29) (1.30) зависимости между решениями пары Теорема 16 (Основное неравенство теории двойственности) Пусть X = ( x1, , xn ) и Y = ( y1, , ym ) - допустимые решения пары двойственных задач в симметричной форме. Тогда, W (Y )  Z ( X ) . Доказательство: W (Y ) = b1 y1 + = (a11 y1 + + bm ym  (a11x1 + am1 ym ) x1 + + (a1n y1 + a1n xn ) y1 + + (am1x1 + amn ym ) xn  c1x1 + 56 amn xn ) ym = + cn xn = Z ( X ) Следовательно, W (Y )  Z ( X ) . Теорема 17 (Достаточный признак оптимальности решения) Пусть X * = ( x1*, , xn* ) и Y * = ( y1*, , ym* ) - допустимые решения пары двойственных задач и W (Y * ) = Z ( X * ) . Тогда, X*, Y* – оптимальные решения этих задач. Доказательство: Пусть X* – не оптимальное решение, тогда существует допустимое решение X такое, что Z ( X )  Z ( X *) = W (Y *) . Получили противоречие теореме 16. Следовательно, X* – оптимальное решение. Пусть Y* – не оптимальное решение, тогда существует допустимое решение Y такое, что W (Y )  W (Y *) = Z ( X *) . Получили противоречие теореме 16. Следовательно, Y* – оптимальное решение. Теорема 18 (О минимаксе) Если одна из пары двойственных задач имеет решение, то и другая имеет решение, причем Zmax = Wmin . Если одна из пары двойственных задач имеет неограниченную функцию, то система ограничений второй задачи не совместна. Теорема 19 (Равновесия) Пусть X * = ( x1*, , xn* ) и Y * = ( y1*, , ym* ) допустимые планы пары двойственных задач в симметричной форме. Эти планы являются оптимальными тогда и только тогда, когда выполняются следующие условия дополняющей нежесткости (1.31).  y*  b − a x* + + a x*  = 0 11 1 1n n   1  1 ................................................   y*  b − a x* + + a x*  = 0 m1 1 mn n   m  m (1.31)  * * *  x1   a11 y1 + + am1 ym − c1  = 0    ................................................  *  xn*   a1n y1* + + amn ym − cn  = 0     ( ) ( ) ( ) ( ) Теорема 19 позволяет определить оптимальное решение одной из пары двойственных задач по решению другой. Если ограничение одной задачи при подстановке оптимального решения обращается в строгое неравенство, то соответствующая двойственная переменная в оптимальном решении двойственной задачи равна 0. Если в оптимальном плане одной задачи какаянибудь переменная положительна, то соответствующее ей ограничение двойственной задачи является уравнением. В случае если одна из пары двойственных задач содержит две переменных, ее можно решить графически, а, затем, найти решение двойственной задачи, используя Теоремы 18 и 19. 57 Пример 2 Решив графически двойственную задачу, найти решение исходной по теореме равновесия. Z = 10x1 − 9x2 − 19x3 − 13x4 − 11x5 → max  x2 − 2 x3 + 2 x4 − 2 x5  4  −2 x1 + 2 x2 + 2 x3 + 2 x4 + x5  2 ,   xi  0, i = 1,5 Решение: Построим двойственную задачу. Сначала согласуем знаки неравенств с целью исходной задачи. Z = 10x1 − 9x2 − 19x3 − 13x4 − 11x5 → max y1  x2 − 2 x3 + 2 x4 − 2 x5  4  y2 2 x1 − 2 x2 − 2 x3 − 2 x4 − x5  −2  x  0, i = 1,2,3,4,5  i Двойственная задача согласно алгоритму: W = 4 y1 − 2 y2 → min x1 2 y2  10  x2  y1 − 2 y2  −9 x3 −2 y1 − 2 y2  −19  x4 2 y1 − 2 y2  −13 x5 −2 y1 − y2  −11   y1, y2  0 Составим уравнения прямых, ограничивающих полуплоскости, определяемых неравенствами системы ограничений. (1) 2y2 = 10 (2) y1 - 2y2 = -9 (3) -2y1 – 2y2 = -19 y1 1 y1 -3 y1 9.5 y2 5 5 y2 4.5 3 y2 9.5 (4) 2y1 - 2y2 = -13 y1 -6.5 y2 6.5 (5) -2y1 - y2 = -11 y1 3 y2 5 5.5 Построим линию уровня W = 0: 4y1 – 2y2 = 0 y1 2 y2 4 Вектор grad W = (4; −2) определяет направление наибольшего возрастания функции W. 58 Рис. 12. Графическое решение двойственной задачи из примера 2 Точка минимума получается в результате пересечения прямых (1) и (2). Для нахождения ее координат решим систему: 2 y2 = 10 y = 5  2   y1 − 2 y2 = −9  y1 = 1 Wmin = W (1;5 ) = 4  1 − 2  5 = −6 Найдем оптимальное решение исходной задачи по теореме равновесия. Запишем условия дополняющей нежесткости.  y1(4 − ( x2 − 2 x3 + 2 x4 − 2 x5 )) = 0  y (−2 − (2 x − 2 x − 2 x − 2 x − x )) = 0 1 2 3 4 5  2  x1(2 y2 − 10) = 0   x2 ( y1 − 2 y2 + 9) = 0  x (−2 y − 2 y + 19) = 0 1 2  3  x4 (2 y1 − 2 y2 + 13) = 0  x (−2 y − y + 11) = 0 1 2  5 Подставим в составленную систему оптимальное решение двойственной задачи: y1 = 1, y2 = 5 . 59 1  (4 − ( x2 − 2 x3 + 2 x4 − 2 x5 )) = 0 5  (−2 − (2 x − 2 x − 2 x − 2 x − x )) = 0 1 2 3 4 5   x1(2  5 − 10) = 0   x2 (1 − 2  5 + 9) = 0  x (−2  1 − 2  5 + 19) = 0  3  x4 (2  1 − 2  5 + 13) = 0  x (−2  1 − 5 + 11) = 0  5 Произведение равно нулю, если один из множителей равен 0. Получаем, 4 − ( x2 − 2 x3 + 2 x4 − 2 x5 ) = 0 −2 − (2 x − 2 x − 2 x − 2 x − x ) = 0 1 2 3 4 5   x1  0 = 0   x2  0 = 0 x  7 = 0  x = 0 3  3  x4  5 = 0  x4 = 0 x  4 = 0  x = 0 5  5 Тогда, x2 = 4 x =4  2 2 x1 − 2 x2 = −2 x1 = 3 Оптимальное решение исходной задачи Zmax = Z (3;4;0;0;0) . По Теореме 18 Zmax = Wmin = −6 . Окончательно, Zmax = Z (3;4;0;0;0) = −6 .   Пример 3 Составить двойственную задачу к задаче из примера 2 раздела 1.8 и найти ее решение по теореме равновесия. Решение: Z ( x1, x2 ) = 120 x1 + 160 x2 → min  x1 + 3 x2  12 5 x1 + 4 x2  31 2 x + 3 x  18  x ,1x  02  1 2 В разделе 1.8 было найдено графически решение этой задачи: Z min = Z ( 3;4 ) = 1000 . Составим двойственную задачу. Знаки неравенств уже согласованы с целью задачи. 60 Z ( x1, x2 ) = 120 x1 + 160 x2 → min y1  x1 + 3 x2  12 y2 5 x1 + 4 x2  31 y3 2 x1 + 3 x2  18 x , x  0  1 2 Двойственная задача: W ( y1, y2 , y3 ) = 12 y1 + 31y2 + 18 y3 → max x1   y1 + 5 y2 + 2 y3  120 x2 3 y1 + 4 y2 + 3 y3  160   y1, y2 , y3  0 Найдем оптимальное решение двойственной задачи по теореме равновесия. Запишем условия дополняющей нежесткости.  y1( x1 + 3x2 − 12) = 0  y2 (5 x1 + 4 x2 − 31) = 0  y3 (2 x1 + 3x2 − 18) = 0  x1(120 − ( y1 + 5 y2 + 2 y3 )) = 0  x2 (160 − (3 y1 + 4 y2 + 3 y3 )) = 0 Подставим в составленную систему оптимальное решение исходной задачи: x1 = 3, x2 = 4 .  y1(3 + 3  4 − 12) = 0  y2 (5  3 + 4  4 − 31) = 0  y3 (2  3 + 3  4 − 18) = 0 3  (120 − ( y1 + 5 y2 + 2 y3 )) = 0 4  (160 − (3 y1 + 4 y2 + 3 y3 )) = 0 Произведение равно нулю, если один из множителей равен 0. Получаем  y1  3 = 0  y1 = 0  y2  0 = 0  y3  0 = 0 120 − ( y1 + 5 y2 + 2 y3 ) = 0 160 − (3 y1 + 4 y2 + 3 y3 ) = 0 Тогда, 120 − (0 + 5 y2 + 2 y3 ) = 0 160 − (3  0 + 4 y2 + 3 y3 ) = 0  − 120 3 54yy ++ 23yy == 160 2 2 2 3 3 7 y2 = 40  y2 = 40 7 40 120 − 5 y2 7 = 320 y3 = = 2 2 7 Оптимальное решение двойственной задачи Wmax = W (0;40 / 7;320 / 7) . По Теореме 18 Окончательно, Zmin = Wmax = 1000 . Wmax = W (0;40 / 7;320 / 7) = 1000 . 120 − 5  61 1.14. Двойственный симплекс-метод Пусть имеется пара симметричных двойственных задач (1.27), (1.28) и (1.29), (1.30). Перейдем к каноническим формам записи задач. (1.32) Z = c1x1 + c2 x2 + + cn xn → max y1 a11x1 + a12 x2 + + a1n xn + xn +1 = b1 ............................................................  (1.33)  ym am1x1 + am 2 x2 + + amn xn + xn + m = bm  xi  0 ( i = 1, , n + m ) W = b1y1 + b2 y2 + + bm ym → min x1 a11 y1 + a21 y2 + + am1 ym − ym +1 = c1 ..................................................   xm a1n y1 + a2n y2 + + amn yn − ym + n = cn  y j  0 ( j = 1, , m + n ) (1.34) (1.35) В п.1.13 было показано, что для получения решения исходной задачи можно перейти к двойственной и по оптимальному плану двойственной задачи найти решение исходной задачи. Можно заметить, что построение самой двойственной задачи не обязательно, так как при рассмотрении симплексной таблицы задачи (1.32), (1.33) легко заметить, что в столбцах записана исходная задача, а в строках – двойственная. При этом оценками плана исходной задачи являются коэффициенты Z-строки cij , оценками плана двойственной задачи – коэффициенты столбца свободных членов bi . Поэтому оптимальный план двойственной задачи можно находить, используя симплексные таблицы исходной задачи. При решении симплекс-методом все коэффициенты в столбце свободных членов должны были быть неотрицательны, а в Z-строке допускались отрицательные коэффициенты, которые в процессе решения преобразовывались в неотрицательные. Поскольку в двойственной задаче столбец свободных членов и Z-строка меняются местами, то можно допустить, что в Z-строке все коэффициенты неотрицательны, а в столбце свободных членов могут быть отрицательные коэффициенты. Тогда при выполнении симплексных преобразований необходимо преобразовывать коэффициенты столбца свободных членов в неотрицательные. Симплексная таблица, в которой все коэффициенты Z-строки неотрицательны, а в столбце свободных членов имеются отрицательные, называется двойственно допустимой, а соответствующее ей базисное решение – псевдопланом. К двойственно допустимой таблице применим алгоритм двойственного симплекс-метода. Двойственный симплекс-метод используется, если первоначальное базисное решение не является опорным. 62 Алгоритм двойственного симплекс-метода 1. В столбце свободных членов среди отрицательных элементов выбирают максимальный по модулю. Соответствующая строка будет разрешающей. 2. Для отрицательных элементов разрешающей строки находят симплексные отношения: модули отношений элементов Z-строки к отрицательным элементам разрешающей строки. Эти отношения записывают в дополнительную строку внизу симплексной таблицы. Если в разрешающей строке нет отрицательных элементов, то задача не имеет решения. 3. Среди симплексных отношений находят минимальное, соответствующий столбец будет разрешающим. 4. На пересечении разрешающей строки и разрешающего элемента находится разрешающий элемент. 5. Выполняют симплексное преобразование таблицы по тем же правилам, что и для обычной симплексной таблицы. 6. Если в столбце свободных членов есть отрицательные, то переходят к п.1. Если отрицательных элементов нет, то решение оптимально. Алгоритм двойственного симплекс-метода часто используют, если после решения задачи возникает какое-то дополнительное ограничение, которое следует учесть в задаче. Для того, чтобы не решать задачу по-новому, можно добавить ограничение в последнюю симплекс-таблицу и решать ее двойственным симплекс-методом. Пример Решить задачу линейного программирования. Z = x1 + x2 + 2 x3 → max  x1 + x2 + x3 = 8 x − x  4  1 2 ,  x + 2 x  6 1 2   xi  0, i = 1,2,3 Решение: Запишем задачу в канонической форме: Z = x1 + x2 + 2 x3 → max  x1 + x2 + x3 = 8 x − x − x = 4  1 2 4   x1 + 2 x2 − x5 = 6  xi  0, i = 1, ,5 Расширенная матрица системы: 1 1 1 0 0 8   1 1 1 0 0 8  1 −1 0 −1 0 4   −1 1 0 1 0 −4  . 1 2 0 0 −1 6   −1 −2 0 0 1 −6      Переменные x3, x4 , x5 – базисные, x1, x2 – свободные. Выразим базисные переменные и функцию через свободные переменные. 63  x3 = 8 − ( x1 + x2 )  x = −4 − (− x + x )  4 1 2   x5 = −6 − (− x1 − 2 x2 )  xi  0, i = 1,2,3,4,5 Z = x1 + x2 + 2(8 − x1 − x2 ) = 16 − x1 − x2 → max Составим симплексную таблицу. б.п. 1 x1 x2 x3 x4 x5 x3 8 1 1 1 0 0 x4 −4 −1 1 0 1 0 x5 −6 −1 −2 0 0 1  Z 16 1 1 0 0 0 CO 1 1/ 2  Таблица является двойственно допустимой. Ей соответствует псевдоплан X 1 = (0;0;8; −4; −6) . Т.к. в столбце свободных членов имеются отрицательные элементы, то строим следующую таблицу согласно алгоритму двойственного симплекс-метода. б.п. 1 x1 x2 x3 x4 x5 x3 5 1/ 2 0 1 0 1/ 2 x4 −7 −3 / 2 0 0 1 1 / 2  x2 3 1/ 2 1 0 0 −1 / 2 Z 13 1 / 2 0 0 0 1/ 2 CO 1/ 3 −  Таблица является двойственно допустимой. Ей соответствует псевдоплан X 2 = (0;3;5; −7;0) . Т.к. в столбце свободных членов имеются отрицательные элементы, то строим следующую таблицу согласно алгоритму симплекс-метода. б.п. 1 x1 x2 x3 x4 x5 x3 8 / 3 0 0 1 1/ 3 2 / 3 x1 14 / 3 1 0 0 −2 / 3 −1 / 3 x2 2 / 3 0 1 0 1 / 3 −1 / 3 Z 32 / 3 0 0 0 1 / 3 2 / 3 Таблице соответствует оптимальный план X 3 = (14 / 3;2 / 3;8 / 3;0;0) максимальное значение функции Zmax = 32 / 3 . и 2. Специальные задачи линейного программирования 2.1. Целочисленные задачи линейного программирования. Метод Гомори При решении многих задач линейного программирования на искомые переменные по их физическому смыслу необходимо наложить дополнительные условия целочисленности. Это может быть, когда искомыми величинами являются неделимые объекты, например, количество станков, комплектов оборудования и т.п. 64 Можно предположить, что решение задачи целочисленного программирования можно получить из решения соответствующей ей задачи линейного программирования округлением нецелых компонент ее оптимального плана. Но на практике это оказывается далеко не так. В качестве примера рассмотрим следующую задачу: Z = x1 + 2x2 → max 5 x1 − 4 x2  0   x1 + 4 x2  12  x  0, целые, i = 1,2  i Решив данную задачу без учета условий целочисленности, получим оптимальный план X * = (2;2.5), Zmax = 7 . Полученное решение не является целочисленным, но при попытке округления как в большую, так и в меньшую сторону, получим точки (2;2) или (2;3), которые не принадлежат области допустимых решений. Оптимальным решением исходной задачи является точка (0;3), которая не могла быть получена округлением точки (2;2.5). Поэтому разработаны специальные методы решения таких задач. Методы решения задач целочисленного программирования можно разделить на 3 основные группы. 1. Методы отсечения. Опишем общую идею таких методов. Для отыскания решения используется многоэтапный процесс. Сначала задача решается без условия целочисленности. Если полученное в результате решение будет целочисленным, то исходная задача решена. Если нет, то к ограничениям задачи, решенной на предыдущем этапе, добавляется еще одно линейное ограничение, обладающее следующими двумя свойствами: а) оно должно отсекать найденный оптимальное нецелочисленное решение; 2) оно не должно отсекать ни одного допустимого целочисленного решения. Такое дополнительное ограничение называется правильным отсечением. После этого задача решается с учетом добавленного ограничения. В случае, если решение и этой задачи не будет целочисленным, добавляется еще одно линейное ограничение, являющееся правильным отсечением. Решается новая задача линейного программирования и т.д., до получения целочисленного решения. Методы отсечения можно геометрически прокомментировать на примере задач, содержащих две переменные. Добавление каждого правильного отсечения к ограничениям задачи соответствует построению прямой, отсекающей от многоугольника решений некоторую часть вместе с вершиной, соответствующей нецелочисленному оптимальному решению, при этом не затрагивая ни одной из целочисленных точек области допустимых решений. 2. Комбинаторные методы. Поскольку число допустимых решений задачи целочисленного программирования конечно, то в принципе возможен их полный перебор. Общая идея комбинаторных методов состоит в направленном переборе, при котором 65 рассматриваются лишь те из них, которые по некоторым признаком оказываются перспективными, с одновременным отбрасыванием бесперспективных. 3. Приближенные методы. Методы отсечения и комбинаторные методы позволяют получить точное решение задачи за конечное число шагов. Но даже для не очень больших задач скорость сходимости этих методов оказывается недостаточной. Поэтому на практике оправдано использование приближенных методов, учитывающих специфику конкретной задачи. Эти методы используют как детерминированные алгоритмы, так и алгоритмы случайного поиска. Это позволяет, с одной стороны, упростить поиск решений, а, с другой стороны, ограничивает сферу применения методов. Метод Гомори является одним из методов отсечения, основан на симплексметоде и использует достаточно простой способ построения правильного отсечения. Сначала дадим определения. Целой частью числа a (обозначается  a  ), называется наибольшее целое число, не превосходящее a . Дробной частью числа a (обозначается a ) называется разность между числом a и его целой частью, т.е. a = a −  a  (расстояние до ближайшего целого, расположенного слева от a ). Дробная часть всегда неотрицательна. Пример 1 3.8 = 3, 3.8 = 0.8, 1.2 = 1, 1.2 = 0.2,  −5.7 = −6, −5.7 = 0.3, −3.2 = −4, −3.2 = 0.8 Пусть задача линейного программирования представлена в канонической форме: (2.1) Z = c1x1 + c2 x2 + + cn xn → max a 11 x1 + a12 x2 + + a1n xn = b1   (2.2)  a x + a x + + a x = b m 1 1 m 2 2 mn n m   x1, x2 , , xn  0, целые Алгоритм метода Гомори 1. Отбросив условие целочисленности, решить задачу симплекс-методом. Если получим целочисленный оптимальный план, то задача решена. Иначе переходим к шагу 2. 2. Для нецелочисленной компоненты решения составить дополнительное ограничение. Пусть для определенности это будет компонента с номером i0. Тогда ограничение будет иметь вид: ai01 x1 + ai0 2 x2 + + ai0n xn  bi0 , (2.3)            где ai0 j , bi0 – дробные части соответствующих коэффициентов. 66 Если в оптимальном плане нецелочисленные значения принимают несколько переменных, то дополнительное неравенство (2.3) определяется базисной переменной с наибольшей дробной частью (это ускоряет процесс получения оптимального целочисленного решения). 3. Добавить неравенство (2.3) к системе ограничений ранее решенной задачи. При этом новая задача решается двойственным симплекс-методом. Для этого в (2.3) необходимо перейти к равенству, введя дополнительную переменную xn+1  0 , которая будет являться базисной. После решения новой задачи двойственным симплекс-методом, переходят к первому этапу. Через конечное число шагов будет найдено оптимальное целочисленное решение или установлена неразрешимость задачи. Пример 2 Решить задачу: Z = x1 + 2x2 → max 3x1 + x2  7  x1 + 3x2  7  x1, x2  0, целые Решение: Перейдем к канонической форме записи задачи: Z = x1 + 2x2 → max  3x1 + x2 + x3 = 7  x1 + 3x2 + x4 = 7   x1, x2 , x3 , x4  0, целые ( ) Расширенная матрица системы ограничений: 3 1 1 0 7 . 1 3 0 1 7 Переменные x3 , x4 – базисные, x1, x2 – свободные. Правая часть неотрицательна, поэтому базисное решение будет опорным. Решим задачу без условия целочисленности. Симплексная таблица: б.п. 1 x1 x2 x3 x4 CO x3 7 3 1 1 0 7 x4 7 1 3 0 1 7 / 3  Z 0 −1 −2 0 0  Таблице соответствует неоптимальное опорное решение значение функции б.п. 1 x1 x3 14 / 3 8 / 3 x2 7 / 3 1 / 3 Z 14 / 3 −1 / 3  Z ( X 1) = 0 . Переходим к новой таблице: x2 x3 x4 CO 0 1 −1 / 3 7 / 4  1 0 1/ 3 7 0 0 2/3 67 X 1 = (0;0) и Таблице соответствует неоптимальное опорное решение X 2 = (0;7 / 3) и значение функции Z ( X 2 ) = 14 / 3 . Переходим к новой таблице: б.п. 1 x1 x2 x3 x4 x1 7 / 4 1 0 3 / 8 −1 / 8 x2 7 / 4 0 1 −1 / 8 3 / 8 Z 21 / 4 0 0 1 / 8 5 / 8 Таблице соответствует оптимальное нецелочисленное 3 решение 3 X = (7 / 4;7 / 4) и значение функции Z ( X ) = 21/ 4 . Найдем дробные части нецелочисленных базисных переменных: 7 / 4 = 3 / 4, 7 / 4 = 3 / 4 . Так как дробные части обоих базисных одинаковы, то отсечение Гомори можно строить по любой из двух строк. Выберем первую строку (подчеркнем ее) и составим дополнительное ограничение Гомори, используя строку для базисной переменной x1. Тогда отсечение Гомори будет определяться неравенством: {1}x1 + 3 / 8 x3 + −1 / 8 x4  7 / 4 . Найдем дробные части: {1} = 0,3 / 8 = 3 / 8, −1 / 8 = 7 / 8 . Ограничение примет вид: Перейдем к равенству: 3 / 8x3 + 7 / 8x4  3 / 4 . 3 / 8x3 + 7 / 8x4 − x5 = 3 / 4, x5  0 . Умножим обе части уравнения на -1: −3 / 8x3 − 7 / 8x4 + x5 = −3 / 4, x5  0 , и добавим новое ограничение в последнюю симплексную таблицу. б.п. 1 x1 x2 x3 x4 x5 x1 7/4 1 0 3 / 8 −1 / 8 0 x2 7 / 4 0 1 −1 / 8 3 / 8 0 x5 −3 / 4 0 0 −3 / 8 −7 / 8 1  Z 21 / 4 0 0 1/ 8 5/8 0 CO 1/ 3 5/7  Полученная таблица является двойственно допустимой. Разрешающий элемент выберем в соответствии с алгоритмом двойственного симплекс-метода. Разрешающая строка – третья, для нее находим симплексные отношения и выбираем минимальное. Переходим к новой таблице: б.п. 1 x1 x2 x3 x4 x5 x1 1 1 0 0 −1 1 x2 2 0 1 0 2 / 3 −1 / 3 x3 2 0 0 1 7 / 3 −8 / 3 Z 5 0 0 0 1/ 3 1/ 3 Таблице соответствует оптимальное целочисленное решение X * = (1;2) и ц значение функции Zmax = Z ( X *) = 5 . Графическая интерпретацию отсечения в рассмотренном примере приведена на рис. 13. 68 Рис.13 Интерпретация отсечения Гомори Область допустимых решений исходной задачи – четырехугольник OABC. Оптимальному нецелочисленному решению X 3 на рисунке соответствует вершина B. Составленное дополнительное ограничение 3 / 8x3 + 7 / 8x4  3 / 4 необходимо выразить через переменные x1, x2 . Предварительно умножим обе части на 8. Получаем: 3x3 + 7 x4  6 3(7 − 3x1 − x2 ) + 7(7 − x1 − 3x2 )  6 21 − 9 x1 − 3x2 + 49 − 7 x1 − 21x2  6 16x1 + 24x2  64 2 x1 + 3x2  8 Зеленая прямая соответствует границе полуплоскости, определяемого новым ограничением. Эта прямая отсекла от области допустимых решений нецелочисленную вершину B. Область допустимых решений новой задачи с учетом ограничений – пятиугольник ОADEC. Оптимальному целочисленному решению X * соответствует на рисунке точка D.  69 Пример 3 Решить задачу: Z = 2 x1 → max 3x1 + x2  6 5 x1 − x2  9  x1, x2  0, целые Решение: Перейдем к канонической форме записи задачи: Z = 2 x1 → max  3x1 + x2 + x3 = 6 5 x1 − x2 + x4 = 9   x1, x2  0, целые ( ) Расширенная матрица системы ограничений: 3 1 1 0 6 . 5 −1 0 1 9 Переменные x3 , x4 – базисные, x1, x2 – свободные. Правая часть неотрицательна, поэтому базисное решение будет опорным. Решим задачу без условия целочисленности. Симплексная таблица: б.п. 1 x1 x2 x3 x4 CO x3 6 3 1 1 0 2 x4 9 5 −1 0 1 9 / 5  Z 0 −2 0 0 0  Таблице соответствует неоптимальное опорное решение X 1 = (0;0) и значение функции Z ( X 1) = 0 . Переходим к новой таблице: б.п. 1 x1 x2 x3 x4 CO x3 3 / 5 0 8 / 5 1 −3 / 5 3 / 8  x1 9 / 5 1 −1 / 5 0 1 / 5 − Z 18 / 5 0 −2 / 5 0 2 / 5  Таблице соответствует неоптимальное опорное решение X 2 = (9 / 5;0) и значение функции Z ( X 2 ) = 18 / 5 . Переходим к новой таблице: б.п. 1 x1 x2 x3 x4 x2 3 / 8 0 1 5 / 8 −3 / 8 x1 15 / 8 1 0 1 / 8 1 / 8 Z 15 / 4 0 0 1 / 4 1 / 4 Таблице соответствует оптимальное нецелочисленное решение X 3 = (15 / 8;3 / 8) и значение функции Z ( X 3 ) = 15 / 4 . Найдем дробные части нецелочисленных базисных переменных: 3 / 8 = 3 / 8, 15 / 8 = 7 / 8 . 70 Так как вторая дробная часть больше, то отсечение Гомори будем строить по второй строке (подчеркнем ее пунктиром) и составим дополнительное ограничение Гомори: {1}x1 + 1 / 8 x3 + 1 / 8 x4  15 / 8 . Найдем дробные части остальных элементов: {1} = 0,1 / 8 = 1 / 8, 1 / 8 = 1 / 8 . Ограничение примет вид: 1/ 8x3 + 1/ 8x4  7 / 8 . Перейдем к равенству: 1/ 8x3 + 1/ 8x4 − x5 = 7 / 8, x5  0 . Умножим обе части уравнения на -1 −1/ 8x3 − 1/ 8x4 + x5 = −7 / 8, x5  0 и добавим новое ограничение в последнюю симплексную таблицу. б.п. 1 x1 x2 x3 x4 x5 x2 3/8 0 1 5 / 8 −3 / 8 0 x1 15 / 8 1 0 1/ 8 1/ 8 0 x5 −7 / 8 0 0 −1 / 8 −1 / 8 1  Z 15 / 4 0 0 1/ 4 1/ 4 0 CO 1/ 2 1/ 2  Полученная таблица является двойственно допустимой. Разрешающий элемент выберем в соответствии с алгоритмом двойственного симплекс-метода. Разрешающая строка – третья, для нее находим симплексные отношения и выбираем минимальное. Переходим к новой таблице: б.п. 1 x1 x2 x3 x4 x5 x2 −4 0 1 0 −1 5  x1 1 1 0 0 1 x3 7 0 0 1 1 −8 Z 2 0 0 0 2 CO 1/ 2 −  Полученная таблица является двойственно допустимой. Разрешающий элемент выберем в соответствии с алгоритмом двойственного симплекс-метода. Разрешающая строка – первая, для нее находим симплексные отношения и выбираем минимальное. Переходим к новой таблице: б.п. 1 x1 x2 x3 x4 x5 x4 4 0 −1 0 1 −5 − x1 1 1 0 0 0 1 − x3 3 0 1 1 0 −3  Z 2 0 0 0 0 2  Таблице соответствует оптимальное целочисленное решение X 4 = (1;0) и значение функции Zmax = Z ( X 4 ) = 2 . Но решение может быть не единственным, т.к. в Z-строке имеется 0 в столбце, соответствующем свободной переменной x2. Найдем второй конец отрезка, на котором могут быть целочисленные решения. Разрешающий столбец – второй. 71 б.п. x4 x1 x2 Z 1 x1 7 0 1 1 3 0 2 0 x2 1 x3 x4 −1 1 0 0 1 0 0 0 x5 −8 1 −3 2 Таблице соответствует оптимальное целочисленное решение X 5 = (1;3) и значение функции Zmax = Z ( X 5 ) = 2 . Кроме того, внутри отрезка X 4 X 5 могут быть еще целочисленные точки. Запишем внутреннюю точку отрезка X 4 X 5 : X = (1 −  ) X 4 +  X 5 = (1 −  )(1;0) +  (1;3) = (1;3 ), 0    1 . Очевидно, что при  = 1/ 3 и  = 2 / 3 получаем еще 2 оптимальных целочисленных решения: X 6 = (1;1) и X 7 = (1;2) . Итак, задача имеет 4 оптимальных целочисленных решения: Zmax = Z (1;0) = Z (1;3) = Z (1;1) = Z (1;2) = 2 . 2.2. Транспортная задача Рассмотрим простейшую формулировку транспортной задачи по критерию стоимости. Пусть имеется m пунктов отправления (поставщиков) A1, A2 , , Am , в которых сосредоточены запасы однородного груза в количествах соответственно a1, a2 , , am , и n пунктов назначения (потребителей) B1, B2 , , Bn с потребностями в грузах соответственно b1, b2 , , bn . Известны стоимости перевозок (тарифы) cij (i = 1, , m; j = 1, , n) , связанные с перевозкой единицы груза от поставщика Аi к потребителю Вj. Матрица С размера mn, состоящая из элементов cij , называется матрицей тарифов. Требуется составить план перевозок, который обеспечивал бы при минимальных транспортных издержках удовлетворение спроса всех потребителей за счет распределения всего продукта, сосредоточенного у поставщиков. Обозначим через xij – количество единиц груза, перевозимое от поставщика Ai (i = 1, , m) к поставщику B j ( j = 1, , n) . Матрица X, размера mn, состоящая из элементов, xij называется матрицей перевозок. Информация о транспортной задаче хранится в распределительной таблице. Поставщики A1 A2  Am Потребители B1 c12 c11 x12 x11 c22 c21 x21  cm1 xm1  B2 x22  cm2 xm 2 Bn c1n  x1n c2n  x2n   cmn  xmn 72 Запасы a1 a2  am Потребности b1  b2 bn m Общее количество груза, находящееся у поставщиков, равно  ai , а общая i =1 n потребность в грузах равна  bj . j =1 Составим математическую модель задачи. Функция транспортных издержек: Z = c11x11 + c12 x12 + + c1n x1n + + cm1xm1 + cm2 xm2 + + cmn xmn . Условие, что все запасы должны быть вывезены:   x11 + x12 + + x1n = a1 .....................................   xm1 + xm2 + + xmn = am Условие, что все потребности должны быть удовлетворены:   x11 + x21 + + xm1 = b1 .....................................   x1n + x2n + + xmn = bn Поскольку отрицательные перевозки не имеют реального смысла для данной задачи (обратные перевозки от пунктов назначения в пункты отправления), будем предполагать, что все переменные неотрицательны. xij  0 (i = 1, , m; j = 1, , n) Получаем (2.4), (2.5) – математическую модель транспортной задачи: m n Z =   cij xij → min (2.4) i =1 j =1  n   xij = ai , i = 1, , m  j =1  m (2.5)  xij = b j , j = 1, , n i =1  xij  0 (i = 1, , m; j = 1, , n)   Система ограничений (2.5) содержит m + n уравнений с m  n неизвестными xij . Как видно, транспортная задача является частным случаем задачи линейного программирования и ее можно решать симплекс-методом. Но ввиду специфики этой задачи хранение информации осуществляется не в симплексных таблицах, а распределительных таблицах вида 2.1. В процессе решения задачи осуществляется переход от одной таблицы к другой, содержащий опорный план более близкий к оптимальному. Алгоритм решения транспортной задачи дублирует идею симплекс-метода. 73 Если общая потребность в пунктах назначения равна общим запасам в пунктах отправления, т.е. m n  ai =  b j , i =1 (2.6) j =1 то такая модель транспортной задачи называется закрытой. В противном случае, модель называется открытой. Теорема 1 Условие (2.6) является необходимым и достаточным условием совместности системы (2.5). В случае невыполнения условия (2.6) необходимо осуществить переход к закрытой модели. Следствие 1 Закрытая модель транспортной задачи имеет хотя бы одно опорное решение. Следствие 2 Закрытая модель транспортной задачи имеет оптимальное решение. Алгоритм перехода от открытой к закрытой модели транспортной задачи 1. Если суммарный спрос потребителей больше общего запаса у m поставщиков, т.е. выполнено условие n  ai   b j , i =1 n то вводится фиктивный j =1 m поставщик Am+1 с запасом груза am +1 =  b j −  ai и нулевыми затратами на j =1 i =1 перевозку от Am+1 к любому потребителю. В этом случае в распределительной таблице заводится дополнительная строка. 2. Если суммарный спрос потребителей меньше общего запаса у m поставщиков, т.е. выполнено условие n  ai   b j , i =1 то вводится фиктивный j =1 m n i =1 j =1 потребитель Bn+1 с потребностью в грузе bn +1 =  ai −  b j и нулевыми затратами на перевозку от любого поставщика к потребителю Bn+1. В этом случае в распределительной таблице заводится дополнительный столбец. Введение фиктивного поставщика или потребителя не влияет на целевую функцию задачи, т.к. затраты на дополнительные перевозки равны 0. Теорема 2 Ранг матрицы системы ограничений (2.5) равен m+n-1. Из теоремы 2 следует, что число базисных переменных при приведении системы к разрешенному виду будет m+n-1. В процессе решения транспортной задачи план перевозок будет располагаться в распределительной таблице 2.1. При этом, если переменная xij принимает ненулевое значение, то это значение вписывается в соответствующую 74 клетку распределительной таблицы, при этом такая клетка называется занятой. В противном случае, в соответствующую клетку распределительной таблицы не вписывается ничего, такая клетка называется свободной. Занятые клетки соответствуют базисным переменным опорного плана, а свободные клетки – свободным пременным. Нулевые перевозки могут появится в распределительной таблице только в случае, если опорное решение – вырожденное. Из теоремы 2 следует, что в распределительной таблице должна быть m+n-1 занятая клетка. Теорема 3 Если в системе (2.5) значения ai (i = 1, , m), b j ( j = 1, , n) – целые, то любое опорное решение задачи (2.4), (2.5) – целочисленное. Эта теорема имеет очень важное значение, т.к. для обычной задачи линейного программирования для нахождения целочисленных решений используются специальные методы. Решение транспортной задачи состоит из трех этапов: − определение исходного опорного плана; − оценка этого плана; − переход к следующему опорному плану путем замены одной из базисных переменных на свободную. Циклом в распределительной таблице называется замкнутая ломаная линия, вершины которой находятся в клетках таблицы, звенья располагаются вдоль строк и столбцов, причем в любой вершине соединяются 2 звена: горизонтальное и вертикальное. В циклах могут быть пересечения звеньев, при этом точки самопересечения ломаной вершинами не являются. На рис. 14 приведены примеры циклов. Рис. 14. Примеры циклов в распределительной таблице Теорема 4 Допустимый план транспортной задачи является опорным тогда и только тогда, когда из занятых клеток для этого плана клеток нельзя образовать цикла. 2.2.1 Нахождение начального опорного плана Построения начального опорного плана является первым этапом решения транспортной задачи. Чем лучше начальный план, тем быстрее сможем найти решение. Но как правило, для нахождения лучшего плана используются более сложные методы. Все методы построения начального опорного плана предполагают последовательное заполнение клеток распределительной таблицы значениями перевозок. Различие в методах объясняется лишь принципами, согласно которым выбирается для заполнения очередная клетка таблицы. Общая суть всех методов построения начального опорного плана: − На каждом шаге заполняют только одну клетку поставкой xij таким образом, чтобы либо удовлетворить все потребности потребителя Bj, либо вывести весь 75 груз от поставщика Ai. В первом случае из дальнейшего рассмотрения исключается j-ый столбец, во втором i-ая строка. − Далее рассматривается новая таблица, в которой исключены из рассмотрения строка или столбец и уменьшились потребности в j-ом столбце и i-ой строке на величину поставки xij и процесс повторяется. − Если для выбора заполненных клеток остались клетки, расположенные в одной строке или столбце, то туда записываются остатки по столбцу соответствующих потребителей или остатки по строке соответствующих поставщиков. − Заполненных клеток должно быть m+n-1. − Если на каком-нибудь шаге метода одновременно удовлетворяются все потребности потребителя Bj и вывозится весь груз от поставщика Ai, то опорный план – вырожденный, и в какую-нибудь клетку j-го столбца и i-ой строки заносят нулевую поставку и из дальнейшего рассмотрения исключают и строку, и столбец. Метод северо-западного угла Это самый простой метод. Заполнение таблицы начинается с верхней левой клетки («северо-западный угол»). На каждом шаге для заполнения выбирается клетка, находящаяся справа или снизу от предыдущей. Начальный опорный план в этом методе обычно получается далеким оп оптимального, т.к. не учитывается стоимость перевозок. Пример 1 Найти начальное опорное решения методом северо-западного угла. Поставщики Потребители B1 B4 Запасы B5 8 3 10 4 10 7 9 6 5 7 3 6 4 12 A3 Потребности B3 5 A1 A2 B2 80 50 60 20 50 130 80 50 Решение: Найдем суммарные запасы груза: Суммарные потребности:  ai = 50 + 130 + 80 =260 . b j = 80 + 50 + 60 + 20 + 50 = 260 .  ai = b j  Модель транспортной задачи – закрытая. Найдем начальный опорный план. 76 Потребители Поставщики A1 A2 A3 B1 B2 5 B3 8 – 50 10 30 – 50 – Потребности 80,30,0 3 7 7 – 6 5 – 6 10 4 – – 50 Запасы B5 10 9 3 – B4 4 20 50,0 60,10,0 20,0 12 50 50,0 50,0 130,100,50,0 80,70,50,0 260 260 Порядок заполнения клеток: A1B1, x11 = min(50,80) = 50 , уменьшаем запасы A1 и потребности B1 на 50, исключаем из дальнейшего рассмотрения первую строку (прочеркиваем незаполненные клетки). A2 B1, x21 = min(130,30) = 30 , уменьшаем запасы A2 и потребности B1 на 30, исключаем из дальнейшего рассмотрения первый столбец. A2B2 , x22 = min(100,50) = 50 , уменьшаем запасы A2 и потребности B2 на 50, исключаем из дальнейшего рассмотрения второй столбец. A2B3, x23 = min(50,60) = 50 , уменьшаем запасы A2 и потребности B3 на 50, исключаем из дальнейшего рассмотрения вторую строку. Далее для выбора остались клетки, расположенные в одной (третьей) строке, записываем туда соответствующие остатки по столбцам. A3B3, x33 = 10 , уменьшаем запасы A3 и потребности B3 на 10. A2B4 , x24 = 20 , уменьшаем запасы A2 и потребности B4 на 20. A2B5 , x25 = 50 , уменьшаем запасы A2 и потребности B5 на 50. В таблице должно быть 3+5-1=7 заполненных клеток. Это условие выполнено. Стоимость перевозок при составленном плане: Z = 50  5 + 30 10 + 50  7 + 50  9 + 10  6 + 20  4 + 50 12 = 2090 .  Метод минимальной стоимости Очевидно, выбор пунктов назначения и отправления целесообразно производить, ориентируясь на тарифы перевозок. На каждом шаге метода минимальной стоимости для заполнения выбирается клетка, имеющая наименьший тариф из тех клеток, которые могут быть заполнены на данном этапе. Если таких клеток несколько, то для заполнения выбирается любая из них. План, полученный этим методом, как правило, является более близким к оптимальному, чем методом северо-западного угла. Пример 2 Найти начальное опорное решение задачи примера 1 методом минимальной стоимости. 77 Потребители Поставщики A1 A2 A3 Потребности B1 B2 5 – B3 8 – 10 7 7 – – 4 – 6 – 5 50 6 10 Запасы B5 10 9 3 50 80,0 3 50 – 80 B4 4 20 50,0 60,10,0 20,0 12 – 50,0 50,0 130,80,0 80,30,10,0 260 260 Решение: Порядок заполнения клеток: A1B3, x13 = min(50,60) = 50 , уменьшаем запасы A1 и потребности B3 на 50, исключаем из дальнейшего рассмотрения первую строку. A3B2 , x32 = min(80,50) = 50 , уменьшаем запасы A3 и потребности B2 на 50, исключаем из дальнейшего рассмотрения второй столбец. A3B4 , x34 = min(30,20) = 20 , уменьшаем запасы A3 и потребности B4 на 20, исключаем из дальнейшего рассмотрения четвертый столбец. A2 B5 , x25 = min(130,50) = 50 , уменьшаем запасы A2 и потребности 53 на 50, исключаем из дальнейшего рассмотрения пятый столбец. A3B3, x33 = min(10,10) = 10 , уменьшаем запасы A3 и потребности B3 на 10, при этом одновременно удовлетворяются потребности и вывозятся все запасы, поэтому запишем нулевую поставку в свободную клетку с наименьшим тарифом из клеток 3-ей строки и 3-го столбца – A3B1 , и исключаем из дальнейшего рассмотрения третий столбец. Для выбора осталась одна клетка. A2 B1, x21 = 80 , уменьшаем запасы A2 и потребности B4 на 20. В таблице должно быть 7 заполненных клеток. Это условие выполнено. Полученный опорный план – вырожденный Стоимость перевозок при составленном плане: Z = 50  3 + 80 10 + 50  5 + 0  7 + 50  3 + 10  6 + 20  4 = 1490 . Стоимость перевозок существенно уменьшилась по сравнению с планом, найденным методом северо-западного угла.  Метод Фогеля Для каждой строки и каждого столбца составляются разности между двумя минимальными тарифами. Среди полученных разностей выбирают максимальную, а затем в соответствующей строке или столбце выбирают для заполнения клетку с минимальным тарифом. Если минимальный тариф одинаков для нескольких клеток строки или столбца, то для заполнения выбирают ту клетку, которая соответствует наибольшей разности минимальных тарифов строки или столбца. План, полученный этим методом, близок к оптимальному (обычно – оптимальный). Метод Фогеля используется при незначительном количестве поставщиков и потребителей. 78 Пример 3 Найти начальное опорное решение задачи примера 1 методом Фогеля. Решение: Потребители Поставщики A1 A2 A3 Потребности B1 B2 5 – B3 8 – 7 80,0 2 2 3 3 6 4 – 3 3 3 3 12 – 50,0 60,10,0 20,0 4 – – – 5 50 6 10 4 – 20 3 50 10 9 – Запасы B5 – 7 – 20 3 50 10 60 B4 2 2 2 2 50,0 50,0 1 1 – – 130,80,60,0 1 1 1 3 80,30,20,0 1 2 2 2 260 260 1 1 7 – Порядок заполнения клеток: A3B2 , x32 = min(80,50) = 50 , уменьшаем запасы A3 и потребности B2 на 50, исключаем из дальнейшего рассмотрения первый столбец. A1B3, x13 = min(50,60) = 50 , уменьшаем запасы A1 и потребности B3 на 50, исключаем из дальнейшего рассмотрения первую строку. A2 B5 , x25 = min(130,50) = 50 , уменьшаем запасы A2 и потребности B5 на 50, исключаем из дальнейшего рассмотрения пятый столбец. A3B3, x33 = min(30,10) = 10 , уменьшаем запасы A3 и потребности B3 на 10, исключаем из дальнейшего рассмотрения третий столбец. A2B4 , x24 = min(80,20) = 20 , уменьшаем запасы A2 и потребности B4 на 20, исключаем из рассмотрения четвертый столбец. Далее для выбора остались клетки, расположенные в одном (первом) столбце, записываем туда остатки по соответствующим строкам. A2 B1, x21 = 60 , уменьшаем запасы A2 и потребности B1 на 60. A3B1, x31 = 20 , уменьшаем запасы A3 и потребности B2 на 20. В таблице должно быть 7 заполненных клеток. Это условие выполнено. Полученный опорный план – вырожденный Стоимость перевозок при составленном плане: Z = 50  3 + 60 10 + 20  6 + 50  5 + 20  7 + 50  3 + 10  6 = 1470 . Стоимость перевозок уменьшилась по сравнению с планом, найденным методом минимальной стоимости.  2.2.2 Определение оптимального плана методом потенциалов Общий принцип определения оптимального плана транспортной задачи методом потенциалов аналогичен принципу решения задачи линейного программирования симплекс-методом. Сначала находят начальный опорный 79 план (методом северо-западного угла, минимальной стоимости или Фогеля), а затем его последовательно улучшают до получения оптимального. Составим двойственную задачу к задаче (2.4), (2.5), при этом в двойственной задаче будем использовать переменные ui (i = 1, , m) и v j ( j = 1, , n) , которые назовем соответственно потенциалами поставщиков и потенциалами потребителей. Двойственная задача будет иметь m+n переменных и mn ограничений. m n W =  aiui +  b j v j → max i =1 (2.7) j =1 (2.8) ui + v j  cij (i = 1, , m; j = 1, , n) Заметим, что в двойственной задаче на переменные не наложено условие неотрицательности, т.к. в исходной задаче все ограничения были равенствами. Из теоремы равновесия следует следующая теорема. Теорема 5 (необходимое условие оптимальности опорного плана) Если план перевозок задачи (2.4), (2.5) – оптимален, то ему соответствует система из m+n чисел ui и v j , удовлетворяющая условиям: ui + v j = cij для xij  0 ui + v j  cij для xij = 0 Сформулируем алгоритм проверки опорного плана на оптимальность: 1. Для каждой базисной переменной xij найденного опорного плана составить систему уравнений ui + v j = cij (2.9) и найти ее решение. Будет получена система m+n-1 уравнений с m+n неизвестными. Поскольку в системе уравнений на одно меньше, чем неизвестных, и уравнения линейно независимы, то система имеет бесконечно много решений. Чтобы найти ее частное решение, необходимо одной из переменных придать произвольное значение (обычно полагают u1 = 0 ). Для удобства найденные потенциалы записывают в распределительную таблицу в дополнительные столбцы и строки справа и снизу таблицы. В силу специфики системы уравнений значения переменных находятся последовательно одно за другим по занятым клеткам (если известен для клетки известен один из потенциалов, то второй находим из уравнения (2.9)). 2. Для каждой свободной клетки определяют балансы sij по формуле: (2.10) sij = cij − (ui + v j ) Балансы заносят в нижний правый угол свободных клеток. Если среди чисел sij нет отрицательных, то найденный опорный план является оптимальным. В противном случае план не оптимален, и можно улучшить решение, заполнив одну из клеток с отрицательным балансом. 80 2.2.3 Переход к новому опорному плану, более близкому к оптимальному Как было отмечено выше, неоптимальный опорный план можно улучшить, выбрав для заполнения клетку с отрицательным балансом. Если таких клеток несколько, то для заполнения выбирают клетку с максимальным по модулю отрицательным балансом. Эта клетка определяет переменную, вводимую в базис. Т.к. выбранная клетка присоединяется к занятым, то необходимо освободить одну из занятых клеток. Вспомним определение цикла распределительной таблицы и дадим ряд определений и сформулируем теоремы. Теорема 6 Число вершин в любом цикле – четно. Означенным циклом в распределительной таблице называется цикл, вершинам которого приписаны знаки «+» и «-», чередуясь. Очевидно, что количество «+» равно количеству «-» в цикле и их количество в строке или столбце совпадает. Сдвигом по означенному циклу в распределительной таблице на величину M называется увеличение перевозок в вершинах со знаком «+» и уменьшение перевозок в вершинах со знаком «-» на величину М. Теорема 7 Сдвиг по означенному циклу преобразует допустимое решение транспортной задачи в новое допустимое решение. Циклом пересчета свободной клетки называется означенный цикл, одна из вершин которого находится в выбранной клетке, остальные – в занятых, причем свободной клетке приписан знак «+». На основании теоремы 6 видно, что не имеет значения, в какую сторону от свободной клетки начинать расставлять знаки. Теорема 8 В распределительной таблице для любой свободной летки существует и притом единственный цикл пересчета. Можно сформулировать алгоритм перехода к новому опорному плану, не увеличивающему значение целевой функции: 1. Найти свободную клетку с наибольшим по модулю отрицательным балансом. Если таких клеток несколько, выбирается любая. 2. Для выбранной свободной клетки строят цикл пересчета и осуществляют сдвиг на величину М = min xij , где xij – поставки, помеченные в клетках цикла знаком «-». При этом одна из клеток цикла со знаком «-» должна освободиться. Если могут освободиться несколько клеток, то освобождается одна, а в остальные заносятся нулевые поставки. На рис. 15 изображен сдвиг по циклу пересчета. На рис. 15(а) изображен цикл до сдвига, на рис. 115(б) – после. Перемещаем min(10;15;40) = 10 единиц груза. Рис. 15. Пример сдвига по циклу пересчета 81 2.2.4 Метод потенциалов На основании вышеизложенного следует, что процесс нахождения оптимального решения транспортной задачи методом потенциалов состоит из следующих этапов: 1. Найти начальный опорный план одним из методов: северо-западного угла, минимальной стоимости, Фогеля. При этом число занятых клеток должно быть m+n-1. 2. По занятым клеткам найти потенциалы ui , v j , решив систему (2.9). 3. Для всех свободных клеток найти балансы sij по формуле (2.10). Если среди балансов свободных клеток нет отрицательных, то оптимальное решение найдено. В противном случае перейти к п.4. 4. Среди отрицательных балансов выбрать максимальный по модулю, построить для клетки, которой он соответствует, цикл пересчета, и осуществить сдвиг по циклу пересчета. Перейти на п.2. Замечания: 1. Если в опорном решении имеются балансы свободных клеток, равные 0, то это означает, что решение с такими транспортными затратами не единственно, можно загрузив такую клетку (осуществив сдвиг по циклу пересчета), получить новое решение с такими же транспортными затратами. 2. Если в процессе решения транспортной задачи получен вырожденный опорный план, то может произойти зацикливание. Чтобы избежать этого, необходимо соответствующие нулевые элементы опорного плана заменить сколь угодно малым положительным числом  и решать задачу как невырожденную. В оптимальном плане такой задачи считать  равным нулю. Пример 4 Найти оптимальное решение транспортной задачи из примера 1. Решение: Будем использовать начальный опорный план, найденный методом минимальной стоимости в примере 2. Потребители Поставщики B1 A1 A2 A3 80 – + B2 B3 5 1 10 8 8 7 7 1 3 50 B4 3 50 9 6 10 + B5 10 9 6 – -1 4 20 Запасы ui 50 130 6 80 3 4 5 5 50 12 10 Потребности 80 50 60 20 50 vj 4 3 1 9 260 260 Найдем потенциалы из системы (2.9) и запишем их значения справа и снизу в таблицу. Саму систему выписывать не будем. Будем считать, что u1 = 0 , в 82 распределительной таблице будем находить клетки, для которых известен один из потенциалов, и из уравнения (2.9) находить второй потенциал и далее рассматривать заполненные клетки, расположенные в строке или столбце для найденного потенциала. Порядок вычисления потенциалов: u1 = 0 , в первой строке есть занятая клетка A1B3 , для нее u1 + v3 = 3 , откуда v3 = 3 . В третьем столбце имеется занятая клетка A3B3 , для нее u3 + v3 = 6 , откуда u3 = 3 . Для занятой клетки A3B1 получаем уравнение u3 + v1 = 7 , откуда v1 = 4 . Для занятой клетки A3B2 получаем уравнение u3 + v2 = 3 , откуда v2 = 0 . Для занятой клетки A3B4 получаем уравнение u3 + v4 = 4 , откуда v4 = 1. Для занятой клетки A2 B1 получаем уравнение u2 + v1 = 10 , откуда u2 = 6 . Для занятой клетки A2 B5 получаем уравнение u2 + v5 = 5 , откуда v5 = −1. Найдем балансы свободных клеток по формуле (2.10) и подпишем их в правом нижнем углу свободных клеток зеленым цветом. s11 = 5 − (0 + 4) = 1 s12 = 8 − (0 + 0) = 8 s14 = 10 − (0 + 1) = 9 s15 = 4 − (0 − 1) = 5 s22 = 7 − (6 + 0) = 1 s23 = 9 − (6 + 3) = 0 s24 = 6 − (6 + 1) = −1  0 s35 = 12 − (3 − 1) = 10 Получили один отрицательный баланс s24 , для улучшения плана построим цикл пересчета для клетки A2 B4 . Переместим по циклу пересчета min(80;20) = 0 груза. Новая таблица: Потребители Поставщики B1 A1 A2 A3 B2 5 8 1 10 8 7 7 1 3 60 20 B3 50 B4 B5 3 10 4 9 10 6 5 5 50 6 20 10 Запасы ui 50 130 6 80 3 50 4 12 1 10 Потребности 80 50 60 20 50 vj 4 3 -1 260 260 Таблице соответствует стоимость перевозок Z = 50  3 + 60 10 + 20  6 + 50  5 + 20  7 + 50  3 + 10  6 = 1470 . 83 Найдем потенциалы по заполненным клеткам, затем балансы – для свободных клеток. Отрицательных балансов нет, следовательно, план оптимален. Наличие нулевого баланса свидетельствует о том, что оптимальный план не единственен. Новый оптимальный план можно найти, осуществив сдвиг по циклу пересчета для клетки A2 B3 . 2.3. Задачи теории игр 2.3.1. Основные понятия При решении ряда практических задач в области экономики, политики и военного дела приходится принимать решения в ситуациях, в которых сталкиваются интересы двух или более сторон, которые преследуют противоположные цели, причём результат любого действия каждой из сторон зависит от того, какое действие предпримет противник. Такие ситуации называются конфликтными. Примеры конфликтных ситуаций: − любая ситуация в ходе военных действий; − планирование военных операций; − конкурентная борьба в экономике; − выборы в парламент; − салонные игры (например, шашки, шахматы, карты). Теория игр – математическая теория конфликтных ситуаций, ее цель выработать рекомендации по рациональному образу действий участников конфликтной ситуации. При этом не учитываются элементы риска, просчеты и ошибки игроков. Для математического анализа конфликтной ситуации отбрасывают второстепенные факты и строят формализованную модель конфликтной ситуации – игру. Конфликтные стороны называются игроками. Игра ведется по определенным правилам. Правила игры устанавливают возможные действия игроков, объём сведений каждой стороны о поведении другой, результат, к которому приводит каждая совокупность ходов. Правила определяют так же конец игры, когда больше ходов делать не разрешается. Каждый игрок делает ход – выбор одного из вариантов действий, предусмотренных правилами игры. Ходы бывают личные и случайные. Личный ход – сознательный выбор игроком допустимого действия. Случайный ход – выбор допустимого действия с помощью механизма случайного выбора (например, подбрасывания монеты) и его осуществление. Будем считать, что в конце игры любой игрок получает выигрыш. Можно провести классификацию игр: − По числу игроков: • одного лица (например, пасьянс); • двух лиц – парная игра (например, шахматы); • n лиц – множественная (они делятся на коалиационные, когда несколько лиц могут заключить союз, и бескоалиационные). − По количеству и характеру ходов: • с полной информацией (например, шахматы); 84 • с неполной информацией (например, карты. Большинство игр – игры с неполной информацией). − По количеству ходов: • конечные (у каждого игрока имеется конечное количество ходов); • бесконечные (например, дуэль). − По выигрышу: • с нулевой суммой (парная игра, в которой выигрыш одной стороны равен проигрышу другой); • с ненулевой суммой (например, экономические процессы создают или уничтожают богатство). Стратегией игрока называется совокупность правил, определяющая выбор варианта действий при каждом ходе игрока в зависимости от ситуации, сложившийся в игре. Игра m  n – конечная парная игра, в которой у одного игрока имеется m стратегий, а у второго n стратегий. Далее будем рассматривать парные игры m  n с нулевой суммой. Пусть имеется игра двух игроков A и B. Пусть у игрока A имеется m стратегий A1, A1,…, Am, а у игрока B имеется n стратегий B1, B1,…, Bn. Пусть aij – выигрыш (положительный или отрицательный) игрока A при выборе им стратегии Ai и игроком B стратегии Bj. Если ходы случайные, то aij – математическое ожидание выигрыша игрока A. Платёжной матрицей или, матрицей игры называется матрица следующего вида: B1 B2 A1  a11 a12 A2  a21 a22  Am  am1 am 2 Bn a1n  a2 n   amn  Пример 1 (Игра "Поиск") Игрок A прячется в одном из двух убежищ, а игрок B его ищет. Правила игры: если игрок B находит A, то A платит ему 1 рубль, в противном случае игрок B платит A 1 рубль. Стратегии игроков: игрок A: A1 – спрятаться в убежище № 1, A2 – спрятаться в убежище № 2; игрок B: B1 – искать в убежище № 1, B2 – искать в убежище № 2; Платежная матрица игры: −1 1 . 1 −1 Это игра с неполной информацией. Если игра проводится один раз, то бессмысленно говорить о разумных стратегиях. Любой игрок с одинаковым основанием может применять любую стратегию. Но если игра многократно повторяется, то положение меняется. Если игрок будет придерживаться одной стратегии или чередования стратегий в определённой последовательности, то ( ) 85 противник догадается об этом и начнёт выигрывать. Поэтому от верного проигрыша игроков может спасти только случайное чередование стратегий. Например, игрок перед своим ходом подбрасывает монету и, если выпала "решка", то игрок выбирает первую стратегию, а если "орёл", то вторую. Оптимальной стратегией называется стратегия, которая при многократном повторении игры обеспечивает игроку максимально возможный средний выигрыш. 2.3.2. Нижняя и верхняя цены игры. Принцип минимакса Дополним матрицу игры столбцом с минимальными значениями в строках и строкой с максимальными значениями в столбцах: B1 B2 A1  a11 a12 A2  a21 a22  Am  am1 am 2 1 2 Bn a1n  1 a2 n   2  amn  m n Величина  = max i = max 1  i m min aij называется нижней ценой игры 1 i  m 1 j  n или максимином). Стратегия игрока A, соответствующая максимину , называется максиминной стратегией игрока A. Если игрок A придерживается своей максиминной стратегии, то ему гарантирован выигрыш не меньше , то есть  – это тот гарантированный минимальный выигрыш, который может обеспечить себе игрок A, придерживаясь наиболее осторожной стратегии. Величина  = min  j = min max aij называется верхней ценой игры 1 j  n 1 j  n 1 i m или минимаксом. Стратегия игрока B, соответствующая минимаксу , называется минимаксной стратегией игрока B. Теорема 1 Для игры двух лиц с нулевой суммой 𝛼 ≤ 𝛽. Если игрок B придерживается своей минимаксной стратегии, то ему гарантирован проигрыш не больше . Положение, при котором игроки используют свои минимаксные стратегии неустойчиво и может быть нарушено поступившими сведениями о выбранной стратегии другого игрока. Если оба игрока разумны, то игрок A будет выбирать свою максиминную стратегию, а игрок B – минимаксную. Пример 2 ( Найдем нижнюю и верхнюю цены игры из примера 1. −1 1 −1 1 −1 −1 1 1 ) 86 Решение: Справа от матрицы записаны  i – минимальные элементы строки, а внизу  j – максимальные элементы столбца. Тогда нижняя цена игры  = max(−1; −1) = −1, верхняя цена игры  = min(1;1) = 1 . Таким образом, если игрок A будет делать личные ходы, а его противник B об этом узнает, то игрок A получит минимальный выигрыш -1, то есть он будет в проигрыше, а игрок B получит минимальный проигрыш 1, то есть он будет выигрывать. Аналогичное утверждение справедливо и для игрока B.  Игра называется игрой с седловой точкой, если нижняя и верхняя цена игры совпадают. В этом случае, величина v = = называется чистой ценой игры. Седловой точке соответствует пара минимаксных стратегий, которые называются оптимальными, а их совокупность называется решением игры. В игре с седловой точкой любому игроку выгодно придерживаться оптимальных стратегий (любое отклонение от оптимальной стратегии ухудшает положение игрока). Чистая цена игры в игре с седловой точкой является значением выигрыша, которое в игре разумных противников игрок A не может увеличить, а игрок B уменьшить. При разумном поведении игроков исход игры с седловой точкой заранее предопределен. Играть в такие игры имеет смысл, если противник не знает оптимальной стратегии. Пример 3 Двое играют в следующую игру: одновременно выбрасывают 1, 2 или 3 пальца. Выигрывает тот, у кого больше пальцев (выигрыш равен разности выброшенных пальцев). Если оба выбросили одинаковое количество пальцев, то никто не выиграл. Платежная матрица:  0 1 −2  −2  1 0 −1 1  2 1 0 0   2 1 0 Тогда нижняя цена игры  = max(−2;1;0) = 0 , верхняя цена игры  = min(2;1;0) = 0 . Так как нижняя  и верхняя  цены игры совпадают, то игра имеет седловую точку, поэтому игра решается в чистых стратегиях с чистой ценой игры v = 0. Оптимальные стратегии сторон: оба игрока выбрасывают по 3 пальца. При этом никто не выигрывает.  2.3.3. Решение игр в смешанных стратегиях Если игра не имеет седловой точки, то игрок A гарантирует себе выигрыш, равный нижней цене игры, которая меньше верхней цены игры. Конечно, игрок А хочет увеличить выигрыш, а В – уменьшить проигрыш. Если игроки будет чередовать свои стратегии случайным образом, то в некоторых случаях А получит бόльший выигрыш, чем нижняя цена игры. Смешанной стратегией игрока A называется набор вероятностей p = ( p1, p2 , , pm ) ( p1 + p2 + + pm = 1 ), с которыми он чередует свои стратегии 87 A1, A1,…, Am. Аналогично определяется смешанная стратегия игрока B как набор вероятностей q = (q1, q2 , , qn ) ( q1 + q2 + + qn = 1 ). Поскольку игроки могут выбирать свои ходы случайно и независимо друг от друга, то случайной становится и величина выигрыша. В этом случае выигрыш А определяется как m n математическое ожидание выигрыша M ( p, q) =  aij pi q j . i =1 j =1 Сформулируем основную теорему теории игр. Теорема 1 (Фон-Неймана) Любая конечная игра имеет по крайней мере одно решение, возможно в смешанных стратегиях. Следствие Для любой конечной игры mn двух лиц существуют смешанные * * стратегии p = ( p1* , p2* , , pm* ) игрока А и q = (q1* , q2* , , qn* ) игрока В такие, что для любых других стратегий p = ( p1, p2 , , pm ) и q = (q1, q2 , , qn ) выполняется * * * * неравенство M ( p, q )  M ( p , q )  M ( p , q) . * Смысл следствия: если игрок А отступает от стратегии p , то его выигрыш * уменьшается; если игрок В отступает от стратегии q , то его проигрыш * * увеличивается. Таким образом, смешанные стратегии ( p , q ) образуют седловую точку во множестве смешанных стратегий, игрокам не выгодно отступать от стратегий, соответствующих этой точке. * * Если ( p , q ) пара смешанных стратегий, образующих седловую точку, то m n величина v =  aij pi*q*j называется ценой игры. i =1 j =1 Теорема 2 Если один из игроков применяет оптимальную смешанную стратегию, то его выигрыш будет не меньше цены игры вне зависимости от применения вторым игроком своих стратегий, т.е. выполняются соотношения: m a i =1 n ij pi*  v, j = 1, , n a q j =1 ij * j  v, i = 1, , m (2.11) (2.12) В дальнейшем эти соотношения будут использоваться для решения игры. Теорема 3 (О цене игры) Цена игры удовлетворяет неравенству      . В общем случае задача решения игры, если матрица игры не содержит седловой точки, тем сложней, чем больше ее размерность. Поэтому в теории игр применяют приемы, позволяющие сократить размерность матрицы. Стратегии называются дублирующими, если в платежной матрице им соответствуют одинаковые строки (столбцы). Если все элементы i-ой строки платежной матрицы меньше соответствующих элементов k-ой строки, то стратегия Ai называется доминирующей для игрока A. Если все элементы j-го 88 столбца платежной матрицы больше соответствующих элементов r-го столбца, то стратегия B j называется доминирующей для игрока B. Теорема 4 если в платежной матрице удалить дублирующие и доминирующие строки и столбцы, то цена игры и оптимальные стратегии не изменятся. Пример 4  1 7 2 7 Для платежной матрицы  6 2 7 2  стратегии A3 и B3 являются  5 1 6 1   доминирующими, стратегия B5 – дублирующей, их можно удалить. Получим матрицу 1 7 . 6 2 ( ) 2.3.4. Решение матричных игр 22 в смешанных стратегиях Игра 22 – наиболее простой случай конечных игр. Рассмотрим игру, не a a имеющую седловой точки, с платежной матрицей  11 12  . a a  21 22  Пусть p = ( p1, p2 ) и q = (q1, q2 ) – смешанные стратегии игроков. Найдем оптимальные стратегии. Если игрок В придерживается стратегии В1, то средний выигрыш А составит a11 p1 + a21 p2 . Если игрок В придерживается стратегии В2, то средний выигрыш А составит a12 p1 + a22 p2 . По свойству оптимальных смешанных стратегий эти средние выигрыши должны совпадать и быть равными цене игры. Получаем систему: a11 p1 + a21 p2 = a12 p1 + a22 p2 = v p1 + p2 = 1 Решаем систему: a11 p1 + a21 (1 − p1 ) = a12 p1 + a22 (1 − p1 ) p1 (a11 − a21 ) + a21 = p1 (a12 − a22 ) + a22 Оптимальные стратегии игрока A: a22 − a21 p1* = a11 − a21 − a12 + a22 a22 − a21 a11 − a12 p2* = 1 − p1* = 1 − = a11 − a21 − a12 + a22 a11 − a21 − a12 + a22 Аналогично, составляем систему для игрока В: a11q1 + a12q2 = a21q1 + a22q2 = v q1 + q2 = 1 Решая систему, находим оптимальные стратегии игрока B: a22 − a12 q1* = a11 − a21 − a12 + a22   89 a11 − a21 a11 − a21 − a12 + a22 Цена игры a11a22 − a12a21 v= a11 − a21 − a12 + a22 Решение игры 22 можно найти так же геометрически (рис.16). Для этого на оси абсцисс отложим отрезок А1А2 длиной 1. Левый конец отрезка соответствует стратегии А1, правый – стратегии А2. Промежуточные точки отрезка соответствуют смешанным стратегиям p = ( p1, p2 ) первого игрока. Причем расстояние от промежуточной точки отрезка до правого края – это вероятность p2 стратегии А2, а расстояние до левого края – вероятность p1 стратегии А1. Через концы отрезка А1А2 проведем прямые, перпендикулярные оси абсцисс, на них будем откладывать выигрыши при стратегиях А1 и А2 соответственно. Если игрок В применяет стратегию В1, то выигрыши первого игрока при стратегии А1 составляет a11, а при стратегии А2 составляет a21. Отложим эти выигрыши на перпендикулярах и соединим полученные точки прямой B1B1 . Если игрок А применяет смешанную стратегию, то его выигрышу соответствует некоторая точка на отрезке B1B1 . Аналогично строим отрезок B2 B2 , соответствующий применению вторым игроком стратегии В2. В соответствии с принципом максимина ломаная B1NB1 – нижняя граница выигрыша, получаемого игроком А. Точка N, в которой выигрыш максимален, определяет цену игры и ее решение. Для нахождения оптимальной стратегии игрока А достаточно составить уравнения прямых и найти точку пересечения. q2* = Рис. 16. Геометрическое решение игры 22 Аналогично можно рассмотреть задачу минимизации верхней границы выигрыша для игрока В. 90 Используя геометрическую интерпретацию можно найти решение игр, заданных матрицей 2  n. Каждой из n стратегий игрока В будет соответствовать прямая. Точка N, лежащая на нижней границе и дающая наибольшую величину выигрыша, определяет цену игры и ее решение. При этом определяются активные стратегии игрока В (соответствующие им прямые пересекаются в точке N). Для активных стратегий вероятности не равны 0, остальные стратегии игроком В не используются (их вероятности равны 0). Аналогично можно решить игру с матрицей m  2. В этом случае строят верхнюю границу выигрыша и на ней определяют минимум. Пример 5  2 5 Решить аналитически игру, заданную платежной матрицей A =  .  6 4 Решение: Найдем нижнюю и верхнюю цену игры.  2 52 6 44   6 5  = max(2;4) = 4,  = min(6;5) = 5 . , следовательно, игра не имеет седловой точки, решение будет в смешанных стратегиях. * Найдем аналитически оптимальную стратегию p = ( p1* , p2* ) игрока А и соответствующую цену игры v. * Так как p оптимальная стратегия, то она должна гарантировать средний выигрыш игроку А, равный цене игры, при любом поведении игрока В: для стратегии В1: 2 p1 + 6 p2 = v , для стратегии В2: 5 p1 + 4 p2 = . С учетом того, что сумма вероятностей смешанной стратегии равна 1, получаем систему уравнений: 2 p1 + 6 p2 = v  5 p1 + 4 p2 = v  p + p =1  1 2 2 Вычтем из первого уравнения второе: −3 p1 + 2 p2 = 0 или p1 = p2 . Значит: 3 2   p1 = 3 p2   p1 + p2 = 1 2 p + 6 p = v 2  1  91 2 5 3 p2 + p2 = 1  p2 = 1  p2 = 3 3 5 3 2 p1 = 1 − p2 = 1 − = 5 5 2 3 22 v = 2 + 6 = 5 5 5 * 22  2 3 Итак: p =  ;  , v = . 5  5 5 Аналогично получаем систему для нахождения смешанной стратегии игрока В. 2q1 + 5q2 = v  6q1 + 4q2 = v q + q = 1  1 2 Вычтем из первого уравнения второе: −4q1 + q2 = 0 Откуда, q2 = 4q1 подставим в первое уравнение. q2 = 4q1  q1 + q2 = 1 2q + 5q = v  1 2 q1 + 4q1 = 1 5q1 = 1 1 q1 = 5 1 4 q2 = 1 − q1 = 1 − = 5 5 1 4 22 v = 2 + 5 = 5 5 5 * 22 1 4 Итак: q =  ;  , v = . 5 5 5 * 22  2 3 * 1 4 Ответ: p =  ;  , q =  ;  , v = . 5 5 5  5 5 Пример 6 ( ) Решить графически игру, заданную платежной матрицей 2 3 11 . 7 5 2 Решение: Проверим наличие у игры седловой точки, найдем нижнюю и верхнюю цену игры. 92 (72 ) 3 11 2 5 2 2 7 5 11  = max(2;2) = 2,  = min(7;5;11) = 5 . , следовательно, игра не имеет седловой точки, решение будет в смешанных стратегиях. Матрица игры имеет размер 23, поэтому решение игры будем искать для игрока А (рис. 17). Отложим отрезок единичной длины А1А2, каждой точке которого поставим в соответствие некоторую смешанную стратегию первого игрока – (p1, p2). В частности, точке А1 соответствует стратегия А1, точке А2 – стратегия А2. В точках А1 и А2 восстановим перпендикуляр и на полученных прямых будем откладывать выигрыши игрока А при соответствующих стратегиях и строить прямые, соответствующие стратегиям игрока В. Рис. 17. Геометрическое решение игры примера 6 В соответствии с принципом минимакса ломаная B1MNB3 – нижняя граница выигрыша, получаемого игроком А. Точка N, в которой выигрыш максимален, определяет цену игры и ее решение. Для нахождения оптимальной стратегии игрока А достаточно составить уравнения прямых и найти точку пересечения прямых B2 B2 и B3 B3 . Уравнение прямой, проходящей через 2 точки (x1,y1) и (x2,y2) имеет вид x − x1 y − y1 . Прямая B2 B2 проходит через точки (0,3) и (1,5), следовательно, = x2 − x1 y2 − y1 x −0 y −3 ее уравнение или −2 x + y = 3 . Прямая B3 B3 проходит через точки = 1− 0 5 − 3 x − 0 y − 11 (0,11) и (1,2), следовательно, ее уравнение или 9 x + y = 11 . Для = 1 − 0 2 − 11 нахождения точки пересечения прямых B2 B2 и B3 B3 решим систему: −2 x + y = 3 9 x + y = 11 Вычтем из первого уравнения второе, получаем  93 8 11 8 49 y = 3 + 2x = 3 + 2  = 11 11 8 8 3 49  8 49  Точка N  ;  , следовательно, p2 = , p1 = 1 − = , v = . 11 11 11 11  11 11  * 49 3 8 Таким образом, p =  ;  , v = . 11  11 11  Из рисунка видно, что стратегия В1 не входит в оптимальную смешанную стратегию, поэтому q3=0, и мы можем найти оптимальную смешанную стратегию, удалив из платежной матрицы первый столбец. Получаем матрицу 3 11 , при этом столбцы ее соответствуют активным стратегиям В , В . 2 3 5 2 −11x = −8  x = ( ) * Так как q – оптимальная, то она должна гарантировать средний выигрыш игроку В, равный цене игры, при любом поведении игрока А: для стратегии А1: 3q2 + 11q3 = v , для стратегии А2: 5q2 + 2q3 = v . С учетом того, что сумма вероятностей смешанной стратегии равна 1, цена 49 игры v = получаем систему уравнений: 11 49  3q2 + 11q3 = 11  49 5q2 + 2q3 = q + q = 1 11 3  2  Вычтем из первого уравнения второе: −2q2 + 9q3 = 0 . −2q2 + 9q3 = 0 q2 + q3 = 1 Решая систему, находим 9  q =  2 11  2 q3 =  11 *  9 2 Оптимальная смешанная стратегия для игрока В q =  0; ;  .  11 11  * 49 3 8 *  9 2 Ответ: p =  ;  , q =  0; ;  , v = . 11  11 11   11 11   94 Пример 7 6 5 Решить графически игру, заданную платежной матрицей  42 67  . 1 8    Решение: Проверим наличие у игры седловой точки, найдем нижнюю и верхнюю цену игры. 6 5 5  4 64  2 72 1 8  1   6 8  = max(5;4;2;1) = 5,  = min(6;8) = 6 . , следовательно, игра не имеет седловой точки, решение будет в смешанных стратегиях. Матрица игры имеет размер 42, поэтому решение игры будем искать для игрока В. Аналогично примеру 6 по горизонтальной оси отложим отрезок единичной длины В1В2, каждой точке которого поставим в соответствие некоторую смешанную стратегию второго игрока – (q1, q2) (рис. 18). В частности, точке В1 соответствует стратегия В1, точке В2 – стратегия В2. В точках В1 и В2 восстановим перпендикуляр и на полученных прямых будем откладывать выигрыши игрока А при соответствующих стратегиях и строить прямые, соответствующие стратегиям игрока А. Рис. 18. Геометрическое решение игры примера 7 В соответствии с принципом минимакса ломаная A1NA4 – верхняя граница выигрыша, получаемого игроком А. Точка N, в которой выигрыш минимален, определяет цену игры и ее решение. Для нахождения оптимальной стратегии игрока В достаточно составить уравнения прямых и найти точку пересечения прямых A1 A1 и A4 A4 . Уравнение прямой, проходящей через 2 точки (x1,y1) и (x2,y2) имеет вид x − x1 y − y1 . Прямая A1 A1 проходит через точки (0,6) и (1,5), следовательно, = x2 − x1 y2 − y1 95 x−0 y−6 или x + y = 6 . Прямая A4 A4 проходит через точки (0,1) = 1− 0 5 − 6 x − 0 y −1 и (1,8), следовательно, ее уравнение или −7 x + y = 1 . Для = 1 − 0 8 −1 нахождения точки пересечения прямых A1 A1 и A4 A4 решим систему: x+ y=6 −7 x + y = 1 Вычтем из первого уравнения второе, получаем 5 8x = 5  x = 8 5 43 y =6− x =6− = 8 8 5 5 3 43  5 43  Точка N  ;  , следовательно, q2 = , q1 = 1 − = , v = . 8 8 8 8 8 8  * 43 5 3 Таким образом, q =  ;  , v = . 8 8 8 Из рисунка видно, что стратегии А2 и А3 не входят в оптимальную смешанную стратегию, поэтому p2=0 и p3=0, и мы можем найти оптимальную смешанную стратегию, удалив из платежной матрицы вторую и третью строку. Получаем матрицу 6 5 , при этом строки ее соответствуют активным 1 8 стратегиям А1, А4. ее уравнение  ( ) * Так как p – оптимальная стратегия, то она должна гарантировать средний выигрыш игроку А, равный цене игры, при любом поведении игрока В: для стратегии В1: 6 p1 + p4 = v , для стратегии В2: 5 p1 + 8 p4 = v . С учетом того, что сумма вероятностей смешанной стратегии равна 1, цена 43 игры v = получаем систему уравнений: 8 43  6 p + p = 1 4  8  43 5 p1 + 8 p4 =  p + p =1 8 4  1  Вычтем из первого уравнения второе: p1 − 7 p4 = 0 . p1 − 7 p4 = 0 p1 + p4 = 1 Решая систему, находим  96 7  p = 1  8  1  p4 = 8  * 1 7 Оптимальная смешанная стратегия для игрока А p =  ;0;0;  . 8 8 * 1 * 5 3 43 7 Ответ: p =  ;0;0;  , q =  ;  , v = . 8 8 8 8 8 Таким образом, имеем следующий алгоритм графического решения простейших матричных игр 2n ( или m2): 1. Строим n (m) прямых, соответствующих стратегиям второго (первого) игрока. 2. Строим нижнюю (верхнюю) границу выигрыша. 3. Выбираем на границе выигрыша точку с максимальной (минимальной) ординатой. 4. Определяем по чертежу пару активных стратегий из числа построенных для второго (первого) игрока. 5. Находим координаты точки максимума (минимума) и решение игры. 2.3.5. Сведение матричной игры к задаче линейного программирования Если у каждого из игроков больше двух возможных стратегий, то можно решение игры свести к решению задачи линейного программирования. Найдем решение игры с платежной матрицей m  n : a1n   a11 a12  a21 a22 a2 n    a amn   m1 am 2 Пусть матрица игры не содержит седловой точки. Тогда решение игры будем искать в смешанных стратегиях p = ( p1, p2 , , pm ) и q = (q1, q2 , , qn ) , где p1 + p2 + + pm = 1 и q1 + q2 + + qn = 1 . * Стратегия p является оптимальной, если при любой стратегии игрока B средний выигрыш игрока A будет больше или равен цены игры v согласно (2.11), таким образом, получаем систему ограничений a11 p1 + a21 p2 + + am1 pm  v a12 p1 + a22 p2 + + am 2 pm  v .............................................. a p + a p + + a p  v mn m  1n 1 2 n 2 Будем считать, что цена игры v больше нуля. Действительно, если v  0, то это означает, что некоторые элементы матрицы игры не положительны. Тогда найдём число M>0, которое прибавим ко всем элементам матрицы игры и получим новую матрицу с положительными элементами. Это сложение сделает цену новой игры, равную v+M, положительной, но не изменит решения игры. 97 Разделим обе части всех неравенств на положительное число  и введем p p p новые переменные: x1 = 1 , x2 = 2 , , xm = m . v v v Тогда система ограничений примет вид a11 x1 + a21 x2 + + am1 xm  1 a12 x1 + a22 x2 + + am 2 xm  1 .............................................. a1n x1 + a2 n x2 + + amn xm  1  xi  0, i = 1, , m 1 Далее, так как p1 + p2 + + pm = 1 , то x1 + x2 + + xm = . v Игрок A стремится максимизировать свой средний выигрыш v, то есть 1 минимизировать отношение .  Таким образом, получаем задачу линейного программирования: Z = x1 + x2 + + xm → min a11 x1 + a21 x2 + + am1 xm  1 a12 x1 + a22 x2 + + am 2 xm  1 .............................................. a1n x1 + a2 n x2 + + amn xm  1  xi  0, i = 1, , m Заметим, что эта задача всегда имеет оптимальное решение * X = ( x1* , x2* , , xm* ) . Его можно найти симплекс-методом. Тогда цена игры v= 1 x1 + x + * * 2 + xm* . Оптимальная смешанная стратегия первого игрока * p = ( p1* , p*2 , , p*m ) , где pi* = x*i  v . * Аналогичные рассуждения дают оптимальную стратегию q игрока B. При любой стратегии игрока А проигрыш игрока В не должен превышать цену игры согласно (2.12). Получаем систему ограничений: a11q1 + a12 q2 + + a1n qn  v a21q1 + a22 q2 + + a2 n qn  v .............................................. a q + a q + + a q  v mn n  m1 1 m 2 2 q q q Обозначим y1 = 1 , y2 = 2 , , yn = m . Тогда для нахождения оптимальной v v v смешанной стратегии игрока B необходимо решить следующую задачу линейного программирования: W = y1 + y2 + + ym → max 98 a11 y1 + a12 y2 + + a1n yn  1 a21 y1 + a22 y2 + + a2 n yn  1 .............................................. am1 y1 + am 2 y2 + + amn yn  1  y j  0, j = 1, , n Это двойственная задача к ранее составленной. Задача всегда имеет оптимальное решение Y * = ( y1* , y2* , , yn* ) , которое можно найти симплексметодом или по теореме равновесия, зная решение ранее составленной задачи. 1 Тогда цена новой игры v = * . Оптимальная смешанная стратегия y1 + y2* + + yn* * второго игрока q = (q1* , q*2 , , qn* ) , где q*j = y*j  v . Пример 8  −1 1 6  Найти решение игры, заданной платежной матрицей  5 2 −3  .  −2 4 5    Решение: Проверим наличие у игры седловой точки, найдем нижнюю и верхнюю цены игр  −1 1 6  −1  5 2 −3  −3  −2 4 5  −2   5 4 6  = max(−1; −3; −2) = −1,  = min(5;4;6) = 5 . , следовательно, игра не имеет седловой точки, решение будет в смешанных стратегиях. Чтобы свести матричную игру для игрока А к задаче линейного программирования преобразуем платежную матрицу так, чтобы все ее элементы были больше нуля – прибавим ко всем элементам матрицы число 4. Получаем преобразованную платежную матрицу:  3 5 10   9 6 1  2 8 9   Средний выигрыш А должен быть не меньше цены игры v при любом поведении игрока В. Так, если игрок В использует свою первую стратегию, то средний выигрыш игрока А составит: 3 p1 + 9 p2 + 2 p3 , тогда должно выполняться 3 p1 + 9 p2 + 2 p3  v . Аналогично, записав неравенства для стратегий В2 и В3, получаем систему линейных ограничений:  3 p1 + 9 p2 + 2 p3  v 5 p1 + 6 p2 + 8 p3  v  10 p1 + p2 + 9 p3  v Разделив обе части уравнения p1 + p2 + p3 = 1 на v  0 (цена игры больше нуля, т.к. все элементы преобразованной матрицы больше нуля), получаем 99 целевую функцию Z= p1 p2 p3 1 + + = . v v v v Цель игрока А – получить максимальный средний выигрыш, т.е. v → max , а значит 1 → min . Введем v pi (i = 1,2,3) , тогда Z = x1 + x2 + x3 → min . v Перейдем в системе ограничений к переменным xi, разделив каждое неравенство на v  0 :  3x1 + 9 x2 + 2 x3  1 5 x1 + 6 x2 + 8 x3  1  10 x1 + x2 + 9 x3  1 Таким образом, для нахождения оптимальной стратегии игрока А необходимо решить задачу линейного программирования: Z = x1 + x2 + x3 → min 3 x1 + 9 x2 + 2 x3  1 5 x1 + 6 x2 + 8 x3  1 10 x + x + 9 x  1  x , x1 , x 2 0 3  1 2 3 Аналогично можно составить и решить задачу линейного программирования для игрока В. Средний проигрыш игрока В должен быть не больше цены игры v при любом поведении игрока А. Получаем систему линейных ограничений:  3q1 + 5q2 + 10q3  v 9q1 + 6q2 + q3  v  2q1 + 8q2 + 9q3  v Из условия q1 + q2 + q3 = 1 , разделив обе части уравнения на v  0 , получаем q q q 1 целевую функцию W = 1 + 2 + 3 = . Цель игрока В – получить минимальный v v v v 1 средний проигрыш, т.е. v → min , а значит → max . Если обозначить v q y j = j ( j = 1,2,3) , то W = y1 + y2 + y3 → max . v Перейдем в системе ограничений к переменным yj, разделив каждое неравенство на >0:  3 y1 + 5 y2 + 10 y3  1 9 y1 + 6 y2 + y3  1  2 y1 + 8 y2 + 9 y3  1 обозначения xi = 100 Таким образом, для нахождения оптимальной стратегии игрока B необходимо решить задачу линейного программирования: W = y1 + y2 + y3 → max 3 y1 + 5 y2 + 10 y3  1 9 y1 + 6 y2 + y3  1 2 y + 8 y + 9 y  1  y ,1y , y 2 0 3  1 2 3 Получили пару двойственных задач. Решим первую задачу симплексметодом. Перейдем в системе ограничений к равенствам. 3x1 + 9 x2 + 2 x3 − x4 = 1 5 x1 + 6 x2 + 8 x3 − x5 = 1 10 x + x + 9 x − x = 1  x , x1 , x 2, x , x 3, x 6 0  1 2 3 4 5 6 Расширенная матрица системы ограничений:  3 9 2 −1 0 0 1  −3 −9 −2 1 0 0 −1  9 6 1 0 −1 0 1  −9 −6 −1 0 1 0 −1 .  2 8 9 0 0 −1 1  −2 −8 −9 0 0 1 −1     В матрице уже имеется базис, выразим базисные переменные x4 , x5 , x6 и целевую функцию через свободные для составления симплексной таблицы. Перейдем к задаче максимизации. Z1 = −Z = −( x1 + x2 + x3 ) = 0 − ( x1 + x2 + x3 ) → max   x4 = −1 − (−3x1 − 9 x2 − 2 x3 )  x5 = −1 − (−5 x1 − 6 x2 − 8 x3 )   x6 = −1 − (−10 x1 − x2 − 9 x3 ) Составляем симплексную таблицу. В таблице сразу подпишем переменные двойственной задачи, которые соответствуют ограничениям исходной задачи. В процессе решения будем менять их положение вместе с соответствующими переменными исходной задачи x1, x2 , x3 . 1 − x1 − x2 − x3 x = − 1 −3 −9 −2 y1 4 −5 −6 −8 y2 x5 = −1 y3 x6 = −1 −10 −1 −9  Z1 = 0 1 1 1 CO 1 / 10 1 1/ 9  Таблица является двойственно допустимой. Ей соответствует псевдоплан 1 X = (0;0;0; −1; −1; −1) . Т.к. в столбце свободных членов имеются отрицательные элементы, то строим следующую таблицу согласно алгоритму двойственного симплекс-метода. 101 y3 − x6 −3 / 10 −5 / 10 −1 / 10 1 / 10 1/ 3 − x2 − x3 y1 x4 = −87 / 10 7 / 10  y2 x5 = −55 / 10 −35 / 10 x1 = 1 / 10 9 / 10 Z1 = 9 / 10 1 / 10 CO 9 / 87 1/ 7  Таблица является двойственно допустимой. Ей соответствует псевдоплан X 2 = (1/ 10;0;0; −7 / 10; −5 / 10;0) . Т.к. в столбце свободных членов имеются отрицательные элементы, то строим следующую таблицу согласно алгоритму двойственного симплекс-метода. y3 y1 1 − x6 − x4 − x3 x2 = 7 / 87 1 / 29 −10 / 87 −7 / 87 y2 x5 = −5 / 87 −9 / 29 −55 / 87 −343 / 87  x1 = 8 / 87 −3 / 29 1 / 87 79 / 87 Z1 = −5 / 29 2 / 29 3 / 29 5 / 29 CO 2/9 9 / 55 15 / 343  1 −7 / 10 −5 / 10 1 / 10 −1 / 10 Таблице соответствует оптимальный план X 3 = (8 / 87;7 / 87;0;0; −5 / 87;0) . Т.к. в столбце свободных членов имеются отрицательные элементы, то строим следующую таблицу согласно алгоритму двойственного симплекс-метода. y3 y1 y2 1 − x6 − x4 − x5 x2 = 4 / 49 x3 = 5 / 343 x1 = 27 / 343 Z1 = −60 / 343 19 / 343 26 / 343 15 / 343 Получили оптимальные планы задач. Значения базисных переменных двойственной задачи находятся в строке для коэффициентов целевой функции исходной задачи. Оптимальные решения задач линейного программирования: X * = (27 / 343;4 / 49;5 / 343), Y * = (26 / 343;15 / 343;19 / 343), Wmax = Zmin = −Z1max = 60 / 343. 1 Так как v = и pi = xi  v, q j = y j  v , то находим цену игры и оптимальные Z стратегии игроков. 343 v=  5.7167 , 60 * 343  27 4 5   9 7 1  p = ; ;   =  ; ;   ( 0.45;0.47;0.08 ) , 60  343 49 343   20 15 12  * 343  26 15 19   13 1 19  q = ; ;   =  ; ;   ( 0.43;0.25;0.32 ) . 60  343 343 343   30 4 60  102 3. Нелинейное программирование В общем случае задача нелинейного программирования (НП) состоит в нахождении экстремума (минимума или максимума) функции (3.1) Z = f ( x1, , xn ) → max(min) , на множестве, задаваемом ограничениями в виде равенств и (или) неравенств gi ( x1, , xn ) = bi (i = 1, , k ) (3.2) gi ( x1, , xn )  bi (i = k + 1, , m) Так же могут быть условия неотрицательности переменных. Предполагается, что среди функций f и gi (i = 1, , m) есть хоть одна нелинейная. Любой n-мерный вектор X = ( x1, , xn ) , удовлетворяющий ограничениям задачи, называется допустимым решением, а множество всех таких векторов — областью допустимых решений (ОДР). Нахождение решений задачи (3.1), (3.2) сводится к определению такой точки этой области, через которую проходит гиперплоскость наивысшего (наинизшего) уровня f ( x1, , xn ) = const . Эта точка может находиться как на границе области допустимых решений, так и внутри ее. Перечислим свойства задач НП, которые существенно усложняют процесс их решения по сравнению с задачами линейного программирования: 1. Множество допустимых решений может иметь очень сложную структуру (например, быть невыпуклым или несвязным). 2. Глобальный максимум (минимум) может достигаться как внутри области, так и на ее границах (где он, вообще говоря, будет не совпадать ни с одним из локальных экстремумов). 3. Целевая функция f может быть не дифференцируемой, что затрудняет применение классических методов математического анализа. Этим объясняется отсутствие общих методов, подобных симплекс-методу в линейном программировании, позволяющих решать любые задачи НП. Тем не менее, отдельные специальные классы нелинейных задач хорошо изучены.  3.1. Графическое решение задачи нелинейного программирования Графический метод можно использовать для решения задачи НП, которая содержит две переменных х1 и х2, например, задачи следующего вида: (3.3) Z = f ( x1, x2 ) → max(min) (3.4) gi ( x1, x2 )  bi (i = 1, , m) . Чтобы найти ее оптимальное решение, нужно выполнить следующие действия: 1. Найти ОДР, определяемую ограничениями задачи. Если окажется, что эта область пуста, то это означает, что задача не имеет решения. 2. Построить семейство линий уровня целевой функции f ( x1, x2 ) = C при различных значениях числового параметра С. 3. При решении задачи на минимум определить направление убывания, а для задачи на максимум – направление возрастания линий уровня целевой функции. 4. Найти точку ОДР, через которую проходит линия уровня с наибольшим в задачи на максимум (соответственно наименьшим в задаче на минимум,) 103 значением параметра С. Эта точка будет оптимальным решением. Если целевая функция не ограничена сверху в задаче на максимум (снизу – в задаче на минимум), то это означает, что задача не имеет оптимального решения. 5. Найти координаты точки оптимума и определить в ней значение целевой функции. Отметим, что в отличие от задачи линейного программирования точка оптимума в задаче НП не обязательно находится на границе ОДР. Ею также может быть внутренняя точка этого множества. Пример 1 Найти максимальное и минимальное значение функции Z = ( x1 − 3) 2 + ( x2 − 4) 2 при условии 3 x1 + x2  7 10 x1 − x2  8 −18 x + 4 x  12  x , x 1 0 2  1 2 Решение: Это задача нелинейного программирования, т.к. целевая функция не линейна. Областью допустимых решений является треугольник АВС (рис. 19). Рис. 19. Область допустимых решений примера 1 Строим линии уровня ( x1 − 3) 2 + ( x2 − 4) 2 = const – концентрические окружности с центром в точке Е(3;4) (рис. 20). Видно, что минимум целевой функции достигается в точке D – точке касания окружности и области, максимальное значение функция принимает в точке С – угловой точке множества допустимых решений. 104 Рис. 20. Нахождение точек минимума и максимума в примере 1 Найдем координаты точки D, для этого воспользуемся равенством угловых коэффициентов прямой 10 x1 − x2 = 8 и касательной к окружности. Выразим x2 из уравнения прямой: x2 = 10 x1 − 8 , следовательно, k1=10. Для касательной к окружности угловой коэффициент – это производная x2 (производная неявной функции). Продифференцируем по x1 обе части уравнения окружности: ( x − 3) 2 + ( x − 4) 2  = С  ( 1 2 ) 2( x1 − 3) + 2( x2 − 4) x2 = 0 x −3 x2 = − 1 = k2 x2 − 4 Из условия получаем уравнение k1 = k2 x −3 − 1 = 10 или x1 + 10 x2 = 43. Это одно из уравнений для нахождения x2 − 4 координат точки D. Точка D лежит на прямой x1 + 10 x2 = 43. Получаем систему: x1 + 10 x2 = 43 10 x1 − x2 = 8  123  x = 1  101 . Решая систему, находим  422  x2 = 101  2 2  123 422   123   422  324 ; − 3 +  − 4 = Следовательно, Z min = Z  . =  101 101   101   101  101 10 x1 − x2 = 8 Для нахождения координат С составим систему , решив −18 x1 + 4 x2 = 12 которую, находим С (2;12). 2 2 Zmax = Z ( 2;12 ) = ( 2 − 3) + (12 − 4 ) = 65 .  105 3.2. Метод множителей Лагранжа Рассмотрим частный случай задачи НП, предполагая, что система ограничений содержит только уравнения, отсутствуют условия неотрицательности переменных и функции f ( x1, , xn ) и gi ( x1, , xn ) непрерывны вместе с частными производными. (3.5) Z = f ( x1, , xn ) → max(min) , на множестве, задаваемом ограничениями в виде равенств и (или) неравенств (3.6) gi ( x1, , xn ) = bi (i = 1, , m) Задача (3.5), (3.6) называют задачей на условный экстремум или классической задачей оптимизации. Чтобы найти решение этой задачи вводят переменные 1, 2 , , m , называемые множителями Лагранжа, и составляют функцию Лагранжа: m L( x1, , xn , 1, , m ) = f ( x1, , xn ) +  i (bi − gi ( x1, , xn )) , (3.7) i =1 находят частные производные функции Лагранжа по всем переменным xj и λi и приравнивают их нулю для нахождения стационарных точек функции Лагранжа. Получается система n + m уравнений c n + m неизвестными x1, , xn , 1, , m для нахождения точек, подозрительных на экстремум. m gi  L f = −  = 0 ( j = 1, , n)  i x x x j i =1 j j (3.8)  L  = bi − gi = 0 (i = 1, , m)  i Находят решения этой системы. Среди этих решений после дополнительного анализа (проверки достаточного признака экстремума) отбираются такие, которые действительно являются точками локального оптимума. После сравнения значений целевой функции в этих точках находится точка, являющаяся глобальным оптимумом. Подчеркнем, что основное практическое значение метода Лагранжа заключается в том, что он позволяет перейти от условной оптимизации к безусловной и, соответственно, расширить арсенал доступных средств решения проблемы. Однако нетрудно заметить, что задача решения системы уравнений, к которой сводится данный метод, в общем случае не проще исходной проблемы поиска экстремума. Методы, подразумевающие такое решение, называются непрямыми. Они могут быть применены для весьма узкого класса задач, для которых удается получить линейную или сводящуюся к линейной систему уравнений. При решении конкретных практических задач обычно используются прямые методы, основанные на итерационных процессах вычисления и сравнения значений оптимизируемых функций. К таким методам относят градиентные методы решения задач безусловной оптимизации. 3.3. Решение задач выпуклого программирования Рассмотрим задачу нелинейного программирования: 106 Z = f ( x1, , xn ) → max , gi ( x1, , xn )  bi (i = 1, , m) x j  0 ( j = 1, , n) (3.9) (3.10) (3.11) Функция f называется выпуклой на выпуклом множестве Х, если для любой пары точек X 1 , X 2  X и любого числа  (0    1) справедливо соотношение f ( X 1 + (1 −  ) X 2 )   f ( X 1 ) + (1 −  ) f ( X 2 ) (3.12) Функция f называется вогнутой на выпуклом множестве Х, если для любой пары точек X 1 , X 2  X и любого числа  (0    1) справедливо соотношение f ( X 1 + (1 −  ) X 2 )   f ( X 1 ) + (1 −  ) f ( X 2 ) (3.13) Функция f называется строго выпуклой (строго вогнутой), если неравенства в соотношениях (3.12), (3.13) являются строгим для всех X 1  X 2 , т.е. знак неравенства "<" (соответственно, ">"). Очевидно, что если f – выпуклая функция, то f1 = -f – вогнутая функция. Сумма выпуклых (вогнутых) функций — выпуклая (вогнутая) функция. Линейная функция является как выпуклой, так и вогнутой функцией. Простейший пример выпуклой функции: z = х2, а вогнутой: z = х . Множество допустимых решений задачи НП удовлетворяет условию регулярности, если существует, по крайней мере, одна точка из ОДР X p  X такая, что gi ( X p )  bi (i = 1, , m) . Задача (3.9) – (3.11) является задачей выпуклого программирования, если она удовлетворяет следующим условиям: 1) целевая функция f выпукла (вогнута); 2) все функции gi в ограничениях (3.10) выпуклые. Легко проверить, что если g – выпуклая (вогнутая) функция, то для любого числа b множество { X | g ( X )  ()b} – выпуклое. Поэтому ОДР в задаче выпуклого программирования - выпуклое множество. Выпуклым будет и множество оптимальных решений. Если же целевая функция – строго выпуклая (вогнутая) функция, то множество точек ее минимума (максимума) состоит из единственной точки. Наиболее важное свойство таких задач дает теорема 2 Теорема 2 Любая точка локального максимума (минимума) задачи выпуклого программирования является точкой ее глобального максимума (минимума). Поэтому, в задаче выпуклого программирования можно говорить об оптимальном решении, не уточняя, идет речь о глобальном или локальном оптимуме. Составим функцию Лагранжа для задачи выпуклого программирования: m L( X , ) = L( x1, , xn , 1, , m ) = f ( x1, , xn ) +  i (bi − gi ( x1, , xn )) . i =1 107 Точка ( X 0 ,  0 ) = ( x10 , , xn0 , 10 , , m0 ) называется седловой точкой функции Лагранжа, если для любых и X = ( x1, , xn ) ( xi  0, i = 1, , n)  = (1 , , m ) ( j  0, j = 1, , m) выполняется: L( X ,  0 )  L( X 0 ,  0 )  L( X 0 ,  ) (3.14) Центральное место в теории нелинейного программирования занимает теорема Куна-Таккера. Теорема (Куна-Таккера) Для задачи выпуклого программирования (3.9) – (3.11) множество допустимых решений которой удовлетворяет условию регулярности, X 0 = ( x10 , , xn0 ) является оптимальным планом тогда и только тогда, если существует  0 = (10 , , m0 ) ( j  0, j = 1, , m) , что ( X 0 ,  0 ) – седловая точка функции Лагранжа. Если предположить, что функции f и gi непрерывно дифференцируемы, то можно записать условия Куна-Таккера, определяющие необходимые и достаточные условия того, чтобы точка ( X 0 ,  0 ) была седловой точкой функции Лагранжа, т.е. являлась решением задачи выпуклого программирования. Эти условия имеют вид:  Lx j ( X 0 ,  0 )  0 ( j = 1, , n)  x 0  L ( X 0 ,  0 ) = 0 ( j = 1, , n)  0j x j  x j  0 ( j = 1, , n) (3.15)   L ( X ,  )  ( i = 1, , m )  i i0  Li ( X 0 ,  0 ) = 0 (i = 1, , m)  0  0 (i = 1, , m)  i Предпоследнее условие означает, что если множитель Лагранжа положителен, то соответствующее ему ограничение в точке оптимума обязательно должно быть равенством. Если же ограничение не является равенством в точке оптимума, то его множитель Лагранжа равен нулю. Это условие аналогично условию дополняющей нежесткости в задаче линейного программирования. В отличие от классической задачи условной оптимизации на множители Лагранжа накладывается условие неотрицательности. Множители Лагранжа допускают интерпретацию, аналогичную интерпретации оптимальных оценок ограничений в задаче линейного программирования. Так множитель Лагранжа i-го ограничения характеризует величину изменения оптимального значения целевой функции при увеличении правой части этого ограничения на единицу и фиксированных значениях остальных ограничений. Однако в отличие от задачи линейного программирования величина *i не равна в точности изменению оптимального значения целевой функции при увеличении правой части i-го ограничения на единицу, а дает лишь приближенную оценку этого изменения. 108 Пример 2 Решить графически задачу нелинейного программирования Z = ( x1 − 5) 2 + ( x2 − 1) 2 → min  x1 − 2 x2  −2 7 x1 − x2  13  x + 3 x  21  x1 , x 20  1 2 Проверить выполнение условий Куна-Таккера для найденной оптимальной точки. Решение: На рис. 21 представлено графическое решение задачи. Линии уровня целевой функции – концентрические окружности с центром в точке (5;1). Минимум функции достигается в точке (4;3). Рис. 21. Графическое решение задачи нелинейного программирования Покажем, что существует Λ0 ≥ 0, при которой в найденной точке выполняются условия Куна-Таккера . Перепишем задачу в виде: Z1 = − Z = −( x1 − 5) 2 − ( x2 − 1) 2 → max −2 − x1 + 2 x2  0 7 x1 − x2 − 13  0 21 − x − 3 x  0  x , x 1 0 2  1 2 Составим функцию Лагранжа: L( X , ) = −( x1 − 5) 2 − ( x2 − 1) 2 + 1 (−2 − x1 + 2 x2 ) + 2 (7 x1 − x2 − 13) + 3 (21 − x1 − 3 x2 ) Найдем частные производные: Lx1 = −2( x1 − 5) − 1 + 72 − 3 Lx2 = −2( x2 − 1) + 21 − 2 − 33 L1 = −2 − x1 + 2 x2 109 L2 = 7 x1 − x2 − 13 L3 = 21 − x1 − 3x2 Запишем условия Куна-Таккера:  x1  Lx1 = 0  x  (−2( x − 5) −  + 7 −  ) = 0  x2  Lx = 0  x1  (−2( x1 − 1) + 21 − 2 − 33 ) = 0 2 2 1 2 3   2    L  1 1 = 0  1  (−2 − x1 + 2 x2 ) = 0 2  L2 = 0 2  (7 x1 − x2 − 13) = 0 3  L = 0 3  (21 − x1 − 3x2 ) = 0 3  Подставим в систему координаты оптимальной точки (4;3), найденной графически. 4  (−2(4 − 5) − 1 + 72 − 3 ) = 0 3  (−2(3 − 1) + 21 − 2 − 33 ) = 0 1  (−2 − 4 + 2  3) = 0 2  (7  4 − 3 − 13) = 0 3  (21 − 4 − 3  3) = 0 4  (2 − 1 + 72 − 3 ) = 0  3  (−4 + 21 − 2 − 33 ) = 0 1  0 = 0 2  12 = 0  3  8 = 0 Произведение равно нулю, если один из множителей равен нулю. Из первого и второго уравнений следует, что выражения в скобках равны нулю. Из четвертого и пятого уравнений следует, что 2 = 3 = 0 . Подставим их в остальные уравнения. 2 − 1 = 0 −4 + 21 = 0  = 0 2 = 0  3 Откуда, находим решение: 1 = 2, 2 = 3 = 0 . Следовательно, точка (4;3) является точкой экстремума.  Квадратичной формой относительно переменных x1, , xn называется функция от этих переменных, имеющая следующий вид: F = c x + c12 x1x2 + c13 x1x3 + 2 11 1 n n =  cij xij (3.16) i =1 j =1 Квадратичная форма называется положительно (отрицательно) – полуопределенной, если F ( X )  0 ( F ( X )  0 ) для любой точки X = ( x1, , xn ) и существует точка X  = ( x1, , xn ) , такая, что не все xi одновременно равны 0, что F ( X ) = 0 . Теорема 3 Квадратичная форма является выпуклой функцией, если она положительно-полуопределенная, и вогнутой функцией, если она отрицательнополуопределенная. Задачей квадратичного программирования называется задача (3.17) – (3.18). 110 n n n f ( X ) =  di xi +  cij xij i =1 n a x j =1 ij j (3.17) i =1 j =1  bi (i = 1, , m) (3.18) x j  0 ( j = 1, (3.19) , n) Задача квадратичного программирования является задаче удовлетворяет всем требованиям задачи выпуклого программирования. Для задачи квадратичного программирования функция Лагранжа запишется в виде: n n n m n i =1 j =1 L =  di xi +  cij xij +  i (bi −  aij x j ) . i =1 i =1 j =1 Если функция имеет седловую точку ( X 0 ,  0 ) , то в этой точке выполняются соотношения (3.15). Вводя в неравенства этой системы дополнительные переменные u j ( j = 1, , n) и vi (i = 1, , m) , обращающие неравенства в равенства, перепишем соотношения (3.15) для задачи квадратичного программирования:  Lx j ( X 0 ,  0 ) + u j = 0 ( j = 1, , n) (3.20)   L ( X ,  ) + v = ( i = 1, , m )  i  i  x0j  u j = 0 ( j = 1, , n) (3.21)  0  i  vi = 0 (i = 1, , m) x 0j , u j  0 ( j = 1, , n), i0 , vi  0 (i = 1, , m) (3.22) Для того, чтобы найти решение задачи квадратичного программирования (3.17) – (3.19) необходимо найти неотрицательное решение системы (3.20). Это решение можно найти с помощью метода искусственного базиса, примененного для нахождения максимального значения функции F = − M  yi , при условиях i (3.20), где yi – искусственные переменные, введенные в уравнения системы (3.20). Алгоритм нахождения решения задачи квадратичного программирования (3.17) – (3.19): 1. Составить функцию Лагранжа. 2.Записать необходимые и достаточные условия существования седловой точки для функции Лагранжа (3.20), (3.21). 3. Используя метод искусственного базиса найти седловую точку или установить ее отсутствие. Пример 3 Решить задачу квадратичного программирования. Z = 2 x1 + 4 x2 − x12 − 2 x22 → max 111   x1 + 2 x2  8 2 x1 − x2  12   x1 , x2  0 Решение: Функция является вогнутой, т.к. представляет собой сумму линейной функции f1 = 2x1 + 4x2 , которую можно рассматривать как вогнутую, и f 2 = − x12 − 2 x22 , которая является отрицательноквадратичной формы определенной, а следовательно, вогнутой. Для составления функции Лагранжа перепишем систему в виде: 8 − x1 − 2 x2 = 0 12 − 2 x1 + x2 = 0  x1 , x2  0 Составим функцию Лагранжа L( X ,  ) = 2 x1 + 4 x2 − x12 − 2 x22 + 1 (8 − x1 + 2 x2 ) + 2 (12 − 2 x1 + x2 ) . Запишем необходимые и достаточные условия существования седловой точки.  Lx1 = 2 − 2 x1 − 1 − 22  0  Lx = 4 − 4 x2 − 21 + 2  0 (3.23)  L2 = 8 − x − 2 x  0 1 1 2    L2 = 12 − 2 x1 + x2  0  x1  (2 − 2 x1 − 1 − 22 ) = 0  x2  (4 − 4 x2 − 21 + 2 ) = 0   (8 − x − 2 x ) = 0 1  (12 − 12 x + 2x ) = 0  2 1 2 x1, x2 , y1, y2  0 Перепишем систему линейных неравенств (3.23) в виде: 2 x1 + 1 + 22  2 4 x2 + 21 − 2  4 x + 2x  8 21x − x2  12  1 2 Перейдем к равенствам: 2 x1 + 1 + 22 − u1 = 2 4 x2 + 21 − 2 − u2 = 4 x + 2x + v = 8 21x − x2 + v1 = 12  1 2 2 x1, x2 , y1, y2 , u1, u2 , v1, v2  0 Откуда получаем (3.24) в виде:  x1  u1 = 0  x2  u2 = 0   v = 0 1  v1 = 0  2 2 Матрица системы ограничений (3.26): 112 (3.24) (3.25) (3.26) (3.27) 0 1 2 −1 0 1 0 2  4 2 −1 0 −1 0 1 4  2 0 0 0 0 0 0 8  −1 0 0 0 0 0 0 12  Для нахождения базисного решения системы (3.26) решим методом искусственного базиса следующую задачу: Z = − M ( y1 + y2 ) → max при ограничениях 2 x1 + 1 + 22 − u1 + y1 = 2 4 x2 + 21 − 2 − u2 + y2 = 4 x + 2x + v = 8 21x − x2 + v1 = 12  1 2 2 x1, x2 , y1, y2 , u1, u2 , v1, v2 , y1, y2  0 Процесс решения опустим, найденное решение X 0 = (1,1,0,0,0,0,5,11) или x10 = 1, x20 = 1, 10 = 0, 20 = 0, u1 = 0, u2 = 0, v1 = 5, v2 = 11 . Проверим выполнение условий (3.27): 1  0 = 0 1  0 = 0 0  5 = 0 . 0  11 = 0  Условия (3.27) выполнены, следовательно ( X 0 ,  0 ) = (1;1;0;0) является седловой точкой функции Лагранжа. Следовательно, X * = (1;1) – оптимальный план исходной задачи.  2 0 1 2  3.4. Градиентные методы Используя градиентные методы можно найти решение любой задачи нелинейного программирования. В общем случае применение таких методов позволяет найти локальный экстремум. Поэтому градиентными методами лучше решать задачи выпуклого программирования, в которых локальный экстремум является глобальным. Процесс нахождения решения градиентными методами заключается в том, что начиная с некоторой точки X 0 , осуществляется последовательный переход к другим точкам X 1 , X 2 , до тех пор, пока градиент f ( x1, , xn ) в некоторой точке X k не станет равным 0 или пока не будет выполняться условие f ( X k +1 ) − f ( X k )   , где  – достаточно малое положительное число. Градиентные методы делятся на две группы. К первой группе относятся методы, в которых исследуемые точки не выходят за границы области допустимых решений. Наиболее известный из таких методов – метод ФранкаВулфа. Ко второй группе относятся методы, в которых исследуемые точки могут как принадлежать, так и не принадлежать ОДР. Наиболее известные из таких методов – метод штрафных функций, Эрроу-Гурвица. 3.4.1. Метод Франка-Вулфа Пусть имеется задача нелинейного программирования: 113 f ( x1, , xn ) → max n a x j =1 ij j (3.28)  bi (i = 1, , m) x j  0 ( j = 1, , m) , (3.29) (3.30) где f ( x1, , xn ) – вогнутая функция. Ограничения этой задачи – линейные неравенства, что дает возможность заменить функцию в окрестности исследуемой точки на линейную. Поэтому решение исходной задачи будет сведено к последовательному решению задач линейного программирования. В процессе решения перебираются точки X k , k = 0,1,2, , принадлежащие области допустимых решений. Для каждой такой точки вычисляется градиент функции grad f ( X k ) = f x1 ( X k ), f x2 ( X k ), , f xn ( X k ) и строят линейную ( ) функцию F = f x1 ( X k )  x1 + f x2 ( X k )  x2 + + f xn ( X k )  xn . (3.31) Затем находят максимальное значение этой линейной функции при ограничениях (3.29), (3.30). Пусть решением этой задачи будет точка Z k . Тогда за новое допустимое решение исходной задачи принимают X k +1 , координаты которой вычисляются по формуле: X k +1 = X k + k ( Z k − X k ) , (3.32) где k – некоторое число из интервала [0;1]. Это число выбирается произвольно или определяется таким образом, чтобы значение f ( X k ) было максимальным. Для это решают уравнение f k = 0 и находят его наименьший корень. Если его значение больше 1, то считают k = 1 . После вычисления новой точки по формуле (3.32) исследую необходимость продолжения вычислений, сравнивая значения функции в двух последних точках. Алгоритм решения задачи (3.28) – (3.30) методом Франка-Вулфа 1. Найти любое допустимое решение исходной задачи. 2. Найти градиент функции в найденной точке. 3. Построить линейную функцию (3.31) и найти ее максимальное значение при ограничениях (3.29), (3.30). 4.Определить шаг вычислений k . 5. Найти новое допустимое решение по формуле (3.32). 6. Проверить необходимость перехода к новому допустимому решению. В случае необходимости перейти на п.2. Пример 4 Методом Франка-Вулфа решить задачу из примера 3 с точностью до 0.01. f = 2 x1 + 4 x2 − x12 − 2 x22 → max 114   x1 + 2 x2  8 2 x1 − x2  12   x1 , x2  0 Решени:е Найдем частные производные функции f x1 = 2 − 2 x1 , f x2 = 4 − 4 x2 . Градиент grad f = (2 − 2 x1;4 − 4 x2 ) . Итерация 1 В качестве начального приближения выберем точку X 0 = (0;0) (она удовлетворяет системе ограничений задачи), f ( X 0 ) = 0 . Находим градиент в этой точке grad f ( X 0 ) = (2;4) . Решаем задачу линейного программирования F = 2 x1 + 4 x2 → max   x1 + 2 x2  8 2 x1 − x2  12   x1 , x2  0 Эта задача имеет оптимальное решение Z 0 = (0;4) . Новое допустимое решение будем находить по формуле X 1 = X 0 + 0 ( Z 0 − X 0 ) . Подставив вместо X 0 , Z 0 найденные значения, получим  x11 = 0 + 0  0 = 0  x1 = 0 +   4 = 4  2 Для нахождения 0 , подставим найденные значения в функцию и выразим функцию через 0 : f ( X 1 ) = 2  0 + 4  40 − 02 − 2  160 2 = 160 − 3202 . Найдем производную этой функции по 0 и приравняем ее нулю: f 0 = 16 − 640 = 0 . Решив уравнение, получим 0 = 0.25 [0;1] , принимаем найденное значение за величину шага. Тогда новая точка X 1 = (0;40 ) = (0;1) , f ( X 1 ) = 2 . Проверим достижение точности: f ( X 1 ) − f ( X 0 ) = 2 − 0 = 2  0.01. Итерация 2 Находим градиент в точке X 1 = (0;1) : grad f ( X 1 ) = (2;0) . Решаем задачу линейного программирования F = 2 x1 → max   x1 + 2 x2  8 2 x1 − x2  12   x1 , x2  0 Эта задача имеет оптимальное решение Z 1 = (6.4;0.8) . Новое допустимое решение будем находить по формуле X 2 = X 1 + 1 ( Z 1 − X 1 ) . Подставив вместо X 1 , Z 1 найденные значения, получим  x12 = 0 + 1  6.4 = 6.41  x 2 = 1 +   (−0.2) = 1 − 0.2  2 1 1 115 Подставим найденные значения в функцию: f ( X 2 ) = 2  6.41 + 4  (1 − 0.21 ) − (6.41 ) 2 − 2  (1 − 0.21 ) 2 = 2 + 12.81 − 41.0412 . f 1 = 12.8 − 82.081 = 0 . 1 = 0.16 [0;1] , принимаем найденное значение за величину шага. Тогда новая точка X 2 = (6.41;1 − 0.21 ) = (1.02;0.97) , f ( X 2 ) = 2.9978 . Проверим достижение точности: f ( X 2 ) − f ( X 1 ) = 2.9978 − 2 = 0.9978  0.01 . Итерация 3 Находим градиент в точке X 2 = (1.02;0.97) : grad f ( X 2 ) = (−0.04;0.12) . Решаем задачу линейного программирования F = −0.04 x1 + 0.12 x2 → max   x1 + 2 x2  8 2 x1 − x2  12   x1 , x2  0 Эта задача имеет оптимальное решение Z 2 = (0;4) . Новое допустимое решение будем находить по формуле X 3 = X 2 + 2 ( Z 2 − X 2 ) . Подставив вместо X 2 , Z 2 найденные значения, получим  x13 = 1.02 + 2  0 = 1.02  x3 = 0.97 +   4 = 4 + 0.97  2 2 2 Выразим функцию через 1 : f ( X 3 ) = 2  1.02 + 4  (42 + 0.97) − 1.02 2 − 2  (42 + 0.97) 2 = 4.9978 + 0.482 − 3222 . f 1 = 0,48 − 642 = 0 . Решив уравнение, получим 2 = 0.008 [0;1] , принимаем найденное значение за величину шага. 3 3 X = (1.02;42 + 0.97) = (1.02;1.002) , f ( X ) = 2.9996 . Проверим достижение точности: f ( X 3 ) − f ( X 2 ) = 2.9996 − 2.9978 − 2 = 0.0018  0.01. Тогда новая точка Видно, что найденная точка находится достаточно близко к оптимальной точке (1;1), найденной в примере 3.  3.4.2. Метод штрафных функций Пусть имеется задача нелинейного программирования: f ( x1, , xn ) → max gi ( x1, , xn )  0, (i = 1, , m) x j  0 ( j = 1, , m) , (3.33) (3.34) (3.35) где f ( x1, , xn ) – вогнутая функция, gi ( x1, , xn ) – выпуклые функции. В методе штрафных функций место непосредственного решения задачи находят максимальное значение функции F ( x1, , xn ) = f ( x1, , xn ) + H ( x1, , xn ) , где H ( x1, , xn ) – определяется системой ограничений и называется штрафной функцией. 116 Для построения штрафной функции наиболее часто используют следующий вид функции: m 0, b i − gi ( x1, , xn )  0 , H ( x1, , xn ) = i ( x1, , xn ) gi ( x1, , xn ) , где  i ( x1 , , xn ) =  , b − g ( x , , x )  i i i 1 n i =1  i  0 – некоторые постоянные числа. Используя штрафные функции последовательно переходят от одной точки к другой до тех пор, пока не будет получено решение с заданной точностью. При этом координаты следующей точки находят по формуле:   f ( X k ) m gi ( X k )   (3.36) x kj +1 = max  0; x kj +   +  i    x   x i =1 j j    Из (3.36) следует, что, если предыдущая точка находится в области допустимых решений, то все коэффициенты  i равны 0, и переход к следующей точке определяется только градиентом целевой функции. Если же предыдущая точка не принадлежит области допустимых решений, то за счет слагаемых с коэффициентами  i происходит возвращение в ОДР. При этом, чем меньше  i , тем быстрее находится решение, но при этом снижается точность. Поэтому итерационный процесс начинают при сравнительно малых значениях  i , а потом эти значения постепенно увеличивают. Алгоритм решения задачи (3.33) – (3.35) методом штрафных функций 1. Найти начальное допустимое решение. 2. Выбрать шаг вычислений  . 3. Найти частные производные от целевой функции и функций, определяющих область допустимых решений. 4. По формуле (3.36) найти координаты новой точки. 5. Проверить, принадлежит ли новая точка ОДР. Если не принадлежит, то переходят к п.6, иначе проверяют достижение заданной точности и в случае необходимости переходят к п.4. 6. Устанавливают значения весовых коэффициентов и переходят к п.4. Пример 5 Методом штрафных функций решить задачу с точностью 0.01. f = − x12 − x22 → max  ( x1 − 7) 2 + ( x2 − 7) 2  18 x1 , x2  0 Решение: Целевая функция представляет собой отрицательно определенную квадратичную форму, следовательно, вогнута. Область допустимых решений, определяемая системой ограничений – выпукла. Найдем частные производные целевой функции: f x1 = −2 x1 , f x2 = −2 x2 . 117 Частные производные функции g ( x1 , x2 ) = 18 − ( x1 − 7) 2 + ( x2 − 7) 2 ограничения: g x1 = 2( x1 − 7) = 2 x1 − 14, g x2 = 2( x2 − 7) = 2 x2 − 14 . из Возьмем  = 0.1 Итерация 1 В качестве начального приближения выберем точку X 0 = (6;7) (она принадлежит ОДР), f ( X 0 ) = −85 . Найдем координаты новой точки по формуле (3.36): x11 = max(0; x10 +   f x1 ( X 0 )) = max(0;6 + 0.1(−2  6)) = 4.8 . x12 = max(0; x20 +   f x2 ( X 0 )) = max(0;7 + 0.1(−2  7)) = 5.6 Получили точку X 1 = (4.8;5.6) . Проверим ее принадлежность ОДР, для этого g ( X 1 ) = 18 − (4.8 − 7) 2 + (5.6 − 7) 2 = подставим в систему ограничений: X 1 = (4.8;5.6) принадлежит ОДР, = 18 − 6.8  0. Откуда следует, что f ( X 1 ) = −54.4 . Проверяем достижение точности: f ( X 1 ) − f ( X 0 ) = −54.4 − (−85) = 30.6  0.01 . Итерация 2 Найдем координаты новой точки по формуле: 2 x1 = max(0; x11 +   f x1 ( X 1 )) = max(0;4.8 + 0.1(−2  4.8)) = 3.84 . x22 = max(0; x12 +   f x2 ( X 1 )) = max(0;5.6 + 0.1(−2  5.6)) = 4.48 Получили точку X 2 = (3.84;4.48) . Проверим ее принадлежность ОДР: g ( X 2 ) = (3.84 − 7) 2 + (4.48 − 7) 2 = 18 − 16.336  0 . Откуда следует, что 2 2 X = (3.84;4.48) принадлежит ОДР, f ( X ) = −34.816 . Проверяем достижение точности^ f ( X 2 ) − f ( X 1 ) = −34.816 − (−54.4) = 19.584  0.01 . Итерация 3 Найдем координаты новой точки по формуле: 3 x1 = max(0; x12 +   f x1 ( X 2 )) = max(0;3.84 + 0.1(−2  3.84)) = 3.072 . x23 = max(0; x22 +   f x2 ( X 2 )) = max(0;4.48 + 0.1(−2  4.48)) = 3.584 Получили точку X 3 = (3.072;3.584) . Проверим ее принадлежность ОДР: g ( X 3 ) = 18 − (3.072 − 7) 2 + (3.584 − 7) 2 = 18 − 27.098  0 . Откуда следует, что X 3 = (3.072;3.584) не принадлежит ОДР. Итерация 4 Найдем координаты новой точки по формуле: 4 x1 = max(0; x13 +   ( f x1 ( X 3 ) +  g x1 ( X 3 )) = = max(0;3.072 + 0.1(−2  3.072 +  (−2  3.072 + 14))) = max(0;2.4576 +   7.856) x24 = max(0; x23 +   ( f x2 ( X 3 ) +  g x2 ( X 3 )) = = max(0;3.584 + 0.1(−2  3.584 +  (−2  3.584 + 14))) = max(0;2.8672 +   6.832) 118 Выберем  таким образом, чтобы точка не слишком далеко удалялась от границы ОДР, но тем не менее попадала в ОДР. Этому условию удовлетворяет  = 1.9 . Тогда получим точку X 4 = (3.950;4.165) . Проверим ее принадлежность ОДР: g ( X 4 ) = (3.950 − 7) 2 + (4.165 − 7) 2 = 18 − 17.340  0 . Откуда следует, что 4 4 X = (3.950;4.165) принадлежит ОДР, f ( X ) = −32.950 . Проверяем достижение точности: f ( X 4 ) − f ( X 2 ) = −32.950 − (−34.816) = 1.866  0.01 . И так далее. Процесс продолжается до достижения заданной точности.  3.4.3. Метод Эрроу-Гурвица В методе штрафных функций значения  i выбирались произвольно, что приводит к значительным колебаниям удаленности точек от области допустимых решений. В методе Эрроу-Гурвица этот недостаток устраняется тем, что на очередном шаге коэффициенты вычисляются по формуле:  ik +1 = max(0; ik −  gi ( X k )) (i = 1, , m) . (3.37) В качестве начальных значений  i0 берут произвольные неотрицательные числа. 4. Многоцелевые задачи Задачи, решаемые с учетом множества показателей или критериев, носят название многоцелевых. При решении таких задач найти такой план, при котором система критериев была бы наилучшей. Если все критерии равнозначны, то эффективным считается такой план, при котором отклонения от оптимумов по каждому критерию равны. С привычной точки зрения задача со многими критериями решения не имеет - далеко не всегда есть возможность одновременного удовлетворения всех заданных условий. Поэтому, когда говорят о решении многокритериальной задачи, имеют в виду какой-нибудь компромисс между изначально противоречивыми требованиями. А так как практически любая подобная ситуация допускает разные компромиссные разрешения, то и подходы к их поиску многочисленны и весьма разнообразны. Перечислим некоторые подходы. Метод уступок - лицо, принимающее решения, подводится к выбору решения путем постепенного ослабления первоначальных требований, как правило, одновременно невыполнимых. Метод идеальной точки - в области допустимых значений неизвестных ищется такая их совокупность, которая способна обеспечить набор значений критериев, в том или ином смысле ближайший к наилучшему, как правило, недосягаемому (в так называемой точке утопии). Метод свертывания - лицо, принимающее решения, сводит многокритериальную задачу к задаче с одним критерием. 119 Метод ограничений - множество допустимых значений неизвестных уменьшается путем осмысленного введения дополнительных ограничений на заданные критерии. Метод анализа иерархий - на основании суждений экспертов оценивается вклад в общую оценку каждого критерия. Далее будем рассматривать случаи, когда решение принимается по двум критериям. 4.1. Множество Парето Рассмотрим на плоскости (U, V) произвольное множество . Каждая точка плоскости обладает одним из следующих трех свойств: либо все точки, ближайшие к ней, принадлежат множеству  (такая точка называется внутренней точкой множества ), либо все точки, ближайшие к ней, множеству  не принадлежат (такая точка называется внешней точкой по отношению к множеству ), либо сколь угодно близко от нее расположены как точки множества , так и точки, множеству  не принадлежащие (такие точки называются граничными точками множества ). Множество всех граничных точек множества называется его границей. Точки множества  можно разбить на три класса (рис. 22): - к первому классу относятся точки, которые, оставаясь во множестве , можно сдвинуть так, чтобы одновременно увеличились обе координаты (в этот класс попадают все внутренние точки множества  и часть его граничных точек); - второй класс образуют граничные точки, перемещением которых по границе  можно увеличить только одну из координат при сохранении значения второй (вертикальный отрезок АВ и горизонтальный отрезок CD на границе множества ); - в третий класс попадут граничные точки, перемещение которых по границе  уменьшает одну из координат при одновременном увеличении другой (дуга BD границы ). Рис. 22. Разбиение точек множества Множество точек третьего класса принято называть границей (множеством) Парето данного множества . На рис. 23 приведены примеры границы Парето некоторых простейших множеств. 120 Рис. 23. Примеры границ Парето Говоря нестрого, граница Парето множества  - это точки, из которых нельзя сдвинуться на «север», «восток» либо «северо-восток», оставаясь в том же множестве . Другими словами, в множество Парето не включаются такие решения, которые могут быть улучшены одновременно по обоим критериям. Укажем простое геометрическое правило, посредством которого можно выделять из заданного плоского множества его границу Парето. Рассмотрим пробный прямой угол, стороны которого сонаправлены координатным осям U и V. Положение этого пробного угла на плоскости однозначно определяется его вершиной Q. Перемещая пробный угол (параллельно самому себе), мы будем собирать только те точки заданного множества , которые можно совместить с точкой Q так, чтобы ни одна другая точка множества  не попадала ни внутрь этого угла, ни на одну из его сторон. Совокупность всех таких точек и будет искомой границей Парето для множества . Рис. 24. Определение границы Парето 4.2. Метод идеальной точки Рассмотрим постановку двухкритериальной задачи в общем виде: Пусть на плоскости (х,y) задано множество ω и в каждой точке этого множества определены две непрерывные функции: U = Φ(x,y) и V = Ψ(x,y). Рис. 25. Множество, на котором заданы функции U и V Необходимо на множестве ω найти точку (x0,y0), в которой Φ(x0,y0) и Ψ(x0,y0) принимают максимальные значения. 121 Сразу же отметим, что в общем случае поставленная задача решения не имеет. В самом деле, изобразим на плоскости (U,V) все точки, координаты которых вычисляются по формулам U = Φ(x,y) и V = Ψ(x,y). Обозначим полученное множество через . Из рисунка видно, что Umax (наибольшее значение U) и Vmax (наибольшее значение V) достигаются в разных точках, а точка P с координатами (Umax, Vmax) лежит вне множества . Таким образом, в исходной постановке задача, вообще говоря, неразрешима - удовлетворить обоим требованиями одновременно невозможно. И, следовательно, нужно искать какое-то компромиссное решение. Рис. 26. Неразрешимость задачи Метод идеальной точки использует множество Парето, составленное из допустимых точек задачи, которые не могут быть «сдвинуты» в пределах допустимого множества с улучшением сразу по обоим критериям. На границе Парето отыскиваются точки, ближайшие к точке утопии P (точка утопии дает сочетание наилучших значений всех критериев, но обычно не удовлетворяет заданным ограничениям). Рассмотрим реализацию метода идеальной точки на конкретном примере. Пример Решить двухкритериальную задачу линейного программирования методом идеальной точки. U = 2 x1 − 2 x2 → max V = −2 x1 − x2 → max − x1 + 4 x2  20 4 x1 + x2  22 x − x  3 2  x1 , x   1 2 0 Решение: 1. Построим область допустимых решений в плоскости x1Ox2 , определяемую системой ограничений. 122 Рис. 27. Область допустимых решений примера Областью допустимых решений задачи является пятиугольник OABCD. 2. Построим в критериальной плоскости область, соответствующую области допустимых решений OABCD. Для этого необходимо найти координаты вершин. В нашем случае, очевидно, что O(0; 0), A(0; 5), B(4; 6), C(5; 2), D(3; 0), т.к. часть этих точек использовалась при построении прямых. В общем случае координаты точки пересечения двух прямых определяют совместным решением их уравнений, например, для точки С, которая является точкой пересечения (2) и (3) прямых необходимо решить систему: 4 x1 + x2 = 22 x1 − x2 = 3 Сложим уравнения, получим: 5x1 = 25  x1 = 5, x2 = x1 − 3 = 2 . Найдем координаты образов точек O, A, B, C, D в линейном преобразовании, определяемом целевыми функциями: O(0; 0)  U = 2  0 − 2  0 = 0 V = −2  0 − 0 = 0 Таким образом, O(0; 0) → O(0; 0). A(0; 5)  U = 2  0 − 2  5 = −10 V = −2  0 − 5 = −5 Таким образом, A(0; 5) → A(–10; –5). B(4; 6)  U = 2  4 − 2  6 = −4 V = −2  4 − 6 = −14 Таким образом, B(4; 6) → B(–4; –14). C(5; 2)  U = 2  5 − 2  2 = 6 V = −2  5 − 2 = −12 Таким образом, C(5; 2) → C(6; –12).  123 D(3; 0)  U = 2  3 − 2  0 = 6 V = −2  3 − 0 = −6 Таким образом, D(3; 0) → D(6; –6). По найденным координатам точек построим в критериальной плоскости UOV образ многоугольника OABCD – многоугольник OABCD . Рис. 28. Образ область допустимых решений примера в плоскости UOV 3. В критериальной плоскости найдем границу Парето – северо-восточную границу области OABCD. Рис. 29. Граница Парето 124 Точкой утопии, в которой достигается максимум одновременно по двум критериям U и V, является точка P: через самую высокую (северную) точку области OABCD провели горизонтальную прямую (через точку O) и через самую правую (восточную) точку области OABCD провели вертикальную прямую (через точки C и D); точка – точка пересечения горизонтальной и вертикальной прямой. Рис. 30. Точка утопии 4. На границе Парето найдем идеальную точку – точку, наиболее близко расположенную к точке утопии. В нашем случае это основание перпендикуляра, опущенного из точки утопии Р на отрезок OD – точка M. Рис. 31. Идеальная точка 125 Найдем координаты точки M. Для этого найдем уравнение прямой OD. Воспользуемся уравнением прямой, проходящей через две точки: O(0; 0), D(6; –6): u − u1 v − v1 = u2 − u1 v2 − v1 u −0 v−0 = 6 − 0 −6 − 0 u v = 6 −6 OD : u + v = 0 Найдем уравнение перпендикуляра, опущенного из точки утопии P на отрезок OD. Воспользуемся уравнением прямой с точкой и вектором нормали n : n1 (u − u0 ) + n2 (v − v0 ) = 0 . n = OD = (6 − 0; −6 − 0) = (6; −6), P(6;0)  6(u − 6) − 6(v − 0) = 0 Уравнение PM  : u − v = 6 . Координаты точки М найдем из системы: u + v = 0 . u −v =6 Сложим уравнения: 2u = 6  u = 3, v = −u = −3 . Таким образом, М(3; –3), а значит, компромиссное решение позволит достигнуть значений целевых функций: U = 3, V = –3.  5. Найдем координаты точки в плоскости x1Ox2 , которой соответствует точка М критериальной плоскости. Для этого решим систему уравнений: VU==−33 −22xx −−2xx ==−33 2−3xx− =2x0 = 3 xx ==1.50 1 1 2 2 1 1 2 2 2 Получили, что компромиссным решением метода идеальной точки является M(1.5; 0), в которой критерии достигают значений U = 3, V = –3. Рис. 32. Компромиссное решение задачи 126 Эта точка принадлежит отрезку OD. 127