Лабораторная работа: Оптимизация сетевого графика по времени
Цель Научиться решать задачу сетевого планирования с одновременной оптимизацией средствами EXCEL.
Дата добавления на сайт: 19 февраля 2025
Лабораторная работа
Оптимизация сетевого графика по времени
Цель Научиться решать задачу сетевого планирования с одновременной оптимизацией средствами EXCEL.
Постановка задачи 1.
Проект представлен сетевым графиком. Для каждой работы известна ее продолжительность tij и минимально возможное время выполнения dij. Пусть задан срок выполнения проекта t0, а расчетное tкр > t0. Продолжительность выполнения работы (i, j) линейно зависит от суммы дополнительно вложенных средств хij и выражается соотношением: t’ij = tij - kijxij. Технологические коэффициенты kij известны.
Требуется найти такие t н ij, toij, xij, чтобы:
срок выполнения всего комплекса работ не превышал заданной величины t0;
суммарное количество дополнительно вложенных средств было минимальным;
продолжительность выполнения каждой работы t’ij была не меньше заданной величины dij.
| Номер задачи | Параметры | Работы | Срок выполнения проекта t0 | |||||||||
| 1,2 | 1,3 | 1,4 | 2,4 | 2,5 | 3,4 | 3,6 | 4,5 | 4,6 | 5,6 | |||
| tij | 7 | 11 | 16 | 6 | 10 | 8 | 13 | 12 | 14 | 9 | ||
| * | dij | 4 | 8 | 13 | 5 | 7 | 6 | 10 | 10 | 11 | 7 | 34 |
| kij | 0,1 | 0,3 | 0,2 | 0,05 | 0,25 | 0,2 | 0,12 | 0,5 | 0,08 | 0,02 | ||
| tij | 9 | 12 | 18 | 8 | 12 | 5 | 12 | 10 | 13 | 12 | ||
| 1 | dij71015610387121035 | |||||||||||
| kij | 0,05 | 0,2 | 0,25 | 0,08 | 0,15 | 0,1 | 0,06 | 0,05 | 0,1 | 0,5 | ||
| tij | 10 | 13 | 24 | 9 | 11 | 17 | 10 | 15 | 15 | 20 | ||
| 2 | dij | 5 | 9 | 11 | 6 | 9 | 12 | 7 | 13 | 13 | 15 | 56 |
| kij | 0,08 | 0,25 | 0,1 | 0,15 | 0,3 | 0,2 | 0,08 | 0,4 | 0,2 | 0,1 | ||
| tij | 6 | 13 | 20 | 9 | 14 | 16 | 15 | 10 | 17 | 13 | ||
| 3 | dij | 5 | 10 | 16 | 7 | 11 | 13 | 12 | 7 | 15 | 9 | 40 |
| kij | 0,05 | 0,25 | 0,3 | 0,07 | 0,15 | 0,1 | 0,05 | 0,03 | 0,14 | 0,5 | ||
| tij | 19 | 10 | 35 | 18 | 20 | 9 | 22 | 17 | 20 | 18 | ||
| 4 | dij | 16 | 5 | 25 | 13 | 15 | 6 | 17 | 13 | 16 | 14 | 60 |
| kij | 0,25 | 0,07 | 0,1 | 0,2 | 0,13 | 0,15 | 0,06 | 0,4 | 0,2 | 0,1 | ||
| tij | 6 | 15 | 26 | 7 | 11 | 10 | 11 | 12 | 13 | 17 | ||
| 5 | dij | 5 | 13 | 20 | 5 | 9 | 7 | 8 | 9 | 12 | 15 | 50 |
| kij | 0,07 | 0,2 | 0,3 | 0,1 | 0,05 | 0,1 | 0,04 | 0,05 | 0,15 | 0,5 | ||
| tij | 10 | 18 | 16 | 12 | 7 | 13 | 11 | 10 | 13 | 12 | ||
| 6 | dij71412105987121042 | |||||||||||
| kij | 0,5 | 0,1 | 0,25 | 0,4 | 0,2 | 0,15 | 0,3 | 0,5 | 0,1 | 0,5 | ||
| tij | 9 | 18 | 21 | 7 | 12 | 19 | 20 | 9 | 15 | 20 | ||
| 7 | dij | 6 | 14 | 18 | 4 | 9 | 15 | 16 | 6 | 13 | 15 | 33 |
| kij | 0,2 | 0,25 | 0,15 | 0,4 | 0,3 | 0,12 | 0,2 | 0,2 | 0,2 | 0,1 | ||
| tij | 15 | 8 | 7 | 5 | 13 | 11 | 7 | 15 | 17 | 13 | ||
| 8 | dij | 12 | 5 | 4 | 3 | 10 | 8 | 4 | 12 | 15 | 9 | 47 |
| kij | 0,25 | 0,2 | 0,15 | 0,1 | 0,3 | 0,4 | 0,2 | 0,25 | 0,14 | 0,5 | ||
| tij | 13 | 22 | 19 | 17 | 10 | 25 | 12 | 13 | 20 | 18 | ||
| 9 | dij | 10 | 18 | 15 | 14 | 7 | 21 | 9 | 10 | 16 | 14 | 49 |
| kij | 0,3 | 0,1 | 0,05 | 0,2 | 0,4 | 0,2 | 0,25 | 0,3 | 0,2 | 0,1 | ||
| tij | 16 | 12 | 10 | 8 | 3 | 9 | 11 | 16 | 13 | 17 | ||
| 10 | dij | 10 | 7 | 6 | 5 | 2 | 7 | 9 | 10 | 12 | 15 | 29 |
| kij | 0,2 | 0,1 | 0,16 | 0,3 | 0,25 | 0,1 | 0,4 | 0,2 | 0,15 | 0,5 |
1 Запишем все данные на сетевой график и рассчитаем сроки свершения событий.
Расчеты показали, что срок выполнения проекта tкр = 40, т.е. превышает директивный срок t0 = 34.
2. Составление математической модели задачи.
Целевая функция имеет вид
f= х12 + х13 + х14 + х34 + х35 + х45 + х14 + х34 + х35 + х45 (min).
Запишем ограничения задачи:
а) срок выполнения проекта не должен превышать t0 = 34:
tо36 Ј 34; tо46 Ј 34; tо56 Ј 34;
б) продолжительность выполнения каждой работы должна быть не меньше минимально возможного времени:
tо12 - t н 12 і 4; tо34 - t н 34 і 6;
tо13 - t н 13 і 8; tо36 - t н 36 і 10;
tо14 - t н 14 і 13; tо45 - t н 45 і 10;
tо24 - t н 24 і 5; tо46 - t н 46 і 11;
tо25 - t н 25 і 7; tо56 - t н 56 і 7;
в) зависимость продолжительности работ от вложенных средств:
tо12 - t н 12 = 7 - 0,1x12; tо13 - t н 13 = 11 - 0,3x13;
tо14 - t н 14 = 16 - 0,2x14; tо24 - t н 24 = 6 - 0,05x24;
tо25 - t н 25 = 10 - 0,25x25; tо34 - t н 34 = 8 - 0,2x34;
tо36 - t н 36 = 13 - 0,12x36; tо45 - t н 45 = 12 - 0,5x45;
tо46 - t н 46 = 14 - 0,08x46; tо56 - t н 56 = 9 - 0,02x56;
г) время начала выполнения каждой работы должно быть не меньше времени окончания непосредственно предшествующей ей работы:
t н 12 = 0; t н 13 = 0; t н14 = 0;
t н 24 і tо12; t н 25 і tо12;
t н 34 і tо13; t н 36 і tо13;
t н 45 і tо14; t н 45 і tо24;
t н 45 і tо34;
t н 46 і tо14; t н 46 і tо24;
t н 46 і tо34;
t н 56 і tо25; t н 56 і tо45;
д) условие неотрицательности неизвестных:
t н ij і 0, tоij і 0, xij і 0, (i, j) О .
3.Численное решение задачи:
Табличную запись математической модели см. табл. 2.2.
Решив данную задачу средствами EXCEL, получаем следующие результаты:
t н12 = 0; tо12 = 7; t н13 = 0; tо13 = 8; t н14 = 0; tо14 = 15;
t н 24 = 7; tо24 = 13; t н 25 = 7; tо25 = 17;
t н 34 = 8; tо34 = 15; t н 36 = 8; tо36 = 21;
t н45 = 15; tо45 = 25; t н 56 = 25; tо56 = 34;
x12 = 0; x13 = 10; x14 = 5; x24 = 0; x25 = 0;
x34 = 5; x36 = 0; x45 =4; x46 =0; x56 = 0;
fmin = 24.
4.Анализ полученных результатов. Чтобы выполнить работы проекта за директивное время t0=34, необходимо дополнительно вложить 24 ден. ед. При этом средства распределятся следующим образом: 10 ден. ед. - в работу (1,3), 5 ден. ед. - в работу (1,4), 5 ден. ед. - в работу (3,4) и 4 ден. ед. - в работу (4,5), что приведет к сокращению продолжительности работы (1,3) на 3 дня, работы (1,4) - на 1 день, работы (3,4) - на 1 день и работы (4,5) - на 2 дня. Сокращение срока реализации проекта за счет вложения дополнительных средств составит 6 ед. времени.
Постановка задачи 2.
Проект представлен сетевым графиком. Для каждой работы известна ее продолжительность tij и минимально возможное время выполнения dij. Для сокращения срока реализации проекта выделено В ден. ед. Вложение дополнительных средств хij в работу (i, j) сокращает время ее выполнения до t’ij = tij - kijxij. Технологические коэффициенты kij известны.
Требуется найти такие t н ij, toij, xij, чтобы:
время выполнения всего комплекса работ было минимальным;
количество используемых дополнительных средств не превышало B ден. ед.;
продолжительность выполнения каждой работы была не меньше заданной величины dij.
| Номер задачи | Пара- метры | Работы | Срок выполнения проекта t0 | |||||||
| 1,2 | 1,3 | 1,4 | 2,4 | 2,5 | 3,4 | 3,6 | 4,5 | |||
| tij | 7 | 11 | 16 | 6 | 10 | 8 | 13 | 12 | ||
| * | dij | 4 | 8 | 13 | 5 | 7 | 6 | 10 | 10 | 34 |
| kij | 0,1 | 0,3 | 0,2 | 0,05 | 0,25 | 0,2 | 0,12 | 0,5 | ||
| tij | 9 | 12 | 18 | 8 | 12 | 5 | 12 | 10 | ||
| 1 | dij7101561038735 | |||||||||
| kij | 0,05 | 0,2 | 0,25 | 0,08 | 0,15 | 0,1 | 0,06 | 0,05 | ||
| tij | 10 | 13 | 24 | 9 | 11 | 17 | 10 | 15 | ||
| 2 | dij | 5 | 9 | 11 | 6 | 9 | 12 | 7 | 13 | 56 |
| kij | 0,08 | 0,25 | 0,1 | 0,15 | 0,3 | 0,2 | 0,08 | 0,4 | ||
| tij | 6 | 13 | 20 | 9 | 14 | 16 | 15 | 10 | ||
| 3 | dij | 5 | 10 | 16 | 7 | 11 | 13 | 12 | 7 | 40 |
| kij | 0,05 | 0,25 | 0,3 | 0,07 | 0,15 | 0,1 | 0,05 | 0,03 | ||
| tij | 19 | 10 | 35 | 18 | 20 | 9 | 22 | 17 | ||
| 4 | dij | 16 | 5 | 25 | 13 | 15 | 6 | 17 | 13 | 60 |
| kij | 0,25 | 0,07 | 0,1 | 0,2 | 0,13 | 0,15 | 0,06 | 0,4 | ||
| tij | 6 | 15 | 26 | 7 | 11 | 10 | 11 | 12 | ||
| 5 | dij | 5 | 13 | 20 | 5 | 9 | 7 | 8 | 9 | 50 |
| kij | 0,07 | 0,2 | 0,3 | 0,1 | 0,05 | 0,1 | 0,04 | 0,05 | ||
| tij | 10 | 18 | 16 | 12 | 7 | 13 | 11 | 10 | ||
| 6 | dij7141210598742 | |||||||||
| kij | 0,5 | 0,1 | 0,25 | 0,4 | 0,2 | 0,15 | 0,3 | 0,5 | ||
| tij | 9 | 18 | 21 | 7 | 12 | 19 | 20 | 9 | ||
| 7 | dij | 6 | 14 | 18 | 4 | 9 | 15 | 16 | 6 | 33 |
| kij | 0,2 | 0,25 | 0,15 | 0,4 | 0,3 | 0,12 | 0,2 | 0,2 | ||
| tij | 15 | 8 | 7 | 5 | 13 | 11 | 7 | 15 | ||
| 8 | dij | 12 | 5 | 4 | 3 | 10 | 8 | 4 | 12 | 47 |
| kij | 0,25 | 0,2 | 0,15 | 0,1 | 0,3 | 0,4 | 0,2 | 0,25 | ||
| tij | 13 | 22 | 19 | 17 | 10 | 25 | 12 | 13 | ||
| 9 | dij | 10 | 18 | 15 | 14 | 7 | 21 | 9 | 10 | 49 |
| kij | 0,3 | 0,1 | 0,05 | 0,2 | 0,4 | 0,2 | 0,25 | 0,3 | ||
| tij | 16 | 12 | 10 | 8 | 3 | 9 | 11 | 16 | ||
| 10 | dij | 10 | 7 | 6 | 5 | 2 | 7 | 9 | 10 | 29 |
| kij | 0,2 | 0,1 | 0,16 | 0,3 | 0,25 | 0,1 | 0,4 | 0,2 |
Решение варианта *.
1. Запишем все данные на сетевой график.
По первоначальному условию tкр = 22, т.е. проект может быть выполнен за 22 ед. времени.
2. Составление математической модели задачи.
Чтобы однозначно записать целевую функцию, добавим на сетевом графике фиктивную работу (5,6).
Целевая функция имеет вид tкр = tо56 (min).
Запишем ограничения задачи:
а) сумма вложенных средств не должна превышать их наличного количества:
х12 + х13 + х14 + х23 + х34 + х35 + х45 Ј 47;
б) продолжительность выполнения каждой работы должна быть не меньше минимально возможного времени:
tо12 - t н 12 і 3; tо34 - t н 34 і 5;
tо13 - t н 13 і 4; tо35 - t н 35 і 4;
tо14 - t н 14 і 1; tо45 - t н 45 і 2;
tо23 - t н 23 і 2; tо56 - t н 56 = 0;
в) зависимость продолжительности работ от вложенных средств:
tо12 - t н 12 = 5 - 0,5x12; tо13 - t н 13 = 6 - 0,2x13;
tо14 - t н 14 = 2 - 0,3x14; tо23 - t н 23 = 4 - 0,25x23;
tо34 - t н 34 = 9 - 0,4x34; tо35 - t н 35 = 7 - 0,2x35;
tо45 - t н 45 = 4 - 0,1x45;
г) время начала выполнения каждой работы должно быть не меньше времени окончания непосредственно предшествующей ей работы:
t н 12 = 0; t н 13 = 0; t н14 = 0;
t н 23 і tо12;
t н 34 і tо13; t н 34 і tо23;
t н 35 і tо13; t н 35 і tо23;
t н 45 і tо14; t н 45 і tо34;
t н 56 і tо35; t н 56 і tо45;
д) условие неотрицательности неизвестных:
t н ij і 0, tоij і 0, xij і 0, (i, j) О .
сетевой математический модель
5.Численное решение задачи:
Табличную запись математической модели см. табл. 2.4.
Решив данную задачу средствами EXCEL, получаем следующие результаты:
t н12 = 0; tо12 = 3; t н13 = 0; tо13 = 3; t н14 = 0; tо14 = 2;
t н 23 = 3; tо23 = 3; t н 34 = 3; tо34 = 8; t н 35 = 3; tо35 = 10;
t н45 = 8; tо45 = 10; t н 56 = 10; tо56 = 10;
x12 = 20; x13 = 0; x23 = 0; x14 = 0; x34 = 10; x35 = 0; x45 =20,
tкр = 10.
5. Анализ полученных результатов. При дополнительном вложении 47 ден. ед., проект может быть выполнен за 10 ед. времени. При этом средства распределятся следующим образом: 20 ден. ед. - в работу (1,2), 10 ден. ед. - в работу (3,4) и 20 ден. ед. - в работу (4,5), что приведет к сокращению продолжительности работы (1,2). Сокращение срока реализации проекта за счет вложения дополнительных средств составит 8 ед. времени.