Задача оптимизации туристических групп Поиск решения и сценарии. Транспортная задача - davaiknam.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Задача №1 Производственная задача 14 Задача №4 Задача о распределении... 9 799.25kb.
Задача о назначении работ 6 Транспортная задача 9 Составление опорного... 1 344.23kb.
Транспортная задача 1 35.37kb.
Дискретное программирование 1 49.85kb.
Задача безусловной оптимизации имеет вид: (1) 1 174.22kb.
Задача нахождения наибольшей общей подпоследовательности 1 60.02kb.
Задача интегрирования дифференциального уравнения. Задача Коши. 1 38.57kb.
Задача Математическая модель оптимизации выпуска продукции 3 345.13kb.
Iv. Численные методы решения обыкновенных дифференциальных уравнений. 1 78.09kb.
Задача рентабельности затрат на производство изделий:. Задача рентабельности... 1 29.32kb.
Задача оптимизации. Задачи дискретной оптимизации Сведение задачи... 1 12.07kb.
Решение задач оптимизации методом 1 50.08kb.
Направления изучения представлений о справедливости 1 202.17kb.

Задача оптимизации туристических групп Поиск решения и сценарии. Транспортная задача - страница №1/1



Содержание

Задачи оптимизации со многими неизвестными


Задача оптимизации туристических групп

Поиск решения и сценарии. Транспортная задача


Задачи оптимизации со многими неизвестными

Для численного решения уравнений со многими неизвестными и ограничениями в Excel включен инструмент Поиск решения.



По умолчанию инструмент не установлен и его следует установить: вставьте дистрибутивный CD-диск и выберите в списке надстроек СервисНадстройки… соответствующий флажок.
Если целевая функция и ограничения линейны, то решение состоит в нахождении множества чисел (х1, х2, … хn), минимизирующих (максимизирующих) линейную целевую функцию f(х1, х2, … хn)= c1х1+c2х2+… +cnхn при mi1х1i2х2+… +аinхn (где i=1,2, … m) и n линейных ограничениях-неравенствах хk>=0 (где k=1, 2, … n). Инструмент Поиск решения обеспечивает максимум 200 изменяемых ячеек хi при поиске решения (nмах=200).

В качестве первого содержательного примера используем предыдущую задачу о комбинезонах, несколько усложнив ее. Расход тканей на единицу каждого комбинезона показан на рис. 2.33 (раздел Решение систем линейных уравнений с помощью матриц). Стоимость пошива комбинезона типа К1 равна 100 руб., К2 – 120 руб., К3 – 110 руб. Дневной запас тканей в ателье следующий: ткани Т1 – 50м, ткани Т2 – 80м, ткани Т3 – 25м, ткани Т4 – 60м. Сколько комбинезонов каждого типа надо производить в день, чтобы получить максимальную стоимость производства? При этом использовать все типы тканей.

Переложим условие задачи на язык формул, т.е. опишем математическую оптимизируемую модель. В процессе решения надо найти дневной выпуск х1, х2 и х3 каждого комбинезона, такой, чтобы получить максимум целевой функции 100х1+120х2+110х3 при ограничениях
х1 + 2х2 + х3 <= 50

1 + 1.5х2 + 3х3 <= 80

0.5х1 + х2 + 0.5х3 <= 25

1 + х2 + 0.5х3 <= 60


Кроме того, количество комбинезонов не может быть дробным и отрицательным, поэтому добавляются ограничения: (х1, х2, х3) >= 0 и (х1, х2, х3) – целые числа.

Теперь введем условие задачи в Excel, как показано ниже:



Как видно в ячейку Н3 введена формула =$B$9*B3+$C$9*C3+$D$9*D3, которая размножена на Н4:Н6. В ячейку F9 введена формула целевой функции =100*B9+120*C9+110*D9. В ячейках В9:D9 будет производиться подбор значения – здесь введены начальные значения хi.

Далее вызываем инструмент СервисПоиск решения…, вводим адреса подготовленных ячеек и ограничения (как на рис. 2.39) и нажимаем кнопку Выполнить.


Рис. 2.39


Заполнение окна Поиск решения не вызывает трудностей. Ограничения добавляются кнопкой Добавить; при этом появляется окно ввода ограничения:

Результат вычислений показан на рис. 2.40:

