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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

31
ȼ ɩɪɨɬɢɜɧɨɦ ɫɥɭɱɚɟ ɫɬɪɨɹɬɫɹ ɨɬɫɟɤɚɸɳɢɟ ɩɥɨɫɤɨɫɬɢ (ɜɜɨɞɹɬɫɹ ɞɨɩɨɥ-
ɧɢɬɟɥɶɧɵɟ ɥɢɧɟɣɧɵɟ ɨɝɪɚɧɢɱɟɧɢɹ), ɭɞɨɜɥɟɬɜɨɪɹɸɳɢɟ ɫɥɟɞɭɸɳɢɦ ɬɪɟɛɨ-
ɜɚɧɢɹɦ:
– ɜɫɟ ɞɨɩɭɫɬɢɦɵɟ ɬɨɱɤɢ ɢɫɯɨɞɧɨɣ ɡɚɞɚɱɢ ɭɞɨɜɥɟɬɜɨɪɹɸɬ ɧɨɜɵɦ ɨɝɪɚɧɢ-
ɱɟɧɢɹɦ;
– ɩɨɥɭɱɟɧɧɨɟ ɬɨɥɶɤɨ ɱɬɨ ɪɟɲɟɧɢɢ ɡɚɞɚɱɢ ɥɢɧɟɣɧɨɝɨ ɩɪɨɝɪɚɦɦɢɪɨɜɚɧɢɹ
ɧɟ ɭɞɨɜɥɟɬɜɨɪɹɟɬ ɷɬɢɦ ɨɝɪɚɧɢɱɟɧɢɹɦ (ɨɬɫɟɤɚɟɬɫɹ).
ɋɭɳɟɫɬɜɭɸɬ ɪɚɡɥɢɱɧɵɟ ɜɟɪɫɢɢ ɬɚɤɨɝɨ ɪɨɞɚ ɚɥɝɨɪɢɬɦɨɜ, ɜ ɤɨɬɨɪɵɯ
ɩɪɟɞɥɚɝɚɸɬɫɹ ɪɚɡɧɵɟ ɩɨɫɬɪɨɟɧɢɹ ɨɬɫɟɤɚɸɳɢɯ ɩɥɨɫɤɨɫɬɟɣ.
4.1. ɉɟɪɜɵɣ ɚɥɝɨɪɢɬɦ Ƚɨɦɨɪɢ
Ɋɚɫɫɦɨɬɪɢɦ ɰɟɥɨɱɢɫɥɟɧɧɭɸ ɡɚɞɚɱɭ ɥɢɧɟɣɧɨɝɨ ɩɪɨɝɪɚɦɦɢɪɨɜɚɧɢɹ ɜ
ɫɥɟɞɭɸɳɟɣ ɮɨɪɦɟ:
,min)(
1
¦
o
n
j
jj
xcx
M
(4.1)
¦
d
n
j
ijij
mibxa
1
,,1, (4.2)
,0t
j
x (4.3)
.,1, njx
j
=
(4.4)
ɂɞɟɹ ɦɟɬɨɞɨɜ ɨɬɫɟɱɟɧɢɣ ɫɨɫɬɨɢɬ ɜ ɫɥɟɞɭɸɳɟɦ. ɉɪɨɰɟɫɫ ɩɨɥɭɱɟɧɢɹ
ɪɟɲɟɧɢɹ ɡɚɞɚɱɢ ɧɚɱɢɧɚɟɬɫɹ ɫ ɪɟɲɟɧɢɹ ɫɨɨɬɜɟɬɫɬɜɭɸɳɟɣ ɟɣ ɨɰɟɧɨɱɧɨɣ ɡɚ-
ɞɚɱɢ ɥɢɧɟɣɧɨɝɨ ɩɪɨɝɪɚɦɦɢɪɨɜɚɧɢɹ (4.1) — (4.3) ɫ ɨɬɛɪɨɲɟɧɧɵɦ ɭɫɥɨɜɢɟɦ
ɰɟɥɨɱɢɫɥɟɧɧɨɫɬɢ. ȿɫɥɢ ɩɨɥɭɱɟɧɧɚɹ ɩɪɢ ɷɬɨɦ ɨɩɬɢɦɚɥɶɧɚɹ ɬɨɱɤɚ
0
x
ɢɦɟɟɬ
ɬɨɥɶɤɨ ɰɟɥɵɟ ɤɨɨɪɞɢɧɚɬɵ, ɬɨ ɨɧɚ ɹɜɥɹɟɬɫɹ ɪɟɲɟɧɢɟɦ ɡɚɞɚɱɢ (4.1) — (4.4).
ȿɫɥɢ ɩɨɥɭɱɟɧɧɨɟ ɪɟɲɟɧɢɟ ɧɟɰɟɥɨɱɢɫɥɟɧɧɨɟ, ɬɨ ɜɜɨɞɢɬɫɹ ɞɨɩɨɥɧɢɬɟɥɶɧɨɟ
ɨɝɪɚɧɢɱɟɧɢɟ, ɤɨɬɨɪɨɟ ɨɬɫɟɤɚɟɬ ɱɚɫɬɶ ɨɛɥɚɫɬɢ ɞɨɩɭɫɬɢɦɵɯ ɪɟɲɟɧɢɣ ɡɚɞɚɱɢ
(4.1) — (4.3) ɜɦɟɫɬɟ ɫ ɧɚɣɞɟɧɧɵɦ ɧɟɰɟɥɨɱɢɫɥɟɧɧɵɦ ɪɟɲɟɧɢɟɦ, ɫɨɯɪɚɧɹɹ
ɩɪɢ ɷɬɨɦ ɜɫɟ ɰɟɥɨɱɢɫɥɟɧɧɵɟ ɬɨɱɤɢ. Ɂɚɬɟɦ ɪɚɫɫɦɚɬɪɢɜɚɟɬɫɹ ɪɟɲɟɧɢɟ ɢɫ-
ɯɨɞɧɨɣ ɡɚɞɚɱɢ (4.1) — (4.3) ɫ ɭɱɟɬɨɦ ɧɨɜɨɝɨ ɨɝɪɚɧɢɱɟɧɢɹ. ȿɫɥɢ ɨɧɨ ɧɟɰɟ-
ɥɨɱɢɫɥɟɧɧɨɟ, ɬɨ
ɜɜɨɞɢɬɫɹ ɧɨɜɨɟ ɨɝɪɚɧɢɱɟɧɢɟ, ɢ ɬɚɤ ɞɨ ɬɟɯ ɩɨɪ, ɩɨɤɚ ɧɟ ɛɭ-
ɞɟɬ ɧɚɣɞɟɧɨ ɰɟɥɨɱɢɫɥɟɧɧɨɟ ɨɩɬɢɦɚɥɶɧɨɟ ɪɟɲɟɧɢɟ. ɉɪɚɜɢɥɚ ɮɨɪɦɢɪɨɜɚɧɢɹ
ɨɬɫɟɤɚɸɳɢɯ ɨɝɪɚɧɢɱɟɧɢɣ ɛɵɥɢ ɪɚɡɪɚɛɨɬɚɧɵ ɚɦɟɪɢɤɚɧɫɤɢɦ ɭɱɟɧɵɦ Ɋ. Ƚɨ-
ɦɨɪɢ. ɂɞɟɹ ɦɟɬɨɞɚ, ɧɚɡɜɚɧɧɨɝɨ ɩɟɪɜɵɦ ɚɥɝɨɪɢɬɦɨɦ Ƚɨɦɨɪɢ, ɡɚɤɥɸɱɚɟɬɫɹ ɜ
ɫɥɟɞɭɸɳɟɦ.
ɉɭɫɬɶ ɜ ɪɟɡɭɥɶɬɚɬɟ ɪɟɲɟɧɢɹ ɡɚɞɚɱɢ (4.1) — (4.3) ɫɢɦɩɥɟɤɫ-ɦɟɬɨɞɨɦ
ɩɨɥɭɱɟɧɚ ɧɟɰɟɥɨɱɢɫɥɟɧɧɚɹ ɨɩɬɢɦɚɥɶɧɚɹ ɬɨɱɤɚ. Ɂɚɤɥɸɱɢɬɟɥɶɧɚɹ ɫɢɦɩɥɟɤɫ-
ɬɚɛɥɢɰɚ
ɫɨɞɟɪɠɢɬ ɭɪɚɜɧɟɧɢɹ ɜɢɞɚ:
¦
Jj
jijii
xaxb ,
(4.5) 
    � ��������� ������ �������� ���������� ��������� (�������� �����-
��������� �������� �����������), ��������������� ��������� �����-
������:
 – ��� ���������� ����� �������� ������ ������������� ����� ������-
 ������;
 – ���������� ������ ��� ������� ������ ��������� ����������������
 �� ������������� ���� ������������ (����������).
    ���������� ��������� ������ ������ ���� ����������, � �������
������������ ������ ���������� ���������� ����������.

                     4.1. ������ �������� ������

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

                          �a
                          j �1
                                 ij   x j �b i , i � 1, m,          (4.2)

                          x j � 0,                                  (4.3)
                          x j � �, j � 1, n.                        (4.4)

     ���� ������� ��������� ������� � ���������. ������� ���������
������� ������ ���������� � ������� ��������������� �� ��������� ��-
���� ��������� ���������������� (4.1) — (4.3) � ����������� ��������
���������������. ���� ���������� ��� ���� ����������� ����� x 0 �����
������ ����� ����������, �� ��� �������� �������� ������ (4.1) — (4.4).
���� ���������� ������� ���������������, �� �������� ��������������
�����������, ������� �������� ����� ������� ���������� ������� ������
(4.1) — (4.3) ������ � ��������� ��������������� ��������, ��������
��� ���� ��� ������������� �����. ����� ��������������� ������� ��-
������ ������ (4.1) — (4.3) � ������ ������ �����������. ���� ��� ����-
�����������, �� �������� ����� �����������, � ��� �� ��� ���, ���� �� ��-
��� ������� ������������� ����������� �������. ������� ������������
���������� ����������� ���� ����������� ������������ ������ �. ��-
����. ���� ������, ���������� ������ ���������� ������, ����������� �
���������.
     ����� � ���������� ������� ������ (4.1) — (4.3) ��������-�������
�������� ��������������� ����������� �����. �������������� ��������-
������� �������� ��������� ����:
                               bi � xi � � aij x j ,                (4.5)
                                                     j� J



                                                31

Страницы