Bài tập lớn Kỹ thuật ra quyết định cho kỹ sư - Đề tài: Giải bài toán quy hoạch tuyến tính bằng Exel - Đậu Hùng Cường

TRƯỜNG ĐẠI HỌC BÁCH KHOA TP.HCM
KHOA ĐIỆN – ĐIỆN TỬ
&œ
BÀI TẬP LỚN
KỸ THUẬT RA QUYẾT ĐỊNH CHO KỸ SƯ
	GVHD	: ThS. HỒ THANH PHƯƠNG
Sinh viên	: ĐẬU HÙNG CƯỜNG
MSSV	: 41100446
Nhóm	: A02-A
TP. HỒ CHÍ MINH
HỌC KỲ I NĂM HỌC 2014-2015
GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH BẰNG EXEL
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. Để rõ hơn, ta xét 1 ví dụ minh họa sau:
Ví dụ: Giải bài toán QHTT sau:
Hàm mục tiêu: 	 
Với các rằng buộc:	 
Nhập dữ liệu vào bảng tính:
Giá trị nghiệm: nhập vào tại các ô B7:F7. Cho giá trị nghiệm ban đầu là 0.
Hàm mục tiêu f(x): có các cơ số gắn với biến nhập tại các ô B8:F8, giá trị hằng số nhập ở ô G8. Công thức của hàm mục tiêu nhập ở ô H8 như sau: H8=B8*$B$7+C8*$C$7+D8*$D$7+E8*$E$7+F8*$F$7.
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:F12. Tính vế trái của các ràng buộc theo công thức tại các ô H10:H12 như sau:
H10=B10*$B$7+C10*$C$7+D10*$D$7+E10*$E$7+F10*$F$7
H11=B11*$B$7+C11*$C$7+D11*$D$7+E11*$E$7+F11*$F$7
H12=B12*$B$7+C12*$C$7+D12*$D$7+E12*$E$7+F12*$F$7
Nhập các giá trị vế phải của các ràng buộc tại các ô I10:I12.
	Kết quả sau khi nhập số liệu vào bẳng tính của ví dụ trên như sau:
	Sau khi đã nạp xong dữ liệu ta tiến hành giải bài toán.
Tiến hành giải bài toán:
Chọn ô H8 và chọn Data\Solver (đối với Microsoft Exel 2010). Bảng hộp thoại Solver Parameters sẽ xuất hiện với các thông số như sau:
Set Objectives: Nhập ô chứa địa chỉ tuyệt đối của hàm mục tiêu. 
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 Variable 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 Objectives đạt một giá trị quy định tại 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ụ thì ta tiến hành khai báo các thông số như sau:
Địa chỉ của hàm mục tiêu H8 được đưa vào Set Objectives
Chọn Max tại 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:F7 tại By Changing Variable 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ất hiệ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. 
Ô 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ụ ta nhập như sau:
Các ràng buộc về dấu: do xj ≥ 0, j = 1,,5 (các ràng buộc đều có dạng ≥) nên ta chọn vùng địa chỉ chứa biến B7:F7 vào Cell Reference, chọn dấu ≥ và nhập 0 vào Constraint:
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:
Constraint:
H10
=
I10
H11
=
I11
H12
=
I12
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 từ danh sách Subject to the Contraints 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.
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:
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ụ, ta chọn Keep Solver Solution, OK. Kết quả nhận được như sau:
	Như vậy, phương án cực biên tìm được của bài toán là :
X = (0, 11.333, 7.333, 0, 2)
	Và giá trị cực đại của hàm mục tiêu f(x) là 103.333.
GIẢI BÀI TOÁN MAX FLOW BẰNG EXEL
Tương tự với cách giải bài toán tuyến tính, chúng ta cũng sử dùng công cụ Solver của Exel để giải bài toán Max flow.
Để hiểu rõ hơn về cách giải, ta sẽ giải 1 ví dụ sau:
Ví dụ: tìm lượng hàng hóa cực đại được chuyển từ điểm S tới điểm T. 
Yêu cầu: không để hàng hóa ứ đọng lại trong mạng lưới; và hàng hóa được chuyển trong mỗi luồng không được vượt quá khả năng của luồng.
Sơ đồ được cho như hình sau:
Nhập dữ liệu vào bảng tính:
Tại cột from ta nhập tên các điểm xuất phát; và cột to ta nhập tên các đến. Trong mạng lưới có những đường truyền nào thì ta sẽ nhập vào hết.
Tại cột capacity ta nhập các giá trị khả năng của đường truyền tương ứng của điểm xuất phát tới điểm đến.
Cột node là tất cả các điểm có trong mạng lưới. Ở đây gồm có 10 điểm: điểm bắt đầu S, điểm kết thúc T, và 8 điểm trung gian được đánh số từ 1 tới 8.
Cột netflow ta nhập các hàm tính giá trị đi ra và đi vào của hàng hóa tại 1 điểm.
Tại ô I4 ta nhập hàm	=SUMIF(from,H4,flow)
	I5 nhập hàm	=SUMIF(from,H5,flow)-SUMIF(to,H5,flow)
	I6 nhập hàm	=SUMIF(from,H6,flow)-SUMIF(to,H6,flow)
	I7 nhập hàm	=SUMIF(from,H7,flow)-SUMIF(to,H7,flow)
	I8 nhập hàm	=SUMIF(from,H8,flow)-SUMIF(to,H8,flow)
I9 nhập hàm	=SUMIF(from,H9,flow)-SUMIF(to,H9,flow)
I10 nhập hàm	=SUMIF(from,H10,flow)-SUMIF(to,H10,flow)
I11 nhập hàm	=SUMIF(from,H11,flow)-SUMIF(to,H11,flow)
I12 nhập hàm	=SUMIF(from,H12,flow)-SUMIF(to,H12,flow)
I13 nhập hàm	=-SUMIF(to,H5,flow)
	Với from là tên gọi của các điểm xuất phát nhập ở các ô B4:B20
	to là tên gọi của các đến nhập ở các ô C4:C20
	flow là tên gọi của các giá trị hàng hóa trên đường đi, tính được ở các ô D4:D20
Cột supply/demand nhập các giá trị hàng hóa còn tồn đọng lại các điểm mà đề bài yêu cầu. Ở đây, không cho hàng hóa ứ đọng lại nên ta nhập giá trị 0.
Sau khi nhập xong ta có bảng như sau:
Tiến hành giải bài toán:
Ta tiến hành mở hộp thoại Solver Parameters lên.
Tại ô Set Objectives ta nhập giá trị $D$22 là giá trị maximum flow đã được gán bằng với giá trị ô I4.
Tại ô By Changing Variable Cells ta nhập ô chứa giá trị trên mỗi luồng cần tính là flow.
Các ràng buộc sẽ nhập như sau:
Ràng buộc về khả năng của đường truyền:
	Ràng buộc về lượng hàng tồn đọng lại trong mạng lưới:
Sau khi nhập nhập xong ta có hộp thoại sau:
Sau khi hoàn tất ta chọn Solve để chạy Solver và thu được kết quả sau:
Vậy giá trị cực đại của hàng hóa vận chuyển từ điểm S tới điểm T là 30. Và hướng đi như sau: