TIN HỌC ỨNG DỤNG
TRONG KINH DOANH
GV: Nguyễn Phương Tâm
Nguyễn Phương Tâm
2
Chương 8: GIẢI BÀI TOÁN TỐI ƯU BẰNG SOLVER
8.1 Công cụ Solver
8.2 Bài toán quy hoạch tuyến tính một chỉ số
8.3 Bài toán quy hoạch tuyến tính hai chỉ số
8.4 Bài toán quy hoạch phi tuyến
Nguyễn Phương Tâm
3
8.1 Công cụ Solver

Solver cũng là một phần trong bộ công cụ What-if
analysis.

Dùng Solver để tìm được giá trị tối ưu cho một
công thức tính toán của một ô, gọi là ô đích hay ô
chứa hàm mục tiêu (target cell)
Nguyễn Phương Tâm
4
8.1 Công cụ Solver

Solver làm việc với một nhóm các ô liên quan trực
tiếp hoặc gián tiếp đến công thức ở ô đích. Solver
điều chỉnh giá trị trong các ô được thay đổi gọi là ô
điều chỉnh hay là ô có thể chỉnh sửa được
(adjustable cells) sao cho kết quả trong ô đích đạt
một tiêu chí nào đó.
Nguyễn Phương Tâm

các ràng
buộc
Nguyễn Phương Tâm
7
8.1 Công cụ Solver
Nguyễn Phương Tâm
8
8.1 Công cụ Solver
Tham số Giải thích
Max Time Thời gian tối đa để giải bài toán, giá trị mặc
định là 100 giây dùng cho các bài toán đơn
giản. Thời gian tối đa có thể nhập là 32.767
giây.
Iterations Số lần lặp tối đa để giải bài toán, giá trị mặc
định là 100 lần dùng cho các bài toán đơn
giản. Thời gian tối đa có thể nhập là 32.767
giây.
Nguyễn Phương Tâm
9
8.1 Công cụ Solver
Precision
Độ chính xác của bài toán. Tại đây có thể
nhập vào các số trong khoảng 0 và 1. Số
càng gần 0 thì độ chính xác càng cao. Giá trị
này điều chỉnh độ sai số cho tập ràng buộc.
Giá trị mặc định là 1 phần triệu.
Tolerance
Chỉ áp dụng đối với bài toán có ràng buộc
nguyên. Nhập vào sai số có thể chấp nhận
được, sai số càng lớn thì tốc độ giải càng

Iteration
Results
Chọn nếu muốn Solver tạm dừng lại và hiển
thị kết quả sau mỗi lần lặp.
Nguyễn Phương Tâm
12
8.1 Công cụ Solver
Estimates
Chọn phương pháp cho Solver dùng để ước
lượng các biến:
Tangent: Sử dụng cách xấp xỉ tuyến tính bậc
nhất
Quadratic: Sử dụng cách xấp xỉ bậc bốn
Derivatives
Chọn cách để ưức lượng hàm mục tiêu và
các ràng buộc
Forward: được dùng phổ biến hơn, khi đó
các giá trị của ràng buộc biến đổi chậm.
Central: Dùng khi các giá trị của ràng buộc
biến đổi nhanh và được dùng khi Solver báo
không thể cải tiến kết quả thu được
Nguyễn Phương Tâm
13
8.1 Công cụ Solver
Search
Quy định giải thuật tìm kiếm kết quả cho
bài toán
Newton: là phương pháp mặc định, nó sử
dụng nhiều bộ nhớ hơn và số lần lặp ít
hơn.

+ c
2
x
2
+ …+c
n
x
n
= f(x) → max/min
a
11
x
1
+ a
12
x
2
+ … a
1n
x
n
Q b
1
a
21
x
1
+ a
22
x

Σ a[1,j] x[j]
b[1]
a[2,1] a[2,2] . . . . . . a[2,n]
Σ a[2,j] x[j]
b[2]
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
a[m,1] a[m,2] . . . . . . a[m,n]
Σ a[m,j]
x[j]
b[m]
x[1] x[2] . . . . . . x[n]
Hàng cuối cùng là các giá trị ban đầu của các biến,
có thể lấy giá trị của tất cả các biến bằng 1
Nguyễn Phương Tâm
18
8.2 Bài toán quy hoạch tuyến tính một chỉ số

Xét bài toán:
x
1
+ 4x
2
+ x
3
→ min (2)
2x
1
+ 3x
2
+ 4x


Tìm phương án tối ưu X (x1,x2,x3) và giá trị
phương trình (2) cực tiểu.

Các bước thực hiện để giải bài toán.
Nguyễn Phương Tâm
19
8.3 Bài toán quy hoạch tuyến tính hai chỉ số

Xét bài toán vận tải:
Có m kho hàng (điểm phát) chứa một loại hàng
hoá, lượng hàng ở kho i là ai và có n nơi tiêu thụ
(điểm thu) loại hàng này, nhu cầu nơi j là bj. Chi
phí vận chuyển một đơn vị hàng từ điểm phát i tới
điểm thu j là cij. Xác định các lượng hàng vận
chuyển xij từ các điểm phát i tới các điểm thu j
sao cho tổng chi phí là nhỏ nhất và nhu cầu các
điểm thu được thoả mãn.
Nguyễn Phương Tâm
20
8.3 Bài toán quy hoạch tuyến tính hai chỉ số

Dạng toán học của bài toán
njmix
mjax
miax
xc
ij
m
i

Cách bố trí dữ liệu trên bảng tính

Đ thu 1 Đ thu 2 Đ thu n Trị mục tiêu
Đ phát 1
c[1,1] c[1,2] . . . . . . c[1,n]
∑c[i,j] x[i,j]
Đ phát 2
c[2,1] c[2,2] . . . . . . c[2,n]
Đ phát 3
. . . . . . . . . . . . . . . . . . . . . . . .
Đ phát 4
c[m,1] c[m,2] . . . . . . c[m,n]
Nguyễn Phương Tâm
22
8.3 Bài toán quy hoạch tuyến tính hai chỉ số

Cách bố trí dữ liệu trên bảng tính
Cộng
hàng
Khả
năng
Phương
án
x[1,1] x[1,2] . . . . . . x[1,n]
Σx[1,j]
a[1]
x[2,1] x[2,2] . . . . . . x[2,n]
Σ x[2,j]
a[2]
. . . . . . . . . . .

Khối G9:G11 là khả năng của 3 điểm phát,
Nguyễn Phương Tâm
25
8.3 Bài toán quy hoạch tuyến tính hai chỉ số

Khối B13:E13 là nhu cầu của 4 điểm thu,

Khối F9:F11 là lượng hàng phát từ mỗi điểm phát i
theo phương án X đã chọn,

Khối B13:E13 là lượng hàng nhận được tại mỗi điểm
thu j theo phương án X.