Учебное пособие: Математичне програмування в економіці

Учебное пособие: Математичне програмування в економіці

Математичне програмування

Тема 1. Предмет, особливості та сфери застосування математичного програмування в економіці. Класифікація задач

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

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

-           формується економічна проблема;

-           створюється математична модель задачі, у якій логічні зв’язки економічної модел перетворюються на математичні співвідношення: функції. рівняння, нерівності;

-           розв’язується математична задача, перевіряється рішення;

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

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

У загальному вигляді математична формулювання задачі виглядає таким чином:

-           необхідно знайти найбільше або найменше значення цільової функції f (x1, x2, x3…, xn);

-           якщо треба виконати умови gi (x1, x2, x3…, xn) £ bi, i = 1,2,3…,m;

-           де: f, gi – відомі функції,

bi - деякі дійсні числа, n > m.

Задачу оптимізації з точки зору економіки можна сформулювати таким чином:

-           знайти такі значення змінних. що надають ефективності діяльності максимальне чи мінімальне значення;

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

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

Обмеження відображають умови, при розв’язанні економічної задачі, наприклад, брак ресурсів, гранична вартість таке інше. Змінні, з яких будується цільова функція, та на які накладаються обмеження, використовують як “інструмент”, за допомогою якого досягається той чи інший варіант цілі. Як змінні задовольняють усім обмеженням, так отриманий варіант називають припустимим (допустимим).

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

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

Функція цілі (критерій оптимальності) повинна об’єктивно характеризувати суспільно-корисну значущість соціально-економічного явища або процесу. Критерій оптимальност можливо з’ясувати лише з економічної сутності проблеми – задача, яку розв’язу фахівець економіст. Принципово неможливо визначити цільову функцію на етап розв’язання задачі математиком. такою ж мірою це все стосується також обмежень задачі оптимізації.

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

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

Якщо у математичній моделі ураховується поетапно час, така задача має назву задачі динамічного програмування; у іншому випадку – задачі статичного програмування.

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

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

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

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

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

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

Приклад 1. Задача про планування випуску продукції малого підприємства.

Планується виробляти жіночі та чоловічі костюми. На жіночій костюм потрібно 1 м. шерсті, 2 м. шовку та 1 людино-тиждень працевитрат. На чоловічий костюм потрібно 3,5 м. шерсті, 0,5 м. шовку і також 1 людино-тиждень працевитрат. Загалом підприємство має 350 м. шерсті, 240 м. шовку та 150 людино-тижнів працевитрат. За попередньою домовленістю із замовником мають виробити 110 костюмів жіночих та чоловічих загалом. Акціонери, які вклали гроші у підприємство та сировину (тканину), вимагають прибуток не менше, ніж 1400 грн. Замовник купує жіночий костюм на 10 грн. дорожче собівартості, чоловічий – на 20 грн. Потрібно з’ясувати: скільки необхідно виготовити жіночих та чоловічих костюмів, щоб задовольнити усім вимогам та отримати найбільший прибуток.

Розв’язок задачі: Позначимо кількість жіночих костюмів, які потрібно виготовити, через х1; кількість чоловічих – х2. Загальний прибуток (критерій оптимізації, мета, ціль) виробництва складає:

Z = f (x) = 10 x1 + 20 x2 ;

витрати: шерсті = 1 ´ х1 + 3,5 ´ х2;

шовку = 2 ´ х1 + 0,5 ´ х2;

трудомісткості = х1 + х2;

результати: кількість загальна костюмів х1 + х2;

прибуток 10 x1 + 20 x2.

Функціональні обмеження задачі мають вигляд:

х1 + 3,5 х2 £ 350;

2 х1 + 0.5 х2 £ 240; обмеження ресурсів

х1 + х2 £ 150;

х1 + х2 ³ 110; обмеження планового завдання

10 х1 + 20 х2 ³ 1400;

Нефункціональн обмеження вочевидь складають:

х1 ³ 0;

х2 ³ 0.

Розв’язок задач математичного програмування у даному прикладі складає: х1 = 70; х2 = 80; f (x)max = 2300 грн.

Приклад 2. Задача про постачання вантажів від постачальників до замовників.

Від трьох постачальників, розташованих у пунктах А1, А2, А3 до чотирьох замовників, розташованих у пунктах В1, В2, В3, В4, треба перевезти однорідний вантаж. Наявність вантажу по пунктах постачальників: А1= 50т, А2 = 40 т, А3 = 20т. Потреба у вантажі: В1 = 30т, В2 = 25т, В3 = 35т, В4 = 20т. Відстані між пунктами замовників та постачальників наведені у таблиці.

Таблиця

Розв’язок задачі. Позначимо xij – кількість вантажу. який буде перевезено з “i”–ого пункта постачання у “j”–ий пункт замовлення; cij відстань від “i”-ого постачальника до “j”-ого замовника. Мета: розшукати вартість перевезення вантажів з найменшою витратою транспортного моменту.

Z = f (x) = S S Cij ´ Xij

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

S Xij = аі, і = 1, 2, 3; - умова вивезення вантажу від кожного з трьох постачальників до 4 замовників;

S Xij = вj; j – 1, 2, 3, 4; - умова отримання кожним замовником необхідної кількості вантажу.

Нефункціональн обмеження: хij ³ 0.

Розв’язок задач складає:

х11 = 25; х12 = 5; х14 = 20; х13 = 0;

х21 = 5; х23 = 35; х22 = 0; х24 = 0;

х31 = 20; х32 = 0; х33 = 0; х34 = 0;

f (x)min = 190т.км.

Приклад 3. Задача про раціональний розкрій.

Підприємство одержує прут сталевого прокату довжиною l = 800 см. Треба виготовити детал трьох (і) різновидів: l1 = 250 см, а1 = 150 штук; l2 = 190 см, а2 = 140 штук; l3 = 100 см, а3 = 4