Фролова Анна Александровна. Выпускная квалификационная работа бакалавра. Построение и анализ математической модели функционирования гостиничного комплекса.


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.
С
АНКТ
-
П
ЕТЕРБУРГСКИЙ ГОСУДАР
СТВЕННЫЙ УНИВЕРСИТЕТ

К
АФЕДРА
МОДЕЛИРОВАНИЯ СОЦИАЛ
ЬНО
-
ЭКОНОМИЧЕСКИХ СИСТЕМ





Фролова Анна Александровна


Выпускная квалификационная работа бакалавра



Построение

и анализ математической модели
функционирования гостиничного комплекса

Направление
010400

Прикладная математика и информатика


Научный руководитель,

доктор физ.
-
мат. наук,

профессор

Малафеев О.А.







Санкт
-
Петербург

201
6

2


Содержание

Введение

................................
................................
................................
.........

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


3


Введение

В современном мире гостиничная сфера
достаточно быстро
развивается. В каждой стране туризм и гостиничный бизнес является одним
из способов увеличения ВВП. Существует множество крупных сетей отелей,
которые расположены по всему миру, например:
Park

inn
,
Marriott
,
Holiday

inn
,
Kempinski

и други
е.

Сеть отелей представляет собой множество средств размещения.
Средства размещения


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

Д
ля каждого владельца отдельного средства размещения или
гостиничной сети в целом важно увеличение прибыли, которое будет
достигнуто увеличением потока клиентов и улучшением качества услуг.
Туристы, выбирая отель, опираются на множественные факторы, наприме
р:
реклама отеля, состояние номерного фонда, соотношение ©цена
-
качествоª и
пр. Конечно, все гостиничные
сети отелей выглядят по
-
разному, по своему
функционируют, имеют разные преимущества и недостатки, но каждый
директор стремится довести свою гостиничную
сеть или отдельный объект
размещения до идеального состояния.

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

Так как модернизация в каждой гостиничной сети требуется постоянн
о
,

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

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

4


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

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

Эта работа направлена на

автоматизаци
ю

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

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

в целом.

5


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

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

Рассматривается модель оптимального распределения ресурсов

или
инвестиций

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

Задача в данной работе состоит из двух частей. Первая часть
заключается в
изучении

метода

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



6


Обзор литературы

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

Определения из теории игр рассматриваются на основе книг Петросяна
Л.А.

[12, 15].

Так же рассмотрено много книг по математическому моделированию
[4,5,7,8,9,10]
.


Принципы и условия оптимальности

описаны в книгах
[3, 9, 13]

В ходе работы рассматривались методы динамического
программирования, рассмотренные в книгах
[
2, 6, 10
]
.

Программа, реализованная в ходе работы, написана на зыке
C
++,
алгоритмы и правила работы на котором описаны в книгах
[1, 14].

7


Глава 1
.

Формализованная постановка задачи
распределения ресурсов по гостинично
му

комплексу
, состояще
му

из n объектов размещения

1.1

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

Пусть I  1, «, n


множество
объектов размещения
. Предполагаем,
что состояние кажд
ого объекта размещения

данно
го

гостинично
го

ко
мплекса

может быть описано одним числовым параметром. Пусть Z
0
i



начальное
количественное состояние
объекта размещения

i. Предполагается заданным
перспективный план развития всех
объектов размещения

данно
го

комплекса

Z


= (
Z

1
, «,
Z

i
, «,
Z

n
)
, определенный на конец некоторого периода
планирования. В плане
Z



компонента
Z

i

означает планируемое
количественное состояние развития
объекта размещения

i. Предполагается,
что на основе плана
Z


= (
Z

1
, «,
Z

i
, «,
Z

n
)

могут быть определены
оптимальны
е состояния всех
объектов размещения

данно
го

комплекса
.

Будем обозначать индексами 1, «, j, «, 
i
}

вектор,
характеризующий состояние объекта размещения

