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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

18
Ɉɩɪɟɞɟɥɟɧɢɟ.
Ɇɚɬɪɢɰɚ
C
ɧɚɡɵɜɚɟɬɫɹ ɩɪɢɜɟɞɟɧɧɨɣ, ɟɫɥɢ ɜɫɟ ɟɟ ɷɥɟ-
ɦɟɧɬɵ ɧɟɨɬɪɢɰɚɬɟɥɶɧɵ, ɚ ɤɚɠɞɚɹ ɫɬɪɨɤɚ ɢ ɤɚɠɞɵɣ ɫɬɨɥɛɟɰ ɫɨɞɟɪɠɚɬ ɩɨ
ɤɪɚɣɧɟɣ ɦɟɪɟ ɩɨ ɨɞɧɨɦɭ ɧɭɥɟɜɨɦɭ ɷɥɟɦɟɧɬɭ.
ɉɪɢɜɟɞɟɧɢɟ ɦɚɬɪɢɰɵ ɦɨɠɟɬ ɛɵɬɶ ɨɫɭɳɟɫɬɜɥɟɧɨ ɫɥɟɞɭɸɳɢɦ ɨɛɪɚɡɨɦ.
ɉɭɫɬɶ ɢɦɟɟɬɫɹ ɦɚɬɪɢɰɚ
njiccC
ijij
,1,,0),( t
. ɇɚɣɞɟɦ
,',min
iijijiij
j
ccc
D
D
., ji ɉɨɥɭɱɢɦ ɦɚɬɪɢɰɭ )'('
ij
cC , ɤɨɬɨɪɚɹ ɜ ɤɚɠ-
ɞɨɣ ɫɬɪɨɤɟ ɫɨɞɟɪɠɢɬ ɧɭɥɟɜɵɟ ɷɥɟɦɟɧɬɵ. ɇɚɣɞɟɦ ɞɚɥɟɟ
,''',min
jijijjij
i
ccc
E
E
., ji ɉɨɥɭɱɟɧɧɚɹ ɦɚɬɪɢɰɚ ''
C
ɹɜɥɹɟɬɫɹ ɩɪɢɜɟɞɟɧ-
ɧɨɣ, ɚ ɫɭɦɦɚ
¦¦
ij
ji
S
E
D
ɧɚɡɵɜɚɟɬɫɹ ɫɭɦɦɨɣ ɩɪɢɜɨɞɹɳɢɯ ɤɨɧɫɬɚɧɬ.
Ɇɚɬɪɢɰɚ '
C
ɨɩɪɟɞɟɥɹɟɬ ɧɨɜɭɸ ɡɚɞɚɱɭ ɤɨɦɦɢɜɨɹɠɟɪɚ, ɤɨɬɨɪɚɹ ɜ ɤɚɱɟ-
ɫɬɜɟ ɨɩɬɢɦɚɥɶɧɨɝɨ ɪɟɲɟɧɢɹ ɛɭɞɟɬ ɢɦɟɬɶ ɬɭ ɠɟ ɩɨɫɥɟɞɨɜɚɬɟɥɶɧɨɫɬɶ ɝɨɪɨ-
ɞɨɜ. Ɇɟɠɞɭ ɜɟɥɢɱɢɧɚɦɢ
L
ɢ
''L
(ɞɥɢɧɚɦɢ ɨɩɬɢɦɚɥɶɧɵɯ ɦɚɪɲɪɭɬɨɜ) ɛɭɞɟɬ
ɫɭɳɟɫɬɜɨɜɚɬɶ ɫɥɟɞɭɸɳɟɟ ɫɨɨɬɧɨɲɟɧɢɟ:
S
L
L
''. Ɉɬɫɸɞɚ ɫɥɟɞɭɟɬ ɨɱɟ-
ɜɢɞɧɨɟ ɧɟɪɚɜɟɧɫɬɜɨ:
S
L
t , ɬɨ ɟɫɬɶ ɫɭɦɦɚ ɩɪɢɜɨɞɹɳɢɯ ɤɨɧɫɬɚɧɬ ɹɜɥɹɟɬɫɹ
ɧɢɠɧɟɣ ɨɰɟɧɤɨɣ ɰɟɥɟɜɨɣ ɮɭɧɤɰɢɢ ɢɫɯɨɞɧɨɣ ɡɚɞɚɱɢ ɤɨɦɦɢɜɨɹɠɟɪɚ.
Ʉɨɧɤɪɟɬɢɡɢɪɭɟɦ ɬɟɩɟɪɶ ɨɫɧɨɜɧɵɟ ɷɬɚɩɵ ɦɟɬɨɞɚ ɜɟɬɜɟɣ ɢ ɝɪɚɧɢɰ ɩɪɢ-
ɦɟɧɢɬɟɥɶɧɨ ɤ ɞɚɧɧɨɣ ɡɚɞɚɱɟ.
ɉɭɫɬɶ
0
:
— ɦɧɨɠɟɫɬɜɨ ɜɫɟɯ ɜɨɡɦɨɠɧɵɯ ɦɚɪɲɪɭɬɨɜ.
1.
ȼɟɬɜɥɟɧɢɟ. ɉɪɢ ɜɟɬɜɥɟɧɢɢ ɨɱɟɪɟɞɧɨɟ ɦɧɨɠɟɫɬɜɨ
k
:
ɪɚɡɛɢɜɚɟɬɫɹ ɧɚ
ɞɜɚ ɩɨɞɦɧɨɠɟɫɬɜɚ ɫɥɟɞɭɸɳɢɦ ɨɛɪɚɡɨɦ. ȼ ɦɚɬɪɢɰɟ
k
C
, ɫɨɨɬɜɟɬɫɬɜɭɸɳɟɣ
ɪɚɡɜɟɬɜɥɹɟɦɨɦɭ ɦɧɨɠɟɫɬɜɭ, ɞɥɹ ɤɚɠɞɨɝɨ ɧɭɥɟɜɨɝɨ ɷɥɟɦɟɧɬɚ
k
ij
c ɜɵɱɢɫɥɹɟɬ-
ɫɹ ɱɢɫɥɨ
k
lj
l
k
il
l
k
ccS
ij
minmin
. Ɂɚɬɟɦ ɨɩɪɟɞɟɥɹɟɬɫɹ ɩɚɪɚ ɢɧɞɟɤɫɨɜ ),(
r
q , ɬɚ-
ɤɚɹ ɱɬɨ
k
ij
ji
k
qr
SS
,
max . ɉɟɪɜɨɟ ɩɨɞɦɧɨɠɟɫɬɜɨ
1
k
: ɮɨɪɦɢɪɭɟɬɫɹ ɞɨɛɚɜɥɟɧɢɟɦ
ɭɫɥɨɜɢɹ 1
qr
x (ɢɡ q -ɝɨ ɝɨɪɨɞɚ ɢɞɬɢ ɜ
r
-ɣ), ɜɬɨɪɨɟ ɩɨɞɦɧɨɠɟɫɬɜɨ
2
k
: ɫɨ-
ɞɟɪɠɢɬ ɭɫɥɨɜɢɟ 0
qr
x .
2.
ȼɵɱɢɫɥɟɧɢɟ ɨɰɟɧɨɤ. ɉɭɫɬɶ ɜ ɫɨɨɬɜɟɬɫɬɜɢɢ ɫ ɩɪɟɞɵɞɭɳɢɦ ɩɭɧɤɬɨɦ
ɩɪɨɢɡɜɟɞɟɧɨ ɪɚɡɛɢɟɧɢɟ
21
kkk
:: : . Ɋɚɫɫɦɨɬɪɢɦ ɩɪɚɜɢɥɨ ɩɟɪɟɯɨɞɚ ɨɬ
ɦɚɬɪɢɰɵ
k
C
ɤ ɦɚɬɪɢɰɚɦ
1
k
C ɢ
2
k
C . Ɇɚɬɪɢɰɚ
2
k
C ɫɨɞɟɪɠɢɬ ɬɟ ɠɟ ɫɬɪɨɤɢ ɢ
ɫɬɨɥɛɰɵ, ɱɬɨ ɢ
k
C
. ɉɨɥɨɠɢɦ
°
¯
°
®
f
z
),(),(,
),,(),(,
rqji
rqjic
c
k
ij
k
ij
. ɉɪɢɦɟɧɹɹ ɤ ɩɨɥɭɱɟɧ-
ɧɨɣ ɦɚɬɪɢɰɟ
k
C
ɩɪɨɰɟɞɭɪɭ ɩɪɢɜɟɞɟɧɢɹ, ɩɨɥɭɱɢɦ ɦɚɬɪɢɰɭ
2
k
C . ɉɪɢ ɷɬɨɦ
ɫɭɦɦɚ ɩɪɢɜɨɞɹɳɢɯ ɤɨɧɫɬɚɧɬ ɛɭɞɟɬ ɪɚɜɧɚ
k
qr
S . Ɍɚɤɢɦ ɨɛɪɚɡɨɦ, ɨɰɟɧɤɨɣ
      �����������. ������� C ���������� �����������, ���� ��� �� ���-
����� ��������������, � ������ ������ � ������ ������� �������� ��
������� ���� �� ������ �������� ��������.
      ���������� ������� ����� ���� ������������ ��������� �������.
�����     �������     �������      C � (cij ), cij � 0, i, j � 1, n . ������
min cij � � i , cij ' � cij � � i , �i, j. ������� ������� C ' � (cij ' ) , ������� � ���-
  j
���      ������           ��������            �������    ��������.       ������     �����
min cij � � j , cij ' ' � cij '� � j , �i, j. ���������� ������� C ' ' �������� ��������-
  i
���, � ����� S � � � i � � � j ���������� ������ ���������� ��������.
                             i       j
     ������� C ' ���������� ����� ������ ������������, ������� � ����-
���� ������������ ������� ����� ����� �� �� ������������������ ����-
���. ����� ���������� L � L' ' (������� ����������� ���������) �����
������������ ��������� �����������: L � L' '� S . ������ ������� ���-
������ �����������: L � S , �� ���� ����� ���������� �������� ��������
������ ������� ������� ������� �������� ������ ������������.
   �������������� ������ �������� ����� ������ ������ � ������ ���-
���������� � ������ ������.
   ����� � 0 — ��������� ���� ��������� ���������.

1.   ���������. ��� ��������� ��������� ��������� � k ����������� ��
��� ������������ ��������� �������. � ������� C k , ���������������
�������������� ���������, ��� ������� �������� �������� cijk ���������-
�� ����� S ijk � min cilk � min cljk . ����� ������������ ���� �������� ( q, r ) , ��-
                         l           l

��� ���   S qrk   �   max S ijk   . ������ ������������ � k1 ����������� �����������
                       i, j
������� xqr � 1 (�� q -�� ������ ���� � r -�), ������ ������������ � k2 ��-
������ ������� xqr � 0 .

2. ���������� ������. ����� � ������������ � ���������� �������
����������� ��������� � k � � k1 � � k2 . ���������� ������� �������� ��
������� C k � �������� C k 1 � Ck2 . ������� Ck2 �������� �� �� ������ �
                                    ��c k , (i, j ) � (q, r ),
�������, ��� � C k . ������� cijk � � ij                       . �������� � �������-
                                     ��� �, (i, j ) � (q, r )
��� ������� Ck ��������� ����������, ������� ������� Ck2 . ��� ����
����� ���������� �������� ����� ����� S qrk . ����� �������, �������
                                                18

Страницы