14 - Лекция

Автомат:

На группу 35% (по всей группе)
Наличие лекций

Оптимизация моделей по стоимости

Сетевая модель строится для нахождения минимального времени выполнения проекта.
! 1000

Подсчитаем все возможные полные пути (от начального события, до конечного)
$L_{1} = 7 + 10 + 9 = 26$
$L_{2} = 7 + 6 + 12 + 9 = 34$
$L_{3} = 7 + 6 + 14 = 27$
$L_{4} = 16 + 12 + 9 = 37$
$L_{5} = 16 + 14 = 30$
$L_{6} = 11 + 8 + 12 + 9 = 40$
$L_{7} = 11 + 8 + 14 = 33$
$L_{8} = 11 + 13 = 24$

$L_{К р} = L_{6} = 40$
$t_{К р} = 40$
$t_{0} = 34$ - необходимое время

t_{i j} = t_{i j} - k_{i j} \cdot x_{i j}

Требуется найти такие $t_{i j}^{н}$ , $t_{i j}^{о}$ , $x_{i j}$ чтобы

срок выполнения всего комплекса работ не превышал заданной величины $t_{0}$
суммарное количество дополнительно вложенных средств было минимальным
продолжительность выполнения каждой работы $t_{i j}$ была не меньше заданной величины $d_{i j}$

$t_{i j}^{н}$ - время начала работы $(i, j)$
$t_{i j}^{о}$ - время окончания работы $(i, j)$
$x_{i j}$ - вложения в работу $(i, j)$

Составление математической модели задачи

Целевая функция имеет вид

f = x_{12} + x_{13} + x_{14} + x_{24} + x_{25} + x_{34} + x_{36} + x_{45} + x_{46} + x_{56} \to min

(Количество $x$ -ов это количество работ)
(Столько же неравенств/ограничений у нас получится)

Запишем ограничения задачи:

а) срок выполнения проекта не должен превышать $t_{0} = 34$

$t_{36}^{о} = 34$
$t_{46}^{о} = 34$
$t_{56}^{о} = 34$

б) продолжительность выполнения каждой работы должна быть не меньше минимально возможного времени:

$t_{12}^{о} - t_{12}^{н} \geq 4$
$t_{13}^{о} - t_{13}^{н} \geq 8$
$t_{14}^{о} - t_{14}^{н} \geq 13$
$t_{24}^{о} - t_{24}^{н} \geq 5$
$t_{25}^{о} - t_{25}^{н} \geq 7$
$t_{34}^{о} - t_{34}^{н} \geq 6$
$t_{36}^{о} - t_{36}^{н} \geq 10$
$t_{45}^{о} - t_{45}^{н} \geq 10$
$t_{46}^{о} - t_{46}^{н} \geq 11$
$t_{56}^{о} - t_{56}^{н} \geq 7$

Всего выходит 13 ограничений

Зависимость продолжительности работ от вложенных средств:

$t_{12}^{о} - t_{12}^{н} = 7 - 0.1 x_{12}$
$t_{14}^{о} - t_{14}^{н} = 16 - 0.2 x_{14}$
$t_{25}^{о} - t_{25}^{н} = 10 - 0.25 x_{25}$
$t_{36}^{о} - t_{36}^{н} = 13 - 0.12 x_{36}$
$t_{46}^{о} - t_{46}^{н} = 14 - 0.08 x_{46}$
$t_{13}^{о} - t_{13}^{н} = 11 - 0.3 x_{13}$
$t_{24}^{о} - t_{24}^{н} = 6 - 0.05 x_{24}$
$t_{34}^{о} - t_{34}^{н} = 8 - 0.2 x_{34}$
$t_{45}^{о} - t_{45}^{н} = 12 - 0.5 x_{45}$
$t_{56}^{о} - t_{56}^{н} = 9 - 0.02 x_{56}$

Время начала выполнения каждой работы должно быть не меньше времени окончания непосредственно предшествующей ей работы:

$t_{12}^{н} = 0$
$t_{14}^{н} = 0$
$t_{13}^{н} = 0$
$t_{25}^{н} \geq t_{12}^{о}$
$t_{36}^{н} \geq t_{13}^{о}$
$t_{45}^{н} \geq t_{24}^{о}$
$t_{46}^{н} \geq t_{14}^{о}$
$t_{46}^{н} \geq t_{34}^{о}$
$t_{56}^{н} \geq t_{45}^{о}$
$t_{24}^{н} \geq t_{12}^{о}$
$t_{34}^{н} \geq t_{14}^{о}$
$t_{45}^{н} \geq t_{14}^{о}$
$t_{45}^{н} \geq t_{34}^{о}$
$t_{46}^{н} \geq t_{24}^{о}$
$t_{56}^{н} \geq t_{25}^{о}$

Условие неотрицательности неизвестных:

$t_{i j}^{н} \geq 0$
$t_{i j}^{о} \geq 0$
$x_{i j} \geq 0$
$(i, j) \in \vec{e}$

В завершении мы должны выделить на сколько сократилось время выполнения всего проекта.