Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Документ'
Б.Л.Пастернак «Доктор Живаго» В. Ерофеев «Москва-Петушки». Саша Соколов «Школа для дураков» Ходасевич В. Ст-ния «Автомобиль», «Берлинское» Пригов Д....полностью>>
'Диплом'
Закінчення 2008/2009 навчального року і проведення державної підсумкової атестації учнів загальноосвітніх навчальних закладів визначено Типовими навч...полностью>>
'Документ'
Гималаи - прихожая Тибета. - Первое знакомство с ламаизмом и его последователями. - Беседа с Далай-ламой. - Смерть и посмертные скитания в верованиях ...полностью>>
'Диплом'
Барышников Владимир Николаевич, д.и.н., проф., заведующий кафедрой истории Нового и новейшего времени исторического факультета Санкт-Петербургского г...полностью>>

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

Главная > Задача
Сохрани ссылку в одной из сетей:

Содержание

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

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

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

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

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

По умолчанию инструмент не установлен и его следует установить: вставьте дистрибутивный CD-диск и выберите в списке надстроек СервисНадстройки… соответствующий флажок.

Если целевая функция и ограничения линейны, то решение состоит в нахождении множества чисел (х1, х2, … хn), минимизирующих (максимизирующих) линейную целевую функцию f(х1, х2, … хn)= c1х1+c2х2+… +cnхn при m<n линейных ограничениях-равенствах аi1х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*H4+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*H3+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$.

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



Скачать документ

Похожие документы:

  1. Современный учитель должен быть прежде всего личностью! Ведь помимо предмета дети многое берут от человека

    Документ
    Современный учитель должен быть прежде всего личностью! Ведь помимо предмета дети многое берут от человека! Конечно, он должен быть умным (это естественно), терпеливым, мобильным, добрым и жёстким одновременно, знающим современные чаяния молодежи.
  2. Категориальное мышление в праве: его значение Акашкин А. Ю

    Документ
    О степени разработанности понятия «категория», вообще, можно говорить только в рамках философского знания. Категории (от греч. kategoría - высказывание, обвинение; признак) в философии, наиболее общие и фундаментальные понятия, отражающие
  3. Транснационализация туристического бизнеса: эволюция и современность монография Москва 2006

    Монография
    В настоящей монографии рассмотрены эволюция процесса транснационализации туристического бизнеса и особенности слияния и поглощения корпораций в туристической отрасли.
  4. Вестник интегративной психологии

    Документ
    Эта статья пишется накануне конференции «Интегративная психология: теория и практика», который будет проходить в г. Ярославле. Неординарность события для нашей науки невольно заставляет задуматься о том, когда, как и почему город на
  5. Программа оптимизации доминирующего психического состояния у представителей различных типов темперамента 15 Т. С. Бабина 16

    Программа
    Печатается по решению Редакционно-издательского совета Балашовского института (филиала) ГОУ ВПО «Саратовский государственный университет имени Н. Г. Чернышевского».

Другие похожие документы..