76

CHƯƠNG
3
Quy hoạch tuyến tính
và những ứng dụng trong
hệ thống nguồn nớc

3.1. Quy hoạch tuyến tính
Mô hình quy hoạch tuyến tính (QHTT) đã và đang đợc áp dụng rộng
rãi trong các bài toán phân bổ tối u tài nguyên. Nh tên của nó gợi ý, mô
hình QHTT có hai tính chất cơ bản là cả hàm mục tiêu và các ràng buộc là
các hàm tuyến tính của các biến quyết định. Dạng tổng quát của một mô
hình QHTT có dạng:
Max (hoặc Min)
j
n
j
j
xcx



1
0
(3.1.1a)

2
x
2
+ + c
n
x
n
(3.1.2a)
Với các ràng buộc:
a
11
x
1
+ a
12
x
2
+ + a
1n
x
n


b1
a
12
x
2
+ a
22

x
2
+ + a
mn
x
n


b
m

x
1


0; x
2


0, x
n


0
ở dạng ma trận, mô hình QHTT có thể viết chính xác là:
Max (hoặc Min) x
0
= C
T
x

, và (2) lợng chất thải đổ trực tiếp
vào sông không qua xử lí, x
2
. Từ sự mô tả mối quan hệ qua lại giữa thành phẩm, lợng chất thải đợc
tạo ra, hiệu suất nhà máy xử lí, một sơ đồ minh họa hệ thống nghiên cứu có thể đợc thiết lập và thể
hiện trên hình 3.1.1. Lợng chất thải ở mỗi nhánh có thể đợc xác định bằng nguyên lý cân bằng
khối lợng.
Vấn đề cốt lõi cần làm trớc khi xây dựng mô hình là xác định mục tiêu và các ràng buộc của bài
toán. Trong ví dụ này, mục tiêu của bài toán tối đa lợi nhuận thực. Các ràng buộc gây ra bởi các hạn
chế về công suất nhà máy xử lí chất thải và lợng chất thải cho phép đổ vào sông đợc quy định với
các nhà kiểm soát ô nhiễm nớc. Khi đã xác định đợc mục tiêu và các ràng buộc của bài toán, bớc
xây dựng mô hình tiếp theo về cơ sở liên quan đến việc chuyển hóa các mô tả các mục tiêu và ràng
buộc bằng ngôn ngữ sang sự diễn tả bằng toán học thông qua các biến quyết định và các thông số.
Lãi thực của nhà máy sản xuất đợc xác định dựa trên 4 yếu tố: (a) số lợng bán ra các thành phẩm
(tính bằng nghìn đô la) giá thành sản xuất của các thành phẩm (tính bằng nghìn đô la), 3x
1
; (c) chi
phí cho việc xử lí chất thải (nghìn đô la) tạo ra từ quá trình sản xuất, 0,6(2
x1
-x
2
) và (d) thuế ảnh hởng
(nghìn đô la) đánh vào lợng chất thải không qua xử lí, 2{x
2
+0,2(2x
1
-x
2
)}. Lợi nhuận thực của nhà
máy bằng tổng lợng tiền thu đợc trừ đi tổng các chi phí. Hàm mục tiêu của bài toán là tối đa hóa


Theo hình. 3.1.1, ràng buộc do hạn chế về công suất của nhà máy xử lí nớc thải có thể diễn tả bằng
công thức toán học là:
2x
1
- x
2


10

Hình 3.1.1
Sơ đồ mô tả hệ thống sản xuất xử lí chất thải.
Ràng buộc này cho thấy lợng chất thải đợc xử lí, 2x
1
- x
2
, không thể vợt quá công suất của nhà
máy, bằng 10 đơn vị chất thải. Tơng tự, ràng buộc liên quan đến tổng lợng chất thải có thể đổ vào
sông đợc diễn giải là:
x
2
+ 0,2(2
x1
- x
2
)

4
ở đó, vế trái (LHS) của điều kiện ràng buộc này là tổng lợng chất thải đổ vào sông (xem hình 3.1.1)

Max x
0
= 5x
1
- x
2

Với các ràng buộc:
2x
1
- x
2


10
4x
1
+ 0,8 x
2


4
2x
1
- x
2


0
x

j
, tỷ lệ trực tiếp với giá trị của
biến quyết định tơng ứng.
2. Giả thiết về tính cộng hợp. Giả thiết này có nghĩa là, tại một
cấp độ hoạt động cho trớc (x
1
, x
2
, x
n
), tổng lợng sử dụng các
tài nguyên và sự đóng góp vào giá trị hiệu quả tổng hợp bằng tổng
các giá trị tơng ứng đợc tạo ra bởi các hoạt động tiến hành riêng
biệt.
3. Giả thiết về tính khả chia. Các đơn vị của các hoạt động có
thể đợc chia ra làm nhiều cấp độ phân chia, do đó giá trị không
nguyên của các biến quyết định là chấp nhận đợc.
4. Giả thiết về tính tất định. Tất cả thông số của mô hình đợc
giả thiết là không đổi và không có tính bất định. ảnh hởng của
tính bất định của các thông số tới kết quả có thể đợc điều tra
bằng việc tiến hành phân tích độ nhậy.
3.1.2. Các dạng của bài toán QHTT
Do các mô hình QHTT có thể đợc thể hiện dới nhiều dạng khác nhau
(tối đa hóa, cực tiểu hóa,

,

,

), việc cần thiết là phải thay đổi các dạng

