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




Скачать 321.65 Kb.
НазваниеТехнология решения задач линейной оптимизации
страница1/4
Дата конвертации29.04.2013
Размер321.65 Kb.
ТипДокументы
  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Лабораторная работа №6 Линейное и дискретное программирование. Решение задач оптимизации с помощью надстройки «Поиск решения»
Цель работы: изучить возможности ms excel для решения задач оптимизации; приобрести навыки решения систем нелинейных уравнений

Технология решения задач линейной оптимизации iconУтверждаю декан фпмк а. М. Горцев "1" марта 2011 г
Обучаемый знакомится с классификацией задач оптимизации, методами решения этих задач и применением методов для решения конкретных...

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

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

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

Технология решения задач линейной оптимизации iconЛабораторная работа №1 Решение задач оптимизации с использованием ms excel
Цель работы: закрепить навыки постановки типовых задач линейного программирования и освоить методику их решения на основе использования...

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

Технология решения задач линейной оптимизации iconВ. В. Котенко Алгоритм дедуктивного построения научных теорий и направления его оптимизации
Компьютерная технология формирования виртуального образа личности при решении задач аутентификации

Технология решения задач линейной оптимизации iconСообразования «Современные компьютерные технологии как средство решения задач оптимизации»
Муниципального общеобразовательного учреждения средней общеобразовательной школы №9 Рузаевского муниципального района

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


Разместите кнопку на своём сайте:
lib.convdocs.org


База данных защищена авторским правом ©lib.convdocs.org 2012
обратиться к администрации
lib.convdocs.org
Главная страница