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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

14
1. ɋɬɪɭɤɬɭɪɚ ɦɟɬɨɞɚ ɞɨɫɬɚɬɨɱɧɨ ɭɧɢɜɟɪɫɚɥɶɧɚ ɢ ɦɨɠɟɬ ɛɵɬɶ ɢɫɩɨɥɶɡɨ-
ɜɚɧɚ ɞɥɹ ɪɟɲɟɧɢɹ ɲɢɪɨɤɨɝɨ ɤɥɚɫɫɚ ɡɚɞɚɱ.
2. Ɇɟɬɨɞ ɨɛɥɚɞɚɟɬ ɩɨɬɟɧɰɢɚɥɶɧɵɦɢ ɜɨɡɦɨɠɧɨɫɬɹɦɢ ɞɥɹ ɫɭɳɟɫɬɜɟɧɧɨɝɨ
ɫɨɤɪɚɳɟɧɢɹ ɩɟɪɟɛɨɪɚ.
3. ȼɧɟɲɧɟɟ ɭɩɪɚɜɥɟɧɢɟ ɩɚɪɚɦɟɬɪɚɦɢ ɦɟɬɨɞɚ ɩɨɡɜɨɥɹɟɬ ɮɨɪɦɢɪɨɜɚɬɶ
ɪɚɡɥɢɱɧɵɟ ɩɪɢɛɥɢɠɟɧɧɵɟ ɚɥɝɨɪɢɬɦɵ.
Ɋɚɫɫɦɨɬɪɢɦ ɡɚɞɚɱɭ ɞɢɫɤɪɟɬɧɨɣ ɨɩɬɢɦɢɡɚɰɢɢ ɜɢɞɚ
,min)(
:
o
x
x
M
(2.1)
ɝɞɟ
:
– ɧɟɤɨɬɨɪɨɟ ɤɨɧɟɱɧɨɟ ɦɧɨɠɟɫɬɜɨ ɢɡ
n
R
.
Ⱦɥɹ ɪɟɲɟɧɢɹ ɞɚɧɧɨɝɨ ɤɥɚɫɫɚ ɡɚɞɚɱ ɱɚɫɬɨ ɢɫɩɨɥɶɡɭɟɬɫɹ ɦɟɬɨɞ ɜɟɬɜɟɣ
ɢ ɝɪɚɧɢɰ, ɜ ɨɫɧɨɜɟ ɤɨɬɨɪɨɝɨ ɥɟɠɚɬ ɫɥɟɞɭɸɳɢɟ ɨɫɧɨɜɧɵɟ ɦɨɞɭɥɢ:
1) ɩɨɫɬɪɨɟɧɢɟ ɞɟɪɟɜɚ ɞɨɩɭɫɬɢɦɵɯ ɜɚɪɢɚɧɬɨɜ;
2) ɫɨɫɬɚɜɥɟɧɢɟ ɨɰɟɧɨɱɧɵɯ ɡɚɞɚɱ;
3) ɨɩɪɟɞɟɥɟɧɢɟ ɩɪɚɜɢɥɚ ɨɛɯɨɞɚ ɞɟɪɟɜɚ ɜɚɪɢɚɧɬɨɜ;
4) ɨɬɛɪɚɫɵɜɚɧɢɟ «ɧɟɩɟɪɫɩɟɤɬɢɜɧɵɯ» ɦɧɨɠɟɫɬɜ ɜɚɪɢɚɧɬɨɜ;
5) ɩɪɨɜɟɪɤɚ ɧɚ ɨɫɬɚɧɨɜ.
Ɋɚɫɫɦɨɬɪɢɦ ɩɨɞɪɨɛɧɨ ɤɚɠɞɵɣ ɢɡ ɭɤɚɡɚɧɧɵɯ ɦɨɞɭɥɟɣ.
1.
ɉɨɫɬɪɨɟɧɢɟ ɞɟɪɟɜɚ ɜɚɪɢɚɧɬɨɜ ɨɫɭɳɟɫɬɜɥɹɟɬɫɹ ɧɚ ɨɫɧɨɜɟ ɪɚɡɛɢɟɧɢɹ
ɦɧɨɠɟɫɬɜ ɧɚ ɤɨɧɟɱɧɨɟ ɱɢɫɥɨ ɧɟɩɟɪɟɫɟɤɚɸɳɢɯɫɹ ɩɨɞɦɧɨɠɟɫɬɜ. Ɏɚɤɬ ɪɚɡ-
ɛɢɟɧɢɹ ɦɧɨɠɟɫɬɜɚ ɧɚɡɵɜɚɟɬɫɹ
ɜɟɬɜɥɟɧɢɟɦ ɢ ɩɪɨɢɡɜɨɞɢɬɫɹ ɧɚ ɨɱɟɪɟɞɧɨɦ
ɲɚɝɟ ɦɟɬɨɞɚ ɜ ɫɨɨɬɜɟɬɫɬɜɢɢ ɫɨ ɫɮɨɪɦɭɥɢɪɨɜɚɧɧɵɦ ɡɚɪɚɧɟɟ ɩɪɚɜɢɥɨɦ. ɗɬɨ
ɩɪɚɜɢɥɨ ɫɜɹɡɚɧɨ ɫɨ ɫɩɟɰɢɮɢɤɨɣ ɤɨɧɤɪɟɬɧɨɝɨ ɞɨɩɭɫɬɢɦɨɝɨ ɦɧɨɠɟɫɬɜɚ ɢɫ-
ɫɥɟɞɭɟɦɨɣ ɡɚɞɚɱɢ. Ɉɞɧɚɤɨ ɟɫɥɢ ɢɫɯɨɞɧɚɹ ɡɚɞɚɱɚ ɫɪɟɞɢ ɩɪɨɱɢɯ ɢɦɟɟɬ ɨɝɪɚ-
ɧɢɱɟɧɢɹ ɜɢɞɚ
n1j01x
j
,},,{
(ɬ. ɟ. ɹɜɥɹɟɬɫɹ ɡɚɞɚɱɟɣ ɫ ɛɭɥɟɜɵɦɢ ɩɟɪɟ-
ɦɟɧɧɵɦɢ), ɬɨ ɦɨɠɧɨ ɜɨɫɩɨɥɶɡɨɜɚɬɶɫɹ ɭɧɢɜɟɪɫɚɥɶɧɵɦ ɩɪɚɜɢɥɨɦ ɜɟɬɜɥɟɧɢɹ:
,
21
:: :
ɝɞɟ
};:{ 1xx
i1
: : };:{ 0xx
i2
: :
i
– ɡɚɮɢɤɫɢɪɨ-
ɜɚɧɧɵɣ ɧɨɦɟɪ ɤɨɨɪɞɢɧɚɬɵ ni1
dd . ɉɨɪɹɞɨɤ ɮɢɤɫɢɪɨɜɚɧɢɹ ɤɨɨɪɞɢɧɚɬ
ɨɝɨɜɚɪɢɜɚɟɬɫɹ ɜ ɩɪɚɜɢɥɟ ɜɟɬɜɥɟɧɢɹ. Ɉɬɦɟɬɢɦ, ɱɬɨ ɩɪɚɜɢɥɨ ɪɚɡɛɢɟɧɢɹ ɦɧɨ-
ɠɟɫɬɜɚ ɧɚ ɩɨɞɦɧɨɠɟɫɬɜɚ ɜ ɤɨɧɤɪɟɬɧɨɣ ɡɚɞɚɱɟ ɦɨɠɟɬ ɛɵɬɶ ɧɟ ɟɞɢɧɫɬɜɟɧ-
ɧɵɦ.
2.
Ɉɰɟɧɤɨɣ ɮɭɧɤɰɢɢ )(
x
M
ɡɚɞɚɱɢ (1) ɧɚ ɦɧɨɠɟɫɬɜɟ
:
ɧɚɡɵɜɚɟɬɫɹ ɬɚɤɨɟ
ɱɢɫɥɨ )(:
[
[
, ɱɬɨ :t
x
x
,)(
[
M
. Ⱦɥɹ ɩɨɥɭɱɟɧɢɹ ɨɰɟɧɨɤ ɫɨɫɬɚɜɥɹɟɬɫɹ
ɨɰɟɧɨɱɧɚɹ ɡɚɞɚɱɚ, ɪɟɲɟɧɢɟ ɤɨɬɨɪɨɣ ɢɫɩɨɥɶɡɭɟɬɫɹ ɞɥɹ ɜɵɱɢɫɥɟɧɢɹ ɫɨɨɬɜɟɬ-
ɫɬɜɭɸɳɟɣ ɨɰɟɧɤɢ. Ʉ ɨɰɟɧɨɱɧɵɦ ɡɚɞɚɱɚɦ ɩɪɟɞɴɹɜɥɹɸɬɫɹ ɫɥɟɞɭɸɳɢɟ ɬɪɟ-
ɛɨɜɚɧɢɹ: ɫ ɨɞɧɨɣ ɫɬɨɪɨɧɵ, ɢɯ ɪɟɲɟɧɢɟ ɧɟ ɞɨɥɠɧɨ ɡɚɧɢɦɚɬɶ ɦɧɨɝɨ ɜɪɟɦɟɧɢ.
ɇɨ ɜɦɟɫɬɟ ɫ ɬɟɦ ɨɰɟɧɤɢ, ɩɨɥɭɱɟɧɧɵɟ ɫ ɢɯ ɩɨɦɨɳɶɸ, ɞɨɥɠɧɵ ɛɵɬɶ ɤɚɤ
ɦɨɠɧɨ ɬɨɱɧɟɟ (ɬ. ɟ. ɪɚɡɧɨɫɬɶ (
)(min)( x
M
[
:
:
) ɧɟ ɞɨɥɠɧɚ ɛɵɬɶ ɫɥɢɲɤɨɦ
ɛɨɥɶɲɨɣ). Ɍɚɤɢɟ ɬɪɟɛɨɜɚɧɢɹ ɨɛɴɹɫɧɹɸɬɫɹ ɬɟɦ, ɱɬɨ ɢɦɟɧɧɨ ɨɰɟɧɤɢ ɢɫ-
ɩɨɥɶɡɭɸɬɫɹ ɩɪɢ ɨɬɛɪɚɫɵɜɚɧɢɢ ɧɟɩɟɪɫɩɟɤɬɢɜɧɵɯ ɦɧɨɠɟɫɬɜ (ɩɪɢ ɫɨɤɪɚɳɟ-
ɧɢɢ ɩɟɪɟɛɨɪɚ). ɉɪɢ ɫɨɫɬɚɜɥɟɧɢɢ ɨɰɟɧɨɱɧɵɯ ɡɚɞɚɱ ɦɨɠɧɨ ɜɨɫɩɨɥɶɡɨɜɚɬɶɫɹ
   1. ��������� ������ ���������� ������������ � ����� ���� ��������-
      ���� ��� ������� �������� ������ �����.
   2. ����� �������� �������������� ������������� ��� �������������
      ���������� ��������.
   3. ������� ���������� ����������� ������ ��������� �����������
      ��������� ������������ ���������.
      ���������� ������ ���������� ����������� ����
                               � ( x) � min,                                (2.1)
                                                x��
��� � – ��������� �������� ��������� �� R n .
      ��� ������� ������� ������ ����� ����� ������������ ����� ������
� ������, � ������ �������� ����� ��������� �������� ������:
   1) ���������� ������ ���������� ���������;
   2) ����������� ��������� �����;
   3) ����������� ������� ������ ������ ���������;
   4) ������������ «���������������» �������� ���������;
   5) �������� �� �������.
   ���������� �������� ������ �� ��������� �������.
