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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

9
0
ij
c . Ɍɨɝɞɚ
0)(
0
XL
, ɫɥɟɞɨɜɚɬɟɥɶɧɨ,
0
X ɨɩɬɢɦɚɥɶɧɚɹ ɬɨɱɤɚ. Ɍɟɨɪɟɦɚ
ɞɨɤɚɡɚɧɚ.
2.2. ȼɟɧɝɟɪɫɤɢɣ ɦɟɬɨɞ
Ⱥɥɝɨɪɢɬɦ ɜɟɧɝɟɪɫɤɨɝɨ ɦɟɬɨɞɚ ɜɤɥɸɱɚɟɬ ɜ ɫɟɛɹ 4 ɷɬɚɩɚ.
1. ɉɪɢɜɟɞɟɧɢɟ ɦɚɬɪɢɰɵ.
2. ȼɵɱɢɫɥɟɧɢɟ ɦɚɤɫɢɦɚɥɶɧɨɝɨ ɱɢɫɥɚ
k ɧɟɡɚɜɢɫɢɦɵɯ ɧɭɥɟɣ ɜ ɩɪɢɜɟɞɟɧ-
ɧɨɣ ɦɚɬɪɢɰɟ.
3. ɉɨɥɭɱɟɧɢɟ ɧɨɜɵɯ ɧɭɥɟɣ ɩɪɢ n
k .
4. Ɉɬɵɫɤɚɧɢɟ n ɧɟɡɚɜɢɫɢɦɵɯ ɧɭɥɟɣ ɩɪɢ n
k .
Ɋɚɫɫɦɨɬɪɢɦ ɤɚɠɞɵɣ ɷɬɚɩ ɩɨɞɪɨɛɧɟɟ.
ɗɬɚɩ 1
Ɇɚɬɪɢɰɚ
C
ɩɨɪɹɞɤɚ nn u ɧɚɡɵɜɚɟɬɫɹ ɩɪɢɜɟɞɟɧɧɨɣ, ɟɫɥɢ ɜɫɟ ɟɟ ɷɥɟ-
ɦɟɧɬɵ ɧɟɨɬɪɢɰɚɬɟɥɶɧɵ ɢ, ɤɪɨɦɟ ɬɨɝɨ, ɜ ɤɚɠɞɨɣ ɫɬɪɨɤɟ ɢ ɜ ɤɚɠɞɨɦ ɫɬɨɥɛɰɟ
ɢɦɟɸɬɫɹ ɧɭɥɟɜɵɟ ɷɥɟɦɟɧɬɵ.
Ɍɚɤɢɦ ɨɛɪɚɡɨɦ, ɩɪɢɜɟɞɟɧɧɚɹ ɦɚɬɪɢɰɚ
C
ɭɞɨɜɥɟɬɜɨɪɹɟɬ ɞɜɭɦ ɭɫɥɨɜɢɹɦ:
1. jic
ij
,,0 t ;
2. ic
ij
,0 ɢ jc
ij
,0.
Ⱦɥɹ ɩɪɢɜɟɞɟɧɢɹ ɦɚɬɪɢɰɵ
C
ɫ ɷɥɟɦɟɧɬɚɦɢ 0t
ij
c ɧɭɠɧɨ ɜɨɫɩɨɥɶɡɨ-
ɜɚɬɶɫɹ ɷɤɜɢɜɚɥɟɧɬɧɵɦɢ ɩɪɟɨɛɪɚɡɨɜɚɧɢɹɦɢ (4). ɉɪɢ ɷɬɨɦ ɜɧɚɱɚɥɟ ɨɫɭɳɟɫɬ-
ɜɥɹɟɬɫɹ ɩɪɢɜɟɞɟɧɢɟ ɦɚɬɪɢɰɵ ɩɨ ɫɬɪɨɤɚɦ (ɩɨ ɫɬɨɥɛɰɚɦ), ɬ. ɟ. ɢɳɟɬɫɹ ɧɚɢ-
ɦɟɧɶɲɢɣ ɷɥɟɦɟɧɬ
i
a
ɜ ɤɚɠɞɨɣ ɫɬɪɨɤɟ ɢ ɨɫɭɳɟɫɬɜɥɹɟɬɫɹ ɩɟɪɟɯɨɞ ɤ ɦɚɬɪɢɰɟ
1
C
ɫ ɷɥɟɦɟɧɬɚɦɢ c
1
1
D
ijij
cc . ȿɫɥɢ ɦɚɬɪɢɰɚ
1
C
ɨɤɚɡɵɜɚɟɬɫɹ ɧɟɩɪɢɜɟ-
ɞɟɧɧɨɣ ɩɨ ɫɬɨɥɛɰɚɦ (ɩɨ ɫɬɪɨɤɚɦ), ɬɨ ɢɳɟɬɫɹ ɧɚɢɦɟɧɶɲɢɣ ɜɚɪɢɚɧɬ
j
B ɜɤɚ-
ɠɞɨɦ ɫɬɨɥɛɰɟ ɢ ɨɫɭɳɟɫɬɜɥɹɟɬɫɹ ɩɟɪɟɯɨɞ ɤ ɦɚɬɪɢɰɟ
2
C
, ɷɥɟɦɟɧɬɵ ɤɨɬɨɪɨɣ
ɜɵɱɢɫɥɹɸɬɫɹ ɫɥɟɞɭɸɳɢɦ ɨɛɪɚɡɨɦ:
jijij
cc
E
12
. Ɇɚɬɪɢɰɚ
2
C
ɩɨ ɩɨɫɬɪɨɟ-
ɧɢɸ ɹɜɥɹɟɬɫɹ ɩɪɢɜɟɞɟɧɧɨɣ.
cij � 0 . ����� L( X 0 ) � 0 , �������������, X 0 ����������� �����. �������
��������.


                              2.2. ���������� �����

  �������� ����������� ������ �������� � ���� 4 �����.

   1. ���������� �������.
   2. ���������� ������������� ����� k ����������� ����� � ��������-
      ��� �������.
   3. ��������� ����� ����� ��� k � n .
   4. ��������� n ����������� ����� ��� k � n .

  ���������� ������ ���� ���������.

                                ���� 1
    ������� C ������� n � n ���������� �����������, ���� ��� �� ���-
����� �������������� �, ����� ����, � ������ ������ � � ������ �������
������� ������� ��������.
    ����� �������, ����������� ������� C ������������� ���� ��������:
    1. cij � 0, �i, j ;
    2. � cij � 0, �i � � cij � 0, �j .
     ��� ���������� ������� C � ���������� cij � 0 ����� ���������-
������ �������������� ���������������� (4). ��� ���� ������� �������-
������� ���������� ������� �� ������� (�� ��������), �. �. ������ ���-
������� ������� ai � ������ ������ � �������������� ������� � �������
C 1 � ���������� c cij1 � cij � �1 . ���� ������� C 1 ����������� �������-
������ �� �������� (�� �������), �� ������ ���������� ������� B j � ��-
���� ������� � �������������� ������� � ������� C 2 , �������� �������
����������� ��������� �������: cij2 � cij1 � � j . ������� C 2 �� �������-
��� �������� �����������.




                                         9

Страницы