L thuyt qui hoch tuyn tnh



 ! "#
1.1 $%&'!()*+,
Để mô tả các phương pháp hữu hạn giải bài toán QHTT người ta thường
xét bài toán cho ở dạng sau đây, gọi là bài toán QHTT dng chuẩn:
Tìm giá trị nhỏ nhất (hoặc lớn nhất) của hàm số
Z = Z(x) =
n
j j
j 1
c x
=
∑
(1.1)
trên tập hợp các vec tơ x thỏa mãn các điều kiện:

n
ij i
j 1
j
a b ,i 1,2, ,m (1.2)
x 0, j 1,2, ,n (1.3)
=
= =
∑
≥ =
Trong đó c
j

Hay cũng vậy
X = {x∈R
n
/ Ax = b, x ≥ 0}

Tương tự như ở phần 1.1 chương III, tập X, định nghĩa như trên được
gọi là tập chấp nhận được, hàm Z = Z(x) được gọi là hàm mục tiêu, các điều
kiện (4.2) gọi là các ràng buộc, các điều kiện (4.3) là các hn ch; ma trận A
Lê Văn Phi, Khoa Toán – Thống kê, Đi h?c Kinh t Tp. HCM 76
L thuyt qui hoch tuyn tnh
bao gồm các phần tử a
ij
gọi là ma trận các ràng buộc; vectơ b gọi là vectơ
hạn chế (vectơ vế phải); vectơ c gọi là vectơ hệ số (hàm mục tiêu). Vectơ
x∈X được gọi là lời giải hoặc phương án chấp nhận được; phương án chấp
nhận được x* tại đó hàm mục tiêu Z nhận giá trị nhỏ nhất (hoặc lớn nhất, tuỳ
theo yêu cầu bài toán) được gọi là lời giải hoặc phương án tối ưu.

 /0&+12&  ! "#

Để trình bày phương pháp đơn hình ta xét bài toán QHTT dạng chuẩn
(1.1) – (1.3). Dễ thấy rằng tập X xác định theo (1.4) có thể được viết lại
thành
n
i. i j
X {x R / A ,x b ,i 1,2, ,m; e ,x 0, j 1,2, ,n}= ∈ = = ≥ =
(1.7)
Trong đó A
i.
là các vectơ hàng của ma trận A; e

.j
là các vectơ cột của ma trận A, j = 1,2,
…,n. Để x
0
là điểm cực biên của X thì điều kiện cần và đủ là các
vectơ A
.j
ứng với các x
j
> 0 là độc lập tuyn tnh.
67%: Do hệ ràng buộc xác định X (s.s. (1.7)) có chứa n vectơ đơn vị
e
j
, nên hạng của hệ đó bằng n. Vì vậy, nếu x
0
là điểm cực biên thì phải thỏa
mãn chặt n ràng buộc độc lập tuyến tính, tức là lời giải duy nhất của một hệ
phương trình vuông không suy biến. Không giảm tính tổng quát, giả sử
0 0
j j
x 0, j 1,2, ,k;x 0, j k 1, ,n> = = = +
. Ở bài toán QHTT dạng chuẩn tất cả
7
Nếu trong số các ràng buộc xác định X có ràng buộc nào đó phụ thuộc tuyến tính
vào các ràng buôc khác thì bằng cách loại bỏ dần này theo các pương pháp xác định
hạng của ma trận thông thường để cho các ràng bộc còn lại là độc lập tuyến tính và
ký hiệu số ràng buộc ấy là m. Khi ấy tập hợp chấp nhận được X sẽ không thay đổi.
8
Rõ ràng r[A] = m ≤ n. Nếu r[A] = n thì hệ (1.2) là hệ phương trình tuyến tính
vuông, không thuần nhất. Hệ này có duy nhất một lời giải. Nếu lời giải này thỏa mãn

= =
∑



= = +

(1.8)
Thay n-k phương trình cuối vào k phương trình đầu, ta có hệ tương đương:

k
ij j i
j 1
a x b ,i 1,2, ,k
=
= =
∑
(1.9)
Do x
0
là lời giải duy nhất của hệ (1.8), nên
0 0 0 0
1 2 k
x (x , x , ,x )=
cũng là lời giải
duy nhất của hệ (1.9). Suy ra các vectơ cột rút gọn

1j
. j
kj

0 0 0 0
1 2 k
x (x , x , ,x )=
là lời giải duy nhất
của hệ phương trình vuông không suy biến (1.9) và vectơ mở rộng
0 0 0
1 k
x (x , ,x ,0, ,0)=
là lời giải duy nhất của hệ (1.8). Điều này chứng tỏ
rằng các vectơ ràng buộc, A
.j
, j = 1,…,k và e
j
, j = k+1,…,n, trong (1.6) là độc
lập tuyến tính. Do đó x
0
là điểm cực biên của X . Nếu k < m thì teo định lý
bổ sung cơ sở (chuơng I) bao giờ cũng có thể bổ sung (m-k) vectơ trong số
(n-k) vectơ ứng với các thành phần
0
j
x 0=
để tạo thành một cơ sở của R
m
.
Sau đó bằng lý luận tương tự cũng có thể chứng tỏ rằng x
0
là điểm cực biên
của X. ª
Như vậy, theo định lý 1.1, nếu x là điểm cực biên của X thì số thành

