Цель работы: овладеть практическими навыками формулирования задач поиска оптимального пути, их решения и анализа на основе принципа оптимальности Беллмана.
Приборы и материалы: линейка, карандаш; микрокалькулятор либо КПК, оснащённый табличным процессором.
1. Составить и решить, используя принцип оптимальности Беллмана, задачу отыскания наиболее дешёвого маршрута доставки груза из пункта A в пункт B при условиях, заданных индивидуальным вариантом задания.
2. Решить задачу при тех же условиях и дополнительном условии обязательного посещения пункта C.
3. Составить и решить, используя принцип оптимальности Беллмана, задачу отыскания минимальной продолжительности выполнения проекта, начинающегося в момент A и завершающегося событием B, при условиях, заданных индивидуальным вариантом задания.
Методические указания по выполнению задания
Задание рекомендуется выполнять, пользуясь графическими изображениями систем допустимых маршрутов и выполняемых работ.
В отчёте должны быть представлены:
¨ граф, отображающий допустимые маршруты, с указанием минимальных затрат на достижение каждого пункта;
¨ оптимальный путь;
¨ минимальные затраты на доставку груза из пункта A в пункт B при условиях заданий 1 и 2;
¨ граф, отображающий последовательность работ, предусмотренную проектом, с указанием ранних сроков наступления каждого события;
¨ критический путь;
¨ минимальный срок выполнения проекта.
Если преподавателем не предписано иначе, отчёт предоставляется в электронном виде на дискете или с использованием средств компьютерных телекоммуникаций.
Фомин Г.П. Математические методы и модели в коммерческой деятельности: Учебник. – 2-е изд. М.: Финансы и статистика, 2005. — Глава 5.
Экономико-математические методы и прикладные модели: Учеб. пособие для вузов / Под ред. В.В. Федосеева. — 2-е изд. М.: ЮНИТИ-ДАНА, 2005. — Раздел 3.5.
Исходные данные индивидуальных вариантов заданий
лабораторной работы №7
| Вариант для заданий | Допустимые маршруты и затраты на перевозку, тыс. руб. Работы и продолжительность их выполнения, рабочих дней | |
| №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 |
Цель работы: овладеть практическими навыками решения задач математического программирования градиентными методами с использованием прикладных программ.