Скачать

Задачі максимізації та оптимізації діяльності підприємства

Задачі максимізації та оптимізації діяльності підприємства

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

Задача полягає в тому, щоб знайти значення обсягів постачань 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. - Платіжна матриця парної гри

При виборі своєї стратегії Ai з нчиру n можливих стратегій А1, А2, …, Аn гравець А повинний враховувати, що його суперник У вибере у відповідь стратегію Bj з нчиру можливих стратегій, прагнучи звести виграш гравця А до мінімуму. Нехай найменший із усіх можливих виграшів гравця А при виборі ним стратегії Ai, тобто найменше значення aij у “i” рядку платіжної матриці дорівнює ai, тобто ai = min aij. Найбільше зі значень ai(i=1, 2, …, n) познаніжо, a, отже, a = max ai. Таке максимальне значення з набору мінімальних виграшів гравця, що відповідають усьому спектру застосовуваних ним стратегій, називають нижньою ціною або максимальним виграшем з мінімальних – максиміном. Максимін являє собою гарантований виграш гравця А при будь-якій стратегії гравця В, тому що гравець А може вибрати ту стратегію, яка приносить йому максимальний виграш з мінімально можливих.

Гравець В, прагнучи зменшити виграш гравця А і розуміючи, що А прагне до максимального виграшу, вибираючи свою контрстратегію Вj, аналізує, насамперед, максимально можливі виграші гравця А. Нехай серед усіх виграшів гравця А при виборі гравцем В стратегії Bj максимально можливе значення дорівнює bj, тобто bj = max bij. Найменше з усіх можливих значень bj(j=1, 2, …, m) познаніжо b, тобто b = min bj. Таке мінімальне значення з нчиру максимальних виграшів гравця, що відповідає всьому спектру застосовуваних ним стратегій, називають верхньою ціною гри або мінімальним виграшем з максимальних – мінімаксом. Мінімакс являє неминучий програш гравця В при кожній зі стратегій гравця А, тому що гравець А буде, природно, прагнути максимізувати програш гравця В і відповідним чином вибирати свою стратегію.

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

6. Модель гри Людини з Природою

У багатьох випадках результат діяльності людей залежить не тільки від вибору ними тієї або іншої стратегії, але і від ситуацій, що складаються в зовнішнім середовищі. Класичний випадок – вплив погодних умов, природних явищ на підсумки економічної діяльності. Люди як би грають із Природою, що створює різні ситуації, які не сприяють одержанню людьми кращих результатів. Яку ситуацію “вибере” Природа у своїй грі з людьми – важко передбачати і тому доводиться враховувати можливі ситуації.

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

Застосуємо максимінну стратегію, прагнучи дістати найбільший прибуток. Виділимо в кожнім з рядків матриці мінімальні значення прибутку, що можуть бути отримані при здійсненні однієї з можливих стратегій A1, A2, A3 і самих несприятливих умовах, створюваних Природою. Це 25 тис. грн. при стратегії А1, 28 тис. грн. при стратегії А2 і 24 тис. грн. при стратегії А Максимальне з цих значень – 28 тис. грн.. відповідає максимінній стратегії А2, що і варто вибрати, забезпечивши тим самим гарантоване одержання цієї величини прибутку при будь-яких умовах, ситуаціях, створюваних Природою.

Проілюструємо тепер мінімаксну стратегію, використовуючи платіжну матрицю, у клітинах якої зазначені величини втрат, що виникають при здійсненні стратегій A1, A2, A3 в умовах B1, B2, B3, B4. Нехай матриця має вид

Виділяємо в кожному з рядків матриці максимально можливі при здійсненні даної стратегії втрати. Це – 55 при стратегії А1, 56 – при стратегії А2 і 52 – при стратегії А Мінімальне з цих значень дорівнює 52 і відповідає стратегії А3, що і є мінімаксною.