 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Тема 8. Модель Витрати-Випуск
|
|
Побудова моделі міжгалузевого балансу. Однофакторна модель. Двофакторна модель. Багатофакторна модель.
Таблиця міжгалузевого балансу і її використання.
Тема 9. Сучасні тенденції у розвитку засобів економіко-математичного моделювання
1. Загальні теоретичні відомості
1.1 Моделювання економічних процесів
Важливим фактором, що визначає роль математики в різних галузях, є можливість опису найбільш істотних рис і властивостей досліджуваного об'єкта мовою математичних символів і співвідношень. Такий опис прийнятий називати математичним моделюванням або формалізацією.
Математичною моделлю реального об'єкта (явища) називається її спрощена, ідеалізована схема, складена за допомогою математичних символів і операцій (співвідношень).
Складність економічних систем перевищує поріг, до якого будується точна математична теорія. Тому універсальних методів побудови математичних моделей в економіці не існує. Можна говорити лише про деякі загальні принципи й вимоги до таких моделей. Перелічимо найбільш основні з них:
- адекватність (відповідність моделі своєму оригіналу);
- об'єктивність (відповідність наукових висновків реальним умовам);
- простота (не засміченість моделі другорядними факторами);
- чутливість (здатність моделі реагувати на зміні початкових параметрів);
- стабільність (малому збурюванню вихідних параметрів повинне відповідати мала зміна рішення завдання);
- універсальність (широта області застосування).
При створенні моделі перевага надається найважливішим факторам. Під найважливішими розуміються фактори, які відіграють істотну роль у задачі і які так, чи інакше впливають на кінцевий результат. Керованими називаються ті параметри задачі, яким можна надавати довільні числові значення, виходячи з умов задачі; некерованими вважаються ті параметри, значення яких зафіксоване й не підлягає зміні.
З погляду призначення, можна виділити описові моделі, імітаційні моделі й моделі прийняття рішення. Описові моделі відображають утримування й основні властивості економічних об'єктів як таких. З їхньою допомогою обчислюються числові значення економічних факторів і показників.
Імітаційні моделі використовуються при дослідженні економічних процесів методом імітації його поведінки. Під імітацією прийнято розуміти дослідження об’єктів, процесів або явищ шляхом проведення експериментів з економіко-математичними моделями ціх обїектів, які реалізовані за допомогою комп’ютерних програм. Дослідження проводяться за наступною схемою. Створюється економіко-математична модель залежності результатів від вхідних даних. При проведені дослідження варіюють вихідними даними і вивчають результати.
Моделі прийняття рішення допомагають знайти найкращі варіанти планових показників або управлінських рішень. Серед них найменш складним є оптимізаційні моделі, за допомогою яких описуються (моделюються) задачі типу планування, а найбільш складними - ігрові моделі, що описують задачі конфліктного характеру з урахуванням перетинання різних інтересів. Ці моделі відрізняються від описових тім, що в них є можливість вибору значень керуючих параметрів (чого немає в описових моделях).
У математичній економіці важко переоцінити роль моделей прийняття рішення. Найбільш часте застосування знаходять ті з них, які зводять вихідні завдання оптимального планування виробництва, раціонального розподілу обмежених ресурсів і ефективної діяльності економічних суб'єктів до екстремальних завдань, до завдань оптимального керування й до ігрових завдань.
Припустимо, що безліч усіх припустимих рішень (альтернатив, стратегій) кожної особи, яка приймає рішення (ОПР), попередньо вивчене й описане математично (наприклад, у вигляді системи нерівностей). Позначимо їх через X1, X2,..., Xn. Після цього процес ухвалення рішення всіма ОПР зводиться до наступного формального акту: кожна ОПР вибирає конкретний елемент зі своєї припустимої безлічі рішень х1ÎХ1, х2ÎХ2,…, хnÎХn. У результаті виходить набір х =(х1,...,хn) обраних рішень, що будемо називати ситуацією.
Для оцінки ситуації х з погляду переслідуваних цілей ОПР будуються функції f1,..., fn (які звуться цільовими функціями або критеріями якості), що ставлять у відповідність кожної ситуації х числові оцінки f1(x),..., fn(x) (наприклад, доходи фірм у ситуації х, або їхньої витрати й т.д.). Тоді ціль i -го ОПР формалізується в такий спосіб: вибрати таке своє рішення хiÎХi, щоб у ситуації х =(х1,...,хn) число fi(х) було як можна більшим (або меншим). Однак досягнення цієї мети від нього залежить частково у виді наявності інших сторін, що впливають на загальну ситуацію x із метою досягнення своїх власних цілей. Цей факт перетинання інтересів (конфліктність) відображається в тім, що функція fi крім xi залежить і від інших змінних xj (j 
i). Тому в моделях ухвалення рішення з багатьма учасниками їхньої мети доводиться формалізувати інакше, чим максимізація або мінімізація значень функції fi(х).
Нарешті, нехай нам удалося математично описати всі ті умови, при яких відбувається ухвалення рішення. (опис зв'язків між керованими і некерованими змінними, опис впливу випадкових факторів, облік динамічних характеристик і т.д.). Сукупність усіх цих умов для простоти позначимо одним символом S.
Таким чином, загальна схема завдання ухвалення рішення може виглядати так:
< N; X1, …, Xn; f1(x),…, fn(x); å >. (1.1.1)
Конкретизуючи елементи моделі (1.1.1), уточнюючи їхні характеристики й властивості, можна получить той або інший конкретний клас моделей прийняття рішення. Так, якщо в (1.1.1) N складається тільки з одного елемента (n=1), а всі умови й передумови вихідного реального завдання можна описати у вигляді безлічі припустимих рішень цьєї єдиної ОПР, то з (1.1.1) одержуємо структуру оптимізаційної (екстремальної) задачі: < Х, f >. У цій схемі ОПР може розглядатися як плануючий орган. В загальному вигляді проблема керування виглядає так:
Треба знайти максимум (мінімум) функції
f(x1, x2, …, xn) - показник якості рішення задачі
при обмеженнях
æ gi (x1, x2, …, xn) £ 0, i = 1, 2, …, m
í
è xj ³ 0, j = 1, 2, …, t £ n
де: xj - параметри управління, які по своєму змісту не можуть мати відємне значення. Серед обмежень задачі можуть бути і рівняння. До такої форми задач приводить аналіз різноманітних задач світогосподарських процесів. Методи пошуку рішення задачі залежать від виду функції f(x) і обмежень gi(x1, x2, …, xn). Якщо цільова функція (показник якості) і обмеження мають лінійну залежність, то такі задачі є задачами лінійного програмування (ЗЛП). В іншому випадку – не лінейного. Якщо змінні приймають тільке цілочисельні значення, то такі задачі є задачами цілочисленого програмування. Якщо кожне наступне значення цільової функції залежить від попереднього, то такі задачі є задачами динамічного програмування.
Якщо в екстремальному завданні явно враховується фактор часу, то вона називається завданням оптимального керування.
Якщо в (1.1.1) N ³ 2, то (1.1.1) є загальною схемою завдання ухвалення рішення в умовах конфлікту, тобто в тих ситуаціях, коли має місце перетинання інтересів двох або більшої кількісті сторін.
1.2 Створення економіко-математичної моделі
Для побудови математичної моделі конкретного економічного завдання (проблеми) рекомендується виконання наступних етапів робіт:
1) визначення відомих і невідомих величин, а також існуючих умов і передумов (що дано й що потрібно знайти?);
2) виявлення найважливіших факторів проблеми;
3) виявлення керованих і некерованих параметрів;
4) побудова емпіричних формул економіко-математичної моделі, математичний опис за допомогою рівнянь, нерівностей, функцій і інших відносин взаємозв'язків між елементами моделі (параметрами, змінними), з дотримуванням умов розглянутого завдання.
Відомі параметри завдання щодо її математичної моделі вважаються зовнішніми (заданими апріорі, тобто до побудови моделі). В економічній літературі їх називають екзогенними змінними. Значення ж споконвічно невідомих змінних обчислюються в результаті дослідження моделі, тому стосовно моделі вони вважаються внутрішніми. В економічній літературі їх називають ендогенними змінними.
Приклади типових економічних задач і створення економіко-матиматичної моделі. Існує багато прикладів типових економічних задач, які мають специфічні моделі. Де які приклади таких задач наведені нижче.
Задача оптимального розкрою матеріалу. Фірма виготовляє виріб, який складається з р деталей. Причому в один виріб ці деталі входять у кількостях k1,..., kr. Із цією метою провадиться розкрій m партій матеріалу. В i-й партії є bi одиниць матеріалу. Кожну одиницю матеріалу можна розкроїти на деталі n способами. При розкрої одиниці i-й партії j-м способом виходить аijr деталей r-го виду.
Потрібно скласти такий план розкрою матеріалу, щоб з них одержати максимальне число виробів.
Транспортна задача. Є n постачальників і m споживачів того самого продукту. Відомі випуск продукції в кожного постачальника й потреби в ній кожного споживача, витрати на перевезення продукції від постачальника до споживача.
Потрібно побудувати план транспортних перевезень із мінімальними транспортними витратами з урахуванням пропозиції постачальників і попиту споживачів.
Задача про призначення на роботу. Є n робіт і n виконавців. Вартість виконання роботи i виконавцем j дорівнює cij. Потрібно розподілити виконавців на роботи так, щоб мінімізувати витрати на оплату праці.
3адача про суміші (про раціон). З m видів вихідних матеріалів кожний з яких складається з n компонент, скласти суміш, у якій утримування компонентів повинне бути не менше b1,...,bn. Відомі ціни одиниць матеріалів с1,...,сm і питома вага j-го компонента в одиниці i-го матеріалу. Потрібно скласти суміш, у якій витрати будуть мінімальними.
Задача про рюкзак. Є n предметів. Вага предмета i дорівнює рi, цінність – сi (i=1,...,n). Потрібно при заданій цінності вантажу вибрати сукупність предметів мінімальної ваги.
Завдача про комівояжера. Є n міст і задані відстані cij між ними (j,i=1,...,n). Виїжджаючи з одного (вихідного) міста, комівояжер повинен побувати у всіх інших містах по одному разі й повернутися у вихідне місто.
Потрібно визначити в якому порядку треба об'їжджати міста, щоб сумарна пройдена відстань була найменша.
Задача про верстати. На універсальному верстаті обробляються однакові партії з n деталей. Перехід від обробки деталі i до обробки деталі j вимагає переналагодження верстата, що займає cij часу.
Потрібно визначити послідовність обробки деталей, при якій загальний час переналагоджень верстата щодо обробки нової партії деталей найменший.
Задача про розподіл капіталовкладень. Є n проектів, причому для кожного проекту j відомий очікуваний ефект h від його реалізації й необхідна величина капіталовкладень gj. Загальний обсяг капіталовкладень не може перевищувати заданої величини b.
Потрібно визначити, які проекти необхідно реалізувати, щоб сумарний ефект був найбільшим.
Задача про розміщення виробництва. Планується випуск m видів продукції, які могли б провадитися на n підприємствах (n>m). Витрати виробництва й збуту одиниці продукції, плановий обсяг річного виробництва продукції й планова вартість одиниці продукції кожного виду відомі. Потрібно з n підприємств вибрати такі m, кожне з яких буде провадити один вид продукції.
Для рішення кожної з наведених класів задач будується економіко-математична модель., методи вирішення якої залежать від структури моделі. Найбільша частка наведених задач може бути представлена моделями у вигляді задач лінійного програмування.
Приклад 1. Організація має 300 кг. металу, 100 м2 скла та 160 чол.год робочого часу. Для виготовлення виробу А потрібно 4 кг. металу, 2 м2 скла і 2 чол.год. робочого часу. Для виготовлення виробу В потрібно 5 кг. металу, 1 м2 скла і 3 чол.год. робочого часу. Прибуток від реалізації А складає 10 у.о., а В – 12 у.о. Треба спланувати випуск продукції так, щоб прибуток був максимальним.
Побудова моделі:
Визначимо невідомі величини, які потрібно знайти. Нехай x1 і x2 – кількість вробів А і В відповідно, тобто план виготовлення, який треба знайти. Прибуток від реалізації продукції буде визначатися лінійною формою:
F = 10x1 + 12 x2 ® max
при обмеженнях на ресурси виробництва по металу, склу та трудовим ресурсам відповідно до технологічних норм,
4x1 + 5x2 £ 300
2x1 + x2 £ 100
2x1 + 3x2 £ 160
x1 ³ 0; x2 ³ 0
Це типова задача лінійного програмування.
Приклад 2. На двох складах зберегається 12т. та 15т. товару який треба перевезти до трьох крамниць (до 1-й крамниці – 8т., до 2-й крамниці – 10т., до 3-й крамниці – 9 т.). Необхідно скласти оптимальний план перевезень якщо вартість перевезення в у.о. 1т. товару зі складів до крамниць наведено в таблиці:
Таблиця 1.1.1
| Крамниці Склади | Крамниця 1 | Крамниця 2 | Крамниця 3 |
| Склад1 | |||
| Склад2 |
Побудова моделі:
Позначимо через x1, x2, x3 - кількість товару, який треба перевезти з першого складу відповідно до крамниці 1, крамниці 2, крамниці 3, а через x4, x5, x6 - кількість товару, який треба перевезти з другого складу відповідно до крамниці 1, крамниці 2, крамниці 3.
У математичному вигляді умови розподілу товарів зі складів до крамниць можна записати двома рівнянями:
x1 + x2 + x3= 12
x4 + x5 + x6= 15
x1 + x4 = 8
x2 + x5 = 10
x3 + x6 = 9
До цієї системи треба додати умови для значень xi³ 0i = 1,2,…,6, яки означають, що товар не повертається на склади. Цільова функція буде мати вид:
F(x) = 30 x1 + 46 x2 +32 x3 + 20 x4 + 53 x5 + 40 x6 ® min
Таким чином, економіко-математична модель задачі складається з цільовой функції і обмежень. Даний приклад являє собою транспортну задачу.
1.3 Загальний вигляд задачі лінійного програмування
Загальна постановка задачі лінійного програмування в канонічному виді вимагає знайти значення змінних x1, x2, …, xn, які забезпечують найменше значення цільової функції
f(x1, x2, …, xn) = c0 + c1x1 + c2 x2 + … + cn xn, (1.3.1)
і задовольняють системі лінейних рівнянь
a11x1 + a12 x2 + … + a1n xn = b1
a21x1 + a22 x2 + … + a2n xn = b2
………………………………. (1.3.2)
am1x1 + am2 x2 + … + amn xn = bm
Прі цьому m < n та всі невідомі хі (і=1,2,..., n)³ 0 (1.3.3)
Набір змінних x1, x2, …, xn, які зодовільняють вимогам (1.3.2), (1.3.3) звуться припустимим рішенням. Припустиме рішення, при якому цільова функція має найменше значення є оптимальним рішенням.
Полагаємо, що всі рівняння системи (1.3.2) лінійно незалежні, а система совмесна. Необхідними умовами існування рішення в задачі оптимізації є співвідношення m < n. При m=n система має тільке одне рішення, що виключає можливість оптимізації. При m > n не виконуються положення, які прийняти вище.
1.4 Приведення задачі лінійного програмування до канонічного виду
При створенні лінійної моделі світогосподарського процесу не обов’язково, що вона буде вимагати пошук найменшого значення, та обмеження будуть представленні рівняннями. Але для пошуку рішення за допомогою симплекс методу це є обов’язковим. Тому виникає необхідність приведення задачі лінійного програмування до канонічного виду. Приведення до канонічного вигляду здійснюється за допомогою наступних правил.
Якщо цільова функція вимагає знаходження максимуму, то якщо її помножити на “-1” функція змінються на знаходження мінімуму. В системі обмежень для перехіду від знаку “£” до знаку “=” треба додати додаткову зміну, а від знаку “³” до знаку “=” додати додаткову зміну з відємним значенням.
Приклад 1. Економіко-математична модель задачі лінійного програмування, яку треба привести до канонічного виду має вигляд
F = 10x1 + 12 x2 ® max
при обмеженнях
4x1 + 5x2 £ 300
2x1 + x2 £ 100
2x1 + 3x2 £ 160
x1 ³ 0; x2 ³ 0
Для приведення цільової функції до канонічного виду виконуємо множення її на “-1”. В кожному обмеженні для зміни знака “ £ ” на знак “=” додаємо додаткову змінну. Ця змінна компенсує різницю між математичною формулою ліворуч та встановленою величиною праворуч. Таким чином задача у канонічному виді
F = - 10x1 - 12 x2 ® min
при обмеженнях
4x1 + 5x2 + x3 = 300
2x1 + x2 + x4 = 100
2x1 + 3x2 + x5 = 160
x1 ³ 0; x2 ³ 0; x3 ³ 0; x4 ³ 0; x5 ³ 0
Приклад 2. Економіко-математична модель задачі лінійного програмування, яку треба привести до канонічного виду має вигляд
F(x) = х1 - х2 - 3х3 ® min
при обмеженнях
2х1 - х2 - 3х3 £ 1
4х1 - 2х2 + х3 ³ -2,
2x1 + x3 £ 5
xj ³ 0 (j = 1, 2, 3)
В цьому прикладі цільова функція вже встановлює пошук найменшого значення. Тому вона не змінюється. В кожному обмеженні для зміни знака “ £ ” на знак “=” додаємо додаткову змінну, а для зміни знака “ ³ ” на знак “=” додаємо додаткову змінну з відємним значенням. Ця змінна компенсує різницю між математичною формулою ліворуч та встановленою величиною праворуч. Таким чином задача у канонічному виді
F(x) = х1 - х2 - 3х3 ® min
при обмеженнях
2х1 - х2 - 3х3 + х4 = 1
4х1 - 2х2 + х3 - х5 = -2,
2x1 + x3 + х6 = 5
xj ³ 0 (j = 1, 2,..., 6)
1.5 Симплексний метод рішення задач лінійного програмування
Існує багато методів які дозволяють знайти оптимальне рішення в задачах лінійного програмування (ЗЛП). Одним з таких методів, який дозволяє ефективно вирішувати такі задачі є симплекс метод. Ідея цього методу складається з переходів від одного розв’язку xk до другого xk+1, для яких виконується умова f(xk) > f(xk+1). Для переходу від одного розв’язку до другого використовуються симлексні таблиці. Кожній симплексній таблиці відповідає один з розв’язків задачі. По змісту симплексної таблиці можна визначити, чі оптимальне рішення знайдено, або що задача рішень не має.
Послідовність рішення задачі лінійного програмування за допомогою симплексного методу. Рішення задачі лінійного програмування виконується в наступній послідовності:
Крок 1. Здійснюється перевірка економіко-математичної моделі на відповідність канонічному виду. Якщо модель не відповідає вимогам, то виконується приведення моделі до канонічного виду.
Крок 2. Для таблиці обмежень будується матриця коефіцієнтів та визначається базіс. Якщо треба, то послідовно у кожній строці визначається базисна змінна і за методом Гауса проводяться необхідні перетворення. Кожна базисна зміна має бути присутньою тільки в одній строці обмежень. Нехай Xk , Xk+1, …, Xk+j - є базіс, тогда Xk= B1, Xk+1= B2, …, Xk+j= Bm – є базисний розв’язок. Подальша задача полягає в тому, щоб від початкового допустимого базисного розв’язку перейти до іншого базисного розв’язку, при якому значення лінійної форми зменшиться. Лінійна форма при початковому базисному розв’язку дорівнює нулю. Для поліпшення результатів розв’язку на кожному кроці треба перевести одну змінну з неосновних в основні і одну змінну з основних в неосновні, тобто дві змінні міняються місцями.
Крок 3. Будуємо симлекс таблицю для лінійної моделі наступного виду:
Таблиця 1.5.1
| e | X1 | X2 | … | Xn | B |
| Xk | a11 | a12 | … | a1n | B1 |
| Xk+1 | a21 | a22 | … | a2n | B2 |
| … | … | … | … | … | … |
| Xk+j | am1 | am2 | … | amn | Bm |
| F (x) | C1 | C2 | … | Cn | C0 |
В таблиці k, k+1, k+j < n, (Xk , Xk+1, …, Xk+j ) – початковий базіс рішення.
Крок 4. Серед коефіцієтів Ci (i = 1,n) обираємо Ci < 0 той, що має найменше значення (найбільше за абсолютним значенням). Стовпець з обраним Ci визначає змінну, яку треба перенести до базису. Щоб обрати змінну, яку треба виключити з бази розраховуємо оценку, яка визнається як Bi /aij. Виключати треба змінну, яка буде мати найменшу оцінку.
Крок 5. Після визначення змінної - притендента на перенесення в базис, використовуючі метод Гауса треба провести відповідні розрахунки в обмеженнях. Для цього строку обмежень з визначеною зміною пділимо на коефіцієнт при цей зміной. Потім знаходимо чому дорівнює ця змінна через інші змінні і підставляємо її значення в інші строки обмеження і лінейну форму.
Крок 6. За результатми проведених змін оновлюємо симплекс таблицю. Якщо серед коефіцієтів Ci (i = 1,n) є Ci < 0, то переходимо до кроку 4. Якщо всі Ci ³ 0, то знайдено оптимальне рішення.
Приклад 1. В прикладі 1 розділа 1.1 на підставі умов завдання побудована економіко-математична модель для пошуку рішення. Ця модель вимагає знайти максимальне значення цільової функції
F = 10x1 + 12 x2 ® max
при обмеженнях на ресурси виробництва по металу, склу та трудовим ресурсам відповідно до технологічних норм,
4x1 + 5x2 £ 300
2x1 + x2 £ 100
2x1 + 3x2 £ 160
x1 ³ 0; x2 ³ 0
Приводимо модель до канонічного виду
F = - 10x1 - 12 x2 ® min
при обмеженнях
4x1 + 5x2 + x3 = 300
2x1 + x2 + x4 = 100
2x1 + 3x2 + x5 = 160
x1 ³ 0; x2 ³ 0; x3 ³ 0; x4 ³ 0; x5 ³ 0
Будуємо сімплекс таблицю і визначаємо базіс. Так як додаткові змінні x3, x4, x5 мають кофецієнт одиницю та присутні тільке один раз в кожній строці обмежень, то ці змінні можуть створювати базіс.
Таблиця 1.5.2
| e | X1 | X2 | X3 | X4 | X5 | B |
| X3 | ||||||
| X4 | ||||||
| X5 | ||||||
| F (x) | -10 | -12 |
Аналізуємо остнню строку таблиці та визначаємо стовпець зі змінною, яку треба перенести до базису. В нашому випадку найменше значення “ -12 ”, що відповідає знмінній x2.
Визначаємо змінну, яку треба вивести з базісу. Для цього вільні значення (стовпець В) ділимо на коефіцієнти у відповідних строках стовпця x2. За підсумками маємо значення
300 / 5; 100 / 1; 160 / 3 або 60; 100; 53,33333
Найменше значення знаходиться в строці зі змінною x5. Таким чином треба провести перетворення моделі за методом Гауса і перенести в базіс x2 замість x5. Обмеження, у якому визначено x2 і x5 поділимо на 3 і отримуємо (2/3)x1 + x2 + (1/3)x5 = 160/3. Вирішуємо рівняння відносно x2
x2 = 160/3 -(2/3)x1 - (1/3)x5
Отримане значення x2 підставляємо в інші обмеження і цільову функцію.
4x1 + 5(160/3 -(2/3)x1 - (1/3)x5) + x3 = 300 або (2/3)x1+ x3 - (5/3)x5 = 100/3,
2x1 + 160/3 -(2/3)x1 - (1/3)x5 + x4 = 100 або (4/3)x1+ x4 - (1/3)x5 = 140/3.
Підставляємо значення x2 в цільову функцію
F = - 10x1 - 12 (160/3 -(2/3)x1 - (1/3)x5) або- 2x1 + 4x5 – 640 ® min,
і отримуємо нову систему цільової функції і обмежень
F = - 2x1 + 4x5 – 640 ® min,
при обмеженнях
(2/3)x1+ x3 - (5/3)x5 = 100/3
(4/3)x1+ x4 - (1/3)x5 = 140/3
(2/3)x1 + x2 + (1/3)x5 = 160/3
Будуємо нову сімлекс таблицю:
Таблиця 1.5.3
| e | X1 | X2 | X3 | X4 | X5 | B |
| X3 | 2/3 | -5/3 | 100/3 | |||
| X4 | 4/3 | -1/3 | 140/3 | |||
| X2 | 2/3 | 1/3 | 160/3 | |||
| F (x) | -2 |
Знову визначаємо змінну, яку треба перевести до базісу. За підсумками аналізу ніжньої строки це змінна x1 .
Визначаємо змінну, яку треба вивести з базісу. Для цього вільні значення (стовпець В) ділимо на коефіцієнти у відповідних строках стовпця x1. За підсумками маємо значення
(100/3):(2/3) = 50; (140/3):(4/3) = 35; (160/3):(2/3) = 80
На цьому кроці найменше значення знаходиться в строці зі змінною x4. Таким чином треба провести перетворення моделі за методом Гауса і перенести в базіс x1 замість x4. Обмеження, у якому визначено x1 і x4 поділимо на 4/3 і отримуємо x1 + (3/4)x4 - (1/4)x5 = 35. Вирішуємо рівняння відносно x1
x1 = 35 - (3/4)x4 + (1/4)x5
Отримане значення x1 підставляємо в інші обмеження і цільову функцію.
2/3(35 - (3/4)x4 + (1/4)x5) + x3 + (5/3)x5 = 100/3 або x3 - (1/2)x4 - (3/2)x5 = 10,
2/3(35 - (3/4)x4 + (1/4)x5) + x2 + (1/3)x5 = 160/3 або x2 - (1/2)x4 + (1/2)x5 = 30,
Підставляємо значення x2 в цільову функцію
F = - 2(35 - (3/4)x4 + (1/4)x5) + 4x5 – 640 ® min, або 1,5 x4 + 3,5x5 – 710 ® min,
і отримуємо нову систему цільової функції і обмежень
F = 1,5x4 + 3,5x5 – 710 ® min,
при обмеженнях
x3 - (1/2)x4 - (3/2)x5 = 10
x1 + (3/4)x4 - (1/4)x5 = 35
x2 - (1/2)x4 + (1/2)x5 = 30,
Будуємо нову сімлекс таблицю:
Таблиця 1.5.4
| e | X1 | X2 | X3 | X4 | X5 | B |
| X3 | -1/2 | -3/2 | ||||
| X1 | 3/4 | -1/4 | ||||
| X2 | -1/2 | 1/2 | ||||
| F (x) | 1,5 | 3,5 |
В нової таблиці немає відємних значень в останій строці. Тому ми маємо оптимальне розв’язування задачі. Змінні x4, x5 , які не входять до бази, дорівнюємо нулю і отримуваємо результат: (x1 = 35; x2 = 30; x3 = 10; x4 = 0; x5 = 0;), максимальне значення функції дорівнює 710. Подставляємо значення x1 = 35 і x2 = 30 до цільової функції і отримуваємо:
F = 10x1 + 12 x2 = 10*35 + 12*30 = 350 + 360 = 710
Це визначає, що рішення вірно.
Приклад 2. На двох складах зберегається 12т. та 15т. товару який треба перевезти до трьох крамниць (до 1-й крамниці – 8т., до 2-й крамниці – 10т., до 3-й крамниці – 9 т.). Необхідно скласти оптимальний план перевезень якщо вартість перевезення в у.о. 1т. товару зі складів до крамниць наведено в таблиці:
Таблиця 1.5.5
| Крамниці Склади | Крамниця 1 8 | Крамниця 2 10 | Крамниця 3 9 |
| Склад1 12 | |||
| Склад2 15 |
Ця задача наведена в прикладі 2 розділа 1.2 на підставі умов завдання побудована економіко-математична модель для пошуку рішення. Ця модель вимагає знайти минимальне значення цільової функції:
F(x) = 30 x1 + 46 x2 +32 x3 + 20 x4 + 53 x5 + 40 x6 ® min
З обмеженнями
x1 + x2 + x3= 12
x4 + x5 + x6= 15
x1 + x4 = 8
x2 + x5 = 10
x3 + x6 = 9
xi³ 0i = 1,2,…,6
У даному випадку задача лінійного програмування вже має канонічний вид. Треба будувати симлекс таблицю, але спочатку необхідно визначити базіс. За методом Гауса виконуємо наступні перетворення, щоб визначити базові змінні. З першого рівняння x1= 12 - x3 - x2. Підставляємо значення x1 до третього рівняння, та виводимо x1 до бази. З четвертого рівняння x2= 10 - x5. Підставляємо значення x2 до першого і третього рівняння, та виводимо x2 до бази. З п’ятого рівняння x3= 9 - x6. Підставляємо значення x3 до першого і третього рівняння, та виводимо x3 до бази. Після ціх перетворень маємо наступні обмеження
x1 - x5 - x6= -7
x4 + x5 + x6= 15
x4 + x5 + x6= 15
x2 + x5 = 10
x3 + x6 = 9
xi³ 0i = 1,2,…,6
Друге рівняння тотожно третьому, тому його можна виключити. Для моделі будуємо симплексну таблицю
Таблиця 1.5.6
| e | X1 | X2 | X3 | X4 | X5 | X6 | B |
| X 1 | -1 | -1 | -7 | ||||
| X 4 | |||||||
| X2 | |||||||
| X 3 | |||||||
| F (x) |
В таблиці немає в останій строці коефіцієнтів, які мають відємне значення, тому подальша оптимізація за допомогою симплекс перетворень не можлива. Для пошуку остаточного рішення треба змінні, які не є базовими дорівняти 0. Якщо за першим рівнянням одночасно x5 та x6 дорівняти 0, то x1 буде мати відємне значення, а це суперечить умовам. Для подальшого пошуку рішення треба застосовувати інши логічно математичні перетворення, за результатами яких остаточне рішення (0;3; 9; 8; 7; 0), а значення цільової функції F(x) = 30*0 + 46*3 +32*9 + 20*8 + 53*7 + 40*0 = 957.
Остаточне рішення має вигляд: Таблиця 1.5.7
| Крамниці Склади | Крамниця1 (потрібно 8т) | Крамниця2 (потрібно10т) | Крамниця3 (потрібно 9т) |
| Склад1 (усього 12т) | Х1=0 | Х2=3 | Х3=9 |
| Склад2 (усього 15т) | Х4=8 | Х5=7 | Х6=0 |
У даному прикладі наведено рішення транспортної задачі симплекс методом. Використання цього методу для вирішення транспортних задач не є ефективним. Для розв’язування транспортних задач більш ефективними є спеціальні методи, які будуть наведени при розгляді транспортних задач.
1.6 Двоїста задача
Двоїстою задачею називається задача, яка побудована з основної наступним шляхом:
| Основна задача | Двоїста задача |
| f (x1, x2, …, xn) = c1x1 + c2 x2 + … + cn xn, ® max при обмеженнях a11x1 + a12 x2 + … + a1n xn £ b1 a21x1 + a22 x2 + … + a2n xn £ b2 ………………………………. am1x1 + am2 x2 + … + amn xn £ bm | j (y1, y2, …, ym) = b1y1 + b2 y2 + … + bm ym, ® min при обмеженнях a11y1 + a21 y2 + … + am1 ym ³ c1 a12y1 + a22 y2 + … + am2 ym ³ c2 ………………………………. a1ny1 + a2n y2 + … + amn ym ³ cn |
1) змінюється напрямок оптимізації з min на max та навпаки.
2) Коефіцієнти при x переносяться в обмеження і з обмежень в цільову функцію.
3) Знаки “£” змінюються на “³”.
4) Матриця умов одной задачі фурмує матрицю умов іншої задачі шляхом транспонування.
Теорема. В основної та двоїстої задачі значення цільових функцій в оптимальних точках співпадають. При цьому якщо основна функція не обмежена, то двоїста задача не має рішення і навпаки.
Двоїста задача дозволяє спростити пошук рішення. Вона пов’язана з основною задачею наступними співвідношеннями. Якщо a - припустиме рішення основної задачі, а b - припустиме рішення двоїстої задачі, то f(a) £ j(b). Якщо f(a) = j(b), то a і b - оптимальне рішення.
Приклад 1. Побудувати двоїсту задачу до наступної лінейної моделі. Знайти максимум цільової функції F = х1 + 3х2 + х3, при обмеженнях:
3х1 + 2х2 - х3 ≤ 5
х1 - 4х2 - 2х3 ≤ 3
2х1 - 5х2 + х3 ≤ 2
xi³ 0i = 1,2,3
Рішення. Побудову двоїстої задачі зручно виконувати за наступною схемою. Будуємо таблицю, в строки якої заносимо обмеження і цільову функцію. Якщо розглянути стовпці цієї таблиці, то вони є основою для побудови двоїстої задачі.
Таблиця 1.6.1
| Двоїста Задача Основна Задача | Обмеження 1 | Обмеження 1 | Обмеження 1 | Цільова функція | ||||
| Обмеження 1 | +3 | х1 | +2 | х2 | -1 | х3 | ≤ | |
| Обмеження 2 | +1 | х1 | -4 | х2 | -2 | х3 | ≤ | |
| Обмеження 3 | +2 | х1 | -5 | х2 | +1 | х3 | ≤ | |
| Цільова функція | +1 | х1 | +3 | х2 | +1 | х3 | ® | max |
Вводимо нову змінну y і будуємо нову цільову функцію. Останій стовпець, де розташовані вільні члени обмежень, використовуваємо як коефіцієнти до змінних в цільовій функції двоїстої задачі. Нова цільова функція має вигляд:
j = 5y1 + 3y2 +2y3 ® min
Обмеження також будуються по коефіцієнтах в стовпцях. Вільні члени обмежень – це коефіцієнти з цільової функції основної задачі:
3y1 + y2 +2y3 ³ 1
2y1 – 4y2 – 5y3 ³ 3
-y1 – 2y2 + y3 ³ 1
yi³ 0i = 1,2,3
Транспортна задача
Виділення транспортної задачі в окремий розділ обумовлено тим, що ця задача має специфічну економіко-математичну модель і може розв’язуватися не універсальним симплекс-методом, а за допомогою так званного розподільного методу і його різноманітних модифікацій.
Найпростішими транспортними задачами є задачі перевезення деякого однорідного вантажу від постачальників до споживачів при забезпеченні мінімальних витрат на перевезення.
Початкові умови таких задач записують у вигляді таблиці. Наприклад, для m постачальників і n споживачів така таблиця має наступний вигляд:
Таблиця 1.7.1
| Споживачі та їх потреби | |||||||
| Постачальники | B1 | B2 | … | Bj | … | Bn | |
| A1 | С11 | С12 | ... | С1j | ... | С1n | |
| A2 | С21 | С22 | ... | С2j | ... | С2n | |
| … | ... | ... | ... | ... | ... | ... | |
| Ai | Сi1 | Сi2 | ... | Сij | ... | Сin | |
| … | ... | ... | ... | ... | ... | ... | |
| Am | Сm1 | Сm2 | ... | Сmj | ... | Сmn |
В таблиці представлено інформацію про потужність постачальників Ai (i = 1,m), потребу споживачів Bj (j = 1,n), а також витрати на перевезення від i - го постачальника j -му споживачу Cij.
Позначимо через xij кількость постачання вантажу від i - го постачальника j -му споживачу. Математично транспортна задача зводиться до знаходження мінімуму цільової функції, яка задає сумарні витрати на перевезення усього вантажу:
F = c11x11 + c12x12 + … + cijxij + … + cmnxmn ® min (1.7.1)
При обмеженнях
X11 + x12 + … + x1n = A1,
X21 + x22 + … + x2n = A2,
.....................
xm1 + xm2 + … + xmn = Am, (1.7.2)
x11 + x21 + … + xm1 = B1,
x12 + x22 + … + xm2 = B2,
.....................
x1n + x2n + … + xmn = Bn.
Якщо в транспортній задачі сумарна потужності всіх постачальників равна сумарній потребі всіх споживачів, то відповідну математичну модель задачі називають закритою, або моделлю з правільним балансом. В іншому випадку – відкритою, або не сбалансованою.
Економіко-математична модель транспортної задачі має наступні особливості і відрізняється від звичайних задач лінейного програмування в загальному вигляді, а саме:
- система обмежень (1.7.2) має вигляд рівнянь, тому відпадає необхідність вводити додаткові змінні;
- матриця коефіцієнтів при змінних в системі (1.7.2) складається тільки з одиниць та нулів;
- система (1.7.2) є системою n + m рівнянь з nm невідомими.
Така специфічність економіко-математичної моделі транспортної задачі привела до появи особливих методів її розв’язування.
Рішення транспортної задачі починається з пошуку початкового розподілу постачань. Найбільш розповсюджуваними методами є метод “північно-західного кута” і метод “найменших витрат”.
1.7.1 Пошук початкового розподілу постачань за методом “північно-західного кута”.
До початку розподілу перевіряємо баланс між сумарною потужністю всіх виробників та сумарною потребою всіх споживачів. Якщо задача сбалансована починаємо виконувати розподіл у наступної послідовності.
“Північно-західний кут” це сама верхня, ліва клітинка. Визначаємо потужність першого виробника. Якщо виробник має потужність більшу, ніж потреба споживача, то в клітинку заносимо кількість вантажу, яка равна повної потреби споживача. Для розподілу залишку переходимо до наступної правої клітинки. Для цієї клітинки виконуємо аналогічний розподіл. Якщо на якому-небудь кроці не вистачє потужності виробника, в клітинку занаситься все, що є у нього і розподіл переносится до наступного виробника та розглядається клітинка, яка зв’язує цього виробника зі споживачем. Розподіл за наступною методикою виконується до останього постачальника і останього споживача. Так як задача збалансована, то розподіл буде виконано повністю.
Для перевірки вартості постачань за таким розподілом необхідно підрахувати суму добутків кількості постачань і їх вартості для всіх заповнених клітинок. Метод “північно-західного кута” найбільш дозволяє просто виконати розподіл, але він не враховує вартість постачань безпосередньо під час розподілу. Тому має низьку ефективність.
Приклад 1. Скласти оптимальний план перевезень однорідного вантажу від виробників до споживачів, якщо запаси вантажу у виробників, потреба споживачів і вартість перевезень задано наступною таблицією:
Таблиця 1.7.2
| Виробники | |||||
| Споживачі |
Рішення. Спочатку перевіряємо баланс між запасами виробників та потребою споживачів:
Запаси виробників - 18+40+12+8=78
Потреба споживачів – 20+15+35+8=78
Задача сбалансована. Будуємо нову таблицю і в її клітинки заносимо розмір партій вантажу, який треба перевезти. Формування партій починаємо з “північно-західного кута”. Перший виробник має запас 18 одиниць, а потреба споживача – 20, тобто перевішчує можливості виробника. Тому в першу клітинку заносимо – 18 і переходимо до наступного виробника. Він має запас в 40 одиниць, а незадоволеність споживача тількі 2 одиниці. Від другого виробника передаємо первому споживачу ці 2 одиниці і вважаємо, що потреба споживача задаволена повністю. Переходимо до другого споживача. Йому потрібно 15 одиниць, а виробника залишилось 38, тому повністю задовільняєм його потребу і переходимо до третього споживача. Третьому споживачу потрібно 35 одиниць, а у виробника залишилось 40-2-15=23 одиниці. Віддаємо 23 одиниці третьому споживачу. Так як його потреба залишилась не задовільненою 35-23=12 переходимо до третього виробника. Третій виробник має 12 одиниць, тому ми повністю задовольняємо потребу третього споживача. Залишилось нерозподілено 8 одиниць у четвертого виробника і 8 одиниць потрібно четвертому споживачу. Виконуємо останнє призначення.
Таблиця 1.7.3
| Виробники | |||||
| Споживачі |
Маючі таблицю вартості перевезень підрахуємо загальні витрати на перевезення за сформованим планом.
S = 18*20 + 2*15 + 15*4 + 23*22 + 12*12 + 8*12 = 1196.
В процесі виконання розподілу розглядається тільки запаси виробників і потреба споживачів. Метод “північно-західного кута” дозволяє легко створити план перевезень, але він не враховує вартість перевезень, тому його ефективність вкрай низька. Він може використовуватися тільке для побудови початкового плану перевезень і потребує подальшої оптимізації.
1.7.2 Пошук початкового розподілу постачань за методом “найменших витрат”.
Метод “найменших витрат” є удосконаленям метода “північно-західного кута”. Перед розподілом також перевіряється баланс між постачальниками і споживачами.
Розподіл виконується за наступною схемою. Проводиться аналіз таблиці вартості транспортних витрат. Обірається постачання з мінімальною вартістю і виконуються його повне задаволення виходячі з можливостей постачальника і споживача. Далі знаходиться наступна клітинка з мінімальною вартістю і також виконується постачання. Процес завершується, якщо весь вантаж виробників буде розподілено відповідно потребам споживачів.
Приклад 1. Скласти план постачань для умов попереднього приклада методом “найменших витрат”.
Рішення. Спочатку аналізуємо таблицю вартості. Найменша вартість постачання дорівнює 4 і визначає вартість постачання від другого виробника другому споживачу. Потреба постачання 15 одиниць, а запас – 40. Після призначення цього перевезення другого споживача задоволено повністю, а у першого виробника залишилось 40-15=25 одиниць вантажу. Знаходимо наступну мінімальну вартість постачання. Вона дорівнює 5 і визначає постачання від першого виробника третьому споживачу. Так як потреба споживача (35) перевищую можливості виробника (18), то призначаємо перевезення всіх 18 одиниць від першого постачальника третьому споживачу. Наступна мінімальна вартість 5 відноситься до другого споживача, потреба якого вже задоволена. Далі вартість – 6. Це перевезення від третього виробника, який має 12 одиниць, четвертому споживачу, потреба якого 8 одиниць. Задовівльняємо цю потребу і у виробника залишається 12-8=4 одиниці вантажу. Наступна вартість 8, але перший виробник вже задовільнив повністю другого споживача. Далі – 12. Це постачання від третього виробника, до третього споживача. У третього виробника залишилось тільки 4 одиниці. Призначаємо їх. Інші 12 відносится до четвертого споживача, потреба якого вже задоволена. Наступна вартість –15 оцінює постачання від другого виробника першому споживачу. Задовільняємо його потребу. Після цього залишився не задоволеним третій споживач, тому залишки виробників надаємо йому.
Таблиця 1.7.4
| Виробники | |||||
| Споживачі |
Підрахуємо загальні витрати на перевезення за сформованим планом.
S = 15*4 +18*5 + 2*15 + 8*6+ 4*12+20*15 + 8*16 + 5*22 = 784.
Метод “найменших витрат” дозволяє отримати суттєве кращий результат, але він також не є оптимальним. Цей метод також застосовується для побудови початкового розподілу і краще наближає до оптимального плану постачань
1.7.3 Рішення транспортної задачі методом потенціалів.
Існуєть багато методів розв’язування транспортних задач. Одним з таких методів є метод потенціалів. Сутність метода полягає у наступному.
Позначимо всіх постачальників через змінні Ui (i=1,m), а всіх споживачів через змінні Vj (j=1,n). Введемо поняття потенціалів. Потенціалами опорного рішення a будемо називати числа Ui і Vj таки, що сума Ui та Vj дорівнює вартості постачань відповідно для кожної клітинки Cij, яка заповнена за результатами початкового розподілу, тобто виконується рівнення Ui + Vj = Cij. Так як початковий розподіл має не менш одного зв’язку між постачальником і споживачем, то якщо встановити початкове значення Ui=0, то така система має рішення і всі значення Ui та Vj будуть знайдені.
По значенням Ui та Vj, які знайдені, розраховуваємо суми потенціалів для всіх не заповнених клетинок за формулою Ui та Vj. Якщо для всіх клетинок буде виконуватися співвідношення Ui + Vj £ Cij, то рішення, яке знайдено є оптимальним. В іншому випадку обіраємо клетинку в якої Ur + Vs > Crs. Якщо в транспортній таблиці провести перерозподіл призначень і включити цю клетинку, то план призначень може бути полипшено.
Для проведення перерозподілу в транспортній таблиці будуємо цикл, одно вершина якого знаходиться в клітинці i=r, j=s, а всі наступні вершини у заповнених клетинках, які є суміжними клітинці i=r, j=s. Кожній вершині присвоюємо “+”, або “-” у наступному порядку. В клетинці i=r, j=s встановлюємо “+”, суміжних клітинках “-”. При проведенні перерозподілу в клітинки зі знаком “+” переносимо повністю, або частково призначення, яке знаходиться в клітинці зі знаком “-” і так далі. Частка переноса призначення визначається можливостями виробника і потребою споживача.
Приклад 1. Скласти оптимальний план постачань для умов попередніх прикладів методом “потенціалів”.
Рішення. На підставі вихидних даних, які наведені в таблиці 1.7.5. За методом найменших витрат знаходимо початкове рішення. (Таблиця 1.7.6)
Для кожної заповненої клітинці створюємо рівняння Ui + Vj = Cij. В початковому плані постачань (Таблиця 1.7.6) заповнено 7 клітинок, тому будуємо систему з 7 рівнянь. Встановлюємо U1 = 0 і знаходимо всі значення Ui та Vj. Результати заносимо в таблицю 1.7.7. Розраховуваємо значення Ui + Vj для всіх не заповнених клітинок і також результати заносимо в таблицю.
| Таблиця 1.7.5 | Таблиця 1.7.6 | |
|
Таблиця 1.7.7
Дата публикования: 2015-10-09; Прочитано: 367 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