i; 1, «, , «, l
j
}


компоненты j
-
вектора
объекта размещения

i
. Предполагаем, что состояние
каждого
вектора

и
компонент

может быть охарактеризовано одним главным
параметром. Пусть Z
0
ij



начальное количественное состояние вектора j,
обслуживающего
объект размещения

i.
Z

i

= (
Z

i
1
, «,
Z

ij
, «,
Z

imi
)
,

i = 1
, ..,
n

заданный перспективный план
для всех векто
ров
, определенный на конец
того же периода, на который определен перспективный план
объекта
размещения гостинично
го

комплекса
.


Должно выполняться равенство:




పఫ


















(1)

8



Пусть теперь Z
0
ijm


начальное количественное
значение компоненты

m,
соответствующей вектору

j
объекта размещения

i. Предполагается заданным
значение для всех компонент
Z

ij

= (
Z

ij
1
, «,
Z

ijm
, «,
Z

ijn
)
, i =

1,

..
,
n, j = 1,

..,

m,
определенн
ое

на конец периода планирования, т.е. того же периода, на
который определены перспективные планы
z

и
Z

i
, i 1,n по
объектам
размещения

и
векторам
. Очевидно, должно выполняться равенство:

























Обозначим через U
i
t) инвестиции, вкладываемые в
объект размещения
i, i  1,n, в год t, t
ϵ

 , 1, «, T
-
1. Предполагается заданная функция С t),
представляющая собой сумму капиталовложений, вкладываемых в
капитальное строительство в год t. Пусть далее U
ij
(t)


капитальные
вложения, вкладываемые в
объект размещения
, j=1,

..,
m
i

вектора

i в год t;
U
ijm
(t)

капитальные вложения,
характеризующие

компоненту
j
объекта
размещения

i в год t.

Должно выполняться:

























































(3)

U
i
t)≥ ; U
ij
t)≥ ; U
ijm
t)≥ ; i1,

..,
n; j=1,

..,
m
i
; m=1,

..,
l
j
.

Зная начальное и планируемое на конец периода состояние
объектов
размещения
,
векторов

и
компонент

и ежегодные капитальные вложения в
ст
роительство, и ремонт
объектов размещения
, можно определить для них
распределение капитальных вложений, удовлетворяющее 3) во все моменты
времени t
ϵ
 , 1, «, T
-
1 и обеспечивающее их одновременный перевод из
заданных начальных состояний в планируемое на
конец периода T при
выполнении определенных требований оптимальности и баланса ресурсов.
Таким требованием
на данном этапе

рассматриваемой
задач
и, например,

будет служить требование максимального сглаживания диспропорций между
9


объектами размещения

данно
го

гостинично
го

комплекса
.
[4]

1.2
О
порный план развития объектов размещения
гостиничного комплекса

Рассмотрим ситуацию, в которой на всех уровнях планирования
развитие осуществляется пропорционально вкладываемому капиталу, т.е.
если:

¨Z
i
(t) = Z
i
(t+1)


Z
i
t); ¨Z
ij
(t) = Z
ij
(t+1)

Z
ij
t); ¨Z
ijm
(t) = Z
ijm
(t+1)

Z
ijm
(t),

через Z
i
(t), Z
ij
(t), Z
ijm
t) обозначены соответственно количественные
состояния
объектов размещения
,
векторов

и
компонент

в год t

ϵ

 , 1, «, T
-
1},


тогда

¨Z
i
(t)*S
i
=U
i
t); ¨Z
ij
(t)*S
ij
=U
ij
(t);

¨Z
ijm
(t)*S
ijm
=U
ijm
(t).

Величины S
i
, S
ij
, S
ijm



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

Одним из планов капитального развития, переводящим
объекты
размещения

из состояния Z
0

в планируемое
Z

, является опорный план
распределения капитальных вложений, который позволяет одновременно
перевести все
объекты размещения