Рис. 2.40


Как видно, оптимальный дневной выпуск комбинезонов равен 13, 12 и 12. При этом в колонке Н видно, что часть тканей остается неизрасходованной.

Поэкспериментируйте: попробуйте вручную изменить подобранные значения (например, х1=14), оцените значения целевой функции и ячеек Н3:Н6. Повторно вызовите инструмент Поиск решения, удалите условие ($B$9:$D$9 = целое) и выполните подбор: результат совпадет с результатом задачи о комбинезонах из раздела Решение систем линейных уравнений.


Обобщим проделанную работу и выделим этапы решения задачи оптимизации со многими неизвестными в Excel с помощью инструмента Поиск решения:

  • анализ задачи, выделение свойств, параметров, ограничений;

  • математическое описание оптимизируемой модели – введение обозначений, ограничений и создание целевой функции;

  • грамотное размещение модели и поиск решения в Excel.

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

Задача оптимизации туристических групп
В качестве второго содержательного примера рассмотрим задачу формирования экскурсионных пакетов. Российская туристическая фирма ежедневно отправляет в три отеля Анталии, Кемера и Мармариса (Турция) соответственно 30, 20 и 16 человек. Экскурсионная программа каждой группы состоит из рафтинга (спуск по горной реке на плоту), яхт-тура вдоль побережья и путешествия джип-сафари в турецкую глубинку. Стоимость экскурсий с трансфером на человека для отелей разных городов следующая:





Рафтинг

Яхт-тур

Джип-сафари

Анталия

55

20

35

Кемер

65

35

20

Мармарис

60

25

25

При этом существуют ограничения на количество человек в экскурсии: рафтинг – 25 чел., яхт-тур – 20 чел., джип-сафари – 30 чел. От каждого отеля на каждую экскурсию должно быть послано не менее 5 чел.

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

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







Рафтинг

Яхт-тур

Джип-сафари

Анталия

х1

х2

х3

Кемер

х4

х5

х6

Мармарис

х7

х8

х9

Целевая функция (стоимость), которую следует минимизировать, запишется так:


55х1 + 20х2 + 35х3 + 65х4 + 35х5 + 20х6 + 60х7 + 25х8 + 25х9
Ограничения на ежедневное количество человек в экскурсиях:
х1 + х2 + х3 = 30 х4 + х5 + х6 = 20 х7 + х8 + х9 = 16
Ограничения на ежедневное количество мест в экскурсиях:
х1 + х4 + х7 <= 25 х2 + х5 + х8 <=20 х3 + х6 + х9 <=30
Другие ограничения – количество туристов от каждого отеля на экскурсию неделимо и больше 5: (х1, х2, … х9) >= 5 и (х1, х2, … х9) – целые числа

Следующим шагом разместим оптимизируемую модель в Excel, как показано ниже:



Здесь, в ячейках Е2:М2 размещены начальные значения неизвестных (х1, х2, … х9)=0. Для единообразной записи ограничений использована таблица коэффициентов Е3:М8. В ячейку D3 записана формула =E$2*E3+F$2*F3+G$2*G3+H$2*H3+I$2*I3+J$2*J3+K$2*K3+L$2*L3+M$2*M3, которая размножена на диапазон D4:D8. В ячейках С3:С8 записаны граничные значения числа туристов от отелей и в экскурсиях. Целевая функция записана в ячейке В1: =55*E2+20*F2+35*G2+65*H2+35*I2+20*J2+60*K2+25*L2+25*M2.

Нам осталось запустить поиск решения и ввести адреса ячеек и ограничения, как на рисунке ниже:



Результат поиска решения показан ниже:

Здесь в ячейках Е2:М2 подобрано оптимальное количество туристов, дающее минимальную стоимость расходов, равную 2295$. Проанализируйте полученное решение и поэкспериментируйте.

В состав Excel входит файл с примерами использования инструмента Поиск решения Solvsamp.xls. Он обычно расположен в папке Program Files\Microsoft Office\Office\Samples. Каждый лист содержит один из шести примеров — "Структура производства", "Транспортная задача", "График занятости", "Управление капиталом", "Портфель ценных бумаг" и "Проектирование цепи". В примерах уже подобраны целевая и влияющие ячейки, а также ограничения. Примеры из Solvsamp.xls помогут разрешить ваши вопросы.

Поиск решения и сценарии. Транспортная задача
При проведении расчетов полезно сохранять и при необходимости вызывать варианты вычислений. В Excel для этого используют сценарии - наборы значений, которые сохраняются с некоторым именем и могут подставляться на листе: СервисСценарии…. Имеется также возможность вывода отчета сценариев, по которому можно проследить зависимости между данными. Здесь сценарии будут рассмотрены в паре с использованием инструмента Поиск решения.

Решим известную транспортную задачу об оптимальных перевозках. Предприятие развозит с двух складов 2 вида товара по 2-м магазинам. Ежедневная потребность магазинов в товарах в штуках следующая:






Магазин 1

Магазин 2

Товар 1

45

40

Товар 2

55

50

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







Магазин 1

Магазин 2

Склад 1

1

2

Склад 2

2

1

Кроме того, известно, что минимальный остаток каждого товара на 1-ом складе равен 30 штук, на 2-ом складе – 90 штук, т.е. товара всегда достаточно для полного удовлетворения ежедневных потребностей магазинов. Необходимо составить план развоза товаров, обеспечивающий минимальную стоимость развоза. Кроме того, произвести расчеты для случая, когда потребности магазинов в каждом товаре возрастут на 30 штук.

Решение. Составим математическую модель и, в первую очередь, введем обозначения неизвестных – х1 – количество товара 1 со склада 1 в магазин 1, х2 – количество товара 1 со склада 1 в магазин 2 и т.д.:


 

 

Магазин 1

Магазин 2

Склад 1

Товар 1

х1

х2

Товар 2

х3

х4

Склад 2

Товар 1

х5

х6

Товар 2

х7

х8

Перечислим ограничения:



  • 1, х2, … х8) >= 5 и (х1, х2, … х8) – целые числа;

  • х12<=30, x3+x4<=30, x5+x6<=90, x7+x8<=90, т.е. со склада нельзя вывести больше, чем там есть товара;

  • x1+x5=45, x3+x7=55, x2+x6=40, x4+x8=50, необходимое магазинам количество товара.

Целевая функция, требующая минимизации, запишется так:
х1 + 2х2 + х3 + 2х4 + 2х5 + х6 + 2х7 + х8
На следующем шаге разместите исходные данные в Excel, как показано на рис. 2.41. Для неизвестных (х1, х2, … х8) отведены ячейки C2:D5. Для удобства записи целевой функции, на основе таблицы C2:D5, создана промежуточная таблица С16:D17. В ней суммируются данные по складам: С16=C2+C3 (т.е. х13), D16=D2+D3 (х24), C17=C4+C5 (х57), D16=D2+D3 (х68).

Целевая функция записана в ячейке В19 с использованием функции СУММПРОИЗВ, которая вычисляет сумму произведений таблиц C12:D13 и С16:D17. Это соответствует выражению х1 + 2х2 + х3 + 2х4 + 2х5 + х6 + 2х7 + х8.

Теперь вызовите инструмент Поиск решения, заполните параметры как на рис. 2.42. На рис. 2.43 приведены результаты вычислений.

Вы, наверное, обратили внимание, что перед сохранением результатов вычислений появляется окно – рис. 2.44. В нем имеется возможность сохранить изменяемые данные в качестве сценария. Повторите расчет и на этом этапе сохраните сценарий – Вам потребуется ввести имя сценария – рис. 2.45.




Рис. 2.41


Рис. 2.42


Рис. 2.43


Рис. 2.44


Рис. 2.45
Исследуем, что же было сохранено в сценарии: СервисСценарии… - откроется окно диспетчера сценариев – рис. 2.46. В левом окне стоит имя записанного ранее сценария. Нажмите кнопку Изменить – откроется правое окно – рис. 2.46. Как видно, в качестве изменяемых ячеек по умолчанию сохранены подобранные значения неизвестных. Нажмите ОК откроется окно со значениями изменяемых ячеек – рис. 2.47. Значения в этом окне могут также изменяться вручную.


Рис. 2.46


Рис. 2.47
Поскольку мы будем изменять (увеличивать) потребности магазинов, то в качестве изменяемых ячеек следует добавить ячейки C8:D9. Вызовите диспетчер сценариев СервисСценарии…. Находясь в окне диспетчера (рис. 2.46, справа), в параметр Изменяемые ячейки через знак «;» допишите новый диапазон, чтобы получилось так: C2:D5;C8:D9. Нажмите ОК и ОК. Таким образом, изменяемые ячейки этого сценария сохранены.

