Автор: Пользователь скрыл имя, 14 Апреля 2012 в 23:01, контрольная работа
теоретические вопросы и задачи: сетевое планирование, симплекс метод и транспортная
Искомый элемент равен 3
Для этого элемента запасы равны 80, потребности 63. Поскольку минимальным является 63, то вычитаем его.
x13
= min(80,63) = 63.
| x | x | 3 | 0 | 80 - 63 = 17 |
| 1 | x | 2 | x | 0 |
| x | 1 | x | 0 | 23 |
| 0 | 0 | 63 - 63 = 0 | 40 | 0 |
Искомый элемент равен 0
Для этого элемента запасы равны 17, потребности 40. Поскольку минимальным является 17, то вычитаем его.
x14 = min(17,40) = 17.
| x | x | 3 | 0 | 17 - 17 = 0 |
| 1 | x | 2 | x | 0 |
| x | 1 | x | 0 | 23 |
| 0 | 0 | 0 | 40 - 17 = 23 | 0 |
Искомый элемент равен 0
Для этого элемента запасы равны 23, потребности 23. Поскольку минимальным является 23, то вычитаем его.
x34 = min(23,23) = 23.
| x | x | 3 | 0 | 0 |
| 1 | x | 2 | x | 0 |
| x | 1 | x | 0 | 23 - 23 = 0 |
| 0 | 0 | 0 | 23 - 23 = 0 | 0 |
| 1 | 2 | 3 | 4 | Запасы | |
| 1 | 6 | 4 | 3[63] | 0[17] | 80 |
| 2 | 1[45] | 5 | 2[25] | 0 | 70 |
| 3 | 3 | 1[27] | 5 | 0[23] | 50 |
| Потребности | 45 | 27 | 88 | 40 |
В
результате получен первый опорный
план, который является допустимым,
так как все грузы из баз
вывезены, потребность магазинов
удовлетворена, а план соответствует
системе ограничений
2.
Подсчитаем число занятых
Значение целевой функции для этого опорного плана равно:
F(x) = 3*63 + 0*17 + 1*45 + 2*25 + 1*27 + 0*23 = 311
Этап II. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
u1 + v3 = 3; 0 + v3 = 3; v3 = 3
u2 + v3 = 2; 3 + u2 = 2; u2 = -1
u2 + v1 = 1; -1 + v1 = 1; v1 = 2
u1 + v4 = 0; 0 + v4 = 0; v4 = 0
u3 + v4 = 0; 0 + u3 = 0; u3 = 0
u3 + v2 = 1; 0 + v2 = 1; v2 = 1
| v1=2 | v2=1 | v3=3 | v4=0 | |
| u1=0 | 6 | 4 | 3[63] | 0[17] |
| u2=-1 | 1[45] | 5 | 2[25] | 0 |
| u3=0 | 3 | 1[27] | 5 | 0[23] |
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vi <= cij.
Минимальные затраты составят:
F(x)
= 3*63 + 0*17 + 1*45 + 2*25 + 1*27 + 0*23 = 311
Ответ:
Минимальные затраты составят 311 д.е.
Модели сетевого планирования и управления комплексом работ.
Построить сетевую модель
Варианты для индивидуального выполнения
Вариант 3
коды to tнв tп
работ
1-2 3 4 5
1-4 3 5 6
1-6 3 4 6
2-3 1 2 3
2-6 1 3 4
3-5 1 2 4
4-6 0 0 0
5-6 0 0 0
6-7 2 3 5
7-8 2 4 5
7-9 2 5 7
7-10 2 6 7
7-11 2 4 7
8-11 1 2 3
9-12 1 3 5
10-11 0 0 0
11-12 1 5 7
12-13 1 7 9
Решение:
Построим
график
Для определения средней (ожидаемой) длительности работ на основе экспертного опроса даются три временные характеристики (оценки времени выполнения работ):
1.
Оптимистическая (минимальная)
2. Пессимистическая (максимальная) оценка tnij ;
3.
Наиболее вероятная оценка tн.
Тогда среднее (ожидаемое) время выполнения работы определяется выражением
toжij
=
toж1-2 = и так для всех видов работ.
Определение степени неопределённости выполнения работ, лежащих на критическом пути:
и так для всех видов работ.
| коды работ | to | tнв | tп | tож | σ2 |
| 1-2 | 3 | 4 | 5 | 4,00 | 0,11 |
| 1-4 | 3 | 5 | 6 | 4,83 | 0,25 |
| 1-6 | 3 | 4 | 6 | 4,17 | 0,25 |
| 2-3 | 1 | 2 | 3 | 2,00 | 0,11 |
| 2-6 | 1 | 3 | 4 | 2,83 | 0,25 |
| 3-5 | 1 | 2 | 4 | 2,17 | 0,25 |
| 4-6 | 0 | 0 | 0 | 0,00 | 0,00 |
| 5-6 | 0 | 0 | 0 | 0,00 | 0,00 |
| 6-7 | 2 | 3 | 5 | 3,17 | 0,25 |
| 7-8 | 2 | 4 | 5 | 3,83 | 0,25 |
| 7-9 | 2 | 5 | 7 | 4,83 | 0,69 |
| 7-10 | 2 | 6 | 7 | 5,50 | 0,69 |
| 7-11 | 2 | 4 | 7 | 4,17 | 0,69 |
| 8-11 | 1 | 2 | 3 | 2,00 | 0,11 |
| 9-12 | 1 | 3 | 5 | 3,00 | 0,44 |
| 10-11 | 0 | 0 | 0 | 0,00 | 0,00 |
| 11-12 | 1 | 5 | 7 | 4,67 | 1,00 |
| 12-13 | 1 | 7 | 9 | 6,33 | 1,78 |
Время
завершения комплекса всех работ
равно времени наибольшего из
путей. Этот путь и называется критическим
путем. В нашем случае это путь под № 3,
он равен 28,17.
| № | Путь | Время |
| 1-2-3-5-6-7-10-11-12-13 | 4+2+2,17+0+3,17+5,5+4,67+6,33= | |
| 1-2-3-5-6-7-11-12-13 | 4+2+2,17+0+3,17+4,17+4,67+6, | |
| 1-2-3-5-6-7-8-11-12-13 | 4+2+2,17+0+3,17+3,83+2+4,67+6, | |
| 1-2-3-5-6-7-9-12-13 | 4+2+2,17+0+3,17+4,83+3+6,33= | |
| 1-2-6-7-10-11-12-13 | 4+2,83+3,17+5,5+0+4,67+6,33= | |
| 1-2-6-7-11-12-13 | 4+2,83+3,17+4,17+4,67+6,33=25, | |
| 1-2-6-7-8-11-12-13 | 4+2,83+3,17+3,83+2+4,67+6,33= | |
| 1-2-6-7-9-12-13 | 4+2,83+3,17+4,83+3+6,33=24,16 | |
| 1-6-7-10-11-12-13 | 4,17+3,17+5,5+0+4,67+6,33=23, | |
| 1-6-7-11-12-13 | 4,17+3,17+4,17+4,67+6,33=22,51 | |
| 1-6-7-8-11-12-13 | 4,17+3,17+3,83+2+4,67+6,33=24, | |
| 1-6-7-9-12-13 | 4,17+3,17+4,83+3+6,33=21,5 | |
| 1-4-6-7-10-11-12-13 | 4,83+0+3,17+5,5+0+4,67+6,33= | |
| 1-4-6-7-11-12-13 | 4,83+0+3,17+4,17+4,67+6,33=23, | |
| 1-4-6-7-8-11-12-13 | 4,83+0+3,17+3,83+2+4,67+6,33= | |
| 1-4-6-7-9-12-13 | 4,83+0+3,17+4,83+3+6,33=22,16 |
Увеличение критического пути приводит к задержке проекта, а сокращение к ускорению выполнения проекта.