PDA

View Full Version : EXCEL - Giải bài toán quy hoạch tuyến tính bằng phương pháp đơn hình



handung107
29-09-06, 12:23 AM
TuanVNUI

Nếu ai đã học khối các trường kinh tế chắc đã trải qua môn toán kinh tế, thật là khó phải không. Mình gửi lên đây file Excel giải bài toán kinh tế bằng thuật toán đơn hình.

Thông tin về chương trình:
+ Giải theo dạng bài toán chưa biết trước phương án cực biên xuất phát.
+ Số nghiệm tối đa 8 nghiệm.
+ Giải bài toán Max/Min.
+ Dùng phương pháp biến giả.

Xin tặng các bạn là sinh viên các trường kinh tế, các bạn đang chuẩn bị khoá học sau Đại học hoặc những bạn đang quan tâm tới toán kinh tế.

Đây là phiên bản đầu tiên 1.0 mình đã viết cách đây một năm, trong sheet dữ liệu đã có 21 đề (phần lớn trong quyển "Toán kinh tế"- ĐHKTQD và các đề thi cao học mấy năm gần đây). Chương trình này sẽ còn phát triển ở các phiên bản tiếp sau.

bds_thang
01-06-08, 11:26 PM
ko chạy được thế hả bac handung107? Bác xem lai đi chứ thế nầom em nhập giữ liệu vao ko kich đc, mới lại mới cái dấu >= hay <= và = ko thay đổi lại đc cho nhau.Hay bị viruts hả bác ?

Bui Duyên
09-02-09, 10:48 PM
Bac handung107 có thể hướng dẫn cụ thể hơn về cách nhập dữ liệu bài vào để giải BT được không a? cảm ơn bác nhiều nhiều

Nguyễn Duy Tuân
10-02-09, 09:16 AM
Các bạn không chạy được có lẽ do máy tính đang cài BKAV nên đã xoá macro của nó tồi. Nếu đang dùng BKAV, hãy mở và bỏ chọn chế độ "Diệt Macros" sau đó bạn download lại rồi chạy.

Khi đã chạy, tại giao diện nhập liệu bạn hãy nhập dữ liệu bài toán.
+ Vào các hệ số (C) của X1, X2,... rồi xác định bài toán Min hay Max phải dùng chuột để chọn.

+ Vào các hệ số của của ma trận (A) tướng ứng với các thành phần X1, X2,..
+ Vào các ràng buộc về dấu của bài toán ứng với X1, X2,....
+ Chọn Giải là xong.

Nếu bạn chưa rõ về những chỉ dẫn trên, hãy chọn nút "Mở bài tập" để xem cách nhập liệu.

VTD_XD
05-04-09, 09:58 PM
File này đã khóa sheet nên không thể thay đổi dấu ">=, =, <=" được, bác Handung107 thử xem lại xem

Nguyễn Duy Tuân
05-04-09, 10:21 PM
File này đã khóa sheet nên không thể thay đổi dấu ">=, =, <=" được, bác Handung107 thử xem lại xem

Bạn hãy dùng chuột để chọn.

VTD_XD
05-04-09, 10:37 PM
http://i705.photobucket.com/albums/ww52/vtd_xd/123.jpg

Nguyễn Duy Tuân
06-04-09, 09:15 AM
Thay đổi chính:
+ Bài toán QHTT giải với số biến (thật + giả) lên tới 11 biến.
+ CHữa một vài lỗi nhỏ của phiên bản trước

xuanhoa7604
29-04-09, 09:22 PM
Muốn thêm điều kiện thì làm thế nào vậy bạn?

nguyentuhp
29-04-09, 10:34 PM
Muốn thêm điều kiện thì dùng SOLVER: 250 biến, 250 điều kiện!
Còn bạn muốn dùng >1.000 biến thì dùng thư viện mở này:
https://sourceforge.net/project/showfiles.php?group_id=145213&package_id=159735

