Практическая работа: Линейное и нелинейное программирование

--PAGE_BREAK--↑
b
ξ1
x2
ξ4
x4
x5
x6
F
3
0
3
1
0
0
1
-3
0
-3/5
9/5
0
-3/5
9/5
x1
3
0
-1
1
0
0
1
1
0
1/5
-3/5
0
1/5
-3/5
ξ2
5
0
0
1
1
0
1
0
0
0
0
0
0
0
←
ξ3
5
0
5
-3
0
1
-3
1
1
0
1/5
-3/5
0
1/5
-3/5
x3
5
-1
-3
2
0
0
2
3
0
3/5
-9/5
0
3/5
-9/5
f
10
-1
5
-3
1
1
-2
-5
0
-1
3
0
-1
3
 
↑
b
ξ1
ξ3
ξ4
x4
x5
x6
F
0
0
-3/5
14/5
0
-3/5
14/5
-14
0
0
-14/5
-14/5
0
-14/5
x1
4
0
1/2
2/5
0
1/5
2/5
10
-2
0
0
-2/5
-2/5
0
-2/5
←
ξ2
5
0
0
1
1
0
1
5
5
0
0
1
1
0
1
x2
1
0
1/5
-3/5
0
1/5
-3/5
3
0
0
3/5
3/5
0
3/5
x3
8
-1
3/5
1/5
0
3/5
1/5
40
-1
0
0
-1/5
-1/5
0
-1/5
f
5
-1
-1
0
1
0
1
-5
0
0
-1
-1
0
-1
 
<img width=«4» height=«268» src=«dopb38438.zip» v:shapes="_x0000_s1026">
<img width=«4» height=«268» src=«dopb38439.zip» v:shapes="_x0000_s1027">
<img width=«4» height=«268» src=«dopb38439.zip» v:shapes="_x0000_s1028">
b
<img width=«4» height=«268» src=«dopb38440.zip» v:shapes="_x0000_s1029">ξ1
ξ3
ξ4
x4
x5
ξ2
F
-14
0
-3/5
0
-14/5
-3/5
-14/5
x1
2
0
1/5
0
-2/5
1/5
-2/5
x6
5
0
0
1
1
0
1
x2
4
0
1/5
0
3/5
1/5
-3/5
x3
7
-1
3/5
0
-1/5
3/5
-1/5
<img width=«580» height=«4» src=«dopb38441.zip» v:shapes="_x0000_s1030">
f
0
-1
-1
-1
0
0
-1
 
b
x4
x5
F
-14
-14/5
-3/5
x6
5
1
0
x2
4
3/5
1/5
x3
7
-1/5
3/5
x1
2
-2/5
1/5
Допустимое базисное оптимальное решение:
X = (2, 4, 7, 0, 0, 5)
F = -14 <shape id="_x0000_i1063" type="#_x0000_t75" o:ole=""><imagedata src=«7394.files/image043.wmz» o:><img width=«61» height=«59» src=«dopb38431.zip» v:shapes="_x0000_i1063">

2.1.7 Решение двойственной задачи
Прямая задача:
<shape id="_x0000_i1064" type="#_x0000_t75" o:ole=""><imagedata src=«7394.files/image045.wmz» o:><img width=«131» height=«243» src=«dopb38424.zip» v:shapes="_x0000_i1064">
Двойственная задача:
<shape id="_x0000_i1065" type="#_x0000_t75" o:ole=""><imagedata src=«7394.files/image075.wmz» o:><img width=«220» height=«145» src=«dopb38442.zip» v:shapes="_x0000_i1065">
Приводим к каноническому виду:
<shape id="_x0000_i1066" type="#_x0000_t75" o:ole=""><imagedata src=«7394.files/image077.wmz» o:><img width=«220» height=«98» src=«dopb38443.zip» v:shapes="_x0000_i1066">
y1, y3 – базисные переменные, y2, y4, y5, y6 – свободные переменные
<shape id="_x0000_i1067" type="#_x0000_t75" o:ole=""><imagedata src=«7394.files/image079.wmz» o:><img width=«301» height=«121» src=«dopb38444.zip» v:shapes="_x0000_i1067">
↑
b
y2
y4
y5
y6
←
y1
14
5
-5
2
-3
14/5
14/5
1/5
-1
2/5
-3/5
y3
9
3
-3
1
-2
3
-42/5
-3/5
3
-6/5
9/5
Ф’
112
35
-40
12
-25
-98
-7
35
-14
21
b
y2
y4
y5
y6
y1
14/5
1/5
-1
2/5
-3/5
y3
3/5
-3/5
0
-1/5
-1/5
Ф’
14
-7
-5
-2
-4
x1
x2
x3
x4
x5
x6
↕
↕
↕
↕
↕
↕
y5
y6
y1
y2
y3
y4
2
4
7
0
0
5
F’ = Ф’ = 14
X = (2,4,7,0,0,5)
F= -F’ = -14   <shape id="_x0000_i1068" type="#_x0000_t75" o:ole=""><imagedata src=«7394.files/image043.wmz» o:><img width=«61» height=«59» src=«dopb38431.zip» v:shapes="_x0000_i1068">

2.2 Задача целочисленного линейного программирования
2.2.1 Постановка задачи целочисленного линейного программирования
Решить ЗЦЛП, при условии целочисленности всех переменных, входящих в задачу, методом ветвей и границ и методом отсекающих плоскостей (методом Гомори).
<shape id="_x0000_i1069" type="#_x0000_t75" o:ole=""><imagedata src=«7394.files/image081.wmz» o:><img width=«133» height=«98» src=«dopb38445.zip» v:shapes="_x0000_i1069">
 

