ПРИМЕНЕНИЕ СИМПЛЕКС-МЕТОДА И МЕТОДА ИСКУССТВЕННОГО БАЗИСА ПРИ ПРОЕКТИРОВАНИИ БОРТОВОГО ПРИБОРНОГО ОБОРУДОВАНИЯ
ПРИМЕНЕНИЕ СИМПЛЕКС-МЕТОДА И МЕТОДА ИСКУССТВЕННОГО БАЗИСА …
6 СИСТЕМЫ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ
УДК.681.324
ПРИМЕНЕНИЕ СИМПЛЕКС-МЕТОДА И МЕТОДА ИСКУССТВЕННОГО БАЗИСА ПРИ ПРОЕКТИРОВАНИИ БОРТОВОГО ПРИБОРНОГО ОБОРУДОВАНИЯ
М.С. Дейко, И.О. Жаринов
Рассматривается применение методов оптимизации проектных решений (симплекс-метод и метод искусственного базиса) в приборостроении. Приводятся примеры их использования при проектировании бортового приборного оборудования. Ключевые слова: оптимизация, приборостроение, симплекс-метод, метод искусственного базиса.
Введение
Методы оптимизации применяются в различных областях науки и техники, в том числе в авиаци-
онном приборостроении. Оптимизация является одной из важнейших процедур при проектировании.
Под оптимизацией будем понимать процесс получения наиболее удачного расположения органов управ-
ления проектируемого прибора относительно друг друга по заданному критерию. Критерий исходит из
требований стандартов (ГОСТ, ОСТ и др.), технологичности изготовления изделия, требований техниче-
ского задания.
Лицевая панель бортового приборного оборудования состоит из множества функциональных эле-
ментов, которые находятся в непосредственной близости друг от друга. Имеются элементы, с которыми
взаимодействует человек (индикационный экран, функциональные кнопки и др.), такие элементы входят в
состав информационно-управляющего поля кабины пилота. Они должны быть расположены рационально,
должно обеспечиваться удобство сборки прибора на заводе-изготовителе и удобство его эксплуатации.
Для определения параметров конструирования органов управления лицевой панели информаци-
онно-управляющего поля кабины пилота летательного аппарата необходимо решить общую оптимиза-
ционную задачу проектирования extr f x1, x2 xn , где x1, x2 xn – параметры проектируемого уст-
ройства; n – количество этих параметров. Общая задача проектирования решается в два этапа. На первом
этапе определяются внешние параметры (габариты) устройства, на втором определяются внутренние
параметры (расстояния между функциональными элементами устройства). Первый этап разрешается
симплекс-методом, второй этап – методом искусственного базиса. Целевая функция проектирования
первого этапа, описывающая внешний параметр проектируемого устройства, имеет вид
f c1x1 c2 x2 cn xn Cx max ,
a11x1 a12 x2 a1n xn b1, a21x1 a22x2 a2nxn b2 , am1x1 am2 x2 amn xn bm ,
(1)
xj 0, j 1, 2,, n ; bi 0, i 1, 2,, m ,
где x1, x2 xn – параметры расстояния между функциональными элементами проектируемого прибора в
горизонтальной плоскости; Cx – сумма горизонтальных размеров всех функциональных элементов лицевой панели; c1, c2 cn – весовые коэффициенты целевой функции проектирования; a11, a12 amn – коэф-
фициенты системы ограничений; b1,b2 bm – свободные члены системы ограничений; m – количество неравенств в системе. Параметры a, b, c выбираются с использованием экспертных оценок [1].
Целевая функция проектирования второго этапа имеет вид
f c1x1 c2 x2 cn xn cn1 y1 cn2 y2 cnk yk Cx Cy max ,
a11x1 a12 x2 a1n xn b1, a21x1 a22x2 a2nxn b2 ,
aamm1211yy11 aamm1222yy22aamm12kkyykkbbmm1,2 ,
am1x1 am2 x2 amn xn bm , amt1 y1 amt2 y2 amtk yk bmt ,
(2)
xj 0, j 1, 2,, n ; yh 0, h 1, 2,, k ; bi 0, i 1, 2,, m t ,
124
Научно-технический вестник информационных технологий, механики и оптики, 2013, № 1 (83)
М.С. Дейко, И.О. Жаринов
где y1, y2 ,, yk – параметры расстояния между функциональными элементами проектируемого прибора в вертикальной плоскости; Cy – сумма вертикальных размеров всех функциональных элементов лицевой панели; k – количество этих параметров; t – количество уравнений в системе граничных условий для параметров y1, y2 ,, yk . Задача проектирования устройства в этом случае определяется в виде поиска значений параметров x1, x2 xn , y1, y2 ,, yk , удовлетворяющих системам граничных условий (1) и (2), при которых
целевые функции f x1, x2 xn и f y1, y2 ,, yk будут принимать максимальные значения.
Применение симплекс-метода для определения внешних параметров проектируемого устройства в горизонтальной плоскости
В основу симплекс-метода [2] положена идея последовательного улучшения получаемого проект-
ного решения. Опишем методику получения значений параметров x1, x2 xn проектируемого устройства. 1. Система уравнений (1) приводится к канонической форме по правилу
nn
aij x j bi aij x j si bi , i 1, 2,, m ,
j 1 j 1
(3)
где s – дополнительно вводимая переменная. Результат имеет следующий вид:
f c1x1 c2 x2 cn xn Cx max ,
a11x1 a12 x2 a1n xn s1 b1, a21x1 a22x2 a2nxn s2 b2 , am1x1 am2 x2 amn xn sm bm ,
(4)
xj 0, j 1, 2,, n ; si 0, bi 0, i 1, 2,, m .
2. Составляется симплекс-таблица. Форма симплекс-таблицы представлена в табл. 1.
i Базис x1
x2 ... xn
s1
s2 ... sm
bi
1 s1
z11 z12 ... z1n z1(n+1) z1(n+2) ... z1(n+m) z1(n+m+1)
2 s2
z21 z22 ... z2n z2(n+1) z2(n+2) ... z2(n+m) z2(n+m+1)
... ... ... ... ... ...
...
... ... ...
...
m sm
zm1 zm2 ... zmn zm(n+1) zm(n+2) ... zm(n+m) zm(n+m+1)
cj z(m+1)1 z(m+1)2 ... z(m+1)n z(m+1)(n+1) z(m+1)(n+2) ... z(m+1)(n+m) z(m+1)(n+m+1)
Таблица 1. Форма симплекс-таблицы
Начальная симплекс-таблица составляется по следующим правилам:
zij zij
aij , i 1, 2,, m, 1, i 1, 2,, m, j
j 1, 2,, n; n 1, n 2,, n m,
при
in
j;
zij zij
0, i 1, 2,, m, j n 1, n 2,, n m, bi , i 1, 2,, m, j n m 1;
при
in
j;
zij
c j , i m 1,
j 1, 2,, n;
(5)
zij
0, i m 1,
j n 1, n 2,, n m;
zij L, i m 1, j n m 1,
где L – значение целевой функции при текущем базисном проектном решении. Заполненная на-
чальная симплекс-таблица, составленная по правилам (5), имеет вид, представленный в табл. 2.
3. Условие оптимальности проектного решения определяется по критерию
cj 0 , j 1, 2,, n .
(6)
4. Разрешающий столбец определяется по правилу
cmax max c1, c2 ,, cn .
(7)
Значение (7) достигается при j r , где r – номер разрешающего столбца.
5. Достаточное условие получения проектного решения при условии выполнения (6) и (7) имеет
вид
air 0 , i 1, 2,, m .
(8)
Научно-технический вестник информационных технологий, механики и оптики, 2013, № 1 (83)
125
ПРИМЕНЕНИЕ СИМПЛЕКС-МЕТОДА И МЕТОДА ИСКУССТВЕННОГО БАЗИСА …
i Базис
x1
x2 ... xn
s1 s2 ... sm bi
1 s1
a11 a12 ... a1n
1
0 ... 0
b1
2 s2
a21 a22 ... a2n
0
1 ... 0
b2
... ...
...
... ... ...
... ... ... ... ...
m sm am1 am2 ... amn 0 0 ... 1 bm cj c1 c2 ... cn 0 0 ... 0 L
Таблица 2. Общий вид начальной заполненной симплекс-таблицы
6. Для генерации кортежа проектных решений определяется разрешающая строка по правилу
min bi / air , air 0, i 1, 2,, m .
(9)
Минимум (9) достигается при i p , где p – номер разрешающей строки.
7. Переход к новому базисному решению (пересчет элементов симплекс-таблицы) осуществляется по следующим формальным правилам:
1. для элементов разрешающей строки используются зависимости
apj
a pj a pr
,
bp
bp a pr
,
j 1, 2,, n m ,
(10)
где apj , bp – новые значения пересчитываемых элементов; apj , bp – старые значения
пересчитываемых элементов; apr – значение разрешающего элемента;
2. элементы разрешающего столбца (кроме разрешающего элемента) обнуляются:
apr 0 , cr 0 , i 1, 2,, m , кроме i p ;
(11)
3. элементы, не принадлежащие разрешающему столбцу и строке, пересчитываются по формулам
aij
aij
air apj a pr
,
bi bi
air bp a pr
,
cj
cj
apj cr a pr
,
L
L
cr bp a pr
,
i
1, 2,, m ,
j 1, 2,, n m ,
(12)
где aij , bi, cj , L – новые значения пересчитываемых элементов; aij , bi , c j , L – старые
значения пересчитываемых элементов.
Блок-схема алгоритма определения параметров x1, x2 xn симплекс-методом приведена на рис. 1, а.
Применение метода искусственного базиса для определения внутренних параметров проектируемого устройства
Методика определения параметров y1, y2 ,, yk с помощью метода искусственного базиса [3, 4]
представлена ниже. 1. Система уравнений (2) приводится к расширенной канонической форме:
f c1x1 c2 x2 cn xn cn1 y1 cn2 y2 cnk yk Ms1 Ms2
Msm Msm1 Msm2 Msmt max,
a11x1 a12 x2 a1n xn s1 l1 b1, a21x1 a22x2 a2nxn s2 l2b2, am1x1 am2 x2 amn xn sm lm bm ,
aamm1211yy11 aamm1222yy22aamm12kkyykkssmm12lmlm12bmbm1,2, amt1 y1 amt2 y2 amtk yk smt lmt bmt ,
(13)
xj 0, j 1, 2,, n ; yh 0, h 1, 2,, k ; si 0, bi 0, li 0, i 1, 2,, m t ;
по правилам:
126
Научно-технический вестник информационных технологий, механики и оптики, 2013, № 1 (83)
М.С. Дейко, И.О. Жаринов
n
aij x j bi
n
aij x j si li bi ,
i 1, 2,, m,
j 1
j 1
k
aih y j bi
n
aij y j si li bi ,
i m 1, m 2,, m t ,
h1
j 1
n n
j 1
aij
x
j
bi
aij x j
j 1
li
bi ,
i 1, 2,, m ,
k n
aih y
h 1
n
f
j
c
bi
n
jxj
aij y j
j 1
k,k
c j yh
li
bi , Cx
C
i
y
m 1, max
m
2,
,
m
t
,
j 1
j n1, h1
f
n
cjxj
nk,k
mt
c j yh Cx Cy Msi max,
j 1
j n1, h1
i 1
(14)
где М>>1; l – вспомогательные переменные.
2. Составляется симплекс-таблица. Правила составления симплекс-таблицы аналогичны (5), за исключением дополнительно вводимой (m+2)-ой строки. Правила заполнения (m+2)-ой строки симплекс-таблицы имеют вид
zij d j , i m t 2, j 1, 2,, n m,
zij
G, i m t 2,
j n m 1,
(15)
mt
где d j avj , j 1, 2,, n m – сумма коэффициентов системы ограничений, содержащих искусv 1
mt
ственные переменные; G bv – сумма всех свободных членов системы ограничений, содерv 1
жащих искусственные переменные, взятая с обратным знаком.
3. Условия оптимальности проектного решения определяются по критериям
d j 0 , j 1, 2,, n m ,
(16)
cj 0 , j 1, 2,, n m .
(17)
4. Переменная, вводимая в базис (разрешающий столбец симплекс-таблицы) определяется как
max d j , j 1, 2,, n m .
(18)
Значение (18) достигается при j r , где r – номер разрешающего столбца.
5. Достаточное условие получения проектного решения при условии выполнения критериев (16) и
(17) имеет вид
air 0 , i 1, 2,, m t .
(19)
6. Для генерации кортежа проектных решений определяется переменная, исключаемая из базиса
(разрешающая строка симплекс-таблицы):
min bi / air , air 0, i 1, 2,, m t .
Минимум (20) достигается при i p , где p – номер разрешающей строки.
(20)
7. Переменная, вводимая в базис (разрешающий столбец симплекс-таблицы), определяется как
max cj , j 1, 2,, n m .
(21)
Значение (21) достигается при j r , где r – номер разрешающего столбца.
8. Достаточное условие получения проектного решения при условии выполнения критериев (4) и
(5) имеет вид
air 0 , i 1, 2,, m t .
(22)
9. Для генерации кортежа проектных решений определяется переменная, исключаемая из базиса
(разрешающая строка симплекс-таблицы):
min bi / air , air 0, i 1, 2,, m t .
Минимум (23) достигается при i p , где p – номер разрешающей строки.
(23)
d j
dj
apj dr a pr
,
G
G
cr bp a pr
,
j 1, 2,, n m ,
(24)
Научно-технический вестник информационных технологий, механики и оптики, 2013, № 1 (83)
127
ПРИМЕНЕНИЕ СИМПЛЕКС-МЕТОДА И МЕТОДА ИСКУССТВЕННОГО БАЗИСА …
где d j ,G – новые значения пересчитываемых элементов; d j , G – старые значения пересчитываемых
элементов. Блок-схема алгоритма определения параметров y1, y2 ,, yk проектируемого устройства методом искусственного базиса приведен на рис. 1, б.
Начало
Ввод параметров a, b, c
Приведение системы (1) к канонической форме
(4) по правилу (3)
Составление симплекс таблицы по правилам (5)
Начало
Ввод параметров a, b, c
Приведение системы (2) к расширенной канонической форме (14) по правилам (13)
Конец
Вывод значений x1,x2,…,xn. y1,y2,…,yk.
Да Проверка условия (6)
Нет решение оптимально по критерию (6) и задача решена
Вывод значений x1,x2,…,xn.
Составление симплекс таблицы по правилам (15)
Решение оптимально по критериям (16) и (17), задача решена
Да
Проверка
Да Проверка
условия (16)
условия (17)
Нет
Определение разрешающего столбца
r по правилу (18)
Нет
Определение разрешающего столбца
r по правилу (21)
Конец
Определение разрешающего столбца r по правилу (7)
Проверка условия (8)
Нет
Да
целевая функция (1) не ограничена и решения нет
Проверка условия (19)
Нет Нет
Проверка условия (22)
Да
Определение разрешающей строки p
по правилу (20)
Да
Определение разрешающей строки p
по правилу (23)
Целевая функция (2) не ограничена. Решения нет
Конец
Конец
Определение разрешающего столбца p по правилу (9)
Переход к новому базисному решению по формулам (10), (11), (12)
Переход к новому базисному решению по
правилам (10), (11), (12), (24)
аб Рис. 1. Блок-схема алгоритмов для задачи проектирования бортового приборного оборудования:
симплекс-метода (а); метода искусственного базиса (б)
10. Переход к новому базисному решению (пересчет элементов симплекс-таблицы) осуществляет-
ся последовательно по правилам (10)–(12) и по правилу:
d j
dj
apj dr a pr
,
G
G
cr bp a pr
,
j 1, 2,, n m ,
(24)
128
Научно-технический вестник информационных технологий, механики и оптики, 2013, № 1 (83)
Д.А. Киров, А.А. Ожиганов
где d j ,G – новые значения пересчитываемых элементов; d j , G – старые значения пересчитываемых элементов. Блок-схема алгоритма определения параметров y1, y2 ,, yk проектируемого устройства методом искусственного базиса приведен на рис. 1, б.
Заключение
Симплекс-метод и метод искусственного базиса были применены на практике в ФГУП «СПб ОКБ «Электроавтоматика» им П.А. Ефимова» в процессе проектирования бортового пульта управления и индикации, входящего в состав информационно-управляющего поля кабины пилота летательного аппарата. В результате решения системы уравнений (1) симплекс-методом и системы уравнений (2) методом искусственного базиса определены значения рабочих параметров проектирования прибора (рис. 2): x1=5 мм; x2=4 мм; y1=8 мм; y2=14 мм; y3=12 мм.
y1
x1 x2 Xкн Yкн
y2
Yэк Экран
y3
Рис. 2. Фрагмент лицевой панели пульта управления и индикации информационно-управляющего поля кабины пилота (Xкн – горизонтальный размер кнопки;
Yкн – вертикальный размер кнопки; Yэк – вертикальный размер экрана)
Проанализировав приведенные методы оптимизации и результаты расчетов на их основе, можно сказать, что они применяются при различных вариантах граничных условиях. Симплекс-метод применяется, когда в условиях проектной задачи в системе уравнений (1) содержится только отношение предпочтения вида «≤». Метод искусственного базиса используется, когда в условиях системы уравнений (2) присутствуют отношения предпочтения «≥» и «=» между левой и правой частями уравнений.
Литература
1. Гатчин Ю.А., Жаринов И.О. Основы проектирования вычислительных систем интегрированной модульной авионики: монография. – М.: Машиностроение, 2010. – 224 с.
2. Экономико-математические методы. Линейное программирование [Электронный ресурс]. – Режим доступа: http://emm.ostu.ru/lect/lect2_2.html, свободный. Яз. рус. (дата обращения 14.05.2012).
3. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1986. – 319 с.
4. Ермаков В.И. Общий курс высшей математики для экономистов. – М.: ИНФРА-М, 2007. – 656 с.
Дейко Михаил Сергеевич Жаринов Игорь Олегович
– Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, магистрант, MadCat_MKII@mail.ru
– ФГУП «СПб ОКБ «Электроавтоматика» имени П.А. Ефимова», доктор технических наук, доцент, руководитель учебно-научного центра, igor_rabota@pisem.net
Научно-технический вестник информационных технологий, механики и оптики, 2013, № 1 (83)
129
6 СИСТЕМЫ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ
УДК.681.324
ПРИМЕНЕНИЕ СИМПЛЕКС-МЕТОДА И МЕТОДА ИСКУССТВЕННОГО БАЗИСА ПРИ ПРОЕКТИРОВАНИИ БОРТОВОГО ПРИБОРНОГО ОБОРУДОВАНИЯ
М.С. Дейко, И.О. Жаринов
Рассматривается применение методов оптимизации проектных решений (симплекс-метод и метод искусственного базиса) в приборостроении. Приводятся примеры их использования при проектировании бортового приборного оборудования. Ключевые слова: оптимизация, приборостроение, симплекс-метод, метод искусственного базиса.
Введение
Методы оптимизации применяются в различных областях науки и техники, в том числе в авиаци-
онном приборостроении. Оптимизация является одной из важнейших процедур при проектировании.
Под оптимизацией будем понимать процесс получения наиболее удачного расположения органов управ-
ления проектируемого прибора относительно друг друга по заданному критерию. Критерий исходит из
требований стандартов (ГОСТ, ОСТ и др.), технологичности изготовления изделия, требований техниче-
ского задания.
Лицевая панель бортового приборного оборудования состоит из множества функциональных эле-
ментов, которые находятся в непосредственной близости друг от друга. Имеются элементы, с которыми
взаимодействует человек (индикационный экран, функциональные кнопки и др.), такие элементы входят в
состав информационно-управляющего поля кабины пилота. Они должны быть расположены рационально,
должно обеспечиваться удобство сборки прибора на заводе-изготовителе и удобство его эксплуатации.
Для определения параметров конструирования органов управления лицевой панели информаци-
онно-управляющего поля кабины пилота летательного аппарата необходимо решить общую оптимиза-
ционную задачу проектирования extr f x1, x2 xn , где x1, x2 xn – параметры проектируемого уст-
ройства; n – количество этих параметров. Общая задача проектирования решается в два этапа. На первом
этапе определяются внешние параметры (габариты) устройства, на втором определяются внутренние
параметры (расстояния между функциональными элементами устройства). Первый этап разрешается
симплекс-методом, второй этап – методом искусственного базиса. Целевая функция проектирования
первого этапа, описывающая внешний параметр проектируемого устройства, имеет вид
f c1x1 c2 x2 cn xn Cx max ,
a11x1 a12 x2 a1n xn b1, a21x1 a22x2 a2nxn b2 , am1x1 am2 x2 amn xn bm ,
(1)
xj 0, j 1, 2,, n ; bi 0, i 1, 2,, m ,
где x1, x2 xn – параметры расстояния между функциональными элементами проектируемого прибора в
горизонтальной плоскости; Cx – сумма горизонтальных размеров всех функциональных элементов лицевой панели; c1, c2 cn – весовые коэффициенты целевой функции проектирования; a11, a12 amn – коэф-
фициенты системы ограничений; b1,b2 bm – свободные члены системы ограничений; m – количество неравенств в системе. Параметры a, b, c выбираются с использованием экспертных оценок [1].
Целевая функция проектирования второго этапа имеет вид
f c1x1 c2 x2 cn xn cn1 y1 cn2 y2 cnk yk Cx Cy max ,
a11x1 a12 x2 a1n xn b1, a21x1 a22x2 a2nxn b2 ,
aamm1211yy11 aamm1222yy22aamm12kkyykkbbmm1,2 ,
am1x1 am2 x2 amn xn bm , amt1 y1 amt2 y2 amtk yk bmt ,
(2)
xj 0, j 1, 2,, n ; yh 0, h 1, 2,, k ; bi 0, i 1, 2,, m t ,
124
Научно-технический вестник информационных технологий, механики и оптики, 2013, № 1 (83)
М.С. Дейко, И.О. Жаринов
где y1, y2 ,, yk – параметры расстояния между функциональными элементами проектируемого прибора в вертикальной плоскости; Cy – сумма вертикальных размеров всех функциональных элементов лицевой панели; k – количество этих параметров; t – количество уравнений в системе граничных условий для параметров y1, y2 ,, yk . Задача проектирования устройства в этом случае определяется в виде поиска значений параметров x1, x2 xn , y1, y2 ,, yk , удовлетворяющих системам граничных условий (1) и (2), при которых
целевые функции f x1, x2 xn и f y1, y2 ,, yk будут принимать максимальные значения.
Применение симплекс-метода для определения внешних параметров проектируемого устройства в горизонтальной плоскости
В основу симплекс-метода [2] положена идея последовательного улучшения получаемого проект-
ного решения. Опишем методику получения значений параметров x1, x2 xn проектируемого устройства. 1. Система уравнений (1) приводится к канонической форме по правилу
nn
aij x j bi aij x j si bi , i 1, 2,, m ,
j 1 j 1
(3)
где s – дополнительно вводимая переменная. Результат имеет следующий вид:
f c1x1 c2 x2 cn xn Cx max ,
a11x1 a12 x2 a1n xn s1 b1, a21x1 a22x2 a2nxn s2 b2 , am1x1 am2 x2 amn xn sm bm ,
(4)
xj 0, j 1, 2,, n ; si 0, bi 0, i 1, 2,, m .
2. Составляется симплекс-таблица. Форма симплекс-таблицы представлена в табл. 1.
i Базис x1
x2 ... xn
s1
s2 ... sm
bi
1 s1
z11 z12 ... z1n z1(n+1) z1(n+2) ... z1(n+m) z1(n+m+1)
2 s2
z21 z22 ... z2n z2(n+1) z2(n+2) ... z2(n+m) z2(n+m+1)
... ... ... ... ... ...
...
... ... ...
...
m sm
zm1 zm2 ... zmn zm(n+1) zm(n+2) ... zm(n+m) zm(n+m+1)
cj z(m+1)1 z(m+1)2 ... z(m+1)n z(m+1)(n+1) z(m+1)(n+2) ... z(m+1)(n+m) z(m+1)(n+m+1)
Таблица 1. Форма симплекс-таблицы
Начальная симплекс-таблица составляется по следующим правилам:
zij zij
aij , i 1, 2,, m, 1, i 1, 2,, m, j
j 1, 2,, n; n 1, n 2,, n m,
при
in
j;
zij zij
0, i 1, 2,, m, j n 1, n 2,, n m, bi , i 1, 2,, m, j n m 1;
при
in
j;
zij
c j , i m 1,
j 1, 2,, n;
(5)
zij
0, i m 1,
j n 1, n 2,, n m;
zij L, i m 1, j n m 1,
где L – значение целевой функции при текущем базисном проектном решении. Заполненная на-
чальная симплекс-таблица, составленная по правилам (5), имеет вид, представленный в табл. 2.
3. Условие оптимальности проектного решения определяется по критерию
cj 0 , j 1, 2,, n .
(6)
4. Разрешающий столбец определяется по правилу
cmax max c1, c2 ,, cn .
(7)
Значение (7) достигается при j r , где r – номер разрешающего столбца.
5. Достаточное условие получения проектного решения при условии выполнения (6) и (7) имеет
вид
air 0 , i 1, 2,, m .
(8)
Научно-технический вестник информационных технологий, механики и оптики, 2013, № 1 (83)
125
ПРИМЕНЕНИЕ СИМПЛЕКС-МЕТОДА И МЕТОДА ИСКУССТВЕННОГО БАЗИСА …
i Базис
x1
x2 ... xn
s1 s2 ... sm bi
1 s1
a11 a12 ... a1n
1
0 ... 0
b1
2 s2
a21 a22 ... a2n
0
1 ... 0
b2
... ...
...
... ... ...
... ... ... ... ...
m sm am1 am2 ... amn 0 0 ... 1 bm cj c1 c2 ... cn 0 0 ... 0 L
Таблица 2. Общий вид начальной заполненной симплекс-таблицы
6. Для генерации кортежа проектных решений определяется разрешающая строка по правилу
min bi / air , air 0, i 1, 2,, m .
(9)
Минимум (9) достигается при i p , где p – номер разрешающей строки.
7. Переход к новому базисному решению (пересчет элементов симплекс-таблицы) осуществляется по следующим формальным правилам:
1. для элементов разрешающей строки используются зависимости
apj
a pj a pr
,
bp
bp a pr
,
j 1, 2,, n m ,
(10)
где apj , bp – новые значения пересчитываемых элементов; apj , bp – старые значения
пересчитываемых элементов; apr – значение разрешающего элемента;
2. элементы разрешающего столбца (кроме разрешающего элемента) обнуляются:
apr 0 , cr 0 , i 1, 2,, m , кроме i p ;
(11)
3. элементы, не принадлежащие разрешающему столбцу и строке, пересчитываются по формулам
aij
aij
air apj a pr
,
bi bi
air bp a pr
,
cj
cj
apj cr a pr
,
L
L
cr bp a pr
,
i
1, 2,, m ,
j 1, 2,, n m ,
(12)
где aij , bi, cj , L – новые значения пересчитываемых элементов; aij , bi , c j , L – старые
значения пересчитываемых элементов.
Блок-схема алгоритма определения параметров x1, x2 xn симплекс-методом приведена на рис. 1, а.
Применение метода искусственного базиса для определения внутренних параметров проектируемого устройства
Методика определения параметров y1, y2 ,, yk с помощью метода искусственного базиса [3, 4]
представлена ниже. 1. Система уравнений (2) приводится к расширенной канонической форме:
f c1x1 c2 x2 cn xn cn1 y1 cn2 y2 cnk yk Ms1 Ms2
Msm Msm1 Msm2 Msmt max,
a11x1 a12 x2 a1n xn s1 l1 b1, a21x1 a22x2 a2nxn s2 l2b2, am1x1 am2 x2 amn xn sm lm bm ,
aamm1211yy11 aamm1222yy22aamm12kkyykkssmm12lmlm12bmbm1,2, amt1 y1 amt2 y2 amtk yk smt lmt bmt ,
(13)
xj 0, j 1, 2,, n ; yh 0, h 1, 2,, k ; si 0, bi 0, li 0, i 1, 2,, m t ;
по правилам:
126
Научно-технический вестник информационных технологий, механики и оптики, 2013, № 1 (83)
М.С. Дейко, И.О. Жаринов
n
aij x j bi
n
aij x j si li bi ,
i 1, 2,, m,
j 1
j 1
k
aih y j bi
n
aij y j si li bi ,
i m 1, m 2,, m t ,
h1
j 1
n n
j 1
aij
x
j
bi
aij x j
j 1
li
bi ,
i 1, 2,, m ,
k n
aih y
h 1
n
f
j
c
bi
n
jxj
aij y j
j 1
k,k
c j yh
li
bi , Cx
C
i
y
m 1, max
m
2,
,
m
t
,
j 1
j n1, h1
f
n
cjxj
nk,k
mt
c j yh Cx Cy Msi max,
j 1
j n1, h1
i 1
(14)
где М>>1; l – вспомогательные переменные.
2. Составляется симплекс-таблица. Правила составления симплекс-таблицы аналогичны (5), за исключением дополнительно вводимой (m+2)-ой строки. Правила заполнения (m+2)-ой строки симплекс-таблицы имеют вид
zij d j , i m t 2, j 1, 2,, n m,
zij
G, i m t 2,
j n m 1,
(15)
mt
где d j avj , j 1, 2,, n m – сумма коэффициентов системы ограничений, содержащих искусv 1
mt
ственные переменные; G bv – сумма всех свободных членов системы ограничений, содерv 1
жащих искусственные переменные, взятая с обратным знаком.
3. Условия оптимальности проектного решения определяются по критериям
d j 0 , j 1, 2,, n m ,
(16)
cj 0 , j 1, 2,, n m .
(17)
4. Переменная, вводимая в базис (разрешающий столбец симплекс-таблицы) определяется как
max d j , j 1, 2,, n m .
(18)
Значение (18) достигается при j r , где r – номер разрешающего столбца.
5. Достаточное условие получения проектного решения при условии выполнения критериев (16) и
(17) имеет вид
air 0 , i 1, 2,, m t .
(19)
6. Для генерации кортежа проектных решений определяется переменная, исключаемая из базиса
(разрешающая строка симплекс-таблицы):
min bi / air , air 0, i 1, 2,, m t .
Минимум (20) достигается при i p , где p – номер разрешающей строки.
(20)
7. Переменная, вводимая в базис (разрешающий столбец симплекс-таблицы), определяется как
max cj , j 1, 2,, n m .
(21)
Значение (21) достигается при j r , где r – номер разрешающего столбца.
8. Достаточное условие получения проектного решения при условии выполнения критериев (4) и
(5) имеет вид
air 0 , i 1, 2,, m t .
(22)
9. Для генерации кортежа проектных решений определяется переменная, исключаемая из базиса
(разрешающая строка симплекс-таблицы):
min bi / air , air 0, i 1, 2,, m t .
Минимум (23) достигается при i p , где p – номер разрешающей строки.
(23)
d j
dj
apj dr a pr
,
G
G
cr bp a pr
,
j 1, 2,, n m ,
(24)
Научно-технический вестник информационных технологий, механики и оптики, 2013, № 1 (83)
127
ПРИМЕНЕНИЕ СИМПЛЕКС-МЕТОДА И МЕТОДА ИСКУССТВЕННОГО БАЗИСА …
где d j ,G – новые значения пересчитываемых элементов; d j , G – старые значения пересчитываемых
элементов. Блок-схема алгоритма определения параметров y1, y2 ,, yk проектируемого устройства методом искусственного базиса приведен на рис. 1, б.
Начало
Ввод параметров a, b, c
Приведение системы (1) к канонической форме
(4) по правилу (3)
Составление симплекс таблицы по правилам (5)
Начало
Ввод параметров a, b, c
Приведение системы (2) к расширенной канонической форме (14) по правилам (13)
Конец
Вывод значений x1,x2,…,xn. y1,y2,…,yk.
Да Проверка условия (6)
Нет решение оптимально по критерию (6) и задача решена
Вывод значений x1,x2,…,xn.
Составление симплекс таблицы по правилам (15)
Решение оптимально по критериям (16) и (17), задача решена
Да
Проверка
Да Проверка
условия (16)
условия (17)
Нет
Определение разрешающего столбца
r по правилу (18)
Нет
Определение разрешающего столбца
r по правилу (21)
Конец
Определение разрешающего столбца r по правилу (7)
Проверка условия (8)
Нет
Да
целевая функция (1) не ограничена и решения нет
Проверка условия (19)
Нет Нет
Проверка условия (22)
Да
Определение разрешающей строки p
по правилу (20)
Да
Определение разрешающей строки p
по правилу (23)
Целевая функция (2) не ограничена. Решения нет
Конец
Конец
Определение разрешающего столбца p по правилу (9)
Переход к новому базисному решению по формулам (10), (11), (12)
Переход к новому базисному решению по
правилам (10), (11), (12), (24)
аб Рис. 1. Блок-схема алгоритмов для задачи проектирования бортового приборного оборудования:
симплекс-метода (а); метода искусственного базиса (б)
10. Переход к новому базисному решению (пересчет элементов симплекс-таблицы) осуществляет-
ся последовательно по правилам (10)–(12) и по правилу:
d j
dj
apj dr a pr
,
G
G
cr bp a pr
,
j 1, 2,, n m ,
(24)
128
Научно-технический вестник информационных технологий, механики и оптики, 2013, № 1 (83)
Д.А. Киров, А.А. Ожиганов
где d j ,G – новые значения пересчитываемых элементов; d j , G – старые значения пересчитываемых элементов. Блок-схема алгоритма определения параметров y1, y2 ,, yk проектируемого устройства методом искусственного базиса приведен на рис. 1, б.
Заключение
Симплекс-метод и метод искусственного базиса были применены на практике в ФГУП «СПб ОКБ «Электроавтоматика» им П.А. Ефимова» в процессе проектирования бортового пульта управления и индикации, входящего в состав информационно-управляющего поля кабины пилота летательного аппарата. В результате решения системы уравнений (1) симплекс-методом и системы уравнений (2) методом искусственного базиса определены значения рабочих параметров проектирования прибора (рис. 2): x1=5 мм; x2=4 мм; y1=8 мм; y2=14 мм; y3=12 мм.
y1
x1 x2 Xкн Yкн
y2
Yэк Экран
y3
Рис. 2. Фрагмент лицевой панели пульта управления и индикации информационно-управляющего поля кабины пилота (Xкн – горизонтальный размер кнопки;
Yкн – вертикальный размер кнопки; Yэк – вертикальный размер экрана)
Проанализировав приведенные методы оптимизации и результаты расчетов на их основе, можно сказать, что они применяются при различных вариантах граничных условиях. Симплекс-метод применяется, когда в условиях проектной задачи в системе уравнений (1) содержится только отношение предпочтения вида «≤». Метод искусственного базиса используется, когда в условиях системы уравнений (2) присутствуют отношения предпочтения «≥» и «=» между левой и правой частями уравнений.
Литература
1. Гатчин Ю.А., Жаринов И.О. Основы проектирования вычислительных систем интегрированной модульной авионики: монография. – М.: Машиностроение, 2010. – 224 с.
2. Экономико-математические методы. Линейное программирование [Электронный ресурс]. – Режим доступа: http://emm.ostu.ru/lect/lect2_2.html, свободный. Яз. рус. (дата обращения 14.05.2012).
3. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1986. – 319 с.
4. Ермаков В.И. Общий курс высшей математики для экономистов. – М.: ИНФРА-М, 2007. – 656 с.
Дейко Михаил Сергеевич Жаринов Игорь Олегович
– Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, магистрант, MadCat_MKII@mail.ru
– ФГУП «СПб ОКБ «Электроавтоматика» имени П.А. Ефимова», доктор технических наук, доцент, руководитель учебно-научного центра, igor_rabota@pisem.net
Научно-технический вестник информационных технологий, механики и оптики, 2013, № 1 (83)
129