Оптимизация сетевой модели задача с решением
Оптимизация сетевых графиков производится с различными целями и по различным критериям: времени, стоимости прямых затрат или ресурсов на основе дополнительных вложений или за счет внутренних резервов. В условиях рыночных отношений приоритет имеет оптимизация на основе перераспределения внутренних резервов. При этом считается, что задано такое множество Х распределений ресурсов, что выбор хотя бы одного из них хÎХ сразу же определяет времена выполнения работ tij. Отсюда следуют следующие возможные варианты постановки задачи математического программирования:
- минимизировать время выполнения работ;
- минимизировать ресурс для заданного директивного времени.
Для решения таких задач удобно использовать надстройку «Поиск решения» табличного процессора Excel, оснащенную аппаратом нелинейного программирования:
Рассмотрим такую задачу, в которой распределение ресурсов осуществляется в рамках директивного времени. В качестве критерия оптимизации выберем минимизацию суммарного ресурса. Отметим, что такая задача не всегда имеет решение. Время ограничено как снизу (величина положительная), так и сверху (не может превысить отводимого порога по располагаемому ресурсу),
В основе модели лежит взаимосвязь ресурса со временем. В простейшем случае можно считать, что объем выполненной работы есть произведение затраченного ресурса на время. На самом деле связь между ресурсом и временем может быть гораздо сложнее, и Ехсеl позволяет для каждой работы записать свою формулу. Мы же рассмотрим простейший случай, позволяющий понять механизм оптимизации на сетях.
Математическая модель простой задачи имеет вид:
, (3.7)
где Rij - ресурс, выделяемый для выполнения работы (потребный - Rijпотр и фактический - Rij); Qij - объем работы (потребный - Qijпотр и фактический - Qij).
Исходя из такой постановки (при равенстве длины критического пути директивному времени) потребный и фактический объемы выполняемых работ должны совпадать. До начала оптимизации каждая из работ выполнялась за tijнорм, а значит и ресурс, выделяемый на нее, соответствовал отношению: Rijпотр=Qijпотр/tijнорм. С изменением времени изменяется и ресурс: Rijпотр=Qijпотр/tij. Работы, расположенные на критическом пути должны стать короче, остальные будут не меньше своих прежних значений. Однако важным условием остается невозможность превысить установленный нормами суммарный ресурс. Следовательно, решение задачи лежит в поиске таких tij и Rij, которые удовлетворяют системе ограничений (3.7). Рассмотрим это на примере.
Пример задачи
Возьмем исходные данные предыдущего примера и дополним их сведениями об объемах выполняемых работ, взятых в условных единицах (таблица 3.5). Пусть все ресурсы выражаются в их денежном эквиваленте. Тогда задачу можно сформулировать так: определить минимальную сумму затрат на выполнение операций разборки двигателя и оптимальным образом распределить ее по работам.
Таблица 3.5
|
№ работы |
Время (мин) |
Qпотр. |
|
1-2 |
12 |
100 |
|
1-3 |
7 |
120 |
|
2-3 |
8 |
120 |
|
2-4 |
12 |
150 |
|
2-5 |
14 |
80 |
|
3-4 |
18 |
180 |
|
4-5 |
8 |
200 |
|
4-6 |
10 |
140 |
|
5-6 |
10 |
120 |
|
Директивное время :Тпотр=60 мин |
Решение задачи.
Для решения данной задачи воспользуемся результатами решения предыдущего примера. Нас интересует не столько сам результат, сколько организованная форма управления базой данных. Поэтому основа в виде расчетных форм остается без изменений. Дополним ее необходимыми полями (таблица 3.6):
- расчетного (нового) времени выполнения работы (tрасч);
- расчетного (нового) размера капиталовложений (Rрасч);
- потребного (нормативного) объема капиталовложений (Rн);
- фактического и потребного объемов выполняемых работ.
Записываем в таблицу следующие значения:
- расчетные время и ресурс задаются равными единице, т. к. решается система нелинейных уравнений;
- потребные объемы работ выбираются из таблицы 15;
- в колонку нормативного ресурса заносится формула Rijпотр=Qijпотр/tijнорм. Например, для снятия муфты сцепления: I12/D12;
- в колонку фактического объема выполняемых работ (Q) записывается произведение расчетного времени на расчетный ресурс. Например: El0*Fl0.
- формулу, записанную для определения времени раннего окончания работ (Тр. о) необходимо изменить, заменив нормативное время выполнения работы на расчетное. Например, в ячейке К9 будет: = E9+J9;
- в колонке времени позднего начала выполняется аналогичная замена, т. е. из времени позднего начала должно вычитаться расчетное (новое) время;
- одновременно необходимо проверить расчетные формулы для раннего начала и позднего окончания работ. Во-первых они должны опираться на исток (ноль) и на сток (tкp) соответственно. Во-вторых, база данных должна охватывать требуемый диапазон ячеек: для ДМАКС - это А5:К14, для ДМИН – А5:М14. Необходимо также обратить внимание на параметры Поле и Критерий для показанных функций.
Таблица 3.6
|
A |
B |
C |
D |
E |
F |
G |
H |
I |
J |
|||||
|
1 |
Критерии выбора |
|||||||||||||
|
2 |
Кон. |
Кон. |
Кон. |
Кон. |
Нач. |
Нач. |
Нач. |
Нач. |
||||||
|
3 |
2 |
3 |
4 |
5 |
2 |
3 |
4 |
5 |
||||||
|
4 |
Параметры сетевого графика |
|||||||||||||
|
5 |
Наим. работы |
Нач. |
Кон. |
Врем |
tрасч |
Rрасч |
Rн |
Q |
Qпотр |
Тр. н. |
Тр. о. |
Тп. н. |
Тп. о. |
Рез. |
|
6 |
Компенсаторы |
1 |
2 |
12 |
1 |
1 |
8.333 |
1 |
100 |
0 |
1 |
0 |
1 |
0 |
|
7 |
Кронштейны |
1 |
3 |
7 |
1 |
1 |
17.143 |
1 |
120 |
0 |
1 |
1 |
2 |
1 |
|
8 |
Турбокомпре-ссор |
2 |
3 |
8 |
1 |
1 |
15 |
1 |
120 |
1 |
2 |
1 |
2 |
0 |
|
9 |
Топливопр. НД и фильтры |
2 |
4 |
12 |
1 |
1 |
12.5 |
1 |
150 |
1 |
2 |
2 |
3 |
1 |
|
10 |
Трубки в. насоса и комп. |
2 |
5 |
14 |
1 |
1 |
5.714 |
1 |
80 |
1 |
2 |
3 |
4 |
2 |
|
11 |
Топливопр. ВД и трубки слива |
3 |
4 |
18 |
1 |
1 |
10 |
1 |
180 |
2 |
3 |
2 |
3 |
0 |
|
12 |
Муфта сцепления |
4 |
5 |
18 |
1 |
1 |
11.111 |
1 |
200 |
3 |
4 |
3 |
4 |
0 |
|
13 |
Топл. насос |
4 |
6 |
10 |
1 |
1 |
14 |
1 |
140 |
3 |
4 |
4 |
5 |
1 |
|
14 |
Вод. насос и компрессор |
5 |
6 |
10 |
1 |
1 |
12 |
1 |
120 |
4 |
5 |
4 |
5 |
0 |
|
15 |
Суммарный ресурс |
9 |
105,8 |
Т критического пути |
5 |
Теперь можно включить средство Поиск решения. В качестве целевой ячейки выбирается суммарный ресурс (ячейка F15), которая стремится к минимуму. Изменяемыми ячейками являются расчетные время и ресурс - E6:F14 (рис.3.4). Добавляем ограничения:
- расчетное время относится к целым (Е6:Е14 - целое) положительным числам (Е6:Е14>=0);
- суммарный расчетный ресурс не больше располагаемого (Fl5<=G15);
- фактический (расчетный) и потребный объемы работ равны между собой (Н6:Н14=I6:I14);
- нормативное время выполнения всех работ равно заданному (К15=60).
 |
