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

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

Федеральне агентство з освіти

Новокузнецький філія-інститут

ГОУ ВПО «Кемеровський державний університет»

кафедра інформаційних систем та управління ім. В.К. Буторина

Курсова робота

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

(Варіант 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

5,87

х1 =

1,75

-1,17

1,03

х5 =

-3,8

1,88

5,8

f (x) =

5,7

-2,5

35,06

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

Таблиця 4.


-Х4

-Х5

1

х2 =

0,39

-0,13

4,4

х1 =

-0,61

0,6

6,19

Х3 =

-2

0,53

1,3

f (x) =

0,64

1,3

36,08

Кінцева симплексная таблиця:

Всі коефіцієнти в рядку цільової функції позитивні, тобто ми знайшли оптимальне рішення.

Таким чином, у точці x1 = 4, x2 = 6, x3 = 1,3, x4 = 0, x5 = 0 цільова функція приймає максимальне значення f (x) = 36.

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

Постановка двоїстої задачі ЛП. Визначити значення двоїстих оцінок можна наступним чином. якщо деякий i-тий ресурс використовується не повністю, тобто є резерв, значить додаткова змінна в обмеженні для даного ресурсу буде більше нуля. Очевидно, що при збільшенні загального машинного часу не відбулося б збільшення цільової функції. Отже, машинне час не впливає на прибуток і для третього обмеження двоїста мінлива y3 = 0. Таким чином, якщо з даного ресурсу є резерв, то додаткова змінна буде більше нуля, а двоїста оцінка даного обмеження дорівнює нулю.

У даному прикладі обидва види сировини використовувалися повністю, тому їх додаткові змінні дорівнюють нулю (в підсумковій таблиці симплексного змінні х3 і х4 є вільними, отже х3 = х4 = 0). Якщо ресурс використовувався повністю, то його збільшення або зменшення вплине на обсяг своєї продукції і, отже, на величину цільової функції. Значення двоїстої оцінки при цьому знаходиться в симплекс-таблиці на перетині рядка цільової функції зі стовпцем даної додаткової змінної.

Отримати рішення двоїстої завдання з отриманої раніше симплексного таблиці і провести аналіз отриманих результатів. Формулювання і результати вирішення вихідної і двоїстої задач розподілу ресурсів наведено в таблиці 4.

Таблиця 4.

Вихідна завдання ЛП

Двоїста задача ЛП

Математична постановка

Позначення та інтерпретація параметрів задачі

xj, j = - Кількість виробленої продукції j-го виду;

f (x) - загальний прибуток від реалізації продукції

yi, i = - Вартість одиниці i-го ресурсу;

- Вартість усіх наявних ресурсів

Економічна інтерпретація язадачі

Скільки і якої продукції необхідно зробити, щоб пр заданих вартостях cj, j = еддініци продукції і розмірах наявних ресурсів bi, i = максимізувати загальний прибуток?

Яка повинна бути ціна одиниці кожного з ресурсів, щоб при заданих їх кількостях bi, i = і величинах вартості одиниці продукції cj, j = мінімізувати загальну вартість затрат?

Результати рішення

Результуюча симплекс-таблиця


-Х4

-Х5

1


х2 =

...

...

4,4


х1 =

...

...

6,19


Х3 =

...

...

1,3


f (x) =

0,64

1,3

36,08


Основні змінні

х1 = 6,19

х2 = 4,4

додаткові змінні

х3 = 1,3

х4 = 0

х5 = 0







Додаткові змінні

y4 = 0

y5 = 0

основні змінні

y1 = 0,64

y2 = 1,3

y3 = 0

Інтерпретація додаткових змінних

xn +1, ...., xn + m - невикористане (резервне) кількість відповідного ресурсу (при наявність резервного ресурсу відповідна двоїста мінлива навна 0)

ym +1, ..., ym + n - наскільки зменшиться цільова функція при примусовому випуску одиниці даної продукції (якщо яка-небудь з основних змінних вихідної задачі дорівнює 0)

Перевірити результати рішення в табличному процесорі Excel. В Excel є надбудова «Пошук рішення», яка дозволяє вирішувати оптимізаційні задачі.

Використавши цю надбудову для вирішення нашої задачі ЛП, отримуємо наступний результат:

Таблиця 6.

Змінні

Цільова функція


Вид продукції

Р1

Р2

Прибуток


Значення

6,1875

4,3844

36,1


Прибуток від од. прод.

3

4

макс


Обмеження

Типи ресурсів

Р1

Р2

Витрата ресурсів

Знак

Запас ресурсів

Сировина S1

0,2

3

14,390625

<=

18

СирьеS2

0,7

2

13,1

<=

13,1

Машинне час

2,3

2

23

<=

23

Але при застосуванні надбудови «пошук рішення» до завдання, двоїстої даній задачі ЛП, приходимо до висновку, що рішення отримане за допомогою надбудови не сходиться з рішенням з симплекс-таблиці:

Таблиця 7.

Змінні


ім'я

x1

x2

f (x)

значення

6,19

4,38

36,1

коеф-ти f (x)

3

4

макс


Обмеження

двойствен. Оцінки

x1

x2

ліва частина

знак

права частина

y

1

8

3

62,653125

<=

18

1,333333

2

0,7

2

13,1

<=

13,1

0

3

2,3

2

23

<=

23

0

Обмеження двоїстої задачі

Цільова функція двоїстої задачі

10,66667

4

24

Лабораторна робота № 2 (Рішення завдання ЛП засобами табличного процесора Excel)

Для заданої змістовної постановки задачі ЛП виконати наступні дії:

Здійснити математичний запис задачі ЛП;

Вирішити завдання з використання надбудови Excel «Пошук рішення»;

Привести математичну постановку двоїстої задачі ЛП;

Отримати рішення двоїстої завдання ЛП з використанням надбудови Excel «Пошук рішення»;

Отримати рішення задачі в припущенні целочисленности змінних;

Зробити аналіз отриманих результатів і дати їх змістовну інтерпретацію.

Завдання: До складу раціону годівлі входять три продукти: сіно, силос і концентрати, що містять такі поживні речовини: білок, кальцій та вітаміни. Вміст поживних речовин в грамах в 1 кілограмі відповідного продукту харчування і мінімально необхідну їх споживання задані таблицею:

Продукти

Живильні речовини


білок

кальцій

вітаміни

1. Сіно

5

6

2

2. Силос

2

4

1

3. Концентрати

18

3

1

Норма споживання

200

120

40


Визначити оптимальний режим годування, з умови мінімальної вартості, якщо ціна 1 кг продукту харчування відповідно становить: для сіна - 30коп., Для силосу-20 коп., Для концентрату - 50 коп.

Рішення

Здійснити математичний запис задачі ЛП. Складемо математичну модель. Позначимо через х1 - кількість одиниць сіна, через х2 - кількість одиниць силосу а через х3 - кількість одиниць концентрату. Функція витрат на покупку цих продуктів виглядає так: f (x) = 30x1 +20 x2 +50 x3 її необхідно мінімізувати. Необхідні норми споживання виражені у вигляді обмежень:


В результаті загальна постановка задачі ЛП має вигляд:

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

Після введення всіх даних вибираємо команду Сервіс / Пошук Рішення та, заповнюємо відкрилося діалогове вікно Пошук Рішення:

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

Далі вибираємо пункт «Параметри», щоб перевірити, які параметри задані для пошуку рішення. У вікні Параметри пошуку рішення можна змінювати умови та варіанти пошуку рішення досліджуваної задачі, а також завантажувати і зберігати оптимізуються моделі.

Для даної задачі досить встановити два прапорці «Лінійна модель» (тому що обмеження і цільова функція є лінійними за змінними) і «невід'ємні значення» (для виконання умов завдання ЛП).

Тепер завдання оптимізації підготовлена ​​повністю. Після натискання кнопки «Виконати» відкривається вікно «Результати пошуку рішення», яке повідомляє, що рішення знайдено.

Таблиця 9

Змінні

Цільова функція

Вид продукту

сіно

силос

концентрат

f (x)



значення

16,77

0,00

6,45

76,13



витрати на ед.прод.

3

2

4

min




Обмеження




Живильні речовини

сіно

силос

концентрат

витрата поживних

речовин

знак

необхідне споживання піт.веществ

білки

5

2

18

200,00

> =

200

кальцій

6

4

3

120,00

> =

120

вітаміни

2

1

1

40,00

> =

40

Привести математичну постановку двоїстої задачі ЛП. Двоїста задача ЛП визначається за формулою:

Математична постановка двоїстої задачі ЛП:

Отримати рішення двоїстої завдання ЛП з використанням надбудови Excel «Пошук рішення». До наявними даними додаються значення двоїстих змінних, комірка, яка містить формулу цільової функції двоїстої задачі, і осередки, що визначають ліві частини обмежень двоїстої задачі. Далі для рішення двоїстої завдання виконуємо за допомогою надбудови Excel «Пошук рішення». Отримуємо:

Таблиця 10

Змінні

Цільова функція

Вид продукту

сіно

силос

концентрат

f (x)

значення

16,77

0,00

6,45

76,13

витрати на ед.прод.

3

2

4

min



Обмеження





Живильні речовини

сіно

силос

концентрат

Ліва частина

знак

Права частина

Двоїсті оцінки

білки

5

2

18

200,00

> =

200

0,6

кальцій

6

4

3

120,00

> =

120

0

вітаміни

2

1

1

40,00

> =

40

0

Обмеження двоїстої функції


Цільова функція двоїстої задачі

3

1,2

10,8

120

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

Таблиця 11

Змінні

Цільова функція

Вид продукту

сіно

силос

концентрат

f (x)



значення

16

0

6

76



витрати на ед.прод.

3

2

4

min




Обмеження




Живильні речовини

сіно

силос

концентрат

витрата поживних

речовин

знак

необхідне споживання поживних

речовин

білки

5

2

18

200

> =

200

кальцій

6

4

3

120

> =

120

вітаміни

2

1

1

40

> =

40

З отриманого рішення очевидно, що для мінімізації витрат необхідно закуповувати 16 кг сіна і 6 кг концентрату, закупівля ж силосу недоцільна. При цьому споживання поживних речовин, таких як - білок, кальцій та вітаміни не зменшиться.

Лабораторна робота № 3 (Рішення транспортної задачі)

Для заданої матриці витрат С, вектора - стовпця запасів В в пунктах відправлення і вектора - рядки потреб А в пунктах призначення вирішити транспортну задачу і скласти звіт за наступними пунктами:

Здійснити математичний запис транспортної задачі;

Вирішити завдання за допомогою надбудови Excel «Пошук рішення»;

Змінити дані для отримання відкритої завдання і вирішити її.

2 3 4 2 4 140

С = 8 4 1 4 1 180

9 7 3 7 2 160

60 70 120 130 100

Рішення

Здійснити математичний запис транспортнойзадачи.Обозначим через хij кількість одиниць сировини, перевезеного з i-го пункту його отримання на j-те підприємство. Тоді умова доставки та вивезення необхідного і наявного сировини забезпечуються за рахунок виконання наступних рівностей:

x11 + x12 + x13 + x14 + x15 = 140

x21 + x22 + x23 + ​​x24 + x25 = 180

x31 + x32 + x33 + x34 + x35 = 160

x11 + x21 + x31 = 60

x 12 + x22 + x32 = 70

x 13 + x23 + ​​x33 = 120

x 14 + x24 + x34 = 130

x 15 + x25 + x35 = 100

При цьому загальна вартість перевезень складе

f (x) = 2x11 +3 +4 x12 x13 +2 x14 +4 x15 +8 x21 +4 x22 + x23 +4 x24 + x25 +9 x31 +7 x32 +3 x33 +7 x34 +2 x35

Таким чином, математична постановка даної транспортної задачі полягає в знаходженні такого неотрицательного рішення системи лінійних рівнянь, при якому цільова функція f (x) приймає мінімальне значення.

Вирішити завдання за допомогою надбудови Excel «Пошук рішення». Знаходимо оптимальний план постачань сировини і відповідні йому транспортні витрати в таблиці 12.

Таблиця 12

Пункти

відправлення

Пункти призначення


В1

В2

В3

В4

В5

Запаси

А1

2

3

4

2

4

140

А2

8

4

1

4

1

180

А3

9

7

3

7

2

160

Потреби

60

70

120

130

100


Транспортна таблиця

А1

140

0

0

0

0

140

А2

0

0

180

0

0

180

А3

0

0

0

0

160

160

Потреби

60

70

120

130

100






Транспортні витрати

780

Змінимо, дані для того, щоб отримати відкриту задачу. Для цього зменшимо запаси і збільшимо потреби, отримаємо:

Таблиця 13

Таблиця витрат

Пункти

відправлення

Пункти призначення


В1

В2

В3

В4

В5

Запаси

А1

2

3

4

2

4

140

А2

8

4

1

4

1

150

А3

9

7

3

7

2

100

Потреби

60

100

120

200

100


Транспортна таблиця

А1

0

0

0

140

0

140

А2

0

0

0

0

150

150

А3

0

0

0

0

100

100

Потреби

60

100

120

200

100






Транспортні витрати

630

Лабораторна робота № 4 (рішення задач нелінійного програмування)

Для заданої математичної постановки задачі НП (цільової функції f (x) і обмежень - рівностей) виконати наступні дії:

Знайти всі умовні екстремуми функцій методом множників Лагранжа і вибрати серед них глобальний мінімум (максимум);

Перевірити результати рішення в табличному процесорі Excel;

(1)

Метод множників Лагранжа

Необхідно перевести умова до виду

Складемо допоміжну функцію Лагранжа:

Для даної задачі отримаємо:

(2)

Диференціюємо дану функцію по х1, х2, x3, і , Отримаємо систему рівнянь:

(3)

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


Вирішивши це рівняння, отримуємо:

х1 = 2,25, х2 =- 1,25, x3 = 1,5, =- 1,5 і =- 3, F = 12

Точка екстремуму заданої функції f (x) - (х1, х2, x3), є точкою глобального мінімуму при заданих обмеженнях функції.

Рішення в табличному процесорі Excel. Перевіримо результати рішення в табличному процесорі Excel.

Рішення завдання за допомогою процесора Excel дало наступні результати:

Таблиця 13

х1

х2

x3


2,25

-1,25

1,50


Цільова функція

12,00



Обмеження

4,00

=

4


6,00

=

6

Рішення завдання обома методами дали однаковий результат.

Лабораторна робота № 5 (задача динамічного програмування про оптимальний розподіл інвестицій)

Завдання

Є чотири підприємства, між якими необхідно розподілити 100 тис. ум.од. коштів. Значення приросту випуску продукції на підприємствах в залежності від виділених коштів X представлені в таблиці. Скласти оптимальний план розподілу коштів, що дозволяє максимізувати загальний приріст випуску продукції.

Таблиця 14

X

g1

g2

g3

g4

0

0

0

0

0

20

14

17

22

20

40

26

20

21

33

60

35

32

37

46

80

52

61

67

30

100

61

72

58

42






Рішення

Етап I. Умовна оптимізація.

Крок 1. k = 4. Припускаємо, що всі кошти 100 ден.ед. передані на інвестування четвертого підприємства. У цьому випадку максимальна прибуток складе F4 (C4) = 46, дані представлені в таблиці 15.

Таблиця 15.

C4

x4

F4 (C4)

X *


0

20

40

60

80

100



0

0

-

-

-

-

-

0

0

20

-

20

-

-

-

-

20

20

40

-

-

33

-

-

-

33

40

60

-

-

-

46

-

-

46

60

80

-

-

-

-

30

-

30

80

100

-

-

-

-

-

42

42

100

Крок 2. k = 3. Визначаємо оптимальну стратегію інвестування в третє і четверте підприємства. При цьому рекурентне співвідношення Беллмана матиме вигляд:

.

На його підставі розраховуються дані таблиці 16

Таблиця 16.

C3

X3

F3 (C3)

X *


0

20

40

60

80

100



0

0 +0

-

-

-

-

-

0

0

20

0 +20

22 +0

-

-

-

-

22

20

40

0 +33

22 +20

21 +0

-

-

-

42

20

60

0 +46

22 +33

21 +20

37 +0

-

-

55

20

80

0 +30

22 +46

21 +33

37 +20

67 +0

-

68

20

100

0 +42

22 +30

21 +46

37 +33

67 +20

58 +0

87

20

Крок 3. k = 2. Визначаємо оптимальну стратегію інвестування в друге і третє підприємства. При цьому рекурентне співвідношення Беллмана матиме вигляд:

.

На його підставі розраховуються дані таблиці 3.

Таблиця 17.

C2

X2

F2 (C2)

X *


0

20

40

60

80

100



0

0 +0

-

-

-

-

-

0

0

20

0 +22

17 +0

-

-

-

-

22

0

40

0 +42

17 +22

20 +0

-

-

-

42

0

60

0 +55

17 +42

20 +22

32 +0

-

-

59

20

80

0 +68

17 +55

20 +42

32 +22

61 +0

-

72

20

100

0 +87

17 +68

20 +55

32 +42

61 +22

72 +0

87

0

Крок 4. k = 1. Визначаємо оптимальну стратегію інвестування в перше і інші підприємства. При цьому рекурентне співвідношення Беллмана матиме вигляд:

.

На його основі знаходяться дані таблиці 4.

Таблиця 18.

C1

X1

F1 (C1)

X *


0

20

40

60

80

100



0

0 +0

-

-

-

-

-

0

0

20

0 +48

14 +0

-

-

-

-

22

0

40

0 +93

14 +48

26 +0

-

-

-

42

0

60

0 +135

14 +93

26 +48

35 +0

-

-

59

0

80

0 +149

14 +135

26 +93

35 +48

52 +0

-

72

0

100

0 +160

14 +149

26 +135

35 +93

52 +48

61 +0

87

0

За даними останньої таблиці максимальних дохід з чотирьох підприємств склав 87 д.ед. При цьому перше і друге підприємства не принесуть ніякого доходу, в них недоцільно вкладати інвестиції. У 3-е підприємство потрібно вкласти 80 д.ед. В 4-е підприємство потрібно вкласти 20 д.ед. У підсумку залишиться 20-Виходить, що оптимальний план Х * (0, 0, 80, 20)

Лабораторна робота № 5 (задача динамічного програмування про вибір оптимального шляху в транспортній мережі)

Завдання

У запропонованій з початкового пункту (1) в кінцевий пункт (11). Вартість проїзду між окремими пунктами транспортної мережі придумати самостійно і транспортної мережі є кілька маршрутів по проїзду представити у відповідній таблиці (T (i, j)). Необхідно визначити оптимальний маршрут проїзду з пункту 1 до пункту 11 із мінімальними транспортними витратами.












Рисунок 2 - Транспортна мережа

Елементи матриці маршрутів транспортної мережі, а також вартість проїзду з пункту i в пункт j (tij) представлена ​​в таблиці 19.

Таблиця 19.

j

i

1

2

3

4

5

6

7

8

9

10

11

1

-

10

12

8

20

-

-

-

-

-

-

2

-

-

-

-

-

15

11

-

-

-

-

3

-

-

-

-

-

6

9

-

-

-

-

4

-

-

-

-

-

7

10

-

-

-

-

5

-

-

-

-

-

13

8

-

-

-

-

6

-

-

-

-

-

-

-

12

14

18

-

7

-

-

-

-

-

-

-

13

15

16

-

8

-

-

-

-

-

-

-

-

-

-

8

9

-

-

-

-

-

-

-

-

-

-

10

10

-

-

-

-

-

-

-

-

-

-

10

11

-

-

-

-

-

-

-

-

-

-

-

Рішення

Етап I. Умовна оптимізація.

Крок 1. k = 1. F1 (S) = ts10.

Таблиця 18.

S

J = 11

F (S)

J *

8

8

8

11

9

10

10

11

10

10

10

11

Крок 2. k = 2. Функціональне рівняння на даному кроці набуває вигляду:

.

Результати розрахунку за наведеною формулою наведені в таблиці:

Таблиця 19.

S

J = 8

J = 9

J = 10

F (S)

J *

6

12 +8

14 +10

18 +10

20

8

7

13 +8

15 +10

16 +10

21

8

Крок 3. k = 3. Функціональне рівняння на даному кроці набуває вигляду:

.

Результати розрахунку за наведеною формулою наведені в таблиці:

Таблиця 20.

S

J = 6

J = 7

F (S)

J *

2

15 +20

11 +21

32

7

3

6 +20

9 +11

26

6

4

7 +20

10 +21

27

6

5

13 +20

8 +21

29

7

Крок 4. k = 4. Функціональне рівняння на даному кроці набуває вигляду:

.

Результати розрахунку за наведеною формулою наведені в таблиці:

Таблиця 21.

S

J = 2

J = 3

J = 4

J = 5

F (S)

J *

1

10 +32

12 +26

8 +27

20 +29

35

4

Етап II. Безумовна оптимізація.

На етапі умовної оптимізації отримано, що мінімальні витрати на проїзд з пункту 1 до пункту 11 становлять F4 (1) = 35, що досягається наступним рухом по магістралях. З пункту 1 слід попрямувати в пункт 4, потім з нього в пункт 6, потім в пункт 8 і з нього в пункт 11. Таким чином, оптимальний маршрут буде J * (1, 4, 6; 8; 11)

Висновок

У курсовій роботі були розглянуті рішення задач нелінійного програмування, лінійного програмування, динамічного програмування.

Для вирішення завдання лінійного програмування були використані наступні методи:

1.Графіческій метод;

2.Сімплексний метод;

3.Постановка двоїстої задачі;

4.Решеніе завдання у пропозиції целочисленности змінних;

Для вирішення задачі нелінійного програмування були використані наступні методи:

1.Метод множників Лагранжа

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

Метод про оптимальний розподіл інвестицій;

Метод вибору стратегії оновлення обладнання;

Метод вибору оптимального шляху в транспортній мережі.

Список літератури

1.Дінаміческое програмування: Рек до виконання лаб. і практ.работ / Укл.: Шипілов С.А: НФІ КемГУ .- 2-е ізд.перераб .- Новокузнецьк. 2002.-19 с.

2.Дінаміческое програмування. Шипілов С.А.

3.Методи умовної оптимізації: Рек. до виконання лаб. і практ.работ / Укл.: Шипілов С.А: НФІ КемГУ .- 2-е ізд.перераб .- Новокузнецьк. 2002.-48 с.

Додати в блог або на сайт

Цей текст може містити помилки.

Математика | Курсова
252.5кб. | скачати


Схожі роботи:
Основні поняття математичного програмування Побудова моделі задачі лінійного програмування
Практикум за рішенням лінійних задач математичного програмування
Завдання лінійного програмування
Завдання лінійного програмування
Завдання лінійного програмування
Завдання з програмування на Visual Basic
Рішення та постоптімальний аналіз завдання лінійного програмування
Програмування мовою С з використанням об єктно орієнтованого програмування
Програмування мовою С з використанням обєктно-орієнтованого програмування
© Усі права захищені
написати до нас