Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow Информационные технологии в туристской индустрии
Посмотреть оригинал

ТЕХНОЛОГИИ И МЕТОДЫ ОПТИМИЗАЦИИ В ЗАДАЧАХ ТУРИСТСКОЙ ИНДУСТРИИ

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

Линейное программирование

Задача нахождения наибольшего (наименьшего) значения линейной функции, называемой целевой, при линейных ограничениях называется задачей линейного программирования. Задачи линейного программирования имеют большое прикладное значение, так как к ним сводятся многие прикладные задачи, в том числе из сферы туризма. Поэтому для них разработаны специальные методы и программы. Из последних самой популярной и эффективной является надстройка Solver (Поиск решения) программного комплекса MS Excel.

Пример 7.1. В отеле есть 11 четырехместных, 9 двухместных и 5 одноместных свободных номера. Туристическая компания предлагает руководству отеля заключить договор на заселение сроком на 4 дня любого числа двух видов групп. Группе первого вида требуется 3 четырехместных, 1 двухместный и 2 одноместных номера, группе второго вида — 2 четырехместных и 2 двухместных номера. Прибыль от размещения группы первого вида составляет 50 тыс. руб., а от размещения группы второго вида — 40 тыс. руб.

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

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

Технология ее решения в MS Excel:

Оставляя ячейки А1 и А2 за независимыми переменными, в ячейки В1: ВЗ вводим формулы ограничений:

=3*А1+2*А2-11

=А1+2*А2-9

=2*А1-5

В ячейку С4 вводим формулу целевой функции:

=50000*А1 +40000*А2

Командами Данные/Поиск решения открываем одноименное диалоговое окно и задаем сценарий решения (рис. 7.1).

Рис. 7.1

Кнопка «Выполнить» возвращает сообщение, что решение найдено (рис. 7.2), в ячейках А1 и А2 появляются оптимальные значения, в ячейке С4 — оптимальное значение целевой функции.

Рис. 7.2

Рис. 7.3

Из полученных данных следует (рис. 7.3), что надо заселить одну группу первого вида и 4 группы второго вида, максимальная прибыль 210 тыс. руб.

Пример 7.2. Для того чтобы отправиться в путешествие, надо купить авиабилеты, забронировать место в гостинице и купить страховку, что можно сделать в трех туристических фирмах по ценам (в у.е), указанным в табл. 7.1. Желая не рисковать всем, будущий турист решил каждую операцию выполнять только в одной фирме.

Какую минимальную сумму ему придется заплатить?

Таблица 7.1

Стоимость услуг в разных фирмах, у.е.

Фирма I

Фирма II

Фирма III

Авиабилеты

2 500

2 200

2 000

Гостиница

1 000

1 500

1 200

Страховка

900

1000

800

В двоичных переменных х,у, принимающих значения х,у= 1, если /'-я операция выполняется в у-й фирме, и х,у = 0 в противном случае, целевая функция задачи:

где С = (Cjj) — матрица стоимостей из табл. 7.1. Ограничения:

Технология решения этой математической модели:

  • 1) запускаем MS Excel и в диапазон А1:СЗ вводим табличные данные (рис. 7.5);
  • 2) диапазон А5:С7 оставляем за независимыми переменными, для наглядности заливаем его желтым цветом;
  • 3) в ячейку D5 вводим формулу =СУММ(А5:С5) и копируем ее в остальные ячейки диапазона D5:D7;
  • 4) в ячейку А8 вводим формулу =СУММ(А5:А7) и копируем ее в остальные ячейки диапазона А8:С8;
  • 5) в ячейку D8 вводим формулу целевой функции =СУММПРОИЗВ(А1 :СЗ;А5:С7);
  • 6) запускаем надстройку «Поиск решения» и задаем сценарий решения (рис. 7.4).

Рис. 7.4

Команда Выполнить возвращает сообщение, что решение найдено, и результаты (рис. 7.5).

Рис. 7.5

Следовательно, надо авиабилеты покупать в фирме II, бронировать гостиницу в фирме I, а страховку покупать в фирме III, минимальные расходы 4000 дол.

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

Пример 7.3. Найти кратчайший маршрут объезда городов, расстояния между которыми заданы в км в табл. 7.2.

Таблица 7.2

Петербург

Москва

Киев

Баку

Тбилиси

Петербург

0

696

1207

3223

2797

Москва

696

0

858

2527

2101

Киев

1207

858

0

2283

1863

Баку

3223

2527

2283

0

579

Тбилиси

2797

2101

1863

579

0

В двоичных переменных х,у, принимающих значения х,у= 1, если в кратчайший маршрут проходит путь из /-го пункта в у'-й, и х,у = О в противном случае, целевая функция задачи:

где C=(Cjj) — матрица стоимостей из таблицы 7.2, /Уу. Ограничения:

Кроме того, есть ограничения на непрерывность маршрута, для краткости они не выписываются. Технология решения этой математической модели:

  • 1) запускаем MS Excel и в диапазон А1:Е5 вводим табличные данные (рис. 7.8);
  • 2) диапазон А7:Е11 оставляем за независимыми переменными, для наглядности заливаем его желтым цветом;
  • 3) в ячейку F7 вводим формулу =СУММ(А7:Е7) и копируем ее в остальные ячейки диапазона G8:G13;
  • 4) в ячейку А12 вводим формулу =СУММ(А7:А11) и копируем ее в остальные ячейки диапазона А12:Е12;
  • 5) в ячейку F12 вводим формулу целевой функции =СУММПРОИЗВ(А1:Е5; А7:Е11);
  • 6) запускаем надстройку «Поиск решения» и задаем сценарий решения (рис. 7.6);

Рис. 7.6

7) кнопкой «Параметры» открываем диалоговое окно и задаем данные, показанные на рис. 7.7.

Оценки

Разности

Метод поиска

© линейная

© прямые

© Ньютона

О квадратичная

О центральные

О сопряженных градиентов

Рис. 7.7

Команда Выполнить возвращает сообщение, что решение найдено, и результаты, которые нас не устраивают, так как маршрут оказался состоящим из двух контуров 1—2—3—1 и 4—5—4 (рис. 7.8).

Рис. 7.8

1. В ячейку G1 вводим формулу дополнительного ограничения =В7+С8+А9.

В ячейку G2 вводим формулу дополнительного ограничения

=E10+D11.

2. В ограничения (см. рис. 7.6) добавляем условия G2<2 и G2<1, снова запускаем вычисления, которые опять дают маршрут, состоящий из двух контуров 1—2—1 и 3—5—4—3 (рис. 7.9).

Рис. 7.9

3. В ячейку G3 вводим формулу еще одного дополнительного ограничения:

= В7+А8.

4. В диалоговое окно (рис. 7.6) добавляем ограничение G3<1 , тогда запуск вычислений приводит к оптимальному маршруту 1—2—5—4—3—1 (рис. 7.10).

Рис. 7.10

Минимальная длина маршрута 6866 км.

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

 
Посмотреть оригинал
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

Популярные страницы