Постановка завдання лінійного програмування В операційному менеджменті за вирішення всіх цих завдань із використанням лінійного програмуванн
вся процедура загалом зводиться до пошуку значень n перемінних x1, x2, …, xn (n — похідне число), що відповідають m лінійним рівнянням або нерівностям (при цьому варто думати, що нерівності є лінійно незалежними) a11x1 + a12x2 + … + a1nxn = b1; a21x1 + a22x2 + … + a2nxn = b2; ................ am1x1 + am2 x2 + … + amn xn = bm (7.2)
і відповідному мінімальному значенню лінійної цільової функції Ф = с 1 х 1 + с2 х 2 + … + с n x n . (7.3)
За обчислення значень x1, x2, …, xn за відповідного максимального показника Ф завдання вирішується в такій самій постановці, але знаки всіх коефіцієнтів с1, с2, …, сn змінюються на протилежні. Так само нерівності типу a′11x1 + a′12x2 + … + a′1nxn = b′1; a′21x1 + a′22 x2 + … + a′2nxn = b′2; (7.4) ................ a′m1x1 + a′m2x2 + … + a′mnxn = b′m можуть бути приведені до вигляду (7.2) множенням обох їх частин на — 1, тобто aij = –a′ij, bi = –b′i (i = 1, 2, …, m; j = 1, 2, …, n). 376
Розділ 7 Економіко-математичні моделі і методи в операційному менеджменті
На практиці під час формулювання загального завдання, крім обмежень (7.4), обумовлюється незаперечність всіх перемінних, тобто xi = 0, i = 1, 2, …, n… (7.5)
Примітка. Якщо для деякого перемінного xj з числа пошукованих x1, x2, …, xn, задано обмеження на знак типу xj = 0, то в завданні, що відтворено співвідношеннями (7.2) і (7.5) з цільовою функцією (7.3), замість xj розглядається невідома x′j = –xj, для якої в систему (7.5) вводиться обмеження x′j = 0. (7.6)
Інші завдання математичного програмування — у тому числі і такі, в яких обмеження і цільова функція аналогічні співвідношенням (7.2), (7.3) і (7.5), але введена додаткова вимога рівності перемінних x1, x2, …, xn, цілим числам) – відносяться до завдань нелінійного програмування. Лінійне програмування досить широко використовується для моделювання різних виробничих процесів, транспортних і економічних завдань. Розглянемо одне з них — з оптимального планування операційної системи. Головна мета — досягнення максимального прибутку за виготовлення декількох видів продукції з орієнтуванням на наявні обмеження на сировину (тобто кількість одиниць видів сировини суворо регламентована і складає, відповідно, а1, а2, …, аm. Сформулюємо завдання. Нехай з m різних видів сировини виробляється n видів продукції. При цьому на виготовлення одиниці j-го виду продукції витрачається aij одиниць сировини i-го виду, а прибуток дорівнює Pj грн. З цього виходить, що наявні запаси сировини можуть бути використані для виробництва різних 377
О. М. Сумець Основи операційного менеджменту
кількостей виробів кожного з розглянутих видів. Імовірно, що оптимальним буде план випуску такої кількості одиниць x1, x2, …, xn кожного виду продукції, коли сумарний прибуток підприємства буде найбільшим. Саме такий план відповідає максимальному значенню лінійної функції Z = p1x1 + p2 x2 + … + pn xn... (7.7) Загальна кількість сировини першого виду, що йде на виготовлення x1 одиниць продукції першого виду, дорівнює а11х1, а загальні витрати сировини першого виду на реалізацію оптимального плану випуску складають a11x1 + a12 x2 + … + a1nxn і не можуть перевищувати наявної кількості а1 сировини. Ця умова передається обмеженням a11x1 + a12x2 + … + a1nxn ≤ а1. Аналогічні міркування справедливі і щодо решти m–1 видів сировини. Система обмежень у даному випадку записується так: a11x1 + a12x2 + … + a1nxn ≤ а1; a21x1 + a22x2 + … + a2n xn ≤ а2; ...................... am1x1 + am2x2 + … + amnxn ≤ аm. (7.8)
А оскільки обсяг продукції, що випускається, не може вимірюватися негативними величинами, то повинні дотримуватися і додаткові умови x1 = 0, x2 = 0, …, xn = 0... (7.9) Таке завдання цілковито відповідає завданню лінійного програмування з цільовою функцією (7.3) і обмеженнями (7.2), якщо замість максимуму функції Z знайти мінімум функції Z’ = – p1x1 – p2x2 – … – pnxn... 378
(7.10)
Розділ 7 Економіко-математичні моделі і методи в операційному менеджменті
Його розв’язання уможливлює визначення операційним менеджером оптимальних обсягів випуску. Далі у процесі обчислень він може виявити ті види продукції, випускати які за цих умов недоцільно, а, можливо, і зробити висновок про зміну номенклатури і навіть вибрати найбільш ефективну альтернативу замінникам. У процесі рішення таких завдань з великою кількістю перемінних, як правило, використовують спеціальні обчислювальні пакети, наприклад, пакет чисельних методів MERCURY або MathCAD PLUS 8.0 і більш сучасні версії. Якщо у формалізованій постановці завдання беруть участь лише дві перемінні (наприклад, ресурси розподіляються між двома продуктами), рішення можна знайти більш простим шляхом — графічно. 7.2.2 Подвійні завдання лінійного моделювання У практиці моделювання виробничих процесів дуже часто те саме завдання визначення екстремума (оптимального рішення) може припускати різні формулювання. Можливість по-різному формулювати завдання зазвичай буває обумовлена відомими співвідношеннями між перемінними завданнями (розв’язуваної ситуації, проблеми). Прикладом може слугувати відповідність між такими перемінними, як собівартість продукції і прибуток, прибуток і витрати виробництва, або у разі вирішення завдань з електротехніки — між напругою і струмом, опором і провідністю тощо. Таким чином коли між двома завданнями лінійного чи нелінійного програмування існують визначені співвідношення, кажуть, що ці завдання подвійні одне стосовно іншого. Відомі теореми подвійності точно описують ці співвідношення. У більшості випадків дані теореми мають форму тверджень, що за певних умов завдання мінімізації з обмеженнями пов’язано з 379
О. М. Сумець Основи операційного менеджменту
визначеним завданням максимізації таким чином: якщо існує розв’язання однієї проблеми, то існує можливість вирішення й іншої, причому вони збігатимуться. У цих випадках вихідне завдання називають прямим, а пов’язану з ним співвідношенням подвійності — подвійним завданням. Зисковість вирішення подвійних завдань очевидна за проведення якісних досліджень завдань лінійного програмування, особливо, коли необхідно досягти не тільки оптимального рішення, але й оцінити вплив на нього змін у параметрах, що представляють собою вихідну інформацію завдань. Проілюструємо суть на наступному прикладі. Припустимо, що для виготовлення продукції x1, x2, …, xn (див. вищенаведений приклад) необхідно закупити ресурси а1, а2, …, аm, на які потрібно установити оптимальні ціни — y1, y2, …, ym. Природньо, операційний менеджер буде зацікавлений у тому, аби витрати на закупівлю усіх видів ресурсів В, що є в кількостях а1, а2, …, аm, були мінімальними: В = а1y1 + а2 y2 + … + аm ym → min. (7.11)
Але продавець ресурсів, у свою чергу, зацікавлений в одержанні від продажу ресурсів а1, а2, …, аm виторгу, який був би не менше суми прибутку, отриманої від переробки цих ресурсів, приміром, на готову продукцію на своєму підприємстві, тобто слід знайти такий набір цін ресурсів (y1, y2, …, ym), який забезпечив би мінімальні витрати (загальні) на ресурси за умови, що сплата за них по кожному виду продукції не менша від прибутку від реалізації цієї продукції. Вирішити дану ділему операційний менеджер може у такий спосіб. Оскільки питомі витрати по кожному виду ресурсів у процесі виготовлення того чи іншого виду продукції відомі, то хід забезпечення виконання вимог продавця можна представити у вигляді відповідної системи обмежень 380
Розділ 7 Економіко-математичні моделі і методи в операційному менеджменті
а11y1 + а21y2 + … + аm1ym ≥ с1; а12y1 + а22y2 + … + аm2ym ≥ с1; .................... а13y1 + а23y2 + … + аm3ym ≥ сm. До всіх цих вимог варто додати ще одну — незаперечності усіх у, оскільки очевидно, що ціни на сировину не можуть бути негативними показниками у1 ≥ 0, у2 ≥ 0, …, ym ≥ 0... Цільова функція, що відбиває мінімальні витрати на сировину, описана залежністю (7.11). Отже, розглянуті два завдання є взаємно подвійними, з якими операційним менеджерам у реальному житті доводиться зустрічатися досить часто. Примітка. На практиці існує визначена кількість завдань керування, у яких керувальні перемінні можуть бути тільки цілими числами. Наприклад, завдання визначення оптимальної чисельності рухомого складу на маршруті тощо. Тобто в даних випадках обсяг рухомого складу, кількість робочих є тільки цілими числами. А тому такі завдання повинні формулюватися операційним менеджером як для цілечисленного програмування. Вирішуватися вони можуть тільки за використання дещо іншого підходу, ніж у попередні рази. Наприклад, задовільні результати за вирішення таких завдань дає використання графічних методів — геометричної інтерпретації завдання лінійного програмування. 7.2.3 Завдання квадратичного програмування Реальне життя насичене прикладами, коли аналізовані процеси, властивості можуть бути представлені лише квадратичними функціями. Тому завдання оптимізації з лінійними 381
О. М. Сумець Основи операційного менеджменту
обмеженнями називають завданнями квадратичного програмування, але за умови, якщо їхні цільові функції квадратичні. Причому пряме завдання можна сформулювати так: максимізувати Ф = ст х + хт Дх → max за умови x ≥ 0, Ax ≤ в. (7.13) Для забезпечення оптимального вирішення варто прийняти, що Д — симетрична негативно визначена матриця. Приклад. Є операційна система керування з дискретним часом. Представимо її наступними рівняннями: x = Ax0 + Bu m y = Hx
(7.12)
(7.14)
де хт = (х1т, х2т, …, хnт); х0 — відома вихідна умова; u — послідовність вхідних сигналів (команд керування). Тоді u = (u0, u1, u2, …, un–1)T... Тут нижні індекси — дискретні моменти часу. Для спрощення рішень будемо визначати вхідні сигнали як скалярні величини. Вихідні сигнали операційної системи позначимо через у рис. 7.9). При цьому «внутрішній стан» системи х описуватиметься рівнянням (7.14). Постановка завдання: необхідно вибрати таке рівняння u, яке б забезпечувало мінімальне значення функції J = y(Qy) + u(Ru) → min, Q > 0, R > 0. 382
(7.15) (7.16)
Розділ 7 Економіко-математичні моделі і методи в операційному менеджменті
ВХІД (керувальні
u0 u1 un-1
команди)
ВИХІД ТРАНСФОРМАЦІЙ НИЙ ПРОЦЕС (х)
........
........
у1 у2 уn
Рис. 7.9 Схема елементарної операційної системи керування
Рішення. Підставивши рівняння (7.14) у вираз (7.15), одержимо J = x т Hт (QHx) + uт(Ru) = = x0 тAтHт(QHAx0) + 2uтУтQHAx0 + + uт(R + УтHтQHB) u. (7.18) Отже, мінімум функції J буде досягнутий за u = –(R + УтHт(QHB))–1 * УтHт(QHAx0). (7.17)
Даний приклад демонструє те, що за використанням математичного апарата — лінійного програмування — можна вирішувати практичні управлінські завдання, якщо вони описуються навіть складними квадратичними функціями. 7.2.4 Симплекс-метод Операційні менеджери можуть застосовувати його для вирішення завдань лінійного програмування загального типу. Зараз для реалізації симплекс-методу існує достатнє число стандартних програм, використовуваних у сучасних комп’ютерах. Стандартний вигляд завдання лінійного програмування. Розглянемо загальний випадок розв’язання завдання лінійного програмування, коли необхідно віднайти n перемінну, що відповідає мінімальному значенню цільової функції і вписується у системи (7.2) і (7.5). 383
О. М. Сумець Основи операційного менеджменту
Після ряду перетворень і введення додаткових перемінних xn+1, xn+2, …, x5 можна систему нерівностей і цільову функцію (7.3) привести до системи лінійно незалежних рівнянь d11x1 + d12x2 + … + d15x5 = B1; d21x1 + d22x2 + … + d25x5 = B2; .................. dj1x1 + dj2x2 + … + dj5x5 = Bj... і виразу для цільової функції Z′ = с′1x1 + с′2x2 + … + с′5x5. (7.20) (7.19)
Для додаткових перемінних вводимо обмеження на знак, що записуємо у вигляді xi ≥ 0, i = 1, 2, …, S… (7.21)
Отже, можна сформулювати нове завдання: знайти перемінні х1, х2, …, х, що відповідають системам обмежень (7.19) і (7.21) і конкретному мінімальному значенню цільової функції (7.20). Обов’язковою приймемо умову, коли будь-яке оптимальне рішення за новим завданням включає значення перемінних x1, x2, …, xn — оптимальне вирішення розглянутого завдання лінійного програмування. У даному випадку вважається, що зазначене завдання набуло стандартного вигляду. Слід зазначити, що цей процес, як правило, збільшує число перемінних і обмежень, однак у багатьох випадках така операція є необхідною.
Ви переглядаєте статтю (реферат): «Постановка завдання лінійного програмування В операційному менеджменті за вирішення всіх цих завдань із використанням лінійного програмуванн» з дисципліни «Операційний менеджмент»
