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

Страницы:
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 

Аз

0

2

0

-4

1

2

-1

0

3

Аб

0

5

0

3

0

0

1

1

ш + 1

 

 

0

0

-1

0

1

3

0

1

А5

-3

1

1

2

0

-1

1

0

2

Аз

0

3

1

-2

1

ш

0

0

3

Аб

0

4

-1

1

0

1

0

1

ш + 1

 

 

-3

-3

-7

0

4

0

0

1

А5

-3

4

2

0

1

0

1

0

2

А4

-1

3

1

-2

1

1

0

0

3

Аб

0

1

-2

3

-1

0

0

1

ш + 1

 

 

-15

-7

1

-4

0

0

0

1

А5

-3

4

2

0

1

0

1

0

2

А4

-1

11/3

-1/3 -2/3

0

1/3

1

0

2/3

3

А2

1

1/3

 

1

-1/3

0

0

1/3

ш + 1

 

 

-46/3

-19/3

0

-11/3

0

0

-1/3

Отже, оптимальний план прямої задачі X* = (О; 1/3; О; 11/3; 4;

46

О); а /шіп 3 •

Знайдемо тепер оптимальний план двоїстої задачі. Його коорди­нати знаходяться в + 1)-у рядку останньої симплексної таблиці, а саме, і-та координата стоїть навпроти відповідного вектора, який входив до початкового базису, якщо до неї додати відповідне значен­ня коефіцієнта цільової функції:

19        19 11 11

Уі = -У+° = -У  У2 = -Т + ° = -3,' =  1 1 Уз = - 3+ = - 3.

46

При цьому Ршах =--3. ►

274

Зауваження. Якщо оптимальний план прямої задачі ви­роджений, то оптимальний план двоїстої задачі, взагалі кажу­чи, не єдиний. Перехід до нової симплексної таблиці здійсню­ють за правилом: рядок, якому відповідає Ьг = О, беруть за провідний, а провідний стовпчик визначають з умови

\   a, 1

9r = min <--- >.

arj <0 I       arj I

При цьому досить перерахувати лише елементи (m + 1)-го рядка, бо стовпчик Aq не змінюється. Приклад б. Розв'язати задачу

/ = 4xi + 4x2 max;

xi + 2x2 < l,

2xi + x2 < 2;

xi > О, x2 > О,

й двоїсту до пеї.

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

F = yi + 2у2 min;

ґ Уі + 2У2 > 4, 1 2yi + У2 > 4;

yi > О, y2 > О.

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

і

Б

c6

Ao

4

4

о

о

 

 

 

 

Ai

А2

Аз

 

І

Аз

о

І

І

 

2

 

І

о

2

 

о

2

2

 

l

 

о

І

m + 1

 

 

о

-4

-4

о

о

І

Ai

4

І

І

 

2

 

І

о

2

 

о

о

о

 

-3

 

-2

І

m + 1

 

 

4

0

4

4

о

І

Ai

4

І

І

 

о

 

І/З

2/3

2

 

4

о

о

 

l

 

2/3

/з

m + 1

 

 

4

0

о

4/3

4/3

27Б

У другій симплексній таблиці умова оптимальності виконується, а це означає, що пряма задача розв'язана: X* = (1;0), ішах = 4.

Оскільки оптимальний план вироджений, то двоїста задача має безліч розв'язків. Перший оптимальний план двоїстої задачі знахо­димо з другої таблиці, а саме У* = (4;0). Для того щоб знайти дру­гий оптимальний план, перейдемо до третьої симплексної таблиці. За провідний візьмемо другий рядок, бо йому відповідає &2 =0. Про­відний стовпчик визначимо з умови

{—4 —2}=шт{з;2}

4

6>2 = min { —; } = min <J -; 2} = 3,   j = 2.

Отже, провідним є стовпчик A2, а провідним елементом є j —З

Страницы:
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лінійна алгебра й аналітична геометрія