А І Українець - Задачі лінійного та нелінійного програмування - страница 1

Страницы:
1  2 

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ ХАРЧОВИХ ТЕХНОЛОГІЙ

ЗАДАЧІ ЛІНІЙНОГО ТА НЕЛІНІЙНОГО ПРОГРАМУВАННЯ

Навчальний посібник

За загальною редакцією професора А. І. Українця

Рекомендовано Міністерством освіти і науки України як навчальний посібник для студентів вищих навчальних закладів

Київ НУХТ 2007

УДК 681.3.06(07)

Гриф надано Міністерством освіти і науки України 08.07.05р., лист № 14/18.2 - 1603

Рецензенти: В. М. Левикін, завідувач кафедри інформаційно-керуючих систем Харківського національного університету радіоелектроніки д-р техн. наук, проф.

В. Я. Жуйков, декан факультету електроніки Національного технічного університету України «Київський політехнічний інститут» д-р техн. наук, проф.

Задачі лінійного та нелінійного програмування: Навч. Посібник / А. І. Українець, А. М. Гуржій, В. В. Самсонов та ін. - К.: НУХТ, 2007. - 208 с.

Висвітлено математичні методи і алгоритми розв'язання задач безумовної та умовної оптимізації відповідно до програм курсів «Математичні методи оптимізації та дослідження операцій», «Інформатика та обчислювальна техніка», «Числові методи» та ін. Особливу увагу приділено обчислювальним алгоритмам. Викладено практичні задачі, які розглядаються на всіх етапах: від постановки задачі до аналізу отриманого результату.

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

© А.І. Українець, А.М. Гуржій, В.В. Самсонов, Т.О. Кривець, В.Я. Городенська

© НУХТ, 2007

ВСТУП

В останні 50 - 60 років у науці та практиці значна увага приділяється розв'язанню задач оптимізації в різних областях господарської діяльності і в першу чергу в економічному плануванні і організації виробництва.

Задачі оптимізації належать до найбільш поширених дисциплін прикладної математики, які в тому чи іншому обсязі занесені до навчальних планів майже всіх університетів. Навчальними планами передбачено вивчення моделей і(або) методів розв'язання оптимізаційних задач. При цьому особливо важливе значення має самостійна робота студентів під час вивчення курсу, оскільки розв'язання тих чи інших задач збагачує їх досвід значно більше, ніж отримані теоретичні знання.

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

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

Розділи посібника містять:

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

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

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

шостий - методи розв'язання транспортної задачі, окремі приклади розв'язання таких задач;

сьомий і восьмий - задачі нелінійного програмування; дев'ятий - задачі сітьового планування.

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

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

Розділ 1. МЕТОДИ ОПТИМІЗАЦП. ЗАГАЛЬНІ ПОЛОЖЕННЯ 1.1. Основи побудови моделей задач оптимізації

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

Моделлю називається деякий об'єкт-замінник, який за певних умов може замінювати об'єкт-оригінал, відтворюючи властивості, які нас цікавлять, та характеристики оригіналу. Вона має істотні переваги та зручності (наочність, доступність дослідів, легкість оперування з нею та ін.). Наприклад, глобус є моделлю Землі, фотографія особи — моделлю власника паспорта, опудало - моделлю тварини.

Математичною моделлю об'єкта є абстрактна чи знакова модель, побудована засобами математики ( наприклад, у вигляді системи рівнянь, графу, логічних побудов та

ін).

Моделювання у вузькому розумінні - процес розроблення моделі. В широкому аспекті моделювання є обов'язковою, неминучою дією у будь-якій доцільній діяльності, воно організовує її, являє собою аспект, а не частину цієї діяльності. Модель, як будь-яка реальність, має свій «життєвий цикл», тобто спочатку в ній виникає потреба, а потім її розробляють, вона проходить етап досліджень, еволюційний етап розвитку, експлуатацію i т. ін. На етапі побудови вирішальну роль відіграють неформалізовані евристичні здібності людини, на інших етапах, крім формалізованих витоків, також присутній інтелект людини.

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

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

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

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

1. Вивчення системи (наприклад, процесу виробництва за певною технологією).

2. Постановка задачі, розроблення документа, що містить опис і характеристики об'єкта чи процесу, зазначення мети, яка повинна бути досягнута внаслідок розв'язання задачі, і умов, що визначають функціонування даного об'єкта чи процесу, опис вхідної та вихідної інформації, можливі підходи до вирішення проблеми.

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

