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

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

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

Объект исследования: рассматривается модель распределения инвестиций по объектам размещения для функционирования гостиничного комплекса. В дипломную работу входит: введение, три главы, приложение, выводы и заключение. Во введении раскрывается актуальность исследования по выбранному направлению, ставятся задачи, определяются объекты, указывается значимость данной работы. В первой главе проанализирована формализованная постановка задачи распределения инвестиций по гостиничному комплексу, состоящему из n объектов размещения, построена и рассмотрена математическая модель. В главе 2 рассмотрено компромиссное множество, принцип оптимальности Беллмана. В главе 3 приведён целочисленный пример распределения капиталовложений по принципу оптимальности Беллмана, так же представлен пример работы программы и описание ее алгоритма. В приложении представлена программа нахождения оптимального распределения капиталовложений с целью получения наибольшей прибыли, написанная на языке C++. Так же представлены дополнительные расчеты численного примера, пропущенные в главе 3. Заключение посвящено выводам о проделанной работе и полученным результатам. Список литературы: 16 библиогр. назв.

Общественные науки в целом

Дипломы

Вуз: Санкт-Петербургский государственный университет (СПбГУ)

ID: 587d36645f1be77c40d58e5a

UUID: d2b880f0-13cc-4d5f-a32b-5abf92203801

Язык: Русский

Опубликовано: почти 8 лет назад

Просмотры: 10

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

Источник: Санкт-Петербургский государственный университет

Комментировать 0

Рецензировать 0

Скачать - 952236 bytes

Поделиться работой

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ КАФЕДРА МОДЕЛИРОВАНИЯ СОЦИАЛЬНО-ЭКОНОМИЧЕСКИХ СИСТЕМ Фролова Анна Александровна Выпускная квалификационная работа бакалавра Построение и анализ математической модели функционирования гостиничного комплекса Направление 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

Рецензии:

Авторизуйтесь, чтобы добавить рецензию

- у работы пока нет рецензий -

Отзывы:

Авторизуйтесь, чтобы оставить отзыв