Задачі математичного програмування

Задачі теорії

ігор

Детерміновані Стохастичні

Статичні Динамічні

Неперервні Дискретні Неперервні Дискретні

Лінійні

Лінійні

Лінійні

Лінійні

Нелінійні

Нелінійні

Нелінійні

Нелінійні

Рисунок 2.2 – Класифікація задач математичного програмування

Як детерміновані, так і стохастичні задачі можуть бути статичними (однокроковими) або

динамічними (багатокроковими). Оскільки економічні процеси розвиваються в часі, відповідні еко-

номіко-математичні моделі мають відображати їх динаміку. Поняття динамічності пов’язане зі змі-

нами об’єкта (явища, процесу) у часі. Наприклад, якщо йдеться про план розвитку економіки України

до 2005 року, то мають бути обґрунтовані значення відповідних макроекономічних показників не

лише на 2005 рік, а й на всі проміжні роки, тобто слід планувати поступовість (динаміку) розвитку

народногосподарських процесів. Такий план називають стратегічним. У ньому має бути обґрунто-

вана оптимальна (найкраща, але реальна) траєкторія розвитку народного господарства. Проте під

впливом некерованих чинників фактичні показники щороку можуть відхилятися від запланованих.

Тому постає необхідність коригувати кожний річний план. Такі плани називають тактичними. Во-

ни визначаються в результаті розв’язання статичної економіко-математичної задачі.

Важливо чітко усвідомити відмінність між одно- та багатокроковими задачами. Багатокроко-

вість як метод розв’язування задач математичного програмування зумовлюється, насамперед, багато-

вимірністю задачі й означає, що послідовно застосовуючи індукцію, крок за кроком знаходять опти-

мальні значення множини змінних, причому отриманий на кожному кроці розв’язок має задовольня-

ти умови оптимальності попереднього розв’язку. Така процедура може бути більш чи менш тісно

пов’язана з часом. Однокрокові задачі, навпаки, характеризуються тим, що всі компоненти оптима-

льного плану задачі визначаються водночас на останній ітерації (останньому кроці) алгоритму. Пот-

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

розв’язування задач лінійного програмування є ітераційним, тобто у певний спосіб дістають допус-

тимий план і в результаті деякої кількості ітерацій визначають оптимальний план. Тут виконуються

ітерації (кроки) алгоритму симплексного методу, але це не можна інтерпретувати як багатокроко-

вість економічного процесу (явища). Деякі задачі математичного програмування можна розглядати

як одно- або багатокрокові залежно від способу їх розв’язання. Якщо задачу можна розв’язувати як

однокрокову, то розв’язувати її як багатокрокову недоцільно, бо в такому разі для знаходження оп-

тимального плану необхідно застосовувати складніші методи. Проте більшість економічних процесів

є динамічними, їх параметри змінюються в часі й залежать від рішень керівництва, які доводиться

приймати з метою спрямування розвитку економічної системи за траєкторією, яка визначена страте-

гічним планом.

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

ними називають задачі, в яких одна, кілька або всі змінні набувають лише дискретних значень. З-

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

значень. Їх називають задачами цілочислового програмування. Якщо всі змінні можуть набувати

будь-яких значень на деяких інтервалах числової осі, то задача є неперервною.

Оскільки в економіко-математичних моделях залежності між показниками описані за допомо-

гою функцій, то відповідно до їх виду всі вище згадані типи задач поділяють на лінійні та нелінійні.

Якщо цільова функція (2.2) та обмеження (2.3) є лінійними, тобто містять змінні xj тільки у першому

або нульовому степенях, то така задача є лінійною. В усіх інших випадках задача буде нелінійною.

Найпростішими з розглянутих типів є статичні, детерміновані, неперервні та лінійні задачі. Ва-

жливою перевагою таких задач є те, що для їх розв’язування розроблено універсальний метод, який

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

розв’язати. Для деяких типів лінійних задач, що мають особливу структуру, розробляють спеціальні

методи розв’язання, які є ефективнішими. Наприклад, транспортну задачу можна розв’язати симплекс-

ним методом, але ефективнішими є спеціальні методи, наприклад, метод потенціалів.

Економічні та технологічні процеси, як правило, є нелінійними, стохастичними, розвиваються

за умов невизначеності. Лінійні економіко-математичні моделі часто є неадекватними, тобто такими,

