Материал: Економетрія - Навчальний посібник ( Лугінін О.Є.)


3.1. задачі лінійного програмування (лп) в економічній

практиці

 

3.1.1. Модель загальної задачі ЛП та її геометрична інтерпретація. Основна задача ЛП

 

Загальна задача ЛП полягає в знаходженні екстремуму (максимуму або мінімуму) лінійної цільової функції при наявності обмежень на п змінних у вигляді т лінійних нерівностей або рівнянь та умов невід'ємності змінних. Лінійне програмування найбільш розповсюджене в економіці та управлінні в прийнятті оптимальних рішень.

Економіко-математична модель загальної задачі ЛП представляється у вигляді:

Z = JPjXj — max (min); (3.1)

j=i

JajXj{<>, =)bt ((= 1...m); (3.2)

j=i

Xj > 0 (( = 1...n); (3.3)

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

Z = PX — max (min); (3.4) AX( <,>, = )B; (3.5)

X > 0. (3.6) У наведених формулах позначено: вирази (3.1), (3.4) -цільова функція; (3.2), (3.5) обмеження на змінні; (3.3), (3.6) -умови невід'ємності змінних; pj, ay, bi відомі постійні коефіцієнти; Xj - змінні, які підлягають визначенню; P=p) -матриця-строка коефіцієнтів цільової функції; B=(b) матриця-стовпець правих частин обмежень; X=(xj) - матриця-стовпець змінних; A=(aij) матриця коефіцієнтів при змінних у системі обмежень; т кількість обмежень; п кількість змінних; позначення (<, >, =) свідчить про те, що можуть використовуватись обмеження-невірності (<, >) або (і) обмеження-рівняння (=).

Задача ЛП називається основною, якщо з її формулювання можуть бути получені всі окремі випадки. Основна задача ЛП формулюється так.

Знайти максимум цільової функції від п змінних

п

Z = XPjXj — max (3.7)

j=і

при заданні т обмежень, які складаються у загальному випадку з r нерівностей та (m-r) рівнянь та умов невід'ємності змінних:

пп

Xajxj bi (i = 1-r); Xakjxj = bk (k = r + l,...m); (3.8)

xj > 0 (k = 1...п); bk > 0 (k = r + 1,...m). (3.9)

Формули (3.7)-(3.9) складають економіко-математичну модель основної задачі ЛП.

Якщо треба знайти мінімум цільовоїфункції (3.7), то задачу мінімізації можна звести до розглянутої задачі максимізації.

При цьому слід при тих же обмеженнях помножити коефіцієнти цільової функції на (-1) та розшукувати max(-Z)=Q. Тоді

minZ=Q (3.10) Геометрична інтерпретація задачі ЛП полягає в тому, що у п-мірному просторі кожне з обмежень на змінні інтерпретується як полупростір допустимих рішень, а система обмежень дає область допустимих рішень у вигляді випуклого многогранника-сімплекса. Кожна грань сімплекса це площина, яка описується і-м обмеженням, яке перетворюється у рівняння.

Значення   цільової   функції   Z   у   будь-якій точці

Х1 (х ,х12,...,хП) можна розглядати як відстань цієї точки від

п

площини рівня Z = X Pjxj = 0, яка проходить через начало

j=1

координат. Переміщуя цю площину паралельно самій собі так, щоб вона проходила через вершини сімплекса, можна для найбільш віддаленої вершини від площини рівня знайти максимальне значення цільової функції 2тах, а для найменш віддаленої вершини 2тіп.

У випадку двох змінних х1 та х2, коли область допустимих рішень задачі ЛП зображується у вигляді многокутника (див. рис. 2.2), графічне знаходження максимального Zmax, та мінімального 2тпп значень цільової функції показано на рисунку як найбільше та найменше ухилення  вершин  многокутника від  сліду площини рівня

 

3.1.2. Приклади задач ЛП і сформованих на їх основі оптимізаційних моделей

 

Задача оптимального використання ресурсів (оптимального планування)

Номенклатура продукції, яка випускається підприємством, складається з п найменувань. Для їх виробництва потрібно т видів ресурсів, запаси яких обмежені. Витрати і-го виду ресурсів на одиницю виду продукції складають ау(і=1...т; у=1...п). Запаси г-го виду ресурсів є Ь одиниць. Прибуток від реалізації одиниці у'-го виробу дорівнює Ру. Потрібно скласти такий оптимальний план випуску продукції кожного виду х', при якому підприємство отримує найбільший прибуток.

Економіко-математична модель буде мати такий вигляд: обчислити оптимальний план випуску продукції Х=(х^, з реалізації якої підприємство отримає найбільший прибуток,

п

що характеризується цільовою функцією 2 = ^ РуХу -» тах,

У=1

п

при обмеженнях на наявність ресурсів ^а уХ ■ < Ь і (і = 1...т)

У=1

та умовах невід'ємності змінних х, > 0 (у' = 1...п) .

Задача оптимального розподілу завдань з випуску однорідної

продукції

На n підприємствах галузі (в цехах одного заводу) випускається однорідна продукція, для якої є m запасів ресурсів. Витрати і-го ресурсу (i=l...m) на j-му підприємстві або цеху (j=l...n) в одиницю часу складають ау. Запаси ресурсів i-го виду дорівнюють Ьі. Показники продуктивності праці характеризуються коефіцієнтами ру. Потрібно скласти такий оптимальний план випуску кожного виду продукції Xj, за яким кожне підприємство (цех) забезпечило б максимальний обсяг випуску продукції.

Економіко-математична модель має вигляд як у попередній задачі: цільова функція Z буде відповідати обсягу продукції, який потрібно максимізувати; кожна нерівність системи обмежень характеризує запаси ресурсів, які при цьому повинні бути використані.

 

Задача оптимального використання потужностей

Підприємству заданий план за часом і номенклатурою випуску виробів: необхідно за термін часу (година, день тощо) випустити Ьу одиниць продукції виду j=1...n; продукція виготовляється на m станках, продуктивність яких задана коефіцієнтами ay(i=1...m; j=1...n). Відомі коефіцієнти Ьу, які відображають усі витрати по виготовленню продукції виду j на i-му станку в одиницю часу. Необхідно скласти оптимальний план роботи станків, щоб витрати на виробництво продукції були мінімальними.

Економіко-математична модель задачі буде такою: цільова функція виражає мінімальні витрати на виробництво усієї продукції при витратах часу Xj кожного і-го станка на

m n

виробництво j-ї продукції Z = ^^bjXij — min ; обмеження

i=1 j=1

n

за часом ^ Xj ^ T (і = 1...m) ;обмеження за номенклатурою

j=1

т

виробів     Xауху = Ьу ;     умови     невід'ємності змінних

і=1

х у > 0 (і = 1...т,у = 1...п) .

 

Задача оптимального розкрою матеріалів

Підприємство отримало полуфабрикати у вигляді т різних як за кількістю одиниць Ь(1=1...т), так і за розмірами партій. У кожній партії полуфабрикат тільки одного розміру. Цей полуфабрикат необхідно розкроїти на необхідні заготівки, щоб максимізувати загальну кількість повних комплектів заготівель.

Відомо, що в один комплект заготівель 5-го виду входить Ку штук полуфабрикатів (5=1...ї). Кожну одиницю полуфабрикату можна розкроїти на заготівки п різними засобами, при чому в розкрої одиниці і-ої партії у-м засобом (у=1...п) можна получити сіу5 заготівель 5-го виду.

Позначимо через х у кількість заготівель із г-ої партії полуфабрикатів, які заплановано розкроїти у-м засобом, так що із г-ої партії при у-му засобу розкрою буде виготовлено ау&у заготівель 5-го виду; у - кількість повних комплектів заготівель.

Тоді економіко-математична модель оптимального розкрою матеріалу запишеться у вигляді максимізації кількісті повних комплектів заготівель, що виражається цільовою функцією Х=у^тах при обмеженнях: за кількістю заготівель

т п

 

для складання числа комплектів     '= 1 =   > у   (у = 1...Ї);

К5

за   кількістю    заготівель   у    і-ої   партії полуфабрикатів

п

XХу = Ьі (і = 1...т);за умовами невід'ємності у>0; ху>0 (і=1...т, у=1...п).

Задача про суміші

Необхідно скласти суміш із n різних видів сировини, кожен з яких містить у собі m видів речовин (елементів). Кількість г-ої речовини (i=l...m) в одиниціу-го виду сировини (j=l...ri) складає ау. Вартість одиниціу-го виду сировини є ру. Допустима кількість г-ої речовини у суміші складає bi.

Позначимо через Ху кількість сировини у-го виду, яку заплановано використати для виготовлення суміші.

Тоді економгко-математична модель задачі зведеться до такої: знайти такий оптимальний план змішування видів сировини, при якому загальна вартість суміші буде мінімальною,     що     виражається     цільовою функцією

n

Z = XРуХу — min, з умовою обмежень на кількість г-го виду

у=1

n

речовин у суміші  XауХу > bi (i = 1...m)  та невід'ємності

у=1

змінних xy>0 (i=1...m, у=1...п).

 

Транспортна задача

Відомо, що є m постачальників А1, А2, Am однорідного вантажу у кількості відповідно а1, а2, am одиниць і п спожавачів вантажу В1, В2, Вп, яким потрібно b1, b2, bn одиниць цього вантажу. Вартість перевезень одиниці вантажу від г-го постачальника (i=1...m) до у-го споживача (у=1...гі) складає Су.

Необхідно скласти такий оптимальний план перевезень вантажу, який забезпечив би мінімальні транспортні витрати.

Позначимо через Ху кількість одиниць вантажу, який перевозиться від г-го постачальника до у-го споживача.

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

m n

пропозиції з сторін постачальників і споживачів: X at = X by .

i=1 у=1

Тоді закрита економгко-математична модель транспортної задачі буде представлена таким чином. Треба мінімізувати транспортні витрати перевезень, що виражається

т n

цільовою функцією Z = ^І^Ісуху     min, при обмеженнях на

i=1 j=1

змінні: увесь вантаж від постачальників повинен бути вивезений

 

Z

j=1

(і = 1...т);попит споживачів у вантажах повинен

 

вимагається

бути     задовільнений     ^ ху = Ь і (у = 1...П); невід'ємність змінних Ху > 0 (і=1...т,у=1...п).

 

Приклади побудови економіко-математичних моделей

 

Приклад 3.1. Задача оптимального використання ресурсів. Підприємству необхідно виготовити три види продукції Р1? Р2, Р3 з використанням двох видів ресурсів К1; И2, запаси яких обмежені. Чисельні дані задачі ілюструються

 

Вид ресурсів

Запас ресурсів

Кількість ресурсів на виготовлення одиниці продукції

 

 

Pi                      Р2 Р3

Ri

40

4                 4 2

R2

30

3                 8 4

Прибуток від реалізації 1 од. продукції, г.о.

-

10

15

12

 

Скласти економіко-математичну модель випуску продукції, щоб при її реалізації отримати найбільший прибуток.

Розв'язання. За невідомими, які необхідно обчислити, позначимо: х1 кількість продукції виду Р1; х2 кількість продукції виду Р2; х3 кількість продукції виду Р3.

В якості цільової функції Z, яку необхідно в даній задачі максимізувати, приймається загальний прибуток від реалізації всіх відів продукції. Тоді частка прибутку від реалізації продукції Р1 складає (10х1), від продукції Р2 (15х2), а від продукції Р3 (12хз); в загалі прибуток від реалізації всіх видів продукції буде Z=10x1+15x2+12xз—^max.

При виготовленні продукції запаси ресурсів не можуть бути перевищені, що накладає обмеження на використання ресурсів. Так, витрати ресурсу виду И на виготовлення продукції Рь Р2, Р3 будуть дорівнювати відповідно (4х;), {4x2) та (2x3). Тоді загальне обмеження для витрат ресурсу И1 має вигляд: 4х1+4х2+2х3<40. За аналогією можна записати обмеження з витрат ресурсу И2 на виготовлення видів продукції Рі, Р2, Рз : 3х1+8х2+4хз<30.

Очевидно, що невідомі х;, х2 та х3 не можуть бути невід'ємними, тобто хї>0, х2>0, х3>0.

Остаточно,    економіко-математична    модель задачі оптимального використання ресурсів буде мати вигляд: Х=10х;+15х2+12х3^>тах 4х1 + 4х2 + 2х3 < 40; [3х1 + 8х2 + 4х3 < 30;

х; > 0; х2 >; х3 > 0. Далі модель треба реалізувати (тобто обчислити) з використанням сімплекс-методу.

Приклад 3.2. Задача про суміші. Для відкорму тварин необхідно з трьох кормів К1, К2, К3 виготовити суміш. Відома вимагаєма годувальність порції суміші на одну тварину: годувальність речовини У1 не менше 10 од.; годувальність речовини У2 не менше 8 од. Інші дані задачі наведені у таблиці:         

Скласти економіко-математичну модель задачі.

Розв'язання. Невідомими задачі позначаються: х1 -кількість корму Кі в суміші; х2 кількість корму К2; х3 -кількість корму Кз.

Цільова фінкція Z, яку в даному разі треба мінімізувати, виражає витрати на корми Кі, К2, К3 в суміші: (4х1) витрати на корм Кі; (2х2) витрати на корм К2; (3х3) витрати на корм К3. Тоді цільова функція має вигляд: Z=4x1+2x2+3x3^^min.

Обмеження на невідомі покладаються з метою забезпечення необхідної годувальності порції суміші з розрахунку на одну тварину. Так, щоб забезпечити годувальність речовини Уі не менш 10 од., необхідно взяти корму Кі у кількості (2х1), корму К2 у кількості (3х2), корму К3 у кількості (х3). Тоді обмеження на годувальність порції суміші з речовини Уі запишеться у вигляді 2х1+3х2+х3>10. За аналогією обмеження на годувальність з речовини У2 буде таким: х1+2х2+х3>8.

Треба також врахувати умови невід'ємності невідомих: х1>0, х2>0, х3>0.

Остаточно, економіко-математична модель задачі про суміші запишеться у вигляді:

Х=4х1+2х2+3х3^>тїп; 2х1 + 3х2 + х3 > 10; [х1 + 2х2 + х3 > 8; х1 > 0; х2 >; х3 > 0.

 

Далі модель реалізується сімплекс-методом.

 

Приклад 3.3. Транспортна задача. На двох складах Аі та А2 є відповідно 11 і 14 од. однорідного вантажу. Попит у ньому магазинів Ві? В2 та В3 дорівнює відповідно 10, 8 і 7 од. Ці дані та вартість перевезень одиниці вантажу від складів до магазинів надані у таблиці:

10        8 7

11 І 8І6І5 " 14 І        4І5І7 "

Скласти економіко-математичну модель плану перевезень вантажів, щоб витрати були мінімальними.

Розв'язання. За невідомі ху приймаються кількість одиниць вантажу, які перевозяться від /-го складу до /-го магазину (/=1,2; /=1,2,3). Тоді цільова функція Z виражає вартість перевезень з мінімальними витратами.

Обмеження на невідомі використовуюються двох типів. По-перше, вантаж із складів повинен бути вивезений, що в даній задачі описується системою з двох рівнянь за числом складів (розглядаються рядки таблиці):

хп +     + х13 — 11;

[х21 + х22 + х23 — 14.

По-друге, кожен магазин повинен отримати стільки вантажу, скільки йому потрібно, що описується системою рівнянь за числом магазинів (розглядаються стовпці таблиці):

 

' х12 + х22 — 8; ^ х13 +        — 7.

Крім того, слід враховувати умови невід'ємності невідомих: ху>0 (/=1,2; у=1,2,3).

Тоді остаточно економіко-математична модель транспортної задачі буде мати вигляд:

Z — 8x11 + 6x12 + 5x13 + 4x21 + 5x22 + 7x23 —> min;

Хц + + — 11; x21 + x22 + x23 — 14;

< x11 + x21        —10;

x12 + x22        — 8;

x13 +   — 7;

xy> 0(i —1,2; j —1,2,3).

Запитання для самоконтролю

У чому полягає загальна задача ЛП?

Який склад математичної моделі задачі ЛП?

Записати математичну модель загальної задачі ЛП.

3.1.4.   Яка задача ЛП називається основною? Записати математичну модель основної задачі ЛП.

3.1.5.   Як зміниться формулювання основної задачі ЛП при мінімізації цільової функції?

3.1.7.   Навести приклади економічних задач, які можна звести до задачі ЛП.

3.1.8.   Сформулювати задачу оптимального використання ресурсів.

3.1.9.   Щоб в ній визначає цільова функція? обмеження на зміни? умови невід'ємності змінних?

3.1.10. Записати економіко-математичну модель задачі оптимального використання ресурсів.

Сформулювати задачу оптимального розподілу завдань з випуску однорідної продукції.

Що в ній визначає цільова функція? обмеження на зміні? умови невід'ємності змінних?

 

Записати економіко-математичну модель задачі оптимального розподілу завдань з випуску однорідної продукції.

Сформулювати задачу оптимального використання потужностей.

 

Що в ній визначає цільова функція? обмеження на зміні? умови невід'ємності змінних?

Записати економіко-математичну модель оптимального використання потужностей.

Сформулювати задачу оптимального розкрою матеріалів.

Що в ній визначає цільова функція? обмеження на зміні? умови невід'ємності змінних?

3.1.19. Записати економіко-математичну модель задачі оптимального розкрою матеріалів.

Сформулювати задачу про суміші.

Що в ній визначає цільова функція? обмеження на зміні? умови невід'ємності змінних?

3.1.22. Записати економіко-математичну модель задачі про суміші.

Сформулювати транспортну задачу.

Що в ній визначає цільова функція? обмеження на зміні? умови невід'ємності змінних?

Записати економіко-математичну модель транспортної задачі.

 

Вправи

 

3.1.1.   Підприємству необхідно виготовити два види продукції Р1 та Р2, на які планується використати таку кількість ресурсів трьох типів, припадаючих на одиницю продукції: 6, 4, 4, од. та 6, 2, 8 од. На виготовлення продукції використовуються ресурси R1, R2, R3, запаси яких обмежені та дорівнюють відповідно 36, 20 і 40 од. Прибуток від реалізації одиниці продукції виду Р1 дорівнює 12 г.о., а від одиниці продукції Р2 15        г.о. Необхідно скласти такий план випуску продукції, щоб від її реалізації отримати найбільший прибуток.

3.1.2.   На підприємстві виготовляються вироби двох видів: А, В. Для цього використовується сировина чотирьох типів І, II, III і IV, запаси яких дорівнюють відповідно 21, 4, 6,

10        од. Для виробу А необхідна така кількість одиниць сировини чотирьох видів: 2, 1, 0, 2 од. Для виробу В необхідна така кількість одиниць сировини відповідних видів: 3, 0, 1, 1 од. Випуск одного виробу типу А дає 3 г.о. прибутку, одного виробу типу В 2 г.о. Скласти план виробництва, який забезпечує найбільший прибуток.

3.1.3.   На підприємстві використовується сталь трьох марок: А, В, С. Запаси їх обмежені і становлять відповідно 10,

16        та 12 од. Підприємство випускає два вида виробів I, II. Для виробу I необхідно однієї одиниці сталі усіх марок. Для виробу

11        необхідно 2 одиниці сталі марки В, 1 одиниця марки С і не потрібна сталь марки А. Від реалізації одиниці виробу виду I підприємство отримує 3 г.о. прибутку, виду II 2 г.о. Скласти план випуску продукції, який має забезпечити найбільший прибуток.

Підприємство має ресурси двох типів у кількості 120 і 80 од. Ці ресурси використовуються для випуску продукції видів І і II, при чому витрати на виготовлення одиниці продукції виду І дорівнює 2 од. ресурсу першого типу та 2 од. ресурсу другого типу; на виготовлення одиниці продукції виду II - 3 од. ресурсу першого типу та 1 од. ресурсу другого типу. Прибуток від реалізації одиниці продукції першого виду складає 6 г.о., другого виду 4 г.о. Скласти план випуску продукції, який забезпечує найбільший прибуток при умові, що продукції першого виду повинно бути випущено не менше продукції другого виду.

Фабрика виготовляє три види тканин. Добові ресурси фабрики складають 700 од. виробничого устаткування, 800 од. сировини та 600 од. електроенергії, витрати яких на одиницю тканини такі: для устаткування за видами тканини 2, 3 і 4 од.; для сировини 1, 4 і 5 од.; для електроенергії 3, 4 і 2 од. Ціна одного метра тканини першого виду складає 8 г.о., другого виду 7 г.о., третього виду 6 г.о. Скільки треба виготовити тканини кожного виду, щоб прибуток від реалізації був найбільший?

Чотири станка I, II, III, IV обробляють два види деталей А та В. Кожна деталь проходить обробку на всіх чотирьох станках. Відомо, що час обробки деталі А на чотирьох станках дорівнює відповідно 1, 2, 1 та 3 години, а деталі В 2, 3, 1 та 1 година. Час роботи станків за один цикл виробництва дорівнює для кожного станка 16, 25, 20 і 24 годин. Прибуток від випуску одної деталі А складає 4 г.о., а деталі В 1 г.о. Скласти план виробництва, який забезпечує найбільший прибуток.

Для відкорму тварин необхідно з двох кормів К1 і К2 виготовити суміш. Задається годувальність порції суміші, яка розрахована на одну тварину: годувальність речовини V1 потрібна бути не менш 12 од.; V2 не менше 6 од.; V3 не менш 9 од. У кожному кілограмі корму К1 міститься 3 од. годувальної речовини V1, 1 од. годувальної речовини V2 і 3 од. годувальної речовини V3. В одному кілограмі корму К2 міститься 2 од. годувальної речовини V1, 2 од. годувальної речовини V2 і 1 од. годувальної речовини V3. Вартість одиниці корму К1 складає 2 г.о., одиниці корму К2 3 г.о. Необхідно змішати наявні корми у такій кількості, щоб забезпечити задану годувальність порції суміші при мінімальних витратах на корми.

3.1.8.   На птахофабриці використовуються два види кормів І і II. В одиниці маси корму І міститься 1 од. вітаміну А,

од. вітаміну В та 1 од. вітаміну С. В одиниці маси корму II міститься 4 од. вітаміну А, 2 од. вітаміну В і відсутній вітамін С. У денний раціон кожної птиці необхідно включати не менше 1 од. вітаміну А, не менше 4 од. вітаміну В і не менше 1 од. вітаміну С. Ціна одиниці маси корму І складає 3 г.о., корму II г.о. Скласти кожноденний раціон відкормлення птиці так, щоб забезпечити найбільш дешевий раціон годування.

3.1.9.   У чотирьох постачальників I, II, III, IV є відповідно 60, 70, 30, 40 од. однорідного вантажу. Попит у них споживачів 1, 2 і 3 дорівнює відповідно 80, 80, 40 од. Ці дані та вартість перевезень одиниці вантажу від постачальників до споживачів надані у таблиці:

 

 

80

80

40

60

4

3

5

70

8

7

6

30

4

5

9

40

10

9

7

Скласти план перевезень вантажів, щоб витрати були мінімальними.

3.1.10. Є умови транспортної задачі з перевезення однорідного вантажу з трьох станцій відправлення А, В і С в п'ять пунктів призначення П1, П2, П3, П4 і П5. Запаси вантажу на станціях, попит на них у пунктах призначення та вартість перевезень одиниці вантажу від пунктів відправлення в пункти призначення надані в таблиці: