Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







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





 

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

Принцип оптимальности.

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

Пусть процесс оптимизации разбит на n шагов. На каждом шаге необходимо определить два типа переменных – переменную состояния s и переменную управления или решения х. Переменная s определяет, в каких состояниях может оказаться система на данном k -ом шаге. В зависимости от s на этом шаге можно применить некоторые решения, которые характеризуются переменной хk. Применение решения х на k -ом шаге приносит некоторый результат uk(s, xk) и переводит систему в некоторое состояние s'(s, xk). Для каждого возможного состояния на k -ом шаге среди всех возможных решений выбирается оптимальное решение хk*, такое, чтобы результат, который достигается за шаги с k -ого по n- ый оказался оптимальным. Числовая характеристика этого результата называется функцией Беллмана fk(s) и зависит от номера шага k и состояния системы s.

Итак решение задачи распадается на два этапа. На первом этапе, он называется условной оптимизацией, отыскивается функция Беллмана и оптимальные решения для всех возможных состояний на каждом шаге, начиная с последнего. На последнем, n -ом шаге найти оптимальное решение хn* и значение функции Беллмана fn(s) совсем не сложно (fn(s)=optimum , где optimum (это максимум или минимум) ищется по всем возможным значениям хn). Дальнейшие же вычисления производятся согласно уравнению Беллмана – рекуррентному уравнению, связывающему функцию Беллмана на каждом шаге с функцией Беллмана, вычисленной на предыдущем шаге. В общем виде это уравнение имеет вид

Fk(s)=optimum

Этот максимум или минимум отыскивается по всем возможным для данных k и s значениям переменной решения хk.

После того, как функция Беллмана и соответствующие оптимальные решения найдены для всех шагов с n-ого по первый, производится второй этап решения задачи, который называется безусловной оптимизацией. Пользуясь тем, что на первом шаге (k =1) состояние системы нам известно – это ее начальное состояние s0 – можно найти оптимальный результат за все n шагов (это f1(s0)) и, кроме того, оптимальное решение на первом шаге х1*, которое этот результат доставляет. После применения этого решения система перейдет в некоторое новое состояние s'(s, x1*), зная которое можно, пользуясь результатами, полученными на этапе условной оптимизации, найти оптимальное решений на втором шаге х2*, и так далее вплоть до n -ого шага.

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

Пример 8. Пусть имеются четыре предприятия, между которыми распределяется 100 тыс. ден. ед. (инвестирование предприятий). Денежные средства распределяются суммами кратными 20 тыс. ден. ед. Значения прибыли предприятия в зависимости от выделенной суммы х приведены в таблице 12. Составить план распределения средств, максимизирующий общий прирост выпуска продукции.

Таблица 12

  Средства х, тыс. ден. ед. Предприятие
№1 №2 №3 №4
Прирост выпуска продукции на предприятиях, , тыс. ден. ед.
         

Решение:

I этап. Условная оптимизация.

Очевидно, что данная задача может быть решена просто перебором всех возможных вариантов распределения 100 тыс.ден.ед. по 4 предприятиям (всевозможных вариантов в данном примере не так уж и много). Однако попытаемся решить её более эффективным способом. Разобьём процесс оптимизации на 4 шага, и будем на каждом k -ом шаге оптимизировать инвестирование не всех предприятий сразу, а только предприятий с k -ого по 4 -ое. При этом, естественно, будем считать, что в остальные предприятия (с 1 -ого по (k-1) -ое) тоже вкладываются некоторые средства, и потому на инвестирование предприятий с k -ого по 4 -ое остаются не все средства, а некоторая сумма сk≤100 тыс.ден.ед. Эта величина и будет являться переменной состояния системы. Переменной управления на k -ом шаге назовем величину хk средств, вкладываемых в k -ое предприятие. В качестве функционального уравнения Беллмана fkk) на k -ом шаге в этой задаче можно выбрать максимально возможную прибыль, которую можно получить с предприятий с k -ого по 4 -ое при условии, что на их инвестирование осталось сk средств. Очевидно, что при вложении в k -ое предприятие хk средств, мы получим прибыль gk(xk), а система к (k+1)- ому шагу перейдет в состояние сk+1=ck-xk, т.е. на инвестирование предприятий с (k+1)- ого до 4 -ого останется сk+1 средств.

Итак, на первом шаге условной оптимизации при k = 4 функция Беллмана представляет собой не что иное, как прибыль только с 4-ого предприятия. При этом на его инвестирование может остаться количество средств сk, 0 сk 100 тыс.ден.ед. (в дальнейшем просто 100) Очевидно, чтобы получить максимум прибыли с последнего предприятия, надо вложить в него все эти средства, т.е. f44)= g44), xk*=сk.

 

Таблица 13

x4   с4                  
    - - - - -    
  -   - - - -    
  - -   - - -    
  - - -   - -    
  - - - -   -    
  - - - - -      

На каждом из последующих шагом для вычисления функции Беллмана приходится использовать результаты, полученные на предыдущем шаге. Пусть на втором шаге для инвестирования предприятия с третьего по четвертое осталось с3 средств (0 с3 100). Тогда от вложения в третье предприятие х3 средств будет получена прибыль g3(x3), а на инвестирование четвертого предприятия останется с3+14=c3-x3 средств. Максимально возможная прибыль, которая может быть получена с этих двух предприятий будет равна

Таблица 14

x3   с3                  
  0+0 - - - - -    
  0+16 11+0 - - - -    
  0+37 11+16 36+0 - - -    
  0+46 11+37 36+16 45+0 - -    
  0+63 11+46 36+37 45+16 60+0 -    
  0+80 11+63 36+46 45+37 60+16 77+0   40, 60

Максимум этого выражения f3*(c3) достигается при некотором значении х3*, которое и является оптимальным решением на втором шаге для состояния системы с3.

На третьем шаге для инвестирования предприятия со второго по четвертое осталось с2 средств (0 с2 100). Тогда от вложения во второе предприятие х2 средств будет получена прибыль g2(x2), а на инвестирование третьего и четвертого предприятий вместе останется с2+13=c2-x2 средств. Максимально возможная прибыль, которая может быть получена с этих трех предприятий будет равна

Таблица 15

x2   с2                  
  0+0 - - - - -    
  0+16 12+0 - - - -    
  0+37 12+16 26+0 - - -    
  0+52 12+37 26+16 36+0 - -    
  0+73 12+52 26+37 36+16 54+0 -    
  0+82 12+73 26+52 36+37 54+16 78+0    

Максимум этого выражения f2*(c2) достигается на некотором значении х2*, которое и является оптимальным решением на третьем шаге для состояния системы с2.

И, наконец, четвертый шаг. Для инвестирования предприятия с первого по четвертое осталось с1 средств (0 с1 100). Тогда от вложения в первое предприятие х1 средств будет получена прибыль g1(x1), а на инвестирование со второго по четвертое предприятий вместе останется с1+12=c1-x1 средств. Максимально возможная прибыль, которая может быть получена с этих предприятий будет равна

 

Таблица 16

x1   с1                  
  0+0 - - - - -    
  0+16 10+0 - - - -    
  0+37 10+16 31+0 - - -    
  0+52 10+37 31+16 42+0 - -    
  0+73 10+52 31+37 42+16 62+0 -    
  0+85 10+73 31+52 42+37 62+16 76+0    

Максимум этого выражения f1*(c1) достигается на некотором значении х1*, которое и является оптимальным решением на третьем шаге для состояния системы с1.

II этап. Безусловная оптимизация. Мы распределяем 100 тыс. ден.ед., т.е. 1-ый шаг: с1 = 100, F(100)= =85 тыс. ден.ед. при х1*=0.

2-ой шаг: с2 = с1 - х1* =100-0=100, из таблицы 15 можем найти, что х2*=20.

3-ий шаг: с3 = с2 – х2* =100-20=80, из таблицы 14 находим, что х3*=40.

4-ый шаг: с4 = с3 – х3* =80-40=40, из таблицы 13 видим, что х4*=40.

Итак, оптимальный план инвестирования четырех предприятий = (0; 20; 40; 40) принесет прибыль равную =85 тыс. ден.ед. Т.е. для получения возможно большей прибыли равной 85 тыс. ден.ед. второму предприятию необходимо выделить из общей суммы 20 тыс. ден.ед., третьему и четвертому по 40 тыс. ден.ед., а первое предприятие инвестиции не получает. ■

 

ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ

 

1. Предприятие производит продукцию двух видов: К1 и К2. Объем сбыта продукции К1 составляет не менее 70% общего объема реализации продукции обоих видов. Для изготовления продукции К1 и К2 используется одно и тоже сырье, суточный запас которого равен 330 кг. Расход сырья на единицу продукции К1 равен 3 кг, а на единицу продукции К2 - 4 кг. Цены продукции К1 и К2 - 10 и 20 ден.ед. соответственно. Определить оптимальное распределение сырья для изготовления продукции К1 и К2. Задачу решить графическим методом.

2. Для производства двух видов продукции А1 и А2 на фабрике использован материал трёх сортов В1, В2 и В3, имеющийся на складе в количестве 594, 614 и 574 соответственно. На изготовление изделия Аj расходуется аij кг материала сорта Вj. Матрица расхода ij) задана. От реализации единицы продукции А1 и А2 фабрика имеет прибыль соответственно 5 и 7 ден.ед. Используя симплекс-метод найти максимальную прибыль от реализации всей продукции.

(а ij)=

3. Построить двойственную задачу к предыдущей задаче (задаче 2) и записать её решение. Используя найденное решение определить наиболее дефицитный ресурс. На фабрику завезли материал сорта В1 в количестве 5 единиц. Возможно ли в этом случае увеличить прибыль и насколько? Оценить целесообразность введения в план нового вида продукции А3, если на её изготовление расходуется по 9 кг каждого сырья, а прибыль от реализации составляет 10 ден.ед.?

4. Готовая продукция заводов Аi (i= ) направляется на склады Вj (j= ). Заводы Аi производят аi тыс. изделий (а1= 250; а2= 150; а1= 400). Пропускная способность складов Вj за это время характеризуется величинами bj тыс. изделий (b1 = 100; b2 = 500; b3 = 100; b4 = 300). Стоимость перевозки с завода Аi на склад Вj одной тысячи изделий равна Сij.

Сij =

Найти план перевозки готовой продукции заводов на склады с минимальными затратами. Указать склады, пропускная способность которых использована не полностью, и величину резерва складских помещений в них.

5. Для увеличения объемов выпуска пользующейся повышенным спросом продукции, изготовляемой четырьмя предприятиями, последним выделены капиталовложения в объеме 600 млн. рублей. Составить оптимальный план распределения этих капиталовложений, если прирост выпуска продукции fj (xi) j -ым предприятием, когда ему выделено xi млн. рублей задается следующей таблицей.

Объем капиталовложений xi (млн. рублей) Прирост выпуска продукции fj (xi)
  Предприятие 1   Предприятие 2   Предприятие 3   Предприятие 4
         

 

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОГО ТЕСТИРОВАНИЯ

1. Математическая модель задачи линейной оптимизации

F = 8x1 +6x2 –3x3 (max)

x1≥0, x2≥0, х3≥0.

записана в форме: 1) симметричной;

2) канонической;

3) общей;

4) матричной.

 

2. После приведения математической модели задачи линейной оптимизации

F = 6x1 -3x2 +7x3 (min)

x1≥0, x3≥0

к каноническому виду мы получаем:

 

1) F = 6x1 -3x2 +7x3 (max) xj≥0, (j= ) 2) F = -6x1 +3() -7x3 (max) x1≥0, xj≥0, (j= ), x ≥0,
3) F =- 6x1 +3x2 -7x3 (max) xj≥0, (j= ) 4) F = -6x1 +3x2 -7x3 (max) xj≥0, (j= )

