Динамическая оптимизация в планировании работ

Для получения решения онлайн, укажите количество объектов An и число стадий работ.
Количество объектов Количество стадий

Пример решения

В условиях задачи производственного планирования найти оптимальные сроки начала строительства каждого из объектов так, чтобы суммарный срок строительства всех объектов был бы минимальным.
Объекты / Стадии№1№2№3№4
A12543
A21426
A33434

Последовательность строительства может быть любой:
A1A2A3
A1A3A2
A2A1A3
A2A3A1
A3A1A2
A3A2A1
Покажем, как оценивается суммарное время строительства для одного из вариантов, например A1A2A3. Сроки окончания работ на первом объекте будут следующими:
A1A2A3
для объекта A1
- окончание стадии №1: 2 мес.
- окончание стадии №2: 2+5=7 мес.
- окончание стадии №3: 7+4=11 мес.
- окончание стадии №4: 11+3=14 мес.
Время t2 начала работ на втором объекте должно удовлетворять следующим неравенствам:
t2 ≥ 2
t2+1 ≥ 7
t2+5 ≥ 11
t2+7 ≥ 14
Эти неравенства выражают требования, чтобы каждая из стадий работ на объекте А2 начиналась лишь после окончания работ соответствующих стадий на объекте А1. Одновременно (параллельно) вести один и тот же вид работ у организации нет возможности по условию задачи.
Наименьшее значение t2, удовлетворяющее этим неравенствам, равно 7 мес.Зная это значение, несложно определить сроки окончания соответствующих стадий работ:
для объекта A2
- окончание стадии №1: 7+1=8 мес.
- окончание стадии №2: 8+4=12 мес.
- окончание стадии №3: 12+2=14 мес.
- окончание стадии №4: 14+6=20 мес.
Время t3 начала работ на втором объекте должно удовлетворять следующим неравенствам:
t3 ≥ 8
t3+3 ≥ 12
t3+7 ≥ 14
t3+10 ≥ 20
Эти неравенства выражают требования, чтобы каждая из стадий работ на объекте А3 начиналась лишь после окончания работ соответствующих стадий на объекте А2.
Наименьшее значение t3, удовлетворяющее этим неравенствам, равно 10 мес.
для объекта A3
- окончание стадии №1: 10+3=13 мес.
- окончание стадии №2: 13+4=17 мес.
- окончание стадии №3: 17+3=20 мес.
- окончание стадии №4: 20+4=24 мес.
Таким образом, для выбранной последовательности строительства объектов A1A2A3 общее время строительства (совпадающее со сроком завершения работ на объекте А3) равно 24 мес.
Аналогично определяем сроки и для других оставшихся последовательностей строительства. Результаты заносим в Таблицу.
A1A3A2
для объекта A1
- окончание стадии №1: 2 мес.
- окончание стадии №2: 2+5=7 мес.
- окончание стадии №3: 7+4=11 мес.
- окончание стадии №4: 11+3=14 мес.
t3 ≥ 2
t3+3 ≥ 7
t3+7 ≥ 11
t3+10 ≥ 14
Следовательно, t3=4 мес.
для объекта A3
- окончание стадии №1: 4+3=7 мес.
- окончание стадии №2: 7+4=11 мес.
- окончание стадии №3: 11+3=14 мес.
- окончание стадии №4: 14+4=18 мес.
t2 ≥ 7
t2+1 ≥ 11
t2+5 ≥ 14
t2+7 ≥ 18
Следовательно, t2=11 мес.
для объекта A2
- окончание стадии №1: 11+1=12 мес.
- окончание стадии №2: 12+4=16 мес.
- окончание стадии №3: 16+2=18 мес.
- окончание стадии №4: 18+6=24 мес.
Следовательно общее время строительства A1A3A2 = 24 мес.
A2A1A3
для объекта A2
- окончание стадии №1: 1 мес.
- окончание стадии №2: 1+4=5 мес.
- окончание стадии №3: 5+2=7 мес.
- окончание стадии №4: 7+6=13 мес.
t1 ≥ 1
t1+2 ≥ 5
t1+7 ≥ 7
t1+11 ≥ 13
Следовательно, t1=3 мес.
для объекта A1
- окончание стадии №1: 3+2=5 мес.
- окончание стадии №2: 5+5=10 мес.
- окончание стадии №3: 10+4=14 мес.
- окончание стадии №4: 14+3=17 мес.
t3 ≥ 5
t3+3 ≥ 10
t3+7 ≥ 14
t3+10 ≥ 17
Следовательно, t3=7 мес.
для объекта A3
- окончание стадии №1: 7+3=10 мес.
- окончание стадии №2: 10+4=14 мес.
- окончание стадии №3: 14+3=17 мес.
- окончание стадии №4: 17+4=21 мес.
Следовательно общее время строительства A2A1A3 = 21 мес.
A2A3A1
для объекта A2
- окончание стадии №1: 1 мес.
- окончание стадии №2: 1+4=5 мес.
- окончание стадии №3: 5+2=7 мес.
- окончание стадии №4: 7+6=13 мес.
t3 ≥ 1
t3+3 ≥ 5
t3+7 ≥ 7
t3+10 ≥ 13
Следовательно, t3=3 мес.
для объекта A3
- окончание стадии №1: 3+3=6 мес.
- окончание стадии №2: 6+4=10 мес.
- окончание стадии №3: 10+3=13 мес.
- окончание стадии №4: 13+4=17 мес.
t1 ≥ 6
t1+2 ≥ 10
t1+7 ≥ 13
t1+11 ≥ 17
Следовательно, t1=8 мес.
для объекта A1
- окончание стадии №1: 8+2=10 мес.
- окончание стадии №2: 10+5=15 мес.
- окончание стадии №3: 15+4=19 мес.
- окончание стадии №4: 19+3=22 мес.
Следовательно общее время строительства A2A3A1 = 22 мес.
A3A1A2
для объекта A3
- окончание стадии №1: 3 мес.
- окончание стадии №2: 3+4=7 мес.
- окончание стадии №3: 7+3=10 мес.
- окончание стадии №4: 10+4=14 мес.
t1 ≥ 3
t1+2 ≥ 7
t1+7 ≥ 10
t1+11 ≥ 14
Следовательно, t1=5 мес.
для объекта A1
- окончание стадии №1: 5+2=7 мес.
- окончание стадии №2: 7+5=12 мес.
- окончание стадии №3: 12+4=16 мес.
- окончание стадии №4: 16+3=19 мес.
t2 ≥ 7
t2+1 ≥ 12
t2+5 ≥ 16
t2+7 ≥ 19
Следовательно, t2=12 мес.
для объекта A2
- окончание стадии №1: 12+1=13 мес.
- окончание стадии №2: 13+4=17 мес.
- окончание стадии №3: 17+2=19 мес.
- окончание стадии №4: 19+6=25 мес.
Следовательно общее время строительства A3A1A2 = 25 мес.
A3A2A1
для объекта A3
- окончание стадии №1: 3 мес.
- окончание стадии №2: 3+4=7 мес.
- окончание стадии №3: 7+3=10 мес.
- окончание стадии №4: 10+4=14 мес.
t2 ≥ 3
t2+1 ≥ 7
t2+5 ≥ 10
t2+7 ≥ 14
Следовательно, t2=7 мес.
для объекта A2
- окончание стадии №1: 7+1=8 мес.
- окончание стадии №2: 8+4=12 мес.
- окончание стадии №3: 12+2=14 мес.
- окончание стадии №4: 14+6=20 мес.
t1 ≥ 8
t1+2 ≥ 12
t1+7 ≥ 14
t1+11 ≥ 20
Следовательно, t1=10 мес.
для объекта A1
- окончание стадии №1: 10+2=12 мес.
- окончание стадии №2: 12+5=17 мес.
- окончание стадии №3: 17+4=21 мес.
- окончание стадии №4: 21+3=24 мес.
Следовательно общее время строительства A3A2A1 = 24 мес.
Таблица – Результаты расчетов
Варианты работВремя, мес.Перспективно или нет
A1A2A324нет
A1A3A224нет
A2A1A321да
A2A3A122нет
A3A1A225нет
A3A2A124нет
Таким образом, наилучший выбор строительства A2A1A3, который займет общее время в 21 месяцев.

Список литературы

  1. Макаров И.М. и др. Теория выбора и принятия решений. - М.: Наука, 1982.-328 с.
  2. Зелинский А.Н. Основы математического моделирования: Учеб. пособие.-К.: УМК ВО, 1991.-236 с.
  3. Скобелев В.Г. Принятие решений: комбинаторный подход: Учеб. пособие. - Донецк: ДГУ, 1997. - 54 с.
 Задать вопрос или оставить комментарий Помощь в решении Поиск