Лабораторна робота №3. Аналітичні технології в інформаційних системах менеджменту: лінійні і нелінійні оптимізаційні моделі в задачах прийняття управлінських рішень

Транспортная задача

Рассмотрим пример, где используется средство поиска решений. Предположим, что фирма имеет 4 фабрики и 5 центров распределения ее товаров. Фабрики фирмы располагаются в Денвере, Бостоне, Новом Орлеане и Далласе с производственными возможностями 200, 150, 255 и 175 единиц продукции ежедневно, соответственно. Центры распределения товаров фирмы располагаются в Лос-Анджелесе, Сент-Луисе, Вашингтоне и Атланте с потребностями в 100, 200, 50, 250 и 150 единиц продукции ежедневно, соответственно. Хранение на фабрике единицы продукции, не поставленной в центр распределения, обходится в $0,75 в день, а штраф за простроченную поставку единицы продукции, заказанной потребителем в центре распределения, но там не находящейся, равен $2,5 в день. Стоимость перевозки единицы продукции с фабрики в пункты распределения приведена в таблице:

Транспортные расходы

		1 Лос-Анджелес	2 Даллас	3 Сент-Луис	4 Вашингтон	5 Атланта
1 2 3 4	Денвер Бостон Новый Орлеан Даллас	1,5 2,5 2 2	2 2 1,5 0,5	1,75 1,75 1,5 1,75	2,25 1 1,75 1,75	2,25 1,5 1,75 1,75

Необходимо так спланировать перевозки, чтобы минимизировать суммарные транспортные расходы.

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

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

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

Для решения данной задачи построим ее математическую модель. Неизвестными в данной задаче являются объемы перевозок. Пусть xij – объем перевозок с і-й фабрики в j-й центр распределения. Функция цели – это суммарные транспортные расходы, т.е.

где c_ij – стоимость перевозки единицы продукции с і-й фабрики в j-й центр распределения.

Неизвестные в данной задаче должны удовлетворять следующим ограничениям:

• Объемы перевозок не могут быть отрицательными

• Так как модель сбалансирована, то вся продукция должна быть вывезена с фабрики, а потребности всех центров распределения должны быть полностью удовлетворены.

В результате имеем следующую модель:

минимизировать:

при ограничениях:

, [1, 5],

, [1, 4],

, [1, 4], [1, 5].

где а_і – объем производства на і-й фабрике, b_j – спрос в j-м центре распределения.

Для решения этой задачи с помощью средства поиска решений введем данные, как показано на рисунке:

Рис.3.1. Исходные данные транспортной задачи

В ячейки А1: Е4 введены стоимости перевозок. Ячейки А6: Е9 отведены под значения неизвестных (объемы перевозок). В ячейки G6: G9 введены объемы производства на фабриках, а в ячейки А11: Е11 введены потребность в продукции в пунктах распределения. В ячейку F10 введена целевая функция

=СУММПРОИЗВ(А1:Е4;А6:Е9)

В ячейки А10: Е10 введены формулы

=СУММ(А6: А9)

=СУММ(В6: В9)

=СУММ(С6: С9)

=СУММ(D6: D9)

=СУММ(Е6: Е9)

определяющие объем продукции, ввозимой в центры распределения.

В ячейки F6: F9 введены формулы

=СУММ(А6: А6)

=СУММ(А7: А7)

=СУММ(А8: А8)

=СУММ(А9: А9)

вычисляющие объем продукции, вывозимой с фабрик.

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

Не забудьте в диалоговом окне Параметры поиска решения (Solver Options) установить флажок Линейная модель (Assume Liner Model). После нажатия кнопки Выполнить (Solve) средство поиска решений находит оптимальный план поставок продукции и соответствующие ему транспортные расходы.

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

Рассмотрим более подробно элементы диалогового окна Поиск решения (Solver)

В поле Установить целевую ячейку (Set Target Cell) диалогового окна Поиск решения (Solvet) дается ссылка на ячейку с функцией, для которой будет находиться максимум, минимум или заданное значение. Тип взаимосвязи между решением и целевой ячейкой задается путем установки переключателя в группе Равной (Equal To). Для нахождения максимального или минимального значения целевой функции этот переключатель ставится в положение Максимальному значению (Max) или Минимальному значению (Min), соответственно. Для нахождения значения целевой функции, заданного в поле группы Равной (Equal To), переключатель ставится в положение Значению (Value Of).

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

