Лекция: Вложение капитала в предприятия

Необходимо инвестировать Z=1000$ в m=10 предприятий. Как следует распределить деньги, если прибыль каждого из них задана как функция от вложенной суммы денег?

Обозначим xi — количество денег, вложенных в i-ое предприятие, pi(x) — прибыль i-го предприятия, если в него было вложено xi долларов. Тогда вопрос о распределении вложений сводится к решению следующей задачи:

Максимизировать

на множестве векторов

;

удовлетворяющих ограничениям

, целые, i=1, 2, …, 10;

x1+x2+ … +x10=1000

Пусть pi(0) = 0 и все функции монотонно возрастают.

Оптимальная стратегия заключена в том, чтобы определить величину xi для каждого предприятия. Предположим, что уже потрачено на первые четыре предприятия $ 450. Как следует потратить остаток на остальные предприятия? Вложение $ 550 в шесть предприятий является подстратегией. Если нам известно оптимальное решение всех подзадач такого типа, то из них можно собрать решение основной задачи. Проиллюстрируем этот подход на числовом примере.

Пример 1. Имеется 4 предприятия и в них нужно вложить $ 5 тыс. Требуется максимизировать

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

,

, целые,i=1, 2, 3, 4.

Граничные условия имеют вид pi(0) = 0 для всех i, значения функций pi(x) приведены в табл. 1.

Таблица 1

x p1(x) p2(x) p3(x) p4(x)

 

Каждая переменная принимает 6 возможных значений и “наивный” подход потребует перебора 64=1296 вариантов. Обозначим через fk(x) максимальную прибыль k первых предприятий, если в них будет вложено x долларов. Тогда f1(x) = p1(x) — максимальная прибыль первого предприятия. Для второго предприятия требуется определить вложения в x. Но если мы вложим x$ во второе предприятие, то остаток (x-x ) следует потратить оптимально, вкладывая его в первое предприятие. Тогда

,

.

Если мы определим значенияf2(x) для всех x, то

,

.

и наконец

,

.

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

Таблица 2

x f1(x) x1(x) f2(x) x2(x) f3(x) x3(x) f4(x) x4(x)

 

После заполнения табл. 2 имеем: f4(5)=61 и x4(5)=1. Это означает, что в четвертое предприятия вложили 1 тыс. долларов. Остается 5000 -1000 = 4000 неиспользованных средств. Обратимся к соответствующей позиции для предприятия №3 в табл. 2. Имеем: f3(4)=41 и x3(4)=3. Остаток средств: х=4-3=1. Для второго предприятия имеем: f2(1)=11 и x2(1)=0. Тогда обращаемся к позиции х=1 для предприятия № 1 и получаем: f1(1)=11 и x1(1)=1.

Оптимальным является набор х1=1; х2=0; х3=3 и х4=4. Процесс его вычисления из таблицы 2 называют обратным ходом динамической шкалы.

Упражнение 1. Решить следующие задачи о распределении средств Z между m предприятиями.

1. Z=7, m=4; 2. Z=10, m=4; 3. Z=8, m=3;

4. Z=9, m=4; 5. Z=5, m=3; 6. Z=6, m=3.

Значения функций fi(x) для каждой из задач представлены в табл. 3.

 

Таблица 3

  N1 N2 N3 N4 N5 N6

 

Задача о загрузке рюкзака

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

Задача ЛП. При заданных вещественных числах аij, bi, cj, i I= {1,2,…,m}, j J= {1,2,…,n} требуется максимизировать линейную функцию

на множестве n-мерных векторов

x=(x1,x2,…,xn),

удовлетворяющих линейным ограничениям

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

Если же на переменных xj кроме неотрицательности наложено требование целочисленности, то задача становится задачей целочисленного линейного программирования (ЦЛП). Многие из задач комбинаторной оптимизации формулируются как задачи ЦЛП. Для них наблюдается разрыв двойственности и методы ЛП для их решения непригодны. Здесь мы не сможем рассматривать весь круг проблем целочисленного программирования. Рассмотрим только простейший тип задач ЦЛП, задачу ЦЛП с одним ограничением. Такого рода задачи называются задачами о загрузке рюкзака. Здесь мы остановимся на трех, часто встречающихся моделях и приведем динамические методы для их решения.

Неограниченная задача о загрузке рюкзака

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

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

Предполагается, что вместимость рюкзака известна и равна G кг, и для каждого типа i= предметов заданы вес qiи ценность ci. Не умоляя общности можно считать, что z1<z2<…<zm. Рассматриваемый вопрос об оптимальной загрузке рюкзака сводится к решению следующей задачи.

