БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ

Кафедра программного обеспечения информационных технологий

Факультет ФКСиС

Специальность ПОИТ

Контрольная работа №2

по дисциплине «Методы оптимизации»

Тема «Применение линейного программирования в сетевом планировании и управлении»

Вариант 4

Выполнил студент: Бордон Е.С.

группа 991051

Зачетная книжка № 99105004

Минск 2021

Задание 1:

Проект представлен сетевым графиком. Для каждой работы известна ее продолжительность t_ij и минимально возможное время выполнения d_ij. Пусть задан срок выполнения проекта t₀, а расчетное t_кр> t₀. Продолжительность выполнения работы (i,j) линейно зависит от суммы дополнительно вложенных средств х_ij и выражается соотношением:

t’_ij = t_ij - k_ijx_ij. Технологические коэффициенты k_ij известны.

Требуется найти: 1) критический путь, ранние и поздние сроки начала и

окончания работ, резервы времени, построить сетевой график;

2) построить линейный график (график Ганта);

3) такие t^н_ij, t^o_ij, x_ij, чтобы:

* срок выполнения всего комплекса работ не превышал заданной величины t₀;

* суммарное количество дополнительно вложенных средств было

минимальным;

* продолжительность выполнения каждой работы t’_ij была не меньше заданной

величины d_ij.

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 ед. времени. Необходимо сократить срок

проекта до t_o =60 ед. времени.

Целевая функция имеет вид:

F = х₁₂ + х₁₃ + х₁₄ + х₂₄ + х₂₅ + х₃₄ + х₃₆ + х₄₅ + х₄₆ + х₅₆ (min).

Запишем ограничения задачи:

а) срок выполнения проекта не должен превышать t_о = 60

t°₃₆ < 60; t°₄₆ < 60; t°₅₆ < 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).