Ограничения, налагаемые на переменные задачи, отображаются в поле Ограничения (Subject to the Constraints). Средство поиска решений допускает ограничения в виде равенств, неравенств, а так же позволяет ввести требование целочисленности переменных. Ограничения добавляется по одному. Для вода ограничений нажмите кнопку Добавить (Add) в диалоговом окне Поиск решения (Solver) и в открывшемся диалоговом окне Добавление ограничения (Add constraint) заполните поля.

Рис. 3.2.Диалоговое окно Добавление ограничения. Ввод двух групп ограничений

В поле Ссылка на ячейку (Cell Reference) введите левую часть ограничения , а в поле Ограничения (Constraints) – правую часть, в нашем примере. С помощью раскрывающегося списка вводится тип соотношения между левой и правой частями ограничения.

Нажмите кнопку Добавить (Add) в диалоговом окне Добавление ограничения (Add Constraint) и введите вторую группу ограничения, налагаемых на переменные. Нажатие кнопки ОК завершает ввод ограничения.

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

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

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

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

• Поле Максимальное время (Max Time) служит для ограничения времени, отпускаемого на поиск решения задачи

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

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

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

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

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

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

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

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

Для того чтобы вывести отчет о результатах решения задачи выберите в диалоговом окне Результаты поиска решения (Solve Results) требуемый тип отчета: Результаты, Устойчивость, Пределы (Answer, Sensitivity, Limit).

Задача о назначениях.

Рассмотрим пример решения задачи о назначениях. Четверо рабочих могут выполнять 4 вида работ. Стоимости с_i,j выполнения i-м рабоим j-й работы приведены в ячейках диапазона А1:D4:

Рис. 3.4. Задача о назначениях. Ввод данных

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

Для решения этой задачи построим ее математическую модель . Пусть переменная х_i,j =1, если i-м рабочим выполняется j-я работа и х_i,j = 0, если i-м рабочим не выполняется j-я работа. Тогда модель имеет следующий вид:

-минимизировать

-при ограничениях :

, j [1, 4],

, i [1, 4],

х_i,j {0, 1}, i [1, 4], j [1, 4]

Для решения этой задачи с помощью поиска решений отведем под неизвестный диапазон ячейки F2:I5, в ячейку J1 введем целевую функцию

=СУММПРОИЗВ(F2:I5; A1:D4), вычисляющую стоимость работ. В ячейки F6:I6, а также J2: J5 введем формулы, задающие левые части ограничений.

Рис. 3.5. Задача о назначениях. Ввод формул.

Затем выбираем команду Сервис. Поиск решений и заполняем открывшееся диалоговое окно.

Не забудьте в диалоговом окне Параметры поиска решений установить флажок Линейная модель. После нажатия кнопки Выполнить средство поиска решений найдет оптимальное решение

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

Решение системы нелинейных уравнений

Средство поиска решений позволяет находить решение системы нелинейных уравнений. Рассмотрим, как это делается, на примере решений следующей системы уравнений:

Напомним, что пара (х и у) является решением системы тогда и только тогда, когда она является решением следующего уравнения с двумя неизвестными.

(х²+у²-3)²+(2х+3у-1)²=0

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

Определяемое решение нелинейной задачи зависит от начального приближения, удачный подбор которого очень важен. В данном слуачае локализовать корни можно, например, протабулировав левую часть уравнения по переменным х и у на отрезке [-3, 3]:

Рис. 3.6. Табуляция нелинейной функции

В ячейках А2:А6 и B1:F1 введены значения х и у соответственно. В ячейку В2 введена формула

=($A2^2+B$1^2-3)^2+(2*$A2+3*B$1-1)^2,

вычисляющая правую часть уравнения при значении х и у из ячеек А2 и В1 соответственно. Протащим эту формулу на диапазон В2: F6. Из рисунка видно, что за начальное приближение к корню целесообразней выбрать следующие пары значений (-1;1), (1;0), (1;-1). Можно убедится что две последние пары начальных приближений с помощью средства поиска решений будут приводить к одному и тому же решению.

Для нахождения первого корня отведем под применением х и у ячейки А10 и В10, соответственно, и введем в них начальные приближения -1 и 1. В ячейку С10 введем формулу:

=(A10^2+B10^2-3)^2+(2*A10+3*B10-1)^2

Затем вызываем команду Сервис. Поиск решений и заполняем открывшееся диалоговое окно.

После нажатия на кнопку Выполнить средство поиска решения находит решение.

Аналогично находится и второе решение. Решениями будут значения 1,576 и -0,717. Убедитесь, что начальное приближение (1;-1) приводит к тому же результату, что и приближение (1;0).