САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
КАФЕДРА МОДЕЛИРОВАНИЯ СОЦИАЛЬНО-ЭКОНОМИЧЕСКИХ СИСТЕМ
Фролова Анна Александровна
Выпускная квалификационная работа бакалавра
Построение и анализ математической модели
функционирования гостиничного комплекса
Направление 010400
Прикладная математика и информатика
Научный руководитель,
доктор физ.-мат. наук,
профессор
Малафеев О.А.
Санкт-Петербург
2016
Содержание
Введение......................................................................................................... 3
Постановка задачи ........................................................................................ 5
Обзор литературы ......................................................................................... 6
Глава 1. Формализованная постановка задачи распределения ресурсов
по гостиничному комплексу, состоящему из n объектов размещения.............. 7
1.1 Распределение капитальных вложений, обеспечивающее перевод
из заданных начальных состояний в планируемые на конец периода. ......... 7
1.2 Опорный план развития объектов размещения гостиничного
комплекса ............................................................................................................. 9
Глава 2. Принципы оптимальности........................................................... 14
2.1 Компромисс ....................................................................................... 14
2.2 Принцип оптимальности Беллмана ................................................. 15
Глава 3. Практическая часть ...................................................................... 17
3.1 Численное решение задачи .............................................................. 17
3.2 Программная реализация ................................................................. 20
3.2.1 Описание программы ................................................................ 20
3.2.2 Пример работы программы ....................................................... 21
3.2.3 Плюсы и минусы программы и ее возможные доработки .... 23
Выводы ......................................................................................................... 24
Заключение .................................................................................................. 25
Список литературы ..................................................................................... 26
Приложение 1. Данные решения примера................................................ 28
Приложение 2. Код программы ................................................................. 31
2
Введение
В
современном
мире
гостиничная
сфера
достаточно
быстро
развивается. В каждой стране туризм и гостиничный бизнес является одним
из способов увеличения ВВП. Существует множество крупных сетей отелей,
которые расположены по всему миру, например: Park inn, Marriott, Holiday
inn, Kempinski и другие.
Сеть отелей представляет собой множество средств размещения.
Средства размещения – объекты, которые эпизодически предоставляют
услуги по размещению и проживанию клиентов. Это могут быть отели,
мини-отели, хостелы, апартаменты, гостевые дома, кемпинги.
Для
каждого
владельца
отдельного
средства
размещения
или
гостиничной сети в целом важно увеличение прибыли, которое будет
достигнуто увеличением потока клиентов и улучшением качества услуг.
Туристы, выбирая отель, опираются на множественные факторы, например:
реклама отеля, состояние номерного фонда, соотношение «цена-качество» и
пр. Конечно, все гостиничные сети отелей выглядят по-разному, по своему
функционируют, имеют разные преимущества и недостатки, но каждый
директор стремится довести свою гостиничную сеть или отдельный объект
размещения до идеального состояния.
Цель данной работы состоит в том, чтобы найти метод оптимального
распределения капиталовложений для модернизации качества услуг.
Так как модернизация в каждой гостиничной сети требуется постоянно,
а не единожды, и каждый раз план распределения капиталовложений
изменяется для достижения показателей, при которых была бы максимальная
прибыль, то данная актуальность данной темы не должна вызывать
сомнений.
Актуальность повышения эффективности управления гостиничным
бизнесом в условиях рынка определена так же потребностями социального и
экономического развития общества.
3
Решение задачи оптимизации деятельности гостиничного комплекса на
потребительском рынке услуг требует наличие математической модели
взаимодействия для обеспечения прогноза результата на предстоящий
период времени в соответствие с выбранной стратегией.
Необходимость
построения
теории
конкурентных
процессов,
моделирующих реальные конфликты была давно, однако существенные
результаты
были
получены
сравнительно
недавно,
а
сама
теория
конкурентных процессов стала развиваться лишь в последние десятилетия.
Эта работа направлена на автоматизацию процесса нахождения
оптимального
плана
распределения
инвестиций
между
несколькими
объектами размещения гостиничной сети, который бы позволил объектам
размещения получать от вложенных в них инвестиций максимальный
прирост прибыли, как на одном объекте размещения, так и в совокупности на
всех объектах размещения в целом.
4
Постановка задачи
Задачей данной работы является построение, описание и анализ
математической модели функционирования гостиничного комплекса, где под
функционированием
рассматривается
процесс
модернизации,
при
распределении капиталовложений по объектам размещения гостиничной
сети, с целью получения наибольшей прибыли и привлечения большего
потока клиентов.
Рассматривается модель оптимального распределения ресурсов или
инвестиций по объектам размещения с учетом изменяющихся условий.
Капиталовложения
производятся
в
несколько
объектов
размещения
одновременно. В некоторый начальный момент времени известны состояния
объектов размещения, состояние вкладываемых средств, а так же возможные
варианты распределения данного капитала. Необходимо распределить
инвестиционные ресурсы по объектам размещения так, чтобы получить
максимальную суммарную прибыль.
Задача в данной работе состоит из двух частей. Первая часть
заключается
в
математического
изучении
метода
планирования,
экономической
построении
модели
оптимизации
и
распределения
капиталовложений, и анализе данной модели. Вторая часть заключается в
том, чтобы написать программу, которая будет рассчитывать оптимальное
распределение инвестиций между объектами размещения.
5
Обзор литературы
В настоящее время, можно найти много литературы на экономическую
тематику. При написании данной работы были использованы научная и
учебно-методическая
литература
на
темы
теории
игр,
принципов
оптимальности, динамическое программирование и др.
Определения из теории игр рассматриваются на основе книг Петросяна
Л.А. [12, 15].
Так же рассмотрено много книг по математическому моделированию
[4,5,7,8,9,10].
Принципы и условия оптимальности описаны в книгах [3, 9, 13]
В
ходе
работы
рассматривались
методы
динамического
программирования, рассмотренные в книгах [2, 6, 10].
Программа, реализованная в ходе работы, написана на зыке C++,
алгоритмы и правила работы на котором описаны в книгах [1, 14].
6
Глава 1. Формализованная постановка задачи
распределения
ресурсов
по
гостиничному
комплексу, состоящему из n объектов размещения
1.1
Распределение
обеспечивающее
перевод
капитальных
из
заданных
вложений,
начальных
состояний в планируемые на конец периода.
Пусть I = 1, …, n – множество объектов размещения. Предполагаем,
что состояние каждого объекта размещения данного гостиничного комплекса
может быть описано одним числовым параметром. Пусть Z0i – начальное
количественное состояние объекта размещения i. Предполагается заданным
перспективный план развития всех объектов размещения данного комплекса
Z = (Z1, …, Zi, …, Zn), определенный на конец некоторого периода
планирования.
В
плане
Z
компонента
Zi
означает
планируемое
количественное состояние развития объекта размещения i. Предполагается,
что на основе плана Z = (Z1, …, Zi, …, Zn) могут быть определены
оптимальные состояния всех объектов размещения данного комплекса.
Будем
обозначать
индексами
{1,
…,
j,
…,
m i}
–вектор,
характеризующий состояние объекта размещения i; {1, …, m, …, lj}–
компоненты j-вектора объекта размещения i. Предполагаем, что состояние
каждого вектора и компонент может быть охарактеризовано одним главным
параметром. Пусть Z0ij – начальное количественное состояние вектора j,
обслуживающего объект размещения i. Zi = (Zi1, …,Zij, …, Zimi), i = 1, .., n–
заданный перспективный план для всех векторов, определенный на конец
того же периода, на который определен перспективный план объекта
размещения гостиничного комплекса.
Должно выполняться равенство:
(1)
7
Пусть теперь Z0ijm– начальное количественное значение компоненты m,
соответствующей вектору j объекта размещения i. Предполагается заданным
значение для всех компонент Zij = (Zij1, …, Zijm, …, Zijn), i = 1, .., n, j = 1, .., m,
определенное на конец периода планирования, т.е. того же периода, на
который определены перспективные планы z и Zi, i =1,n по объектам
размещения и векторам. Очевидно, должно выполняться равенство:
Обозначим через Ui(t) инвестиции, вкладываемые в объект размещения
i, i = 1,n, в год t, t ϵ {0, 1, …, T-1}. Предполагается заданная функция С(t),
представляющая
собой
сумму
капиталовложений,
вкладываемых
в
капитальное строительство в год t. Пусть далее Uij(t) – капитальные
вложения, вкладываемые в объект размещения, j=1, .., mi вектора i в год t;
Uijm(t) –капитальные вложения, характеризующие компоненту j объекта
размещения i в год t.
Должно выполняться:
(3)
Ui(t)≥0;
Uij(t)≥0;
Uijm(t)≥0; i=1, .., n; j=1, .., mi;
m=1, .., lj.
Зная начальное и планируемое на конец периода состояние объектов
размещения, векторов и компонент и ежегодные капитальные вложения в
строительство, и ремонт объектов размещения, можно определить для них
распределение капитальных вложений, удовлетворяющее (3) во все моменты
времени t ϵ{0, 1, …, T-1} и обеспечивающее их одновременный перевод из
заданных начальных состояний в планируемое на конец периода T при
выполнении определенных требований оптимальности и баланса ресурсов.
Таким требованием на данном этапе рассматриваемой задачи, например,
будет служить требование максимального сглаживания диспропорций между
8
объектами размещения данного гостиничного комплекса.[4]
1.2 Опорный план развития объектов размещения
гостиничного комплекса
Рассмотрим ситуацию, в которой на всех уровнях планирования
развитие осуществляется пропорционально вкладываемому капиталу, т.е.
если:
∆Zi(t) = Zi(t+1) – Zi(t); ∆Zij(t) = Zij(t+1) –Zij(t); ∆Zijm(t) = Zijm(t+1) –Zijm(t),
через Zi(t), Zij(t), Zijm(t) обозначены соответственно количественные
состояния объектов размещения, векторов и компонент в год t ϵ {0, 1, …, T1},
тогда ∆Zi(t)*Si=Ui(t); ∆Zij(t)*Sij=Uij(t); ∆Zijm(t)*Sijm=Uijm(t).
Величины Si, Sij, Sijm – единичные стоимости на соответствующих
уровнях, которые рассматриваются на втором этапе планирования.
Одним из планов капитального развития, переводящим объекты
размещения из состояния Z0 в планируемое Z, является опорный план
распределения капитальных вложений, который позволяет одновременно
перевести все объекты размещения из Z0 в Z и в какой-то степени
ликвидирует диспропорции между ними.
Определим опорный план развития объектов размещения гостиничного
комплекса.
Если доля средств, вкладываемых в каждый объект размещения, из
года в год не изменяется, то развитие от начального состояния Z0 к заданному
конечному Z будет происходить, лишь при условии, если для этого объекта
размещения будет выделяться в каждый год t сумма:
(4)
- капиталоемкость объекта размещения i;
- сумма инвестиций, необходимая для всех объектов
9
размещения;
Ясно, что
Должно выполняться, так как сумма инвестиций, вкладываемых во все
объекты размещения, должна быть равна заданной ранее функции C(t).
Таким образом, коэффициент при С(t) в выражении (4) означает долю
средств, необходимых для развития объектов размещения гостиничной
структуры.
Построим теперь опорный план распределения капитальных вложений
на
всех
уровнях
иерархической
системы
управления
развитием
инвестируемых объектов размещения.
Для векторов:
U ij (t )
( Z ij Z ij0 ) S ij
(Z
ij
Z ij0 ) S ij
U i (t )
j
при
U
ij
(t )U i (t )
j
Для компонент:
U ijm (t )
0
( Z ijm Z ijm
) S ijm
(Z ijm Z ijm0 ) S ijm
U ij (t )
j
при
U
ijm
(t )U ij (t )
m
Используя предыдущее построение, попытаемся предложить некую
грубую методику допустимости перспективного плана развития с точки
зрения сохранения существующего в данном изолированном комплексе
равновесия.
10
При подобном планировании обычно определяют некоторые основные
показатели (для основных объектов размещения) Z = (Z1, …, Zi, …, Zn), к
которым
должно
стремиться
развитие
гостиничного
комплекса.
Приближение к данным показателям требует развития материальных и
трудовых ресурсов.
В связи с тем, что для небольшого гостиничного комплекса удельные
затраты на развитие 1/S можно считать постоянными, для простоты мы
будем строить одноуровневую модель.
Пусть Z0- начальное состояние тех основных объектов размещения, по
которым заданы показатели в перспективном плане развития Z .
Система модернизации ежегодно для своего развития получает
некоторый капитал С(t). 1/S – удельные затраты для каждого объекта
размещения также известны. Построим опорный план развития данной
системы:
U i (t )
( Z i Z i (t )) / S i
(Z
i
Z i (t )) / S j
C (t )
i
По заданному опорному плану рассчитываем ресурсы, требуемые для
ее развития.
Пусть кроме основных объектов размещения существуют еще и
вспомогательные. Выделяя некую долю C (t ) на развитие основных
объектов размещения, мы можем получить опорный план развития
гостиничного комплекса:
U i (t )
( Z i Z i (t )) / S i
(Z i Z i (t )) / S j
C (t )
i
Тогда можем рассчитать ресурсы, требуемые для него, а также объем
капитальных вложений, необходимый для развития вспомогательных
объектов размещения.
Пусть H k1 - количество ресурса типа k, имеющегося в наличии в год t,
11
который может быть использован на развитие; ik - количество ресурса типа
k, необходимое для развития объекта размещения i на единицу; aij количественный рост j-того вспомогательного объекта размещения при росте
объекта размещения i на единицу; 1/ l j - удельные капитальные вложения,
необходимые для роста вклада j-того вспомогательного объекта размещения;
ij - количество ресурса типа k, необходимое для развития вспомогательного
k (t ) - капитальные вложения,
объекта размещения j на 1 единицу;
направленные на развитие объекта размещения, производящей ресурс типа k
в год t; 1 / j - удельные капитальные вложения, необходимые для роста
производства ресурсов на единицу;
j (t )
- капитальные вложения,
направленные на развитие j-того вспомогательного объекта размещения в год
t;
y j (t )
- количественное состояние j-того вспомогательного объекта
размещения в год t.
0
Известно, что наибольшая скорость движения из состояния Z в Z при
выделении на развитие основных объектов размещения капитальные
вложения * C (t ) , где * max при условии:
Z
i
ik
y j ij H k1 k k (t )
i
j
Z a
i
ij
l j j (t ) yi (t )
i
k
(t ) j (t ) C (t ) C (t )
k
j
k (t ) 0, k 0, j 1, m, k 1, n
Или, что тоже самое: max при условии:
S U
i
i
(t ) ik l j j (t ) H k1 k k (t ),
i
j
S U (t )a
i
i
ij
l j j (t )
i
k
k
(t ) j C (t ) C (t )
j
k (t ) 0, j (t ) 0, j 1, m, k 1, n
12
Решение данной задачи даст нам опорный план развития для основных
объектов размещения: U j * U (t ), капитальные вложения
k
(t) на развитие
k
производства объектов размещения и капитальные вложения, необходимые
для развития вспомогательных объектов размещения.
Пусть H k (t ) - количественное состояние ресурса типа k в год t, y j (t ) количественное
состояние
объекта
размещения
j.
После
освоения
капитальных вложений k (t ) и j (t ) , получаемых в результате решения
задачи, мы получим новое состояние: H k (t 1) H k (t ) k k (t ) . Величины
H k (t ) могут быть рассчитаны для всех k и t.
Пусть Т – момент достижения объектами размещения планируемого
состояния Z ; величины H k , k 1, n задают ограничения на ресурсы данного
гостиничного комплекса; начальное состояние Z 0 называется допустимым,
если не существует такого t 0,1,..., T и такого индекса k 0 , что
H k 0 (t ) H k 0
Предполагаемая методика определения допустимости перспективных
проектов развития объектов размещения позволяет сравнивать различные
планы с точки зрения их влияния на существующее равновесие в
гостиничном комплексе и восстанавливать его, если оно нарушено.[7]
13
Глава 2. Принципы оптимальности
Для принятия решений в различных ситуациях существует множество
принципов оптимальности, таких как, например, вектор Шепли, равновесие
по Нэшу, оптимальное решение по Парето.[8,12] В ходе данной работы,
рассматриваются
лишь
два
принципа
оптимальности,
таких
как
компромиссное множество и принцип оптимальности Беллмана. Рассмотрим
и дадим понятия этих принципов оптимальности.
2.1 Компромисс
Дадим определение компромиссного множества. Будем рассматривать
следующую игру Γ, которая описывается множеством игроков I, с
элементами i ∈ I.
Множество игроков конечно. Каждый из игроков имеет множество
стратегий. Обозначим множество стратегий i-го игрока xi
Множество всех возможных ситуаций в игре это произведение
И для каждого игрока i определена функция дохода Нi: Х->R1
Посчитаем невязки :
.
После того, как посчитали невязки для каждого игрока, можем
построить идеальный вектор M=(M1…Mn).
Далее имеем
Это и будет компромиссным множеством.[10,15]
Если рассматривать это определение в контексте данной работы то
можно сформулировать его так. Рассматривается гостиничный комплекс с
множеством владельцев различных объектов размещения данного комплекса.
У каждого владельца своя функция дохода от траектории развития
14
комплекса. У каждого из них существует своя оптимальная стратегия
развития. Почитаем степень неудовлетворенности каждого владельца как
разность максимальной функции дохода и той которую он имеет. Таким
образом мы найдем ситуацию в которой самый обиженный владелец обижен
в наименьшей степени.
2.2 Принцип оптимальности Беллмана
Идея данного принципа оптимальности состоит в том, что каким бы ни
был последующий шаг, нужно выбирать управление системы таким образом,
чтобы максимизировать доход как на данном шаге, так и на всех
последующих шагах. Следовательно, оптимальную стратегию мы можем
получить двигаясь от конца к началу, т.е. начинаем поиск стратегии с
последнего n-го шага. Одним словом, на каждом шаге ищется такое
управление, которое обеспечивает оптимальное продолжение процесса
относительно достигнутого в данный момент состояния и обеспечивает
максимальное значение функции дохода.
Управление, выбор которого основывается на предположениях о том,
какой был произведен предыдущий шаг, называется условно оптимальным
управлением.
Таким образом, на каждом шаге требуется находить условно
оптимальное управление для любой из возможных ситуаций предыдущего
шага.
Опишем теперь данный принцип оптимальности математически.
Пусть
− максимальный доход, получаемый за n шагов при
переходе системы из начального состояния
оптимальной
un*) а
- максимальный доход, получаемый при переходе из любого
в
конечное
состояние
управления
при
реализации
состояния
стратегии
в конечное состояние
при
u*=(u1*,u2*,
оптимальной
…,
стратегии
15
управления на оставшихся n-k шагах. Тогда
при k=1, …, n.
Это и есть основное функциональное уравнение Беллмана.[3, 12]
16
Глава 3. Практическая часть
С практической точки зрения, была решена задача переводящая
систему объектов размещения гостиничной сети из начального состояния, в
какое-то конечное состояние с целью максимизации прибыли. Так же была
реализована программа для решения данной задачи в общем случае.
3.1 Численное решение задачи
Рассмотрим задачу о выделении m средств, которые должны быть
распределены между n объектами размещения гостиничного комплекса.
Для наглядности возьмем параметры равные m = 5, n = 10. Итак,
рассмотрим оптимальный план распределения 5 тыс. денежных единиц
между десятью объектами размещения.
Рассмотрим исходные данные, приведенные в таблице 1.
Кол-во денежных
Получение общей прибыли денежных единиц
единиц
X
p1(x) p2(x) p3(x) p4(x) p5(x) p6(x) p7(x) p8(x) p9(x) p10(x)
1
47
35
22
25
40
43
37
38
51
69
2
48
37
34
27
42
46
39
39
53
71
3
49
37
41
29
45
48
51
64
55
72
4
50
39
42
33
46
52
54
65
57
75
5
55
45
57
38
54
61
67
72
78
83
Таблица 1
Количество шагов в данной задаче i = 10.
1) На первом шаге предполагаем, что все средства отданы последнему,
десятому объекту размещения (i = 10), в этом случае ищем максимальный
доход по таблице. Очевидно, что он равен 83.
На каждом дальнейшем шаге, будем строить таблицу, в которой первые
столбцы это вложенные средства(ei-1), 2 – проект (ui), 3 – остаток средств(ei =
ei-1-ui, 4 – по исходным данным, о функциях дохода(pi(ui)), 5 – седьмой
столбец предыдущей таблицы, 6 – сумма значений 4-го и 5-го столбца, 7 –
17
максимальное
значение
предыдущего
столбца
для
фиксированного
начального состояния, 8 – распределение инвестиций из второго столбца, на
котором достигается максимум в седьмом столбце.
2) На втором шаге будем распределять инвестиции между 9 и 10
объектами размещения (i = 9). Проделав все действия, получаем таблицу 2.
При этом рекуррентное соотношение по принципу оптимальности
Беллмана, который мы рассматривали в п.2.2 имеет вид:
e8
1
u9
0
1
0
1
2
0
1
2
3
0
1
2
3
4
0
1
2
3
4
5
2
3
4
5
e9=e8-u9
1
0
2
1
0
3
2
1
0
4
3
2
1
0
5
4
3
2
1
0
p9(u9)
P*9(e8)
0
69
51
0
0
71
51
69
53
0
0
72
51
71
53
69
55
0
0
75
51
72
53
71
55
69
57
0
0
83
51
75
53
72
55
71
57
69
78
0
Таблица 2
P8(u9,e8)
69
51
71
120
53
72
122
122
55
75
123
124
124
57
83
126
125
126
126
78
P*9(e9)
69
u9 (e9)
0
120
1
122
1
124
2
126
1
3)На третьем шаге распределяем инвестиции между 8,9,10 объектами
размещения
(i=8).
Проделав
все
действия,
получаем
таблицу
3.
При этом рекуррентное соотношение по принципу оптимальности Беллмана
имеет аналогичный вид что и на предыдущем шаге.
e7
1
2
u8
0
1
0
1
e8=e7-u8
1
0
2
1
p8(u8)
0
38
0
38
P*8(e7)
69
0
120
69
P7(u8,e7)
69
38
120
107
P*8(e8)
69
u8 (e8)
0
120
0
18
2
0
1
2
3
0
1
2
3
4
0
1
2
3
4
5
3
4
5
0
3
2
1
0
4
3
2
1
0
5
4
3
2
1
0
39
0
38
39
64
0
38
39
64
65
0
38
39
64
65
72
0
122
120
69
0
124
122
120
69
0
126
124
122
120
69
0
Таблица 3
39
122
158
108
64
124
160
159
133
65
126
162
161
184
134
72
158
1
160
1
184
3
Далее, проделав, аналогичные действия, и получив результаты,
представленные в Приложении 1, переходим к последнему шагу.
10)Определяем оптимальную стратегию при распределении денежных
средств между объектами размещения 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Проделав все
действия, получаем таблицу 10.
0
e
1
2
3
4
5
1
u
0
1
0
1
2
0
1
2
3
0
1
2
3
4
0
1
2
3
4
5
1
0
1
e =e -u
1
0
2
1
0
3
2
1
0
4
3
2
1
0
5
4
3
2
1
0
1
0
P1(u )
P*1(e )
0
69
47
0
0
120
47
69
48
0
0
163
47
120
48
69
49
0
0
203
47
163
48
120
49
69
50
0
0
241
47
203
48
163
49
120
50
69
55
0
Таблица 10
1 0
P0(u ,e )
69
47
120
116
48
163
167
117
49
203
210
168
118
50
241
250
211
169
119
55
1
1
1
P*1(e )
69
u (e )
0
120
0
167
1
210
1
250
1
Просмотрев в обратном порядке все таблицы, по аналогии, получаем,
19
что оптимальный план распределения инвестиций (1, 0, 0, 0, 1, 1, 0, 0, 1, 1)
Таким образом, увидим, что наибольшая возможная прибыль, которую мы
можем получить из исходных данных (таблица 1), равна 250. И для этого
необходимо вложить 1 тыс. денежных единиц в объект размещения 1, 1 тыс.
денежных единиц в средство размещения 5, 1 тыс. денежных единиц в
средство размещения 6, 1 тыс. денежных единиц в средство размещения 9, 1
тыс. денежных единиц в средство размещения 10.
3.2 Программная реализация
Как видно из примера, чем больше объектов размещения мы
рассматриваем и чем больше средств инвестируем, тем более сложны и
громоздки расчеты. В связи с этим, была реализована программа, которая
считает примеры любого размера.
3.2.1 Описание программы
Программа реализована на языке C++.
Пусть
n
–
количество
объектов
размещения,
которые
мы
рассматриваем, W – общая сумма капитальных вложений, которую мы
вкладываем в объекты размещения с целью получения максимальной
прибыли.
Для каждого объекта размещения i, i = 1, .., n перебирается сумма в
денежных единицах (далее д.е.), которую мы вкладываем в первые i
предприятий, назовем это сумму c (0≤c≤W). Теперь по принципу
оптимальности Беллмана, на каждом шаге нужно выбирать такой результат,
чтобы оптимальной была сумма выигрышей на всех оставшихся до конца
процесса шагах, включая выигрыш на данном шаге. Переберем, сколько мы
вложили в i-ое предприятие. Пусть это будет k (0≤k≤с). Тогда, при вложении
c д.е. в первые i предприятий выберем максимум среди вложений k д.е. в i-ое
и c-k в предыдущие i-1 предприятия. Таким образом, ответ задачи
получается, когда мы вкладываем все W д.е. во все n предприятий.
20
3.2.2 Пример работы программы
В качестве примера работы программы, возьмем исходные данные
задачи, решенной в п. 3.1. Благодаря этому проверим правильность работы
программы.
В первую строку вводим W – количество инвестируемых средств, n –
количество объектов размещения. Далее вводим данные из таблицы 1.
Рисунок 1
На рисунке 1 представлен пример входных данных, в файле input.txt.
Запустив программу, посмотрим на результат, полученный в файле
output.txt. Отобразим его на рисунке 2.
21
Рисунок 2
Таким образом, видим, что получили те же результаты, что и ранее.
Так же можем в процессе решения данной задачи вывести в файл
промежуточные расчеты, соответствующие алгоритму, рассказанному в 3.2.1
Получаем результаты, представленные на рисунке 3.
Рисунок 3
Опираясь на эти данные, можно говорить о том, что получаются
верные результаты.
22
3.2.3
Плюсы
и
минусы
программы
и
ее
возможные
доработки
Данный алгоритм работает за O(n W2) времени и O(n W) памяти, что
является оптимальным для этой задачи. Однако, если мы хотим только
посчитать суммарную прибыль, расход памяти можно уменьшить до O(W).
Минус данной программы состоит в громоздких входных данных,
которые должны содержаться в файле.
23
Выводы
1. Построена и рассмотрена модель распределения ресурсов по
гостиничному комплексу, состоящему из n объектов размещения
2. Решен целочисленный пример распределения инвестиций между
десятью объектами размещения
3. Реализована программа, решающая данную задачу в общем случае
не только для целых чисел.
24
Заключение
В ходе выполнения данной работы были изучены многочисленные
источники, в таких сферах как «Динамическое программирование» [2, 6, 10]
и «Экономическая оптимизация» [3, 9, 13]. Были углублены знания в
принципы оптимальности и моделирование экономических процессов.
Так
же,
была
построена
модель
распределения
ресурсов
по
гостиничному комплексу, состоящему из n объектов размещения, и описаны
принципы оптимальности, используемые при решении целочисленного
примера.
Был решен целочисленный пример распределения инвестиций между
объектами размещения, и была разработана программа, решающая данную
задачу в общем случае, которая работает так же с вещественными числами. С
помощью
этой
программы
была
проверена
правильность
решения
целочисленного примера, рассмотренного до этого.
25
Список литературы
1. Бьерн Страуструп, Язык программирования С++, Изд-во Бином, 2011,
1136 с.
2. Беллман Р., Калаба Р., Динамическое программирование и современная
теория управления, М.: Изд-во Иностранная литература, 1960, 400с.
3. Зенкевич Н.А.,
Петросян
Л.А., Оптимальный
поиск
в
условиях
конфликта. Л., ЛГУ, 1987 г, 75 с.
4. Зубов В.И., Петросян Л.А. Математические методы в планировании,
Ленинград, 1982, 112 с.
5. Колокольцев В.Н., Малафеев О.А. Динамические конкурентные
системы многоагентного взаимодействия и их асимптотическое
поведение(часть I), Вестник гражданских инженеров. 2010. № 4. С.
144-153.
6. Лежнев А.В., Динамическое программирование в экономических
задачах, М.: 2010.-176 с.
7. Малафеев О.А., Дроздов Г.Д. Моделирование процессов в системе
управления городским строительством, Санкт-Петербург, Том 1, 2001,
401 c.
8. Малафеев О.А., Зубова А.Ф. Математическое и компьютерное
моделирование
социально-экономических
систем
на
уровне
многоагентного взаимодействия (введение в проблемы равновесия,
устойчивости, надежности), Санкт-Петербург, 2006, 1006 c.
9. Малафеев О.А., Пахар О.В. Динамическая нестационарная задача
инвестирования
проектов
в
условиях
конкуренции,
Проблемы
механики и управления: Нелинейные динамические системы. 2009. №
41. С. 103-108.
10.Парфенов
А.П.,
Малафеев
О.А.
Равновесие
и
компромиссное
управление в сетевых моделях многоагентного взаимодействия,
Проблемы
механики
и
управления:
Нелинейные
динамические
26
системы. 2007. № 39. С. 154-167.
11.Петросян Л.А., Захаров В.В. Введение в математическую экологию. Л.,
ЛГУ, 222 с.
12.Петросян Л.А., Зенкевич Н.А., Шевкопляс Е.В. Теория игр. — СанктПетербург: БХВ — Петербург, 2012. — 480 С.
13.Печерский С.Л., Соболев А.И. Проблема оптимального распределения
в социально-экономических задачах и кооперативные игры. - Л.: Наука,
1983. - 176 с.
14.Scott Meyers, «Effective Modern C++», 2016, 304 с
15.Malafeev O.A., Kolokoltsov V.N. Understanding game theory, New Jersey,
2010,286.
16.Ссылка на онлайн компилятор программы, реализованной в данной
работе:
http://cpp.sh/6iw5w
27
Приложение 1. Данные решения примера
4) I = 7
6
7
e
1
u
0
1
0
1
2
0
1
2
3
0
1
2
3
4
0
1
2
3
4
5
2
3
4
5
7
6
7
e =e -u
1
0
2
1
0
3
2
1
0
4
3
2
1
0
5
4
3
2
1
0
7
6
P7(u )
P*7(e )
0
69
37
0
0
120
37
69
39
0
0
158
37
120
39
69
51
0
0
160
37
158
39
120
51
69
54
0
0
184
37
160
39
158
51
120
54
69
67
0
Таблица 4
7 6
P6(u ,e )
69
37
120
106
39
158
157
108
51
160
195
159
120
54
184
197
197
171
123
67
7
7
7
P*7(e )
69
u (e )
0
120
0
158
0
195
1
197
1
5) i = 6.
5
6
e
1
2
3
4
5
u
0
1
0
1
2
0
1
2
3
0
1
2
3
4
0
1
2
3
4
5
6
5
6
e =e -u
1
0
2
1
0
3
2
1
0
4
3
2
1
0
5
4
3
2
1
0
6
P6(u )
0
43
0
43
46
0
43
46
48
0
43
46
48
52
0
43
46
48
52
61
5
P*6(e )
69
0
120
69
0
158
120
69
0
195
158
120
69
0
197
195
158
120
69
0
6 5
P5(u ,e )
69
43
120
112
46
158
163
115
48
195
201
166
117
52
197
238
204
168
121
61
6
6
6
P*6(e )
69
u (e )
0
120
0
163
1
201
1
238
1
28
Таблица 5
6) I = 5
4
5
e
1
u
0
1
0
1
2
0
1
2
3
0
1
2
3
4
0
1
2
3
4
5
2
3
4
5
5
4
5
e =e -u
1
0
2
1
0
3
2
1
0
4
3
2
1
0
5
4
3
2
1
0
5
4
p5(u )
P*5(e )
0
69
40
0
0
120
40
69
42
0
0
163
40
120
42
69
45
0
0
201
40
163
42
120
45
69
46
0
0
238
40
201
42
163
45
120
46
69
54
0
Таблица 6
5 4
P4(u ,e )
69
40
120
109
42
163
160
111
45
201
203
162
114
46
238
241
205
165
115
54
5
5
5
P*5(e )
69
u (e )
0
120
0
163
0
203
1
241
1
7) I = 4
3
4
e
1
2
3
4
5
u
0
1
0
1
2
0
1
2
3
0
1
2
3
4
0
1
2
3
4
5
4
3
4
e =e -u
1
0
2
1
0
3
2
1
0
4
3
2
1
0
5
4
3
2
1
0
4
p4(u )
0
25
0
25
27
0
25
27
29
0
25
27
29
33
0
25
27
29
33
38
3
P*4(e )
69
0
120
69
0
163
120
69
0
203
163
120
69
0
241
203
163
120
69
0
Таблица 7
4 3
P3(u ,e )
69
25
120
94
27
163
145
96
29
203
188
147
98
33
241
228
190
149
102
38
4
4
4
P*4(e )
69
u (e )
0
120
0
163
0
203
0
241
0
29
8) I = 3
2
3
e
1
u
0
1
0
1
2
0
1
2
3
0
1
2
3
4
0
1
2
3
4
5
2
3
4
5
3
2
3
e =e -u
1
0
2
1
0
3
2
1
0
4
3
2
1
0
5
4
3
2
1
0
3
2
p3(u )
P*3(e )
0
69
22
0
0
120
22
69
34
0
0
163
22
120
34
69
41
0
0
203
22
163
34
120
41
69
42
0
0
241
22
203
34
163
41
120
42
69
57
0
Таблица 8
3 2
P2(u ,e )
69
22
120
91
34
163
142
103
41
203
185
154
110
42
241
225
197
161
111
57
3
3
3
P*3(e )
69
u (e )
0
120
0
163
0
203
0
241
0
9) I = 2
1
2
e
1
2
3
4
5
u
0
1
0
1
2
0
1
2
3
0
1
2
3
4
0
1
2
3
4
5
2
1
2
e =e -u
1
0
2
1
0
3
2
1
0
4
3
2
1
0
5
4
3
2
1
0
2
1
p2(u )
P*2(e )
0
69
35
0
0
120
35
69
37
0
0
163
35
120
37
69
37
0
0
203
35
163
37
120
37
69
39
0
0
241
35
203
37
163
37
120
39
69
45
0
Таблица 9
2 1
P1(u ,e )
69
35
120
104
37
163
155
106
37
203
198
157
106
39
241
238
200
157
108
45
2
2
2
P*2(e )
69
u (e )
0
120
0
163
0
203
0
241
0
30
Приложение 2. Код программы
#include <vector>
#include <iostream>
#include <iomanip>
#include <future>
using std::cout;
using std::vector;
void printArray(vector<vector<double>>& a)
{
for (int i = 0; i < a.size(); ++i, cout << "\n")
for (int j = 0; j < a[0].size(); ++j, cout << " ")
cout << std::fixed << std::setw(5) << a[i][j];
}
int main()
{
freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
cout.precision(2);
int w, n;
std::cin >> w >> n;
vector<vector<double>> d(n + 1, vector<double>(w + 1, 0)), a(n + 1,
vector<double>(w + 1, 0));
vector<vector<int>> parent(n + 1, vector<int>(w + 1, -1));
vector<int> ans;
for (int i = 1; i <= w; ++i)
for (int j = 1; j <= n; ++j)
std::cin >> d[j][i];
31
//printArray(d);
for (int i = 1; i <= n; ++i)
for (int c = 0; c <= w; ++c)
{
a[i][c] = a[i - 1][c];
for (int k = 0; k <= c; ++k)
if (a[i][c] < a[i - 1][c - k] + d[i][k])
a[i][c] = a[i - 1][c - k] + d[i][k],
parent[i][c] = k;
}
//printArray(a);
std::function<void(int, int)> findans = [&](int k, int s)
{
if (k == 0)
return;
if (parent[k][s] == -1)
findans(k - 1, s),
ans.push_back(0);
else
findans(k - 1, s - parent[k][s]),
ans.push_back(parent[k][s]);
};
findans(n, w);
cout << "Overall profit is " << std::fixed << a[n][w] << "\n";
for (int i = 0; i < n; ++i)
cout << ans[i] << " y. e goes to " << (i + 1) << "-th\n";
return 0;
}
32
Отзывы:
Авторизуйтесь, чтобы оставить отзыв