cũng là lời giải của
hệ phương trình tuyến tính Ax = b, nên x
0
còn gọi là một 48%%9%*:;-
Khi k < m, tức x
0
là thoái hóa. Do chỉ có k vectơ độc lập tuyến tính nên
không đủ để lập nên một cơ sở của R
m
. Theo giả thiết, trong số n vectơ A
.j
có
đúng m vectơ độc lập tuyến tính. Vì thế, bao giờ cũng có thể bổ sung thêm
m-k vectơ trong số các vectơ còn lại ứng với các thành phần bằng 0 để có
được một cơ sở của R
m
. Vì x
0
có n-k thành phần bằng 0, nên có
m k
n k
n k
C
m k
−
−
−
 
=
 ÷

(gọi tắt là bin cơ sở) và x
R
là vectơ ứng với các x
j
mà A
.j
không nằm trong
cơ sở (gọi tắt là bin phi cơ sở). Đặt J = {j/ x
j
là biến phi cơ sở}. Hệ phương
trình tuyến tính Ax = b tương đương với hệ sau đây:
(B R)
B
R
x
x
 
 ÷
 
= b
Hay, cũng vậy
Bx
B
+ Rx
R
= b (1.12)
1
Nếu x* là thoái hóa thi B là một trong những ma trận cơ sở ứng với nó.
Lê Văn Phi, Khoa Toán – Thống kê, Đi h?c Kinh t Tp. HCM 79
L thuyt qui hoch tuyn tnh


Bi ij j i0
j J
x y x y
∈
+ =
∑
, i = 1,2,…,m (1.14)
Trong đó y
ij
=
1
Bi. .j
A ,A
−
, y
io
=
1
Bi.
A ,b
−
, và
1
Bi.
A
−
là vectơ hàng i của B
-1
, i =

= +
∑ ∑ ∑
=
m
Bi i0
i 1
c y
=
∑
(1.16)
Phương pháp đơn hình được tiếp tục với việc xét xem liệu Z* có phải là giá
trị nhỏ nhất hay không. Tư tưởng cơ bản để thực hiện việc kiểm tra này là
biểu diễn các biến cơ sở trong hàm mục tiêu thành biểu thức của các biến phi
cơ sở. Sau đó lần lượt xét sự thay đổi của hàm mục tiêu ứng với việc thay
đổi (tăng dần của một biến phi cơ sở nào đó). Để làm việc này người ta tiến
hành như sau:
Trước hết
2
Dễ thấy rằng các hệ số y
ij
và y
i0
, i = 1,2.,…,m, là tọa độ của các vectơ A
.j
,j∈J, và b
tương ứng theo cơ sở {A.

,….,A.
7
},
( )
m m
1
m 1, j Bi ij j Bi Bi. . j j
i 1 i 1
y (c y c ) c A ,A c
−
+
= =
= − = −
∑ ∑
(1.18)

1
m 1, j B . j j
y , c ,B A c
−
+
= −
, j∈ J
Khi ấy giá trị hàm mục tiêu Z trở thành

m 1,0 m 1, j j
j J
Z y y x
+ +
∈
= −

m 1, j j m 1,0
j J
Z y x y
+ +
∈
+ =
∑
(1.20)
Hệ (1.20) tương đương hoàn toàn với hệ (1.4). Nếu y
io
≥ 0, i =1,2,…,m, ta
nói rằng (1.20) là dạng chính tắc chấp nhận được. Từ hệ này thấy rằng, ứng
với x = x* ta có
*
j
x 0, j J= ∈
và do đó
*
Bi i0
x y 0,i 1,2, ,m= ≥ =
; Z* = y
m+1,0
.
Xuất phát từ x* sẽ có 3 trường hợp xãy ra. Đó là
• Trường hợp 1: ∀j, j =1,2,…,n-m: y
m+1,j
≤ 0. Khi ấy, vì ∀x∈X: x
j
≥ 0, j∈J,
nên theo (1.20), Z = Z(x) ≥ y

