БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ
Кафедра программного обеспечения информационных технологий
Факультет ФКСиС
Специальность ПОИТ
Контрольная работа №2
по дисциплине «Методы оптимизации»
Тема «Применение линейного программирования в сетевом планировании и управлении»
Вариант 4
Выполнил студент: Бордон Е.С.
группа 991051
Зачетная книжка № 99105004
Минск 2021
Задание 1:
Проект представлен сетевым графиком. Для каждой работы известна ее продолжительность tij и минимально возможное время выполнения dij. Пусть задан срок выполнения проекта t0, а расчетное tкр> t0. Продолжительность выполнения работы (i,j) линейно зависит от суммы дополнительно вложенных средств хij и выражается соотношением:
t’ij = tij - kijxij. Технологические коэффициенты kij известны.
Требуется найти: 1) критический путь, ранние и поздние сроки начала и
окончания работ, резервы времени, построить сетевой график;
2) построить линейный график (график Ганта);
3) такие tнij, toij, xij, чтобы:
* срок выполнения всего комплекса работ не превышал заданной величины t0;
* суммарное количество дополнительно вложенных средств было
минимальным;
* продолжительность выполнения каждой работы t’ij была не меньше заданной
величины dij.
4) по найденным данным найти новый критический путь, ранние и поздние
сроки начала и окончания работ, резервы времени, построить сетевой график;
5) построить линейный график;
6) сделать выводы;
Номер задачи |
Пара-метры |
Работы |
t0 |
||||||||||
1,2 |
1,3 |
1,4 |
2,4 |
2,5 |
3,4 |
3,6 |
4,5 |
4,6 |
5,6 |
|
|||
4 |
tij |
19 |
10 |
35 |
18 |
20 |
9 |
22 |
17 |
20 |
18 |
60 |
|
dij |
16 |
5 |
25 |
13 |
15 |
6 |
17 |
13 |
16 |
14 |
|||
kij |
0,25 |
0,07 |
0,1 |
0,2 |
0,13 |
0,15 |
0,06 |
0,4 |
0,2 |
0,1 |
Решение:
Запишем все данные на сетевой график (Рис.1) и рассчитаем сроки свершения событий.
Рис1. Исходный сетевой график
Если все работы проекта будут выполняться в обычном режиме, то tкр = 72, т.е. проект может быть выполнен за 72 ед. времени. Необходимо сократить срок
проекта до to =60 ед. времени.
Целевая функция имеет вид:
F = х12 + х13 + х14 + х24 + х25 + х34 + х36 + х45 + х46 + х56 (min).
Запишем ограничения задачи:
а) срок выполнения проекта не должен превышать tо = 60
t°36 < 60; t°46 < 60; t°56 < 60;
б) продолжительность выполнения каждой работы должна быть не меньше минимально возможного времени:
; ; ; ;
; ; ; ;
; ;
в) зависимость продолжительности работ от вложенных средств:
; ;
; ;
; ;
; ;
; ;
г) время начала выполнения каждой работы должно быть не меньше времени окончания непосредственно предшествующей ей работы:
; ; ; ; ;
; ; ; ;
; ; ; ; ;
д) условие неотрицательности неизвестных:
; ; ; .
Составим таблицу для ввода исходных данных:
Рис2. Excel
Ячейки B3:АЕ3 отведены под переменные. В ячейках B4:АЕ39 и АН5:Y39
записаны коэффициенты при переменных, свободные коэффициенты системы
ограничений и коэффициенты целевой функции.
В ячейке W4 введем формулу: AF4 = СУММПРОИЗВ(B3:АЕ3; B4:АЕ4) и
скопируем ее вниз до ячейки AF39. Ячейка AF4 соответствует значению целевой
функции, a AF5:W39 – левым частям системы ограничений.
Далее обрабатываем данные согласно параметрам (рис.3). Модель полностью введена. Нажимаем кнопку НАЙТИ РЕШЕНИЕ. Найденное оптимальное решение (рис.4) представляем на сетевом графике (рис.5).
Рис. 3 Параметры поиска решения
Рис 4 Найденное оптимальное решение Excel
Рис. 5 Оптимальное решение
Итак, при дополнительном вложении 87 ден.ед., проект может быть
выполнен за 60 ед. времени. При этом средства распределятся следующим
образом: 12 ден.ед. - в работу (1,2), 20 ден.ед. - в работу (1,4), 5 ден.ед. - в
работу (2,4), 10 ден.ед. - в работу (4,5) и 40 ден.ед. - в работу (5,6).