Задача R1. При заданных величинах G, qi, ci, i= требуется максимизировать функцию

на множестве векторов

x = (x1, x2, …, xm),

с целочисленными неотрицательными компонентами, удовлетворяющими условию

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

где – Xz – множество всех неотрицательных целочисленных векторов x=(x1,x2,…,xm), для которых и граничные значения f(z)=0, z<q0=q1.

Для z [q0,G] справедливы рекуррентные соотношения

(1)

где Iz — множество i, для которых qiz.

Соответствующие величины f(z) и i(z) размещаются в таблице, построенной по типу табл. 4.

Таблица 4

q0 q0+1 q0+2
.
G
f(q0) f(q0+1) f(q0+2) f(G)
i(q0) i(q0+1) i(q0+2) i(G)

 

Проиллюстрируем решение задачи R1 на примере.

Пример 2. Входными данными задачи R1 являются:<G=45;m=4; q=(7,10,12,16), c=(11,15,21,16)>.

Результаты прямого хода динамического процесса приведены в табл. 5.

Таблица 5

z
f(z)
i(z)
z
f(z)
i(z)
z
f(z)
i(z)

 

Поясним фрагмент прямого хода для z=33. Предположим, что значения f(z) и i(z) для z [7;32] найдены и размещены в таблице 5. Воспользуемся рекуррентным соотношением 1. В рюкзак вместимостью z =33 любой из 4=х предметов.

При i=1: f1(33)= c1+f(z-q1) = 11+f(26)=11+43=54;

При i=2: f2(33)= c2+f(z-q2) = 15+f(23)=15+37=52;

Приi=3: f3(33)= c3+f(z-q3) = 21+f(21)=21+33=54;

При i=4: f4(33)= c4+f(z-q4) = 26+f(17)=26+26=52.

Максимальное значение f(33)=54 получено при i=1 или i=3. Зафиксируем одно из них: i=3.

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

z=45; f (45) =75; i (45) =1.

Так как q1=7, следующее значение z=45-7=38 и для z=38 имеем: f (38) =64; i (38) =3. Следующее значение z=38-q3=38-12=26. Для z=26 имеем: f (26) =43; i (26) =1. Следующее значение z=26-7=19 f (19) =32; i (19) =1. Следующее значение z=19-7=12; f (12) =21; i(12)=3. Наконец z=12-12=0 является остатком. Таким образом, оптимальный вектор x*=(3;0;2;0); μ(x*)= f(45)=75.

Упражнение 2. Решить неограниченную задачу загрузки рюкзака при следующих исходных данных:

1. <G=23; m=4; q=(5,7,11,13); c=(10,10,12,12)>;

2. <G=43; m=5; q=(7,11,12,16,19); c=(5,10,10,12,15)>;

3. <G=33; m=4; q=(8,9,11,12); c=(10,10,10,10)>;

4. <G=27; m=5; q=(3,7,8,11,13); c=(5,7,10,12,15)>;

5. <G=19; m=5; q=(3,5,8,9,11); c=(5,10,12,12,13)>;

6. <G=25; m=4; q=(6,7,9,11); c=(10,12,15,15)>;

7. <G=41; m=5; q=(7,10,12,13,17); c=(10,12,14,15,16)>;

8. <G=47; m=5; q=(8,11,13,13,15); c=(10,13,16,18,20)>;

9. <G=37; m=5; q=(6,7,10,11,12); c=(8,10,12,13,19)>;

10. <G=46; m=5; q=(7,11,12,13,15); c=(8,9,11,13,16)>.

Ограниченная задача о загрузке рюкзака

Часто в задаче о загрузке рюкзака неотрицательный целочисленный вектор должен удовлетворять дополнительным ограничениям xidi, где di — заданные натуральные числа, указывающие количество предметов в наборе для каждого вида i=. В таких случаях задача о рюкзаке описывается следующей моделью.

Задача R2. При заданных положительных величинах qi, ci, di, i= и G максимизировать линейную функцию

на множестве целочисленных векторов, удовлетворяющих условиям

Метод решения этой задачи базируется на рассмотрение двух параметрического семейства экстремальных задач

fk (z) =, z=, k=, (2)

где — множество неотрицательных целочисленных k — мерных векторов xk=(x1,x2,…, xk), удовлетворяющих ограничениям

xidi, i=; .

Вычислительный процесс так же разбивается на два этапа: прямой и обратный ход динамической шкалы. На первом этапе уже используется двухпараметрическое семейство функций

