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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

38
Ɋɟɲɟɧɢɟ.
Ɋɚɡɛɢɜɚɟɦ ɩɪɨɰɟɫɫ ɪɟɲɟɧɢɹ ɧɚ ɱɟɬɵɪɟ ɷɬɚɩɚ (ɩɨ ɤɨɥɢɱɟɫɬɜɭ ɩɪɟɞɩɪɢ-
ɹɬɢɣ).
I ɷɬɚɩ. Ɉɛɫɭɠɞɚɸɬɫɹ ɢɧɜɟɫɬɢɰɢɢ ɧɚ ɩɟɪɜɨɟ ɩɪɟɞɩɪɢɹɬɢɟ.
ȼɨɡɦɨɠɧɵɟ ɡɧɚɱɟɧɢɹ ɩɟɪɟɦɟɧɧɨɣ ɩɪɢ ɫɨɫɬɨɹɧɢɢ S = 80 ɦɨɝɭɬ ɛɵɬɶ ɪɚɜɧɵ-
ɦɢ 0, 20, 40, 60, 80.
ɉɨɫɤɨɥɶɤɭ ɜ ɡɚɞɚɱɟ ɫ ɨɞɧɨɣ ɩɟɪɟɦɟɧɧɨɣ ɜɵɛɨɪ ɨɬɫɭɬɫɬɜɭɟɬ, ɬɨ ɜɤɥɚ-
ɞɵɜɚɟɦɚɹ ɫɭɦɦɚ
1
x
ɛɭɞɟɬ ɪɚɜɧɚ ɜɵɞɟɥɟɧɧɵɦ ɫɪɟɞɫɬɜɚɦ S ɢ ɨɩɬɢɦɚɥɶɧɵɟ
ɡɧɚɱɟɧɢɹ ɰɟɥɟɜɨɣ ɮɭɧɤɰɢɢ ɛɭɞɭɬ ɪɚɜɧɵ
 
111
xgSf
.
Ɍɚɤɢɦ ɨɛɪɚɡɨɦ,
  
.3680,2560,1640,820
1111
ffff
II ɷɬɚɩ. ȼɵɞɟɥɟɧɧɭɸ ɫɭɦɦɭ S ɪɚɫɩɪɟɞɟɥɹɟɦ ɦɟɠɞɭ ɩɟɪɜɵɦ ɢ ɜɬɨɪɵɦ
ɩɪɟɞɩɪɢɹɬɢɹɦɢ. Ɋɟɤɭɪɪɟɧɬɧɨɟ ɭɪɚɜɧɟɧɢɟ ɩɪɢ ɷɬɨɦ ɢɦɟɟɬ ɜɢɞ

^`
.max
21222
2
xSfxgSf
x
ɉɨɢɫɤ ɜɟɞɟɬɫɹ ɩɨ ɩɟɪɟɦɟɧɧɨɣ
2
x
, ɤɨɬɨɪɚɹ ɜ ɡɚɜɢɫɢɦɨɫɬɢ ɨɬ ɱɢɫɥɚ S
ɦɨɠɟɬ ɩɪɢɧɢɦɚɬɶ ɡɧɚɱɟɧɢɹ 0; 20;…S.
Ɍɚɤɢɦ ɨɛɪɚɡɨɦ:
ɩɪɢ S = 20
 ^ `
10100,08max20
2
f
ɩɪɢ
;20
2
x
ɩɪɢ S = 40
 ^ `
2020,108,16max40
2
f
ɩɪɢ
;40
2
x
ɩɪɢ S = 60
 ^ `
