УМК (1013374), страница 32
Текст из файла (страница 32)
Следует соединить элемент a ij в предыдущей таблице с разрешающим элементом a sr . Получена одна из диагоналейпрямоугольника. Вторую диагональ образует соединение элементов a ir и a sj .192Далее из текущего значения a ij вычитается произведение элементов a ir и a sj ,деленное на разрешающий элемент a sr (рис.1).ai j = aij −a sra sja ira ija sj ⋅ ai ra srРис. 1Перейти к шагу 3.З а м е ч а н и я.1. Если в задаче в каждом уравнении имеется базисная переменная, то на шаге 1нет необходимости делать линейные преобразования или вводить искусственные переменные.2. Если решается задача поиска минимума, то стратегия симплекс-метода аналогична, только в базис вводится переменная, которой соответствует наименьшая отрицательная оценка Δ r .
Процесс перехода заканчивается, когда найдено такое базисное решение, что все относительные оценки Δ j , j = 1, … , m + n , становятся неотрицательны-ми: Δ j ≥ 0 , j = 1, … , m + n .Пример 1. Найти максимум и минимум в задачеf ( x ) = − x1 + 2 x 2 − x 3 − x 4 → extr,− x1 + x 2 + x 3 = 2,x1 + x 2 + x 4 = 4,x j ≥ 0,j = 1, … ,4. Решается каноническая задача. Переменные x 3 и x 4 являются базисными, таккак они входят только в одно уравнение, причем с коэффициентом +1.Сначала решим задачу графически:а) выразим базисные переменные через небазисные (свободные) и используем условие x j ≥ 0, j = 1,... ,4 :x 3 = 2 + x1 − x 2 ≥ 0, x 4 = 4 − x1 − x 2 ≥ 0,x1 ≥ 0, x 2 ≥ 0;б) выразим целевую функцию через небазисные (свободные) переменные:f ( x ) = − x1 + 2 x 2 − 2 − x1 + x 2 − 4 + x1 + x 2 = − 6 − x1 + 4 x 2 ;в) решим полученную задачу линейного программированияf ( x ) = − 6 − x1 + 4 x 2 → extr ,2 + x1 − x 2 ≥ 0,4 − x1 − x 2 ≥ 0,x1 ≥ 0,x 2 ≥ 0.193Для этого построим соответствующее множество допустимых решений X .
Затем найдемградиент: ∇f (x ) = (−1; 4)T , проведем линию уровня функции перпендикулярно градиенту и будем передвигать ее параллельно самой себе до касания с множеством допустимыхрешений.x22 + x1 − x 2 = 04f (x ) = 5C3f (x ) = 2∇f2Bf (x ) = − 6X-2-1DA1324x14 − x1 − x 2 = 0Рис. 1Так как градиент направлен в сторону наискорейшего возрастания функции в данной точке, то в точке C = (1, 3) T достигается максимум (рис. 1).Значения остальныхпеременных находятся из условий связи: x 3 = 2 + 1 − 3 = 0; x 4 = 4 − 1 − 3 = 0. В ре∗зультате получаем ответ в исходной задаче x max= (1, 3, 0, 0) T .Заметим, что минимум достигается в точке D = (4, 0) T .
При этомx 3 = 2 + 4 − 0 = 6; x 4 = 4 − 4 − 0 = 0. В результате получаем точку минимума в исход∗= (4, 0, 6, 0) T .ной задаче x minРешим поставленную каноническую задачу симплекс-методом.1. Найдем начальное базисное решение:а) нет необходимости вводить искусственные переменные, так как в каждом уравнении уже есть базисная переменная;б) подчеркнем базисные переменные x 3 и x 4 в уравнениях, описывающих ограничения;в) свободными переменными являются x1 и x 2 ;г) начальное базисное решение находится при приравнивании нулю свободных переменных: x1 = x 2 = 0 .
Тогда x 3 = 2 , x 4 = 4 . Начальное базисное решениеx = (0; 0; 2; 4)T . Ему соответствует точка А на рис. 1.2. Заполним табл. 1 согласно алгоритму с учетом результатов п.1.194c iBБПБР−1x1–1–1x3x424−11x2−1x3−1x41110012Таблица 1cjБРa irzjΔj31. Вычислим относительные оценки Δ j , j = 1, … , 4 :Δ1 = −1 − [(−1) ⋅ (−1) + (−1) ⋅ 1] = −1 ,z1 = (−1) ⋅ (−1) + (−1) ⋅ 1 = 0 ;Δ 2 = 2 − [(−1) ⋅ 1 + (−1) ⋅ 1] = 4 ,z 2 = (−1) ⋅ 1 + (−1) ⋅ 1 = −2 ;Δ 3 = −1 − [(−1) ⋅ 1 + (−1) ⋅ 0] = 0 ,z 3 = (−1) ⋅ 1 + (−1) ⋅ 0 = −1 ;Δ 4 = −1 − [(−1) ⋅ 0 + (−1) ⋅ 1] = 0 ,z 4 = (−1) ⋅ 0 + (−1) ⋅ 1 = −1и занесем их в табл.
2.c iBБПБР−1x1−1−1x3x424−111110010−24−10−10−1x2−1x3−1x42Таблица 2cjБРa irzjΔj⊗41. Проанализируем относительные оценки. Оценка Δ 2 = 4 > 0 наибольшая положительная. Проведем анализ столбца x 2 . Все коэффициенты положительны, r = 2 . Введем в базис переменную x 2 .51 . Определим переменную, выводимую из базиса. Для этого вычислим наименьБР, оно равно 2 (табл. 3).
Поэтому s = 1 и выведемшее из неотрицательных отношенийa irпеременную x 3 , расположенную в первой строке.195−12−1−1Таблица 3cjc iBБПБРx1x2x3x4БРa ir−1x32−1110−1x4411012 =214 =410−24−10−10−1⊗zjΔj⊗16 . Вычислим новое базисное решение. Результаты пересчета табл. 3 приведены втабл. 4.Таблица 4cj2−1−1−1c iBБПБРx1x2x3x42−1x2x422−12101−101БРa irzjΔjВ табл. 4 в столбец БП введена переменная x 2 вместо x 3 (табл.
3). Первой пересчитывается строка, соответствующая введенной переменной x 2 . Она получается в результате деления каждого элемента разрешающей строки табл. 3, помеченной ⊗, на разрешающий элемент, равный 1. Остальные элементы пересчитаем по «правилу прямоугольника». Для второй строки табл. 3 имеем:4−1⋅2= 2,11−1 ⋅ (−1)= 2,11−1 ⋅1= 0,10−1 ⋅1= −1 ,11−1⋅0= 1.1Перейдем к шагу 3.32. Вычислим относительные оценки Δ j , j = 1, … , 4 . Строку Δ j пересчитаем, воспользовавшись табл. 3, также по «правилу прямоугольника» (табл. 5):Δ1 = −1 −4 ⋅ (−1)4 ⋅14 ⋅10⋅4= 3 , Δ2 = 4 −= 0 , Δ3 = 0 −= − 4 , Δ4 = 0 −= 0.111142. Проанализируем относительные оценки и, как следствие, текущее базисное решение x 2 = 2 , x 4 = 2 , x1 = x 3 = 0 .
Ему соответствует точка В на рис. 1.Оценка Δ 1 = 3 > 0 – наибольшая положительная. Следовательно, исследуемоерешение не является оптимальным. Проанализируем столбец x1 . Среди его коэффициентов есть положительный, r = 1 . Введем в базис переменную x1 .196−12−1−1c iBБПБРx1x2x3x42−1x2x422−12−410201301−13−4Таблица 5cjБРa ir−10zjΔj⊗5 .
Определим переменную, которая должна быть выведена из базиса. Для этогоБР. Оно единственно и равновычислим наименьшее из неотрицательных отношенийa ir2единице (табл. 6). Следовательно, s = 2 и переменная x1 заменяется переменной x 4 ,расположенной во второй строке.Таблица 6cj2−1−1−1x1x2x3x4БРc iBБПБРa ir2−1x2x422−12101−101−42330−4−10-22=1 ⊗zjΔj⊗62. Вычислим новое базисное решение. Результаты пересчета табл. 6 приведены втабл. 7.Таблица 7cj2−1−1−1x1x2x3x4БРc iBБПБРa ir2x2301−1x111012− 121212zjΔjВ табл. 7 в столбец БП на место x 4 введена переменная x1 .
Первой пересчитывается строка, соответствующая введенной переменной x1 . Она получается в результатеделения каждого элемента разрешающей строки табл. 6, помеченной ⊗, на разрешающийэлемент, равный 2. Остальные элементы пересчитываются по «правилу прямоугольника».Для первой строки имеем:1972−2 ⋅ (−1)(−1) ⋅ 20 ⋅ (−1)(−1) ⋅ (−1) 1(−1) ⋅ 1 1= 3, −1−= 0, 1 −= 1, 1 −= , 0−= .2222222Перейдем к шагу 3.33. Вычислим относительные оценки Δ j , j = 1, … , 4 . Строка Δ j пересчитываетсяпо табл. 6 с применением «правила прямоугольника» (табл.
8):3⋅23⋅03 ⋅ (−1)53 ⋅13Δ1 = 3 −= 0 , Δ2 = 0 −= 0 , Δ3 = − 4 −= − , Δ4 = 0 −=− .222222c iBБПБР−1x12x2301−1x1110−12002x2−1x3−1x412− 1232− 52121212− 32Таблица 8cjБРa irzjΔj4 3. Проанализируем относительные оценки и, как следствие, текущее базисноерешение x 2 = 3 , x1 = 1, x 3 = x 4 = 0 . Так как все Δ j ≤ 0 , на текущем базисном решениидостигается максимум.
Так как число нулевых оценок равно числу базисных переменных, то решение единственное. Этому решению соответствует точка С на рис. 1. Такимобразом, в процессе применения процедуры симплекс-метода произошел направленныйперебор вершин множества допустимых решений. Переход из вершины А в вершину В , азатем в С связан с последовательным увеличением значения целевой функции.Найдем минимум в поставленной задаче. Используем табл. 2, т.е. будем считать,что шаги 1–3 алгоритма реализованы (табл.
9).Таблица 9cj2−1−1−1c iBБПБРx1x2x3x4БРa ir−1−1x3x424−11111001--0−24−10−10−141=4 ⊗zjΔj⊗4 . Проанализируем относительные оценки. Поскольку ищется минимум, условием окончания процесса является неотрицательность всех относительных оценок, а привыборе разрешающего столбца следует найти наименьшую отрицательную оценку. Оценка Δ1 = −1 – наименьшая отрицательная. Проанализируем столбец x1 . Среди коэффициентов есть положительный, поэтому r = 1 . Введем в базис переменную x1 .119851 . Определим переменную, которая должна быть выведена из базиса.
Для этогоБР. Оно единственно и равно 4вычислим наименьшее из неотрицательных отношенийa ir(табл. 9). Следовательно, s = 2 и в базисе переменная x 4 заменяется переменной x1 ,расположенной во второй строке.61 . Вычислим новое базисное решение. Результаты пересчета табл. 9 приведены втабл. 10.Таблица 10cj2−1−1−1x1x2x3x4БРc iBБПБРa ir−1−1x3x16401211011zjΔjВ табл. 10 в столбец БП на место x 4 введена переменная x1 . Первой пересчитывается строка, соответствующая введенной переменной x1 . Она получается в результатеделения каждого элемента разрешающей строки табл. 9, помеченной ⊗, на разрешающийэлемент, равный 1. Элементы первой строки пересчитываются по «правилу прямоуголь4 ⋅ (−1)1 ⋅ (−1)1 ⋅ (−1)0 ⋅ (−1)(−1) ⋅ 1= 6,−1 −= 0, 1−= 2, 1−= 1, 0 −= 1.ника»: 2 −11111Перейдем к шагу 3.32.
Вычислим относительные оценки Δ j , j = 1, … , 4 . Строка Δ j пересчитываетсяпо табл. 10 согласно «правилу прямоугольника» (табл. 11):Δ 1 = −1 −(−1) ⋅ 1(−1) ⋅ 1(−1) ⋅ 0(−1) ⋅ 1= 0 , Δ2 = 4 −= 5 , Δ3 = 0 −= 0 , Δ4 = 0 −= 1.1111c iBБПБР−1x1−1−1x3x16401Таблица 11cjx2−1x3−1x4–121–310–111–2zj0501Δj2БРa ir4 2. Проанализируем относительные оценки и, как следствие, текущее базисное решение x 3 = 6 , x1 = 4, x 2 = x 4 = 0 . Так как все оценки Δ j ≥ 0 , на текущем базисном реше-нии достигается минимум. Поскольку число нулевых оценок равно числу базисных переменных, то решение единственное.
Этому решению соответствует точка D на рис.1. 199Занятие 7. ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.РЕШЕНИЕ ОСНОВНОЙ ЗАДАЧИА.2. Решение основной задачиПостановка задачиНайти максимум функцииnf ( x) = ∑ c j x jj =1при ограниченияхn∑ aij x j ≥ bi ,j =1n∑ aij x j ≤ bi ,i = 1, … , m ;i = m + 1, … , p ;j =1x j ≥ 0 , j = 1, … , n .Задача линейного программирования называется основной. Предполагается, чтоbi ≥ 0 , i = 1, … , p .Стратегия поискаДля решения основной задачи симплекс-методом она должна быть приведена кканонической задаче путем введения в каждое ограничение по одной дополнительнойпеременной: в каждое ограничение-неравенство со знаком « ≤ » вводится дополнительнаяпеременная со знаком « + » (она становится базисной), а в каждое ограничениенеравенство со знаком « ≥ » вводится дополнительная переменная со знаком «–».Каноническая задача записывается следующим образом:nf ( x) = ∑ c j x j → max ,j =1n∑ aij x j − x n +i = bi ,i = 1, … , m ;j =1n∑ aij x j + x n +i = bi ,i = m + 1, … , p ;j =1x1 ≥ 0, … , x n + p ≥ 0 .Так как в общем случае в уравнениях нет базисных переменных, то для того,чтобы можно было применить симплекс-метод, делается переход к М-задаче.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
