Стохастическое программирование

В принципе динамическое планирование может разворачиваться  и в прямом направлении, т. е. от первого  шага процесса к последнему. (4)

1.3 Сетевое  планирование и управление

Сетевое планирование и  управление возникло в 1957 - 1958 гг. под  названием «метод критического пути»  и метод PERT (метод оценки и пересмотра планов).

Методы сетевого планирования и управления предусматривают:

1) представление планов  в виде сети;

2) определение календарных графиков;

3) определение вероятностных  величин;

4) возможность применения  в различных условиях.

Метод сетевого планирования и управления пригоден как в промышленности, так и в сельском хозяйстве.

Применение сетевого планирования и управления в сельском хозяйстве носит пока ещё экспериментальный характер и ограничивается составлением планов на короткие напряженные рабочие периоды. Необходимость выполнять все сельскохозяйственные работы в установленные агротехнические сроки, неопределенность, вносимая в производственный процесс капризами природы, несомненно, затрудняют использование экономико-математических методов, в том числе и методов сетевого анализа. Но даже тот опыт применения указанных методов в сельском хозяйстве, который имеется в настоящее время, позволяет сделать вывод об их высокой эффективности в данной отрасли.

Методы сетевого планирования и управления дают возможность:

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

2) предсказать вероятное  время выполнения;

3) улучшить план, если  мы найдем, что предсказанное  время выполнения является недостаточно  хорошим;

4) проверить ход выполнения  работ по плану после того, как план приведен в действие;

5) использовать информацию о ходе работ для своевременного планирования времени и затрат.

В настоящее время  известно большое количество модификаций  системы сетевого планирования и  управления: RAMPS, PERT, CRM, LESS, COMET и ряд  других.

В свое время в СССР также была разработана система сетевого планирования и управления (СПУ), включающая методы КОППР,СУР, КОМПАС и другие. Система СПУ основана на использовании современных достижений в области общей теории управления, кибернетики прикладной математики и вычислительной техники.

В сетевом планировании и управлении широко применяется аппарат математического программирования, теории графов, теория вероятностей и других математических дисциплин. Формализация задач планирования и управления позволяет широко использовать средства вычислительной техники и строить сетевые системы по общим принципам построения АСУ.

Предпосылкой создания сетевых систем являлось развитие раздела  исследования операций, изучающего модели упорядочивания. Идея моделирования  комплексов операций с помощью сетей привела к появлению самостоятельного направления в теории и практике организационного управления, получившего в отечественной литературе название сетевого планирования и управления (СПУ).

Все методы сетевого планирования имеют в своей основе сетевую  модель, в которой условными знаками - стрелками изображают во взаимосвязи работы, которые необходимо выполнить для достижения поставленной цели. Сеть может быть укрупненной или детальной, но в любом случаи она должна давать представление о том, какими путями можно прийти к коночной цели и какие издержки при этом потребуются. Уже одно то, что информация о предполагаемом ходе выполнения работ представляется в виде сети, наглядно изображающей условия выполнения каждой из работ в общем комплексе, является достаточной рекомендацией к использованию сетевых графиков в практической работе. При вычерчивании сети легко выявляются все недостатки, логические неувязки в организационной структуре планируемого мероприятия.

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

Помимо графического изображения работ, которые предполагается выполнить для достижения намеченной цели, сетевой график содержит некоторые  оценки (времени, стоимости, ресурсов, технической надежности элементов), даваемые каждой работе в отдельности. Эти оценки могут быть точными или приближенными. С известной вероятностью появления каждой из них. Сетевой график с нанесенными на него оценками служит основой для последующего анализа возможных изменений и контроля за его выполнением. Основными параметрами, которые оцениваются при таком анализе, служат время и затраты. Эти два фактора, как правило, находятся в непосредственной зависимости один от другого: чем короче заданный срок выполнения работ, тем больше затрат потребуется на их выполнение, и наоборот. Анализ сетевого графика в системе СПУ позволяет выбрать оптимальный вариант плана, обеспечивающий выполнение всех работ в заданные сроки с минимальными затратами. Система СПУ предусматривает либо одну оценку времени для выполнения каждой работы - «наиболее вероятное время», либо три оценки: «оптимистическую», «пессимистическую» и «наиболее вероятную» оценки времени по каждой работе. Эти три оценки используются для расчета среднего ожидаемого времени выполнения работ и вычисления вероятности выполнения программы в заданные сроки. Несмотря на указанные и некоторые другие различия в методах анализа сетевых моделей, общая их идея одна - все они используют графическое построение в виде сети с временными или другими оценками для планирования действий, приводящих в конечном итоге к желаемому результату. (5)

