Logo GenDocs.ru

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

Загрузка...

Лекции по ТПР - файл Лекция№11-тпр.doc


Лекции по ТПР
скачать (681.7 kb.)

Доступные файлы (18):

Лекция№01-тпр.doc38kb.12.11.2008 13:15скачать
Лекция№02-тпр.doc97kb.12.11.2008 13:25скачать
Лекция№03-тпр.doc179kb.12.09.2004 22:30скачать
Лекция№04-тпр.doc146kb.12.09.2004 22:31скачать
Лекция№05-тпр.doc131kb.12.09.2004 22:32скачать
Лекция№06-тпр.doc248kb.12.09.2004 22:33скачать
Лекция№09.doc177kb.03.10.2006 21:09скачать
Лекция№10-тпр.doc179kb.12.09.2004 22:49скачать
Лекция№11-тпр.doc353kb.25.11.2005 11:46скачать
Лекция№12-тпр.doc205kb.12.09.2004 22:53скачать
Лекция№13-тпр.doc191kb.12.09.2004 22:54скачать
Лекция№14-тпр.doc83kb.14.12.2004 14:25скачать
Лекция№15-тпр.doc301kb.12.09.2004 23:02скачать
Лекция№16-тпр.doc131kb.12.09.2004 23:04скачать
Лекция№17-тпр.doc542kb.12.09.2004 23:03скачать
Лекция№7-тпр.doc142kb.12.09.2004 22:38скачать
Лекция№8-тпр.doc93kb.12.09.2004 22:44скачать
Лекция№9-тпр.doc142kb.12.09.2004 22:47скачать

Лекция№11-тпр.doc

Лекция №11.

Задача о загрузке рюкзака (задача о ранце).

Постановка задачи. Пусть имеются N видов грузов с номерами .

Единица груза j-го вида имеет все aj. Если груз j-го вида берется в количестве xj, то его ценность в общем случае составляет F(xj). Имеется «рюкзак», грузоподъемность которого равна B. Требуется загрузить рюкзак имеющимися грузами таким образом, чтобы вес его был не больше заданного B, а ценность «рюкзака» была максимальной.

Составим Мат. Модель задачи. Пусть xj – количество груза j-го вида, помещаемого в рюкзак. Тогда можно записать:

(1)

(2)

(3)

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

Для этого погрузку «рюкзака» можно интерпретировать как N-этапный процесс принятия решений: на 1-м этапе принимается решение о том, сколько нужно взять груза 1-го вида, на 2-ом этапе – сколько груза 2-го вида и т.д. Такая интерпретация наталкивает на возможность применения для решения задачи (1) – (3) метода динамического программирования. Для этого приведем задачу (1) – (3) к виду (4) – (7) из предыдущей лекции.

Для этого введем обозначения: – вес рюкзака перед погрузкой груза j-го вида груза или вес рюкзака после погрузки грузов видов 1, 2, …, j – 1.Очевидно, что

y1 = 0. (4)
^

Текущий вес рюкзака определяется выражением


(5)

Текущий вес рюкзака в силу (2) удовлетворяет неравенству

 B. (6)

Очевидно ограничения (4) – (6) эквивалентны ограничению (2), поэтому вместо модели (1) – (3) можно рассматривать модель (1), (3) – (6). Здесь ограничение (6) выводит эту модель за рамки модели (4) – (7) из предыдущей лекции. Для сведения задачи к общему виду задач динамич. программирования, запишем (6) с учетом (5):

.

Отсюда следует: ,

или окончательно с учетом (3):

(7)

В результате исходная модель (1) – (3) свелась к эквивалентной модели вида

(8)

(9)

(10)

(11)

Задача (8)-(11) является частным случаем общей задачи динамического программирования, в которой . Здесь ограничение (9) является рекуррентным и отражает процесс загрузки рюкзака, а неравенство (10) задает область возможных значений .

Рассмотрим решение задачи (8)-(11) методои динамического программирования:

1 шаг. Вычисляется величина

(12).

В результате решения серии задач максимизации получаем точки максимума и значения .

S-тый шаг (). Вычисляются величины

(13)

В результате решения серии задач максимизации, получаем и . При s=1 решается только одна задача на максимум, т.к. значение - задано.

Для определения безусловных точек максимума, т.е. решения исходной задачи, проводим обратное движение алгоритма:

.

Отсюда:

.

Далее: . И так далее . Причем есть максимальное значение целевой функции.

Наличие условия целочисленности переменных xj и упрощает решение задачи. В этом случае . Здесь [] указывает на то, что берется целая часть числа. Если не целые, то .


Пример:

Постановка задачи:

Имеется свободный капитал в размере 4 млн. у.е. Этот капитал может быть распределен между 4-мя предприятиями, причем распределение осуществляется только целыми частями (0, 1, 2, 3 или 4 млн. у.е.). Прибыль, получаемая каждым предприятием при инвестировании в него определенной суммы, указана в таблице.