из Z
0

в
Z


и в какой
-
то степени
ликвидирует диспропорции между ними.

Определим опорный план развития
объектов размещения гостинично
г
о

комплекса
.

Если доля средств, вкладываемых в кажд
ый

объект размещения
, из
года в год не изменяется, то развитие от начального состояния Z
0

к заданному
конечному
Z


будет происходить, лишь при условии, если для это
го

объекта
размещения

будет выделяться в
каждый год t сумма:






































ି












ି

























(4)













-

капиталоемкость
объекта размещения

i
;



















-

сумма инвестиций, необходимая для всех объектов
10


размещения
;

Ясно, что














Должно выполняться, так как сумма инвестиций, вкладываемых во все
объекты размещения, должна быть равна заданной ранее функции
C
(
t
).

Таким образом, коэффициент при С
t) в выражении 4) означает долю
средств, необходимых для развития

объектов размещения гостиничной
структуры
.

Построим теперь опорный план распределения капитальных вложений
на всех уровнях иерархической системы

управления развитием
инвестируемых объектов
размещения
.

Для
векторов
:



при


Для
компонент
:


при


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

в данном изолированном
комплексе

равновесия.

11


При подобном планировании обычно определяют некотор
ые основные
показатели для основных
объектов размещения
)

Z


= (
Z

1
, «,
Z

i
, «,
Z

n
)
, к
которым должно стремиться развитие гостинично
го

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

В связи с тем, что для не
большого
гостиничного

комплекса

удельные
затраты на развитие 1/S можно считать постоянными, для простоты мы
будем строить одноуровневую модель.

Пусть
Z
0
-

начальное состояние тех основных
объектов размещения
, по
которым заданы показатели в перспективном пл
ане развития
.

Система
модернизации

ежегодно для своего разв
ития получает
некоторый капитал

С t). 1/S



удельные затраты для каждо
го

объекта
размещения

также известны. Построим опорный план развития данной
системы:






По заданному опорному плану рассчитываем ресурсы, требуемые для
ее развития.

Пусть кроме основных
объектов размещения

существуют еще и
вспомогательные. Выделяя некую долю

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

комплекса
:






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

Пусть

-

количество ресурса типа k, имеющегося в наличии в год t,
12


который может быть использован на развитие;

-

количество ресурса типа
k, необходимое для развития
объекта размещения

i на единицу;

-

количественный рост j
-
то
го

вспомогательно
го

объекта размещения

при росте
объекта размещения

i на единицу; 1/

-

удельные капитальные вложения,
необходимые для роста вклада j
-
то
го

вспомогательно
го

объекта размещения
;

-

количество ресурса типа k, необходимое для развития вспомогательно
го

объекта размещения

j на 1 единицу;

-

капитальные вложения,
направленные на развитие
объекта размещения
, производящей ресурс типа k
в год t;

-

удельные капитальные вложения, необходимые для роста
производства ресурсов на единицу;

-

капитальные вложения,
направленные на развитие j
-
то
го

вспомогательно
го

объекта размещения

в год
t;

-

количеств
енное состояние j
-
то
го

вспомогательно
го

объекта
размещения

в год t.

Известно, что наибольшая скорость движения из состояния
в


при
выделении на развитие основных
объектов размещения

капитальные
вложения
, где

при условии:





Или, что тоже самое: x

при условии:





13


Решение данной задачи даст нам опорный план развития для основных
объектов размещения
:

капитальные вложения
на развитие
производства
объектов размещения

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

Пусть

-

количественное состояние ресурса типа k в год t,

-

количественное состояние
объекта размещения

j. После освоения
капитальных

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

Пусть Т


момент достижения
объектами

размещения

планируемого
состояния
; величины

задают ограничения на ресурсы данно
го

гостинично
го

комплекса
; начальное состояние

называется допустимым,
если не существует такого

и такого индекса
, что


