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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

35
ɇɚ 3-ɣ ɢɬɟɪɚɰɢɢ ɫɢɦɩɥɟɤɫ-ɦɟɬɨɞɚ ɧɚɣɞɟɧɨ ɧɟɰɟɥɨɱɢɫɥɟɧɧɨɟ ɪɟɲɟɧɢɟ
)
2
25
,0,0,
6
35
,
3
5
(
1
x . ȼɵɛɢɪɚɟɦ, ɧɚɩɪɢɦɟɪ,
3
5
1
1
x – ɞɪɨɛɧɭɸ ɛɚɡɢɫɧɭɸ ɤɨ-
ɨɪɞɢɧɚɬɭ – ɢ ɩɨ ɫɨɨɬɜɟɬɫɬɜɭɸɳɟɣ ɫɬɪɨɤɟ ɬɚɛɥɢɰɵ ɮɨɪɦɢɪɭɟɦ ɧɨɜɨɟ ɨɝɪɚ-
ɧɢɱɟɧɢɟ:
}{}{}{
3
5
64
3
1
3
3
1
xxx
. ɂɥɢ:
3
2
64
3
1
3
3
1
xxx
. Ⱦɨ-
ɛɚɜɥɹɟɦ ɷɬɨ ɨɝɪɚɧɢɱɟɧɢɟ ɜ ɬɚɛɥɢɰɭ ɢ ɨɫɭɳɟɫɬɜɥɹɟɦ ɨɞɧɭ ɢɬɟɪɚɰɢɸ ɞɜɨɣ-
ɫɬɜɟɧɧɨɝɨ ɫɢɦɩɥɟɤɫ-ɦɟɬɨɞɚ. ȼ ɪɟɡɭɥɶɬɚɬɟ ɩɨɥɭɱɚɟɦ ɬɨɱɤɭ
)0,
2
23
,0,1,
2
11
,2(
2
x
. ȼɵɛɢɪɚɟɦ ɞɪɨɛɧɭɸ ɤɨɨɪɞɢɧɚɬɭ
2
11
2
2
x
ɢ ɞɨɛɚɜɥɹɟɦ
ɨɝɪɚɧɢɱɟɧɢɟ
2
1
76
2
1
xx
ɢɬ. ɞ.
ɇɚ ɩɨɫɥɟɞɧɟɣ ɢɬɟɪɚɰɢɢ ɩɨɥɭɱɟɧɚ ɬɨɱɤɚ
)0,0,1,11,1,2,5,2(
4
x
, ɤɨɬɨɪɚɹ
ɹɜɥɹɟɬɫɹ ɰɟɥɨɱɢɫɥɟɧɧɨɣ. Ɉɫɬɚɧɨɜ.
Ɉɬɜɟɬ:
)5,2(
*
x
,
.22)(
*
x
M
ɍɉɊȺɀɇȿɇɂə
1. Ⱦɨ ɩɪɢɜɟɞɟɧɢɹ ɡɚɞɚɱɢ ɤ ɤɚɧɨɧɢɱɟɫɤɨɦɭ ɜɢɞɭ ɜɫɟ ɢɫɯɨɞɧɵɟ ɞɚɧɧɵɟ
ɞɨɥɠɧɵ ɛɵɬɶ ɩɪɢɜɟɞɟɧɵ ɤ ɰɟɥɵɦ. ɉɨɱɟɦɭ?
2. Ɋɟɲɢɬɶ ɐɁɅɉ ɦɟɬɨɞɨɦ ɨɬɫɟɱɟɧɢɣ:
.x,x,0x,x
,0x11x7
,11x2
,2/7xx
max,x4x3)a
2121
21
1
21
21
=t
d
d
d
o
.x,x,0x,x
,48xx6
,40x5x
,4xx2
max,x2x)b
2121
21
21
21
21
=t
d
d
d
o
.x,x,0x,x
,10xx2
,7xx
,10x2x
max,x4x)c
2121
21
2
1
21
21
21
=t
d
d
d
o
Ɉɬɜɟɬ:
max
x
=(5,3). Ɉɬɜɟɬ:
max
x
=(6,9). Ɉɬɜɟɬ:
max
x
=(2,5).
5. ȾɂɇȺɆɂɑȿɋɄɈȿ ɉɊɈȽɊȺɆɆɂɊɈȼȺɇɂȿ
ȼ ɞɚɧɧɨɦ ɪɚɡɞɟɥɟ ɪɚɫɫɦɚɬɪɢɜɚɸɬɫɹ ɡɚɞɚɱɢ ɨɩɬɢɦɚɥɶɧɨɝɨ ɭɩɪɚɜɥɟɧɢɹ,
ɨɛɥɚɞɚɸɳɢɟ ɫɥɟɞɭɸɳɢɦɢ ɫɜɨɣɫɬɜɚɦɢ:
 ɩɪɨɰɟɫɫ ɩɪɢɧɹɬɢɹ ɪɟɲɟɧɢɹ ɦɨɠɟɬ ɛɵɬɶ ɪɚɡɛɢɬ ɧɚ ɨɬɞɟɥɶɧɵɟ ɷɬɚɩɵ