2.2.2 Метод Гомори
<shape id="_x0000_i1070" type="#_x0000_t75" o:ole=""><imagedata src=«7394.files/image083.wmz» o:><img width=«133» height=«145» src=«dopb38446.zip» v:shapes="_x0000_i1070">
<shape id="_x0000_i1071" type="#_x0000_t75" o:ole=""><imagedata src=«7394.files/image085.wmz» o:><img width=«141» height=«74» src=«dopb38447.zip» v:shapes="_x0000_i1071">
<shape id="_x0000_i1072" type="#_x0000_t75" o:ole=""><imagedata src=«7394.files/image087.wmz» o:><img width=«141» height=«73» src=«dopb38448.zip» v:shapes="_x0000_i1072">
x3, x4 – базисные переменные,  x1, x2 – свободные переменные
<shape id="_x0000_i1073" type="#_x0000_t75" o:ole=""><imagedata src=«7394.files/image089.wmz» o:><img width=«167» height=«74» src=«dopb38449.zip» v:shapes="_x0000_i1073">
↑
b
x1
x2
x3
11
2
3
11/2
-5
-1/2
-1/2
←
x4
10
4
1
10/4
5/2
1/4
1/4
F’
0
2
1
-5
-1/2
-1/2
↑
b
x4
x2
←
x3
6
-1/2
5/2
12/5
12/5
-1/5
2/5
x1
5/2
1/4
1/4
10
-3/5
1/20
-1/10
F’
-5
-1/2
1/2
-6/5
1/10
-1/5
b
x1
x2
x3
12/5
-1/5
2/5
x4
19/10
3/10
-1/10
F’
-31/5
-2/5
-1/5
X = (19/10, 12/5, 0, 0)
F = -F’ = 31/5
Составляем неравенство Гомори:
<shape id="_x0000_i1074" type="#_x0000_t75" o:ole=""><imagedata src=«7394.files/image091.wmz» o:><img width=«168» height=«281» src=«dopb38450.zip» v:shapes="_x0000_i1074">
↑
b
x4
x3
F’
-31/5
-2/5
-1/5
1/5
1/10
-1/2
x2
12/5
-1/5
2/5
-2/5
-1/5
1
x1
19/10
3/10
-1/10
1/10
-1/4
←
u2
-2/5
-1/5
-2/5
1
1/2
-5/2
b
x4
u2
F’
-6
-3/10
-1/2
x2
2
-2/5
1
x1
2
7/20
-1/4
x3
1
1/2
-5/2
X = (2, 2, 1, 0)
F = -F’ = 6 <shape id="_x0000_i1075" type="#_x0000_t75" o:ole=""><imagedata src=«7394.files/image093.wmz» o:><img width=«60» height=«59» src=«dopb38451.zip» v:shapes="_x0000_i1075">

2.2.3 Метод ветвей и границ
<lock v:ext=«edit» aspectratio=«t»><shape id="_x0000_s1032" type="#_x0000_t75" o:divferrelative=«f»><fill o:detectmouseclick=«t»><path o:extrusionok=«t» o:connecttype=«none»><lock v:ext=«edit» text=«t»><shapetype id="_x0000_t202" coordsize=«21600,21600» o:spt=«202» path=«m,l,21600r21600,l21600,xe»><path gradientshapeok=«t» o:connecttype=«rect»><img width=«348» height=«168» src=«dopb38452.zip» v:shapes="_x0000_s1031 _x0000_s1032 _x0000_s1033 _x0000_s1034 _x0000_s1035 _x0000_s1036 _x0000_s1037 _x0000_s1038 _x0000_s1039 _x0000_s1040 _x0000_s1041 _x0000_s1042">
b
x1
x2
x3
12/5
-1/5
2/5
x4
19/10
3/10
-1/10
F’
-31/5
-2/5
-1/5
Задача № 1
<shape id="_x0000_i1076" type="#_x0000_t75" o:ole=""><imagedata src=«7394.files/image096.wmz» o:><img width=«133» height=«169» src=«dopb38453.zip» v:shapes="_x0000_i1076">
<shape id="_x0000_i1077" type="#_x0000_t75" o:ole=""><imagedata src=«7394.files/image098.wmz» o:><img width=«141» height=«98» src=«dopb38454.zip» v:shapes="_x0000_i1077">
Приводим к каноническому виду:
x3, x4, x5 – базисные переменные, x1, x2 – свободные переменные
<shape id="_x0000_i1078" type="#_x0000_t75" o:ole=""><imagedata src=«7394.files/image100.wmz» o:><img width=«140» height=«99» src=«dopb38455.zip» v:shapes="_x0000_i1078">
↑
b
x1
x2
x3
11
2
3
11/2
-5
-1/2
-1/2
←
x4
10
4
1
5/2
5/2
1/4
1/4
x5
2
0
1
0
0
0
F’
0
2
1
-5
-1/2
-1/2
↑
b
x4
x2
x3
6
-1/2
5/2
12/5
-5
0
-5/2
x1
5/2
1/4
1/4
10
-1/2
0
-1/4
←
x5
2
0
1
2
2
0
1
F’
-5
-1/2
1/2
-1
0
-1/2
b
x4
x5
x3
1
-1/2
-5/2
x1
2
1/4
-1/4
x2
2
0
1
F’
-6
-1/2
-1/2
    продолжение
--PAGE_BREAK--