Предпр. Капитал

0 млн. у.е.

1 млн. у.е.

2 млн. у.е.

3 млн. у.е.

4 млн. у.е.

1-е предпр.

0

10

17

25

36

2-е предпр.

0

11

16

25

35

3-е предпр.

0

10

18

24

34

4-е предпр.

0

9

19

26

35

Требуется распределить инвестиции между предприятиями из условия максимальной общей прибыли.

^ Построение ММ.

Обозначим: хj- количество капиталовложений, выделенных j-тому предприятию (). Тогда прибыль, записанная в таблице, можно обозначить как Fj(xj) (). Например, F1(0)=0; F1(1)=10; F1(2)=17 и т.д. .... F2(0)=0; F2(1)=11; F4(4)=35.

Тогда математическая модель примет вид:





хj0 – целые, ()

Данная модель является частным случаем задачи о загрузке рюкзака, где N=4, В=4, аj=1 (). Введя новую переменную yj- израсходованные средства до выделения капиталовложений j-тому предприятию, приведем исходную модель к виду ЗДП:



; ()

y1=0;

; ()

Решение задачи проведем в соответствии с алгоритмом динамического программирования:

1 шаг.



  1. Зафиксируем y4=0. Тогда допустимые значения x4[0, 4-0]=[0,1,2,3,4].

    1. x4=0. Тогда F4(0)=0.

    2. x4=1. F4(1)=9.

    3. x4=2. F4(2)=19.

    4. x4=3. F4(3)=26

    5. x4=4. F4(4)=35.

Максимальное значение , и достигается оно при x4=4. Таким образом, заполняется первая строчка таблицы.

  1. Зафиксируем y4=1. Тогда допустимые значения x4[0, 4-1]= [0,1,2,3].

    1. x4=0. Тогда F4(0)=0.

2.2) x4=1. F4(1)=9.

2.3) x4=2. F4(2)=19.

2.4) x4=3. F4(3)=26

Максимальное значение , и достигается оно при x4=3. Таким образом, заполняется вторая строка таблицы.

Далее аналогично фиксируем y4=2, y4=3, y4=4. Заполняем оставшиеся строки таблицы.

Таблица шага №1.

y4 x4

0

1

2

3

4





0

0

9

19

26

35

35

4

1

0

9

19

26

-

26

3

2

0

9

19

-

-

19

2

3

0

9

-

-

-

9

1

4

0

-

-

-

-

0

0


2 шаг.



  1. Зафиксируем y3=0. Тогда допустимые значения x3[0, 4-0]=[0,1,2,3,4].

    1. x3=0. Тогда F3(0)=0. Определим значение второго слагаемого: при y3=0 и x3=0. Найдем y4=0+0=0. Тогда, обратившись к таблице шага 1, увидим, что . Следовательно, F3(0)+ =0+35=35. Этот результат заносим в таблицу шага 2 в ячейку, соответствующую y3=0 и x3=0.

    2. x3=1. Аналогично: F3(1)=10. Найдем y4= y3+ x3=0+1=1. Из таблицы шага 1 определим: =. Сумма

F3(1)+ =10+26=36.

    1. x3=2. F3(2)=18. y4=0+2=2.  ==19. Тогда F3(2)+ =18+19=37.

    2. x3=3. F3(3)=24, y4=0+3=3.  ==9. Тогда

F3(3)+ =24+9=33.

    1. x3=4. F3(4)=34. y4=0+4=4.  ==0. Тогда

F3(4)+ =34+0=34.

Максимальное значение =37, и достигается оно при x3=2. Первая строчка таблицы заполнена.

  1. Зафиксируем y3=1. Тогда допустимые значения x3[0, 4-1]= [0,1,2,3].

    1. x3=0. F3(0)=0. y4=1+0=1.  ==26. Тогда

F3(0)+ =0+26=26.

    1. x3=1. F3(1)=10. y4=1+1=2.  ==19. Тогда

F3(1)+ =10+19=29.

    1. x3=2. F3(2)=18. y4=1+2=3.  ==9. Тогда

F3(2)+ =18+9=27.

    1. x3=3. F3(3)=24 y4=1+3=4.  ==0. Тогда

F3(3)+ =24+0=24.

Максимальное значение , и достигается оно при x3=1. Таким образом, заполняется вторая строка таблицы.

  1. Зафиксируем y3=2. Тогда допустимые значения x3[0, 4-2]= [0,1,2].

3.1) x3=0. F3(0)=0. y4=2+0=2.  f4(2) =19. F3(0)+ f4(2)=0+19=19.

    1. x3=1. F3(1)=10. y4=2+1=3.  =9. F3(1)+ =10+9=19.

    2. x3=2. F3(2)=18. y4=2+2=3.  =0. F3(2)+ =18+0=18.