1.4Теория массового  обслуживания

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

Например, организация нормального  процесса обслуживания покупателей связана с правильным определением следующих показателей: количества предприятий данного торгового профиля, численности продавцов в них, наличия соответствующих основных фондов, частоты завоза товаров, численности обслуживаемого населения, плотности обращаемости и потребности в соответствующих товарах. Если предположить, что предприятие располагает необходимыми основными фондами, торгует товарами, имеющимися в достаточном количестве, то и тогда в процессе обслуживания остаются такие переменные величины, которые могут существенно повлиять на качество обслуживания. Надлежит, следовательно, выбрать такой оптимальный вариант организации торгового обслуживания населения, при котором время обслуживания будет минимальным, качество - высоким, не будет излишних народохозяйственных затрат. Математический аппарат теории массового обслуживания облегчает решение этой задачи.

Системы массового обслуживания (СМО) занимают важное место во многих сферах хозяйственной деятельности. Примерами СМО могут служить телефонные станции, ремонтные мастерские (заводы, базы, бригады), погрузочно-разгрузочные комплексы (порты, товарные станции), транспортные системы, автозаправочные станции, больницы, торговые точки, предприятия бытового обслуживания и т. д. Обрабатывающее предприятие, например машиностроительный завод, его цех, участок, станок также могут рассматриваться как СМО, обслуживающие поступающее сырье, заготовки, полуфабрикаты, комплектующие изделия.

Каждая СМО имеет одно или несколько обслуживающих устройств, называемых каналами обслуживания (каналы связи, ремонтные бригады, краны, бензоколонки, продавцы, кассиры, парикмахеры, станки), и предназначена для обслуживания - выполнения потока заявок, требований, поступающих в систему большей частью в случайные моменты времени. Время обслуживания заявки также обычно случайно. Случайный характер потока заявок и времени обслуживания приводит либо к накоплению необслуженных заявок, либо к недогрузке СМО, простою ее каналов.

Задача теории массового  обслуживания состоит в выработке  рекомендаций по рациональному построению СМО, рациональной организации их работы и регулированию потока заявок с  целью обеспечить более высокую  эффективность обслуживания при  малых затратах на создание и функционирование системы. Для этого теория массового обслуживания устанавливает зависимости между характеристиками потока заявок, числом и производительностью каналов обслуживания и «выходными» характеристиками СМО, описывающими результаты ее работы. Системы массового обслуживания делятся на две группы: СМО с отказами в обслуживании и СМО с ожиданием, или очередью. В СМО с отказами заявка, поступившая в момент, когда все каналы обслуживания заняты, получает «отказ» и сразу покидает систему, а не становится в очередь. Примерами системы с отказами могут служить система телефонной связи города, пошивочная мастерская, если нет «записи на очередь».

В системах с ожиданием  заявка, пришедшая в такой момент, когда все каналы заняты, не уходит, а становится в очередь и ждет освобождения канала. Системы с ожиданием делятся на системы с неограниченным ожиданием начала обслуживания, с ограничением времени ожидания и с ограничением длины очереди. Обслуживание очереди (дисциплина очереди) может быть упорядоченным, т. е. строго в порядке поступления заявок, случайным, когда заявки обслуживаются в некотором случайном порядке, и с приоритетами, когда в первую очередь обслуживаются заявки, обладающие некоторыми признаками. Принадлежность СМО к тому или другому виду зависит не только от характера системы, но и от приемлемой срочности обслуживания, наличия или отсутствия других СМО, оказывающих те же услуги, и других факторов.

