Примеры решения задач по теме «Динамическое программирование. Расчёт показателей динамических СМО»

Задача № 1

Рассмотрим на примере задачи коммивояжера, как работает динамическое программирование. Суть ее состоит в следующем: имеется n+1 населенных пунктов А₁ А₂ …, А_n с заданным между ними расстояниями d_ij (i,j=1,2…,n). Требуется, отправляясь из начального пункта А₁ выбрать такой маршрут передвижения, при котором коммивояжер, побыв в каждом из населенных пунктов по одному разу, вернулся бы в исходный пункт А₁ проделав минимально возможный суммарный путь.

Эта задача может быть решена методом простого перебора всех возможных маршрутов. Общее число таких маршрутов равно:

123…(n-1) n.

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

Динамическое программирование позволяет решить данную проблему и сократить число вычислений. Допустим, что имеется 5 пунктов: А₁ А₂ А₃ А₄ А₅ . Известны расстояния между ними. Эти расстояния представлены следующей матрицей:

	А1	А2	А3	А4	А5
А1	0	300	250	200	400
А2	300	0	500	350	600
А3	250	500	0	250	200
А4	200	350	250	0	250
А5	400	600	200	250	0

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

Начнем с вариантов, состоящих из трех участков. Например, отправляясь из исходного пункта А₁ можно добраться в третий пункт А₄ шестью способами:

A1-A2-A3-A4

A1-A3-A2-A4

A1-A2-A5-A4

A1-A5-A2-A4

A1-A3-A5-A4

Зная расстояние между пунктами, можно вычислить суммарный путь для каждого из шести вариантов. Аналогично рассматриваем все остальные варианты движения: от исходного до первого, от исходного до второго, от исходного до четвертого, …….. Результаты помещаются в таблицу 1.

Таблица 1

Вариант движения	Расстояние, км.	Перспективно или нет
A1-A3-A4-A2	850	Да
A1-A4-A3-A2	950	Да
A1-A3-A5-A2	1050	Да
A1-A5-A3-A2	1100	Нет
A1-A4-A5-A2	1050	Да
A1-A5-A4-A2	1000	Да
A1-A2-A4-A3	900	Да
A1-A4-A2-A3	1050	Да
A1-A2-A5-A3	1100	Нет
A1-A2-A3-A4	1050	Да
A1-A3-A2-A4	1100	Нет
A1-A2-A5-A4	1150	Нет
A1-A5-A2-A4	1350	Нет
A1-A3-A5-A4	700	Да
A1-A5-A3-A4	850	Да

Продолжение таблицы 1

---

Вариант движения	Расстояние, км.	Перспективно или нет
A1-A2-A3-A5	1000	Да
A1-A3-A2-A5	1350	Нет
A1-A2-A4-A5	900	Да
A1-A3-A4-A2	1150	Нет
A1-A3-A4-A5	750	Да
A1-A4-A3-A5	650	Да

После заполнения таблицы выделяем только перспективные варианты, дополняем их номером не посещенного населенного пункта и повторяем процедуру: определяем перспективность движения уже для четырех участков пути. Для этого к вычисленной длине перспективного пути прибавляем расстояние до не посещенного еще населенного пункта (см. таблица 2).

Таблица 2

Вариант движения	Расстояние, км.	Перспективно или нет
A1-A4-A5-A3-A2	1150	Да
A1-A4-A3-A5-A2	1250	Да
A1-A3-A5-A4-A2	1050	Да
A1-A3-A4-A5-A2	1350	Нет
A1-A3-A4-A2-A5	1450	Нет
A1-A5-A3-A4-A2	1200	Да
A1-A2-A4-A3-A5	1100	Да
A1-A5-A4-A3-A2	1400	Нет
A1-A2-A4-A5-A3	1100	Да
A1-A4-A3-A2-A5	1550	Нет
A1-A5-A4-A2-A3	1500	Нет
A1-A2-A3-A5-A4	1250	Нет

Так как нам необходимо возвратиться в исходный пункт, то выделенные перспективные последовательности движения дополняем исходным пунктом А₁ (см. таблицу 3).

