PHẦN I: TÓM TẮT NỘI DUNG
1.1. Tên giải pháp:
“SỬ DỤNG CÔNG CỤ SOLVER TRONG EXCEL ĐỂ GIẢI BÀI TOÁN
QUY HOẠCH TUYẾN TÍNH”
1.2. Yếu tố mới và sáng tạo: Giải pháp hoàn toàn mới, được áp dụng lần đầu
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 theomục tiêu định
trước là hết sức quan trọng. Nếu tất cả các yếu tố 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 quản lý kinh tế. Trong môn học Toán cao cấp việc giải bài
toán quy hoạch tuyến tínhthông thường được thực hiện bằng thuật toán đơn
hình.Tuy nhiên đa phần sinh viên đạt điểm không cao hoặc phải thi lại, học lại.
Nguyên nhân chủ yếu là do các em chưa quen với cách học, cách giảng dạy trên đại
học, chưa thích ứng kịp với các khái niệm mới khiến việc học khó khăn.
Để đáp ứng được nhu cầu hiện nay, bản thân đã nghiên cứu công cụ hỗ trợ
Solver trong phần mềm Excel để giải quyết các bài toán về quy hoạch tuyến tính
hiệu quả, chính xác và nhanh chóng.Và đây cũng là đề tài nghiên cứu trong năm
nay.
1.3 Phạm vi áp dụng: Đề tài này là sự đúc kết của bản thân và có thể được áp
dụng cho các cá nhân hoặc các tổ chức khác cần giải quyết các bài toán lập kế
hoạch sản xuất tối ưu với tài nguyên có hạn.
Hiệu quả của giải pháp: Sử dụng công cụ Slover trong phần mềm Excel để
giải các bài toán quy hoạch tuyến tính dễ dàng và hiệu quả. Cụ thể:
-

Tiết kiệm được thời gian so với phương pháp thủ công
Chỉ vài cú click chuột

người ta không hề nghĩ tới, kể cả khoa học và xã hội.
Với những hiệu quả kinh tế mà toán học đem lại mà nhiều trường cao đẳng,
đại học cả nước đều đưa vào giảng dạy với bộ môn toán cao cấp cho nhiều ngành
nghề khác nhau. Trong bộ môn này, có một bộ phận gắn liền với việc quản lý, lập
kế hoạch sản xuất sao cho kết quả mang lại là tối ưu với chi phí thấp. Đó chính là
bộ phận quy hoạch tuyến tính.
II.

NHỮNG KHÓ KHĂN
 Quy hoạch tuyến tính là học phần đại cương sinh viên thường được học ở
năm thứ nhất và cũng là một khó khăn lớn của sinh viên. Học phần này là
mô ̣t phầ n của toán cao cấ p và nằ m trong phầ n kiế n thức đa ̣i cương, kiế n thức
không phải ở mức khó, tuy nhiên đa phần sinh viên lại đạt điểm không cao
hoặc phải thi lại, học lại. Nguyên nhân chủ yếu là do các em chưa quen với
cách học, cách giảng dạy trên đại học, chưa thích ứng kịp với các khái niệm
mới khiến việc học khó khăn.
 Học Toán cao cấp không quá khó. Cái khó là mới vào đại học chưa quen với
môi trường mới, cách giảng dạy của thầy cô và cách tự học, tự tìm hiểu theo
định hướng. Nếu sinh viên không thay đổi và tìm ra cách học phù hợp thì
chắc chắn đến lúc thi sẽ bị điểm thấp.
Trang 2


 Khó khăn lớn nhất đối với sinh viên là việc tìm lời giải cho bài toán tối ưu
với chi phí tính toán rất lớn do dữ liệu cần xử lý và số phương án quá nhiều.
Vì vậy, việc tính toán thủ công để tìm phương án tối ưu trong thực tế là
không khả thi hoặc tốn rất nhiều thời gian.
Thí dụ: Bài toán lập kế hoạch sản xuất tối ưu với tài nguyên có hạn.
Một nhà máy sản xuất hai loại sản phẩm (I) và (II) từ hai loại nguyên liệu A và
B. Biết rằng mỗi sản phẩm loại I cần 4 đơn vị nguyên liệu A và 2 đơn vị nguyên

pháp đơn hình, gồm các bước sau:
Bước 1: Khởi đầu.
Lập bảng đơn hình (1) ứng với phương án xuất phát X(1): xác định các ẩn cơ sở,
các hệ số để đưa vào bảng đơn hình khởi đầu.
Trang 3


