›
›

Bài giảng Tin học ứng dụng trong kinh doanh - Chương 6: Bài toán tối ưu - Nguyễn Thị Thùy Liên

Download
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
CjXj → max(min)  
f(x1,.. xn ) =  
j=1  
Hệ ràng buộc  
n
AijXj Bi  
: ràng buộc quản lý (=, >=, <=)  
j=1  
Xi là các số thực  
Tin hꢀc ꢁng dꢂng  
4
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<=500000000  
• Công suất : x1<=5000, x2<=10000  
• Ràng buộc tự nhiên x1>=0, x2>=0  
Tin hꢀc ꢁng dꢂng  
13  
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  
được, sai số càng lớn thì tốc độ giải càng  
Tolerance  
nhanh. Giá trị mặc định là 5%.  
20  
Tải về để xem bản đầy đủ
pdf 44 trang baolam 11/05/2022 4640
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Tin học ứng dụng trong kinh doanh - Chương 6: Bài toán tối ưu - Nguyễn Thị Thùy Liên", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pdfbai_giang_tin_hoc_ung_dung_trong_kinh_doanh_chuong_6_bai_toa.pdf