АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Построение кратчайшего пути на сети

Читайте также:
  1. I. Функции эндоплазматической сети.
  2. II. Построение характеристического графика часовой производительности.
  3. MathCad: построение, редактирование и форматирование графиков в декартовой системе координат.
  4. V. Построение одного тренировочного занятия
  5. Алгоритм 2.1. Построение выходной таблицы, столбиковой диаграммы и кумуляты
  6. Билет 4. Формирование сбытовой сети.
  7. Вертикальный и горизонтальный анализ баланса. Построение аналитического баланса
  8. Возрастное построение городского населения (в процентах)
  9. Вопрос 2. Построение доверительного интервала при неизвестном законе генерального распределения.
  10. Вопрос 3. Типичные следственные ситуации и построение версий
  11. Вопрос №22: Трофические цепи и уровни биогеоценозов. Трофические сети.
  12. ГЛАВА 13 Построение тренировочных циклов

Дан неориентированный граф, для каждого ребра которого задана его длина. Вершины графа пронумерованы числами от 1 до N. Требуется найти путь минимальной длины, соединяющий 1-ю вершину с N-й.

Решим эту задачу методом динамического программирования.

I. Инвариантное погружение. Рассмотрим семейство задач P(k), k=1,...,N, где P(k) – задача о нахождении пути минимальной длины, соединяющий 1-ю вершину с k-й. Исходная задача запишется в виде P(N).

II. Функция Беллмана. Пусть B(k) – длина минимального пути в задаче P(k), x*(k) – последовательность дуг оптимального пути в этой задаче.

III. Уравнение Беллмана (связь между решениями задач семейства). Пусть G – множество вершин, для которых задача нахождения минимального пути уже решена. Рассмотрим множество вершин G1, смежных с множеством G, т.е. не входящих в G, но в которые можно попасть из множества G по некоторой дуге графа.

Обозначим l=(x,y) – дуга l начинается в вершине x и заканчивается в вершине y, d(l) – длина дуги l.

Пусть min{d(l)+B(k) | l=(m,k), m∈G1, k∈G} = d(l*)+B(k*), l*=(m*,k*). (3.3.1)

Тогда B(m*) = d(l*)+B(k*), (3.3.2)

причем x*(m*) = (x*(k*), l*). (3.3.3)

IV. Решение семейства задач. Уравнения (3.3.1) – (3.3.3) фактически не надо решать. Они указывают последовательность решения задач нашего семейства. Самые простая задача – найти кратчайший путь из 1-й вершины в эту же вершину, при этом B(1)=0, x*(1) не содержит дуг.

Таким образом, первоначально множество G = {1}, G1 содержит все смежные с 1-й вершины. Уравнения (3.3.1)–(3.3.3) позволяют расширить множество G, вычислив значение B для одной из смежных вершин (для той, на которой достигается минимум в (3.3.1)).

 

37. Задача оптимального планирования. Обработка деталей на двух станках.

Имеется n деталей, которые необходимо последовательно обработать сначала на одном, а потом на втором станке. Для каждой детали известно время ai обработки на первом станке и bi – на втором станке. Последовательность обработки деталей на обоих станках одинакова.

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

I. Семейство задач. Обозначим через P(i1,..,ik | Y) задачу, в которой детали с номерами i1,..,ik не обрабатываются, а второй станок включается через Y секунд после начала работы (первого станка). Наша исходная задача: P(пустое множество| 0) – все детали обрабатываются, 2-й станок включается сразу.

II. Функция Беллмана. Введем обозначения: B (i1,..,ik | Y) – оптимальное время обработки партии в задаче P(i1,..,ik | Y), x*(i1,..,ik | Y) – оптимальная последовательность обработки деталей.

III. Уравнение Беллмана. Рассмотрим задачу P(i1,..,ik | Y). Возьмём одну из деталей i1,..,ik поставим в очередь первой. Эта деталь (с номером i) будет полностью обработана через время Δt=ai+bi, если Y≤ai (т.е. второй станок успеет включиться), Δt=Y+bi, если Y>ai (т.е. придется ждать включения второго станка).

В итоге Δt =max{Y, ai}+bi = ai + bi + max{Y – ai, 0}.

Мы можем считать, что второй станок для оставшихся деталей включается через bi + max{Y – ai, 0} секунд после обработки i-й детали на первом станке.

Предполагая, что оставшиеся детали обрабатываются оптимальным образом, мы затрачиваем на такую обработку время, равное ai + B (i1,..,ik, i | bi + max{Y – ai, 0}).

Обозначим через Ik множество всех номеров деталей, не совпадающих с номерами i1,..,ik.

Тогда получим уравнение Беллмана

B(i1,..,ik | Y) = min {ai + B (i1,..,ik, i | bi + max{Y – ai, 0}) | i∈Ik}, (3.4.1)

причем

x*(i1,..,ik | Y) = (i*, x*(i1,..,ik, i*| bi* + max{Y – ai*, 0})), (3.4.2)

где i* – индекс, на котором достигается минимум в (3.4.1).

Уравнение (3.4.1) позволяет связать между собой значения целевых функций различных задач нашего семейства, (3.4.2) – последовательности обработки деталей в этих задачах. Уравнение Беллмана (3.4.1) показывает, что для решения задач с n необрабатываемыми деталями нужно знать решение задач с n+1 необрабатываемой деталью. Другими словами, задачи следует рассматривать в порядке возрастания количества обрабатываемых деталей.

IV. Решение семейства задач. Простейшими задачами семейства являются задачи семейства, в которых обрабатывается только одна деталь (с номером k): P(I\{k} | Y), где I – множество всех номеров деталей (напомним, что в обозначениях задачи до вертикальной черты указываются номера всех необрабатываемых деталей).

Как мы уже вычисляли,

B(I\{k} | Y) = max{Y, ai}+bi = ai + bi + max{Y – ai, 0}, (3.4.3)

при этом

x*(I\{k} | Y) = (k) (3.4.4)

– вектор с одной координатой.

Уравнение Беллмана (3.4.1)-(3.4.2) позволяет на основании (3.4.3)-(3.4.4) вычислять решения остальных задач семейства.


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)