Solver và các bài tóan quy hoạch tuyến tính

[handung107]

Solver là một công cụ cao cấp của Excel, nhưng chắc các bạn ít người sử dụng. Thật ra, trong kế toán hàng ngày, với các bài toán quy hoạch tuyến tính đơn giản, bằng nhiều cách khác nhau, ta có thể tự tìm ra những gì cần giải, mà không cần dùng đến Solver, nhưng nếu ta hiểu thêm về Add-in này, chắc chắn sẽ không thừa đâu, các bạn à.

Trên diễn đàn, chưa có bài nào về Solver hoàn chỉnh, hôm nay, tôi sẽ giới thiệu với các bạn bằng những thí dụ cụ thể nhất để các bạn có thể áp dụng vào các bài toán hàng ngày

Bài toán 1 :

- Một xưởng sản xuất làm 3 sản phẩm : TV, máy Cassete, loa. Mỗi sản phẩm được lắp ráp từ những phụ kiện có sẵn trong kho. Có 5 loại vật tư phụ kiện : khung máy, đèn hình, bộ loa, bộ nguồn, bảng mạch điện tử. Mục tiêu là sản xuất đầy đủ các sản phẩm để có lãi nhiều nhất với số vật tư phụ kiện còn tồn trong kho.
Số vật tư tồn đầu kỳ là : 450 khung máy, 250 đèn hình, 800 bộ loa, 450 bộ nguồn và 600 bảng mạch điện tử.

Định mức cho :

- TV : 1 khung, 1 đèn hình, 2 bộ loa, 1 bộ nguồn, 2 bảng mạch điện tử
- Cassette : 1 khung, 2 bộ loa, 1 bộ nguồn, 1 bảng mạch điện tử
- Loa : 1 bộ loa, 1 bảng mạch điện tử

Lãi cho mỗi sản phẩm được dự tính là TV 75đ, Cassette 50đ, loa 35đ

Với đại số, chúng ta sẽ thiết lập các phương trình tuyến tính như sau :

Gọi x1 là số lượng TV, x2 là số lương Cassette, x3 là số lượng loa sản xuất. Ta có :

Tổng số lãi : L = 75x1 + 50x2 + 35 x3
Các điều kiện của bài toán là :

- 1x1 + 1x2 + 0x3 <=400 (khung máy)
- 1x1 + 0x2 + 0x3 <=200 (đèn hình)
- 2x1 + 2x2 +1x3 <=800 (bộ loa)
- 1x1 + 1x2 + 0x3 <=400 (bộ nguồn)
- 2x1 + 1x2 + 1x3 <=600 (bảng mạch điện tử )
Vì số san phẩm sản xuất x1, x2, x3 phải là số dương nên ta cũng có điều kiện là x1 >=0; x2>=0; x3>=0

Các bạn thấy đó, nếu giải bằng đại số...thực sự "phê" đấy. Chúng ta có thể nhờ Excel giải giùm bằng Solver

[handung107]

Bây giờ, chúng ta sẽ thiết lập mô hình bảng tính trogn Excel

Cách nhanh nhất (tuy không phải là tốt nhất), bạn sẽ đặt :
- A1 : giá trị của x1, ta gõ số 0 (vì chưa biết nghiệm số)
-A2 : giá trị của x2, cũng gõ 0
- A3 : giá trị của x3, gõ 0
- A4 : tổng số lãi thu được, ta gọi đây là hàm mục tiêu (HMT)
A4 = 75*A1 + 50*A2 + 35*A3

Tiếp theo, từ B1 đến B5, ta nhập các điểu kiện của phương trình

B1 = 1*A1 +1*A2 + 0*A3 (= A1 + A2) (khung máy)
B2 = A2 (đèn hình)
B3 = 2*A1 + 2*A2 + 1*A3 (bộ loa)
B4 = A1 + A2 (bộ nguồn)
B5 = 2*A1 + A2 + A3 (bảng mạch điện tử)

Đối thoại với Solver :

Ta đặt con trỏ ngay Cell A4 (HMT), và mở hộp thoại Solver Parameter bằng cách sử dụng Menu Tools / Solver. Nếu bạn không thấy Solver trong Menu này, bạn phải vào Tools / Add-in, đánh dấu kiểm vào Solver trong hộp thoại liệt kê DS các Add-in đã được cài vào Excel của bạn. Nếu bạn cũng không thấy ở đây, thì hoặc bạn nhấp vào nút Browse, tìm đường dẫn đến thư mục có Add-in này, hoặc bạn đã bỏ qua không cài nó khi cài Office. Trường hợp này, bạn phải tìm dĩa Office để cài thêm thôi

Khi hộp thoại Solver Parameter xuất hiện, bạn sẽ thấy các mục như sau :

