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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

36
 ɰɟɥɟɜɚɹ ɮɭɧɤɰɢɹ ɞɨɥɠɧɚ ɛɵɬɶ ɚɞɞɢɬɢɜɧɨɣ:

i
N
i
i
xgxG
¦
1
.
ɍɤɚɡɚɧɧɵɟ ɫɜɨɣɫɬɜɚ ɩɨɡɜɨɥɹɸɬ ɨɫɭɳɟɫɬɜɢɬɶ
ɢɧɜɚɪɢɚɧɬɧɨɟ ɩɨɝɪɭɠɟ-
ɧɢɟ ɢɫɯɨɞɧɨɣ ɡɚɞɚɱɢ ɜ
ɫɟɦɟɣɫɬɜɨ ɚɧɚɥɨɝɢɱɧɵɯ ɡɚɞɚɱ. ɋɪɟɞɢ ɡɚɞɚɱ ɷɬɨɝɨ
ɫɟɦɟɣɫɬɜɚ ɧɚɯɨɞɹɬɫɹ, ɜ ɱɚɫɬɧɨɫɬɢ, ɡɚɞɚɱɢ ɫ ɨɞɧɨɣ ɩɟɪɟɦɟɧɧɨɣ. Ɍɚɤɢɟ ɡɚɞɚ-
ɱɢ, ɤɚɤ ɩɪɚɜɢɥɨ, ɥɟɝɤɨ ɪɟɲɚɸɬɫɹ. ɋ ɩɨɦɨɳɶɸ ɪɟɤɭɪɪɟɧɬɧɵɯ ɫɨɨɬɧɨɲɟɧɢɣ
(ɭɪɚɜɧɟɧɢɣ Ȼɟɥɥɦɚɧɚ) ɭɫɬɚɧɚɜɥɢɜɚɟɬɫɹ ɫɜɹɡɶ ɦɟɠɞɭ ɡɚɞɚɱɚɦɢ ɛɨɥɶɲɢɯ
ɪɚɡɦɟɪɨɜ ɫ ɡɚɞɚɱɚɦɢ ɦɟɧɶɲɢɯ ɪɚɡɦɟɪɨɜ: ɡɚɞɚɱɢ ɫ ɞɜɭɦɹ ɩɟɪɟɦɟɧɧɵɦɢ ɪɟ-
ɲɚɸɬɫɹ ɫ ɢɫɩɨɥɶɡɨɜɚɧɢɟɦ ɨɞɧɨɦɟɪɧɵɯ, ɡɚɞɚɱɢ ɫ ɬɪɟɦɹ ɩɟɪɟɦɟɧɧɵɦɢ – ɫ
ɢɫɩɨɥɶɡɨɜɚɧɢɟɦ ɞɜɭɦɟɪɧɵɯ ɢ ɬ. ɞ. ɉɪɢ ɷɬɨɦ ɤɚɠɞɵɣ ɪɚɡ ɪɟɲɚɸɬɫɹ ɡɚɞɚɱɢ
ɩɨɢɫɤɚ ɩɨ ɨɞɧɨɣ ɩɟɪɟɦɟɧɧɨɣ.
5.1. ɉɪɢɧɰɢɩ ɨɩɬɢɦɚɥɶɧɨɫɬɢ Ȼɟɥɥɦɚɧɚ
ɉɪɢɧɰɢɩ ɨɩɬɢɦɚɥɶɧɨɫɬɢ ɡɚɤɥɸɱɚɟɬɫɹ ɜ ɬɨɦ, ɱɬɨ,
ɤɚɤɨɜɵ ɛɵ ɧɢ ɛɵɥɢ
ɫɨɫɬɨɹɧɢɟ ɨɛɴɟɤɬɚ ɜ ɧɚɱɚɥɟ ɥɸɛɨɝɨ ɲɚɝɚ ɢ ɪɟɲɟɧɢɟ, ɩɪɢɧɢɦɚɟɦɨɟ
ɧɚ
ɷɬɨɦ ɲɚɝɟ, ɩɨɫɥɟɞɭɸɳɟɟ ɪɟɲɟɧɢɟ ɞɨɥɠɧɨ ɛɵɬɶ ɨɩɬɢɦɚɥɶɧɵɦ
ɨɬɧɨ-
ɫɢɬɟɥɶɧɨ ɬɨɝɨ ɫɨɫɬɨɹɧɢɹ, ɜ ɤɨɬɨɪɨɟ ɩɟɪɟɯɨɞɢɬ ɨɛɴɟɤɬ
ɜ ɪɟɡɭɥɶɬɚɬɟ
ɩɪɢɧɹɬɨɝɨ ɪɟɲɟɧɢɹ.
ɗɬɨ ɫɜɨɣɫɬɜɨ ɨɩɬɢɦɚɥɶɧɨɝɨ ɩɨɜɟɞɟɧɢɹ.
ɇɚ ɟɝɨ ɨɫɧɨɜɟ ɡɚɩɢɫɵɜɚɟɬɫɹ
ɪɟɤɭɪɪɟɧɬɧɨɟ ɭɪɚɜɧɟɧɢɟ Ȼɟɥɥɦɚɧɚ (ɞɥɹ ɡɚɞɚɱɢ ɦɚɤɫɢɦɢɡɚɰɢɢ).
 ^`
.,max
1 kkkkk
x
kk
xpTfxgpf
k
Ɂɞɟɫɶ ɢɫɩɨɥɶɡɨɜɚɧɵ ɫɥɟɞɭɸɳɢɟ ɨɛɨɡɧɚɱɟɧɢɹ:
k
p
– ɫɨɫɬɨɹɧɢɟ ɨɛɴɟɤɬɚ ɜ ɧɚɱɚɥɟ k-ɝɨ ɲɚɝɚ;
k
x
– ɪɟɲɟɧɢɟ, ɩɪɢɧɢɦɚɟɦɨɟ ɧɚ k-ɦɲɚɝɟ;

kk
pf
– ɨɩɬɢɦɚɥɶɧɨɟ ɡɧɚɱɟɧɢɟ ɰɟɥɟɜɨɣ ɮɭɧɤɰɢɢ ɜ ɡɚɞɚɱɟ ɫ k ɩɟɪɟɦɟɧɧɵɦɢ;

kkk
xpTf ,
1
— ɨɩɬɢɦɚɥɶɧɨɟ ɡɧɚɱɟɧɢɟ ɰɟɥɟɜɨɣ ɮɭɧɤɰɢɢ ɜ ɡɚɞɚɱɟ ɫ (k-1)-ɣ
ɩɟɪɟɦɟɧɧɨɣ;
)(
kk
xg
— ɡɧɚɱɟɧɢɟ ɰɟɥɟɜɨɣ ɮɭɧɤɰɢɢ, ɩɨɥɭɱɟɧɧɨɟ ɜ ɪɟɡɭɥɶɬɚɬɟ ɪɟɲɟɧɢɹ,
ɩɪɢɧɹɬɨɝɨ ɧɚ ɞɚɧɧɨɦ ɲɚɝɟ;

kkk
xpTp ,
1
— ɭɪɚɜɧɟɧɢɟ ɩɪɨɰɟɫɫɚ, ɤɨɬɨɪɨɟ ɩɨɤɚɡɵɜɚɟɬ, ɤɚɤ ɦɟɧɹɟɬɫɹ
ɫɨɫɬɨɹɧɢɟ ɨɛɴɟɤɬɚ
1k
p
ɜ ɪɟɡɭɥɶɬɚɬɟ ɩɪɢɧɹɬɨɝɨ ɪɟɲɟɧɢɹ
k
x
.
ɉɪɨɰɟɫɫ ɪɟɲɟɧɢɹ ɡɚɤɥɸɱɚɟɬɫɹ ɜ ɬɨɦ, ɱɬɨ ɫɧɚɱɚɥɚ ɪɟɲɚɸɬɫɹ ɡɚɞɚɱɢ,
ɨɛɨɡɧɚɱɟɧɧɵɟ ɱɟɪɟɡ

11
pf
, ɝɞɟ
1
p
— ɥɸɛɨɟ ɜɨɡɦɨɠɧɨɟ ɫɨɫɬɨɹɧɢɟ (ɞɨɩɭɫ-
ɬɢɦɨɟ ɦɧɨɠɟɫɬɜɨ ɫɨɫɬɨɹɧɢɣ ɨɩɪɟɞɟɥɹɟɬɫɹ ɢɧɞɢɜɢɞɭɚɥɶɧɨ ɜ ɤɚɠɞɨɣ ɡɚɞɚ-
ɱɟ). Ɂɚɬɟɦ, ɢɫɩɨɥɶɡɭɹ ɩɨɥɭɱɟɧɧɵɟ ɪɟɡɭɥɶɬɚɬɵ, ɫ ɩɨɦɨɳɶɸ ɪɟɤɭɪɪɟɧɬɧɨɝɨ
ɭɪɚɜɧɟɧɢɹ ɪɟɲɚɸɬɫɹ ɡɚɞɚɱɢ ɫ ɞɜɭɦɹ ɩɟɪɟɦɟɧɧɵɦɢ
                                                                                    N
   �� ������� ������� ������ ���� ����������: G � x � � � g i � xi � .
                                                                                    i �1
     ��������� �������� ��������� ����������� ������������ �������-
��� �������� ������ � ��������� ����������� �����. ����� ����� �����
��������� ���������, � ���������, ������ � ����� ����������. ����� ����-
��, ��� �������, ����� ��������. � ������� ������������ �����������
(��������� ��������) ��������������� ����� ����� �������� �������
�������� � �������� ������� ��������: ������ � ����� ����������� ��-
������ � �������������� ����������, ������ � ����� ����������� – �
�������������� ��������� � �. �. ��� ���� ������ ��� �������� ������
������ �� ����� ����������.

                  5.1. ������� ������������� ��������

    ������� ������������� ����������� � ���, ���, ������ �� �� ����
��������� ������� � ������ ������ ���� � �������, ����������� ��
���� ����, ����������� ������� ������ ���� ����������� ����-
�������� ���� ���������, � ������� ��������� ������ � ����������
��������� �������.
    ��� �������� ������������ ���������. �� ��� ������ ������������
������������ ��������� �������� (��� ������ ������������).

                         f k � p k � � max�g k � xk � � f k �1 �T � p k , xk ���.
                                       xk



         ����� ������������ ��������� �����������:
 p k – ��������� ������� � ������ k-�� ����;
xk – �������, ����������� �� k-� ����;
 f k � pk � – ����������� �������� ������� ������� � ������ � k �����������;
 f k �1 �T � p k , xk �� — ����������� �������� ������� ������� � ������ � (k-1)-�
����������;
g k ( xk ) — �������� ������� �������, ���������� � ���������� �������,
��������� �� ������ ����;
 pk �1 � T � pk , xk � — ��������� ��������, ������� ����������, ��� ��������
��������� ������� pk �1 � ���������� ��������� ������� xk .
         ������� ������� ����������� � ���, ��� ������� �������� ������,
������������ ����� f1 � p1 � , ��� p1 — ����� ��������� ��������� (�����-
����� ��������� ��������� ������������ ������������� � ������ ����-
��). �����, ��������� ���������� ����������, � ������� �������������
���������                 ��������      ������     �     �����      �����������


                                              36

Страницы