Предполагаемая методика определения допустимости перспективных
проектов
развития объектов размещения
позволяет сравнивать различные
планы с точки зр
ения их влияния на существующее
равновесие в
гостиничном комплексе

и восстанавливать его, если оно нарушено.
[7]

14


Глава 2
.

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

Для принятия решений в различных ситуациях существует множество
принципов оптимальности, таких как, например, в
ектор Шепли, равновесие
по Нэшу, оптимальное решение по Парето.
[8,12]

В ходе данной работы,
рассматриваются лишь два принципа оптимальности, таких как
компромиссное множество и принцип оптимальности Беллмана.

Рассмотрим
и дадим понятия этих принципов оптим
альности
.

2.1
Компромисс


Дадим о
пределение компромиссного множества
. Будем рассматривать

следующ
ую

игр
у

Γ
, которая описывается множеством
игроков I, с
элементами i

I.

Множество игроков конечно. Каждый из игроков имеет множество
стратегий. Обозначим множество стратегий i
-
го игрока xi

Множество
всех возможных
ситуаций в игре это произведение








И
для каждого
игрока

i

определена функция дохода Нi: Х
-
�R1

Посчитаем невязк
и :












.

После того, как посчитали невязки для каждого игрока, можем
построить
идеальный вектор M M
1
«M
n
)
.

Далее имеем






















Это и будет компромиссным множеством.
[
10,
15]

Если рассматривать это определение в контексте данной работы то
можно сформулировать его так. Рассматривается гостиничный комплекс с
множеством владельцев различных объектов размещения данного комплекса.
У каждого владельца своя функция дохода от траектори
и развития
15


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


2.
2

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

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

как на данном шаге, так и на всех
последующих шагах. Следовательно, оптимальную стратегию мы можем
получить двигаясь
от конца к началу, т.е. начинаем поиск стратегии с
последнего
n
-
го

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





ି






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

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

Опишем теперь данный принцип оптимальности математически.

Пусть








− максим
альный доход, получаемый за

n

шагов при
переходе системы

из начального состояния




в конечное состояние




при
реализации оптимальной стратегии управления

u
*=(
u1
*,
u2
*,
«
,
un
*)

а








-

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




в конечное состояние




при оптимальной стратегии
16


управления на оставшихся

n
-
k

шагах. Тогда

























































































при

k
=1,

«, n.


Это и есть основное функциональное уравнение Беллмана.
[
3,
12
]

17


Глава 3
.

Практическ
ая часть

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

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

3.1 Численное решение задачи

Рассмотрим задачу о выделении
m

средств, которые должны быть
распределены между
n

объектами размещения

гостиничного комплекса
.

Для наглядности возьмем параметры равные
m

= 5
,
n

= 10.
Итак,
рассмотрим оптимальный план распределения 5
тыс
. денежных единиц
между десятью
объектами размещения
.


Рассмотрим исходные данные, приведенные в таблице 1.

Кол
-
во денежных
единиц

Получение общей прибыли денежных единиц

X

p
1
(x)

p
2
(x)

p
3
(x)

p
4
(x)

p
5
(x)

p
6
(x)

p
7
(x)

p
8
(x)

p
9
(x)

p
10
(x)

1

47

35

22

25

40

43

37

38

51

69

2

48

3
7

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)
, в этом случае ищем максимальный
доход по таблице.
Очевидно, что он равен 3.

На каждом дальнейшем шаге, будем строить таблицу, в которой первые
столбцы это
вложенные средства
(
e
i
-
1
)
, 2


проект

(
u
i
)
, 3


остаток средств
(
e
i

=
e
i
-
1
-
u
i
, 4


по исходным данным, о функциях дохода
(
p
i
(
u
i
))
, 5


седьмой
столбец предыдущей таблицы, 6


сумма значений 4
-
го и 5
-
го столбца,


18


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


распределение инвестиций из второго столбца, на
котором достигается максимум в седьмом столбце.

2) На втором шаге будем распределять инвестиции ме
жду 9 и 1
объектами размещения