, 1,2, ,
0. 1,2, ,
n
i j i
j
j
a x b i m
x j n

với
với
(3.1.4b)
Ví dụ 3.1.2. Biến đổi mô hình QHTT của ví dụ đợc nêu ở mục trớc về sản xuất, xử lí nớc thải
sang dạng chính tắc.
Lời giải. Vì hàm mục tiêu có dạng chính tắc có thể là cực đại hóa hay cực tiểu hóa nên không cần
thiết phải biến đổi hàm mục tiêu này. Tuy nhiên, dạng chính tắc của mô hình QHTT đòi hỏi tất cả cá
ràng buộc phải ở dạng phơng trình. Điều này không thỏa mãn với cả 3 ràng buộc của mô hình ta
đang xét. Do vậy cách biến đổi là điều kiện cần thiết. Chú ý rằng vì ràng buộc đầu tiên có dạng ,
một biến ảo (slack variables) không âm s
1
có thể đợc cộng vào vế trái của ràng buộc, trở thành:
2x
1
- x
2
+ s
1

Max x
0
= 5x
1
- x
2
+ 0s
1
+ 0s
2
+ 0s
3

Với ràng buộc:
2x
1
- x
2
+ s
1
= 10
0,4 x
1
+ 0,8x
2
+ s
2
= 4
2x
1

ij j i
j
j
a x b i m
x j n

(3.1.5b)
Cần chú ý rằng các hệ số ở vế phải của ràng buộc có thể mang giá trị âm.
Ví dụ 3.1.3. Chuyển đổi mô hình QHTT gốc cho ví dụ sản xuất, xử lí nớc thải sang dạng chuẩn.
Lời giải: Vì hàm mục tiêu nguyên bản đã có dạng tối đa hóa nh yêu cầu nên không cần có sự biến
đổi thêm đối với nó. Đối với các ràng buộc, hai ràng buộc ban đầu có dạng nên thỏa mãn yêu cầu
của dạng chuẩn. Tuy nhiên, ràng buộc thứ 3 có dạng , để chuyển nó sang dạng ta nhân cả hai vế
ràng buộc này với -1 và có kết quả nh sau:
-2x
1
+ x
2


0
Yêu cầu không âm của các biến quyết định cùng đợc thỏa mãn. Cuối cùng chúng ta có mô hình
QHTT dới dạng chuẩn sau:
Max (x
0
) = 5x
1
- x



0
Thông thờng, mô hình QHTT sau khi đợc xây dựng thờng không
thỏa mãn các đặc tính của dạng chính tắc cũng nh dạng chuẩn. Các biến
đổi cơ sở sau đây giúp các bạn có thể chuyển đổi một mô hình QHTT sang
bất kỳ dạng nào:
1. Tối đa hóa một hàm f(x) thì tơng ứng với tối thiểu hóa giá trị âm
của nó, có nghĩa là: Max f(x) = Min {-f(x)}
2. Các ràng buộc có dạng có thể chuyển đổi sang dạng bằng cách
nhân hai vế của bất phơng trình với -1
3. Một phơng trình có thể đợc thay thế bằng hai bất phơng trình
trái dấu nhau. Ví dụ, phơng trình g(x) = b có thể đợc thay thế
bằng g(x)

b và g(x)

b.
4. Một bất phơng trình có dấu giá trị tuyệt đối có thể thay thế bằng
hai bất phơng trình không có dấu giá trị tuyệt đối. Ví dụ,
( )
g x b


không thể thay thế bằng g(x)

b và g(x)