Bước 2: Kiểm tra điều kiện tối ưu
(a) Tính các ∆j
(b) Kiểm tra điều kiện tối ưu: ∆j≥0 ∀j.
Nếu thỏa mãn: dừng thuật toán. Chuyển sang bước 4.
Nếu vi phạm điều kiện tối ưu, tức là còn có giá trị ∆j< 0 (với cột j nào đó),
chuyển sang bước 3.
- Sau hai bước trên, ta có bảng đơn hình đầu tiên, với các giá trị ∆j ở dòng cuối.
Do điều kiện tối ưu bị vi phạm, ta chuyển sang bước 3.
Bảng đơn hình (1)
Hệ số ci Ẩn cơ sở Phương
c1 =8
c2 = 6
c3 = 0
c4 = 0
án
x1
x2
x3
x4
0
x3
60
4

mới.
(e) Tính toán các hệ số trong bảng đơn hình mới (bảng 2), ta nhận được phương án
X(2):
- Chia tất cả dòng xoay cũ cho phần tử trục (kể cả ở cột phương án), sau đó
chuyển dòng mới vào vị trí tương ứng ở bảng mới (gọi là dòng xoay mới).
- Biến đổi để các phần tử cùng cột với cột xoay cũ có dạng vecto đơnvị, với
phần tử trục bằng 1, bằng phép biển đổi Gauss cho ma trận hệ số và cả cột
phương án, đưa kết quả vào bảng mới sau đó chuyển sang bước 2.
Bảng đơn hình (2)
Hệ số ci Ẩn cơ sở Phương
c1 =8
c2 = 6
c3 = 0
c4 = 0
án
x1
x2
x3
x4
8
x1
15
1
1/2
1/4
0
0
x4
8
0

1/6
6
x2
8
0
1
-1/6
1/3
∆1 = 0
∆2 =0
∆3 =5/3
∆4 =2/3
∆j =∑ 𝑐𝑖 . 𝑎𝑖𝑗 − 𝑐𝑖
Điều kiện tối ưu đã thỏa mãn với bảng (3): ∆j ≥ 0 ∀j. Chuyển sang bước 4.
Bước 4: Xác định nghiệm bài toán.
(a) Phương án trên bảng là tối ưu: X3 = (12, 6, 0, 0)
khi đó ta chọn phương án tối ưu của bài toán gốc là :
X* = (12, 6).
(b) Giá trị hàmmụctiêu: fmax = f(X*) = 8*12+6*6 = 132.
Rõ ràng, bằng thuật toán đơn hình, chúng ta dễ dàng tìm ra được giá trị của hàm
mục tiêu. Nhưng việc xử lý tính toán và thời gian bỏ ra để hoàn thành công việc là
rất lớn. Do đó, chúng ta nên cần chọn một công cụ hỗ trợ để giải quyết các bài toán
tối ưu.
III.

GIẢI PHÁP KHẮC PHỤC

Trước những băn khoăn của sinh viên về việc làm thế nào để vượt qua cái khô
khan của toán học cũng như vai trò của nó trong đời sống xã hội. Để giải quyết khó
khăn này, Microsoft Excel đã xây dựng công cụ Solver giúp giải các bài toán tối

Hàm mục tiêu:

f(x) = 8x1+ 6x2+ 0x3 +0 x4 max

Điều kiện ràng buộc:

Trang 7


4𝑥1 + 2𝑥2 + 𝑥3
= 60
+ 𝑥4 = 48
{ 2𝑥1 + 4𝑥2
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ≥ 0
Tổ chức dữ liệu trên Excel
 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.
 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:E11.
Tính vế trái của các ràng buộc theo công thức tại các ô F10:F11. Nhập các
giá trị vế phải của các ràng buộc tại các ô G10:G11.
Theo bảng sau:

Tiến hành giải bài toán
(1) Chọn ô F8 và chọn Data | Solver. Bảng hộp thoại Solver Parameters
xuất hiện và gồm các thông số sau:

Trang 8




Chú ý: Nếu bài yêu cầu ràng buộc (xj) 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 Ô dấu
Constraint
F10
=
G10
F11
=
G11
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.

Trang 10


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

Trang 11


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ể

Rạch Giá, ngày 15 tháng 05 năm 2016

Trang 13