1
1

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 1. MT S BÀI TOÁN THC T
BÀI 2. CÁC KHÁI NIM C BN
BÀI 3. CÁC DNG C BIT CA BTQHTT
BÀI 4. GII BTQHTT BNG PP HÌNH HC
BÀI 5. GII BTQHTT BNG PP N HÌNH
2

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 1. MT S BÀI TOÁN THC T
1. Bài toán cái túi
max)(
1



n
i
ii
xcxf









n
i
ii
),,1(0
1
max)(
1



n
i
ii
xcxf









nguyennix
bxa
i
n
i
ii
),,1(0

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 1. MT S BÀI TOÁN THC T
1. Bài toán cái túi
Vd: Mt cái gi trái cây chati đa 15 kg.
120650u đ
80450Bi
551200Dahu
Giá bán (100đ/qu)Khilng (g)Loi








nguyenxxx
xxx
xxxxf
,0,,
1565,045,02,1
(min)max1208055)(
321
321
321













nguyenxxx
xxx
xxxxf
,0,,
1565,045,02,1
(min)max1208055)(
321
321
321
4

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 1. MT S BÀI TOÁN THC T
2. Bài toán lpk hoch snxutti u

Mô hình toán nh sau:
3
5

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 1. MT S BÀI TOÁN THC T
2. Bài toán lpk hoch snxutti u
max


n
i
ii
xcR









),1(0
),1(
1
nix
mjbxa
i
n
i
jiij
max
1



n
i









),1(0
),1(
1
nix
mjbxa
i
n
i
jiij
6

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 1. MT S BÀI TOÁN THC T
2. Bài toán lpk hoch snxutti u
3,41,42,81,51,2Giá bán (triu đng/cái)
12284326800 siDây M4
241218141587500 cáiCúc M3
2,41,81,51,21,54800 m
ViM2
2,82,23,22,52,215400 m
ViM1
SP A5SP A4SP A3SP A2SP A1














5,1,0,0,,,,
26800122843
875002412181415
48004,28,15,12,15,1
154008,22,22,35,22,2
max4,34,18,25,12,1)(
54321
54321
54321
54321
54321
54321
inguyenxnguyenxxxxx
xxxxx
xxxxx
xxxxx
xxxxx

54321
54321
54321
54321
inguyenxnguyenxxxxx
xxxxx
xxxxx
xxxxx
xxxxx
xxxxxxf
i






























5,1,0,0,,,,
26800122843
875002412181415
48004,28,15,12,15,1
154008,22,22,35,22,2
max4,34,18,25,12,1)(
54321
54321
54321
54321
54321
54321
inguyenxnguyenxxxxx
xxxxx
xxxxx
xxxxx
xxxxx
xxxxxxf
i
8

),1(0
),1(
1
mix
njbxa
i
j
m
i
iij
min
1



m
i
ii
xcC









),1(0
),1(

njbxa
i
j
m
i
iij
min
1



m
i
ii
xcC









),1(0
),1(
1
mix
njbxa
i

i
iij
10

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 1. MT S BÀI TOÁN THC T
3. BT xác đnh khuphnthc nti u
Ví d:  nuôi 1 loi gia súc, ngitacóth s dng
4 loithc n F1, F2, F3 & F4 vihàmlng (%) các
chtdinhdng N1, N2 & N3 trong tng loinh sau:
37282632Giá mua (1000đ/kg)
950262025N3
1200450181815N2
80020302420N1
MaxMinF4F3F2F1
Nhu cu (g)Loithc n
Chtdinhdng
6
11

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH
BÀI 1. MT S BÀI TOÁN THC T
3. BT xác đnh khuphnthc nti u





















4,10
95,026,020,025,0
45,018,018,015,0
20,118,018,015,0
80,020,030,024,020,0
min37282632)(
431
421
421
4321
4321
ix
xxx
xxx
xxx
xxxx
xxxxxf

xxx
xxx
xxxx
xxxxxf
i
















4,10
95,026,020,025,0
45,018,018,015,0
20,118,018,015,0
80,020,030,024,020,0
min37282632)(
431
421
421



















),1,,1(,0
11
1
1
mjnix
xx
bx
ax
ij
n
i
ij
















),1,,1(,0
11
1
1
mjnix
xx
bx
ax
ij
n
i
ij
m
j
ij













),1,,1(,0
11
1
1
mjnix
xx
bx
ax
ij
n
i
ij
m
j
ij
j
n
i










),1,,1(,0
11
1
1
mjnix
xx
bx
ax
ij
n
i
ij
m
j
ij
j
n
i
ij
i
m







),1,,1(,0
11
1
1
mjnix
xx
bx
ax
ij
n
i
ij
m
j
ij
j
n
i
ij
i
m
j
ij
mi




),1,,1(,0
11
1
1
mjnix
xx
bx
ax
ij
n
i
ij
m
j
ij
j
n
i
ij
i
m
j
ij
7
13

CHNG I- BÀI TOÁN QUY HOCH TUYN TÍNH

c) Cho doanh nghipA vayvi lãi sut 14%nm.
d) ut vào d án X vi lãi sutk vng là 16%/nm.
Bitrng:
1) S tingititkimcók h
nítnhtphigp đôi s tingikok hn.
2) S tin dùng cho vay không đc quá 320 triu đng.
3) S tin đut vào d án X không quá 75% s tingingânhàngnhng
philnhns tin cho doanh nghipA vay.
Hãy lpmôhìnhtoánxácđnh các khon đut sao cho s tinlãithuđc
là lnnht.