(
i

= 9).

Проделав все действия, п
олучаем таблицу 2.

При этом рекуррентное соотношение
по принципу оптимальности
Беллмана
, который мы рассматривали

в п.2.2

имеет вид:





































e
8

u
9

e
9
=e
8
-
u
9

p
9
(u
9
)

P*
9
(e
8
)

P
8
(u
9
,e
8
)

P*
9
(e9)

u
9

(e
9
)

1

0

1

0

69

69

69

0


1

0

51

0

51

2

0

2

0

7
1

71

1
20

1


1

1

51

69

12
0


2

0

53

0

53

3

0

3

0

7
2

72

1
2
2

1


1

2

51

7
1

12
2


2

1

53

69

1
22


3

0

55

0

55

4

0

4

0

7
5

75

1
24

2


1

3

51

7
2

12
3


2

2

53

7
1

124


3

1

55

69

1
24


4

0

57

0

57

5

0

5

0

83

83

1
26

1


1

4

51

7
5

12
6


2

3

53

7
2

1
25


3

2

55

7
1

1
26


4

1

57

69

1
26


5

0

78

0

78

Таблица 2


3)На третьем шаге распределяем инвестиции между ,9,1 объектами
размещения i ).
Проделав все действия, получаем таблицу 3
.

При этом рекуррентное соотношение

по принципу оптимальности Беллмана

имеет аналогичный вид что и на предыдущем шаге.


e
7

u
8

e
8
=
e
7
-
u
8

p
8
(u
8
)

P*
8
(e
7
)

P
7
(u
8
,e
7
)

P*
8
(e
8
)

u
8

(e
8
)

1

0

1

0

69

69

69

0


1

0

38

0

38

2

0

2

0

1
20

120

120

0


1

1

38

69

1
07

19



2

0

39

0

39

3

0

3

0

1
2
2

122

158

1


1

2

38

1
20

1
58


2

1

39

69

1
08


3

0

64

0

64

4

0

4

0

1
24

124

160

1


1

3

38

1
2
2

1
6
0


2

2

39

1
20

1
59


3

1

64

69

133


4

0

65

0

65

5

0

5

0

1
26

126

184

3


1

4

38

1
24

162


2

3

39

1
2
2

1
6
1


3

2

64

1
20

184


4

1

65

69

134


5

0

7
2

0

7
2

Таблица 3

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

10)
Определяем оптимальную стратегию при распределении дене
жных
средств между объектами размещения

1, 2, 3, 4, 5, 6, 7
, 8, 9, 10.
Проделав все
действия, получаем таблицу
10
.

e
0

u
1

e
1
=
e
0
-
u
1

P
1
(u
1
)

P*
1
(e
0
)

P
0
(u
1
,e
0
)

P*
1
(e
1
)

u
1

(e
1
)

1

0

1

0

69

69

69

0


1

0

47

0

47

2

0

2

0

120

120

120

0


1

1

47

69

116


2

0

48

0

48

3

0

3

0

163

163

167

1


1

2

47

120

167


2

1

48

69

117


3

0

49

0

49

4

0

4

0

203

203

210

1


1

3

47

163

210


2

2

48

120

168


3

1

49

69

118


4

0

50

0

50

5

0

5

0

241

241

250

1


1

4

47

203

250


2

3

48

163

211


3

2

49

120

169


4

1

50

69

119


5

0

55

0

55

Таблица
10

Просмотрев в обратном порядке все таблицы, по аналогии,
получаем,

20


что оптимальный план распределения инвестиций
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
≤k≤
с). Тогда, при вложении
c

д.е. в первые i

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

д.е. в i
-
ое
и c
-
k в предыдущие i
-
1

предприятия. Таким образом
,

ответ задачи
получ
ается, когда мы вкладываем все W

д.е. во все n