СМО называется разомкнутой, если поток заявок не зависит от ее функционирования. Это бывает, когда  заявок много и интенсивность потока заявок не изменяется заметно в результате работы СМО. Примерами разомкнутых СМО могут служить АТС, ремонтные бригады, мастерские, если заявок на ремонт так много, что работа СМО практически не влияет на их поступление. СМО называется замкнутой, если поток заявок зависит от функционирования системы. Так ремонтное предприятие должно рассматриваться как замкнутая СМО, если заявки поступают не очень часто и их поток зависит от пропускной способности предприятия.

Одним из важнейшим показателем эффективности СМО является ее производительность, или пропускная способность, или среднее число заявок, которое система может обслужить за единицу времени, и относительная пропускная способность - отношение среднего числа заявок, обслуживаемых за единицу времени, к среднему числу поступивших за это время заявок.

Поток заявок характеризуется  распределением заявок по времени. Исследование СМО весьма облегчается, если принимается  простой поток заявок. В реальных условиях работы СМО поток заявок в большинстве случаев считаться может простейшим лишь на небольшом интервале времени, однако очень часто исследования СМО проводят, принимая поток заявок простейшим. Это объясняется, во-первых, простотой проведения анализа при таком потоке и, во-вторых, тем, что простейший поток очень напряженный, а следовательно, можно предполагать, что при реальном потоке эффективность СМО будет не хуже, чем дал анализ при простейшем потоке. Теория массового обслуживания позволяет проводить анализ СМО и при других, более сложных, чем простейший поток заявок, учитывающих нестационарность последействие, т. е. зависимость между заявками. Рассматриваются также схемы с учетом возможности выхода из строя каналов обслуживания, системы со взаимопомощью и дублированием каналов. (1)

1.5 Стохастическое  программирование

Раздел математического  программирования, изучающий задачи со случайными коэффициентами, называется стохастическим программированием. Если для случайных величин, фигурирующих в задаче, на основании статистических и других исследований удается установить вероятностные характеристики (функцию распределения, математическое ожидание, дисперсию), то говорят, что задача решается в условиях риска. Если же никаких сведений о статистических закономерностях изменения случайных параметров не имеется, то получаем так называемую задачу в условиях неопределенности. Стохастическое программирование изучает задачи обоих указанных типов.

При постановке стохастической задачи не только формулируются ограничительные  условия и целевая функция, но сразу же устанавливается, какой план будет считаться допустимым и какой – оптимальным. В обычных (детерминированных) задачах допустимым называется план, удовлетворяющий системе ограничений, а оптимальным – доставляющий кроме того, функционалу наибольшее (наименьшее) значение. Для стохастической задачи эти определения будут далеко не полными. Действительно, план Х (х₁, х₂,...,х_n) может удовлетворять системе ограничений при одной совокупности значений случайных коэффициентов и не удовлетворять при другой. Аналогично, некоторый план может быть оптимальным для одного набора случайных коэффициентов функции цели и не оптимальным – для другого.

В отдельных задачах  найденный план не может быть впоследствии изменен даже при получении информации о поведении системы в будущем. Это имеет место в ситуациях, связанных с капитальным строительством. Например, нельзя менять расположение или хотя бы мощность перерабатывающих предприятий в зависимости от видов урожай. Всякий план такой задачи следует считать детерминированным.

В других задачах план можно откорректировать даже в ходе его выполнения. Так, если бы долгосрочные прогнозы погоды были достаточно надежными, оптимальное сочетание сельскохозяйственных культур можно было бы уточнять ежегодно: на засушливый год увеличивать посевы засухоустойчивых культур, на дождливый – влагоустойчивых. В подобных задачах план представляет собой набор случайных чисел, для которых в процессе решения находят нужные характеристики.

Рассмотрим теперь возможные  определения допустимого плана. Можно потребовать, чтобы набор значений переменных удовлетворял всем ограничениям задачи при любых реализациях случайных коэффициентов, и только такой план считать допустимым. В столь узкие рамки заключают решение в том случае, если малейшее нарушение хотя бы одного ограничений ведет к катастрофическим последствиям. Стохастическая задача с указанным определением допустимого плана называется жесткой. Она не позволяет корректировать найденное оптимальное решение, которое в силу этого всегда детерминировано.