minhdiep
21-09-09, 03:28 PM
Bác ơi - nó yêu cầu Pass - em chịu không làm thế nào được

thach a na
06-10-09, 01:20 PM
tôi vẫn không thể nhập dữ liệu vào phần mềm giải toán quy hoạch tuyến tính. Phải làm sao? xin hướng dẫn dùm. Cảm ơn.

Nguyễn Duy Tuân
06-10-09, 01:30 PM
bạn vào phần "Mở bài tập" để xem cách nhập nhé.

connguahoang89
04-11-09, 10:39 AM
anh ơi.giải thích rõ thêm cho em về cách tính bảng đơn hình với.thanks nha.em mới học nên chưa rõ lắm

loveforht87
05-12-09, 02:41 PM
Thay đổi chính:
+ Bài toán QHTT giải với số biến (thật + giả) lên tới 11 biến.
+ CHữa một vài lỗi nhỏ của phiên bản trước
Mình có vấn đề muốn hỏi bạn, trong File đính kèm nhé. Mong nhận được hồi âm sớm!

Nguyễn Duy Tuân
30-01-10, 10:18 PM
Mình có vấn đề muốn hỏi bạn, trong File đính kèm nhé. Mong nhận được hồi âm sớm!

Yêu cầu:
Xác định X=[X1, X2, X3] sao cho:
F(X)= 3X1-2X2+X3→ min
Với
5X1+4X2+3X3=12
4X1+2X2+X3≤10
Xj≥0 (j=1,3)
Đáp án:
- Min F(X)=-6, với tập nghiệm X=[0,3,0]
Thắc mắc:
- Nếu trong file Excel điền các hệ số trực tiếp như trong Sheet Bode (Cách làm trực tiếp) mà mình “Cất” lại thì ra nghiệm đúng X=[0,3,0], nhưng mình phân vân cách đặt ẩn giả của bạn, không giống với ý mình?
- Với bài toàn này, bọn mình đặt X4 là ẩn giả, X5 là ẩn phụ nên Bài toán ban đầu được viết dưới dạng:
F(X)= 3X1-2X2+X3+MX4+0X5→ min
Với
5X1+4X2+3X3+X4 =12
4X1+2X2+X3 +X5=10
- Khi đó đưa các hệ số này vào trong File Excel thì bài toán vô nghiệm, tại sao vậy?
- Cách quy ước ẩn giả của bạn là thế nào vậy? Làm thế nào để quy định 1 ẩn là ẩn giả? Trong bảng đơn hình bỏ các biến không dùng trong Bài toán thế nào?



Chào bạn,

Bài toán QHTT mình giải theo phương pháp dùng biến giả. Sơ lược về phương pháp này như sau:

+ Cộng (+), hoặc trừ (-) "biến bù" (X) nếu ràng buộc của nó là <= hoặc >= . Mục đích để tạo ra đẳng thức (=).
+ Sau khi đã tạo ra các biến bù (bước trên) mà vẫn chưa lấy được phương án cực biên xuất phát (ma trận đơn vị) thì tạo thêm các biến giả (Xg) ở những ràng buộc chưa có vecto cột đơn vị.

Các biến Xj >=0, Xgj >=0 (j = 1-n)

Đúng ra khi đã đưa bài toán biến giả thì phải viết lại bài toán Y
Y = Xg1 + Xg2 + ...Xgn -> Min (luôn đạt Min với bài toán biến giả)

Quá trình giải bài toán trên bảng đơn hình qua các bước để loại biến giả (Xg) ra khỏi bảng, khi đó bài toán trở về dạng ban đầu (tìm được phương án cực biên của bài toán đã cho). Nếu không loạdduwwocj biến Xg -> Bài toán vô nghiệm.
Sau khi biến giả đã được loại bỏ mà bảng đơn hình cuối cùng tìm được nghiệm thì kết luận phương án cực biên tối ưu (PACBTU) của bài toán. Lưu ý , PACBTU của bài toán đã cho ta chỉ viết những nghiệm của bài toán gốc, tức là trong nghiệm không viết những biến bù và biến giả vào. Nếu kiểm tra lại thì phải thay các biến X vào ràng buộc của bài toán gốc (bài toán ban đầu) chứ không thay vào bài toán sau khi đã biến đổi.


