Технология решения задач линейной оптимизации






Скачать 321.62 Kb.
НазваниеТехнология решения задач линейной оптимизации
страница1/4
Дата публикации17.11.2013
Размер321.62 Kb.
ТипДокументы
top-bal.ru > Математика > Документы
  1   2   3   4
Тема: Технология решения задач линейной оптимизации

Цель: освоение специального инструментария MS Excel для решения оптимизационных задач.

Краткие теоретические сведения.

Типы задач оптимизации:

  • Задачи о перевозках: например, минимизация расходов по доставке товаров с нескольких фабрик в несколько магазинов с учетом спроса;

  • Задачи распределения рабочих мест: например, минимизация расходов на содержание штата с соблюдением требований, определенных законодательством;

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

  • Замена или смешивание материалов: например. Манипуляция материалами с целью снижения себестоимости, поддержания необходимого уровня качества и соблюдения требований потребителей.

  • Задачи линейной алгебры: решение линейных уравнений.

Мощный инструмент «Поиск решения» (Оптимизатор) предназначен для высококвалифицированного менеджера, владеющего математическими методами поиска оптимального решения сложно специальной проблемы.

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

В технологическом процессе решения линейной оптимизационной задачи с помощью Excel выделяются три типовых этапа:

  1. подготовительный (подготовка табличной модели до обращения к диалоговому окну оптимизатора, ввод данных и формул);

  2. основной (диалог с оптимизатором для определения целевой ячейки, экстремума, изменяемых ячеек, а также ограничений);

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

Задачи, решаемые с помощью оптимизатора, имеют три характерных признака:

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

  • В формуле целевой ячейки должны быть сделаны ссылки на одну или более изменяемых ячеек, от значений которых зависит результат. Они могут быть названы также неизвестными или переменными для решения. Поиск решения устанавливает значения изменяемых ячеек так, чтобы найти для формулы целевой ячейки оптимальное решение.

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

Элементы диалогового окна Поиск решения


Рис. 1. Диалоговое окно Поиск решения
Рассмотрим элементы диалогового окна ^ Поиск решения. Для этого зайдем в Сервис, Поиск решения. Средство поиска решений является одной из надстроек Excel. Если в меню Сервис отсутствует команда Поиск решения, то для установки необходимо выполнить команду Сервис, Надстройки, Поиск решения.

После этого выберем команду ^ Сервис, Поиск решения и заполняем открывшееся диалоговое окно Поиск решения следующим образом. В поле Установить целевую ячейку диалогового окна Поиск решения дается ссылка на ячейку с функцией, для которой будет находится максимум, минимум или заданное значение.

Тип взаимосвязи между решением и целевой ячейкой задается путем установки переключателя в группе ^ Равной. Для нахождения максимального или минимального значения целевой функции этот переключатель ставится в положении Максимальному значению или Минимальному значению, соответственно. Для нахождения значения целевой функции, заданного в поле группы Равной, переключатель ставится в положение Значению.

В поле ^ Изменяя ячейки указываются ячейки, которые должны изменяться в процессе поиска решения задачи, т.е. ячейки отведенные под переменные задачи.

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

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

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

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


Рис. 2. Диалоговое окно Параметры поиска решения

Рассмотрим элементы этого окна:

Поле ^ Максимальное время служит для ограничения времени, отпускаемого на поиск решения задачи.

Поле Предельное число итераций служит для ограничения числа промежуточных вычислений.

Поля ^ Относительная погрешность и Допустимое отклонение служит для задания точности, с которой ищется решение. Рекомендуется после нахождения решения с величинами данных параметров, заданными по умолчанию, повторить вычисления с большей точностью и меньшим допустимым отклонением и сравнить с первоначальным решением. Использование подобной проверки особенно рекомендуется для задач с требованием целочисленности переменных.

Флажок ^ Линейная модель служит для поиска решения линейной задачи оптимизации или линейной аппроксимации нелинейной задачи. В случае нелинейной задачи этот флажок должен быть сброшен, в случае линейной задачи – установлен, т.к. в противном случае возможно получение неверного результата.

Флажок Показывать результаты итерации служит для приостановки поиска решения и просмотра результатов отдельных итераций

Флажок ^ Неотрицательные значения служит для вывода и просмотра только положительных значений.

Флажок Автоматическое масштабирование служит для включения автоматической нормализации входных и выходных значений, качественно различающихся по величине, например, при максимизации прибыли в процентах по отношению к вложениям, исчисляемым в миллионах рублей.

Группа ^ Оценки служит для выбора метода экстраполяции

Группа Разности служит для выбора метода численного дифференцирования

Группа Метод поиска служит для выбора алгоритма оптимизации

Для того чтобы вывести отчет о результатах решения задачи выберите в диалоговом окне ^ Результаты поиска решения требуемый тип отчета: Результаты, Устойчивость, Пределы.
Лабораторная работа

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

1. Линейная оптимизационная задача

Рассмотрим на примере, как с помощью средства поиска решений решаются линейные оптимизационные задачи.

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


Ресурсы 

Нормы затрат ресурсов на одно изделие

Общее количество ресурсов

стол

шкаф

 

Древесина:

1 вида

0,2

0,1

40

2 вида

0,1

0,3

60

^ Трудоемкость (человеко-часов)

1,2

1,5

371,4

Прибыль от реализации одного изделия (руб.)

6

