БИЛЕТ 10 ВОПРОС 1 Методика определения состава работ критического пути структурного плана

Для того чтобы определить состав работ критического пути структурного плана, необходимо рассчитать полные резервы времени всех работ, которые принадлежат данному структурному плану. Если полный резерв времени какой – либо работы =0, то эта работа входит в состав работ критического пути. Таким образом выясняется, как проходит критический путь, то есть какие работы в критическом пути.

БИЛЕТ 10 ВОПРОС 2 Транспортная задача ЛП

ТЗЛП заключается в определении объема перевозок от поставщиков к потребителям, если известны выпуск продукции у каждого поставщика и потребности потребителей; затраты на перемещение грузов от поставщиков к потребителям. План грузоперевозок для им.min затраты. Причем это могут быть затраты денежных средств, транспортных работ или перевозок.

Особенности транспортной задачи

1) Все ограничения имеют вид равенств

2) Каждая переменная входит всего 2 ограничения.

3) Коэффициент при переменных в ограничениях =1

Решение задач ТЗЛП включает 2 основных этапа построение опорного решения (начального плана перевозок) и построение оптимального решения.

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

Условия и метод построения оптимального решения транспортной задачи.

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

Условие потенциальности показывает, что разность потенциалов потребителя и поставщика = стоимости перевозки между ними, если перевозка осуществляется, и не больше стоимости перевозки при её отсутствии.

Алгоритм решения транспортной задачи методом потенциалов состоит из двух этапов: предварительного и общего. Первый включает: 1. построение опорного решения 2. присвоение и расчёт системы потенциалов 3. проверка первоначального плана на оптимальность. Если опорное решение не является оптимальным, то переходят ко второму (общему) этапу, который включает: 1. улучшение плана перевозок 2. исправление системы потенциалов 3. проверка улучшенного плана на оптимальность. Общий шаг циклически выполняется до получения оптимального плана перевозок.

Алгоритм решения транспортной задачи на сети. В ряде случаев транспортную задачу целесообразно решать в сетевой постановке, отличающейся наглядностью. Транспортная сеть это совокупность вершин или узлов (пункты отправления и приёма грузов, промежуточные пункты) и соединяющих их транспортных коммуникаций или звеньев. На каждом звене проставляются удельная стоимость перевозки груза по данному транспортному участку Сij , а при ограниченности пропускной способности звена также и её максимальное значение dij. Около каждой вершины в скобках со знаком + или – проставляются объемы отправления и приёма грузов. Соответственно.