що неточно описують процес, який досліджується, тому доводиться будувати стохастичні, динамічні,

нелінійні моделі. Розв’язувати такі задачі набагато складніше, ніж лінійні, оскільки немає універса-

льного методу їх розв’язання. Для окремих типів нелінійних задач розроблено спеціальні числові ме-

тоди розв’язання. Проте слід зазначити, що на практиці застосовують, здебільшого, лінійні економі-

ко-математичні моделі. Часто нелінійні залежності апроксимують (наближають) до лінійних. Такий

підхід є доволі ефективним.

У нелінійному програмуванні (залежно від функцій, які використовуються в економіко-

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

опуклого програмування у тому разі, коли цільова функція угнута, якщо вона мінімізується, та опу-

кла, якщо вона максимізується, а всі обмеження – однотипні нерівності типу (≤) або рівняння, в яких

ліві частини є опуклими функціями, а праві частини – сталими величинами. У разі обмежень типу (≥)

їх ліві частини мають бути вгнутими функціями. Тоді область допустимих планів є опуклою та існує

глобальний, єдиний екстремум. Квадратичне програмування – якщо цільова функція квадратична, а

обмеження лінійні.

Щойно було розглянуто лише основні типи задач математичного програмування. Можна та-

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

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

програмування, коли обмеження є лінійними, а цільова функція – дробово-лінійна. Особливий тип

становлять задачі теорії ігор, які широко застосовуються в ринковій економіці. Адже тут діють дві

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

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

сумою.

2.2 Приклади задач економіко-математичного моделювання (самостійна робота)

Складність економічних систем (явищ, процесів) як об’єктів досліджень вимагає їх ретельного

вивчення з метою з’ясування найважливіших функціональних залежностей, внутрішніх взає-

мозв’язків між їхніми елементами. В результаті здійснюються можливі спрощення та допущення, що,

очевидно, погіршує адекватність побудованих математичних моделей і є чудовим приводом для кри-

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

туації.

Не існує загальних рекомендацій щодо процесу моделювання, тому в кожному конкретному

разі вимоги до побудови математичної моделі залежать від цілей та умов досліджуваної системи.

У процесі застосування математичного моделювання в економіці чітка постановка задачі та її

формалізація є найскладнішим етапом дослідження, вимагає ґрунтовних знань передусім економічної

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

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

Починаючи з робіт Л.В.Канторовича, в математичному програмуванні сформовано певний набір класи-

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

дослідженнях економічних проблем.

Наведемо кілька вже формалізованих типових постановок економічних задач, що

розв’язуються методами математичного програмування (більшість сформульованих задач будуть ви-

вчатися далі).

Всі розглянуті задачі залежно від наявності та точності початкової інформації, мети дослі-

дження, ступеня врахування невизначеності, специфіки застосування до конкретного процесу мо-

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

в складнішій постановці, де один, кілька чи всі параметри визначаються з певним рівнем імовірності

та використовуються нелінійні залежності.

Задача визначення оптимального плану виробництва: для деякої виробничої системи (цеху,

підприємства, галузі) необхідно визначити план випуску кожного виду продукції за умови найкращо-

го способу використання наявних ресурсів. У процесі виробництва задіяний визначений набір ресур-

сів: сировина, трудові ресурси, технічне обладнання тощо. Відомі загальні запаси ресурсів, норми

витрат кожного ресурсу та прибуток з одиниці реалізованої продукції. Задаються також за потреби

обмеження на обсяги виробництва продукції у певних співвідношеннях(задана асортиментність).

Критерії оптимальності: максимум прибутку, максимум товарної продукції, мінімум витрат

ресурсів.

Задача про «дієту» (або про суміш): деякий раціон складається з кількох видів продуктів.

Відомі вартість одиниці кожного компонента, кількість необхідних організму поживних речовин та

потреба в кожній речовині, вміст в одиниці кожного продукту кожної поживної речовини. Необ-

хідно знайти оптимальний раціон – кількість кожного виду продукту, що враховує вимоги забезпе-

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

Критерій оптимальності — мінімальна вартість раціону.

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

якої однорідної продукції (кількість пунктів виробництва та споживання не збігається). Відомі обсяги

виготовленої продукції в кожному пункті виробництва та потреби кожного пункту споживання. Та-

кож задана матриця, елементи якої є вартістю транспортування одиниці продукції з кожного пункту

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

продукції, за яких були б найкраще враховані необхідності вивезення продукції від виробників та за-

безпечення вимог споживачів.

Критерії оптимальності: мінімальна сумарна вартість перевезень, мінімальні сумарні витрати

часу.

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

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

ємства; потреби в продукції кожного виду; матриця потужностей виробництва всіх видів продукції,

що виготовляються на кожному підприємстві, а також собівартості виробництва одиниці продукції

кожного підприємства. Необхідно розподілити виробництво продукції між підприємствами у такий

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

потужності підприємств.

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

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

кандидатів, причому кожного кандидата можна призначати лише на одну роботу і кожна робота мо-

же бути виконана тільки одним кандидатом. Відома матриця, елементами якої є ефективності (у виб-

раних одиницях) кожного претендента на кожній роботі. Розв’язком задачі є оптимальний розподіл

кандидатів на посади.

Критерій оптимальності: максимальний сумарний ефект від виконання робіт.

Задача комівояжера: розглядається кілька міст. Комівояжеру необхідно, починаючи з міста,

в якому він перебуває, обійти, не буваючи ніде двічі, всі міста і повернутися в початкове. Відома

матриця, елементи якої – вартості пересування (чи відстані) між всіма попарно пунктами подорожі.

Знайти оптимальний маршрут.

Критерій оптимальності: мінімальна сумарна вартість (відстань) пересування по маршруту.

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

підприємств протягом деякого періоду, який розділено на певну кількість підперіодів. Задана сума

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

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

даткових капіталовкладень) у кожному з підприємств групи для всіх підперіодів. Необхідно ви-

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