В окне Параметры можно показать: Неотрицательные значения и Автоматическое масштабирование. Выбор масштаба относится к тем задачам, в которых изменяемые ячейки и значения ЦФ отличаются на несколько порядков.
Рис.3.4
Запускаем программу на выполнение и получаем результат (табл. 3.7, рис.3.5).
Таблица 3.7
|
A |
B |
C |
D |
E |
F |
G |
H |
I |
J |
|||||
|
1 |
Критерии выбора |
|||||||||||||
|
2 |
Кон. |
Кон. |
Кон. |
Кон. |
Нач. |
Нач. |
Нач. |
Нач. |
||||||
|
3 |
2 |
3 |
4 |
5 |
2 |
3 |
4 |
5 |
||||||
|
4 |
Параметры сетевого графика |
|||||||||||||
|
5 |
Наим. работы |
Нач. |
Кон. |
Врем |
tрасч |
Rрасч |
Rн |
Q |
Qпотр |
Тр. н. |
Тр. о. |
Тп. н. |
Тп. о. |
Рез. |
|
6 |
Компенсаторы |
1 |
2 |
12 |
9 |
11.111 |
8.333 |
100 |
100 |
0 |
9 |
0 |
9 |
0 |
|
7 |
Кронштейны |
1 |
3 |
7 |
20 |
6.000 |
17.143 |
120 |
120 |
0 |
20 |
0 |
20 |
0 |
|
8 |
Турбокомпре-ссор |
2 |
3 |
8 |
11 |
10.909 |
15.000 |
120 |
120 |
9 |
20 |
9 |
20 |
0 |
|
9 |
Топливопр. НД и фильтры |
2 |
4 |
12 |
27 |
5.556 |
12.500 |
150 |
150 |
9 |
36 |
9 |
36 |
0 |
|
10 |
Трубки вод. насоса и компр. |
2 |
5 |
14 |
41 |
1.951 |
5.714 |
80 |
80 |
9 |
50 |
9 |
50 |
0 |
|
11 |
Топливопр. ВД и трубки слива |
3 |
4 |
18 |
16 |
11.250 |
10.000 |
180 |
180 |
20 |
36 |
20 |
36 |
0 |
|
12 |
Муфта сцепления |
4 |
5 |
18 |
14 |
14.286 |
11.111 |
200 |
200 |
36 |
50 |
36 |
50 |
0 |
|
13 |
Топл. насос |
4 |
6 |
10 |
23 |
6.087 |
14.000 |
140 |
140 |
36 |
59 |
37 |
60 |
1 |
|
14 |
Вод. насос и компрессор |
5 |
6 |
10 |
10 |
12.000 |
12.000 |
120 |
120 |
50 |
60 |
50 |
60 |
0 |
|
15 |
Суммарный ресурс |
79.150 |
105.82 |
Т крит. пути |
60 |
 |
Рис.3.5
Результаты решения.
Всего критических путей - 4 (первый - 1-2-3-4-5-6, второй - 1-3-4-5-6, третий - 1-2-4-5-6, четвертый - 1-2-5-6). За счет перераспределения финансов уменьшилось время выполнения работ 1-2, 3-4 и 4-5; по остальным работам время увеличилось. Финансовые вложения уменьшились со 105,8 до 75,15, то есть на 25,2%.
