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

UptoLike

Рубрика: 

28
.x,x,x,x
,xx
,xx
,xx
min,xx)a
=t
d
d
d
o
2121
21
21
21
21
0
112
1322
113
32
.x,x,x,x
,xx
,xx
,xx
min,xx)b
=t
d
d
d
o
2121
21
3
1
21
21
21
0
102
11
155
43
.x,x,x,x
,xx
,xx
,xx
min,xx)c
=t
d
d
d
o
2121
21
2
1
21
21
21
0
102
7
102
4
Ɉɬɜɟɬ:
min
x
=(2,4). Ɉɬɜɟɬ:
min
x
=(7,4). Ɉɬɜɟɬ:
min
x
=(2,5).
3.4. ɉɚɪɚɦɟɬɪɢɡɚɰɢɹ ɚɥɝɨɪɢɬɦɚ ɜɟɬɜɟɣ ɢ ɝɪɚɧɢɰ
Ɇɨɞɭɥɶɧɚɹ ɫɯɟɦɚ ɜɟɬɜɟɣ ɢ ɝɪɚɧɢɰ ɞɚɟɬ ɜɨɡɦɨɠɧɨɫɬɶ ɜɵɞɟɥɢɬɶ ɩɚɪɚ-
ɦɟɬɪɵ, ɜɧɟɲɧɟɟ ɭɩɪɚɜɥɟɧɢɟ ɤɨɬɨɪɵɦɢ ɩɨɡɜɨɥɹɟɬ ɮɢɤɫɢɪɨɜɚɬɶ ɬɭ ɢɥɢ ɢɧɭɸ
ɜɟɪɫɢɸ ɚɥɝɨɪɢɬɦɚ. Ʉɚɤ ɜɢɞɧɨ ɢɡ ɩɚɪɚɝɪɚɮɚ 1, ɬɚɤɢɦɢ ɩɚɪɚɦɟɬɪɚɦɢ ɦɨɝɭɬ
ɛɵɬɶ ɫɩɨɫɨɛɵ ɜɟɬɜɥɟɧɢɹ, ɩɪɚɜɢɥɚ ɜɵɱɢɫɥɟɧɢɹ ɨɰɟɧɨɤ, ɫɬɪɚɬɟɝɢɹ ɨɛɯɨɞɚ
ɞɟɪɟɜɚ ɜɚɪɢɚɧɬɨɜ ɢ ɞɪ. ɉɪɚɜɢɥɨ ɜɵɛɨɪɚ ɩɚɪɚɦɟɬɪɨɜ ɦɨɠɟɬ ɨɫɭɳɟɫɬɜɥɹɬɶɫɹ
ɧɚ ɤɚɠɞɨɦ ɲɚɝɟ ɜɟɬɜɥɟɧɢɹ ɫ ɭɱɟɬɨɦ
ɪɟɫɭɪɫɨɜ ɗȼɆ. Ʉɪɨɦɟ ɬɨɝɨ, ɫɯɟɦɚ ɦɟ-
ɬɨɞɚ ɜɟɬɜɟɣ ɢ ɝɪɚɧɢɰ ɩɨɡɜɨɥɹɟɬ ɫɬɪɨɢɬɶ ɩɪɢɛɥɢɠɟɧɧɵɟ ɚɥɝɨɪɢɬɦɵ ɪɟɲɟ-
ɧɢɹ ɡɚɞɚɱ ɞɢɫɤɪɟɬɧɨɣ ɨɩɬɢɦɢɡɚɰɢɢɢ. Ⱦɥɹ ɷɬɨɝɨ ɞɨɫɬɚɬɨɱɧɨ, ɧɚɩɪɢɦɟɪ,
ɜɧɟɫɬɢ ɢɡɦɟɧɟɧɢɹ ɜ ɫɩɨɫɨɛɵ ɨɬɫɟɜɚ ɩɟɪɫɩɟɤɬɢɜɧɵɯ ɦɧɨɠɟɫɬɜ, ɜ ɤɪɢɬɟɪɢɢ
ɨɫɬɚɧɨɜɚ. ɇɚɩɪɢɦɟɪ, ɩɪɚɜɢɥɨ ɨɬɛɪɚɫɵɜɚɧɢɹ ɦɨɠɧɨ ɫɤɨɪɪɟɤɬɢɪɨɜɚɬɶ ɫɥɟ-
ɞɭɸɳɢɦ ɨɛɪɚɡɨɦ (ɩɪɢ ɨɬɵɫɤɚɧɢɢ ɦɚɤɫɢɦɭɦɚ).
eR
k
d
[
,
ɝɞɟ e ɧɚɩɟɪɟɞ ɡɚɞɚɧɧɚɹ ɩɨɝɪɟɲɧɨɫɬɶ.
Ⱦɥɹ ɩɪɨɝɪɚɦɦɧɨɣ ɩɚɪɚɦɟɬɪɢɡɚɰɢɢ ɦɟɬɨɞɚ ɜɜɟɞɟɦ ɫɥɟɞɭɸɳɢɟ ɨɩɪɟɞɟ-
ɥɟɧɢɹ.
ɉɚɪɚɦɟɬɪ N
ɧɚɡɨɜɟɦ ɝɥɭɛɢɧɨɣ ɩɚɦɹɬɢ ɚɥɝɨɪɢɬɦɚ, ɟɫɥɢ ɜ ɬɟɱɟɧɢɟ N
ɲɚɝɨɜ ɚɥɝɨɪɢɬɦ ɪɚɛɨɬɚɟɬ ɜ ɫɨɨɬɜɟɬɫɬɜɢɢ ɫɨ ɫɬɚɧɞɚɪɬɧɨɣ ɫɯɟɦɨɣ (ɛɟɡ ɢɡɦɟ-
ɧɟɧɢɣ, ɫ ɡɚɮɢɤɫɢɪɨɜɚɧɧɵɦɢ ɩɚɪɚɦɟɬɪɚɦɢ).
ɇɚɡɨɜɟɦ ɱɢɫɥɨ
A
ɢɧɞɢɤɚɬɨɪɨɦ ɩɟɪɫɩɟɤɬɢɜɧɨɫɬɢ ɚɥɝɨɪɢɬɦɚ, ɟɫɥɢ
ɨɬɛɪɚɫɵɜɚɧɢɟ ɩɨɞɦɧɨɠɟɫɬɜ ɩɪɨɢɡɜɨɞɢɬɫɹ ɩɨ ɩɪɚɜɢɥɭ:
k
:
ɜɵɛɪɚɫɵɜɚɟɬɫɹ
ɢɡ ɞɚɥɶɧɟɣɲɟɝɨ ɪɚɫɫɦɨɬɪɟɧɢɹ, ɟɫɥɢ

A
k
d
:
[
. Ɉɱɟɜɢɞɧɨ, ɱɬɨ ɦɚɧɢɩɭɥɹ-
ɰɢɹ ɪɚɡɥɢɱɧɵɦɢ ɡɧɚɱɟɧɢɹɦɢ ɷɬɢɯ ɩɚɪɚɦɟɬɪɨɜ ɩɨɡɜɨɥɹɟɬ ɩɨɥɭɱɚɬɶ ɫɨɜɨ-
ɤɭɩɧɨɫɬɶ ɩɪɢɛɥɢɠɟɧɧɵɯ ɚɥɝɨɪɢɬɦɨɜ ɪɚɡɧɨɣ ɬɨɱɧɨɫɬɢ. Ⱦɟɣɫɬɜɢɬɟɥɶɧɨ,
«ɛɨɥɶɲɢɟ ɡɧɚɱɟɧɢɹ»
N
ɢ
R
A
, ɝɞɟ
R
ɜɟɥɢɱɢɧɚ ɪɟɤɨɪɞɚ, ɩɪɢɜɨɞɹɬ ɤ
ɬɨɱɧɨɦɭ ɚɥɝɨɪɢɬɦɭ ɪɟɲɟɧɢɹ, ɡɧɚɱɟɧɢɹ 1
N
ɢ
eA
k
k
[
max
, ɝɞɟ 0!e
ɦɚɥɨɟ ɱɢɫɥɨ, ɩɨɪɨɠɞɚɸɬ ɩɪɢɛɥɢɠɟɧɧɵɣ ɚɥɝɨɪɢɬɦ ɩɪɨɯɨɞɚ ɩɨ ɞɟɪɟɜɭ ɜɚɪɢ-
ɚɧɬɨɜ, ɩɨ ɦɧɨɠɟɫɬɜɚɦ ɫ ɦɚɤɫɢɦɚɥɶɧɨɣ ɨɰɟɧɤɨɣ ɞɨ ɩɟɪɜɨɝɨ ɩɨɥɭɱɟɧɢɹ ɞɨ-
ɩɭɫɬɢɦɨɣ ɬɨɱɤɢ. ȿɫɥɢ ɚɥɝɨɪɢɬɦ ɩɪɟɞɭɫɦɚɬɪɢɜɚɟɬ ɜɨɡɦɨɠɧɨɫɬɶ ɢɡɦɟɧɟɧɢɹ
ɩɚɪɚɦɟɬɪɨɜ ɜ ɩɪɨɰɟɫɫɟ ɪɟɲɟɧɢɹ, ɬɨ ɜɨɡɦɨɠɧɨ ɜɧɟɲɧɟɟ ɭɩɪɚɜɥɟɧɢɟ ɬɨɱɧɨ-
ɫɬɶɸ ɚɥɝɨɪɢɬɦɚ. ȼɨɡɦɨɠɧɨɫɬɶ ɭɩɪɚɜɥɟɧɢɹ ɫɬɪɚɬɟɝɢɟɣ ɢ ɬɨɱɧɨɫɬɶɸ ɚɥɝɨ-
ɪɢɬɦɚ ɩɨɡɜɨɥɹɟɬ ɩɨɥɭɱɚɬɶ ɦɧɨɠɟɫɬɜɨ ɪɚɡɧɨɨɛɪɚɡɧɵɯ
ɩɪɢɛɥɢɠɟɧɧɵɯ ɚɥɝɨ-
    a ) � 2 x1 � 3 x2 � min,       b ) � 3x1 � 4 x2 � min,       c ) � x1 � 4 x2 � min,
      � x1 � 3x2 � 11,               � x1 � 5 x2 � 15,              � x1 � 2 x2 � 10 ,
      2 x1 � 2 x2 � 13,              x1 � x2 � 11 ,   1
                                                      3             x1 � x2 � 7 12 ,
      2 x1 � x2 � 11,                2 x1 � x2 � 10,                2 x1 � x2 � 10 ,
       x1 , x2 � 0, x1 , x2 � �.     x1 , x2 � 0, x1 , x2 � �.      x1 , x2 � 0 , x1 , x2 � �.
           min                                min