3. На рисунке изображен случай, когда своего максимального значения функция f(х) достигает

  1) в точке Е; 2) в точке В; 3) в точке А; 4) на отрезке ВД; 5) в точке F

4. В прямоугольной системе координат множество точек, удовлетворяющих ограничению изображено на рисунке

 

  1)   2)
  3)  
 
Х1
Х2
 
4)

5. Решая задачу линейной оптимизации графическим методом мы получаем следующую иллюстрацию. По данному рисунку можно сказать, что задача имеет:

  1) множество решений на максимум; 2) ОДР несовместна; 3) единственное решение на максимум; 4) единственное решение на минимум.

6. При решении данной задачи линейного программирования графическим методом F= 8x1 +3x2 (max)

x1≥0, x2≥0

получаем следующую иллюстрацию:

  1)    
 
 
2)

 

 
 
 
3)

  4)
 
 

7. Решение задачи максимизации находящееся в симплексной таблице является

БП   СП
3 1 5
х6 х2 х4 -1  
F        

 

  1) опорным; 2) оптимальным; 3) вырожденным; 4) не опорным.  

8. Определите разрешающий элемент в следующей симплексной таблице при решении задачи максимизации:

БП   СП
1 5 3
х4 х2 х6        
F   -2   -5

 

  1) 6; 2) 5; 3) 7; 4) 3; 5) 0.

9. После пересчета элементов данной таблицы задачи максимизации линейного программирования

БП   СП
1 2
х3 х4 х5      
F   -5 -8

мы приходим к следующей таблице

1)

БП   СП
5 2
х3 х4 х1   -1/12 -1/4 1/12 4/3 21/3 1/3
F   5/12 -19/3

 

2)

БП   СП
5 2
х3 х4 х1   1/12 1/4 -1/12 4/3 21/3 -1/3
F   5/12 -19/3

 

3)

БП   СП
1 4
х3 х4 х1   5/8 3/8 21/2 -1/8 1/8 -1/2
F   -2  

 

4)

БП   СП
1 4
х3 х4 х1   5/8 -3/8 21/2 1/8 -1/8 1/2
F   -2  

 

 

10. Экстремальные значения целевых функций двойственных задач линейного программирования связаны следующим соотношением:

1)

2)

3)

11. Модель двойственной задачи построенной к данной

f = 8х1 - 4х2+ 7х3 max.

1+ 3х2 - 4х3 106,

1+ 4 х2 + х3 205,

1+ 2х2+ 8х3 340.

хj 0, (j= .

 

принимает следующий вид:

1) φ = 8 у1 – 4 у2 + 7 у3 min 1 + 3 у2 – 4у3 106 1 +4 у2 + у3 205 1 + 2у2 + 8у3 340 уi 0, I = 2) φ = 106 у1 + 205 у2 +340 у3 min 1 + 5 у2 + 4у3 8 1 +4 у2 + 2 у3 -4 -4у1 + у2 + 8у3 7 уi 0, i =
3) φ = 106 у1 + 205 у2 +340 у3 max 1 + 5 у2 + 4у3 8 1 +4 у2 + 2 у3 -4 -4у1 + у2 + 8у3 7 уi 0, I = 4) φ = 8 у1 - 4 у2 + 7 у3 max 1 + 3 у2 - 4у3 106 1 +4 у2 + у3 205 1 + 2у2 + 8у3 340 уi 0, i =

 

 

12. При решении пары двойственных задач (одна из которых задача об оптимальном использовании ресурсов) получен следующий результат:

f() = 20x1+10x2+9x3 (max); =(10; 0; 3; 0; 8; 0); =(2; 0; 4; 0; 5; 0). Значение прибыли, если в производство ввести 3 единицы наиболее дефицитного ресурса, будет равно