i0
– y
il
.λ ≥ 0, i = 1,2,…,m (1.21)
Do (1.20) tương đương với hệ (1.4), đồng thời x(λ) thỏa mãn (1.5) (điều
kiện không âm), nên x(λ)∈X với bất kỳ giá trị không âm nào đó của λ.
Dễ thấy rằng giá trị hàm mục tiêu ứng với x(λ) bằng
Z(λ) = Z[x(λ)] = y
m+1,0
– y
m+1,l
.x
l
= y
m+1,0
– y
m+1,l
.λ (1.22)
Vì theo giả thiết y
m+1,l
> 0, nên giá trị này sẽ tiến dần tới -∞ khi λ → ∞.
Tức là khi λ → ∞ , x(λ)∈X và Z(λ) → -∞ . Nói cách khác, trong trường
hợp này, hàm mục tiêu không bị chặn dưới trên X, nên giá trị Z
min
không
tồn tại. Suy ra bài toán QHTT không có lời giải tối ưu.
• Trường hợp 3: ∃ l, 1 ≤ l≤ l, để cho y
m+1,l
> 0và∃k, 1≤ k ≤ m,
y

Tổng hợp lại, trong trường hợp này, để x(λ) vẫn còn là chấp nhận được
thì

il
i0
i,y 0
il
y
0
min
y
>
≤ λ ≤
Khi ấy giá trị Z[x(λ)] cũng tính theo công thức (1.22) và
Z(λ) < y
m+1,0
= Z(x
0
),
nếu λ > 0. Tuy nhiên để cho Z giảm nhiều nhất người ta chọn
il
i0
0
i,y 0
il
y
min
y
>
λ = λ =

Bk
(λ
0
) = y
k0
– y
kl
.λ
0
= y
k0
– y
kl
.(y
k0
/y
kl
) = 0
Theo định lý đổi cơ sở (định lý1.1, chương I), do tọa độ thứ k của vectơ
A
.l
theo cơ sở B = [A.
B1
, A.
B2
,…, A.
Bk
,…, A.
Bm
], y

(λ
0
) = y
i0
– y
il
.x
l
= y
i0
– y
il
.λ
0

= y
i0
– y
il
(y
k0
/y
kl
) ≥ 0
4
Số biến nhận giá trị dương ở x(λ
0
) không vượt quá m (thêm một biến
dương và bớt di ít nhất một biến dương khác); đồng thời các vectơ A
.j

