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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

11
ɉɪɢ ɪɟɲɟɧɢɢ ɡɚɞɚɱɢ ɨ ɧɚɡɧɚɱɟɧɢɹɯ ɛɭɞɟɦ ɩɪɨɜɨɞɢɬɶ ɭɤɚɡɚɧɧɵɟ ɥɢ-
ɧɢɢ, ɜ ɪɟɡɭɥɶɬɚɬɟ ɱɟɝɨ ɧɟɤɨɬɨɪɵɟ ɷɥɟɦɟɧɬɵ ɨɤɚɠɭɬɫɹ ɡɚɱɟɪɤɧɭɬɵɦɢ, ɞɪɭ-
ɝɢɟ – ɡɚɱɟɪɤɧɭɬɵ ɞɜɚɠɞɵ ɢ ɨɫɬɚɥɶɧɵɟ – ɧɟɡɚɱɟɪɤɧɭɬɵɦɢ.
ɗɬɚɩ 3
Ɉɛɨɡɧɚɱɢɦ ɱɟɪɟɡ
r
ij
ɫ ɷɥɟɦɟɧɬ ɩɪɢɜɟɞɟɧɧɨɣ ɦɚɬɪɢɰɵ
2
C
, ɡɚɱɟɪɤɧɭɬɵɣ
r
ɪɚɡ )2,1,0(
r
ɧɚ 2-ɦ ɷɬɚɩɟ, ɢ ɩɨɥɨɠɢɦ
0
min
ij
c
D
, ɝɞɟ ɦɢɧɢɦɭɦ ɛɟɪɟɬɫɹ ɩɨ
ɜɫɟɦ
j
i,
, ɬ. ɟ. ɢɳɟɬɫɹ ɧɚɢɦɟɧɶɲɢɣ ɢɡ ɧɟɡɚɱɟɪɤɧɭɬɵɯ ɷɥɟɦɟɧɬɨɜ ɦɚɬɪɢɰɵ
2
C
. ȿɫɥɢ ɬɟɩɟɪɶ ɩɪɨɜɟɫɬɢ ɩɟɪɟɫɱɟɬ ɷɥɟɦɟɧɬɨɜ ɦɚɬɪɢɰɵ
2
ɋ
ɩɨ ɮɨɪɦɭɥɚɦ
°
°
¯
°
°
®
!
,
,
,
2
1
0
D
D
ij
ij
ij
ɧɨɜ
ij
c
c
c
c
ɬɨ ɬɚɤɢɟ ɩɪɟɨɛɪɚɡɨɜɚɧɢɹ ɹɜɥɹɸɬɫɹ ɫɥɟɞɫɬɜɢɟɦ ɩɪɢɦɟɧɟɧɢɹ Ɍɟɨɪɟɦɵ 1. ɉɟ-
ɪɟɫɱɢɬɚɟɦ ɷɥɟɦɟɧɬɵ ɦɚɬɪɢɰɵ
2
C
ɢɡ ɩɪɢɦɟɪɚ 2 ɩɪɢ 1
D
, ɜ ɢɬɨɝɟ ɩɨɥɭɱɢɦ
ɩɪɢɜɟɞɟɧɧɭɸ ɦɚɬɪɢɰɭ
¸
¸
¸
¸
¸
¸
¹
·
¨
¨
¨
¨
¨
¨
©
§
86000
64020
62330
24100
00003
3
ɋ .
ȼɫɟ ɟɟ ɧɭɥɢ ɫɨɞɟɪɠɚɬ, ɧɚɩɪɢɦɟɪ, 1-ɹ ɝɨɪɢɡɨɧɬɚɥɶ ɢ ɬɪɢ ɜɟɪɬɢɤɚɥɢ: 1-ɚɹ, 2-ɹ,
3-ɹ. ɋɥɟɞɨɜɚɬɟɥɶɧɨ, ɡɞɟɫɶ 54
k ɢ 2
D
.
ȿɳɟ ɨɞɢɧ ɩɟɪɟɫɱɟɬ ɞɚɟɬ ɩɪɢɜɟɞɟɧɧɭɸ ɦɚɬɪɢɰɭ
¸
¸
¸
¸
¸
¸
¹
·
¨
¨
¨
¨
¨
¨
©
§
64000
42020
40330
02100
00225
1
C .
Ɂɞɟɫɶ ɭɠɟ .5 nk
ɗɬɚɩ 4
Ɉɬɵɫɤɚɧɢɟ n ɧɟɡɚɜɢɫɢɦɵɯ ɧɭɥɟɣ ɨɫɭɳɟɫɬɜɥɹɟɬɫɹ ɩɟɪɟɛɨɪɨɦ ɜɫɟɯ
ɜɨɡɦɨɠɧɵɯ ɜɚɪɢɚɧɬɨɜ. ɍɞɨɛɧɨ ɩɟɪɟɛɨɪ ɧɚɱɢɧɚɬɶ ɫ ɨɬɵɫɤɚɧɢɹ ɫɬɪɨɤ ɢɥɢ
ɫɬɨɥɛɰɨɜ, ɫɨɞɟɪɠɚɳɢɯ ɟɞɢɧɫɬɜɟɧɧɵɣ ɧɭɥɟɜɨɣ ɷɥɟɦɟɧɬ, ɩɨɫɤɨɥɶɤɭ ɬɚɤɨɣ
ɷɥɟɦɟɧɬ ɨɛɹɡɚɬɟɥɶɧɨ ɜɨɣɞɟɬ ɜ ɝɪɭɩɩɭ ɧɟɡɚɜɢɫɢɦɵɯ. ȼɵɛɪɚɜ ɷɥɟɦɟɧɬ
ls
c
,
ɢɫɤɥɸɱɚɸɬ ɢɡ ɪɚɫɫɦɨɬɪɟɧɢɹ
l
-ɸ ɫɬɪɨɤɭ ɢ
s
-ɣ ɫɬɨɥɛɟɰ, ɩɨɫɥɟ ɱɟɝɨ ɩɟɪɟɯɨ-
     ��� ������� ������ � ����������� ����� ��������� ��������� ��-
���, � ���������� ���� ��������� �������� �������� ������������, ���-
��� – ���������� ������ � ��������� – ��������������.

                                 ���� 3
    ��������� ����� �ijr ������� ����������� ������� C 2 , ����������� r
��� (r � 0,1,2) �� 2-� �����, � ������� � � min cij0 , ��� ������� ������� ��
���� i, j , �. �. ������ ���������� �� ������������� ��������� �������
C 2 . ���� ������ �������� �������� ��������� ������� � 2 �� ��������
                                         �cij0 � � ,
                                         ��
                                cij��� � �cij1 �,
                                          � 2
                                          ��cij � � ,
�� ����� �������������� �������� ���������� ���������� ������� 1. ��-
��������� �������� ������� C 2 �� ������� 2 ��� � � 1 , � ����� �������
����������� �������
                                 � 3 0 0 0 0�
                                 �                    �
                                 � 0 0 1 4 2�
                            �3 � �0 3 3 2 6� .
                                 �                    �
                                 �0 2 0 4 6�
                                 �0 0 0 6 8�
                                 �                    �
��� �� ���� ��������, ��������, 1-� ����������� � ��� ���������: 1-��, 2-�,
3-�. �������������, ����� k � 4 � 5 � � � 2 .
       ��� ���� �������� ���� ����������� �������
                                 �5 2 2 0 0�
                                 �                    �
                                 �0 0 1 2 0�
                            C1 � � 0 3 3 0 4 � .
                                 �                    �
                                 � 0 2 0 2 4�
                                 �0 0 0 4 6�
                                 �                    �
       ����� ��� k � n � 5.

                               ���� 4
     ��������� n ����������� ����� �������������� ��������� ����
��������� ���������. ������ ������� �������� � ��������� ����� ���
��������, ���������� ������������ ������� �������, ��������� �����
������� ����������� ������ � ������ �����������. ������ ������� cls ,
��������� �� ������������ l -� ������ � s -� �������, ����� ���� ������-

                                     11

Страницы