ПЕРЕДМОВА Головне завдання фахівців з економіки та підприємництва — керувати економічними системами, розробляючи і впроваджуючи стратегічні та тактичні плани. Керування економічними системами — це, по суті, використання знань про системи, здобуття нової інформації та застосування її з метою відшукання найефективніших способів досягнення заданих результатів. Організаційна форма, що має будуватися не за бюрократичним принципом, а на засадах адхократії, стає структурою холдингового типу: за таких умов координується робота багатьох тимчасових груп, які розпочинають і припиняють свою діяльність згідно з темпами змін у навколишньому середовищі. Отже, для керування економічними системами необхідна інформація. Людство вступило у ХХІ століття, у якому стрімко відбуваються процеси інформатизації та інтелектуалізації суспільства. Знання та індивідуальний підхід перетворюються на основну цінність інформатизованого суспільства. Більш того, головним фактором для людини стає не абсолютний дохід, а, як стверджує Р. Інглегарт, ступінь безпечності, статус і якість життя. Прагнення до матеріальних цінностей змінюється на прагнення до самовираження, пошуку сенсу життя, бажання залишити свій слід у ньому. Дедалі більше людей на Заході надають перевагу праці не найдохіднішій, а творчо цікавій, яка дає змогу самореалізуватися. Те, що К. Маркс і Ф. Енгельс цілком справедливо визначали як суспільство вільної індивідуальності, починає виявлятися у країнах Заходу. Наразі ми стаємо свідками інтелектуалізації та інформатизації західного суспільства і можемо бути впевненими, що цей процес не обмине Україну. Наша країна має до цього готуватися, розвивати наукові дослідження, виховувати відповідних фахівців і, що найважливіше, таких, котрі мають відповідний рівень знань. На наших очах пройшла комп’ютерна революція. У домівках з’явилися комп’ютери, оснащені сучасним програмним забезпеченням з широкими можливостями. Завдяки Інтернету наше суспільство має змогу використовувати у своїй діяльності світові досягнення науки, культури тощо. Десять років тому такий перебіг справ мало хто міг передбачити. Немає сумніву, що у наступному десятиріччі комп’ютер стане таким же поширеним, як і телефон. Інформатизація суспільства — закономірний процес. Наприклад, у США злам припав на 1991 рік, коли вперше витрати на придбання інформаційної техніки (112 млрд дол.) перевищили витрати на придбання промислового обладнання (107 млрд дол.)1. Цей рік можна вважати першим роком інформаційної ери. Відтоді різниця між зазначеними витратами постійно збільшується. Зростання ролі знань, сучасних технологій, добування нової важливої для керування інформації притаманне інформатизованим суспільствам. С. Л. Удовик вдало на прикладі компаній «ІВМ» та «Microsoft» показав сутність і переваги використання інформаційних технологій. Наприкінці 1996 року ринкова вартість компанії «Microsoft» становила 85,5, а «ІВМ» — 70,7 млрд дол., хоча остання продавала набагато більше продукції. Окрім того, вартість основних виробничих засобів та устаткування «ІВМ» сягає 16,6 млрд дол., а «Microsoft» — не перевищує 930 млн дол. Отже, з позиції індустріального суспільства основною вартістю «Microsoft» є «повітря» — ідеї, думки, набутий працівниками досвід, престижне ім’я, можливості, особливо можливості перспективні, а також розумні й творчі голови службовців. Як вдало висловився Д. Танскотт з приводу «Microsoft», активи компанії щовечора розходяться по домівках. Більш того, з погляду матеріальних активів інша добре відома у нас компанія — «Visa International» — просто не існує, хоча й здійснює фінансові угоди на третину трильйона доларів за рік2. Зауважимо, що в розвинутих країнах чисельність працівників, зайнятих у сфері виробництва, з року в рік зменшується. Так, нині у США частка таких працівників становить близько 10 %, а в інтелектуальних сферах зайнято вже майже 60 %. Принагідно зазначимо, що рівень рентабельності у виробничій сфері не перевищує 5—15 %, а в інтелектуальній — 1000—2000 %. Саме тому високотехнологічні й інтелектуальні суспільства практично не переживають криз — рівень рентабельності їхньої продукції витримує багаторазове зниження цін. За умов інформатизації суспільства головним його надбанням стає інтелектуальний продукт, отримуваний завдяки розробці нових технологій та інвестиціям у знання. Підкреслимо, що коли йдеться про інформатизацію суспільства, то керівник має відповідати за використання й ефективність знань. Отже, у таких суспільствах змінюються сутність і методи керування економічними системами. Інформаційна та комп’ютерна революція прискорює розвиток суспільства, яке буде не капіталістичним і не комуністичним, а інформаційним. Ефективність сягне такого високого рівня, що всі члени суспільства в матеріальному плані будуть повністю задоволені. Проте це не означає, що в суспільстві не буде суперечностей. Суспільство внаслідок такої революції поділиться на два протилежні класи, а саме, на тих, хто опанував комп’ютерні технології, і на тих, хто цього не зробив або не зміг зробити. Виникне реальне протистояння в суспільстві, яке може мати негативніші наслідки, ніж перехід наших предків від кустарного до фабричного виробництва. Річ у тім, що промислова революція, яка розтягнулася в часі, дала можливість людям адаптуватися до нових умов. При цьому створювалися нові робочі місця. Комп’ютерна революція проходить стрімко, загрожує зруйнувати більше робочих місць, ніж створити, формуються нові жорсткі «класові» бар’єри, особливо між високо- і малоосвіченими членами суспільства. Принагідно зазначимо, що українське суспільство значною мірою відстає від світового рівня у процесах інформатизації, використання комп’ютерної техніки. Важливою для нашого суспільства є проблема вдосконалення керування економічними системами на базі комп’ютерних технологій, тобто інтенсивного впровадження систем підтримки прийняття рішень (СППР), які впродовж трьох останніх десятиліть широко застосовуються у розвинутих країнах. Наприклад, для розроблення програмного забезпечення СППР США щорічно витрачають понад 1 млрд доларів. Хоча в Україні такі системи ще практично не використовуються, але інтелектуальна діяльність нашого суспільства є доволі прогресуючою і динамічною, його інформатизація потребуватиме використання СППР. Фахівці-економісти мають бути готовими до такого перебігу процесів інформатизації. СППР, окрім загального програмного забезпечення, містять у собі банк економіко-математичних методів і моделей. Щоб ефективно застосовувати СППР, необхідно знати засадні принципи та прийоми математичного моделювання, вміти будувати економіко-математичні моделі економічних процесів та явищ, знати методи оптимізації різних задач. Усе це є змістом дисциплін економіко-математичного циклу. Отже, глибоке вивчення цього циклу дисциплін дасть змогу фахівцеві-економісту вступити в інформаційне суспільство, допоможе здобувати нові знання та унікальну інформацію. Цей цикл дисциплін є базовим у підготовці економістів і підприємців. Тільки з допомогою методів математичного моделювання можна збагатитися знаннями про системи, у тому числі й економічні. Математичне програмування є однією з засадних дисциплін економіко-математичного циклу, які вивчають в економічних вузах. У пропонованому навчальному посібнику на прикладі економічних задач досить популярно викладені основні методи математичного програмування, освоєння яких не потребує глибоких математичних знань, а лише старанної праці. У посібнику дано теоретичні засади та алгоритми розв’язання задач математичного програмування, домашні завдання тощо. У підручнику, окрім загальнодоступного матеріалу, включено параграфи 1.4; 2.8.7; 2.9; 3.7; 5.10; 6.6, що містять понадпрограмний матеріал і присвячені студентам, які ширше і глибше цікавляться прикладною математикою. Вказаний матеріал не є обов’язковим для бакалаврів-економістів, але його вивчення є бажаним для студентів, які будуть займатися математичним моделюванням. Читач може опустити відмічений текст, що не впливатиме на подальше засвоєння матеріалу. Кінцевий рівень знань відповідає програмі курсу «Математичне програмування». Увагу допитливого студента звернемо на той факт, що розвиток математичного програмування почався трохи більше шести десятиліть тому. 1939 року академік Л. В. Канторович, досліджуючи деякі задачі економічного змісту, розробив методи чисельного розв’язування екстремальних задач. Цей науковий напрямок розвивається досить бурхливо. Ряд вчених за розроблення методів оптимізації отримали Нобелівські премії, серед них — і академік Л. В. Канторович. Отже, працьовиті і талановиті студенти мають можливість ознайомитися в періодичній пресі з останніми досягненнями у сфері оптимізації функціонування і розвитку економічних процесів. Опанувати математичне моделювання і методи оптимізації студенти мають неодмінно, щоб стати в інформаційному суспільстві фахівцями високого рівня. «Мало є речей, які не піддаються математичному обґрунтуванню; і коли вони не піддаються, це ознака того, що наші знання про них дуже малі і нечіткі. А маючи змогу вдатись до математичного обґрунтування, великою дурістю було б шукати якесь інше, — це все одно, що йти навпомацки в темряві, коли поряд стоїть свічка». Дж. Арбатнот ПРЕДМЕТ, СФЕРИ ТА ОСОБЛИВОСТІЗАСТОСУВАННЯ МАТЕМАТИЧНОГО ПРОГРАМУВАННЯ В ЕКОНОМІЦІ. КЛАСИФІКАЦІЯ ЗАДАЧ 1.1. Предмет та об’єкти математичного програмування Назва дисципліни «Математичне програмування» асоціюється передусім з програмуванням як процесом створення програм для ПЕОМ за допомогою спеціальної мови. Проте насправді це лише не дуже вдалий переклад англійського терміну mathematical programming, що означає розроблення на основі математичних розрахунків програми дій для досягнення обраної мети. В економічних, виробничих, технологічних процесах різних галузей народного господарства виникають задачі, подібні за постановкою, що мають ряд спільних ознак та розв’язуються подібними методами. Типова постановка задачі математичного програмування така: деякий процес може розвиватися за різними варіантами, кожен з яких має свої переваги та недоліки, причому, як правило, таких варіантів може бути безліч. Необхідно із усіх можливих варіантів вибрати найкращий. З цією метою використовуються математичні методи. Сутність задачі економічного вибору та пов’язану з цим необхідність використання моделей та методів математичного програмування проілюструємо на прикладі. Фірма спеціалізується на виготовленні та реалізації електроплит і морозильних камер. Припустимо, що збут продукції необмежений, проте обсяги ресурсів (праці та основних матеріалів) обмежені. Завдання полягає у визначенні такого плану виробництва продукції на місяць, за якого виручка була б найбільшою. Норми використання ресурсів та їх загальний запас, а також ціни одиниці кожного виду продукції наведені в табл. 1.1. Таблиця 1.1 ІНФОРМАЦІЯ, НЕОБХІДНА ДЛЯ СКЛАДАННЯ ВИРОБНИЧОЇ ПРОГРАМИ Вид продукції Норми витрат на одиницю продукції Ціна одиниці продукції, ум. од.
робочого часу, люд.-год. листового заліза, м2 скла, м2
Морозильна камера 9,2 3 — 300
Електрична плита 4 6 2 200
Загальний запас ресурсу на місяць 520 240 40 —
Розглянемо кілька можливих варіантів виробничої програми. Перша виробнича програма. Очевидно, що найпростішим з усіх можливих варіантів є виробництво одного виду продукції. Припустимо, що виготовляються лише морозильні камери. Ресурс робочого часу (520 люд.-год.) дає змогу виготовляти 520 : 9,2 = 56 морозильних камер. Наявна кількість листового заліза забезпечує виготовлення 240 : 3 = 80 морозильних камер. Скло для виготовлення даного виду продукції не використовується. Отже, кожного місяця можна випускати лише 56 морозильних камер, що дасть виручку обсягом 56 300 = 16 800 ум. од. Зазначимо, що у разі реалізації такої виробничої програми загальний запас листового заліза використовується не повністю, а скло не використовується взагалі. Друга виробнича програма. Визначимо кількість електроплит, які можна виготовити за даних обсягів ресурсів:
На виробництво 20 електроплит буде використано таку кількість ресурсів: буде використано залишок
Залишки першого та другого ресурсів забезпечать виробництво морозильних камер обсягом:
Отже, друга виробнича програма уможливлює виробництво 20 електроплит та 40 морозильних камер. Виручка становитиме: 20 · 200 + 40 · 300 = 16 000 ум. од. Зіставляючи першу та другу виробничі програми, бачимо, що за першою виручка є більшою, отже, вона краща, ніж друга. Зрозуміло, що розглянуті програми не вичерпують усіх можливих варіантів. Наприклад, доцільно було б розглянути програму виробництва 41 морозильної камери та можливої кількості електроплит; 42 морозильних камер та можливої кількості електроплит; 43 морозильних камер та можливої кількості електроплит і т. д. Отже, для того, щоб знайти найкращий варіант виробництва продукції, необхідно перебрати досить велику кількість всіх можливих варіантів (для інших задач у більшості випадків кількість таких варіантів є дуже великою або нескінченною). Зауважимо, що дана задача є надто спрощеною порівняно з реальними економічними задачами, в яких кількість ресурсів та видів продукції може сягати сотень найменувань, і тоді простий перебір всієї множини варіантів абсолютно неможливий. Отже, постає необхідність розроблення спеціальних математичних методів розв’язання таких задач, тобто математичного обґрунтування найефективніших виробничих програм. Саме зі словом «програма» і пов’язана назва предмета — «математичне програмування». Пошук реального оптимального плану є, як правило, складним завданням і належить до екстремальних задач, в яких необхідно визначити максимум чи мінімум (екстремум) функції за визначених обмежень. Математичне програмування — один із напрямків прикладної математики, предметом якого є задачі на знаходження екстремуму деякої функції за певних заданих умов. Об’єктами математичного програмування є різноманітні галузі людської діяльності, де в певних ситуаціях необхідно здійснити вибір найкращого з можливих варіантів дій. Основою такого вибору є знаходження розв’язку екстремальної задачі методами математичного програмування. Розв’язання екстремальної економічної задачі складається з побудови економіко-математичної моделі, підготовки інформації, відшукання оптимального плану, економічного аналізу отриманих результатів і визначення можливостей їх практичного застосування. Математична модель економічного об’єкта (системи) — це його спрощений образ, поданий у вигляді сукупності математичних співвідношень (рівнянь, нерівностей, логічних співвідношень, графіків тощо). 1.2. Математична постановка задачі математичного програмування Подамо схематично довільну економічну систему у такому вигляді (рис. 1.1):
Рис. 1.1. Схема економічної системи Параметри сk (k = 1, 2, ..., l) є кількісними характеристиками системи. Наприклад, якщо йдеться про таку економічну систему, як сільськогосподарське підприємство, то його параметрами є наявні ресурси (земельні угіддя, робоча сила, сільськогосподарська техніка, тваринницькі та складські приміщення), рівень урожайності сільськогосподарських культур, продуктивності тварин, норми витрат ресурсів, ціни та собівартість проміжної і кінцевої продукції, норми податків, проценти за кредит, ціни на куповані ресурси тощо. Частина параметрів сk для певної системи може бути сталими величинами, наприклад, норми висіву насіння сільськогосподарських культур, норми споживання тваринами кормів тощо, а частина — змінними, тобто залежатиме від певних умов, як, скажімо, урожайність сільськогосподарських культур, собівартість продукції, реалізаційні ціни на рослинницьку й тваринницьку продукцію. Змінні величини бувають незалежними чи залежними, дискретними чи неперервними, детермінованими або випадковими. Наприклад, залежною змінною є собівартість продукції, незалежною від процесу функціонування підприємства величиною є початковий розмір статутного фонду, дискретною — кількість корів, неперервною — площа посіву озимої пшениці, детермінованою — норма висіву насіння кукурудзи на гектар, випадковою — кількість телят, які народяться у плановому періоді. Вхідні змінні економічної системи бувають двох видів: керовані xj (j = 1, 2, ..., n), значення яких можна змінювати в деякому інтервалі; і некеровані змінні yi (і = 1, 2, ..., m), значення яких не залежать від волі людей і визначаються зовнішнім середовищем. Наприклад, обсяг придбаного пального — керована, а температура повітря — некерована змінна. Залежно від реальної ситуації керовані змінні можуть переходити у групу некерованих і навпаки. Наприклад, у разі насиченого ринку обсяги придбання дизельного палива є керованою змінною величиною, а за умов дефіциту цього ресурсу — некерованою. Кожна економічна система має певну мету свого функціонування. Це може бути, наприклад, отримання максимуму чистого прибутку. Ступінь досягнення мети, здебільшого, має кількісну міру, тобто може бути описаний математично. Нехай F — вибрана мета (ціль). За цих умов вдається, як правило, встановити залежність між величиною F, якою вимірюється ступінь досягнення мети, вхідними змінними та параметрами системи: F = f (x1, x2, ..., xn; y1, y2, ..., ym; c1, c2, ..., cl). (1.1) Функцію F називають цільовою функцією, або функцією мети. Для економічної системи це є функція ефективності її функціонування та розвитку, оскільки значення F відображує ступінь досягнення певної мети. У загальному вигляді задача математичного програмування формулюється так: Знайти такі значення керованих змінних xj, щоб цільова функція набувала екстремального (максимального чи мінімального значення). Отже, потрібно відшукати значення . (1.2) Можливості вибору xj завжди обмежені зовнішніми щодо системи умовами, параметрами виробничо-економічної системи тощо. Наприклад, площа посіву озимої пшениці обмежена наявністю ріллі та інших ресурсів, сівозмінами, можливістю реалізації зерна, необхідністю виконання договірних зобов’язань тощо. Ці процеси можна описати системою математичних рівностей та нерівностей виду: (1.3) Тут набір символів (, =, ) означає, що для деяких значень поточного індексу і виконуються нерівності типу , для інших — рівності (=), а для решти — нерівності типу . Система (1.3) називається системою обмежень, або системою умов задачі. Вона описує внутрішні технологічні та економічні процеси функціонування й розвитку виробничо-економічної системи, а також процеси зовнішнього середовища, які впливають на результат діяльності системи. Для економічних систем змінні xj мають бути невід’ємними: . (1.4) Залежності (1.2)—(1.4) утворюють економіко-математичну модель економічної системи. Розробляючи таку модель, слід дотримуватись певних правил: 1. Модель має адекватно описувати реальні технологічні та економічні процеси. 2. У моделі потрібно враховувати все істотне, суттєве в досліджуваному явищі чи процесі, нехтуючи всім другорядним, неістотним у ньому. Математичне моделювання — це мистецтво, вузька стежка між переспрощенням та переускладненням. Справді, прості моделі не забезпечують відповідної точності, і «оптимальні» розв’язки за такими моделями, як правило, не відповідають реальним ситуаціям, дезорієнтують користувача, а переускладнені моделі важко реалізувати на ЕОМ як з огляду на неможливість їх інформаційного забезпечення, так і через відсутність відповідних методів оптимізації. 3. Модель має бути зрозумілою для користувача, зручною для реалізації на ЕОМ. 4. Необхідно, щоб множина змінних xj була не порожньою. З цією метою в економіко-математичних моделях за змоги слід уникати обмежень типу «=», а також суперечливих обмежень. Наприклад, ставиться обмеження щодо виконання контрактів, але ресурсів недостатньо, аби їх виконати. Якщо система (1.3), (1.4) має єдиний розв’язок, то не існує набору різних планів, а отже, й задачі вибору оптимального з них. Будь-який набір змінних x1, x2, ..., xn, що задовольняє умови (1.3) і (1.4), називають допустимим планом, або планом. Очевидно, що кожний допустимий план є відповідною стратегією економічної системи, програмою дій. Кожному допустимому плану відповідає певне значення цільової функції, яке обчислюється за формулою (1.1). Сукупність усіх розв’язків системи обмежень (1.3) і (1.4), тобто множина всіх допустимих планів утворює область існування планів. План, за якого цільова функція набуває екстремального значення, називається оптимальним. Оптимальний план є розв’язком задачі математичного програмування (1.2)—(1.4). 1.3. Приклад економіко-математичної моделі Повертаючись до наведеного прикладу 1.1, побудуємо економіко-математичну модель даної задачі. Позначимо через х1 кількість вироблених морозильних камер, а через х2 — електроплит. Виразимо математично умови, що обмежують використання ресурсів. Виходячи з нормативів використання кожного з ресурсів на одиницю продукції, що наведені в табл. 1.1, запишемо сумарні витрати робочого часу: 9,2х1 + 4х2. За умовою задачі ця величина не може перевищувати загальний запас даного ресурсу, тобто 520 люд.-год. Ця вимога описується такою нерівністю:
Аналогічно запишемо умови щодо використання листового заліза та скла: ;
Необхідно серед множини всіх можливих значень х1 та х2 знайти такі, за яких сума виручки максимальна, тобто: . Отже, умови задачі, описані в прикладі 1.1, можна подати такою економіко-математичною моделлю: , за умов: ; ; ; . Остання умова фіксує неможливість набуття змінними від’ємних значень, тому що кількість виробленої продукції не може бути від’ємною. Розв’язавши задачу відповідним методом математичного програмування, дістаємо такий розв’язок: для максимальної виручки від реалізації продукції необхідно виготовляти морозильних камер — 50 штук, електроплит — 15 (х1 = 50, х2 = 15). Перевіримо виконання умов задачі: ; ; . Всі умови задачі виконуються, до того ж оптимальний план дає змогу повністю використати два види ресурсів з мінімальним надлишком третього. Виручка становитиме: ум. од. Отриманий оптимальний план у порівнянні з першим варіантом виробничої програми уможливлює збільшення виручки на ум. од., тобто на . 1.4. Багатокритеріальна оптимізація* Зауважимо, що в класичній постановці задачі математичного програмування передбачається одна цільова функція, яка кількісно визначена. У реальних економічних системах на роль критерію оптимальності (ефективності) претендують кілька десятків показників. Наприклад, максимум чистого доходу від реалізації виробленої продукції чи максимум рівня рентабельності, мінімум собівартості виробленої продукції або мінімум витрат дефіцитних ресурсів. Крім того, бажаним є застосування кількох критеріїв одночасно, причому вони можуть бути взагалі несумісними. Наприклад, вимога досягти максимальної ефективності виробництва за мінімальних витрат ресурсів з погляду постановки математичної задачі є некоректною. Мінімальні витрати ресурсів — це нульові витрати, що мають місце за повної відсутності будь-якого процесу виробництва. Аналогічно максимальна ефективність може бути досягнута лише у разі використання певних обсягів (звичайно не нульових) ресурсів. Тому коректними є постановки задач такого типу: досягти максимальної ефективності при заданих витратах чи досягти заданого ефекту за мінімальних витрат. Оскільки не існує єдиного універсального критерію економічної ефективності, то досить часто вдаються до розгляду багатокритеріальної оптимізації. Хоча задача математичного програмування передбачає одну цільову функцію, розроблено математичні методи, що дають змогу будувати компромісні плани, тобто здійснювати багатокритеріальну оптимізацію. Найчастіше способи використання багатьох критеріїв у задачах математичного програмування зводяться до штучного об’єднання кількох вибраних показників в один. Наведемо кілька таких способів [7]. Нехай у задачі обрано m критеріїв оптимальності Fi . Загальний критерій може мати вигляд суми окремих показників ефективності з відповідними коефіцієнтами: , (1.5) де — додатні чи від’ємні коефіцієнти. Додатні коефіцієнти відповідають тим критеріям, які потрібно максимізувати, а від’ємні — тим, які мінімізуються. Абсолютні значення коефіцієнтів відповідають пріоритету (важливості) того чи іншого показника. Наприклад, якщо розв’язується виробнича задача, то з додатними коефіцієнтами ввійдуть такі величини, як обсяг прибутку, отриманого від реалізації товарів та послуг, з від’ємними — витрати ресурсів (часу, праці), собівартість одиниці продукції. Узагальнений критерій може подаватись у вигляді дробу, де в чисельнику знаходиться добуток показників, які необхідно максимізувати, припустимо , а в знаменнику — добуток тих, які потрібно мінімізувати : (1.6) Загальним недоліком критеріїв (1.5), (1.6) є те, що існує можливість недостатню ефективність одного критерію компенсувати іншим. Наприклад, зниження значення виконання попередніх замовлень (в (1.6) буде в чисельнику) може компенсуватися зменшенням використання ресурсів (знаменник дробу (1.6)). Оскільки окремі величини в чисельнику та знаменнику пропорційно зменшилися, то значення дробу не змінюється, проте складені на основі таких розрахунків плани можуть призвести до негативних наслідків. Такі критерії порівнюють із запропонованим Львом Толстим жартома «критерієм оцінки людини» у вигляді дробу, де в чисельнику зазначають справжні достоїнства людини, а у знаменнику — її думку про себе. Отже, якщо людина майже немає достоїнств (чисельник дробу буде малим числом) і водночас у неї зовсім відсутня зарозумілість (в знаменнику — майже нуль), то вона буде мати нескінченно велику цінність (оскільки будь-яке число, поділене на нескінченно малу величину, дає нескінченність). Отже, до використання зазначених способів формування цільових функцій необхідно підходити зважено та продумано. Ще один метод запропонував І. Никовський [24]. Оптимальний план знаходять окремо за кожним з вибраних критеріїв, після чого отримують множину значень цільової функції . На останньому етапі розв’язується початкова задача з одним критерієм виду: , (1.7) де — значення i-го критерію оптимальності в оптимальному компромісному плані. За такого підходу розв’язок задачі визначається за критерієм, що дорівнює мінімальному значенню модулів часток відхилень значень кожної цільової функції у компромісному плані від їх оптимальних значень у їх же оптимальних значеннях, що робить всі критерії однаково важливими. Для врахування переваг одних критеріїв над іншими доцільно застосовувати узагальнений критерій такого виду: . (1.8) Недоліками цих двох способів є, по-перше, жорстке співвідношення між значеннями відхилень критеріїв оптимальності, що значно звужує множину допустимих планів; по-друге, одному значенню деякого критерію може відповідати множина інших, причому таких, за яких оптимальний план з економічного погляду ефективніший; по-третє, відсутня методика об’єктивного визначення коефіцієнтів . Зведення багатокритеріальної задачі до задачі з одним критерієм може також здійснюватися через виділення з вибраного набору показників одного, який вважають найважливішим — Fk і намагаються досягти його максимального значення (якщо необхідно знайти мінімум, то досить змінити знак показника). Всі інші показники (критерії) є другорядними, і на них накладаються обмеження виду: , де є нижньою межею значення відповідного показника, або , якщо необхідно, щоб значення показника не перевищувало . Для виробничих задач можна виділити як найважливіший показник ефективності прибуток і, максимізуючи його величину, додатково вводити обмеження щодо рентабельності виробництва не нижче або собівартості не вище певного рівня. Такі обмеження входять до системи початкових умов задачі. Останнім розглянемо так званий «метод послідовних поступок». Всі обрані критерії необхідно ранжирувати за спаданням їх важливості: спочатку головний, скажімо F1, потім менш важливий F2 і т. д. Вважатимемо, що необхідно досягти максимального значення за всіма критеріями (якщо необхідно знайти мінімум, то змінюють знак показника). Спочатку розв’язується задача з одним головним критерієм (знаходиться значення ), потім призначають деяку невелику за абсолютним значенням «поступку» , на яку можна змінити (зменшити) значення критерію задля того, щоб досягти максимального (більшого) значення за наступним критерієм F2. Величина «поступки» залежить від потрібної точності розрахунків та достовірності початкових даних. Потім до системи початкових обмежень задачі приєднують обмеження, що встановлює рівень можливого відхилення показника: , і розв’язують нову задачу з критерієм оптимальності F2 і т.д. Процес розв’язання задачі у такий спосіб показує, ціною яких «поступок» досягається бажаний результат. Очевидно, що багатокритеріальні задачі математичного програмування не мають універсального способу розв’язування. Отже, вибір та коректне застосування будь-якого з наведених способів залишається за суб’єктом прийняття рішень. Завдання математичного програмування полягає в забезпеченні потрібною кількістю науково обґрунтованої інформації, на підставі якої здійснюється вибір управлінського рішення. 1.5. Історична довідка В суто математичному плані деякі оптимізаційні задачі були відомі ще в стародавній Греції. Однак, сучасне математичне програмування передусім розглядає властивості та розв’язки математичних моделей економічних процесів. Тому початком його розвитку як самостійного наукового напрямку слід вважати перші спроби застосування методів математичного програмування в прикладних дослідженнях, насамперед в економіці. Справжнім початком математичного програмування в сучасному розумінні вважають праці радянського вченого Л. В. Канторовича. Наприкінці 30-х років у Ленінградському університеті ним уперше були сформульовані та досліджувались основні задачі, критерії оптимальності, економічна інтерпретація, методи розв’язання та геометрична інтерпретація результатів розв’язання задач лінійного програмування (1939 року Л. В. Канторович оприлюднив монографію «Математичні методи організації і планування виробництва»). Сам термін «лінійне програмування» був введений дещо пізніше, 1951 року, у працях американських вчених Дж. Данцига та Г. Кумпанса. Однак у своїй монографії Дж. Данциг зазначає, що Л. В. Канторовича слід визнати першим, хто виявив, що широке коло важливих виробничих задач може бути подане у чіткому математичному формулюванні, яке уможливлює підхід до таких задач з кількісного боку та розв’язання їх чисельними методами. 1947 року Дж. Данцигом також був розроблений основний метод розв’язування задач лінійного програмування — симплексний метод, що вважається початком формування лінійного програмування як самостійного напрямку в математичному програмуванні. Наступним кроком стали праці Дж. Неймана (1947 р.) щодо розвитку концепції двоїстості, що уможливило розширення практичної сфери застосування методів лінійного програмування. Періодом найінтенсивнішого розвитку математичного програмування є п’ятдесяті роки. У цей час з’являються розробки нових алгоритмів, теоретичні дослідження з різних напрямків математичного програмування: 1951 року — праця Г. Куна і А. Таккера, в якій наведено необхідні та достатні умови оптимальності нелінійних задач; 1954 року — Чарнес і Лемке розглянули наближений метод розв’язання задач з сепарабельним опуклим функціоналом та лінійними обмеженнями; 1955 року — ряд робіт, присвячених квадратичному програмуванню. У п’ятдесятих роках сформувався новий напрямок математичного програмування — динамічне програмування, значний вклад у розвиток якого вніс американський математик Р. Белман. На жаль, у період найбурхливішого розвитку математичного програмування за кордоном у Радянському Союзі не спостерігалося значних досягнень через штучні ідеологічні обмеження. Відродження досліджень з математичного моделювання економіки почалося в 60-80-тих роках і стосувалося опису «системи оптимального функціонування соціалістичної економіки». Серед радянських вчених того періоду слід виокремити праці В. С. Немчинова, В. В. Новожилова, Н. П. Федоренка, С. С. Шаталіна, В. М. Глушкова, В. С. Михалевича, Ю. М. Єрмольєва та ін. На сучасному етапі математичне програмування включає широке коло задач з відповідними методами розв’язання, що охоплюють різноманітні проблеми розвитку та функціонування реальних економічних систем. Розробляються банки економіко-математичних моделей, які в поєднанні з потужною, швидкодіючою обчислювальною технікою та сучасними програмними продуктами утворюватимуть системи ефективної підтримки прийняття рішень у різних галузях економіки. 1.6. Класифікація задач математичного програмування У математичному програмуванні виділяють два напрямки — детерміновані задачі і стохастичні. Детерміновані задачі не містять випадкових змінних чи параметрів. Уся початкова інформація повністю визначена. У стохастичних задачах використовується вхідна інформація, яка містить елементи невизначеності, або деякі параметри набувають значень відповідно до визначених функцій розподілу випадкових величин. Наприклад, якщо в економіко-математичній моделі врожайності сільськогосподарських культур задані своїми математичними сподіваннями, то така задача є детермінованою. Якщо ж врожайності задані функціями розподілу, наприклад нормального з математичним сподіванням а і дисперсією D, то така задача є стохастичною. Якщо у відповідних економічних процесах випадкові явища не відіграють істотної ролі, то задачу можна розв’язувати як детерміновану. У іншому разі адекватна економіко-математична модель має бути стохастичною, тобто містити випадкові функції та величини. Структура та розв’язування таких задач вивчаються в окремому розділі, який називається стохастичним програмуванням. Кожен з названих напрямків включає типи задач математичного програмування, які в свою чергу поділяються на інші класи. Схематично класифікацію задач зображено на рис. 1.2 (Поділ наведений для детермінованих задач, але він такий же і для стохастичних).
Рис. 1.2. Класифікація задач математичного програмування Як детерміновані, так і стохастичні задачі можуть бути статичними (однокроковими) або динамічними (багатокроковими). Оскільки економічні процеси розвиваються в часі, відповідні економіко-математичні моделі мають відображати їх динаміку. Поняття динамічності пов’язане зі змінами об’єкта (явища, процесу) у часі. Наприклад, якщо йдеться про план розвитку економіки України до 2005 року, то мають бути обґрунтовані значення відповідних макроекономічних показників не лише на 2005 рік, а й на всі проміжні роки, тобто слід планувати поступовість (динаміку) розвитку народногосподарських процесів. Такий план називають стратегічним. У ньому має бути обґрунтована оптимальна (найкраща, але реальна) траєкторія розвитку народного господарства. Проте під впливом некерованих чинників фактичні показники щороку можуть відхилятися від запланованих. Тому постає необхідність коригувати кожний річний план. Такі плани називають тактичними. Вони визначаються в результаті розв’язання статичної економіко-математичної задачі. Важливо чітко усвідомити відмінність між одно- та багатокроковими задачами. Багатокроковість як метод розв’язування задач математичного програмування зумовлюється, насамперед, багатовимірністю задачі й означає, що послідовно застосовуючи індукцію, крок за кроком знаходять оптимальні значення множини змінних, причому отриманий на кожному кроці розв’язок має задовольняти умови оптимальності попереднього розв’язку. Така процедура може бути більш чи менш тісно пов’язана з часом. Однокрокові задачі, навпаки, характеризуються тим, що всі компоненти оптимального плану задачі визначаються водночас на останній ітерації (останньому кроці) алгоритму. Потрібно розрізняти ітераційність алгоритму і його багатокроковість. Наприклад, симплекс-метод розв’язування задач лінійного програмування є ітераційним, тобто у певний спосіб дістають допустимий план і в результаті деякої кількості ітерацій визначають оптимальний план. Тут виконуються ітерації (кроки) алгоритму симплексного методу, але це не можна інтерпретувати як багатокроковість економічного процесу (явища). Деякі задачі математичного програмування можна розглядати як одно- або багатокрокові залежно від способу їх розв’язання. Якщо задачу можна розв’язувати як однокрокову, то розв’язувати її як багатокрокову недоцільно, бо в такому разі для знаходження оптимального плану необхідно застосовувати складніші методи. Проте більшість економічних процесів є динамічними, їх параметри змінюються в часі й залежать від рішень керівництва, які доводиться приймати з метою спрямування розвитку економічної системи за траєкторією, яка визначена стратегічним планом. Задачі математичного програмування поділяють також на дискретні і неперервні. Дискретними називають задачі, в яких одна, кілька або всі змінні набувають лише дискретних значень. З-поміж них окремий тип становлять задачі, в яких одна або кілька змінних набувають цілочислових значень. Їх називають задачами цілочислового програмування. Якщо всі змінні можуть набувати будь-яких значень на деяких інтервалах числової осі, то задача є неперервною. Оскільки в економіко-математичних моделях залежності між показниками описані за допомогою функцій, то відповідно до їх виду всі вище згадані типи задач поділяють на лінійні та нелінійні. Якщо цільова функція (1.2) та обмеження (1.3) є лінійними, тобто містять змінні xj тільки у першому або нульовому степенях, то така задача є лінійною. В усіх інших випадках задача буде нелінійною. Найпростішими з розглянутих типів є статичні, детерміновані, неперервні та лінійні задачі. Важливою перевагою таких задач є те, що для їх розв’язування розроблено універсальний метод, який називається симплексним методом. Теоретично кожну задачу лінійного програмування можна розв’язати. Для деяких типів лінійних задач, що мають особливу структуру, розробляють спеціальні методи розв’язання, які є ефективнішими. Наприклад, транспортну задачу можна розв’язати симплексним методом, але ефективнішими є спеціальні методи, наприклад, метод потенціалів. Економічні та технологічні процеси, як правило, є нелінійними, стохастичними, розвиваються за умов невизначеності. Лінійні економіко-математичні моделі часто є неадекватними, тобто такими, що неточно описують процес, який досліджується, тому доводиться будувати стохастичні, динамічні, нелінійні моделі. Розв’язувати такі задачі набагато складніше, ніж лінійні, оскільки немає універсального методу їх розв’язання. Для окремих типів нелінійних задач розроблено спеціальні числові методи розв’язання. Проте слід зазначити, що на практиці застосовують, здебільшого, лінійні економіко-математичні моделі. Часто нелінійні залежності апроксимують (наближають) до лінійних. Такий підхід є доволі ефективним. У нелінійному програмуванні (залежно від функцій, які використовуються в економіко-математичній моделі) виокремлюють опукле та квадратичне програмування. Задача належить до опуклого програмування у тому разі, коли цільова функція вгнута, якщо вона мінімізується, та опукла, якщо вона максимізується, а всі обмеження — однотипні нерівності типу (?) або рівняння, в яких ліві частини є опуклими функціями, а праві частини — сталими величинами. У разі обмежень типу (?) їх ліві частини мають бути вгнутими функціями. Тоді область допустимих планів є опуклою та існує глобальний, єдиний екстремум. Квадратичне програмування — якщо цільова функція квадратична, а обмеження лінійні. Щойно було розглянуто лише основні типи задач математичного програмування. Можна також за різними ознаками виокремити й інші підтипи. Це особливо стосується задач лінійного, нелінійного і стохастичного програмування. Наприклад, як окремий тип розглядають дробово-лінійне програмування, коли обмеження є лінійними, а цільова функція — дробово-лінійна. Особливий тип становлять задачі теорії ігор, які широко застосовуються в ринковій економіці. Адже тут діють дві чи більше конфліктних сторін, які мають частково або повністю протилежні цілі. У сукупності задач теорії ігор, у свою чергу, також виокремлюють певні підтипи. Наприклад, ігри двох осіб із нульовою сумою. Наведена вище класифікація задач використана для структурування курсу «Математичне програмування». 1.7. Приклади економічних задач математичного програмування Складність економічних систем (явищ, процесів) як об’єктів досліджень вимагає їх ретельного вивчення з метою з’ясування найважливіших функціональних залежностей, внутрішніх взаємозв’язків між їхніми елементами. В результаті здійснюються можливі спрощення та допущення, що, очевидно, погіршує адекватність побудованих математичних моделей і є чудовим приводом для критики. Однак лише прийняття певних допущень уможливлює формалізацію будь-якої економічної ситуації. Не існує загальних рекомендацій щодо процесу моделювання, тому в кожному конкретному разі вимоги до побудови математичної моделі залежать від цілей та умов досліджуваної системи. У процесі застосування математичного моделювання в економіці чітка постановка задачі та її формалізація є найскладнішим етапом дослідження, вимагає ґрунтовних знань передусім економічної суті процесів, які моделюються. Однак, вдало створена математична модель може надалі застосовуватись для розв’язування інших задач, які не мають відношення до ситуації, що початково моделювалася. Починаючи з робіт Л. В. Канторовича, в математичному програмуванні сформовано певний набір класичних постановок задач, економіко-математичні моделі яких широко використовуються в практичних дослідженнях економічних проблем. Наведемо кілька вже формалізованих типових постановок економічних задач, що розв’язуються методами математичного програмування (більшість сформульованих задач будуть вивчатися в наступних розділах). Всі розглянуті задачі залежно від наявності та точності початкової інформації, мети дослідження, ступеня врахування невизначеності, специфіки застосування до конкретного процесу можуть бути сформульовані як у вигляді статичних, детермінованих, неперервних лінійних задач, так і в складнішій постановці, де один, кілька чи всі параметри визначаються з певним рівнем імовірності та використовуються нелінійні залежності. Задача визначення оптимального плану виробництва: для деякої виробничої системи (цеху, підприємства, галузі) необхідно визначити план випуску кожного виду продукції за умови найкращого способу використання наявних ресурсів. У процесі виробництва задіяний визначений набір ресурсів: сировина, трудові ресурси, технічне обладнання тощо. Відомі загальні запаси ресурсів, норми витрат кожного ресурсу та прибуток з одиниці реалізованої продукції. Задаються також за потреби обмеження на обсяги виробництва продукції у певних співвідношеннях(задана асортиментність). Критерії оптимальності: максимум прибутку, максимум товарної продукції, мінімум витрат ресурсів. Задача про «дієту» (або про суміш): деякий раціон складається з кількох видів продуктів. Відомі вартість одиниці кожного компонента, кількість необхідних організму поживних речовин та потреба в кожній речовині, вміст в одиниці кожного продукту кожної поживної речовини. Необхідно знайти оптимальний раціон — кількість кожного виду продукту, що враховує вимоги забезпечення організму необхідною кількістю поживних речовин. Критерій оптимальності — мінімальна вартість раціону. Транспортна задача: розглядається певна кількість пунктів виробництва та споживання деякої однорідної продукції (кількість пунктів виробництва та споживання не збігається). Відомі обсяги виготовленої продукції в кожному пункті виробництва та потреби кожного пункту споживання. Також задана матриця, елементи якої є вартістю транспортування одиниці продукції з кожного пункту виробництва до кожного пункту споживання. Необхідно визначити оптимальні обсяги перевезень продукції, за яких були б найкраще враховані необхідності вивезення продукції від виробників та забезпечення вимог споживачів. Критерії оптимальності: мінімальна сумарна вартість перевезень, мінімальні сумарні витрати часу. Задача оптимального розподілу виробничих потужностей: розглядаються кілька підприємств, що виготовляють певну кількість видів продукції. Відомі фонд робочого часу кожного підприємства; потреби в продукції кожного виду; матриця потужностей виробництва всіх видів продукції, що виготовляються на кожному підприємстві, а також собівартості виробництва одиниці продукції кожного підприємства. Необхідно розподілити виробництво продукції між підприємствами у такий спосіб, щоб задовольнити потреби у виготовленні продукції та максимально використати виробничі потужності підприємств. Критерій оптимальності: мінімальні сумарні витрати на виготовлення продукції. Задача про призначення: нехай набір деяких видів робіт може виконувати певна чисельність кандидатів, причому кожного кандидата можна призначати лише на одну роботу і кожна робота може бути виконана тільки одним кандидатом. Відома матриця, елементами якої є ефективності (у вибраних одиницях) кожного претендента на кожній роботі. Розв’язком задачі є оптимальний розподіл кандидатів на посади. Критерій оптимальності: максимальний сумарний ефект від виконання робіт. Задача комівояжера: розглядається кілька міст. Комівояжеру необхідно, починаючи з міста, в якому він перебуває, обійти, не буваючи ніде двічі, всі міста і повернутися в початкове. Відома матриця, елементи якої — вартості пересування (чи відстані) між всіма попарно пунктами подорожі. Знайти оптимальний маршрут. Критерій оптимальності: мінімальна сумарна вартість (відстань) пересування по маршруту. Задача оптимального розподілу капіталовкладень. Планується діяльність групи (системи) підприємств протягом деякого періоду, який розділено на певну кількість підперіодів. Задана сума коштів, які можна вкладати в будь-яке підприємство чи розподіляти між ними протягом всього періоду планування. Відомі величини збільшення виробництва продукції (за умови здійснення додаткових капіталовкладень) у кожному з підприємств групи для всіх підперіодів. Необхідно визначити, як розподіляти кошти на початку кожного підперіоду між підприємствами так, щоб сумарний дохід за весь період був максимальним.