i(z)=min{ ,di}, z=, i= (3)

На первом шаге процесса вычисляют величины

x1(z)= 1(z), f1(z)= , z= (4)

Найденные значения величин f1(z) заносят в первый столбец таблицы 6, а отвечающие им значения x1(z) во второй столбец этой таблицы. Далее, используя рекуррентные соотношения

fk(z)= max{xkck+fk-1(z-xkqk)}, z=, k=, (5)

последовательно вычисляют значения функции fk и заносят их в соответствующие столбцы таблицы 6. Одновременно фиксируют величины xk(z), при которых достигаются максимумы и заносят их в следующий за fk(z) столбец табл. 6.

Таблица 6

z f1(z) x1(z) f2(z) x2(z) fm(z) xm(z)
q0 f1(q0) x1(q0) f2(q0) x2(q0) fm(q0) xm(q0)
q0 +1 f1(q0 +1) x1(q0 +1) f2(q0 +1) x2(q0 +1) fm(q0 +1) xm(q0 +1)
q0+2 f1(q0+2) x1(q0+2) f2(q0+2) x2(q0+2) fm(q0+2) xm(q0+2)
G f1(G) x1(G) f2(G) x2(G) fm(G) xm(G)

 

На втором этапе осуществляется обратный ход, используя содержимое таблицы 6. Поясним алгоритм на примере.

Пример 3. Рассмотрим ограниченную задачу о загрузке рюкзака с исходными данными <G=21; m=4; q=(7,10,12,16) c=(11,15,21,26) d=(2,1,1,2)>.

Динамическая шкала типа 6. приведена в табл. 7.

Таблица 7

z f1(z) x1(z) f2(z) x2(z) f3(z) x3(z) f4(z) x4(z)

Поясним вычисления на первом этапе для фрагмента: z=19; k=3. При этом все значения для k=1, k=2 для всех z [7,21] и k=3, z<19 уже известны и размещены в таблице. В рюкзак вместимостью z=19 можно поместить 0 или 1 предмет третьего вида.

При x3=0:f3(19)=0+f2(19)=26;

При x3=1: f3(19)=21*1+f2(19-12)=21+f2(7)=21+11=32.

Максимальное значение f3(19)=32, x3=1.

На обратном ходе для z=19 имеем x3=1; тогда новое значение z=19-12=7; x2=0 и, наконец, для z=7 имеем x1=1. Получаем вектор x=(1,0,1,0).

Упражнение 3. Решить ограниченные задачи загрузки рюкзака при следующих исходных данных.

1. <G=13; m=3; q=(3,5,8); c=(10,20,15); d=(2,2,1)>;

2. <G=14; m=3; q=(3,5,8); c=(10,15,20); d=(2,1,1)>;

3. <G=15; m=3; q=(3,4,7); c=(10,10,20); d=(1,1,2)>;

4. <G=12; m=3; q=(3,5,6); c=(10,12,15); d=(2,1,1)>;

5. <G=11; m=3; q=(4,7,8); c=(10,15,20); d=(2,1,1)>;

6. <G=9;m=4; q=(3,4,6,7); c=(10,10,18,20); d=(2,1,1,1)>;

7. <G=8; m=4; q=(3,4,4,5); c=(10,10,12,15); d=(2,2,1,1)>;

8. <G=7; m=4; q=(2,3,4,4); c=(10,12,18,18); d=(2,2,1,1)>;

9. <G=6; m=4; q=(2,2,3,5); c=(10,8,12,20); d=(1,2,1,1)>;

10. <G=5; m=4; q=(1,2,2,3); c=(10,18,20,25); d=(2,1,1,1)>.

Задача 0-1 рюкзак

В рамках ограниченной задачи о загрузке рюкзака часто встречаются ситуации, когда каждый предмет i имеется только в единственном экземпляре и его можно загрузить или не загрузит в рюкзак. В первом случае xi=1, а во втором — xi=0. Формально ситуация описывается моделью R2 и может быть разрешена с помощью рекуррентных соотношений (5). Однако для решения задачи 0-1 рюкзак достаточно применения однопараметрического семейства функций f(z) с рекуррентными соотношениями типа (1). Вместо номера предмета i(z), для которого в (1) достигнут максимум, удобно записывать кортеж Kz, совокупность номеров различных предметов, суммарный вес которых не превосходит z и равен f(z). Алгоритм, как и ранее, состоит из двух этапов. Поясним его подробнее на примере.

