[ Завдання математичного програмування ] | 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 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Інтерпретація додаткових змінних
Перевірити результати рішення в табличному процесорі Excel. В Excel є надбудова «Пошук рішення», яка дозволяє вирішувати оптимізаційні задачі. Використавши цю надбудову для вирішення нашої задачі ЛП, отримуємо наступний результат: Таблиця 6.
Але при застосуванні надбудови «пошук рішення» до завдання, двоїстої даній задачі ЛП, приходимо до висновку, що рішення отримане за допомогою надбудови не сходиться з рішенням з симплекс-таблиці: Таблиця 7.
Лабораторна робота № 2 (Рішення завдання ЛП засобами табличного процесора Excel) Для заданої змістовної постановки задачі ЛП виконати наступні дії: Здійснити математичний запис задачі ЛП; Вирішити завдання з використання надбудови Excel «Пошук рішення»; Привести математичну постановку двоїстої задачі ЛП; Отримати рішення двоїстої завдання ЛП з використанням надбудови Excel «Пошук рішення»; Отримати рішення задачі в припущенні целочисленности змінних; Зробити аналіз отриманих результатів і дати їх змістовну інтерпретацію. Завдання: До складу раціону годівлі входять три продукти: сіно, силос і концентрати, що містять такі поживні речовини: білок, кальцій та вітаміни. Вміст поживних речовин в грамах в 1 кілограмі відповідного продукту харчування і мінімально необхідну їх споживання задані таблицею:
Визначити оптимальний режим годування, з умови мінімальної вартості, якщо ціна 1 кг продукту харчування відповідно становить: для сіна - 30коп., Для силосу-20 коп., Для концентрату - 50 коп. Рішення Здійснити математичний запис задачі ЛП. Складемо математичну модель. Позначимо через х1 - кількість одиниць сіна, через х2 - кількість одиниць силосу а через х3 - кількість одиниць концентрату. Функція витрат на покупку цих продуктів виглядає так: f (x) = 30x1 +20 x2 +50 x3 її необхідно мінімізувати. Необхідні норми споживання виражені у вигляді обмежень:
В результаті загальна постановка задачі ЛП має вигляд:
Вирішити завдання з використання надбудови Excel «Пошук рішення». Як значення змінних виступає кількість закуповуваної продукції кожного виду. В осередках «Витрата поживних речовин» містяться формули, що визначають ліві частини обмежень, а в осередках необхідне споживання поживних речовин - значення правих частин обмежень. Після введення всіх даних вибираємо команду Сервіс / Пошук Рішення та, заповнюємо відкрилося діалогове вікно Пошук Рішення: Як цільова осередки вибираємо клітинку, в якій перебуває значення цільової функції, виконуємо максимізацію функції, змінюючи клітинки зі значеннями кількості продукції. Встановлюємо обмеження. Далі вибираємо пункт «Параметри», щоб перевірити, які параметри задані для пошуку рішення. У вікні Параметри пошуку рішення можна змінювати умови та варіанти пошуку рішення досліджуваної задачі, а також завантажувати і зберігати оптимізуються моделі. Для даної задачі досить встановити два прапорці «Лінійна модель» (тому що обмеження і цільова функція є лінійними за змінними) і «невід'ємні значення» (для виконання умов завдання ЛП). Тепер завдання оптимізації підготовлена повністю. Після натискання кнопки «Виконати» відкривається вікно «Результати пошуку рішення», яке повідомляє, що рішення знайдено. Таблиця 9
| 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
Змінимо, дані для того, щоб отримати відкриту задачу. Для цього зменшимо запаси і збільшимо потреби, отримаємо: Таблиця 13
Лабораторна робота № 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
Рішення завдання обома методами дали однаковий результат. Лабораторна робота № 5 (задача динамічного програмування про оптимальний розподіл інвестицій) Завдання Є чотири підприємства, між якими необхідно розподілити 100 тис. ум.од. коштів. Значення приросту випуску продукції на підприємствах в залежності від виділених коштів X представлені в таблиці. Скласти оптимальний план розподілу коштів, що дозволяє максимізувати загальний приріст випуску продукції. Таблиця 14
Рішення Етап I. Умовна оптимізація. Крок 1. k = 4. Припускаємо, що всі кошти 100 ден.ед. передані на інвестування четвертого підприємства. У цьому випадку максимальна прибуток складе F4 (C4) = 46, дані представлені в таблиці 15. Таблиця 15.
| 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
Крок 4. k = 4. Функціональне рівняння на даному кроці набуває вигляду: . Результати розрахунку за наведеною формулою наведені в таблиці: Таблиця 21.
Етап 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 с. Будь ласка, не зберігайте тестовий текст. |