Автор: Пользователь скрыл имя, 13 Декабря 2011 в 08:55, лабораторная работа
Динамическое программирование – метод оптимизации, в котором процесс принятия решения и управления может быть разбит на отдельные этапы (шаги).
В отличие от линейного программирования, в котором симплексный метод является универсальным методом решения, в динамическом программировании такого универсального метода не существует. Одним из основных методов динамического программирования является метод рекуррентных соотноше –ний, который основывается на использовании принципа оптимальности Беллмана.
| Склады | Магазины | Запас | |||
| А | В | С | |||
| V1 = 3 | V2 = 2 | V3 = 4 | |||
| 1 | U1 = 0 | 3
30 |
1 | 1 | 30 |
| 2 | U2 = 2 |
5
10 |
4
15 |
2
|
25 |
| 3 | U3 = 1 | 4 |
3
5 |
5
10 |
15 |
| 4 | U4 = 1 | 1 | 5 | 5
30 |
30 |
| Спрос | 40 | 20 | 40 | ||
L = 30 •
3 + 10 • 5 + 15 • 4 + 5 • 3 + 10 • 5 + 30
• 5 = 415.
Для
занятых клеток все рассчеты остаются
в силе, отличаются они только для
свободных клеток.
U1; V2: U1 + С12 = 0 + 1 = 1 < 2
U1; V3: U1 + С13 = 0 + 1 = 1 < 4
U2; V3: U2 + С23 = 2 + 2 = 4 ≥ 4
U3; V1: U3 + С31 = 1 + 4 = 5 > 3
U4; V1: U4 + С41 = 1 + 1 = 2 < 3
U4; V2: U4 + С42 = 1 + 5 = 6 > 2
В отличие от предыдущего раза, когда у нас не было такой клетки, где разность Vj – (Ui+Cij) была бы максимальна, сейчас разность достигает максимального значения в клетке (U1; V3).
Как
и в предыдущий раз, выполняем перемещение.
Посмотрим, насколько изменится конечный
результат.
| Склады | Магазины | Запас | |||
| А | В | С | |||
| V1 = 3 | V2 = 2 | V3 = 1 | |||
| 1 | U1 = 0 |
3
25 |
1 |
1
5 |
30 |
| 2 | U2 = 2 |
5
15 |
4
10 |
2
|
25 |
| 3 | U3 = 1 | 4 |
3
10 |
5
5 |
15 |
| 4 | U4 = 4 | 1 | 5 | 5
30 |
30 |
| Спрос | 40 | 20 | 40 | ||
L
= 25 • 3 + 5 • 1 + 15 • 5 + 10 • 4 + 10
• 3 + 5 • 5 + 30 • 5 = 400.
Для первой клетки все остается неизменным: U1 = 0, V1 = 3.
U1; V3: U1 = 0, V3 = 1 – 0 = 1.
U2; V1: V1 = 3, U2 = 5 – 3 = 2.
U2; V2: U2 = 2, V2 = 4 – 2 = 2.
U3; V2: V2 = 2, U3 = 3 – 2 = 1.
U3; V3: V3 = 1, U3 = 5 – 1 = 4.
U4; V3: V3 = 1, U4 = 5 – 1 = 4.
U1; V2: U1 + С12 = 0 + 1 = 1 < 2
U2; V3: U2 + С23 = 2 + 2 = 4 > 1
U3; V1: U3 + С31 = 1 + 4 = 5 > 3
U4; V1: U4 + С41 = 4 + 1 = 5 > 3
U4;
V2: U4 + С42 = 4 + 5 =
9 > 2
| Склады | Магазины | Запас | |||
| А | В | С | |||
| V1 = 3 | V2 = 1 | V3 = 3 | |||
| 1 | U1 = 0 |
3
15 |
1
10 |
3
5 |
30 |
| 2 | U2 = 2 |
5
25 |
4
|
2
|
25 |
| 3 | U3 = 1 | 4 | 3
10 |
5
5 |
15 |
| 4 | U4 = 4 | 1 | 5 | 5
30 |
30 |
| Спрос | 40 | 20 | 40 | ||
L
= 15 • 3 + 10 • 1 + 5 • 3 + 25 • 5 + 10 • 3 + 5 • 5 + 30
• 5 = 400.
Для первой клетки все остается неизменным: U1 = 0, V1 = 3.
U1; V2: U1 = 0, V2 = 1 – 0 = 1.
U1; V3: U1 = 0, V3 = 3 – 0 = 3.
U2; V1: V1 = 3, U2 = 5 – 3 = 2.
U3; V2: V2 = 1, U3 = 3 – 2 = 1.
U3; V3: V3 = 3, U3 = 5 – 3 = 2.
U4; V3: V3 = 3, U4 = 5 – 1 = 4.
U2; V2: U2 + С22 = 2 + 4 = 6 > 1
U2; V3: U2 + С23 = 2 + 2 = 4 > 3
U3; V1: U3 + С31 = 4 + 1 = 5 > 3
U4; V1: U4 + С41 = 4 + 1 = 5 > 3
U4; V2: U4 + С42 = 4 + 5 = 9 > 1
Как видим решение является оптимальным, но с небольшими отличиями.
Ответ: оптимальный план содержит шесть перевозок:
- с первого склада – 15 единиц магазину А, 10 единиц магазину В и 5 единиц магазину С;
- со второго склада – 25 единиц магазину А;
- с третьего склада – 10 единиц магазину В и 5 единиц магазину С;
- с четвертого склада – 30 единиц магазину С.
При этом общая сумма транспортных опять же составляет 400 денежных единиц.
Информация о работе Лабораторные работы по Методам Оптимизации