kj
k0
l j Bk
j J, j l
kl kl kl
y
y
1
x x x
y y y
∈ ≠
= − −
∑
(1.25)
Thay thế (khử) x
l
ở các phương trình còn lại ở (1.20)
Bi i0 ij j il l
j J, j l
x y y x y x
∈ ≠
= − −
∑
, i = 1,2,…,m, i ≠ k
4
Nếu y
il
≤ 0 thì – y
il
(y

.λ
0
≥ y
i0
– y
il
(y
i0
/y
kl
) = 0.
Lê Văn Phi, Khoa Toán – Thống kê, Đi h?c Kinh t Tp. HCM 83
L thuyt qui hoch tuyn tnh
Hay
kj
k0
Bi i0 il ij il j il Bk
j J,j l
kl kl kl
y
y
1
x (y y ) (y y )x y x
y y y
∈ ≠
= − − − +
∑
Hay cũng vậy

kj

Z (y y )x y x y y
y y y
+ + + + +
∈ ≠
+ − − = −
∑
Đặt

kj
ij ij il
kl
kj
kj
kl
kj
m 1, j m 1, j m 1,l
kl
y
y' y y , i 0,1,2, ,m;i k
y
y
y'
y
y
y' y y
y
+ + +
= − = ≠
=
= −

l
, x’j = x
j
, j ≠ l, x’
l
= x
Bk
.
Sau khi có dạng chính tắc (1.27), phương pháp giải sẽ được tiếp tục với một
trong 3 trường hợp như trên.
Phép biến đổi đơn hình chuyển từ dạng chính tắc (1.20) sang dạng chính
tắc (1.27) còn gọi là phép biến đổi trục xoay với phần tử trục xoay (phần tử
chuẩn) tương ứng là y
kl
, cột chuẩn là cột l và hàng chuẩn là hàng k. Người ta
thường đóng khung phần tử chuẩn để phân biệt với các phần tử khác
5
.
5
Một đơn hình S trong không gian R
n
là một tập hợp lồi bị chặn có n+1 đỉnh. Ví dụ trong R
1
,
đó là một đoạn thẳng, trong R
2
, S là một tam giác, trong R
3
, S là một tứ diện . Phép biến đổi
trên đây dựa trên nguyên lý của một đơn hình, tức là, giả sử phương án hiện có ứng với một

+ +
∈ ∈
= − =
∑ ∑
. Bảng đơn
hình xuất phát có dạng:
6
Bảng 4.1
Biến
cơ sở
Phương
án
x
1
… x
l
… x
n
λ
0
c
1
… c
l
… c
n
x
B1
y
10

Z y
m+1,0
y
m+1,1
… y
m+1,l
y
m+1,n
Bước 2: Xác định
m 1,l m 1, j
1 j n
y max{y }
+ +
≤ ≤
=
(1.28)
• Nếu y
m+1,l
= 0, thì y
m+1,j
≤ 0, j =1,2,…,n. Ta có trường hợp 1. Phương
án hiện có là phương án tối ưu, tức là x*
Bi
= y
io
, i = 1,2,…,m; x*
j
= 0,
x
j


 

∞ ≤ ∀

(1.29)
thì đỉnh đang xét ứng với lời giải tối ưu. Vì vậy phương pháp này được gọn ngắn gọn là
phương pháp đơn hình, mặc dù tập chấp nhận được trong R
n
thường có nhiều hơn n+1 đỉnh.
6
Từ (1.13), (1.18) dễ dàng suy ra rằng các cột tương ứng với biến cơ sở x
Bi
sẽ có dạng vectơ
đơn vị e
i
= (0,0,…,0,1,0,…,0), i =1,2,…,m.
Lê Văn Phi, Khoa Toán – Thống kê, Đi h?c Kinh t Tp. HCM 85
Cột chuẩn
Hàng chuẩn
L thuyt qui hoch tuyn tnh
• Nếu λ
0
= ∞ thì Z không bị chặn dưới (trười hợp 2). Bài toán QHTT
không giải được.
• Khi λ
0
< ∞ , sang bước 4
Bước 4: Thực hiện phép biến đổi đơn hình, đưa x
l

+ 4x
7
→ min
1 2 3 4
2 3 5 6 7
3 4 6 7 8
j
1 1 1
x x x x 3000
2 2 2
2 2 2 2
x x x x x 3000
3 3 3 3
1 1 1 1
x x x x x 1000
4 2 4 2
x 0, j 1,2,3, ,8

+ + + =



+ + + + =



+ + + + =


 ≥ =

0
= (3000, 0, 0, 0, 3000, 0, 0, 1000) và Z
0
= 18000. Bảng đơn hình xuất phát có
dạng:
7
Khi gặp phải một phương án cơ sở suy biến, tức là ứng với nó sẽ có nhiều dạng chính tắc
chấp nhận được (4.8) khác nhau,thuật toán có thể rơi vào tình trạng xoay vòng. Để khắc phục
nhược điểm này, người ta áp dụng kỹ thuật nhiễu loạn trong phần xác định biến đưa ra khỏi
cơ sở (hàng chuẩn). Do các phần mềm vi tính hiện nay đều đã đề cẫp đến trường hợp này, nên
chúng tôi không trình bày cơ sở lý thuyết cũng như cách trình bày các kỹ thuật này trong giáo
trình. Nếu bạn đọc quan tâm xin tham khảo tài liệu trích dẫn.
Lê Văn Phi, Khoa Toán – Thống kê, Đi h?c Kinh t Tp. HCM 86
L thuyt qui hoch tuyn tnh
Bảng 4.2:
Biến
cơ sở
Phương
án
x
1
x
2
x
3
x
4
x
5
x

= min{b
i
/y
i2
, y
i2
> 0}= min
{6000, 4500} = 4500 = y
22
. Vậy vectơ ra khỏi cơ sở là A
.B2
= A
.5
. Suy ra
hàng chuẩn là k = 2.
• Trên hàng k = 2, thay thế x
5
bởi x
2
ta có bảng 2.
Bảng 4.3:
Biến
cơ sở
Phương
án
x
1
x
2
x

giá trị Z
min
= 3000.
Tuy nhiên, do các hệ số đặt trưng ứng với x
4
và x
5
có giá trị bằng 0,
nên bài toán có thể có phương án tối ưu khác. Để tìm các phương án tối ưu
này chỉ cần đưa A
.3
, A
.4
vào cơ sở và thực hiện phép biến đổi đơn hình tương
ứng. Cụ thể, nếu đưa A
.3
vào cơ sở thay cho A
.1
ta có bảng 3. Ở đây lời giải
tối ưu mới là x* = (0, 3000, 3000, 0, 0, 0, 0, 250).
Tương tự, xuất phát từ bảng 3, khi đưa A
.4
vào cơ sở thay cho A
.3
, ta
có phương án tối ưu khác. Đó là x* = (0, 4500, 0, 1500, 0, 0, 0, 250). Giá trị
tối ưu vẫn không thay đổi là bằng 3000.
Lê Văn Phi, Khoa Toán – Thống kê, Đi h?c Kinh t Tp. HCM 87
L thuyt qui hoch tuyn tnh
Bảng 4.4:

8
250 -1 0 0 0 3/4 3/4 3/4 1 -
Z 3000 0 0 0 0 -5 -5 -5 0
. ! *:;%9&)'
? ! "#@%&8%ABC
:;40&+12&

