Дискретная оптимизация. Чернышова Г.Д - 32 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

32
I
i , ɝɞɟ I — ɦɧɨɠɟɫɬɜɨ ɛɚɡɢɫɧɵɯ ɩɟɪɟɦɟɧɧɵɯ, J — ɦɧɨɠɟɫɬɜɨ ɧɟɛɚɡɢɫ-
ɧɵɯ ɩɟɪɟɦɟɧɧɵɯ ɡɚɞɚɱɢ,
i
b
ɢ
ij
a — ɩɟɪɟɫɱɢɬɚɧɧɵɟ ɤ ɞɚɧɧɨɦɭ ɲɚɝɭ ɡɧɚɱɟ-
ɧɢɹ
i
b
ɢ
ij
a .
ȼɵɛɟɪɟɦ ɢɧɞɟɤɫ
I
i ɬɚɤɨɣ, ɱɬɨ ɛɚɡɢɫɧɚɹ ɤɨɨɪɞɢɧɚɬɚ
ii
bx
— ɞɪɨɛ-
ɧɚɹ. ɉɨ ɨɩɪɟɞɟɥɟɧɢɸ ɰɟɥɨɣ ɱɚɫɬɢ ɱɢɫɥɚ ɢɦɟɟɦ: ][
yy t . Ɍɚɤ ɤɚɤ jx
j
t ,0,
ɬɨ
¦¦
t
Jj
jij
Jj
jij
xaxa ][. ɋɥɟɞɨɜɚɬɟɥɶɧɨ, ɫ ɭɱɟɬɨɦ ɪɚɜɟɧɫɬɜɚ (4.5) ɢɦɟɟɦ:
¦
t
Jj
jijii
xaxb ][
. ȿɫɥɢ ɩɟɪɟɦɟɧɧɵɟ
njx
j
,1, =
, ɬɨ ɩɨɫɥɟɞɧɟɟ ɧɟɪɚɜɟɧ-
ɫɬɜɨ ɦɨɠɧɨ ɩɟɪɟɩɢɫɚɬɶ ɬɚɤ:
¦
t
Jj
jijii
xaxb .][][ (4.6)
ȼɵɱɢɬɚɹ ɢɡ ɪɚɜɟɧɫɬɜɚ (3.5) ɧɟɪɚɜɟɧɫɬɜɨ (3.6), ɩɨɥɭɱɚɟɦ ɧɟɪɚɜɟɧɫɬɜɨ
¦
d
Jj
jiji
xab ,}{}{
(4.7)
ɝɞɟ ɫɢɦɜɨɥɨɦ {y} ɨɛɨɡɧɚɱɟɧɚ ɞɪɨɛɧɚɹ ɱɚɫɬɶ ɱɢɫɥɚ y. ɇɟɪɚɜɟɧɫɬɜɨ (4.7) ɜɟɪ-
ɧɨ ɞɥɹ ɜɫɟɯ ɞɨɩɭɫɬɢɦɵɯ ɰɟɥɵɯ ɬɨɱɟɤ ɜ ɡɚɞɚɱɟ (4.1) — (4.3). Ɉɞɧɚɤɨ ɤɨɨɪ-
ɞɢɧɚɬɵ ɩɨɥɭɱɟɧɧɨɝɨ ɧɟɰɟɥɨɱɢɫɥɟɧɧɨɝɨ ɪɟɲɟɧɢɹ ɧɟ ɭɞɨɜɥɟɬɜɨɪɹɸɬ ɷɬɨɦɭ
ɨɝɪɚɧɢɱɟɧɢɸ, ɬɚɤ ɤɚɤ ɞɥɹ ɧɟɝɨ ɜɫɟ ɧɟɛɚɡɢɫɧɵɟ ɩɟɪɟɦɟɧɧɵɟ Jjx
j
,0, ɢ,
ɫɥɟɞɨɜɚɬɟɥɶɧɨ,
0}{ d
i
b
, ɱɬɨ ɧɟɜɨɡɦɨɠɧɨ ɞɥɹ ɧɟɰɟɥɨɝɨ ɱɢɫɥɚ ɩɨ ɨɩɪɟɞɟɥɟ-
ɧɢɸ ɞɪɨɛɧɨɣ ɱɚɫɬɢ.
ɇɟɪɚɜɟɧɫɬɜɨ (4.7) ɦɨɠɟɬ ɛɵɬɶ ɢɫɩɨɥɶɡɨɜɚɧɨ ɞɥɹ ɞɨɩɨɥɧɢɬɟɥɶɧɨɝɨ ɨɬ-
ɫɟɤɚɸɳɟɝɨ ɨɝɪɚɧɢɱɟɧɢɹ. ȼ ɩɪɢɜɟɞɟɧɧɭɸ ɤ ɤɚɧɨɧɢɱɟɫɤɨɣ ɮɨɪɦɟ ɡɚɞɚɱɭ ɟɝɨ
ɜɜɨɞɹɬ ɜ ɜɢɞɟ
¦
Jj
imnjij
bxxa },{}{
1
(4.8)
ɝɞɟ
1mn
x
– ɞɨɩɨɥɧɢɬɟɥɶɧɚɹ ɩɟɪɟɦɟɧɧɚɹ (ɩɨɫɥɟ ɩɪɢɜɟɞɟɧɢɹ ɡɚɞɚɱɢ (4.1) – (4.3)
ɤ ɤɚɧɨɧɢɱɟɫɤɨɦɭ ɜɢɞɭ ɩɟɪɟɦɟɧɧɵɯ ɜ ɧɟɣ ɛɭɞɟɬ
mn
).
4.2. Ⱥɥɝɨɪɢɬɦɢɱɟɫɤɚɹ ɫɯɟɦɚ ɦɟɬɨɞɚ
ɒɚɝ 1.
ɇɚɣɬɢ ɬɨɱɤɭ
1
x
— ɪɟɲɟɧɢɟ ɡɚɞɚɱɢ ɥɢɧɟɣɧɨɝɨ ɩɪɨɝɪɚɦɦɢɪɨɜɚɧɢɹ
(4.1) – (4.3) (ɛɟɡ ɭɫɥɨɜɢɹ ɰɟɥɨɱɢɫɥɟɧɧɨɫɬɢ). ɉɨɥɨɠɢɬɶ ɤ = 1.
ɒɚɝ 2. ȿɫɥɢ
k
x
— ɰɟɥɨɱɢɫɥɟɧɧɚɹ, ɬɨ ɪɟɲɟɧɢɟ ɧɚɣɞɟɧɨ, ɨɫɬɚɧɨɜ. ɂɧɚɱɟ
ɡɚɮɢɤɫɢɪɨɜɚɬɶ ɦɧɨɠɟɫɬɜɚ I ɢ J — ɢɧɞɟɤɫɨɜ ɛɚɡɢɫɧɵɯ ɢ ɧɟɛɚɡɢɫɧɵɯ ɩɟɪɟ-
ɦɟɧɧɵɯ.
ɒɚɝ 3. ȼɵɛɪɚɬɶ ɧɨɦɟɪ
I
i ɬɚɤɨɣ, ɱɬɨ ɤɨɨɪɞɢɧɚɬɚ
k
i
x
— ɞɪɨɛɧɚɹ.
ɒɚɝ 4. Ⱦɨɛɚɜɢɬɶ ɜ ɫɢɦɩɥɟɤɫ-ɬɚɛɥɢɰɭ ɧɨɜɨɟ ɨɝɪɚɧɢɱɟɧɢɟ:
¦
Jj
ikmnjij
bxxa }{}{
.
i � I , ��� I — ��������� �������� ����������, J — ��������� �������-
��� ���������� ������, bi � aij — ������������� � ������� ���� �����-
��� bi � aij .
     ������� ������ i � I �����, ��� �������� ���������� xi � bi — ����-
���. �� ����������� ����� ����� ����� �����: y � [ y ] . ��� ��� x j � 0, �j ,
��   � aij x j � � [aij ]x j .   �������������, � ������ ��������� (4.5) �����:
     j� J          j� J

bi � xi �   � [aij ]x j   . ���� ���������� x j � �, j � 1, n , �� ��������� �������-
            j� J
���� ����� ���������� ���:
                                      [bi ] � xi � � [aij ]x j .                (4.6)
                                                    j�J

      ������� �� ��������� (3.5) ����������� (3.6), �������� �����������
                               {bi } � � {aij }x j ,                  (4.7)
                                              j�J
��� �������� {y} ���������� ������� ����� ����� y. ����������� (4.7) ���-
�� ��� ���� ���������� ����� ����� � ������ (4.1) — (4.3). ������ ����-
������ ����������� ���������������� ������� �� ������������� �����
�����������, ��� ��� ��� ���� ��� ���������� ���������� x j � 0, j � J , �,
�������������, {bi } � 0 , ��� ���������� ��� �������� ����� �� ��������-
��� ������� �����.
    ����������� (4.7) ����� ���� ������������ ��� ��������������� ��-
��������� �����������. � ����������� � ������������ ����� ������ ���
������ � ����
                               � {aij }x j � xn � m �1 � {bi },     (4.8)
                                     j� J
��� xn � m �1 – �������������� ���������� (����� ���������� ������ (4.1) – (4.3)
� ������������� ���� ���������� � ��� ����� n � m ).


                           4.2. ��������������� ����� ������

��� 1. ����� ����� x1 — ������� ������ ��������� ����������������
(4.1) – (4.3) (��� ������� ���������������). �������� � = 1.
��� 2. ���� x k — �������������, �� ������� �������, �������. �����
������������� ��������� I � J — �������� �������� � ���������� ����-
������.
��� 3. ������� ����� i � I �����, ��� ���������� xik — �������.
��� 4. �������� � ��������-������� ����� �����������:
                               � {aij }x j � xn � m � k � {bi } .
                                     j� J

                                               32

Страницы