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

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

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

2.Таблица 2cjMx5БРairc iBБПБРx11x2M0x5x44141322100110M2M 1  2MM0M0M011 M00x3x4zjj41. Проанализируем относительные оценки. Оценка  2  1  2M  0 , так какx 4  14 , x5  4 ,и, следовательно, текущее базисное решениеM 0x1  x 2  x3  0 не оптимально. Рассмотрим коэффициенты столбца при переменнойx 2 . Поскольку оба коэффициента положительны, то r  2 и переменная x 2 должнабыть введена в число базисных.51.

Определим переменную, выводимую из базиса. Для этого вычислим отношеБР4 14ния. Имеем ,(табл. 3). Выберем из них наименьшее значение. Следователь2 2airно, s  1 и из числа базисных должна быть удалена переменная x5 и заменена переменной x 2 .Таблица 3cj1001Mx1x2x3x4x5БРc iBБПБРairM0x5x44141322100110M2MM01 M1  2MM0M027zjj61. Вычислим новое базисное решение, занося результаты пересчета табл.

3 в табл. 4.Таблица 42031x21c iBБПБР1x220x410x1112400x3x412100cjMx5БРair1211zjjВ табл. 4 в столбец БП введена переменная x 2 вместо x 5 . Первой пересчитывается строка, соответствующая введенной переменной x 2 . Она получается в результатеделения каждого элемента разрешающей строки табл. 3, помеченной , на разрешающий элемент, равный 2. Остальные элементы пересчитываются по &правилу прямоугольника[. Для второй строки имеем:14 42 10 ,232  (1) 4,2222 0,202  (1) 1,2120 1,201 2 1 .2Перейдем к шагу 3.32.

Вычислим оценки  j , j  1,  , 5 . Строка  j пересчитывается по табл. 3также согласно &правилу прямоугольника[:1  1  M (1  2M )  (1) 1 ,224  0 2  0 ,(1  2M )  0 0;21c iBБПБР1x220x410x15  0 1x21241212 3  M 1010204(1  2M )  (1)1 ,22(1  2M )  11 M  .2200x3x412101212100Mx5Таблица 5cjБРair12112M zj12j42.

Проанализируем относительные оценки и, как следствие, текущее базисное1решение x 2  2 , x 4  10 , x1  x3  x5  0 . Оценка  1   0 , поэтому рассмотрим2коэффициенты столбца при переменной x1 . Так как этот столбец содержит один положительный коэффициент, то r  1 и переменная x1 должна быть введена в числобазисных переменных.52. Определим переменную, выводимую из базиса. Для этого вычислим наиБР10меньшее из неотрицательных отношений.

Оно равно(табл. 6). Следовательно,4airs  2 и поэтому из базиса должна быть удалена переменная x 4 и заменена переменной x1 .1c iBБПБР1x220x410x11x21241212100x3x4121001012121Mx5Таблица 6cjБРair121-104zj1200M 12j62. Вычислим новое базисное решение. Результат пересчета табл.

6 приведентабл. 7.c iBБПБРx11x21x2011x126810410100x3x4Mx5381418143814Таблица 7cjБРairzjjПерейдем к шагу 3.205в33. Вычислим оценки  j ,x1 j  1,  , 5 , и определим, является ли решение1026, x2 , x3  x 4  x5  0 оптимальным (табл. 8).84c iBБПБРx11x21x2268011x1104101100100x3x4Mx5381458581838141818Таблица 8cjБРair1458M zj58j1026, x2 ,481026x3  x 4  x5  0 является оптимальным. Решение исходной задачи x1 , x 2 48получается путем отбрасывания дополнительных переменных x 3 , x 4 и искусственнойВсе оценки  j неположительны, следовательно, решение x1 переменной x 5 .

Графически оно соответствует точке x  (рис. 1). ■Пример 2. Найти условный максимум в задачеf ( x)  2 x1  4 x 2  max, x1  2 x 2  4,3x1  2 x 2  14,x1, x 2  0. Приведем поставленную основную задачу к канонической. Так как оба неравенства имеют знак &  [, то введем дополнительные переменные x 3 и x 4 со знаком&+[ (они становятся базисными). В итоге получим каноническую задачу:f ( x)  2 x1  4 x 2  max,1x1  2 x 2  1x 3  0 x 4  4,3 x1  2 x 2  0 x 3  1x 4  14,x1, x 2 , x 3 , x 4  0.Решим ее симплекс-методом.2061. Найдем начальное базисное решение: x1  x 2  0 (так как x1 , x 2 # свободныепеременные), x3  4 , x 4  14 .2.

Заполним табл. 1 согласно алгоритму.c iBБПБР2x100x3x441413400x2x3x4221001Таблица 1cjБРa irzjj31. Вычислим оценки  j , j  1,  , 4 , и определим, является ли базисное реше-ние x3  4, x 4  14 , x1  x 2  0 оптимальным (табл. 2).Таблица 2cjc iBБПБР2x100x3x4414132210010000zj2400j400x2x3x4БРa ir41. Проанализируем относительные оценки. Оценка  2  0 , поэтому исследуе-мое решение не является оптимальным. Рассмотрим столбец x 2 . Его коэффициентыположительны.

Значит, r  2 и в базис должна быть введена переменная x 2 .51. Определим переменную, которая должна быть выведена из базиса, вычисливБРнаименьшее из неотрицательных отношений. Оно равно 2 (табл. 3). Следоваa irтельно, из базиса должна быть выведена переменная x3 и заменена переменной x 2 .207Таблица 3cjc iBБПБР2x100x3x44141322100100002 7zj2400j61.400x2x3x4БРa irВычислим новое базисное решение. Результаты пересчета табл.

3 приведеныв табл. 4.c iBБПБР4x220x4102x1124400x2x3x4112100Таблица 4cjБРa ir1zjjПерейдем к шагу 3.32. Вычислим оценки  j ,j  1,  , 4 , и определим, является ли решениеx 2  2, x 4  10, x1  x3  0 оптимальным (табл. 5).c iBБПБР4x220x4102x1Таблица 5cj400x2x3x412410204121210zj020j0208БРa ir4 2. Все оценки  j , j  1,  , 4 , не положительны, значит, исследуемое решениеx 2   2, x 4   10, x1  x 3  0 оптимально. Значение целевой функции в точке максимума f max  8 .

Найденному решению соответствует вершина А на рис. 2. Однако, какследует из геометрической интерпретации исходной задачи, она имеет бесконечноемножество решений, лежащих на ребре АВ. В этом легко убедиться с помощью симплекс-метода, если ввести в базис переменную x1 вместо переменной x 4 , которой соответствует оценка  4  0 . Соответствующие расчеты приведены в табл. 6.

Заметим,что равенство нулю оценки 1 для небазисной переменной x1 также свидетельствуето наличии бесконечного множества решений.3x1  2 x 2  14x2f x1  2 x 2  44B32A12f (x )  0c iBБПБР4x22x126810421345x1Рис. 2Таблица 6cj2x1400x2x3x401101814204381420zj020jБРa irВсе оценки  j , j  1,  , 4 не положительны, значит, исследуемое базисное ре26  10; x1 ; x3  x4  0 оптимально. Значение целевой функции в точке84максимума f max  8 . Полученному решению соответствует вершина В на рис. 2.Равенство нулю оценки  4 для небазисной переменной x 4 в табл.

6 свидетельствует оналичии бесконечного множества решений. ■шение x 2 209.

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

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