Пример 4. Входные данные задачи <G=5; m=7; q=(2,1,3,4,3,2,1)>, стоимостные характеристики совпадают с весовыми и все номера в каждом картеже должны быть различными (соблюдение равенства di=1 для всех i). Динамическая шкала представлена в табл. 8. Последняя строка соответствует решению. В данном случае – множеству решений, отвечающих одному и тому же значению f(z)=5.

Таблица 8

z f(z) {Kz}
(2) (7)
(1) (6) (2,7)
(3) (5) (1,2) (1,7) ( 2,6) (6,7)
(4) (2,3) (3,7) (2,5) (5,7) (1,2,7) (2,6,7) (1,6)
(2,4) (4,7) (2,3,7) (2,5,7) (1,2,6) (1,6,7) (1,3) (3,6) (2,3,7) (1,5) (5,6)

 

Рассмотрим подробнее процесс вычисления f(4)=4, и соответствующего множества картежей. Для z=4 имеем q4=4, первый картеж (4). Далее от z=4 отнимаем q2=q7=1, т.е. получаем 4=1+3; попарно объединяем кортежи, отвечающие z=1 и z=3; получаем кортежи (2,3) (3,7) (2,5) (5,7) отнимаем от z=4 q1=q6=2, получаем 4=2+2 и попарно объединяем не пересекающиеся и еще не зафиксированные кортежи, получаем: (1,6), (1,2,7) (2,6,7). Построенные три группы кортежей дают нам множество K4.

Для z=5 имеем множество K5, любой кортеж из K5 соответствует оптимальному решению.

Упражнение 4. Решить задачи (0-1) – рюкзак при следующих исходных данных:

1. <G=8; m=5; q=(2,3,2,4,3)> 2. <G=9; m=5; q=(2,2,3,5,4)>

3. <G=10; m=5; q=(2,3,4,3,2)> 4. <G=10; m=5; q=(1,3,3,4,2)>

5. <G=12; m=4; q=(3,5,4,2)> 6. <G=12; m=4; q=(3,4,5,6)>

7. <G=13; m=5; q=(2,3,5,7,2)> 8. <G=13; m=5;q=(3,4,4,5,6)>

9. <G=14; m=5; q=(2,2,3,5,7)> 10. <G=14; m=5; q=(3,3,4,5,7)>.

 

Контрольные вопросы

1. В чем заключается принцип оптимальности?

2. Какие задачи можно решать с помощью динамического программирования?

3. Чем отличаются ограниченная и неограниченная задачи о загрузке рюкзака?

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

5. Может ли существовать несколько оптимальных решений для одного набора исходных данных задачи о вложении капитала в предприятия?

6. Всегда ли при решении задач, рассмотренных выше, получают оптимальное решение с помощью динамического программирования?

Заключение

В работе рассмотрен один из методов динамического программирования — задача о загрузке рюкзака. Данная задача часто встает перед нами в жизни, ведь мы постоянно сталкиваемся с ограниченностью загружаемого нами пространства.

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

Список использованной литературы:

1. Ширяев В. И. Исследование операций и численные методы оптимизации. Из-во: КомКнига. 2007. — 216 с.

2. Акулич И.Л., Веселько Е.И., Ройш П., Стрельченок В.Ф. Экономико-математические методы и модели. Компьютерные технологии решения: Учебное пособие – Мн.: БГЭУ, 2003. – 348 с.

3. Белман Р., Дрейфус С. Прикладные задачи динамического программирования // М.: Наука.1965.

4. Мухачева Э.А., Рубинштейн Г.Ш. Математическое программирование // Новосибирск: наука СО.1987.

5. Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование // М.: Физматмит. 2002.

 

 

Составители: МУХАЧЕВА Элита Александровна,

ФИЛИППОВА Анна Сергеевна

ТАРАСОВА Татьяна Дмитриевна

 

 

МАТЕМАТИЧЕСКИЕ МЕТОДЫ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

для самостоятельной работы студентов по курсам

«Математические методы и модели исследования операций»,

«Методы оптимизации», «Комбинаторные алгоритмы»

Часть 3

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

 

Подписано в печать. .08. Формат 60х84 1/16.

Бумага офсетная. Печать плоская. Гарнитура Times New Roman.

Усл. печ. л. 2,25. Усл. кр.-отт. 2,0. Уч.-изд. л. 2,0.

Тираж 100 зкз. Заказ №

 

ГОУ ВПО Уфимский государственный авиационный

технический университет

Центр оперативной полиграфии УГАТУ

450000, Уфа-центр, ул. К. Маркса, 12

 
 
еще рефераты
Еще работы по информатике