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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

23

¸
¸
¸
¸
¸
¸
¸
¸
¸
¸
¸
¹
·
¨
¨
¨
¨
¨
¨
¨
¨
¨
¨
¨
©
§
01000000
00100000
00000001
00001000
10000000
00010000
00000100
00000010
ij
x
ɫɨ ɡɧɚɱɟɧɢɟɦ ɰɟɥɟɜɨɣ ɮɭɧɤɰɢɢ 16
L
.
ɋɨɨɬɜɟɬɫɬɜɭɸɳɢɣ ɦɚɪɲɪɭɬ: 1-2-3-5-4-8-7-5-1.
Ɇɟɧɹɟɦ ɪɟɤɨɪɞ: 16
R
, ɢ ɩɨɞɦɧɨɠɟɫɬɜɚ
1412108764
::::::: ,,,,,,
ɜɵɛɪɚɫɵɜɚɸɬɫɹ ɢɡ ɪɚɫɫɦɨɬɪɟɧɢɹ ɤɚɤ ɧɟɩɟɪɫɩɟɤɬɢɜɧɵɟ (ɢɯ ɨɰɟɧɤɢ ɩɪɟɜɵ-
ɲɚɸɬ ɢɥɢ ɪɚɜɧɵ ɪɟɤɨɪɞɧɨɦɭ ɡɧɚɱɟɧɢɸ). Ɍɚɤ ɤɚɤ ɛɨɥɶɲɟ ɩɨɞɦɧɨɠɟɫɬɜ ɞɥɹ
ɜɟɬɜɥɟɧɢɹ ɧɟ ɨɫɬɚɥɨɫɶ, ɬɨ ɧɚɣɞɟɧɧɚɹ ɬɨɱɤɚ ɹɜɥɹɟɬɫɹ ɨɩɬɢɦɚɥɶɧɵɦ ɪɟɲɟɧɢ-
ɟɦ. Ɉɞɧɚɤɨ ɨɧɨ ɦɨɠɟɬ ɛɵɬɶ ɧɟ ɟɞɢɧɫɬɜɟɧɧɵɦ, ɬɚɤ ɤɚɤ ɩɨɞɦɧɨɠɟɫɬɜɚ
74
:: ,
ɬɚɤ ɠɟ ɢɦɟɸɬ ɨɰɟɧɤɭ 16. ɑɬɨɛɵ ɜɵɹɫɧɢɬɶ, ɫɭɳɟɫɬɜɭɸɬ ɥɢ ɞɪɭɝɢɟ
ɪɟɲɟɧɢɹ, ɧɭɠɧɨ ɨɫɭɳɟɫɬɜɥɹɬɶ ɞɚɥɶɧɟɣɲɟɟ ɜɟɬɜɥɟɧɢɟ ɷɬɢɯ ɦɧɨɠɟɫɬɜ.
Ⱦɟɪɟɜɨ ɜɚɪɢɚɧɬɨɜ ɜ ɪɚɫɫɦɨɬɪɟɧɧɨɦ ɩɪɢɦɟɪɟ ɢɦɟɟɬ ɫɥɟɞɭɸɳɢɣ ɜɢɞ.
10
14
15
16
16
15
18
16
18
16
17
16
19
16
17
x
23
=1 x
23
=0
x
87
=1 x
87
=0
x
32
=1 x
32
=0
x
61
=1 x
61
=0 x
87
=1 x
87
=0
x
76
=1 x
76
=0
x
35
=1 x
35
=0
                                        �0     1 0 0 0 0 0 0�
                                        �                     �
                                        �0     0 1 0 0 0 0 0�
                                        �0     0 0 0 1 0 0 0�
                                        �                     �
                              �xij � � �� 0    0 0 0 0 0 0 1�
                                          0    0 0 1 0 0 0 0�
                                        �                     �
                                        �1     0 0 0 0 0 0 0�
                                        �                     �
                                        �0     0 0 0 0 1 0 0�
                                        �0
                                        �      0 0 0 0 0 1 0 ��

�� ��������� ������� ������� L � 16 .
      ��������������� �������: 1-2-3-5-4-8-7-5-1.
      ������ ������: R � 16 , � ������������ � 4 , � 6 , � 7 , � 8 , �10 , �12 , �14
������������� �� ������������ ��� ��������������� (�� ������ �����-
���� ��� ����� ���������� ��������). ��� ��� ������ ����������� ���
��������� �� ��������, �� ��������� ����� �������� ����������� ������-
��. ������ ��� ����� ���� �� ������������, ��� ��� ������������
� 4 , � 7 ��� �� ����� ������ 16. ����� ��������, ���������� �� ������
�������, ����� ������������ ���������� ��������� ���� ��������.
      ������ ��������� � ������������� ������� ����� ��������� ���.
                                   x23=1      10         x23=0

                                  x87=1         14    x87=0            15
                                                               x32=1           x32=0
                               16                    16           15           18
                    x61=1              x61=0              x87=1        x87=0

                     16                   18              16           17
           x76=1           x76=0

            16               19
   x35=1           x35=0

   16               17




                                                23

Страницы