Езу9у. Учебное пособие Рекомендовано методическим советом Уральского федерального университета в качестве учебного пособия для студентов вуза, обучающихся по направлениям подготовки
 Скачать 5.85 Mb.
|
|
Теорема 4.1 (правило перехода к новой вершине). Если хотя бы одна оценка ∆ j , j∉J разложения вектора A j по базису допустимого решения отрицательна ∆ j < 0 (положительна ∆ j > 0), а при соответствующей переменной x j есть хотя бы один положительный коэффициент α ij > 0, то CX 2 > CX 1 в задаче на максимум (CX 2 < CX 1 в задаче на минимум). Таким образом, можно найти новое базисное решение, на котором значе- ние целевой функции будет больше в задаче на максимум и меньше в задаче на минимум. Чтобы обеспечить наибольшее изменение целевой функции при переходе от одного базисного решения к другому, векторы, исключаемый (выводимый) 94 из базиса и вводимый в базис допустимого решения, согласно (4.12) необходимо выбирать из условий: в задаче на максимум max{ , } max{ , }; j j j Z j J j J ∆ ∉ = −θ ∆ ∉ (4.13) в задаче на минимум min{ , } min{ , }. j j j Z j J j J ∆ ∉ = −θ ∆ ∉ (4.14) В упрощенном варианте вектор, вводимый в базис допустимого решения, выбирается из условий: в задаче на максимум min{ , }; j j J ∆ ∉ (4.15) в задаче на минимум max{ , }. j j J ∆ ∉ (4.16) Теорема 4.2 (правило неограниченности целевой функции). Если существует вектор A j , для которого оценка ∆ j ≤ 0 и при соответствующей переменной x j нет ни одного положительного коэффициента (все α ij ≤ 0, 1, ), i m = то в задаче на максимум целевая функция не ограничена в области допустимых решений, т. е. max Z(X) = + ∞. Аналогично, если существует A j : ∆ j ≥ 0 и для любого 1, i m = α ij ≤ 0 (в задаче на минимум), то min Z(X) = −∞. Теорема 4.3 (правило оптимальности решения). Допустимое базисное решение задачи линейного программирования является оптимальным, если для любого вектора A j оценка разложения по базису допустимого решения неотрицательная (неположительная), то есть: • все ∆ j ≥ 0 в задаче на максимум; • все ∆ j ≤ 0 в задаче на минимум. Признак единственности оптимального решения. Оптимальное решение задачи линейного программирования является единственным, если для любого вектора A j , не входящего в базис, оценка вектора отлична от нуля, то есть: 0, { 1, 2, , }. j j m m n ∆ ≠ ∀ ∈ + + Здесь в базис входят первые m векторов. Условие существования множества оптимальных решений. Задача линей- ного программирования имеет бесконечное множество оптимальных решений, если при оптимальном решении оценка хотя бы одного вектора, не входящего в базис, равна нулю, т. е. существует { 1, 2, , }: 0. j j m m n ∈ + + ∆ = 95 4.3. Алгоритм решения задачи симплексным методом Для решения задачи симплексным методом применяется следующий а л г о р и т м: 1. Привести задачу линейного программирования к каноническому виду. 2. Найти первое допустимое решение с базисом из единичных векторов и коэффициенты разложений векторов по этому базису. Если это сделать труд- но, то использовать метод искусственных переменных, который изложен в сле- дующем пункте. 3. Если базисное решение найти невозможно, то задача не имеет решения ввиду несовместности системы ограничений. 4. Вычислить оценки разложений векторов по базису допустимого решения и заполнить симплекс-таблицу. 5. Если выполнено правило оптимальности (теорема 4.3), то найденное решение оптимальное. 6. Если найденное решение задачи единственное, то решение задачи за- канчивается. 7. Если выполняется условие существования множества оптимальных ре- шений, то найти все оптимальные решения. 8. Проверить, существует ли ∆ j < 0 (∆ j > 0) и 1, i m ∀ = a ij ≤ 0. Если да, то Z max = + ∞(Z min = −∞). 9. Если не выполняются условия шагов 4–8, то выбрать любой небазисный столбец, где ∆ j < 0, следуя условиям (4.13)–(4.14) или (4.15)–(4.16), и зафикси- ровать его номер l. 10. Определить для выбранного столбца параметр θ 0l , т. е. найти строку, где i il b a минимально по всем i таким, что a il > 0, и зафиксировать ее номер k. Элемент a kl выбрать за разрешающий и вернуться к п. 4. Алгоритм конечен, так как при каждой новой итерации осуществляется переход к новой вершине многоугольника решений, а вершин конечное число. Пример 4.1. Решить симплексным методом следующую задачу линейного программирования: ( ) 1 3 4 1 2 3 4 1 2 3 7 4 max, 2 6, 2 1; 0, 1, 4. j Z X x x x x x x x x x x x j = + − → − + − ≤ + − ≤ − ≥ = 96 Решение. Приведем задачу линейного программирования к каноническо- му виду. Для этого сначала умножим обе части второго неравенства системы ограничений на (−1): 1 2 3 2 1 | ( 1). x x x + − ≤ − × − Получим неравенство с положительной правой частью: 1 2 3 2 1. x x x − − + ≥ Далее вводим дополнительные (Д) переменные x 5 и x 6 : Д 1 2 3 4 5 1 2 3 6 2 6, 2 1; 0, 1, 4. j x x x x x x x x x x j − + − ≤ + − − + ≥ − ≥ = Итак, задача принимает вид: ( ) 1 3 4 7 4 max, Z X x x x = + − → 1 2 3 4 5 1 2 3 6 2 6, 2 1; x x x x x x x x x − + − + = − − + − = (4.17) 0, 1, 6. j x j ≥ = Используя метод Гаусса — Жордана, приведем систему ограничений (4.17) к равносильной разрешенной системе уравнений (табл. 4.2). Для сохранения неотрицательности правых частей уравнений вводим параметр θ j . Получим первое базисное решение X 1 = (0, 0, 1, 0, 6, 0) с базисом (A 5 , A 3 ). Таблица 4.2 Шаг Базис A 1 A 2 A 3 ↓ A 4 A 5 A 6 B θ 3 Базисное решение 1 A 5 1 –1 2 –1 1 0 6 3 –2 –1 1 0 0 –1 1 1 2 A 5 5 1 0 –1 1 2 4 X 1 = (0, 0, 1, 0, 4, 0) A 3 –2 –1 1 0 0 –1 1 Далее вычислим оценки разложений векторов по базису допустимого ре- шения по формулам (4.6)–(4.7): 0 0,1 4 ( ) ( ) ,1 0 4 1 1 1; CB ∆ = = ⋅ = ⋅ + ⋅ = 1 1 1 (0,1) (5, 2) 7 0 5 1 ( 2) 7 9; CA c ∆ = − = ⋅ − − = ⋅ + ⋅ − − = − 97 2 2 2 (0,1) (1, 1) 0 0 1 1 ( 1) 1; CA c ∆ = − = ⋅ − − = ⋅ + ⋅ − = − 3 3 3 (0,1) (0,1) 1 0 0 1 1 1 0; CA c ∆ = − = ⋅ − = ⋅ + ⋅ − = 4 4 4 (0,1) ( 1,0) 4 0 ( 1) 1 0 4 4; CA c ∆ = − = ⋅ − + = ⋅ − + ⋅ + = 5 5 5 (0,1) (1,0) 0 0 (1) 1 0 0; CA c ∆ = − = ⋅ − = ⋅ + ⋅ = 6 6 6 (0,1) (2, 1) 0 0 2 1 ( 1) 0 1. CA c ∆ = − = ⋅ − − = ⋅ + ⋅ − − = − Теперь можем составить симплексную таблицу (табл. 4.3). Таблица 4.3 Базис C баз B 7 0 1 –4 0 0 θ 1 θ 2 θ 6 A 1 ↓ A 2 A 3 A 4 A 5 A 6 ← A 5 0 4 5 1 0 –1 1 2 4/5 4 2 A 3 1 1 –2 –1 1 0 0 –1 Z(X) ∆ j 1 –9 –1 0 4 0 –1 В первом столбце «Базис» записываются векторы, входящие в базис допу- стимого решения. Порядок записи соответствует номерам разрешенных неиз- вестных в уравнениях-ограничениях. Во втором столбце «C баз » записываются коэффициенты целевой функции при базисных неизвестных в том же порядке. В последней строке с оценками ∆ j в столбце «B» записывается значение целе- вой функции Z(X 1 ) = CB. Заметим, что оценки единичных векторов, входящих в базис, всегда равны нулю. Начальное базисное решение не является оптимальным, так как в рассма- триваемой задаче на максимум векторам A 1 , A 2 , A 6 соответствуют отрицатель- ные оценки ∆ 1 = −9, ∆ 2 = −1, ∆ 6 = −1 (признак оптимальности не выполняется). В данном случае можно найти новое решение, при котором значение целевой функции не уменьшится. Приращение целевой функции находится по форму- ле (4.13). Находим ( ) ( ) ( ) 4 36 max max 9 , 4 1 , 2 1 5 5 j j Z ∆ = − ⋅ − − ⋅ − − ⋅ − = при j = 1. Таким образом, вместо вектора A 5 в базис следует ввести вектор A 1 . За раз- решающий элемент принимаем число 5 (единственный положительный элемент этого столбца) (табл. 4.3). Выполняем преобразования Гаусса — Жордана. Приходим к табл. 4.4 с новым базисным решением 2 4 13 , 0, , 0, 0, 0 , 5 5 X = базисом (A 1 , A 3 ), значением целевой функции 2 ( ) 41 5. Z X = В оценочной стро- 98 ке все оценки ∆ j ≥ 0, 1, 4, j = следовательно, полученное допустимое базисное решение является оптимальным. Таблица 4.4 Базис C баз B 7 0 1 –4 0 0 A 1 A 2 A 3 A 4 A 5 A 6 A 1 7 4/5 1 1/5 0 –1/5 1/5 2/5 A 3 1 13/5 0 –3/5 1 –2/5 2/5 –1/5 Z(X) ∆ j 41/5 0 4/5 0 11/5 4/5 13/5 Так как исходная задача имеет четыре неизвестных, то в ответе две допол- нительные неизвестные не записываем. Итак, 41 max ( ) 5 Z X = при 4 13 , 0, , 0 . 5 5 X ∗ = 4.4. Альтернативный вариант оформления симплекс-метода Запишем задачу линейного программирования (4.1)–(4.3) в компактном виде и рассмотрим для определенности задачу на максимум: 1 1 2 2 ( ) max, n n Z X c x c x c x = + + + → ( ) 1 1 , , ij j i n j a x b i m = = = ∑ (4.18) ( ) 1, 0 j j n x = ≥ Будем считать, что r(A) = m < n, b i ≥ 0 ( 1, ). i m = Введем новую переменную x 0 = c 1 x 1 + c 2 x 2 + … + c n x n . Рассмотрим две системы линейных уравнений: ( ) 1 ( 1, ), (I) 0 1, n ij j i j j a x b i m x j n = = = ≥ = ∑ 99 и ( ) 0 1 1 0, (II) ( 1, ), 0 1, . n j j j n ij j i j j x c x a x b i m x j n = = − = = = ≥ = ∑ ∑ Утверждение. Совокупность действительных чисел 0 1 ( , , , ) n x x x является решением системы (II) в том и только в том случае, если набор 1 ( , , ) n x x — ре- шение системы (I), причем 0 x CX = — значение целевой функции на некотором решении 1 ( , , ) n X x x = системы (I). Это утверждение позволяет свести исходную задачу к задаче нахождения решения 0 1 ( , , , ) n x x x системы (II) с максимальным (минимальным) значением компоненты 0 x 4.5. Симплекс-анализ Пусть система линейных уравнений (I) приведена к единичному базису. Для определенности будем считать, что x 1 , x 2 , …, x m — базисные переменные, а x m+1 , x m+2 , …, x n — свободные. Тогда система уравнений (II) будет эквивалентна системе: 0 1 1 1 1 1 1, 1 1 1 1 , 1 1 0, , ; m m m m n n m m n n m m m m mn n m x c x c x c x c x x x x x x x + + + + + + − − − − − − = + α + + α = β + α + + α = β (4.19) 0, 1, , j x j n ≥ = где 0, 1, . i i m β ≥ ∀ = Составим симплекс-таблицу (табл. 4.5), соответствующую системе урав- нений (4.19). В первом столбце указываются базисные переменные (БП) системы (4.19). В следующих столбцах записывают коэффициенты при неизвестных x j , 0, . j n = Понятно, что коэффициенты при x 0 (кроме коэффициента целевой функции) не изменяются при преобразованиях матрицы системы. Коэффициенты первого 100 уравнения системы (4.19) записываются отдельной строкой. На самом деле это коэффициенты целевой функции (кроме коэффициента при x 0 ), записанные с противоположными знаками. В дальнейшем будем называть эту строку стро- кой целевой функции или Z-строкой. Коэффициенты каждого из остальных уравнений (ограничений) записываются в отдельную строку. Значения правых частей этих уравнений записаны в столбце «B». Таблица 4.5 БП x 0 x 1 x 2 … x m x m+1 … x n B Z = x 0 → max 1 –c 1 –c 2 … –c m –c m+1 … –c n 0 x 1 0 1 0 … 0 α 1, m+1 … α 1n β 1 x 2 0 0 1 … 0 α 2, m+1 … α 2n β 2 … … … … … … … … … … x m 0 0 0 … 1 α m, m+1 … α mn β m Умножим строки ниже Z-строкина c 1 , …, c m соответственно и прибавим к Z-строке, получим табл. 4.6. Таблица 4.6 БП x 0 x 1 x 2 … x m x m+1 … x n B Z = x 0 → max 1 0 0 … 0 1 m c + … n c β 0 x 1 0 1 0 … 0 α 1, m+1 … α 1n β 1 x 2 0 0 1 … 0 α 2, m+1 … α 2n β 2 … … … … … … … … … … x m 0 0 0 … 1 α m, m+1 … α mn β m В результате система (4.19) преобразуется в разрешенную относительно x 0 , x 1 , …, x m : 0 1 1 0 1 1, 1 1 1, 1 , 1 1 , , ; m m n n m m n n m m m m mn n m x c x c x x x x x x x + + + + + + + + + = β + α + + α = β + α + + α = β (4.20) 0, 1, . j x j n ≥ = Итак, получено первое допустимое базисное решение системы (4.20): 0 X = (β 0 , β 1 , β 2 , …, β m , 0, …, 0). Очевидно, что это базисное решение системы (4.19). Из (4.20) находим: 101 0 0 1 1 1 1 1, 1 1 1 , 1 1 , , ; m m n n m m n n m m m m m mn n x c x c x x x x x x x + + + + + + = β − − − =β −α − − α = β − α − − α 0, 1, . j x j n ≥ = Пусть в задаче на максимум все 0. m j c + ≥ Тогда 0 0 x ≤ β и увеличить значе- ние целевой функции за счет увеличения свободных неизвестных x m+1 , …, x m невозможно. Таким образом, (β 0 , β 1 , β 2 , …, β m , 0, …, 0) — оптимальное решение, причем x 0 = β 0 — оптимальное (максимальное) значение целевой функции. |