4. Задачи линейного программирования. Решение канонической задачи. Решение основной задачи (1013385), страница 2

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

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

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(1)  (1) 1(1)  1 12  (1)(1)  20  (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 . Определим переменную, которая должна быть выведена из базиса. Для этогоБРвычислим наименьшее из неотрицательных отношений. Оно единственно и равно 4a 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ника»: 2  6,1  0, 1 2, 1 1, 0  1.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А.2. Решение основной задачиПостановка задачиНайти максимум функцииnf ( x)   c j x jj 1при ограниченияхn aij x j  bi ,i  1,  , m ;j 1n aij x j  bi ,i  m  1,  , p ;j 1xj  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 ,j 1n aij x j  x n i  bi ,i  1,  , m ;i  m  1,  , p ;j 1x1  0,  , x n  p  0 .Так как в общем случае в уравнениях нет базисных переменных, то для того,чтобы можно было применить симплекс-метод, делается переход к М-задаче.

В каждое из m первых уравнений вводится искусственная переменная со знаком &  [ (онастановится базисной), а к целевой функции добавляется сумма искусственных переменных, умноженная на &  M [. В результате получаем задачу в расширенной форме:200nf ( x)   c j x j  Mj 1m x n  p i  max ,i 1n aij x j  x n i  x n  p i  bi ,j 1n aij x j  x n i  bi ,i  1,  , m ;i  m  1,  , p ;j 1x1  0,  , x n  p  m  0 .З а м е ч а н и я. Если решается задача поиска минимума целевой функции,то при переходе к M -задаче перед числом M ставится знак &  [.Пример 1. Найти условный максимум в задачеf ( x)  x1  x 2  max ,1x1  2 x 2  4 ,3x1  2 x 2  14 ,x1 , x 2  0 . Приведем поставленную основную задачу к канонической.

Так как первое неравенство имеет знак &  [ , введем дополнительную переменную x 3 со знаком &#[.Поскольку во втором неравенстве знак &  [, то введем дополнительную переменнуюx 4 со знаком &+[ (она становится базисной). В итоге получим каноническую задачу:f ( x)  x1  x 2  max , x1  2 x 2  x 3  4 ,3x1  2 x 2  x4  14 ,x1,..., x 4  0 .Поскольку в первом уравнении нет базисных переменных, то перейдем к M -задаче.Для этого введем искусственную переменную x 5 и добавим ее к целевой функции скоэффициентом &  M [. В результате получим задачу в расширенной форме:f ( x)  x1  x 2  M x 5  max , 1x1  2 x 2  1x3  0 x 4  1x5  4 ,3 x1  2 x2  0 x3  1x4  0 x5  14 ,x1, , x5  0 .201Применим алгоритм симплекс-метода.1.

Найдем начальное базисное решение. Базисными переменными являютсяx 5 , x 4 , а свободными x1 , x 2 , x 3 . Приравняем свободные переменные к нулю. Тогдаx1  x 2  x3  0 и x 4  14 , x5  4 . Начальное базисное решение (0; 0; 0; 14; 4)T . Начальному базисному решению соответствует начало координат на рис. 1.2. Заполним табл. 1 согласно алгоритму.c iBБПБРx11x2M0x5x44141322100x3x41001Таблица 1cjMx5БРair10zjjx27 x1  2 x 2  4x21 2f (x )  0  14fx13x1  2 x 2  14Рис. 131 . Вычислим относительные оценки  j , j  1,  , 5 :1  1  [(M )  (1)  0  3]  1  M ; 2  1  [(M )  2  0  2]  1  2M ; 3  0  [(M )  (1)  0  0]  M ; 4  0  [(M )  0  0  1]  0 ; 5  M  [(M )  1  0  0]  0 .202Результаты приведены в табл.

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

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