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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

3
1. ɆȺɌȿɆȺɌɂɑȿɋɄɂȿ ɆɈȾȿɅɂ
ȾɂɋɄɊȿɌɇɈȽɈ ɉɊɈȽɊȺɆɆɂɊɈȼȺɇɂə
I. ɐɟɥɨɱɢɫɥɟɧɧɵɟ ɡɚɞɚɱɢ ɥɢɧɟɣɧɨɝɨ ɩɪɨɝɪɚɦɦɢɪɨɜɚɧɢɹ
1) ɉɪɨɢɡɜɨɥɶɧɚɹ ɡɚɞɚɱɚ (ɐɁɅɉ).
,b
A
x
(1.1)
,0t
x
(1.2)
,,...,2,1, njɱɢɫɥɚɰɟɥɵɟx
j
(1.3)

.minmax
1
¦
o
n
j
jj
xc (1.4)
Ɍɪɟɛɨɜɚɧɢɟ ɰɟɥɨɱɢɫɥɟɧɧɨɫɬɢ ɩɟɪɟɦɟɧɧɵɯ ɩɨɹɜɥɹɟɬɫɹ, ɧɚɩɪɢɦɟɪ, ɜɡɚ-
ɞɚɱɚɯ ɨɩɬɢɦɚɥɶɧɨɝɨ ɩɥɚɧɢɪɨɜɚɧɢɹ ɧɚ ɩɪɨɢɡɜɨɞɫɬɜɚɯ, ɫɩɟɰɢɚɥɢɡɢɪɭɸɳɢɯ-
ɫɹ ɩɨ ɜɵɩɭɫɤɭ ɲɬɭɱɧɵɯ ɢɡɞɟɥɢɣ.
2) Ɂɚɞɚɱɚ ɨ ɪɚɧɰɟ.
^`
1,0
j
x , (1.5)
¦
d
n
j
jj
Axa
1
, (1.6)
¦
o
n
j
jj
xc
1
max
. (1.7)
Ɍɚɤɚɹ ɡɚɞɚɱɚ ɜɨɡɧɢɤɚɟɬ ɩɪɢ ɜɵɛɨɪɟ ɧɚɛɨɪɚ ɩɪɟɞɦɟɬɨɜ ɦɚɤɫɢɦɚɥɶɧɨɣ
ɫɬɨɢɦɨɫɬɢ ɞɥɹ ɩɨɝɪɭɡɤɢ ɜ ɧɟɤɨɬɨɪɭɸ ɬɚɪɭ (ɪɚɧɟɰ) ɩɪɢ ɨɝɪɚɧɢɱɟɧɢɹɯ ɧɚ
ɨɛɴɟɦ ɢɥɢ ɧɚ «ɝɪɭɡɨɩɨɞɴɟɦɧɨɫɬɶ».
Ɉɛɨɛɳɟɧɢɟɦ ɷɬɨɣ ɡɚɞɚɱɢ ɹɜɥɹɟɬɫɹ ɦɧɨɝɨɦɟɪɧɚɹ ɡɚɞɚɱɚ ɨ ɪɚɧɰɟ, ɜɤɨ-
ɬɨɪɨɣ ɩɪɢɫɭɬɫɬɜɭɟɬ ɧɟɫɤɨɥɶɤɨ ɨɝɪɚɧɢɱɟɧɢɣ. ȿɫɥɢ, ɤɪɨɦɟ ɬɨɝɨ, ɤɚɠɞɵɣ
ɩɪɟɞɦɟɬ ɢɦɟɟɬɫɹ ɜ ɤɨɥɢɱɟɫɬɜɟ ɧɟɫɤɨɥɶɤɢɯ ɟɞɢɧɢɰ, ɬɨ ɬɪɟɛɨɜɚɧɢɟ (1.5) ɡɚ-
ɦɟɧɹɟɬɫɹ
ɧɚ ɬɪɟɛɨɜɚɧɢɟ ɰɟɥɨɱɢɫɥɟɧɧɨɫɬɢ. ȼ ɬɚɤɨɦ ɫɥɭɱɚɟ ɡɚɞɚɱɚ ɨ ɪɚɧɰɟ
ɩɪɟɜɪɚɳɚɟɬɫɹ ɜ ɰɟɥɨɱɢɫɥɟɧɧɭɸ ɡɚɞɚɱɭ ɥɢɧɟɣɧɨɝɨ ɩɪɨɝɪɚɦɦɢɪɨɜɚɧɢɹ ɫ ɧɟ-
ɨɬɪɢɰɚɬɟɥɶɧɨɣ ɦɚɬɪɢɰɟɣ ɨɝɪɚɧɢɱɟɧɢɣ.
II. Ɂɚɞɚɱɢ ɤɨɦɛɢɧɚɬɨɪɧɨɝɨ ɬɢɩɚ
1) Ɂɚɞɚɱɚ ɨ ɧɚɡɧɚɱɟɧɢɹɯ (ɡɚɞɚɱɚ ɜɵɛɨɪɚ).
^`
1,0
ij
x , (1.8)
nix
n
i
ij
,...,2,1,1
1
¦
, (1.9) 
                1. �������������� ������
             ����������� ����������������

I. ������������� ������ ��������� ����������������

    1) ������������ ������ (����).
                            Ax � b,                                           (1.1)
                            x � 0,                                            (1.2)
                            x j � ����� �����,              j � 1,2,..., n,   (1.3)
                              n

                             �c     j   x j � max�min �.                      (1.4)
                             j �1



     ���������� ��������������� ���������� ����������, ��������, � ��-
����� ������������ ������������ �� �������������, ����������������-
�� �� ������� ������� �������.

    2) ������ � �����.
                             x j � �0,1�,                                     (1.5)
                              n
                             �ajxj � A          ,                             (1.6)
                             j �1
                              n
                             � c j x j � max .                                (1.7)
                             j �1


    ����� ������ ��������� ��� ������ ������ ��������� ������������
��������� ��� �������� � ��������� ���� (�����) ��� ������������ ��
����� ��� �� «����������������».
    ���������� ���� ������ �������� ����������� ������ � �����, � ��-
����� ������������ ��������� �����������. ����, ����� ����, ������
������� ������� � ���������� ���������� ������, �� ���������� (1.5) ��-
�������� �� ���������� ���������������. � ����� ������ ������ � �����
������������ � ������������� ������ ��������� ���������������� � ��-
������������� �������� �����������.

II. ������ �������������� ����

    1) ������ � ����������� (������ ������).
                            xij � �0,1� ,                                     (1.8)
                              n
                             � xij � 1,       i � 1,2,..., n ,                (1.9)
                             i �1

                                          3

Страницы