- Set Target Cell : tại bảng tính như trên là A4, nếu các bảng khác, nó chính là HMT (hàm mục tiêu ta muốn tìm)
- Lựa chọn Max từ các Option, đúng cho trường hợp này
- Click chuột vào nút Guess, sẽ xuất hiện cửa sổ và bạn sẽ thấy A1:A3 (tức là các Cell liên quan đến A4)
- Bây giờ ta đưa các điểu kiện vào bằng cách nhấp nút Add --> Add Constraint
- Như vậy, tại Cell Reference, các bạn nhập địa chỉ các ô chứa các điều kiện, còn Constraint các bạn nhập điều kiện liên quan, giữa 2 hộp này, bạn sẽ chọn các điều kiện tương ứng như <=, <, =, >=, >
- thí dụ : Cell Reference nhập A1 :A3, nhấp mũi tên chọn >=, Constraint nhập số 0
- Nhấp Add, tiếp tục Cell Refernce nhập B1, Constraint nhập 400, chọn <=
- Tương tự cho đến B5
- Nhấp OK, trở lại hộp thoại Solver, bạn vào Options. Trên hộp thoại này, bạn đánh dấu vào khung kiểm tra "Assume Linear Model" (chuyển sang mô hình tuyến tính)
- Bây giờ, bạn nhấp Solve để Excel tìm các nghiệm vào A1, A2, A3
- Còn lại, các bạn sẽ hiểu cần làm gì rồi...

[handung107]

1/ Khai báo nhiều biến trong hộp thoại Solver

Trong hộp thoại "By Changing Cells" để khai báo biến cho mô hình, ta có thể :
- Gõ từ bàn phím tọa độ các vùng, mỗi vùng ngăn cách nhau bằng dấu phẩy
- Nhấp chuột, đồng thời giữ phím Ctrl để chọn các vùng biến

2/ Khai báo điều kiện ràng buộc :

- Với mô hình tuyến tính đơn giản này, vế trái của điều kiện luôn ở "Cell rẻence" như là các ô tham chiếu đơn lẻ, vế phải "Cóntraint" như là các hằng số. Tuy vậy, bạn có thể đưa vế trái là một vùng, một cột, nhưng không cho phép bạn nhiều lựa chọn cùng lúc
- Điều kiện ràng buộc bên vế phải cũng là một vùng phải có kích thước tương đương như vậy
- Với thí dụ trên, bạn có thể đưa vào cả vế trái vùng B1:B5, nhưng bạn phải nhập các số tương đương 400, 600, 800...vào một vùng khác C1:C5 chẳng hạn và đưa vào vế phải

3/ Tránh trùng lặp và xung đột khi khai báo điều kiện :

- Nếu ta khai báo ràng buộc cả cận trên lẫn cận dưới cho cùng một Cell thì Solver sẽ dùng cận chặt hơn. TD : Khi ta khai báo B1<=10 và B1<=5 thì Solver sẽ dùng B1<=5
- Nếu ta dùng ràng buộc cả <= và >= cho cùng một biến quyết định thì Solver sẽ báo lỗi khi ta chạy chương trình

[tuankietdhkt]

tại sao solver không tìm ra giải pháp tối ưu mà hiển thị bảng" the set cell values do not convêrg" Mong mọi người chỉ cách giải quyết.

[nothingtolove]

Dear Mr.handung107,

Mình đang mày mò nghiên cứu Solve, thấy ví dụ của bác hay hay nên thử làm.
Tuy nhiên, theo như ý bác các đkiện x1,x2,x3>=0 thì mình thấy ko đúng, vì yêu cầu của bài toán là sản xuất ra tất cả sản phẩm, do vậy x1,x2,x3 phải >=1 mới hợp lý.
Mình thử chọn đkiện: x1,x2,x3 >=0 như bác thì sản phẩm là TV 200, Casette 200, Loa 0 --> Sai với yêu cầu.
Nhưng nếu chọn đkiện: x1,x2,x3 >=1 thì TV lại là số lẻ 199.5 Cassette 200 Loa 1, còn các phụ kiện thì cũng số lẽ.
Như vậy phải thêm hàm ràng buộc các số đó phải là số nguyên, nhưng mình lại ko biết. Bác có cách nào ko? Share mình với.
Bài toán này đã lâu rồi, ko biết bác còn nhớ ko?

[gtri]

Bản solver hiện tại chỉ giải được 200 ẩn, nghe nói có phiên bản mới giải được nhiều ẩn hơn không biết có đúng không. Bác nào có giới thiệu cho tôi với

[TranThanhPhong]

Bản solver hiện tại chỉ giải được 200 ẩn, nghe nói có phiên bản mới giải được nhiều ẩn hơn không biết có đúng không. Bác nào có giới thiệu cho tôi với

Bạn có thể vượt qua giới hạn trên bằng Add-Ins Premium Solver hỗ trợ 2000 biến quyết định (đối với bài toán tuyến tính) và 500 cho bài toán phi tuyến tính.

Nếu bài toán quá lớn thì có thể sử dụng Premium Solver Platform hỗ trợ 8000 tới biến.

TTP.

[gtri]

Bản mới này không biết có đĩa CD cài đặt không hả bạn, tải trên mạng xuống quả thực là tôi không biết cách. Tôi đang sử dung solver trong excel 2003 để tính toán gặp giới hạn 200 ẩn thì bế tắc, có cách nào cập nhật 2 bản mới làm ơn bạn chỉ giùm. Cảm ơn bạn đã chỉ đường

[vietcauduong]

Mình có một bài toán nhờ các bạn giúp đỡ làm trong solver để tính tối ưu đoạn thép cắt là ít nhất:Cây thép dài 11,7m cần cắt ra thành nhìu đoạn có chiều dài khác nhau như x1, x2, x3...=constans
Làm sao tổng V= x1+x2+x3+...<=11,7;MaxV?cám ơn nhìu!

[vietcauduong]

x1, x2, x3....=constans