рний дохід за весь період був максимальним.

Наведемо кілька розглянутих вище типових задач математичного програмування, сформульо-

ваних у термінах лінійного програмування.

2.2.1 Задача визначення оптимального плану виробництва

Для деякої виробничої системи (цеху, підприємства, галузі) необхідно визначити план випус-

ку n видів продукції Х = (х 1, х 2, …, х n) за умови найкращого способу використання її наявних ресур-

сів. У процесі виробництва задіяні m ресурсів: сировина, трудові ресурси, технічне оснащення тощо.

Відомі загальні запаси ресурсів bi (i =1, m), норми витрат і -го ресурсу на виробництво одиниці j -ої

продукції aij (i = 1, m; j = 1, n) та прибуток з одиниці j -ої реалізованої продукції c j (j = 1, n).

Критерій оптимальності: максимум прибутку.

Позначимо через х 1, х 2, …, х n обсяги виробництва відповідно першого, другого і т. д. видів

продукції.

Оскільки на одиницю продукції 1-го виду витрачається 11 a ресурсу першого виду, то на виро-

бництво першого виду продукції обсягом х 1 необхідно витратити а 11 х 1 цього ресурсу. На другий вид

продукції обсягом х 2 витрати першого ресурсу дорівнюватимуть а 12 х 2 і т. д. На виробництво всіх ви-

дів продукції буде використано такий обсяг першого ресурсу: а 11 х 1 + а 12 х 2 + … + а 1 nxn. Ця величина

має не перевищувати наявного обсягу першого ресурсу — b 1. Отже, обмеження щодо використання

першого ресурсу матиме вигляд: а 11 х 1 + а 12 х 2 + … + а 1 nxn ≤ b 1. Аналогічно записують обмеження сто-

совно використання всіх інших виробничих ресурсів. Прибуток від реалізації виготовленої продукції

всіх видів становитиме: с 1 х 1 + с 2 х 2 + … + сnxn.

Загалом лінійна економіко-математична модель даної задачі матиме вигляд:

max F = c 1 x 1 + c 2 x 2 +... + cn xn

за умов:

ï ï ï

î

ï ï ï

í

ì

+ + + £

+ + + £

+ + + £

+ + + £

....

..........................................

...;

...;

...;

1 1 2 2

31 1 32 2 3 3

21 1 22 2 2 2

11 1 12 2 1 1

m m mn n m

n n

n n

n n

a x a x a x b

a x a x a x b

a x a x a x b

a x a x a x b

1 0, 2 0,..., 0 ³ ³ ³ x x xn.

Математична модель виробничої задачі може бути застосована для різних економічних задач,

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

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

мо кілька конкретних прикладів виробничих задач.