-b
5. Nếu một biến quyết định x không có ràng buộc về dấu (có thể

để lãi thực của
nhà sản xuất là lớn nhất.
Lời giải. Xét mô hình QHTT xây dựng cho bài toán ở ví dự 3.1.1, nó liên quan đến hai biến quyết
định và ba ràng buộc (ngoại trừ các yêu cầu không âm của các biến quyết định). Miền nghiệm
(feasible space) đợc xác định bởi tất cả các ràng buộc của mô hình, bao gồm cả ràng buộc không âm
của các biến quyết định. Do hai biến quyết định không thể âm, miền nghiệm phải nằm trong góc
phần t thứ nhất (Đông Bắc). Miền nghiệm (vùng gạch chéo) cho bài toán ví dụ này đợc thể hiện
trên hình 3.2.1. Mỗi đờng liền nét trên hình 3.2.1 đợc xác định từ mỗi ràng buộc tơng ứng ở
phơng trình, và hai trục thể hiện hai điều kiện không âm của hai biến quyết định x
1
và x
2.
Mũi tên
trên mỗi đờng chỉ ra nửa mặt phẳng mà trên đó tất cả các điểm thỏa mãn ràng buộc này. Miền
nghiệm do đó là miền giao của tất cả các nửa mặt phẳng khả thi và tất cả các điểm trên miền nghiệm
thỏa mãn đồng thời tất cả các ràng buộc. Mỗi điểm thuộc miền này là một nghiệm khả thi cho mô
hình tối u.

Do giá trị của lợi nhuận thực tối đa là cha biết, một quá trình thử sai cần đợc tiến hành. Đầu tiên, ta
vẽ một đờng thẳng x
0
= 0 để cho hàm mục tiêu tơng ứng đi qua gốc tọa độ. Về mặt toán học mà
nói, tất cả các điểm (x
1
, x
2
) nằm trên đờng
5x
1
- x

dơng và tăng liên tục khi đờng này đợc chuyển xa về phía phải. Tuy nhiên, đờng này không thể
dịch chuyển sang phải một cách vô hạn kể cả khi nó liên tục làm tăng lợi nhuận thực. Nh có thể
nhận thấy, sau khi vợt qua điểm C, đờng thẳng hàm mục tiêu không chứa một nghiệm khả thi nào.
Trong ví dụ này, có thể kết luận rằng, cặp x
1
, x
2
tại điểm C, (6,2), là nghiệm tối u của bài toán. Lợi
nhuận thực có thể đạt đợc của nhà xuất là 5 (6) - 1 (2) = 28 nghìn đô la
Phơng pháp đồ giải chỉ áp dụng đợc cho những bài toán có chứa hai
biến quyết định. Đối với các bài toán có nhiều hơn hai biến quyết định,
hình dạng của các hàm mục tiêu và các phơng trình ràng buộc có dạng các
mặt đa diện lồi trong không gian n-chiều.
3.2.2. Các điểm cực trị (điểm góc) khả thi
Trong ví dụ minh họa vừa rồi, nghiệm tối u của bài toán QHTT tìm
đợc khi sử dụng phơng pháp đồ nằm tại một điểm góc của miền nghiệm
(gọi là điểm khả thi cực trị). Cần nhấn mạnh rằng, không có gì là đặc biệt 83
và trùng hợp về ví dụ này và dẫn đến một kết quả nh vậy. Thực tế, đối với
tất cả các bài toán QHTT nghiệm tối u luôn rơi vào biên của miền nghiệm.
Các điểm cực trị khả thi trong một bài toán QHTT có ba tính chất quan
trọng. ý nghĩa của nó đối với kỹ thuật giải đại số sẽ đợc mô tả ở phần sau.
Những tính chất sau đây đợc đa ra không kèm với chứng minh toán học.
Những chứng minh này có thể tìm thấy ở các sách QHTT hay sách quy
hoạch toán (Dantzig, 1963, Bradley, Hax và Magrati, 1977; và Taha, 1987).
Tính chất 1a: Nếu mô hình QHTT chỉ có duy nhất một nghiệm tối u,
nghiệm này phải nằm tại một điểm cực trị khả thi. Tính chất 1b. Nếu bài
toán có nhiều nghiệm tối u, ít nhất hai trong số các nghiệm tối u nằm tại

nghiệm tối u không thể xác định đợc trớc khi tất cả các điểm cực trị khả
thi đợc liệt kê và xem xét.
Tính chất 3: Nếu một điểm cực trị khả thi tốt hơn (đánh giá với x
0
) tất
cả các điểm khả thi bên cạnh nó thì nó cũng tốt hơn tất cả các điểm cực trị
khả thi còn lại (có nghĩa là nó là một điểm tối u toàn cục.)
Từ tính chất này ta không phải đi liệt kê và xem xét tất cả các điểm cực
trị khả thi để tìm đợc nghiệm tối u của bài toán. Thay vào đó, vị trí của
một điểm cực trị khả thi đang xem xét có thể đợc khẳng định đơn giản
bằng việc so sánh nó với các điểm cạnh nó. Nếu tính chất 3 đợc thỏa mãn, 85
điểm cực trị khả thi mà ta đang xét là nghiệm tối u toàn cục của bài toán
QHTT.
Nên nhấn mạnh rằng yêu cầu cơ bản cho tính chất này tồn tại là miền
nghiệm là lồi. Nếu không, nghiệm tối u thu đợc sẽ không đợc đảm bảo
là nghiệm tối u toàn cục mà chỉ là nghiệm tối u cục bộ. Hiện tợng này
đặc biệt thờng xuyên xảy ra trong các bài toán quy hoach phi tuyết tính.
May mắn là miền nghiệm của các bài toán QHTT hầu nh là luôn luôn lồi.
3.2.3. Thuật giải cho các bài toán quy hoạch tuyến tính
ở mục này ba tính chất quan trọng của điểm cực trị khả thi thảo luận
trớc đây sẽ đợc ứng dụng vào một bài toán QHTT và một thuật giải sẽ
đợc thiết kế để giải bài toán QHTT này. Chúng ta quay lại bài toán sản
xuất, xử lí chất thải trớc đây. Nh đợc mô tả ở hình 3.2.1, mô hình QHTT
có bốn điểm cực trị khả thi. Đầu tiên, ta phải xác định điểm xuất phát cho
việc tìm kiếm nghiệm tối u. Hiển nhiên là nếu điểm xuất phát gần với
điểm tối u, ta có thể hy vọng việc tìm kiếm nghiệm sẽ nhanh hơn. Tuy
nhiên, nhìn chung là rất khó có thể xác định ngay từ đầu một điểm xuất

và loại bỏ bởi điểm D trong bớc trớc đây). Giá trị của x
0
tại điểm C là tốt
hơn so với tất cả các điểm CTKT bên cạnh (điểm B và D). Từ tính chất thứ
ba của các điểm CTKT thảo luận trớc đây, ta có thể kết luận rằng nghiệm 86

