Оптимизационные модели принятия решений
Использование оптимизационных моделей при принятии решений
Успешность решения подавляющего большинства экономических задач зависит от наиболее эффективного способа использования ресурсов (денег, товаров, сырья, оборудования, рабочей силы и др.). Именно эффективностью использования, как правило, ограниченных, ресурсов определяется конечный результат деятельности любой экономической системы (фирмы, предприятия, отрасли).
Экономическая суть методов оптимизации заключается в том, что исходя из наличия определенных ресурсов выбирается такой способ их использования (распределения), при котором обеспечивается максимум (или минимум) интересующего ЛПР показателя.
Задачи нахождения значений параметров, обеспечивающих экстремум функции  при наличии ограничений, наложенных на аргументы (независимые переменные)  , носят общее название задач математического программирования.
Трудности, возникающие при решении задач математического программирования, определяются, в частности:
видом функциональной зависимости критерия эффективности, называемого также целевой функцией, от независимых переменных;
размерностью задачи, то есть количеством независимых переменных;
видом и количеством ограничений, которым удовлетворяют независимые переменные.
Среди задач математического программирования самыми простыми и наиболее хорошо изученными являются так называемые задачи линейного программирования (линейной оптимизации). Для них характерно то, что целевая функция линейно зависит от , а также то, что ограничения, накладываемые на независимые переменные, имеют вид линейных равенств или неравенств относительно этих переменных.
Такие задачи часто встречаются на практике — например, при решении проблем, связанных с распределением ресурсов, планированием производства, организацией работы транспорта и т.д. Во многих случаях расходы и доходы линейно зависят от количества закупленных или утилизированных средств (например, суммарная стоимость партии товаров линейно зависит от количества закупленных единиц; оплата перевозок производится пропорционально весам перевозимых грузов и т.п.).
Задачи линейного программирования, естественно, не исчерпывают все возможные типы взаимосвязей экономических параметров. Более сложными для анализа и численного решения являются задачи нелинейного программирования (нелинейной оптимизации), характеризуемые нелинейной зависимостью целевой функции и (или) функций-ограничений от независимых переменных .
Отметим еще два типа задач математического программирования, имеющих широкую распространенность в практике принятия управленческих решений.
Динамическое программирование служит для выбора наилучшего плана выполнения многоэтапных действий. В общем виде постановка задачи динамического программирования сводится к следующему. Имеется некоторая управляемая операция (целенаправленное действие), распадающаяся (естественно или искусственно) на ряд шагов (этапов). На каждом этапе осуществляется распределение и перераспределение ресурсов (управление) с целью улучшения ее результата в целом. Задача динамического программирования — определить оптимальное управление на каждом шаге и, тем самым, оптимальное управление всей операцией в целом.
Следует отметить также задачи стохастического программирования. Особенность данного класса задач заключается в том, что ищется оптимальное решение в условиях неполной определенности, когда ряд параметров, входящих в целевую функцию и ограничения, представляют собой случайные величины.
Решение задач динамического и стохастического программирования, а также ряда других задач (например, параметрического программирования), выходит за рамки настоящего курса лекций.
Линейные модели оптимизации в управлении
Сначала рассмотрим задачи линейной оптимизации (или оптимизационные задачи линейного программирования), математические модели которых содержат лишь линейные зависимости от переменных.
Как уже отмечалось, оптимизация, включающая теорию и методы решения задач, в которых критерий оптимальности (целевая функция) линейно зависит от параметров задачи, является наиболее разработанным разделом информационных технологий оптимальных решений. Линейные модели широко используются в теории и практике принятия управленческих решений.
Современные информационные технологии оптимизации решений широкого класса практических задач включают их формулировку (построение математической модели), математические методы и компьютерные программы решения этих задач, а также методы экономико-математического анализа оптимальных решений.
Общая задача линейной оптимизации заключается в нахождении максимума (минимума) линейной целевой функции:
|
(2.1)
|
при ограничениях
Функция называется целевой функцией, критерием оптимальности или линейной формой.
Вектор значений неизвестных  удовлетворяющих условию задачи (2.1) – (2.4), называется допустимым решением или допустимым планом задачи линейной оптимизации. Совокупность всех допустимых планов называется множеством допустимых планов. Допустимое решение  называется оптимальным, если оно обеспечивает максимальное (или, в зависимости от условий задачи, — минимальное) значение целевой функции.
Решение задач линейной оптимизации может быть получено без особых затруднений (естественно, при корректной формулировке проблемы). Классическим методом решения задач данного типа является симплекс-метод. В случае лишь двух переменных успешно может использоваться также графический метод решения, обладающий преимуществом наглядности. Очевидно, в случае  применение графического метода невозможно.
При решении ряда оптимизационных задач требуется, чтобы значения неизвестных выражались в целых числах. Естественно, к задачам подобного типа относятся те, в которых требуется определить необходимые для принятия решений значения физически цельных объектов (машин, агрегатов различного типа, людей, транспортных единиц и т.д. и т.п.). Такие задачи относятся к задачам целочисленной оптимизации. Математическая модель задачи линейной нецелочисленной оптимизации также определяется формулами (2.1) – (2.4), но в данном случае налагается дополнительное требование целочисленности всех (или части) неизвестных. Если требование целочисленности распространяется лишь на часть неизвестных величин задачи, то такая задача называется частично целочисленной.
Процесс построения математической модели для решения задачи начинается, как правило, с ответов на следующие вопросы:
Для определения каких величин должна быть построена модель, т.е. как идентифицировать переменные задачи?
Какие ограничения должны быть наложены на переменные, чтобы выполнялись условия, характерные для моделируемой системы?
В чем состоит цель задачи, для достижения которой из всех допустимых значений переменных нужно выбрать те, которые будут соответствовать оптимальному (наилучшему) решению задачи?
После ответа на данные вопросы для построения модели остается только идентифицировать переменные и представить цель и ограничения в виде математических функций этих переменных.
Надлежащий анализ вопросов подобного рода и корректная формулировка математической модели являются центральным звеном решения задач линейной (и не только линейной) оптимизации.
Эффективным средством решения задач линейной оптимизации является MS Excel. Входящий в состав данного программного продукта пакет Поиск решения (Solver) позволяет проводить решения задач подобного рода с большим (свыше 200) числом переменных и ограничений.
Отметим, что применительно к задачам оптимизации производственной программы предприятия наиболее типичными задачами линейной оптимизации являются оптимизация дохода, прибыли, себестоимости, номенклатуры производимой продукции, затрат станочного времени и т.п.
Рассмотрим использование информационных технологий решения задач линейной оптимизации на ряде конкретных примеров, имеющих непосредственное отношение к практике принятия управленческих решений.
Пример 1. Определение оптимального ассортимента продукции
Предприятие изготавливает два вида продукции П1 и П2 , которая поступает в оптовую продажу. Для производства используются два вида сырья A и B . Максимально возможные запасы сырья в сутки составляют 9 и 13 единиц соответственно. Расход сырья на единицу продукции приведен в таблице.
Таблица 2.1
Сырьё
|
Расход сырья на единицу продукции
|
Запас сырья, ед.
|
П1
|
П2
|
A
|
2
|
3
|
9
|
B
|
3
|
2
|
13
|
Маркетинговые исследования показали, что суточный спрос на продукцию П1 не превышает спрос на продукцию П2 более чем на 1 ед. Кроме того, известно, что спрос на продукцию П2 не превышает 2 единиц в сутки.
Оптовые цены единицы продукции равны для П1 — 3 д.е., для П2 — 4 д.е. Какое количество продукции каждого вида должно производить предприятие, чтобы доход от реализации продукции был максимальным?
Решение.
Очевидно, фирме требуется определить объемы производства каждого вида продукции в тоннах, максимизирующие доход в д.е. от реализации продукции, с учетом ограничений на спрос и расход исходных продуктов. Предположим, что предприятие изготовит  единиц продукции П1 и  единиц продукции П2. Поскольку производство продукции ограничено имеющимся в распоряжении предприятия сырьем каждого вида и спросом на данную продукцию, а также учитывая, что количество изготовляемых изделий не может быть отрицательным, получим следующую систему ограничений:
Доход от реализации продукции (целевая функция) составит . Таким образом, данная простая задача сводится к максимизации целевой функции  при учете вышеприведенных ограничений.
Проведем решение задачи в Excel.
Введем данные на рабочий лист так, как показано на Рис 2.1.
Рис. 2.1.
Искомые значения переменных  будут располагаться в ячейках B3 и C3 соответственно, целевая функция – в ячейке E7.
В ячейки D9-D14 введем левые части функций – ограничений в той последовательности, в которой они были представлены выше.
Далее, запускаем пакет Поиск решения и устанавливаем целевую и изменяемые ячейки, а также вводим ограничения (Рис.2.2).
Рис. 2.2. Окно диалога Поиск решения
Поиск решения дает ответ  .
Пример 2. Использование мощностей оборудования
Предприятие имеет m моделей машин различных мощностей. Задан план по времени и номенклатуре:  — время работы каждой машины; продукции -го вида должно быть выпущено не менее  единиц.
Необходимо составить такой план работы оборудования, чтобы обеспечить минимальные затраты на производство, если известны производительность каждой i - машины по выпуску j-го вида продукции  и стоимость единицы времени, затрачиваемого i-й машиной на выпуск j-го вида продукции  .
Другими словами, задача для предприятия состоит в следующем: требуется определить время работы время работы i — машины по выпуску j-го вида продукции  , обеспечивающее минимальные затраты на производство при соблюдении ограничений по общему времени работы машин T и заданному количеству продукции .
Решение.
По условию задачи машины работают заданное время T, поэтому данное ограничение можно представить в следующем виде:
Ограничение по заданному количеству продукции имеет вид:
Задача решается на минимум затрат на производство:
В данной постановке задачи предполагается, что количество выпускаемой продукции должно быть, по крайней мере, не менее . В некоторых случаях не допускается превышение плана по номенклатуре; очевидно в этом случае в ограничениях по количеству продукции необходимо использовать знак равенства.
Проведем решение задачи в Excel. Введем данные на рабочий лист так, как показано на Рис 2.3.
В ячейки B7:E7 введем формулы для ограничений по объему выпускаемой продукции ( ), в диапазон ячеек F19:F21 – формулы для ограничений по времени работы машин ( ). В качестве целевой ячейки выберем H11 и введем в нее формулу минимизируемой функции.
Рис. 2.3. Данные для решения примера 2
С помощью Поиска решения получим следующий ответ:
Машина
|
Время работы
|
1
|
2
|
3
|
4
|
1
|
803,92
|
0,00
|
0,00
|
196,07
|
2
|
625,00
|
0,00
|
375,00
|
0,00
|
3
|
0,00
|
1000,00
|
0,00
|
0,00
|
Искомое значение минимальных затрат на производство составляет 725,32 д.е.
Следующий рассматриваемый пример относятся к области целочисленной оптимизации.
Пример 3. Оптимизация производственной программы
Автомобилестроительный завод выпускает три модели автомобилей, которые изготавливаются последовательно в трех цехах. Мощность цехов составляет 300, 250 и 200 человеко-дней в декаду. В первом цехе для сборки одного автомобиля первой модели требуется 6 человеко-дней, второй модели – 4 и третьей модели – 2 человеко-дня в неделю соответственно. Во втором цехе трудоемкость равна 3, 4 и 5 человеко-дней соответственно, в третьем – по 3 человеко-дня на каждую модель. Прибыль, получаемая от продажи автомобиля каждой модели, составляет соответственно 15, 13 и 10 тыс. д.е. Требуется построить модель оптимального плана и определить оптимальные количества моделей каждого типа, т.е. такие, при которых прибыль завода будет максимальной.
Решение. Пусть  — количество выпускаемых автомобилей i-й модели в течение декады (i=1,2,3). Модель может быть описана следующей целевой функцией и системами ограничений:
Решение.
Введем данные на рабочий лист так, как показано на Рис. 2.4.
Искомые значения переменных  будут размещаться в ячейках A10:B10, целевая функция — в ячейке E10.
В ячейки A3:A5 введем левые части функций — ограничений, соответствующих второму, третьему и четвертому соотношению из (2.5).
С помощью Поиска решения получим ответ  
Рис. 2.4. Данные для решения примера 3.
Нелинейные модели оптимизации в управлении
В настоящем разделе мы кратко рассмотрим задачи нелинейной оптимизации (называемые иначе оптимизационными задачами нелинейного программирования), математические модели которых содержат нелинейные зависимости от переменных. Источники нелинейности в задачах подобного типа могут относиться, в частности, к одной из двух категорий:
Реально существующие и эмпирически наблюдаемые нелинейные соотношения, например непропорциональные зависимости между объемом производства и затратами, между количеством используемого в производстве компонента и некоторыми показателями качества готовой продукции, между затратами сырья и физическими параметрами (давление, температура и т.п.) соответствующего производственного процесса, между выручкой и объемом реализации и т.п.
Установленные (постулируемые) руководством правила поведения или задаваемые зависимости, например, правила расчета с потребителями энергии или других видов услуг, правила определения страховых уровней запаса продукции, гипотезы о характере вероятностного распределения рассматриваемых в модели случайных величин, различного рода договорные условия взаимодействия между партнерами по бизнесу и др.
В качестве примера можно рассмотреть формирование оптимальной производственной программы предприятия. По критерию затрат учитывается себестоимость единицы продукции, которая уменьшается при увеличении объема выпускаемой продукции, что приводит к нелинейному критерию эффективности. Нелинейные зависимости возникают также в ограничениях задачи при точном учете норм расхода ресурсов на единицу производимой продукции.
Вообще говоря, решение нелинейных задач по сложности значительно превосходит решение рассмотренных ранее задач линейной оптимизации. В связи с этим долгое время в практике экономического управления модели линейной оптимизации успешно применялись даже при наличии нелинейности. В одних случаях нелинейность была несущественна и ею можно было пренебречь, в других – проводилась линеаризация нелинейных соотношений или применялись специальные приемы, например строились так называемые аппроксимационные модели, благодаря чему достигалась требуемая адекватность. Тем не менее, часто встречаются задачи, для которых нелинейность является существенной и упомянутые выше методы аппроксимации неэффективны, в связи с чем нелинейность необходимо учитывать в явном виде.
В отличие от задачи линейной оптимизации (линейного программирования), не существует одного или нескольких алгоритмов, эффективных для решения любых нелинейных задач. Какой-то алгоритм может быть эффективен при решении задач одного типа и неприемлемым для задач другого типа. В связи с этим разработаны алгоритмы для решения каждого класса (типа) задач. Следует иметь в виду, что даже программы, ориентированные на решение определенного класса задач, не гарантируют правильность решения любых задач этого класса и оптимальность решения следует проверять в каждом конкретном случае.
Перечислим некоторые наиболее употребительные методы решения задач нелинейной оптимизации (нелинейного программирования):
Оптимизация нелинейной функции с ограничениями на неотрицательность значений переменных (наиболее широко используемыми моделями данного класса являются модели квадратичного программирования, в которых целевая функция является квадратичной функцией переменных .
Модели выпуклого программирования; в моделях данного класса целевая функция является вогнутой (или выпуклой), а функции-ограничения являются выпуклыми функциями. При данных условиях локальный максимум (или минимум) функции является также глобальным. При решении таких задач используется метод множителей Лагранжа, а также теорема Куна-Таккера.
Сепарабельное программирование. В задачах данного класса целевая функция и функции-ограничения могут быть представлены в виде сумм отдельных компонент. Данные задачи могут быть сведены к задачам линейного программирования.
Дробно-нелинейное программирование. В этих задачах производится максимизация (минимизация) целевой функции вида  . Если функции  линейны (задача дробно-линейного программирования), то задача сводится к линейной.
Невыпуклое программирование. Задачи данного типа принадлежат к наименее изученным и наиболее сложным задачам нелинейной оптимизации. В данном случае целевая функция и (или) функции-ограничения не выпуклы. Надежных методов решения таких задач в настоящее время не существует.
Мы ограничимся рассмотрением лишь наиболее простых задач нелинейной оптимизации, не требующих использования сложных аналитических выкладок и анализа, задач, которые могут эффективно решаться на базе табличного процессора Excel.
Задача нелинейной оптимизации в общем случае состоит в отыскании такого вектора неизвестных , который обращал бы в максимум (минимум) функцию
|
(2.6)
|
и удовлетворял бы системе ограничений
|
(2.7)
|
где на некоторые или на все переменные налагается условие неотрицательности.
|
