Vấn đề tối ưu hóa là những vấn đề trong quá trình làm bài tập, giải bài tập hay làm luận văn, tiểu luận mà chúng ta gặp phải trong nhiều môn học thuộc kỹ thuật, khoa học, kinh tế. Quá trình tối ưu hoá là tìm ra phương pháp hiệu quả nhất, sử dụng các nguồn lực hạn chế để đạt được mục tiêu của tình huống. Các vấn đề tối đa hóa lợi nhuận, tối ưu danh mục đầu tư như trong môn học Quản trị Danh Mục Đầu tư; Giảm thiểu chi phí, giảm thiểu tổng quãng đường đã đi như trong môn học Quản trị chuỗi cung ứng; Thiết kế mạng lưới cung ứng.... Show Một số ví dụ về bài toán tối ưu mà các bạn thường gặp như sau:
Phương pháp chung để giải quyết bài toán tối ưuĐối với bài toán đã cho, chúng ta sẽ xây dựng một mô tả toán học gọi là mô hình toán học để biểu diễn tình huống. Mô hình để tối ưu bao gồm các thành phần sau: Đặt tên biến quyết định: Các biến được biểu diễn bằng các ký hiệu như X1, X2, X3, ..Xn. Các biến này đại diện cho số lượng không xác định (số lượng mặt hàng để sản xuất, số tiền để đầu tư và vv). • Hàm mục tiêu: Mục tiêu của bài toán được biểu thị dưới dạng biểu thức toán học trong các biến quyết định. Mục tiêu có thể là tối đa hóa lợi nhuận, giảm thiểu chi phí, khoảng cách, thời gian, v.v. • Các hàm ràng buộc: Các hạn chế hoặc yêu cầu của vấn đề được thể hiện dưới dạng bất đẳng thức hoặc phương trình trong các biến quyết định.Nếu mô hình bao gồm hàm mục tiêu tuyến tính và các ràng buộc tuyến tính trong các biến quyết định, thì nó được gọi là mô hình tối ưu tuyến tính. Như vậy tối ưu tuyến tính là tối ưu mô hình với hàm mục tiêu tuyến tính và các ràng buộc tuyến tính. Thuật toán Simplex được phát triển bởi Dantzig (1963) được sử dụng để giải quyết các vấn đề tối ưu tuyến tính. Một số ví dụ sử dụng Excel SolverTrong bài viết này, Hocthue.net trình bày cách sử dụng mô hình hóa bảng tính và Excel Solver để giải quyết các vấn đề tối ưu tuyến tính. Bây giờ Hocthue.net trình bày cách sử dụng mô hình hóa sử dụng Excel để tìm giải pháp tối ưu cho các vấn đề tối ưu hóa. Ở mức đơn giản, nếu mô hình có hai biến, phương pháp đồ thị có thể được sử dụng để giải mô hình. Rất ít vấn đề trong thế giới thực chỉ liên quan đến hai biến. Đối với các vấn đề có nhiều hơn hai biến, chúng ta cần sử dụng các kỹ thuật phức tạp để tìm ra giải pháp tối ưu. Cách tiếp cận bảng tính và Solver làm cho việc giải các bài toán tối ưu hóa trở thành một nhiệm vụ đơn giản cho những sinh viên trong quá trình làm bài tập, làm tiểu luận liên quan đến tình huống tối ưu tuyến tính. Bước đầu tiên là tổ chức bảng tính để đại diện cho mô hình. Học Thuê.net sử dụng các ô riêng biệt để biểu diễn các biến quyết định, tạo công thức trong một ô để biểu diễn hàm mục tiêu và tạo công thức trong một ô cho mỗi ràng buộc bên trái. Khi mô hình được triển khai trong bảng tính, bước tiếp theo là sử dụng Solver để tìm giải pháp. Trong Solver, chúng ta cần xác định vị trí (ô) của hàm mục tiêu, các biến quyết định, bản chất của hàm mục tiêu (tối đa hóa / tối thiểu hóa) và các ràng buộc. Ví dụ 1: Bài toàn vận tải đơn giản: Bài toán được mô tả với dữ liệu đơn giản ở các bảng ở hình bên dưới như sau: Ở Bảng 1:Dữ liệu gồm có : Bên cung gồm 4 đơn vị là A, B, C, D với lượng hàng tương ứng 200... 500. Bên Cầu gồm có 6 khách hàng KH1..KH5. Ở Bảng 2: Kết quả tối ưu dựa trên sử dụng Solver của Excel với các điều kiện sau: Hàm mục tiêu (objective: Tối thiểu hoá chi phí ở I32 (hàng cuối cùng trong hình bên dưới). Ô thay đổi: Các ô màu vàng bên dưới. Hàm ràng buộc: - Bên gửi <=Bên cung - Bên nhận = Bên gửi. Bảng bài toán vận tải tối ưu với chi phí thấp nhất. Ví dụ 2: Tối ưu hoá danh mục đầu tư sử dụng Solver theo phương pháp Markowitz. Bài toán ở đây là nhà đầu tư muốn đầu tư 5 mã chứng khoán với kỳ vọng lợi nhuận đã có. Tuy nhiên câu hỏi đặt ra là tỷ lệ mỗi mã cổ phiếu bao nhiêu cho ít rủi ro nhất. Rủi ro ở đây được đo lường bằng phương sai nhé. 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 theo mục tiêu định trước là hết sức quan trọng. Nếu tất cả các yếu tố (biến số) 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 (QHTT) để 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 kinh tế việc giải bài toán QHTT thực hiện bằng thuật toán đơn hình. Trong phần mềm Excel sử dụng một công cụ cài thêm là Solver có thể giải bài toán tối ưu nhanh chóng. Các bài toán QHTT dạng chính tắc và dạng chuẩn chỉ là các trường hợp riêng bài toán QHTT dạng tổng quát. Vì thế ở đây ta sẽ xem xét cách giải quyết bài toán QHTT dạng tổng quát rồi từ đó áp dụng tương tự cho hai dạng còn lại.
Hình 1. Hộp thoại Add-ins chứa các chức năng mở rộng của Excel (2) Chọn Solver Add-Ins và chọn OK. 2. Xây dựng bài toán trong Excel 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ụ sau: Ví dụ 1: Cho bài toán QHTT sau: Hàm mục tiêu: f(x) = 2x 1 +8x 2 -5x 3 +15x 4 → max với ràng buộc: 3x 1 -x 2 +x 3 +10x 4 = x 1 +2x 2 +x 3 +5x 4 9 2x 1 +10x 2 +2x 3 -5x 4 26 x j 0, j = 1 4 là 0. Tổ chức dữ liệu trên bảng tính: ➢ Biến quyết định: được nhập tại các ô B7:E7. Cho các giá trị khởi động ➢ 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. 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 ví dụ 1 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. Hình 4. Khai báo hàm mục tiêu và các biến ➢ Thêm các ràng buộc vào Subject to the Contraints: Nhấp nút Add, bảng Add Constraint xuất hiện và gồm các thông số sau: Hình 5. Hộp thoại thêm các ràng buộc Cell Reference: Ô hoặc vùng ô chứa công thức của các ràng buộc. Ô 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 ví dụ 1 các ràng buộc được nhập như sau:
và nhập 0 vào Constraint: Hình 6. Thêm các ràng buộc 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.
Như vậy phương án cực biên tìm được là X=(0,3,0,0) và giá trị cực đại của hàm mục tiêu f(x) là 36.
Ta cần phải nắm vững một số thuật ngữ sau: 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 (ràng buộc lỏng). 5. Các lựa chọn bài toán Để thiết lập các thuộc tính cho Solver thì trong bảng Solver Parameters ta nhấp chuột vào Options hộp thoại Solver Options cho ta các lựa chọn sau: Hình 2 Thiết lập các thuộc tính cho Solver Max Time: Thời gian tối đa để giải bài toán là 32 giây (mặc định là 100 giây cho các bài toán đơn giản). Iterations: Số lần lặp tối đa để giải các bài toán là 32 lần(mặc định là 100 lần). Precision: Độ chính xác của bài toán (từ 0 đến 1, mặc định là 0, giá trị càng gần với 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. Tolerance: Chỉ áp dụng đối với các 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 nhanh (mặc định là 5%) Convergence: Chỉ áp dụng đối với các bài toán không tuyến tính. Khi tỉ số của giá trị tính toán ban đầu của ô đích đến giá trị tính toán hiện hành ít hơn giá trị đồng quy Solver ngừng việc tìm kiếm dù có tìm thấy lời giải hay không.
MỞ RỘNG BÀI TOÁN Việc ứng dụng mô hình QHTT trong quản lý kinh tế và quản trị doanh nghiệp là rất phổ biến. Chúng ta thường bắt gặp mô hình này trong các bài toán như: bài toán lập kế hoạch sản xuất tối ưu cho doanh nghiệp, bài toán phân bổ vốn đầu tư, bài toán dự trữ.. phần này xin trình bày 2 loại bài toán QHTT thông dụng nhất là: bài toán nguyên vật liệu và bài toán vận tải.
NVLi ai1 ai2 ... aij ... ain bi ... ... ... ... ... ... ... ... NVLm am1 am2 ... amj ... amn bm Lợi nhuận đơn vị c 1 c 2 ... cj ... cn Hãy tìm phương án sản xuất để tối đa hoá lợi nhuận. Bài giải: Gọi xj là lượng sản phẩm loại j mà nhà máy sẽ sản xuất nên x j 0. Do đó phương án sản xuất của nhà máy là vectơ x=(x 1 , x 2 ,...,xj,..,xn). Khi đó: Tổng chi phí nguyên vật liệu loại i để sản xuất x là j = 1 aij x j sẽ không vượtquá dự trữ bi: j = 1 aij x j biTổng lợi nhuận thu được khi sản xuất x là j = 1 c j x jVậy mô hình toán học của bài toán nguyên vật liệu có thể phát biểu theo mô hình bài toán QHTT như sau: Hàm mục tiêu: f(x)= j = 1 c j x j → maxCác ràng buộc: j = 1 aij x j bi ,i = 1, mx j 0, j = 1, n n n n n n Hình 10. Lập bài toán trên bảng tính B2: Giải bài toán:
Hình 11. Khai báo các thông số của bài toán
Phương án tối ưu (phương án cực biên) là x = (200, 0, 0, 0, 200) với f(x) max = 124 000. Hay phương án sản xuât tối ưu của nhà máy là sản xuất 200 đơn vị sản phẩm 1 và 200 đơn vị sản phẩm 5 khi đó lợi nhuận tối ưu đạt được là 124 000 đơn vị tiền tệ. Không có nguyên liệu nào bị lãng phí. 2. Bài toán vận tải ➢ Bài toán tổng quát: Có m kho hàng cùng chứa một loại hàng hoá, lượng hàng có ở kho i là ai (i = 1, m).Có n địa điểm tiêu thụ loại hàng nói trên, với nhu cầu tiêu thụ ở điểm j là bj (j = 1, n).n i= 1 xij = bjxij 0,i = 1, m, j = 1, n Ta thấy ngay được điều kiện cần và đủ để bài toán vận tải có phương án tối ưu là tổng tất cả các lượng hàng tiêu thụ bằng tổng tất cả các lượng hàng ở các kho, nghĩa là: i= 1 ai = j = 1 bj➢ Ví dụ 3 Sử dụng công cụ Solver như đã trình bày ở trên hãy lập phương án vận chuyển xăng tối ưu từ 4 kho đến 5 trạm xăng bán lẻ của một công ty kinh doanh xăng dầu khu vực V. Bài giải: B1: Xây dựng bài toán Gọi xij là lượng hàng vận chuyển từ kho i đến điểm tiêu thụ j nên xij 0,i = 1,4, j = 1,. Hàm mục tiêu: f(x) = 30x 11 + 27x 12 + 26x 13 + 9x 14 + 23x 15 + 13x 21 + 4x 22
m m x 13 + x 23 + x 33 + x 43 <= 7 x 14 + x 24 + x 34 + x 44 <= 7 x 15 + x 25 + x 35 + x 45 <= 2 Tổ chức dữ liệu trên bảng tính như sau: Hình 12. Tổ chức bài toán trên bảng tính Bước 2: Tiến hành giải bài toán Chọn ô B16 rồi dùng lệnh Tools\Solver |