tối u của ví dụ sản xuất, xử lí chất thải là sản xuất 6 đơn vị thành phẩm và
đổ trợc tiếp hai đơn vị chất thải ra sông mà không qua xử lí. Điều đó cũng
có nghĩa là có 2(6) - 2=10 đơn vị chất thải đi qua nhà máy xử lí. Giá trị lãi
ròng tơng ứng là 28 nghìn đô la.
Các bớc đợc mô tả trên đây (sử dụng 3 tính chất của các điểm CTKT
để giải một mô hình QHTT) hình thành khái niệm về một thuật giả nổi
tiếng đợc gọi là Phơng pháp đơn hình (Simplex method). Phơng pháp
này là một quy trình tổng quát để giải các bài toán QHTT. Nó là một
phơng pháp rất hiệu quả đã đợc áp dụng để giải các bài toán lớn hơn liên
quan đến hàng trăm các biến quyết định và ràng buộc trên máy tính điện tử.
Các chơng trình máy tính dựa trên phơng pháp đơn hình có mặt rộng rãi
để sử dụng.
Ví dụ 3.2.2. Giải bằng phơng pháp đại số bài toán sản xuất, xử lí chất thải của ví dụ 3.2.1.
Lời giải. Hàm mục tiêu và các ràng buộc có thể đợc viết nh sau:
Hàm mục tiêu: x
0
- 5x
1
+ x
2
+ 0s

+ x
2
+ 0s
1
+ 0s
2
+ s
3
= 0
Bớc đầu tiên bắt đầu với điểm CTKT (x
1
= 0 và x
2
= 0)
Bớc lặp 1
Bớc lặp bắt đầu bằng việc lựa chọn hoặc biến x
1
hoặc biến x
2
nên tăng giá từ giá trị 0, Do x
1
có hệ số
âm lớn nhất (-5) nên nó sẽ có tác động lớn nhất cho việc làm tăng hàm mục tiêu. Quyết định tiếp theo
là cần tăng x
1
lên bao nhiêu. Cần nhớ rằng các biến ảo không bao giờ có giá trị âm. Đầu tiên kiểm tra
ràng buộc 1 bằng cách tìm giá trị x
1
với s
1

3
= 0
s
3
= 10
Vì các biến ảo vẫn giữ giá trị dơng với x
1
= 5. Ta xét ràng buộc 2 và tìm giá trị của x1 với x
2
= 0 và
s
2
= 0,
Ràng buộc 2: 0,4x
1
+ 0,8 (0) + 0s
1
+ 0 + s
3
= 4
x
1
= 10
Bây giờ chúng ta đi kiểm tra ràng buộc 1 và 3
Ràng buộc 1: 2(10) - 0 + s
1
+ 0s
2
+ 0s
3

+ 0s
1
+ 0s
2
+ 0 = 0
x
1
= 0
Điều này nói lên rằng nó không di chuyển khỏi vị trí xuất phát. 87
Kết quả của sự phân tích trên cho ta thấy giá trị lớn nhất của x
1
có thể tăng đợc là x
1
= 5, với x
2
= 0,
s
2
= 2,
s3
= 10, Nhìn lại hình 3.2.2, điểm này chính là điểm D. Giá trị hàm mục tiêu x0 tơng ứng với
nghiệm khả thi tại điểm D là:
x
0
- 5(5) + 0 + 0s
1
+ 0s

x x s s s


Ràng buộc 1:
1 2 1 2 3
1 1
0 0 5
2 2
x x s s s


Ràng buộc 2:
2 1
2 1 2 3
0,4(5 ) 0,8 0 0 4
2 2
x s
x s s s


1 2 1 2 3
0 0.2 0 2
x s s s s


Ràng buộc 3:
2 1
2 1 2 3
2(5 ) 0 0 0
2 2

Ràng buộc 1:
2
x
= 2
1
x
-10 Nếu
1
x
và
2
x
>0 thì
1
s
=0
Ràng buộc 2:
2
x
= 2 + 0,2
1
s
-
2
s
Nếu
1
x
và
2