Mặc dù ngày nay, nhờ sự giúp đỡ của tin học, với nhiều phần mềm tin
học khác nhau người ta có thể giải bài toán QHTT ở một dạng bất kỳ, việc
trình bày phương pháp sau dây, gọi là phương pháp cơ sở giả tạo, sẽ giúp
cho người đọc một lần nữa nắm được các kiến thức lý thuyết cơ bản của
QHTT và của phương pháp đơn hình.
Việc thực hiện phương pháp đơn hình ở phần I giả thiết bài toán QHTT
cho ở dạng chính tắc mở rộng (1.20), trong đó các y
i0
≥ 0, i =
___
1,m
. Trên
thực tế, không phải bài toán QHTT nào cũng có thể được cho ở dạng này.
Hơn thế nữa, việc chuyển một bài toán QHTT ở dạng bất kỳ về dạng (1.20)
đôi khi cũng tốn nhiều chi phí như là giải một bài toán QHTT bình thường.
Khi đó việc tìm lời giải tối ưu sẽ không còn có ý nghĩa nữa. Vì vậy nảy sinh
một câu hỏi là làm thế nào có thể tận dụng được thuật toán cho ở phần 1.2 để
giải bài toán QHTT ở dạng bất kỳ?
Câu hỏi này được giải quyết bằng phương pháp cơ sở giả to sẽ trình
bày sau đây. Giả sử bài toán QHTT cho ở dạng chuẩn
(2.1)
n
j j

Lê Văn Phi, Khoa Toán – Thống kê, Đi h?c Kinh t Tp. HCM 88
L thuyt qui hoch tuyn tnh
Thay thế cho bài toán (2.1), người ta khảo sát bài toán sau đây :
(2.2)
m
G Gi
i 1
____
n
ij j Gi i
j 1
___ ____
j Gi
Z x min
a x x b ,i 1,m
x 0, j 1,n; x 0,i 1,m
=
=

= →
∑



+ = =
∑



≥ = ≥ =

≠ ∅. Thật vậy, phương án x
0
G
với x
0
j
= 0, j = 1,2,…,n và x
0
Gi
= b
i
, i =
1,2,…,m, là phương án chấp nhận được của (2.2). Mặt khác, hàm mục tiêu
Z
G
ở (2.2) là bị chặn dưới (Z
G
≥ 0). Như vậy, theo tính chất của bài toán
QHTT (phần §2, chương III) bài toán (2.2) luôn luôn có lời giải tối ưu.
Để tìm lời giải tối ưu cho bài toán (2.2), người ta có thể áp dụng thuật
toán đã trình bày trong phần 1.2, vì từ (2.2) có thể viết ra dạng chính tắc
chấp nhận được (2.3), trong đó y
ij
= a
ij
, y
i0
= b
i
,

∑

Do đó ta có phương án cực biên xuất phát là x
0
G
với x
0
G
= (0, 0,…, 0, y
10
, y
20
,
…, y
m0
). Cơ sở B
G
= [A
.G1
,…, A
.Gm
] là cơ sở giả tạo, ứng với các biến giả
x
G1
,…, x
Gm
.
8
Giả sử bài toán (2.2) có phương án tối ưu là
x*

là phương án tối ưu
của bài toán (2.1).
67%: Giả sử X≠∅; tức là ∃x’∈X, sao cho Ax’= b, x’≥ 0. Khi đó (x’,
x’
G
) ∈X với x’
Gi
= 0, i =1,2,…,m. Nhưng Z
G
(x’, x
G
) = 0 < Z
Gmin
. Mâu thuẩn
với giả thiết rằng (x*, x
G
*) là phương án tối ưu của bài toán (P
G
). Vậy X =
∅. Khi Z
Gmin
= 0, thì , trước hết x* là phương án chấp nhận được của bài toán
(2.1). Dễ thấy rằng đó cũng là điểm cực biên của X.ª
Để có dạng chính tắc chấp nhận được tương ứng, ta tiến hành như sau.
Nếu tất cả các biến giả đều là biến phi cơ sở, thì có thể áp dụng ngay dạng
chính tắc hiện có để tiếp tục giải bài toán (2.1). Nếu có ít nhất một biến giả
nào đó, x
Gk
chẳng hạn, ta phân biệt hai trường hợp:
a) y

