В П Лавренчук, П Настасієв, О В Мартинюк - Вища математиказагальний курсчастина iлінійна алгебра й аналітична геометрія - страница 94

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95  96  97  98  99  100  101  102  103  104  105 

А*       .    Ґ А,­— піт -*

--_ ^ —

і назвемо його провідним.

5. Переходимо до наступної симплексної таблиці, виконав­ши жорданове перетворення попередньої таблиці з провідним (розв'язувальним) елементом І агз І, і повертаємося до кроку 1.

Оптимальний план прямої задачі визначається базисними змінними та їхніми значеннями в стовпчику Ао останньої сим­плексної таблиці, а двоїстої задачі - змінними двоїстої задачі,

278які відповідають базисним стовпчикам вихідної задачі, та їхні­ми значеннями, що знаходяться в оціночному (т + 1)-у рядку з урахуванням .

Двоїстий симплексний метод зручно використовувати та­кож для розв'язування задач, які мають одиничний базис, але не належать до задач у базисній формі, оскільки мають від'ємні компоненти серед елементів вектора-стовпчика Ао і (т + 1)-го рядка одночасно. Розв'язуються такі задачі в два етапи. Спочатку за допомогою двоїстого симплексного методу виключаються всі Ьі < 0, а потім оптимальний план знаходить­ся звичайним симплексним методом. Треба лише на першому етапі замінити крок 4 на такий:

4'. Серед від'ємних коефіцієнтів агз провідного рядка виби­раємо елемент агз, для якого

Ьг Г Ьг 1

— = ша^ — >.

Приклад 7. За допомогою двоїстого симплексного методу розв'язати задачу

/ = 3жі + 2ж2 4ж3 шіп;

Г жі + Ж2 2жз > 4, [ 3жі + Ж2 4жз > 7;

ж3 > 0, з Є {1, 2, 3},

і знайти розв'язок двоїстої до неї.

< Двоїста задача до заданої має вигляд

Я = 4уі + 7у2 шах;

Уі + 3у2 < 3, Уі + У2 < 2,

—2Уі 2 <4;

Уі > 0, У2 > 0. Зведемо пряму задачу до канонічної форми

/ = 3жі + 2ж2 4ж3 шіп;

279

—жі

3ж

ж0- > 0, З Є{1, 5}.

ж2 + 2жз + ж4 = —4, 3жі — ж2 + 4жз + жб = —7;

Розв'язування цієї задачі проведемо за допомогою симплексних таблиць

і

Б

сб

Ао

3

2

—4

0

0

 

 

 

 

Аі

А2

Аз

А4

Аб

1

2

Аб

0 0

—4 —7

—1 —3

—1 —1

2

4

1

0

0 1

т + 1

 

 

0

—3

—2

4

0

0

1 2

 

0 2

3 7

2 3

0 1

—2 —4

1

0

—1 —1

т + 1

 

 

14

3

0

—4

0

—2

1 2

Аі

3 2

3/2 5/2

1

0

0 1

1

1

1/2 —3/2

1/2 1/2

т + 1

 

 

19/2

0

0

1

—3/2

1/2

У першій симплексній таблиці умова оптимальності не вико­нується і в стовпчику Ао є від'ємні елементи. За провідний рядок візьмемо другий, бо йому відповідає найбільше за абсолютною вели­чиною Ьі < 0, і Є {1, 2}. Провідний елемент виберемо, скориставшись відношенням

шах {—7 ——[}=ШаХ{1;7}

7.

Цим елементом є 1

симплексного методу. За провідний ет ний елемент 2 , бо 90і = тіп < 2; 3 \

У другій симплексній таблиці умова оптимальності не виконуєть­ся, а умова допустимості виконується, бо в стовпчику Ао всі Ьі > 0, і Є {1, 2} . Тому цю задачу розв'язуємо за допомогою звичайного симплексного методу. За провідний стовпчик беремо Аі, за провід-

7і = 3 3] = 2.

У третій симплексній таблиці умова оптимальності виконується,

V*     (3 5 Л   , 19

а це означає, що задача розв'язана. Отже, X   = І 2; 2   / , ^тіп = ~2~.

Розв'язок двоїстої задачі міститься в + 1)-у рядку остан­ньої симплексної таблиці в стовпчиках А4 і Аб, що відповідають початковому опорному плану. Оскільки при зведенні прямої зада­чі до канонічної базисної форми ми змінили знаки на протилежні

280в обмеженнях-нерівностях, то значення для уі і у* треба взяти з

3 1 19 протилежними знаками. Тому У * = ( 2; 2 Г ^та* = /тіп = у.

Приклад 8. Розв'язати задачу

/ = 5ж2 + 7ж4 шіп;

10ж2 + жз + ж4 = —16, жі 3ж2 3ж4 = —12,

6ж2 2ж4 + жб = —17;

ж0- > 0, З Є {1,..., 5},

і двоїсту до неї.

< Двоїстою до заданої є задача

Я = 16уі 12у2 17уз шах;

У2 < 0,

10уі 3у2 6уз < 5,

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95  96  97  98  99  100  101  102  103  104  105 


Похожие статьи

В П Лавренчук, П Настасієв, О В Мартинюк - Вища математиказагальний курсчастина iлінійна алгебра й аналітична геометрія