Методы оптимальных решений

Министерство образования и науки Российской Федерации федеральное государственное бюджетное образовательное учреждение высшего образования «САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПРОМЫШЛЕННЫХ ТЕХНОЛОГИЙ И ДИЗАЙНА» Кафедра математики Методы оптимальных решений Конспект лекций для студентов-заочников, обучающихся по направлениям подготовки 38.03.02 – «Менеджмент» 38.03.01 – «Экономика» Составители: В. В. Потихонова Л. И. Король Санкт-Петербург 2016 Утверждено на заседании кафедры 10.02.2016 г., протокол № 5 Рецензент О. Б. Тѐрушкина Тексты лекций посвящены рассмотрению теоретических сведений по следующим темам: векторные пространства, экономико-математические модели, графический и симплекс методы решения задач линейного программирования, элементы теории двойственности, транспортная задача. Приводятся подробные решения типовых задач по всем разделам. Оригинал-макет подготовлен составителями Подписано в печать 27.06.16.Формат 60х841/16 Усл. печ. л. 3,1. Тираж 100 экз. Заказ 582/16 http://publish.sutd.ru Отпечатано в типографии ФГБОУВО «СПбГУПТД» 191028, С.-Петербург, ул. Моховая, 26 2 Тема 1. Векторные пространства 1. Понятие п-мерного вектора Из курса аналитической геометрии известно, что фиксированной системе координат каждый вектор A однозначно определен своими координатами: вектор, расположенный на числовой оси, определяется координатой A (х), т. е. одним действительным числом. Т.о. прямая – одномерное векторное пространство. Всякий вектор A , расположенный на плоскости с заданной системой координат, определяется двумя координатами или компонентами: A = (х; у) ( A  a1 ;a2  ), т. е. упорядоченной системой из двух действительных чисел. Плоскость является двумерным векторным пространством. Всякий вектор A трехмерного векторного пространства определяется тремя координатами: A = (х; у; z) ( A  a1 ; a2 ; a3  ), т. е. упорядоченной системой из трех действительных чисел. В экономике, физике, геометрии приходится изучать объекты, для задания которых недостаточно трех действительных чисел. Пусть, например, некоторый промышленный район производит станки, хлопчатобумажные ткани, автомобили, телевизоры, шерстяные изделия и т. д. Для характеристики производства района, очевидно, потребуется упорядоченная система из n действительных чисел. Таким образом, целесообразно рассмотреть совокупности всевозможных упорядоченных систем из n действительных чисел. Обобщим понятие вектора следующим образом. Определение 1. Любая упорядоченная последовательность из п действительных чисел a1 , a2 ,...., an представляет собой п- мерный вектор A , который можно записать в виде A  a1 ; a2 ;..., an   a1    a  или A   2  ,   a   n где a i - координата вектора; п - размерность вектора. Замечание. Координаты п-мерного вектора удобнее обозначать одной буквой, но с разными индексами (в отличие от трехмерного вектора), а сам вектор – той же заглавной буквой. Для п-мерных векторов вводятся понятия равенства, операции сложения, вычитания, умножения на скаляр, так же как и для трехмерных векторов. Напомним, что сложение векторов и умножение вектора на число называют линейными операциями над векторами. 3  Два вектора A u B с одним и тем же числом координат A  a1 ; a2 ;..., an  ,  B  b1 , b2 , bn  будем считать равными в том случае, когда a1  b1 ; a2  b2 ; ......., an  bn . Равенство обозначается обычно A  B .  Суммой векторов A u B называется вектор A  B  a1  b1 , a2  b2 , ...., an  bn .  Произведение вектора A на число: kA  ka1 , ka2 , ..., kan ; k  число.  Роль нуля играет нулевой вектор  0,0,...,0 .  Вектор  1A называется противоположным вектору A и обозначается  A  A   a1 ;a2 ;..., an  . Определение 2. Множество всех п-мерный векторов с действительными компонентами, для которых введено понятие линейных операций, называется п-мерным векторным пространством и обозначается R n . Подчеркнем тот факт, что непосредственный геометрический смысл имеют лишь пространства R1 , R 2 , R 3 . Пространство R n при n  3 – чисто математический объект. Вместе с тем этот объект очень удобен для описания реальных процессов, в том числе экономических. Как известно из геометрии, если векторы A и B заданы своими координатами,  т. е. A  a1 ; a2 ; a3  и B  b1 , b2 , b3  , то их скалярное произведение A  B  a1b1  a2 b2  a3b3 . По аналогии:  Скалярным произведением п-мерных векторов A и B называется число A  B  a1b1  a2 b2  ...  an bn . Скалярное произведение имеет экономический смысл. Если A  a1 ; a2 ;..., an   есть вектор объемов различных товаров, а B  b1 , b2 ,..., bn  – вектор их цен, то их скалярное произведение A  B выражает суммарную стоимость этих товаров.  Свойства скалярного произведения: 1. A  B  B  A 2. A  B  C   A  B  A  C 3. kA   B  k A  B  4. A  A  0, если А  ненулевой вектор; А  А  0, если А  нулевой вектор. Определение 3. Векторное п-мерное пространство, в котором введено понятие скалярного произведения, удовлетворяющее указанным свойствам, называется евклидовым пространством. Вектор называется нормированным, если длина его равна единице. Каждый ненулевой вектор A можно нормировать, т.е. умножить на такое число k , чтобы вектор kA был нормированным. В самом деле, при k  1 / A : 4 1 1 A  A  1. A A Угол между векторами А и В определится равенством cos   AB , где AB 0  .  Два вектора называются ортогональными, если их скалярное произведение равно нулю. В случае R 3 ортогональность векторов A и B означает перпендикулярность вектора A к вектору B . Векторы e1 , e2 ,..., en п-мерного евклидова пространства образуют ортонормированный базис, если эти векторы попарно ортогональны и длина каждого из них равна единице. Таким базисом в трехмерном пространстве R 3 являются орты координатных    осей – векторы i , j , k . Рассмотрим линейное уравнение, содержащее п неизвестных: a1 x1  a2 x2  ...  an xn  b . Левая часть этого уравнения – линейная функция от п неизвестных Z  a1 x1  a2 x2  ...  an xn и может быть представлена в виде скалярного произведения векторов Z  A  X , где A  a1 ; a2 ;..., a n  , X  x1 ; x2 ;..., xn  . Линейная функция от неизвестных x1 ; x2 ;..., xn вполне определяется вектором A из своих коэффициентов, и, наоборот, всякий п-мерный вектор однозначно определяет некоторую линейную функцию. Исходя из этого, сложение и умножение вектора на число превращаются в операции над линейными функциями, которые широко используются при решении задач математического программирования. 2. Линейная зависимость и независимость векторов Одним из центральных понятий линейной алгебры является понятие линейной зависимости. Сначала заметим следующее: если при рассмотрении некоторого вопроса приходится иметь дело с несколькими векторами, то, как правило, их обозначают одной и той же буквой, но с различными индексами, например, A1 , A2 ,..., Am . Весь такой набор векторов называют системой векторов.  Определение 1. Пусть даны векторы A1 , A2 ,..., Am из R n . 5 Любой вектор A вида A = k1 A1  k2 A2  ...  km Am называется линейной комбинацией векторов Ai с коэффициентами k1 , k 2 ,..., k m (какие угодно числа) (или коротко m k A i 1 i i ). При наличии последнего равенства также говорят, что вектор A линейно выражается через векторы A1 , A2 ,..., Am или что A разлагается по векторам.  Определение 2. Векторы A1 , A2 ,..., An называются линейно зависимыми, если линейная комбинация равна нулю при условии, что хотя бы один из скаляров k1 , k 2 ,..., k m отличен от нуля.  Определение 3. Векторы A1 , A2 ,..., Am называются линейно независимыми, если линейная комбинация равна нулю m k A i 1 i i =0 только при условии, что все числа k1  k 2  ...  k m  0. Пусть теперь задан еще п-мерный вектор B , он равен некоторой линейной комбинации векторов A1 , A2 ,..., Am , т. е. найдется такой набор чисел l1 , l2 ,..., l n , что B = l1 A1  l2 A2  ...  l m Am . В этом случае будем говорить, что вектор B разлагается по векторам A1 , A2 ,..., Am . Числа l1 , l2 ,..., l m в разложении называются коэффициентами разложения вектора B по системе A1 , A2 ,..., Am . Разложение B  k1 A1  k 2 A2  ...  k m Am считается отличным от разложения B  l1 A1  l 2 A2  ...  l m Am , если различна хотя бы одна пара соответствующих коэффициентов разложения. Перечислим ряд свойств линейной зависимости. 1. Система из одного вектора A линейно зависима, если A =0. 2. Если система векторов A1 , A2 ,..., Am линейно зависима, то хотя бы один из векторов этой системы разлагается по остальным. Пусть k i  0 , тогда Ai  k1 k k k k A1  2 A2  ...  i1 Ai1  i1 Ai1  ...  m Am , ki ki ki ki ki т. е. один из векторов системы A1 , A2 ,..., Am разложен по остальным векторам этой системы. 3. Верно и обратное: система, содержащая более одного вектора, линейно зависима тогда и только тогда, когда среди данных векторов имеется такой, который линейно выражается через остальные. 4. Если часть системы линейно зависима, то и вся система линейно зависима. 6 5. Если система A1 , A2 ,..., Am линейно независима, но при прибавлении к ней еще одного вектора A становится линейно зависимой, то вектор A линейно выражается через векторы A1 , A2 ,..., Am . Теорема. В пространстве R n любая система из т векторов, где m>n линейно зависима. Если вектор B и система векторов A1 , A2 ,..., An – произвольные векторы, то задача разложения вектора B по системе векторов A1 , A2 ,..., An , как будет показано далее, сводится к решению системы линейных уравнений. 3. Векторная форма системы линейных уравнений Используя введенные операции над векторами, запишем систему линейных уравнений в векторной форме a11 x1  a12 x2  ...  a1n x n  b1  a21 x1  a22 x2  ...  a2 n x n  b2  . . . . . . . . . . . . . . . . . . . . . . . . . . . a m1 x1  a m 2 x2  ...  a mn x n  bm (1.1) Обозначим через A1 , A2 ,..., An столбцы коэффициентов при неизвестных x1 , x2 ,..... x n , через B столбец свободных членов системы уравнений, т. е.  a1n   a11   a12   b1           a2n   a 21   a 22  b  A1   ; A2   ; .... ; An   ; B  2                 a  a  b  a   m1   m2   m  mn  Теперь систему уравнений (1.1) можно записать в виде A1 x1  A2 x2  ....  An xn  B. (1.2) Последнее уравнение называется векторной формой системы линейных уравнений. Его называют также просто системой линейных уравнений. Последовательность чисел k1 , k 2 ,...., k n  является решением уравнения (1.2), если A1k1  A2 k 2  ....  An k n  B – верное векторное равенство. Таким образом, для разложения вектора B по системе A1 , A2 ,..., An достаточно найти какое-нибудь решение системы линейных уравнений A1 x1  A2 x2  ....  An xn  B , а для доказательства линейной независимости векторов A1 , A2 ,.... , An надо показать, что однородная система A1 x1  A2 x2  ....  An xn  0 имеет только нулевые решения. 7 Пример. Дана система векторов A1 , A2 , A3 , A4 и вектор B : 1  0   1 1    1           A1   0 ; A1   2 , A3   5 , A4   2 , B   7  .  2  2 3   4 5            Разложить вектор B по системе векторов A1 , A2 , A3 , A4 . Решение. Найдем общее решение системы линейных уравнений методом Гаусса. Замечание. Решение систем линейных уравнений методом Гаусса (последовательных исключений) рассматривалось в курсе математики (см. раздел 1). A1 x1  A2 x2  A3 x3  A4 x4  B . Представим систему в виде расширенной матрицы:  1 0  1 1  1   0 2 5 2 7  2 2 3 4 5    Прибавим к последней строке первую, предварительно умноженную на -2:  1 0  1 1  1   0 2 5 2 7  , 0 2 5 2 7    Из последней строки вычтем вторую:  1 0  1 1  1   0 2 5 2 7  0 0 0 0 0    И, наконец, вторую строку поделим на 2: 1 0 1 1 1   x1  x3  x 4  1     0 1 5 / 2 1 7 / 2  или  5 7 0 0 0 0 0   x2  2 x3  x 4  2   Переменные x1 и x 2 называются разрешенными (или основными), а x3 и x 4 – свободными переменными. Система имеет бесчисленное множество решений. Выразив разрешенные переменные через свободные, получим общее решение системы:  x1  1  x3  x4  .  7 5  x2  2  2 x3  x4 8 Если свободные неизвестные x3 и x4 положить равными нулю, то для 7 2 разрешенных неизвестных получим значения x1  1, x2  . Следовательно, B   A1  7 A2  0 A3  0 A4 . 2 Если x3  x4  1 , то x1  1, x2  0 и тогда получим еще одно разложение вектора B   A1  0 A2  A3  A4 . Замечание. Если система состоит из п векторов п-мерного линейного векторного пространства R n , то для того чтобы векторы A1 , A2 ,..., An в R n были линейно независимыми, необходимо и достаточно, чтобы определитель, составленный из координат векторов, не был бы равен нулю (   0 ). 4. Теоремы о векторах п-мерного векторного пространства Теорема 1. В п-мерном линейном векторном пространстве R n существует система из п линейно независимых векторов. Рассмотрим следующую систему из п единичных п-мерных векторов: 1   0  0        0 1   0 E1   ; E2   ; ... E n              0  0 1        Эта система называется системой единичных векторов n-мерного векторного пространства (называемых также ортами по аналогии с системой ортов трехмерного пространства). Покажем, что они линейно независимы. Не нарушая общности доказательства, положим п=4 и вычислим определитель, составленный из координат векторов: 1  1 1  1  0 , т. о. векторы линейно независимы. 1 Теорема 2. Любая совокупность n  1 векторов п-мерного пространства линейно зависима.  Определение. Размерность пространства – это максимальное число содержащихся в нем линейно независимых векторов. 9  Определение. Любая совокупность п линейно независимых векторов пмерного пространства R n называется базисом. Система единичных векторов образует один из базисов n-мерного векторного пространства это ортонормированный базис. Теорема 3. Каждый вектор A линейного пространства R n можно представить и притом единственным способом в виде линейной комбинации векторов базиса. Пример. Вектор A = (3;-2; 4; -5) можно записать как линейную комбинацию единичных векторов E1  1; 0; 0; 0 E2  0;1; 0; 0 ; E3  0; 0;1; 0 E4  0; 0; 0;1 с коэффициентами, которые равны координатам вектора A : A = 3 E1 -2 E 2 + 4 E 3 -5 E 4 = (3;-2,4;-5). 5. Ранг и базис системы векторов п-мерного пространства  Определение. Рангом r  системы векторов A1 , A2 ,..., Am называется максимальное число линейно независимых векторов данной системы. Т. о. базис системы векторов A1 , A2 ,..., Am – это линейно независимая часть системы векторов, например, векторы B1 ; B2 ; .....Br , входящие в систему. Следовательно, остальная часть системы A1 , A2 ,..., Am разлагается по векторам B1 ; B2 ; .....Br . Ранее показано, что диагональная система п-мерных векторов: 1   0  0        0 1   0 E1   ; E2   ; ... E n    линейно независима.           0  0 1        Теорема 4. Если диагональная система векторов является частью системы п-мерных векторов A1 , A2 ,..., Am , то эта диагональная система является базисом системы векторов. Теорема 5. Каждый вектор системы A1 , A2 ,..., Am единственным образом разлагается по векторам ее базиса. 1  0  3        Пример. Показать, что векторы A1  1 ; A2  1  ; A3    2  образуют базис  2   1 2        3   и выразить A4   4  через базис. 5   10 Решение. Имеем три вектора в R 3 , поэтому для проверки независимости векторов достаточно вычислить определитель, составленный из координат 1 0 3 1 2 1 1  3  9  0 определитель векторов A1 , A2 , A3 .   1 1  2  1 2 2 1 2 1 2 отличен от нуля, следовательно, векторы A1 ; A2 ; A3 - линейно независимы. Составим линейную комбинацию векторов A4  A1 x1  A2 x2  A3 x3 , где x1 , x2 , x3 коэффициенты разложения вектора A4 по базису. Заметим, что разложение вектора A4 представляет собой систему уравнений в векторной форме. Запишем ее в виде расширенной матрицы и решим методом Гаусса. 1 0 3 3    1 1  2 4  2 1 2 5   1 0 3 3   1 0 3 3  1 0 0 3       0 1  5 1   0 1  5 1  0 1 0 1 .  0  1  4  1  0 0  3 0   0 0 1 0        Итак, разложение вектора A4 по базису A1 , A2 , A3 будет иметь вид A4  3  A1  1  A2  0  A3  3 A1  A2 . Вернемся к системе линейных уравнений (1.1) a11 x1  a12 x 2  ...  a1n x n  b1 ; a x  a x  ...  a x  b ;  21 1 22 2 2n n 2  .. . . . . . . . .. . . . . . . . .. . . . . . . . a m1 x1  a m 2 x 2  ...  a mn x n  bm . Система содержит п неизвестных и т уравнений. Введем векторы (векторы т-мерного пространства)  a1n   a11   a12   b1           a2n   a 21   a 22  b  A1   ; A2   ; ...... An   ; B  2                 a  a  b  a   m1   m2   m  mn  Запишем систему в векторном виде A1 x1  A2 x2  ....  An xn  B . Рассмотрим конкретный пример. Дана система линейных уравнений  x1  3x 4  x5  7   x 2  2 x 4  4 x5  12   x  4 x  3x  10 4 5  3  3 x 4  x5  7  x1   2 x 4  4 x5  12  x2  x3  4 x 4  3x5  10  1   0  0 3 1  7              Введем векторы A1   0 ; A2  1 ; A3   0 ; A4   2 ; A5   4 ; B  12  .  0  0 1   4 3  10              11 A1 ; A2 ; A3 ; A4 ; A6 ; B – векторы трехмерного пространства; A1 ; A2 ; A3 – составляют базис пространства. Данная система имеет бесчисленное множество решений, зависящих от двух переменных, в частности: x1  7  3x 4  x5 ; x 2  12  2 x 4  4 x5 ; x3  10  4 x 4  3x5 . Здесь x4 , x5 свободные, а x1 ; x2 ; x3 основные или базисные переменные. При x4  0; x5  0  x1  7; x2  12; x3  10 . Запишем это решение в виде вектора X 0  7;12;10; 0; 0 . Принимая x4  1; x5  0  x1  4; x2  10; x3  6 , получено другое решение X 1  4;10; 6;1; 0. Аналогично для системы (1.1). Если среди векторов A1 ; A2 ; A3 ; ....... An есть базис из т единичных векторов, то решение системы будет иметь n  m свободных переменных, через которые будут выражаться т базисных переменных. Если векторы A1 ; A2 ; .....Am составляют базис пространства, то система будет иметь следующее решение: x1  b1 ; x2  b2 ;.... xm  bm ; xm1  xm2  ....  xn  0 . Здесь все свободные переменные приняты равными нулю. Назовем это решение базисным. В приведенном ранее примере это X 0  7;12;10; 0; 0 . Так как любой из векторов-коэффициентов может быть ортом, то система может иметь не одно базисное решение. Систему всегда можно преобразовать в равносильную ей систему с таким расчетом, чтобы любой из ортов ( A1 ; A2 ; .....Am ) вывести из базиса, а вместо него сделать ортом другой вектор-коэффициент системы, который не входил в первоначальный базис. Во вновь полученной системе базисное решение будет отличаться от первоначального. 12 6. Выпуклые множества в п-мерном пространстве В школьном курсе математики выпуклыми назывались многоугольники, целиком расположенные по одну сторону от прямых, на которых лежат их стороны. Общим определяющим свойством, отличающим выпуклый многоугольник от невыпуклого, является то, что если взять любые две его точки и соединить отрезком, то весь отрезок будет принадлежать этому многоугольнику. В А М С а) невыпуклое N D б) выпуклое Рис. 1.1 Говорят, что множество точек называется выпуклым, если оно вместе с любыми двумя точками содержит весь отрезок, соединяющий эти точки. Примерами выпуклых множеств являются не только многоугольники, но и круг, сектор, отрезок, куб, шар, пирамида и т. д. Пересечение (общая часть) любого числа выпуклых множеств есть выпуклое множество. Среди точек выпуклого множества можно выделить внутренние (M и N на рис. 1.1) граничные (отрезки АВ, ВС, СD и АС) и угловые точки (А, В, С и D). До сих пор рассматривались выпуклые множества точек на плоскости и в пространстве. Аналитически такие точки изображались упорядоченной парой или тройкой чисел. Понятие точки можно обобщить, подразумевая под точкой (или вектором) упорядоченный набор п чисел X  x1; x2 ;...xn  , в котором числа x1 ; x2 ;... xn – называются координатами точки (вектора). Как известно, множество всех точек X  x1; x2 ;... xn  образует п-мерное векторное пространство. Фигуры п-мерного пространства уже не имеют реального геометрического смысла и все исследования этого пространства уже 13 надо проводить в аналитической форме. Тем не менее, оказывается целесообразным и в этом случае использовать такие понятия, как выпуклость для облегчения представления об объектах п-мерного векторного пространства. Итак, ранее было дано определение выпуклого множества как множества, которое вместе с любыми двумя своими точками содержит отрезок их соединяющий. Что следует понимать под «отрезком» в случае п-мерного пространства? Дадим аналитическое определение этого понятия.  Точка М называется выпуклой линейной комбинацией двух точек А и В, если (1.3) M  1 A  2 B; 1  0, 2  0, 1  2  1 Если  пробегает все значения от 0 до 1, то точка М описывает отрезок АВ. Точки А и В называются угловыми или крайними точками отрезка АВ. Т.о. отрезок – это множество точек М, подчиненных соотношению (1.3). Пусть теперь имеется k точек A1 , A2 ,..., Ak  R n и действительные числа i ; i  1,..., , k  , тогда линейную комбинацию этих точек можно записать в виде точки А: A  A11  A2 2  ....  Ak k Точка А называется выпуклой линейной комбинацией точек A1 , A2 ,..., An , если выполняются условия A  A11  A2 2  ....  An n ; i  0; n  i 1 i  1. 1 2 4 A1  A2  A3 – есть выпуклая линейная комбинация 7 7 7 3 2 4 1 2 4 точек A1 , A2 , A3 , а линейные выражения A1  A2  A3 u A1  A2  A3 не 7 7 7 7 7 7 Например, выражение являются выпуклыми комбинациями, так как для первого выражения 3 2 4 4    1 u 3    0 – для второго выражения. 7 7 7 7 Из определения выпуклой линейной комбинации точек, очевидно, что угловая точка не может быть представлена как выпуклая линейная комбинация двух других точек отрезка.  Выпуклым множеством будем называть множество таких точек, которое вместе со своими любыми точками содержит и их любую выпуклую линейную комбинацию (т. е. содержит отрезок между ними).  Крайними (или угловыми) точками выпуклого множества будем называть такие точки, которые нельзя представить в виде выпуклой линейной комбинации других точек. Например, вершины треугольника являются крайними точками. 14  Любую точку выпуклого множества можно представить в виде выпуклой линейной комбинации ее крайних точек.  Выпуклое множество будем называть многогранником или многогранной областью, если оно содержит конечное количество крайних точек. Теорема. Выпуклый п-мерный многогранник является выпуклой линейной комбинацией своих угловых точек. Тема 2. Математические модели экономических задач Основные понятия и определения Математической моделью экономической задачи называется совокупность математических соотношений, описывающих рассматриваемый экономический процесс. Для составления математической модели необходимо: 1) выбрать переменные задачи; 2) составить систему ограничений; 3) задать целевую функцию. Переменными задачи называются величины, x1; x2 ;... xn , которые характеризуют экономический процесс. Их обычно записывают в виде вектора X  x1; x2 ;... xn  . Системой ограничений задачи называется совокупность уравнений и неравенств, которым удовлетворяют переменные задачи и которые следуют из ограниченности ресурсов или других экономических условий, например, положительности переменных. В общем случае они имеют вид:  i x1 , x2 ,...., xn   0, i  1,2,...l   i x1 , x2 ,...., xn    0; , i  l  1, l  2,...m (2.1) Целевой функцией называют функцию Z  X   f x1 , x2 ,...xn  (2.2) переменных x1; x2 ;...xn , которая характеризует качество выполнения задачи и экстремум которой требуется найти. Если целевая функция (2.2) и система ограничений (2.1) линейны, то задача математического программирования называется задачей линейного программирования (ЗЛП). Допустимым решением (планом) задачи ЛП называется любой п-мерный вектор X  x1; x2 ;... xn  , удовлетворяющий системе ограничений и условиям неотрицательности переменных. 15 Оптимальным решением задачи ЛП называется такое допустимое решение (план) X *  x1* , x2* ,..., xn*  задачи, при котором целевая функция достигает экстремума. Таким образом, решение задачи ЛП заключается в нахождении оптимального решения (плана) X * и вычислении целевой функции при этом решении Z X *   Z max Z min  . Будем рассматривать три формы ЗЛП, а именно: 1) общая задача; 2) основная задача; 3) каноническая задача. Задачу ЛП будем называть общей задачей, если система ограничений (2.1) содержит, хотя бы одно неравенство, и основной задачей, если все ограничения системы (2.1) являются уравнениями. Таким образом, общая задача ЛП имеет вид: система ограничений – система т линейных уравнений и неравенств с п переменными a11 x1  a12 x 2  ....  a1n x n  b1 ; a x  a x  ....  a x  b ;  21 1 22 2 2n n 2  ... . . . . . . . . . . . a m1 x1  a m 2 x 2  ...  .a mn x n  bm . (2.3) Условие неотрицательности переменных, вытекающее из экономического смысла вводимых переменных, (2.4) x j  0; j  1,2,..., n. Линейная целевая функция, зависящая от п неизвестных Z  X   c1 x1  c2 x2  ...  cn xn  opt max или min , (2.5) где X  x1 , x2 ,..., xn  - вектор неизвестных. Общую задачу линейного программирования можно привести к основному виду при помощи следующих утверждений: 1. Неравенство a1 x1  a2 x2  ....  an xn  b равносильно равенству a1 x1  a2 x2  ....  an xn  xn1  b и простейшему неравенству xn1  0 . 2. Неравенство a1 x1  a2 x2  ....  an xn  b равносильно равенству a1 x1  a2 x2  ....  an xn  xn1  b и простейшему неравенству xn1  0 . Переменные, вводимые в неравенства ЗЛП, называются дополнительными или вспомогательными. Каноническая задача является частным случаем основной задачи, т. е. система ограничений содержит только уравнения, при этом система уравнений удовлетворяет двум условиям: 16 1) в каждом уравнении содержится переменная с коэффициентом, равным единице, отсутствующая во всех остальных уравнениях. Такая переменная называется базисной переменной; 2) свободные члены всех уравнений неотрицательны. Переменные, не являющиеся базисными, называются свободными переменными. В канонической задаче целевая функция выражается только через свободные переменные. При т=2, п=4 например, каноническую задачу можно представить в виде: Z  X   c0  c1 x1  c2 x2  opt max или min  a11 x1  a12 x 2  x3  b1  0,  a 21 x1  a 22 x 2  x 4  b2  0, x j  0, (2.6)  j  1  4 Здесь x3 и x 4 - базисные переменные. Если в канонической задаче положить все свободные переменные равными нулю, то базисные переменные будут равны неотрицательным свободным членам уравнений. Полученное таким способом решение ЗЛП называется базисным решением (планом) канонической задачи. При x1  x2  0 из системы (1.6) получим, что x3  b1  0; x4  b2  0 и базисное решение задачи будет иметь вид. При этом значение целевой функции Z  X   c0 . Из трех задач ЛП главная роль отводится канонической задаче, так как алгоритм симплекс-метода (речь о нем идет далее) непосредственно применяется к канонической задаче, а общая и основная задачи в конечном счете сводятся к канонической. Рассмотрим ЗЛП в основном виде. Ведем более короткую запись ЗЛП в матричной форме: Z  CX  min (max) при ограничениях AX  B, X  0 , где C  c1 , c2 ,..., cn  ;  a11  a A   21  ... . a  m1  1  1 a1n       x    b2  2 a22 a 2 n  X  ; B  ;  ...   ...  . . . .      x  b  a m 2 a mn   n  n a12 x b Векторная форма записи ЗЛП: Z  X   CX  min (max) при ограничениях A1 x1  A2 x2  ...  An xn  A0 ; и условии X  0 , 17 где CX – скалярное произведение векторов C  c1 , c2 ,..., cn  и X  x1 , x2 ,..., xn  ,  a11   a12   a1n   b1           a21   a22   a2 n  b  векторы A1   ; A2   ; ...; An   ; A0   2  (их называют векторами  ...   ...   ...   ...  a  a  a  b   m1   m2   mn   n условий) состоят соответственно из коэффициентов при переменных и свободных членов. Пример Привести к основному виду ЗЛП: Z  X   3x1  x2  x3  min  x1  2 x 2  x3  7   x1  x 2  2 x3  1 2 x  x  2 x  2 2 3  1 x j  0, j  1, 2, 3 Первое уравнение системы ограничений оставляем без изменения, во второе и третье неравенства введем дополнительные переменные x4  0 u x5  0 :  x1  2 x 2  x3  7   x1  x 2  2 x3  x 4  1 2 x  x  2 x  x  2 2 3 5  1 x j  0, j  1, 2, 3, 4, 5 . Целевая функция имеет вид Z  X   3x1  x2  x3  0 x4  0 x5  min .  Иногда возникает необходимость перейти в задаче от нахождения максимума к нахождению минимума, или наоборот. Для этого достаточно изменить знаки всех коэффициентов целевой функции на противоположные, а в остальном задачу оставить без изменения, т. е. Z  max   Z   min . Оптимальные решения полученных таким образом задач на максимум и минимум совпадают, а значения целевых функций при оптимальных решениях отличаются только знаком. Основные теоремы линейного программирования Теорема 1. Множество всех допустимых решений системы ограничений задачи линейного программирования является выпуклым. В частном случае, когда в систему ограничений входят только две переменные x1 и x 2 , это множество можно изобразить на плоскости. Так как речь идет о допустимых решениях ( x1 ≥ 0 и x2  0 ), то соответствующее множество будет располагаться в первой четверти декартовой системы координат. Это множество может быть замкнутым (многоугольник), незамкнутым (неограниченная многогранная область), состоять из 18 единственной точки и, наконец, система ограничений-неравенств может быть противоречивой. Теорема 2. Если ЗЛП имеет оптимальное решение, то целевая функция принимает максимальное или минимальное значение (достигает экстремума) в одной из угловых точек многогранника решений. Если целевая функция принимает максимальное (минимальное) значение более чем в одной угловой точке, то она принимает его в любой точке, являющейся выпуклой линейной комбинацией этих точек. Эта теорема является фундаментальной, так как она указывает принципиальный путь решения задач линейного программирования. Действительно, вместо исследования бесконечного множества допустимых решений для нахождения оптимального решения, надо исследовать лишь ограниченное число угловых точек многогранника решений. Теорема 3. Каждому допустимому базисному решению задачи линейного программирования соответствует угловая точка многогранника решений, и наоборот, каждой угловой точке многогранника решений соответствует допустимое базисное решение. Следствие т. 2 и т. 3: если задача линейного программирования имеет оптимальное решение, то оно совпадает, по крайне мере, с одним из ее допустимых базисных решений. Примеры задач линейного программирования 1. Задача об использовании ресурсов. При производстве двух видов продукции P1 и P2 используются три вида сырья (ресурсов). Составить такой план выпуска продукции, при котором прибыль от ее реализации была бы максимальной. Исходные данные приведены в таблице 2.1. Т а б л и ц а 2.1 Вид Запас Расход ресурса на единицу продукции P1 P2 ресурса ресурса 20 12 30 S1 S2 S3 Прибыль 2 1 1 40 1 1 3 50 Решение: составим экономико-математическую модель задачи. Обозначим вектор переменных величин X x1 , x2  , где x1 – объем выпуска продукции 1-го вида, x 2 - объем выпуска продукции 2-го вида. Для их изготовления потребуется единиц сырья в соответствии с таблицей. Так как потребление ресурсов не 19 должно превышать их запасов, то связь между запасами и потреблением сырья выразится системой неравенств (система ограничений): 2 x1  x2  20   x1  x2  12  x  3x  30 2  1 По смыслу задачи переменные x1  0; x2  0 . Суммарная прибыль от реализации продукции (целевая функция): Z  X   C1 x1  C2 x2  max; L X   40 x1  50 x2  max . Итак, экономико-математическая модель задачи: найти такой план выпуска продукции X x1 , x2  , удовлетворяющий системе ограничений, при котором функция Z  X  принимает максимальное значение. Задачу легко обобщить на случай выпуска п видов продукции с использованием т видов сырья (ресурсов). Обозначим x j  j  1, 2, ..., n – число единиц продукции Pj , запланированной к производству; bi i  1, 2, ..., m – запас ресурса S i ; aij – число единиц ресурса, затрачиваемого на изготовление единицы продукции Pj (число aij часто называют технологическими коэффициентами); c j – прибыль от реализации единицы продукции Pj . Тогда экономико-математическая модель задачи об использовании ресурсов в общей постановке примет вид: найти такой план X x1 , x2 ,..., x n  выпуска продукции, удовлетворяющей системе a11 x1  a12 x 2  ....  a1n x n  b1 ; a x  a x  ....  a x  b ;  21 1 22 2 2n n 2  . . . . . . . . . . . . . . . .  a m1 x1  a m 2 x 2  ....  a mn x n  bm ; и условию xi  0; i  1,2,..., n , при котором целевая функция Z  X   C1 x1  C2 x2  ...  Cn xn принимает максимальное значение. 2. Задача составления рациона (задача о диете, задача о смесях) Имеется 3 вида корма, содержащие питательные вещества А, В, С. При откорме животных каждое животное ежедневно должно получать не менее 60 ед. питательного вещества А, не менее 50 ед. питательного вещества В, 20 не менее 12 ед. питательного вещества С. Содержание единиц питательного вещества в 1 кг каждого из видов корма приведены в таблице 2.2. Т а б л и ц а 2.2 Питательные Количество ед. питательных веществ в 1 кг корма вещества 1-й вид 2-й вид 3-3 вид А 1 3 4 В 2 4 2 С 1 4 3 Стоимость 1 кг 9 у.е. 12 у.е. 10 у.е. корма Составить дневной рацион, обеспечивающий получение необходимого количества питательных веществ при минимальных денежных затратах, если цена 1 кг корма первого вида составляет 9 усл.ед., второго вида – 12 усл.ед., третьего вида – 10 усл.ед. Составим экономико-математическую модель задачи. Обозначим x1 ; x2 ; x3 – количество кормов 1, 2 и 3-го вида, входящих в дневной рацион. Тогда этот рацион будет включать x1  3x2  4 x3 – вещества А, 2 x1  4 x2  2 x3 – вещества В, x1  4 x2  3 x3 – вещества С. Так как содержание каждого питательного вещества должно быть соответственно не менее 60, 50 и 12 ед., то получим систему неравенств:  x1  3x 2  4 x3  60;  2 x1  4 x 2  2 x  50;  x  4 x  3x  12. 2  1 Кроме того, переменные (2.7) x1  0; x2  0; x3  0. (2.8) Общая стоимость рациона составит Z  X   9 x1  12 x2  10 x3 . Итак, экономико-математическая модель задачи: составить дневной рацион X  x1 , x2 , x3  , удовлетворяющий системе (2.7) и условию (2.8), при котором целевая функция Z  X   9 x1  12 x2  10 x3  min принимает минимальное значение. Задачу можно обобщить на любое количество переменных. 21 3. Задача об использовании мощностей (о загрузке оборудования) Для производства двух видов изделий А и В используются три типа технологического оборудования: S1 , S 2 и S 3 . Для производства единицы изделия А оборудование первого типа используется в течении 1 ч, оборудование второго типа – 3 ч, оборудование третьего типа – 3 ч. Для производства единицы изделия В оборудование первого типа используется в течение 2 ч, оборудование второго типа – 3 ч, оборудование третьего типа – 1 ч. На изготовление всех изделий предприятие может использовать оборудование первого типа не более чем 32 ч, оборудование второго типа – 60 ч, оборудование третьего типа – 50 ч. Прибыль от реализации единицы готового изделия А составляет 4 денежные единицы, а изделия В – 2 денежные единицы. Составить план производства изделий А и В, обеспечивающий максимальную прибыль от их реализации. Запишем исходные данные в таблицу 2.3: Т а б л и ц а 2.3 Тип Общий фонд Затраты времени на обработку одного оборудования рабочего времени изделия оборудования, ч А В S1 32 1 2 S2 60 3 3 S3 50 3 1 Прибыль, ден. ед. 4 2 Составим экономико-математическую модель задачи. Под планом производства будем понимать ответ на вопрос: сколько изделий А и сколько изделий В надо выпустить, чтобы прибыль была максимальна? Ведем переменные задачи: пусть x1 – объем выпуска изделия А, x 2 – объем выпуска изделия В. Прибыль рассчитывается по формуле Z  4 x1  2 x2 . Тогда математическая модель задачи будет иметь вид 1) Система ограничений:  x1  2 x 2  32;  3x1  3x 2  60; 3x  x  50. 2  1 22 2) По смыслу задачи переменные x1  0; x2  0 (условие неотрицательности переменных). 3) Целевая функция – суммарная прибыль от реализации изделий: Z ( x1 , x2 )  4 x1  2 x2  max . Итак, экономико-математическая модель задачи: найти такой план выпуска изделий X x1 , x2  , удовлетворяющий системе ограничений, при котором функция Z  X  принимает максимальное значение. Тема 3. Геометрическая интерпретация задачи линейного программирования В случае, когда система ограничений общей задачи ЛП содержит неравенства, связывающие только две переменные, задача допускает наглядный графический способ решения. При n  2 общая задача имеет вид: a11 x1  a12 x 2  b1 ; a x  a x  b ;  21 1 22 2 2  ... . . . ... .  a m1 x1  a m 2 x 2  bm ; x1  0; x2  0. Z  X   c1 x1  c2 x2  max  min  (3.1) (3.2) (3.3) Каждое линейное неравенство системы (3.1) на плоскости x1 0x2 определяет полуплоскость с границей, задаваемой прямой ai1 x1  ai 2 x2  bi , i  1,2,..., m ; условие неотрицательности переменных x1  0 и x2  0 определяют полуплоскости справа от прямой x2  0 и вверх от прямой x1  0 , т. е. первую координатную четверть. Если система (3.1) – (3.2) совместна, то пересечение полуплоскостей образуют выпуклый многоугольник, внутренние и граничные точки которого образуют область допустимых решений (множество планов). Этот многоугольник может быть ограниченным или представлять собой бесконечную выпуклую область. В случае несовместности системы (3.1)- (3.2) множество решений пусто. 23 Целевая функция Z  X   Z x1 , x2  является функцией двух переменных. Градиент функции ( grad Z ) – это вектор, координатами которого являются  Z Z  ; .  x  1 x 2  частные производные данной функции, т. е. grad Z   Z Z  c1;  c2 , вектор grad Z  c1 ;c2  перпендикулярен к линиям уровня x1 x 2 и направлен в сторону наибольшего возрастания функции. Линии уровня функции двух переменных – множество параллельных прямых Z  X   const, т. е. c1 x1  c2 x2  C , где С – произвольная постоянная. Решение задачи (3.1) – (3.3) сводится к отысканию такой точки X * области решений, через которую проходит линия уровня Z  X   const, соответствующая наибольшему (наименьшему) значению функции Z X *   Z max Z min  . Построив прямую c1 x1  c2 x2  const (например, при значении C=0), параллельным переносом ее перемещают по области решений в направлении grad Z , если Z  max или в противоположном направлении, если Z  min . Оптимальное значение целевая функция принимает в угловых точках или на границе многоугольника решений (в соответствии со свойствами задачи ЛП). Для нахождения координат точки, в которой целевая функция оптимальна, сначала по чертежу определяют те границы, пересечением которых является найденная точка. Затем из уравнений этих прямых составляется система уравнений, решение которой дает координаты точки. Вернемся к примеру о производстве двух видов изделий А и В, рассмотренному в теме 2. Математическая модель задачи. 1) Система ограничений  x1  2 x2  32;  3x1  3x2  60; 3x  x  50. 2  1 2) x1  0; x2  0 (условие неотрицательности переменных); 3) Целевая функция – суммарная прибыль от реализации изделий Z ( x1 , x2 )  4 x1  2 x2  max . Поскольку задача содержит две переменные, решим ее графически. 24 Для этого построим на плоскости ( x1 0 x2 ) области, описываемые системой  x1  2 x 2  32  ограничений: 3x1  3x 2  60 3x  x  50 2  1 Каждое из неравенств определяет полуплоскость с границей, задаваемой прямой. Выпишем соответствующие уравнения. 1) x1  2 x2  32 2) 3x1  3x2  60 3) x1  x2  50 Проведем на плоскости эти прямые (рис. 3.1) Рис. 3.1 Для того чтобы определить, какая из двух полуплоскостей является решением данного неравенства, нужно в любой из полуплоскостей выбрать пробную точку и подставить ее координаты в левую часть неравенства. Если получится верное неравенство, то содержащая пробную точку полуплоскость 25 будет решением неравенства; если неравенство не выполняется, то решением является полуплоскость, не включающая пробной точки. Если прямая не проходит через начало координат, то в качестве пробной точки удобно брать точку (0;0) – начало координат. Подставим в первое неравенство x1  0 и x2  0 , получим верное неравенство 0  32 , следовательно, точка (0;0) – принадлежит полуплоскости решений. Ее можно пометить каким-либо способом (на рис. 3.1 – это штриховка зеленого цвета). Аналогично решаем остальные неравенства. В результате три неравенства системы ограничений и условие неотрицательности переменных определяют на плоскости многоугольник АВСDЕ, ограниченный слева и снизу координатными осями (рис. 3.2). Рис. 3.2 Найдем вектор grad Z  4; 2 , он, как отмечалось ранее, указывает направление наискорейшего возрастания целевой функции. Начало этого вектора в начале координат, конец в точке с координатами (4;2). 26 Найдем максимальное значение целевой функции на области решений. Для этого построим произвольную линию уровня, например Z  X   4 x1  2 x2  0 . График линии уровня (построен пунктирной линией красного цвета) передвигается в направлении своего градиента, до тех пор, пока не достигнет граничной точки многоугольника (точка D). Эта точка является точкой пересечения линий (2) и (3). Решая систему, составленную из данных  x1  x2  20 уравнений  , 3x1  x2  50 получаем координаты точки D(15; 5), определяющие оптимальный план (решение) задачи X *  15; 5 . Таким образом, для получения максимальной прибыли объем выпуска изделия А – x1 должен составлять 15 единиц, объем выпуска изделия В – x 2 должен составлять 5 единиц. При этом прибыль от реализации изделий составит: Z  X *  Z max (15;5)  4  15  2  5  60  10  70 (ден.ед) Тема 4. Симплекс-метод Симплекс-метод разработан для решения ЗЛП в каноническом виде. Основное содержание симплексного метода состоит в следующем. Для последовательного улучшения решения необходимо:  определить способ нахождения первоначального допустимого базисного, т. е. опорного решения;  указать способ перехода от одного опорного решения к другому;  задать критерии, которые позволяют своевременно прекратить перебор решений на оптимальном решении или сделать заключение об отсутствии решения. Как указывалось ранее, задача линейного программирования называется приведенной основному виду, если 1) система ограничений содержит только равенства; 2) правые части системы ограничений и все переменные неотрицательны/ Иногда ЗЛП симплексным методом решают только в одном виде, например, на максимум. Будем рассматривать задачи, когда требуется найти максимум целевой функции. Тогда основная задача ЛП имеет вид Z  X   c1 x1  c2 x2  ...  cn xn  max 27 a11 x1  a12 x 2  ....  a1n x n  b1 a x  a x  ....  a x  b  21 1 22 2 2n n 2  ... . . . .  a m1 x1  a m 2 x 2  ....  a mn x n  bm x j  0; j  1, 2,..., n x j  0; j  1, 2, ..., n. (4.1) Векторная форма записи основной ЗЛП: Z  X   CX  max при ограничениях A1 x1  A2 x2  ...  An xn  B; и условии X  0 , где СХ – скалярное произведение векторов C  c1 , c2 ,..., cn  и X  x1 , x2 ,..., xn  ,  a11   a12   a1n   b1           a21   a22   a2 n  b  векторы A1   ; A2   ; ...; An   ; A0   2   ...   ...   ...   ...  a  a  a  b   m1   m2   mn   n (векторы условий) состоят соответственно из коэффициентов при переменных и свободных членов. Переход от общей формы к основной: 1. Если в правой части системы ограничений имеются отрицательные числа, то необходимо умножить на «-1» обе части равенства, в котором в правой части стоит отрицательное число. 2. Чтобы перейти от неравенства к равенству в системе ограничений, необходимо прибавить (вычесть) дополнительную неотрицательную переменную к левой части неравенства; 3. Если в задаче требуется найти минимум целевой функции, то вводим новую целевую функцию Z1  X   Z  X  , тогда max Z1   min Z . Т. е. достаточно изменить знаки всех коэффициентов целевой функции на противоположные, а в остальном задачу оставить без изменения. Оптимальные решения полученных таким образом задач на максимум и минимум совпадают, а значения целевых функций при оптимальных решениях отличаются только знаком. Пример. Решить ЗЛП Z  X   x1  2 x 2  3x3  min 2 x1  x 2  x3  1;  4 x1  2 x 2  x3  2; 3x  x  5; 3  1 x j  0; j  1, 2, 3 (4.2) Задача задана в общем виде. Приведем ее к основной задаче. Добиваемся, чтобы все правые части неравенств оказались неотрицательными. Для этого 28 второе неравенство системы умножаем на (-1), при этом знак неравенства меняется на противоположный. Система приобретает вид 2 x1  x 2  x3  1;   4 x1  2 x 2  x3  2; 3x  x  5; 3  1 x j  0; j  1,2, 3. Во все неравенства введем дополнительные переменные x4  0, x5  0, x6  0 : Z  X   x1  2 x 2  3x3  min  1; 2 x1  x 2  x3  x 4   4 x1  2 x 2  x3  x5  2; 3x  x3  x6  5;  1 x j  0; j  1, 2,..., 6. Целевая функция имеет вид Z1  X   Z  X    x1  2x 2  3x3  0x 4  x5  x6   min . Решение основной ЗЛП симплекс-методом проводится в симплекс-таблице, куда заносятся все исходные данные. Каждому уравнению системы ограничений соответствует строка таблицы. В первый столбец выписывается базис системы векторов-условий. Во второй столбец – коэффициенты целевой функции, соответствующие базисным переменным; в третий столбец выписываются свободные члены уравнений bi , остальные элементы таблицы равны коэффициентам при соответствующих неизвестных. Последняя строка называется индексной, о ней скажем позже. Последний столбец оставим для оценочных отношений, необходимых для расчета наибольшего возможного значения переменной. Т а б л и ц а 4.1 cn c1 c2 Базис Свободный … Оценочное Cб член отношение A1 A2 An … В b1 a11 a12 a1n … b2 a 21 a 22 a2 n … … … … … … Z X  bm a m1 am2 a mn Если система ограничений состоит только из уравнений, правые части которых неотрицательны, и в каждом уравнении содержится разрешенная переменная, то это задача в канонической форме. Векторы, соответствующие разрешенным переменным, составляют базис, а базисные переменные 29 канонической задачи составят естественный начальный опорный план (решение) X 0 при условии, что все неосновные переменные приняты равными нулю. Т. е. если, например, векторы A1 , A2 ,... Ak составляют базис, то начальное базисное решение будет X 0  x1 , x2 ..., xk ,0,0...0  b1 , b2 ,...bk ,0,0,...0 , k при этом значение целевой функции составит Z  X    ci bi i 1 Такая задача называется задачей с естественным базисом. Если система ограничений не имеет базиса, то базисное решение можно найти методом Гаусса, однако чаще всего применяют так называемый М-метод, который будет рассмотрен далее. Продолжим решение примера (3.2). Составим симплексную таблицу Базис Сб A4 A5 A6 A0 1 2 5 -1 1 3 A1 A2 A3 A4 A5 A6 2 -4 3 -1 2 1 -1 1 1 1 1 Т а б л и ц а 4.2 Оценочные отношения Векторы A4 , A5 , A6 образуют естественный ортонормированный базис, поэтому запишем их в первый столбец таблицы. Переменные x4 , x5 , x6 являются базисными переменными. Приравняв нулю свободные переменные ( x1  x2  x3  0) , получаем начальное базисное решение X 0  0,0,0,1,2,5 . С помощью вышеприведѐнной таблицы мы выполнили шаг решения ЗЛП симплексным методом. Эта часть решения называется нулевым шагом или нулевой итерацией. Чтобы проверить оптимальность найденного решения, нужно для каждого вектора A j при неизвестном x j вычислить оценку  j по формуле m  j  Cб A j  c j или  j   ci xij  c j ( C б A j – скалярное произведение векторов i 1 Cб и A j ). Для нашего примера: 30 0  2   0 1          1   0     4    1  1;  4   0    0   0  0; 0  3   0 0          0    1  0  0          2   0    2   1  1;  5   0    1   0  0;  0  0   0  0         0  1       3   0     1  3  3; 0  1      0 0      5   0    0   0  0. 0 1     Найденные значения оценок вносятся в индексную строку. Обратим внимание на то, что оценки всех базисных векторов равны нулю. Проверка на оптимальность – это анализ индексной строки. Возможны 3 случая: 1. Все элементы индексной строки неотрицательны (  j  0 ) в задаче на максимум (или неположительные  j  0 в задаче на минимум), тогда план оптимален и целевая функция достигла своего максимума. Ранее мы условились, что будем рассматривать каноническую задачу на максимум. Если решается задача на минимум, то возможно ее преобразование к задаче на максимум заменой целевой функции Z  X  на функцию Z1  X   Z  X  . Как известно решения этих задач совпадают. 2. Среди элементов индексной строки есть отрицательные (в задаче на максимум), но в столбцах над ними нет положительных элементов, тогда говорят, что целевая функция не ограничена сверху на области решений и оптимального решения не существует. 3. Среди оценок  j есть отрицательные, и в столбцах над ними есть хоть один положительный элемент. Значит, целевая функция не достигла максимума и надо переходить к следующему шагу. В нашем случае в индексной строке имеется две отрицательные оценки  2  1 и  3  3 . Следовательно, найденное решение X 0  0,0,0,1,2,5 неоптимальное и его можно улучшить за счет введения в ортонормированный базис одного из векторов, имеющих отрицательные оценки. Лучше всего для этого выбрать вектор с максимальной по абсолютной величине оценкой  j  0 . В нашем примере это  3  3 и, следовательно, вектор A3 будем вводить в базис. Пометим его стрелочкой, а весь столбец выделим серым цветом, этот столбец называется разрешающим. 31 Для определения вектора, выводимого из базиса, составляют так называемые  , если a ij  0; оценочные отношения, вычисляемые по формулам  i   bi , если a  0. ij  aij  В строке с минимальным  i >0 находится вектор, выводимый из базиса. Эту строку будем называть разрешающей (или ключевой) строкой. На пересечении разрешающей (i-й) строки и разрешающего (j-го) столбца находится разрешающий (ключевой) элемент (выделен жирным шрифтом и подчеркнут) Значения оценочных отношений для нашего примера внесены в последний столбец таблицы.  min =1. Следовательно, разрешающий элемент находится на пересечении первой строки и третьего столбца (помечен красным цветом) и, следовательно, вектор A4 выводится из базиса, а вектор A3 вводится. Теперь вектор, вводимый в базис, должен стать ортом, т.е. единичным вектором. Эта операция выполняется методом Гаусса: 1) разрешающую строку делим на разрешающий элемент (если он не равен 1, как в нашем случае), получаем новую разрешающую строку для следующей симплексной таблицы; 2) все остальные элементы разрешающего столбца обнуляем с помощью новой разрешающей строки. В результате получим новую симплексную таблицу (первая итерация). X 1  0,0,1,0,3,4 – новое базисное решение, значение целевой функции при этом решении Z  X 1   3 . Базис A4 A5 A6 j Сб В -1 1 3 A1 A2 A3 A4 A5 A6 1 2 5 2 -4 3 -1 2 1 -1 1 1 1 1 Z1  X 0   0 1 -1 -3  32 Т а б л и ц а 4.3 Оценочные отношения X 0  0,0,0,1,2,5 1 5  1 1    min  ;   1. Вектор A3 вводится, вектор A4 выводится Базис Сб В Z1  X 1   3 -1 1 3 A1 A2 A3 A4 A5 A6 2 -2 1 7 -1 1 1 -4 1 1 1 -1 3 1 1  A3 A2 A6 3 1 4 3 1 -2 3 1 1 2 1 -2 1 1 -1 1 Z1  X 2   15 -1 7 4 Окончание табл. Оценочные отношения X 1  0,0,1,0,3,4 3 4  1 1    min  ;   3. Вводится вектор A2 , A5 выводится X 2  0,3,4,0,0,1 1  3   min    1 / 3. A1 вводится, A6 выводится  A3 A2 A1 3 1 -1 4 11/3 1/3 1 1 1 Z1  X 3   46 / 3 2 1 -1/3 1/3 -2/3 1/3 19 3 11 3 2/3 1/3 1 3  1 11  X 3   , ,4,0,0,0 . 3 3  Все оценки отрицательны – план оптимален и единственен В результате трех итераций получено оптимальное решение X *   , 1 11  ,4,0,0,0  . 3 3  Так как исходная задача содержала три переменные, то отбросим значения дополнительных переменных: X *   , 1 11  ,4  . Оптимальное значение целевой 3 3  функции: Z min  X *  46 / 3 . Следует отметить, что, если в оптимальном решении есть оценки, равные нулю, у векторов, не вошедших в базис, то это говорит о том, что найденное оптимальное решение не единственно. Решение задачи ЛП с искусственным базисом Метод искусственного базиса применяется для решения основной ЗЛП в случае, когда задача не имеет начального решения с базисом из единичных векторов (ортонормированным базисом). 33 В этом случае в уравнения, не содержащие базисной переменной, добавляют со знаком «+» неотрицательные переменные, называемые искусственными. В отличие от дополнительных переменных, искусственные переменные влияют на целевую функцию Z  X  , они входят в нее с коэффициентами М, причем в задачу на максимум к коэффициентом –М, в задачу на минимум с коэффициентом +М. Величина М предполагается достаточно большим положительным числом M  1 , значение которого не задается. Поэтому такая задача носит название М-задачи. В случае решения задачи на максимум расширенная задача имеет вид Z ( X )  c1 x1  c2 x2  ...  cn xn  M xn1  ...  xnm   max при ограничениях: a11 x1  a12 x 2  ...  a1n x n  x n 1  b1 a x  a x  ...  a x  x  b  21 1 22 2 2n n n2 2  ..... a m1 x1  a m 2 x 2  ...  a mn x n  x n  m  bm xj  0. Векторы An1 , An2 ,..., Anm называются искусственными векторами. Данная задача имеет начальное опорное решение X 1  0,0,...,0, b1 , b2 ,..., bm  с базисом Б  ( An1 , An2 ,..., Anm ) (в этом случае исходный базис целиком состоит из искусственных векторов). Справедлива следующая теорема. 1) Если в оптимальном решении М-задачи все искусственные переменные равны 0, то соответствующие значения остальных переменных дают оптимальное решение исходной задачи; 2) если в оптимальном решении М-задачи хотя бы одна искусственная переменная отлична от 0, то исходная задача не имеет решения (из-за несовместимости системы ограничений); 3) если М-задача не имеет решения из-за неограниченности целевой функции, то и исходная задача решения не имеет. Особенности алгоритма метода искусственного базиса 1. Виду того, что начальное опорное решение расширенной ЗЛП содержит искусственные переменные, входящие в целевую функцию с коэффициентами -М (max) или +М (min), оценка разложений векторов условий  j  Cб X j  c j состоит из двух слагаемых  j  j  j M  . 34 Так как М – велико, то на первом этапе расчета для нахождения векторов, вводимых в базис, используется только слагаемое j M  . 2. Векторы, соответствующие искусственным переменным, которые выводятся из базиса опорного решения, исключаются из рассмотрения. 3. После того как все векторы, соответствующие искусственным переменным, исключены из базиса, расчет продолжается обычным симплексным методом с использованием оценок  j , не зависящих от М. 4. Переход от решения расширенной ЗЛП к решению исходной ЗЛП осуществляется с помощью указанных ранее замечаний. Пример. Найти решение следующей задачи: Z  X   x1  x2  4 x3  max  x1  4 x 2  x3  20;  2 x1  x 2  3x3  24;  x  x  6; 2  1 x j  0  j  1, 2, 3. Приведем задачу к основному виду, введя дополнительные переменные: Z  X   x1  x2  4 x3  0 x 4  0 x5  0 x6  Mx7  max  x1  4 x2  3 x3  x 4  20  2 x1  x2  3 x3  x5  24 x  x  x  6 2 6  1 x j  0  j  1,2,3,4,5,6   x1  4 x2  3x3  x 4  20  2 x1  x2  3x3  x5  24 x  x  x  x  6 2 6 7  1  В первых двух уравнениях содержатся базисные переменные x4 u x5 (это дополнительные переменные), а в третьем базисная переменная отсутствует, поэтому введем искусственную переменную x 7 , которая и будет являться базисной. Решаем М-задачу. Составим симплексную таблицу. Базис A4 A5  A7 Сб -M В 20 24 6 Z 0 = 0-6М 1 1 4 Т а б л и ц а 4.4 -M A1 A2 A3 A4 A5 A6 A7 1 2 1 4 1 1 1 3 1 1 -1 1 -1 1М  -1 -1 -4 1 35 Базис 1 1 4 Окончание таблицы -M A1 A2 A3 A4 A5 A6 1 3 -1 1 1 3 -4  1 1 1 2 1 -1 1 10/3 1/3 1 1 1 -1/3 1/3 1/3 2/3 -1 Z 2 =22 -4/3 4/3 5/3 3 5 3 1 1 1 2/1 1/10 1/10 Сб В Z 1 =6  A4 A3 A1 A2 A3 A1 4 1 10 4 6 1 4 1 A7 4/1 6/5 9/5 Все оценки положительны, поэтому решение X 3  3, 3, 5, 0, 0, 0 оптимально. Z 3 =26 Отбрасывая дополнительные переменные, получим ответ: Z max  26 при X *  3, 3, 5 . Тема 5. Понятие двойственности в линейном программировании Любой задаче линейного программирования (исходной, или прямой) можно оставить в соответствие другую задачу, которая называется двойственной или сопряженной. Обе задачи образуют пару двойственных задач. Каждая из задач является двойственной к другой задаче рассматриваемой пары. Экономическая интерпретация задачи, двойственной задаче об использовании сырья Пусть предприятие имеет т видов сырья в количестве b1 , b2 ,..., bm , которые используются для изготовления п видов продукции. Известно: a ij – расход i -го сырья на единицу j -й продукции; c j – прибыль при реализации единицы j -го вида продукции. Составить план выпуска продукции, обеспечивающий максимальную прибыль. 36 Математическая модель данной задачи (рассматривалась в теме 2) имеет вид: Z  X   c1 x1  c2 x2  ...  cn xn  max a11 x1  a12 x 2  ....  a1n x n  b1 a x  a x  ....  a x  b  21 1 22 2 2n n 2  ... . . . . . . . . . . . .  a m1 x1  a m 2 x 2  ....  a mn x n  bm xi  0; y1 y2 ... ym i  1, 2,..., n Здесь xi – объем производства j -го вида продукции. Предположим, что второй производитель хочет перекупить сырье. Необходимо определить оптимальные цены на сырье. Ведем вектор оценок (цен) видов сырья Y   y1 , y2 ,..., ym  . Затраты на приобретение i -го вида сырья в количестве bi равны bi yi . Второму производителю выгодно минимизировать суммарные затраты на приобретение всех видов сырья, поэтому целевая функция имеет вид F Y   b1 y1  b2 y 2  ...  bm y m  min . Первому производителю невыгодно продавать сырье, если суммарная стоимость всех видов сырья, расходуемых на каждое изделие j -й продукции, т. е. a1 j y1  a2 j y2  ....  amj ym меньше прибыли c j , получаемой от реализации этого изделия. Система ограничений приобретает вид: a11 y1  a 21 y 2  ....  a m1 y m  c1  a12 y1  a 22 y 2  ....  a m 2 y m  c 2  . . . . . . . . . . . . a1n y1  a 2 n y 2  ....  a mn y m  c n Очевидно, что оценки видов сырья должны удовлетворять условиям неотрицательности: yi  0; i  1, 2, ..., m . Т.о. связь исходной и двойственной задач состоит в том, что:  коэффициенты c j целевой функции исходной задачи являются свободными членами системы ограничений двойственной задачи;  коэффициентами целевой функции F (Y ) являются свободные члены системы ограничений исходной задачи;  матрица коэффициентов системы ограничений двойственной задачи есть транспонированная матрица коэффициентов системы ограничений исходной задачи;  в исходной задаче п неизвестных и т ограничений, в двойственной т неизвестных и п ограничений. 37 Рассмотренная пара задач относится к симметричным парам двойственных задач. В теории двойственности используются четыре пары двойственных задач (приведем их в матричной форме записи): Исходная задача Двойственная задача Симметричные пары F Y   YA0  min, 1. Z  X   CX  max, AX  A0 , AT Y  C , X  0; Y  0. F Y   YA0  max, 2. Z  X   CX  min, AX  A0 , AT Y  C , Y 0 X 0 3. Z  X   CX  max, Несимметричные пары AX  A0 , X  0; 4. Z  X   CX  min, AX  A0 , F Y   A0Y  min, YAT  C. F Y   A0Y  max, AT Y  C. X 0 Здесь C  c1 , c2 ,...cn  , Y   y1 , y2 ,..., ym  , 1. 2. 3. 4. 38  a11 a21....am1   b1   x1        b a a ... a   x    2 12 22 m 2 AT   , A0   , X   2  .  . .   ..   ..  . . b  x   a a ....a  mn   m  n  1n 2 n Общие правила составления двойственных задач Во всех ограничениях исходной задачи свободные члены должны находиться в правой части, а члены с неизвестными – в левой. Ограничения-неравенства исходной задачи должны быть записаны так, чтобы знаки неравенств у них были направлены в одну сторону. Если знаки неравенств в исходной задаче «  », то целевая функция должна максимизироваться, т.е. Z  X   max , а если «  », то минимизироваться. Каждому ограничению исходной задачи соответствует неизвестное в двойственной задаче, при этом неизвестное, отвечающее ограничениюнеравенству, должно удовлетворять условию неотрицательности. Если в системе ограничений исходной задачи имеются равенство, то неизвестное, отвечающее этому ограничению-равенству, может быть любого знака. 5. Целевая функция двойственной задачи имеет вид F Y   c0  b1 y1  b2 y2  ...  bm y m , где c 0 – свободный член целевой функции Z  X  исходной задачи, y1 , y2 ,..., y m – неизвестные в двойственной задаче, b1 , b2 ,..., bm – свободные члены в ограничениях исходной задачи. 6. Целевая функция F Y  двойственной задачи должна оптимизироваться противоположным по сравнению с Z  X  образом, т. е. если Z  X   max , то F Y   min и наоборот. Пример Пусть у предприятия имеется 2 вида сырья S1 u S 2 , остатки которых составляют 35 и 20 ед. Из них можно наладить производство 3 видов товаров T1 , T2 , T3 . От реализации единицы каждого вида продукции предприятие получит прибыль: от реализации товара T1 – 7 ден. ед., от реализации T2  6 ден. ед., от T3  18 ден. ед. Нормы расхода сырья приведены в т Т а б л и ц а 5.1 Вид сырья S1 S2 Прибыль, ден. ед. Запас сырья 35 20 T1 T2 T3 1 2 7 1 1 6 5 2 18 Задача 1. Наладить производство, тогда возникает вопрос о плане выпуска, который задается тремя неизвестными x1 , x2 , x3 – объемами выпуска продукции, которые в свою очередь подчинены условиям:  x1  x 2  5 x3  35;  2 x1  x 2  2 x3  20; x1  0; x 2  0; x3  0. Прибыль от реализации товаров Z  X   7 x1  6 x2  18x3  max . Вторая возможность: задача 2 – продать сырье другой организации, тогда возникает вопрос, по какой цене. Пусть y1 u y 2 – условные цены единицы сырья ( y1  0 ; y2  0 ). Требования к цене со стороны продающего предприятия: если продать сырье, идущее на изготовление ед. каждого товара, то выручка должна быть не менее чем прибыль от его реализации. 39 T1 Сырье S1 : Сырье S 2 : T2 T3  x1  x 2  5 x3  35 условная цена y1  2 x1  x 2  2 x3  20 условная цена y 2 Тогда ограничения для условных цен будут иметь вид: по T1 :  y1  2 y 2  7  по T2 :  y1  y 2  6 по T3 :  5 y1  2 y 2  18 yi  0; i  1, 2. Других требований к ценам предприятие-продавец предъявить не может. Что касается покупателя, то его пожелание заключается в сокращении до минимума расходов на покупку сырья: F  y   35 y1  20 y2  min . Таким образом, сформулированы 2 задачи: задача 1 (прямая, исходная) задача 2 (двойственная) Z  X   7 x1  6 x2  18x3  max F  y   35 y1  20 y2  min  x1  x 2  5 x3  35  2 x1  x 2  2 x3  20 x1  0; x 2  0; x3  0  y1  2 y 2  7   y1  y 2  6 5 y  2 y  18 2  1 yi  0; i  1, 2. В короткой, матричной, записи они будут иметь вид Z  X   CX  max, AX  B, X  0; F Y   YB  min, AT Y  C , Y  0. Основная теорема двойственности Если из пары двойственных задач одна обладает оптимальным решением (планом), то и другая имеет решение, причем для экстремальных значений целевых функций выполняется соотношение min Z  X   max F Y  . Если целевая функция одной из задач не ограничена, то другая не имеет решения вследствие несовместимости системы ограничений. Докажем эту теорему на примере. Продолжим рассмотрение примера, приведенного выше. Решим исходную задачу симплексным методом. Математическая модель задачи имеет общий вид Z  X   7 x1  6 x2  18x3  max 40  x1  x 2  5 x3  35;  2 x1  x 2  2 x3  20; x1  0; x 2  0; x3  0. Преобразуем систему ограничений к основному виду, введя дополнительные переменные.  x1  x 2  5 x3  x 4  35;  2 x1  x 2  2 x3  x5  20; xi  0; i  1  5, Z  X   7 x1  6 x2  18x3  0  x4  0  x4  max . Решение выполним в симплексной таблице. Базис  A4 A5 Z X  Свободный член В 35 20 j Z 0 =0 Cб 7 6 18 A1 A2 A3 A4 A5 1 2 -7 1 1 -8 5 2 -18 1 1  Т а б л и ц а 5.2 Оценочное отношение  35   5 ;   min    7  20   2  Вводим вектор A3 , выводим A4 A3 18 7 1/5 1/5 1 1/5  A5 6 8/5 3/5 -2/5 1 Z X  j Z 1 =126 17/5 12/5 18/5  7  1 / 5 ;   min    15 / 4  6   8 / 5   Вводим вектор A1 , выводим A5 A3  A1 Z X  18 7 j 25/4 15/4 Z 2 =138,75 1 1/8 3/8 -9/8  1 1/4 -1/8 -1/4 5/8 11/4 17/8  25 / 4  ;     min  1 / 8   10 15 / 4   3 / 8  41 Базис Cб Свободный член В 7 6 18 A1 A2 A3 A4 A5 Окончание таблицы Оценочное отношение Вводим вектор A2 , выводим A1 A3 A2 Z X  18 5 5 10 j Z 3 =150 -1/3 8/3 3 1 1 1/3 -2/3 2 -1/3 5/3 4 Все оценки неотрицательны, следовательно, получено оптимальное решение X опт *   0,10,5 ; Zопт  X *  150 . Решим теперь двойственную задачу. F  y   35 y1  20 y2  min  y1  2 y 2  7   y1  y 2  6 5 y  2 y  18 2  1 yi  0; i  1, 2. Система ограничений содержит две неизвестные, поэтому можно решить задачу графическим методом. Многоугольник решений – открытая область АВСD (рис. 5.1). 42 Рис. 5.1 Границу АВ образует прямая 5 y1  2 y2  18 , границу ВС – прямая y1  y2  6 , границу CD – прямая y1  2 y2  7 . Рассмотрим целевую функцию задачи F  y   35 y1  20 y2  min . Построим прямую, отвечающую значению функции F  y   0; 35 y1  20 y2  0 . Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление минимизации F(у). Начало вектора – точка (0; 0), конец – точка (35; 20). Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области. На рис. 5.1 эта прямая обозначена пунктирной линией. Прямая F(у) = const пересекает область в точке B. Так как точка B получена в результате пересечения прямых (2) и (3), то ее координаты удовлетворяют уравнениям этих прямых:  y1  y 2  6,  5 y1  2 y 2  18. Решив систему уравнений, получим y1  2; y2  4 . Откуда найдем минимальное значение целевой функции: 43 Fmin  y   35  2  20  4  150 . Тема 6. Транспортная задача Общая постановка задачи Под названием «транспортная задача» (ТЗ) объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к ЗЛП и могут быть решены симплексным методом. Однако матрица системы ограничений ТЗ настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение. Транспортная задача формулируется в следующем виде: однородный продукт, сосредоточенный в т пунктах отправления A1 , A2 ,..., Am в количествах a i единиц соответственно, следует доставить в п пунктов назначения B1 , 2 ,..., Bn в количествах b j . Стоимость перевозки продукта из i-го пункта отправления в j-й пункт назначения (тариф) равна cij . Исходные данные ТЗ обычно представляют в виде таблицы. 44 Т а б л и ц а 6.1 Запасы Пункты потребления поставщиков Bn B1 B2 … Пункты поставки A1 a1 c11 c12 … c1n A2 a2 c 21 c 22 … c2n … … … … … Am am Запросы потребителей c m1 cm2 … c mn b1 b2 … bn Требуется составить такой план перевозок (т. е. указать количество перевезенного груза от каждого поставщика к каждому потребителю), при котором будут полностью разгружены поставщики и удовлетворены потребители, а транспортные издержки будут минимальны. Если суммарные запасы поставщиков равна суммарным запросам потребителей, т. е. m n  a  b i 1 i j 1 j , то модель транспортной задачи называется закрытой, при нарушении этого условия – открытой. Рассмотрим задачу ТЗ закрытого типа. Составим математическую модель задачи. Пусть xij – количество единиц продукта, перевозимого по маршруту i, j  . Задача заключается в нахождении таких величин xij , при которых суммарная стоимость перевозок была бы минимальной. Таким образом, переменными (неизвестными) ТЗ являются xij i  1, 2,..., m; j  1, 2,..., n . Матрица  x11  x X mn  21 ...  x  m1 x12 x 22 ... xm 2 ... x1n   ... x 2 n  называется планом перевозок. ... ...   ... x mn  Так как произведение cij xij определяет затраты на перевозку груза из i-го пункта отправления в j-й пункт назначения, то суммарные затраты m n  c i 1 j 1 ij xij 45 определяют целевую функцию, минимум которой необходимо обеспечить по условию задачи. Следовательно, целевая функция имеет вид: m n Z  X    cij xij  c11 x11  c12 x12  ...  c mn x mn  min (6.1) i 1 j 1 Система ограничений состоит из двух групп уравнений:  x11  x12  ....  x1n  a1     x 21  x 22  ....  x 2 n  a 2  m уравнений ...................................     x  x  ....  x  a  m1 m2 mn m   x11  x 21  ....  x m1  b1   x  x  ....  x  b  22 m2 2  12  n уравнений ....................................   x  x  ....  x  b  2n mn n  1n xij  0; i  1, 2,..., m; j  1, 2,..., n (6.2) (6.3) Первые т уравнений соответствуют ограничениям по запасам поставщиков, т. е. учитывают вывозимую от поставщиков продукцию, последние п – продукцию, доставляемую потребителям. Математически транспортная задача ставится следующим образом: среди множества решений системы линейных уравнений (6.2) и неравенств (6.3) найти такое решение (план)  x11  x X *   21 ...  x  m1 x12 x 22 ... xm 2 ... x1n   ... x 2 n  , ... ...   ... x mn  которое минимизирует целевую функцию (6.1). Таким образом, транспортная задача является задачей ЛП и может быть решена симплекс-методом, алгоритм которого состоит из следующих шагов: 1. Построение начального плана. 2. Проверка его на оптимальность. Если план оптимален, то задача решена, в противном случае – переход к п. 3. 3. Построение нового плана с меньшей (или равной) стоимостью перевозок. Специфические особенности системы ограничений ТЗ привели к разработке упрощенного метода решения на каждом шаге алгоритма. Пример Имеются три пункта поставки однородного груза А1, А2, А3 и пять пунктов В1, В2, В3, В4, В5 потребления этого груза. На пунктах А1, А2, А3 находится груз 46 в количествах 90, 70, 110 т. В пункты В1, В2, В3, В4, В5 требуется доставить соответственно 50, 60, 50, 40, 70 тонн груза. Тарифы перевозок заданы в табл. 6.2. Т а б л и ц а 6.2 Пункты Пункты потребления Запасы поставки В1 В2 В3 В4 В5 А1 9 1 1 5 6 90 А2 6 4 6 8 5 70 А3 2 9 3 5 3 110 Потребности 50 60 50 40 70 Найти такой план перевозок, при котором общие затраты будут минимальными. Составим математическую модель задачи. Обозначим xij – количество груза, перевезенного от поставщика i к потребителю j. Становятся очевидными следующие ограничения (так как весь груз должен быть вывезен и все потребности удовлетворены полностью): 5 3 x  xi1  50 j 1 i 1  70 3j  110 5 3 x  xi3  50 j 1 i 1 3 x i4 3 i 1 2j x  xi 2  60 x  90 5 3 i 1 1j j 1 i 1 i5  40  70 При этом должна быть минимизирована целевая функция Z ( X )  9 x11  x12  x13  5 x14  6 x15  6 x21  4 x22  6 x23  8 x24   5 x25  2 x31  9 x32  3x33  5 x34  3x35  min . 1. Построение начального плана Прежде всего, проверим, является ли задача закрытой. 47 a1  a 2  a 2  90  70  110  270; b1  b2  b3  b4  b5  50  60  50  40  70  270. Поскольку 3 5 i 1 j 1  ai  b j , то мы имеем дело с закрытой ТЗ. Решение будем строить непосредственно в транспортной таблице (табл. 6.2), приведенной в условии примера. Начальный план строим методом северозападного угла. Принцип заполнения таблицы состоит в том, что, начиная с крайней левой верхней ячейки (принцип северо-западного угла), количество грузов вписывается в таблицу так, чтобы потребности полностью удовлетворялись или груз полностью вывозился. Пункты поставки А1 В1 9 50 А2 6 А3 2 Потребности 50 Пункты потребления В2 В3 В4 1 1 5 40 4 6 8 20 50 9 3 5 40 60 50 40 Т а б л и ц а 6.3 Запасы В5 6 90 70 70 5 70 3 110 270 В клетку (1,1) табл. 6.3, соответствующую северо-западному углу, помещаем 50 ед. груза из первого пункта поставки А1. Потребности потребителя В1 полностью удовлетворены. Оставшиеся 40 ед. груза первого поставщика отправляем второму потребителю, заполнив клетку (1,2). Недостающие потребителю В2 20 ед. груза возьмем у второго поставщика А2. Теперь потребитель B2 полностью обеспечен. У поставщика А2 остались 50 ед. груза, отправим их потребителю В3, полностью удовлетворив его запросы. Запасы поставщика А3 распределим между потребителями В4 и В5. Таблица 6.3 представляет собой начальный план задачи. Заполненные клетки таблицы (выделены цветом) соответствуют базисным переменным, пустые – свободным переменным из системы ограничений (6.2) (свободные переменные равны нулю). Поскольку система ограничений содержит n  m  1 линейно независимых уравнений, то и число базисных переменных будет таким же (т – число поставщиков, п – число потребителей). 48 План с n  m  1 заполненными клетками называется невырожденным, при меньшем числе заполненных клеток – вырожденным. Для того чтобы снять вырождение, необходимо в пустые клетки записать нулевые перевозки, дополнив число базисных переменных до количества n  m  1 . Ноль можно поставить только в пустую клетку, которая не образует цикла вместе с уже заполненными. Циклом называется такая последовательность клеток таблицы транспортной задачи i1 , j1 , i1 , j2 ; ... ik , j1  , в которой две и только две соседние клетки расположены в одной строке или столбце, причем первая и последние клетки также находятся в одной строке или столбце. Цикл изображают в виде замкнутой ломаной линии. В любой клетке цикла происходит поворот звена ломаной линии на 900. Простейшие циклы изображены на рис. 6.1. Рис. 6.1 Построение циклов начинают с какой-либо занятой клетки и переходят по столбцу (строке) к другой занятой клетке, в которой делают поворот на 900 и движутся по строке (столбцу) к следующей занятой клетке и т. д., пытаясь возвратиться к первоначальной клетке. Проверим вырожденность плана нашей задачи: мы имеем трех поставщиков ( т=3) и пять потребителей (п=5), следовательно n  m  1 =7. Заполненных клеток 6, т. е. план – вырожденный. Поставим нулевую поставку в клетку (3.3). Вычислим значение целевой функции (стоимость перевозки) для этого плана: Z  50  9  40 1  20  4  50  6  40  5  70  3  1280 . 2. Проверка плана на оптимальность При проверке плана на оптимальность воспользуемся методом потенциалов. Каждому поставщику Ai и потребителю B j поставим в соответствие некоторые числа U i и V j , называемые потенциалами, таким образом, чтобы для каждой занятой клетки сумма потенциалов равнялась бы стоимости перевозки, стоящей в этой клетке, т.е. U i  V j  Cij . 49 Количество неизвестных потенциалов составит n  m , а уравнений в системе ограничений всего n  m  1 . Поэтому один из потенциалов задается произвольно, после чего остальные потенциалы определяются однозначно. Обычно полагают U 1  0 . Критерий оптимальности: для того чтобы план ТЗ был оптимальным, необходимо и достаточно, чтобы для всех пустых (незанятых) клеток сумма потенциалов должна быть меньше или равна стоимости перевозки, стоящей в этой клетке, т. е. U i  V j  Cij . Проверим на оптимальность построенный нами план. Для этого вначале построим систему потенциалов. Полагаем U1=0, а далее Ui + Vj = сij для занятых клеток таблицы. (1.1): (1.2): (2.2): (2.3): (3.3): U1 + V1 = 9 ; V1 = 9 U1 + V2 = 1; V2 = 1 U2 + V2 = 4; U2 = 3 U2 + V3 = 6; V3 = 3 V3  U 3 =3; U3 = 0; (3.4): U3 + V4 = 5 ; V4 = 5; (3.5): U3 + V5 = 3 ; V5 = 3 Пункты поставки А1 В1 V1=9 U1=0 9 50 А2 U2=3 6 А3 U3=0 2 Потребности 50 Пункты потребления В2 В3 В4 V2=1 V3=3 V4=5 1 1 5 40 4 6 8 20 50 9 3 5 40 60 50 40 Т а б л и ц а 6.4 Запасы В5 V5=3 6 90 70 70 5 70 3 110 270 Проверим критерий оптимальности. Просматриваем строки и для каждой незанятой клетки проверяем выполнение условия U i  V j  Cij : (1.3): U1 + V3 = 3>1 на 2 (1.4): U1 + V4 = 5=5 (1.5): U1 + V5 = 3<6 (2.1): U2 + V1 = 12>6 на 6 50 (2.4): U2 + V4 = 8=8 (2.5): U2 + V5 = 6>5 на 1 (3.1): U3 + V1 = 9>2 на 7 (3.2): U3 + V2 = 1<9 Поскольку условие оптимальности не выполнено для 4 клеток, то построенный план не является оптимальным и может быть улучшен. 3. Улучшение плана Из условий, где критерий не выполняется, выбираем то условие, где разница максимальна. Это – клетка (3.1) и для нее строим цикл пересчета. Перебросим в ячейку (3.1) 50 единиц груза из ячейки (1.1). Чтобы компенсировать недостаток в первой строке, перебросим те же 50 единиц груза из ячейки (2.3) в ячейку (1.3). Теперь чтобы компенсировать недостаток в строке 2, перебросим из ячейки (3.5) 50 единиц в ячейку (2.5). Таким образом, образовался цикл, показанный в таблице пунктиром. Клетка (3.1) – вершина цикла. Она находится в пустой клетке, остальные вершины – в заполненных. Клетка (3.1) помечена знаком «+», далее последовательно расставлены знаки «-« и «+». Среди клеток, помеченных знаком «-« обычно определяют наименьшее значение перевозки и его перемещают по циклу. В нашем случае эта величина составила 50 единиц груза. Т а б л и ц а 6.5 Пункты Пункты потребления Запасы поставки В1 В2 В3 В4 В5 V1=9 V2=1 V3=3 V4=5 V5=3 А1 U1=0 9 1 1 5 6 90 -50 50 40 +50 А2 U2=3 6 4 6 8 5 70 20 -50 50 +50 А3 U3=0 2 9 3 5 3 110 +50 40 -50 70 Потребности 50 60 50 40 70 270 Получаем новую таблицу, для которой повторяем расчет потенциалов. Полагаем U1=0, а далее Ui + Vj = сij для занятых клеток таблицы. U1 + V2 = 1; V2 = 1 U1 + V3 = 1; V3 = 1 U2 + V2 = 4; U2 = 3 51 U2 + V5 = 5; U3 + V5 = 3; U3 + V1 = 2; U3 + V4 = 5 ; Пункты поставки В1 V1=1 А1 U1=0 А2 U2=3 А3 U3=1 Потребности 50 50 V5 = 2 U3 = 1 V1 = 5 V4 = 4 Т а б л и ц а 6.6 Пункты потребления Запасы В2 В3 В4 В5 V2=1 V3=1 V4=4 V5=2 9 1 1 5 6 90 40 50 6 4 6 8 5 70 20 50 2 9 3 5 3 110 40 20 60 50 40 70 270 Проверим критерий оптимальности: Ui + Vj  сij для свободных клеток. U1 + V1 = 1<9 U1 + V4 = 4<5 U1 + V5 = 2<6 U2 + V1 = 4<6 U2 + V3 =4<6 U2 + V4 =7<8 U3 + V2 =2<9 U3 + V3 =2<3 Критерий выполнен, значит, полученное решение оптимально.  0 40 50 0 0    Итак, оптимальный план перевозок: X *   0 20 0 0 50   50 0 0 40 20    Найдем минимальную стоимость перевозок. Z  40  50  4  20  5  50  2  50  5  40  3  20  780. Открытая модель транспортной задачи Открытые модели ТЗ могут быть двух видов: 52 а) m i 1 б) n  a  b i j 1 m n i 1 j 1 j – запас превышает потребность;  ai  b j – потребность превышает запас. В случае а) вводят фиктивный n  1 -й пункт назначения с потребностью m n i 1 j 1 bn 1   ai   b j и полагают стоимость перевозок в этот пункт назначения ci ,n1  0 . Соответствующие значения в оптимальном плане будут означать оставшийся неотправленным груз поставщиков. В случае б) вводится фиктивный m  1 -й пункт отправления с запасами груза n m j1 i 1 a m1   b j   a i и стоимостью перевозок cm1. j  0 . Груз, соответствующий поставкам от фиктивного поставщика, останется недополученным потребителями. Таким образом, открытая модель ТЗ может быть сведена к закрытой модели. 53