9/5/2025
1
ĐẠI HỌC QUỐC GIA TP.HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC BÁCH KHOA
KHOA ĐIỆN-ĐIỆN TỬ
KỸ THUẬT RA QUYẾT ĐỊNH
GV: TRƯƠNG HOÀNG KHOA
Email: trhkhoa@hcmut.edu.vn
1
Kỹ thuật ra quyết định
Chương 1. Thuật toán đơn hình
2
1.1 Biến cơ sở và không cơ sở
1.2 Nghiệm cơ sở
1.3 Phương pháp giải
1
2
9/5/2025
2
Kỹ thuật ra quyết định
1.1 Biến cơ sở và không cơ sở
3
▪Tìm nghiệm của phương trình:
sử dụng phương pháp khử Gauss-Jordan
Nghiệm của phương trình tuyến tính
▪Trước tiên, ta sử dụng một ví dụ đơn giản và sau đó
tổng quát hóa cho các trường hợp chung.
▪Xét hệ hai phương trình với năm ẩn số:
Kỹ thuật ra quyết định
1.1 Biến cơ sở và không cơ sở
4
▪Đối với ví dụ này, số ẩn số vượt quá số phương trình và
do đó hệ có nhiều nghiệm; đây là lý do chính mà nghiệm
phương trình tuyến tính là không tầm thường (nontrivial).
▪Phương pháp khử Gauss – Jordan sử dụng phép biến đổi
hàng sơ cấp (elementary row operations)
▪Nhân một hàng bất bất kỳ với số khác 0
▪Cộng bội k của một hàng vào một hàng khác
▪Biến đổi S1thành S2 bằng cách nhân phương trình (i) với
-1 và cộng nó vào phương trình (ii)
Nghiệm của phương trình tuyến tính
3
4
9/5/2025
3
Kỹ thuật ra quyết định
1.1 Biến cơ sở và không cơ sở
5
▪Biến cơ sở (basic variable) là một biến 𝑥𝑖xuất hiện với
hệ số 1 trong một phương trình và với hệ số 0 trong tất
cả phương trình khác.
▪Các biến 𝑥𝑗không phải là biến cơ sở được gọi là biến
không cơ sở (nonbasic variables)
▪Trong hệ S2, 𝑥1là biến cơ sở; 𝑥2, 𝑥3, 𝑥4, và 𝑥5là biến
không cơ sở.
▪Các biến cơ sở có thể được tạo ra qua các phép biến
đổi hàng sơ cấp.
Các định nghĩa:
Kỹ thuật ra quyết định
1.1 Biến cơ sở và không cơ sở
6
▪Phép toán trục (Pivot operation) là một chuỗi các phép
biến đổi hàng sơ cấp để làm giảm một hệ phương trình
tuyến tính thành một hệ mà trong đó một biến xác định
trở thành một biến cơ sở.
▪Hệ chính tắc (canonical system) là một tập hợp các
phương trình tuyến tính thu được thông qua các phép
toán trục (pivot operation). Nó có đặc điểm là có cùng số
biến cơ sở với số phương trình trong hệ.
Các định nghĩa:
5
6
9/5/2025
4
Kỹ thuật ra quyết định
1.2 Nghiệm cơ sở
7
▪Biến đổi hệ S2 thành hệ chính tắc S3có dạng:
▪Nghiệm cơ sở (basic solution) thu được từ một hệ chính
tắc với tất cả các biến không cơ sở được đặt thành 0
▪Ví dụ: đặt 𝑥3= 𝑥4= 𝑥5= 0 thì
𝑥1= 6 và 𝑥2= 2
Dạng hệ chính tắc:
Kỹ thuật ra quyết định
1.2 Nghiệm cơ sở
8
▪Nghiệm cơ sở khả thi là một nghiệm cơ sở mà giá trị của
tất cả các biến cơ sở là không âm.
▪Trong ví dụ hệ S2 , chúng ta có thể chọn hai nghiệm bất
kì là nghiệm cơ sở.
▪Tổng quát cho một hệ gồm mphương trình với nẩn số,
có 𝑛
𝑚tổ hợp có thể có của các nghiệm cơ sở.
▪Khi n tăng số tổ hợp trở nên lớn mặc dù nó là hữu hạn.
▪Ví dụ, chúng ta có:
tổ hợp của các sự lựa chọn có thể có.
Nghiệm cơ sở khả thi (basic feasible solution):
7
8
9/5/2025
5
Kỹ thuật ra quyết định
1.3 Phương pháp giải
9
▪Tiếp theo, chúng ta sử dụng một ví dụ đơn giản để xây
dựng phương pháp giải đơn hình.
▪Phương pháp đơn hình là một cách giải có hệ thống và
hiệu quả để kiểm tra một tập hợp các lời giải khả thi cơ
sở của phương trình tuyến tính để tìm ra lời giải tối ưu.
▪Chúng ta áp dụng các khái niệm được giới thiệu trong
các định nghĩa ở trên.
Phương pháp giải đơn hình:
Kỹ thuật ra quyết định
1.3 Phương pháp giải
10
Ví dụ phương pháp đơn hình:
Dạng
chính tắc
9
10