Chương 6
Bài toán tối ưu
GV: Nguyễn Thị Thùy Liên

Email: [email protected]


Bài toán tối ưu
 Trong toán học, thuật ngữ tối ưu hóa chỉ việc nghiên cứu
cá bài toán có dạng:
Cho trước một hàm f: A->R từ tập hợp A tới tập số thực.
Tìm: một phần từ x0 thuộc A:
sao cho f(x0)≤f(x) với mọi x thuộc A(“cực tiểu hóa”)
hoặc sao cho f(x0)≥f(x) với mọi x thuộc A(“cực đại hóa”)
 Một phát biểu bài toán như vậy đôi khi được gọi là một
quy hoạch toán học. Nhiều bài toán thực tế và lý thuyết có
thể được mô hình theo cách tổng quát trên.

2


Bài toán tối ưu
 Miền xác định A của hàm f được gọi là không gian tìm
kiếm. Thông thường là tập con của Rn , thường được xác
định bởi một tập các ràng buộc, các đẳng thức, bất đẳng
thức mà các thành viên của A phải thỏa mãn.
 Các phần tử của A được gọi là các lời giải khả thi.
 Hàm f được gọi là hàm mục tiêu hoặc hàm chi phí cực tiểu
hóa(hoặc cực đại hóa) hàm mục tiêu được gọi là lời giải
tối ưu.
 Các lĩnh vực con chính:


5


Quy trình giải bài toán tối ưu trong Excel
Mô tả bài toán – Lập mô hình
Tổ chức dữ liệu trong Excel
Giải bài toán bằng Solver

6


Lập mô hình
B1: Xác định và đặt tên biến
 Biến quyết định: nhà quản lý “kiểm soát được”
 Biến ngoài: ảnh hưởng nhưng không kiểm soát
được -> tham số bài toán

 Biến trung gian: làm rõ ý nghĩa hơn bài toán
Phải đặt tên cho các biến
Ví dụ: x1- chọn xe đạp; c1- chi phí xe đạp, v- giá vé
xe bus…
7


Lập mô hình
B2: Xác định mục tiêu => hàm mục tiêu
Xác định mục tiêu và biểu diễn dưới dạng hàm mục tiêu
(hàm theo biến quyết định ở bước 1 và dạng mục tiêu
-> min/max)

B=TR-TC =0
Phương tình quan hệ: TR = P*Q, TC = F+V*Q, Q≥0
=>giải: B= TR-TC = P*Q – (F+V*Q) = Q(P-V)-F
B = Qhv(P-V) –F =0 (hòa vốn)
 Qhv = F/(P-V)
10


Tổ chức dữ liệu trong Excel
Ví dụ: tổ chức dữ liệu BEP
Biến quyết định
(giá trị hằng)

Giá trị gốc
Hàm mục tiêu
(công thức)

Phương trình
quan hệ

11


Bài toán
Một doanh nghiệp sản xuất quần áo, có một máy sản
xuất quần và hai máy sản xuất ao. Công suất tối đa
của máy sản xuất quần là 5000 cái/tháng. Công suất
tối đa của máy sản xuất áo là 10000 cái/tháng. Tổng
vống công ty chi tiêu cho sản xuất hàng tháng là 500
triệu đồng. Chi phí sản xuất 1 quần là 60.000 đ/cái.


14


Giới thiệu Solver
Solver là một công cụ cấp cao của excel, nhưng có ít
người biết đến nó
Solver có rất nhiều ứng dụng, từ kinh doanh,
marketing, xây dựng thời gian biểu, đầu tư cổ phiếu,
giải bài toán quy hoạch tuyến tính.. Đều có thể sử
dụng solver và giải chúng một cách nhanh chóng.
Giả sử bạn có một số tiền tiêu vặt hàng tháng, làm sao
để cân đối các khoản chi tiêu để ăn sáng, xăng xe,
mua sách vở,….

15


Công cụ solver
B1: Nhấp chuột vào menu Tools ở trên thanh menu.
B2: Nhấp chuột vào chữ Add-Ins, khi đó một cửa sổ
sẽ hiện ra

16


Công cụ solver
B3: Nhấp chuột chọn Solver Add-Ins
B4: Nhấp chuột vào nút OK, khi đó trong Tools sẽ có
hàng Solver

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.
19


Công cụ Solver – solver option

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.

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
Tolerance
được, sai số càng lớn thì tốc độ giải càng
nhanh. Giá trị mặc định là 5%.
20


Công cụ Solver – solver option

Convergence

Chỉ áp dụng cho các bài toán không

thị kết quả sau mỗi lần lặp.
22


Công cụ Solver – solver option
Chọn phương pháp cho Solver dùng để ước
lượng các biến:
Estimates 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
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 đó
Derivatives 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
23


Công cụ Solver – solver option

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.
Conjugate: Cần bộ nhớ ít hơn nhưng số