- •1 Методы и модели линейного программирования
- •1.1. Основные положения
- •1.2. Симплексный метод
- •1.3. Метод Гомори. Целочисленное решение
- •1.4. Двойственная задача
- •1.4.1. Анализ устойчивости двойственных оценок
- •1.5. Решение задачи линейного программирования средствами Microsoft Excel
- •1.6. Задачи с булевыми переменными
- •1.7. Варианты заданий линейного программирования
- •2.Динамическое программирование
- •2.1. Суть метода динамического программирования
- •2.2. Задача о рюкзаке. Уравнение Беллмана для задачи о рюкзаке.
- •2.3. Реализации метода динамического программирования для задачи о рюкзаке.
- •2. Двухиндексные задачи линейного программирования. Стандартная транспортная задача (тз).
- •Исходные параметры модели тз
- •1.4. Варианты заданий линейного программирования
- •3. Сетевое моделирование
- •3.1. Основные положения
- •3.2. Сетевой график и правила его построения
- •3.3 Расчет параметров сетевых графиков
- •3.4. Оптимизация сети методом время-стоимость
- •3.5 Варианты заданий сетевого планирования
- •4. Правила оформления курсового проекта
- •Библиографический список
- •Приложение 1
- •Курсовой проект
3.2. Сетевой график и правила его построения
Сетевой график представляет собой графическое изображение планируемого комплекса работ, в котором отражаются взаимосвязи отдельных работ и последовательности их выполнения.
В основе сетевого графика лежит сеть комплекса, изображаемая с помощью ориентированного графа, отображающего отношения порядка отдельных работ, составляющих этот комплекс.
Р аботы (дуги работы) в сетевых графиках отображаются в виде стрелок из сплошных линий ( ), дуги, показывающие связь между отдельными работами и не требующие для своего осуществления ни затрат времени, ни ресурсов, обозначаются пунктирными стрелками ( ). Событие обычно обозначается кружками и нумеруются числами натурального ряда.
Ориентированным будет такой граф, у которого все дуги направленные. В свою очередь направленными дугами называют такие дуги графа, граничные вершины каждой из которых подразделяются на начальные и конечные. Соответственно по отношению к начальной вершине дугу называют выходящей, а относительно конечной вершины - входящей.
Одна из важнейших характеристик сетевого графика - путь. Путь в ориентированном связном графе - это ориентированная цепь различных дуг, в которой каждая начальная вершина следующей дуги совпадает с конечной вершиной предшествующей дуги. Начало пути в графе определяется начальной вершиной первой дуги в ориентированной цепи дуг, конец пути характеризуется конечной вершиной последней дуги.
При построении сетевого графика пользуются следующими правилами:
Исходное событие, соответствующее началу выполнения работ комплекса, нужно помещать в левой, а завершающее событие, определяющее достижение конечной цели, в правой части графика.
В целях более быстрого нахождения циклов нужно стремиться к тому, чтобы дуги-работы имели направление слева на право. Наличие дуги, имеющей противоположное направление, может свидетельствовать о появлении цикла.
По возможности нужно добиваться такого построения сети, чтобы отдельные дуги не пересекались бы друг с другом.
Нумерацию событий нужно производить так, чтобы каждое следующее событие приобретало возрастающий номер по отношению к предшествующему.
Любые две вершины (события) сети, одна из которых по отношению к данной дуге-работе представляет начальное событие, а другая - конечное событие, нужно соединять одной (и только одной!) дугой.
Не должно быть дуг, которые ниоткуда не выходят и никуда не входят.
Примеры правильного и неверного построения сетей приведены, соответственно, на рисунке 3.1. а) и б).
а) б)
Рисунок 3.1. Примеры построения сети
3.3 Расчет параметров сетевых графиков
Временные параметры сетевого графика – расчетные величины, количественно характеризующие моменты начала и окончания работ и событий, а также соответствующие резервы времени:
Ранний срок наступления j-го события - наиболее ранний (минимальный) из возможных моментов наступления данного события при заданной продолжительности работ:
Поздний срок наступления i-го события - наиболее поздний (максимальный) из допустимых моментов наступления данного события, при котором еще возможно выполнение всех последующих работ в установленный срок:
Ранний срок начала работы - наиболее ранний (минимальный) из возможных моментов начала данной работы при заданной продолжительности работ:
Ранний срок окончания работы - наиболее ранний (минимальный) из возможных моментов окончания данной работы при заданной продолжительности работ:
Поздний срок окончания работы - наиболее поздний (максимальный) из допустимых моментов окончания данной работы, при котором еще возможно выполнение всех последующих работ в установленный срок. Он численно равен позднему сроку наступления конечного события этой работы:
Поздний срок начала работы - наиболее поздний (максимальный) из допустимых моментов начала данной работы, при котором еще возможно выполнение всех последующих работ в установленный срок: .
Резерв времени события - это промежуток времени, на который может быть отсрочено наступление события i без нарушения сроков завершения всего комплекса, определяется как разность между поздним и ранним сроками наступления этого события: .
Полный резерв времени работы - максимальное время, на которое можно отсрочить начало или увеличить продолжительность работы без изменения общего срока выполнения комплекса: .
Свободный резерв времени работы - максимальное время, на которое можно отсрочить начало или увеличить продолжительность работы не изменив при этом ранних сроков наступления начального и конечного событий: .
Критический путь - максимальный по продолжительности путь в сети комплекса, идущий от исходного события к завершающему.