Динамическое программирование - Решение задач методами динамического программирования, нахождение кратчайшего пути
Под динамическим программированием понимают некоторый специальный метод оптимизации, суть которого состоит в отыскании оптимального решения путем выполнения вычислений в несколько шагов(этапов). Вся задача оптимизации разделяется на несколько шагов, причем все шаги могут быть уникальными или одинаковыми и чередоваться друг с другом. Некоторые задачи оптимизации легко разделяются на шаги естественным способом, а для других - вводится искусственное разделение на шаги.
Примерами задач, решаемых динамическим программированием, могут быть: распределение ресурсов (финансовых, сырьевых, материальных и т. д.) между предприятиями, замена (или ремонт) промышленного оборудования, прокладка коммуникаций (трубопроводов, дорог и т. д.) и пр. В этих задачах, как правило, в качестве шагов (этапов) выступают отрезки времени (годы, кварталы и т. д.), которые ясно задаются в условии задачи.
Оптимальное решение задачи в целом складывается из оптимальных решений на каждом шаге
Где - оптимальное решение на I-М шаге.
В этом случае говорят, что целевая функция L обладает "аддитивным критерием качества".
Нахождение кратчайшего пути.
Задача динамического программирования по своей сути является управляемым процессом, причем управление выполняется на каждом шаге. Особо надо подчеркнуть, что выбор оптимального решения на конкретном шаге не дает гарантии получения оптимального решения для всей задачи. То есть для получения оптимального решения для всей задачи иногда приходится выбирать не лучшее решение на конкретном шаге. Таким образом, планирование многошаговой задачи сводится к выбору такого решения на каждом шаге, которое последствия на следующих (будущих шагах). На текущем шаге выбирается не лучшее решение, а то, которое предполагает максимальную сумму выигрыша от всех оставшихся шагов.
Учитывая вышесказанное, выполнить вычисления в задачах динамического программирования удобнее от конца к началу. Действительно легко можно планировать последний, M-1. Выполняя вычисления по последнему шагу, надо сделать ряд предположений: как закончился предыдущий, M-1, шаг и для каждого предположения найти условно-оптимальное решение на M-М шаге. Аналогично выполняются M-1, M-2 и т. д. шаги, вплоть до первого шага. Таким образом, будут найдены условно-оптимальные решения на каждом шаге. Далее выполняется переход от условно-оптимального решения к безусловно-оптимальному решению на каждом шаге, т. е. выполняются решения о первого шага к последнему, ориентируясь на полученные условно-оптимальные решения. Теперь на первом шаге известна "стоимость" решения задачи от второго шага до последнего шага и, следовательно, можно указать оптимальное решение на первом шаге (снизить "стоимость" первого шага). Далее выполняются аналогично второй, третий и т. д. шаги.
При использовании динамического программирования многошаговая задача решается дважды: от конца к началу (определение условно-оптимального решения) и от начала к концу (определение безусловно-оптимального решения). Первый этап длительный и трудоемкий, второй - короткий и уточняет решение первого этапа (по готовым рекомендациям определяется безусловно-оптимальное решение на каждом шаге).
3. Специальная часть
Похожие статьи
-
Постановка задачи Постановка практической задачи ЛП включает следующие основные этапы: - определение показателя эффективности, переменных задачи, -...
-
Решение задачи, Анализ оптимального решения - Использование методов линейного программирования
1. Для задания необходимых параметров оптимизации нажатием кнопки Параметры откроем окно "Параметры поиска решения" (рис.4). В этом окне оставьте...
-
Признак оптимальности плана перевозок T. З. устанавливает теорема. Теорема. Для того, чтобы некоторый допустимый план X = (xij)m-nT. З. был оптимальным,...
-
Методика решения задач ЛП графическим методом - Линейное программирование
I. В ограничениях задачи (1.2) заменить знаки неравенств знаками точных равенств и построить соответствующие прямые. II. Найти и заштриховать...
-
Построение модели В данной задаче искомыми неизвестными являются количество полок каждого вида, которые будут произведены в текущем месяце. Таким...
-
Транспортная задача оптимальность Поставим в соответствие поставщикам потенциалы Ui, , а потребителям - Vj, . В оптимальном плане для всех базисных...
-
Математическое обеспечение позволяет использовать методы автоматизированного поиска оптимальных вариантов при проектировании системы. Часто при решении...
-
Математический аппарат Для понимания всего дальнейшего полезно знать и представлять себе геометрическую интерпретацию задач линейного программирования,...
-
2.2 Нахождение кратчайших путей в графе - Определение кратчайшего пути в графе
Начальные понятия Будем рассматривать ориентированные графы G = < V , E> , дугам которых приписаны веса. Это означает, что каждой дуге < U ,...
-
Первый этап решения задачи - Использование методов линейного программирования
В зависимости от размеров листов ДСП и габаритов полок детали В1 и В2 можно выкроить различными способами. Рассмотрим 3 возможных варианта такого раскроя...
-
Решение задачи линейного программирования Постановка задачи Сформулируем задачу: определить значения переменных, обеспечивающие минимизацию целевой...
-
Построение модели предметной области с помощью описания структур данных и программного кода является классическим подходом в разработке ИС. Зачастую...
-
Аннотация В статье рассматриваются два способа уменьшения времени вычисления дерева решений для задач линейного параметрического программирования с...
-
Это задача оптимизации, в которой переменные принимают только два значения: "единица - ноль". Пример - задача "коммивояжера". Цель работы: минимизировать...
-
Транспортная задача - Использование методов линейного программирования
Одна из наиболее распространенных задач математического программирования -- транспортная задача. В общем виде ее можно представить так: требуется найти...
-
Постановка задачи Целью работы является изучение основных этапов автоматизированного структурного проектирования технологических маршрутов: -...
-
"РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ИСПОЛЬЗОВАНИЕМ MICROSOFT EXCEL" Цель работы Приобретение навыков решения задач линейного программирования...
-
Языки и системы программирования, их эволюция - Автоматизация решения задач пользователя
Язык программирования - это способ записи программ решения различных задач на ЭВМ в понятной для компьютера форме. Процессор компьютера непосредственно...
-
Транспортная задача - Линейное программирование
Одна из наиболее распространенных задач математического программирования -- транспортная задача. В общем виде ее можно представить так: требуется найти...
-
Теория Графов, 1.1 Историческая справка - Определение кратчайшего пути в графе
Граф дискретный программирование 1.1 Историческая справка ТЕОРИЯ ГРАФОВ - это область дискретной математики, особенностью которой является геометрический...
-
Средствами решения задачи является алгоритмический язык С++. Операторы и функции, используемые для решения поставленной задачи: #Include - подключение...
-
Геометрический метод, Двойственная задача - Линейное программирование
Применяется для задач с двумя переменными. Метод решения состоит в следующем: На плоскости строятся прямые, которые задают соответствующие ограничения:...
-
Предложенный подход к решению задач исследования Используя в качестве основы присутствующее в наличии программное обеспечение, которое применимо к...
-
Специфика транспортной задачи позволяет находить новое опорное решение задачи и новый базис по правилу более простому, чем в симплекс-методе. Пусть...
-
Описание решения задачи - Работа в среде программирования Lazarus
Для реализации проекта создано 4 формы: 1. Форма "Титульный лист" (рисунок 3), на которой находятся: Ш Кнопка Начало (Button) для перехода на следующую...
-
Выведем в общем виде уравнение движения заданной динамической модели при помощи уравнений Лагранжа II рода. Полная кинетическая энергия: , Полная...
-
Собственными называют периодические колебания консервативной системы, совершающиеся исключительно под воздействием инерционных и упругих сил. Для...
-
Варианты - Решение задач линейного программирования с использованием Microsoft Excel
Используя MS Excel, найти решение для модели ЛП, соответствующей заданному варианту (табл. 1.5). Таблица 1.5 Варианты задач к лабораторной работе № 1 №...
-
Средствами решения задачи является алгоритмический язык С++. Операторы и функции, используемые для решения поставленной задачи: #Include - подключение...
-
Технические требования Техническое задание данной работы требует разработать программу для визуального редактирования HTML-кода. Программа должна быть...
-
Теоретическая основа линейного программирования, Симплекс метод - Линейное программирование
Симплекс метод Симплекс метод - метод линейного программирования, который реализует рациональный перебор базисных допустимых решений, в виде конечного...
-
Цель Работы - научиться использовать операции динамического выделения и освобождения памяти на примере работы с одномерными и двумерными массивами, а...
-
Языки и методы параллельного программирования - Администрирование параллельных процессов
Применение параллельных архитектур повышает производительность при решении задач, явно сводимых к обработке векторов. Автоматическое распараллеливание...
-
Producteev Первым из рассмотренных продуктов является Producteev. Это приложение обладает богатым набором функций. Каждый проект является единым рабочим...
-
Метод ветвей и границ, Ветку считают тупиковой, если: - Целочисленное программирование
Впервые метод ветвей и границ был предложен Ландом и Дойгом в 1960 году для решения общей задачи целочисленного линейного программирования (Land A. H.,...
-
Для решения сформулированной задачи, т. е, для нахождения оптимального варианта конструкции наиболее эффективным является метод динамического...
-
Язык программирования R - Технологии больших данных: анализ и выбор решения для реализации проекта
Язык программирования R является универсальным и разработан для применения в следующих областях: разведочный анализ данных, классические статистические...
-
Решение задач линейного программирования - Основы информатики
Имеются n пунктов производства и m пунктов распределения продукции. Стоимость перевозки единицы продукции с i-го пункта производства в j-ый центр...
-
Понятие и виды моделирования Исследовательские задачи, решаемые с помощью моделирования различных физических систем, можно разделить на четыре группы: 1)...
-
Теорема. Чтобы транспортная задача была разрешима, необходимо и достаточно, чтобы выполнялось условие: (1.5) Доказательство: Необходимость. Пусть...
Динамическое программирование - Решение задач методами динамического программирования, нахождение кратчайшего пути