QUY HOẠCH TUYẾN TÍNH 02/09/2012
Chuongnn-hui.blogspot.com 1
: Ths
1
tín : 2 (30 .
tiên : xong trình
toán C2.
: Trang cho sinh viên
các mô hình trong
kinh .
:
các khái bài toán quy
tính, bài toán bài toán .
các pháp toán:
pháp hình, hình
pháp .
2
:
:
4
5
j
(j=1,2, ,n)
S
1
S
2
S
n
nguyên
N
1
a
11
a
12
a
1n
b
1
N
2
a
21
a
22
j
j
(j=1,2, ,n)
j
N
1
dùng cho
a
11
x
1
+ a
12
x
2
a
1n
x
n
1
N
2
n
b
m lãi là:
f = f(x
1
, x
2
, , x
n
) = c
1
x
1
+ c
2
x
2
c
n
x
n
8
2
a
1n
x
n
b
1
.
a
21
x
1
+ a
22
x
2
a
2n
x
n
b
2
a
m1
x
1
+ a
i
mà phân S
j
có
lý cùng vào các
phân là: a
ij
+ N
i
lý theo
lao là: b
i
xí hoàn thành
lao là .
10
Phân
S
1
S
2
N
m
a
m1
a
m2
a
mn
b
m
11
j
j
(j=1,2, ,n). x
j
1
b
2
N
m
a
m1
x
1
+ a
m2
x
2
a
mn
x
n
b
m là:
f = f(x
1
, x
2
, , x
n
a
11
x
1
+ a
12
x
2
a
1n
x
n
b
1
.
a
21
x
1
+ a
22
x
2
a
2n
x
n
b
2
Xí hàng hoá m phát
P
i
(i=1,2,,m) n thu T
j
(j=1,2,,n).
+ hàng có phát P
i
là: a
i
+ hàng thu T
j
là: b
j
+ Phí hàng P
i
T
j
là: c
ij
hàng có các phát
hàng các thu.
Hãy hàng hoá chi
phí là và yêu thu phát.
14
1nP
2
:a
2
c
21c
22
c
2n
P
m
:a
m
c
m1c
in
= a
i
j
là:
x
1j
+ x
2j
mj
= b
j
:
f = f(x
11
, x
12
mn
) = c
11
x
11
+ c
mn
x
mn
x
11
+ x
12
x
1n
= a
1
x
m1
+ x
m2
x
mn
= a
m
x
11
+ x
21
x
xí
lãi B lãi C lãi
.
QUY HOẠCH TUYẾN TÍNH 02/09/2012
Chuongnn-hui.blogspot.com 4
là: D1D2 và
D3D1D2
D3D1
D2 D3
cho
lý
III
AB
C, phân AB,
C, phân A, 1
C.
Xí
.
3
3
3
.
f(x) = c
1
x
1
+ c
2
x
2
n
x
n
max(min) (1)
a
i1
x
1
+ a
i2
x
2
a
in
x
n
b
i
, i I
1
x
n
= b
i
, i I
3
(4)
x
j
0, j J
1
(5) .
x
j
0, j J
2
(6) .
x
j
, j J
3
(7) .
1
I
2
I
3
2x
6
max
x
1
+ 2x
2
x
4
+ x
5
8
x
1
3x
3
x
4
+ 3x
6
2
2x
1
+ x
2
+ x
3
x
4
= 5
x
5
: hàm f(x) = c
1
x
1
+ c
2
x
2
n
x
n
1
, x
2
n
+ a
i2
x
2
in
x
n
= b
i
, i m
x
j
0, j .
hay
f(x) = c
j
x
j
max(min)
a
ij
x
j
= b
i
x
+ a
ij
x
j
b
i
thành a
ij
x
j
x
n+i
= b
i
sung thêm x
n+i
0.
j
0 thành
j
0
j
= x
j
+
j
thành
2
+ x
3
x
4
8
x
1
x
3
+ x
4
= 5
x
1
2x
2
x
3
+ 3x
4
7
x
1
, x
3
0
x
2
1
x
3
+ x
8
x
9
= 5
x
1
x
3
x
6
+ 2x
7
+ 3x
8
3x
9
= 7
x
j
+ f(x) = 2x
1
x
2
+ 2x
4
12
x
2
, x
4
0
x
1
0
x
3
f(x) = x
2
3x
4
2x
7
+ x
8
x
9
min
2x
2
x
4
x
x
9
= 12
x
j
tìm min.
biên
Xét bài toán
f(x) = c
j
x
j
in
a
ij
x
j
= b
i
x
j
n .
liên x
j
các án biên bài toán quy
tính là .
Ví :
+ Xét bài toán
f(x) = 4x
1
+
x
2
+ x
3
min
x
1
+2x
2
x
3
= 5
x
1
x
2
+ 2x
3
+ x
2
+ x
3
= 4
x
1
x
2
= 0
x
j
0, j=1,2,3
nào sau là án biên không suy
: x
0
= (1, 1, 2), x
1
= (2, 2, 0), x
2
= (0, 0, 4)?
: x
1
= (2, 2, 0)
Cách
3
+ x
4
= 5
x
2
x
3
+ 2x
4
= 1
x
j
0, j=1,2,3,4
+ f(x) = 2x
1
x
3
+ 2x
4
min
x
1
+ x
2
+ x
),
(4, 0, 6, 0), (7, 3, 0, 0)
39
Do thành án
biên không suy là m nên suy ra thành
0 là n m.
suy ra tìm án biên ta có
cho n m thành 0 tính giá
m thành còn cách m
trình m .
40
Tìm các bài toán
+ f(x) = x
1
+
6x
3
5x
4
min
x
1
+ 2x
3
+ x
5
= 8
x
2
+ x
4
x
5
= 4
x
3
+ x
4
+ x
5
= 6
x
j
0,
(5,
, 0, 0), (0,
,
+ và bài toán quy
tính chính có án là nó có
án khác và hàm tiêu .
+ bài toán quy tính chính
có án thì nó có ít
án biên là án .
ý: ta có bài toán quy
tính chính nó có
án cách tìm các án
biên bài toán, án là án
mà giá hàm tiêu (hay .
43
toán
+ f(x) = x
1
+
6x
3
5x
4
min
x
1
+ 2x
3
+ 3x
5
= 8
x
2
+ x
4
x
5
= 4
x
3
+ x
4
+ x
5
= 6
x
j
0,
x* = (0,
, 0,
),
f
min
+ 2y
6
x 0, y 0
f
min
45
+ f(x) = x
+ 3y
max
x
+ 2y
6
2x
+ y
10
4
x 0, y 0
f
max
x
j
48
QUY HOẠCH TUYẾN TÍNH 02/09/2012
Chuongnn-hui.blogspot.com 9
1
, x
2
m
i
j
= (x
1j
, x
2j
, x
mj
j
i
j
.
{A
i
}
ij
= a
ij
.
50
+ Xét bài toán
f(x) = x
1
+ 6x
2
+ 9x
3
in
x
1
+ 2x
3
= 6
x
2
+ x
3
= 8
x
j
0, j = 1, 2, 3.
không?
min
biên
j sao cho
j
> 0 và x
ij
> 0 i
thì
53
hình
Xét bài toán
f(x) = c
j
x
j
in
a
ij
x
j
= b
i
án
x
1
x
2
x
n
c
1
c
2
c
n
x
1
c
1
x
m
c
m
x
m1
x
m2
x
mn
f(x
0
)
1
2
n
55
56
1
57
3
+ 2x
4
+ 4x
5
+ 3x
6
= 9
x
j
0, j = 1,
(0, 8, 0, 3, 0, 1).
f
min
58
+ f(x) =
1
2
+ x
3
x
4
min
x
1
i
ta
: bài toán
+ f(x) =
1
+ x
2
+ 3x
3
4
min
x
1
+ 2x
2
x
3
+ x
4
= 2
2x
1
+ 3x
3
4
min
x
1
+
x
4
= 3
x
2
x
4
= 2
x
3
x
4
= 5
= 11
3x
2
+ x
3
+ 14x
4
= 16
x
j
0, j = 1,2,3,4.
62
f(x) = 3x
1
2
3
+ 6x
4
in
x
1
+
x
j
in
a
ij
x
j
= b
i
, i = 1, 2, m
x
j
i
n+i
g = c
j
x
j
+ Mx
n+1
+ Mx
n+2
j
0, j = n+m
0
t = (x
n+1
n+m
) thì bài toán chính không có
.
65
+ k
+
j
x
j
có
= AM + B,
j
=
j
M+
A, B, , trình bày trên 2 dòng.
66
QUY HOẠCH TUYẾN TÍNH 02/09/2012
Chuongnn-hui.blogspot.com 12
Ví : bài toán
+ f(x) =
1
+ x
2
+ 3x
3
4
min
x
1
+ 2x
2
x
3
+ x
4
= 2
1
2
3
+ 6x
4
in
x
1
+ x
2
+ x
3
+ 13x
4
= 14
2x
1
+ x
2
+ 14x
4
= 11
3x
2
+ x
3
+ 14x
4
+ x
3
ax
x
1
5x
2
+ x
3
= 6
2x
1
+ 2x
2
+ x
4
= 7
x
1
+ 2x
2
+ x
5
= 5
x
j
0, j = 1,2,3,4,5.
69
+ x
4
= 7
3x
1
2
+ 8x
3
+ x
5
= 10
4x
1
2
+ x
6
= 12
x
j
0, j =
: (5, 4, 0, 0, 11, 0).
f
max
= 11.
70
Cell Reference:
có
74
75
Keep Solver Solution:
tình
xem
Có
Limits.
2
in
x
n
b
i
, i I
1
(1)
a
i1
x
1
+ a
i2
x
2
in
x
n
b
i
, i I
2
(2)
a
3
(6)
78
QUY HOẠCH TUYẾN TÍNH 02/09/2012
Chuongnn-hui.blogspot.com 14
Bài toán bài toán (P) là bài toán (Q):
g(y) = b
1
y
1
+ b
2
y
2
b
m
y
m
min(max)
a
1j
y
1
+ a
2j
y
2
y
1
+ a
2j
y
2
mj
y
m
= c
j
, j J
3
y
i
0, i I
1
y
i
0, i I
2
y
i
, i I
3
2x
1
x
3
+ 3x
4
+ 2x
5
5
x
1
+ 3x
2
2x
4
x
5
= 6
3x
1
+ 2x
2
x
3
+ x
4
3
x
1
, x
4
2
y
1
+ 3y
3
+ 2y
4
= 1
2y
1
y
2
y
4
y
1
+ 3y
2
2y
3
+ y
4
= 1
y
1
+ 2y
2
y
j
0 J
1
a
ij
y
i
c
j
x
j
0 J
2
a
ij
y
i
c
j
x
j
J
3
a
ij
y
i
= c
I
3
y
i
82
+ f(x) = x
1
+ x
2
+ x
4
3x
5
max
x
1
+ 2x
2
2x
4
+ x
5
= 4
x
1
+ 3x
, x
5
0
x
3
, x
4
0
x
1
83
Bài toán (Q):
g(y) = 4y
1
+ 7y
2
+ 6y
3
+ 3y
4
min
y
1
y
2
+ 2y
3
+ 3y
3
y
4
3
y
2
0
y
4
0
y
1
,y
3
84
QUY HOẠCH TUYẾN TÍNH 02/09/2012
Chuongnn-hui.blogspot.com 15
Xét bài toán quy tính chính
tìm min.
lý 1 )
Cho x, y theo là án bài toán
và ta có f(x) g(y).
ý: lý ta có án bài toán
và theo là x, y mà f(x) = g(y)
thì x, y là án bài toán
b
x
1
+ x
2
+ 4x
4
= 6
2x
2
+ x
3
+ 5x
4
= 8
x
j
0, j=1,2,3,4
), f
min
= 6.
89
: án bài toán là
y* = (1,
) và g
max
2x
1
+ 5x
2
+ x
3
+ x
5
= 8
x
j
0, j=1,2,3,4,5
có án là x* = (0, 1, 0, 2, 3), f
min
= 6.
Tìm án bài toán .
90
QUY HOẠCH TUYẾN TÍNH 02/09/2012
Chuongnn-hui.blogspot.com 16
: án bài toán là
y* = (5, 1, 1) và g
max
= 6 = f
min
Dùng hình bài toán
+ bài toán
f(x) = x
y* = (1,
) và g
max
= 6 = f
min
+ bài toán
f(x) = x
1
+ x
2
+ x
3
+ x
4
+ x
5
min
3x
1
+ x
2
+ x
3
= 1
5x
1
+ x
2
các
x
j
hình tiên
thêm c
j
.
Ta các bài toán có ma
b
i
0 bài toán có ma
. các bài toán có ma
có b
i
< 0 ta áp
pháp hình sau
93
+ Tìm án
+ hình . các
trong án không âm thì ta có
án .
+ Dòng quay r là dòng có âm
trong án.
+ quay là s
trong các
6
4x
1
+ x
2
+ x
3
+ x
4
9
x
j
0, j=1,2,3,4.
(2, 0, 0, 1), giá
f
min
= 6.
95
+ f(x) = 15x
1
+ 12x
2
+ 10x
3
min
3x
1
+ 4x
phát) P
i
, i=1,2,,m n tiêu thu)
T
j
, j=1,2,,n. hàng có kho P
i
là a
i
,
i=1,2,,m. hàng tiêu T
j
là
b
j
, j=1,2,,n. Chi phí hàng
kho P
i
tiêu T
j
là c
ij
, i=1,2,m,
j=1,2,,n. Cho hàng các kho
hàng tiêu .
Hãy hàng hoá sao cho
chi phí là và yêu thu
phát.
98
= b
j
ý: Bài toán cân thu phát luôn có
án và ta có
pháp hình.
99
Thu
P
hát
b
1
b
2
b
n
a
1
c
11
x
11
c
12
x
x
m1
c
m2
x
m2
c
mn
x
mn
100
Xét m n.
+ Ô là ô (i, j) trên dòng i, j mà
hàng x
ij
> 0, ô là ô (i, j) mà x
ij
= 0.
+ Dây là các ô sao cho
không có quá hai ô liên trên cùng
dòng .
sung thêm ô có ít chu
trình.
i
T
j
.
+ án biên là án có ô
không thành chu trình là m + n 1,
ô này m + n 1 ta có án
biên không suy ta có án
biên suy . suy ta có
sung thêm 0 có m + n 1 ô
không thành chu trình.
103
+ Tìm
+ Phân
hàng.
.
104
:
+
30
60
955
12236
253015200
45304035
60
50
40
45
157280
574
f = 630
108
QUY HOẠCH TUYẾN TÍNH 02/09/2012
Chuongnn-hui.blogspot.com 19
+ 130
140
120
160
180
2018
f = 12870
109
Tìm án biên không suy ban .
Áp pháp hay Vogel.
giá án có toán quy 0
phí ô
+ Tìm u
i
và v
án .
Xây án
+ ô (r, s) là ô sao cho c
rs
< 0, bé tìm
chu trình U qua ô (r, s) và T các ô .
+ +/ các ô trong U, là ô (r, s),
phân chia U = U
+
U
, U
+
là các ô
mang + và U
là các ô mang .
111
+ h = min{x
ij
(i, j) U
}, ma
án (x
ij
) thành ma án
(x
ij
45
157280
574955
min
= 555
113
+
+ án suy ta sung thêm các
0 có m+n1 ô không thành chu trình. 130
140
120
160
180
201822
f
min
= 12690
114
QUY HOẠCH TUYẾN TÍNH 02/09/2012
Chuongnn-hui.blogspot.com 20
+ a
i
< b
j
hay cung ta
12755
911101550
8714
hay cung ta
sung thu T
n+1
b
n+1
= a
i
b
j
và
c
in+1
= 0 các ô (i, n+ 1), i = 1,,m.
Ví : bài toán
100
65
95
80
752
= 875
116
+ có ô ta ô và vào
phí M và hành làm bình .
án không có giá trong ô .
Ví : bài toán
100
65
95
40
80
651110
70
f
min
= 2065
117
bài toán
tìm án biên ta
tiên cho các ô có phí Vogel ta
tiên cho các ô có phí trên dòng
hay có phí hai ô có
phí hành làm bình .
án là c
ij
0 i, j
sau khi quy 0 phí ô . án
ta sung ô (i, j) mà c
ij
> 0
án bình .
118
10190
40253530
121
Copyright: Tài liệu đại học ©