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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

8
Ɉɛɨɡɧɚɱɢɦ ɱɟɪɟɡ
:
ɞɨɩɭɫɬɢɦɨɟ ɦɧɨɠɟɫɬɜɨ ɡɚɞɚɱɢ ɨ ɧɚɡɧɚɱɟɧɢɹɯ. ȼ
ɫɨɨɬɜɟɬɫɬɜɢɢ ɫ ɨɩɪɟɞɟɥɟɧɢɟɦ ɦɚɬɪɢɰ ɧɚɡɧɚɱɟɧɢɣ ɦɨɠɧɨ ɭɬɜɟɪɠɞɚɬɶ, ɱɬɨ
ɦɧɨɠɟɫɬɜɨ ɬɚɤɢɯ ɦɚɬɪɢɰ ɫɨɫɬɚɜɥɹɟɬ ɞɨɩɭɫɬɢɦɨɟ ɦɧɨɠɟɫɬɜɨ
:
.
Ɂɚɦɟɱɚɧɢɟ. ȼɫɟ ɡɚɞɚɱɢ ɨ ɧɚɡɧɚɱɟɧɢɹɯ ɪɚɡɦɟɪɚ n×n ɢɦɟɸɬ ɨɞɧɨ ɢ ɬɨ
ɠɟ ɞɨɩɭɫɬɢɦɨɟ ɦɧɨɠɟɫɬɜɨ ɢ ɨɬɥɢɱɚɸɬɫɹ ɞɪɭɝ ɨɬ ɞɪɭɝɚ ɬɨɥɶɤɨ ɤɨɷɮɮɢɰɢ-
ɟɧɬɚɦɢ ɰɟɥɟɜɨɣ ɮɭɧɤɰɢɢ, ɬ. ɟ. ɦɚɬɪɢɰɟɣ C= )(
ij
c.
Ɍɟɨɪɟɦɚ 1. ȿɫɥɢ ɷɥɟɦɟɧɬɵ ɦɚɬɪɢɰ C ɢ D ɩɨɪɹɞɤɚ n×n ɫɜɹɡɚɧɵ ɪɚɜɟɧ-
ɫɬɜɚɦɢ
jiijij
cd
E
D
, ɬɨ ɡɚɞɚɱɢ ɨ ɧɚɡɧɚɱɟɧɢɹɯ ɫ ɞɚɧɧɵɦɢ ɦɚɬɪɢɰɚɦɢ C
ɢ D ɷɤɜɢɜɚɥɟɧɬɧɵ, ɬ. ɟ. ɦɧɨɠɟɫɬɜɚ ɢɯ ɪɟɲɟɧɢɣ (ɨɩɬɢɦɚɥɶɧɵɯ ɬɨɱɟɤ) ɫɨɜ-
ɩɚɞɚɸɬ.
Ⱦɨɤɚɡɚɬɟɥɶɫɬɜɨ. ȼɨ-ɩɟɪɜɵɯ, ɤɚɤ ɨɬɦɟɱɚɥɨɫɶ ɜɵɲɟ, ɞɨɩɭɫɬɢɦɵɟ
ɦɧɨɠɟɫɬɜɚ ɨɛɟɢɯ ɡɚɞɚɱ ɫɨɜɩɚɞɚɸɬ. ȼɨ-ɜɬɨɪɵɯ, ɫɪɚɜɧɢɦ ɡɧɚɱɟɧɢɹ ɰɟɥɟɜɵɯ
ɮɭɧɤɰɢɣ ɨɛɟɢɯ ɡɚɞɚɱ, ɢɫɩɨɥɶɡɭɹ ɨɝɪɚɧɢɱɟɧɢɹ. ȼ ɪɟɡɭɥɶɬɚɬɟ ɩɨɥɭɱɚɟɦ ɰɟ-
ɩɨɱɤɭ ɪɚɜɟɧɫɬɜ.
,
111111111111
11111111
Fxcxcxxxc
xxxcxd
n
i
n
j
ijij
const
n
j
j
n
i
i
n
i
n
j
ijij
n
j
n
i
ijj
n
i
n
j
iji
n
i
n
j
ijij
n
i
n
j
ijj
n
i
n
j
iji
n
i
n
j
ijij
n
i
n
j
ijij
¦¦¦¦¦¦¦¦¦¦¦¦
¦¦¦¦¦¦¦¦

EDED
ED
ɢɡ ɤɨɬɨɪɨɣ ɫɥɟɞɭɟɬ, ɱɬɨ ɡɧɚɱɟɧɢɹ ɞɜɭɯ ɰɟɥɟɜɵɯ ɮɭɧɤɰɢɣ ɫ ɦɚɬɪɢɰɚɦɢ
C ɢ D ɨɬɥɢɱɚɸɬɫɹ ɧɚ ɩɨɫɬɨɹɧɧɭɸ F. ɗɬɨ ɨɡɧɚɱɚɟɬ, ɱɬɨ ɦɢɧɢɦɭɦɵ ɷɬɢɯ
ɮɭɧɤɰɢɣ ɞɨɫɬɢɝɚɸɬɫɹ ɜ ɨɞɧɢɯ ɢ ɬɟɯ ɠɟ ɬɨɱɤɚɯ (ɧɚ ɨɞɧɢɯ ɢ ɬɟɯ ɠɟ ɦɚɬ-
ɪɢɰɚɯ ɧɚɡɧɚɱɟɧɢɣ).
Ɍɟɨɪɟɦɚ ɞɨɤɚɡɚɧɚ.
ȼ ɞɚɥɶɧɟɣɲɟɦ ɩɪɟɨɛɪɚɡɨɜɚɧɢɹ ɜɢɞɚ
jiijij
cd
E
D
(ɞɨɛɚɜɥɟɧɢɟ ɤɨ
ɜɫɟɦ ɷɥɟɦɟɧɬɚɦ ɥɸɛɨɣ ɫɬɪɨɤɢ ɢɥɢ ɥɸɛɨɝɨ ɫɬɨɥɛɰɚ ɨɞɧɨɝɨ ɢ ɬɨɝɨ ɠɟ ɱɢɫɥɚ)
ɛɭɞɟɦ ɧɚɡɵɜɚɬɶ ɷɤɜɢɜɚɥɟɧɬɧɵɦɢ ɩɪɟɨɛɪɚɡɨɜɚɧɢɹɦɢ.
ɋɥɟɞɫɬɜɢɟ. ȼɫɟɝɞɚ ɦɨɠɧɨ ɫɱɢɬɚɬɶ, ɱɬɨ ɜɫɟ ɷɥɟɦɟɧɬɵ ɦɚɬɪɢɰɵ C ɧɟ-
ɨɬɪɢɰɚɬɟɥɶɧɵ, ɬ. ɟ. .,,0 jic
ij
t
Ⱦɟɣɫɬɜɢɬɟɥɶɧɨ, ɷɬɨɝɨ ɦɨɠɧɨ ɞɨɛɢɬɶɫɹ ɩɪɢɦɟɧɟɧɢɟɦ ɷɤɜɢɜɚɥɟɧɬɧɵɯ
ɩɪɟɨɛɪɚɡɨɜɚɧɢɣ.
Ɍɟɨɪɟɦɚ 2. ɉɭɫɬɶ ɜɫɟ ɷɥɟɦɟɧɬɵ ɦɚɬɪɢɰɵ C ɧɟɨɬɪɢɰɚɬɟɥɶɧɵ, ɬ. ɟ.
.,,0 jic
ij
t ȿɫɥɢ ɜ ɧɟɣ ɢɦɟɸɬɫɹ n ɧɟɡɚɜɢɫɢɦɵɯ ɧɭɥɟɜɵɯ ɷɥɟɦɟɧɬɨɜ
,0
ij
c ɬɨ ɢɯ ɫɭɦɦɚ ɹɜɥɹɟɬɫɹ ɦɢɧɢɦɚɥɶɧɨɣ.
Ⱦɨɤɚɡɚɬɟɥɶɫɬɜɨ. Ʉɚɤɨɜɚ ɛɵ ɧɢ ɛɵɥɚ ɞɨɩɭɫɬɢɦɚɹ ɬɨɱɤɚ
:
X
,
¦¦
t
n
i
n
j
ijij
xcXL
11
0)(
. ȼɜɟɞɟɦ ɦɚɬɪɢɰɭ ɧɚɡɧɚɱɟɧɢɣ
0
X ɫ ɟɞɢɧɢɰɚɦɢ
ɢɦɟɧɧɨ ɧɚ ɬɟɯ ɦɟɫɬɚɯ, ɝɞɟ ɪɚɫɩɨɥɨɠɟɧɵ ɜɵɛɪɚɧɧɵɟ ɧɟɡɚɜɢɫɢɦɵɟ ɷɥɟɦɟɧɬɵ
      ��������� ����� � ���������� ��������� ������ � �����������. �
������������ � ������������ ������ ���������� ����� ����������, ���
��������� ����� ������ ���������� ���������� ��������� � .
     ���������. ��� ������ � ����������� ������� n×n ����� ���� � ��
�� ���������� ��������� � ���������� ���� �� ����� ������ ��������-
������ ������� �������, �. �. �������� C= (cij ) .
     ������� 1. ���� �������� ������ C � D ������� n×n ������� �����-
������ d ij � cij � � i � � j , �� ������ � ����������� � ������� ��������� C
� D ������������, �. �. ��������� �� ������� (����������� �����) ���-
������.
     ��������������. ��-������, ��� ���������� ����, ����������
��������� ����� ����� ���������. ��-������, ������� �������� �������
������� ����� �����, ��������� �����������. � ���������� �������� ��-
����� ��������.

                  n       n        n   n           n   n               n   n
                 � � d ij xij �� � cij xij � � � � i xij � � � � j xij �
                 i �1 j �1        i �1 j �1       i �1 j �1           i �1 j �1
     n   n                    n   n           n    n          n   n               n           n   n   n
  � � � cij xij � � � i � xij � � � j � xij �� � cij xij � � � i � � � j � � � cij xij � F ,
    i �1 j �1     i �1  j �1    j �1  i �1   i �1 j �1     i �1    j �1
                                                           �    ��
                                                                � ��  � i �1 j �1
                                                                                      const


�� ������� �������, ��� �������� ���� ������� ������� � ���������
C � D ���������� �� ���������� F. ��� ��������, ��� �������� ����
������� ����������� � ����� � ��� �� ������ (�� ����� � ��� �� ���-
����� ����������).
       ������� ��������.
       � ���������� �������������� ���� d ij � cij � � i � � j (���������� ��
���� ��������� ����� ������ ��� ������ ������� ������ � ���� �� �����)
����� �������� �������������� ����������������.
       ���������. ������ ����� �������, ��� ��� �������� ������� C ��-
������������, �. �. cij � 0, �i, j.
       �������������, ����� ����� �������� ����������� �������������
��������������.
       ������� 2. ����� ��� �������� ������� C ��������������, �. �.
cij � 0, �i, j. ���� � ��� ������� n ����������� ������� ���������
cij � 0, �� �� ����� �������� �����������.
       ��������������. ������ �� �� ���� ���������� ����� X � � ,
             n        n
L( X ) � � � cij xij � 0 .                 ������ ������� ���������� X 0 � ���������
         i �1 j �1
������ �� ��� ������, ��� ����������� ��������� ����������� ��������
                                                              8

Страницы