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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

5
¦
t
n
j
jij
xa
1
1
, (1.19)
¦
o
n
j
j
x
1
min
. (1.20)
Ɇɚɬɪɢɰɚ A, ɫɨɫɬɨɹɳɚɹ ɢɡ ɧɭɥɟɣ ɢ ɟɞɢɧɢɰ, ɧɨɫɢɬ ɧɚɡɜɚɧɢɟ ɦɚɬɪɢɰɵ
ɩɨɤɪɵɬɢɣ. Ɏɨɪɦɚɥɶɧɨ ɡɚɞɚɱɚ ɫɨɫɬɨɢɬ ɜ ɜɵɛɨɪɟ ɦɢɧɢɦɚɥɶɧɨɝɨ ɤɨɥɢɱɟɫɬɜɚ
ɫɬɨɥɛɰɨɜ, ɨɛɴɟɞɢɧɟɧɢɟ ɤɨɬɨɪɵɯ ɩɨɤɪɵɜɚɟɬ ɜɫɟ ɫɬɪɨɤɢ ɦɚɬɪɢɰɵ (ɜ ɤɚɠɞɨɣ
ɫɬɪɨɤɟ ɢɦɟɟɬɫɹ ɩɨ ɤɪɚɣɧɟɣ ɦɟɪɟ ɨɞɧɚ ɟɞɢɧɢɰɚ).
Ɍɚɤɚɹ ɡɚɞɚɱɚ ɜɨɡɧɢɤɚɟɬ, ɧɚɩɪɢɦɟɪ, ɩɪɢ ɬɟɫɬɢɪɨɜɚɧɢɢ, ɞɢɚɝɧɨɫɬɢɤɟ.
III. Ɂɚɞɚɱɢ ɫ ɪɚɡɪɵɜɧɨɣ ɰɟɥɟɜɨɣ ɮɭɧɤɰɢɟɣ (
ɬɪɚɧɫɩɨɪɬɧɚɹ ɡɚɞɚɱɚ ɫ ɮɢɤɫɢ-
ɪɨɜɚɧɧɵɦɢ ɞɨɩɥɚɬɚɦɢ
).
0t
ij
x , (1.21)
miax
n
j
iij
,...,2,1,
1
¦
, (1.22)
njbx
m
i
jij
,...,2,1,
1
¦
, (1.23)

¦¦
o
m
i
n
j
ijij
xc
11
min
, (1.24)

°
¯
°
®
!
.0,
,0,0
ijijijij
ij
ijij
xdxc
x
xc
(1.25)
Ⱦɚɧɧɚɹ ɡɚɞɚɱɚ ɨɬɥɢɱɚɟɬɫɹ ɨɬ ɫɬɚɧɞɚɪɬɧɨɣ ɬɪɚɧɫɩɨɪɬɧɨɣ ɩɪɟɞɩɨɥɨɠɟ-
ɧɢɟɦ ɨ ɬɨɦ, ɱɬɨ ɢɡɞɟɪɠɤɢ ɧɚ ɩɟɪɟɜɨɡɤɭ ɫɜɹɡɚɧɵ ɧɟ ɬɨɥɶɤɨ ɫ ɤɨɥɢɱɟɫɬɜɨɦ
ɩɟɪɟɜɨɡɢɦɨɝɨ ɬɨɜɚɪɚ, ɧɨ ɬɚɤɠɟ ɫ ɞɨɩɨɥɧɢɬɟɥɶɧɵɦɢ ɞɨɩɥɚɬɚɦɢ, ɜɨɡɧɢɤɚɸ-
ɳɢɦɢ ɜ ɫɥɭɱɚɟ, ɟɫɥɢ ɩɟɪɟɜɨɡɤɚ ɢɦɟɟɬ ɦɟɫɬɨ ɩɨ ɩɥɚɧɭ.
ɂɡɧɚɱɚɥɶɧɨ ɜ ɡɚɞɚɱɟ ɨɬɫɭɬɫɬɜɭɟɬ ɭɫɥɨɜɢɟ ɰɟɥɨɱɢɫɥɟɧɧɨɫɬɢ ɩɟɪɟɦɟɧ-
ɧɵɯ. Ɉɞɧɚɤɨ ɩɭɬɟɦ ɜɜɟɞɟɧɢɹ ɧɨɜɵɯ ɩɟɪɟɦɟɧɧɵɯ (ɛɭɥɟɜɵɯ
) ɨɧɚ ɦɨɠɟɬ ɛɵɬɶ
ɩɟɪɟɩɢɫɚɧɚ ɤɚɤ ɡɚɞɚɱɚ ɞɢɫɤɪɟɬɧɨɝɨ ɩɪɨɝɪɚɦɦɢɪɨɜɚɧɢɹ.

min,
11
o
¦¦
mɶ
i
n
j
ijijijij
ydxc (1.26)
miax
n
j
iij
,...,2,1,
1
¦
, (1.27)
,,...,2,1,
1
njbx
m
i
jij
¦
(1.28)
,
ijijij
yMx d (1.29)
ɝɞɟ
^
`
^`
jiyxbaM
ijijjiij
,1,0,0,,min t . (1.30) 
                                          n
                                         � aij x j � 1 ,                                   (1.19)
                                         j �1
                                          n
                                         � x j � min .                                     (1.20)
                                         j �1
    ������� A, ��������� �� ����� � ������, ����� �������� �������
��������. ��������� ������ ������� � ������ ������������ ����������
��������, ����������� ������� ��������� ��� ������ ������� (� ������
������ ������� �� ������� ���� ���� �������).
    ����� ������ ���������, ��������, ��� ������������, �����������.

III. ������ � ��������� ������� �������� (������������ ������ � �����-
��������� ���������).
                              xij � 0 ,                          (1.21)
                                          n
                                         � xij � ai ,      i � 1,2,..., m ,                (1.22)
                                         j �1
                                         m
                                         � xij � b j ,       j � 1,2,..., n ,              (1.23)
                                         i �1
                                          m n
                                         �� cij �xij � � min ,                             (1.24)
                                         i �1 j �1

                                                      ��0, xij � 0,
                                         cij �xij � � �                                    (1.25)
                                                       ��cij xij � d ij , xij � 0.

    ������ ������ ���������� �� ����������� ������������ ����������-
���� � ���, ��� �������� �� ��������� ������� �� ������ � �����������
������������ ������, �� ����� � ��������������� ���������, ��������-
���� � ������, ���� ��������� ����� ����� �� �����.
    ���������� � ������ ����������� ������� ��������������� �������-
���. ������ ����� �������� ����� ���������� (�������) ��� ����� ����
���������� ��� ������ ����������� ����������������.
                 �� �c             xij � d ij yij � � min,
                 m�     n

                              ij                                                           (1.26)
                 i �1 j �1
                  n
                 � xij � ai ,           i � 1,2,..., m ,                                   (1.27)
                 j �1
                  m

                 �x
                 i �1
                        ij
                             � bj ,      j � 1,2,..., n,                                   (1.28)
                 xij � M ij yij ,                                                          (1.29)
                 ��� M ij � min�ai ,b j �,               xij � 0,    yij � �0,1� �i, j .   (1.30)


                                                     5

Страницы