Езу9у. Учебное пособие Рекомендовано методическим советом Уральского федерального университета в качестве учебного пособия для студентов вуза, обучающихся по направлениям подготовки
 Скачать 5.85 Mb.
|
|
Задачи для самостоятельного решения Решить графически: 3.1. 1 2 ( ) 2 max, Z X x x = + → 3.2. 1 2 ( ) 2 3 max, Z X x x = − → 1 2 1 2 1 2 1 2 2 4, 5 40, 2 3 7, 4; x x x x x x x x − + ≥ − + ≤ − ≤ + ≤ 1 2 1 2 1 2 10, 15, 0 7, 0 10. x x x x x x + ≥ − ≤ ≤ ≤ ≤ ≤ , 1 2 0 0. x x ≥ ≥ 3.3. 1 2 ( ) 3 max, Z X x x = − → 3.4. 1 2 ( ) 2 5 min, Z X x x = + → 1 2 1 2 1 1 2 2 1 2, 2 2 3, 0 1, 1 2 2; 0. x x x x x x x x ≤ + ≤ ≤ − ≤ ≤ ≤ ≤ − ≤ ≥ 1 2 1 2 1 2 3 4, 8 3 16, 2, 0 9. x x x x x x + ≥ − ≥ − ≥ ≤ ≤ целевым функциям одинаковое оптимальное значение. Это касается ответов к задачам 3.10–3.15. Иногда указываются несколько возможных ответов. 86 3.5. Z 1 2 ( ) 5 3 max, X x x = + → 3.6. 1 2 ( ) 3 4 min, Z X x x = + → 1 2 1 2 1 2 1 2 2, 3 2, 4 5 16, 1, 0 4. x x x x x x x x + ≥ − + ≥ − − ≥ − ≥ ≤ ≤ 1 2 1 2 1 2 0 2 3, 1 0, 0 2, 0 3. x x x x x x ≤ + ≤ − ≤ − ≤ ≤ ≤ ≤ ≤ 3.7. 1 2 ( ) 3 min, Z X x x = − → 3.8. 1 2 ( ) 5 4 min, Z X x x = − + → , 1 2 1 2 1 2 1 2 2 3 10, 2 6, 2 1; 0 0. x x x x x x x x + ≤ − ≤ + ≥ ≥ ≥ , 1 2 1 2 1 2 1 2 1 2 1 1, 1, 3 2 2, 2 2; 0 0. x x x x x x x x x x − ≤ − + ≤ + ≥ − − + ≤ − ≤ ≥ ≥ 3.9. 1 2 ( ) 2 3 min, Z X x x = + → 3.10. 1 2 ( ) 5 7 min, Z X x x = + → 1 2 1 2 1 2 1 2 3 2 9, 1, 2 2; 0, 0. x x x x x x x x + ≥ − + ≥ − ≥ − ≥ ≥ ( ) 5 1 2 3 4 1 2 3 5 1 2 4 5 8 4 30, 8 16 54, 8 18 50; 0 1, . i x x x x x x x x x x x x x i + − − = + − − = + − − = ≥ = 3.11. 1 2 ( ) min, Z X x x = − + → 3.12. 1 2 ( ) 3 max, Z X x x = + → ( ) 5 1 2 3 4 5 1 2 3 5 1 2 3 4 4 3 6, 4 15, 2 4 3; 0 1, . i x x x x x x x x x x x x x x i − − + + = + + + = − − + = − ≥ = ( ) , 6 1 2 5 6 1 2 4 6 1 2 3 5 2 3 4 2 10, 2 2 25, 2 3 9, 6 36; 0 1, . i x x x x x x x x x x x x x x x x i − + + = + + + = − − + = − + + = ≥ = 3.13. 1 2 4 5 ( ) 3 2 3 min, Z X x x x x = − + + + → 3.14. 1 2 3 4 5 ( ) 10 4 5 min, Z X x x x x x = + + + − − → ( ) , 6 1 2 3 4 1 2 4 5 1 2 4 5 1 2 6 3 2 2, 4 21, 4 13, 3; 0 1, . i x x x x x x x x x x x x x x x x i − − + = − + + = − − + = + − = ≥ = ( ) , 5 1 2 3 1 2 4 1 2 5 2 20, 2 3 12, 2 4 16; 0 1, . i x x x x x x x x x x i + + = − − = − − − + = − ≥ = 3.16.'>3.15. 1 2 5 ( ) 2 min, Z X x x x = + + → 3.16. 1 2 5 ( ) 3 5 min, Z X x x x = + + → ( ) 5 1 2 3 4 5 2 3 4 5 3 4 5 5, 2, 1; 0 1, . i x x x x x x x x x x x x x i + + + + = + + − = − + = ≥ = ( ) 5 1 2 3 4 5 2 3 4 5 3 4 5 5, 2, 3; 0 1, . i x x x x x x x x x x x x x i − + + + = − − + = − − − = ≥ = Ответы к задачам для самостоятельного решения 3.1. ( ) 3,8; 0,2 ; max ( ) 7,8. X Z X = = 3.2. ( ) 7, 3 ; max ( ) 5. X Z X = = 3.3. Система ограничений несовместна. 3.4. Значение целевой функции не ограничено. 3.5. ( ) 14, 4 ; max ( ) 82. X Z X = = 3.6. ( ) 0, 0 ; min ( ) 0. X Z X = = 3.7. ( ) 0,10 3 ; min ( ) 10 3. X Z X = = − 3.8. ( ) 1, 0 ; min ( ) 5. X Z X = = − 3.9. ( ) 1,4; 2,4 ; min ( ) 10. X Z X = = 3.10. ( ) 3, 2, 2, 0, 0 ; min ( ) 29. X Z X = = 3.11. ( ) 4,1,7,0,0 , X = а также ( ) 3,0,9,0,3 ; X = min Z(X) = −3. 3.12. ( ) ( ) 3, 6, 0, 0, 3,7 ; max 21. X Z X = = 3.13. ( ) ( ) 7,2;11,8; 0; 4; 0;16 ; min 10. X Z X = = 3.14. ( ) ( ) 6, 8, 0, 0, 28 ; min 72. X Z X = = − 3.15. ( ) 0, 3, 0,1 2, 3 2 , X = а также ( ) 0, 0, 3 2, 2, 3 2 ; X = ( ) min 3 2. Z X = 3.16. ( ) 3, 1, 3, 0, 0 ; X = ( ) min 6. Z X = 88 4. СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 4.1. Симплекс-метод Симплексный метод — систематическая процедура решения задач линей- ного программирования, заданных в канонической форме. Симплекс-метод основывается на следующем: • область допустимых решений является выпуклым и многогранным мно- жеством с конечным числом вершин; • оптимальным решением задачи линейного программирования является одна из вершин области допустимых решений; • вершины области допустимых решений соответствуют некоторым допу- стимым (неотрицательным) базисным решениям системы ограничений задачи. С помощью симплекс-метода осуществляется целенаправленный перебор вершин допустимой области задачи линейного программирования. Каждое базисное решение проверяется на оптимальность, а операции однократного замещения осуществляются таким образом, чтобы значение целевой функции не уменьшалось в задаче на максимум или не увеличивалось в задаче на ми- нимум. Таким образом, с помощью симплекс-метода за конечное число шагов можно либо найти оптимальное решение, либо установить его отсутствие. Симплекс-метод был предложен Дж. Данцигом * в 1949 г., но еще ранее близкие идеи были разработаны Л. В. Канторовичем ** Для задач небольшой размерности симплекс-метод реализуется «вручную». Для решения задач большой размерности используют ЭВМ и специальное программное обеспечение. * Джордж Бернард Данциг (1914–2005) — американский математик, разработчик алгоритма, применяемого в решениях задач симплекс-методом. Считается основоположником линейного программирования, наряду с Леонидом Канторовичем и Джоном фон Нейманом. ** Леонид Витальевич Канторович (1912–1986) — советский математик и экономист, один из создателей линейного программирования. Единственный в СССР лауреат Нобелевской пре- мии по экономике 1975 г. «за вклад в теорию оптимального распределения ресурсов». 89 Далее рассмотрим два варианта оформления симплекс-метода. Первый ва- риант — это классическое изложение исполнения симплекс-процедуры, второй вариант, на наш взгляд, лучше (возможно, легче) использовать при решении задач «вручную». Оба варианта реализуются по схеме: 1) определение начального (первого) допустимого базисного решения задачи; 2) осуществление перехода к лучшему решению; 3) прекращение перебора решений на оптимальном решении или заклю- чение об отсутствии решения. 4.2. Теоретическое обоснование симплекс-метода Рассмотрим следующую задачу линейного программирования, в которой многогранное множество определено с помощью равенств, а на переменные накладывается условие неотрицательности: ( ) ( ) 1 1 2 2 max min , n n Z X c x c x c x = + + + → (4.1) 11 1 12 2 1 1 21 1 22 2 2 2 1 1 2 2 , , ; n n n n m m mn n m a x a x a x b a x a x a x b a x a x a x b + + + = + + + = + + + = (4.2) 0 ( 1, ). j x j n ≥ = (4.3) Будем считать, что: 1) r(A) = m < n, где A = (a ij ) m×n , т. е. r(A) совпадает с числом равенств-огра- ничений (4.2); 2) правые части системы ограничений неотрицательны, т. е. b i ≥ 0 ( ) 1, . i m = Заметим, что любое многогранное множество может быть представлено в предложенной выше так называемой канонической форме (см. п. 2.2). Решение задачи линейного программирования называется допустимым (неотрицательным) базисным решением, если векторы-столбцы коэффициентов при неизвестных в системе ограничений, соответствующие неотрицательным компонентам вектора, линейно независимы. Векторы-столбцы, коэффициенты целевой функции (4.1) и неизвестные x j , отвечающие базису, называются базисными. 90 В случае, когда число положительных компонент допустимого базисного решения равно m, это решение называют невырожденным базисным решением, в противном случае (меньше m) — вырожденным. Пусть система линейных уравнений (4.2) приведена к единичному базису. Для определенности будем считать, что x 1 , x 2 , …, x m — базисные неизвестные, а x m+1 , x m+2 , …, x n — свободные. В таком случае система линейных уравнений (4.2) будет эквивалентна разрешенной системе: 1 1, 1 1 1 1 , 1 1 , m m n n m m m m mn n m x x x x x x + + + + + α + + α = β + α + + α = β (4.4) где β i ≥ 0, 1, . i m ∀ = При этом начальное базисное решение имеет вид: ( ) ( ) 1 1 1 1 1 2 1 2 , , , , 0, , 0 , , , , 0, , 0 . m m X x x x = = β β β Тогда на основании векторного смысла базисного решения (см. п. 1.5, фор- мула (1.8)) можно записать: 1 1 1 1 1 2 2 B, m m A x A x A x + + + = (4.5) где A 1 , A 2 , …, A m — базис системы векторов-столбцов матрицы A; B = (β 1 , β 2 , …, β m ) — вектор-столбец свободных членов. Любой вектор-столбец матрицы А можно разложить по векторам-столбцам базиса A 1 , A 2 , …, A m , то есть 1 , 1, . m j ij i i A A j n = = α = ∑ Иначе 1 2 j j j mj A α α = α — вектор коэффициентов разложения вектора A j по ба- зису A 1 , A 2 , …, A m допустимого решения. Целевую функцию Z(X) запишем так, чтобы она зависела только от сво- бодных неизвестных x m+1 , x m+2 , …, x n : ( ) ( ) 1 1 1 1 1 1 1, 1 1 1 , 1 1 1 1 1 , 1 1 1 1 1 ( ) m m m m n n m m n n m m m m m mn n m m n n m m m j j m i i m m n i in n j i i Z X c x c x c x c x c x x c x x c x c x c c c x c c x + + + + + + + + + + + = = = = + + + + + = = β − α − − α + + β − α − − α + + + + = = β + − α + + − α ∑ ∑ ∑ 91 Обозначим ( ) 1 1, , m j i ij j i c c j m n = ∆ = α − = + ∑ (4.6) ( ) 0 1 1 , m j j j Z X c = ∆ = = β ∑ (4.7) или в векторно-матричной форме: ( ) 0 1, , , j j j C c j m n C ∆ = Α − = + ∆ = Β (4.8) где С = (с 1 , с 2 , …, с m ) — вектор коэффициентов целевой функции при базисных неизвестных; с j — коэффициенты целевой функции при х j Назовем ∆ j оценками разложения вектора A j по базису допустимого ре- шения (или оценками свободных неизвестных х j ). Тогда с учетом (4.5) и (4.6): 1 1 0 ( ) m m n n Z X x x + + + ∆ + + ∆ = ∆ Данное равенство можно рассматривать как еще одно уравнение системы (4.4). В результате получим расширенную систему: ( ) ( ) 1 0 1 1, , n i ij j i j m n j j j m x x i m Z X x = + = + + α = β = + ∆ = ∆ ∑ ∑ (4.9) Результаты проведенных преобразований, записанные в виде системы (4.9), можно занести в таблицу,называемую симплексной (табл. 4.1). Таблица 4.1 Базис C баз B c 1 c 2 … c m c m+1 … c j … c n A 1 A 2 … A m A m+1 … A j … A n A 1 c 1 β 1 1 0 … 0 α 1, m+1 … α 1j … α 1n A 2 c 2 β 2 0 1 … 0 α 2, m+1 … α 2j … α 2n … … … … … … … … … … … … A m c m β m 0 0 … 1 α m, m+1 … α mj … α mn Z(X) ∆ j ≥ 0 ∆ 0 0 0 … 0 ∆ m+1 … ∆ j … ∆ n Последняя строка этой таблицы, называемая оценочной или индексной, рассчитывается по формулам (4.6)–(4.7). При переходе от одного базисного 92 решения к другому оценочную строку можно рассчитывать также по «правилу прямоугольника», которое используется в методе Гаусса — Жордана. Наша задача — от решения X 1 перейти к новому неотрицательному базисно- му решению X 2 с большим значением целевой функции для задачи на максимум и с меньшим для задачи на минимум. Предположим, что в векторном равенстве 1 1, 1 1 2, 1 2 , 1 m m m m m m A A A A + + + + = α + α + + α (4.10) α 1, m+1 > 0. Вычтем из (4.5) равенство (4.10), умноженное на θ: ( ) ( ) 1 1 1 1, 1 1 , 1 1 m m m m m m x A x A A + + + − θα + + − θα = Β − θ или ( ) ( ) 1 1 1 1, 1 1 , 1 1 m m m m m m x A x A A + + + − θα + + − θα + θ = Β (4.11) Обозначим ( ) 1 1 1 1, 1 , 1 , ... , , , 0, ..., 0 . m m m m X x x θ + + = − θα − θα θ Равенство (4.11) показывает, что решение X θ будет допустимым в задаче (4.1)–(4.3), если все его компоненты будут неотрицательны, т. е. 1 , 1 0, j i m x + − θα ≥ 1, i m ∀ = и θ ≥ 0. Если θ = 0, то X 1 = X θ и мы не получим нового решения, поэтому такой случай рассматривать не будем. Пусть θ > 0. Если α i, m+1 ≤ 0, то β i − θα i, m+1 ≥ 0. Если α i, m+1 > 0, то β i ≥ θα i, m+1 , следовательно, , 1 i i m+ θ β α ≤ Чтобы данное неравенство было верно для каждого i = 1, 2, …, m, необходимо потребовать, чтобы , 1 0, 1 : 0 , 1 0 min i m i m i i m + + α > + β < θ ≤ θ = α То есть, если 0 < θ ≤ θ 0, m+1 , то X θ — допустимое базисное решение (4.1)–(4.3). Предположим, что θ 0, m+1 достигается на α i, m+1 , т. е. 1 1 1 0, 1 1, 1 1, 1 m m m x + + + β θ = = α α В X θ положим θ = θ 0, m+1 и обозначим ( ) 2 2 2 2 2 1 0, , ..., , , 0, ..., 0 , m m X X x x x θ + = = где 2 1 0, 1 , 1 2 1 0, 1 2, , i i m i m m m x x i m x + + + + = − θ α = = θ Так как A 2 , …, A m+1 линейно независимы (доказываем от противного), то X 2 — допустимое базисное решение. 93 Понятно, что X 2 получается из X 1 с помощью симплексных преобразований с выбором разрешающего элемента α 1, m+1 . Найдем теперь приращение целевой функции при переходе от X 1 к X 2 : ( ) ( ) ( ) ( ) ( ) 1 1 2 2 0, 1 2, 1 2 0, 1 , 1 0, 1 1 1 1 1 1 0, 1 1, 1 1 2 0, 1 2, 1 2 0, 1 , 1 0, 1 1 0 1 0, 1 1 0, 1 1, 1 1 2, 1 2 , 1 1 0, m m m m m m m m m m m m m m m m m m m m m m m m m m m m CX x c x c c x c x c x c c CX c c c c CX + + + + + + + + + + + + + + = + + + + + + = − θ α + + − θ α + θ = = − θ α + − θ α + − θ α + θ = = + θ − θ α + α + + α = = + θ 1 1 , 1 1 0, 1 1 1 m m m i m i m m i c c CX + + + + + = − α = − θ ∆ ∑ Итак, в векторно-матричной форме 2 1 0, 1 1 m m CX CX + + = − θ ∆ Если θ 0j достигается на α ij , то при переходе от одного решения X 1 к другому X 2 приращение целевой функции находится по формуле 2 1 0 j j j Z CX CX ∆ = − = −θ ∆ (4.12) Здесь j — номер вектора, вводимого в базис допустимого решения, оценки ∆ j определяются формулами (4.6)–(4.8), параметр θ 0j , обеспечивающий неотри- цательность базисного решения, необходимо выбирать из условия 0 : 0 min ij i k j i ij kj ∀α > β β θ = = α α Далее J — множество индексов (номеров) базисных неизвестных. |