(ɲɚɝɢ);
 ɪɟɲɟɧɢɟ, ɩɪɢɧɢɦɚɟɦɨɟ ɧɚ ɤɚɠɞɨɦ ɲɚɝɟ, ɡɚɜɢɫɢɬ ɬɨɥɶɤɨ ɨɬ ɫɨɫɬɨɹɧɢɹ
ɭɩɪɚɜɥɹɟɦɨɝɨ ɨɛɴɟɤɬɚ ɧɚ ɞɚɧɧɨɦ ɲɚɝɟ;
 ɫɨɫɬɨɹɧɢɟ ɨɛɴɟɤɬɚ ɜ ɤɨɧɰɟ ɤɚɠɞɨɝɨ ɲɚɝɚ ɡɚɜɢɫɢɬ ɬɨɥɶɤɨ ɨɬ ɫɨɫɬɨɹ-
ɧɢɹ ɜ ɧɚɱɚɥɟ ɲɚɝɚ ɢ ɨɬ ɪɟɲɟɧɢɹ, ɩɪɢɧɢɦɚɟɦɨɝɨ ɧɚ ɷɬɨɦ ɲɚɝɟ;
     �� 3-� �������� ��������-������ ������� ��������������� �������
      5 35     25                           5
x1 � ( , ,0,0, ) . ��������, ��������, x11 � – ������� �������� ��-
      3 6      2                            3
�������� – � �� ��������������� ������ ������� ��������� ����� ����-
�������: {3}x3 �{3}x4 � x6 � �{3}. ���: 3 x3 � 3 x 4 � x6 � � 3 . ��-
                 1          1                  5              1   1                       2

������� ��� ����������� � ������� � ������������ ���� �������� ����-
���������    ��������-������.    �    ����������   ��������    �����
  2    11    23                                    2  11
x � (2, ,1,0, ,0) . �������� ������� ���������� x2 �     � ���������
        2     2                                        2
�����������          � 12 x6 � x7 � � 12   � �. �.
    �� ��������� �������� �������� ����� x 4 � (2, 5, 2,1,11,1,0, 0) , �������
�������� �������������. �������.
    �����: x* � (2, 5) , � ( x* ) � 22.

                                      ����������

    1. �� ���������� ������ � ������������� ���� ��� �������� ������
������ ���� ��������� � �����. ������?
    2. ������ ���� ������� ���������:

a ) 3 x1 � 4 x2 � max,            b ) x1 � 2 x2 � max,            c ) x1 � 4 x2 � max,
  x1 � x2 � 7 / 2 ,                  � 2 x1 � x2 � 4 ,                � x1 � 2 x2 � 10 ,
  2 x1 � 11,                         � x1 � 5 x2 � 40 ,               x1 � x2 � 7 21 ,
  � 7 x1 � 11x2 � 0 ,                6 x1 � x2 � 48 ,                 2 x1 � x2 � 10 ,
  x1 , x2 � 0 , x1 , x2 � �.         x1 , x2 � 0 , x1 , x2 � �.       x1 , x2 � 0 , x1 , x2 � �.
           max                               max
�����: x         =(5,3).         �����: x          =(6,9).         �����: x max =(2,5).


                 5. ������������ ����������������

     � ������ ������� ��������������� ������ ������������ ����������,
���������� ���������� ����������:
   �� ������� �������� ������� ����� ���� ������ �� ��������� �����
      (����);
   �� �������, ����������� �� ������ ����, ������� ������ �� ���������
      ������������ ������� �� ������ ����;
   �� ��������� ������� � ����� ������� ���� ������� ������ �� ������-
      ��� � ������ ���� � �� �������, ������������ �� ���� ����;
                                                   35

Страницы