TRƯờNG ĐạI HọC VINH
KHOA TOáN
--------------
lê thị thu hiền
ứNG DụNG PHầN MềM MICROSOFT OFFICE EXCEL
Để GIảI BàI TOáN QUY HOạCH TUYếN TíNH
KHóA LUậN TốT NGHIệP ĐạI HọC
NGàNH TOáN TIN Học ứNG DụNG
VINH 2010
TRƯờNG ĐạI HọC VINH
KHOA TOáN
--------------
lê thị thu hiền
ứNG DụNG PHầN MềM MICROSOFT OFFICE EXCEL
Để GIảI BàI TOáN QUY HOạCH TUYếN TíNH
KHóA LUậN TốT NGHIệP ĐạI HọC
NGàNH TOáN Tin học ứNG DụNG
Cán bộ hớng dẫn khóa luận
Th.S. Nguyễn Thị Thanh Hiền
Sinh viên thực hiện: Lê Thị Thu Hiền
3.1. Bài toán lập kế hoạch sản xuất.. 28
3.2. Bài toán vận tải.................. 33
3.3. Giải bài toán quy hoạch phi tuyến. 37
Kết luận 40
Tài liệu tham khảo.. 41
Mở ĐầU
Thực tế hiện nay, sự cạnh tranh 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. Đặc biệt, 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 để mô tả, phân
tích và tìm lời giải cho vấn đề lựa chọn tối u. Trong đó phơng pháp đơn hình đợc
George Bemanrd Dantzig đa ra năm 1947 cùng lúc với việc khai sinh ra quy hoạch
tuyến tính, phơng pháp này thực sự có hiệu quả để giải những bài toán quy hoạch
tuyến tính cỡ lớn trong thực tế mà ta thờng gặp, nh để vận chuyển hàng hóa đầy đủ
nhng có tổng chi phí là nhỏ nhất đây chính là bài toán vận tải. Hoặc trong kinh
doanh phải lập kế hoạch sản xuất đối với các nguyên liệu và sản phẩm để thu đợc
tổng lợi nhuận là lớn nhất
Tuy nhiên, trong thực tế công việc này lại khá phức tạp, gây không ít khó khăn
và lúng túng cho những đối tợng quan tâm đến nó. Để giải quyết vấn đề này, trong
phần mềm ứng dụng Microsoft Office Excel sử dụng một công cụ cài thêm là
Sover có thể giải các bài toán tối u nhanh chóng. Solver là một chức năng tính toán
trong Microsoft Excel. Nó chủ yếu đợc sử dụng để xác định giá trị tối đa hay tối
thiểu của một mục tiêu đợc xếp vào một ô trong bảng tính Excel. Trong tối u hóa,
BàI TOáN QUY HOạCH TUYếN TíNH
1.1. Bài toán
Xét bài toán quy hoạch tuyến tính tổng quát:
min {f(X) =}
với điều kiện
Trong trờng hợp đặc biệt, bài toán quy hoạch tuyến tính có dạng:
min{f(X)=}
(1.1)
với điều kiện
Bài toán có dạng (1.1)(1.2)(1.3) đợc gọi là bài toán quy hoạch tuyến tính dạng
chính tắc.
Chú ý rằng bài toán quy hoạch tuyến tính tổng quát có thể đa về bài toán quy
hoạch tuyến tính dạng chính tắc tơng đơng nhờ các quy tắc sau đây.
+ Nếu có bất đẳng thức hoặc thì ta đa thêm ẩn phụ xn+i 0, với hệ số hàm mục
tiêu cn+i = 0 để có
hoặc bi .
+ Nếu có ẩn xk cha ràng buộc về dấu, thì có thể thay nó bởi hai biến mới và
không âm, với xk = - .
Để thuận lợi trong trình bày, chúng ta đa ra các cách viết khác nhau của bài toán
(1.1)(1.2)(1.3) nh sau:
* Dạng ma trận: Ký hiệu ma trận hàng C = ( c1 c2 cn)1ì n
Các ma trận cột: X = (x1 x2 xn)Tnì1 ;b = (b1 b2 bm)T mì1 và ma trận A=(aij)mìn.
Ta có bài toán: min CX
với điều kiện
* Dạng vector: Ký hiệu các vector
C = (c1, c2, , cn), X = (x1, x2, , xn),
Ao = (b1, b2, ,bm), Aj = (a1j, a2j, ..., anj), j=1, 2, , n.
Ta có bài toán: min <C,X>
hoạch tuyến tính chỉ cần tìm trên tập phơng án cực biên.
1.2.3.3. Định lý. Phơng án X = (xj) là cực biên khi và chỉ khi hệ vector cột {A j}
ứng với các xj > 0 độc lập tuyến tính.
Chứng minh: xem [2], tr 43.
Hệ quả. Số tọa độ dơng của phơng án cực biên có tối đa là m.
Số phơng án cực biên của M là hữu hạn.
Chứng minh: xem [2], tr 45.
Định nghĩa. Phơng án cực biên có đủ m tọa độ dơng đợc gọi là không suy biến
(hay không thoái hóa).
Bài toán quy hoạch tuyến tính có tất cả các phơng án cực biên không suy biến đợc gọi là bài toán không suy biến.
Hệ m vector {Aj} độc lập tuyến tính tơng ứng với phơng án cực biên X nh đã nêu
trong định lý 1.2.3.3 gọi là cơ sở liên kết của X.
Trên cơ sở định lý 1.2.3.3 và hệ quả, ta có thể xem đó là tiêu chuẩn sàng lọc để
giữ lại hữu hạn phơng án cực biên và đi tìm phơng án tối u trên tập hữu hạn này.
1.3. Phơng pháp đơn hình
1.3.1. ý tởng chung. Xuất phát từ phơng án cực biên Xo nào đó. Kiểm tra Xo có
tối u hay không?
Nếu Xo tối u thì dừng.
Nếu cha, tìm hớng giảm từ Xo, xây dựng phơng án cực biên mới X1 tốt hơn Xo.
Quá trình tiếp tục nh vậy, ta đợc dãy các phơng án cực biên tốt dần (theo nghĩa
giá trị hàm mục tiêu giảm dần từ phơng án cực biên trớc đến phơng án cực biên
sau) Xo, X1, , Xk. Sau hữu hạn bớc lặp ta đợc phơng án tối u hoặc phát hiện ra bài
toán vô nghiệm. Đó là nội dung của quá trình xây dựng dãy các phơng án cực biên
tốt dần, còn gọi là phơng pháp đơn hình.
Xét bài toán
min CX
(1.1)
với điều kiện
Chứng minh: xem [2], tr 73.
Chú ý: Để xây dựng phơng án cực biên mới tốt hơn phơng án cực biên Xo, ta
thực hiện:
a) Đa vector Ak vào làm cơ sở, thông thờng nếu có nhiều j > 0 thì chọn
k = max {j : j > 0}.
b) Chọn vector A ra khỏi cơ sở nhờ vào việc xác định:
o = = .
Lúc này phơng án cực biên mới sẽ có cơ sở là A1As-1As+1AmAk.
Vấn đề đặt ta là: tại phơng án cực biên Xo, biết đợc các đại lợng xio, xij, j và
f(Xo). Tại phơng án cực biên X1, chúng ta cần tính đại lợng tơng ứng xi1, xij, j và
f(X1).
Bằng phép biến đổi tọa độ khi thay đổi cơ sở, ta có công thức
xk = = .
xj =
(1.5)
f(X1) = f(Xo) - ok.
(1.6)
Ta cần tính xi và aij. Theo công thức biến đổi tọa độ khi thay đổi cơ sở trong
đại số tuyến tính, ta có:
aij =
(1.7)
Cũng từ đó, thay và tính toán trực tiếp ta đợc: j = j - k.
Từ định lý 1.4.2.1, 1.4.2.2, 1.4.2.3 ta có thuật toán đơn hình.
Thuật toán
Bớc 0. Chọn cơ sở đơn vị và phơng án cực biên xuất phát
C
kiện
ơ
XB*
A1
A2
A3
A4
A5
A6
g số
*
Chọn
cơ sở liên
sở
kết
A4A2A5 là
A4 1
9
1
0
0
1
0
6
các
vector
A2 -1
2
3
1
0
0
2, 0, 9, 6,
0)
và
A6 -1
1
3/2
1/2
-2
0
0
1
II
bảng đơn
hình.
A5
III
IV
1
4
-2
-1
-1/4
1
1/12
0
0
A6
-1
3/2
1/6
0
0
1/6
0
1
A5
1
3/2
1/3
0
1
-1/6
1/2
0
A6
-1
3/2
1/6
0
0
1/6
-1/3
-5/2
0
Tại bảng IV có j 0, (j = 1, , n) nên ta có phơng án tối u là
X =(0, 5, 3/2, 0, 0, 3/2), với fmin = -5.
Chú ý: Thuật toán đơn hình nêu trên đòi hỏi biết trớc phơng án cực biên xuất
phát Xo. Ta xét 2 trờng hợp:
Trờng hợp 1. Khi bài toán có dạng (1.1)-(1.3), ma trận A chứa ma trận đơn vị,
khi đó chỉ cần chỉ ra hệ cơ sở đơn vị tơng ứng các ẩn cơ sở, ta đợc phơng án cực
biên xuất phát Xo (nh đã làm ở ví dụ trên).
Trờng hợp 2. Xét bài toán dạng chính tắc
min{f(X)=}
(1.1)
với điều kiện
Khi ma trận A = (aij) cha chứa ma trận đơn vị, ta đa thêm ẩn giả tạo xn+i 0 với
hệ số hàm mục tiêu cn+i = M > 0 đủ lớn để có bài toán giả tạo (M) nh sau:
min{f(X)=+ M()}
(1.9)
với điều kiện
Lúc này bài toán (M) có ma trận chứa ma trận đơn vị nh đã nêu trong trờng hợp
1, có thể chọn cơ sở đơn vị {An+i} với các ẩn cơ sở xn+i, i = 1, 2, , m, ta đợc phơng
án cực biên xuất phát
= (0, 0, , 0, b1, b2, , bm) n+m.
Xuất phát từ , có thể giải bài toán (M) bằng phơng pháp đơn hình. Vấn đề đặt ra
là giữa bài toán (1.1)-(1.3) đã cho và bài toán (M) có mối quan hệ nh thế nào? Định
Cơ
Số
Sở
A4
A6
A7
I
II
III
IV
A4
A6
A3
A4
A2
A3
A1
A2
A3
C*
0
2
-1
6
6
4
0
10
10
2
2
2
2
7
1
-1/2
5/2
3/4
1/2 11/4
14/5
1
12/5
0
2/5
0
-36/5
0
-2
A2
0
1
0
0
0
1
0
0
A4
1
0
0
0
0
1
0
0
0
0
1
0
0
0
2/5
1/5
-3/10
-11/10
0
0
0
M
A7
0
0
1
0
0
Tại bảng IV có j 0, (j = 1, , 5) nên ta có phơng án tối u là
Xt. = (14/5, 12/5, 2/5, 0, 0), với fmax = 36/5.
Chơng 2
GIảI BàI TOáN QUY HOạCH TUYếN TíNH TRÊN MICROSOFT
OFFICE EXCEL
2.1. Công cụ Add-Ins Solver
2.1.1. Cài đặt
Trình cài thêm (Add-Ins) Solver thờng có mặt trong gói phần mềm Microsoft
Office khi cài đặt với lựa chọn Complete (đầy đủ) hoặc khi lựa chọn Custom (theo
ý ngời sử dụng) với lựa chọn cho Excel là Run all from my computer (cài đặt Excel
với đầy đủ các thành phần).
Để cài thêm Solver, ta tiến hành các bớc nh sau:
1. Lắp đĩa nguồn cài đặt Office gốc vào ổ CD-ROM hoặc ổ DVD.
2. Mở một file Excel.
3. Truy cập menu Tools/ Add-Ins (xem hình 2.1):
Chọn mục này khi cần tìm max của hàm mục tiêu.
Chọn mục này khi cần tìm min của hàm mục tiêu.
Chọn mục này và nhập giá trị vào ô hình chữ nhật bên cạnh
nếu muốn ô đích bằng một giá trị nhất định.
Ô chứa các địa chỉ tuyệt đối của các biến của bài toán.
Mục này dùng để nhập các ràng buộc của bài toán.
Để đoán giá trị trong các ô không chứa công thức do công
thức trong ô đích chỉ đến.
Hiển thị hộp thoại Add Constraint để thêm các ràng buộc
(xem phần 2.1.2.2).
Hiển thị hộp thoại Change Constrait để thay đổi các ràng
buộc.
Để xóa ràng buộc đã chọn.
Thực hiện việc giải toán.
Đóng hộp thoại Solver Parameters mà không tiến hành giải
bài toán.
Hiển thị hộp thoại Solver Options để ghi mô hình bài toán,
nạp lại mô hình đã ghi hoặc nhập các lựa chọn khác (xem
phần 2.1.2.3).
Xóa các thiết lập cho bài toán hiện tại và khôi phục các
thiết lập ngầm định.
Hiển thị trợ giúp cho Solver.
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 khi giá trị của hàm mục tiêu tại Set Target Cell đạt một giá trị quy định tại
Equal To và đồng thời thỏa mãn tập các ràng buộc tại Subject to the Constraints.
2.1.2.2. Hộp thoại Solver Options
Khi chọn Options trong hộp thoại Solver Parameters xuất hiện hộp thoại Solver
Options (xem hình 2.5), Solver cho phép chọn một số tùy chọn để tiến hành giải bài
nhau. Solver sẽ tự động điều chỉnh các biến để tìm ra lời
giải. Chẳng hạn nh bài toán tối đa % lợi nhuận trên hàng
triệu vốn đầu t.
Chọn mục này nếu muốn Solver tạm dừng lại và hiển thị
kết quả sau mỗi lần lặp.
Chọn phơng án cho Solver ớc lợng các biến.
Tangent: Sử dụng cách xấp xỉ tuyến tính bậc nhất.
Quandratic: Sử dụng cấp xỉ bậc hai. Lựa chọn này cho độ
chính xác cao hơn đối với bài toán quy hoạch phi tuyến.
Chọn cách để ớc lợng hàm mục tiêu và các ràng buộc.
Rorward: Dùng khi giá trị của các ràng buộc thay đổi
chậm (đợc dùng phổ biến).
Central: Dùng khi giá trị của các ràng buộc biến đổi
nhanh và khi Solver báo không thể cải tiến kết quả đợc.
Quy định cho Solver giải thuật tìm kiếm kết quả cho bài
toán.
Newton: Là phơng pháp mặc định, sử dụng nhiều bộ
nhớ nhng có số lần lặp ít.
Conjugate: Cần ít bộ nhớ nhng số lần lặp nhiều hơn.Đợc
sử dụng khi giải các bài toán phức tạp và bộ nhớ máy tính
có giới hạn.
Chọn nơi lu mô hình toán. Sử dụng khi muốn lu nhiều mô
hình trên một worksheet. Mô hình đầu tiên đã lu tự động.
Hiển thị hộp thoại Load modle để xác định vùng địa chỉ
của mô hình bài toán cần nạp vào.
2.2. Giải bài toán quy hoạch tuyến tính trên Microsoft Excel
Excel Solver có thể tìm cực đại hay cực tiểu của một hàm số đặt trong một ô gọi
là ô đích. Solver chỉnh sửa một nhóm các ô (gọi là các ô có thể chỉnh sửa) có liên
quan trực tiếp hay gián tiếp đến công thức nằm trong ô đích để tạo ra kết quả. Ta có
thể thêm vào các ràng buộc để hạn chế các giá trị mà Solver có thể dùng. Đối với
c[n]
c[i] x[j]
a[1,n] a[1,j] x[j]
a[2,n] a[2,j] x[j]
a[m,n] a[m,j] x[j]
x[3]
b[1]
b[2]
b[m]
Hàng cuối cùng là các giá trị ban đầu của các biến để các công thức của Excel
hoạt động, có thể lấy giá trị của tất cả các biến bằng 1 hoặc bằng 0.
Để thấy rõ tính u việt của việc dùng Solver so với cách thủ công khi giải bài
toán quy hoạch tuyến tính, ta giải lại ví dụ 1 và ví dụ 2 chơng 1 nh sau:
Ví dụ 1: Giải bài toán sau đây dùng Solver
Min (f = x1 x2 + x3 + x4 + x5 x6)
(1)
Với điều kiện
Các bớc thực hiện để giải bài toán:
Bớc 1. Nhập dữ liệu bài toán vào bảng tính dới dạng sau:
Hình 2.6. Tổ chức bài toán trên bảng tính.
Constraint: Ô chứa giá trị vế phải của các ràng buộc tơng ứng (có thể là số tự
nhập vào hay giá trị tuyệt đối của ô chứa giá trị đó).
Chú ý. Nếu các yêu cầu ràng buộc (x j) là nguyên thì trong ô dấu ta chọn int,
nếu là kiểu nhị phân ta chọn bin.
+ Tiếp tục chọn
trình.
để nhập tiếp các ràng buộc phơng trình và bất phơng
Cell Reference
$H$3:$H$5
=
Constraint
$I$3:$I$5
Hình 2.9b.
Chọn
để kết thúc việc khai báo các ràng buộc. Tuy nhiên, nếu hiệu
chỉnh ràng buộc ta chọn ràng buộc đó và chọn Change, xóa ràng buộc ta chọn ràng
buộc từ danh sách Subject to the Constraints và nhấp Delete.
Hình 2.10. Các ràng buộc của bài toán (1) đợc điền đầy đủ.
Sau khi nhập xong các ràng buộc, nháy vào nút Options, hiện hộp thoại Solver
Options, đánh dấu kiểm vào mục Assume Linear Model (khẳng định mô hình của
ta là tuyến tính).
Hình 2.11.
Bớc 4. Trong hộp thoại Solver Parameters nháy vào nút Solver để bắt đầu giải
Bớc 3. Chọn ô E2 và dùng lệnh Tools/ Solver, xuất hiện hộp thoại Solver
Paramaters với cách chọn hàm mục tiêu và các ràng buộc nh hình 2.15.
Hình 2.15. Các ràng buộc của bài toán (2) đợc điền đầy đủ.
Sau khi nhập xong các ràng buộc, nháy vào nút Options, hiện hộp thoại Solver
Options, đánh dấu kiểm vào mục Assume Linear Model (khẳng định mô hình của
ta là tuyến tính).
Bớc 4. Trong hộp thoại Solver Parameters nháy vào nút Solver để bắt đầu giải
bài toán tối u. Giải xong bài toán xuất hiện hộp thoại Solver Results, chọn mục
Keep Solver Solution (giữ kết quả và in ra bảng tính), nháy OK.
Bảng kết quả nhận đợc nh sau:
Hình 2.16.
Kết quả giải bài toán nằm ở các ô B6:D6, nh vậy phơng án tối u tìm đợc là: X =
(2.8, 2.4, 0.4) hay X = (14/5, 12/5, 2/5), giá trị cực tiểu hàm mục tiêu f(X) là 7.2 (=
36/5) ở ô E2.
2.3. Giải thích thuật ngữ
Tuy nhiên để tiện cho việc phân tích kết quả thì trong bảng Solver Results ở ví
dụ 1 ta chọn thêm mục Reports Answer khi đó bảng kết quả nhận đợc nh sau:
Hình 2.17. Hiển thị kết quả giải bài toán trong ví dụ 1 khi chọn Reports Answer.
Ta cần 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: Điều kiện ràng buộc.
Status: Trạng thái.
Binding: Ràng buộc chặt (nghĩa là, kết quả Excel tính đợc bằng so với yêu cầu).
Not Binding: Ràng buộc không chặt (ràng buộc lỏng) (nghĩa là, kết quả Excel
ợng nguyên vật liệu loại i cần thiết để sản xuất ra một đơn vị sản phẩm loại j, bi là
dự trữ nguyên vật liệu loại i, cj là lợi nhuận từ việc bán một đơn vị sản phẩm loại j,
với i = và j = .
Vấn đề đặt ra là phải sản xuất mỗi loại sản phẩm là bao nhiêu sao cho tổng lợi
nhuận thu đợc từ việc bán các sản phẩm đạt lớn nhất trong điều kiện nguyên liệu
hiện có.
Bài toán đợc mô tả theo bảng sau:
v1
v2
vi
vm
Lợi nhuận đơn
S1
a11
a21
ai1
am1
Sj
cn
vị
Gọi xj là lợng sản phẩm loại j mà nhà máy sẽ sản xuất (xj 0, j =).
Do đó phơng án sản xuất của nhà máy là X=(x1,x2,,xj,,xn).
Khi đó:
Tổng lợi nhuận thu đợc từ việc bán các sản phẩm là: .
Vì yêu cầu lợi nhuận thu đợc cao nhất nên cần tìm max hàm mục tiêu, nghĩa là:
max f(X) = .
Lợng nguyên liệu thứ i dùng để sản xuất sản phẩm thứ 1 là ai1x1.
Lợng nguyên liệu thứ i dùng để sản xuất sản phẩm thứ 2 là ai2x2.
Lợng nguyên liệu thứ i dùng để sản xuất sản phẩm thứ n là ainxn.
Vậy lợng nguyên liệu thứ i dùng để sản xuất tất cả các sản phẩm là .
Vì lợng nguyên liệu thứ i dùng để sản xuất các loại sản phẩm không thể vợt quá
lợng đợc cung cấp là bi nên: bi, ().
Suy ra mô hình toán học của bài toán lập kế hoạch sản xuất có thể phát biểu
theo mô hình bài toán quy hoạch tuyến tính nh sau:
max f(x) =
với điều kiện
3.1.2. Ví dụ
Ví dụ 3. Một nhà máy dự định tiến hành sản xuất 5 loại sản phẩm S j (j=). Cả 5
loại sản phẩm này đều sử dụng 4 loại nguyên vật liệu chính v i (i= ). Có mức sử
dụng nguyên vật liệu, lợi nhuận đơn vị thu đợc và giới hạn dự trữ nh sau:
Copyright: Tài liệu đại học ©