Задача сетевого планирования с вложением средств

Задача сетевого планирования с вложением средств

Задача сетевого планирования с вложением средств

Задача сетевого планирования с вложением средств

Тогда задача принимает следующий вид.
Получаем задачу линейного программирования. Рассмотрим пример решения такой задачи симплекс-методом.
Задача сетевого планирования с вложением средств

Пример (вариант 50)
Пусть имеется комплекс работ А1, А2, …, А7. Работы А3 и А4 опираются на А1 и А2, А5 и А6 опираются на А3 и А4, А7 опирается на А5 и А6.
Критическими работами являются работами А1, А3, А5, А7. Проверим первое достаточное условие.
Работа А1 остается критической при максимальном вложении средств.
Работа А3 перестает быть критической при максимальном вложении средств. Первое условие не выполнено.

Пример (вариант 50)
Второе условие выполнено. Следовательно, критический путь не меняется.
Преобразуем ограничение на критическое время.

Пример (вариант 50)
Запишем данные в симплекс-таблицу.
Получаем следующую задачу линейного программирования.

Пример (вариант 50)

Пример (вариант 50)

Пример (вариант 50)
Оптимальный план найден.

Имеется комплекс работ А1, …, Аn. Будем считать, что время выполнения работ зависит от вложенных в них дополнительных средств. Полагаем, что эти зависимости являются линейными. В этом случае задача может быть сведена к нескольким задачам линейного программирования.
Если с работой Аi снимается xi единиц средств, то время ее выполнения определяется формулой:
при .
− время выполнения работы Аi без изменения средств,
− некоторый коэффициент,
− максимальное количество средств, которое может быть снято.
Задача сетевого планирования с вложением средств

Пример
Пусть имеется комплекс из четырех работ А1, А2, А3, А4. Работа А3 опирается на А1 и А2, работа А4 также опирается на А1 и А2. Зависимости времени выполнения работ от количества вложенных средств имеет вид:

Пример
Преобразуем ограничения на связи между работами.

Пример
Ограничения на связи между работами имеют вид
Ограничения на завершения последних работ имеют вид
После преобразования ограничений записываем симплекс-таблицу.

Пример

Пример

Пример

Пример

Пример

Пример

Пример
Оптимальный план найден.

Пример
Ответ:
Проверка.

Пусть имеется комплекс работ А1, А2, …, А7. Работы А3 и А4 опираются на А1 и А2, А5 и А6 опираются на А3 и А4, А7 опирается на А5 и А6.
В этой задаче...
выполнены первое и второе условия;
первое условие выполнено, а второе − нет;
второе условие выполнено, а первое − нет;
не выполнены оба условия.
Задание для самоконтроля