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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

21
ʋ 1 2 3 4 5 6 7 8
D
1
+
f
3 1
0
2 2
0
5 0
2
0
+
f
+
f
0
1 1 3
0
5
3
0 0
+
f
1
0
1 3 5 0
4
2 5 1 +
f
0
1 5 1 0
.
5
2 4
0
1 +
f
2 1 2 0
6
1 7 8 5 3 +
f
0
4 0
7
0
6 6 4 2
0
+
f
0
0
8
6 8 7 2 8 2
0
+
f
0
ɋ
2
=
E
0 0 0 0 0 0 0 0
5
ɋɱɢɬɚɟɦ ɨɰɟɧɤɢ:
14410)(
1
:
[
,
15510)(
2
:
[
. ȼ ɬɚɤɨɦ ɫɥɭ-
ɱɚɟ ɞɚɥɶɧɟɣɲɟɦɭ ɜɟɬɜɥɟɧɢɸ ɩɨɞɥɟɠɢɬ ɦɧɨɠɟɫɬɜɨ
1
:
. Ⱦɥɹ ɤɚɠɞɨɝɨ ɧɭɥɟ-
ɜɨɝɨ ɷɥɟɦɟɧɬɚ ɦɚɬɪɢɰɵ
1
C
ɫɱɢɬɚɟɦ
1
ij
S :
,0
1
78
1
71
1
57
1
54
1
52
1
25
1
21
1
17
1
14
1
12
SSSSSSSSSS
,1
1
78
1
76
1
67
1
45
SSSS 2
87
S
. ɂɦɟɟɦ
1
87
2}2,1,0max{ S
. ɋɥɟɞɨɜɚɬɟɥɶɧɨ,
)7,8(),(
r
q .
Ɏɨɪɦɢɪɭɟɦ ɦɧɨɠɟɫɬɜɚ
3
:
ɢ
4
:
, ɞɨɛɚɜɥɹɹ ɫɨɨɬɜɟɬɫɬɜɟɧɧɨ ɭɫɥɨɜɢɹ
1
87
x
ɢ
0
87
x
. ȼɵɱɢɫɥɹɟɦ ɦɚɬɪɢɰɵ
3
C
ɢ
4
C
.
ȼɵɱɢɫɥɹɟɦ ɨɰɟɧɤɢ:
16214)(
3
:
[
,
16214)(
4
:
[
.
ʋ 1 2 4 5 6 8
D
1 +
f
0 0
2 2 4 0
3
0
+
f
1
0
1 4 0
4 2 2 +
f
0
1
0
0 ,
5 1
0 0
+
f
1
0
0
6
0
3 4 2 +
f
2 1
7
0
3 4 2
0
+
f
0
ɋ
3
=
E
0 0 0 0 0 1
2
ʋ 1 2 4 5 6 7 8
D
1 +
f
0 0
2 2
0
5 0
3
0
+
f
1
0
1 3 5 0
4 2 2 +
f
0
1 5 1 0
5 1
0 0
+
f
1
0
1 0 .
6 1 4 5 3 +
f
0
4 0
7
0
3 4 2
0
+
f
0
0
8 4 3
0
6
0
+
f
+
f
2
ɋ
4
=
E
0 0 0 0 0 0 0
2
                     � 1   2  3  4  5  6  7  8                                  �
                     1 +� 3   1  0  2  2  0  5                                  0
                     2  0 +� +�  0  1  1  3  0                                  5
                     3  0  0 +�  1  0  1  3  5                                  0
                     4  2  5  1 +�  0  1  5  1                                  0       .
           �2=
                     5  2  4  0  1 +�  2  1  2                                  0
                     6  1  7  8  5  3 +�  0  4                                  0
                     7  0  6  6  4  2  0 +�  0                                  0
                     8  6  8  7  2  8  2  0 +�                                  0
                     �     0     0      0     0     0     0     0       0       5

     ������� ������: � (�1 ) � 10 � 4 � 14 , � (� 2 ) � 10 � 5 � 15 . � ����� ���-
��� ����������� ��������� �������� ��������� �1 . ��� ������� ����-
���� �������� ������� C1 ������� S ij1 :
 1     1     1      1      1      1      1      1      1      1
S12 � S14 � S17 � S 21 � S 25 � S 52 � S 54 � S 57 � S 71 � S 78 � 0,
  1       1      1     1                                          1
S 45 � S 67 � S 76 � S 78 � 1, S 87 � 2 . ����� max{0,1,2} � 2 � S87 . �������������,
(q, r ) � (8,7) .
       ��������� ��������� � 3 � � 4 , �������� �������������� �������
x87 � 1 � x87 � 0 . ��������� ������� C 3 � C 4 .

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

                         � 1   2  4  5  6  7  8                             �
                         1 +� 0   0  2  2  0  5                             0
                         3  0 +� 1   0  1  3  5                             0
                         4  2  2 +� 0   1  5  1                             0
               �4=       5  1  0  0 +� 1   0  1                             0       .
                         6  1  4  5  3 +� 0   4                             0
                         7  0  3  4  2  0 +� 0                              0
                         8  4  3  0  6  0 +� +�                             2
                         �  0  0  0  0  0  0  0                             2
     ��������� ������: � (� 3 ) � 14 � 2 � 16 , � (� 4 ) � 14 � 2 � 16 .

                                             21

Страницы