Модели и методы принятия решений

Аналогично предыдущему из табл. 2 выбираем четыре перспективных варианта.

Так как нам необходимо возвратиться в исходный пункт, то выделенные перспективные последовательности движения дополняем этим исходным пунктом A0. Вычисляем для них суммарные расстояния и заносим результаты в табл. 3.

Таблица 3 – Суммарные расстояния перспективных вариантов движения

Из таблицы видно, что имеется два оптимальных маршрута следования коммивояжера А0 А4 А3 А2 А1 А0 и А0 А1 А2 А3 А4 А0, имеющие минимальную из всех возможных маршрутов длину, равную 720 км.

2. ДИНАМИЧЕСКАЯ ОПТИМИЗАЦИЯ В ПЛАНИРОВАНИИ РАБОТ

Задача 1.10

В условиях задачи производственного планирования (см. МУ [12]) найти оптимальные строки начала строительства каждого из объектов так, чтобы суммарный срок строительства всех объектов был бы минимальным.

Таблица 1.10.10 – Исходные данные

Решение

Считая, что работа на каждом объекте должна продолжаться непрерывно с момента начала строительства до его окончания, требуется определить сроки начала строительства каждого объекта так, чтобы суммарный срок строительства всех объектов был минимальным.

Последовательность строительства может быть любой:

Покажем, как оценивается суммарное время строительства для одного из вариантов, например А1 А2 А3. Сроки окончания работ на первом объекте будут следующими (см. табл. 1.10.10):

-окончание первой стадии 1 месяц;

-окончание второй стадии 1 + 2 = 3 месяца;

-окончание третьей стадии 3 + 5 = 8 месяцев;

окончание четвертой стадии 8 + 2 = 10 месяцев.

Время t2 начала работ на втором объекте должно удовлетворять следующим неравенствам:

Эти неравенства выражают требования, чтобы каждая из стадий работ на объекте А2 начиналась лишь после окончания работ соответствующих стадий на объекте А1. Одновременно (параллельно) вести один и тот же вид работ у организации нет возможности но условию задачи.

Первое неравенство выражает требование, чтобы первая стадия работ на втором объекте начиналась лишь после окончания первой стадии работ на первом объекте, т.е. через один месяц.

Второе неравенство выражает требование, чтобы вторая стадия работ на втором объекте начиналась лишь после окончания второй стадии работ на первом объекте, т.е. через четыре месяца. При этом надо помнить, что первая стадия работ на втором объекте уже выполнена (t2 +3).

Третье неравенство выражает требование, чтобы третья стадия работ на втором объекте начиналась лишь после окончания третьей стадии работ на первом объекте, т.е. через восемь месяцев (первая и вторая стадии работ на втором объекте уже выполнены, следовательно, t2 +5).

Четвертое неравенство выражает требование, чтобы четвертая стадия работ на втором объекте начиналась лишь после окончания четвертой стадии работ на первом объекте, т.е. через десять месяцев (первая, вторая и третья стадии работ на втором объекте выполнены, следовательно, t2 + 8).

Наименьшее значение t2, удовлетворяющее этим неравенствам, равно 3. Поэтому самый ранний возможный срок начала строительства второго объекта А2 три месяца после начала строительства первого объекта А1. Зная это значение, несложно определить сроки окончания соответствующих стадий работ:

окончание первой стадии 3 + 3 = 6 месяцев;

окончание второй стадии 6 + 2 = 8 месяцев;

окончание третьей стадии 8 + 3 = 11 месяцев;

окончание четвертой стадии 11 + 4 = 15 месяцев.

Зная сроки окончания стадии работ на втором объекте, аналогично определяем срок t3 начала строительства третьего объекта (A3). Для него неравенства будут следующие:

что приводит к минимальному сроку t3 = 6 мес. Следовательно, сроки окончания отдельных стадий строительства третьего объекта будут соответственно:

окончание первой стадии 6 + 2 = 8 месяцев;

окончание второй стадии 8 + 5 = 13 месяцев;

окончание третьей стадии 13 + 2 = 15 месяцев;

окончание четвертой стадии 15 + 4 = 19 месяцев.

Таким образом, для выбранной последовательности строительства объектов А[ А2 А3 общее время строительства (совпадающее со сроком завершения работ на объекте А3) равно 19 мес.

Аналогично определяем сроки и для других оставшихся последовательностей строительства. Результаты заносим в Таблицу.

А1 А3 А2

Стадии А1:

1 – 1 мес.;

2 – 3 мес.;

3 – 8 мес.;

4 – 10 мес

Неравенства t3:

Следовательно, t3 = 1 мес.

Стадии А3:

1 – 3 мес.;

2 – 8 мес.;

3 – 10 мес.;

4 – 14 мес

Неравенства t2:

Следовательно, t3 = 6 мес.

Стадии А2:

1 – 9 мес.;

2 – 11 мес.;

3 – 14 мес.;

4 – 18 мес.

Следовательно общее время строительства А1 А3 А2 = 18 мес.

А2 А1 А3

Стадии А2:

1 – 3 мес.;

2 – 5 мес.;

3 – 8 мес.;

4 – 12 мес

Неравенства t1:

Следовательно, t1 = 5 мес.

Стадии А1:

1 – 6 мес.;

2 – 8 мес.;

3 – 13 мес.;

4 – 15 мес

Неравенства t3:

Следовательно, t3 = 6 мес.

Стадии А3:

1 – 8 мес.;

2 – 13 мес.;

3 – 15 мес.;

4 – 19 мес

Следовательно общее время строительства А2 А1 А3 = 19 мес.

А2 А3 А1

Стадии А2:

1 – 3 мес.;

2 – 5 мес.;

3 – 8 мес.;

 Скачать реферат