Задачімаксимізації та оптимізації діяльності підприємства
1.Найпростіша задача на максимізацію прибутку компанії
Компаніяробить два продукти в кількості x1 і x2 тонн за місяць відповідно. Тоннапершого продукту приносить 12 тис. грн… прибутку, а тонна другого – 8 тис.грн. Виробничі потужності компанії дозволяють випускати не більше 100 тонн двохпродуктів разом, при цьому виробництво першого продукту не може перевищуватибільше ніж у три рази виробництво другого. Треба визначити оптимальний обсягвиробництва, що приносить компанії оптимальний прибуток.
Стосовнодо даної задачі цільова функція (критерій оптимальності) має вид
F(x1,x2,……xn)=F(x1,x2)=12x1+8x2 тис. грн.
Обсягивипуску x1 і x2 є свідомо позитивні величини, тобто
x1 ≥0; x2 ≥ 0.
Міжзначеннями x1 і x2 маються зв'язки
x1 +x2 ≤ 100 x1 ≤ 3 x2
Такимчином, підходимо до типової задачі лінійного математичного програмування, колитреба відшукати значення керуючих параметрів x1, x2, що додають максимальнезначення цільової функції 12x1 + 8x2 з урахуванням фіксованих зв'язків іобмежень.
Постановкуі розв’язання цієї задачі зручно проілюструвати графічно, відобразивши зв'язкий обмеження в системі координат x1, x2, як зображено на рис. 1.
/>
Рис.1.- Графічна інтерпретація задачі оптимізації
Внаслідокпозитивних значень x1 і x2 (x1 ≥ 0; x2 ≥ 0) роз’вязання вартошукати в першому квадранті. Обмеження за сумарним випуском (x1 + x2 ≤100) звужує область пошуку до трикутника ОАС, який знаходиться всерединіобмеженого зверху прямою x1 + x2 = 100. Обмеження x1 ≤ 3 x2 ще більшзвужує область припустимих за умовою задачі значень x1 і x2, укладаючи її втрикутник ОАВ, обмежений знизу прямою x1 ≤ 3 x2. Серед усіх значень x1 іx2, ув'язнених всередині ОАВ, оптимальним відповідає тока В. У цій точці, щовідповідає координатам x1 = 75; x2 = 25, досягається найбільше з припустимихзначень x1, рівне 75. До найбільшого ж значення x1 і треба прагнути, тому щоперший вид продукції дає у розрахунку на одну тонну більше прибутку, ніж другий(12 > 8), тобто треба вибирати найбільше з можливих, припустимих значень x1.Оптимальному роз’вязанню відповідає, таким чином, точка B, у якій цільовафункція досягає свого максимального значення
12x1+ 8x2 = 12 · 75 + 8 ·25 = 1100 тис. грн.
Легкоперевірити, що усередині трикутника ОАВ будь-яке інше сполучення, крім x1 = 75;x2 = 25, забезпечує менший сумарний прибуток.
2.Транспортна задача
Розглянемоспочатку загальну постановку цієї досить складної оптимізаційної задачі іпобудуємо її економіко-математичну модель, яку потім проілюструємо найпростішимприкладом.
Нехайє n постачальників товару і m його споживачів. Кожен “i” постачальник здатнийпоставляти споживачам за визначений час кількість товару, рівному Ni, а кожен“j” споживач має потребу в кількості товару, рівному Mj. Познаніжо через xijкількість товару, що поставляється “i” постачальником “j” споживачу. Тодізагальний обсяг постачань Q, дорівнює обсягу попиту всіх споживачів, виразитьсяспіввідношенням:
Q = />, (1)
де Nj= /> є сумапостачань усім m споживачам з боку “i” постачальника.
Mj = /> є сума потреб“j” споживача, засвідчуваних постачальниками всіх n постачальників.
Приймемодалі, що вартість перевезення товару “i” постачальником “j” споживачу дорівнюєcij. Тоді загальна вартість перевезень, що залежать від прикріплення “i”постачальника до “j” споживача, тобто від значень xij дорівнює
F(xij) = />, i=1,2…n;j=1,2…m (2)
Оптимізаційназадача полягає в тому, щоб знайти значення xij, тобто величини постачань(перевезень) товару від кожного постачальника до кожного споживача, при якихзагальна вартість перевезень F(x11, x12, … xij, … xnm) буде мінімальною.Роз’вязання задачі повинне задовольняти таким обмеженням:
1)усі значення xij ненегативні, тобто
xij ≥0, (3)
2)можливість перевезень і запити споживача задовольняються цілком, що вираженоспіввідношенням (1).
Економіко-математичнамодель транспортної задачі, у поданому виді, яка характеризується цільовоюфункцією (2) і обмеженнями (1), (3), являє оптимізаційну модель задачілінійного математичного програмування. Роз’вязання таких задач при великихзначеннях кількості постачальників товару “n” і кількості споживачів товару “m”вимагає застосування складних математичних методів. Тому проілюструємороз’вязання транспортної задачі на простому прикладі, в якому відшуканняоптимального роз’вязання не складе великої праці.
Нехайє два постачальники і три споживачі товару. Можливості постачання і попитспоживачів, а також вартість перевезень одиниці вантажу наведені в такійтаблиці:
Таблиця1Споживачі Потреба в товарі, тонн Постачаль-ники Можливість переве-зення, тонн Вартість доставки одиниці товару споживачу, грн. за тонну Спожи-вач 1 Спожи-вач 2 Спожи-вач 3
1
2
3
50
70
40
1
2
100
60
C11 = 10
C21 = 8
C12 = 9
C22 = 10
C13 = 11
C23 = 9
Задачаполягає в тому, щоб знайти значення обсягів постачань x11, x12, x13 першогопостачальника першому, другому і третьому споживачам і обсяги постачань x21,x22, x23 другого постачальника відповідно першому, другому і третьомуспоживачам, при яких сумарні витрати
F(x11, x12, x13, x21, x22, x23) = C11x11 + C12x12 + C13x13 + C21x21 + C22x22 ++C23x23 = 10x11 + 9x12 + 11x13 + 8x21 + 10x22 + 9x23
будутьнайменшими. Одночасно повинні дотримуватися умови,
x11 +x12 + x13 = 100; x21 + x22 + x23 = 60; x11 + x21 = 50;
x21 +x22 = 70; x13 + x23 = 40,
якіхарактеризують повне задоволення потреб споживачів і повне використанняможливостей постачальників товару.
Томущо найдешевшою є вартість доставки одиниці товару другим постачальником першомуспоживачу, то використовуємо цю можливість цілком і приймемо x21 = 50 тонн ітим самим цілком задовольнимо його потребу. Можливість доставки, що залишилася,60 — 50 =10 тонн товару з боку другого постачальника надамо третьому споживачу,тобто x23 = 10, тому що витрата на доставку йому одиниці товару (C23 = 9)менше, ніж другому споживачу (C22 = 10) і менше, ніж доставка першим постачальником(C13 = 11). Звідси випливає, що x23 = 10 тонн. Можливості другого постачальникана цьому вичерпані і потреби, що залишилися, повинні бути задоволені першимпостачальником. Він поставить другому споживачу x12 = 70 тонн і третьомуспоживачу x13 = 30 тонн, тому що 10 тонн цей споживач вже одержав від другогопостачальника. Ну а постачання товару першим постачальником першому споживачу,так само, як і постачання другим постачальником другому споживачу виявлятьсянепотрібними, так що x11 = 0 і x22 = 0.
У підсумкушукане роз’вязання задачі має вид
X11 =0; X12 = 70; X13 = 30; X21 = 50; X22 = 0; X23 = 10,
асумарні витрати на постачання товарів, рівні
0 ·10 + 70 · 9 + 30 · 11 + 50 · 8 + 0 · 10 + 10 · 9 = 1450 грн.
і ємінімально можливі. Середня вартість перевезення однієї тонни товару складе /> грн. затонну, тим часом як при відсутності оптимізації середня ціна дорівнює
/> грн. за тонну
3.Моделі керування запасами
Моделікерування запасами покликані дати суб'єкту керування відповідь на питання проте, який рівень запасу ресурсів варто мати, як він повинний змінюватися в часі,оновлятися в зв'язку з надходженням і витратою ресурсів, щоб забезпечитибезперебійність, надійність проходження економічних процесів і в той же часмінімізувати витрати, пов’язані зі збереженням, поповненням і витратою запасів.Тому що рівень попиту зненацька виникаючих потреб у витраті ресурсів, щозапасаються, має найчастіше випадковий характер, то моделі керування запасамиповинні бути стохастичними, імовірнісними. Але в спрощеній постановці можливо івикористання детермінованих моделей.
Найбільшпоширені моделі керування складськими запасами. Розглянемо спочатку, якформується економіко-математична модель керування складськими запасами взагальній постановці.
Познаніжопоточний рівень запасу продукту на складі в момент часу t величиною 3(t). Тодісправедлива рівність
3(t)= 3нач + P(t) – R(t), (4)
де 3нач– початковий запас товарів на складі в момент t = 0;
P(t)– надходження товарів на склад за час t;
R(t)– витрата товарів зі складу за час t.
Очевидно,що в будь-який момент запас товарів на складі не може бути негативним, тобто
3(t) ≥0, (5)
Надходженняі витрата товарів зі складу звичайно виробляється партіями. Позначивши обсягпостачання в одній партії через Pi, а обсяг партії, що витрачається, Ri,перетворимо вихідне співвідношення до виду
/>, (6)
де n– кількість партій товару, що поставляються;
m –кількість партій товару, що витрачаються.
Цюрівність можна розглядати як базисну в моделі керування запасами. У залежностівід того, які величини, показники в ньому задані, а які є шуканими, розрізняютьрізні види керування запасами. У модель можуть входити також обмежувальні умовиі додаткові зв'язки між показниками, змінними величинами. Часто в модельвключаються показники витрати, що характеризують, на постачання, збереження,відправлення товарів зі складу і задача ставиться в площині мінімізації витрат.Замість одного виду товару іноді доводиться розглядати кілька видів, щоускладнює задачу.
4.Задача мінімізації витрат на доставку і збереження товару на складі
Товарпоставляється на склад партіями, кожна партія має той самий обсяг x. Задоставку однієї партії товару склад сплачує C1 грн., величина C1 не залежитьвід обсягу партії. За час Т склад одержує кількість товару, рівною Q.Збереження одиниці об'єму товару в одиницю часу коштує складу в C2 грн… Товарзі складу рівномірно постачається замовникам, які самі оплачують перевезеннятоварів зі складу. Потрібно встановити мінімальний обсяг партії постачання х,при якому сумарні витрати складу на доставку будуть мінімальними.
Встановимоспочатку витрати на доставку товару за час T. Тому що кількість партій дорівнюєчастці від розподілу загального обсягу постачань Q на обсяг однієї партії х, товитрати рівні />. Витрати на збереженнявстановимо, виходячи з того, що отримана складом партія товару х витрачаєтьсярівномірно, таким чином, на складі зберігається в середньому кількість товару,рівна половині поставленої партії, тобто />. Множачи цю кількість на час T іна питомі витрати збереження одиниці товару на одиницю часу, одержуємо, щозагальні витрати на збереження рівні />. Таким чином, сумарні витрати Cскладають
/>.
Требазнайти значення обсягу партії х, при якому сумарні витрати З виявлятьсямінімальними. Як відомо з математики, у точці екстремуму безупинної функціїЗ(х) похідна від її за аргументом х дорівнює нулю. Отже,
/>,
звідкизнаходимо шукане значення х0, тобто оптимальний обсяг партії товару
/>.
Це іє роз’вязання задачі.
Наприклад,якщо З1 = 6000 грн. за доставку партії товару, З2 = 300 грн. за збереженнятонни товару на складі протягом доби, загальний обсяг постачання Q = 100 тонн зачас Т = 40 доби, то
/> т,
тобтодля мінімізації витрат на доставку і збереження товару на складі требапоставляти його на склад партіями по 10 тонн у кожній партії.
5.Ігрові моделі
Ігровіекономіко-математичні моделі являють математичний опис економічних ситуацій, вяких відбувається зіткнення, протиставлення інтересів двох або декількохпротиборствуючих сторін (гравців), які переслідують різні цілі і діють такимчином, що лінія, спосіб дії одного з учасників залежить від дій іншого.Математична модель подібної конфліктної ситуації одержала назву гри, в якійберуть участь особи, які протистоять; сторони іменуються гравцями, а результатпротистояння сторін називають виграшем і, відповідно програшем. Якщо виграшгравця дорівнює програшу його супротивника, то така гра двох осіб називаєтьсягрою з нульовою або антагоністичною сумою.
Ігровімоделі дозволяють учасникам гри вибрати так звану оптимальну стратегію, тобтовстановити, в залежності від ситуації, що складається, спосіб дій, якийдозволяє максимізувати можливий виграш або мінімізувати можливий програш.Найбільш простий варіант гри – парна кінцева гра двох гравців, у якій кожний зних має вибір з кінцевого числа стратегій. Обрисуємо модель такої гри взагалі,а потім наведемо ілюстровані приклади її використання.
Припустимо,що в грі беруть участь гравці А і В. Гравець А має у своєму розпорядженні nстратегій, способів дій: A1, A2, …, An, а гравець В має у своєму розпорядженніможливість реалізувати m стратегій: B1, B2, …, Bm… В залежності від того, якустратегію Aj (i=1,2,…,n)вибере гравець А і яку стратегію Bj (j=1,2,…,m) виберегравець В, залежить результат гри кожного з них, тобто виграш aij одного з гравціві, відповідно, програш іншого. Таким чином, будь-якій парі стратегій (Ai, Bj)відповідає визначене значення виграшу aij. У підсумку сукупність усіх можливихвиграшів у даній грі утворить матрицю, стовпці якої відповідають стратегіїодного гравця, а рядка – стратегії іншого. Таку матрицю називають платіжною абоматрицею гри.
Загальнийвид платіжної матриці, рядки якої відповідають стратегіям гравця А, а стовпці –стратегіям гравця В, зображений на рис. 2.
Рисунок2. — Платіжна матриця парної гри B1 B2 Bm A1 a11 a12 a1m A2 a21 a22 a2m An an1 an2 anm
Привиборі своєї стратегії Ai з нчиру n можливих стратегій А1, А2, …, Аn гравець Аповинний враховувати, що його суперник У вибере у відповідь стратегію Bj знчиру можливих стратегій, прагнучи звести виграш гравця А до мінімуму. Нехайнайменший із усіх можливих виграшів гравця А при виборі ним стратегії Ai, тобтонайменше значення aij у “i” рядку платіжної матриці дорівнює ai, тобто ai = minaij. Найбільше зі значень ai(i=1, 2, …, n) познаніжо, a, отже, a = max ai. Такемаксимальне значення з набору мінімальних виграшів гравця, що відповідаютьусьому спектру застосовуваних ним стратегій, називають нижньою ціною абомаксимальним виграшем з мінімальних – максиміном. Максимін являє собоюгарантований виграш гравця А при будь-якій стратегії гравця В, тому що гравецьА може вибрати ту стратегію, яка приносить йому максимальний виграш змінімально можливих.
ГравецьВ, прагнучи зменшити виграш гравця А і розуміючи, що А прагне до максимальноговиграшу, вибираючи свою контрстратегію Вj, аналізує, насамперед, максимальноможливі виграші гравця А. Нехай серед усіх виграшів гравця А при виборі гравцемВ стратегії Bj максимально можливе значення дорівнює bj, тобто bj = max bij.Найменше з усіх можливих значень bj(j=1, 2, …, m) познаніжо b, тобто b = minbj. Таке мінімальне значення з нчиру максимальних виграшів гравця, щовідповідає всьому спектру застосовуваних ним стратегій, називають верхньоюціною гри або мінімальним виграшем з максимальних – мінімаксом. Мінімакс являєнеминучий програш гравця В при кожній зі стратегій гравця А, тому що гравець Абуде, природно, прагнути максимізувати програш гравця В і відповідним чиномвибирати свою стратегію.
Відомийу теорії ігор принцип мінімакса рекомендує гравцям вибирати з розуміньобережності, зменшення ризику максимінну стратегію при прагненні одержатинайбільший виграш або мінімаксну при прагненні мінімізувати програш.Проілюструємо це положення на простих прикладах.
6.Модель гри Людини з Природою
Убагатьох випадках результат діяльності людей залежить не тільки від вибору нимитієї або іншої стратегії, але і від ситуацій, що складаються в зовнішнімсередовищі. Класичний випадок – вплив погодних умов, природних явищ на підсумкиекономічної діяльності. Люди як би грають із Природою, що створює різніситуації, які не сприяють одержанню людьми кращих результатів. Яку ситуацію“вибере” Природа у своїй грі з людьми – важко передбачати і тому доводитьсявраховувати можливі ситуації.
НехайЛюдина має у своєму розпорядженні можливість здійснювати три стратегії дій Ai зметою одержання прибутку, а Природа здатна створити чотири види ситуацій Bj,кожна з яких впливає тим або іншим способом на величину прибутку. Складемоплатіжну матрицю, у клітинах якої зафіксовані розраховані визначеними методами(які в прикладі не розглядаються) величини можливого прибутку. Наприклад,матриця прибутків у тисячах грн. має вид: B1 B2 B3 B4 A1 25 32 29 27 A2 29 36 28 32 A3 27 28 31 24
Застосуємомаксимінну стратегію, прагнучи дістати найбільший прибуток. Виділимо в кожнім зрядків матриці мінімальні значення прибутку, що можуть бути отримані приздійсненні однієї з можливих стратегій A1, A2, A3 і самих несприятливих умовах,створюваних Природою. Це 25 тис. грн. при стратегії А1, 28 тис. грн. пристратегії А2 і 24 тис. грн. при стратегії А Максимальне з цих значень – 28 тис.грн… відповідає максимінній стратегії А2, що і варто вибрати, забезпечивши тимсамим гарантоване одержання цієї величини прибутку при будь-яких умовах,ситуаціях, створюваних Природою.
Проілюструємотепер мінімаксну стратегію, використовуючи платіжну матрицю, у клітинах якоїзазначені величини втрат, що виникають при здійсненні стратегій A1, A2, A3 вумовах B1, B2, B3, B4. Нехай матриця має вид B1 B2 B3 B4 A1 53 55 48 51 A2 49 52 50 56 A3 51 53 52 47
Виділяємов кожному з рядків матриці максимально можливі при здійсненні даної стратегіївтрати. Це – 55 при стратегії А1, 56 – при стратегії А2 і 52 – при стратегії АМінімальне з цих значень дорівнює 52 і відповідає стратегії А3, що і ємінімаксною.