Bài tập lớn Kỹ thuật ra quyết định cho kỹ sư

Kỹ thuật ra quyết định cho kỹ sư

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

Nhóm

: 41100446

: A02-A

TP. HỒ CHÍ MINH

HỌC KỲ I NĂM HỌC 2014-2015

Đậu Hùng Cường – 41100446

Page 1

Kỹ thuật ra quyết định cho kỹ sư

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:

f (x)  2x₁ 6x₂ 4x₃ 2x₄ 3x₅ max

Hàm mục tiêu:

x  2x  4x  50



1

2

3





4x  2x  x  60

2

3

4

3x₂ x₅ 36

Với các rằng buộc:





x_j 0, j 1,...,5.

1. 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.

Đậu Hùng Cường – 41100446

Page 2

Kỹ thuật ra quyết định cho kỹ sư

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.

2. 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:

Đậu Hùng Cường – 41100446

Page 3

Kỹ thuật ra quyết định cho kỹ sư

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.

Đậu Hùng Cường – 41100446

Page 4

Kỹ thuật ra quyết định cho kỹ sư

➢ 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 x_j≥ 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

H11

H12

=

I10

I11

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.

Đậu Hùng Cường – 41100446

Page 5

Kỹ thuật ra quyết định cho kỹ sư

-

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:

Đậu Hùng Cường – 41100446

Page 6

Kỹ thuật ra quyết định cho kỹ sư

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.

Đậu Hùng Cường – 41100446

Page 7

Kỹ thuật ra quyết định cho kỹ sư

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:

1. 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.

Đậu Hùng Cường – 41100446

Page 8

Kỹ thuật ra quyết định cho kỹ sư

Tại ô I4 ta nhập hàm

=SUMIF(from,H4,flow)

I5 nhập hàm

I6 nhập hàm

I7 nhập hàm

I8 nhập hàm

I9 nhập hàm

I10 nhập hàm

I11 nhập hàm

I12 nhập hàm

I13 nhập hàm

=SUMIF(from,H5,flow)-SUMIF(to,H5,flow)

=SUMIF(from,H6,flow)-SUMIF(to,H6,flow)

=SUMIF(from,H7,flow)-SUMIF(to,H7,flow)

=SUMIF(from,H8,flow)-SUMIF(to,H8,flow)

=SUMIF(from,H9,flow)-SUMIF(to,H9,flow)

=SUMIF(from,H10,flow)-SUMIF(to,H10,flow)

=SUMIF(from,H11,flow)-SUMIF(to,H11,flow)

=SUMIF(from,H12,flow)-SUMIF(to,H12,flow)

=-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:

Đậu Hùng Cường – 41100446

Page 9

Kỹ thuật ra quyết định cho kỹ sư

2. 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:

Đậu Hùng Cường – 41100446

Page 10

Kỹ thuật ra quyết định cho kỹ sư

- Sau khi nhập nhập xong ta có hộp thoại sau:

Đậu Hùng Cường – 41100446

Page 11

Kỹ thuật ra quyết định cho kỹ sư

- 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:

Đậu Hùng Cường – 41100446

Page 12