2828,208,1016,25max60f
2
ɩɪɢ
40
2
x
, ɚ ɬɚɤɠɟ
ɩɪɢ
60
2
x
;
ɩɪɢ S = 80
ɦɚɤɫɢɦɭɦ ɞɨɫɬɢɝɚɟɬɫɹ ɩɪɢ
80
2
x
.
III ɷɬɚɩ. Ɋɟɲɚɟɬɫɹ ɡɚɞɚɱɚ ɪɚɫɩɪɟɞɟɥɟɧɢɹ ɫɪɟɞɫɬɜ ɦɟɠɞɭ ɬɪɟɦɹ ɩɪɟɞɩɪɢ-
ɹɬɢɹɦɢ. Ɋɟɤɭɪɪɟɧɬɧɨɟ ɭɪɚɜɧɟɧɢɟ ɜ ɷɬɨɦ ɫɥɭɱɚɟ ɢɦɟɟɬ ɜɢɞ
 ^`
.max
32333
3
xSfxgSf
x
ɉɨɢɫɤ ɜɟɞɟɬɫɹ ɩɨ ɩɟɪɟɦɟɧɧɨɣ
3
x
, ɤɨɬɨɪɚɹ ɦɨɠɟɬ ɩɪɢɧɢɦɚɬɶ ɡɧɚɱɟɧɢɹ
0, 20,…S.
ɩɪɢ S = 20
 ^ `
1212,10max20
3
f
ɩɪɢ
;20
3
x
ɩɪɢ S = 40
 ^ `
2221,1210,20max40
3
f
ɩɪɢ
;20
3
x
ɩɪɢ S = 60
 ^ `
2827,2110,1220,28max60
3
f
ɩɪɢ
;0
3
x
ɩɪɢ S = 80
 ^ `
4138,2710,2120,1228,40max80
3
f
ɦɚɤɫɢɦɭɦ
ɞɨɫɬɢɝɚɟɬɫɹ ɩɪɢ
.40
3
x
�������.
    ��������� ������� ������� �� ������ ����� (�� ���������� �������-
����).
I ����. ����������� ���������� �� ������ �����������.
��������� �������� ���������� ��� ��������� S = 80 ����� ���� �����-
�� 0, 20, 40, 60, 80.
    ��������� � ������ � ����� ���������� ����� �����������, �� ����-
�������� ����� x1 ����� ����� ���������� ��������� S � �����������
�������� ������� ������� ����� ����� f1 �S � � g1 � x1 � .
    ����� �������,

                 f1 �20 � � 8, f1 �40 � � 16, f1 �60 � � 25, f1 �80 � � 36.

II ����. ���������� ����� S ������������ ����� ������ � ������
�������������. ������������ ��������� ��� ���� ����� ���

                         f 2 �S � � max�g 2 � x2 � � f1 �S � x2 ��.
                                     x2



    ����� ������� �� ���������� x2 , ������� � ����������� �� ����� S
����� ��������� �������� 0; 20;…S.
    ����� �������:
��� S = 20 � f 2 �20 � � max�8 � 0, 0 � 10� � 10 ��� x2 � 20;
��� S = 40 � f 2 �40 � � max�16, 8 � 10, 20� � 20 ��� x2 � 40;
��� S = 60 � f 2 �60 � � max�25, 16 � 10, 8 � 20, 28� � 28 ��� x2 � 40 , � �����
��� x2 � 60 ;
��� S = 80 � �������� ����������� ��� x2 � 80 .

III ����. �������� ������ ������������� ������� ����� ����� �������-
������. ������������ ��������� � ���� ������ ����� ���

                         f 3 �S � � max�g 3 � x3 � � f 2 �S � x3 ��.
                                     x3



     ����� ������� �� ���������� x3 , ������� ����� ��������� ��������
0, 20,…S.
��� S = 20 � f 3 �20 � � max�10, 12� � 12 ��� x3 � 20;
��� S = 40 � f 3 �40 � � max�20, 10 � 12, 21� � 22 ��� x3 � 20;
��� S = 60 � f 3 �60 � � max�28, 20 � 12, 10 � 21, 27� � 28 ��� x3 � 0;
��� S = 80 � f 3 �80 � � max�40, 28 � 12, 20 � 21, 10 � 27, 38� � 41 ��������
����������� ��� x3 � 40.

                                            38

Страницы