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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

7
,minxc)X(L
n
1i
n
1j
ijij
¦¦
o
°
°
°
¯
°
°
°
®
:
¦
¦
.,1,},1,0{
,,1,1
,,1,1
1
1
njix
nix
njx
ij
n
j
ij
n
i
ij
Ɂɚɦɟɱɚɧɢɟ. ȿɫɥɢ ɩɨɫɥɟɞɧɢɟ ɨɝɪɚɧɢɱɟɧɢɹ ɡɚɦɟɧɢɬɶ ɭɫɥɨɜɢɹɦɢ ɜɢɞɚ
,,,10 jix
ij
dd ɬɨ ɩɨɥɭɱɟɧɧɚɹ ɡɚɞɚɱɚ ɹɜɥɹɟɬɫɹ ɱɚɫɬɧɵɦ ɫɥɭɱɚɟɦ ɬɪɚɧɫ-
ɩɨɪɬɧɨɣ ɡɚɞɚɱɢ, ɭ ɤɨɬɨɪɨɣ, ɤɚɤ ɢɡɜɟɫɬɧɨ, ɨɩɬɢɦɚɥɶɧɨɟ ɪɟɲɟɧɢɟ ɜɫɟɝɞɚ ɫɭ-
ɳɟɫɬɜɭɟɬ. Ɍɚɤɢɦ ɨɛɪɚɡɨɦ, ɡɚɞɚɱɭ ɨ ɧɚɡɧɚɱɟɧɢɹɯ ɦɨɠɧɨ ɪɟɲɚɬɶ
ɦɟɬɨɞɨɦ
ɩɨɬɟɧɰɢɚɥɨɜ
, ɩɪɢɱɟɦ ɜ ɫɨɨɬɜɟɬɫɬɜɢɢ ɫɨ ɫɩɟɰɢɮɢɤɨɣ ɷɬɨɝɨ ɦɟɬɨɞɚ ɦɨɠɧɨ
ɭɬɜɟɪɠɞɚɬɶ, ɱɬɨ ɪɟɲɟɧɢɟɦ ɹɜɥɹɟɬɫɹ
2
n
-ɦɟɪɧɵɣ ɜɟɤɬɨɪ, ɢɥɢ ɦɚɬɪɢɰɚ ɩɨ-
ɪɹɞɤɚ n×n, ɷɥɟɦɟɧɬɵ ɤɨɬɨɪɨɣ ɪɚɜɧɵ 0 ɢɥɢ 1. ɗɬɨ ɨɡɧɚɱɚɟɬ, ɱɬɨ ɩɨɥɭɱɟɧɧɵɣ
ɨɬɜɟɬ ɛɭɞɟɬ ɬɚɤɠɟ ɹɜɥɹɬɶɫɹ ɨɬɜɟɬɨɦ ɜ ɢɫɯɨɞɧɨɣ ɡɚɞɚɱɟ ɨ ɧɚɡɧɚɱɟɧɢɹɯ. Ɉɞ-
ɧɚɤɨ ɧɚɱɚɥɶɧɚɹ ɛɚɡɢɫɧɚɹ ɬɨɱɤɚ, ɩɨɥɭɱɟɧɧɚɹ, ɧɚɩɪɢɦɟɪ, ɩɨ ɦɟɬɨɞɭ
ɫɟɜɟɪɨ-
ɡɚɩɚɞɧɨɝɨ ɭɝɥɚ
, ɫɨɞɟɪɠɢɬ ɧɟ m+n–1=2n–1, ɚ ɜɫɟɝɨ ɥɢɲɶ n ɧɟɧɭɥɟɜɵɯ ɤɨɦ-
ɩɨɧɟɧɬ ɪɚɜɧɵɯ 1, cɥɟɞɨɜɚɬɟɥɶɧɨ, ɩɪɢ 2tn ɷɬɨɬ ɩɥɚɧ ɫɬɚɧɨɜɢɬɫɹ ɜɵɪɨɠ-
ɞɟɧɧɵɦ. Ʉɚɤ ɢɡɜɟɫɬɧɨ, ɷɬɨ ɨɛɫɬɨɹɬɟɥɶɫɬɜɨ ɫɭɳɟɫɬɜɟɧɧɨ ɭɫɥɨɠɧɹɟɬ ɜɵɱɢɫ-
ɥɢɬɟɥɶɧɭɸ ɩɪɨɰɟɞɭɪɭ ɪɟɲɟɧɢɹ ɬɪɚɧɫɩɨɪɬɧɨɣ ɡɚɞɚɱɢ. ɉɨ ɷɬɨɣ ɩɪɢɱɢɧɟ ɞɥɹ
ɪɟɲɟɧɢɹ ɡɚɞɚɱɢ ɨ ɧɚɡɧɚɱɟɧɢɹɯ ɫɭɳɟɫɬɜɭɸɬ ɫɩɟɰɢɚɥɶɧɵɟ ɦɟɬɨɞɵ. Ɋɚɫɫɦɨɬ-
ɪɢɦ ɨɞɢɧ ɢɡ ɧɢɯ, ɤɨɬɨɪɵɣ ɧɨɫɢɬ ɧɚɡɜɚɧɢɟ
ɜɟɧɝɟɪɫɤɢɣ ɦɟɬɨɞ.
ȼ ɞɚɥɶɧɟɣɲɟɦ ɧɚɦ ɩɨɬɪɟɛɭɟɬɫɹ ɫɥɟɞɭɸɳɟɟ ɨɩɪɟɞɟɥɟɧɢɟ.
Ɉɩɪɟɞɟɥɟɧɢɟ. Ʌɸɛɵɟ k ɷɥɟɦɟɧɬɨɜ (
nk ,2
) ɦɚɬɪɢɰɵ C= )(
ij
c ɩɨɪɹɞɤɚ
n×n ɧɚɡɵɜɚɸɬɫɹ ɧɟɡɚɜɢɫɢɦɵɦɢ, ɟɫɥɢ ɜɫɹɤɢɟ ɞɜɚ ɢɡ ɧɢɯ ɪɚɫɩɨɥɚɝɚɸɬɫɹ ɜ
ɪɚɡɧɵɯ ɫɬɪɨɤɚɯ ɢ ɜ ɪɚɡɧɵɯ ɫɬɨɥɛɰɚɯ.
Ɍɟɩɟɪɶ ɦɨɠɧɨ ɩɟɪɟɮɨɪɦɭɥɢɪɨɜɚɬɶ ɡɚɞɚɱɭ ɨ ɧɚɡɧɚɱɟɧɢɹɯ ɫɥɟɞɭɸɳɢɦ
ɨɛɪɚɡɨɦ:
ɫɪɟɞɢ
2
n
ɷɥɟɦɟɧɬɨɜ ɞɚɧɧɨɣ ɦɚɬɪɢɰɵ C ɧɚɣɬɢ n ɧɟɡɚɜɢɫɢɦɵɯ
ɷɥɟɦɟɧɬɨɜ
ss
ji
c ,
ns ,1
, ɬɚɤɢɯ, ɱɬɨ ɫɭɦɦɚ
¦
n
s
ji
ss
c
1
ɦɢɧɢɦɚɥɶɧɚ.
Ⱦɥɹ ɨɛɨɫɧɨɜɚɧɢɹ ɜɟɧɝɟɪɫɤɨɝɨ ɦɟɬɨɞɚ ɩɨɬɪɟɛɭɸɬɫɹ ɫɥɟɞɭɸɳɢɟ ɩɨɧɹ-
ɬɢɹ ɢ ɭɬɜɟɪɠɞɟɧɢɹ
.
Ɇɚɬɪɢɰɟɣ ɧɚɡɧɚɱɟɧɢɣ
ɩɨɪɹɞɤɚ n×n ɧɚɡɵɜɚɟɬɫɹ ɦɚɬɪɢɰɚ, ɜ ɤɨɬɨɪɨɣ
ɢɦɟɸɬɫɹ n ɧɟɡɚɜɢɫɢɦɵɯ ɟɞɢɧɢɰ ɢ
)1(
2
nnnn
ɧɭɥɟɣ. ɂɧɵɦɢ ɫɥɨɜɚɦɢ,
ɷɬɨ ɦɚɬɪɢɰɚ, ɭ ɤɨɬɨɪɨɣ ɜ ɤɚɠɞɨɣ ɫɬɪɨɤɟ ɢ ɜ ɤɚɠɞɨɦ ɫɬɨɥɛɰɟ ɢɦɟɟɬɫɹ ɪɨɜɧɨ
ɨɞɧɚ ɟɞɢɧɢɰɚ, ɚ ɨɫɬɚɥɶɧɵɟ ɷɥɟɦɟɧɬɵ ɹɜɥɹɸɬɫɹ ɧɭɥɹɦɢ.
                                       n       n
                             L( X ) � � � cij xij � min ,
                                      i �1 j �1
                                  n
                                �
                                �� xij � 1, j � 1, n,
                                �i �1
                                �n
                              � � � xij � 1, i � 1, n,
                                � j �1
                                � x �{0,1}, i, j � 1, n.
                                � ij
                                �
     ���������. ���� ��������� ����������� �������� ��������� ����
0 � xij � 1, �i, j , �� ���������� ������ �������� ������� ������� �����-
������� ������, � �������, ��� ��������, ����������� ������� ������ ��-
��������. ����� �������, ������ � ����������� ����� ������ �������
�����������, ������ � ������������ �� ���������� ����� ������ �����
����������, ��� �������� �������� n 2 -������ ������, ��� ������� ��-
����� n×n, �������� ������� ����� 0 ��� 1. ��� ��������, ��� ����������
����� ����� ����� �������� ������� � �������� ������ � �����������. ��-
���� ��������� �������� �����, ����������, ��������, �� ������ ������-
��������� ����, �������� �� m+n–1=2n–1, � ����� ���� n ��������� ���-
������ ������ 1, c������������, ��� n � 2 ���� ���� ���������� �����-
������. ��� ��������, ��� �������������� ����������� ��������� �����-
��������� ��������� ������� ������������ ������. �� ���� ������� ���
������� ������ � ����������� ���������� ����������� ������. �������-
��� ���� �� ���, ������� ����� �������� ���������� �����.
       � ���������� ��� ����������� ��������� �����������.
     �����������. ����� k ��������� ( k � 2, n ) ������� C= (cij ) �������
n×n ���������� ������������, ���� ������ ��� �� ��� ������������� �
������ ������� � � ������ ��������.
       ������ ����� ����������������� ������ � ����������� ���������
�������: ����� n 2 ��������� ������ ������� C ����� n �����������
                                                    n
��������� ci s j s , s � 1, n , �����, ��� �����   � ci   s js
                                                                 ����������.
                                                   s �1
      ��� ����������� ����������� ������ ����������� ��������� ����-
��� � �����������.

      �������� ���������� ������� n×n ���������� �������, � �������
������� n ����������� ������ � n 2 � n � n( n � 1) �����. ����� �������,
��� �������, � ������� � ������ ������ � � ������ ������� ������� �����
���� �������, � ��������� �������� �������� ������.

                                           7

Страницы