4. Вибір методу розв'язання — аналіз виду і структури розробленої математичної моделі, що дає можливість зробити висновки про клас оптимізаційної задачі і можливий метод її розв'язання. За відсутності потрібних методів розробляється новий метод.

5. Розроблення алгоритму — детальний опис вибраного методу розв'язання задачі з урахуванням усіх можливих ситуацій і логічних переходів за послідовністю певних кроків. Для наочності і логічності послідовність усіх операцій зображується графічно у вигляді схеми алгоритму.

6. Складання програми універсальною мовою програмування. Вибір мови програмування зумовлений вимогами до програмного та технічного забезпечення (зокрема типу ЕОМ).

7. Налагодження програми — виправлення синтаксичних та логічних помилок у програмі.

8. Тестування програми — перевірка програми на контрольному прикладі.

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

10. Коригування моделі, методу, алгоритму і програми у разі потреби.

11. Підготовка та введення реальної інформації для розв'язання задачі. Важливість цього етапу зумовлена відповідальністю за підготовку та використання вірогідної інформації. Лише за умов використання вірогідної інформації можна розраховувати на одержання оптимальних розв'язків задачі. Важливість цього етапу також пов'язана з великим обсягом підготовчої роботи. Понад 80 % усіх витрат припадає саме на підготовку початкових даних.

12. Виконання розрахунків на ЕОМ.

13. Аналіз одержаних результатів і розроблення рекомендацій щодо удосконалення процесу.

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

15. Оцінювання економічного ефекту від впровадження.

У процесі розв'язання певних задач ті чи інші етапи можуть пропускатися. Наприклад, якщо одержано задачу, для розв'язання якої існують уже готові програми, то етапи 4—8 не виконуються. Для застосування оптимізаційних методів економічна задача повинна бути формалізована у вигляді економіко-математичної моделі.

Математична модель — це опис процесу чи об'єкта за допомогою математичних засобів (рівностей чи нерівностей).

Математична модель задачі оптимізації складається з цільової функції та обмежень задачі. Функція, максимум або мінімум якої шукається, називається цільовою.

Цільова функція - це деякий алгебраїчний вираз, який відображає мету (ціль) задачі. Наприклад, у лінійному алгебраїчному виразі

c1x1 + c2x2 max (1.1) x1 та x2 можуть визначати невідомий об'єм виробництва продукції відповідно першого і

другого видів;    c1 та c2 прибуток від реалізації одиниці продукції відповідно першого і

другого видів. Тоді c1x1 прибуток від реалізації продукції першого виду; c2 x2 — прибуток

від реалізації продукції другого виду; c1 Х1 + c2x2 - це загальний прибуток від реалізації всього обсягу продукції першого і другого видів.

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

Наприклад:

[аЛЛхЛ + a12x2 < h;

і 11 і     12 2     15 (1.2)

[а21 + а22Х2 < Ь2;

x1 > 0, x2 > 0, (1.3) де b1, b2 - ліміти обмежувальних ресурсів першого і другого видів; aij — норми витрат i -го

виду ресурсів (сировини, матеріалів і т. ін.) на виробництво j - ї продукції; x1, x2 — обсяг виробництва продукції відповідно першого і другого видів.

Обмеження (1.2) свідчать про те, що витрати матеріалів не можуть перевищувати запаси.

Обмеження (1.3) відображають умови невід'ємності невідомих задачі. Завдання полягає у визначенні таких змінних x1, x2, які б задовольняли всі обмеження задачі (1.1) — (1.3) і при яких цільова функція (1.1) досягне свого максимуму.

Можна по-різному побудувати математичну модель однієї і тієї самої задачі оптимізації. Від вдалої її побудови часто залежить успіх розв'язання задачі.

Для побудови математичної моделі конкретної задачі оптимізації потрібно:

1. Визначити мету, якої треба досягти в результаті розв'язання задачі.

2. Визначити невідомі величини.

3. Побудувати цільову функцію, що відображає мету даної задачі. Цільова функція містить невідомі задачі з деякими коефіцієнтами.

4. Виявити умови задачі і записати їх у вигляді обмежень. При цьому обмежувальні ресурси відобразити у правій частині обмежень, а витрати цих ресурсів — у лівій.

5. Проаналізувати одержану математичну модель і визначити, до якого класу задач оптимізації вона належить.

1.2. Класифікація задач оптимізації

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

1. Безумовної оптимізації (без обмежень), у яких не накладаються обмеження на допустимі значення змінних.

2. Умовної оптимізації (з обмеженнями), в яких на змінні накладено обмеження.

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

Розглянемо задачі умовної оптимізації.

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

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

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

• задачі опуклого програмування — мінімізації опуклих функцій на опуклій множині розв'язків;

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

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

дискретних значень із заданої множини: Xj є{al,a2,---,ak}. Наприклад, потужність підприємства визначається кількістю технологічних ліній і може набувати лише фіксованих значень: Х] є {0,100,200,300};

• задачі булевого програмування, в яких змінні можуть набувати лише двох значень: або нуля, або одиниці: x j є {0,1},

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

• задачі параметричного програмування, в яких коефіцієнти залежать від виду певного параметра. Наприклад, цільова функція Z = (1 t)Х1 + tx2 залежить від значень параметра

t;

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

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

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

витрат на компоненти Ui: g = U1 + U2 + ... + Un, а витрати на компоненти виражені степеневою функцією Ui = ct^'12...С". Тут коефіцієнт ci — додатна стала, показникистепеня a   — довільні числа, а параметри проекту t1,t2,...,tm є додатними змінними (за

таких умов функція g називається поліномом);

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

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

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

