Технические темы
1 1 1 1 1 1 1 1 1 1 Рейтинг 0.00 (0 Голоса)

Оптимизация сетевой модели задача с решением

Оптимизация сетевых графиков производится с различными целями и по различным критериям: времени, стоимости прямых затрат или ресурсов на основе дополнительных вложений или за счет внутренних резервов. В условиях рыночных отношений приоритет имеет оптимизация на основе перераспределения внутренних резервов. При этом считается, что задано такое множество Х распределений ресурсов, что выбор хотя бы одного из них хÎХ сразу же определяет времена выполнения работ 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расч

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расч

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%.

Добавить комментарий


Защитный код
Обновить

Google