close

Вход

Забыли?

вход по аккаунту

?

Методы математического программирования и оптимизации как инструмент управления качеством.

код для вставкиСкачать
Экономика УДК 621.01(07)
МЕТОДЫ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ И ОПТИМИЗАЦИИ КАК
ИНСТРУМЕНТ УПРАВЛЕНИЯ КАЧЕСТВОМ
А.Н.Кононова1
Иркутский государственный университет,
664025, г. Иркутск, Ленина, 3.
Предложен анализ существующих методов математического программирования и оптимизации как инструмент
управления качеством. Показана область применимости в задаче разработки и обеспечения качества нелинейного программирования метода наименьших квадратов. Задача о наименьших квадратах (ЗНК) формируется в
контексте задач нелинейной регрессии.
Библиогр. 7 назв.
Ключевые слова: стандарты семейства ИСО 9000; методы оптимизации; математическое программирование; управление качеством; нелинейное программирование; функция Лагранжа; задача наименьших квадратов; нелинейная регрессия.
METHODS OF MATHEMATICAL PROGRAMMING AND OPTIMIZATION AS A TOOL FOR QUALITY MANAGEMENT
A.N. Kononova
Irkutsk State University,
3, Lenin St., Irkutsk, 664025.
The author proposes an analysis of existing methods of mathematical programming and optimization as a tool for quality
management. The article demonstrates the domain of applicability of the method of least squares in the problem of development and ensuring the quality of non-linear programming. The problem of the least-squares is formed within the
context of nonlinear regression problems.
Keywords: ISO 9000 family of standards; optimization methods; mathematical programming; quality management; nonlinear programming; Lagrangian function; problem of least squares; nonlinear regression.
Методы оптимизации относятся к разделу прикладной математики. В основе математического программирования лежит математический аппарат решения задач оптимизации. Можно указать некоторые
приложения математического программирования в
задачах управления качеством, определяемым требованиями стандартов семейства ИСО 9000:
• оптимизация технико-экономических систем;
• транспортные задачи;
• задачи управления;
• автоматика (распознавание систем, фильтрация, управление технологическими процессами, роботы);
• техника (управление размерами, оптимизация
информационных систем, компьютерных сетей);
• математическая экономика (решение макроэкономических задач, оптимизация моделей предпринимательства);
• теория принятия решений.
Постановка любой задачи оптимизации начинается с определения набора независимых переменных,
определения области допустимых значений для этих
переменных (ограниченные задачи). Обычно оптимизируется скалярная мера качества, которая зависит от
переменных (целевая функция). Решение оптимизационной задачи – приемлемый набор значений переменных, которому отвечает оптимальное решение
целевой функции. Под оптимальным решением пони-
мают максимальность или минимальность целевой
функции.
Общая постановка задач оптимизации [3,5,6]:
найти
орt f (x) , x∈Rn, f(x)∈R1,
x∈X
где x – векторный аргумент, по которому ведется оптимизация; X – область допустимых значений x; f(x) –
целевая функция.
Введем обозначения: opt f(x)=f(x*)=f*, где f* – оптимальное значение целевой функции; x* – значение
аргумента, при котором определяется f*.
Постановка задачи минимизации или максимизации не нарушает общности. min f(x) = max - f(x);X –
определяется функциями ограничения; X={g(x)>=0},
g(x)∈Rm, где m – количество ограничений.
Часто важно различать ограничения неравенства
и строгого равенства (h(x)=0).
По виду решаемой задачи выделяют следующие
разделы математического программирования [3,5]:
1. Линейное программирование (ЛП) – раздел
математического программирования, изучающий задачу поиска минимальной (максимальной) линейной
функции при линейных ограничениях в виде равенств
или неравенств.
2. Нелинейное программирование – раздел математического программирования, изучающий методы
решения и характер экстремума в задачах оптимиза-
___________________________
1
Кононова Алеся Николаевна, кандидат экономических наук, доцент кафедры культурологии и управления социальными
процессами, e-mail: lesya2008@mail.ru
Kononova Alesia, Candidate of Economy, Associate Professor of the Department of Cultural Studies and Management of Social
Processes, e-mail: lesya2008@mail.ru
ВЕСТНИК ИрГТУ №2 (49) 2011 209
Экономика ции с нелинейной целевой функцией и (или) нелинейными ограничениями.
3. Стохастическое программирование – раздел
математического программирования, изучающий модели выбора оптимальных решений в ситуациях, характеризуемых случайными величинами.
Существуют также методы, которые при решении
задач оптимизации учитывают специфику этих задач.
Такие методы превосходят по эффективности общие
алгоритмы и их выделяют в отдельный класс методов
для решения задач специальной структуры.
Можно выделить следующие разделы [3,4]:
1. Целочисленное программирование - решает
задачи оптимизации, в которых на значения переменных наложено требование целочисленности.
2. Квадратичное программирование - решает задачи оптимизации с квадратичной целевой функцией
и линейными ограничениями.
3. Геометрическое программирование – решает
задачи оптимизации, в которых целевая функция и
ограничения представляют собой обобщенные многочлены с положительными коэффициентами.
4. Сепарабельное программирование - решает
задачи оптимизации с сепарабельной целевой функцией и сепарабельными ограничениями.
5. Дробно-линейное программирование - решает
задачи оптимизации с дробно-линейной целевой
функцией и линейными ограничениями.
Нелинейное программирование. В настоящее
время не существует универсальных методов оптимизации, пригодных для решения задач произвольного
вида. В связи с этим ведется работа в направлении
совершенствования и разработок алгоритмов нелинейной оптимизации, которые можно классифицировать [3,6]:
1. По наличию ограничений на методы:
- безусловной оптимизации (найти min f(x),
x∈Rn);
- условной оптимизации (найти min f(x), x∈Rn,
X{gi(x)>=0, i=1…m}).
2. По способу поиска экстремальной точки на методы
- прямого поиска;
- косвенного поиска.
Основным достоинством методов прямого поиска является то, что с их помощью можно решать
задачи с разрывной целевой функцией. Эти методы
основаны на сравнении вычисленных значений f(x) в
различных точках. Однако эти вычисления занимают
много вычислительных ресурсов и часто не позволяют
найти оптимальное решение с необходимой точностью.
Алгоритмы косвенного поиска основаны на
стремлении найти решение задачи оптимизации, не
исследуя промежуточные точки, удаленные от оптимума.
3.По количеству независимых переменных на методы
- по решению одномерных задач;
- по решению многомерных задач.
4.По способу вычисления производных на методы
210
- градиентные;
- квазиградиентные.
Кроме процедур вычисления шага поиска оптимального решения, необходимо определить направление, расчет которого, как правило, базируется на
использовании вектора градиента
S ( k ) = −∇ f ( x ( k ) ).
На практике часто приходится сталкиваться с задачами, целевые функции которых очень сложны и не
всегда бывает возможность аналитически вычислить
частные производные. Тогда можно воспользоваться
конечной разностью аппроксимации градиента.
5.По способу определения направления поиска на
методы
- второго порядка;
- первого порядка.
Среди методов второго порядка наиболее популярны методы, основанные на квадратичной аппроксимации (метод Ньютона). Тогда направление поиска
оптимума определяется с использованием первых и
вторых производных f(x).
Идея методов первого порядка основана на использовании первых производных f(x). Вторые же производные можно заменить на их аппроксимации, вычисленные на каждом шаге итерационного процесса
(квазиньютоновские методы).
S ( k ) = −∇f ( x ( k ) );
S ( k ) = −∇ 2 f ( x ( k ) )∇f ( x ( k ) ).
Необходимые и достаточные условия существования безусловного оптимума. Пусть дана задача безусловной оптимизации: найти min f(x) , x∈R.
Введем обозначения: вектор-градиент функции
f(x)
⎡ ∂f ( x) ∂f ( x) ⎤
...
∇ T f ( x) = ( grad f )T = ⎢
⎥
∂xn ⎦
⎣ ∂x1
– симметричная матрица вторых частных производных (Гессиан).
⎡ ∂ 2 f ( x) ⎤
∇T f ( x ) = G f ( x ) = ⎢
=
⎥
⎢⎣ ∂xi ∂x j ⎥⎦ i , j =1…n
⎡ ∂2 f
∂2 f
∂2 f ⎤
…
⎢
⎥
2
∂x1∂x2
∂x1∂xn ⎥
⎢ ∂x1
⎢ ∂2 f
∂2 f
∂2 f ⎥
…
⎢
⎥
2
= ⎢ ∂x2 ∂x1
∂x2 ∂xn ⎥ .
∂x2
⎢ …
…
…
… ⎥
⎢
⎥
⎢ ∂2 f
∂2 f ⎥
…
…
⎢
⎥
∂xn2 ⎦
⎣ ∂xn ∂x1
Классический подход позволяет определить экстремальные точки в Rn пространстве [4, 7].
Нелинейная задача наименьших квадратов
(НЗНК). Среди задач на поиск безусловного оптимума
особое место занимает задача следующего вида:
ВЕСТНИК ИрГТУ №2 (49) 2011 Экономика Найти
min f(x) =
1 m 2
∑ri (x) =
2 i =1
1
1
2
R(x) 2 = RT (x) R(x) ,
2
2
где R(x) = [ r1 (x)…rm (x)] T∈ Rm
(1)
– нелинейная векторная функция векторного аргумента (1) возникает, например, при настройке математической модели на реальные данные [3].
Под математической моделью понимается некоторая функция ϕ(x,t) с независимым аргументом t и
векторным параметром х.
Предположим, что она предназначена для предсказания некоторой величины y в зависимости от t, и
пусть m фактических значений y при определенных t
измерено, т.е. получена таблица экспериментальных
данных:
(1)
(2)
(l)
y
…
t
y
y
(2)
1
t
t
2
t2
t2
M
M
M
y
(1)
t
m
1
(1)
(1)
tm
1
(2)
(2)
tm
t
…
…
…
…
(l)
t
v = [v1 …vm ]T − множители Лагранжа.
После этого задача условной оптимизации (2)
сводится к задаче безусловной оптимизации: Найти
min L(x,v), x∈Rn, v∈Rm. При этом учитывается, что:
( x, v) − opt argL,
x * - opt argf,
L* = f * .
При использовании условных стационарных точек
справедливы необходимые и достаточные условия
существования экстремумов и седловых точек для
функции Лагранжа:
1. Необходимое условие первого порядка
⎧∇ x L ( x, v) = ∇f ( x) − vT J h ( x) = 0
(4)
⎨
⎩∇ v L ( x, v) = h( x) = 0
1
(l)
t2
M
(l)
tm
Тогда согласование модели с реальностью будет
состоять в том, чтобы подобрать параметр х коэффициента регрессии, при котором
ri ( x) = ϕ ( x , ti ) − yi
.
Если R(x) линейна, то (6.54) представляет линейную задачу о наименьших квадратах (ЛЗНК).
Фактически задача регрессии формируется в виде:
Найти min f(x) =
1 m
∑ (φ ( x , ti ) − yi )2 .
2 i =1
НЗНК тесно связана с ранее рассмотренными задачами. Так, при m=n она может быть интерпретирована как система нелинейных уравнений (СНУ), а для
любого значения m она представляет лишь частный
случай задачи безусловной оптимизации.
Учет ограничений в виде равенств в задачах
оптимизации. Рассмотрим задачу нелинейного программирования [3,8]:
Найти min f(x), x∈X, f(x)∈R2, X{h(x)=0}, h(x)∈Rm (2)
Задача (6.74) может быть решена как задача безусловной оптимизации (при m≤n), если исключить из
целевой функции m независимых переменных с помощью заданных равенств, т.е. задача сводится к виду:
Найти min f(h(x),х), f∈R1 – скалярная величина.
При этом размерность задачи уменьшается с n до
n-m. Однако такой метод применим лишь в тех случаях, когда уравнение-ограничение можно разрешить
относительно некоторого набора независимых пере=
менных.
Более универсальным является метод Лагранжа.
Здесь вводится функция Лагранжа, которая имеет
вид:
L ( x, v ) = f ( x ) − v T h ( x ) ,
(3)
h( x ) = h ( x ) − b = 0,
2. Достаточное условие второго порядка.
Пусть f(x), h(x) – дважды дифференцируемые
функции. Если существуют такие v*, x*, что выполняется (4) и, кроме того, матрица Гессе (функция Лагранжа) ∇ L ( x, v) = G L положительно (отрицательно) определена, то х* – строгий локальный минимум
(максимум).
Большинство практических задач, связанных с оптимизацией качества сложных объектов, характеризуются многими критериями, причем выбрать из них
один как целевую функцию, а остальные рассматривать как ограничения не всегда удается. Трудности
обусловлены противоречивостью критериев, их физическим различием, наличием случайных факторов, а
также ограниченностью или отсутствием информации
о структуре объекта и его функциональных внутренних
взаимосвязях.
Рассмотрим класс задач, в которых качество объекта
оценивается
некоторыми
критериями
f1(x),f2(x),…,fm(x).
Критерии fi(x) являются частными критериями, которые в совокупности образуют векторный критерий.
f(x) = [f1(x),f2(x),…,fm(x)]T – обобщенный критерий
качества.
Таким образом, многокритериальную задачу (задачу векторной оптимизации) можно записать следующим образом:
2
Найти min f(x), f(x) ∈ R m , x ∈ R n
g j ( x) ≥ 0, j = 1,K, J
(5)
При m=1 – задача однокритериальная и является
стандартной задачей условной оптимизации.
При m≥2 поиск решений (6.92) усложняется, т.к. fi
обычно противоречивы и не существует решения х*,
наилучшим образом одновременно удовлетворяющего каждому из критериев.
ВЕСТНИК ИрГТУ №2 (49) 2011 211
Экономика Пусть качество продукции характеризуется критериями f1(х) и f2(х). При максимизации критериев для
f1* → c , для f 2* → d в диапазоне [a,b].
x* = c,
x* = d .
На интервале
a ≤ x ≤ c,
d ≤ x≤b
критерии непротиворечивы, однако, управляя
процессом в этих пределах, нельзя добиться для f1 и f2
удовлетворительных результатов. Оптимальное ре-
шение следует искать в диапазоне с ≤ x ≤ d .
При решении многокритериальных задач часто
используют метод обобщенного критерия. Суть его
сводится к следующему.
Все частные критерии {fi(x)} нормируют, т.е. приводят к сопоставимому безразмерному виду с помощью некоторых преобразований.
zi = ϕi ( f i ( x)), i = 1,K, n.
Обычно преобразования ϕi выбираются таким образом, чтобы новые критерии имели значение в диапазоне [0,1]. Затем zi сворачивают в обобщенный критерий вида
F (α , x ) = F (α 1 ,K , α m , z1 ( x ),K , z m ( x )) ,
который учитывает относительную важность частных
критериев с помощью весовых коэффициентов {αi}.
Обычно αi определяется с помощью методов математической обработки результатов экспертного опроса. Таким образом, исходная задача (5) сводится к
задаче с одним критерием:
Найти min F(α , z), α , z ∈ R m
g ( x) ≥ 0, g(x) ∈ R J .
(6)
Так как свертывание частных критериев можно
проводить различными способами, то задача выбора
свертки носит частный характер. В многокритериальной задаче оптимизации качество объекта считается
тем лучше, чем меньше его fi(x) и F, т.е. необходимо
учитывать требования согласованности и предпочтений по fi(x) и F.
(1)
Векторная оценка { f i ( x )} предпочтительнее,
чем { f i ( x
(2)
)} , если
f i ( x (1) ) ≤ f i ( x ( 2 ) ) и на ка-
ком-либо критерии fк(x) достигается строгое выполнение неравенства:
f k ( x (1) ) ≤ f k ( x ( 2) ).
Качество объекта при х(1) оказывается лучше качества объекта при х(2) и по критерию F, если он представляет собой изотонную функцию, то есть строго
монотонную по каждому fi. Тогда решение задачи (6)
обеспечивает такую векторную оценку fi(х*), которую
нельзя улучшить по всем i-м критериям одновременно.
Во многих случаях задачи о наименьших квадратах (ЗНК) формируются в контексте задач нелинейной
регрессии. В реальных условиях однажды построенная модель требует с течением времени корректировки, то есть адаптации по обновляющейся экспериментальной информации. Тогда необходимы алгоритмы
корректировки модели по поступающей информации.
Библиографический список
ка, 1991.
1. Азаров В.Н., Лаохин Ю.Л. Интегрированные информаци5. Карманов В.Г. Математическое программирование. М.:
онные системы управления качеством. М.: Европ. Центр по
Физматлит, 2000.
качеству, 2002. 64 с.
6. Реклейтис Г., Рейвиндран А., Рэгсдел К. Оптимизация в
2. Антикризисное управление: учебник / ред. Э.М. Коротков .
технике: в 2-х кн. М.: Мир, 1986.
М.,2001. 432 с.
7. Пантелеев А.А. Финансово-экономические аспекты управ3. Аттетков А.В., Галкин С.В., Зарубин В.С. Методы оптимиления инновациями. М.: Европ. Центр по качеству, 2002.
зации: учеб. для студ. втузов. М.: Изд-во МГТУ, 2001.
80 с.
4. Вальков В.М., Вершин В.Е. Автоматизированные системы
управления технологическими процессами. Л.: Политехни-
212
ВЕСТНИК ИрГТУ №2 (49) 2011 
Документ
Категория
Без категории
Просмотров
5
Размер файла
530 Кб
Теги
метод, оптимизация, математические, управления, инструменты, программирование, качество
1/--страниц
Пожаловаться на содержимое документа