1.    ���������� ������ ��������� �������������� �� ������ ���������
�������� �� �������� ����� ���������������� �����������. ���� ���-
������ ��������� ���������� ���������� � ������������ �� ���������
���� ������ � ������������ �� ���������������� ������� ��������. ���
������� ������� �� ���������� ����������� ����������� ��������� ��-
��������� ������. ������ ���� �������� ������ ����� ������ ����� ����-
������� ���� x j �{1,0}, j � 1, n (�. �. �������� ������� � �������� ����-
�������), �� ����� ��������������� ������������� �������� ���������:
� � � 1 � � 2 , ��� � 1 � {x � � : xi � 1}; � 2 � {x � � : xi � 0}; i – ���������-
������ ����� ���������� 1 � i � n . ������� ������������ ���������
������������� � ������� ���������. �������, ��� ������� ��������� ���-
������ �� ������������ � ���������� ������ ����� ���� �� ���������-
���.
2.    ������� ������� � (x ) ������ (1) �� ��������� � ���������� �����
����� � � � (�) , ��� � ( x) � � , �x � � . ��� ��������� ������ ������������
��������� ������, ������� ������� ������������ ��� ���������� �������-
�������� ������. � ��������� ������� ������������� ��������� ���-
�������: � ����� �������, �� ������� �� ������ �������� ����� �������.
�� ������ � ��� ������, ���������� � �� �������, ������ ���� ���
����� ������ (�. �. �������� ( � (�) � min � ( x ) ) �� ������ ���� �������
                                            �

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

Страницы