vm1

B2, B3 i B4 цегельнi заводи. Потреби заводiв у глинi не бiльшi, нiж продуктивнiсть кар’єрiв. Вiдомо скiльки глини потрiбно кожному заводу i скiльки її добувають у кожному з кар’єрiв. Вiдома також вартiсть перевезення однiєї тонни глини з кожного кар’єру до вiдповiдного заводу. Треба спланувати постачання зводiв глиною так, щоб витрати були найменшими. Всi необхiднi данi наведено в таблицi

J Нехай xij – кiлькiсть глини, яку одержує з кар’єру Ai,

i2 f1; 2; 3g, цегельний завод Bj, j 2 f1; 2; 3; 4g. Тодi система нерiвностей

8

< x11 + x12 + x13 + x14 · 49;

:x21 + x22 + x23 + x24 · 48; x31 + x32 + x33 + x34 · 42

характеризує кiлькiсть глини, яку буде вивезено з кожного кар’єру, а система рiвнянь

визначає кiлькiсть глини, яку одержує кожний з цегельних заводiв.

Витрати на перевезення вантажу складають:

1)у пункт B1 f1 = 5x11 + 8x21 + 17x31,

2)у пункт B2 f2 = 8x12 + 10x22 + 28x32,

3)у пункт B3 f3 = 24x13 + 20x23 + 35x33,

4)у пункт B4 f4 = 30x14 + 32x24 + 40x34.

221

Сумарнi витрати

f = f1 + f2 + f3 + f4 = 5x11 + 8x21 + 17x31 + 8x12 + 10x22+ +28x32 + 24x13 + 20x23 + 35x33 + 30x14 + 32x24 + 40x34:

Отже, математична модель задачi має вигляд:

f = 5x11 + 8x21 + 17x31 + 8x12 + 10x22 + 28x32 + 24x13+

+20x23 + 35x33 + 30x14 + 32x24 + 40x34 ! min;

xij ¸ 0; i 2 f1; 2; 3g; j 2 f1; 2; 3; 4g: I

1.2. Форми запису задачi лiнiйного програмування.При постановцi задач лiнiйного програмування можливi рiзнi випадки: цiльова функцiя в одних задачах максимiзується, а в iнших – мiнiмiзується, обмеження на змiннi можуть задаватися рiвностями або нерiвностями. Крiм того, умова невiд’ємностi поширюється не на всi змiннi. Важливим є те, що цi вiдмiнностi носять формальний характер. Зокрема, немає необхiдностi розрiзняти задачi максимiзацiї i мiнiмiзацiї цiльової функцiї, оскiльки

max f(x) = ¡ min(¡f(x));

min f(x) = ¡ max(¡f(x)):

У залежностi вiд вигляду системи обмежень задачi лiнiйного програмування подiляють на три типи: стандартну, канонiчну i загальну.

222

матрицi однакового розмiру, то нерiвнiсть A · B рiвносильна

нерiвностям aij · bij, i 2 f1; : : : ; mg, j 2 f1; : : : ; ng.

Векторна форма. Якщо позначити через Aj j-й стовпчик матрицi A, тобто

то задачi (7) – (9) i (10) – (12) можна подати вiдповiдно у виглядi:

де CX – Скалярний добуток векторiв C = (c1; c2; : : : ; cn) i X =

(x1; x2; : : : ; xn).

1.3. Еквiвалентнi перетворення задач лiнiйного програмування. Очевидно, що стандартна i канонiчна задачi є частинними випадками загальної. У той же час всi цi типи задач еквiвалентнi мiж собою : загальна задача за допомогою простих перетворень зводиться до стандартної або канонiчної, а останнi перетворюються одна в одну. Тому, розв’язавши одну з них, ми однозначно дiстанемо розв’язок другої.

225

На конкретних прикладах опишемо перетворення, якi доз-

воляють звести один тип задачi до iншого.

Приклад 4. Звести до канонiчного вигляду задачу

