6. Общие сведения об оптимизационных задачах. Л10
Оптимизационные задачи широко распространены в технической и финансовой сфере (транспортная задача, задача о назначении и др). Признаком оптимизационной задачи является требование поиска экстремума некоторой функции. Решение оптимизационной задачи заключается в получение оптимального значения выбранного параметра.
Математическая формулировка задачи включает три части: целевую функцию; ограничения; граничные условия. В том случае, если в ограничения и целевую функцию переменные входят в первой степени, задача называется линейной. Нахождение оптимальных значений переменных линейной задачи называется задачей линейного программирования.
Таким образом задача линейного программирования включает: а) целевую функцию, которую следует максимизировать или минимизировать; б) ограничения записанные в виде равенств; в) ограничения записанные в виде неравенств; д) граничные условия, которые показывают предельно допустимые минимальные dj и максимальные значения Dj переменных.
;
;
;
.
.
Постановка транспортной задачи. Л11
Фирма имеет 4 фабрики по производству электродов для ручной сварки и 5 центров распределения продукции. Фабрики располагаются в Мариуполе, Донском, Торезе, Киеве с производственными возможностями 200, 150, 225, 175 единиц продукции ежедневно. Распределительные центры располагаются в Мариуполе, Краматорске, Харькове , Виннице и Дружковке с потребностями 100, 200, 50, 250, 150 единиц продукции ежедневно, соответственно. Хранение на фабрике не поставленной в центр распределения единицы продукции обходится 5 грн в день, а штраф за просрочку поставки заказанный потребителем в центр распределения единицы продукции, но там не находящейся, равен 10 грн в день.
Необходимо так спланировать перевозки, чтобы минимизировать суммарные транспортные расходы.
Важно отметить, что т. к. данная модель сбалансирована, т. е. суммарный объем произведенной продукции равен суммарному объему потребностей в ней, то в этой модели не надо учитывать издержки, связанные как со складированием, так и с недопоставками продукции. В противном случае в модель надо ввести:
в случае перепроизводства — фиктивный пункт распределения; стоимость перевозок единицы продукции в этот фиктивный пункт полагается равной стоимости складирования, а объемы перевозок в этот пункт равны объемам складирования
излишек продукции на фабриках;
в случае дефицита — фиктивную фабрику; стоимость перевозок единицы продукции из фиктивной фабрики полагается равной стоимости штрафов за недопоставку продукции, а объемы перевозок из этой фабрики равны объемам недопоставок продукции в пункты распределения.
Для решения данной задачи построим ее математическую модель. Неизвестными здесь являются объемы перевозок. Пусть xij — объем перевозок с i-й фабрики в j-й центр распределения. Функцией цели являются суммарные транспортные расходы, т. е.
,
где сij— стоимость перевозки единицы продукции с i-й фабрики в j-й центр распределения. Кроме того, неизвестные должны удовлетворять следующим ограничениям:
неотрицательность объема перевозок;
т. к. модель сбалансирована, то вся продукция должна быть вывезена с фабрик, и потребность всех центров распределения должна быть полностью удовлетворена.
Таким образом, мы имеем следующую модель:
минимизировать:
,
при ограничениях:
, ,
, ,
, ,
где ai— — объем производства на i-й фабрике, bj –спрос в j-м центре распределения.
8. Средство “Поиск решения” для решения оптимизационных задач л12
Выполните следующую подготовительную работу для решения транспортной задачи с помощью средства Поиск решения (рис. 8.1).
Введите в ячейки диапазона B3:F6 стоимости перевозок.
Отведите ячейки диапазона B8:F11 под значения неизвестных (объемов перевозок).
Введите в ячейки диапазона Н8:H11 объемы производства на фабриках.
Введите в ячейки диапазона В13:F13 потребность в продукции в пунктах распределения.
В ячейку В16 введите функцию цели =СУММПРОИЗВ(ВЗ:F6;В8:F11)
В ячейки диапазонов G8:G11 введите формулы, вычисляющие объемы производства на фабриках, в ячейки диапазона B12:F12 объемы доставляемой продукции в пункты распределения. А именно:
Рис. 8.1 - Исходные данные транспортной задачи и заполненное диалоговое окно Поиск решения.
Ячейка Формула Ячейка Формула
G8 = СУММ (B8 : F8) B12 = СУММ (B8 : B11)
G9 = СУММ (B9 : F9) C12 = СУММ (C8 : C11)
G10 = СУММ (B10 : F10) D12 = СУММ (D8 : D11)
G11 = СУММ (B11 : F11) E12 = СУММ (E8 : E11)
F12 = СУММ (F8 : F11)
7. Выберите команду Сервис | Поиск решения и заполните диалоговое окно Поиск решения, как показано на рис. 8.1. Окно Поиск решения имеет элементы, перечисленные в табл. 8.1.
Примечание: Поиск решения является одной из надстроек (add-ins) MS Excel. Если в меню Сервис отсутствует команда Поиск решения, для ее установки необходимо выбрать команду Сервис / Надстройки. На экране отобразится диалоговое окно Надстройки. В списке Список надстроек выберите Поиск решения и нажмите кнопку ОК. Если в этом списке нет средства Поиск решения, то его надо сначала инсталлировать с диска Microsoft Office. Для этого достаточно повторно запустить программу установки Microsoft Office и убедиться, что выбран параметр установки надстройки Поиск решения.
Таблица 8.1 - Элементы окна Поиск решения
Элемент |
Описание |
Поле Установить целевую ячейку |
Приводится ссылка на ячейку с функцией, максимум, минимум или значением которой Поиск решения будет искать, изменяя значения параметров так, чтобы они удовлетворяли налагаемым на них ограничениям. В примере с задачей о красках в поле Установить целевую ячейку вводим B16 |
Группа Равной
|
Тип взаимосвязи между решением и целевой ячейкой устанавливается путем выбора переключателя в группе Равной. Для отыскания максимального значения целевой функции выбирается переключатель максимальному значению, минимального переключатель минимальному значению. Если отыскиваются значения переменных, для которых значение функции из целевой ячейки равно установленному в поле группы Равной значению, то выбирается переключатель значению. В транспортной задаче выберите переключатель минимальному значению, т.к находим план перевозок с минимальными расходами. |
Поле Изменяя ячейки |
Приводится ссылка на диапазон ячеек или группу диапазонов ячеек, отведенных под неизвестные. Значения в этих ячейках должны изменяться в процессе поиска решения задачи, так чтобы найти решение, удовлетворяющее заданным ограничениям. В нашем случае введем в поле Изменяя ячейки диапазон B8:F11. |
Список Ограничения |
Допускаются ограничения в виде равенств, неравенств, требования того, что неизвестные могут принимать только целые значения, либо только значения 0 или 1. Ограничения добавляются по одному за раз и отображаются в окне Добавление ограничения, вызываемого нажатием кнопки Добавить (рис. 2.2).
|
Рис. 8.2 – Окно Добавление ограничения
Нажмите кнопку Параметры. На экране отобразится диалоговое окно Параметры поиска решения (рис. 8.3). В диалоговом окне Параметры поиска решения можно
изменять условия и варианты поиска решения исследуемой задачи, а также загружать и сохранять оптимизируемые модели. Значения и состояния элементов управления, используемые по умолчанию, подходят для решения большинства задач. Опишем элементы этого окна (табл. 8.2).
Рис. 8.3 – Окно Параметры поиска решения
Таблица 8.2 - Элементы окна Параметры поиска решения
Элемент |
Описание |
Поле Максимальное время |
Служит для ограничения времени, отпускаемого на поиск решения задачи |
Поле Предельное число итераций |
Служит для ограничения числа промежуточных вычислений |
Поля Относительная погрешность и Допустимое отклонение |
Служат для задания точности, с которой отыскивается решение. Рекомендуется после нахождения решения с величинами данных параметров, заданных по умолчанию, повторить вычисления с большей точностью и меньшим допустимым отклонением и сравнить с первоначальным методом. Использование подобной проверки особенно рекомендуется для задач с целочисленными ограничениями на переменные |
Флажок Линейная модель |
Служит для поиска решения линейной задачи оптимизации или линейной аппроксимации нелинейной задачи. В случае нелинейной задачи этот флажок должен быть сброшен. Для линейной задачи — установлен, т. к. в противном случае возможно получение неверного результата |
Флажок Показывать результаты итераций |
Служит для приостановки поиска решения и просмотра результатов отдельных итераций
|
Флажок Неотрицательные значения
|
Позволяет установить нулевую нижнюю границу для тех влияющих ячеек, для которых она не была указана в поле Ограничение диалогового окна Добавить ограничение |
Флажок Автоматическое масштабирование |
Служит для включения автоматической нормализации входных и выходных значений, качественно различающихся по величине. Например, максимизация прибыли в процентах по отношению к вложениям, исчисляемым в миллионах рублей |
Группа Оценки |
Служит для выбора метода экстраполяции |
Группа Разности |
Служит для выбора метода численного дифференцирования |
Группа Метод поиска |
Служит для выбора алгоритма оптимизации |