8




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

Для решения этой задачи необходимо построить математическую модель. Процесс построения модели можно начать с ответа на следующие три вопроса:

  1. Для определения каких величин строится модель?

  2. В чем состоит цель, для достижения которой из множества всех допустимых значений переменных выбираются оптимальные?

  3. Каким ограничениям должны удовлетворять неизвестные?

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

Суммарная прибыль от производства столов и шкафов равна z = 6*x1 + 8*x2. Целью фабрики является определение среди всех допустимых значений х1 и х2 таких, которые максимизируют суммарную прибыль, т.е. целевую функцию z.

Перейдем к ограничениям, которые налагаются на х1 и х2. Объем производства шкафов и столов не может быть отрицательным, следовательно:



Нормы затрат древесины на столы и шкафы не может превосходить максимально возможный запас данного исходного продукта, следовательно:





Кроме того, ограничение на трудоемкость не превышает количества затрачиваемых ресурсов



Таким образом, математическая модель данной задачи имеет следующий вид:

Максимизировать



при следующих ограничениях:







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

Решим данную задачу с помощью команды Сервис, Поиск решения (Tools, Solver). Средство поиска решений является одной из надстроек Excel. Если в меню Сервис(Tools) отсутствует команда Поиск решения (Solver), то для ее установки необходимо выполнить команду Сервис, Надстройки, Поиск решения (Tools, Add-ins, Solver).

Отведем ячейки А3 и В3 под значения переменных х1 и х2 (рис. 1).



Рис. 3. Диапазоны, отведенные под переменные, целевую функцию и ограничения

В ячейку С4 введем функцию цели: =6*А3+8*В3, в ячейки А7:А9 введем левые части ограничений:

=0,2*А1+0,1*В3

=0,1*А3+0,3*В3

=1,2*А3+1,5*В3,

а в ячейки В7:В9 – правые части ограничений.

Теперь выберем команду Сервис, Поиск решения (Tools, Solver) и заполним открывшееся диалоговое окно Поиск решения (Solver), как показано на рис. 2.



Рис. 4. Диалоговое окно Поиск решения задачи о максимизации прибыли на фабрике

Не забудьте в диалоговом окне Параметры поиска решения (Solver Options) установить флажок Линейная модель (Assume Linear Model). После нажатия кнопки Выполнить (Solve) открывается окно Результаты поиска решения (Solver Results), которое сообщает, что решение найдено (рис. 3).



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

Результаты расчета задачи представлены на рис. 4, из которого видно, что оптимальным является производство 102 столов и 166 шкафов. Этот объем производства принесет фабрике 1940 руб. прибыли.



Рис. 6. Результаты расчета с помощью средства поиска решений для задачи максимизации выпуска столов и шкафов

Задания для самостоятельного решения

1) Для производства двух видов изделий А и В используется токарное, фрезерное и шлифовальное оборудование. Нормы затрат времени для каждого из типов оборудования на одно изделие данного вида приведены в таблице. В ней же указан общий фонд рабочего времени каждого из типов оборудования, а также прибыль от реализации одного изделия.

^ Тип оборудования

Затраты времени (станко-часов) на обработку одного изделия

Общий фонд полезного рабочего времени

 

А

В

 

Фрезерное

10

8

168

Токарное

5

10

180

Шлифовальное

6

12

144

Прибыль от реализации одного изделия (руб.)

14

18



  1   2   3   4

Добавить документ в свой блог или на сайт

Похожие:

Технология решения задач линейной оптимизации iconРешение задач оптимизации в excel
Надстройка "Поиск решения". Задачи линейного программирования возникают, например, при планировании перевозок, распределения производственных...

Технология решения задач линейной оптимизации iconФедеральное агентство по образованию государственное образовательное учреждение
Целью работы является: изучение различных задач оптимизации (линейное и дискретное программирование). познакомиться с методикой решения...

Технология решения задач линейной оптимизации iconУрок по истории Древнего мира в 5 классе тема «Восстание Спартака»
Используемые технологии: икт, технология лоо, тркм, технология решения проблемных задач

Технология решения задач линейной оптимизации iconПримерная программа дисциплины «Линейная алгебра»
...

Технология решения задач линейной оптимизации iconУроке математики в 7 классе
Обучающая цель: отработать навыки решения задач с помощью уравнения, решения логических задач, отработать навыки решения геометрических...

Технология решения задач линейной оптимизации iconТема: «Способы решения задач на переливание»
Дидактическая цель занятия: ознакомить учащихся с понятием и типами задач на переливание, способами их решения. Закрепить навыки...

Технология решения задач линейной оптимизации iconЗадачи по линейному программированию и оптимизации
Постройте двойственные задачи к задачам из упражнения №3 раздела 1, сформулируйте для них условия признака оптимальности. Достаточно...

Технология решения задач линейной оптимизации iconПроекта «Решение задач на движение». Проект направлен на изучение...
Проект включает в себя изложение теории, рассмотрение решения задач на движение различного уровня сложности, задачи для самостоятельного...

Технология решения задач линейной оптимизации icon«Методы и способы решения задач на поверхностное натяжение и капиллярные явления»
«Методы решения физических задач». Цель курса в целом, и урока в частности, повысить мотивацию к изучению физики, развивать логическое...

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



Школьные материалы


При копировании материала укажите ссылку © 2018
контакты
top-bal.ru

Поиск