Методические указания по изучению дисциплины и выполнению контрольной работы Для студентов заочного факультета всех специализаций (стр. 2 из 6)
Студенту следует разобраться, какие задачи, относящиеся к транспорту, связи, обслуживанию, могут быть решены с позиций теории СМО. Для понимания методов решения задач необходимо твердо уяснить, что такое марковские процессы, какие потоки событий являются простейшими и почему. Студент должен рассчитывать с помощью полученных знаний основные характеристики эффективности работы СМО, уметь приводить различные практические случаи к одной из рассматриваемых в теме моделей: одноканальной или многоканальной, без очереди или с очередью (с отказами или без).
Литература: [2, п.10]; [3].
1. Какие задачи решаются с помощью АСУ и на каких методах базируется получение решений?
2. Что такое базы данных?
3. Какие базы данных являются реляционными?
4. В чем заключается основное отличие экспертных систем от остальных компьютерных программ?
5. Что такое принятие решения в условиях неопределенности?
6. Какие величины называются случайными? Что у случайных величин не случайно?
7. Какую задачу решает метод максимального правдоподобия? Как на практике получается функция распределения плотности вероятности?
8. Почему проверка фактора на значимость в дисперсионном факторном анализе формируется в виде проверки гипотезы о равенстве средних?
9. Как с помощью регрессионных моделей строить прогноз по данным наблюдений?
10. Когда следует прибегать к методам экспертных оценок?
11. Что необходимо знать, решая задачу методами (любыми) оптимального управления?
12. Какой вывод из геометрической интерпретации задачи линейного программирования положен в основу симплекс-метода?
13. Что такое метод “северо-западного угла” в транспортной задаче?
14. Как решаются транспортные задачи с неправильным балансом?
15. В чем заключаются задачи о назначениях и как в них записываются искомые неизвестные?
16. Возможно ли применение сетевых (потоковых) моделей в случае нарушения условия непрерывности потока?
17. Для чего в задаче коммивояжера предусмотрена процедура возврата?
18. В чем суть принципа минимакса? Какие стратегии называются минимаксными?
19. Как в принципе пошаговой оптимизации в динамическом программировании учитываются последствия от сделанного шага?
20. Почему в динамическом программировании решаемую задачу приходиться решать как бы дважды: сначала от конца к началу, затем опять к концу?
21. Что общего и в чем отличие в записях уравнений Беллмана и Эйлера, относящегося к простейшей задачи вариационного исчисления?
22. Как прямыми методами решаются задачи оптимизации?
23. Какие процессы называются марковскими? Приведите примеры из практики.
24. Что такое финальные вероятности и когда они возможны?
25. В чем особенность схемы гибели и размножения и почему она так распространена?
26. Как понимать неограниченность очереди в системе массового обслуживания?
27. Какое состояние в СМО с неограниченной очередью наиболее вероятно?
28. Какое условие необходимо соблюсти, чтобы в СМО с очередью смог осуществиться установившийся режим? Как это можно физически интерпретировать?
МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ВЫПОЛНЕНИЮ
КОНТРОЛЬНОЙ РАБОТЫ
Назначением контрольной работы является закрепление у студентов основных понятий, составляющих предмет АСУ, а также проверка способности практического применения инженерных методов расчета транспортных задач, изложенных в курсе.
В задании требуется определить оптимальный маршрут перевозки коммерческого груза и оптимальную загрузку самолета, приносящих максимальный выигрыш.
Для решения задачи следует использовать метод ветвей и границ задачи коммивояжера и симплекс-метод задачи линейного программирования. В методических целях решение выполняется вручную (поэтому задание выбрано предельно простым). Решение, полученное симплекс-методом, должно быть дополнено геометрическим построением.
Условия задания, состоящего из двух задач, следующие.
Для данного типа самолета известны предельная коммерческая загрузка Q и полезный объем V в условных единицах. Самолет должен одним рейсом (с промежуточными посадками) обслужить 5 пунктов маршрута и возвратиться в исходный пункт, получив при этом максимальную прибыль. Матрица стоимости перелета из пункта в пункт задается (табл.1). Вследствие различных скидок она не симметрична.
В задаче 1 определяется оптимальный маршрут, а в задаче 2 – оптимальная загрузка.
Определение оптимальной загрузки ВС. Требуется определить самую прибыльную загрузку самолета. Рейсом может быть перевезено два вида груза: один дорогой, но тяжелый, второй менее прибыльный, зато полегче. При загрузке следует учесть ограничения на габариты и вес. Стоимость единицы веса груза первого вида составляет S1 , второго S2. Отношение удельных объемов грузов
, где a – последняя цифра шифра студента. Отношение полезного объема к 
: 
, где b – предпоследняя цифра шифра. Предельная коммерческая загрузка Q равна 100 + 10c , где c – третья с конца цифра шифра. Соответственно S1=13/(a +2) , S2=6/(b+1).Определение оптимального маршрута ВС. Требуется определить самый дешевый путь облета всех пунктов с возвратом в исходный.
Таблица 1
| Пункты (узлы) | Исх.1 | 2 | 3 | 4 | 5 | 6 |
| Исх.1 | - | 25+a | 45+b | 15+c | 30+a | 25+b |
| 2 | 5+c | - | 15+b | 1+a | 30+c | 30+b |
| 3 | 20+a | 15+b | - | 35+c | 5+b | a |
| 4 | 20+b | 15+c | 25+a | - | 20+a | 20+c |
| 5 | 10+b | 45+a | 25+c | 50+b | - | 5+a |
| 6 | 25+a | 5+b | 5+c | 10+a | 5+b | - |
По шифру студента находятся: a – последняя цифра, b – предпоследняя, c – третья с конца.
Задание следует начать выполнять с поиска оптимального маршрута. В этом случае определяются тарифы на перевозку груза (правда, в данной работе они непосредственно не потребуются). Из условия задачи следует, что она является классическим выражением задачи коммивояжера, для которой имеется эффективный метод решения - ветвей и границ. Им и надо воспользоваться. Покажем метод на примере.
Пусть матрица стоимостей Cij перелета из i-го пункта в j-й задана (табл.2) .
Таблица 2
| Пункты | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | - | 27 | 43 | 16 | 30 | 26 |
| 2 | 7 | - | 16 | 1 | 30 | 30 |
| 3 | 20 | 13 | - | 35 | 5 | 0 |
| 4 | 21 | 16 | 25 | - | 18 | 18 |
| 5 | 12 | 46 | 27 | 48 | - | 5 |
| 6 | 23 | 5 | 5 | 9 | 5 | - |
Метод заключается в пошаговой оптимизации, когда последовательно на каждом шаге выбирается по одному звену в оптимальный маршрут Т. Оптимальность понимается как минимальная стоимость Z(T). Выбор производится из соображения сиюминутной выгоды, т.е. без учета возможных последствий. На каждом шаге выбирается то звено, которое имеет наибольшее значение штрафа (который бы пришлось заплатить, если это звено не взять в оптимальный маршрут). Однако такая тактика выбора звеньев сопряжена с риском отвергнуть тот маршрут (содержащий отброшенные звенья), который впоследствии окажется самым дешевым. Поэтому тактика сиюминутной выгоды подстраховывается вычислением так называемых нижних границ стоимостей маршрутов, в том числе отвергнутых на каждом шаге выбора. Затем после вычисления всего маршрута, претендующего на оптимальность, его стоимость сравнивается с нижними границами отвергнутых маршрутов, которые графически изображаются ветвями. Если окажется, что какая-то нижняя граница будет меньше стоимости маршрута, то соответствующая ветвь анализируется точно так же, как до этого строился первоначальный маршрут. Такая процедура называется возвратом. При возврате соответствующая ветвь сама начинает ветвиться. Ветвление может прекратиться, когда все нижние границы ветвей превысят стоимость ранее найденного маршрута.