Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Методика выполнения работы. Примеры решения задач на основе метода динамического программирования

Обзор задач теории графов | Задача о закреплении самолетов за воздушными линиями | Пример 4.5 | Задача о ранце | Пример 4.6 | Задача коммивояжера | Пример 4.7 | Задача о доставке (покрытии множества) | Пример 4.8 | Задание на лабораторную работу |


Читайте также:
  1. I. ЗАДАНИЯ ДЛЯ АУДИТОРНОЙ РАБОТЫ
  2. I. Итоговая государственная аттестация включает защиту бакалаврской выпускной квалификационной работы
  3. I. Цель работы
  4. I. Цель работы
  5. I. Цель работы
  6. I. Цель работы.
  7. I.3.1. Определение номенклатуры и продолжительности выполнения видов (комплексов) работ

Примеры решения задач на основе метода динамического программирования

При рассмотрении примеров будем использовать следующие обозначения:

Sk –состояние в конце k-го шага (или, другими словами, состояние в начале k+1-го шага);

Uk – любое возможное (допустимое) решение на k-м шаге;

Uk*оптимальное решение на k-м шаге;

Zk – критерий эффективности на k-м шаге;

Еk – суммарный критерий эффективности на всех шагах, начиная с k-го (т.е. на шагах от k-го до N-го);

Еk* – оптимальный (в рассматриваемых примерах – максимальный) суммарный критерий эффективности на всех шагах, начиная с k-го.

Пример 7.1. Денежные средства в размере 60 млн ден.ед. распределяются между четырьмя предприятиями (П1, П2, П3, П4), принадлежащими одной крупной фирме. денежные средства выделяются в размерах, кратных 20 млн ден.ед. Каждым предприятием разработаны планы использования денежных средств на развитие производства. Определена прибыль, которую получит каждое предприятие в результате использования выделенных средств (табл. 7.1).

Таблица 5.1

Выделенные средства, млн. ден.ед. Прибыль предприятий, млн. ден.ед.
П1 П2 П3 П4
         
         
         
         

 

Например, если предприятию П1 не будут выделены средства, то оно не получит никакой прибыли. Если этому предприятию будет выделено 20 млн. ден.ед., то его прибыль от использования этих средств составит 9 млн. ден.ед. Если будет выделено 40 млн. ден.ед., то прибыль составит 16 млн. ден.ед., а при выделении 60 млн – 22 млн. ден.ед.

Требуется распределить имеющиеся средства (60 млн. ден.ед.) между предприятиями таким образом, чтобы общая прибыль была максимальной.

В данной задаче в качестве шагов будем рассматривать выделение средств предприятиям: первый шаг – выделение средств предприятию П1, второй – П2, и т.д. (всего 4 шага). Таким образом, распределение средств между предприятиями можно рассматривать как многошаговую операцию. В качестве состояния этой операции будем использовать величину имеющихся средств, которые требуется распределить. Начальное состояние S0 = 60. Решение на каждом шаге – это денежные средства, выделяемые предприятию (Uk, k= 1,…, 4). Критерий эффективности для каждого шага – прибыль, полученная предприятием (Zk,k= 1,…, 4). Общий критерий эффективности – это прибыль фирмы, т.е. сумма прибылей всех предприятий: Е = Z1 + Z2 + Z3 + Z4.

Задача удовлетворяет свойству отсутствия последействия. Состояние по окончании каждого шага (т.е. имеющаяся сумма средств, подлежащая распределению, Sk) зависит только от суммы, имевшейся в начале шага (Sk-1) и от решения, принятого на данном шаге (т.е. от выделенной на данном шаге денежной суммы Uk): Sk = Sk-1– Uk. Критерий эффективности на каждом шаге (т.е. прибыль предприятия Zk) зависит только от решения на данном шаге, т.е. от выделенной предприятию суммы Uk, и не зависит от того, сколько средств выделено другим предприятиям.

Задача удовлетворяет также свойству аддитивности критерия эффективности: общий критерий эффективности (прибыль фирмы) равен сумме критериев эффективности на отдельных шагах (прибылей предприятий).

Задача решается в два цикла.

 


Дата добавления: 2015-07-21; просмотров: 86 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Постановка задачи. Принцип работы метода динамического программирования| Цикл условной оптимизации

mybiblioteka.su - 2015-2024 год. (0.005 сек.)