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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

25
3.3. Ɇɟɬɨɞ ɜɟɬɜɟɣ ɢ ɝɪɚɧɢɰ ɞɥɹ ɥɢɧɟɣɧɵɯ ɡɚɞɚɱ
ɰɟɥɨɱɢɫɥɟɧɧɨɝɨ ɩɪɨɝɪɚɦɦɢɪɨɜɚɧɢɹ
Ɋɚɫɫɦɨɬɪɢɦ ɰɟɥɨɱɢɫɥɟɧɧɭɸ ɡɚɞɚɱɭ ɥɢɧɟɣɧɨɝɨ ɩɪɨɝɪɚɦɦɢɪɨɜɚɧɢɹ
(ɐɁɅɉ):
,minxc)x(
n
j
jj
¦
o
1
M
°
¯
°
®
=dd
d
:
¦
.,1,,0
,,1,
1
0
njxdx
mibxa
jjj
n
j
ijij
ɉɪɨɰɟɫɫ ɩɨɥɭɱɟɧɢɹ ɪɟɲɟɧɢɹ ɡɚɞɚɱɢ ɧɚɱɢɧɚɟɬɫɹ ɫ ɪɟɲɟɧɢɹ ɫɨɨɬɜɟɬ-
ɫɬɜɭɸɳɟɣ ɟɣ ɨɰɟɧɨɱɧɨɣ ɡɚɞɚɱɢ ɥɢɧɟɣɧɨɝɨ ɩɪɨɝɪɚɦɦɢɪɨɜɚɧɢɹ ɫ ɨɬɛɪɨɲɟɧ-
ɧɵɦ ɭɫɥɨɜɢɟɦ ɰɟɥɨɱɢɫɥɟɧɧɨɫɬɢ. ȿɫɥɢ ɩɨɥɭɱɟɧɧɚɹ ɩɪɢ ɷɬɨɦ ɨɩɬɢɦɚɥɶɧɚɹ
ɬɨɱɤɚ
0
x
ɢɦɟɟɬ ɬɨɥɶɤɨ ɰɟɥɵɟ ɤɨɨɪɞɢɧɚɬɵ, ɬɨ ɨɧɚ ɹɜɥɹɟɬɫɹ ɪɟɲɟɧɢɟɦ ɢɫ-
ɯɨɞɧɨɣ ɡɚɞɚɱɢ. ȼ ɩɪɨɬɢɜɧɨɦ ɫɥɭɱɚɟ ɡɧɚɱɟɧɢɟ
)(
0
x
M
ɞɚɟɬ ɧɢɠɧɸɸ ɨɰɟɧɤɭ
ɰɟɥɟɜɨɣ ɮɭɧɤɰɢɢ.
Ʉɨɧɤɪɟɬɢɡɢɪɭɟɦ ɨɫɧɨɜɧɵɟ ɷɬɚɩɵ ɦɟɬɨɞɚ ɜɟɬɜɟɣ ɢ ɝɪɚɧɢɰ ɩɪɢɦɟɧɢ-
ɬɟɥɶɧɨ ɤ ɞɚɧɧɨɣ ɡɚɞɚɱɟ.
1.
ȼɟɬɜɥɟɧɢɟ. ɉɭɫɬɶ
),...,(
1
k
n
kk
xxx
– ɨɩɬɢɦɚɥɶɧɚɹ ɬɨɱɤɚ, ɩɨɥɭɱɟɧɧɚɹ
ɩɪɢ ɪɟɲɟɧɢɢ ɨɰɟɧɨɱɧɨɣ ɡɚɞɚɱɢ ɧɚ ɦɧɨɠɟɫɬɜɟ
k
:
. ȿɫɥɢ
k
x
ɭɞɨɜɥɟɬɜɨɪɹɟɬ
ɬɪɟɛɨɜɚɧɢɹɦ ɰɟɥɨɱɢɫɥɟɧɧɨɫɬɢ, ɬɨ ɦɧɨɠɟɫɬɜɨ
k
:
ɢɫɤɥɸɱɚɟɬɫɹ ɢɡ ɞɚɥɶ-
ɧɟɣɲɟɝɨ ɪɚɫɫɦɨɬɪɟɧɢɹ (ɧɚɣɞɟɧɨ ɨɩɬɢɦɚɥɶɧɨɟ ɪɟɲɟɧɢɟ ɧɚ ɧɟɦ). Ɂɧɚɱɟɧɢɟ
)(
k
x
M
ɫɪɚɜɧɢɜɚɟɬɫɹ ɫ ɪɟɤɨɪɞɧɵɦ (ɩɪɢ ɷɬɨɦ ɜɨɡɦɨɠɧɨ ɫɦɟɧɚ ɪɟɤɨɪɞɚ). ȿɫɥɢ
ɠɟ ɟɫɬɶ ɧɟ ɰɟɥɚɹ ɤɨɦɩɨɧɟɧɬɚ
k
j
x , ɬɨ ɦɧɨɠɟɫɬɜɨ
k
:
ɪɚɡɛɢɜɚɟɬɫɹ ɧɚ ɞɜɚ
ɩɨɞɦɧɨɠɟɫɬɜɚ ɫɥɟɞɭɸɳɢɦ ɨɛɪɚɡɨɦ:
21
kkk
:: : ,
]}[,{
1
k
jjkk
xxx d: : , }1][,{
2
t: :
k
jjkk
xxx , ɝɞɟ ɫɢɦɜɨɥɨɦ
][
ɨɛɨ-
ɡɧɚɱɟɧɚ ɰɟɥɚɹ ɱɚɫɬɶ ɱɢɫɥɚ.
2.
ȼɵɱɢɫɥɟɧɢɟ ɨɰɟɧɨɤ. Ɉɰɟɧɨɱɧɨɣ ɡɚɞɚɱɟɣ ɧɚ ɦɧɨɠɟɫɬɜɟ
k
:
ɛɭɞɟɬ ɹɜ-
ɥɹɬɶɫɹ ɡɚɞɚɱɚ, ɜ ɤɨɬɨɪɨɣ ɨɬɛɪɨɲɟɧɨ ɬɪɟɛɨɜɚɧɢɟ ɰɟɥɨɱɢɫɥɟɧɧɨɫɬɢ ɩɟɪɟ-
ɦɟɧɧɵɯ. ɉɪɢ ɪɟɲɟɧɢɢ ɨɰɟɧɨɱɧɨɣ ɡɚɞɚɱɢ ɩɨɥɭɱɚɟɦ ɨɩɬɢɦɚɥɶɧɭɸ ɬɨɱɤɭ
k
x
.
Ɂɧɚɱɟɧɢɟ
)(
k
x
M
ɞɚɟɬ ɧɢɠɧɸɸ ɨɰɟɧɤɭ ɦɧɨɠɟɫɬɜɚ
k
:
(ɦɨɠɧɨ ɜ ɤɚɱɟɫɬɜɟ
ɨɰɟɧɤɢ ɛɪɚɬɶ ɰɟɥɭɸ ɱɚɫɬɶ
)(
k
x
M
).
ɉɪɚɜɢɥɨ ɨɛɯɨɞɚ ɞɟɪɟɜɚ ɜɚɪɢɚɧɬɨɜ, ɜɵɛɨɪ ɩɟɪɫɩɟɤɬɢɜɧɨɝɨ ɦɧɨɠɟɫɬɜɚ
ɩɪɢ ɜɟɬɜɥɟɧɢɢ ɢ ɩɪɨɜɟɪɤɚ ɤɪɢɬɟɪɢɹ ɨɩɬɢɦɚɥɶɧɨɫɬɢ ɨɫɭɳɟɫɬɜɥɹɸɬɫɹ ɜ ɫɨ-
ɨɬɜɟɬɫɬɜɢɢ ɫɨ ɫɬɚɧɞɚɪɬɧɨɣ ɫɯɟɦɨɣ ɦɟɬɨɞɚ ɜɟɬɜɟɣ ɢ ɝɪɚɧɢɰ.
                3.3. ����� ������ � ������ ��� �������� �����
                      �������������� ����������������

    ���������� ������������� ������ ��������� ����������������
(����):
                                             n
                                   � ( x ) � � c j x j � min ,
                                            j �1

                                 �n
                                 �� aij x j �b i , i � 1, m,
                             � 0 � j �1
                                 �0 � x � d , x � �, j � 1, n.
                                 �      j     j      j

     ������� ��������� ������� ������ ���������� � ������� �������-
�������� �� ��������� ������ ��������� ���������������� � ��������-
��� �������� ���������������. ���� ���������� ��� ���� �����������
����� x 0 ����� ������ ����� ����������, �� ��� �������� �������� ��-
������ ������. � ��������� ������ �������� � ( x 0 ) ���� ������ ������
������� �������.
     �������������� �������� ����� ������ ������ � ������ �������-
������ � ������ ������.
1.   ���������. ����� x k � ( x1k ,..., xnk ) – ����������� �����, ����������
��� ������� ��������� ������ �� ��������� � k . ���� x k �������������
����������� ���������������, �� ��������� � k ����������� �� ����-
������� ������������ (������� ����������� ������� �� ���). ��������
� ( x k ) ������������ � ��������� (��� ���� �������� ����� �������). ����
�� ���� �� ����� ���������� x kj , �� ��������� � k ����������� �� ���
������������        ���������           �������:        � k � � k1 � � k2 ,
� k1 � {x � � k , x j � [ x kj ]} , � k2 � {x � � k , x j � [ x kj ] � 1} , ��� �������� [�] ���-
������� ����� ����� �����.
2.     ���������� ������. ��������� ������� �� ��������� � k ����� ��-
������ ������, � ������� ��������� ���������� ��������������� ����-
������. ��� ������� ��������� ������ �������� ����������� ����� x k .
�������� � ( x k ) ���� ������ ������ ��������� � k (����� � ��������
������ ����� ����� ����� � ( x k ) ).
      ������� ������ ������ ���������, ����� �������������� ���������
��� ��������� � �������� �������� ������������� �������������� � ��-
���������� �� ����������� ������ ������ ������ � ������.


                                                   25

Страницы