Поиск решения

  • doc
  • 06.05.2020
Публикация на сайте для учителей

Публикация педагогических разработок

Бесплатное участие. Свидетельство автора сразу.
Мгновенные 10 документов в портфолио.

Иконка файла материала 19. Поиск решения.doc

Поиск решения

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

 

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

 

Если целевая функция и ограничения линейны, то решение состоит в нахождении множества чисел (х1, х2, … хn), минимизирующих (максимизирующих) линейную целевую функцию f1, х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).

В качестве содержательного примера рассмотрим задачу оптимизации туристических групп (экскурсионных пакетов). Российская туристическая фирма ежедневно отправляет в три отеля Анталии, Кемера и Мармариса (Турция) соответственно 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

 

В процессе решения надо найти такие х1…х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 в виде, наиболее удобном для дальнейших вычислений, как показано ниже:

 

 

Здесь, в ячейках G1:G9 размещены начальные значения неизвестных (х1, х2, … х9)=0. В ячейках С3:С8 записаны граничные значения числа туристов от отелей и в экскурсиях. В ячейках D3:D8 записаны формулы-заготовки для ограничений: =G1+G2+G3, =G4+G5+G6, =G7+G8+G9, =G1+G4+G7, =G2+G5+G8, =G3+G6+G9. Целевая функция записана в ячейке В1: =55*G1+20*G2+35*G3+65*G4+35*G5+20*G6+60*G7+25*G8+25*G9.

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

 

 

Результат поиска решения выглядит так:

 

 

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

Поэкспериментируйте: попробуйте вручную изменить подобранные значения, оцените значения целевой функции. Повторно вызовите инструмент Поиск решения, удалив условие (х1, х2, … х9) >= 5 или добавив новое условие, и выполните подбор.

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

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

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

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

 

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

 

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

Отметим, что инструмент Поиск решения работает аналогичным образом в программе Calc OpenOffice.


Скачано с www.znanio.ru