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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

30
ɍɉɊȺɀɇȿɇɂə
1. ɋɨɫɬɚɜɶɬɟ ɤɨɧɤɪɟɬɧɭɸ ɜɵɱɢɫɥɢɬɟɥɶɧɭɸ ɫɯɟɦɭ ɚɥɝɨɪɢɬɦɚ, ɨɛɟɫɩɟ-
ɱɢɜɚɸɳɟɝɨ ɜ ɤɚɱɟɫɬɜɟ ɨɬɜɟɬɚ ɩɟɪɜɭɸ ɩɨɩɚɜɲɭɸɫɹ ɜ ɪɟɡɭɥɶɬɚɬɟ ɜɵɛɪɚɧɧɨɣ
ɫɬɪɚɬɟɝɢɢ ɞɨɩɭɫɬɢɦɭɸ ɬɨɱɤɭ:
ɚ) ɢɫɩɨɥɶɡɭɣɬɟ ɫɬɪɚɬɟɝɢɸ «ɩɨ ɦɚɤɫɢɦɭɦɭ ɨɰɟɧɤɢ»,
ɛ) ɢɫɩɨɥɶɡɭɣɬɟ ɫɬɪɚɬɟɝɢɸ ɨɞɧɨɫɬɨɪɨɧɧɟɝɨ ɨɛɯɨɞɚ ɞɟɪɟɜɚ.
2. ɉɪɟɞɥɨɠɢɬɟ ɪɟɤɨɦɟɧɞɚɰɢɢ ɩɨ ɭɩɪɚɜɥɟɧɢɸ ɩɚɪɚɦɟɬɪɚɦɢ
N
ɢ
A
ɜ
ɩɪɨɰɟɫɫɟ ɪɚɛɨɬɵ ɚɥɝɨɪɢɬɦɚ (ɤɚɤ ɪɟɚɤɰɢɸ ɧɚ ɩɨɫɬɭɩɚɸɳɭɸ ɢɧɮɨɪɦɚɰɢɸ ɜ
ɩɪɨɰɟɫɫɟ ɪɚɛɨɬɵ ɚɥɝɨɪɢɬɦɚ).
3. ɋɨɫɬɚɜɶɬɟ ɚɥɝɨɪɢɬɦ ɪɟɲɟɧɢɹ ɡɚɞɚɱɢ ɥɢɧɟɣɧɨɝɨ ɩɪɨɝɪɚɦɦɢɪɨɜɚɧɢɹ ɫ
ɰɟɥɨɱɢɫɥɟɧɧɵɦɢ ɩɟɪɟɦɟɧɧɵɦɢ ɩɪɢ 2
N
,
2
minmax
[
[
A
.
4. ɋɨɫɬɚɜɶɬɟ ɚɥɝɨɪɢɬɦɵ ɪɟɲɟɧɢɹ ɡɚɞɚɱɢ ɤɨɦɦɢɜɨɹɠɟɪɚ ɩɪɢ
ɚ) 1
N
,
R
A
(
2
minmax
[
[
A
);
ɛ)4
N
,
0,
max
!
H
H
[
A
.
5. ɋɨɫɬɚɜɶɬɟ ɚɥɝɨɪɢɬɦ ɪɟɲɟɧɢɹ ɡɚɞɚɱɢ ɞɥɹ ɤɨɧɜɟɣɟɪɧɨɣ ɫɢɫɬɟɦɵ ɩɪɢ
ɚ)5
N
,
0,
0
!
H
H
[
A
;
ɛ) 5
N
,
0,
min
!
H
H
[
A
;
ɜ) 5
N
,
2
minmax
[
[
A
;
ɝ) 5
N
,

2
,max
min0max
[
[
[
A
.
6. ȼ ɤɚɤɢɯ ɫɥɭɱɚɹɯ ɦɨɠɟɬ ɛɵɬɶ ɧɟ ɩɨɥɭɱɟɧɨ ɧɢ ɨɞɧɨɣ ɞɨɩɭɫɬɢɦɨɣ ɬɨɱ-
ɤɢ?
4. ɆȿɌɈȾɕ ɈɌɋȿɑȿɇɂɃ
Ɉɫɧɨɜɧɚɹ ɢɞɟɹ ɦɟɬɨɞɨɜ ɨɬɫɟɱɟɧɢɣ (ɦɟɬɨɞɨɜ ɫɟɤɭɳɢɯ ɩɥɨɫɤɨɫɬɟɣ) ɫɨ-
ɫɬɨɢɬ ɜ ɫɥɟɞɭɸɳɟɦ. ɂɫɯɨɞɧɚɹ ɡɚɞɚɱɚ «ɩɨɝɪɭɠɚɟɬɫɹ» ɜ ɡɚɞɚɱɭ ɥɢɧɟɣɧɨɝɨ
ɩɪɨɝɪɚɦɦɢɪɨɜɚɧɢɹ, ɤɨɬɨɪɚɹ ɦɨɠɟɬ ɛɵɬɶ ɪɟɲɟɧɚ, ɧɚɩɪɢɦɟɪ, ɫɬɚɧɞɚɪɬɧɵɦ
ɫɢɦɩɥɟɤɫɧɵɦ ɦɟɬɨɞɨɦ. ɉɨɥɭɱɟɧɧɨɟ ɜ ɪɟɡɭɥɶɬɚɬɟ ɪɟɲɟɧɢɟ ɩɪɨɜɟɪɹɟɬɫɹ ɧɚ
ɞɨɩɭɫɬɢɦɨɫɬɶ ɜ ɢɫɯɨɞɧɨɣ ɡɚɞɚɱɟ. ȿɫɥɢ ɩɨɥɭɱɟɧɧɚɹ ɬɨɱɤɚ ɞɨɩɭɫɬɢɦɚ,
ɬɨ
ɨɧɚ ɹɜɥɹɟɬɫɹ ɪɟɲɟɧɢɟɦ ɢɫɯɨɞɧɨɣ ɡɚɞɚɱɢ
.
                                       ����������

    1. ��������� ���������� �������������� ����� ���������, ������-
��������� � �������� ������ ������ ���������� � ���������� ���������
��������� ���������� �����:
         �) ����������� ��������� «�� ��������� ������»,
         �) ����������� ��������� �������������� ������ ������.
    2. ���������� ������������ �� ���������� ����������� N � A �
�������� ������ ��������� (��� ������� �� ����������� ���������� �
�������� ������ ���������).
    3. ��������� �������� ������� ������ ��������� ���������������� �
                                            � � � min
�������������� ����������� ��� N � 2 , A � max        .
                                                2
      4. ��������� ��������� ������� ������ ������������ ���
                                 � max � � min
      �) N � 1 , A � R ( A �                     );
                                           2
      �) N � 4 , A � � max � � , � � 0 .


      5. ��������� �������� ������� ������ ��� ����������� ������� ���
      �) N � 5 , A � � 0 � � , � � 0 ;
      �) N � 5 , A � � min � � , � � 0 ;
                       � max � � min
      �) N � 5 , A �                   ;
                             2
                       � max � max�� 0 , � min �
      �) N � 5 , A �                                  .
                                   2
      6. � ����� ������� ����� ���� �� �������� �� ����� ���������� ���-
��?
                             4. ������ ���������

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

                                                  30

Страницы