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

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

Графічне розв'язування двоїстої задачі подамо на рис. 3

У2І

Областю допустимих розв'язків є кут ABC. Очевидно, що лінія найнижчого рівня проходить через точку B, тобто в цій точці цільо­ва функція F досягає мінімуму. Координати точки B знаходимо з системи рівнянь

f і - 3y2 = 6, \ і + 4y2 = 4.

Маємо у** = 7, 2; у*, = 2, 8, тобто У* = (7, 2; 2, 8), Fmin = 134, 8. Якщо підставити У * в обмеження двоїстої задачі, то дістанемо

3 • 7, 2 + 2, 8 • 5 = 35, 6 > 15, 2 7, 2 - 3 2, 8 = 6, -7, 2 + 4 2, 8 = 4.

271

Оскільки перше обмежеппя задовольпяється як строга перів-пість, то згідпо з другою теоремою двоїстості, зміппа x* = О. Підста­вивши xi = О у систему обмежепь вихідпої задачі, одержимо систему рівпяпь:

(     2x2 - x3 = 9, \ + 4x3 = 2Б;

звідки випливає, що x* = l2, 2, а x* = , 4. Тому X* = (О; l2, 2; , 4), /max = 1З4, В. ►

Друга теорема двоїстості має певний економічний зміст. Згідно з умовою 1) теореми 4, якщо деяка продукція Pj входить в оптимальний план виробництва, тобто x* > О, то при опти­мальній системі цін двоїстої задачі витрати ресурсів на його виготовлення збігаються з вартістю цієї продукції.

З умови 2) випливає, що коли в оптимальній системі цін деякий ресурс Si має ціну y* > О, то у відповідності з опти­мальним планом виробництва прямої задачі цей ресурс буде використаний повністю.

Скориставшись обмеженнями прямої та двоїстої задач, можна доповнити тлумачення умов 1) і 2) теореми 4.

З другого співвідношення теореми 4 випливає, що коли

m

/^aijy* > Cj, то x* = О, а це означає, що при збитковості

i=

виробництва продукції Pj вона не вироблятиметься на цьому підприємстві.

З першого співвідношення теореми 4, у свою чергу, одер-

п

жуємо, що за умови      ajx* < bi оцінка y* = О, тобто, коли

j=

при оптимальному плані виробництва г-й ресурс використову­ватиметься не повністю, то його оцінка y* повинна дорівнювати нулю. Отже, оптимальна двоїста оцінка ресурсу y* вказує, чи є відповідний ресурс дефіцитним, чи ні.

5.4. Розв'язування нари двоїстих задач сим­плексним методом. Нехай задача (1) - (3) розв'язана за допомогою симплексного методу і знайдено оптимальний план X* = (x^;...; x^), який визначається базисом, утвореним векторами Ai1 ,...,Aim. Позначимо через C6 = (ci1;...; Cim)

272вектор-рядок, складений з коефіцієнтів при невідомих у ці­льовій функції задачі (1) - (З), які відповідають цьому бази­су, а через A-1 матрицю, обернену до матриці A, складеної з компонентів векторів Ai1,... Aim базису. Доведено, що вектор Y* = C6a-1 є оптимальним планом двоїстої задачі (Б) - (7).

Отже, якщо знайдено за допомогою симплексного методу оптимальний план задачі (1) - (З), то з останньої симплексної таблиці визначають C6 і A-1, і, отже, за допомогою співвід­ношення Y* = C6a-1 одержують оптимальний план двоїстої задачі (Б) - (7).

Якщо ми маємо канонічну задачу лінійного програмування і двоїсту до неї, то у випадку, коли серед векторів A1,..., Ап, складених з коефіцієнтів при невідомих у системі обмежень прямої задачі, є m одиничних, указану матрицю A-1 утворю­ють числа перших m рядків останньої симплексної таблиці, які стоять у стовпчиках цих векторів. Тоді відпадає необхідність визначати оптимальний план двоїстої задачі множенням C6 на А-1, оскільки компоненти цього плану збігаються з відповідни­ми елементами Aj (m + 1)-го рядка одиничних векторів, якщо коефіцієнт cj = О, і дорівнюють сумі відповідного елемента Aj цього рядка та cj, якщо cj = О.

У випадку задачі (1) - (З) компоненти оптимального плану двоїстої задачі (Б) - (7) збігаються з числами Aj (m + 1)-го рядка останньої симплексної таблиці. Указані числа стоять у стовпчиках векторів, що відповідають додатковим змінним.

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

f = x2 - x4 - Зx5 min; xi + 2x2 - x4 + x5 = 1,

- 4x2 + x3 + 2x4 - x5 = 2, Зx2 + x5 + x6 = Б;

xj > О, j Є {1,..., б},

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

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

F = yi + 2y2 + Буз max;

27З

Уі < о,

2уі - 2 + 3уз < 1, У2 < О, -Уі + 2у2 < -1, Уі - У2 + Уз < -3, Уз < о.

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

і

Б

сб

Ао

0

1

0

-1

-3

0

 

 

 

 

Аі

А2

Аз

 

А5

Аб

1

Аі

0

1

1

2

0

-1

1

0

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