Таблица 3

Вариант движения	Расстояние, км.
A1-A3-A5-A4-A2-A1	1350
A1-A2-A4-A3-A5-A1	1500
A1-A2-A4-A5-A3-A1	1350
A1-A4-A5-A3-A2-A1	1450
A1-A5-A3-A4-A2-A1	1500
A1-A4-A3-A5-A2-A1	1550

Из таблицы видно, что имеется два оптимальных маршрута следования коммивояжера A1-A2-A4-A5-A3-A1 и A1-A3-A5-A4-A2-A1, имеющие минимальную из всех возможных маршрутов длину, равную 1350.

Задача № 2.

Планируется строительство нескольких объектов А₁, А₂,….,А_n. Ресурсы строительной организации ограничены. Предположим, что строительство каждого объекта состоит из m последовательных стадий (земляные работы, закладка фундамента, кладка стен и др.). Мощность строительных организаций не позволяет вести один и тот же вид работ одновременно на нескольких объектах. Продолжительность каждого вида работ задана, например, в месяцах:

Объекты	Виды (стадии) работ
	1	2	3	4
А1	1	3	4	2
А2	3	2	3	1
А3	2	2	1	4

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

---

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

А₁ А₂ А₃

А₁ А₃ А₂

А₂ А₁ А₃

А₂ А₃ А₁

А₃ А₁ А₂

А₃ А₂ А₁

Необходимо найти оптимальную последовательность, при которой бы суммарный срок строительства был минимальным.

Покажем, как оценивается суммарное время строительства для одного из вариантов, например для А₁ А₂ А₃. сроки окончания работ на первом объекте, исходя из предыдущей таблицы, будут следующими:

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

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

• окончание третей стадии 4+4=8 месяца;

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

Время t₂ работы на втором объекте должно удовлетворять следующим неравенствам: t₂  1;

t₂ +3 4;

t₂ +5 8;

t₂ +8 10;

Эти неравенства выражают требования, чтобы каждая из стадий работ на объекте А₂ начиналась лишь после окончания работ соответствующих стадий на объекте А₁.

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

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

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

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

Наименьшее значение t₂, удовлетворяющее этим неравенствам = 3. поэтому, самый ранний возможный срок начала строительства второго объекта А₂ – 3 месяца после начала строительства первого объекта А₁. зная это значение, несложно определить сроки окончания соответствующих стадий работ:

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

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

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

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

Зная сроки окончания стадии работ на втором объекте, аналогично определяем срок t₃ начала строительства третьего объекта (А₃). Для него неравенства будут следующими: t₃  6;

t₃ +2 8

t₃ +4 11;

t₃+5 12;

что приводит к минимальному сроку t₃=7 месяцев. Следовательно, сроки окончания отдельных стадий строительства объектов А₁ А₂ А₃ общее время строительства = 16 мес.

Аналогично можно определить сроки и для других оставшихся последовательностей строительства: А₁ А₂ А₃; А₂ А₁ А₃; А₂ А₃ А₁; А₃ А₁ А₂; А₃ А₂ А_1.

---

Поскольку в рассмотренном примере имеется всего 3!=6 вариантов строительства, то выбор наилучшего варианта может быть осуществлен простым перебором вариантов. При большом количестве n количество комбинаций может быть очень большим. В такой ситуации выбор оптимальной последовательности может быть осуществлен точно таким же способом, как и в задаче о коммивояжере: сначала берется усеченная последовательность строительства объектов, из нее выбираются перспективные варианты (с минимумом времени), далее она постепенно дополняется с повторением процедур расчета и оценки.

---

Смотрите также файлы

• 8.1. Постановка задачи динамического программирования. Принцип Беллмана..docx

• 7.3. Пример решения задачи нелинейного программирования.docx

• 7.1. Математическая постановка и методы решения задачи нелинейного программирования.docx

• 6.2. Пример решения задачи целочисленного программирования методом ветвей и границ.docx

• 6.1. Постановка и методы решения задач целочисленного программирования.docx