Минимизация затрат на выполнение комплекса работ при заданном времени

Условные задачи следующие: директивно задано предельное время выполнения комплекса работ. Необходимо определить продолжительность работ, при которых затраты на выполнение комплекса будут минимально возможными, а время выполнения комплекса не превысит директивного времени.

Формализованная структура задачи следующая:

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

(8)

Преобразуем целевую функцию

(9)

В связи с тем, что первая часть целевой функции фиксирована,

(10)

Целевую функцию можно свести к следующему виду:

(11)

Система ограничений состоит из следующих подсистем:

а) t_k d_k (12)

б) t_k D_k (13)

Число выражений в каждой из этих подсистем совпадает с числом действительных работ N_раб.

в) (14)

где – булева переменная;

1, если k-я работа входит в 1-й полный путь

0, если k-я работа не входит в 1-й полный путь

Каждое выражение данной подсистемы ограничений определяет максимальную продолжительность каждого полного пути сетевого графика. Число выражений совпадает с числом полных путей.

В связи с тем, что одним из общих ограничений задач линейного программирования является X 0, в рассмотренной задаче необходимо ввести новые переменные, отвечающие этому требованию, т. е.

(15)

С учетом введения новых переменных система ограничений примет вид:

а) (16)

б) (17)

в) 1=1, (18)

В связи с введением новых переменных целевая функция примет вид:

(19)

Преобразуем полученную целевую функцию:

(20)

Но вторая часть функции константа, т. е.

(21)

Тогда целевая функция примет вид:

(22)

Для дальнейших расчетов в качестве целевой функции будет использоваться выражение:

(23)

где

Если рассмотреть структуру полученной задачи линейного программирования, то выяснится, что это вторая частная параметрическая задача. В системе ограничения в составе свободного члена используется параметр T, предел изменения которого определен выражением (4).

Преобразуем задачу таким образом, чтобы параметр T был в целевой функции, т. е. перейдем к первой частной параметрической задаче. Для этого используем принцип двойственности. Целевая функция примет вид:

(24)

Система ограничений:

(25)

где – булева переменная:

1, если входит в к-е ограничение (26)

0, если не входит в к-е ограничение

Справедливо соотношение (для оптимальных планов прямой и двойственной задачи):

Двойственно-сопряженная задача на максимум. Перейдем от задачи на минимум к задаче на максимум. Для этого умножим целевую функцию (24) на –1.

Получим:

(27)

для которой

Решение двойственной задачи позволяет установить:

a) деление исходного интервала изменения T (4) на частные интервалы, в пределах которых оптимальное значение будет постоянным;

b) значение для каждого частного интервала;

c) линейный вид целевой функции от T для каждого частного интервала, устанавливающий зависимость минимальных затрат на выполнение комплексных работ от T

(28)

где A_i, B_i – коэффициент линейной функции для i-го частного интервала.

Используя выражение (28), можно определить значение минимальных затрат, соответствующих T_д.

Для этого достаточно:

а) определить частный интервал изменения T, в который попадает T_д,

где , – границы i-го частного интервала.

Это, в свою очередь, позволяет определить значения A_i и B_i.

б) подставить значения T_д в выражение (28), т. е.

Дата добавления: 2015-10-28