f= 8x1 + 2x2 ! max;

½x1 + x2 · 16;

4x1 ¡ 2x2 · 20; x1 ¸ 0:

J У цiй задачi обидва обмеження є нерiвностями, а на змiнну x2 не накладено жодних обмежень. Для зведення задачi до канонiчного вигляду введемо в обмеження-нерiвностi додатковi (балансуючi) змiннi x3 ¸ 0 i x4 ¸ 0 так, щоб нерiвностi x1 +x2 · 16, 4x1 ¡2x2 · 20 перетворилися на рiвностi x1 + x2 + x3 = 16, 4x1 ¡ 2x2 + x4 = 20. Змiннi x3 i x4 ввiйдуть в цiльову функцiю з нульовими коефiцiєнтами. Оскiльки змiнна x2 довiльна, то подамо її у виглядi x2 = x02 ¡x002 , де x02 ¸ 0, x002 ¸ 0. Тодi дiстанемо канонiчну задачу

f = 8x1 + 2x02 ¡ 2x002 ! max;

½

x1 + x02 ¡ x002 + x3 = 16;

4x1 ¡ 2x02 + 2x002 + x4 = 20;

x1 ¸ 0; x02 ¸ 0; x002 ¸ 0; x3 ¸ 0; x4 ¸ 0: I

Приклад 5. Звести до канонiчного вигляду задачу:

f = 2x1 ¡ 3x2 + x3 ¡ 2x4 ! min;

8

< 3x1 ¡ 2x2 + 4x3 + x4 · 12;

:¡2x1 + 3x2 + x3 ¡ 2x4 ¸ 6; ¡x1 + 2x2 ¡ x3 + 3x4 = 8;

x1 ¸ 0; x2 ¸ 0; x3 · 0:

J На змiннi x1 i x2 вже накладено умову невiд’ємностi, а тому їх залишаємо без змiн. Змiнну x3 замiнимо на x¹3 = ¡x3 i тому отримаємо, що x¹3 ¸ 0. Змiнну x4 замiняємо на рiзницю x4 = x04 ¡ x004 , де x04 ¸ 0, x004 ¸ 0. Крiм того, введемо двi додатковi (балансуючi) змiннi x5 ¸ 0, x6 ¸ 0, якi перетворюють перше i друге обмеженнянерiвностi в обмеження-рiвностi. Далi вiд цiльової функцiї f перейдемо до функцiї f~ = ¡f.

226

Отже, задача зведена до такого канонiчного вигляду:

f~ = ¡(2x1 ¡ 3x2 ¡ x¹3 ¡ 2x04 + 2x004 ) ! max;

8

< 3x1 ¡ 2x2 ¡ 4¹x3 + x04 ¡ x004 + x5 = 12; ¡2x1 + 3x2 ¡ x¹3 ¡ 2x0 + 2x00 ¡ x6 = 6;

: 4 0 4 00

¡x1 + 2x2 + x¹3 + 3x4 ¡ 3x4 = 8;

x1 ¸ 0; x2 ¸ 0; x¹3 ¸ 0; x04 ¸ 0; x004 ¸ 0; x5 ¸ 0; x6 ¸ 0: I

Приклад 6. Звести до стандартного вигляду канонiчну задачу

f= 2 ¡ x1 + 3x2 ! max;

½2x1 + x2 + x3 ¡ 3x4 = 10; 4x1 + x2 ¡ x3 + x4 = 8;

xj ¸ 0; j 2 f1; : : : ; 4g:

J Запишемо систему обмежень у виглядi нерiвностей, зменшивши кiлькiсть незалежних змiнних. Для цього спочатку зведемо цю систему до базисної форми, скориставшись методом ЖорданаГаусса:

Отже, система обмежень набула базисного вигляду

½¡x1 + x3 ¡ 2x4 = 1;

3x1 + x2 ¡ x4 = 9:

