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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

20
¸
¸
¸
¸
¸
¸
¸
¸
¸
¸
¸
¹
·
¨
¨
¨
¨
¨
¨
¨
¨
¨
¨
¨
©
§
f
f
f
f
f
f
f
f
0382787
0124661
5146983
3242154
2631264
7542323
6987617
7254235
C
.
ȼɵɛɟɪɟɦ ɫɬɪɚɬɟɝɢɸ «ɩɨ ɦɢɧɢɦɭɦɭ ɨɰɟɧɤɢ». ɉɨɥɨɠɢɦ
f
R
. Ɉɫɭ-
ɳɟɫɬɜɢɜ ɨɩɟɪɚɰɢɸ ɩɪɢɜɟɞɟɧɢɹ, ɩɨɥɭɱɚɟɦ ɦɚɬɪɢɰɭ
0
C
.
ȼ ɩɨɫɥɟɞɧɟɦ ɫɬɨɥɛɰɟ ɢ ɧɢɠɧɟɣ ɫɬɪɨɤɟ ɡɚɩɢɫɚɧɵ ɩɪɢɜɨɞɹɳɢɟ ɤɨɧɫɬɚɧ-
ɬɵ. ɂɯ ɫɭɦɦɚ S=10, ɬɨ ɟɫɬɶ
10)(
0
:
[
. Ⱦɥɹ ɤɚɠɞɨɝɨ ɧɭɥɟɜɨɝɨ ɷɥɟɦɟɧɬɚ
ɦɚɬɪɢɰɵ
0
C
ɫɱɢɬɚɟɦ
0
ij
S :
,0
0
71
0
35
0
31
0
17
SSSS
0000
14 45 53 67
SSSS
00
76 78
SS1,
,2
0
87
S 3
0
32
S
,
5
0
23
S
. ɂɦɟɟɦ
0
23
5}5,3,2,1,0max{ S
. ɋɥɟ-
ɞɨɜɚɬɟɥɶɧɨ, )3,2(),(
r
q . Ɏɨɪɦɢɪɭɟɦ ɦɧɨɠɟɫɬɜɚ
1
:
ɢ
2
:
, ɞɨɛɚɜɥɹɹ ɫɨɨɬ-
ɜɟɬɫɬɜɟɧɧɨ ɭɫɥɨɜɢɹ
1
23
x
ɢ
0
23
x
. ȼɵɱɢɫɥɹɟɦ ɦɚɬɪɢɰɵ
1
C
ɢ
2
C
.
ʋ 1 2 3 4 5 6 7 8
D
1
+
f
3 1
0
2 2
0
5 2
2
5 +
f
0
5 6 6 8 5 1
3
0 0
+
f
1
0
1 3 5 2
4
2 5 1 +
f
0 1 5 1 1
.
5
2 4
0
1 +
f
2 1 2 1
6
1 7 8 5 3 +
f
0
4 1
7
0
6 6 4 2
0
+
f
0
0
8
6 8 7 2 8 2
0
+
f
0
ɋ
0
=
E
1 0 0 0 0 1 0 0
10
ʋ 1 2 4 5 6 7 8
D
1
+
f
0 0
2 6
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 1
,
6
1 4 5 3 +
f
0
4 0
7
0
3 4 2
0
+
f
0
0
8
6 5 2 8 2
0
+
f
0
ɋ
1
=
E
0 3 0 0 0 0 0
4
                 �� � 5   3  2  4  5  2  7 �
                 �                           �
                 � 7  � � 1  6  7  8  9  6 �
                 � 3   2 �� 3   2  4  5  7 �
                 �                           �
                 � 4   6  2 �� 1   3  6  2 �
              C ��                             .
                   4   5  1  2 �� 4   2  3 �
                 �                           �
                 � 3   8  9  6  4 �� 1   5 �
                 �                           �
                 � 1   6  6  4  2  1 �� 0 �
                 � 7
                 �     8  7  2  8  3  0 � � ��

    ������� ��������� «�� �������� ������». ������� R � �� . ���-
������� �������� ����������, �������� ������� C 0 .

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

    � ��������� ������� � ������ ������ �������� ���������� �������-
��. �� ����� S=10, �� ���� � (� 0 ) � 10 . ��� ������� �������� ��������
������� C 0 ������� S ij0 : S170 � S 31
                                     0      0
                                        � S 35     0
                                               � S 71 � 0, S140 � S45
                                                                   0     0
                                                                      � S53 � S670 �
                     0         0          0                                     0
� S760 � S780 � 1, S 87 � 2, S 32 � 3 , S 23 � 5 . ����� max{0,1,2,3,5} � 5 � S 23 . ���-
����������, (q, r ) � (2,3) . ��������� ��������� �1 � � 2 , �������� ����-
���������� ������� x23 � 1 � x23 � 0 . ��������� ������� C1 � C 2 .

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

                                             20

Страницы