j
dùng để ghi hệ số trong hàm mục tiêu của bài toán
(P). Mặt khác, do các biến x
Gi
là giả (người ta thêm vào để tạo cơ sở giả), nên
một ki một biến nào đó bị loại khỏi cơ sở thì không cần đưa vào cơ sở nữa.
Vì vậy ngay từ đầu không cần phải thêm các cột ứng với các biến giả.
5(>: Giản bài toán QHTT sau đây

1 2 3 4 5
Z x 3x 3x 2x 4x min= − + − + →
Lê Văn Phi, Khoa Toán – Thống kê, Đi h?c Kinh t Tp. HCM 90
L thuyt qui hoch tuyn tnh
(P)
1 3 4 5
1 3 4 5
1 2 3 4 5
1 3 4 5
x 4x 2x 5x 3
8x x x 2x 30
5 7 5 1
x x x x x 7
3 3 3 3
17x 2x 4x x 63
+ − + =


− − − =





− − − + =



+ − + =


+ − + + =


x
j
≥ 0, j = 1,2,…,5; x
Gi
≥ 0, i = 1,2,4
Ở đây bài toán (P
G
) chỉ có 3 biến giả, vì hàng thứ 2 đã có biến cơ sở là x
2
,
nên không cần thêm biến giả vào hàng này. Kết quả tính toán như sau:
Bảng 4.5: (Thời kỳ I)
Biến
cơ sở
Phương
án
x
1

án
x
1
x
2
x
3
x
4
x
5
λ
0
1 -3 3 -2 4
x
1
3 1 0 4 -2 5 -
x
G2
6 0 0 -33 15 -42 2/5
x
2
2 0 1 -9 5 -8 2/5
x
G4
12 0 0 -66 30 -84 2/5
Z
G
18 0 0 -99 45 -126
Lê Văn Phi, Khoa Toán – Thống kê, Đi h?c Kinh t Tp. HCM 91

%!&LM&N%+O
7%
FP-vì các hệ số đặc trưng đều ≤ 0.Đây là phương án tối
ưu suy biến (chỉ có 2 biến cơ sở là dương.
P ! "#7;LQ
 ! R$%&'!S
P-:;40&+12&
Phương pháp cơ sở giả tạo cho phép ứng dụng phương pháp đơn hình
thông thường để giải bài toán QHTT ở dạng bất kỳ. Tuy nhiên khi sử dụng
phương pháp này người ta phải phân biệt giữa thời kỳ I và thời kỳ II; tức là
sử dụng 2 hàm mục tiêu khác nhau và do đó có các hệ số đặc trưng khác
nhau. Thủ tục này có thể làm cho người thực hiện mắc sai lầm. Vì vậy cần
phát triễn một phương pháp nào đó giảm được phiền hà này. Từ cơ sở lý
thuyết của phương pháp cơ sở giả tạo người ta nghĩ ra tưởng kết hợp hai thời
kỳ làm một. Dó đó xuất hiện phương pháp đơn hình mở rộng, hay còn gọi là
phương pháp bài toán M.
Cơ sở lý thuyết của phươngpháp này như sau. Ta xét bài toán QHTT
(2.1)
n
j j
j 1
n
ij j i
j 1
j
Z c x min
a x b ,i 1,2, m
x 0, j 1,2, ,n
=
=

=

= + →
∑ ∑



+ = =
∑



≥ = ≥ =


Lê Văn Phi, Khoa Toán – Thống kê, Đi h?c Kinh t Tp. HCM 92
L thuyt qui hoch tuyn tnh
Trong đó các hệ số a
ij
, b
i
, c
j
, i = 1,2,…,m; j = 1,2,…,n không thay đổi như ở
(2.1); M được giả thiết là vô cùng lớn (lớn hơn bất cứ một số hữu hạn nào
khi đem so sánh với nó). Các x
j
, j = 1,2,…,n, vẫn gọi là biến thực, còn các
x
Gi

) là lời giải tối ưu của P
M
với m?i M
≥
M
0
thì x*
G
= 0. Do đó x* là lời giải tối ưu của P.

67%:
a) Trước hết ta chứn minh rằng, nếu x
0
là lời giải tối ưu của P thì sẽ tồn tại
M
0
để cho (x
0
, 0) là lời giải tối ưu của P
M
. Thật vậy, bài toán đối ngẫu
của P có dạng
W = 〈b, y〉 → max
(D) A
T
y ≤ c
Giả thiết P giải được kéo theo D giải được. Tức là tồn tại y
0
để cho cặp
(x

W
M
= 〈b, y〉 → max
(D
M
) A
T
y ≤ c
y
i
≤ M, i = 1,2,…,m
Lê Văn Phi, Khoa Toán – Thống kê, Đi h?c Kinh t Tp. HCM 93
L thuyt qui hoch tuyn tnh
Để cho cặp P
M
và D
M
có lời giải tối ưu thì điều kiện cần và đủ là tìm thấy
G
(x,x , y)
để cho
(3.2)
G
G
____
T
i
m
Gi
i 1

(3.5) M
0
=
{ }
0 0 0
1 2 m
max y , y , ,y
Tức (x
0
, 0) là lời giải tối ưu của P
M
, và y
0
là lời giải tối ưu của D
M
với mọi giá
trị M ≥ M
0
.
a) Bây giờ ta sẽ chứng minh, nếu ∀M không nhỏ hơn M
0
nào đó mà (x*,
x*
G
) là lời giải tồi ưu của P
M
thì x*
G
= 0, và do đó x* là lời giải tối ưu của P.
Thật vậy, theo giả thiết, P có lời giải tối ưu là x

