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

Одномерная задача динамического программирования

Читайте также:
  1. VI. Общая задача чистого разума
  2. Базовые средства программирования
  3. Базовые управляющие структуры структурного программирования
  4. Блок программирования, регуляции и контроля деятельности
  5. Вопрос 2 Проверка и оценка в задачах со случайными процессами на примере решения задач экозащиты, безопасности и риска.
  6. Вопрос 5. Какие ресурсные ограничения моделей общей задачи линейного программирования должны анализироваться в первую очередь?
  7. Встроенные языки программирования (часть 1).
  8. Высокоуровневые языки программирования
  9. Геометрическая интерпретация задачи линейного программирования.
  10. Глава 10 Системный подход к задачам управления. Управленческие решения
  11. ГЛАВА 2.1. ЗАЩИТА ИННОВАЦИЙ КАК ЗАДАЧА УПРАВЛЕНИЯ ИННОВАЦИОННЫМИ ПРОЦЕССАМИ
  12. Глава 3. Основы алгоритмизации и программирования

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

Необходимо оптимальным образом распределить ресурс в объеме xo по n вариантам (объектам, схемам, этапам) при целевой функции

и ограничениях

,

где xi – объем ресурса, назначаемый по i-му варианту (0 £xi £ xо);

f(x)– нелинейная функция, определяющая эффект (затраты) в зависимости от значений x;

n – общее число вариантов; xобщ – общий объем распределяемого ресурса.

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

Обозначим через xci – количество ресурса, назначаемого суммарно по i-му варианту и всем предыдущим вариантам. При этом объем ресурса по предыдущим вариантам распределен оптимально исходя из минимума затрат или максимума эффекта.

Тогда целевая функция Zi при рассмотрении i-го этапа решения определяется по выражению

Zi(xci, xi)= fi(xi) + f* i-1 (xci - xi),

где 0 £xсi £ xобщ при i £ n-1 и xсi= xобщ при i = n;

f*i-1 – функция, определяющая эффект (затраты) оптимальным образом по предыдущим вариантам в зависимости от объема ресурса xci-1;

Значение f*i определяется по Zi:

для i =1 (xc1=x1);

, .

Определение и соответствующих им при данном xсiпроизводятся поэтапно от i=2 до i=n.

По окончательному результату поэтапных расчетов формируется оптимальное решение {xоi}:

xоi= (для i = n);

xоi = при (для );

(для i=1).

Вариант алгоритма решения однопродуктовой задачи динамического программирования приведен на рисунке 3.24. Решение предусмотрено для целевой функции, подлежащей оптимизации на максимум. Для решения задачи на минимум необходимо ввести исходные значения sвji с отрицательным знаком или внести изменения в блоках 12 (заменить 1E+12 на -1E+12) и 15 (условие < на >).

Выводимые j, kjidx , snm представляют соответственно номер варианта, объем ресурса по варианту и значение целевой функции для оптимального решения.

 

Пример. Банковский кредит может быть использован по 4-м вариантам (n=4). Общий объем кредита xобщ = 800 тыс.ед. Дискретность распределения кредита по вариантам использования dx = 200 тыс.ед. Зависимость эффекта по вариантам использования кредита нелинейна и задана таблично (таблица 3.11).

 

Таблица 3.11 – Значения эффектов в зависимости от номера варианта i и объема ресурса x

Номер варианта i Эффект fi (x) при объемах использования кредита x
x=0 x=200 x=400 x=600 x=800
           
           
           
           

Необходимо распределить кредит, чтобы суммарный эффект от его использования был максимальным.
1

Пуск

 

Ввод n, xoбщ, dx n – число вариантов распределения ресурса

xoбщ – общий объем ресурса

dx – дискретность распределения ресурса

 

m = xoбщ/ dx m – число разбиений ресурса

 

 

sвji, ; sвji – эффект (затраты) по j-му варианту

при объеме использования ресурса xi

 

 

5 6

s1i = sв1i

k1i = i

 

 

8 Да 9 10

Нет

r = m j = n r = 1

 

r = m

 

 

12 18

p = 1E+12

 

 

16 19

sji =c l: kji = l; p = c l Вывод j, kjrdx

 

Да

 

Нет 15 14 20

c l < p c l =sвj l + sj-1, i- l r = r - kjr

 

 

 

Вывод snm

Рисунок 3.24 – Алгоритм решения однопродуктовой задачи

динамического программирования 22

Останов


РЕШЕНИЕ.

Имеем целевую функцию = max;

ограничения xобщ = x1 + x2+ x3 + x4 = 800; 0 £xi £ xобщ,

а также – для одного первого варианта.

На втором этапе (i=2) рассматриваем одновременно распределение ресурса для первого и второго варианта. Результаты расчетов сводим в таблицу 3.12. Значком (*) отмечен столбец, соответствующий оптимальному значению при данном xci.

Таблица 3.12 – Расчет при i=2

xci        
xi                            
xci - xi                            
                           
                           
+ 12*     23*       34*     44*   44*  
       

На третьем этапе (таблица 3.13) решения рассматриваются одновременно оптимальный вариант по 1-му и 2-му вариантам совместно с третьим вариантом (i=3).

 

Таблица 3.13 – Расчет при i=3

xci        
xi                            
xci - xi                            
                           
                           
+ 12*   23*     34*       44*        
       

Переходим к последнему этапу (i=4). При этом xсi = xо (таблица 3.14).

Исходя из результатов выполнения последнего этапа расчетов следует, что кредит можно использовать с максимальным эффектом, равных 45 тыс.ед., при этом, хо4 = 200 тыс.ед.

Тогда на 3-й и все предыдущие варианты остается 600 тыс.ед. Оптимальный объем использования кредита по 3-му варианту, как следует из этапа 3 решения, при xс i = 600 равен xо3 = 0;

на 2-й и все предыдущие остается по прежнему 800-200-0=600. Оптимальный объем использования кредита по 2-му варианту, как следует из этапа 2 решения, при xс i = 600 равен xо2 = 400.

 

Таблица 3.14 – Расчет при i=4

xci  
xi          
xci - xi          
         
         
+   45*      
 


Оптимальный объем кредита к использованию по первому варианту определяется как остаток xо1 =800-200-0-400 = 200.

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

1-й – 200 тыс.ед; 2-й – 400 тыс.ед., 3-й – 0 тыс.ед; 4-й – 200 тыс.ед.


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 |

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



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