Максимальное значение достигается при двух возможных значениях x3: x3=1 и x3=0. В таблицу можно занести любое из них. Таким образом, заполняется третья строка таблицы.

Далее аналогично фиксируем y3=3, y3=4. Заполняем оставшиеся строки таблицы.


Таблица шага №2.

y3 x3

0

1

2

3

4





0

35

36

37

33

34

37

2

1

26

29

27

24

-

29

1

2

19

19

18

-

-

19

0 (или 1)

3

9

10

-

-

-

10

1

4

0

-

-

-

-

0

0


3 шаг.



Все вычисления производятся аналогично шагу 2. Не останавливаясь более подробно на этапах решения подзадачи данного шага, приведем получившуюся в результате таблицу.

Таблица шага №3.

y2 x2

0

1

2

3

4





0

37

40

35

35

35

40

1

1

29

30

26

25

-

30

1

2

19

21

16

-

-

21

1

3

10

11

-

-

-

11

1

4

0

-

-

-

-

0

0


4 шаг.



Последний шаг интересен тем, что здесь решается единственная задача максимизации при заданном y1=0.

y1=0. Следовательно x1[0, 4-0]= [0,1,2,3,4]. Выполняя все действия, аналогично предыдущим шагам, получим таблицу последнего шага, состоящую из единственной строки, соответствующей y1=0.

Таблица шага №4.

y1 x1

0

1

2

3

4





0

40

40

38

36

36

40

0 (или 1)

Далее проводим обратное движение алгоритма:

  1. y1=0, x1*=0,  y2*= y1+ x1*=0+0=0.

  2. Определяем значение x2* из таблицы шага № 3 по найденному y2*=0. Значению y2= y2*=0 соответствует значение x2(y2)=1. Следовательно, x2*=1. Далее можно определить y3*= y2*+ x2*=0+1=1.

  3. Аналогично, обращаясь к таблице шага №2, найдем: x3*= x3(1)=1, 

y4*= y3*+ x3*=1+1=2.

  1. Из таблицы шага №1 : x4*= x4(2)=2.

Окончательно имеем: первому предприятию средства не выделяются (x1*=0), второму выделяется 1 млн. у.е. (x2*=1), третьему предприятию – 1 млн. у.е. (x3*=1), и четвертому – 2 млн. у.е. (x4*=2). При этом значение целевой функции (общая прибыль по всем 4-м предприятиям) составит:

==40.


Метод динамического программирования для ЗНП с мультипликативной целевой функцией. Задача о надёжности.

Пусть имеется оптимизационная задача вида:

(1)

(2)

(3)

-задан (4)

З
десь предполагается, что Fj(xj,yj)>0 для всех допустимых значений xj,yj. В этом случае для решения задачи (1)-(4) рекуррентные соотношения Беллмана имеют вид:

(5)

, (6)

При j=1 величина y1 задана, поэтому в этом случае решается только одна задача максимизации.

В результате решения оптимизационных задач в соответствии (5) и (6) получим условные точки максимума и функции , . Далее, делая обратный ход алгоритма, находим окончательное решение задачи и .

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


^ Задачу о надежности.

Пусть конструируется электронный прибор, состоящий из трех основных компонентов. Все компоненты соединены последовательно, поэтому выход из строя одной из них приводит к отказу всего прибора. Надежность (вероятность безотказной работы) прибора можно повысить путем дублирования каждого компонента. Конструкция прибора позволяет использовать запасных блоков для каждого j-того компонента, т.е. каждый компонент может содержать до блоков, соединенных параллельно. Общая стоимость прибора не должна превышать С долларов. Если j-тый компонент имеет штук соединенных параллельно блоков, то его надежность составляет и стоимость . Требуется определить количество блоков в каждом j-том компоненте , при котором надежность прибора максимальна, а стоимость прибора не превышает заданной величины С.

Построение ММ. По определению, надежность F прибора, состоящего из N последовательно соединенных компонентов, каждый из которых включает параллельно соединенных блоков, равна произведению надежности компонент. Тогда ММ имеет вид:

(7)

(8)

, (9)

Из физического смысла задачи следует, что , >0 для всех допустимых .

Введем дополнительную переменную - количество средств, израсходованных на дублирование компонент 1,2,… j-1.Тогда можно записать:


(10)

(11)

Из (10) следует: . Тогда с учетом (9) область допустимых значений будет иметь вид , а рекуррентные соотношения Беллмана принимают вид:

(12).

(13)

Покажем применение рекуррентных соотношений Беллмана для решения задачи (7)-(9), решаемых в порядке . Проводя преобразования, аналогичные преобразованиям задачи о загрузке рюкзака, получим:







Здесь , есть область изменения при фиксированном .


Скачать файл (681.7 kb.)

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

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации