Динамическая оптимизация в планировании работ
Для получения решения онлайн, укажите количество объектов An и число стадий работ.
Пример решения
В условиях задачи производственного планирования найти оптимальные сроки начала строительства каждого из объектов так, чтобы суммарный срок строительства всех объектов был бы минимальным.| Объекты / Стадии | №1 | №2 | №3 | №4 |
| A1 | 2 | 5 | 4 | 3 |
| A2 | 1 | 4 | 2 | 6 |
| A3 | 3 | 4 | 3 | 4 |
Последовательность строительства может быть любой:
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 мес.
Таблица – Результаты расчетов
| Варианты работ | Время, мес. | Перспективно или нет |
| A1A2A3 | 24 | нет |
| A1A3A2 | 24 | нет |
| A2A1A3 | 21 | да |
| A2A3A1 | 22 | нет |
| A3A1A2 | 25 | нет |
| A3A2A1 | 24 | нет |
Список литературы
- Макаров И.М. и др. Теория выбора и принятия решений. - М.: Наука, 1982.-328 с.
- Зелинский А.Н. Основы математического моделирования: Учеб. пособие.-К.: УМК ВО, 1991.-236 с.
- Скобелев В.Г. Принятие решений: комбинаторный подход: Учеб. пособие. - Донецк: ДГУ, 1997. - 54 с.