Phương pháp định lượng trong quản lý - Chuong 2: Quy hoạch tuyến tính
Đị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
Bạn đang xem nội dung tài liệu Phương pháp định lượng trong quản lý - Chuong 2: Quy hoạch tuyến tính, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
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 KH A 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:
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
y
2
8 16 10
8
10
20
y
1
F=haèng soá
D
C
B
A
C(4,6) F
max
=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
y
2
7 18 12
6
12
14
y
1
F=haèng soá
D
C
B
A
B(9,3) F
min
=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ø F
max
= 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ø F
max
= 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ø F
min
= 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ø F
min
= 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ø F
max
= 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ø F
min
= 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
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 31
PHƯƠNG PHÁP
ĐƠN HÌNH
Bài toán Max HMT
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 32
PHÖÔNG PHAÙP ÑÔN HÌNH
Phöông phaùp ñôn hình cho pheùp xaùc ñònh lôøi giaûi
cô baûn cuûa moät heä thoáng phöông trình vaø kieåm
tra xem lôøi giaûi ñoù coù toái öu hay chöa.
Ñeå coù lôøi giaûi cô baûn, phaûi gaùn cho (n-m) bieán giaù
trò baèng khoâng vaø giaûi heä m phöông trình vaø m
aån soá coøn laïi. Phöông phaùp naày cho pheùp
chuyeån töø lôøi giaûi cô baûn naøy sang moät lôøi giaûi
cô baûn khaùc, toát hôn lôøi giaûi tröôùc, cho ñeán khi
ñaït ñeán lôøi giaûi toái öu.
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 33
PHÖÔNG PHAÙP ÑÔN HÌNH
Nhöõng bieán coù giaù trò laø 0 ôû moãi
böôùc laëp thì khoâng keå trong lôøi
giaûi cô baûn. Nhöõng bieán khoâng
ñöôïc laáy giaù trò 0 seõ ñöôïc xem ôû
trong lôøi giaûi cô baûn cuûa baøi toaù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 34
NGUYÊN LÝ ƯU TIÊN CHỌN
TỔ HỢP NGHIỆM
Sẽ ưu tiên đưa nghiệm Xi nào
có hệ số ai LỚN !
PGS. Dr. Nguyễn Thống
MaxXa...XaXaF nn2211
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 35
Ví duï: Söû duïng phöông phaùp ñôn hình ñeå
giaûi.
Haøm muïc tieâu : Max F = 5x1 + 3x2 [1]
Vôùi caùc raøng buoäc :
6x1 + 2x2 <=36 [2]
5x1 + 5x2 <=40 [3]
2x1 + 4x2 <=38 [4]
vôùi x1 , x2>=0
(Ghi chuù: trong tröôøng hôïp naøy duøng p/p ñoà thò)
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 36
1. Laäp baûng ban ñaàu cho phöông phaùp ñôn hình.
a.Theâm caùc bieán buø s1,s2,s3>0 ñeå bieán ñoåi caùc baát
phöông trình treân thaønh phöông trình :
6x1 + 2x2 + s1 = 36 [2]
5x1 + 5x2 + s2 = 40 [3]
2x1 + 4x2 + s3 = 28 [4]
b. Phöông trình treân döôùi daïng ma traän :
PGS. Dr. Nguyễn Thống
6 2 1 0 0
5 5 0 1 0
2 4 0 0 1
36
40
28
1
2
1
2
3
*
x
x
s
s
s
7
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 37
HÀM MỤC TIÊU
MỘT CÁCH “HÌNH THỨC” SAU KHI BỔ
SUNG CÁC BIẾN “BÙ” THÌ HMT SẼ
BIẾN THÀNH:
Max F = 5x1 + 3x2 +0.s1+0.s2+0.s3
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 38
c. Baûng ban ñaàu cuûa phöông phaùp ñôn hình :
Nghieäm: x1=0, x2=0, s1=36,s2=40, s3=28, HMT=0
!!! Treân 1 coät, neáu heä soá khoâng coù daïng (0..,1,..0,..)
Bieán töông öùng =0
PGS. Dr. Nguyễn Thống
x1 x2 s1 s2 s3 Haèng soá
6 2 1 0 0 36
5 5 0 1 0 40
2 4 0 0 1 28
-5 -3 0 0 0 0
Heä soá HMT ñoåi daáu – Haøng tham khaûo
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 39
Choïn giaù trò “xoay” vaø thay ñoåi heä cô baûn.
Ñeå ñaït ñeán giaù trò toái öu cuûa haøm muïc tieâu,
chuùng ta xem xeùt moät lôøi giaûi cô baûn môùi.
Ñeå ñaït ñöôïc vaán ñeà ñoù, chuùng ta phaûi ñöa
vaøo moät bieán môùi trong lôøi giaûi cô baûn vaø
ñoàng thôøi phaûi loaïi boû moät trong nhöõng
bieán trong lôøi giaûi cuõ.
Ta goïi söï thay ñoåi heä cô baûn laø quaù trình
choïn bieán môùi ñeå ñöa vaøo vaø ñoàng thôøi
choïn bieán cuõ ñeå loaïi ra.
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 40
Nguyeân taéc thay ñoåi nhö sau :
a. Giaù trò tham khaûo aâm coù giaù trò tuyeät ñoái lôùn
nhaát xaùc ñònh bieán môùi ñöa vaøo lôøi giaûi cô baûn.
Trong tröôøng hôïp naøy, ñoù laø giaù trò -5 vaø naèm ôû
coät ñaàu tieân (x1), do ñoù x1 seõ ñöôïc ñöa vaøo lôøi
giaûi cô baûn. Coät chöùa x1 seõ trôû thaønh coät xoay vaø
ñaùnh daáu muõi teân .
b. Haøng xoay seõ ñöôïc xaùc ñònh bôûi tyû soá nhoû nhaát
giöõa coät haèng soá vaø caùc phaàn töû cuûa coät xoay
töông öùng. Trong tröôøng hôïp naøy laø haøng thöù
nhaát bôûi vì (36/6<40/5<28/2).
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 41
KHÖÛ
• Ñaây laø böôùc cho pheùp giaûi heä m phöông trình vaø
coù m aån soá coøn laïi trong lôøi giaûi cô baûn. Bôûi vì chæ
coù duy nhaát moät bieán môùi ñöa vaøo lôøi giaûi cô baûn
vaø böôùc tính luoân luoân taïo ra moät ma traän ñôn
vò, trong böôùc naøy ta seõ bieán ñoåi sao cho giaù trò
xoay baèng 1 (chöùa taát caû caùc soá haïng cuûa haøng
naøy cho giaù trò xoay) vaø taïo ra caùc giaù trò baèng 0
cho caùc soá haïng khaùc trong phaàn coät xoay coøn
laïi, baèng caùch thay noù bôûi moät toå hôïp tuyeán tính
cuûa haøng ñang xeùt vaø haøng xoay (gioáng nhö
trong phöông phaùp khöû Gauss) .
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
42
x1 x2 s1 s2 s3 Haèng soá
1 1/3 1/6 0 0 36/6
5 5 0 1 0 40
2 4 0 0 1 28
-5 -3 0 0 0 0
x1 x2 s1 s2 s3 Haèng soá
1 1/3 1/6 0 0 6
0 10/3 -5/6 1 0 10
0 10/3 -1/3 0 1 16
0 -4/3 5/6 0 0 30
Nghieäm: x1=6, x2=0, s1=0,s2=10, s3=16,HMT=30
8
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 43
TOÁI ÖU HOÙA
HMT seõ cöïc ñaïi khi ta khoâng coøn giaù trò
tham khaûo naøo aâm ôû haøng cuoái.
Chuùng ta tieáp tuïc söï thay ñoåi lôøi giaûi cô baûn
vaø söï khöû vôùi nguyeân taéc nhö trình baøy ôû
böôùc treân.
Coät x2 seõ ñöôïc choïn laø coät xoay vaø haøng 2 seõ
ñöôïc choïn laø haøng xoay, do ñoù 10/3 seõ laø
giaù trò xoay, khi ñoù ôû böôùc naøy thì s1 vaø s2
seõ bò loaïi ra khoûi lôøi giaûi cô baû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
44
x1 x2 s1 s2 s3 Haèng soá
1 1/3 1/6 0 0 6
0 1 -0.25 3/10 0 3
0 10/3 -0.33 0 1 16
0 -1.33 5/6 0 0 30
x1 x2 s1 s2 s3 Haèng soá
1 0 1/4 -0.1 0 5
0 1 -0.25 3/10 0 3
0 0 1/2 -1 1 6
0 0 1/2 2/5 0 34
Nghieäm: x1=5, x2=3, s1=0,s2=0, s3=6,HMT=34
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 45
MỘT SỐ LƯU Ý
Biến bù s=0 Bất phương trình ràng
buộc đã đạt tối đa biến thành
phương trình.
Biến bù s > 0 Bất phương trình
ràng buộc tương ứng chưa đạt tối đa
“tài nguyên” này còn.
Kết quả trên ràng buộc [2] & [3] đã
đạt tối đa, ràng buộc [4] còn 6 đơn vị.
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 46
Bài tập: Dùng phương pháp đơn hình giải:
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 47
PHÖÔNG PHAÙP ÑÔN HÌNH
BAØI TOAÙN CÖÏC TIEÅU
Khi chuùng ta söû duïng phöông phaùp ñôn hình ñeå
tìm moät giaù trò cöïc tieåu, nhöõng bieán buø theâm
vaøo mang tröôùc noù daáu tröø seõ ñöa ñeán moät
daïng baøi toaùn ñaëc bieät.
Trong thöïc teá, ngöôøi ta coù theå giaûi baøi toaùn cöïc
tieåu baèng caùch thay noù baèng baøi toaùn ñoái
ngaãu ñeå trôû thaønh baøi toaùn cöïc ñaïi.
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 48
Söû duïng phöông phaùp ñôn hình ñeå giaûi baøi
toaùn sau :
Haøm muïc tieâu : Min F = 2x1 + 4x2
vôùi caùc raøng buoäc :
2x1 + x2 >= 14
x1 + x2 >= 12
x1 + 3x2 >= 18
vôùi x1, x2 >=0
PGS. Dr. Nguyễn Thống
9
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 49
Baûng ban ñaàu cho phöông phaùp ñôn hình (coù moät ít
thay ñoåi so vôùi baøi toaùn tröôùc).
a. Phöông trình vôùi caùc bieán buø :
2x1 + x2 - s1 = 14
x1 + x2 - s2 = 12
x1 + 3x2 - s3 = 18
PGS. Dr. Nguyễn Thống
2 1 1 0 0
1 1 0 1 0
1 3 0 0 1
14
12
18
1
2
1
2
3
*
x
x
s
s
s
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 50
TöØ ma traän naøy ta thaáy raèng neáu x1=x2=0, lôøi giaûi
cô baûn khoâng theå chaáp nhaän vì s1=-14, s2=-12,
s3=-18 (giaù trò aâm). Ñeå giaûi quyeát vaán ñeà naøy ta
seõ ñöa vaøo caùc bieán nhaân taïo Ai.
Bieán nhaân taïo (Ai) laø moät bieán aûo ñöôïc ñöa vaøo
moät caùch ñaëc bieät ñeå taïo neân moät lôøi giaûi cô baûn
chaáp nhaän ñöôïc, do ñoù noù khoâng coù yù nghóa veà
maët kinh teá. Ta ñöa vaøo moãi baát phöông trình
ban ñaàu moät bieán nhaân taïo :
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 51
PGS. Dr. Nguyễn Thống
2 1 1 0 0 1 0 0
1 1 0 1 0 0 1 0
1 3 0 0 1 0 0 1
14
12
18
1
2
1
2
3
1
2
3
*
x
x
s
s
s
A
A
A
x1 x2 s1 s2 s3 A1 A2 A3 Haèng soá
2 1 -1 0 0 1 0 0 14
1 1 0 -1 0 0 1 0 12
1 3 0 0 -1 0 0 1 18
-2 -3 0 0 0 -M -M -M 0
M>0 ñuû lôùn ñeå A
i
bò loaò ra khoûi p/t HMT
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 52
QUY HOAÏCH NGUYEÂN
• Ñaây laø moät tröôøng hôïp ñaëc bieät cuûa
baøi toaùn quy hoaïch tuyeán tính, ôû ñoù ta
chæ chaáp nhaän bieán quyeát ñònh coù giaù
trò nguyeân.
Choïn soá löôïng thieát bò saûn xuaát, soá
löôïng saûn phaå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 53
QUY HOAÏCH NGUYEÂN
Moät phöông phaùp giaûi cô baûn cho quy hoaïch
nguyeân thöôøng goïi laø “cutting plane“.
Ñaàu tieân xaùc ñònh bieán quyeát ñònh baèng phöông
phaùp quy hoaïch tuyeán tính.
Tröôøng hôïp bieán keát quaû khoâng nguyeân thieát
laäp raøng buoäc môùi töø baûn tính QHTT.
Giaûi heä p/t QHTT vôùi raøng buoäc môùi.
Quy trình seõ keát thuùc khi chuùng ta ñaõ nhaän caùc
bieán quyeát ñònh hoaøn toaøn nguyeâ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 54
Ví duï: Moät Xí nghieäp cheá taïo hai loaïi radio A vaø B .
- Lôïi nhuaän thu ñöôïc töø A vaø B laàn löôït laø 100 $US
vaø 200 $US.
- Moät ngöôøi thôï caàn 1 h vaø 4 h ñeå laép raùp A vaø B.
Moãi ngaøy ngöôøi thôï chæ coù theå laøm vieäc 12 h.
- Ngoaøi ra theo keát quaû cuûa phoøng nghieân cöùu tieáp
thò thì khaû naêng tieâu thuï cuûa thò tröôøng toái ña laø
4 saûn phaåm/ngaøy, khoâng phaân bieät loaïi radio
naøo.
PGS. Dr. Nguyễn Thống
10
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 55
- Veà khaû naêng coâng ngheä, xöôûng caàn 3 h vaø 1
h ñeå cheá taïo caùc linh kieän cho A vaø B.
- Xöôûng naøy hoaït ñoäng toái ña 10 h/ngaøy.
Xaùc ñònh chieán löôïc saûn xuaát A vaø B ñeå cöïc
ñaïi hoùa lôïi nhuaän cho Xí nghieäp, chuù yù laø
vieäc cheá taïo moät soá leõ radio A vaø B laø
khoâng coù nghóa thöïc teá.
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 56
Goïi x
1
= Soá löôïng radio A cheá taïo (nguyeân).
x
2
= Soá löôïng radio B cheá taïo (nguyeân).
s
1
,s
2
,s
3
: caùc bieán buø
Haøm muïc tieâu :
Max F = 100 (x
1
+ 2x
2
)
Giaûi baèng phöông phaùp ñôn hình. Sau khi theâm caùc
bieán buø s
i
vaøo caùc raøng buoäc ta coù :
x
1
+ x
2
+s
1
= 4
3x
1
+ x
2
+ s
2
= 10
x
1
+ 4x
2
+ s
3
= 12
Laäp baûng ñaàu tieân cuûa phöông phaùp ñôn hì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 57
x1 x2 s1 s2 s3 Haèng soá
1 1 1 0 0 4
3 1 0 1 0 10
1 4 0 0 1 12
-1 -2 0 0 0 0
PGS. Dr. Nguyễn Thống
x1 x2 s1 s2 s3 Haèng soá
3/4 0 1 1 -1/4 1
11/4 0 0 1 -1/4 7
1/4 1 0 0 1/4 3
-1/2 0 0 0 1/2 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 58
Keát quaû: x1 = 4/3 ,x2 =8/3, s1=s3=0,s2=10/3 vaø F
max
=
20/3. (x100)
Do keát quaû cho bieán quyeát ñònh x1 & x2 khoâng phaûi laø
soá nguyeân
ta khoâng chaáp nhaän tieáp tuïc giaûi vôùi Cuting plane.
PGS. Dr. Nguyễn Thống
x1 x2 s1 s2 s3 Haèng soá
1 0 4/3 0 -1/3 4/3
0 0 -11/3 1 2/3 10/3
0 1 -1/3 0 1/3 8/3
0 0 2/3 0 1/3 20/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 59
• Phöông phaùp sau ñaây goïi laø phöông phaùp Gomory
cho pheùp taïo ra caùc raøng buoäc boå sung töø baûng
cuoái cuøng cuûa phöông phaùp ñôn hình ôû treân. Caùc
cöôûng böùc boå sung naøy seõ giôùi haïn theâm phaàn mieàn
nghieäm coù theå.
• (Chuù yù: neân choïn raøng buoäc coù bieán buø =0
!!!)
• Raøng buoäc thöù 3 trong baûng cuoái cuøng cuûa phöông
phaùp ñôn hình cho ta :
PGS. Dr. Nguyễn Thống
333
8 31
2
SS
x
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 60
Moãi soáõ haïng trong phöông trình treân seõ ñöôïc
phaân tích thaønh toång cuûa moät soá nguyeân vaø
moät phaàn leõ theo nguyeân taéc sau :
Goïi: vì s
i
>=0 k>=0
Tröø hai phöông trình treân vaø chuyeån giaù trò 2 ra
veá sau
PGS. Dr. Nguyễn Thống
2
2
3
1
2
3
0
1
32 1 3
x s s( ) ( )
33
2 31 ssk
2
3
2
2 1
k x s
11
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 61
Bôûi vì (x2-s1-2) laø soá nguyeân, do ñoù ñieàu kieän caàn cho k
laø k>=2/3. Ngöôïc laïi thì neáu:
(2/3-k) laø soá leõ, ñieàu naày khoâng chaáp nhaän ñöôïc.
Toùm laïi:
PGS. Dr. Nguyễn Thống
0
2
3
k
3
2
3
S
3
S2
k 31
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 62
Töø p/trình tröôùc (caùc raøng buoäc ñaõ theâm bieán
buø):
s1 = 4 - x1 -x2
s3 = 12 - x1 - 4x2
Thay theá s1 vaø s3 vaøo phöông trình raøng
buoäc:
Do ñoù : x1+2x2 6 Raøng buoäc môùi vaø seõ
ñöa vaøo p/t QHTT ñeå giaûi laïi.
PGS. Dr. Nguyễn Thống
3
2
33
2 31
SS
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 63
Ñaây laø raøng buoäc môùi boå sung, noù cho pheùp giôùi
haïn mieàn nghieäm coù theå. Ta laïi baét ñaàu giaûi baøi
toaùn vôùi raøng buoäc boå sung naøy baèng phöông
phaùp ñôn hình. Quy trình naøy seõ chaám döùt khi
bieán quyeát ñònh nhaän laáy lôøi giaûi nguyeân ôû lôøi giaûi
toái öu. Lôøi giaûi cho baøi toaùn naày seõ laø :
Vaø F
max
= 600 $ ( < nghieäm baøi toaùn QHTT)
Chuù yù ta coù 2 lôøi giaûi toái öu cho baøi toaùn naøy.
PGS. Dr. Nguyễn Thống
1
2
1
2
0
3
2
2
x
x
x
x
&
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 64
Baøi taäp: Moät xí nghieäp cheá taïo hai loaïi radio A vaø
B .
- Lôïi nhuaän thu ñöôïc töø A vaø B laàn löôït laø 100
$US vaø 200 $US.
- Moät ngöôøi thôï caàn 1 h vaø 4 h ñeå laép raùp A vaø B.
- Moãi ngaøy ngöôøi thôï chæ coù theå laøm vieäc 12 h.
- Ngoaøi ra theo keát quaû cuûa phoøng nghieân cöùu tieáp
thò thì khaû naêng tieâu thuï cuûa thò tröôøng toái ña laø 4
saûn phaåm/ngaøy, khoâng phaân bieät loaïi radio naøo.
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 65
- Veà khaû naêng coâng ngheä, xöôûng caàn 3
h vaø 1 h ñeå cheá taïo caùc linh kieän cho
A vaø B.
- Xöôûng naøy hoaït ñoäng toái ña 10
h/ngaøy.
Xaùc ñònh chieán löôïc saûn xuaát A vaø B
ñeå cöïc ñaïi hoùa lôïi nhuaän cho xí
nghieäp.
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 66
Höôùng daãn:
Goïi x1 = Soá löôïng radio A cheá taïo (nguyeân)
x2 = Soá löôïng radio B cheá taïo (nguyeân)
• Haøm muïc tieâu :
Max F = 100 (x1 + 2x2)
• Raøng buoäc:
x1 + x2 < = 4
3x1 + x2 < = 10
x1 + 4x2 < = 12
PGS. Dr. Nguyễn Thống
12
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 67
QUY HOẠCH
NHỊ NGUYÊN
(Binary)
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 68
QUY HOAÏCH NHI NGUYEÂN
Trong tröôøng hôïp baøi toaùn QHTT ôû ñoù
nghieäm chæ coù hai khaû naêng löïa choïn 0
hoaëc 1, ta goïi quy hoaïch nhò nguyeâ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 69
Baøi taäp (Quy hoaïch nhò nguyeân).
Moät Nhaø ñaàu tö coù 4 döï aùn löïa choïn sao cho lôïi
nhuaän kyø voïng lôùn nhaát. Soá lieäu nhö sau:
Bieát raèng khaû naêng huy ñoäng voán naêm 1 laø 7tyû, naêm
2 laø 9 tyû. Do yeâu caàu kyõ thuaät, döï aùn 1 vaø 3 khoâng
ñöôïc choïn ñoàng thôøi. Thieát laäp HMT & raøng buoäc.
PGS. Dr. Nguyễn Thống
Döï aùn Ñaàu tö naêm 1 Ñaàu tö naêm 2 Lôïi nhuaän
1 2 4 1
2 3 2 0.9
3 2 2 0.7
4 3 3 1.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 70
Gọi x1, x2, x3, x4 là biến quyết định (x1=0 không
chọn p/a 1 và x1=1 chọn phương án 1,…).
Hàm mục tiêu:
F =x1 +0.9x2+0.7x3+1.1x4 Max
RÀNG BUỘC:
Năm 1: 2x1+3x2+2x3+3x4 <=7 [1]
Năm 2: 4x1+2x2+2x3+3x4 <=9 [2]
x1+x3 <=1 [3]
x1,x2,x3,x4 : binary [4]
(Dùng Solver trong Excel giải)
Xem SolVer_ViDu_QHNguyen.xls
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 71
• Baøi taäp: Coâng ty loïc hoùa daàu Z coù caùc phöông aùn
ñaàu tö (tr.$) nhö sau:
Döï aùn Phöông aùn Voán ñaàu
tö naêm 1
Voán ñaàu
tö naêm 2
Lôïi nhuaän
roøng quy ñoåi
1 Xaây döïng NM loïc daàu môùi. 5 7 1
2 Naâng caáp NM cuõ. 3 2 0.6
3 Xaây döïng ñöôøng oáng daãn
phuïc vuï p/a 1.
1 1.5 0.3
4 Xaây döïng NM cung caáp hoùa
chaát coâng nghieäp loïc daàu.
3 3 0.8
5 Xaây döïng NM ñieän noäi boä. 4.5 3 0.9
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 72
Khaû naêng giaûi ngaân cuûa Coâng ty ñeå ñaàu tö nhö sau:
• Naêm 1 : toái ña laø 14 tr.$
• Naêm 2: toái ña laø 11 tr.$
• Bieát raèng neáu phöông aùn 1 ñöôïc choïn thì p/a 2
khoâng choïn vaø ngöôïc laïi. Töông töï cho 2 p/a aùn 4
vaø 5. Phöông aùn 3 chæ ñöôïc xem xeùt khi coù p/a 1.
YÊU CẦU
Thieát laäp HMT & caùc raøng buoäc.
Söû duïng phöông phaùp Quy Hoaïch Nhò Nguyeân ñeå
tìm toå hôïp caùc phöông aùn ñaàu tö lôïi nhuaän cöïc
ñaïi (Xem SolVer_ViDu_QHNguyen.xls)
PGS. Dr. Nguyễn Thống
13
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 73
(tr.USD) F
1
F
2
F
3
F
4
0 0.00 0.00 0.00 0.00
1 0.28 0.25 0.15 0.20
2 0.45 0.41 0.25 0.33
3 0.65 0.55 0.40 0.42
4 0.78 0.65 0.50 0.48
5 0.90 0.75 0.62 0.53
6 1.02 0.80 0.73 0.56
7 1.13 0.85 0.82 0.58
8 1.23 0.88 0.90 0.60
9 1.32 0.90 0.96 0.60
10 1.38 0.99 1.00 0.60
Ví duï: Lôïi nhuaän roøng kyø voïng töø kinh doanh cuûa caùc
p/a (F
i
) theo voán ñaàu tö (010 tr.$) nhö sau
(Excel file Solver_QHTT1).
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 74
QUY HOAÏCH NHÒ NGUYEÂN
Yeâu caàu: Thieát laäp heä phöông trình quy
hoaïch nhò nguyeân vôùi muïc tieâu laø cöïc ñaïi
lôïi nhuaän vôùi giaù trò voán cho bieát tröôùc.
Höôùng daãn:
- Thieát laäp haøm muïc tieâu cuûa baøi toaùn.
- Thieát laäp caùc raøng buoäc.
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 75
• Xaùc ñònh phöông aùn kinh doanh coù hieäu quaû nhaát
theo caùc giaù trò voán ban ñaàu laø 10 tr.$.
F
1
F
2
F
3
F
4
0 0 0 0 0
1 0 0 1 0
2 0 0 0 1
3 0 1 4E-16 0
4 1 0 0 0
5 0 0 0 0
6 0 0 0 0
7 0 0 0 0
8 0 0 0 0
9 0 0 0 0
10 0 0 0 0
Sum 1 1 1 1 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 76
SÖÛ DUÏNG EXCEL VỚI COÂNG CUÏ
SOLVER ÑEÅ GIAÛI
CAÙC BAØI TOAÙN
- QUY HOAÏCH TUYEÁN TÍNH;
- QUY HOAÏCH NGUYEÂN;
- QUY HOAÏCH NHÒ NGUYEÂN;
- QUY HOAÏCH 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 77
PGS. Dr. Nguyễn Thống EXCEL VÔÙI SOLVER
Ñòa chæ HMT
trong file Excel
Ñòa chæ cac
bieán trong
file Excel P/t caùc raøng buoäc
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 78
Ví duï: Duøng Solver giaûi baøi toaùn QHTT sau:
Max Z = x1 + 2x2 + x3
Vôùi raøng buoäc :
2x1 + 3x2 +3x3 <=11
x1, x2, x3 >=0
PGS. Dr. Nguyễn Thống
14
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 79
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 80
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 81
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 82
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 83
Baøi taäp QUY HOAïCH NGUYEÂN
Laáy ví duï treân vôùi lôøi giaûi nguyeâ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 84
PGS. Dr. Nguyễn Thống
15
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 85
Baøi taäp (Quy hoaïch nhò nguyeân).
Moät Nhaø ñaàu tö coù 4 döï aùn löïa choïn sao cho Lôïi
nhaän kyø voïng lôùn nhaát. Soá lieäu nhö sau:
Bieát raèng khaû naêng huy ñoäng voán naêm 1 laø 7tyû, naêm
2 laø 9 tyû. Do yeâu caàu kyõ thuaät, döï aùn 1 vaø 3 khoâng
ñöôïc choïn ñoàng thôøi.
PGS. Dr. Nguyễn Thống
Döï aùn Ñaàu tö naêm 1 Ñaàu tö naêm 2 Lôïi nhuaän
1 2 4 1
2 3 2 0.9
3 2 2 0.7
4 3 3 1.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 86
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 87
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 88
Tìm lôøi giaûi trong tröôøng hôïp khoâng coù raøng
buoäc giöõa hai döï aùn 1 vaø 3.
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 89
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 90
Baøi taäp: Söû duïng Solver ñeå giaûi caùc baøi taäp ôû
treân.
PGS. Dr. Nguyễn Thống
16
PHÖÔNG PHAÙP ÑÒNH LÖÔÏNG TRONG QUAÛN LYÙ
Chương 2: Quy hoạch tuyến tính
11/26/2013 91
HẾT CHƯƠNG
PGS. Dr. Nguyễn Thống
Các file đính kèm theo tài liệu này:
chuong2_ppdl_qhtt_8624.pdf
