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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

22
ȼ ɫɨɨɬɜɟɬɫɬɜɢɢ ɫɨ ɫɬɪɚɬɟɝɢɟɣ ɞɚɥɶɧɟɣɲɟɦɭ ɜɟɬɜɥɟɧɢɸ ɩɨɞɥɟɠɢɬ
ɦɧɨɠɟɫɬɜɨ
2
:
, ɬɚɤ ɤɚɤ ɨɧɨ ɢɦɟɟɬ ɧɚɢɦɟɧɶɲɭɸ ɨɰɟɧɤɭ
15)(
2
:
[
. Ⱥɧɚɥɨ-
ɝɢɱɧɨ ɞɥɹ ɜɫɟɯ ɧɭɥɟɜɵɯ ɷɥɟɦɟɧɬɨɜ ɦɚɬɪɢɰɵ
2
C
ɫɱɢɬɚɟɦ
2
ij
S ɢ ɨɩɪɟɞɟɥɹɟɦ,
ɱɬɨ )2,3(),(
r
q . Ɏɨɪɦɢɪɭɟɦ ɦɧɨɠɟɫɬɜɚ
5
:
ɢ
6
:
, ɞɨɛɚɜɥɹɹ ɫɨɨɬɜɟɬɫɬɜɟɧ-
ɧɨ ɭɫɥɨɜɢɹ
1
32
x
ɢ
0
32
x
. Ɇɚɬɪɢɰɵ
5
C
ɢ
6
C
ɢɦɟɸɬ ɜɢɞ:
ȼɵɱɢɫɥɹɟɦ ɨɰɟɧɤɢ:
15015)(
5
:
[
,
18315)(
6
:
[
. Ⱦɚɥɶɧɟɣ-
ɲɟɦɭ ɜɟɬɜɥɟɧɢɸ ɩɨɞɥɟɠɢɬ ɦɧɨɠɟɫɬɜɨ
5
:
.
Ⱦɟɥɢɦ
5
:
ɧɚ ɩɨɞɦɧɨɠɟɫɬɜɚ
7
:
ɢ
8
:
ɩɨ ɩɚɪɟ )7,8(),(
r
q . Ɋɚɫɫɱɢɬɚɜ
ɦɚɬɪɢɰɵ
7
C
ɢ
8
C
, ɨɩɪɟɞɟɥɹɟɦ
16115)(
7
:
[
,
17215)(
8
:
[
. Ɇɢ-
ɧɢɦɚɥɶɧɭɸ ɨɰɟɧɤɭ 16 ɢɦɟɟɬ ɬɪɢ ɩɨɞɦɧɨɠɟɫɬɜɚ:
43
:: ,
ɢ
7
:
.
ȼɵɛɟɪɟɦ ɞɥɹ ɞɚɥɶɧɟɣɲɟɝɨ ɜɟɬɜɥɟɧɢɹ
3
:
. Ⱦɟɥɢɦ ɟɝɨ ɧɚ ɩɨɞɦɧɨɠɟɫɬɜɚ
9
:
ɢ
10
:
ɩɨ ɩɚɪɟ )1,6(),(
r
q . ɉɨɥɭɱɢɦ
16)(
9
:
[
,
18)(
10
:
[
.
Ⱦɚɥɟɟ ɞɟɥɢɦ
9
:
ɧɚ ɩɨɞɦɧɨɠɟɫɬɜɚ
11
:
ɢ
12
:
ɩɨ ɩɚɪɟ )6,7(),(
r
q . ȼɵ-
ɱɢɫɥɹɟɦ
16)(
11
:
[
,
19)(
12
:
[
.
Ⱦɟɥɢɦ
11
:
ɩɨ ɩɚɪɟ )5,3(),(
r
q ɧɚ
13
:
ɢ
14
:
. ɉɪɢ ɷɬɨɦ ɩɨɥɭɱɚɟɦ
ɦɚɬɪɢɰɭ
13
C
ɪɚɡɦɟɪɚ 2
u
2. ȼ ɪɟɡɭɥɶɬɚɬɟ ɜɵɩɢɫɵɜɚɟɦ ɞɨɩɭɫɬɢɦɭɸ ɬɨɱɤɭ
(ɦɚɬɪɢɰɭ X)
ʋ 1 3 4 5 6 7 8
D
1 +
f
1 0
2 2
0
5 0
2
0
+
f
0 1
1 3
0
0
4 2 1 +
f
0
1 5 1 0
5 2
0
1 +
f
2 1 2 0 ,
6 1 8 5 3 +
f
0
4 0
7
0
6 4 2
0
+
f
0
0
8 6 7 2 8 2
0
+
f
0
ɋ
5
=
E
0 0 0 0 0 0 0
0
ʋ 1 2 3 4 5 6
7
8
D
1 +
f
0
1
0
2 2
0
5 0
2
0
+
f
+
f
0
1 1 3
0
5
3
0
+
f
+
f
1
0
1 3 5 0
4 2 2 1 +
f
0
1 5 1 0 .
5 2 1
0
1 +
f
2 1 2 0
6 1 4 8 5 3 +
f
0
4 0
7 0
3 6 4 2
0
+
f
0
0
8 6 5 7 2 8 2
0
+
f
0
ɋ
6
=
   � ������������ �� ���������� ����������� ��������� ��������
��������� � 2 , ��� ��� ��� ����� ���������� ������ � (� 2 ) � 15 . �����-
����� ��� ���� ������� ��������� ������� C 2 ������� S ij2 � ����������,
��� (q, r ) � (3,2) . ��������� ��������� � 5 � � 6 , �������� ������������-
�� ������� x32 � 1 � x32 � 0 . ������� C 5 � C 6 ����� ���:
               � 1  3  4  5  6  7  8 �
               1 +� 1  0  2  2  0  5 0
               2 0 +� 0   1  1  3  0 0
               4 2  1 +� 0   1  5  1 0
           �5= 5 2  0  1 +� 2   1  2 0                             ,
               6 1  8  5  3 +� 0   4 0
               7 0  6  4  2  0 +� 0 0
               8 6  7  2  8  2  0 +� 0
               �  0 0  0  0  0  0  0 0


               �    1    2     3     4         5    6    7    8    �
               1    +�   0     1     0         2    2    0    5    0
               2    0    +�    +�    0         1    1    3    0    5
               3    0    +�    +�    1         0    1    3    5    0
               4    2    2     1     +�        0    1    5    1    0   .
        �6=
               5    2    1     0     1         +�   2    1    2    0
               6    1    4     8     5         3    +�   0    4    0
               7    0    3     6     4         2    0    +�   0    0
               8    6    5     7     2         8    2    0    +�   0

     ��������� ������: � (� 5 ) � 15 � 0 � 15 , � (� 6 ) � 15 � 3 � 18 . �������-
���� ��������� �������� ��������� � 5 .
     ����� � 5 �� ������������ � 7 � � 8 �� ���� (q, r ) � (8,7) . ���������
������� C 7 � C8 , ���������� � (� 7 ) � 15 � 1 � 16 , � (� 8 ) � 15 � 2 � 17 . ��-
��������� ������ 16 ����� ��� ������������: � 3 , � 4 � �7 .
     ������� ��� ����������� ��������� � 3 . ����� ��� �� ������������
� 9 � �10 �� ���� (q, r ) � (6,1) . ������� � (� 9 ) � 16 , � (�10 ) � 18 .
     ����� ����� � 9 �� ������������ �11 � �12 �� ���� (q, r ) � (7,6) . ��-
������� � (�11 ) � 16 , � (�12 ) � 19 .
     ����� �11 �� ���� (q, r ) � (3,5) �� �13 � �14 . ��� ���� ��������
������� C13 ������� 2 � 2. � ���������� ���������� ���������� �����
(������� X)


                                          22

Страницы