Теперь в ячейки C8:D9 введите увеличенные потребности магазинов (75, 70, 85, 80), повторите поиск решения, сохраните результат, но не сохраняйте сценарий – создадим его другим путем, вручную: вызовите диспетчер сценариев и нажмите кнопку Добавить…. Назовите сценарий Большие потребности, в качестве изменяемых ячеек введите C8:D9;C2:D5. Нажмите ОК и ОК. Таким образом, в списке сценариев проявится второй сценарий. Кнопка Вывести рядом со списком позволяет загрузить выбранный в списке сценарий. При этом не сохраненные ячейки не изменяются.


Задания для самостоятельного выполнения:

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



  1. Об оптимальных перевозках – транспортная задача. Ее цель состоит в минимизации затрат на перевозки товара со складов к потребителям. Именно к этой задаче сводится множество задач распределения ресурсов. Торговое предприятие развозит с двух своих складов 4 вида товара по сети из 5-ти магазинов. Средние дневные продажи магазинов каждого вида товара в штуках следующие:







Магазин 1

Магазин 2

Магазин 3

Магазин 4

Магазин 5

Товар 1

45

40

30

50

25

Товар 2

55

50

40

60

20

Товар 3

50

30

25

40

20

Товар 4

40

35

20

30

25

Известна также стоимость доставки единицы товара по магазинам – она задана таблицей:







Магазин 1

Магазин 2

Магазин 3

Магазин 4

Магазин 5

Склад 1

1

2

6

4

2

Склад 2

2

1

5

3

1

Кроме того, известно, что минимальный остаток каждого товара на 1-ом складе равен 100 штук, на 2-ом складе – 150 штук. Необходимо составить план развоза товаров, обеспечивающий минимальную стоимость развоза. Задание 1 в сокращенном виде решено в предыдующем разделе.




  1. О рационе питания – оптимальная смесь. Минимальный ежедневный рацион питания животного на ферме должен содержать 6 единиц белков, 8 единиц жиров и 12 единиц углеводов. Животные получают три вида кормов, стоимостью 3, 2 и 4 рубля за кг. Содержание единицы белков, жиров и углеводов в 1 кг корма приведено в таблице:







Белков (ед.)

Жиров (ед.)

Углеводов (ед.)

Корм 1

17

3

6

Корм 2

5

2

3

Корм 3

2

3

7

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




  1. Об оптимальном плане – ассортимент продукции. Ателье шьет комбинезоны трех типов К1, К2, К3 и использует ткани четырех типов Т1, Т2, Т3, Т4. Нормы расхода ткани каждого типа на каждый комбинезон приведены в таблице:







К1

К2

К3

Т1

1

2

1

Т2

2

1.5

3

Т3

0.5

1

0.5

Т4

3

1

0.5

Стоимость пошива комбинезона типа К1 равна 100 руб., К2 – 120 руб., К3 – 110 руб. (это расходы на сдельную оплату труда работников). Месячный запас тканей типа Т1 равен 1500м, Т2 – 2400м, Т3 – 900м, Т4 – 1800м. Месячный фонд зарплаты равен 100000 руб. Необходимо пошить не менее 1000 комбинезонов и обеспечить прибыль не менее 100000 руб. Прибыль от реализации комбинезона типа К1 равна 100 руб., К2 – 80 руб., К3 – 90 руб.

Необходимо определить оптимальное количество комбинезонов каждого вида (прибыль максимальна).


  1. Об оптимальном использовании ресурсов. Составьте оптимальный план производства, чтобы стоимость всей продукции мыла максимальной, если:







Стоимость 1 ед. продукции

Нормы расхода ресурсов

Трудовых

Сырьевых

Материалов

Продукция 1

40

6

8

6

Продукция 2

30

5

7

5

Объемы имеющихся ресурсов: трудовых – 48, сырьевых – 56, материалов – 72. Цена единицы сырья – 2$, цена единицы материалов – 1.5$.



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







Одиночество нельзя заполнить воспоминаниями, они только усугубляют его. Гюстав Флобер
ещё >>