2
x
= 2
1
x
-10, ta có
1
x
=6. Đối với hàm mục tiêu ta thay
2
2
x

vào, có:
0 1 2 1 2 3
0 1 2 1 2 3
0 1 2 3
0 1 2 1 2 3
3 5
(2 0, 2 ) 0 0 25
2 2
3 5
3 0,3 0 0 25
2 2
3
2,2 0 28
2
0 0 2,2 1,5 0 25
x s s s s s
x s s s s s

3. Luật dừng: Dùng các bớc lập khi điểm CTKT hiện tại là tốt hơn
so với các điểm bên cạnh nó.
3.3. Phơng pháp đơn hình
3.3.1. Các khái niệm đại số và thiết lập cơ bản
Nh đã đợc minh hoạ từ trớc, mô hình QHTT sử dụng phơng pháp
đồ giải cũng nh hớng tiếp cận tìm kiếm có thể đợc thực hiện dễ dàng khi
bài toán chỉ bao gồm hai biến quyết định. Mục đích của ví dụ trên chỉ là để
minh hoạ các khái niệm hình học của phơng pháp đơn hình và thuật toán
cơ bản của nó. Để giải các bài toán có quy mô lớn hơn, xét về số lợng các
biến quyết định và các ràng buộc, các phơng pháp đợc đề cập trớc đây
không thể áp dụng đợc. Hơn nữa, để thực hiện các thuật toán giải trên máy
tính, các vấn đề phải đợc diễn giải đại số. 89

