1
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
1
TRƯỜNG ĐẠI HỌC BÁCH KHOA TP. HCM
Khoa KTXD - Bộ môn KTTNN
Giảng viên: PGS. TS. NGUYỄN THỐNG
E-mail: nguyenthong@hcmut.edu.vn or nthong56@yahoo.fr
Web: http://www4.hcmut.edu.vn/~nguyenthong
Tél. (08) 38 691 592 - 098 99 66 719
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 2
NỘI DUNG MÔN HỌC
Chương 1: Giới thiệu PPĐL trong quản lý
Chương 2: Quy hoạch tuyến tính.
Chương 3: Cơ sở lý thuyết RQĐ
Chương 4: Bài toán vận tải.
Chương 5: Quản lý kho.
Chương 6: Ra quyết định đ mục tiêu.
Chương 7: Lý thuyết sắp hàng.
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 3
NỘI DUNG MÔN HỌC (tt)
Chương 8: Phân tích thành phần chính (PCA).
Chương 9: Kiểm định Cronbach’s Alpha &
KMO
Chương 10: Phương pháp AHP
Chương 11: Qui hoạch động
Chương 12: Hoạch định dự án
Chương 13: Xích Markov
Chương 14: Lý thuyết trò chơi.
Chương 15: Mô phỏng Monte Carlo.
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 4
TÀI LIỆU THAM KHẢO
1. Phương pháp định lượng trong quản lý.
NXB Trẻ 1999. Tác giả PGS. Dr. Nguyễn
Thống & Dr. Cao Hào Thi.
2. Phân tích số liệu và áp dụng vào dự báo.
NXB Thanh Niên 2000. Tác giả PGS. Dr.
Nguyễn Thống
3. Phần mềm: SPSS, QSB, Crystal Ball
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG
QUAÛN LYÙ
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 5
NỘI DUNG
- Giôùi thieäu vaán ñeà.
- Phöông phaùp ñoà thò.
- Phöông phaùp ñôn hình.
- Quy hoïach nguyeân.
- Quy hoïach nhò nguyeân.
- Giaûi baøi toaùn quy hoaïch vôùi Solver
(Excel).
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 6
GIỚI THIỆU
Quy hoạch tuyến tính (QHTT) là một kỹ
thuật toán học nhằm xác định gía trị của
các biến x1,x2,x3,...,xn (biến quyết định)
sao cho :
- Làm cực đại hoặc cực tiểu gía trị của hàm
mục tiêu (HMT) Z :
Z =f(x1,x2,x3,...,xn )
- Các biến x1,x2,x3,...,xn thỏa mãn các ràng
buộc :
Ri = ri(x1,x2,x3,...,xn )
PGS. Dr. Nguyễn Thống
2
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 7
GIỚI THIỆU
-Trong quy hoạch tuyến tính, hàm mục
tiêu f và các ràng buộc ri là những biểu
thức tuyến tính (bậc nhất) đối với các
biến quyết định x1,x2,x3,...,xn .
-Trong tröôøng hôïp khaùc quy hoïach phi
tuyeán.
PGS. Dr. Nguyễn Thống
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 8
CÁC BƯỚC CƠ BẢN BÀI TOÁN QHTT
Định nghĩa biến quyết định
Thiết lập HMT
Thiết lập các ràng buộc với
biến quyết định.
Giải để xác định biến quyết
định
PGS. Dr. Nguyễn Thống
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 9
Ví dụ: Một nhà sản xuất gỗ sản xuất hai loại
bàn : bàn tròn (x1) và bàn chữ nhật (x2).
Mỗi bàn tròn cần:
-2,5 giờ để lắp ghép
-3 giờ để đánh bóng
-1 giờ để vào thùng.
Một bàn chữ nhật cần :
-1 giờ để lắp ghép
-3 giờ để đánh bóng
-2 giờ để vào thùng.
PGS. Dr. Nguyễn Thống
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 10
Trong một tuần, do giới hạn về mặt điều
động nhân sự, xưởng chỉ có thể bố trí:
-20 giờ để lắp ghép
-30 giờ để đánh bóng
-16 giờ để vào thùng.
Lợi nhuận cho mỗi bàn tròn là 3000$ và
4000$ cho mỗi bàn chữ nhật.
Tìm phương án sản xuất tối ưu (xác định
x1, x2) để mang về cho nhà sản xuất lợi
nhuận cao nhất.
PGS. Dr. Nguyễn Thống
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 11
Gọi x1 và x2 là số lượng lần lượt của bàn tròn
và bàn chữ nhật (biến quyết định).
Hàm mục tiêu : Max F = 1000( 3x1 + 4x2 ) [1]
Các ràng buộc :
•Ràng buộc về thời gian ghép thô :
2,5x1 + x2 <=20 [2]
•Ràng buộc về thời gian đánh bóng :
3x1 + 3x2 <=30 [3]
•Ràng buộc về thời gian đóng thùng :
x1 + 2x2 <=16 [4]
Về ý nghĩa vật lý ta phải có : x1,x2 >=0 [5]
PGS. Dr. Nguyễn Thống
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 12
•Ví dụ: Một nông dân mong muốn đàn cừu
của nông trại tiêu thụ các loại sản phẩm
thức ăn có các loại chất dinh dưỡng là
A,B,C với khẩu phần hàng ngày ít nhất,
nhưng phải đảm bảo về mặt dinh dưỡng
tối thiểu yêu cầu theo lời khuyên của nhà
chuyên môn.
•Nhu cầu tối thiểu hàng ngày về chất dinh
dưỡng A,B,C theo thứ tự là 14,12,18 đơn
vị.
PGS. Dr. Nguyễn Thống
3
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 13
Trên thị trường có loại sản phẩm y1 và y2.
•Sản phẩm y1 cung cấp :
2 đơn vị A và 1 đơn vị B và 1 đơn vị C.
•Sản phẩm y2 cung cấp :
1 đơn vị A và 1 đơn vị B và 3 đơn vị C.
Biết rằng giá đơn vị sản phẩm y1, y2 lần lượt
là 2000$ và 4000$.
Xác định số lượng y1 và y2 để chi phí ít nhất.
PGS. Dr. Nguyễn Thống
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 14
Gọi y1 và y2 là số lượng sản phẩm được mua
(là biến quyết định).
Hàm mục tiêu : Min F = 1000(2y1 + 4y2)
Ràng buộc:
- Về chất dinh dưỡng loại A :
2y1 + y2>=14
- Về chất dinh dưỡng loại B :
y1 + y2 >=12
- Về chất dinh dưỡng loại C :
y1 + 3y2 >=18
- Về ý nghĩa vật lý ta phải có : y1,y2 >=0
PGS. Dr. Nguyễn Thống
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 15
PHƯƠNG PHÁP GIẢI BÀI TOÁN
QHTT
Phương pháp đồ thị (chỉ có 2
biến quyết định).
Phương pháp đơn hình
(phương pháp tổng quát có số
lượng biến quyết định bất kỳ).
PGS. Dr. Nguyễn Thống
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 16
PHƯƠNG PHÁP ĐỒ THỊ
(CHỈ CÓ 2 BIẾN QUYẾT ĐỊNH)
Bài toán Max
Bài toán Min
PGS. Dr. Nguyễn Thống
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 17
BÀI TOÁN MAX
Giải hệ bất phương trình ràng
buộc bằng đồ thị Xác định
miền nghiệm có thể,
Vẽ họ đường thẳng biểu thị
HMT.
Xác định nghiệm.
PGS. Dr. Nguyễn Thống
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 18
Hàm mục tiêu :
Max F = 1000( 3x1 + 4x2 ) [1]
Các ràng buộc :
2,5x1 + x2 <=20 [2]
3x1 + 3x2 <=30 [3]
x1 + 2x2 <=16 [4]
Về ý nghĩa vật lý ta phải có : x1,x2 >=0
PGS. Dr. Nguyễn Thống
4
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 19
PHƯƠNG PHÁP ĐỒ THỊ BÀI TOÁN MAX
Duøng trong tröôøng hôïp chæ coù 2 bieán quyeát ñònh:
PGS. Dr. Nguyễn Thống
O
y2
8 16
10
8
10
20
y1
F=haèng soá
D C
B A
C(4,6) Fmax =36000
Vuøng nghieäm coù theå
[2]
[3]
[4]
[1]
4
6
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 20
BÀI TOÁN MIN
PGS. Dr. Nguyễn Thống
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 21
Hàm mục tiêu :
Min F = 1000(2y1 + 4y2) [1]
Ràng buộc:
2y1 + y2>=14 [2]
y1 + y2 >=12 [3]
y1 + 3y2 >=18 [4]
PGS. Dr. Nguyễn Thống
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 22
PHƯƠNG PHÁP ĐỒ THỊ BÀI TOÁN MIN
PGS. Dr. Nguyễn Thống
O
y2
7 18
12
6
12
14
y1
F=haèng soá
D
C
B
A
B(9,3) Fmin =44000
Vuøng nghieäm coù theå
[2]
[3]
[4]
[1]
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 23
Nhaän xeùt:
-Nghieäm luoân luoân naèm treân ñöôøng “ranh
giôùi” (ABCD).
-Seõ coù nhieàu nghieäm trong tröôøng hôïp
ñöôøng thaúng bieåu thò HMT gaëp “ña giaùc
nghieäm” treân 1 ñoïan thaúng treân bieân.
-Ñöôøng thaúng nghieäm bieåu thò giaù trò HMT
laø haèng soá.
PGS. Dr. Nguyễn Thống
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 24
Baøi taäp 1: Moät xöôûng saûn xuaát hai loaïi theùp
ñaëc bieät g1 vaø g2. Loaïi g1 caàn 2h ñeå naáu
chaûy, 4h ñeå luyeän, 10h ñeå caét ñònh hình.
Loaïi g2 caàn 5h ñeå naáu chaûy, 1h ñeå luyeän,
5h ñeå caét ñònh hình.
Lôïi nhuaän mang ñeán bôûi loaïi g1 laø 24$ vaø
loaïi g2 laø 8$. Khaû naêng cuûa xöôûng coù theå
boá trí 40h ñeå naáu chaûy, 20h ñeå luyeän vaø
60h ñeå caét ñònh hình.
Xaùc ñònh phöông aùn saûn xuaát ñeå nhaø saûn
xuaát coù lôïi nhuaän cao nhaát.
Ñaùp soá : g1 = 4 , g2 = 4 vaø Fmax = 128$
PGS. Dr. Nguyễn Thống
5
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 25
Baøi taäp 2: Moät nhaø saûn xuaát hai loaïi ñaù xaây döïng :
loaïi lôùn (x1) , loaïi beù (x2). Loaïi x1 caàn 2h ñeå
nghieàn, 5h ñeå phaân loaïi, 8h ñeå laøm saïch. Loaïi x2
caàn 6h ñeå nghieàn, 3h ñeå phaân loaïi, 2h ñeå laøm
saïch. Lôïi nhuaän mang laïi töø loaïi x1 vaø x2 laàn löôït
laø 40$ vaø 50$. Khaû naêng thieát bò cho pheùp söû duïng
trong moät tuaàn laø : 36h ñeå nghieàn, 30h ñeå phaân
loaïi vaø 40h ñeå laøm saïch.
a. Xaùc ñònh phöông aùn saûn xuaát x1, x2 ñeå nhaø saûn
xuaát coù lôïi nhuaän cao nhaát.
b. Xaùc ñònh lôøi giaûi neáu lôïi nhuaän x2 laø 160$.
Ñaùp soá : x1 = 3 , x2 = 5 vaø Fmax = 370$
PGS. Dr. Nguyễn Thống
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 26
Baøi taäp 3: Moät nhaø laøm vöôøn muoán taïo moät
hoãn hôïp phaân boùn töø hai loaïi saûn phaåm cô
baûn, sao cho toái thieåu nhaän ñöôïc 15 ñôn vò
potasse, 20 ñôn vò nitrate vaø 3 ñôn vò
phosphate. Loaïi x1 coù giaù laø 120$ cung caáp
ñöôïc 3 ñôn vò potasse, 1 ñôn vò nitrate, 3 ñôn
vò phosphate. Loaïi x2 coù giaù laø 60$ cung caáp
ñöôïc 1 ñôn vò potasse, 5 ñôn vò nitrate, 2 ñôn
vò phosphate. Xaùc ñònh phöông aùn choïn löïa
ñeå cöïc tieåu hoùa chi phí cuûa nhaø laøm vöôøn.
Ñaùp soá : x1 = 2 , x2 = 9 vaø Fmin = 780$
PGS. Dr. Nguyễn Thống
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 27
Baøi taäp 4: Moät ngheä só raát quan taâm ñeán söùc khoeû
mong muoán moãi ngaøy coù ñöôïc toái thieåu 36 ñôn vò
vitamin A, 28 ñôn vò vitamin C, vaø 32 ñôn vò
vitamin D. Loaïi thuoác thöù 1 giaù laø 3$US coù theå
cung caáp 2 ñôn vò vitamin A vaø 2 ñôn vò vitamin C
vaø 8 ñôn vò vitamin D. Loaïi thuoác thöù 2 giaù laø
4$US coù theå cung caáp 3 ñôn vò vitamin A, 2 ñôn vò
vitamin C vaø 2 ñôn vò vitamin D. Xaùc ñònh löôïng
thuoác söû duïng ñeå chi phí cuûa ngheä só naøy laø beù
nhaát.
Ñaùp soá : y1 = 6 , y2 = 8 vaø Fmin = 50 $US
PGS. Dr. Nguyễn Thống
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 28
Baøi taäp 5: Tìm lôøi giaûi toái öu cho baøi toaùn sau:
Haøm muïc tieâu : Max F = 20x1+10x2
Caùc raøng buoäc : 4x1+3x2 <=48
3x1+5x2 <=60
x1 <=9
x1, x2 >=0
Ñaùp soá : x1 = 9, x2 = 4 vaø Fmax = 220
Baøi taäp 6: Haøm muïc tieâu : Min F = 30x1+50x2
Caùc raøng buoäc : 6x1+2x2 >=3
3x1+2x2 >=24
5x1+10x2 >=60
x1, x2 >=0
Ñaùp soá : x1= 6 , x2=3 vaø Fmin = 330
PGS. Dr. Nguyễn Thống
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 29
PHƯƠNG PHÁP
ĐƠN HÌNH
(Phương pháp tổng quát)
PGS. Dr. Nguyễn Thống
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 30
NGUYÊN TẮC
Thử và so sánh kết quả của tất
cả các điểm nằm trên “ranh
giới” của VÙNG ĐA GIÁC
NGHIỆM.
PGS. Dr. Nguyễn Thống