Езу9у. Учебное пособие Рекомендовано методическим советом Уральского федерального университета в качестве учебного пособия для студентов вуза, обучающихся по направлениям подготовки
 Скачать 5.85 Mb.
|
|
0 x 3 0 1 2 1 0 0 10 5 ← x 4 0 –1 2 0 1 0 6 3 x 5 0 1 –1 0 0 1 4 — Таблица 4.13 БП x 0 x 1 ↓ x 2 x 3 x 4 x 5 b i θ 1 Z = x 0 1 –10 0 0 5 0 30 ← x 3 0 2 0 1 –1 0 4 2 x 2 0 –1 2 0 1 0 6 — x 5 0 1 0 0 1 2 14 14 Получим второе неотрицательное базисное решение X 2 = (0, 3, 4, 0, 7) с ба- зисом (A 2 , A 3 , A 5 ) и значением целевой функции Z(X 1 ) = 30. На рис. 4.2 это точка А(0,3). В Z-строке осталось одно отрицательное число (−10). Поэтому разре- шающий столбец первый. Находим θ 01 = min {2, 14} = 2. Разрешающая строка тоже первая. Используя жордановы преобразования, получим новую таблицу (табл. 4.14). Рис. 4.2. Альтернативные оптимальные решения 10 x 1 x 2 4 5 O C A ν B x 1 + 2x 2 = 10 110 Таблица 4.14 БП x 0 x 1 x 2 x 3 x 4 ↓ x 5 b i θ 4 Z = x 0 1 0 0 5 0 0 50 x 1 0 2 0 1 –1 0 4 — x 2 0 0 4 1 1 0 16 16 ← x 5 0 0 0 –1 3 4 24 8 Третье базисное решение X 3 = (2, 4, 0, 0, 6) с базисом (A 1 , A 2 , A 5 ) и значением целевой функции Z(X 3 ) = 50. На рис. 4.2 этому решению соответствует точка В (2, 4). В Z-строке не осталось отрицательных чисел. Поэтому полученное допустимое базисное решение X 3 = (2, 4, 0, 0, 6) и соотвествующее ему значение Z(X 3 ) = 50 оптимальны. Обратим внимание на столбец x 4 табл. 4.14: коэффициент целевой функции при x 4 равен нулю, хотя x 4 — небазисная переменная. Это означает, что вектор A 4 можно ввести в базис без изменения значения целевой функции, но значение x 4 изменится. Аналогично находим θ 04 = min{16, 8} = 8. Разрешающий элемент — число 3 в выделенной рамке (табл. 4.14). Используя жордановы преобразования, получим новую таблицу (табл. 4.15). Таблица 4.15 БП x 0 x 1 x 2 x 3 x 4 x 5 b i Z = x 0 1 0 0 5 0 0 50 x 1 0 6 0 2 0 4 36 x 2 0 0 12 4 0 –4 24 x 4 0 0 0 –1 3 4 24 Итак, мы имеем еще одно оптимальное решение X 4 = (6, 2, 0, 8, 0) с базисом (A 1 , A 2 , A 4 ) и значением целевой функции Z(X 4 ) = 50. На рис. 4.2 это точка С(6, 2). Итак, с помощью симплекс-метода мы нашли две вершины В(2, 4) и С(6, 2), значение целевой функции в которых одно и то же: Z(X 3 ) = Z(X 4 ) = 50. Понятно, что целевая функция принимает одно и то же значение во всех точках отрезка BC. Таким образом, задача имеет бесконечное множество решений. Каждое из них представляет собой выпуклую линейную комбинацию решений X 3 = (2, 4, 0, 0, 6) и X 4 = (6, 2, 0, 8, 0). Записываем это в виде max 3 4 (1 ) , 0 1, X X X = α + − α ≤ α ≤ где 3 4 max (2, 4, 0, 0, 6), (6, 2, 0, 8, 0), 50. X X Z = = = 111 На практике альтернативные оптимальные решения позволяют сделать выбор среди множества решений (в нашем случае все точки отрезка BC) без ухудшения значения целевой функции. Если рассматривать задачу планиро- вания производства двух видов товара, которые соответствуют неизвестным x 1 и x 2 , то более выгодно производить два вида товара, а не один, что как раз соответствует нашему случаю. Итак, X max = αX 3 + (1 − α)X 4 , 0 ≤ α ≤ 1, X 3 = (2, 4), X 4 = (6, 2), Z max = 50. Пример 4.4 (неограниченная целевая функция).Решить симплексным ме- тодом следующую задачу линейного программирования: ( ) 1 2 3 2 5 max(min), Z X x x = + + → 1 2 1 2 1 2 8, 3 6, 3; x x x x x − + ≤ − ≥ ≥ 2 0. x ≥ Решение. Приведем задачу к каноническому виду. Для этого введем допол- нительные неизвестные x 3 , х 4 , x 5 : 1 2 3 1 2 4 1 5 2 8, 3 6, 3; x x x x x x x x − + + = − − = − = 0, 1, 5. j x j ≥ = Система линейных уравнений не является разрешенной. Можно вначале найти первое неотрицательное базисное решение, а потом применить симплекс- метод. Сделаем это сразу с помощью симплекс-таблиц. Таблица 4.16 БП x 0 x 1 ↓ x 2 x 3 x 4 x 5 b i Z = x 0 1 –3 –2 0 0 0 5 x 3 0 –1 2 1 0 0 8 0 3 –1 0 –1 0 6 0 1 0 0 0 –1 3 Вначале не будем обращать внимание на коэффициенты целевой функции: наша цель получить первое неотрицательное базисное решение. Выберем разре- шающий элемент во второй строке и в столбце x 1 табл. 4.16, получим табл. 4.17. 112 Таблица 4.17 БП x 0 x 1 x 2 ↓ x 3 x 4 x 5 b i Z = x 0 1 0 –3 0 –1 0 11 x 3 0 0 5 3 –1 0 30 x 1 0 3 –1 0 –1 0 6 0 0 1 0 1 –3 3 Далее в качестве разрешающего элемента выбираем число 1 на пересече- нии столбца x 2 и третьей строки. В результате жордановых преобразований приходим к табл. 4.18. Таблица 4.18 БП x 0 x 1 x 2 x 3 x 4 x 5 ↓ b i Z = x 0 1 0 0 0 2 –9 20 ← x 3 0 0 0 1 –2 5 5 x 1 0 1 0 0 0 –1 3 x 2 0 0 1 0 1 –3 3 Итак, первое допустимое решение получено: X 1 = (3, 3, 5, 0, 0) с базисом (A 3 , A 1 , A 2 ) и значением Z(X 1 ) = 20. На рис. 4.3 этому решению соответствует точка В(3, 3). Будем наращивать переменную x 5 (в оценочной строке при x 5 наимень- ший отрицательный коэффициент (−9)). Выбираем в качестве разрешающего элемента число 5 (это единственное положительное число в этом столбце). Таблица 4.19 БП x 0 x 1 x 2 x 3 ↓ x 4 x 5 b i θ 3 Z = x 0 → min 5 0 0 9 –8 0 145 ← x 5 0 0 0 1 –2 5 5 5 x 1 0 5 0 1 –2 0 20 20 x 2 0 0 5 3 –1 0 30 10 Получено новое решение X 2 = (4, 6, 0, 0, 1) с базисом (A 5 , A 1 , A 2 ) и значением целевой функции / 1 ( ) 145 5 29 Z X = = (табл. 4.19). На рис. 4.3 это точка С(4, 6). Это решение не является оптимальным, можно увеличить значение целевой функции за счет x 4 (отрицательная оценка (−8) переменной x 4 ). Но все коэф- фициенты этого столбца отрицательны, а это приводит к недопустимому ре- шению. Вывод: целевая функция не ограничена в направлении переменной x 4 , т. е. Z max = + ∞. Кроме того, множество ограничений также не ограничено в на- правлении возрастания x 4 113 Рассмотрим теперь задачу Z(X) = 3x 1 + 2x 2 + 5 → min при тех же ограниче- ниях. Строка целевой функции (табл. 4.19) эквивалентна уравнению Z = x 0 = =−9/5x 3 + 8/5x 4 + 29. Переменная x 3 равна нулю, ее возрастание хотя бы на едини- цу приводит к уменьшению целевой функции Z = x 0 ≡ −9/5x 3 + 8/5x 4 + 29 на 9/5. Среди оценок Z-строки положительная только при x 3 , поэтому переменную x 3 вводят в число базисных. Находим θ 03 = min {5, 20, 10} = 5. Разрешающий элемент выбираем в первой строке: число 1 (выделено рамкой). Используя жордановы преобразования, получим новую таблицу (табл. 4.20). Таблица 4.20 БП x 0 x 1 x 2 x 3 x 4 ↓ x 5 b i θ 4 Z = x 0 1 0 0 0 2 –9 20 x 3 0 0 0 1 –2 5 5 — x 1 0 1 0 0 0 –1 3 — ← x 2 0 0 1 0 1 –3 3 3 Получено следующее допустимое решение X 3 = (3, 3, 5, 0, 0) с базисом (A 3 , A 1 , A 2 ) и значением Z(X 3 ) = 20. Обратим внимание на то, что значение целевой функции уменьшилось на 9 ед. В строке целевой функции имеется положи- тельный коэффициент 2 при x 4 . Единственное положительное число 1 в этом столбце находится в третьей строке, выбираем его в качестве разрешающего элемента и выделяем рамкой. В результате имеем табл. 4.21, в Z-строке которой нет положительных коэффициентов. Рис. 4.3. Геометрическая иллюстрация неограниченного решения 2 x 1 B C 4 0 x 2 ν A 114 Таблица 4.21 БП x 0 x 1 x 2 x 3 x 4 x 5 b i Z = x 0 1 0 –2 0 0 –3 14 x 3 0 0 2 1 0 –1 11 x 1 0 1 0 0 0 –1 3 x 4 0 0 1 0 1 –3 3 Строка целевой функции эквивалентна уравнению Z = x 0 ≡ 2x 2 + 3x 5 + 14. В силу неотрицательности переменных верно неравенство 0 2 5 2 3 14 14. x x x ≡ + + ≥ Итак, X * = Х min = (3, 0, 11, 3, 0), Z min = 14. На рис. 4.3 решению X * = (3, 0, 11, 3, 0) соответствует точка A(3, 0). Ответ. Z min = 14 при X * = (3, 0); Z max = + ∞. Пример 4.5 (отсутствие допустимых решений). Решить симплексным методом следующую задачу линейного программирования: ( ) 1 2 4 6 3 3 max, Z X x x x = − + + → 1 2 4 1 2 4 1 2 3 3 2 18, 2 2 9, 2 4 2 10; x x x x x x x x x + + ≥ + + ≤ − − + = 0, 1, 4. j x j ≥ = Решение. Приведем задачу линейного программирования к каноническому виду. Для этого введем дополнительные переменные x 5 , x 6 : 1 2 4 5 1 2 4 6 1 2 3 3 2 18, 2 2 9, 2 4 2 10; x x x x x x x x x x x + + − = − − − − = − + = 0, 1, 6. j x j ≥ = Система линейных уравнений не является разрешенной. Можно вначале найти первое неотрицательное базисное решение, а потом применить симплекс- метод. Сделаем это, как и в предыдущем примере, сразу с помощью симплекс- таблиц. Заметим, что наш выбор определения базисного решения реализуется «легко» при небольшом числе переменных (табл. 4.22). При большом числе переменных это сделать трудно. Далее (п. 4.6) изложен метод искусственных переменных, решающий эту проблему. 115 Таблица 4.22 БП x 0 x 1 x 2 ↓ x 3 x 4 x 5 x 6 b i Z = x 0 1 6 –3 0 –3 0 0 0 0 3 2 0 1 –1 0 18 0 –2 –1 0 –2 0 –1 9 x 3 0 2 –4 2 0 0 0 10 В качестве разрешающего элемента выбираем число 2 на пересечении столбца x 2 и первой строки. В результате жордановых преобразований придем к табл. 4.23. Таблица 4.23 БП x 0 x 1 x 2 x 3 x 4 x 5 x 6 b i Z = x 0 2 21 0 0 –3 –3 0 54 x 2 0 3 2 0 1 –1 0 18 0 –1 0 0 –3 –1 –2 36 x 3 0 8 0 2 2 –2 0 46 Разрешающий элемент выбран в первой строке и в третьей, осталось вы- брать во второй, но это невозможно: все коэффициенты при неизвестных вто- рого уравнения отрицательны. То есть в уравнении, соответствующем второй строке: 1 4 5 6 3 2 36, x x x x − − − − = левая часть неположительна, а правая положительна. Таким образом, огра- ничения задачи линейного программирования несовместны, т. е. не могут выполняться одновременно. Поэтому задача не имеет допустимых решений. Ответ. Система ограничений несовместна. 4.6. Метод искусственного базиса В задачах линейного программирования, где все ограничения являются неравенствами типа « ≤ » (с неотрицательной правой частью), дополнительные переменные позволяют сформировать начальное допустимое базисное решение. В этом случае матрица системы уравнений канонической формы обязательно включает в себя единичную матрицу. И хотя мы уже находили первое базис- ное решение в задачах с ограничениями в виде равенств или неравенств типа « ≥ », изложим общий способ построения начального допустимого базисного 116 решения задачи линейного программирования с помощью искусственных переменных. 4.6.1. М-метод Рассмотрим задачу линейного программирования в канонической форме: 1 1 2 2 ( , ) m ( ax min , ) ( ) n n Z X c x c x c x c x = = + + + → 1 ( 1, ), n ij j i j a x b i m = = = ∑ 0 ( 1, ). j x j n ≥ = Будем считать, что: 1) r(A) = m < n, где A = (a ij ) m×n , 2) правые части системы ограничений неотрицательны, т. е. b i ≥ 0 ( 1, ). i m ∀ = Допустим, что единичный базис матрицы A не выделен. Составим расши- ренную задачу с использованием искусственных переменных, которые вводятся в ограничения-равенства для получения первого допустимого решения с еди- ничным базисом. Каждая искусственная переменная вводится в левую часть одного из уравнений с коэффициентом +1 и в целевую функцию в задаче на мак- симум с коэффициентом (−M), а в задаче на минимум с коэффициентом +M. Число М считается «большим» (M 1). Тем самым новые переменные «штра- фуются». «Штраф» составляет произведение числа М на сумму искусственных переменных, взятое со знаком «минус», в задаче на максимум, и со знаком «плюс» — в задаче на минимум. Естественно считать, что процесс оптимизации симплекс-метода приведет к нулевому значению новых переменных. Для определенности рассмотрим задачу на максимум: ( ) 1 1 2 2 1 2 max, n n n n n m Z X c x c x c x M x M x M x + + + = + + + − − − − → (4.27) 11 1 12 2 1 1 1 21 1 22 2 2 2 2 1 1 2 2 , , ; n n n n n n m m mn n n m m a x a x a x x b a x a x a x x b a x a x a x x b + + + + + + + = + + + + = + + + + = (4.28) ( ) ( ) 0 1, ; 0 1, . j i x j n m b i m ≥ = + ≥ = (4.29) Признак оптимальности решения: если расширенная задача ли- нейного программирования (4.27)–(4.29) имеет оптимальное решение 0 1 2 ( , , , ,0, ,0), n X x x x = у которого все искусственные переменные равны 117 нулю, то исходная задача имеет оптимальное решение 1 2 ( , , , ), n X x x x = ко- торое получается из 0 X отбрасыванием нулевых искусственных переменных. Признак отсутствия решения ввиду несовместности системы ограниче- ний: если расширенная задача имеет оптимальное решение, у которого хотя бы одна искусственная переменная не равна нулю (т. е. существует j * такое, что 0), n j x ∗ + > то исходная задача не имеет решения ввиду несовместности системы ограничений. Признак отсутствия решения ввиду неограниченности целевой функции: если расширенная задача не имеет решения ввиду неограниченности целевой функции, то исходная задача не имеет решения по той же причине. А л г о р и т м метода искусственного базиса: 1. Введем новую переменную 0 1 1 2 2 1 2 n n n n n m Z x c x c x c x Mx Mx Mx + + + ≡ = + + + − − − − и перепишем это уравнение в виде 0 1 1 2 2 1 2 0. n n n n n m x c x c x c x Mx Mx Mx + + + − − − − + + + + = 2. Строим симплекс-таблицу (табл. 4.24). Таблица 4.24 БП 0 x x 1 x 2 … x n x n+1 x n+2 … x n+m b i М-строка 0 0 0 … 0 М М … М 0 0 Z x = 1 –c 1 –c 2 … –c n 0 0 … 0 0 x n+1 0 a 11 a 12 … a 1n 1 0 … 0 b 1 x n+2 0 a 21 a 22 … a 2n 0 1 … 0 b 2 … … … … … … … … … … … x n+m 0 a m1 a m2 … a mn 0 0 … 1 b m |