- Với bài toàn này, bọn mình đặt X4 là ẩn giả, X5 là ẩn phụ nên Bài toán ban đầu được viết dưới dạng:
F(X)= 3X1-2X2+X3+MX4+0X5→ min
Với
5X1+4X2+3X3+X4 =12
4X1+2X2+X3 +X5=10


Bạn đặt biến chưa chính xác. Nó phải được đặt như sau:
- X4 là ẩn phụ, X5 là ẩn giả. Bài toán ban đầu được viết dưới dạng:

Y = X5g -> Min

Với
5X1+4X2+3X3 + X5g =12
4X1+2X2+X3 + X4 =10

Bài toán này giải ra được X = (0, 3, 0) thay vào các ràng buộc của bài toán ban đầu đều thỏa mãn - > Nó là PACBTU.

Cách bài toán QHTT có 2 kiểu là dùng bài toán "M" hoặc "biến giả". Năm 1995 mình cũng học phương pháp này nhưng sau đó các thày đổi sang bài toán "biến giả" (các thày bảo đây là phương pháp mới) và mình thấy hay nên từ đó dùng phương pháp này để làm. Bạn có thể tham khảo các tài liệu "Toán tối ưu"; "Bài toán quy hoach tuyến tính" + "Phương pháp biến giả".

Nguyễn Duy Tuân
20-05-11, 04:41 PM
bạn ơi! thế còn trường hợp biến không ràng buộc về dấu thì làm thế nào?

Cách giải là chúng ta đặt Xn = Xn1' - Xn2' = 0, với Xn1, Xn2 >=0. Tuy nhiên do thoài gian có hạn nên tôi chưa lập trình cho trường hợp này, hy vọng sau này sẽ hoàn thiện hơn.

Nguyễn Duy Tuân
20-05-11, 04:43 PM
mình cũng không tương tự như bạn, chẳng sử dụng được!!!!Cấp cứu

File có sử dụng VBA/Macro nên các bạt phải vào menu Tools->Macro->Security chọn Low hoặc Meduim (chọn Enabled Macros khi mở file).

Các dấu của các ràng muộc bạn hãy dùng chuột để chọn.

Nguyễn Duy Tuân
26-07-11, 04:49 PM
cái này có thể sai tốt trên iphone khong vậy

File Excel này có VBA nên hiện nay chưa chạy được trên các dòng điện thoại bạn à.

VitekB
14-03-12, 03:30 PM
Em vẫn không thể nào tải được ạ :(

KINDAICHI
11-08-12, 09:40 AM
Thay đổi chính:
+ Bài toán QHTT giải với số biến (thật + giả) lên tới 11 biến.
+ CHữa một vài lỗi nhỏ của phiên bản trước

Bạn có thể thêm ràng buộc chính có 4 ràng buộc trở lên không ? Trong file của bạn ràng buộc chính chỉ có 3 bất phương trình.

Nguyễn Duy Tuân
11-08-12, 11:27 AM
Bạn có thể thêm ràng buộc chính có 4 ràng buộc trở lên không ? Trong file của bạn ràng buộc chính chỉ có 3 bất phương trình.

Điều này hoàn toàn có thể làm được, nhưng thời gian này mình bận nên không có time để nâng cấp chương trình.

maichi93
22-10-12, 09:00 PM
bạn à. mình giải bài toán qhtt hệ ràng buộc có 4 pt. phải thêm slove. mình đưa slove ra rùi mà tiếp theo lam ntn mình k biết. nhờ bạn hướng dẫn mình đc k? mình dùng excel 2010.

livinglove
03-11-12, 02:11 PM
Trời ơi?
Sao mình ko thể chạy được vây?
Tải về rùi mà chạy được, ai giúp mình với?
huhu