предприятий
.

21


3.2.2 Пример работы программы

В качестве примера работы программы, в
озьмем исходные данные
задачи, решенной в
п.
3.1.

Благодаря этому проверим правильность работы
программы.

В первую строку вводим
W



количество инвестируемых средств,
n



количество объектов размещения.

Далее вводим данные из таблицы 1.


Рисунок 1

На рисунке 1
представлен пример входных данных, в файле
input
.
txt
.

Запустив программу, посмотрим на результат, полученный в файле
output
.
txt
. Отобразим его на рисунке 2
.

22



Рисунок 2

Таким образом, видим, что получили те же результаты, что и ранее.

Так же
можем в процессе решения данной задачи вывести в файл
промежуточные расчеты, соответствующие алгоритму, рассказанному в 3.2.1

Получаем результаты, представленные на рисунке 3
.


Рисунок 3

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

23


3.2.3 Плюсы и минусы программы и ее возможные
доработки

Д
анный алгоритм работает за O
n

W
2
) времени и O n

W) памяти, что
является оптимальным для этой задачи. Однако,

если мы хотим только
посчитать суммарную прибыль, расход памяти можно уменьшить

до O W)
.

Минус данной программы состоит в громоздких входных данных,
которые должны содержаться в файле.

24


Выводы

1. Построена и рассмотрена модель распределения ресурсов по
г
остиничному комплексу, состоящему из
n

объектов размещения

2. Решен целочисленный пример распределения инвестиций между
десятью объектами размещения

3. Реализована программа, решающая данную задачу в общем случае

не только для целых чисел.

25


Заключение

В
ходе выполнения данной работы были изучены многочисленные
источники, в таких сферах как ©Динамическое программированиеª

[2, 6, 10]

и ©Экономическая оптимизацияª

[3, 9, 1
3
]
.
Были углублены знания в
принципы оптимальности и моделирование экономических процес
сов.

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

и

описаны
принципы оптимальности, используемые при решении целочисленного
примера.

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

26


Список литературы

1.

Бьерн Страуструп, Язык программирования С
, Изд
-
во Бином, 2 11,
1136 с.

2.

Беллман Р., Калаба Р., Динамическое программирование и современная
теория управления, М.: Изд
-
во Иностранная

литература, 196 , 4 с.

3.

Зенкевич

Н.А., Петросян Л.А.
,

Оптимальный поиск в условиях
конфликта. Л., ЛГУ, 19 г, 5

с.

4.

Зубов В.И., Петросян Л.А. Математические методы в планировании,
Ленинград, 19 2, 112 с.

5.

Колокольц
е
в В.Н., Малафеев О.А. Динамические конку
рентные
системы многоагентного взаимодействия и их асимптотическое
поведение часть I), Вестник гражданских инженеров. 2 1 . № 4. С.
144
-
153.

6.

Лежнев А.В., Динамическое программирование в экономических
задачах, М.: 2 1 .
-
1 6 с.

7.

Малафеев О.А., Дроздов Г.Д. Мо
делирование процессов в системе
управления городским строительством, Санкт
-
Петербург, Том 1, 2 1,
401 c.

8.

Малафеев О.А., Зубова А.Ф. Математическое и компьютерное
моделирование социально
-
экономических систем на уровне
многоагентного взаимодействия введен
ие в проблемы равновесия,
устойчивости, надежности), Санкт
-
Петербург, 2 6, 1 6 c.

9.

Малафеев О.А., Пахар О.В. Динамическая нестационарная задача
инвестирования проектов в условиях конкуренции, Проблемы
механики и управления: Нелинейные динамические систем
ы. 2 9. №
41. С. 1 3
-
108.

10.

Парфенов А.П., Малафеев О.А. Равновесие и компромиссное
управление в сетевых моделях многоагентного взаимодействия,
Проблемы механики и управления: Нелинейные динамические
27


системы. 2 . № 39. С. 154
-
167.

11.

Петросян

Л.А., Захаров

В
.В.

Введение в математическую экологию. Л.,
ЛГУ, 222

с.

12.

Петросян Л.А., Зенкевич Н.А., Шевкопляс Е.В.

Теория игр.


Санкт
-
Петербург: БХВ


Петербург, 2 12.


4 С.

13.

Печерский С.Л., Соболев А.И.

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

Л.: Наука,
1983.
-

1 6 с.

14.

Scott Meyers, ©Effective Modern Cª, 2 16, 3 4
с

15.

Malafeev O.A., Kolokoltsov V.N. Understanding game theory, New Jersey,
2010,286.

16.

Ссылка на онлайн компилятор программы, реализованной в данной
работе
:

http://cpp.sh/6iw5w


28


Приложение
1
.
Данные решения примера

4)
I

= 7

e
6

u
7

e
7
=
e
6
-
u
7

P
7
(u
7
)

P*
7
(e
6
)

P
6
(u
7
,e
6
)

P*
7
(e
7
)

u
7

(e
7
)

1

0

1

0

69

69

69

0


1

0

37

0

37

2

0

2

0

120

120

120

0


1

1

37

69

106


2

0

39

0

39

3

0

3

0

158

158

158

0


1

2

37

120

157


2

1

39

69

108


3

0

51

0

51

4

0

4

0

160

160

195

1


1

3

37

158

195


2

2

39

120

159


3

1

51

69

120


4

0

54

0

54

5

0

5

0

184

184

197

1


1

4

37

160

197


2

3

39

158

197


3

2

51

120

171


4

1

54

69

123


5

0

67

0

67

Таблица
4


5)
i

= 6.

e
5

u
6

e
6
=
e
5
-
u
6

P
6
(u
6
)

P*
6
(e
5
)

P
5
(u
6
,e
5
)

P*
6
(e
6
)

u
6

(e
6
)

1

0

1

0

69

69

69

0


1

0

43

0

43

2

0

2

0

120

120

120

0


1

1

43

69

112


2

0

46

0

46

3

0

3

0

158

158

163

1


1

2

43

120

163


2

1

46

69

115


3

0

48

0

48

4

0

4

0

195

195

201

1


1

3

43

158

201


2

2

46

120

166


3

1

48

69

117


4

0

5
2

0

5
2

5

0

5

0

197

197

238

1


1

4

43

195

238


2

3

46

158

204


3

2

48

120

168


4

1

5
2

69

121


5

0

6
1

0

6
1

29


Таблица
5



6)
I = 5

e
4

u
5

e
5
=
e
4
-
u
5

p
5
(u
5
)

P*
5
(e
4
)

P
4
(u
5
,e
4
)

P*
5
(e
5
)

u
5

(e
5
)

1

0

1

0

69

69

69

0


1

0

4
0

0

4
0

2

0

2

0

120

120

120

0


1

1

4
0

69

109


2

0

42

0

42

3

0

3

0

163

163

163

0


1

2

4
0

120

160


2

1

42

69

111


3

0

4
5

0

4
5

4

0

4

0

201

201

203

1


1

3

4
0

163

203


2

2

42

120

162


3

1

4
5

69

114


4

0

46

0

46

5

0

5

0

238

238

241

1


1

4

4
0

201

241


2

3

42

163

205


3

2

4
5

120

165


4

1

46

69

115


5

0

54

0

54

Таблица
6


7)
I = 4

e
3

u
4

e
4
=
e
3
-
u
4

p
4
(u
4
)

P*
4
(e
3
)

P
3
(u
4
,e
3
)

P*
4
(e
4
)

u
4

(e
4
)

1

0

1

0

69

69

69

0


1

0

25

0

25

2

0

2

0

120

120

120

0


1

1

25

69

94


2

0

2
7

0

2
7

3

0

3

0

163

163

163

0


1

2

25

120

