Tài liệu ỨNG DỤNG EXCEL ĐỂ GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH docx

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (487.66 KB, 26 trang )

1
ỨNG DỤNG EXCEL
ĐỂ GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH
Sự cạnh tranh khốc liệt 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. 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
(QHTT) để mô tả, phân tích và tìm lời giải cho vấn đề lựa chọn tối ưu trong
quản lý kinh tế. Trong môn học Toán kinh tế
việc giải bài toán QHTT thực hiện
bằng thuật toán đơn hình. Trong phần mềm Excel sử dụng một công cụ cài
thêm là Solver có thể giải bài toán tối ưu nhanh chóng.
2.1 NHẮC LẠI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH
2.1.1 Bài toán QHTT dạng tổng quát
Bài toán QHTT dạng tổng quát là bài toán tối ưu hoá hay bài toán tìm cực
trị (cực tiểu hoặc cực đại) của một hàm tuyến tính với điều kiện các biến số phải
thoả mãn một hệ phương trình và (hoặc) bất phương trình tuyến tính. Mô hình
toán học của bài toán QHTT tổng quát có thể viết như sau:
Hàm mục tiêu:
max(min)), ,(
1
21
→=
∑
=
n

j
jj
xcxxf
(2.1)
với các ràng buộc (điều kiện):

()
1
1
, Iibxa
i
n
j
jij
∈=
∑
=
(2.2)
2
()
2
1
, Iibxa
i
j
jij
∈≥
∑
=
(2.3)

()
3
1
, Iibxa
i
n
j
jij
∈≤
∑
=
(2.4)
0≤
j
x
hoặc
0≥
j
x
(2.5)
trong đó:
I
1
, I
2
, I
3
là tập các chỉ số (I
1
, I

2
, I
3
không giao nhau), ký hiệu
I I I I
321
∪∪=

a
ij
, b
i
, c
j
với
njIi ÷=∈ 1,
là các hằng số (có thể là tham số), n là số
biến số
x
j
với
nj ÷= 1
là các biến số (ẩn số) của bài toán, (2.5) được gọi là các
ràng buộc về dấu
* Một số khái niệm và định nghĩa

(1) Một nhóm ràng buộc có hệ véc tơ tương ứng độc lập tuyến tính được
gọi là các ràng buộc độc lập tuyến tính. Các ràng buộc dấu luôn là độc lập tuyến
tính.
(2) Phương án: Một véc tơ x = (x

1
,x
2
,…,x
n
) thoả mãn hệ ràng buộc của
bài toán gọi là một phương án của bài toán.
Để phân biệt tính chất của các ràng buộc (cả ràng buộc dấu) đối với một
phương án cụ thể, ta có các khái niệm ràng buộc: chặt và lỏng.
+ nếu đối với phương án x mà ràng buộc i thoả mãn với dấu đẳng thức
(2.2) hoặc x
i
= 0 (nếu là ràng buộc dấu) thì ta nói phương án x thoả mãn chặt
ràng buộc i hay ràng buộc i là chặt đối với phương án x.
+ nếu đối với phương án x mà ràng buộc i thoả mãn với dấu bất đẳng thức
(2.3), (2.4) hoặc x
i
> 0, x
i
< 0 (tuỳ thuộc ràng buộc loại gì) thì ta nói phương án
x thoả mãn lỏng ràng buộc i hay ràng buộc i là lỏng đối với phương án x.
3
Ràng buộc i có dạng phương trình thì nó sẽ là chặt với mọi phương án của
bài toán, nếu có dạng bất phương trình thì nó có thể là chặt đối với phương án
này và là lỏng đối với phương án kia.
(3) Phương án tối ưu (phưong án tốt nhất): Một phương án mà tại đó trị
số hàm mục tiêu đạt cực tiểu (hoặc cực đại, tuỳ trường hợp cụ thể của f(x)) g
ọi
là phương án tố ưu.
(4) Phưong án tốt hơn: Xét bài toán có f(x)

→
min (max) và hai phương
án x
1
, x
2
của nó. Phương án x
1
gọi là tốt hơn phương án x
2
nếu
(
)
()
(
)
21
xfxf ≥≤
.
Nếu có các dấu bất đẳng thức thực sự thì gọi là tốt hơn thực sự.
Một bài toán có tồn tại phương án tối ưu gọi là bài toán giải được và
ngược lại nếu không có phương án tối ưu gọi là bài toán không giải được. Bài
toán không giải được là do một trong hai nguyên nhân sau:
+ Bài toán không có phương án
+ Bài toán có phương án, nhưng hàm mục tiêu không bị chặn dưới nếu
f(x)
→
min hoặc không bị chặn trên nếu f(x)
→
max trên tập phương án.

(5) Phương án cực biên (PACB): Một phương án thoả mãn chặt n ràng
buộc độc lập tuyến tính được gọi là phương án cực biên.
Một bài toán có số ràng buộc (kể cả ràng buộc dấu nếu có) ít hơn n thì
chắc chắn sẽ không có phương án cực biên dù nó có phương án.
Phương án cực biên thoả mãn chặt đúng n ràng buộc gọi là phương án cực
biên không suy biến, thoả mãn chặt hơn n ràng buộc g
ọi là phương án cực biên
suy biến. Nếu tất cả các phương án cực biên của bài toán đều không suy biến thì
gọi là bài toán không suy biến, ngược lại là bài toán suy biến.
Để thuận tiện cho việc trình bày các kết quả lý thuyết cũng như thuật toán
giải QHTT, người ta thường sử dụng hai dạng đặc biệt của bài toán QHTT là bài
toán dạng chính tắc và bài toán dạng chuẩn.
2.1.2 Bài toán QHTT dạng chính tắc
4
Bài toán QHTT dạng chính tắc có dạng như sau:
Hàm mục tiêu:
max(min)), ,(
1
2
→=
∑
=
n
j
jj
xcxxf
(2.1)
với các ràng buộc:
mibxa
i

n
j
jij
÷==
∑
=
1,
1
(2.6)
njx
j
÷=≥ 1,0
(2.7)
Như vậy, bài toán QHTT dạng chính tắc gồm có 2 nhóm: nhóm các ràng
buộc dạng phương trình (2.6), nhóm ràng buộc dạng bất phương trình chỉ bao
gồm các ràng buộc về dấu (2.7).
2.1.3 Bài toán QHTT dạng chuẩn
Bài toán QHTT dạng chuẩn có dạng như sau:
Hàm mục tiêu:
max(min)), ,(
1
2
→=
∑
=
n
j
jj
xcxxf
(2.1)

với các ràng buộc:
mibxa
i
n
j
jij
÷=≥
∑
=
1,
1
(2.8)
njx
j
÷=≥ 1,0
(2.7)
Bài toán QHTT dạng chuẩn chỉ gồm 1 nhóm các ràng buộc dạng bất
phương trình bao gồm các ràng buộc về dấu là (2.8) và (2.7).
2.2 CÁC BƯỚC GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH TRONG EXCEL
Để giải quyết các bài toán QHTT phần mềm Excel cung cấp cho chúng ta
một công cụ khá hữu ích là Solver. Các bài toán QHTT dạng chính tắc và dạng
chuẩn chỉ là các trường hợp riêng bài toán QHTT dạng tổng quát. Vì thế ở đây ta
sẽ xem xét cách giải quyết bài toán QHTT dạng tổng quát rồi từ đó áp dụng
tương tự cho hai dạng còn lại.
2.2.1 Cài thêm công cụ Add-ins Solver
Vào thực đơn Tools\ Solver. Nếu chưa thấy chức năng Solver trên thực
đơn Tools thì ta cần bổ
sung chức năng này vào Excel. Các bước tiến hành:
(1) Vào menu Tools\ Add-Ins, xuất hiện cửa sổ:
5

Hình 2.1 Hộp thoại Add-ins chứa các chức năng mở rộng của Excel
(2) Chọn Solver Add-Ins và chọn OK.
2.2.2 Xây dựng bài toán trong Excel
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. Ta xét ví dụ sau:
Ví dụ 2.1: Cho bài toán QHTT sau:
Hàm mục tiêu: f(x) = 2x
1
+8x
2
-5x
3
+15x
4
→
max
với ràng buộc: 3x
1
-x
2
+x
3
+10x
4
=5
x
1

+2x
2
+x
3
+5x
4
≥

9
2x
1
+10x
2
+2x
3
-5x
4
≤
26
41,0 ÷=≥ jx
j

Tổ chức dữ liệu trên bảng tính:
¾ Biến quyết định: được nhập tại các ô B7:E7. Cho các giá trị khởi động
là 0.
¾ Hàm mục tiêu f(x): có giá trị căn cứ vào giá trị khởi động của các biến.
Công thức tại ô F8.
6
¾ 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:E12. Tính vế trái của các ràng buộc theo công thức tại các ô F10:F12.

Nhập các giá trị vế phải của các ràng buộc tại các ô G10:G12.
Theo bảng sau:

Hình 2.2 Tổ chức bài toán trên bảng tính
Sau khi nạp xong dữ liệu vào bảng tính ta tiến hành giải bài toán.
2.2.3 Tiến hành giải bài toán
(1) Chọn ô F8 và chọn Tools\ Solver. Bảng hộp thoại Solver Parameters
xuất hiện và gồm các thông số sau:

Hình 2.3 Hộp thoại khai báo các thông số cho Solver
Trong đó:
7
Set Tanget Cell: Nhập ô chứa địa chỉ tuyệt đối của hàm mục tiêu.
Equal 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 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 Tanget Cell đạt một giá trị quy
định tại Equal 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ụ 2.1 ta tiến hành khai báo các thông số cho Solver như sau:
¾ Địa chỉ của hàm mục tiêu F8 được đưa vào Set Target Cell
¾ Chọn Max tại Equal 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:E7 tại By Changing Cells.

Hình 2.4 Khai báo hàm mục tiêu và các biến
¾ 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:
8

Hình 2.5 Hộp thoại thêm các ràng buộc
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ụ 2.1 các ràng buộc được nhập như sau:
+ Các ràng buộc về dấu: do
41,0 ÷=≥ jx
j
(các ràng buộc đều có dạng
≥
) nên ta chọn vùng địa chỉ chứa biến B7:E7 vào Cell Reference, chọn dấu
≥

và nhập 0 vào Constraint:

Hình 2.6 Thêm các ràng buộc
Chú ý: Nếu bài 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 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
F10 = G10

F11 >= G11
F12 <= G12
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 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.

Hình 2.7 Khai báo các thông số của bài toán
¾ 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:

Hình 2.8 Chọn kiểu báo cáo
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ụ 2.1 ta chọn Keep Solver Solution, OK. Bảng kết quả nhận được
như sau:
10

Như vậy phương án cực biên tìm được là X=(0,3,0,0.8) và giá trị cực đại
của hàm mục tiêu f(x) là 36.
2.2.4 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 ta chọn thêm mục Answer Reports khi đó bảng kết quả nhận được của
ví dụ 2.1 như sau:

Ta cần phải 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: Công thức tính.
Status: Trạng thái.
Binding: Ràng buộc chặt.
11
Not Binding: Ràng buộc không chặt (ràng buộc lỏng).
2.3 CÁC LỰA CHỌN KHI GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH
2.3.1 Các lựa chọn
Để thiết lập các thuộc tính cho Solver thì trong bảng Solver Parameters
ta nhấp chuột vào Options hộp thoại Solver Options cho ta các lựa chọn sau:

Hình 2.9 Thiết lập các thuộc tính cho Solver
Max Time: Thời gian tối đa để giải bài toán là 32.767 giây (mặc định là
100 giây cho các bài toán đơn giản).
Iterations: Số lần lặp tối đa để giải các bài toán là 32.767 lần(mặc định là
100 lần).
Precision: Độ chính xác của bài toán (từ 0 đến 1, mặc định là 0.000001,
giá trị càng gần với 0 thì độ chính xác càng cao). Giá trị này điều chỉnh độ sai số
cho tập ràng buộc.
Tolerance: Chỉ áp dụng đối với các bài toán có ràng buộc nguyên. Nhập
vào sai s
ố có thể chấp nhận được. Sai số càng lớn thì tốc độ giải càng nhanh
(mặc định là 5%)
Convergence: Chỉ áp dụng đối với các bài toán không tuyến tính. Khi tỉ
số của giá trị tính toán ban đầu của ô đích đến giá trị tính toán hiện hành ít hơn
giá trị đồng quy Solver ngừng việc tìm kiếm dù có tìm thấy lời giải hay không.
12
Giá trị nằm trong khoảng từ 0 đến 1. Giá trị càng gần 0 thì độ chính xác càng

cao và cần nhiều thời gian hơn (mặc định là 0.0001).
Assume Linear Model: Khi tất cả quan hệ trong mô hình là tuyến tính thì
chọn mục này để tăng tốc độ giải bài toán.
Assume Non-Negative: Chọn tuỳ chọn này nếu muốn giả định tất cả các
biến của bài toán đều không âm.
Use Automatic Scaling: Chọn tuỳ chọn này khi ô đích và ô thay đổi có sự
khác nhau lớn. 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 đồng vốn đầu tư.
Show Iteration Results: Chọn tuỳ chọn 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.
Ba tính năng nâng cao điều khiển cho Solver:
Estimates: Chọn phương pháp 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ách xấp xỉ bậc bốn.
Derivatives: Chọn cách để ước lượng hàm mục tiêu và các ràng buộc
– Forward: Dùng khi giá trị của các ràng buộc biến đổ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ả thu được.
Search: Quy định 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ớ và có số lần
lặp ít.
– Conjugate: cần ít bộ nhớ hơn phương pháp Newton nhưng số lần lặp
thì 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.
Save Model: Chọn nơi lưu mô hình bài toán. Sử dụng khi muốn lưu nhiề
u

mô hình trên một worksheet. Mô hình đầu tiên đã được lưu tự động.
Load Model: Xác định vùng địa chỉ của mô hình bài toán cần nạp vào.
13
2.3.2 Hạn chế khi giải bài toán quy hoạch tuyến tính trong Excel
Hạn chế của bài trình cài thêm Solver là chỉ giải được các bài toán có tối da
là 16 biến số. Mặt khác số lần lặp tối đa để giải bài toán là 32767, thời gian tối đa
để giải bài toán là 32767…nên bên cạnh đó nó còn tồn tại một số mặt hạn chế
nhất định về quy mô của bài toán và khó khăn trong việc tìm miền tối ưu.
Đối với những bài toán tố
i ưu có quy mô lớn ta có thể sử dụng phần mềm
Lindo đây là một phần mềm tin học rất mạnh trong lĩnh vực này.
2.4 MỞ RỘNG BÀI TOÁN
Việc ứng dụng mô hình QHTT trong quản lý kinh tế và quản trị doanh
nghiệp là rất phổ biến. Chúng ta thường bắt gặp mô hình này trong các bài toán
như: bài toán lập kế hoạch sản xuất tối ưu cho doanh nghiệp, bài toán phân bổ
vốn đầu tư, bài toán dự trữ…Tuy nhiên trong phần này xin trình bày ra đây 2
loại bài toán QHTT thông dụng nhất là: bài toán nguyên vật liệu và bài toán vận
tải.
2.4.1 Bài toán nguyên vật liệu
¾ Bài toán tổng quát
Một nhà máy có khả năng sản xu
ất n loại sản phẩm. Để sản xuất các sản
phẩm này cần phải sử dụng m loại nguyên vật liệu. Biết rằng:
a
ij
là lượ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
b
i
là dự trữ nguyên vật liệu loại i

c
j
là lợi nhuận từ việc bán một đơn vị sản phẩm loại j
với
mi ,1=
và
nj ,1=

Bài toán được mô tả theo bảng sau:
S
1
S
2
… S
j
… S
n
Dự trữ
NVL1 a
11
a
12
…

a
1j
… a
1n
b
1

NVL2 a
21
a
22
…

a
2j
… a
2n
b
2
… … … … … … … …
14
NVL
i
a
i1
a
i2
…

a
ij
… a
in
b
i
… … … … … … … …
NVL

m
a
m1
a
m2
…

a
mj
… a
mn
b
m
Lợi nhuận đơn vị c
1
c
2
…
c
j
… c
n

Hãy tìm phương án sản xuất để tối đa hoá lợi nhuận.
Bài giải:
Gọi x
j
là lượng sản phẩm loại j mà nhà máy sẽ sản xuất nên
0x

j
≥
.
Do đó phương án sản xuất của nhà máy là vectơ x=(x
1
, x
2
,…,x
j
, ,x
n
).
Khi đó:
Tổng chi phí nguyên vật liệu loại
i
để sản xuất x là
∑
=
n
j
jij
xa
1
sẽ không vượt
quá dự trữ
b
i
:
i
n

j
jij
bxa ≤
∑
=1

Tổng lợi nhuận thu được khi sản xuất x là
∑
=
n
j
jj
xc
1

Vậy mô hình toán học của bài toán nguyên vật liệu có thể phát biểu theo
mô hình bài toán QHTT như sau:
Hàm mục tiêu: f(x)=
∑
=
→
n
j
jj
xc
1
max

Các ràng buộc:
mibxa

i
n
j
jij
,1,
1
=≤
∑
=

n1,j0,x
j
=≥

Việc giải bài toán nguyên vật liệu trong Excel cũng bao gồm 2 bước:
B1: Xây dựng bài toán (lập bài toán và tổ chức dữ liệu trên bảng tính).
B2: Tiến hành giải bài toán bằng cách chạy Solver theo trình tự như trên.
Ta xét một ví dụ cụ thể sau:
¾ Ví dụ 2.2
15
Một nhà máy dự định tiến hành sản xuất 5 loại sản phẩm S
j
(
1,5j =
). 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 NVL
i
(
4,1=i

). Có
mức tiêu hao nguyên vật liệu, lợi nhuận đơn vị thu được và giới hạn dự trữ như
sau:
S
1
S
2
S
3
S
4
S
5
Dự trữ
NVL
1
2 5 6 8 4
1200
NVL
2
3 1 5 6 1
800
NVL
3
7 5 4 5 2
2000
NVL
4
8 5 7 9 1
1865

Lợi nhuận đơn vị
300 250 500 150 320

Hãy xây dựng phương án sản xuất để nhà máy đạt được tổng lợi nhuận
lớn nhất.
Bài giải:
B1: Xây dựng bài toán
Gọi x
j
với j=1,5 là sản lượng sản phẩm loại j sẽ sản xuất. (x
j
>=0)
Nên phương án sản xuất của nhà máy là vectơ x = (x
1
, x
2
, x
3
, x
4
, x
5
).
Hàm mục tiêu: f(x) = 300x
1
+ 250x
2
+ 500x
3
+ 150x

4
+ 320x
5

Æ
max
Các ràng buộc:

2x
1
+ 5x
2
+ 6x
3
+ 8x
4
+ 4x
5
<= 1200
3x
1
+ x
2
+ 5x
3
+ 6x
4
+ x
5

<= 800
7x
1
+ 5x
2
+ 4x
3
+ 5x
4
+ 2x
5
<= 2000
8x
1
+ 5x
2
+ 7x
3
+ 9x
4
+ x
5
<= 1865
Bài toán được tổ chức trên bảng tính như sau:
16

Hình 2.10 Lập bài toán trên bảng tính
B2: Giải bài toán:
–
Chọn ô G8 rồi thực hiện lệnh

Tools\ Solver,
điền đầy đủ thông tin vào
hộp thoại
Solver Parameters
như sau
:

Hình 2.11 Khai báo các thông số của bài toán
–
Nhấn
Solver để thực
hiện việc chạy Solvers. Trong bảng hộp thoại kết
quả
Solver Results
tích chọn mục
Keep Solver Solution
và chọn thêm báo cáo

Answer Report
ta nhận được kết quả:

17

Phương án tối ưu (phương án cực biên) là x = (200, 0, 0, 0, 200) với
f(x) max = 124 000. Hay phương án sản xuât tối ưu của nhà máy là sản xuất 200
đơn vị sản phẩm 1 và 200 đơn vị sản phẩm 5 khi đó lợi nhuận tối ưu đạt được là
124 000 đơn vị tiền tệ. Không có nguyên liệu nào bị lãng phí.
2.4.2 Bài toán vận tải
¾ Bài toán tổng quát:

Có
m kho hàng cùng chứa một loại hàng hoá, lượng hàng có ở kho i là a
i

(
)
mi ,1=
.
Có
n
địa điểm tiêu thụ loại hàng nói trên, với nhu cầu tiêu thụ ở điểm
j
là
b
j

(
)
nj ,1=
.
18
Biết
c
ij
là cước phí vận chuyển một đơn vị hàng hoá từ kho
i
đến điểm tiêu
thụ
j
.

Bài toán được mô tả theo bảng sau:
D
1
D
2
… D
j
… D
n
Dự trữ
K
1
c
11
c
12
…

c
1j
… c
1n
a
1
K
2
c
21
c
22

…

c
2j
… c
2n
a
2
… … … … … … … …
K
i
c
i1
c
i2
…

c
ij
… c
in
a
i
… … … … … … … …
K
m
c
m1
c
m2

…

c
mj
… c
mn
a
m
Nhu cầu tiêu thụ b
1
b
2
…

b
j
…

b
n

Hãy lập kế hoạch vận chuyển hàng từ các kho đến các điểm tiêu thụ sao
cho tổng chi phí vận chuyển là nhỏ nhất.
Bài giải:
Gọi
x
ij
là lượng hàng vận chuyển từ kho
i

đến điểm tiêu thụ
j
nên
njmix
ij
,1,,0 ==≥
. Ta có:
Tổng chi phí vận chuyển:
∑∑
==
m
i
n
j
ijij
xc
11

Lượng hàng vận chuyển khỏi kho
i
:
∑
=
n
j
ij
x
1

Lượng hàng vận chuyển đến điểm tiêu thụ

j
:
∑
=
m
i
ij
x
1

Như vậy mô hình toán học của bài toán vận tải có thể viết dưới dạng bài
toán QHTT như sau:
Hàm mục tiêu: f(x) =
min
11
→
∑∑
==
m
i
n
j
ijij
xc

Các ràng buộc:
∑
=
≤
n

j
ij
x
1
a
i
19

∑
=
m
i
ij
x
1
= b
j

njmix
ij
,1,,1,0 ==≥

Ta thấy ngay được điều kiện cần và đủ để bài toán vận tải có phương án
tối ưu là tổng tất cả các lượng hàng tiêu thụ bằng tổng tất cả các lượng hàng ở
các kho, nghĩa là:
∑∑
==
=
n

j
j
m
i
i
ba
11

Cũng giống như bài toán nguyên vật liệu để tiến hành giải bài toán trong
Excel ta cần phải trải qua 2 bước là: xây dựng bài toán và tiến hành chạy
Solver. Xét ví dụ cụ thể sau:
¾ Ví dụ 2.3

Sử dụng công cụ Solver như đã trình bày ở trên hãy lập phương án vận
chuyển xăng tối ưu từ 4 kho đến 5 trạm xăng bán lẻ của một công ty kinh doanh
xăng dầu khu vực V.
Bài giải:
B1: Xây dựng bài toán
Gọi
x
ij
là lượng hàng vận chuyển từ kho
i
đến điểm tiêu thụ
j
nên
5,1,4,1,0 ==≥ jix
ij
.
Hàm mục tiêu: f(x) = 30x

11
+ 27x
12
+ 26x
13
+ 9x
14
+ 23x
15
+ 13x
21
+ 4x
22

+ 22x
23
+ 3x
24
+ x
25
+ 3x
31
+ x
32
+ 5x
33
+ 4x
34
+ 24x
35

+ 16x
41
+ 30x
42
+ 17x
43
+
10x
44
+ 16x
45

Æ
min
Các ràng buộc:
x
11
+ x
12
+ x
13
+ x
14
+ x
15
<= 4
x
21
+ x
22

+ x
23
+ x
24
+ x
25
<= 6
x
31
+ x
32
+ x
33
+ x
34
+ x
35
<= 10
x
41
+ x
42
+ x
43
+ x
44
+ x
45
<= 10
x

11
+ x
21
+ x
31
+ x
41
<= 7
x
12
+ x
22
+ x
32
+ x
42
<= 7
20
x
13
+ x
23
+ x
33
+ x
43
<= 7
x
14
+ x

24
+ x
34
+ x
44
<= 7
x
15
+ x
25
+ x
35
+ x
45
<= 2
Tổ chức dữ liệu trên bảng tính như sau:

Hình 2.12 Tổ chức bài toán trên bảng tính
Bước 2:

Tiến hành giải bài toán
Chọn ô
B16
rồi dùng lệnh
Tools\Solver

Hình 2.13 Khai báo các thông số của bài toán
21
Sau khi nhập đầy đủ thông tin vào bảng

Solver Parameters
ta chọn
Solve\Keep Solver Solution ,OK.
Ta được bảng kết quả sau:

Phân tích kết quả:
Vậy phương án vận chuyển là:
x = (0,0,0,4,0,0,4,0,0,2,7,3,0,0,0,0,0,7,3,0)
Vì tổng lượng xăng dự trữ ở các kho bằng tổng nhu cầu xăng ở các trạm
(30) nên phương án tìm được là phương án tối ưu.
Chú ý 1:
Nếu muốn có bảng kết quả chi tiết để phân tích thì trong bảng
Solver Results
ta chọn thêm mục
Reports\ Answer
(hoặc\và
Sensitivity
hoặc\và

Limits
) tuỳ thuộc vào mức độ chi tiết yêu cầu của bài.
Chú ý 2:
Đối với những bài toán chưa tìm được lời giải mong muốn ta có
thể thay đổi các thông số đầu vào của bài toán rồi chọn Tools\ Solver để tìm ra
phương án tối ưu.

2.5 ỨNG DỤNG EXCEL ĐỂ GIẢI HỆ PHƯƠNG TRÌNH TUYẾN TÍNH
22
Dạng tổng quát của hệ phương trình tuyến tính là hệ
m
phương trình đại
số bậc nhất đối với
n
ẩn số:
a
11
x
1
+ a
12
x
2
+… +a
1n
x
n
= b
1

a
21
x
1
+ a
22
x

2
+… +a
2n
x
n
= b
1
(*)
……………………………
a
m1
x
1
+ a
m2
x
2
+… +a
1m
x
n
= b
1

với x
1
, x
2
,…, x
n

là các ẩn số; a
ij
là hệ số ở phương trình thứ i của ẩn x
j
; b
i

là vế phải của phương trình.
Khi m = n ta có hệ phương trình vuông với n phương trình n ẩn.
Khi b
i
= 0 ta có một hệ thuần nhất.
Toán học đã cung cấp cho chúng ta khá nhiều phương pháp để giải các hệ
phương trình tuyến tính như: phương pháp thế, phương pháp cộng đại số,
phương pháp ma trận – định thức …Phần mềm Excel cũng cung cấp cho ta hai
công cụ rất dễ dàng, nhanh chóng và chính xác để tiến hành giải hệ phương trình
tuyến tính là: sử dụng trình cài thêm
Solver
và sử dụng kết hợp hai hàm
MINVERSE
và
MMULT
.
2.5.1 Giải hệ phương trình bằng Solver
Ngoài ứng dụng để giải các bài toán QHTT
Solver
còn có thể ứng dụng để
giải các bài toán về hệ phương trình. Khi đó chỉ có các ràng buộc dạng phương
trình và không có hàm mục tiêu. Các bước tiến hành giải hệ phương trình hoàn
toàn tương như khi giải bài toán QHTT. Để hiểu hơn ta tiến hành xét ví dụ sau:

Ví dụ 2.4:
Giải hệ phương trình sau:
2x
1
+ 4x
2
+ 3x
3
= 4
3x
1
+ x
2
– 2x
3
= -2
4x
1
+ 11x
2
+ 7x
3
= 7
Bước 1:
Tổ chức dữ liệu vào bảng tính
Nhập các hệ số, vế phải của phương trình và cho giá trị khởi động cho các
biến vào bảng tính như hình sau:
23

Hình 2.14 Lập bài toán trên bảng tính

Bước 2:
Giải hệ phương trình
Chọn
Tools\ Solver, OK
. Rồi tiến hành điền đầy đủ thông tin vào hộp
thoại
Solver Paraments
(bỏ trống mục
Set Target Cell
).

Hình 2.15 Khai báo các thông số của bài toán
Sau khi điền đầy đủ thông tin ta nhấp
Solve
. Trong bảng hộp thoại
Solver
Results
ta kiểm vào
Keep Solver Solution
để lưu kết quả trên bảng tính.
24

Hình 2.16 Chọn loại báo cáo
Chọn
OK
để hoàn tất quá trình chạy Solver
.
Ta được bảng kết quả như
sau:

Vậy nghiệm tìm được của hệ phương trình là: x = 1, y= -1, z = 2.
Không chỉ sử dụng Solver để giải hệ phương trình phần mềm Excel còn
cung cấp thêm một công cụ nữa để giải hệ phương trình bằng phương pháp ma
trận là sử dụng hàm
MINVERSE
và
MMULT
2.5.2 Giải hệ phương trình bằng hàm MINVERSE và hàm MMULT
Khi hệ phương trình (*) có m = n thì nó trở thành hệ vuông gồm n
phương trình n ẩn. Khi đó ma trận hệ số A, ma trận biến X sẽ là một ma trận
vuông cấp n và ma trận của vế phải hệ phương trình B là:
a
11
a
12
… a
1n
a
11
a
12
… a
1n

a
21
a
22
… a
2n

a
21
a
22
… a
2n

A = …………… X = ……………

a
n1
a
n2
… a
nn
a
n1
a
n2
… a
nn

B = b
1
b
2
… b
n

Vậy hệ (*) được viết lại là: A * X = B (**) nên X = A
-1
*B (***)
25
2.5.1.1 Giới thiệu hàm MINVERSE và hàm MMULT
 Hàm MINVERSE
Là hàm dùng để tìm ma trận nghịch đảo.

Cú pháp
:
MINVERSE(array)
array: là địa chỉ ma trận cần nghịch đảo.
Ví dụ 2.5

 Hàm MMULT
Là hàm dùng để nhân 2 ma trận.
Cú pháp
:
MMULT(array1, array2)
array1, array2: là địa chỉ của các ma trận cần nhân.
Ví dụ 2.6

Chú ý
: – Nhấn tổ hợp phím
Ctrl + Shift + Enter
sau khi nhập xong công
thức.
– Chỉ khi là ma trận vuông nếu không khi sử dụng hàm này sẽ báo
lỗi #VALUE!.
– Nếu có phần tử nào trong ma trận là rỗng hoặc là chữ thì báo lối

#VALUE!.
2.5.2.2 Giải hệ phương trình
Quá trình giải hệ phương trình bằng phương pháp ma trận sử dụng hai
hàm
MINVERSE và MMULT được tiến hành theo 3 bước sau:
jjxcxxf ( 2.1 ) với những ràng buộc ( điều kiện kèm theo ) : ( ), Iibxajij ∈ = ( 2.2 ) ( ), Iibxajij ∈ ≥ ( 2.3 ) ( ), Iibxajij ∈ ≤ ( 2.4 ) 0 ≤ hoặc0 ≥ ( 2.5 ) trong đó :, I, Ilà tập những chỉ số ( I, I, Ikhông giao nhau ), ký hiệuI I I I321 ∪ ∪ = ij, b, cvớinjIi ÷ = ∈ 1, là những hằng số ( hoàn toàn có thể là tham số ), n là sốbiến sốvớinj ÷ = 1 là những biến số ( ẩn số ) của bài toán, ( 2.5 ) được gọi là cácràng buộc về dấu * Một số khái niệm và định nghĩa ( 1 ) Một nhóm ràng buộc có hệ véc tơ tương ứng độc lập tuyến tính đượcgọi là những ràng buộc độc lập tuyến tính. Các ràng buộc dấu luôn là độc lập tuyếntính. ( 2 ) Phương án : Một véc tơ x = ( x, x, …, x ) thoả mãn hệ ràng buộc củabài toán gọi là một giải pháp của bài toán. Để phân biệt đặc thù của những ràng buộc ( cả ràng buộc dấu ) so với mộtphương án đơn cử, ta có những khái niệm ràng buộc : chặt và lỏng. + nếu so với giải pháp x mà ràng buộc i thoả mãn với dấu đẳng thức ( 2.2 ) hoặc x = 0 ( nếu là ràng buộc dấu ) thì ta nói giải pháp x thoả mãn chặtràng buộc i hay ràng buộc i là chặt so với giải pháp x. + nếu so với giải pháp x mà ràng buộc i thoả mãn với dấu bất đẳng thức ( 2.3 ), ( 2.4 ) hoặc x > 0, x < 0 ( tuỳ thuộc ràng buộc loại gì ) thì ta nói phương ánx thoả mãn lỏng ràng buộc i hay ràng buộc i là lỏng so với giải pháp x. Ràng buộc i có dạng phương trình thì nó sẽ là chặt với mọi giải pháp củabài toán, nếu có dạng bất phương trình thì nó hoàn toàn có thể là chặt so với phương ánnày và là lỏng so với giải pháp kia. ( 3 ) Phương án tối ưu ( phưong án tốt nhất ) : Một giải pháp mà tại đó trịsố hàm mục tiêu đạt cực tiểu ( hoặc cực lớn, tuỳ trường hợp đơn cử của f ( x ) ) gọilà giải pháp tố ưu. ( 4 ) Phưong án tốt hơn : Xét bài toán có f ( x ) min ( max ) và hai phươngán x, xcủa nó. Phương án xgọi là tốt hơn giải pháp xnếu ( ) 21 xfxf ≥ ≤ Nếu có những dấu bất đẳng thức thực sự thì gọi là tốt hơn thực sự. Một bài toán có sống sót giải pháp tối ưu gọi là bài toán giải được vàngược lại nếu không có giải pháp tối ưu gọi là bài toán không giải được. Bàitoán không giải được là do một trong hai nguyên do sau : + Bài toán không có giải pháp + Bài toán có giải pháp, nhưng hàm mục tiêu không bị chặn dưới nếuf ( x ) min hoặc không bị chặn trên nếu f ( x ) max trên tập giải pháp. ( 5 ) Phương án cực biên ( PACB ) : Một giải pháp thoả mãn chặt n ràngbuộc độc lập tuyến tính được gọi là giải pháp cực biên. Một bài toán có số ràng buộc ( kể cả ràng buộc dấu nếu có ) ít hơn n thìchắc chắn sẽ không có giải pháp cực biên dù nó có giải pháp. Phương án cực biên thoả mãn chặt đúng n ràng buộc gọi là giải pháp cựcbiên không suy biến, thoả mãn chặt hơn n ràng buộc gọi là giải pháp cực biênsuy biến. Nếu tổng thể những giải pháp cực biên của bài toán đều không suy biến thìgọi là bài toán không suy biến, ngược lại là bài toán suy biến. Để thuận tiện cho việc trình diễn những tác dụng triết lý cũng như thuật toángiải QHTT, người ta thường sử dụng hai dạng đặc biệt quan trọng của bài toán QHTT là bàitoán dạng chính tắc và bài toán dạng chuẩn. 2.1.2 Bài toán QHTT dạng chính tắcBài toán QHTT dạng chính tắc có dạng như sau : Hàm mục tiêu : max ( min ) ), , ( → = jjxcxxf ( 2.1 ) với những ràng buộc : mibxajij ÷ = = 1, ( 2.6 ) njx ÷ = ≥ 1,0 ( 2.7 ) Như vậy, bài toán QHTT dạng chính tắc gồm có 2 nhóm : nhóm những ràngbuộc dạng phương trình ( 2.6 ), nhóm ràng buộc dạng bất phương trình chỉ baogồm những ràng buộc về dấu ( 2.7 ). 2.1.3 Bài toán QHTT dạng chuẩnBài toán QHTT dạng chuẩn có dạng như sau : Hàm mục tiêu : max ( min ) ), , ( → = jjxcxxf ( 2.1 ) với những ràng buộc : mibxajij ÷ = ≥ 1, ( 2.8 ) njx ÷ = ≥ 1,0 ( 2.7 ) Bài toán QHTT dạng chuẩn chỉ gồm 1 nhóm những ràng buộc dạng bấtphương trình gồm có những ràng buộc về dấu là ( 2.8 ) và ( 2.7 ). 2.2 CÁC BƯỚC GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH TRONG EXCELĐể xử lý những bài toán QHTT ứng dụng Excel cung ứng cho chúng tamột công cụ khá có ích là Solver. Các bài toán QHTT dạng chính tắc và dạngchuẩn chỉ là những trường hợp riêng bài toán QHTT dạng tổng quát. Vì thế ở đây tasẽ xem xét cách xử lý bài toán QHTT dạng tổng quát rồi từ đó áp dụngtương tự cho hai dạng còn lại. 2.2.1 Cài thêm công cụ Add-ins SolverVào thực đơn Tools \ Solver. Nếu chưa thấy công dụng Solver trên thựcđơn Tools thì ta cần bổsung tính năng này vào Excel. Các bước triển khai : ( 1 ) Vào menu Tools \ Add-Ins, Open hành lang cửa số : Hình 2.1 Hộp thoại Add-ins chứa những công dụng lan rộng ra của Excel ( 2 ) Chọn Solver Add-Ins và chọn OK. 2.2.2 Xây dựng bài toán trong ExcelViệc thiết kế xây dựng bài toán trong Excel cũng tương tự như như việc kiến thiết xây dựng bàitoán khi tất cả chúng ta triển khai giải thủ công bằng tay thường thì. Sau khi nghiên cứu và phân tích đầubài tất cả chúng ta cần viết được hàm mục tiêu và những ràng buộc của bài toán rồi tiếnhành tổ chức triển khai tài liệu vào bảng tính. Ta xét ví dụ sau : Ví dụ 2.1 : Cho bài toán QHTT sau : Hàm mục tiêu : f ( x ) = 2 x + 8 x - 5 x + 15 xmaxvới ràng buộc : 3 x - x + x + 10 x = 5 + 2 x + x + 5x2 x + 10 x + 2 x - 5x2641, 0 ÷ = ≥ jxTổ chức tài liệu trên bảng tính : ¾ Biến quyết định hành động : được nhập tại những ô B7 : E7. Cho những giá trị khởi độnglà 0. ¾ Hàm mục tiêu f ( x ) : có giá trị địa thế căn cứ vào giá trị khởi động của những biến. Công thức tại ô F8. ¾ Các ràng buộc : nhập những thông số của những quan hệ ràng buộc tại những ôB10 : E12. Tính vế trái của những ràng buộc theo công thức tại những ô F10 : F12. Nhập những giá trị vế phải của những ràng buộc tại những ô G10 : G12. Theo bảng sau : Hình 2.2 Tổ chức bài toán trên bảng tínhSau khi nạp xong tài liệu vào bảng tính ta thực thi giải bài toán. 2.2.3 Tiến hành giải bài toán ( 1 ) Chọn ô F8 và chọn Tools \ Solver. Bảng hộp thoại Solver Parametersxuất hiện và gồm những thông số kỹ thuật sau : Hình 2.3 Hộp thoại khai báo những thông số kỹ thuật cho SolverTrong đó : Set Tanget Cell : Nhập ô chứa địa chỉ tuyệt đối của hàm mục tiêu. Equal To : Xác định số lượng giới hạn cho hàm mục tiêu hoặc giá trị cần đạt đếncủa hàm mục tiêu : Max, Min hay Value of tuỳ thuộc vào nhu yếu của bài. By Changing Cells : Nhập địa chỉ tuyệt đối của những ô ghi những giá trị banđầu của biến. Subject to the Constraints : Nhập những ràng buộc của bài toán. Cách làm của Solver là đổi khác giá trị của những biến tại By ChangingCells cho đến lúc giá trị của hàm mục tiêu tại Set Tanget Cell đạt một giá trị quyđịnh tại Equal To và đồng thời thoả mãn tập những ràng buộc tại Subject to theConstraints. Với ví dụ 2.1 ta thực thi khai báo những thông số kỹ thuật cho Solver như sau : ¾ Địa chỉ của hàm mục tiêu F8 được đưa vào Set Target Cell¾ Chọn Max tại Equal To để Solver tìm giải thuật cực lớn cho hàm mụctiêu. ¾ Nhập địa chỉ của những biến quyết định hành động B7 : E7 tại By Changing Cells. Hình 2.4 Khai báo hàm mục tiêu và những biến¾ Thêm những ràng buộc vào Subject to the Contraints : Nhấp nút Add, bảng Add Constraint Open và gồm những thông số kỹ thuật sau : Hình 2.5 Hộp thoại thêm những ràng buộcCell Reference : Ô hoặc vùng ô chứa công thức của những ràng buộc. Ô dấu : Cho phép ta lựa chọn dấu của những ràng buộc tương ứng. Constraint : Ô chứa giá trị vế phải của những ràng buộc tương ứng ( ta cũngcó 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ụ 2.1 những ràng buộc được nhập như sau : + Các ràng buộc về dấu : do41, 0 ÷ = ≥ jx ( những ràng buộc đều có dạng ) nên ta chọn vùng địa chỉ chứa biến B7 : E7 vào Cell Reference, chọn dấuvà nhập 0 vào Constraint : Hình 2.6 Thêm những ràng buộcChú ý : Nếu bài nhu yếu ràng buộc ( x ) là nguyên thì trong ô dấu ta chọnint, nếu là kiểu nhị phân ta chọn bin. + Tiếp tục chọn Add để nhập tiếp những ràng buộc phương trình và bấtphương trình : Cell Reference ConstraintF10 = G10F11 > = G11F12 < = G12Chọn OK để kết thúc việc khai báo những ràng buộc. Tuy nhiên, muốn hiệuchỉnh ràng buộc ta chọn ràng buộc và chọn Change, xoá ràng buộc ta chọn ràngbuộc từ list Subject to the Contraints và nhấp Delete. Hình 2.7 Khai báo những thông số kỹ thuật của bài toán¾ Sau khi hoàn tất ta chọn Solve để chạy Solver, hộp thoại hiệu quả xuấthiện và cho ta hai sự lựa chọn sau : Hình 2.8 Chọn kiểu báo cáoKeep Solver Solution : Giữ tác dụng và in ra bảng tính. Restore Original Values : Huỷ hiệu quả vừa tìm được và trả những biến vềtình trạng bắt đầu. Save Scenario : Lưu hiệu quả vừa tìm được thành một trường hợp để có thểxem lại sau này. Ngoài ra có 3 loại báo cáo giải trình là Answer, Sensitivity và Limits. Ở ví dụ 2.1 ta chọn Keep Solver Solution, OK. Bảng hiệu quả nhận đượcnhư sau : 10N hư vậy giải pháp cực biên tìm được là X = ( 0,3,0,0. 8 ) và giá trị cực đạicủa hàm mục tiêu f ( x ) là 36.2.2. 4 Giải thích thuật ngữTuy nhiên để tiện cho việc nghiên cứu và phân tích hiệu quả thì trong bảng SolverResults ta chọn thêm mục Answer Reports khi đó bảng tác dụng nhận được củaví dụ 2.1 như sau : Ta cần phải nắm vững một số ít thuật ngữ sau : Original Value : Giá trị bắt đầu. Final Value : Giá trị sau cuối. Formula : Công thức tính. Status : Trạng thái. Binding : Ràng buộc chặt. 11N ot Binding : Ràng buộc không chặt ( ràng buộc lỏng ). 2.3 CÁC LỰA CHỌN KHI GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH2. 3.1 Các lựa chọnĐể thiết lập những thuộc tính cho Solver thì trong bảng Solver Parametersta nhấp chuột vào Options hộp thoại Solver Options cho ta những lựa chọn sau : Hình 2.9 Thiết lập những thuộc tính cho SolverMax Time : Thời gian tối đa để giải bài toán là 32.767 giây ( mặc định là100 giây cho những bài toán đơn thuần ). Iterations : Số lần lặp tối đa để giải những bài toán là 32.767 lần ( mặc định là100 lần ). Precision : Độ đúng chuẩn của bài toán ( từ 0 đến 1, mặc định là 0.000001, giá trị càng gần với 0 thì độ đúng chuẩn càng cao ). Giá trị này kiểm soát và điều chỉnh độ sai sốcho tập ràng buộc. Tolerance : Chỉ vận dụng so với những bài toán có ràng buộc nguyên. Nhậpvào sai số hoàn toàn có thể gật đầu được. Sai số càng lớn thì vận tốc giải càng nhanh ( mặc định là 5 % ) Convergence : Chỉ vận dụng so với những bài toán không tuyến tính. Khi tỉsố của giá trị giám sát khởi đầu của ô đích đến giá trị đo lường và thống kê hiện hành ít hơngiá trị đồng quy Solver ngừng việc tìm kiếm dù có tìm thấy giải thuật hay không. 12G iá trị nằm trong khoảng chừng từ 0 đến 1. Giá trị càng gần 0 thì độ đúng mực càngcao và cần nhiều thời hạn hơn ( mặc định là 0.0001 ). Assume Linear Model : Khi tổng thể quan hệ trong quy mô là tuyến tính thìchọn mục này để tăng vận tốc giải bài toán. Assume Non-Negative : Chọn tuỳ chọn này nếu muốn giả định tổng thể cácbiến của bài toán đều không âm. Use Automatic Scaling : Chọn tuỳ chọn này khi ô đích và ô đổi khác có sựkhác nhau lớn. Solver sẽ tự động hóa kiểm soát và điều chỉnh những biến để tìm ra giải thuật. Chẳnghạn như bài toán tối đa % doanh thu trên hàng triệu đồng vốn góp vốn đầu tư. Show Iteration Results : Chọn tuỳ chọn này nếu muốn Solver tạm dừnglại và hiển thị hiệu quả sau mỗi lần lặp. Ba tính năng nâng cao điều khiển và tinh chỉnh cho Solver : Estimates : Chọn giải pháp cho Solver ước đạt những biến - Tangent : Sử dụng cách xê dịch tuyến tính bậc nhất. - Quandratic : Sử dụng cách xê dịch bậc bốn. Derivatives : Chọn cách để ước đạt hàm mục tiêu và những ràng buộc - Forward : Dùng khi giá trị của những ràng buộc đổi khác chậm ( đượcdùng thông dụng ). - Central : Dùng khi giá trị của những ràng buộc biến hóa nhanh và khiSolver báo không hề nâng cấp cải tiến tác dụng thu được. Search : Quy định giải thuật tìm kiếm tác dụng cho bài toán - Newton : là giải pháp mặc định, sử dụng nhiều bộ nhớ và có số lầnlặp ít. - Conjugate : cần ít bộ nhớ hơn chiêu thức Newton nhưng số lần lặpthì nhiều hơn. Được sử dụng khi giải những bài toán phức tạp và bộ nhớ máy tínhcó số lượng giới hạn. Save Model : Chọn nơi lưu quy mô bài toán. Sử dụng khi muốn lưu nhiềmô hình trên một worksheet. Mô hình tiên phong đã được lưu tự động hóa. Load Model : Xác định vùng địa chỉ của quy mô bài toán cần nạp vào. 132.3.2 Hạn chế khi giải bài toán quy hoạch tuyến tính trong ExcelHạn chế của bài trình cài thêm Solver là chỉ giải được những bài toán có tối dalà 16 biến số. Mặt khác số lần lặp tối đa để giải bài toán là 32767, thời hạn tối đađể giải bài toán là 32767 … nên cạnh bên đó nó còn sống sót một số ít mặt hạn chếnhất định về quy mô của bài toán và khó khăn vất vả trong việc tìm miền tối ưu. Đối với những bài toán tối ưu có quy mô lớn ta hoàn toàn có thể sử dụng phần mềmLindo đây là một ứng dụng tin học rất mạnh trong nghành này. 2.4 MỞ RỘNG BÀI TOÁNViệc ứng dụng quy mô QHTT trong quản trị kinh tế tài chính và quản trị doanhnghiệp là rất thông dụng. Chúng ta thường phát hiện quy mô này trong những bài toánnhư : bài toán lập kế hoạch sản xuất tối ưu cho doanh nghiệp, bài toán phân bổvốn góp vốn đầu tư, bài toán dự trữ … Tuy nhiên trong phần này xin trình diễn ra đây 2 loại bài toán QHTT thông dụng nhất là : bài toán nguyên vật liệu và bài toán vậntải. 2.4.1 Bài toán nguyên vật liệu¾ Bài toán tổng quátMột xí nghiệp sản xuất có năng lực sản xuất n loại loại sản phẩm. Để sản xuất những sảnphẩm này cần phải sử dụng m loại nguyên vật liệu. Biết rằng : ijlà lượng nguyên vật liệu loại i thiết yếu để sản xuất ra một đơn vị chức năng sảnphẩm loại jlà dự trữ nguyên vật liệu loại ilà doanh thu từ việc bán một đơn vị chức năng sản phẩm loại jvớimi, 1 = vànj, 1 = Bài toán được miêu tả theo bảng sau : … S … SDự trữNVL1 a11121j … a1nNVL2 a21222j … a2n … … … … … … … … 14NVL i1i2ij … ain … … … … … … … … NVLm1m2mj … amnLợi nhuận đơn vị chức năng c … cHãy tìm giải pháp sản xuất để tối đa hoá doanh thu. Bài giải : Gọi xlà lượng sản phẩm loại j mà xí nghiệp sản xuất sẽ sản xuất nên0xDo đó giải pháp sản xuất của nhà máy sản xuất là vectơ x = ( x, x, …, x, , x ). Khi đó : Tổng chi phí nguyên vật liệu loạiđể sản xuất x làjijxasẽ không vượtquá dự trữjijbxa ≤ = 1T ổng doanh thu thu được khi sản xuất x làjjxcVậy quy mô toán học của bài toán nguyên vật liệu hoàn toàn có thể phát biểu theomô hình bài toán QHTT như sau : Hàm mục tiêu : f ( x ) = jjxcmaxCác ràng buộc : mibxajij, 1, = ≤ n1, j0, x = ≥ Việc giải bài toán nguyên vật liệu trong Excel cũng gồm có 2 bước : B1 : Xây dựng bài toán ( lập bài toán và tổ chức triển khai tài liệu trên bảng tính ). B2 : Tiến hành giải bài toán bằng cách chạy Solver theo trình tự như trên. Ta xét một ví dụ đơn cử sau : ¾ Ví dụ 2.215 Một xí nghiệp sản xuất dự tính thực thi sản xuất 5 loại mẫu sản phẩm S1, 5 j = ). Cả 5 loại loại sản phẩm này đều sử dụng 4 loại nguyên vật liệu chính NVL4, 1 = i ). Cómức tiêu tốn nguyên vật liệu, doanh thu đơn vị chức năng thu được và số lượng giới hạn dự trữ nhưsau : Dự trữNVL2 5 6 8 41200NVL3 1 5 6 1800NVL7 5 4 5 22000NVL8 5 7 9 11865L ợi nhuận đơn vị300 250 500 150 320H ãy thiết kế xây dựng giải pháp sản xuất để nhà máy sản xuất đạt được tổng lợi nhuậnlớn nhất. Bài giải : B1 : Xây dựng bài toánGọi xvới j = 1,5 là sản lượng sản phẩm loại j sẽ sản xuất. ( x > = 0 ) Nên giải pháp sản xuất của nhà máy sản xuất là vectơ x = ( x, x, x, x, x ). Hàm mục tiêu : f ( x ) = 300 x + 250 x + 500 x + 150 x + 320 xmaxCác ràng buộc : 2 x + 5 x + 6 x + 8 x + 4 x < = 12003 x + x + 5 x + 6 x + x < = 8007 x + 5 x + 4 x + 5 x + 2 x < = 20008 x + 5 x + 7 x + 9 x + x < = 1865B ài toán được tổ chức triển khai trên bảng tính như sau : 16H ình 2.10 Lập bài toán trên bảng tínhB2 : Giải bài toán : Chọn ô G8 rồi triển khai lệnhTools \ Solver, điền rất đầy đủ thông tin vàohộp thoạiSolver Parametersnhư sauHình 2.11 Khai báo những thông số kỹ thuật của bài toánNhấnSolver để thựchiện việc chạy Solvers. Trong bảng hộp thoại kếtquảSolver Resultstích chọn mụcKeep Solver Solutionvà chọn thêm báo cáoAnswer Reportta nhận được hiệu quả : 17P hương án tối ưu ( giải pháp cực biên ) là x = ( 200, 0, 0, 0, 200 ) vớif ( x ) max = 124 000. Hay giải pháp sản xuât tối ưu của nhà máy sản xuất là sản xuất 200 đơn vị chức năng loại sản phẩm 1 và 200 đơn vị chức năng loại sản phẩm 5 khi đó doanh thu tối ưu đạt được là124 000 đơn vị chức năng tiền tệ. Không có nguyên vật liệu nào bị tiêu tốn lãng phí. 2.4.2 Bài toán vận tải¾ Bài toán tổng quát : Cóm kho hàng cùng chứa một loại hàng hoá, lượng hàng có ở kho i là ami, 1 = Cóđịa điểm tiêu thụ loại hàng nói trên, với nhu yếu tiêu thụ ở điểmlànj, 1 = 18B iếtijlà cước phí luân chuyển một đơn vị chức năng hàng hoá từ khođến điểm tiêuthụBài toán được diễn đạt theo bảng sau : … D … DDự trữ11121j … c1n21222j … c2n … … … … … … … … i1i2ij … cin … … … … … … … … m1m2mj … cmnNhu cầu tiêu thụ bHãy lập kế hoạch luân chuyển hàng từ những kho đến những điểm tiêu thụ saocho tổng ngân sách luân chuyển là nhỏ nhất. Bài giải : Gọiijlà lượng hàng luân chuyển từ khođến điểm tiêu thụnênnjmixij, 1, , 0 = = ≥. Ta có : Tổng chi phí luân chuyển : ∑ ∑ = = ijijxc11Lượng hàng luân chuyển khỏi khoijLượng hàng luân chuyển đến điểm tiêu thụijNhư vậy quy mô toán học của bài toán vận tải đường bộ hoàn toàn có thể viết dưới dạng bàitoán QHTT như sau : Hàm mục tiêu : f ( x ) = min11 ∑ ∑ = = ijijxcCác ràng buộc : ij19ij = bnjmixij, 1, , 1,0 = = ≥ Ta thấy ngay được điều kiện kèm theo cần và đủ để bài toán vận tải đường bộ có phương ántối ưu là tổng toàn bộ những lượng hàng tiêu thụ bằng tổng toàn bộ những lượng hàng ởcác kho, nghĩa là : ∑ ∑ = = ba11Cũng giống như bài toán nguyên vật liệu để thực thi giải bài toán trongExcel ta cần phải trải qua 2 bước là : thiết kế xây dựng bài toán và thực thi chạySolver. Xét ví dụ đơn cử sau : ¾ Ví dụ 2.3 Sử dụng công cụ Solver như đã trình diễn ở trên hãy lập giải pháp vậnchuyển xăng tối ưu từ 4 kho đến 5 trạm xăng kinh doanh nhỏ của một công ty kinh doanhxăng dầu khu vực V.Bài giải : B1 : Xây dựng bài toánGọiijlà lượng hàng luân chuyển từ khođến điểm tiêu thụnên5, 1,4,1,0 = = ≥ jixijHàm tiềm năng : f ( x ) = 30x11 + 27x12 + 26x13 + 9x14 + 23x15 + 13x21 + 4x22 + 22x23 + 3x24 + x25 + 3x31 + x32 + 5x33 + 4x34 + 24x35 + 16x41 + 30x42 + 17x4310 x44 + 16x45 minCác ràng buộc : 11 + x12 + x13 + x14 + x15 < = 421 + x22 + x23 + x24 + x25 < = 631 + x32 + x33 + x34 + x35 < = 1041 + x42 + x43 + x44 + x45 < = 1011 + x21 + x31 + x41 < = 712 + x22 + x32 + x42 < = 72013 + x23 + x33 + x43 < = 714 + x24 + x34 + x44 < = 715 + x25 + x35 + x45 < = 2T ổ chức tài liệu trên bảng tính như sau : Hình 2.12 Tổ chức bài toán trên bảng tínhBước 2 : Tiến hành giải bài toánChọn ôB16rồi dùng lệnhTools \ SolverHình 2.13 Khai báo những thông số kỹ thuật của bài toán21Sau khi nhập vừa đủ thông tin vào bảngSolver Parametersta chọnSolve \ Keep Solver Solution, OK.Ta được bảng hiệu quả sau : Phân tích hiệu quả : Vậy giải pháp luân chuyển là : x = ( 0,0,0,4,0,0,4,0,0,2,7,3,0,0,0,0,0,7,3,0 ) Vì tổng lượng xăng dự trữ ở những kho bằng tổng nhu yếu xăng ở những trạm ( 30 ) nên giải pháp tìm được là giải pháp tối ưu. Chú ý 1 : Nếu muốn có bảng tác dụng cụ thể để nghiên cứu và phân tích thì trong bảngSolver Resultsta chọn thêm mụcReports \ Answer ( hoặc \ vàSensitivityhoặc \ vàLimits ) tuỳ thuộc vào mức độ chi tiết cụ thể nhu yếu của bài. Chú ý 2 : Đối với những bài toán chưa tìm được lời giải mong ước ta cóthể đổi khác những thông số kỹ thuật nguồn vào của bài toán rồi chọn Tools \ Solver để tìm raphương án tối ưu. 2.5 ỨNG DỤNG EXCEL ĐỂ GIẢI HỆ PHƯƠNG TRÌNH TUYẾN TÍNH22Dạng tổng quát của hệ phương trình tuyến tính là hệphương trình đạisố bậc nhất đối vớiẩn số : 11 + a12 + … + a1n = b21 + a22 + … + a2n = b ( * ) … … … … … … … … … … … m1 + am2 + … + a1m = bvới x, x, …, xlà những ẩn số ; aijlà thông số ở phương trình thứ i của ẩn x ; blà vế phải của phương trình. Khi m = n ta có hệ phương trình vuông với n phương trình n ẩn. Khi b = 0 ta có một hệ thuần nhất. Toán học đã phân phối cho tất cả chúng ta khá nhiều giải pháp để giải những hệphương trình tuyến tính như : giải pháp thế, giải pháp cộng đại số, giải pháp ma trận - định thức … Phần mềm Excel cũng phân phối cho ta haicông cụ rất thuận tiện, nhanh gọn và đúng chuẩn để thực thi giải hệ phương trìnhtuyến tính là : sử dụng trình cài thêmSolvervà sử dụng phối hợp hai hàmMINVERSEvàMMULT2. 5.1 Giải hệ phương trình bằng SolverNgoài ứng dụng để giải những bài toán QHTTSolvercòn hoàn toàn có thể ứng dụng đểgiải những bài toán về hệ phương trình. Khi đó chỉ có những ràng buộc dạng phươngtrình và không có hàm mục tiêu. Các bước thực thi giải hệ phương trình hoàntoàn tương như khi giải bài toán QHTT. Để hiểu hơn ta triển khai xét ví dụ sau : Ví dụ 2.4 : Giải hệ phương trình sau : 2 x + 4 x + 3 x = 43 x + x - 2 x = - 24 x + 11 x + 7 x = 7B ước 1 : Tổ chức tài liệu vào bảng tínhNhập những thông số, vế phải của phương trình và cho giá trị khởi động cho cácbiến vào bảng tính như hình sau : 23H ình 2.14 Lập bài toán trên bảng tínhBước 2 : Giải hệ phương trìnhChọnTools \ Solver, OK. Rồi triển khai điền vừa đủ thông tin vào hộpthoạiSolver Paraments ( bỏ trống mụcSet Target Cell ). Hình 2.15 Khai báo những thông số kỹ thuật của bài toánSau khi điền vừa đủ thông tin ta nhấpSolve. Trong bảng hộp thoạiSolverResultsta kiểm vàoKeep Solver Solutionđể lưu hiệu quả trên bảng tính. 24H ình 2.16 Chọn loại báo cáoChọnOKđể hoàn tất quy trình chạy SolverTa được bảng tác dụng nhưsau : Vậy nghiệm tìm được của hệ phương trình là : x = 1, y = - 1, z = 2. Không chỉ sử dụng Solver để giải hệ phương trình ứng dụng Excel còncung cấp thêm một công cụ nữa để giải hệ phương trình bằng chiêu thức matrận là sử dụng hàmMINVERSEvàMMULT2. 5.2 Giải hệ phương trình bằng hàm MINVERSE và hàm MMULTKhi hệ phương trình ( * ) có m = n thì nó trở thành hệ vuông gồm nphương trình n ẩn. Khi đó ma trận thông số A, ma trận biến X sẽ là một ma trậnvuông cấp n và ma trận của vế phải hệ phương trình B là : 1112 … a1n1112 … a1n2122 … a2n2122 … a2nA = … … … … … X = … … … … … n1n2 … annn1n2 … annB = b … bVậy hệ ( * ) được viết lại là : A * X = B ( * * ) nên X = A-1 * B ( * * * ) 252.5.1.1 Giới thiệu hàm MINVERSE và hàm MMULT  Hàm MINVERSELà hàm dùng để tìm ma trận nghịch đảo. Cú phápMINVERSE ( array ) array : là địa chỉ ma trận cần nghịch đảo. Ví dụ 2.5  Hàm MMULTLà hàm dùng để nhân 2 ma trận. Cú phápMMULT ( array1, array2 ) array1, array2 : là địa chỉ của những ma trận cần nhân. Ví dụ 2.6 Chú ý : - Nhấn tổng hợp phímCtrl + Shift + Entersau khi nhập xong côngthức. - Chỉ khi là ma trận vuông nếu không khi sử dụng hàm này sẽ báolỗi # VALUE !. - Nếu có thành phần nào trong ma trận là rỗng hoặc là chữ thì báo lối # VALUE !. 2.5.2. 2 Giải hệ phương trìnhQuá trình giải hệ phương trình bằng chiêu thức ma trận sử dụng haihàmMINVERSE và MMULT được thực thi theo 3 bước sau :

Source: https://mindovermetal.org
Category: Ứng dụng hay