Оптимизационные задачи
Оптимизационные задачи разделяются на два класса:
классические задачи;
задачи математического программирования;
Среди классических задач выделяют:
задачи на безусловный экстремум;
задачи на условный экстремум;
Методами математического программирования решаются задачи:
линейного программирования;
нелинейного программирования;
целочисленного программирования;
параметрического программирования;
стохастического программирования;
динамического программирования.
Задачи на условный экстремум решаются методом множителей Лагранжа.
Задачи на безусловный экстремум решаются методами математического анализа. При этом выделяют два типа задач:
нахождение критических точек внутри области определения функции;
нахождение наибольшего и наименьшего значения функции на отрезке, то есть с учетом того, что эти значения могут находиться на концах отрезков.
Критические точки – это точки, в которых производная равна нулю или не существует.
Если производная существует, и равна нулю, то критическая точка является точкой экстремума (рис. 6.1.а) или точкой перегиба (рис. 6.1.б).
Для функции y=x2критическая точка есть точка минимума, а для функцииy=x3– точка перегиба.
а) б)
Рис. 6.1.График функции, для которой критическая точка является точкой экстремума (а) или точкой перегиба (б)
Для функции y= |x| в точкеx= 0 производная не существует и критическая точка является точкой минимума (рис. 6.2).
Рис. 6.2.График функции, у которой в точке х = 0 производная не существует, но имеется экстремум
Нахождение наибольшего и наименьшего значения функции рассмотрим на примере их определения для функции y=x3– 1,5x2– 6x + 1 на отрезке [-2; 0]
Так как производная y' = 3x2– 3x– 6 определена для любогоx, остается решить уравнениеy' = 0. Решая его, находимx= -1 иx= 2. Критическая точкаx= 2 не принадлежит рассматриваемому отрезку. Поэтому выбираются наибольшее и наименьшее из чиселy(-2) = -1;y(-1) = 4,5 иy(0) = 1. В результате имеем для отрезка [-2; 0]:maxy=y(-1) = 4,5;miny=y(-2) = -1.
В качестве примера рассмотрим в первом приближении задачу оптимального управления запасами, которая представляет собой классическую задачу поиска безусловного экстремума на отрезке [0; ∞).
Рассматриваемая в основной модели управления запасами целевая функция имеет вид y= 1/x+x→min
Производная функция y' = -1/x2+ 1.
Экстремальное
значение функция принимает в точке
x*опт= 1. Это
значение получено следующим образом.
Имеем функциюy= 1/x+x, и производнуюy'
= -1/x2+ 1. Из условияy' = 0 находим 1/x2= 1;x=
=
±1.x= -1 не удовлетворяет
заданному отрезку.
Тогда x*опт= 1.
Графически задача представлена на рис. 6.3.
Рис. 6.3.Пример безусловной оптимизации при непрерывном аргументе
В модели управления запасами целевая функция определяет минимум суммарных затрат (издержек), которые складываются из затрат на хранение единицы товара 1/x, и стоимости поставляемой партииx.
Поскольку в данной задаче на безусловный экстремум все величины являются непрерывными, задача решается методами математического анализа.
Оптимизация систем массового обслуживания
Рассматривается задача определения оптимального варианта СМО по критерию минимума суммарных затрат.
Отличие от задачи управления запасами состоит в том, что управляемая переменная – количество каналов n– является не непрерывной, а целочисленной величиной. Поэтому задача решается методом перебора, т.е. с определением численных значений характеристик вариантов.
Пусть в качестве критерия оптимальности принят критерий в виде минимума суммарных затрат на содержание каналов СМО и потерь, связанных с отказом в обслуживании заявок, т.е.:
C(n) =Cc+Cn→
,
где C(n) – суммарные затраты;
Cc– затраты на содержание каналов;
Сn– потери, связанные с отказом в обслуживании заявок;
n– количество каналов;
Затраты на содержание каналов могут быть представлены в виде
Сс= Сс1∙n,
где Cc1– затраты на содержание одного канала в течение определенного времени (например, в течение месяца).
Потери, связанные с необслуживанием заявок, определяются следующим образом:
Сn=Cn1∙L∙Pотк,
где Сn1– потери, связанные с необслуживанием одной заявки;
L– количество заявок, поступающих в систему в течение определённого времени;
Pотк– вероятность отказа.
Поскольку Pоткесть функция количества каналов, то критерий оптимальности может быть записан в виде:
С(n)
=Cc1∙n+Cn1
∙L∙Pотк(n)→
.
Составляющая затрат в функции nимеет вид линейно возрастающей зависимости. Составляющая потерь из-за необслуживания представляет собой зависимость, убывающую в функции отn.
Пример решения задачи оптимизации СМО.
Рассматривается оптимизация количества торговых точек.
Пусть в торговую
точку поступает продовольственная
продукция с интенсивностью λ = 1 т/сутки;
среднее время хранения t= 1,3 суток. Тогда интенсивность «ухода»
бракованной продукции ω
=
0,75.
Интенсивность продаж, т.е. обслуживания μ = 1 т/сутки. Т.о. μ = λ и составляет одну тонну в сутки.
Решение. СМО является системой с ограниченным временем ожидания.
Определяем параметры ρ и β:
ρ =
= 1
β =
= 0,75
Определяем вероятность Роткпо таблицам Ротк(n,ρ,β). Таблица вероятности отказа системы с ограниченным временем ожидания в очереди представлена в Приложении П7. Согласно таблице зависимость Ротк(n) при ρ = 1 и β = 0,75 имеет следующий вид (табл. 6.1)
Таблица 6.1.
|
n |
1 |
2 |
3 |
4 |
|
Ротк |
0,341 |
0,095 |
0,02 |
0,003 |
Приведенные в табл. 6.1. данные показывают, что с увеличением количества торговых точек процент потерь продукции уменьшается с 34,1% при одной точке до 2% при трех точках. Однако увеличение числа имеющихся торговых точек приводит к увеличению стоимости содержания обслуживающего персонала и повышению накладных расходов. Поэтому проведем экономическую оценку и определим оптимальное количество торговых точек.
Пусть экономические параметры имеют следующее значение:
Затраты на содержание одной торговой точки Сс1= 1000грн/мес.
Стоимость 1 кг продукции: Сn1= 1грн/кг.
Количество доставляемой продукции в месяц: L= 30λ = 30 ∙ 1000 = 30000 кг.
Зависимость стоимости затрат, потерь и суммарной стоимости от количества торговых точек представлена в табл.6.2.
Таблица 6.2.
|
Количество торговых точек n |
1 |
2 |
3 |
4 |
|
Затраты Cc1∙n |
1000 |
2000 |
3000 |
4000 |
|
Потери Cn1∙L∙Pотк |
10200 |
2850 |
600 |
90 |
|
Суммарные издержки |
11200 |
4850 |
3600 |
4090 |
Из результатов, представленных в таблице, следует, что наиболее экономичной является торговая сеть, состоящая из трех точек. Увеличение количества торговых точек с 3 до 4 нецелесообразно, так как снижение процента потерь незначительно (с 2% до 0,3%), а стоимость содержания сети существенно возрастает.
Графически составляющие затрат, потерь и суммарные издержки представлены на рис.6.4.
Рис. 6.4.Оптимизация СМО при целочисленном аргументе
Согласно графику суммарные издержки C(n) имеют минимум при некотором целочисленном значенииn=n*= 3.