Федеральне агентство з освіти
Новокузнецький філія-інститут
ГОУ ВПО «Кемеровський державний університет»
кафедра інформаційних систем та управління ім. В.К. Буторина
Курсова робота
Завдання математичного програмування
(Варіант 4)
Новокузнецьк 2010
Зміст
Введення
1. Поняття математичного програмування
2. Поняття лінійного програмування. Види завдань лінійного програмування
3. Поняття нелінійного програмування
4. Динамічне програмування
Лабораторна робота № 1 (Завдання лінійного програмування)
Лабораторна робота № 2 (Рішення завдання ЛП засобами табличного процесора Excel)
Лабораторна робота № 3 (Рішення транспортної задачі)
Лабораторна робота № 4 (рішення задач нелінійного програмування)
Лабораторна робота № 5 (задача динамічного програмування про оптимальний розподіл інвестицій)
Лабораторна робота № 5 (задача динамічного програмування про вибір оптимального шляху в транспортній мережі)
Висновок
Список літератури
Введення
Перехід від адміністративних до економічних методів управління виробництвом, розвиток ринкових відносин, поширення договірних цін - все це націлює економічні служби на пошук найкращих господарських рішень, що забезпечують максимум результатів або мінімум витрат. Необхідність пошуку таких рішень обумовлюється, насамперед, існуванням обмежень на фактори виробництва, у межах яких підприємства (окремі виробники) постійно функціонують. Якби ці обмеження були відсутні, то нічого було б вибирати, не було б і варіантів рішень.
Відомо, що певний вид продукції можна зробити, використовуючи різні технологічні способи; в деяких виробництвах можлива взаємозамінність матеріалів; один і той же тип обладнання може бути використаний для виробництва різних видів продукції і т.п.
Як краще організувати виробництво, за якими цінами вигідно виробляти продукцію, як найкраще використовувати виробничі ресурси, які вивільняються і т.п.?
На всі ці питання дозволяє отримати відповідь математичне програмування, що є дієвим інструментом прийняття рішень.
Математичне програмування являє собою математичну дисципліну, що займається вивченням екстремальних завдань і розробкою методів їх вирішення.
У загальному вигляді математична постановка екстремальної задачі полягає у визначенні найбільшого або найменшого значення цільової функції f (x1, х2 ,.........., xn) при умовах gi (x1, х2 ,....... ..., xn) ≤ bi, де f і gi - задані функції, a bi - деякі дійсні числа.
Залежно від властивостей функцій f і gi математичне програмування можна розглядати як ряд самостійних дисциплін, що займаються вивченням і розробкою методів вирішення певних класів завдань.
Перш за все завдання математичного програмування діляться на завдання лінійного і нелінійного програмування. При цьому якщо всі функції f і gi лінійні, то відповідна задача є задачею лінійного програмування. Якщо ж хоча б одна із зазначених функцій нелінійна, то відповідне завдання є завданням нелінійного програмування. Найбільш вивченим розділом математичного програмування є лінійне програмування. Для вирішення завдань лінійного програмування розроблено цілий ряд ефективних методів, алгоритмів і програм. Серед задач нелінійного програмування найбільш глибоко вивчені завдання опуклого програмування. Це завдання, в результаті рішення яких визначається мінімум опуклою (або максимум увігнутою) функції, заданої на опуклому замкненому множині.
У свою чергу, серед завдань опуклого програмування більш докладно досліджені задачі квадратичного програмування. У результаті вирішення таких завдань потрібно в загальному випадку знайти максимум (або мінімум) квадратичної функції за умови, що її змінні задовольняють деякій системі лінійних нерівностей або лінійних рівнянь або деякій системі, яка містить як лінійні нерівності, так і лінійні рівняння.
В задачах цілочислового програмування невідомі можуть приймати тільки цілочисельні значення.
Завдання, процес знаходження рішення якої є багатоетапним, відноситься до задачі динамічного програмування.
1. Поняття математичного програмування
Математичне програмування - це математична дисципліна, в якій розробляються методи відшукання екстремальних значень цільової функції серед безлічі її можливих значень, що визначаються обмеженнями.
Наявність обмежень робить задачі математичного програмування принципово відмінними від класичних завдань математичного аналізу з відшукання екстремальних значень функції. Методи математичного аналізу для пошуку екстремуму функції в задачах математичного програмування виявляються непридатними.
Для вирішення задач математичного програмування розроблені і розробляються спеціальні методи і теорії. Тому що при вирішенні цих завдань доводиться виконувати значний обсяг обчислень, то при порівняльній оцінці методів велике значення надається ефективності та зручності їх реалізації на ЕОМ.
Математичне програмування можна розглядати як сукупність самостійних розділів, що займаються вивченням і розробкою методів вирішення певних класів завдань.
Залежно від властивостей цільової функції і функції обмежень всі завдання математичного програмування діляться на два основні класи:
задачі лінійного програмування,
задачі нелінійного програмування;
задачі динамічного програмування.
Якщо цільова функція і функції обмежень - лінійні функції, то відповідна завдання пошуку екстремуму є задачею лінійного програмування. Якщо хоча б одна із зазначених функцій нелінійна, то відповідна завдання пошуку екстремуму є завданням нелінійного програмування.
2. Поняття лінійного програмування. Види завдань лінійного програмування
Лінійне програмування (ЛП) - один з перших і найбільш детально вивчених розділів математичного програмування. Саме лінійне програмування стало тим розділом, з якого і почала розвиватися сама дисципліна "математичне програмування". Термін "програмування" в назві дисципліни нічого спільного з терміном "програмування (тобто складання програми) для ЕОМ" не має, тому що дисципліна "лінійне програмування" виникла ще до того часу, коли ЕОМ стали широко застосовуватися для вирішення математичних, інженерних, економічних та ін завдань.
Термін "лінійне програмування" виник в результаті неточного перекладу англійського "linear programming". Одне із значень слова "programming" - складання планів, планування. Отже, правильним перекладом англійського "linear programming" було б не "лінійне програмування", а "лінійне планування", що більш точно відображає зміст дисципліни. Однак, терміни лінійне програмування, нелінійне програмування, математичне програмування і т.д. в нашій літературі стали загальноприйнятими і тому будуть збережені.
Отже, лінійне програмування виникло після другої світової війни і стало швидко розвиватися, привертаючи увагу математиків, економістів та інженерів завдяки можливості широкого практичного застосування, а також математичної стрункості.
Можна сказати, що лінійне програмування застосовно для вирішення математичних моделей тих процесів і систем, в основу яких може бути покладена гіпотеза лінійного представлення реального світу.
Лінійне програмування застосовується при вирішенні економічних завдань, у таких завданнях як управління і планування виробництва; в задачах визначення оптимального розміщення обладнання на морських суднах, у цехах; в задачах визначення оптимального плану перевезень вантажу (транспортна задача); в задачах оптимального розподілу кадрів і т. д.
Завдання лінійного програмування (ЛП), як уже зрозуміло з сказаного вище, полягає в знаходженні мінімуму (або максимуму) лінійної функції при лінійних обмеженнях.
Існує кілька методів вирішення завдань ЛЗ. У даній роботі будуть розглянуті деякі з них, зокрема:
Графічний метод розв'язання задачі ЛП;
Симплексний метод;
Рішення завдання ЛП засобами табличного процесора Excel;
3. Поняття нелінійного програмування
У більшості інженерних завдань побудова математичної моделі не вдається звести до задачі лінійного програмування.
Математичні моделі в задачах проектування реальних об'єктів або технологічних процесів повинні відображати реальні протікають в них фізичні і, як правило, нелінійні процеси. Змінні цих об'єктів або процесів пов'язані між собою фізичними нелінійними законами, такими, як закони збереження маси або енергії. Вони обмежені граничними діапазонами, що забезпечують фізичну реалізованість даного об'єкта або процесу. В результаті, більшість завдань математичного програмування, які зустрічаються в науково-дослідних проектах і в завданнях проектування - це завдання нелінійного програмування (НП).
У даній роботі буде розглядатися такий метод вирішення завдань НП, як метод множників Лагранжа.
Метод множників Лагранжа дозволяє відшукувати максимум (або мінімум) функції при обмеженнях-равенствах. Основна ідея методу полягає в переході від завдання на умовний екстремум до задачі відшукання безумовного екстремуму деякої побудованої функції Лагранжа.
4. Динамічне програмування
Динамічне програмування являє собою математичні апарат, що дозволяє швидко знаходити оптимальне рішення у випадках, коли аналізована ситуація не містить факторів невизначеності, але є велика кількість варіантів поведінки, що приносять різні результати, серед яких необхідно вибрати найкращий. Динамічне програмування підходить до вирішення певного класу задач шляхом розкладання на частини, невеликі та менш складні завдання. В принципі, завдання такого роду можуть бути вирішені шляхом перебору всіх можливих варіантів і вибору серед них найкращого, однак часто такий перебір дуже ускладнений. У цих випадках процес прийняття оптимального рішення може бути розбитий на кроки (етапи) та досліджено за допомогою методу динамічного програмування.
Рішення задач методами динамічного програмування проводиться на основі сформульованого Р. Е. Беллманом принципу оптимальності: оптимальне поведінка має тим властивістю, що яким би не було первісний стан системи і початкове рішення, наступне рішення має визначати оптимальну поведінку відносно стану, отриманого в результаті первинного рішення.
Таким чином, планування кожного кроку повинно проводиться з урахуванням загальної вигоди, одержуваної по завершенні всього процесу, що і дозволяє оптимізувати кінцевий результат за обраним критерієм.
Разом з тим динамічне програмування не є універсальним методом рішення. Практично кожне завдання, яке вирішується цим методом, характеризується своїми особливостями і вимагає проведення пошуку найбільш прийнятної сукупності методів для її вирішення. Крім того, великі обсяги і трудомісткість вирішення багатокрокових завдань, що мають безліч станів, призводять до необхідності відбору задач малої розмірності якого використання стислій інформації.
Динамічне програмування застосовується для вирішення таких завдань, як: розподіл дефіцитних капітальних вкладень між новими напрямками їх використання; розробка правил управління попитом і запасами; складання календарних планів поточного і капітального ремонтів обладнання та його заміни; пошук найкоротших відстаней на транспортній мережі і т.д.
Нехай процес оптимізації розбитий на n кроків. На кожному кроці необхідно визначити два типи змінних - змінну стану S і змінну управління X. Мінлива S визначає, в яких станах може виявитися система на даному k-му кроці. Залежно від S на цьому кроці можна застосувати деякі управління, які характеризуються змінною X. Застосування управління X на k-му кроці приносить певний результат Wk (S, Xk) і переводить систему в деякий новий стан S '(S, Xk). Для кожного можливого стану на k-му кроці серед всіх можливих управлінь вибирається оптимальне управління X * k таке, щоб результат, який досягається за кроки з k-го по n-й, виявився оптимальним. Числова характеристика цього результату називається функцією Беллмана Fk (S) і залежить від номера кроку k і стану системи S.
Всі рішення завдання розбиваються на два етапи. На першому етапі, який називають умовною оптимізацією, відшукуються функція Беллмана і оптимальні управління для всіх можливих станів на кожному кроці, починаючи з останнього.
Після того, як функція Беллмана і відповідні оптимальні управління знайдені для всіх кроків з n-го по перший, проводиться другий етап рішення задачі, який називається безумовною оптимізацією.
У загальному вигляді завдання динамічного програмування формулюється так: потрібно визначити таке управління X *, що переводить систему з початкового стану S0 в кінцевий стан Sn, при якому цільова функція F (S0, X *) приймає найбільше (найменше) значення.
Особливості математичної моделі динамічного програмування полягають в наступному:
задача оптимізації формулюється як кінцевий багатокроковий процес управління;
цільова функція є аддитивной і дорівнює сумі цільових функцій кожного кроку
;
вибір управління Xk на кожному кроці залежить тільки від стану системи до цього кроку Sk-1 і не впливає на попередні кроки (немає зворотного зв'язку);
стан системи Sk після кожного кроку управління залежить тільки від попереднього стану системи Sk-1 і цього керуючого впливу Xk (відсутність післядії) і може бути записано у вигляді рівняння стану:
;
на кожному кроці управління Xk залежить від кінцевого числа керуючих змінних, а стан системи Sk залежить від кінцевого числа змінних;
оптимальне управління X * являє собою вектор, який визначається послідовністю оптимальних покрокових управлінь:
X *= (X * 1, X * 2, ..., X * k, ..., X * n),
число яких і визначає кількість кроків завдання.
Умовна оптимізація. Як вже зазначалося вище, на даному етапі відшукуються функція Беллмана і оптимальні управління для всіх можливих станів на кожному кроці, починаючи з останнього відповідно до алгоритму зворотного прогонки. На останньому n-му кроці знайти оптимальне управління X * n і значення функції Беллмана Fn (S) не складно, так як
Fn (S) = max {Wn (S, Xn)},
де максимум шукається по всіх можливих значень Xn.
Подальші обчислення проводяться згідно рекурентного співвідношення, що зв'язує функцію Беллмана на кожному кроці з цієї ж функцією, але обчисленої на попередньому кроці:
Fk (S) = max {Wk (S, Xk) + Fk +1 (S '(S, Xk))}. (1)
Цей максимум (або мінімум) визначається по всіх можливих для k і S значенням змінної управління X.
Безумовна оптимізація. Після того, як функція Беллмана і відповідні оптимальні управління знайдені для всіх кроків з n-го по перший (на першому кроці k = 1 стан системи дорівнює її початкового стану S0), здійснюється другий етап вирішення завдання. Знаходиться оптимальне управління на першому кроці X1, застосування якого призведе систему в стан S1 (S, x1 *), знаючи яке можна, користуючись результатами умовної оптимізації, знайти оптимальне управління на другому кроці, і так далі до останнього n-го кроку.
Лабораторна робота № 1 (Завдання лінійного програмування)
Завдання:
Для заданої математичної постановки задачі ЛП, прийнявши додатково умова неотрицательности змінних, виконати наступні дії:
Вирішити задачу графічним методом;
Привести задачу до канонічної форми запису;
Скласти симплексних таблицю;
Провести рішення задачі симплексним методом ручним способом або з використання комп'ютера;
Здійснити постановку двоїстої задачі ЛП;
Отримати рішення двоїстої завдання з отриманої раніше симплексного таблиці і провести аналіз отриманих результатів;
Перевірити результати рішення в табличному процесорі Excel;
Скласти звіт з приведення результатів по кожному пункту.
Ресурси | Запаси | Продукція | |
Р1 | Р2 | ||
S1 | 18 | 0.2 | 3 |
S2 | 13.1 | 0.7 | 2 |
МВ | 23 | 2.3 | 2 |
Прибуток від одиниці продукції в У.Е. | 3 | 4 |
Рішення:
Графічний метод. Для побудови багатокутника рішень перетворимо вихідну систему
, Одержимо
зобразимо граничні прямі.
Лінійна функція F = f (x) є рівнянням прямої лінії c1x1 + c2x2 = const. Побудуємо графік цільової функції при f (x) = 0. для побудови прямий 3x1 + 4x2 = 0 будуємо радіус-вектор N = (3, 4) і через точку 0 проводимо пряму, перпендикулярну йому. Побудовану пряму F = 0 переміщаємо паралельно самій собі в напрямку вектора N.
З малюнка 1 випливає, що опорної по відношенню до збудованого багатокутнику рішень ця пряма стає в точці B, де функція F приймає максимальне значення. Точка В лежить на перетині прямих 0,7 x1 + 2x2 ≤ 13,1 і 2,3 x1 + 2x2 = 23 / Для визначення її координат вирішимо систему рівнянь:
Оптимальний план завдання: х1 = 6.187; х2 = 4.38, підставляючи значення х1 і х2 в цільову функцію, отримуємо Fmax = 3 * 6.187 +4 * 4.38 = 36.08.
Таким чином, для того, щоб отримати максимальний прибуток у розмірі 36.06 доларів, необхідно запланувати виробництво 6 од. продукції P1 та 4 од. продукції P2.
Канонічний вид завдання ЛП. Запишемо в канонічній формі завдання розподілу ресурсів. Додавши до вихідної системи обмежень невід'ємні змінні х3 ≥ 0, х4 ≥ 0, х5 ≥ 0, маємо:
При цьому в далі одержуваному вирішенні змінні х3 і х4 будуть відповідати обсягам невикористаного сировини S1 і S2, а х5 - невикористаним машинному часу.
Симплексна таблиця ЛП. У разі базисних змінних {x3, x4, x5} початкова симплекс таблиця буде виглядати:
Таблиця 1.
-Х1 | -Х2 | ||
х3 = | 0,2 | 3 | 18 |
х4 = | 0,7 | 2 | 13,1 |
х5 = | 2,3 | 2 | 23 |
f (x) = | 3 | 4 |
Вона вже відповідає опорному плану x (0) = [0 0 18 13,1 23] Т (стовпець вільних членів).
Симплексний метод розв'язання задачі ЛП. Для того, щоб опорний план був оптимальний, при максимізації цільової функції необхідно, щоб коефіцієнти в рядку цільової функції були невід'ємними, тобто при пошуку максимуму ми повинні звільнитися від негативних коефіцієнтів у рядку f (x).
Алгоритм симплекс методу.
1. Вибір дозволяє стовпця. Як дозволяючого вибираємо стовпець з мінімальним коефіцієнтом у рядку f (x). У даному прикладі це стовпець х2.
2. Вибір роздільної рядка. Для вибору роздільної рядка (дозволяє елемента) серед позитивних коефіцієнтів дозволяє стовпця вибираємо той елемент, для якого відношення коефіцієнтів у стовпці вільних членів до коефіцієнта в дозвільному стовпці мінімально. Дозволяє елемент розраховується за формулою:
У даному прикладі такої рядком буде рядок х3, т.к. відношення коефіцієнта у стовпці вільних членів до коефіцієнта в дозвільному стовпці мінімально.
3. Заміна базису. Для переходу до наступної симплексного таблиці (наступного опорному плану з великим значенням цільової функції) робимо крок модифікованого жорданова виключення з дозволяючим елементом arl, при якому базисна змінна xr стає вільною і водночас вільна мінлива xi стає базисної.
3.1 на місці дозволяє елемента ставиться 1 і ділиться на дозволяє елемент;
3.2 інші елементи розв'язного стовпця змінюють знак на протилежний і діляться на дозволяє елемент;
3.3 інші елементи роздільною рядки діляться на дозволяє елемент;
3.4. всі інші елементи симплексного таблиці обчислюються за формулою:
3.5. елементи правого стовпця і нижнього рядка перераховуються за тим же принципом, що і елементи в центральній частині таблиці.
Симплексна таблиця, розрахована за алгоритмом:
Таблиця 2.
-Х1 | -Х3 | ||
х2 = | 0,067 | 0,3 | 6 |
х4 = | 0,57 | -0,67 | 1,1 |
х5 = | 2,17 | -0,67 | 11 |
f (x) = | -3,27 | 1,3 | 72,6 |
Наступним дозволяючими стовпцем буде стовпець х1, а роздільної рядком - х4. Далі діємо за тим же алгоритмом.
Таблиця 3.
-Х4 | -Х3 | 1 | |
х2 = | -0,1 | 0,24 |