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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

26
(2)
(1)
(3)
x
0
x
2
7
3
5
7
x
1
ɋɯɟɦɚ ɪɚɛɨɬɵ ɦɟɬɨɞɚ ɜɟɬɜɟɣ ɢ ɝɪɚɧɢɰ ɞɥɹ ɐɁɅɉ
ɒɚɝ 1.
Ɉɩɪɟɞɟɥɟɧɢɟ ɧɚɱɚɥɶɧɨɝɨ ɪɟɤɨɪɞɚ. (ɉɪɢ ɨɬɫɭɬɫɬɜɢɢ ɞɨɩɨɥɧɢɬɟɥɶ-
ɧɨɣ ɢɧɮɨɪɦɚɰɢɢ R = f ). Ɂɚɞɚɬɶ k = 0.
ɒɚɝ 2. Ɋɟɲɟɧɢɟ ɨɰɟɧɨɱɧɨɣ ɡɚɞɚɱɢ ɧɚ ɦɧɨɠɟɫɬɜɟ
0
:
. ȿɫɥɢ ɩɨɥɭɱɟɧɧɚɹ
ɬɨɱɤɚ
0
x
ɰɟɥɨɱɢɫɥɟɧɧɚɹ, ɬɨ ɪɟɲɟɧɢɟ ɧɚɣɞɟɧɨ. Ɉɫɬɚɧɨɜ.
ɒɚɝ 3. ȼɵɛɨɪ ɢɧɞɟɤɫɚ
j
ɬɚɤɨɝɨ, ɱɬɨ ɤɨɨɪɞɢɧɚɬɚ
j
k
x
— ɧɟ ɰɟɥɚɹ.
ɒɚɝ 4. ȼɟɬɜɥɟɧɢɟ
21
kkk
:: : .
ɒɚɝ 5. Ɋɟɲɟɧɢɟ ɨɰɟɧɨɱɧɵɯ ɡɚɞɚɱ ɥɢɧɟɣɧɨɝɨ ɩɪɨɝɪɚɦɦɢɪɨɜɚɧɢɹ ɢ ɜɵɱɢɫ-
ɥɟɧɢɟ ɨɰɟɧɨɤ )(
2
k
:
[
ɢ )(
1
k
:
[
. ȿɫɥɢ ɤɚɤɚɹ-ɬɨ ɢɡ ɩɨɥɭɱɟɧɧɵɯ ɨɩɬɢɦɚɥɶɧɵɯ
ɬɨɱɟɤ ɰɟɥɨɱɢɫɥɟɧɧɚɹ, ɬɨ ɩɟɪɟɯɨɞ ɤ ɲɚɝɭ 7.
ɒɚɝ 6. ȼɵɛɨɪ ɩɟɪɫɩɟɤɬɢɜɧɨɝɨ ɦɧɨɠɟɫɬɜɚ
s
:
ɜ ɫɨɨɬɜɟɬɫɬɜɢɢ ɫɨ ɫɬɪɚɬɟɝɢ-
ɟɣ. ɉɨɥɨɠɢɬɶ .
k ɉɟɪɟɯɨɞ ɤ ɲɚɝɭ 2.
ɒɚɝ 7. ȼɨɡɦɨɠɧɚɹ ɫɦɟɧɚ ɪɟɤɨɪɞɚ ɢ ɫɨɤɪɚɳɟɧɢɟ ɩɟɪɟɛɨɪɚ ɡɚ ɫɱɟɬ ɨɬɛɪɚɫɵ-
ɜɚɧɢɹ ɧɟɩɟɪɫɩɟɤɬɢɜɧɵɯ ɦɧɨɠɟɫɬɜ.
ɒɚɝ 8. ɉɪɨɜɟɪɤɚ ɤɪɢɬɟɪɢɹ ɨɩɬɢɦɚɥɶɧɨɫɬɢ. ȿɫɥɢ ɨɧ ɜɵɩɨɥɧɟɧ, ɨɫɬɚɧɨɜ.
ɂɧɚɱɟ ɩɟɪɟɯɨɞ ɤ ɲɚɝɭ 6.
ɉɪɢɦɟɪ.



°
°
¯
°
°
®
=t
d
d
d
:
o
.x,x,x,x
,xx
,xx
,xx
min,xx
2121
21
21
21
0
21
0
3554
27
138112
ɉɨɥɚɝɚɟɦ R = f .
Ɋɟɲɚɟɦ ɢɫɯɨɞɧɭɸ ɡɚɞɚɱɭ ɛɟɡ
ɬɪɟɛɨɜɚɧɢɹ ɰɟɥɨɱɢɫɥɟɧɧɨɫɬɢ. Ƚɪɚ-
ɮɢɱɟɫɤɚɹ ɢɥɥɸɫɬɪɚɰɢɹ ɪɟɲɟɧɢɹ
ɩɪɢɜɟɞɟɧɚ ɧɚ ɪɢɫɭɧɤɟ. Ɉɩɬɢɦɚɥɶɧɨɣ ɬɨɱɤɨɣ ɹɜɥɹɟɬɫɹ
)2,4(
9
5
9
4
0
x
,
7)()(
0
0
: x
M[
.
Ɍɚɤ ɤɚɤ ɬɨɱɤɚ ɧɟ ɰɟɥɨɱɢɫɥɟɧɧɚɹ, ɨɫɭɳɟɫɬɜɥɹɟɦ ɜɟɬɜɥɟɧɢɟ (ɧɚɩɪɢɦɟɪ,
ɩɨ ɩɟɪɜɨɣ ɤɨɨɪɞɢɧɚɬɟ):
,
210
:: : }4,{
101
d: : xx
,
}5,{
102
t: : xx
.
Ɋɟɲɚɟɦ ɞɜɟ ɡɚɞɚɱɢ ɥɢɧɟɣɧɨɝɨ ɩɪɨɝɪɚɦɦɢɪɨɜɚɧɢɹ, ɡɚɤɥɸɱɚɸɳɢɟɫɹ ɜ
ɦɢɧɢɦɢɡɚɰɢɢ ɮɭɧɤɰɢɢ )(
x
M
ɧɚ ɦɧɨɠɟɫɬɜɚɯ
1
:
ɢ
2
:
ɛɟɡ ɬɪɟɛɨɜɚɧɢɹ ɰɟɥɨ-
ɱɢɫɥɟɧɧɨɫɬɢ. ɉɨɥɭɱɚɟɦ
)2,4(
11
8
1
x
,
6)(
1
:
[
,
:
2
Ø. ɉɨɥɚɝɚɟɦ
f : )(
2
[
.
            ����� ������ ������ ������ � ������ ��� ����

��� 1. ����������� ���������� �������. (��� ���������� �����������-
��� ���������� R = � � ). ������ k = 0.
��� 2. ������� ��������� ������ �� ��������� � 0 . ���� ����������
����� x 0 �������������, �� ������� �������. �������.
��� 3. ����� ������� j ������, ��� ���������� xkj — �� �����.
��� 4. ��������� � k � � k1 � � k2 .
��� 5. ������� ��������� ����� ��������� ���������������� � �����-
����� ������ � (� k2 ) � � (� k1 ) . ���� �����-�� �� ���������� �����������
����� �������������, �� ������� � ���� 7.
��� 6. ����� �������������� ��������� � s � ������������ �� ��������-
��. �������� k � s. ������� � ���� 2.
��� 7. ��������� ����� ������� � ���������� �������� �� ���� �������-
����� ��������������� ��������.
��� 8. �������� �������� �������������. ���� �� ��������, �������.
����� ������� � ���� 6.
                                             x1
������.
                                             7      (2)
     � x1 � x2 � min,
   �2 x1 � 11x2 � 38, �1�
   �x � x � 7,                              (3)
   � 1                        �2�
�0 �          2


   �4 x1 � 5 x2 � 5,          �3� 3                                (1)
   �� x1 , x2 � 0, x1 , x2 � �.               x0
�������� R = � � .                                                                  x2
       ������ �������� ������ ���
���������� ���������������. ���-                5                        7
�������� ����������� �������
��������� �� �������. ����������� ������ ��������                  x 0 � (4 94 ,2 95 ) ,
� ( � 0 ) � � ( x 0 ) � �7 .
         ��� ��� ����� �� �������������, ������������ ��������� (��������,
��        ������          ����������): � 0 � �1 � � 2 , �1 � {x � � 0 , x1 � 4} ,
� 2 � {x � � 0 , x1 � 5} .
         ������ ��� ������ ��������� ����������������, ������������� �
����������� ������� � (x ) �� ���������� �1 � � 2 ��� ���������� ����-
�����������. ��������        x1 � (4,2 118 ) , � (�1 ) � �6 , � 2 � Ø. ��������
� (� 2 ) � �� .
                                       26

Страницы