145


2

1

2
7

69

96


3

0

29

0

29

4

0

4

0

203

203

203

0


1

3

25

163

188


2

2

2
7

120

147


3

1

29

69

98


4

0

33

0

33

5

0

5

0

241

241

241

0


1

4

25

203

228


2

3

2
7

163

190


3

2

29

120

149


4

1

33

69

102


5

0

38

0

38

Таблица
7

30



8)
I =
3

e
2

u
3

e
3
=
e
2
-
u
3

p
3
(u
3
)

P*
3
(e
2
)

P
2
(u
3
,e
2
)

P*
3
(e
3
)

u
3

(e
3
)

1

0

1

0

69

69

69

0


1

0

22

0

22

2

0

2

0

120

120

120

0


1

1

22

69

91


2

0

34

0

34

3

0

3

0

163

163

163

0


1

2

22

120

142


2

1

34

69

103


3

0

41

0

41

4

0

4

0

203

203

203

0


1

3

22

163

185


2

2

34

120

154


3

1

41

69

110


4

0

42

0

42

5

0

5

0

241

241

241

0


1

4

22

203

225


2

3

34

163

197


3

2

41

120

161


4

1

42

69

111


5

0

57

0

57

Таблица
8

9)
I =
2

e
1

u
2

e
2
=
e
1
-
u
2

p
2
(u
2
)

P*
2
(e
1
)

P
1
(u
2
,e
1
)

P*
2
(e
2
)

u
2

(e
2
)

1

0

1

0

69

69

69

0


1

0

35

0

35

2

0

2

0

120

120

120

0


1

1

35

69

104


2

0

3
7

0

3
7

3

0

3

0

163

163

163

0


1

2

35

120

155


2

1

3
7

69

106


3

0

37

0

37

4

0

4

0

203

203

203

0


1

3

35

163

198


2

2

3
7

120

157


3

1

37

69

106


4

0

39

0

39

5

0

5

0

241

241

241

0


1

4

35

203

238


2

3

3
7

163

200


3

2

37

120

157


4

1

39

69

108


5

0

45

0

45

Таблица
9

31


Приложение
2
.
Код программы

#include vectov-;㻈&#xt4o-;r00;r

#include iostreami4;&#xo-3s;t-3;&#xream;ᘀ

#include iomanipi4;&#xo-3m;źn;&#x-4i-;p-3;

#include futur༐u;t-3;&#xu-3r;踀e

using std::cout;

using std::vector;


void printArray(vectorvectordouble-3;&#xo4u4; -3l;&#x-3e8;-3;&#xo4u4; -3l;&#x-3e8;& 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;


s
td::cin�� w�� n;


vectorvectordoubleÔo4;&#xu4b-;l-3;Ôo4;&#xu4b-;l-3; d(n + 1, vectordouble-3;&#xo4u4; -3l;&#x-3e8;(w + 1, 0)), a(n + 1,
vectordoublÔo4;&#xu-3b;l-3;e(w + 1, 0));


vectorvectorint&#xi4n4;&#xt-30;&#xi4n4;&#xt-30; parent(n + 1, vectorint&#xi-3n;t-3;(w + 1,
-
1));


vectorinti-3;&#xn4t-;  ans;


for (int i = 1; i = w; ++i)


for (int j =
1; j = n; ++j)


std::cin� � d[j][i];

32



//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::functionvoid(int, int)&#xv4o4;&#xi-3d;&#x-38i;&#x-3n4;&#xt-3,;&#x 4i4;&#xn-3t;&#x-380; findans = [&](int k, int s)


{


if (k == 0)


r


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 i
s " std::fixed a[n][w] "
\
n";


for (int i = 0; i n; ++i)


cout ans[i] " y. e goes to " (i + 1) "
-
th
\
n";



}


Приложенные файлы

  • pdf 10917879
    Размер файла: 930 kB Загрузок: 0

Добавить комментарий