semopt6 (1013532), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Проанализируем относительные оценки и, как следствие, текущее базисное решение 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.

Характеристики

Список файлов лекций