Лабораторная работа №7. Динамическое программирование

Цель работы: овладеть практическими навыками формулирования задач поиска оптимального пути, их решения и анализа на основе принципа оптимальности Беллмана.

Приборы и материалы: линейка, карандаш; микрокалькулятор либо КПК, оснащённый табличным процессором.

Задание

1. Составить и решить, используя принцип оптимальности Беллмана, задачу отыскания наиболее дешёвого маршрута доставки груза из пункта A в пункт B при условиях, заданных индивидуальным вариантом задания.

2. Решить задачу при тех же условиях и дополнительном условии обязательного посещения пункта C.

3. Составить и решить, используя принцип оптимальности Беллмана, задачу отыскания минимальной продолжительности выполнения проекта, начинающегося в момент A и завершающегося событием B, при условиях, заданных индивидуальным вариантом задания.

Методические указания по выполнению задания

Задание рекомендуется выполнять, пользуясь графическими изображениями систем допустимых маршрутов и выполняемых работ.

Требования к отчёту

В отчёте должны быть представлены:

• граф, отображающий допустимые маршруты, с указанием минимальных затрат на достижение каждого пункта;

• оптимальный путь;

• минимальные затраты на доставку груза из пункта A в пункт B при условиях заданий 1 и 2;

• граф, отображающий последовательность работ, предусмотренную проектом, с указанием ранних сроков наступления каждого события;

• критический путь;

• минимальный срок выполнения проекта.

Если преподавателем не предписано иначе, отчёт предоставляется в электронном виде на дискете или с использованием средств компьютерных телекоммуникаций.

Литература

Фомин Г.П. Математические методы и модели в коммерческой деятельности: Учебник. – 2-е изд. М.: Финансы и статистика, 2005. — Глава 5.

Экономико-математические методы и прикладные модели: Учеб. пособие для вузов / Под ред. В.В. Федосеева. — 2-е изд. М.: ЮНИТИ-ДАНА, 2005. — Раздел 3.5.

Варианты заданий приведены в табл. 6.

Таблица 6

Исходные данные индивидуальных вариантов заданий лабораторной работы №7