Тут x2 i x3 базиснi змiннi, а x1 i x4 – вiльнi змiннi. Запишемо задачу, виразивши цiльову функцiю i обмеження через вiльнi змiннi.

227

Для цього з системи обмежень знайдемо x2 i x3 через вiльнi змiннi

½x3 = 1 + x1 + 2x4; x2 = 9 ¡ 3x1 + x4

i пiдставимо їх в цiльову функцiю. Тодi одержимо, що

f = 2 ¡ x1 + 3(9 ¡ 3x1 + x4) = 29 ¡ 10x1 + 3x4:

Оскiльки x2 ¸ 0 i x3 ¸ 0, то систему обмежень можна записати у виглядi нерiвностей

½¡x1 ¡ 2x4 · 1;

3x1 ¡ x4 · 9:

Отже, наша задача набуде такого вигляду:

f = 29 ¡ 10x1 + 3x4 ! max;

½¡x1 ¡ 2x4 · 1;

3x1 ¡ x4 · 9:

x1 ¸ 0; x4 ¸ 0: I

Вправи

1. Для пропонованої задачi скласти математичну модель:

1) Треба утворити сумiш з трьох хiмiчних речовин A1; A2, A3. Вiдомо, що утворена сумiш повинна мiстити: речовини A1 не менше 6 одиниць, речовини A2 не менше 8 одиниць, речовини A3 не менше 12 одиниць. Речовини A1; A2; A3 мiстяться у трьох видах продуктiв ¦1; ¦2; ¦3 у концентрацiях, що визначаються таблицею

Цiна одиницi продукту ¦1 становить 2 гр.од., продукту ¦2 – 3 гр.од., продукту ¦3 – 2,5 гр.од. Сумiш повинна бути такою, щоб вартiсть використаних продуктiв була найменшою.

228

2) Три нафтопереробних заводи A1; A2, A3 iз максимальною щоденною продуктивнiстю вiдповiдно 30, 20, 35 тис. тонн бензину забезпечують чотири бензосховища B1, B2, B3, B4, потреби яких становлять 10, 20, 25, 20 тис. тонн бензину вiдповiдно. Бензин транспортується до бензосховища за допомогою трубопроводiв. Вартiсть перекачування 1000 т бензину вiд заводiв до сховищ наведено в таблицi

Необхiдно спланувати переказування бензину так, щоб сумарна вартiсть була мiнiмальною.

3) З листового прокату необхiдно вирiзати заготовки двох типiв A i B для виготовлення 60 штук виробiв. Для одного виробу треба три заготовки типу A i вiсiм заготовок типу B. Розмiри листа, а також розмiри i конфiгурацiя заготовок дозволяють вибрати чотири рацiональних варiанти, що вiдображено в таблицi

Скласти такий план розкрою, щоб одержати необхiдну кiлькiсть заготовок кожного типу при мiнiмальних сумарних вiдходах.

4)Магазин оптової торгiвлi реалiзує три види продукцiї P1, P2

i P3. Для цього використовують два типи обмежених ресурсiв: S1 – корисна площа примiщень, яка складає 450 м2; S2 – робочий час працiвникiв магазину, що дорiвнює 600 людино/год. Товарообiг повинен бути не меншим 240 тис. грн. Необхiдно скласти план товарообiгу, який забезпечував би максимальний прибуток. Витрати ресурсiв на реалiзацiю i отримуваний при цьому прибуток наведенi в таблицi

229

Вiдповiдi

18: 1) f = 2x1 + 3x2 + 2; 5x3 ! min; < 2x1 + x2 + 3x3 ¸ 6;

:x1 + x2 + 1; 5x3 ¸ 8;

3x1 + 4x2 + 2x3 ¸ 12;

xj ¸ 0; j 2 f1; 2; 3g;

2) f = 4x11 + 5x12 + 3x13 + 7x14 + 7x21 + 6x22 + 2x23 + 5x24+ +2x31 + 3x32 + 9x33 + 8x34 ! min;

230