Xem mẫu
- Chương 6
Bài toán tối ưu
GV: Nguyễn Thị Thùy Liên Email: lien.nguyenthithuy@phenikaa-uni.edu.vn
- 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.
Tin học ứng dụng
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:
▪ Quy hoạch tuyến tính
▪ Quy hoạch phi tuyến
Tin học ứng dụng
3
- Bài toán quy hoạch tuyến tính
❖Mô hình bài toán quy hoạch tuyến tính (QHTT)
❖Hàm mục tiêu: n
f(x1,.. xn ) = CjXj → max(min)
j=1
Hệ ràng buộc
n
AijXj Bi
j=1
: ràng buộc quản lý (=, >=,
- Bài toán quy hoạch tuyến tính
❖Phương án: Một véc tơ x=(x1 , x2 ,….xn) thỏa mãn hệ
ràng buộc phương án của bài toán
❖Phương án tối ưu: Một phương án mà tai đó hàm mục
tiêu đạt giá trị cực tiểu (hoặc cực đại)
=> Giải bài toán tối ưu chính là đi tìm phương án tối ưu
Tin học ứng dụng
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
Tin học ứng dụng
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…
Tin học ứng dụng
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)
Z(X) = CX =>min/max/const
Ví dụ: Cực đại hóa lợi nhuận
Lợi nhuận = Z(x) = c1x1+ c2x2 + c3x3 ->max
Ví dụ: Cực tiểu hóa chi phí
Chi phí = Z(x = c1x1+ c2x2 + c3x3 ->min
Tin học ứng dụng
8
- Lập mô hình
❖B3: Xác định hệ ràng buộc
Xác định tất cả các hạn chế, ràng buộc đối với bài toán
và biểu diễn dưới dạng phương trình hay bất phương
trình theo các biến quyết định
AX B
X ≥0
Chú ý: Ràng buộc tự nhiên: Giá trị không âm, số
nguyên, chọn. Không chọn
Ví dụ: xi ≥ 0 (i=1,n); xi nguyên, Xi ϵ {0,1}
Tin học ứng dụng
9
- Lập mô hình – ví dụ
❖Bài tập: mô hình hóa bài toán điểm hòa vốn (BEP)
❖Biến quyết đinh: Q: sản lượng
❖Tham số: F: cp cố định, V cp biến đổi bình quân, P giá
❖Biến trung gian: TC:tổng cp, TR:tổng lợi nhuận
❖Hàm mục tiêu: B: lợi nhuận, 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)
Tin học ứng dụng
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ệ
Tin học ứng dụng
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.
Chi phí sản xuất áo là: 40.000đ/cái. Giá bán một quần
là : 100.000đ/cái. Giá bán một áo là 65.000đ/cái.
❖Mục tiêu của công ty là tối đa hóa lợi nhuận. Anh/chị
hãy tính số lượng quần, số lượng áo cần thiết sản xuất
và lợi nhuận hàng tháng của công ty.
Tin học ứng dụng
12
- Bài toán
❖B1: Lập mô hình
▪ 1. Xác định biến các biến
• Biến quyết định: Gọi x1 là số lượng quần, x2 là số lượng
áo cần sản xuất
• Xác định tham số: a1: giá quần, a2: giá áo, b1: chi phí
quần, b2: chi phí áo
▪ 2. Xác định hàm mục tiêu
• Mục tiêu tối đa lợi nhuận:
B = B(quần) + B(áo) -> max => c1.x1+c2.x2 -> max
(c1 = a1-b1) (c2 = a2-b2)
▪ 3. Xác định ràng buộc
• Ràng buộc chi phí: 60000x1+40000x2
- Bài toán
❖B2: Thiết lập dữ liệu cho bài toán
Tin học ứng dụng
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ở,….
Tin học ứng dụng
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
Tin học ứng dụng
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
Tin học ứng dụng
17
- Tìm lời giải bằng Solver
❖B5: Menu Tool -> Solver Giải quyết
Hàm mục tiêu
Các ẩn
Các ràng buộc Nhập các ràng buộc Làm lại
Tin học ứng dụng
18
- Công cụ Solver – solver option
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.
19
- Công cụ Solver – solver option
Độ 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ố
Precision 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
nguon tai.lieu . vn
