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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

4
njx
n
j
ij
,...,2,1,1
1
¦
, (1.10)
¦¦
o
n
i
n
j
ijij
xc
11
min
. (1.11)
Ɂɚɞɚɱɭ ɨ ɧɚɡɧɚɱɟɧɢɹɯ ɬɪɚɞɢɰɢɨɧɧɨ ɫɜɹɡɵɜɚɸɬ ɫ ɪɚɫɩɪɟɞɟɥɟɧɢɟɦ ɩɪɟ-
ɬɟɧɞɟɧɬɨɜ ɩɨ ɪɚɛɨɱɢɦ ɦɟɫɬɚɦ ɩɪɢ ɭɫɥɨɜɢɢ, ɱɬɨ ɤɨɥɢɱɟɫɬɜɨ ɪɚɛɨɱɢɯ ɦɟɫɬ
ɪɚɜɧɨ ɤɨɥɢɱɟɫɬɜɭ ɩɪɟɬɟɧɞɟɧɬɨɜ. Ɋɚɡɧɨɜɢɞɧɨɫɬɶɸ ɹɜɥɹɟɬɫɹ ɨɬɤɪɵɬɚɹ ɡɚɞɚ-
ɱɚ, ɜ ɤɨɬɨɪɨɣ ɱɢɫɥɨ ɪɚɛɨɱɢɯ ɦɟɫɬ ɧɟ ɫɨɜɩɚɞɚɟɬ ɫ ɱɢɫɥɨɦ ɩɪɟɬɟɧɞɟɧɬɨɜ. Ɂɚ-
ɞɚɱɚ ɹɜɥɹɟɬɫɹ ɨɫɨɛɵɦ ɱɚɫɬɧɵɦ ɫɥɭɱɚɟɦ ɬɪɚɧɫɩɨɪɬɧɨɣ ɡɚɞɚɱɢ ɥɢɧɟɣɧɨɝɨ
ɩɪɨɝɪɚɦɦɢɪɨɜɚɧɢɹ. Ɉɫɨɛɟɧɧɨɫɬɶɸ ɹɜɥɹɟɬɫɹ ɫɢɥɶɧɚɹ ɜɵɪɨɠɞɟɧɧɨɫɬɶ
ɡɚɞɚ-
ɱɢ ɨ ɧɚɡɧɚɱɟɧɢɹɯ, ɱɬɨ ɞɟɥɚɟɬ ɡɚɬɪɭɞɧɢɬɟɥɶɧɵɦ ɩɪɢɦɟɧɟɧɢɟ ɬɪɚɞɢɰɢɨɧɧɨɝɨ
ɦɟɬɨɞɚ ɩɨɬɟɧɰɢɚɥɨɜ.
2) Ɂɚɞɚɱɚ ɤɨɦɦɢɜɨɹɠɟɪɚ.
^`
1,0
ij
x , (1.12)
nix
n
i
ij
,...,2,1,1
1
¦
, (1.13)
njx
n
j
ij
,...,2,1,1
1
¦
. (1.14)
Ⱦɨɩɨɥɧɢɬɟɥɶɧɨɟ ɬɪɟɛɨɜɚɧɢɟ ɨɬɫɭɬɫɬɜɢɹ ɩɨɞɰɢɤɥɨɜ (1.15)
¦¦
o
n
i
n
j
ijij
xc
11
min
. (1.16)
Ɂɚɞɚɱɚ ɤɨɦɦɢɜɨɹɠɟɪɚ ɨɬɥɢɱɚɟɬɫɹ ɨɬ ɡɚɞɚɱɢ ɨ ɧɚɡɧɚɱɟɧɢɹɯ ɭɫɥɨɜɢɟɦ
(1.15), ɤɨɬɨɪɨɟ ɜɨɡɧɢɤɚɟɬ ɜ ɫɜɹɡɢ ɫ ɬɟɦ, ɱɬɨ ɜ ɞɚɧɧɨɣ ɡɚɞɚɱɟ ɢɳɟɬɫɹ
ɦɚɪ-
ɲɪɭɬ
. ɂɦɟɟɬɫɹ ɬɪɟɛɨɜɚɧɢɟ ɩɪɨɯɨɠɞɟɧɢɹ ɱɟɪɟɡ ɤɚɠɞɵɣ ɢɡ n ɝɨɪɨɞɨɜ ɪɨɜɧɨ
ɩɨ ɨɞɧɨɦɭ ɪɚɡɭ. ɉɪɢ ɷɬɨɦ ɰɟɥɟɜɚɹ ɮɭɧɤɰɢɹ (1.16) ɦɨɠɟɬ, ɧɚɩɪɢɦɟɪ, ɨɛɨ-
ɡɧɚɱɚɬɶ ɫɭɦɦɚɪɧɨɟ ɪɚɫɫɬɨɹɧɢɟ ɦɚɪɲɪɭɬɚ.
ɍɫɥɨɜɢɟ (1.15) ɦɨɠɟɬ ɛɵɬɶ ɡɚɩɢɫɚɧɨ ɚɧɚɥɢɬɢɱɟɫɤɢ, ɧɚɩɪɢɦɟɪ, ɜ ɜɢɞɟ
,,1,,1 njinnxuu
jiji
d
(1.15)
ɝɞɟ
2,...,2,1,0 nu
i
— ɰɟɥɵɟ, ji z ,
,1,1 ni nj ,1
.
ɉɪɢ ɩɨɫɬɪɨɟɧɢɢ ɦɟɬɨɞɨɜ ɪɟɲɟɧɢɹ ɱɚɫɬɨ ɭɫɥɨɜɢɟ (1.15) ɭɱɢɬɵɜɚɟɬɫɹ
ɚɥɝɨɪɢɬɦɢɱɟɫɤɢ.
Ɂɚɞɚɱɚ ɤɨɦɦɢɜɨɹɠɟɪɚ ɢɡɜɟɫɬɧɚ ɜ ɩɪɢɥɨɠɟɧɢɹɯ ɤɚɤ ɡɚɞɚɱɚ ɨ ɩɟɪɟɧɚ-
ɥɚɞɤɚɯ, ɜɨɡɧɢɤɚɸɳɚɹ ɩɪɢ ɨɩɬɢɦɢɡɚɰɢɢ ɡɚɝɪɭɡɤɢ ɨɛɨɪɭɞɨɜɚɧɢɹ.
3) Ɂɚɞɚɱɚ ɨ ɦɢɧɢɦɚɥɶɧɨɦ ɩɨɤɪɵɬɢɢ.
^`
1,0
ij
a , (1.17)
^`
1,0
j
x , (1.18) 
                                  n
                                 � xij � 1,      j � 1,2,..., n ,   (1.10)
                                 j �1
                                  n     n
                                 �� cij xij � min .                 (1.11)
                                 i �1 j �1


     ������ � ����������� ����������� ��������� � �������������� ���-
��������� �� ������� ������ ��� �������, ��� ���������� ������� ����
����� ���������� ������������. �������������� �������� �������� ����-
��, � ������� ����� ������� ���� �� ��������� � ������ ������������. ��-
���� �������� ������ ������� ������� ������������ ������ ���������
����������������. ������������ �������� ������� ������������� ����-
�� � �����������, ��� ������ ��������������� ���������� �������������
������ �����������.

  2) ������ ������������.
               xij � �0,1� ,                                        (1.12)
                 n
                � xij � 1,   i � 1,2,..., n ,                       (1.13)
                i �1
                  n
                � xij � 1,   j � 1,2,..., n .                       (1.14)
                j �1
�������������� ���������� ���������� ���������                      (1.15)
                 n     n
                �� cij xij � min .                                  (1.16)
                i �1 j �1
     ������ ������������ ���������� �� ������ � ����������� ��������
(1.15), ������� ��������� � ����� � ���, ��� � ������ ������ ������ ���-
����. ������� ���������� ����������� ����� ������ �� n ������� �����
�� ������ ����. ��� ���� ������� ������� (1.16) �����, ��������, ���-
������� ��������� ���������� ��������.
     ������� (1.15) ����� ���� �������� ������������, ��������, � ����
                         ui � u j � nxi j � n � 1, i, j � 1, n,    (1.15)
��� ui � 0,1, 2,..., n � 2 — �����, i � j , i � 1, n � 1, j � 1, n .
    ��� ���������� ������� ������� ����� ������� (1.15) �����������
��������������.
    ������ ������������ �������� � ����������� ��� ������ � ������-
������, ����������� ��� ����������� �������� ������������.

  3) ������ � ����������� ��������.
                          aij � �0,1�,                              (1.17)
                                 x j � �0,1�,                       (1.18)
                                             4

Страницы