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

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

j

Зауваження З. Якщо в останній симплексній таблиці ви­конується умова оптимальності плану, але число тих Aj, які дорівнюють нулю, більше за число обмежень m, то це означає,

247що оптимальний план не єдиний. Для знаходження другого оп­тимального плану, треба перейти до наступної симплексної таб­лиці, взявши за провідний той з небазисних стовпчиків, якому відповідає Д.,- = 0, а провідний рядок вибравши за симплекс­ним відношенням.

Приклад 1. Підприємство на основі трьох типів ресурсів Б і, Б2 і £3 може організувати виробництво певної продукції двома різними способами Рі і Р2.

Запаси ресурсів і витрати кожного типу ресурсів при кожному способі виробництва визначено таблицею

Типи

Витрати ресурсів

Запаси

ресурсів

Pi

P2

ресурсів

Si

1

2

4

S2

1

1

3

S3

2

1

В

При першому способі виробництва підприємство випускає за один місяць 3 тис. виробів, при другому - 4 тис. виробів.

Скільки місяців повинне працювати підприємство кожним з цих способів, щоб при наявних ресурсах забезпечити максимальний ви­пуск продукції?

< Складемо математичну модель задачі. Нехай x\ - час (в міся­цях) роботи підприємства способом Pi, а x2 - час (в місяцях) роботи підприємства способом P2. Тоді математична модель має вигляд:

f = 3xi + 4x2 max;

xi + 2x2 < 4, xi + x2 < 3, 2xi + x2 < 8;

xi > 0,   x2 > 0.

Для того щоб розв'язати цю задачу симплексним методом, зве­демо її до канонічного базисного вигляду, ввівши додаткові (балан­суючі) змінні x3 > 0, x4 > 0 і x5 > 0:

f = 3xi + 4x2 max;

2xi + 2x2 + x3 =4, xi + x2       + x4 = 3, 2xi + x2 + x5 = 8;

248

Х > 0,    І Є{1,--., 5}.

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

і

Б

сб

Ао

3

4

0

0

0

 

 

 

 

Аі

А2

Аз

А4

А5

1

Аз

0

4

 

1

 

2

1

0

0

2

АА

0

3

 

1

 

1

0

1

0

3

А5

0

8

 

2

 

1

0

0

1

т + 1

 

 

0

-3

-4

0

0

0

1

А2

4

2

 

1/2

 

1

1/2

0

0

2

А4

0

1

 

1/2

 

0

-1/2 -1/2

1

0

3

А5

0

6

 

3/2

 

0

 

0

1

т + 1

 

 

8

-1

0

2

0

0

1

А2

4

1

 

0

 

1

1

-1

0

2

Аі

3

2

 

1

 

0

-1

2

0

3

 

0

3

 

0

 

0

1

-3

1

т + 1

 

 

10

0

0

1

2

0

У першій симплексній таблиці умова оптимальності не вико­нується, бо Ді = —3 < 0, Д2 = —4 < 0. Оскільки найбільшим за абсолютною величиною є Д2, то до базису треба ввести вектор А 2 і вивести А3, бо

6»о2 = тіп 3 8 1 тіп {2 3 8} = 2,  і = 1.

Провідним елементом є 2 . Переходимо до наступної симплекс­ної таблиці, зробивши перерахунок елементів таблиці за методом Жордана-Гаусса.

У другій симлексній таблиці є від'ємне Ді = —1. Стовпчик, який йому відповідає, беремо за провідний. Провідний рядок виберемо за симплексним відношенням

#оі = тіп {—■—■—\ \1/2' 1/2' 3/2] тіп {4 2 4} = 2,  і = 2.

Переходимо до третьої симплексної таблиці, взявши за провідний

елемент

249

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

Отже, за першим способом підприємство повинно працювати два місяці, а за другим - один місяць. При цьому максимальний випуск продукції становитиме 10 тис. од.^

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

І = 2х2 4хз + 2х5 тіп;

Г х\ + 3x2 хз + 2x5 = 7, \   —2x2 + 4хз + Х4 = 12;

> 0,   і Є{1,..., 5}.

Оскільки задача записана в канонічній базисній формі, то розв'язуватимемо її за допомогою симплексного методу

і

Б

сб

Ао

0

2

—4

0

2

 

 

 

 

Аі

А2

Аз

А4

А5

1

Аі

0

7

1

 

3

 

— 1

0

2

2

А4

0

12

0

 

—2

 

4

1

0

т + 1

 

 

0

0

—2

4

0

—2

1

Аі

0

10

1

1

5/2

 

0

1/4

2

2

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