1) 2) 3) 4) 5)
        другой ответ

 

13. Оцените целесообразность включения в план нового вида продукции, нормы затрат ресурсов на единицу которого равны соответственно 3, 4, 2, а прибыль от реализации равна 40 ден.ед., если при решении задачи о производстве продукции при оптимальном использовании ресурсов было получено следующее решение

  f() = 5x1+3x2+x3 (max) (5; 0; 24; 4; 0; 0) (0; 9; 3; 0; 2; 0).   1) нецелесообразно; 2) данное задача не разрешима; 3) целесообразно.

 

14. Оцените целесообразность закупки 10 единиц второго вида ресурса по цене 2,5 ден.ед., если при решении задачи о производстве продукции при оптимальном использовании ресурсов было получено следующее решение

  f() = 46x1+25x2+30x3 (max) (500;405; 0; 0; 0; 20) (4; 3; 0; 0; 0; 8).     4) нецелесообразно; 5) данное задача не разрешима; 6) целесообразно.  

 

15. План находящийся в данной таблице является

 

           
    4   7   1   5   2
    6   2   4   1   3
    5   6   7   4   8

 

  1) распределенным; 2) закрытым 3) опорным 4) оптимальным.  

 

 

16. Для клетки (1; 4) замкнутый цикл представлен в таблице

1)

         
    3   2 75 1 5
    9   8   7   6
    10   11 12   13

 

2)

         
  25 3   2   1 5
    9   8   7   6
  125 10   11   12   13

 

 

3)

         
  25 3   2 75 1   5
  150 9   8   7   6
    10   11   12   13

 

 

4)

         
  25 3   2   1 5
  150 9   8   7   6
    10   11   12   13

 

 

17. Оценка свободной клетки (2; 1) равна

 

         
    5   1   2   3
    6   3   7   1
    2   5   6   4

 

1) 8; 2) 1; 3) -1; 4) 4; 5) 7  

18. Полученный план перевозок транспортной задачи является

 

           
    6   7   2   8   0
    4   10   5   3   0
    8   9   12   11   0

 

  1) вырожденным; 2) оптимальным; 3) не опорным; 4) открытым.  

19. Если значение потенциала U2 = 1, то значение потенциала V3 будет равно

 

         
    5   4   1   3
    3   7   2   8
    2   6   4   5

 

  1) 6; 2) 5; 3) 0; 4) -2; 5) 3.

20. Для данного опорного плана, находящегося в следующей таблице, значение функции будет равно

 

           
    6   7   2   8   0
    4   10   5   3   0
    8   9   12   11   0

 

  1) 1050; 2) 990; 3) 850; 4) 1070.  

21. Принцип оптимальности Беллмана для задачи в которой решается вопрос о том, как спланировать работу группы предприятий, чтобы экономический эффект от выделенных этим предприятиям дополнительных финансовых или материальных ресурсов был максимальным, формализуется в следующее функциональное уравнение динамического программирования.

1)

2) fn(t)= max

3) fn(xn-1, un) = min (zn(xn-1, un)+fn-1(xn))

ОТВЕТЫ

 

К задачам для самостоятельного решения

1. (70, 30), fmax =1300.

2. (52; 1; 0; 84; 0), fmax =267.

3. (67/220; 0; 3/20; 0; 0), φmin=267; да, на ∆b1=5*(67/220)=67/44; (67/220)*9+0*9+(3/20)*9=45/11<10 – целесообразно.

4. Х1* = или Х2* = , fmin = 1850

5. =(100; 400; 100; 0) или =(200; 400; 0; 0), F(600)= = 910.

 

К тестовым заданиям

((__lxGc__=window.__lxGc__||{'s':{},'b':0})['s']['_228467']=__lxGc__['s']['_228467']||{'b':{}})['b']['_699615']={'i':__lxGc__.b++};





ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...

Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем...

ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...

Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...





Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:

             
Ответ            

©2015- 2024 zdamsam.ru Размещенные материалы защищены законодательством РФ.