Bài giảng Tin học ứng dụng trong kinh doanh - Chương 6: Bài toán tối ưu

Bài giảng Tin học ứng dụng trong kinh doanh - Chương 6: Bài toán tối ưu cung cấp cho học viên những kiến thức về 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, quy trình giải bài toán tối ưu trong Excel, tổ chức dữ liệu trong Excel, giải bài toán bằng Solver,... Mời các bạn cùng tham khảo chi tiết nội dung bài giảng!
Nội dung trích xuất từ 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 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 th ...