Báo cáo tóm tắt sáng kiến kinh nghiệm - Giải pháp sử dụng công cụ Solver trong Excel để giải bài toán quy hoạch tuyến tính

Nội dung tóm tắt: Báo cáo tóm tắt sáng kiến kinh nghiệm - Giải pháp sử dụng công cụ Solver trong Excel để giải bài toán quy hoạch tuyến tính

1. PHẦN I: TÓM TẮT NỘI DUNG 1.1. Tên giải pháp: “SỬ DỤNG CÔNG CỤ SOLVER TRONG EXCEL ĐỂ GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH” 1.2. Yếu tố mới và sáng tạo: Giải pháp hoàn toàn mới, được áp dụng lần đầu Sự cạnh tranh khốc liệt trong hoạt động sản xuất kinh doanh luôn đòi hỏi các nhà quản lý doanh nghiệp phải thường xuyên lựa chọn phương án để đưa ra các quyết định nhanh chóng, chính xác và kịp thời với những ràng buộc và hạn chế về các điều kiện liên quan tới tiềm năng của doanh nghiệp, điều kiện thị trường, hoàn cảnh tự nhiên và xã hội. Việc lựa chọn phương án nào là tối ưu theomục tiêu định trước là hết sức quan trọng. Nếu tất cả các yếu tố liên quan đến khả năng, mục đích và quyết định lựa chọn đều có mối quan hệ tuyến tính thì chúng ta hoàn toàn có thể sử dụng mô hình quy hoạch tuyến tính để mô tả, phân tích và tìm lời giải cho vấn đề lựa chọn tối ưu trong quản lý kinh tế. Trong môn học Toán cao cấp việc giải bài toán quy hoạch tuyến tínhthông thường được thực hiện bằng thuật toán đơn hình.Tuy nhiên đa phần sinh viên đạt điểm không cao hoặc phải thi lại, học lại. Nguyên nhân chủ yếu là do các em chưa quen với cách học, cách giảng dạy trên đại học, chưa thích ứng kịp với các khái niệm mới khiến việc học khó khăn. Để đáp ứng được nhu cầu hiện nay, bản thân đã nghiên cứu công cụ hỗ trợ Solver trong phần mềm Excel để giải quyết các bài toán về quy hoạch tuyến tính hiệu quả, chính xác và nhanh chóng.Và đây cũng là đề tài nghiên cứu trong năm nay. 1.3 Phạm vi áp dụng: Đề tài này là sự đúc kết của bản thân và có thể được áp dụng cho các cá nhân hoặc các tổ chức khác cần giải quyết các bài toán lập kế hoạch sản xuất tối ưu với tài nguyên có hạn. Hiệu quả của giải pháp: Sử dụng công cụ Slover trong phần mềm Excel để giải các bài toán quy hoạch tuyến tính dễ dàng và hiệu quả. Cụ thể: - Tiết kiệm được thời gian so với phương pháp thủ công - Chỉ vài cú click chuột - Không sử dụng hàm trong Excel - Dễ dàng tìm được phương án cực biên và giá trị của hàm mục tiêu Trang 1
2. PHẦN II: NỘI DUNG I. ĐẶT VẤN ĐỀ II. NHỮNG KHÓ KHĂN III. GIẢI PHÁP KHẮC PHỤC IV. KẾT QUẢ ĐẠT ĐƯỢC V. KẾT LUẬN I. ĐẶT VẤN ĐỀ Toán học ngày càng có nhiều ứng dụng phong phú trong các vấn đề tổ chức và quản lý sản xuất. Thông thường trước mọi vấn đề quản lý sản xuất người ta có thể đưa ra nhiều phương án. Làm thế nào để có thể chọn được phương án tốt nhất. Ngày nay đã sử dụng rộng rãi các thành tựu của các ngành toán học mới như: Quy hoạch tuyến tính, lý thuyết đô thị, lý thuyết trò chơi Việc sử dụng máy tính điện tử và phương pháp toán học để điều khiển sản xuất ngày càng phát triển, đã đem lại những hiệu quả kinh tế rất to lớn. Một nét nổi bật nữa là ngày nay toán học đã xâm nhập vào nhiều ngành khoa học mà trước đây người ta không hề nghĩ tới, kể cả khoa học và xã hội. Với những hiệu quả kinh tế mà toán học đem lại mà nhiều trường cao đẳng, đại học cả nước đều đưa vào giảng dạy với bộ môn toán cao cấp cho nhiều ngành nghề khác nhau. Trong bộ môn này, có một bộ phận gắn liền với việc quản lý, lập kế hoạch sản xuất sao cho kết quả mang lại là tối ưu với chi phí thấp. Đó chính là bộ phận quy hoạch tuyến tính. II. NHỮNG KHÓ KHĂN  Quy hoạch tuyến tính là học phần đại cương sinh viên thường được học ở năm thứ nhất và cũng là một khó khăn lớn của sinh viên. Học phần này là môṭ phần của toán cao cấp và nằm trong phần kiến thứ c đaị cương, kiến thứ c không phải ở mứ c khó, tuy nhiên đa phần sinh viên lại đạt điểm không cao hoặc phải thi lại, học lại. Nguyên nhân chủ yếu là do các em chưa quen với cách học, cách giảng dạy trên đại học, chưa thích ứng kịp với các khái niệm mới khiến việc học khó khăn.  Học Toán cao cấp không quá khó. Cái khó là mới vào đại học chưa quen với môi trường mới, cách giảng dạy của thầy cô và cách tự học, tự tìm hiểu theo định hướng. Nếu sinh viên không thay đổi và tìm ra cách học phù hợp thì chắc chắn đến lúc thi sẽ bị điểm thấp. Trang 2
3.  Khó khăn lớn nhất đối với sinh viên là việc tìm lời giải cho bài toán tối ưu với chi phí tính toán rất lớn do dữ liệu cần xử lý và số phương án quá nhiều. Vì vậy, việc tính toán thủ công để tìm phương án tối ưu trong thực tế là không khả thi hoặc tốn rất nhiều thời gian. Thí dụ: Bài toán lập kế hoạch sản xuất tối ưu với tài nguyên có hạn. Một nhà máy sản xuất hai loại sản phẩm (I) và (II) từ hai loại nguyên liệu A và B. Biết rằng mỗi sản phẩm loại I cần 4 đơn vị nguyên liệu A và 2 đơn vị nguyên liệu B; mỗi sản phẩm loại (II) cần 2 đơn vị nguyên liệu A và 4 đơn vị nguyên liệu B. Khi bán một sản phẩm loại I lãi 8 đơn vị tiền, khi bán 1 sản phẩm loại (II) lãi 6 đơn vị tiền. Hãy lập kế hoạch sản xuất sao cho thu lãi nhiều nhất với số dự trữ nguyên liệu có hạn: 60 đơn vị nguyên liệu A và 48 đơn vị nguyên liệu B. Giải bài toán với lời giải thủ công Lập mô hình: Biến quyết địnhx1, x2 là số sản phẩm loại (I), (II) cần sản xuất. Tổng lãi: Hàm mục tiêu: f(x) = 8x1+ 6x2 max (1) Điều kiện ràng buộc: Tổng số nguyên liệu A: 4x1 + 2x2 ≤ 60 (a) (2) Tổng số nguyên liệu B: 2x1 + 4x2 ≤ 48 (b) x1, x2 ≥ 0 Vậy ta có bài toán tối ưu với hàm mục tiêu (1) thỏa mãn điều kiện ràng buộc (2). a) Đưa về dạng chính tắc Thêm các ẩn bù x3, x4 vào các ràng buộc (a), (b). Bài toán được đưa về dạng chính tắc: f(x) = 8x1 + 6x2+ 0x3 + 0x4 max Điều kiện ràng buộc: 4 1 + 2 2 + 3 = 60 {2 1 + 4 2 + 4 = 48 1, 2, 3, 4 ≥ 0 b) Đưa về dạng chuẩn. Bài toán đã ở dạng chuẩn với các ẩn cơ sở là x3 và x4, ta có ngay một phương án 1 cơ bản xuất phát là X = (x1, x2, x3, x4) = (0, 0, 60, 48) Khi bài toán đã thỏa mãn điều kiện (a) và (b) thì việc giải bài toán bằng phương pháp đơn hình, gồm các bước sau: Bước 1: Khởi đầu. Lập bảng đơn hình (1) ứng với phương án xuất phát X(1): xác định các ẩn cơ sở, các hệ số để đưa vào bảng đơn hình khởi đầu. Trang 3
4. Bước 2: Kiểm tra điều kiện tối ưu (a) Tính các ∆j (b) Kiểm tra điều kiện tối ưu: ∆j≥0 ∀j. Nếu thỏa mãn: dừng thuật toán. Chuyển sang bước 4. Nếu vi phạm điều kiện tối ưu, tức là còn có giá trị ∆j< 0 (với cột j nào đó), chuyển sang bước 3. - Sau hai bước trên, ta có bảng đơn hình đầu tiên, với các giá trị ∆j ở dòng cuối. Do điều kiện tối ưu bị vi phạm, ta chuyển sang bước 3. Bảng đơn hình (1) Hệ số ci Ẩn cơ sở Phương c1 =8 c2 = 6 c3 = 0 c4 = 0 án x1 x2 x3 x4 0 x3 60 4 2 1 0 0 x4 48 2 4 0 1 ∆j =∑ 푖. 푖푗 − 푖 ∆1=-8 ∆2= -6 ∆3= 0 ∆4= 0 Bước 3: Biến đổi bảng. (a) Chọn cột xoay: ứng với ∆j< 0 nhỏ nhất, đó là ∆1 = -8. Cột xoay là cột 1. 푖 (b) Chọn dòng xoay: trên cột xoay, tìm dòng ứng với min vớiaij≥ 0. Trong bảng 푖푗 đơn hình (1) là dòng 1. (c) Xác định phần tử trục là phần tử giao của dòng xoay và cột xoay. (phần tử được đánh dấu trong bảng đơn hình (1)). (d) Xác định ẩn cơ sở mới là ẩn ứng với cột xoay để đưa vào, và ẩn cơ sở cũ ứng với hàng xoay để loại khỏi bảng đơn hình mới. Trong bảng đơn hình (1): ẩn đưa vào là x1, ẩn loại ra sẽ là x3. Sau đó lập bảng đơn hình mới ứng với cơ sở mới. (e) Tính toán các hệ số trong bảng đơn hình mới (bảng 2), ta nhận được phương án X(2): - Chia tất cả dòng xoay cũ cho phần tử trục (kể cả ở cột phương án), sau đó chuyển dòng mới vào vị trí tương ứng ở bảng mới (gọi là dòng xoay mới). - Biến đổi để các phần tử cùng cột với cột xoay cũ có dạng vecto đơnvị, với phần tử trục bằng 1, bằng phép biển đổi Gauss cho ma trận hệ số và cả cột phương án, đưa kết quả vào bảng mới sau đó chuyển sang bước 2. Bảng đơn hình (2) Hệ số ci Ẩn cơ sở Phương c1 =8 c2 = 6 c3 = 0 c4 = 0 án x1 x2 x3 x4 8 x1 15 1 1/2 1/4 0 0 x4 8 0 3 -1/2 1 ∆j =∑ 푖. 푖푗 − 푖 ∆1 =0 ∆2 =-2 ∆3 =2 ∆4 = 0 Trang 4
5. Với bảng đơn hình (2), điều kiện tối ưu chưa thỏa mãn, bước 3 được lặp lại, ta nhận được bảng đơn hình (3), với phương án X3. Bảng đơn hình (3) Hệ số ci Ẩn cơ sở Phương c1 =8 c2 = 6 c3 = 0 c4 = 0 án x1 x2 x3 x4 8 x1 12 1 0 1/3 1/6 6 x2 8 0 1 -1/6 1/3 ∆j =∑ 푖. 푖푗 − 푖 ∆1 = 0 ∆2 =0 ∆3 =5/3 ∆4 =2/3 Điều kiện tối ưu đã thỏa mãn với bảng (3): ∆j ≥ 0 ∀j. Chuyển sang bước 4. Bước 4: Xác định nghiệm bài toán. (a) Phương án trên bảng là tối ưu: X3 = (12, 6, 0, 0) khi đó ta chọn phương án tối ưu của bài toán gốc là : X* = (12, 6). (b) Giá trị hàmmụctiêu: fmax = f(X*) = 8*12+6*6 = 132. Rõ ràng, bằng thuật toán đơn hình, chúng ta dễ dàng tìm ra được giá trị của hàm mục tiêu. Nhưng việc xử lý tính toán và thời gian bỏ ra để hoàn thành công việc là rất lớn. Do đó, chúng ta nên cần chọn một công cụ hỗ trợ để giải quyết các bài toán tối ưu. III. GIẢI PHÁP KHẮC PHỤC Trước những băn khoăn của sinh viên về việc làm thế nào để vượt qua cái khô khan của toán học cũng như vai trò của nó trong đời sống xã hội. Để giải quyết khó khăn này, Microsoft Excel đã xây dựng công cụ Solver giúp giải các bài toán tối ưu. Trong phần này sẽ giới thiệu cách sử dụng công cụ Solver trong Excel 2007 để tìm phương án tối ưu thông qua một số bài toán tối ưu quen thuộc đó là bài toán nguyên vật liệu sản xuất. Trước hết, để sử dụng được công cụ Solver trong Excel, chúng ta thực hiện các bước sau: Bước 1. Nhấp chuột vào nút Office | chọn Excel Options Trang 5
6. Bước 2.Trong hộp thoại Excel Options, chọn Add-Ins từ danh sách bên trái, danh sách các Add-Ins trong Excel được liệt kê trong hộp Add-Ins với các phân nhóm khác nhau. Bước 3.Tại Manage, chọn Excel Add-Ins từ danh sách và nhấn nút Go để mở hộp thoại Add-Ins. Trang 6
7. Bước 4. Chọn Solver Add-in từ dan hsách Add-Ins avaiable và nhấn nút OK. Bước 5. Trong ngăn Data xuất hiện thêm nhóm Analysis chứa lệnh Solver. Sau khi đã Add-Ins công cụ Slover vào Excel, kế đến ta thực hiện giải bài toán lập kế hoạch sản xuất để tối ưu hóa lợi nhuận. Việc xây dựng bài toán trong Excel cũng tương tự như việc xây dựng bài toán khi chúng ta tiến hành giải thủ công thông thường. Sau khi phân tích đầu bài chúng ta cần viết được hàm mục tiêu và các ràng buộc của bài toán rồi tiến hành tổ chức dữ liệu vào bảng tính. Ta xét ví dụ bài toán lập kế hoạch sản xuất đã trình bày ở trên: Hàm mục tiêu: f(x) = 8x1+ 6x2+ 0x3 +0 x4 max Điều kiện ràng buộc: Trang 7
8. 4 1 + 2 2 + 3 = 60 {2 1 + 4 2 + 4 = 48 1, 2, 3, 4 ≥ 0 Tổ chức dữ liệu trên Excel Biến quyết định: được nhập tại các ô B7:E7. Cho các giá trị khởi động là 0. Hàm mục tiêu f(x): có giá trị căn cứ vào giá trị khởi động của các biến. Công thức tại ô F8. Các ràng buộc: nhập các hệ số của các quan hệ ràng buộc tại các ô B10:E11. Tính vế trái của các ràng buộc theo công thức tại các ô F10:F11. Nhập các giá trị vế phải của các ràng buộc tại các ô G10:G11. Theo bảng sau: Tiến hành giải bài toán (1) Chọn ô F8 và chọn Data | Solver. Bảng hộp thoại Solver Parameters xuất hiện và gồm các thông số sau: Trang 8
9. Trong đó: Set Tanget Cell: Nhập ô chứa địa chỉ tuyệt đối của hàm mục tiêu. Equal To: Xác định giới hạn cho hàm mục tiêu hoặc giá trị cần đạt đến của hàm mục tiêu: Max, Min hay Value of tuỳ thuộc vào yêu cầu của bài. By Changing Cells: Nhập địa chỉ tuyệt đối của các ô ghi các giá trị ban đầu của biến. Subject to the Constraints: Nhập các ràng buộc của bài toán. Cách làm của Solver là thay đổi giá trị của các biến tại By Changing Cells cho đến lúc giá trị của hàm mục tiêu tại Set Tanget Cell đạt một giá trị quy định tại Equal To và đồng thời thoả mãn tập các ràng buộc tại Subject to the Constraints. Với bài toán trên, ta tiến hành khai báo các thông số cho Solver như sau: Địa chỉ của hàm mục tiêu F8 được đưa vào Set Target Cell Chọn Max tại Equal To để Solver tìm lời giải cực đại cho hàm mục tiêu. Nhập địa chỉ của các biến quyết định B7:E7 tại By Changing Cells. Thêm các ràng buộc vào Subject to the Contraints: Nhấp nút Add, bảng Add Constraint xuấ thiện và gồm các thông số sau: Cell Reference: Ô hoặc vùng ô chứa công thức của các ràng buộc. Trang 9
10. Ô dấu: Cho phép ta lựa chọn dấu của các ràng buộc tương ứng. Constraint: Ô chứa giá trị vế phải của các ràng buộc tương ứng (ta cũng có thể nhập trực tiếp giá trị vế phải của ràng buộc tương ứng). Với bài toán trên, các ràng buộc được nhập như sau: + Các ràng buộc về dấu: do xj≥ 0, j = 1÷ 4 (các ràng buộc đều có dạng ≥) nên ta chọn vùng địa chỉ chứa biến B7:E7 vào Cell Reference, chọn dấu ≥ và nhập 0 vào Constraint: Chú ý: Nếu bài yêu cầu ràng buộc (xj) là nguyên thì trong ô dấu ta chọn int, nếu là kiểu nhị phân ta chọn bin. + Tiếp tục chọn Add để nhập tiếp các ràng buộc phương trình và bất phương trình: Cell Reference Ô dấu Constraint F10 = G10 F11 = G11 Chọn OK để kết thúc việc khai báo các ràng buộc. Tuy nhiên, muốn hiệu chỉnh ràng buộc ta chọn ràng buộc và chọn Change, xoá ràng buộc ta chọn ràng buộc từ danh sách Subject to the Contraints và nhấp Delete. Trang 10
11. Sau khi hoàn tất ta chọn Solve để chạy Solver, hộp thoại kết quả xuất hiện và cho ta hai sự lựa chọn sau: Trang 11
12. Keep Solver Solution: Giữ kết quảvà in ra bảng tính. Restore Original Values: Huỷ kết quả vừa tìm được và trả các biến về tình trạng ban đầu. Save Scenario: Lưu kết quả vừa tìm được thành một tình huống để có thể xem lại sau này. Ngoài ra có 3 loại báo cáo là Answer, Sensitivity và Limits. Ở ví dụ này ta chọn Keep Solver Solution, OK. Bảng kết quả nhận được như sau: Như vậy phương án cực biên tìm được là X=(12, 6, 0, 0) và giá trị cực đại của hàm mục tiêu f(x) là 132. Trang 12
13. IV. KẾT QUẢ ĐẠT ĐƯỢC Sử dụng công cụ Slover trong phần mềm Excel để giải quyết các bài toán quy hoạch tuyến tính rất dễ dàng và hiệu quả. Cụ thể: - Tiết kiệm được thời gian so với phương pháp thủ công - Chỉ vài cú click chuột - Không sử dụng hàm trong Excel - Dễ dàng tìm được phương án cực biên và giá trị của hàm mục tiêu V. KẾT LUẬN Đây là đề tài của tôi trong quá trình công tác và nghiên cứu các ứng dụng mới nhằm đáp ứng nhu cầu học tập của sinh viên cũng như nhu cầu tìm lời giải tối ưu cho các cơ quan xí nghiệp nhằm tạo ra các sảm phẩm với lợi nhuận cao mà chi phí vận liệu có hạn. Qua đây tôi rất mong nhận được nhiều ý kiến từ các đồng nghiệp, hội đồng khoa học để tôi tiếp tục hoàn thiện và có thể áp dụng đưa vào giảng dạy. Rạch Giá, ngày 15 tháng 05 năm 2016 Trang 13