Вариант для заданий		Допустимые маршруты и затраты на перевозку, тыс. руб. (задания 1 и 2); работы и продолжительность их выполнения, рабочих дней (задание 3).
№1,2	№3
1	3	A1: 4,0; A2: 5,9; A3: 3,1; A4: 11,0; 110: 8,8; 14: 5,5; 24: 4,0; 25: 4,0; 35: 3,5; 3C: 1,5; 36: 5,6; 47: 4,2; 48: 2,0; 57: 2,2; C8: 5,0; CB: 24,4; 69: 1,8; 611: 6,0; 78: 3,3; 810: 7,7; 811: 4,0; 911: 7,9; 9B: 6,8; 10  B: 8,9; 11B: 3,5
2	4	A1: 8,0; A2: 1,4; A3: 4,2; A4: 7,7; 110: 6,3; 14: 4,5; 24: 6,0; 25: 6,1; 35: 5,0; 36: 1,5; 3C: 4,8; 47: 4,0; 410: 8,9; 57: 5,2; 68: 4,2; C9: 5,0; C11: 3,4; 78: 3,3; 810: 7,0; 811: 9,0; 911: 7,9; 9B: 6,8; 10  11: 2,2; 11B: 3,5
3	5	A1: 3,1; A3: 9,1; A2: 1,5; 110: 8,8; 14: 5,5; 24: 4,0; 25: 4,0; 35: 3,5; 37: 1,5; 36: 5,6; 4C: 4,2; 48: 6,3; 5C: 2,2; 78: 2,0; 7B: 14,4; 69: 1,8; 611: 6,0; C8: 3,3; C11: 2,0; 810: 7,0; 811: 4,0; 911: 7,9; 9B: 6,8; 10  B: 8,9; 11B: 3,5
4	6	A1: 7,0; A2: 5,9; A3: 3,1; AC: 11,0; 110: 8,8; 1C: 5,5; 2C: 4,0; 25: 4,0; 35: 3,5; 34: 1,5; 36: 8,8; C7: 4,2; C8: 2,0; 57: 2,2; 48: 5,0; 49: 2,4; 69: 1,8; 611: 6,0; 78: 8,0; 810: 7,7; 811: 4,0; 911: 4,9; 9B: 3,8; 10  B: 8,9; 11B: 9,5
5	7	A1: 5,0; A2: 6,9; A3: 4,1; A4: 12,0; 110: 9,8; 14: 6,5; 24: 4,0; 25: 4,0; 35: 3,5; 3C: 1,5; 36: 5,6; 410: 4,2; 48: 2,0; 57: 2,2; C8: 5,0; CB: 24,4; 69: 1,8; 611: 6,0; 78: 3,3; 810: 7,7; 811: 4,0; 911: 6,0; 9B: 5,8; 10  B: 7,9; 11B: 2,5
6	8	A1: 6,5; A3: 4,2; 12: 1,4; A4: 7,7; 110: 6,3; 14: 4,5; 24: 6,0; 25: 6,1; 35: 5,0; 36: 1,5; 3C: 2,8; 47: 4,0; 410: 8,9; 57: 5,2; 68: 4,2; C9: 5,0; C11: 3,4; 78: 12,3; 810: 7,0; 811: 9,0; 911: 7,9; 9B: 6,8; 10  11: 7,1; 11B: 3,5
7	9	A1: 13,0; A3: 2,1; A2: 1,5; 110: 8,8; 14: 5,5; 24: 4,0; 25: 4,0; 35: 3,5; 37: 1,5; 36: 5,6; 4C: 4,2; 48: 6,3; 5C: 2,2; 78: 2,0; 7B: 4,9; 69: 1,8; 611: 6,0; C8: 3,3; C11: 5,4; 89: 7,0; 811: 4,0; 911: 7,9; 9B: 3,3; 10  B: 1,9; 11B: 3,5
8	10	A1: 3,0; A2: 3,9; A3: 6,1; AC: 7,0; 110: 7,8; 1C: 15,3; 2C: 5,0; 25: 6,0; 35: 9,5; 34: 7,1; 36: 8,0; C7: 1,2; C8: 11,0; 57: 2,2; 48: 5,0; 49: 2,4; 69: 1,8; 611: 6,0; 78: 8,0; 810: 7,7; 811: 4,0; 911: 4,9; 9B: 3,8; 10  B: 8,9; 11B: 9,5
9	11	A1: 7,0; A2: 8,8; A3: 6,0; A4: 13,3; 19: 11,8; 14: 8,5; 24: 7,1; 25: 4,0; 35: 6,5; 3C: 4,5; 36: 8,6; 47: 7,2; 48: 5,3; 57: 5,2; C8: 7,9; CB: 19,3; 69: 4,8; 611: 9,2; 78: 5,9; 810: 10,7; 811: 6,8; 911: 11,0; 9B: 9,7; 10  B: 11,8; 11B: 6,0
10	12	A1: 8,0; A2: 6,0; A4: 3,8; 110: 6,3; 14: 4,5; 23: 4,2; 24: 6,0; 25: 6,1; 35: 5,0; 36: 1,5; 3C: 12,8; 47: 4,0; 410: 8,9; 5C: 0,5; 57: 5,2; 68: 4,2; C9: 2,2; C11: 1,1; 78: 3,3; 810: 7,0; 811: 9,0; 911: 7,9; 9B: 6,8; 10  11: 2,2; 11B: 7,6
11	13	A1: 2,1; A3: 7,0; A2: 1,5; 110: 6,8; 14: 4,5; 24: 3,0; 25: 3,5; 35: 3,5; 37: 1,0; 36: 5,0; 4C: 0,2; 48: 3,3; 5C: 1,2; 78: 1,9; 7B: 22,4; 69: 4,8; 611: 5,0; C8: 5,3; C11: 1,2; 810: 6,0; 811: 3,0; 911: 6,9; 9B: 5,8; 10  B: 7,9; 11B: 2,8
12	14	A1: 1,3; A2: 6,9; A3: 3,1; AC: 5,6; 110: 6,1; 1C: 5,5; 2C: 4,0; 25: 4,0; 35: 3,5; 34: 1,5; 36: 8,8; C7: 4,2; C8: 2,0; 57: 2,2; 49: 2,4; 69: 1,8; 611: 6,0; 78: 8,0; 810: 7,7; 811: 9,3; 911: 4,9; 9B: 3,8; 10  B: 8,9; 11B: 9,5
13	15	A1: 4,5; A2: 11,3; A3: 3,5; A4: 15,8; 19: 9,3; 14: 11,1; 24: 4,6; 25: 6,5; 35: 4,0; 3C: 7,0; 36: 6,1; 47: 9,7; 48: 2,8; 57: 7,7; C8: 5,4; CB: 21,8; 69: 2,3; 611: 11,7; 78: 3,4; 810: 13,2; 811: 4,3; 911: 13,5; 9B: 7,2; 10  B: 14,3; 11B: 3,5
14	16	A1: 9,0; A2: 5,0; A4: 3,8; 110: 7,3; 14: 3,5; 23: 4,2; 24: 7,0; 25: 5,1; 35: 5,0; 36: 2,5; 3C: 11,8; 47: 4,0; 410: 9,9; 5C: 1,5; 57: 5,2; 68: 5,2; C9: 1,2; C11: 1,1; 78: 4,3; 810: 2,7; 811: 9,0; 911: 8,9; 9B: 5,8; 10  11: 2,2; 11B: 7,6
15	17	A1: 7,1; A3: 7,0; A2: 6,5; 110: 6,8; 14: 9,5; 24: 3,0; 25: 8,5; 35: 3,5; 37: 6,0; 36: 5,0; 4C: 5,2; 48: 3,3; 5C: 1,2; 78: 6,9; 7B: 20,0; 69: 9,8; 611: 5,0; C8: 5,3; C11: 7,2; 810: 6,0; 811: 8,1; 911: 6,9; 9B: 10,5; 10  B: 7,9; 11B: 7,8
16	18	A1: 4,3; A2: 2,9; A3: 3,1; AC: 5,6; 110: 8,1; 1C: 3,5; 2C: 4,0; 25: 4,0; 35: 5,5; 34: 1,5; 36: 6,8; C7: 4,2; C8: 4,0; 57: 1,0; 49: 2,4; 69: 1,8; 611: 4,0; 78: 10,0; 810: 7,7; 811: 9,3; 911: 6,6; 9B: 1,8; 10  B: 8,9; 11B: 4,4
17	19	A1: 4,5; A2: 11,3; A3: 3,5; A4: 15,8; 19: 9,3; 14: 11,1; 24: 4,6; 25: 6,5; 35: 4,0; 3C: 7,0; 36: 6,1; 47: 9,7; 48: 2,8; 57: 7,7; C8: 5,4; CB: 21,8; 69: 2,3; 611: 11,7; 78: 3,4; 810: 13,2; 811: 4,3; 911: 13,5; 9B: 7,2; 10  B: 14,3; 11B: 3,5
18	20	A1: 5,0; A2: 1,4; A3: 4,2; A4: 4,7; 110: 6,3; 14: 4,5; 24: 3,4; 25: 6,1; 35: 5,0; 36: 8,5; 5C: 4,8; 47: 4,0; 410: 5,9; 57: 5,2; 68: 4,2; C9: 2,3; C11: 3,4; 78: 3,3; 810: 4,0; 811: 9,0; 911: 7,9; 9B: 3,8; 10  11: 2,2; 11B: 3,9
19	1	A1: 2,0; A3: 8,0; A2: 0,4; 110: 8,8; 14: 5,5; 24: 4,0; 25: 2,9; 35: 2,4; 37: 1,5; 36: 5,6; 4C: 5,3; 48: 7,4; 5C: 3,3; 78: 2,0; 7B: 14,4; 69: 2,9; 611: 7,1; C8: 4,3; C11: 2,0; 810: 7,0; 811: 5,1; 911: 9,0; 9B: 7,9; 10  B: 8,9; 11B: 2,4
20	2	A1: 8,9; A2: 12,9; A3: 5,1; AC: 11,0; 110: 8,8; 1C: 5,5; 2C: 4,0; 24: 2,9; 35: 6,5; 34: 1,5; 36: 8,8; C7: 4,2; C8: 2,0; 57: 2,2; 48: 5,0; 49: 2,4; 69: 1,8; 611: 6,0; 78: 8,0; 810: 7,7; 811: 4,0; 910: 14,9; 9B: 3,8; 10  B: 3,9; 11B: 4,5