ứng dụng Excel để giải bài toán QTTT

Chương 2
GIẢI CÁC BÀI TOÁN QUI HOẠCH TUYẾN TÍNH TRONG EXCEL
Nhắc lại kiến thức cơ bản

Cài thêm trình Solver để giải bài toán qui hoạch tuyến tính
Tools/add-ins/solver add-in
Chuẩn bị bài toán trong Excel
Chú ý các bước xây dựng các ràng buộc
Giải bài toán trong Excel:Tools/solver
Diễn giải kết quả

Chú giải một số thuật ngữ
Tools/add-ins/solver add-in
Chuẩn bị bài toán trong Excel
Chú ý các bước xây dựng các ràng buộc
Giải bài toán trong Excel:Tools/solver
Diễn giải kết quả

Ví dụ 1:Bài toán chính tắc
Tìm max của hàm số
f(x)=3x1-x2-2x3+x4
Thỏa mãn ràng buộc:
x1+2x2-x3+x4=2
2x1-6x2+3x3+3x4=9
x1-x2+x3-x4=6
xj>=0 j=1,2,3,4
Chú ý một số thuật ngữ trong Excel
Set target cell: chọn ô chứa hàm mục tiêu
By changing cells: bằng cách làm biến đổi các ô
Subject to the constrains: thỏa mãn các ràng buộc
Chú ý khi nhập các ràng buộc
Int kiểu số nguyên
Bin: Kiểu nhị phân

Ví dụ 2: Bài toán nguyên vật liệu
Sản xuất 4 loại sản phẩm từ 3 loại nguyên vật liệu chính:
Kí hiệu nguyên vật liệu là NVL1, NVL2, NVL3
Kí hiệu sản phẩm là S1, S2, S3, S4.
Ràng buộc về tiêu hao NVL và lợi nhuận trên một sản phẩm như sau
Ràng buộc bài toán NVL
Ví dụ 2: Bài toán nguyên vật liệu
Yêu cầu:
Tìm phương án sản xuất tối đa hóa lợi nhuận
Lập bài toán:
Hàm mục tiêu: tìm max 500S1+300S2+200S3+280S4
Ràng buộc:
10S1+5S2+4S3+2S4≤2000
8S1+5S2+1.2S3+2.6S4≤1800
5S1+8S2+2.5S3+10S4≤2000
Sj≥0, j=1,2,3,4


Sử dụng hàm SUMPRODUCT để lập bài toán trong EXCEL
Cú pháp:
= SUMPRODUCT(array1,array2,..)
Tính tích vô hướng của các vector array1, array2,..
Giải bài toán bằng solver
Chọn answer report để có điều kiện phân tích kết quả.
Một số thuật ngữ:
Original value: Giá trị ban đầu
Final value: giá trị cuối cùng
Formula: công thức tính
Status: trạng thái
Binding: ràng buộc chặt
Not binding: ràng buộc không chặt
Phân tích kết quả bài toán
Chọn Report Sensitivity để phân tích độ nhạy của bài toán.
Sensitivity cho biết các hệ số của hàm mục tiêu có thể thay đổi đến mức độ nào mà vẫn thỏa mãn các ràng buộc khác và bài toán vẫn đạt tối ưu.
Chọn Report Limits để phân tích giới hạn của các ô chứa hàm mục tiêu và các ràng buộc.
Hai lựa chọn này không có ý nghĩa với các ràng buộc nguyên.
Phân tích độ nhạy của bài toán
Phân tich giới hạn của các hệ số
Ví dụ 3: bài toán vận tải
Là bài toán QHTT có dạng:

Ví dụ 3: Bài toán vận tải
Chở một loại hàng hóa từ 3 nơi sản xuất A1, A2, A3 đến 4 địa điểm tiêu thụ B1, B2, B3, B4
Khả năng sản xuất và khả năng tiêu thụ, cước phí vận tải như sau:
Điều kiện cân bằng thu phát
Bảng vận tải
Lập bài toán
Gọi Xij là lượng hàng vận chuyển từ Ai đến Bj (i=1,2,3; j=1,2,3,4)
Hàm mục tiêu:
14X11 + 2X12 + 2X13 + 12X14 + 10X21 + 9X22 + 7X23 + 14X24 + 6X31 + 14X32 + 26X33 + 14X34 -- min
Các ràng buộc
Lập bài toán
X11 + X12 + X13 + X14 = 30
X21 + X22 + X23 + X24 = 40
X31 + X32 + X33 + X34 = 60
X11 + X21 + X31 = 30
X12 + X22 + X32 = 25
X13 + X23 + X33 = 35
X14 + X24 + X34 = 40
Xij ≥0 (i=1,2,3; j=1,2,3,4)
Các lựa chọn khi giải trong Excel
Iterations: số bước lặp
Precision: Độ chính xác
Tolerance: sai số cho phép
Convergence: mức độ hội tụ của hàm mục tiêu
Assume linear model: giả thiết hàm tuyến tính
Assume non-negative: giả thiết không âm
Các lựa chọn khi giải trong Excel
Use Automatic scaling: tự động thay đổi tham số
Show iteration results: trình bày kết quả của từng bước lặp.

Chú ý
Dựa vào công cụ Excel có thể thay đổi điều kiện ràng buộc để tìm được phương án thích hợp với các điều kiện của bài toán thực tế.

Giải hệ phương trình bậc nhất
Bài toán:
Vừa gà vừa chó
Bó lại cho tròn
Ba mươi sáu con
Một trăm chân chẵn
Hỏi có mấy con gà, mấy con chó
Sử dụng Excel để giải hệ phương trình tuyến tính
Sử dụng hàm nghịch đảo ma trận (MINVERSE) và hàm nhân ma trận (MMULT) có thể giải hệ phương trình tuyến tính bằng phương pháp ma trận.
Ví dụ: giải hệ phương trình
8x1+x2+2x3=0
5x1+7x2-3x3=0
2x1+x2-2x3=-2
Sử dụng Excel để giải hệ phương trình tuyến tính
Bước 1: Viết các hệ số của phương trình thành ma trận.
Bước 2: dùng hàm MINVERSE để nghịch đảo ma trận.
Bước 3: Dùng hàm MMULT để nhân ma trận nghịch đảo với vế phải của phương trình.
Chú ý: khi nghịch đảo và nhân ma trận sử dụng công thức mảng (nhấn đồng thời Ctrl shift enter)