1.3. Приклади задач оптимізації Приклад 1. На верстатах І, ІІ, ІІІ, IV виготовляють деталі двох видів - А і В. Тривалість оброблення кожної деталі на кожному з верстатів, тривалість роботи

верстатів протягом одного циклу виробництва наведено в табл. 1.1. Прибуток, одержуваний

від реалізації однієї деталі виду А, становить 4, В — 1 грн.

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

був максимальний?

Таблиця 1.1

Тривалість оброблення деталі, хв_\   Тривалість роботи

 

 

 

верстатів протягом

 

 

 

одного циклу

Показники

А

В

виробництва, хв

Верстат 1

1

2

16

Верстат 2

2

3

26

Верстат 3

1

1

10

Верстат 4

3

1

24

Прибуток, грн

4

1

 

Розв 'язання.   Мета задачі — максимізація прибутку від реалізації деталей кожного

виду.

Головним моментом побудови математичної моделі є ідентифікація змінних. Нехай x1

— кількість виробів виду А, x2 — кількість виробів виду B, або у компактнішому записі: x.

— кількість виробів j -го виду, де j = 1 і 2.

Тепер визначимо цільову функцію, яка виражає прибуток від реалізації виробів A і B f = 4x1 + 1x2. Оскільки мета задачі — максимізація прибутку, то цільова функція f = 4 x1 + 1x2 повинна прямувати до максимуму.

Обмеження задач: якщо припустити, що виготовляють x1 одиниць виробів виду A і

x2 — виду B, то для виготовлення такої кількості виробів потрібно витратити 1x1 + 2x2 часу роботи   верстата 1. Оскільки тривалість роботи   верстата 1 протягом одного циклу виробництва не може перевищувати 16, то має виконуватись нерівність x1 + 2x2 < 16. Аналогічні нерівності можна записати для верстатів 2, 3 і 4:

2x1 + 3x2 < 26;

x1 + x2 < 10;

3x1 + x2 < 24.

Оскільки кількість виготовлюваних виробів не може бути від'ємною величиною, то

x1 > 0; x2 > 0. Отже, математична модель задачі набуде вигляду:максимізувати при обмеженнях

x1 + 2 x2 < 16;

1      2 (1.5)

x1 + x2 < 10;

3x1 + x2 < 24;

x1 > 0; x2 > 0. (1.6)

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

Приклад 2. Торговельна організація планує реалізацію двох груп товарів. Фонди, виділені для цих товарів, відповідно становлять 80 і 50 тис. грн. Рівень витрат, пов'язаний зі збереженням товару першої групи, — 2, другої групи — 1 %, рівень прибутку — відповідно 3 і 2 %. Гранично допустимі витрати, пов'язані зі збереженням товару, становлять 2,6 тис. грн. Враховуючи закупівлю товарів вартістю, вищою за виділені фонди, потрібно знайти план товарообігу, при якому торговельна організація отримає максимальний прибуток.

Розв'язання. Мета задачі — максимізація прибутку торговельної організації від товарообігу.

Страницы:
1  2 


Похожие статьи

А І Українець - Задачі лінійного та нелінійного програмування

А І Українець - Принципи формування механізму інноваційного розвитку вітчизняних машинобудівних підприємств