ПРИМЕНЕНИЕ СИМПЛЕКС-МЕТОДА И МЕТОДА ИСКУССТВЕННОГО БАЗИСА ПРИ ПРОЕКТИРОВАНИИ БОРТОВОГО ПРИБОРНОГО ОБОРУДОВАНИЯ

ПРИМЕНЕНИЕ СИМПЛЕКС-МЕТОДА И МЕТОДА ИСКУССТВЕННОГО БАЗИСА …

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, a21x1 a22x2 a2nxn  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  cn1 y1  cn2 y2  cnk yk  Cx  Cy  max ,

a11x1  a12 x2   a1n xn  b1, a21x1 a22x2 a2nxn  b2 ,

aamm1211yy11 aamm1222yy22aamm12kkyykkbbmm1,2 ,

am1x1  am2 x2    amn xn  bm , amt1 y1  amt2 y2    amtk yk  bmt ,

(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, a21x1 a22x2 a2nxn  s2  b2 , 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,

при

in

j;

  

zij zij

 0, i  1, 2,, m, j  n 1, n  2,, n  m,  bi , i  1, 2,, m, j  n  m 1;

при

in



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. для элементов разрешающей строки используются зависимости

apj



a pj a pr

,

bp



bp a pr

,

j  1, 2,, n  m ,

(10)

где apj , bp – новые значения пересчитываемых элементов; apj , bp – старые значения

пересчитываемых элементов; apr – значение разрешающего элемента;

2. элементы разрешающего столбца (кроме разрешающего элемента) обнуляются:

apr  0 , cr  0 , i  1, 2,, m , кроме i  p ;

(11)

3. элементы, не принадлежащие разрешающему столбцу и строке, пересчитываются по формулам

aij

 aij



air apj a pr

,

bi  bi



air bp a pr

,

cj

 cj



apj cr a pr

,

L 

L

cr bp a pr

,

i

 1, 2,, m ,

j  1, 2,, n  m ,

(12)

где aij , bi, cj , L – новые значения пересчитываемых элементов; aij , bi , c j , L – старые

значения пересчитываемых элементов.

Блок-схема алгоритма определения параметров x1, x2  xn симплекс-методом приведена на рис. 1, а.

Применение метода искусственного базиса для определения внутренних параметров проектируемого устройства

Методика определения параметров y1, y2 ,, yk с помощью метода искусственного базиса [3, 4]
представлена ниже. 1. Система уравнений (2) приводится к расширенной канонической форме:

f  c1x1  c2 x2    cn xn  cn1 y1  cn2 y2  cnk yk  Ms1  Ms2 

  Msm  Msm1  Msm2   Msmt  max,

a11x1  a12 x2   a1n xn  s1  l1  b1, a21x1 a22x2 a2nxn  s2 l2b2,  am1x1  am2 x2    amn xn  sm  lm  bm ,

aamm1211yy11 aamm1222yy22aamm12kkyykkssmm12lmlm12bmbm1,2, amt1 y1  amt2 y2    amtk yk  smt  lmt  bmt ,

(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 ,

 h1

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 n1, h1

  


f



n
cjxj 

nk,k

mt
c j yh  Cx  Cy  Msi  max,

 j 1

j n1, h1

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)

mt
где d j  avj , j  1, 2,, n  m – сумма коэффициентов системы ограничений, содержащих искусv 1

mt
ственные переменные; 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