m
i 1
0
=
∑
= 〈c, x*〉 + M
m
*
Gi
i 1
x
=
∑
Vế trái ở (3.6) độc lập với M, còn vế phải thì tăng theo M. Vì vậy, để đẵng
thức đúng với mọi giá trị M không nhỏ hơn M
0
thì điều kiện cần thiết là x*
G
= 0. Do đó (x*, 0) là lời giải tối ưu của P
M
, và x* là lời giải tối ưu của P.ª
Từ định lý này ta suy ra phương pháp giải bài toán P từ việc giải bài toán
P
M
như sau. Trước hết dùng phương pháp đơn hình thông thường giải bài
toán P
M
với cơ sở xuất phát là x
Gi
= b

.
Do M không bị chặn trên nên bất đẵng thức này không đúng. Suy ra X=∅.
2) Bài toán P
M
có lời giải tối ưu là (x*, x*
G
) và x*
Gi
= 0, i =1,2, ,m. Khi
đó theo định lý 3.1, thì x* là lời giải tối ưu của P.
Lê Văn Phi, Khoa Toán – Thống kê, Đi h?c Kinh t Tp. HCM 94
L thuyt qui hoch tuyn tnh
3) Với mọi giá trị của M, hàm mục tiêu của P
M
, Z
M
không bị chặn dưới
trên X
M
. Khi đó dễ thấy rằng hàm mục tiêu của P, Z, cũng không bị chặn
dưới trên X, nếu X≠∅, vì Z ≤ Z
M
, ∀ M≥ 0.
P T*%U  ! "#7;LQ:
Việc thực hiện phương pháp đơn hình mở rộng bắt đầu bằng việc thành
lập bài toán P
M
theo (3.2). Tương tự như phương pháp đơn hình hai thời kỳ,
việc thêm biến giả chỉ nhằm tạo ra biến cơ sở ban đầu cho mỗi hàng. Vì vậy,
nếu hàng nào đã có thể chọn ra biến cơ sở thì không cần thêm biến giả vào

> y
m+1,q
(M) = α
q
.M +.β
q
⇔
j q
j q j q
hoaëc
vaø
α > α


α = α β >β


Từ đây suy ra:
y
m+1,l
(M) = α
l
.M +β
l
< 0 ⇔
l
l l
0 hoaëc
0vaø 0
α <

kl
= 1, a
il
= 0, i ≠ k) thì không thêm biến
giả vào đó nữa. Khi ấy x
BK
= x
l
, c
BK
= c
l
.
Lê Văn Phi, Khoa Toán – Thống kê, Đi h?c Kinh t Tp. HCM 95
L thuyt qui hoch tuyn tnh
Để kiểm tra tiêu chuẩn tối ưu ta chọn:

{ }
l j
maxα = α
, ứng với x
j
là phi cơ sở
10
1) Nếu α
l
< 0, tức là y
m+1,l
(M) = α
l

