Автор работы: Пользователь скрыл имя, 01 Декабря 2011 в 00:54, курсовая работа
Подобно методу «разделяй и властвуй», динамическое программирование решает задачу, разбивая её на подзадачи и объединяя их решения. Алгоритмы типа «разделяй и властвуй» делят задачу на независимые подзадачи, эти подзадачи—на более мелкие подзадачи и так далее, а затем собирают решение основной задачи «снизу вверх». Динамическое программирование применимо тогда, когда подзадачи не являются независимыми, иными словами, когда у подзадач есть общие «подподзадачи». В этом случае алгоритм типа «разделяй и властвуй» будет делать лишнюю работу, решая одни и те же подподзадачи по нескольку раз. Алгоритм, основанный на динамическом программировании, решает каждую из подзадач единожды и запоминает ответы в специальной таблице. Это позволяет не вычислять заново ответ к уже встречавшейся подзадаче.
В типичном случае динамическое программирование применяется к задачам оптимизации. Примерами задач динамического программирования являются задача о перемножении матриц и задача о нахождении найбольшей общей подпоследовательности. Эти задачи и методы их решения будут рассмотрены в данной работе.
ВСТУПЛЕНИЕ 5
1 МАТЕМАТИЧНА ПОСТАНОВКА ЗАДАЧІ 6
2 ПРИКЛАДИ ЗМІСТОВИХ ПОСТАНОВОК ЗАДАЧІ 8
3 АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ О ПЕРЕМНОЖЕНИИ МАТРИЦ 10
3.1 Метод північно-західного кута 12
3.2 Метод найменшого часу 13
3.3 Оцінка складності алгоритмів 14
4 ПРИКЛАДИ РОЗВ’ЯЗАННЯ ЗАДАЧ «ВРУЧНУ» 15
5 РОЗВ’ЯЗАННЯ ЗАДАЧІ З ДОПОМОГОЮ EXCEL 26
6 ПРОГРАМНА РЕАЛІЗАЦІЯ АЛГОРИТМУ 31
ВИСНОВОК 33
ПЕРЕЛІК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ 34
Додаток А 34
Лістинг програми 34
Рисунку 4.8. - Матриця часу для другого прикладу.
Складаємо робочу таблицю, на основі вхідних даних, яка показана на рисунку 4.9.
| 400 | 200 | 150 | 450 | |
| 550 | 1 | 7 | 3 | 2 |
| 250 | 6 | 9 | 8 | 1 |
| 300 | 2 | 3 | 2 | 7 |
| 100 | 1 | 2 | 4 | 1 |
Рисунок 4.9 - Робоча таблиця.
Будуємо початковий план методом «найменшого часу», заповнюючи послідовно клітини (1,1), (4,4), (2,4), (1,4), (3,3), (3,2) (1,2).
На
рисунку 4.10 показаний не тільки початковий
розв’язок, але і потенціали зайнятих
клітин.
| 400 | 200 | 150 | 450 | ui | |
| 550 | 1
400 |
7
50 |
3 | 2
100 |
1 |
| 250 | 6 | 9 | 8 | 1
250 |
0 |
| 300 | 2 | 3
150 |
2
150 |
7 | -3 |
| 100 | 1 | 2 | 4 | 1
100 |
0 |
| vj | 0 | 6 | 5 | 1 |
Рисунок 4.10. Таблиця з початковим планом і потенціалами.
Обчислюючи потенціали вільних клітин, отримуємо дві від’ємні оцінки, тому план не є оптимальним. При цьому час на його реалізацію рівний найбільшому з часу, записаних в зайнятих клітинах, тобто, найбільшому з чисел 1, 2, 3, 7. Час рівний 7 одиницям вартості. Найбільша від’ємна оцінка в відповідній клітинці (4,2). Будуємо цикл з початком в тій клітинці і вершинами в клітинках (1,2), (1,4), (4,4). Величина поставки, яку треба буде перерозподілити по цьому циклу, рівна 50. Клітинка з часом(тарифами) 8 і 9 можна викреслити і просто не використовувати в подальшому(при їх використанні час виконання плану збільшиться).
| 400 | 200 | 150 | 450 | |
| 550 | 1 | 7 | 3 | 2 |
| 250 | 6 | 9 | 8 | 1 |
| 300 | 2 | 3 | 2 | 7 |
| 100 | 1 | 2 | 4 | 1 |
Рисунок 4.11 – Початковий план і потенціали.
Новий план з відповідними потенціалами показано на рисунку 4.12.
| 1
400 |
7 | 3 | 2
150 |
1 |
| 6 | 9 | 8 | 1
250 |
0 |
| 2 | 3
150 |
2
150 |
7 | -3 |
| 1 | 2
50 |
4 | 1
50 |
0 |
| 0 | 6 | 5 | 1 |
Рисунок 4.12 - План перевезень після першої ітерації «розгрузки»
Всі потенціали незайнятих клітин не є від’ємні. Отже, план оптимальний. Дійсно, максимальний час рівний 3. Побудувати розвантажувальний цикл в даній таблиці не можна. Тому максимальний час перевезень в оптимальному плані рівний 3.
Приклад 3. На рисунку 4.13 маємо транспортну таблицю, заповнену аналогічно рисунку 4.9. Потрібно знайти максимальний час перевезення при оптимальному плані.
| 60 | 80 | 100 | 120 | |
| 400 | 15 | 8 | 7 | 14 |
| 80 | 7 | 6 | 9 | 8 |
| 100 | 6 | 11 | 6 | 10 |
| 240 | 21 | 7 | 18 | 5 |
Рисунок 4.13 - Таблиця з вхідними даними до задачі з прикладу 3.
Будуємо початковий план перевезень методом найменшої вартості. Початковий план матиме вигляд, як показано на рисунку 4.14.
| 520 | 80 | 100 | 120 | |
| 400 | 15
300 |
8
0 |
7
100 |
14 |
| 80 | 7
0 |
6
80 |
9 | 8
0 |
| 100 | 6
100 |
11 | 6
0 |
10 |
| 240 | 21
120 |
7
0 |
18 | 5
120 |
Рисунок 4.14 - Початковий план перевезень для прикладу 3.
Знаходимо значення найбільшого часу в таблиці. Воно рівне 21. «Розвантажуємо» клітинку (4,1). Для цього будуємо 2 цикли. Перший матиме вершини (1,1), (4,4) і (1,4), а другий (2,1), (2,2), (4,2).
Отримуємо новий план перевезень, показаний на рисунку 4.14.
| 520 | 80 | 100 | 120 | |
| 400 | 15
400 |
8
0 |
7
0 |
14 |
| 80 | 7
20 |
6
60 |
9 | 8
0 |
| 100 | 6
100 |
11 | 6
0 |
10 |
| 240 | 21
0 |
7
20 |
18
100 |
5
120 |
Рисунок 4.14 - План перевезень після першої ітерації «розвантаження».
Максимальний час перевезень рівний 18 в клітині (4,3). Можна зменшити кількість продукції, перевезеної по цьому маршруту, але повністю звільнити цей маршрут для даної таблиці не можна. Тому цей план є оптимальним.
Приклад 4. Маємо рисунок 4.15 з вхідними даними та початковим планом, одержаний методом найменшого часу. Завдання знайти оптимальний план перевезення і максимальний час
| 200 | 100 | 200 | 300 | |
| 200 | 9 | 8
100 |
7 | 6
100 |
| 200 | 8 | 7 | 6
200 |
8 |
| 200 | 5
200 |
6 | 7 | 8 |
| 200 | 6 | 8 | 7 | 5
200 |
Рисунок 4.15 - Початковий план перевезень для прикладу 4.
Будуємо цикл (1,2), (1,3), (2,3), (2,2). Отримуємо новий план, показаний на рисунку 4.16.
| 200 | 100 | 200 | 300 | |
| 200 | 9 | 8 | 7
100 |
6
100 |
| 200 | 8 | 7
100 |
6
100 |
8 |
| 200 | 5
200 |
6 | 7 | 8 |
| 200 | 6 | 8 | 7 | 5
200 |
Рисунок 4.16 - План перевезень після побудови першого циклу.
Комірку (1,3) можна «розвантажити», побудувавши цикл, але комірка (2,2) залишається без змін, бо з нею не можна побудувати цикл. Отже, даний план є оптимальним, а найдовший час перевезення рівний 7.
5 РОЗВ’ЯЗАННЯ ЗАДАЧІ З ДОПОМОГОЮ MICROSOFT EXCEL
Для того, щоб знайти розв’язання задачі з допомогою Microsoft Excel, треба виконати підготовчу роботу. Спочатку будуємо визначаємося з кількістю точок відправлення і споживання продукції. Далі будуємо дві таблиці. Перша задає час перевезень, а друга – кількість одиниць продукції, що буде перевезена по кожному з маршрутів. Далі заповнюємо таблицю, яка задає час перевезень, а також вказуємо кількість одиниць продукції, яка буде відправлятися з кожного пункту відправлення в пункти споживання. Таблицю з перевезеннями залишаємо пустою, лише в поля, де задаємо кількість сумарних перевезень, пишемо формули сум по рядкам і по стовпцям, як показано на рисунку 5.1.
Рисунку 5.1 - Приклад заповнення матриць.
Далі будуємо ще 2 матриці. Одна з них показує, чи є перевезення по маршруту, а інша – добуток відповідних елементів матриці часу перевезень на відповідні елементи новоствореної булевої матриці. Залишається тільки записати цільову функцію, яка є максимумом по всіх комірках останньої матриці. В результаті маємо дві таблиці вигляду, зображених на рисунку 5.2.
Информация о работе Задача о наибольшей общей подпоследовательности