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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

17
ɒɚɝ 7. Ɉɫɬɚɧɨɜ,
R
min
M
.
Ɂɚɦɟɬɢɦ, ɱɬɨ ɬɚɤɚɹ ɩɨɫɥɟɞɨɜɚɬɟɥɶɧɨɫɬɶ ɲɚɝɨɜ ɦɨɠɟɬ ɛɵɬɶ ɧɟ ɪɚɰɢɨ-
ɧɚɥɶɧɨɣ ɜ ɫɥɭɱɚɟ, ɟɫɥɢ ɩɪɢ ɜɵɱɢɫɥɟɧɢɢ ɨɰɟɧɨɤ ɡɚɜɟɞɨɦɨ ɧɟ ɦɨɝɭɬ ɩɨɹ-
ɜɢɬɶɫɹ ɞɨɩɭɫɬɢɦɵɟ ɬɨɱɤɢ (ɧɚɩɪɢɦɟɪ, ɩɪɢ ɪɟɲɟɧɢɢ ɡɚɞɚɱɢ ɤɨɦɦɢɜɨɹɠɟɪɚ).
ɍɉɊȺɀɇȿɇɂə
1. Ⱦɨɤɚɠɢɬɟ ɫɜɨɣɫɬɜɨ ɦɨɧɨɬɨɧɧɨɫɬɢ ɨɰɟɧɨɤ ɜ ɭɫɥɨɜɢɹɯ, ɩɪɢ ɤɨɬɨɪɵɯ
ɜɟɬɜɥɟɧɢɟ ɢ ɫɨɫɬɚɜɥɟɧɢɟ ɨɰɟɧɨɱɧɵɯ ɡɚɞɚɱ ɨɫɭɳɟɫɬɜɥɹɟɬɫɹ ɩɨ ɩɪɚɜɢɥɚɦ,
ɭɤɚɡɚɧɧɵɦ ɜ ɩɩ. 1 ɢ 2 ɨɩɢɫɚɧɢɹ ɨɫɧɨɜɧɵɯ ɦɨɞɭɥɟɣ.
2. ɉɪɟɞɥɨɠɢɬɟ ɞɪɭɝɢɟ ɫɬɪɚɬɟɝɢɢ ɨɛɯɨɞɚ ɞɟɪɟɜɚ ɜɚɪɢɚɧɬɨɜ.
3. Ⱦɨɤɚɠɢɬɟ, ɱɬɨ ɩɪɢ ɢɫɩɨɥɶɡɨɜɚɧɢɢ ɨɫɧɨɜɧɨɝɨ ɩɪɚɜɢɥɚ ɨɬɛɪɚɫɵɜɚɧɢɹ
ɧɟɩɟɪɫɩɟɤɬɢɜɧɵɯ ɦɧɨɠɟɫɬɜ (ɩ. 4) ɧɟ ɩɪɨɢɫɯɨɞɢɬ ɩɨɬɟɪɢ ɪɟɲɟɧɢɹ.
4. ȼ ɩɪɟɞɥɨɠɟɧɧɨɣ ɚɥɝɨɪɢɬɦɢɱɟɫɤɨɣ ɫɯɟɦɟ ɨɬɵɫɤɢɜɚɟɬɫɹ ɨɞɧɨ
ɪɟɲɟ-
ɧɢɟ, ɞɚɠɟ ɟɫɥɢ ɨɧɨ ɜ ɡɚɞɚɱɟ ɧɟ ɟɞɢɧɫɬɜɟɧɧɨ. Ƚɞɟ ɩɪɨɢɫɯɨɞɢɬ ɩɨɬɟɪɹ ɞɪɭɝɢɯ
ɪɟɲɟɧɢɣ? ɂɫɩɪɚɜɶɬɟ ɚɥɝɨɪɢɬɦ ɬɚɤɢɦ ɨɛɪɚɡɨɦ, ɱɬɨɛɵ ɩɨɹɜɢɥɚɫɶ ɜɨɡɦɨɠ-
ɧɨɫɬɶ ɨɬɵɫɤɚɧɢɹ ɜɫɟɯ ɪɟɲɟɧɢɣ ɡɚɞɚɱɢ.
3.2. Ɇɟɬɨɞ ɜɟɬɜɟɣ ɢ ɝɪɚɧɢɰ ɞɥɹ ɪɟɲɟɧɢɹ
ɡɚɞɚɱɢ ɤɨɦɦɢɜɨɹɠɟɪɚ
ɉɨɫɬɚɧɨɜɤɚ ɡɚɞɚɱɢ ɤɨɦɦɢɜɨɹɠɟɪɚ ɫɨɫɬɨɢɬ ɜ ɫɥɟɞɭɸɳɟɦ. ɂɦɟɟɬɫɹ n
ɝɨɪɨɞɨɜ. Ɂɚɞɚɧɚ ɦɚɬɪɢɰɚ ɪɚɫɫɬɨɹɧɢɣ ɦɟɠɞɭ ɧɢɦɢ:
njicC
ij
,1,),(
. Cɱɢ-
ɬɚɟɦ, ɱɬɨ jic
ij
,,0 t . ȼ ɨɛɳɟɦ ɫɥɭɱɚɟ ɜɨɡɦɨɠɧɨ, ɱɬɨ
jiij
cc z . Ʉɪɨɦɟ ɬɨɝɨ,
ɛɭɞɟɦ ɩɨɥɚɝɚɬɶ, ɱɬɨ
ic
ii
f ,
. ɂɳɟɬɫɹ ɤɪɚɬɱɚɣɲɢɣ ɡɚɦɤɧɭɬɵɣ ɦɚɪɲɪɭɬ
(ɰɢɤɥ), ɩɪɨɯɨɞɹɳɢɣ ɱɟɪɟɡ ɤɚɠɞɵɣ ɝɨɪɨɞ ɪɨɜɧɨ ɨɞɢɧ ɪɚɡ ɢ ɦɢɧɢɦɢɡɢɪɭɸ-
ɳɢɣ ɫɭɦɦɚɪɧɨɟ ɩɪɨɣɞɟɧɧɨɟ ɪɚɫɫɬɨɹɧɢɟ. Ɇɚɬɟɦɚɬɢɱɟɫɤɚɹ ɩɨɫɬɚɧɨɜɤɚ ɡɚɞɚ-
ɱɢ ɦɨɠɟɬ ɛɵɬɶ ɡɚɩɢɫɚɧɚ, ɧɚɩɪɢɦɟɪ, ɫɥɟɞɭɸɳɢɦ ɨɛɪɚɡɨɦ.
,minxcL
n
i
n
j
ijij
¦¦
o
11
.,1,},1,0{
,,1,1
,,1,1
1
1
njix
nix
njx
ij
n
j
ij
n
i
ij
¦
¦
ȼ ɷɬɨɣ ɩɨɫɬɚɧɨɜɤɟ ɧɟ ɭɱɢɬɵɜɚɟɬɫɹ ɟɫɬɟɫɬɜɟɧɧɨɟ ɬɪɟɛɨɜɚɧɢɟ ɫɜɹɡɧɨ-
ɫɬɢ ɦɚɪɲɪɭɬɚ (ɨɬɫɭɬɫɬɜɢɹ ɩɨɞɰɢɤɥɨɜ), ɧɨ ɜ ɞɚɥɶɧɟɣɲɟɦ ɨɧɨ ɛɭɞɟɬ ɜɵɩɨɥ-
ɧɹɬɶɫɹ ɚɥɝɨɪɢɬɦɢɱɟɫɤɢ.
��� 7. �������, � min � R .
      �������, ��� ����� ������������������ ����� ����� ���� �� �����-
������� � ������, ���� ��� ���������� ������ �������� �� ����� ���-
������ ���������� ����� (��������, ��� ������� ������ ������������).


                              ����������

    1. �������� �������� ������������ ������ � ��������, ��� �������
��������� � ����������� ��������� ����� �������������� �� ��������,
��������� � ��. 1 � 2 �������� �������� �������.
    2. ���������� ������ ��������� ������ ������ ���������.
    3. ��������, ��� ��� ������������� ��������� ������� ������������
��������������� �������� (�. 4) �� ���������� ������ �������.
     4. � ������������ ��������������� ����� ������������ ���� ����-
���, ���� ���� ��� � ������ �� �����������. ��� ���������� ������ ������
�������? ��������� �������� ����� �������, ����� ��������� ������-
����� ��������� ���� ������� ������.

                      3.2. ����� ������ � ������ ��� �������
                            ������ ������������

      ���������� ������ ������������ ������� � ���������. ������� n
�������. ������ ������� ���������� ����� ����: C � (cij ), i, j � 1, n . C��-
����, ��� cij � 0, �i, j . � ����� ������ ��������, ��� cij � c ji . ����� ����,
����� ��������, ��� cii � ��, �i . ������ ���������� ��������� �������
(����), ���������� ����� ������ ����� ����� ���� ��� � �����������-
��� ��������� ���������� ����������. �������������� ���������� ����-
�� ����� ���� ��������, ��������, ��������� �������.
                                      n    n
                             L � �� cij xij � min ,
                                     i �1 j �1
                               n
                              � xij � 1,              j � 1, n,
                              i �1
                               n
                              � xij � 1,              i � 1, n,
                              j �1

                          xij �{0,1}, i, j � 1, n.
     � ���� ���������� �� ����������� ������������ ���������� ������-
��� �������� (���������� ���������), �� � ���������� ��� ����� �����-
������ ��������������.
                                                 17

Страницы