Учебная работа № 5041. «Контрольная Сетевые модели, вариант 6
Учебная работа № 5041. «Контрольная Сетевые модели, вариант 6
Содержание:
Контрольная работа №2 СЕТЕВЫЕ МОДЕЛИ
1. Транспортная задача.
1.1. Записать математическую модель транспортной задачи с промежуточными пунктами, заданной сетью на рис.85 и таблицей 7
1.2. Найти оптимальное решение задачи из п.1.1.
Примечание. Конечный результат должен быть записан для исходной сети с промежуточными пунктами, а не для вспомогательной классической транспортной задачи.
1.3. Произвести анализ на чувствительность задачи из п.1.1.
1.3.1. Найти наименьшее значение каждого из коэффициентов C25 и C47 в исходной сети с промежуточными пунктами, при которых прежнее решение остается оптимальным.
1.3.2. Допустим, что один избыток запасов Ai (i=1,3,5,7) увеличился на ?. Найти приращение целевой функции при ?=1, а также предельное значение ?, при котором прежнее решение остается оптимальным.
Примечание. Для каждого Ai (i=1,3,5,7) показать цикл перераспределения на матрице условий.
1.3.3. Допустим, что один избыток запасов Ai (i=1,3,5) увеличился на ? одновременно с таким же увеличением потребности Ai+1. Найти приращение целевой функции при ?=1, а также предельное значение ?, при котором прежнее решение остается оптимальным.
Примечание. Для каждой пары Ai иAi+1(i=1,3,5) показать цикл перераспределения на матрице условий.
2. Задача коммивояжера.
2.1. Записать математическую модель для симметричной(cij=cji ) задачи коммивояжера, заданной сетью на рис.85 и таблицей 7 (параметры Ai во внимание не принимаются).
2.2. Найти оптимальное решение модели из п.2.1.
Выдержка из похожей работы
из сети все выходящие из пронумерованных
вершин дуги, Нумеруем в произвольном
порядке вершины, в которые не входит ни
одна дуга, произвольным образом
возрастающими по порядку номерами, Шаг
2 проделываем до тех пор, пока не дойдем
до конечной вершины, которой присваиваем
следующий по порядку номер,
В результате правильной нумерации
вершин сетевой график, приведенный
на рис, 4 примет вид
Рис,5
Номера
работ на дугах соответственно заменены
продолжительностью их выполнения
(продолжительность фиктивной работы
соответствующей дуги-связи полагаем
равной 0),
Рассмотрим
основные временные параметры сетевого
графика, Пусть tij
–продолжительность
работы, для которой соответствующая
дуга (i,
j)
в сетевом
графике имеет в качестве начальной –
вершину с номером i
, а в качестве
конечной – вершину с номером j,
Ранним
сроком начала работы (i,
j)
называется наименьшее допустимое время
tijPH
, когда может
быть начато ее выполнение,
Если
работа начата в ранний срок, то время
ее окончания tijP0
называется
ранним сроком окончания
tijPН
= tijPО-tij
Ранний
срок начала всех работ, для которых
вершина i
– начальная,
называется ранним сроком наступления
события i
и обозначается TiP,
Ранний
срок наступления конечного события
называется критическим временем и
обозначается Ткр,
Таким образом,
критическое
время – это минимальный срок, за
который может быть выполнен весь комплекс
работ,
Каждый
путь из начальной вершины в конечную,
состоящий из дуг (работ) и дуг-связей
продолжительностью Ткр,
называется критическим путем, а работы,
составляющие такие пути – критическими
работами,
Поздними
сроками начала и окончания работы
(i,
j)
называется
наибольшее допустимое время начала
(tijПН)
и окончания (tijПO)
этой работы без нарушения сроков
выполнения всего комплекса работ,
Очевидно:
tijПН
= tijПО-tij,
Наиболее
поздний из поздних сроков окончания
работ, входящих в вершину j,
называется поздним сроком наступления
события j
и обозначается ТjП,
Рассмотрим
работу (i,
j),
Плановая
продолжительность этой работы равна
tij,
Максимально
допустимое время, на которое можно
увеличить продолжительность работы
(i,
j)
или задержать начало ее выполнения, при
котором не изменится время выполнения
всего проекта, называется полным резервом
Rij
времени
этой работы, Он равен:
Rij
= TjП
— TiP
– tij
