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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

33
ɒɚɝ 5. ɋ ɭɱɟɬɨɦ ɞɨɛɚɜɥɟɧɧɨɝɨ ɨɝɪɚɧɢɱɟɧɢɹ ɨɬɵɫɤɚɬɶ ɧɨɜɨɟ ɪɟɲɟɧɢɟ
1k
x
.
ɉɨɥɨɠɢɬɶ k = k+1. ɉɟɪɟɣɬɢ ɧɚ ɲɚɝ 2.
Ɂɚɦɟɱɚɧɢɟ. ɂɫɩɨɥɶɡɨɜɚɧɢɟ ɨɛɵɱɧɨɝɨ ɫɢɦɩɥɟɤɫ-ɦɟɬɨɞɚ ɩɪɢ ɪɟɲɟɧɢɢ
ɞɚɧɧɨɣ ɡɚɞɚɱɢ ɧɟɭɞɨɛɧɨ, ɬɚɤ ɤɚɤ ɞɨɛɚɜɥɟɧɢɟ ɧɨɜɨɝɨ ɨɝɪɚɧɢɱɟɧɢɹ ɤɚɠɞɵɣ
ɪɚɡ ɛɭɞɟɬ ɩɪɢɜɨɞɢɬɶ ɤ ɧɟɨɛɯɨɞɢɦɨɫɬɢ ɜɵɡɨɜɚ ɦɟɬɨɞɚ ɢɫɤɭɫɫɬɜɟɧɧɨɝɨ ɛɚɡɢ-
ɫɚ. Ȼɨɥɟɟ ɩɪɟɞɩɨɱɬɢɬɟɥɶɧɵɦ ɜ ɞɚɧɧɨɣ ɫɢɬɭɚɰɢɢ ɹɜɥɹɟɬɫɹ ɞɜɨɣɫɬɜɟɧɧɵɣ
ɫɢɦɩɥɟɤɫ-ɚɥɝɨɪɢɬɦ. ȼ ɬɚɤɨɦ ɫɥɭɱɚɟ ɧɨɜɨɟ ɨɝɪɚɧɢɱɟɧɢɟ ɜɜɨɞɢɬɫɹ ɜ ɫɢɫɬɟɦɭ
ɜ ɜɢɞɟ:
ij j n m k i
jJ
{a }x x {b },


¦
ɢ ɩɟɪɟɦɟɧɧɚɹ
kmn
x
ɫɬɚɧɨɜɢɬɫɹ ɛɚɡɢɫɧɨɣ. ɋɨɝɥɚɫɧɨ ɞɜɨɣɫɬɜɟɧɧɨɦɭ ɫɢɦ-
ɩɥɟɤɫ-ɦɟɬɨɞɭ ɢɫɤɥɸɱɟɧɢɸ ɢɡ ɛɚɡɢɫɚ ɩɨɞɥɟɠɢɬ ɬɚ ɩɟɪɟɦɟɧɧɚɹ
l
x
, ɡɧɚɱɟɧɢɟ
ɤɨɬɨɪɨɣ ɨɬɪɢɰɚɬɟɥɶɧɨ. (ȿɫɥɢ ɜɫɟ ɛɚɡɢɫɧɵɟ ɩɟɪɟɦɟɧɧɵɟ ɧɟɨɬɪɢɰɚɬɟɥɶɧɵ, ɬɨ
ɢɦɟɸɳɟɟɫɹ ɪɟɲɟɧɢɟ ɨɩɬɢɦɚɥɶɧɨ). Ⱦɥɹ ɜɜɨɞɚ ɜ ɛɚɡɢɫ ɜɵɛɢɪɚɟɬɫɹ ɬɚ ɢɡ ɧɟ-
ɛɚɡɢɫɧɵɯ ɩɟɪɟɦɟɧɧɵɯ
k
x
, ɞɥɹ ɤɨɬɨɪɨɣ
0
lk
a
ɢ ɨɬɧɨɲɟɧɢɟ
||
lk
k
a
'
ɦɢɧɢ-
ɦɚɥɶɧɨ.
ɉɪɢɦɟɪ. Ɋɟɲɢɬɶ ɡɚɞɚɱɭ ɰɟɥɨɱɢɫɥɟɧɧɨɝɨ ɥɢɧɟɣɧɨɝɨ ɩɪɨɝɪɚɦɦɢɪɨɜɚɧɢɹ.
max,x4x)x(
21
o
M
,2/15xx
,10x2x
21
21
d
d
.x,x,0x,x
,10xx2
2121
21
=t
d
Ɋɟɲɟɧɢɟ. ɉɪɢɜɟɞɟɦ ɡɚɞɚɱɭ ɤ ɤɚɧɨɧɢɱɟɫɤɨɦɭ ɜɢɞɭ (ɩɪɟɞɜɚɪɢɬɟɥɶɧɨ ɭɦɧɨ-
ɠɢɜ ɜɬɨɪɨɟ ɨɝɪɚɧɢɱɟɧɢɟ ɧɚ 2).
max,x4x
21
o
,15xx2x2
,10xx2x
421
321
.5,1j,x,0x
,10xxx2
jj
521
=t
��� 5. � ������ ������������ ����������� �������� ����� ������� x k �1 .
�������� k = k+1. ������� �� ��� 2.

     ���������. ������������� �������� ��������-������ ��� �������
������ ������ ��������, ��� ��� ���������� ������ ����������� ������
��� ����� ��������� � ������������� ������ ������ �������������� ����-
��. ����� ���������������� � ������ �������� �������� ������������
��������-��������. � ����� ������ ����� ����������� �������� � �������
� ����:
                       �� { aij }x j � xn� m � k � �{ bi } ,
                         j�J

� ���������� xn� m� k ���������� ��������. �������� ������������� ���-
�����-������ ���������� �� ������ �������� �� ���������� xl , ��������
������� ������������. (���� ��� �������� ���������� ��������������, ��
��������� ������� ����������). ��� ����� � ����� ���������� �� �� ��-
                                                              �k
�������� ���������� xk , ��� ������� alk � 0 � ���������            ����-
                                                            | alk |
������.
������. ������ ������ �������������� ��������� ����������������.
                              � ( x ) � x1 � 4 x2 � max,
                              � x1 � 2 x2 � 10 ,
                               x1 � x2 � 15 / 2 ,
                               2 x1 � x2 � 10 ,
                              x1 , x2 � 0 , x1 , x2 � �.
�������. �������� ������ � ������������� ���� (�������������� ����-
��� ������ ����������� �� 2).
                              x1 � 4 x2 � max,
                              � x1 � 2 x2 � x3 � 10 ,
                               2 x1 � 2 x2 � x4 � 15 ,
                               2 x1 � x2 � x5 � 10 ,
                               x j � 0 , x j � � , j � 1,5.




                                     33

Страницы