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

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

/ = сіхі + С2Х2 + СпХп тах; (1)

{ацхі + аі2Х2 + ... + аіпХп < Ьі, ахі + а22Х2 + .+ а2пХп < Ь2, атіхі + ат2Х2 + ... + атпХп < Ьт;

Х3 > 0,   і Є{1,...,п}, (3) або в матричній формі

/ = СХ тах;

262

АХ < А0; X > 0. (4)

Вважатимемо, що величини Ьі, , Су, і є {1,...,т}, і є {1,..., п}, мають той самий зміст, що й в задачі (1) - (3). Нехай, крім того, сировину можна направити або на виготовлення продукції, або на продаж іншому підприємству. Запитується, яку мінімальну ціну треба встановити за одиницю сировини Бі, і є {1,... ,т}, щоб прибуток від реалізації усіх запасів си­ровини був не меншим, ніж прибуток від реалізації продукції, яку можна виробити з цієї сировини.

Якщо позначити через у і, і є {1,... ,т}, шукану ціну оди­ниці сировини типу Бі, і є {1,...,т}, то прибуток, який ми одержимо від продажу сировини необхідної для виготовлення одиниці продукції    , дорівнюватиме

т

/^аіууі,   і є{1,...,п},

а прибуток від реалізації усіх запасів сировини становитиме

п

Щоб продаж сировини був не менш вигідний, ніж реаліза­ція готової продукції, виготовленої з неї, повинна виконуватися нерівність

т

/^аі3уі > Су,   і є{1,...,п}.

Будь-яка система цін уі, і є {1,...,т}, установлених із врахуванням цієї умови, задовольняє інтереси продавця сиро­вини. Зрозуміло, що врахування інтересів покупця вимагає ви­бору такої системи цін, яка мінімізує сумарну вартість сирови­ни, тобто

п

Я = ^ Ьіуі тіп .

263

Отже, математичною моделлю двоїстої задачі є така:

Б = Ьіуі + Ь2У2 + ■■ + Ьтут тіп; (5)

йііУі + а21У2 + ■■ + СітіУт > Сі, аі2Уі + Й22У2 + ■■■ + ат2Ут > С2, (6)

йіпУі + а2пУ2 + ■■■ + ЯтпУт > СП;

Уг > о,  і є^^^т}, (7)

або в матричній формі

Б = УА0 — тіп; У А > С;

У > 0. (8)

Змінні Уг > 0, і Є {1, ■, т}, називають оцінками або об­ліковими (неявними) цінами.

Якщо порівняти задачі (1) - (3) і (5) - (7), то побачи­мо правило, у відповідності з яким одна симетрична задача (пряма) перетворюється в іншу (двоїсту). Змінних Уг в задачі (5) - (7) стільки, скільки обмежень в системі нерівностей (2). Матриця умов задачі (5) - (7) є транспонованою до матриці умов задачі (1) - (3). Задача максимізації переходить у зада­чу мінімізації, обмеження-нерівності вигляду " <" замінюються обмеженнями-нерівностями вигляду ">". Вектор коефіцієнтів цільової функції прямої задачі стає вектором обмежень двоїстої задачі, а вектор Ао обмежень задачі (1) - (3) стає вектором кое­фіцієнтів цільової функції двоїстої задачі (5) - (7). Зауважимо, що коли одна з пари взаємно двоїстих задач симетрична, то й друга симетрична.

Зв'язок між обмеженнями взаємно двоїстих симетричних задач зручно зображати у вигляді такої схеми :

п

^ ац х3 < Ьг <—► Уг > 0, і Є т};

3 = 1

264

Хз > 0 <—► ^ агз Уг > с3-, і є{1^^,

г

Це означає, що кожному обмеженню однієї задачі відповідає змінна з тим самим номером іншої задачі, а кожній змінній однієї задачі відповідає обмеження з тим самим номером іншої задачі.

5.2. Різні вигляди математичних моделей двої­стих задач.

Розглянемо канонічну задачу

f = CX max;

АХ = А0;

X > 0. (9)

Описані в попередньому пункті правила побудови двоїстої задачі для випадку симетричної задачі можна застосувати і до задачі (9), записавши її у вигляді симетричної задачі. Доведе­но, що двоїста задача до задачі (9) має вигляд:

F = YА0 > min;

YA > C, (10)

де на вектор Y не накладається умова невід'ємності. Взаємно двоїсті задачі (9), (10) називають несиметричними, оскіль­ки в прямій задачі система обмежень задана рівностями, а в двоїстій - нерівностями, у прямій задачі всі змінні невід'ємні, а в двоїстій можуть бути й від'ємними.

Отже, взаємно двоїсті задачі бувають двох типів: симетрич­ні й несиметричні.

Симетричні задачі

1) Пряма задача Двоїста задача

f = CX max; F = YAo min;

AX < A0; YA > C;

X > 0. Y > 0.

26Б

2) Пряма задача

f = CX min;

AX > Aq; X > О.

Двоїста задача F = YAq max; YA < C; Y > О.

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