Економічний зміст, деякі основні типи задач та моделі динамічного програмування. Алгоритм методу динамічного програмування - Економіко-математичне моделювання
Всі економічні процеси та явища є динамічними, оскільки вони функціонують і розвиваються не тільки у просторі, але й у часі. Для народного господарства в цілому, його галузей, регіонів чи окремих підприємств з метою їх стабільного функціонування та розвитку необхідно розробляти стратегічні та тактичні плани. Стратегічні плани містять параметри діяльності об'єктів, які характеризують їх віддалене майбутнє. Отже, вони мають розроблятися на основі динамічних моделей, для знаходження розв'язків яких застосовуються методи динамічного програмування.
Динамічне програмування являє собою математичний апарат, що дає змогу здійснювати планування багатокрокових керованих процесів, а також процесів, які розвиваються у часі.
Отже, динамічне програмування не є окремим методом розв'язування задач, а являє собою теорію, що поєднує ряд однотипних ідей та прийомів, які застосовуються для розв'язування досить різних за змістом задач.
До задач динамічного програмування належать такі, що пов'язані з оптимальним розподілом капіталовкладень, розподілом продукції між різними регіонами, визначенням найкоротшого шляху завезення товарів споживачам, задачі щодо заміни устаткування, оптимального управління запасами тощо. Економічні процеси можна уявити складеними з кількох етапів (кроків). На кожному з них здійснюється вплив на розвиток всього процесу. Тому у разі планування багатоетапних процесів прийняття рішень на кожному етапі має враховувати попередні зміни та бути підпорядкованим кінцевому результату. Динамічне програмування дає змогу прийняти ряд послідовних рішень, що забезпечує оптимальність розвитку процесу в цілому. Слід зазначити, що оптимальні плани стосовно окремих відрізків планового періоду не завжди є оптимальними для всього інтервалу планування. Наприклад, недостатньо визначити оптимальний план виробництва на один місяць і орієнтуватися на нього протягом тривалого часу. Досить ймовірно, що в наступні місяці виробництво за тим самим планом може стати неоптимальним, оскільки за його розроблення можливості дальшого розвитку не враховувались. Доцільніше визначати оптимальні плани на кожен місяць з урахуванням змін у попередніх періодах. Лише тоді річний оптимальний план виробництва буде сумарним результатом оптимальних рішень, що приймалися для кожного місяця.
На практиці часто доводиться зустрічатись з випадками, коли метою (ціллю) оптимізації є встановлення найкращої послідовності тих чи інших робіт (виробничих операцій, етапів будівництва різних споруд тощо). З подібною метою зустрічаються при розв'язанні задач так званого динамічного програмування.
Однією з перших задач такого роду, що привернули увагу математиків, була так звана задача про комівояжера (мандрівного торговця). Суть її така: є міст з заданими між ними відстанями. Потрібно, відправившись з, вибрати такий маршрут пересування, при якому комівояжер, побувавши в кожному місті по одному разу, повернувся б до вихідного пункту, пройшовши при цьому мінімально можливий сумарний шлях.
Основний спосіб динамічного програмування полягає в знаходженні правил домінування, які дозволяють робити порівняння варіантів розвитку послідовностей і завчасне відсіювання безперспективних варіантів. У ряді випадків в задачах динамічного програмування вдається одержати такі сильні правила домінування, що вони визначають елементи оптимальної послідовності однозначно один за одним. В такому випадку правила домінування називають розв'язувальними правилами.
Розв'язувальні правила звичайно виводяться за допомогою принципу оптимальності Беллмана. Суть принципу оптимальності така. Нехай критерій (задається формулою або алгоритмом), який дає числову оцінку якості варіанта (послідовності) , можна застосовувати не тільки до всієї послідовності, але і до будь-якого її початкового відрізку. Послідовність, якій відповідає екстремальне значення критерію, називається оптимальною. Якщо будь-який початковий відрізок оптимальної послідовності також оптимальний (в класі всіх послідовностей, складених з тих же елементів, і можливо, такий, що має ті ж початок і кінець, що і даний відрізок), то вважають, що для відповідної задачі справедливий принцип оптимальності.
Розглянемо зразок розв'язання задачі про комівояжера методом динамічного програмування:
1. Введення даних про пункти і відстані між пунктами i та j dij (dij =0 при i=j) .2. Обчислення всіх можливих варіантів відстаней, що складаються з трьох дільниць A0, Ai1, Ai2, Ai3. Вони групуються по останньому пункту і з них залишаються ті варіанти, що об'єднують однакові пункти, але мають найменший шлях.3. До тих варіантів, що залишились додають ще четверту дільницю і повторюють процедуру з пункту 2. Це повторюється для п'ятої, шостої і т. д. дільниць, доки не повертається в пункт А0. Той варіант (чи варіанти), що залишилися, і визначають найкоротший шлях, по якому комівояжеру можна об'їздити всі місті Аi (i=0,...,n), якщо він почне та закінчить свою подорож в А0.
Похожие статьи
-
Якщо в транспортній задачі не виконується така умова, тобто загальна кількість продукції постачальників не дорівнює загальному попиту всіх споживачів, то...
-
1. Задача оптимального планування виробництва. Визначити план виробництва х=(х1,...,хn)'(xj - шукана кількість одиниць продукції Pj), який би при заданих...
-
Для побудови алгоритмів розв'язання задач матричних ігор використовується властивість оптимальних змішаних стратегій: оптимальна змішана стратегія...
-
Умова цілочисловості є по суті нелінійною і може зустрічатися в задачах, що містять як лінійні, так і нелінійні функції. Задачі математичного...
-
До задач дробово лінійного програмування відносяться задачі нелінійного програмування математична модель яких в загальному можна представити в наступному...
-
1. записуємо цільову функцію та обмеження 2. приводимо систему обмежень до канонічної форми 3. знаходимо рівняння прямої. Будуємо ці прямі в системі...
-
Методом розв'язку ТЗ є метод потенціалів. для того, щоб можна було застосувати цей метод, необхідне виконання 2х умов: - ТЗ є закритою; - побудовано...
-
Цілочисельне програмування - різновид лінійного програмування, в якому отримані значення повинні бути цілими числами. Особливий інтерес до задач...
-
Оптимізаційна задача - це емм задача мета якої полягає у знаходженні найкращого виконання сформованих обмежуючих умов. K1, k2,k3 - знаки нерівності A,...
-
Транспортна задача -- це задача вибору оптимального варіанта доставки товару від пунктів виробництва до пунктів споживання з урахуванням усіх реальних...
-
Динамическое программирование Динамическое программирование -- один из разделов оптимального программирования, в котором процесс принятия решения и...
-
Доцільність використання імітаційної моделі - Основні аспекти імітаційного моделювання
Переваги застосування імітаційного моделювання найбільш помітно виявляються у разі моделювання виробничих і технологічних процесів, процесів...
-
Опорним називають базисний розв'язок, який не містить від'ємних чисел. Серед опорних розв'язків і міститься оптимальний розв'язок, що максимізує чи...
-
Основні етапи побудови імітаційної моделі - Основні аспекти імітаційного моделювання
Далі будемо розглядати послідовність виконання робіт під час реалізації методу машинної імітації та склад етапів побудови імітаційної моделі. Розглянемо...
-
Опорний розвязок(план) - невідємний базисний розв'язок. Базисні розвязки - це частинний розвязок, який знаходиться якщо надати всім вільним змінним...
-
В разделе 1 курсовой работы требуется: Определить количество закупаемого заданным филиалом фирмы сырья у каждого АО, (xj), максимизируя прибыль филиала....
-
Модуль імітаційного моделювання ARIS Simulation використовується в тих випадках, коли необхідно проаналізувати поведінку в часі розроблених моделей...
-
Условие задачи. Пусть имеются n кандидатов для выполнения этих работ. Назначение кандидата i на работу j связано с затратами CIj (i, j = 1,2,..., n)....
-
При решении экономических задач часто анализировать ситуации, в которых сталкиваются интересы двух или более конкурирующих сторон, преследующих различные...
-
Постановка задачі - Економетричні моделі
Задача. Для виготовлення чотирьох видів продукції використовують три види сировини. Запаси сировини, норми його витрати і прибуток від реалізації...
-
В основі моделі (2.2.) - (2.6) лежить рівняння, яке має вигляд: , Зробимо просте перетворення, зробивши заміну: (2.7) І отримаємо рівняння (2.8): (2.8)...
-
Исходная задача: При ограничениях: Двойственной является следующая задача: При ограничениях: Число неизвестных в двойственной задаче равно 2....
-
Транспортная задача - Экономико-математические методы
Методы линейного программирования, являются хорошим инструментом для решения ряда проблем распределения ресурсов. Применение пакетов прикладных программ...
-
Решение транспортной задачи методом потенциалов - Математическая модель решения транспортной задачи
Этот метод позволяет автоматически выделять циклы с отрицательной ценой и определять их цены. Пусть имеется транспортная задача с балансовыми условиями...
-
Використання системи наскрізного моделювання при вирішенні фінансово-економічних задач
Використання системи наскрізного моделювання при вирішенні фінансово-економічних задач Постановка проблеми. Вирішення складних фінансово-економічних...
-
Розглядаючи моделі для аналізу фінансового стану можна зробити висновок, що вони дуже подібні між собою, але їхнім недоліком є те, що вони розраховують...
-
На цьому етапі виконуються роботи, пов'язані з підготовкою та реалізацією імітаційної моделі на комп'ютері. Розробляється логічна схема моделі, яка...
-
Система ... називається системою обмежень, або системою умов задачі. Вона описує внутрішні технологічні та економічні процеси функціонування й розвитку...
-
Закритою називається транспортна задача в якій загальна кількість продукції постачальників дорівнює загальному попиту всіх споживачів, тобто . Теорема:...
-
Оцінка адекватності моделі - Основні аспекти імітаційного моделювання
Якою б складною і повною не була модель, вона тим не менш є наближеним відображенням реального об'єкта і відображає його за певних прийнятих припущеннях....
-
Умова задачі Бройлерне господарство птахівницької ферми налічує 20000 курчат, які вирощуються до 8-тижневого віку і після відповідної обробки надходять у...
-
Метод Гомори последовательных отсечений - Математическое моделирование экономических процессов
При решении многих задач (планирование мелкосерийного производства, распределение кораблей по путям сообщения, выработка суждений типа "да-нет" и т. п.)...
-
Модели теории игр. Основные определения и термины В разных областях целенаправленной деятельности, например при разработке и эксплуатации АСУ, часто...
-
Графіки, що ілюструють зміну статистичних явищ у часі, називаються Динамічними . Для зображення динаміки явищ використовують лінійні, стовпчикові,...
-
Теоретическое обоснование математического моделирования - Математические методы и модели в экономике
Коммерческая деятельность в том или ином виде сводится к решению таких задач: как распорядиться имеющимися ресурсами для достижения наибольшей выгоды или...
-
Моделювання є процесом побудови, вивчення та застосування моделей. Воно є невід'ємною частиною будь-якої цілеспрямованої діяльності. Процес моделювання...
-
Оптимизация инвестиционного портфеля (ИП) [Дубровин и др., 2008], [Мищенко и др., 2002], [Серов, 2000] является одной из важных экономических задач,...
-
Використання концепції ефективного автомобіля для моделювання динаміки транспортних потоків у транспортній мережі міста Постановка проблеми. Однією з...
-
ВСТУП - Основні аспекти імітаційного моделювання
Імітаційне моделювання застосовується у всіх сферах діяльності людини починаючи від моделей технічних, технологічних та організаційних систем і...
-
Метод дифференциальных рент для решения транспортной задачи - Формирование оптимального штата фирмы
Для решения транспортных задач используется несколько методов. Рассмотрим решение с помощью метода дифференциальных рент. При нахождении решения...
Економічний зміст, деякі основні типи задач та моделі динамічного програмування. Алгоритм методу динамічного програмування - Економіко-математичне моделювання