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

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

Решение задачи.

Для решения данной задачи воспользуемся результатами решения предыдущего примера. Нас интересует не столько сам результат, сколько организованная форма управления базой данных. Поэтому основа в виде расчетных форм остается без изменений. Дополним ее необходимыми полями (таблица 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

Теперь можно включить средство Поиск решения. В качестве целевой ячейки выбирается суммарный ресурс (ячейка 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

Рис.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%.

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