МОСКОВСЬКИЙ КІНОВІДЕОІНСТІТУТ (філія)
Санкт-Петербурзького ДЕРЖАВНОГО УНІВЕРСИТЕТУ КІНО І ТЕЛЕБАЧЕННЯ
Курсова робота
«Економіко-математичні методи і прикладні моделі»
Виконала студентка 3-го курсу
(Прискорений)
Ющак Є.В.
Викладач Манцев А.П.
м. Москва, 2002
I. Вступ.
Предметом вивчення дисципліни є кількісні характеристики економічних процесів, що протікають в промисловому виробництві, вивчення їх взаємозв'язків на основі економіко-математичних методів і моделей. Ці моделі лінійного і нелінійного програмування, моделі дослідження операцій, моделі масового обслуговування.
Важливе місце відводиться економіко-математичних моделей в ціноутворенні. Особлива увага приділяється методам і моделям прогнозування кон'юнктури ринку та визначення цін, моделям і методам аналізу інвестиційних проектів, моделей в управлінні фінансами.
Чимале місце відводиться моделями оптимального галузевого та регіонального регулювання - економіко-математичними моделями проекту розвитку окремих галузей промисловості. Це такі важливі моделі, як варіантна, транспортно-виробнича, модель розрахунку паливного балансу регіону.
Основним поняттям є поняття математичної моделі. У загальному випадку слово модель - це відображення реального об'єкта. Таке відображення об'єкта може бути представлено схемою, ескізом, фотографією, моделлю описового характеру у вигляді графіків і таблиць і т.д. Математична модель - це система математичних рівнянь, нерівностей, формул і різних математичних виразів, що описують реальний об'єкт, складові його характеристики і взаємозв'язки між ними. Процес побудови математичної моделі називають математичним моделюванням. Моделювання та побудова математичної моделі економічного об'єкта дозволяють звести економічний аналіз виробничих процесів до математичного аналізу та прийняття ефективних рішень.
Оскільки нами вивчаються економічні завдання, то й будуються економіко-математичні моделі, що включають:
1) вибір деякого числа змінних величин для формалізації моделі об'єкта;
2) інформаційну базу даних об'єкта;
3) вираз взаємозв'язків, що характеризують об'єкт, у вигляді рівнянь і нерівностей;
4) вибір критерію ефективності і вираз його у вигляді математичного співвідношення - цільової функції.
Отже, для прийняття ефективних рішень в плануванні та управлінні виробництвом необхідно економічну сутність досліджуваного економічного об'єкта формалізувати економіко-математичної моделлю, тобто економічне завдання представити математично у вигляді рівнянь, нерівностей та цільової функції на екстремум (максимум чи мінімум) при виконанні всіх умов на обмеження і змінні.
II. Основні поняття моделювання.
2.1. Загальні поняття та визначення моделі.
Змістом будь-економіко-математичної моделі є виражена у формально-математичних співвідношеннях економічна сутність умов завдання та поставленої мети. У моделі економічна величина представляється математичним співвідношенням, але не завжди математичне співвідношення є економічним. Опис економічних умов математичними співвідношеннями - результат того, що модель встановлює зв'язки і залежності між економічними параметрами або величинами.
За змістом розрізняють економіко-математичні та економіко-статистичні моделі. Різниця між ними полягає в характері функціональних залежностей, що пов'язують їх величини. Так, економіко-статистичні моделі пов'язані з показниками, згрупованими різними способами. Статистичні моделі встановлюють залежність між показниками і визначають їх чинниками у вигляді лінійної і нелінійної функції. Економіко-математичні моделі включають в себе систему обмежень, цільову функцію.
Система обмежень складається з окремих математичних рівнянь або нерівностей, званих балансовими рівняннями чи нерівностями.
Цільова функція пов'язує між собою різні величини моделі. Як правило, в якості мети вибирається економічний показник (прибуток, рентабельність, собівартість, валова продукція і т.д.). Тому цільову функцію іноді називають економічною, критеріальної. Цільова функція - функція багатьох змінних величин і може мати вільний член.
Критерії оптимальності - економічний показник, що виражається за допомогою цільової функції через інші економічні показники. Одному й тому ж критерію оптимальності можуть відповідати кілька різних, але еквівалентних цільових функцій. Моделі з однієї і тієї ж системою обмежень можуть мати різні критерії оптимальності та різні цільові функції.
Рішенням економіко-математичної моделі, або допустимим планом називається набір значень невідомих, який задовольняє її системі обмежень. Модель має безліч рішень, або безліч допустимих планів, і серед них треба знайти єдине, яке задовольняє системі обмежень і цільової функції. Допустимий план, що задовольняє цільової функції, називається оптимальним. Серед допустимих планів, який задовольняє цільової функції, як правило, є єдиний план, для якого цільова функція і критерій оптимальності мають максимальне або мінімальне значення. Якщо модель завдання має безліч оптимальних планів, то для кожного з них значення цільової функції однаково.
Якщо економіко-математична модель задачі лінійна, то оптимальний план досягається в крайній точці області зміни змінних величин системи обмежень. У випадку нелінійної моделі оптимальних планів і оптимальних значень цільової функції може бути декілька. Тому необхідно визначати екстремальні плани і екстремальні значення цільової функції. План, для якого цільова функція моделі має екстремальне значення, називають екстремальним планом, або екстремальним рішенням.
Для нелінійних моделей іноді існують екстремальні значення цільової функції, а для лінійних моделей екстремальних планів і екстремальних значень цільової функції бути не може.
Таким чином, для прийняття оптимального рішення будь-якої економічної задачі необхідно побудувати її економіко-математичну модель, за структурою включає в собі систему обмежень, цільову функцію, критерій оптимальності та рішення.
Методика побудови економіко-математичної моделі полягає в тому, щоб економічну сутність завдання представити математично, використовуючи різні символи, змінні і постійні величини, індекси та інші позначення.
Всі умови задачі необхідно записати у вигляді рівнянь або нерівностей. Тому, в першу чергу необхідно визначити систему змінних величин, які можуть для конкретного завдання позначити шуканий обсяг виробництва продукції на підприємстві, кількість перевезеного вантажу постачальниками конкретним споживачам.
2.2. Постановка задач оптимізації
У загальному вигляді завдання оптимізації, або завдання визначення екстремуму, ставиться таким чином.
Нехай задані:
функція f (X), визначена на множині O Í R N ;
безліч D Í R N.
Знайти точку Y = (y 1, y 2 ,..., y N) Î D, в якій функція f (X) досягає екстремального (мінімального або максимального) значення, тобто
f (X) = extr f (X) і Y Î D.
Функція f (X) називається цільовою функцією, змінні X - керованими змінними, D - допустимим множиною і будь-який набір значень Y керованих змінних, що належить D (Y Î D), - допустимим рішенням задачі оптимізації.
Зрозуміло, що шукана точка Y, в якій f (X) досягає свого екстремуму, повинна належати перетинанню області визначення O функції f (X) і допустимого безлічі D (YÎ O Ç D). Якщо безлічі O і D збігаються з усім простором R N (O = D = R N), то таке завдання називається завданням на безумовний екстремум. Якщо хоча б одна з множин O або D є власним підмножиною простору R N (O Ì R N, D Ì R N) або безлічі O і D перетинаються (O Ç D ¹ Æ), то таке завдання називається завданням на умовний екстремум, в іншому випадку (O Ç D = Æ) точка екстремуму Y не існує. Підкреслимо один приватний випадок: якщо безлічі O і D перетинаються в одній точці Y, то ця точка Y є єдиним допустимим рішенням.
Зазвичай в задачі умовного екстремуму задається не саме допустиме безліч рішень D, а система співвідношень, його визначальна,
y j (X 1, х 2, х N) £ (=, ³) 0, j = 1, 2, ... М,
тобто
D = {X: yj (X) £ (=, ³) 0, j = 1, 2, ... , M} Í R N,
або безліч D може одночасно задаватися як в явному вигляді, тобто допустиме рішення Х має належати деякій області P Ì R N, так і системою обмежень.
III. Методи лінійного програмування.
3.1. Загальна і типова задача в лінійному програмуванні.
Оптимізаційна задача - це економіко-математична задача, яка полягає в знаходженні оптимального (максимального чи мінімального) значення цільової функції, причому значення змінних повинні належати деякій області допустимих значень.
У самому загальному вигляді завдання математично записується так:
U = f (X) ® max; X Î W,
Де X = (Х1, Х2, ..., Хn);
W - область допустимих значень змінних Х1, Х2, ..., Хn;
f (X) - цільова функція.
Для того, щоб вирішити задачу оптимізації, досить знайти її оптимальне рішення, тобто вказати X () Î W таке, що f (X ()) ³ f (X), при будь-якому X Î W, або для випадку мінімізації - що f (X ()) ≤ f (X), при будь-якому X Î W .
Оптимізаційна задача є нерозв'язною, якщо вона не має оптимального рішення. Зокрема, завдання максимізації буде нерозв'язна, якщо цільова функція f (X) не обмежена зверху на допустимому безлічі W.
Методи рішення оптимізаційних завдань залежать як від виду цільової функції f (X), так і від будови допустимого безлічі W. Якщо цільова функція в задачі є функцією n змінних, то методи рішення називають методами математичного програмування.
У математичному програмуванні прийнято виділяти такі основні завдання в залежності від виду цільової функції f (X) і від області W:
· Завдання лінійного програмування, якщо f (X) і W лінійні;
· Задачі цілочислового програмування, якщо ставиться умова цілочисельності змінних Х1, Х2, ..., Хn;
· Задачі нелінійного програмування, якщо форма f (X) носить нелінійний характер.
Завдання лінійного програмування.
Завданням лінійного програмування називається завдання дослідження операцій, математична модель якої має вигляд:
f (X) = å СjXj ® max (min);
å aij xj = bi, iÎI, IÍM = {1, 2, ... m};
å aij xj £ bi, iÎM;
Xj ³ 0, jÎJ, JÍN = {1, 2, ... n}.
При цьому система лінійних рівнянь і нерівностей, що визначає допустиму кількість рішень задачі W, називається системою обмежень задачі лінійного програмування, а лінійна функція f (X) називається цільовою функцією або критерієм оптимальності.
Будь-яку задачу лінійного програмування можна звести до задачі лінійного програмування у канонічній формі. Для цього в загальному випадку потрібно вміти зводити задачу максимізації до задачі мінімізації; переходити від обмежень нерівностей до обмежень рівностей і замінювати змінні, які не підкоряються умові неотрицательности. Максимізація деякою функції еквівалентна мінімізації тієї ж функції, взятої з протилежним знаком, і навпаки.
Правило приведення завдання лінійного програмування до канонічного виду полягає в наступному:
1) якщо у вихідній задачі потрібно визначити максимум лінійної функції, то слід змінити знак і шукати мінімум цієї функції;
2) якщо в обмеженнях права частина негативна, то слід помножити це обмеження на -1;
3) якщо серед обмежень є нерівності, то шляхом введення додаткових невід'ємних змінних вони перетворюються в рівності;
4) якщо деяка змінна Хk не має обмежень по знаку, то вона замінюється (в цільовій функції і у всіх обмеженнях) різницею між двома новими невід'ємними змінними::
Xk = X `k - X l, де l - вільний індекс, X `k ³ 0, Xk ³ 0.
3.2. Постановка задачі лінійного програмування
Під терміном «транспортні завдання» розуміється широке коло завдань не тільки транспортного характеру. Спільним для них є, як правило, розподіл ресурсів, що знаходяться у m виробників (постачальників), але n споживачам цих ресурсів.
На автомобільному транспорті часто зустрічаються такі завдання, пов'язані з транспортним:
· Прикріплення споживачів ресурсу до виробників;
· Прив'язка пунктів відправлення до пунктів призначення;
· Взаємна прив'язка вантажопотоків прямого і зворотного напрямів;
· Окремі завдання оптимального завантаження промислового обладнання;
· Оптимальний розподіл обсягів випуску промислової продукції між заводами-виробниками.
Транспортним завданням притаманні такі особливості:
· Розподілу підлягають однорідні ресурси;
· Умови задачі описуються тільки рівняннями;
· Всі змінні виражаються в однакових одиницях виміру;
· У всіх рівняннях коефіцієнти при невідомих дорівнюють одиниці;
· Кожна невідома зустрічається тільки в двох рівняннях системи обмежень.
Транспортні задачі можуть вирішуватися симплекс-методом.
3.3. Рішення транспортної задачі
Початковий розподіл виберемо за методом найменших вартостей. Порядок заповнення клітин: (3,1), (1,2), (4,3). (2,4), (1,5), (1,4), (3,5), (4,5)
Сумарні витрати:
f (x) = 6'18 +7'15 +8'32 +8'5 +8'40 +7'10 +14'7 +16'13 = 1107
Розглянемо процес знаходження потенціалів для даного розподілу.
Покладемо, Ui = 0 Þ V2 = U1 + C12 = 7; V5 = U1 + C15 = 7 = U3 +14 = U4 +16 Þ U3 = -7, U4 = -9; V3 = U4 + C43 = -1; V4 = U2 +8 = U1 +8 Þ U2 = U1 = 0; V4 = 8.
Знайдемо оцінки: d ij = (U i + c ij)-V j:
11 0 15 0 0
(Dij) = 13 1 11 0 8
0 -4 4 -3 0
8 -6 0 -5 0
Даний план не є оптимальним, тому що є негативні оцінки.
Побудуємо контур перерозподілу для клітини (4,2). Найменша поставка в вершині контуру зі знаком "-" дорівнює 13, тому проведемо перерозподіл поставок, зменшивши поставки в клітинах зі знаком "-" на 13 і збільшивши постачання в клітинах зі знаком "+" на 13. результати поставлені в таблиці 2.
Санкт-Петербурзького ДЕРЖАВНОГО УНІВЕРСИТЕТУ КІНО І ТЕЛЕБАЧЕННЯ
Курсова робота
«Економіко-математичні методи і прикладні моделі»
Виконала студентка 3-го курсу
(Прискорений)
Ющак Є.В.
Викладач Манцев А.П.
м. Москва, 2002
I. Вступ.
Предметом вивчення дисципліни є кількісні характеристики економічних процесів, що протікають в промисловому виробництві, вивчення їх взаємозв'язків на основі економіко-математичних методів і моделей. Ці моделі лінійного і нелінійного програмування, моделі дослідження операцій, моделі масового обслуговування.
Важливе місце відводиться економіко-математичних моделей в ціноутворенні. Особлива увага приділяється методам і моделям прогнозування кон'юнктури ринку та визначення цін, моделям і методам аналізу інвестиційних проектів, моделей в управлінні фінансами.
Чимале місце відводиться моделями оптимального галузевого та регіонального регулювання - економіко-математичними моделями проекту розвитку окремих галузей промисловості. Це такі важливі моделі, як варіантна, транспортно-виробнича, модель розрахунку паливного балансу регіону.
Основним поняттям є поняття математичної моделі. У загальному випадку слово модель - це відображення реального об'єкта. Таке відображення об'єкта може бути представлено схемою, ескізом, фотографією, моделлю описового характеру у вигляді графіків і таблиць і т.д. Математична модель - це система математичних рівнянь, нерівностей, формул і різних математичних виразів, що описують реальний об'єкт, складові його характеристики і взаємозв'язки між ними. Процес побудови математичної моделі називають математичним моделюванням. Моделювання та побудова математичної моделі економічного об'єкта дозволяють звести економічний аналіз виробничих процесів до математичного аналізу та прийняття ефективних рішень.
Оскільки нами вивчаються економічні завдання, то й будуються економіко-математичні моделі, що включають:
1) вибір деякого числа змінних величин для формалізації моделі об'єкта;
2) інформаційну базу даних об'єкта;
3) вираз взаємозв'язків, що характеризують об'єкт, у вигляді рівнянь і нерівностей;
4) вибір критерію ефективності і вираз його у вигляді математичного співвідношення - цільової функції.
Отже, для прийняття ефективних рішень в плануванні та управлінні виробництвом необхідно економічну сутність досліджуваного економічного об'єкта формалізувати економіко-математичної моделлю, тобто економічне завдання представити математично у вигляді рівнянь, нерівностей та цільової функції на екстремум (максимум чи мінімум) при виконанні всіх умов на обмеження і змінні.
II. Основні поняття моделювання.
2.1. Загальні поняття та визначення моделі.
Змістом будь-економіко-математичної моделі є виражена у формально-математичних співвідношеннях економічна сутність умов завдання та поставленої мети. У моделі економічна величина представляється математичним співвідношенням, але не завжди математичне співвідношення є економічним. Опис економічних умов математичними співвідношеннями - результат того, що модель встановлює зв'язки і залежності між економічними параметрами або величинами.
За змістом розрізняють економіко-математичні та економіко-статистичні моделі. Різниця між ними полягає в характері функціональних залежностей, що пов'язують їх величини. Так, економіко-статистичні моделі пов'язані з показниками, згрупованими різними способами. Статистичні моделі встановлюють залежність між показниками і визначають їх чинниками у вигляді лінійної і нелінійної функції. Економіко-математичні моделі включають в себе систему обмежень, цільову функцію.
Система обмежень складається з окремих математичних рівнянь або нерівностей, званих балансовими рівняннями чи нерівностями.
Цільова функція пов'язує між собою різні величини моделі. Як правило, в якості мети вибирається економічний показник (прибуток, рентабельність, собівартість, валова продукція і т.д.). Тому цільову функцію іноді називають економічною, критеріальної. Цільова функція - функція багатьох змінних величин і може мати вільний член.
Критерії оптимальності - економічний показник, що виражається за допомогою цільової функції через інші економічні показники. Одному й тому ж критерію оптимальності можуть відповідати кілька різних, але еквівалентних цільових функцій. Моделі з однієї і тієї ж системою обмежень можуть мати різні критерії оптимальності та різні цільові функції.
Рішенням економіко-математичної моделі, або допустимим планом називається набір значень невідомих, який задовольняє її системі обмежень. Модель має безліч рішень, або безліч допустимих планів, і серед них треба знайти єдине, яке задовольняє системі обмежень і цільової функції. Допустимий план, що задовольняє цільової функції, називається оптимальним. Серед допустимих планів, який задовольняє цільової функції, як правило, є єдиний план, для якого цільова функція і критерій оптимальності мають максимальне або мінімальне значення. Якщо модель завдання має безліч оптимальних планів, то для кожного з них значення цільової функції однаково.
Якщо економіко-математична модель задачі лінійна, то оптимальний план досягається в крайній точці області зміни змінних величин системи обмежень. У випадку нелінійної моделі оптимальних планів і оптимальних значень цільової функції може бути декілька. Тому необхідно визначати екстремальні плани і екстремальні значення цільової функції. План, для якого цільова функція моделі має екстремальне значення, називають екстремальним планом, або екстремальним рішенням.
Для нелінійних моделей іноді існують екстремальні значення цільової функції, а для лінійних моделей екстремальних планів і екстремальних значень цільової функції бути не може.
Таким чином, для прийняття оптимального рішення будь-якої економічної задачі необхідно побудувати її економіко-математичну модель, за структурою включає в собі систему обмежень, цільову функцію, критерій оптимальності та рішення.
Методика побудови економіко-математичної моделі полягає в тому, щоб економічну сутність завдання представити математично, використовуючи різні символи, змінні і постійні величини, індекси та інші позначення.
Всі умови задачі необхідно записати у вигляді рівнянь або нерівностей. Тому, в першу чергу необхідно визначити систему змінних величин, які можуть для конкретного завдання позначити шуканий обсяг виробництва продукції на підприємстві, кількість перевезеного вантажу постачальниками конкретним споживачам.
2.2. Постановка задач оптимізації
У загальному вигляді завдання оптимізації, або завдання визначення екстремуму, ставиться таким чином.
Нехай задані:
функція f (X), визначена на множині O Í R N ;
безліч D Í R N.
Знайти точку Y = (y 1, y 2 ,..., y N) Î D, в якій функція f (X) досягає екстремального (мінімального або максимального) значення, тобто
f (X) = extr f (X) і Y Î D.
Функція f (X) називається цільовою функцією, змінні X - керованими змінними, D - допустимим множиною і будь-який набір значень Y керованих змінних, що належить D (Y Î D), - допустимим рішенням задачі оптимізації.
Зрозуміло, що шукана точка Y, в якій f (X) досягає свого екстремуму, повинна належати перетинанню області визначення O функції f (X) і допустимого безлічі D (YÎ O Ç D). Якщо безлічі O і D збігаються з усім простором R N (O = D = R N), то таке завдання називається завданням на безумовний екстремум. Якщо хоча б одна з множин O або D є власним підмножиною простору R N (O Ì R N, D Ì R N) або безлічі O і D перетинаються (O Ç D ¹ Æ), то таке завдання називається завданням на умовний екстремум, в іншому випадку (O Ç D = Æ) точка екстремуму Y не існує. Підкреслимо один приватний випадок: якщо безлічі O і D перетинаються в одній точці Y, то ця точка Y є єдиним допустимим рішенням.
Зазвичай в задачі умовного екстремуму задається не саме допустиме безліч рішень D, а система співвідношень, його визначальна,
y j (X 1, х 2, х N) £ (=, ³) 0, j = 1, 2, ... М,
тобто
D = {X: yj (X) £ (=, ³) 0, j = 1, 2, ... , M} Í R N,
або безліч D може одночасно задаватися як в явному вигляді, тобто допустиме рішення Х має належати деякій області P Ì R N, так і системою обмежень.
III. Методи лінійного програмування.
3.1. Загальна і типова задача в лінійному програмуванні.
Оптимізаційна задача - це економіко-математична задача, яка полягає в знаходженні оптимального (максимального чи мінімального) значення цільової функції, причому значення змінних повинні належати деякій області допустимих значень.
У самому загальному вигляді завдання математично записується так:
U = f (X) ® max; X Î W,
Де X = (Х1, Х2, ..., Хn);
W - область допустимих значень змінних Х1, Х2, ..., Хn;
f (X) - цільова функція.
Для того, щоб вирішити задачу оптимізації, досить знайти її оптимальне рішення, тобто вказати X () Î W таке, що f (X ()) ³ f (X), при будь-якому X Î W, або для випадку мінімізації - що f (X ()) ≤ f (X), при будь-якому X Î W .
Оптимізаційна задача є нерозв'язною, якщо вона не має оптимального рішення. Зокрема, завдання максимізації буде нерозв'язна, якщо цільова функція f (X) не обмежена зверху на допустимому безлічі W.
Методи рішення оптимізаційних завдань залежать як від виду цільової функції f (X), так і від будови допустимого безлічі W. Якщо цільова функція в задачі є функцією n змінних, то методи рішення називають методами математичного програмування.
У математичному програмуванні прийнято виділяти такі основні завдання в залежності від виду цільової функції f (X) і від області W:
· Завдання лінійного програмування, якщо f (X) і W лінійні;
· Задачі цілочислового програмування, якщо ставиться умова цілочисельності змінних Х1, Х2, ..., Хn;
· Задачі нелінійного програмування, якщо форма f (X) носить нелінійний характер.
Завдання лінійного програмування.
Завданням лінійного програмування називається завдання дослідження операцій, математична модель якої має вигляд:
f (X) = å СjXj ® max (min);
å aij xj = bi, iÎI, IÍM = {1, 2, ... m};
å aij xj £ bi, iÎM;
Xj ³ 0, jÎJ, JÍN = {1, 2, ... n}.
При цьому система лінійних рівнянь і нерівностей, що визначає допустиму кількість рішень задачі W, називається системою обмежень задачі лінійного програмування, а лінійна функція f (X) називається цільовою функцією або критерієм оптимальності.
Будь-яку задачу лінійного програмування можна звести до задачі лінійного програмування у канонічній формі. Для цього в загальному випадку потрібно вміти зводити задачу максимізації до задачі мінімізації; переходити від обмежень нерівностей до обмежень рівностей і замінювати змінні, які не підкоряються умові неотрицательности. Максимізація деякою функції еквівалентна мінімізації тієї ж функції, взятої з протилежним знаком, і навпаки.
Правило приведення завдання лінійного програмування до канонічного виду полягає в наступному:
1) якщо у вихідній задачі потрібно визначити максимум лінійної функції, то слід змінити знак і шукати мінімум цієї функції;
2) якщо в обмеженнях права частина негативна, то слід помножити це обмеження на -1;
3) якщо серед обмежень є нерівності, то шляхом введення додаткових невід'ємних змінних вони перетворюються в рівності;
4) якщо деяка змінна Хk не має обмежень по знаку, то вона замінюється (в цільовій функції і у всіх обмеженнях) різницею між двома новими невід'ємними змінними::
Xk = X `k - X l, де l - вільний індекс, X `k ³ 0, Xk ³ 0.
3.2. Постановка задачі лінійного програмування
Під терміном «транспортні завдання» розуміється широке коло завдань не тільки транспортного характеру. Спільним для них є, як правило, розподіл ресурсів, що знаходяться у m виробників (постачальників), але n споживачам цих ресурсів.
На автомобільному транспорті часто зустрічаються такі завдання, пов'язані з транспортним:
· Прикріплення споживачів ресурсу до виробників;
· Прив'язка пунктів відправлення до пунктів призначення;
· Взаємна прив'язка вантажопотоків прямого і зворотного напрямів;
· Окремі завдання оптимального завантаження промислового обладнання;
· Оптимальний розподіл обсягів випуску промислової продукції між заводами-виробниками.
Транспортним завданням притаманні такі особливості:
· Розподілу підлягають однорідні ресурси;
· Умови задачі описуються тільки рівняннями;
· Всі змінні виражаються в однакових одиницях виміру;
· У всіх рівняннях коефіцієнти при невідомих дорівнюють одиниці;
· Кожна невідома зустрічається тільки в двох рівняннях системи обмежень.
Транспортні задачі можуть вирішуватися симплекс-методом.
3.3. Рішення транспортної задачі
| Потужності постав- ників 140 | Потужності споживачів | U i | ||||
| 18 | 15 | 32 | 45 | 30 | ||
| 30 | 10 | 7 / 15 | 14 | 8 / 5 | 7 / 10 | 0 |
| 40 | 12 | 8 | 10 | 8 / 40 | 15 | 0 |
| 25 | 6 / 18 | 10 | 10 | 12 | 14 / 7 | -7 |
| 45 | 16 | 10 | 8 / 32 | 12 | 16/13 | -9 |
| Vj | -1 | 7 | -1 | 8 | 7 | |
Початковий розподіл виберемо за методом найменших вартостей. Порядок заповнення клітин: (3,1), (1,2), (4,3). (2,4), (1,5), (1,4), (3,5), (4,5)
Сумарні витрати:
f (x) = 6'18 +7'15 +8'32 +8'5 +8'40 +7'10 +14'7 +16'13 = 1107
Розглянемо процес знаходження потенціалів для даного розподілу.
Покладемо, Ui = 0 Þ V2 = U1 + C12 = 7; V5 = U1 + C15 = 7 = U3 +14 = U4 +16 Þ U3 = -7, U4 = -9; V3 = U4 + C43 = -1; V4 = U2 +8 = U1 +8 Þ U2 = U1 = 0; V4 = 8.
Знайдемо оцінки: d ij = (U i + c ij)-V j:
11 0 15 0 0
(Dij) = 13 1 11 0 8
0 -4 4 -3 0
8 -6 0 -5 0
Даний план не є оптимальним, тому що є негативні оцінки.
Побудуємо контур перерозподілу для клітини (4,2). Найменша поставка в вершині контуру зі знаком "-" дорівнює 13, тому проведемо перерозподіл поставок, зменшивши поставки в клітинах зі знаком "-" на 13 і збільшивши постачання в клітинах зі знаком "+" на 13. результати поставлені в таблиці 2.
| Потужності постав- ників 140 | Потужності споживачів | U i | ||||
| 18 | 15 | 32 | 45 | 30 | ||
| 30 | 10 | 7 / 2 | 14 | 8 / 5 | 7 / 23 | 0 |
| 40 | 12 | 8 | 10 | 8 / 40 | 15 | 0 |
| 25 | 6 / 18 | 10 | 10 | 12 | 14 / 7 | -7 |
| 45 | 16 | 10/13 | 8 / 32 | 12 | 16 | -3 |
| Vj | -1 | 7 | 5 | 8 | 7 | |
Сумарні витрати:
f (x) = 6'18 +7'2 +10'13 +8'32 +8'5 +8'40 +7-23 +14-7 = 1127
Покладемо U1 = 0
V2 = U1 + C12 = 7 = U4 +10 Þ U4 = -3
V3 = U4 +8 = 5; V4 = U1 +8 = 8 = U2 +8 Þ U2 = 0
V5 = U1 +7 = 7 = U3 +14 Þ U3 = -7
V1 = U3 +6 = -1
dij = (Ui + Cij)-Vj
9 0 9 0 0
(Dij) = 11 1 5 0 8
0 -3 -2 -3 0
14 0 0 1 6
Наявність негативних оцінок свідчить про те, що план не є оптимальним. Побудуємо контур перерозподілу для клітини (3,2). Найменша поставка в вершині контуру зі знаком "-" дорівнює 2. Зробимо перерозподіл поставок. Результати представимо у таблиці 3.
| Потужності постав- ників 140 | Потужності споживачів | U i | ||||
| 18 | 15 | 32 | 45 | 30 | ||
| 30 | 10 | 7 | 14 | 8 / 5 | 7 / 25 | 0 |
| 40 | 12 | 8 | 10 | 8 / 40 | 15 | 0 |
| 25 | 6 / 18 | 10 / 2 | 10 | 12 | 14 / 5 | -7 |
| 45 | 16 | 10/13 | 8 / 32 | 12 | 16 | -7 |
| Vj | -1 | 7 | 5 | 8 | 7 | |
Сумарні витрати:
f (x) = 6'18 +10'2 +10'13 +8'32 +8'5 +8'40 +7'25 +14'7 = 1119
Покладемо, U1 = 0 Þ V4 = 8, V5 = 7; V4 = U2 +8 Þ U2 = 0
V5 = U3 +14 Þ U3 = 7-14 = -7; V1 = -7 +6 = -1; V2 = -7 +10 = +3
V2 = U4 +10 Þ U4 = 3-10 = -7; v3 = -7 +8 = 1
9 4 13 0 0
(Dij) = 13 5 9 0 8
2 0 2 -3 0
10 0 0 -3 2
Наявність негативних оцінок свідчить про те, що план не є оптимальним. Побудуємо контур перерозподілу для клітини (3,4).
Найменша поставка в клітці зі знаком "-" дорівнює 5. Зробимо перерозподіл поставок результати представимо в таблиці 4.
| Потужності постав- ників 140 | Потужності споживачів | U i | ||||
| 18 | 15 | 32 | 45 | 30 | ||
| 30 | 10 | 7 | 14 | 8 | 7 / 30 | 0 |
| 40 | 12 | 8 | 10 | 8 / 40 | 15 | 0 |
| 25 | 6 / 18 | 10 / 2 | 10 | 12 / 5 | 14 | -4 |
| 45 | 16 | 10/13 | 8 / 32 | 12 | 16 | -4 |
| Vj | 2 | +6 | 4 | 8 | 7 | |
Сумарні витрати:
f (x) = 7'30 +8'40 +6'18 +10'2 +12'5 +10'13 +8'32 = 1104
U1 = 0 Þ V5 = 7; U2 = 0 Þ V4 = 8 = U3 +12 Þ U3 =- 4 Þ
V1 = 6-4 = 2, V2 = 10-4 = +6 = U4 +10; V3 = -4 +8 = +4
8 1 10 0 0
(Dij) = 10 2 6 0 8
0 0 2 0 3
10 0 0 0 5
Матриця оцінок (dij) не містять негативних величин Þ цей план є оптимальним, тому що С34 = 0, а клітка (3,4) не є коми, то даний план не є єдиним. Вартість перевезень за цим планом, як було розраховано раніше, дорівнює f (x) = 1104.
3.6. Симплекс-метод розв'язання задач лінійного програмування.
Симплекс-метод дозволяє відмовитися від методу перебору при вирішенні задач лінійної оптимізації, є основним чисельним методом вирішення завдань лінійного програмування і дозволяє за менше число кроків, ніж у методі перебору, отримати рішення.
Реалізація алгоритму симплекс-методу.
1. Записати завдання в канонічній формі: замінити всі обмеження-нерівності з позитивною правої;
2. Розділити змінні на базисні і вільні: перенести вільні змінні в праву частину обмежень-нерівностей.
3. Висловити базисні змінні через вільні: вирішити систему лінійних рівнянь (обмежень-нерівностей) - відносно базисних змінних;
4. Перевірити неотрицательности базисних змінних: переконатися в позитивності вільних членів у виразах для базисних змінних. Якщо це не так, повернутися до пункту 2, вибираючи інший варіант поділу змінних на базисні і вільні.
5. Висловити функцію мети через вільні змінні: базисні змінні, що входять у функцію, виразити через вільні змінні;
6. Обчислити отримане базисне рішення і функцію цілі на ньому: прирівняти до 0 вільні змінні;
7. проаналізувати формулу функції мети: коли всі коефіцієнти вільних змінних позитивні (негативні), то знайдене базисне рішення буде мінімальним (максимально) і завдання вважається вирішеною;
8. Визначити включається в базис і исключаемую з базису змінні: якщо не всі коефіцієнти при вільних змінних у функції мети позитивні (негативні), то слід вибрати вільну змінну, що входить у функцію мети з максимальним за модулем негативним (позитивним) коефіцієнтом, та збільшувати її до тих пір, поки яка-небудь з базисних змінних не стане рівною 0. Вільну змінну розглядаємо як нову базисну змінну (включається в базис), а базисну змінну розглядаємо як нову базисну змінну (исключаемую з базису);
9. Використовуючи новий поділ змінних на базисне і вільне, повернутися до пункту 3 та повторювати всі етапи до тих пір, поки не буде знайдено оптимальне рішення.
На закінчення відзначимо, що визначення оптимального рішення розпадається на два етапи:
· Перебування будь-якого припустимого рішення з позитивним вільним членом;
· Визначення оптимального рішення, що дає екстрему цільової функції.
IV. Методи нелінійного програмування.
4.1. Основні поняття, постановка і методи розв'язання задачі нелінійного програмування.
Нелінійне програмування (планування) - математичні методи відшукання максимуму або мінімуму функції при наявності обмежень вигляді нерівностей або рівнянь. Максимізуючи (мінімізуючи) функція являє собою прийнятий критерій ефективності вирішення задачі, відповідний поставленої мети. Він носить назву цільової функції. Обмеження характеризує наявні можливості вирішення задачі.
Цільова функція або хоча б одне з обмежень нелінійне (тобто на графіках зображується не прямими-кривими-лініями) суть рішення задач нелінійного програмування полягає в тому, щоб знайти умови, що звертають цільову функцію в мінімум чи максимум. Рішення, що задовольняє умові завдання й відповідне наміченої мети, називається оптимальним планом. Нелінійне програмування служить для вибору найкращого плану розподілу обмежених ресурсів з метою вирішення поставленого завдання. У загальному вигляді постановка задачі нелінійного програмування зводиться до наступного. Умови завдання видаються за допомогою системи нелінійних рівнянь або нерівностей, що виражають обмеження, що накладається на використання наявних ресурсів.
Z1 (X1, X2 ,..., Xn) ³ 0;
Z2 (X1, X2 ,..., Xn) ³ 0;
...................................
Zm (X1, X2 ,..., Xn) ³ 0;
при Xi ³ 0,
де Z1, Z2, ..., Zm - відповідні функції, що характеризують умова вирішення поставленого завдання (обмеження); Хi - шукані величини, що містять рішення задачі.
Цільова функція задається у вигляді:
y = f (X1, X2, ..., Xn).
Причому принаймні одна з функцій y, Z1, Z2, ..., Zm - нелінійна.
Методами нелінійного програмування вирішуються завдання розподілу неоднорідних ресурсів.
Нехай є m різнорідних ресурсів, які передбачається реалізувати для бізнесу в n регіонах країни.
Відомі оціночні можливості (ймовірності) почати бізнес в j-му регіоні (Pj), а також ефективності використання i-го ресурсу в n-му регіоні (wij).
Розподіл ресурсів по регіонах характеризується так званим параметром управління (hij):
hij = 0, якщо i-й ресурс не направляється до j-й регіон,
1, якщо i-й ресурс направляється в j-й регіон.
Необхідно розподілити ресурси по регіонах таким чином (вибирати такі значення hij), щоб величина повної ймовірності досягнення мети Рц була максимальною:
Рц = å Pj [1 - P (1-hijwij] = max.
Повинно виконуватися також обмеження
S hij = 1, i = 1, 2, ... m
Обмеження означає, що кожен з m ресурсів обов'язково повинен призначатися в будь-якій з регіонів.
Динамічне програмування (планування)
Динамічне програмування (планування) служить для вибору найкращого плану виконання багатоетапних дій. Для багатоетапних дій характерно протікання в часі. Крім дій, природно носять багатоетапний характер (наприклад, перспективне планування), у ряді завдань вдаються до штучного розчленування на етапи, з тим, щоб зробити можливим застосування методу динамічного програмування.
У загальному вигляді постановка задачі динамічного програмування зводиться до наступного:
Є деяка керована операція (цілеспрямована дія), що розпадається (природно або штучно) на m кроків - етапів. На кожному кроці здійснюється розподіл і перерозподіл беруть участь в операції з метою поліпшення її результату в цілому. Ці розподілу в динамічному програмуванні називаються управліннями операцією і позначаються літерою U. Ефективність операції в цілому оцінюється тим же показником, що і ефективність її управління W (U).
При цьому ефективність управління W (U) залежить від всієї сукупності управлінь на кожному кроці операції:
W = W (U) = W (U1, U2, ..., Um).
Управління, при якому показник W досягає максимуму, називається оптимальним управлінням. Оптимальне керування позначається буквою U.
Оптимальне управління багатокрокових процесом складається із сукупності оптимальних крокових управлінь:
U = (U1, U2, ..., Um).
Завдання динамічного програмування - визначити оптимальне керування на кожному кроці Ui (i = 1, 2, ..., m) і, тим самим, оптимальне управління всією операцією в цілому.
У більшості практичних завдань приймається, що показник ефективності операції W в цілому являє собою суму ефективності дій на всіх етапах (кроках) операції:
W = å wi,
де wi - ефективність операції на i-му кроці.
При цьому у випадку оптимального управління
W = max åwi
Істота рішення динамічного програмування полягає в наступному:
- Оптимізація проводиться методом послідовних наближень (ітерацій) у два кола, на початку від останнього кроку операції до першого, а потім навпаки від першого до останнього;
- На першому колі, йдучи від подальших кроків до попередніх, знаходиться так зване умовне оптимальне керування;
- Умовне оптимальне керування вибирається таким, щоб всі попередні кроки забезпечували максимальну ефективність подальшого кроку, іншими словами, на кожному кроці є таке управління, яке забезпечує оптимальне продовження операції; цей принцип вибору управління називається принципом оптимальності;
- Так триває до першого кроку, але оскільки перший крок не має попереднього, то отримане для нього умовне оптимальне керування втрачає свій умовний характер і стає просто оптимальним управлінням, яке ми шукаємо;
- Друге коло оптимізації починається з першого кроку, для якого оптимальне керування відомо.
Маючи для всіх кроків після нього умовне оптимальне керування, ми знаємо, що необхідно робити на кожному наступному кроці. Це дає нам можливість послідовно переходити від умовних до оптимальних управлінням дл всіх наступних кроків, що забезпечує оптимальність операції в цілому.
Нехай є m типів різних вантажів, якими необхідно завантажити транспортний засіб таким чином, щоб загальна вартість вантажу W була максимальною. Вартість вантажу є функцією отгрузопод'емності транспортного засобу:
W = f (G)
Відомі маси вантажів i-го типу Рi та їх вартості Ci.
Необхідно завантажити транспортний засіб таким чином, щоб загальна вартість вантажу була максимальною:
W = fm (G) = max å xiCi,
де xi - кількість предметів вантажу i-го типу, що завантажуються в транспортний засіб; xi виступає тут у якості управління (Ui = xi)
Обмежуючими умовами є:
å xi Pi £ G
xi = 0, 1, 2 ...
Перша умова вимагає, щоб загальна маса вантажу не перевищувала вантажопідйомності транспортного засобу, а друге - щоб предмети, що становлять вантаж різних типів, були неподільні.
Поняття критерію оптимальності
Формулювання критеріїв економічних систем є необхідною передумовою оптимізації планових рішень. У загальному випадку під критерієм оптимальності розуміється ознака, на підставі якого проводиться оцінка, порівняння альтернатив, класифікація об'єктів і явищ. Критерій оптимальності функціонування економічної системи - це один з можливих критеріїв (ознак) її якості, а саме ту ознаку, по яким функціонування системи визнається найкращим з можливих варіантів її функціонування. У сфері прийняття економічних рішень критерій оптимальності - це показник, що виражає граничну міру економічного ефекту прийнятого господарського рішення для порівняльної оцінки можливих рішень вибору найкращого з них. Найбільш часто використовується максимум прибутку або мінімум витрат.
Критерій оптимальності зазвичай носить кількісний характер і показує, наскільки один з варіантів краще чи гірше іншого. Порядковий критерій визначає лише те, що один варіант краще або гірше іншого. Математичної формою критерію оптимальності в економіко-математичних моделях є цільова функція, екстремальне значення якої характеризує гранично допустиму ефективність діяльності модельованого об'єкта.
Якщо за классифицирующие ознака прийняти рівень спільності, то для економічної системи існують глобальний критерій оптимального розвитку в масштабі Землі, соціально-економічний критерій, а також «глобальний» (узагальнений) і локальний критерій оптимальності в приватних системах моделей.
Якщо за классифицирующие ознака взяти математичну формулювання, то критерії поділяються на скалярні і векторні, адитивні і мультиплікативні, інтегральні критерії в тимчасовому аспекті та інтегральні в просторовому аспекті та ін
Можлива класифікація моделей з тимчасового аспекту, зі способів формування критеріїв, за типом застосовуваних вимірників, за способами використання критеріїв.
Сутність глобального і локального критеріїв оптимальності.
Найчастіше термін «глобальний» застосовується або по відношенню до критерію однорівневої моделі, або по відношенню до критерію «верхньої» моделі багаторівневої системи моделей. В останньому випадку, разом з глобальним, фігурують локальні критерії моделей нижніх рівнів, що відображають інтереси окремих господарських ланок, соціальних груп.
Поділ критеріїв на глобальний і локальний може бути віднесено до будь-якої ієрархічно побудованій системі моделей, наприклад моделі галузі або підприємства.
Глобального критерієм може бути дана словесна формулювання, а для вирішення практичних завдань планування і управління таке формулювання деталізується і представляється у вигляді сукупності більш конкретних локальних критеріїв. Математично глобальний критерій прийнято формулювати у вигляді скалярної цільової функції, яка узагальнено виражає все різноманіття цілей або у вигляді векторної функції, що представляє собою набір зводяться один до одного приватних цільових функцій.
Більшість багаторівневих систем мають два рівні: верхній і нижній. Система моделей виробничої програми підприємства включає в себе моделі розрахунку загальнозаводських показників і показників окремих цехів. При формуванні узагальнених критеріїв повинні враховуватися і місцеві (приватні інтереси), а локальні критерії - підпорядковані узагальненому.
Складність системи цілей пояснюється різноманіттям завдань суспільного розвитку і розвитку систем, а також тим, наскільки великі й інтенсивні зовнішні зв'язки даної системи.
Підприємство є елементом більш загальних систем: галузі промисловості, ек5ономіческого регіону. Тому діяльність підприємства оцінюється в рамках будь-якої з цих загальних систем за відповідними показниками. З цієї точки зору підприємство повинно найкращим чином відповідати цілям зовнішньої системи. З іншого боку, саме підприємство - складна система, елементами якої є колективи його працівників (бригади, відділи, служби, ділянки і т.д.) і окремі індивідууми. Отже, діяльність підприємства повинна бути спрямована на забезпечення найкращих інтересів колективу та його працівників. Система критеріїв оптимальності діяльності підприємства включають обсяги випуску основних типів продукції вищої категорії якості, продуктивність праці, собівартість продукції, фонд заробітної плати.
Система критеріїв галузевої системи включає задоволення суспільних потреб виробленої продукції, економію ресурсів, впровадження досягнень науково-технічного прогресу, забезпечення надійності виконання планових завдань. Зовнішні зв'язки галузевих систем, а значить, і комплекси їх цілей, ускладнюються фактором часу, просторовою організацією, поєднанням різних підходів і аспектів планування.
Множинність цілей розвитку систем істотно ускладнює планування, особливо, якщо цілі різноспрямовані, і наближення до одних цілям видаляє систему від досягнення інших. Таким чином виникає завдання їх узгодження. Відшукування найкращих рішень за кількома критеріями називається багатокритеріальної або векторної оптимізацією.
Векторна оптимізація
Математичне формулювання задачі векторної оптимізації:
Нехай X = {x1, ..., x N} (j = 1, N) - вектор змінних, зазвичай передбачається неотрицательности вектора змінних X ³ 0, функціональна взаємозв'язок змінних встановлюється певними співвідношеннями, на які накладаються обмеження:
gi (X) £ bi (i = 1, M).
Функціонування системи оцінюється певними критеріями, записуваними у вигляді цільових функцій fr (X) (r = 1, K). Безліч критеріїв можна представити у вигляді векторної цільової функції
F (X) = {f1 (X), ...> fr (X)}.
Щоб мінімізувати приватний критерій fr (X), досить максимізувати-fr (X), так як min fr (X) =- max (-fr (X)). Тому надалі передбачається, що кожний компонент векторного критерію максимізує. Завдання багатоцільової оптимізації записується як векторна задача математичного програмування (ВЗМП)
F (X) = {f1 (X), ...> fr (X)} (max),
gi (X) £ bi (i = 1, M),
X ³ 0.
Будемо розглядати ВЗМП для випадку, коли точки оптимуму X * r (r = 1, K), отримані при рішенні задачі по кожному критерію fr (r = 1, K) не збігаються (випадок їх збігу зустрічається вкрай рідко і таке завдання не представляє інтересу ). Тому з математичної точки зору завдання є некоректною, тому що якщо один з критеріїв досягає свого оптимуму, то поліпшення за іншими компонентами векторного критерію неможливо. Звідси випливає, що рішенням ВЗМП може бути тільки якесь компромісне рішення.
Особливістю завдань векторної оптимізації є наявність в області допустимих значень області компромісів, в якій неможливо одночасне поліпшення всіх критеріїв. Належні області компромісів плани називають ефективними, або оптимальними за Парето (по імені італійського економіста, вперше сформулював проблему векторної оптимізації і принцип оптимальності рішення).
Поняття перевагу плану. План X ° не гірше плану X `, якщо
fr (X °) ³ fr (X `) (r = 1, K). Якщо серед цих нерівностей хоча б одне суворе, то план X ° краще (краще) X `, тобто при переході від X ° до X `значення жодного критерію не погіршився і хоча б одного критерію покращився. План X ° оптимальний за Парето (ефективний), якщо він допустимий і не існує іншого плану X `, для якого fr (X °) ³ fr (X`) (r = 1, K), і хоча б для одного критерію виконується суворе нерівність.
До загальної формулюванні багатокритеріальної задачі можуть зводитися завдання різного змісту, які можна підрозділити на чотири типи.
1. Завдання оптимізації на множині цілей, кожна з яких повинна бути врахована при виборі оптимального рішення. Прикладом може служити задача складання плану роботи підприємства, в якій критеріями служить ряд економічних показників.
2. Завдання оптимізації на множині об'єктів, якість функціонування кожного з яких оцінюється самостійним критерієм. Якщо якість функціонування кожного об'єкта оцінюється кількома критеріями (векторним критерієм), то таке завдання називається багатовекторною. Прикладом може служити задача розподілу дефіцитного ресурсу між декількома підприємствами. Для кожного підприємства критерієм оптимальності є ступінь задоволення його потреб в ресурсі чи інший показник, наприклад, величина прибутку. Для плануючого органу критерієм виступає вектор локальних критеріїв підприємств.
3. Завдання оптимізації на множині умов функціонування. Задано спектр умов, в яких належить працювати об'єкту, і стосовно до кожного умові якість функціонування оцінюється деякими приватним критерієм.
4. Завдання оптимізації на множині етапів функціонування. Розглядається функціонування об'єктів на деякому інтервалі часу, розбитому на кілька етапів. Якість управління на кожному етапі оцінюється приватним критерієм, а на безлічі етапів - загальним векторним критерієм. Прикладом може бути розподіл квартального плану цеху по декадах. У кожній декаді необхідно забезпечити максимальне завантаження. У результаті вийде критерій максимізації завантаження в кожній декаді кварталу.
Багатокритеріальні задачі можна також класифікувати за іншими ознаками: за варіантами оптимізації, за кількістю критеріїв, за типами критеріїв, за співвідношенням між критеріями, за рівнем структуризації, наявності фактора невизначеності.
При розробці методів розв'язання векторних задач доводиться вирішувати ряд специфічних проблем.
Проблема нормалізації виникає у зв'язку з тим, що локальні критерії мають, як правило, різні одиниці і масштаби виміру, і це робить неможливим їх безпосереднє порівняння. Операція приведення критеріїв до єдиного масштабу і безрозмірного увазі носить назву нормування. Найбільш поширеними способами нормування є заміна абсолютних значень критеріїв їх безрозмірними відносними величинами
fr (X) = fr (X),
f * r
або відносними значеннями відхилень від оптимальних значень критеріїв f * r
fr (X) = f * r - fr (X),
f * r
Проблема вибору принципу оптимальності пов'язана з визначенням властивостей оптимального рішення і вирішенням питання - в якому сенсі оптимальне рішення перевершує всі інші.
Проблема врахування пріоритету критеріїв встає, якщо локальні критерії мають різну значущість. Необхідно знайти математичне визначення пріоритету та ступінь його впливу на рішення задачі.
Проблема обчислення оптимуму виникає, якщо традиційні обчислювальні схеми та алгоритми непридатні для вирішення завдань векторної оптимізації.
Вирішення перелічених проблем йде в декількох напрямках. Основні напрямки:
Методи, засновані на згортання критеріїв в єдиний;
Методи, що використовують обмеження на критерії;
Методи цільового програмування;
Методи, засновані на відшуканні компромісного рішення;
Методи, в основі яких лежать людино-машинні процедури прийняття рішень (інтерактивне програмування).
У методах, заснованих на згортання критеріїв, з локальних критеріїв формується один. Найбільш поширеним є методу лінійної комбінації приватних критеріїв. Нехай задано вектор вагових коефіцієнтів критеріїв a = {a1, ..., ar}, що характеризують важливість належного критерію, åar = 1, ar ³ 0 (r = 1, K). Лінійна скалярізованная функція являє собою суму приватних критеріїв, помножених на вагові коефіцієнти. Завдання математичного програмування стає однокритерійним і має вигляд
F ° = åarfr (X) (max),
qi (X) £ bi (I = 1, M),
X ³ 0.
Критерії в згортку можуть бути унормовані. Рішення, отримане в результаті оптимізації скалярізованного критерію ефективно.
До недоліків методу можна віднести те, що малим збільшення коефіцієнтів відповідають більші приросту функції, тобто рішення задачі нестійкий, а також необхідність визначення вагових коефіцієнтів.
Напрямок методів, які використовують обмеження на критерії включає два підходи:
1) метод провідного критерію;
2) методи послідовного застосування критеріїв (метод послідовних поступок, метод обмежень).
У методі провідного критерію всі цільові функції крім однієї переводяться в розряд обмежень. Нехай g = (g2, g3, ..., Gк-1) - вектор, компоненти якого є нижні межі відповідних критеріїв. Завдання буде мати вигляд
F = f1 (max)
fr ³ gr (r = 2, K),
qi (X) £ bi (I = 1, M),
X ³ 0.
Отримане цим методом рішення може не бути ефективним, тому необхідно перевірити його приналежність області компромісів.
Метод провідного критерію застосовується в таких завданнях, як мінімізація повних витрат за умови виконання плану з виробництва різних видів продукції, максимізація випуску комплектних наборів при обмеженні на спожиті ресурси.
Алгоритм методу послідовних поступок:
1. Критерії нумеруються в порядку убування важливості.
2. Визначається значення f * 1. Особою, яка приймає рішення, встановлюється величина поступки D1 за цим критерієм.
3. Вирішується завдання за критерієм f2 з додатковим обмеженням f1 (X) ³ f * 1 - D1.
Далі пункти 2 і 3 повторюються для критерію f2, ..., fk.
Отримане рішення не завжди належить області компромісів.
При вирішенні завдань методами цільового програмування передбачається наближення значення кожного критерію до певної величиною fr, тобто досягнення певної мети. У самому загальному вигляді завдання цільового програмування формулюється як задача мінімізації сум відхилень цільових функцій від цільових значень з нормованими вагами.
d (F (X), F) = (å w R êf R (X) - f R ê p) (Min),
де F = {f 1 ,...., f R} - вектор цільових значень,
W = {w 1 ,..., w R} - вектор ваг, зазвичай å w R = 1, w R ³ 0
(R = 1, K), значення p знаходяться в межах 1 £ p £ ¥,
d (.) - відстань (міра відхилення) між F (X) і F.
У багатьох випадках застосування цільового програмування вважають p = 1. Наприклад, у лінійному цільовому програмуванні функції f R (X) (r = 1, K) і