Hình 3.2.2
Minh họa thuật giải đại số bài toán QHTT.
Trong việc giải bài toán sử dụng các quy trình đại số thì việc dùng các
phơng trình nhìn chung thuận tiện hơn so với dùng bất phơng trình. Do
đó, để giải một mô hình QHTT sử dụng phơng pháp đại số đơn hình, đầu
tiên, mô hình phải chuyển thành dạng chính tắc (nh trong ví dụ 3.1.2). Bài
toán QHTT bao gồm 5 biến quyết định (x
1
, x
2
, s
1
, s
2

trong đó các hệ số bên vế phải của nó bằng 0, 90

Trong bài tập vừa rồi, (n-m) biến quyết định đặt bằng 0 đợc gọi là các
biến không cơ sở trong khi m biến quyết định còn lại mà các giá trị của
chúng tìm đợc bằng cách giải hệ phơng trình gồm m phơng trình và m
ẩn, đợc gọi là các biến cơ sở. Nghiệm của các biến cơ sở là không âm
đợc gọi là nghiệm cơ sở khả thi và nó xác định điểm cực trị khả thi tơng
ứng nằm trong miền nghiệm. Do vậy, trong việc giải đại số mô hình QHTT,
chỉ cần đi xem xét từng nghiệm khả thi cơ sở của mô hình có dạng QHTT
chuẩn.
3.3.2. Dạng đại số của phơng pháp đơn hình
Phơng pháp đơn hình giải một mô hình QHTT bằng cách lợi dụng 3
tính chất của điểm cực trị khả thi đã đợc thảo luận trớc đó. Thuật toán
tìm kiếm sự tối u của một mô hình QHTT luôn tuân theo 2 điều kiện cơ
bản: (1) Điều kiện tối u và (2) Điều kiện khả thi.
Điều kiện tối u đảm bảo rằng không gặp các điểm suy giảm (đối với
điểm nghiệm đang xét). Điều kiện khả thi đảm bảo rằng, bắt đầu với một
nghiệm khả thi cơ sở, chỉ có các nghiệm khả thi cơ sở đợc xem xét trong
suốt quá trình tính toán.
Bảng 3.3.1
Các điểm cực trị khả thi của bài toán sản xuất và xử lí chất thải

(x
1
x
2
s

3

Nghiệm
x
0
1 -5 1 0 0 0 0
s
1
0 2 -1 1 0 0 10
s
2
0 0,4

0,8

0 1 0 4
s
3
0 -2 1 0 0 1 0
Để giải đại số mô hình QHTT, dạng chính tắc của mô hình có thể đợc
đặt vào dạng bảng nh trong bảng 3.3.2, trong đó hàm mục tiêu đợc diễn
tả nh sau: 91
x
0
- 5x
1
+ x

0

ở bảng đơn hình. Điều này là tơng đơng với việc lựa chọn một biến với hệ
số dơng lớn nhất trong hàm mục tiêu gốc bởi vì độ lớn của hệ số hàm mục
tiêu diễn tả tốc độ thay đổi của hàm mục tiêu do thay đổi một đơn vị giá trị
của biến quyết định.
Hệ số có giá trị âm lớn nhất đợc chọn bởi vì nó có tiềm năng lớn nhất
trong việc cải thiện giá trị hàm mục tiêu. Mặt khác, việc lựa chọn biến vào
cho bài toán cực tiểu hoá tuân theo quy luật ngợc lại. Đó là, lựa chọn biến
không cơ sở với hệ số dơng lớn nhất trong hàng của hàm mục tiêu trong
bảng đơn hình nh là biến vào. Khi mà biến vào đã đợc xác định, một
trong số các biến cơ sở hiện thời phải đợc chọn để trở thành biến không cơ
sở. Sự lựa chọn biến đi ra đợc thực hiện bằng điều kiện khả thi để chắc
chắn rằng chỉ có các nghiệm khả thi đợc liệt kễ xem xét trong suốt các
bớc lặp. Biến ra đợc lựa chọn sử dụng tiêu chuẩn sau:
i
i
ik
b
a


với mọi a
ik
>0
với a
ik
là các hệ số của các ràng buộc liên quan đến các biến vào x
k


tìm kiếm có thể thu đợc từ bảng đơn hình bằng cách tính tỷ số của các phần tử trong cột nghiệm
với các phần tử ràng buộc nằm trong cột tơng ứng với biến vào. Xem xét ví dụ đợc minh họa
trong bảng 3.3.2, hai cột đợc sử dụng để tính toán giao điểm đợc chỉ ra bên dới trong bảng 3.3.3
và theo:
1
1
11
2
2
21
10
5
2
4
10
0,4
b
a
b
a





Tỷ số nhỏ nhất là

= min (

1

2 0,4 4 10
3 -2 0 -
và không cơ sở phải đợc cập nhất. Sử dụng danh sách các biến mới, các
tính toán đa ra một bảng đơn hình mới. Trong tính toán, chỉ ra trong bảng
3.3.2, nên chú ý rằng các phần tử trong mỗi cột dới từng biến cơ sở hiện
thời có giá trị bằng 1 tại các điểm giao của hàng chứa biến ra và toàn bộ các
phần tử khác đều bằng 0, Các biến đổi đại số sau đây đợc thực hiện để
thỏa mãn yêu cầu này.
Các giá trị của các phần tử trong bảng đơn hình liên quan tới các biến cơ
sở và không cơ sở mới có thể đợc tính toán theo các biến đổi hàng (hay
phơng pháp giải triệt tiêu Gauss-Jordan). Hàng ràng buộc có liên quan tới
biến ra đợc gọi là phơng trình chính và làm cơ sở cho biến đổi hàng này.
Các phần tử nằm tại điểm giao giữa cột đi vào và hàng chính đợc gọi là
phần tử chính. Phơng trình chính và phần tử chính đóng vai trò trung tâm
trong tính toán. Trong biến đổi hàng, mục tiêu là biến đổi bảng sang dạng 93
có các phần tử chính bằng một và các phần tử khác bằng không tại bất kỳ
đâu trong cột liên quan tới biến cơ sở mới.
Ví dụ 3.3.2. Xem bảng 3.3.2. thực hiện phép biến đổi chính để cập nhật bảng đơn hình sau khi x
1
và
s
1
đợc lựa chọn tơng ứng là biến vào và biến ra.
Lời giải. Biết rằng x
1
là biến vào và s
1

Bảng 3.3.4
Minh hoạ các biến đổi hàng
x
0

x
1
x
2
s
1

s
2

s
3

Nghiệm

Biến đổi hàng
1 -5 1 0 0 0 0 (+)(x)(5)
0 2 -1 1 0 0 10
(ữ)(2)
0 0,4

0,8

0 1 0 4 (+)(x)( 4)
0 -2 1 0 0 1 0 (+)(x)(2)

0 0 1 -0,2 1 0 2
s
3
0 0 0 1 0 1 10
Trong tính toán thực tế, không cần tính toán các phần tử trong cột cha
các biến cơ sở. Thực ra không phải tất cả các phần tử trong bảng cần tính
toán ở mỗi bớc lặp. Biến đối hàng đợc mô tả ở phần trên có thể đợc sửa
đổi làm tăng tính mềm dẻo để có thể tính toán các giá trị của bất kỳ phần tử
nào trong bảng. Giả thiết rằng trong bất kỳ vòng lặp nào của phơng pháp
đơn hình, phần tử a
ij
ở hàng i cột j là phần tử chính. Giá trị của phân tử tại
giao của hàng k cột l, a
kl
, có thể đợc tình toán theo:
A


kl
= (a
kl
. a
ij
- a
kj
. a
il
)/ a
ij
(3.3.1)

bởi vì không còn biến nào có tiềm năng làm tăng thêm giá trị của x
0,

Xem xét bảng đơn hình hiện thời ta thấy rằng hệ số mục tiêu liên quan
tới x
2
(một biến không cở sở) trong hàng x
0
là -1,5. Điều này chỉ ra rằng nếu
tăng giá trị của x
2
từ mức không có thể tiếp tục làm tăng giá trị hiện thời
của x
0
= 25. Do đó x
2
đợc lựa chọn làm biến vào. Để lựa chọn biến ra, các
tỷ số giữa các nghiệm của các biến cơ sở hiện thời (x
1
, s
2
, s
3
) với các thành
phần trong bảng ở các cột đi vào đợc tính toán. Biến cơ sở hiện thời liên
quan tới tỷ số dơng nhỏ nhất đợc lựa chọn làm biến ra. Có nghĩa là, biến
cơ sở hiện thời, tơng ứng với min(-,2/1,10/0) =
min(-,2,) = 2 là biến ra trong vòng lặp thứ hai của phơng pháp đơn hình.
Hàng chính là hàng s
2

) = (6,
2), là nghiệm tối u và lãi thực tối đa có thể thu đợc cho ngời sản xuất
x*
0
= 28 nghìn đô la.
3.3.3. Tóm tắt phơng pháp đơn hình
Từ các mô tả của thuật toán đơn hình để giải các bài toàn QHTT, quy
trình giải tuân theo hai điều kiện cơ bản, đó là, điều kiện tối u và điều kiện
khả thi. Cụ thể hơn cho các biến đổi đại số, hai điều kiện này có thể đợc
mô tả bằng ngôn từ nh sau.
Bảng 3.3.6
Kết quả của bớc lặp 2
Cơ sở

x
0
x
1
x
2
s
1
s
2
s
3
Nghiệm

1 10
96

Điều kiện tối u làm cơ sở cho việc lựa chọn các biến vào có tiềm năng
làm tiếp tục tăng giá trị của hàm mục tiêu. Nếu cho rằng hàng x
0
đợc thể
hiện lại chỉ theo các biến không cơ sở, ta đi lựa chọn các biến vào trong bài
toán tối đa hoá (tối thiểu hoá) từ các biến không cơ sở có hệ số âm (dơng)
nhất ở hàng x
0,
Khi tất cả các hệ số vế trái của hàng x
0
trong bảng đơn hình
là không âm (không dơng), ta đã đạt đợc nghiệm tối u của bài toán.
Điều kiện khả thi làm cơ sở cho việc lựa chọn các biến ra để cho các
nghiệm thu đợc từ các bớc lặp đơn hình luôn khả thi. Biến ra là các biến
cơ sở tơng ứng với các tỷ số dơng nhỏ nhất của giá trị hiện thời của các
biến cơ sở trên các hệ số ràng buộc dơng của các biến vào, không phụ
thuộc vào loại bài toán là cực đại hay cực tiểu hoá.
Các bớc sau đây tóm tắt phơng pháp đơn hình cho bài toán cực đại
hoá:
Bớc 0: Biến đổi bài toán về dạng chính tắc với một nghiệm khả thi cơ
sở xuất phát và sau đó thiết lập dạng bảng. Bảng ban đầu phải luôn chứa các
nghiệm cơ sở khả thi (kiểm tra xem có một ma trận đơn vị).
Bớc 1: Lớt qua hàng x
0

Bây giờ sử dụng hàng này để thực hiện việc biến đổi hàng (phép cộng của
hàng này sau khi đợc nhân) với các hàng khác để thu đợc tất cả các số
không cho các giá trị còn lại trong cột chính (bao gồm cả hàng x
0
). Quay lại
bớc 1.
Phơng trình chính:
Phơng trình chính mới = phơng trình chính cũ / phần tử chính
Các phơng trình khác:
Phơng trình mới = phơng trình cũ - (hệ số cột đi ra) x (phơng trình
chính mới) 97
3.4. Phơng pháp biến nhân tạo
Thuật toán đơn hình đợc trình bày trong mục trớc có thể áp dụng trực
tiếp cho các bài toán mà các biến cơ sở ban đầu có sẵn ngay sau bớc khởi
tạo. Đây là trờng hợp nếu tất cả các ràng buộc trong mô hình là

, các
biến ảo có thể đợc thêm vào để làm cho chúng trở thành đẳng thức. Ma
trận các hệ số công nghệ của các biến ảo tại bớc khởi tạo ban đầu có dạng
một ma trận đơn vị. Tuy nhiên, sẽ cần đến một số sự hiệu chỉnh công thức
mô hình cho các bài toán mà không thể dễ dàng tìm thấy nghiệm khả thi cơ
sở bắt đầu. Điều này thờng xảy ra với những mô hình có các các ràng buộc
thuộc loại

hoặc =. Bằng việc đơn giản là trừ đi biến ảo, s
3
, từ vế trái của

vì thế hệ số công nghệ gắn liền với s
3
là +1. Điều
này là có thể đợc phép bởi vì vế phải của ràng buộc thứ ba là bằng 0 và sự
vận dụng về dấu không vi phạm yêu cầu của vế phải không âm trong dạng
chính tắc. Tuy nhiên, nếu vế phải của ràng buộc thứ ba là dơng, nh là hai
ràng buộc kia, thay đổi chiều của bất đẳng thức sẽ vi phạm yêu cầu không
âm của dạng chính tắc.
Phơng pháp biến nhân tạo đơn giản là một thủ thuật toán học mà
thông qua sự bổ xung các biến (gọi là biến nhân tạo) để có thể giải một mô
hình quy hoạch tuyến tính sử dụng thuật toán đơn hình chính tắc đợc trình
bày ở trên. Về cơ bản, các biến nhân tạo đợc sử dụng trong hai trờng hợp:
(a) với các ràng buộc thuộc loại

, các ràng buộc đợc viết thành:
1
n
ij j i i i
j
a x s r b



(3.4.1)
còn (b) với các ràng buộc thuộc loại =, các ràng buộc đợc viết thành
1
n
ij j i i
j
a x r b

đợc đa ra. Sẽ vẫn sử dụng ví dụ sản xuất, xử lí rác thải để minh họa
những phơng pháp luận này.
3.4.1. Phơng pháp đánh thuế (phơng pháp M lớn)
Không vận dụng dấu của ràng buộc thứ ba của ví dụ sản xuất - xử lí rác
thải, tập hợp ràng buộc có thể đợc viết dới dạng chính tắc:
1 2 1
1 2 2
1 2 3 3
2 10
.4 .8 4
2 0
x x s
x x s
x x s r




(tất cả x
1
, x
2
, s
1
, s
2
, s
3
và r
3

99
Bằng biểu hiện tơng tự, nếu bài toán thuộc loại cực tiểu hóa, một hệ số
dơng lớn (+M) sẽ đợc chỉ định cho mỗi biến nhân tạo trong hàm mục
tiêu
Min
0
1 1
n m
j j i
j i
x c x Mr

Số M lớn này có thể đợc xem nh bất lợi đơn vị cho bất kỳ sự vi phạm
nào của các ràng buộc mô hình. Hàm mục tiêu cho ví dụ này có thể đợc
thành tạo là
Max
0 1 2 1 2 3 3
5 0 0 0
x x x s s s Mr


Có hai hạn chế cơ bản của phơng pháp số lớn M. Đó là:
Bớc cuối cùng phải đợc tiến hành trớc khi phát hiện ra rằng bài toán
không có nghiệm khả thi, tức là, một số biến nhân tạo là dơng.
Trong việc thực thi tính toán của phơng pháp số lớn M, ta phải giả sử
một giá trị số của M. Làm nh vậy, các lỗi tính toán và tính bất ổn định có
thể xuất hiện trong tiến trình lặp chủ yếu do một bài toán xác định tỷ lệ.

0
khác 0 khi sự tối u đợc đạt tới, bài toán không có
miền nghiệm.
Dựa trên sự hoàn thành Pha I, sự tối u hóa Pha II tiếp tục, miễn là tất cả
các biến nhân tạo đều trở thành các biến không cơ sở ở mức 0, Trong các 100

tính toán Pha II, bảng tính toán cuối cùng của Pha I đợc hiệu chỉnh bằng
việc hạ thấp các cột gắn liền với các biến nhân tạo. Hơn nữa, dòng r
0
của
bảng đợc thay thế bằng dòng x
0
của hàm mục tiêu gốc. Trớc khi kiểm tra
điều kiện tối u, ta phải kiểm tra bảng đó thỏa mãn yêu cầu rằng dòng x
0

chỉ có thể là một hàm của các biến không cơ sở hay cha. Nếu điều kiện
này không thỏa mãn, các phép tính dòng phải đợc thực hiện để thỏa mãn
yêu cầu. Khi điều kiện này đợc thỏa mãn, thuật toán đơn hình đợc áp
dụng để giải tối u hóa bài toán.
Ví dụ 3.4.1. Giải bài toán sản xuất, xử lí rác thải sử dụng phơng pháp hai pha.
Lời giải. Việc thiết lập Pha I của bài toán sản xuất, xử lí rác thải có thể đợc biểu diễn là:
Min r
0
= r
3


1
, x
2
và s
3
. Điều này có thể đợc hoàn thành bằng việc
thêm dòng r
3
cho dòng r
0,
Bảng kết quả đợc trình bày trong bảng 3.4.1(b).
Mô hình pha I bây giờ có thể đợc tối u hóa bằng việc chọn x
1
làm biến vào theo điều kiện tối u
cho các bài toán cực tiểu hóa. Việc lựa chọn một biến ra cũng giống nh trớc đây theo điều kiện khả
thi. Sau một bớc lặp, nghiệm tối u cho pha I của ví dụ này đợc đạt tới dựa trên bảng 3.4.1(c). Dựa
vào bảng cuối cùng của thủ tục pha I, bảng bắt đầu của pha II đợc trình bày trong bảng 3.4.1(d).
Chú ý rằng bài toán cực đại hóa gốc đợc xem xét trong các tính toán pha II.

Chú ý rằng bảng 3.4.1(d) không thỏa mãn yêu cầu rằng dòng x
0
chỉ có thể là một hàm của các biến
không cơ sở. Biến cơ sở x
1
có hệ số khác 0 trong dòng x
0,
Một lần nữa, các phép tính toán dòng lại
đợc áp dụng để khử hệ số -5 của x
1
trong dòng x