�����: x         =(2,4).           �����: x         =(7,4).      �����: x min =(2,5).

                 3.4. �������������� ��������� ������ � ������

     ��������� ����� ������ � ������ ���� ����������� �������� ����-
�����, ������� ���������� �������� ��������� ����������� �� ��� ����
������ ���������. ��� ����� �� ��������� 1, ������ ����������� �����
���� ������� ���������, ������� ���������� ������, ��������� ������
������ ��������� � ��. ������� ������ ���������� ����� ��������������
�� ������ ���� ��������� � ������ �������� ���. ����� ����, ����� ��-
���� ������ � ������ ��������� ������� ������������ ��������� ����-
��� ����� ���������� ������������. ��� ����� ����������, ��������,
������ ��������� � ������� ������ ������������� ��������, � ��������
��������. ��������, ������� ������������ ����� ��������������� ���-
������ ������� (��� ��������� ���������).
                               �k � R � e ,
��� e – ������� �������� �����������.
     ��� ����������� �������������� ������ ������ ��������� ������-
�����.
     �������� N ������� �������� ������ ���������, ���� � ������� N
����� �������� �������� � ������������ �� ����������� ������ (��� ����-
�����, � ���������������� �����������).
     ������� ����� A ����������� ��������������� ���������, ����
������������ ����������� ������������ �� �������: � k �������������
�� ����������� ������������, ���� � �� k � � A . ��������, ��� ��������-
��� ���������� ���������� ���� ���������� ��������� �������� ����-
�������� ������������ ���������� ������ ��������. �������������,
«������� ��������» N � A � R , ��� R – �������� �������, �������� �
������� ��������� �������, �������� N � 1 � A � max � k � e , ��� e � 0 –
                                                                    k
����� �����, ��������� ������������ �������� ������� �� ������ ����-
�����, �� ���������� � ������������ ������� �� ������� ��������� ��-
�������� �����. ���� �������� ��������������� ����������� ���������
���������� � �������� �������, �� �������� ������� ���������� �����-
���� ���������. ����������� ���������� ���������� � ��������� ����-
����� ��������� �������� ��������� ������������� ������������ ����-
                                             28