Сетевые методы планирования и управления

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

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

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

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

Рис. № 1

События 1 обозначает, что началась работа a. События 2 фиксирует окончание работы а и начало работ b и с. Иначе, условием для начала работы b и работы с является окончание а. Работу d нельзя начать до окончания b, а работу е – до окончания работы с. Наступление события 5 знаменует собой окончание работ d и е и одновременно завершение всего комплекса.

Таким образом, все боты, включенные в комплекс, участвуют в достижении конечной цели, и все они должны быть выполнены.

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

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

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

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

Следующее основное правило, которое необходимо соблюдать в сетевых графиках, гласит: график не должен содержать циклов. Пример цикла показан на рис. 2

Рис. № 2

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

Достоинства и особенности системы сетевого планирования и управления. Преимущества этой системы заключаются в том, что она:

1.                  облегчает планирование и отражает ход работ;

2.                  дает документальное изложение плана;

3.                  заблаговременно сосредоточивает внимание руководства на трудных участках;

4.                  расширяет связи;

5.                  показывает, какая требуется координация работ;

6.                  экономит время на том, что информация о тысячах событий и работ может быть быстро обработана на вычислительной машине;

7.                  объединяет все элементы программы с той подробностью, которая нужна  для руководства каждого уровня;

8.                  обладает большой гибкостью;

9.                  предсказывает вероятность успеха;

10.             позволяет достичь сокращения сроков выполнения (в отдельных случаях  до 50%) важных комплексов и значительной экономии затрат.

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

1.5             Линейное программирование

              Линейное программирование — математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.

              Линейное программирование является частным случаем выпуклого программирования, которое в свою очередь является частным случаем математического программирования. Одновременно оно — основа нескольких методов решения задач целочисленного и нелинейного программирования. Одним из обобщений линейного программирования является дробно-линейное программирование. Многие свойства задач линейного программирования можно интерпретировать также как свойства многогранников и таким образом геометрически формулировать и доказывать их. Термин «программирование» нужно понимать в смысле «планирования». Он был предложен в середине 1940-х годов Джорджем Данцигом, одним из основателей линейного программирования, ещё до того, как компьютеры были использованы для решения линейных задач оптимизации.

              Математическая формулировка задачи линейного программирования:

              Нужно определить максимум линейной целевой функции (линейной формы)

при условиях

Иногда на xi также накладывается некоторый набор ограничений в виде равенств, но от них можно избавиться, последовательно выражая одну переменную через другие и подставляя её во всех остальных равенствах и неравенствах (а также в функции f).

Такую задачу называют «основной» или «стандартной» в линейном программировании.

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

2.     Практическое применение

2.1  Динамическое программирование

Задача о загрузке корабля

В качестве примера численного решения рассмотрим "задачу о загрузке корабля", которую в других эквивалентных постановках называют "задачей о рюкзаке" или "задачей линейного раскроя".

Пусть имеется корабль грузоподъемности W, который может быть загружен предметами N типов. Если обозначить через Wk и Ck вес и ценность предмета k-го типа и через Xk количество таких предметов, то можно поставить задачу загрузки корабля грузом максимальной ценности в виде:

максимизировать

при условиях 

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

Поскольку нам безразлично, в каком порядке грузить наши предметы, то вообразим искусственный n-шаговый процесс, на первом шаге которого загружается X предметов n -го типа (на втором n-1 -го, затем n-2 -го и на последнем - первого типа). Тогда, обозначив через Fn(W) суммарную ценность загрузки в n-шаговом процессе при заданной грузоподъемности W и при использовании оптимальной политики, на основе принципа оптимальности сводим задачу к системе рекуррентных соотношений

,

где область максимизации определяется целыми значениями X в диапазоне от нуля до целой части отношения W / Wn.

Пусть Xn(W)-оптимальное количество предметов, загружаемое на первом шаге n - шагового процесса при начальной грузоподъемности W.

Пример. Решим поставленную задачу при N=3, C1=8, C2=7, C3=4, W=10, W1=4, W2=3, W3=2.

При поиске F2(W) приходится перебирать значения X в диапазоне от 0 до целой части отношения W к W2 и выбирать среди соответствующих значений максимизируемой функции максимальное. Например, при W=10 перебираем X, равные 0, 1, 2, 3 и

Аналогично отыскиваем значения F3(W) и X3(W).

Полученная таблица позволяет найти оптимальную политику загрузки при любом W, не превышающем 10.

Так при W=8 оптимальное количество предметов третьего типа (загружаемых на первом шаге 3 - шагового процесса) равно X3(8)=1, оптимальное количество предметов второго типа (загружаемых на первом шаге оставшегося 2 - шагового процесса) равно X2(8-2 1)=X2(6)= 1, оптимальное количество предметов первого типа (загружаемых на последнем шаге 3-шагового процесса) равно X1(6-3ґ2) = X1(0) = 0.

При W=10 возникают два варианта оптимальной загрузки;

Приведенный пример еще раз показывает, что решение методом динамического программирования обеспечивает получение политики при любом значении W, тогда как другие подходы к решению дают лишь частное

решение.

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

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

Задача

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

Администрация университета разрешила посещение всеми студентами всех библиотек обоих корпусов. При раздельном использовании библиотек между корпусами, которыми они принадлежали, коэффициент загруженности равнялся 95,8%:действительно,

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

Для анализа задачи улучшения использования библиотек  необходимо сравнение двух вариантов, а именно:

(а) варианта с независимыми обслуживающими системами типа (М/М/2): (GD//) при =10 студентов в час и =5,217 обслуживаний студентов в час

(б) варианта с одной очередью типа (М/М/4): (GD//) при =2*10=20 студентов в час и =5,217 обслуживаний студентов в час.

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

Коэффициент загруженности во втором случае будет таким же, как и  в первом случае, а именно

Объединение всех четырех библиотек в рамках одной системы не приводит на первый взгляд к  эффекту. Если, однако, рассмотреть другие показатели, это первое впечатление не подтвердится. Вычислим Wq (среднее время ожидания студентом обслуживания от момента прихода в библиотеку до момента выдачи книг) в первом и втором случаях. Тогда для с=2 будем иметь