Обзор экономико-математических методов. Применение стохастического программирования для решения экономических задач
Дипломная работа - Менеджмент
Другие дипломы по предмету Менеджмент
?афов оперирует понятием пути, объединяющим последовательность взаимосвязанных ребер. Контур означает такой путь, у которого начальная вершина совпадает с конечной.
Сетевой график - это ориентированный граф без контуров. В сетевом моделировании имеются два основных элемента - работа и событие.
Работа - это активный процесс, требующий затрат ресурсов, либо пассивный (ожидание), приводящий к достижению намеченного результата. Фиктивная работа - это связь между результатами работ, не требующая затрат времени и ресурсов. Событие - это результат выполнения одной или нескольких предшествующих работ. Путь - это любая непрерывная последовательность (цепь) работ и событий. Критический путь - это путь, не имеющий резервов и включающий самые напряженные работы комплекса. Работы, расположенные на критическом пути, называют критическими. Все остальные работы являются некритическими (ненапряженными) и обладают резервами времени, которые позволяют передвигать сроки их выполнения, не влияя на общую продолжительность выполнения всего комплекса работ. При построении сетевых моделей необходимо соблюдать следующие правила.
. Сеть изображается слева направо, и каждое событие с большим порядковым номером изображается правее предыдущего. Общее направление стрелок, изображающих работы, также в основном должно быть расположено слева направо, при этом каждая работа должна выходить из события с меньшим номером и входить в событие с большим номером.
. Два соседних события могут объединяться лишь одной работой. Для изображения параллельных работ вводятся промежуточное событие и фиктивная работа (рис. 1).
Рис. 1
Рис. 2
3. В сети не должно быть тупиков, т.е. промежуточных событий, из которых не выходит ни одна работа (рис. 2).
. В сети не должно быть промежуточных событий, которым не предшествует хотя бы одна работа (рис. 3).
Рис. 3
Рис. 4
. В сети не должно быть замкнутых контуров, состоящих из взаимосвязанных работ, создающих замкнутую цепь (рис. 4).
Для правильной нумерации событий поступают следующим образом: нумерация событий начинается с исходного события, которому дается номер 1. Из исходного события 1 вычеркивают все исходящие из него работы, на оставшейся сети вновь находят событие, в которое не входит ни одна работа. Этому событию дается номер 2.
Затем вычеркивают работы, выходящие из события 2, и вновь находят на оставшейся части сети событие, в которое не входит ни одна работа, ему присваивается номер 3, и так продолжается до завершающего события. Пример нумерации сетевого графика показан на рис. 5.
Рис. 5
Продолжительность выполнения работ устанавливается на основании действующих нормативов или по экспертным оценкам специалистов. В первом случае временные оценки являются детерминированными (однозначными), во втором - стохастическими (вероятностными).
1.5 Стохастическое программирование
игра обслуживание стохастический программирование
Раздел математического программирования, изучающий задачи со случайными коэффициентами, называется стохастическим программированием. Если для случайных величин, фигурирующих в задаче, на основании статистических и других исследований удается установить вероятностные характеристики (функцию распределения, математическое ожидание, дисперсию), то говорят, что задача решается в условиях риска. Если же никаких сведений о статистических закономерностях изменения случайных параметров не имеется, то получаем так называемую задачу в условиях неопределенности. Стохастическое программирование изучает задачи обоих указанных типов.
При постановке стохастической задачи не только формулируются ограничительные условия и целевая функция, но сразу же устанавливается, какой план будет считаться допустимым и какой - оптимальным. В обычных (детерминированных) задачах допустимым называется план, удовлетворяющий системе ограничений, а оптимальным - доставляющий кроме того, функционалу наибольшее (наименьшее) значение. Для стохастической задачи эти определения будут далеко не полными. Действительно, план Х (х1, х2,...,хn) может удовлетворять системе ограничений при одной совокупности значений случайных коэффициентов и не удовлетворять при другой. Аналогично, некоторый план может быть оптимальным для одного набора случайных коэффициентов функции цели и не оптимальным - для другого.
В отдельных задачах найденный план не может быть впоследствии изменен даже при получении информации о поведении системы в будущем. Это имеет место в ситуациях, связанных с капитальным строительством. Например, нельзя менять расположение или хотя бы мощность перерабатывающих предприятий в зависимости от видов урожай. Всякий план такой задачи следует считать детерминированным.
В других задачах план можно откорректировать даже в ходе его выполнения. Так, если бы долгосрочные прогнозы погоды были достаточно надежными, оптимальное сочетание сельскохозяйственных культур можно было бы уточнять ежегодно: на засушливый год увеличивать посевы засухоустойчивых культур, на дождливый - влагоустойчивых. В подобных задачах план представляет собой набор случайных чисел, для которых в процессе решения находят нужные характеристики.
Рассмотрим теперь возможные определения допустимого плана. Можно потребовать, чтобы набор значений переменных удовлетворял всем ограничениям ?/p>