thực hiện phép biến đổi đơn hình.
Bước 3:
1) Nếu hàm mục tiêu của P
M
không bị chặn dưới trên X
M
, thì P
không giải được (Z cũng không bị chặn dưới).
2) Giả sử phương án tối ưu của P
M
là (x*, x*
G
):
a)
*
Gi
x 0, i= ∀
. Khi đó x* là phương án tối ưu của P.
b)
*
Gk
x 0,1 k m∃ > ≤ ≤
. Bài toán P không giải được (X= ∅).
P-P5(>
Giải bài toán QHTT sau đây:
(P)
1 2 3 4 5
1 3 4 5
1 3 4 5
1 2 3 4 5

11
:
10
α
j
= β
j
= 0, nếu x
j
là biến cơ sở.
11
Vì ở hàng thứ 3 có biến cơ sở là x
2
, nên khi thành lập bài toán M không cần thiết phải thêm
biến giả x
G3
vào hàng này nữa
Lê Văn Phi, Khoa Toán – Thống kê, Đi h?c Kinh t Tp. HCM 96
L thuyt qui hoch tuyn tnh
(P
M
)
M 1 2 3 4 5 G1 G2 G4
1 3 4 5 G1
1 3 4 5 G2
1 2 3 4 5
1 3 4 5 G 4
j Gi
Z x 3x 3x 2x 4x Mx Mx Mx min
x 4x 2x 5x x 3

= x
5
= 0; x
G1
= 3, x
G2
= 30, x
2
= 7, x
G4
= 63 ta có bảng 1:
Bảng 4.8:
Biến
cơ sở
C
Bi
Phương
án
x
1
x
2
x
3
x
4
x
5
λ
0

C
Bi
Phương
án
x
1
x
2
x
3
x
4
x
5
λ
0
1 -3 3 -2 4
x
1
1 3 1 0 4 -2 5 -
x
G2
M 6 0 0 -33 15 -42 2/5
x
2
-3 2 0 1 -9 5 -8 2/5
x
G4
M 12 0 0 -66 30 -84 2/5
αj

x
1
1 19/5 1 0 -2/5 0 -3/5
x
4
-2 2/5 0 0 -11/5 1 -14/5
x
2
-3 0 0 1 2 0 6
x
G4
M 0 0 0 0 0 0
αj
0 0 0 0 0 0
βj
3 0 0 -5 0 -17
Đến đây phương pháp đơn hình mở rộng kết thúc với O
S7%
FO
7%
FP và
phương án tối ưu DEF?GHIJKJKJ.HIJKC. (Chú : Mặc dù x
G4
vẫn còn trong
cơ sở nhưng có giá trị bằng 0, đồng thời các hệ số tương ứng trên hàng 4
cũng bằng 0. Do vậy có thể gạch bỏ ràng buộc này vì nó phụ thuộc tuyến
tính vào các ràng buộc khác).
= ! "#"N%V+
=-:;40&+12&*W@  ! "#"N%V+
Ở ba phần trước chúng ta đã tìm hiểu ba phương pháp giải bài toán

m
, cho trước. Bài toán (4.1)
có thể viết dưới dạng khác như sau:
Lê Văn Phi, Khoa Toán – Thống kê, Đi h?c Kinh t Tp. HCM 98
L thuyt qui hoch tuyn tnh

____
i. i
Z c,x min
A ,x b ,i 1,m
x 0

= →


= =


≥


Trong đó A
i.
là các vectơ hàng của A, A
i.
∈R
n
. Các giả thiết ứng với bài toán
(4.1) tương tự như phần ghi chú ở trang 91, tức là r[A] = m và m < n. Bài
toán đối ngẫu của (4.1) có dạng:

.j
là các vectơ cột của A, j = 1,2,…,n. Đặt
(4.4) X = {x∈R
n
/ Ax = b, x ≥ 0}
hay
____ ____
n
i. i j
X {x R / A ,x b ,i 1,m;x 0, j 1,n}= ∈ = = ≥ =
tương ứng
(4.5) Y = {y∈R
m
/ A
T
y ≤ c}
hay
____
m
.j j
Y {y R / A , y c , j 1,n}= ∈ ≤ =
là các tập hợp chấp nhận được của bài toán (4.1), tương ứng (4.3), là bài toán
đối ngẫu của (4.1).
Giả sử B là một ma trận cơ sở nào đó của A, bao gồm các cột của A. Vì
theo giả thiết r[A] = m, nên B có đúng m cột độc lập tuyến tính. Không giảm
tổng quát, giả sử B được viêt dưới dạng (1.11); tức là
(4.6) B = [A.
B1
, A.
B2

 
Trong đó
1
Bi
A ,1 i m
−
≤ ≤
, ký hiệu hàng i của ma trận B
-1
. Từ đây suy ra
Lê Văn Phi, Khoa Toán – Thống kê, Đi h?c Kinh t Tp. HCM 99
L thuyt qui hoch tuyn tnh
(4.7)
1
Bi .Bk
1, khi i k
A ,A
0, khi i k
−
=

=

≠

Biến đổi tương tự như phần 1.2, trang 94, hệ phương trình {Ax = b, Z =
〈c,x〉} tương đương với dạng chính tắc mở rộng (1.20)

Bi ij j i0
j J

1
Bi.
A ,b
−
, i =1,2,…,m

m m
1 1
m 1,0 Bi i0 Bi Bi B
i 1 i 1
y c y c A ,b c ,B b
− −
+
= =
= = =
∑ ∑( )
m m
1
m 1, j Bi ij j Bi Bi. . j j
i 1 i 1
y (c y c ) c A ,A c
−
+
= =
= − = −
∑ ∑


0
và dạng chính tắc (4.8) ta phân biệt 3 trường hợp:
Trường hợp 1: 1
%'
≥KJi =1,2,…,m. Khi ấy (4.8) là dạng chính tắc chấp
nhận được. Do vậy X ≠ ∅ và có thể áp dụng phương pháp đơn hình thông
thường để giải bài toán QHTT (4.1).
Trường hợp 2: ∃AJ≤A≤7Jvới1
A'
XKva∃4J≤4≤J1
7YJ4
ZK.
Trong trường hợp này không thể áp dụng được phương pháp đơn hình thông
thường và phương pháp đơn hình đối ngẫu. Người ta tìm cách biến đổi (4.8)
sao cho hoặc là xãy ra trường hợp 1 hoặc trường hợp 3.
Trường hợp 3: ∃AJ≤A≤7Jvới1
A'
XKvà ∀[FJ.J\J1
7YJ[
≤K-
Khi đó điểm x
0
được gọi là một giả phương án của bài toán (4.1). Bạn đọc
sẽ chứng minh trong bài tập rằng điểm
(4.10) y
0
= (B
-1
)
T