Приклад 2.2. Фірма має 1 млн.грн. обігових коштів. Відомі витрати грошей у кожному місяці,

а також обов’язкові залишки обігових коштів на кінець кожного місяця. Також передбачається, що

для успішного функціонування фірма витрачатиме значно меншу суму, ніж 1 млн.грн. Отже, решту

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

тягом кварталу для досягнення максимального прибутку за процентними ставками, якщо відомі ви-

трати та потреби в резервах:

1.01 – 31.01: витрати — 80 000 грн; необхідний запас на 31.01 – 300000 грн;

1.02 – 28.02: витрати — 30 000 грн; необхідний запас на 28.02 – 200 000 грн;

1.03 – 31.03: витрати — 50 000 грн; необхідний запас на 31.03 – 190 000 грн.

Кредит терміном на 1 місяць дає 2% прибутку, терміном на 2 місяці – 5%, а терміном на 3 мі-

сяці – 8%.

Вважатимемо, що кредити надаються першого числа кожного місяця і погашаються також

першого числа відповідного місяця.

Побудова економіко-математичної моделі.

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

позначимо через х 11 суму кредиту, що надано на один місяць з 1.01, аналогічно х 12, х 13 – суми одномі-

сячних кредитів, що надані відповідно в другому та у третьому місяцях.

Кредити терміном на два місяці протягом першого кварталу можна надавати лише в першому

і другому місяцях, тому позначимо через х 21 суму кредиту, що надано на два місяці в січні, х 22 – суму

кредиту, що надана в лютому на два місяці. Нарешті, кредит на три місяці можна надати лише один

раз із 1.01, його позначимо через х 31.

Розглянемо ситуацію на початку першого місяця кварталу: початкова сума 1млн грн витрача-

тиметься на вкладення коштів у всі види кредитів, потреби в обігових коштах для господарської дія-

льності фірми становитимуть 80 000 грн, а на кінець місяця фірма бажає мати резерв обсягом 300 000

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

1000 000 - x 11 - x 21 - x 31 - 80 000 ³ 300 000.

Наявні кошти в кінці місяця (окрім резерву) визначаються за формулою:

620 000 ().

1 1000 000 () 80 000 300 000

11 21 31

11 21 31

x x x

S x x x

= - + +

= - + + - - =

На початку другого місяця сума S 1 може надаватися в кредит, але лише двох видів та має за-

безпечувати витрати діяльності. Одночасно на початку другого місяця повертаються кошти, що є

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

кінець другого місяця, маємо таке обмеження щодо використання коштів у лютому:

S 1- x 12 - x 22 +1,02 x 11 - 30000 ³ 200000,

а наприкінці лютого обсяг наявних коштів становитиме:

S 2 = S 1 - (x 12 + x 22) + 1,02 x 11 - 230 000.

Аналогічно запишемо використання коштів у березні:

S 2 - x 13 + 1,02 x 12 + 1,05 x 21 - 50000 ³190000.

Загальна сума коштів, отриманих як проценти за надані кредити, дорівнюватиме:

P = 0,02(x 11 + x 12 + x 13) + 0,05(x 21 + x 22) + 0,08 x 31.

Загалом математична модель цієї задачі має вигляд:

max P = 0,02(x 11 + x 12 + x 13) + 0,05(x 21 + x 22) + 0,08 x 31

за умов:

ïî

ïí

ì

- + + - ³

- - + - ³

- - - - ³

2 1,02 1,05 50 000 190 000.

1 1,02 30 000 200 000;

1000 000 80 000 300 000;

13 12 21

12 22 11

11 21 31

S x x x

S x x x

x x x

xij ³ 0(i =1,3),(j =1,3).

Приклад 2.3. На ринок поставляється картопля з трьох фермерських господарств за цінами

відповідно 80, 75 та 65 коп. за 1 кг. На завантаження 1 т картоплі в господарствах відповідно витра-

чається по 1, 6 та 5 хвилин. Замовлено 12 т картоплі, і для своєчасної доставки необхідно, щоб на її

завантаження витрачалося не більше сорока хвилин. Потрібно визначити, з яких фермерських госпо-

дарств і в якій кількості необхідно доставляти картоплю, щоб загальна вартість закупівлі була міні-

мальною, якщо фермери можуть виділити для продажу відповідно 10, 8 та 6 т картоплі.