Lyự thuyeỏt qui hoaùch tuyeỏn tớnh
C HNG VI: TI U TUYN TNH CHA THAM S
Trong thc t, mt s mụ hỡnh bi toỏn ti tuyn tớnh, cỏc h s ban u nh a
ij
, b
i
, c
j
, i
= 1,2,,m; j = 1,2,,n, cú th khụng c cho bit mt cỏch chớnh xỏc hoc giỏ tr ca
chỳng thng ph thuc vo s thay i ca mt hay nhiu tham s nh thi gian, thi tit,
cht lng nguyờn liu, nhiờn liu v.v Nu phi tin hnh vic gii bi toỏn ng vi tng
giỏ tr khỏc nhau ca cỏc tham s y thỡ khi lng v do úchi phớ tớnh toỏn s rt ln v, do
vy, vic gii bi toỏn TTT tỡm phng ỏn ti u s mt ht ý ngha kinh t.
khc phc khú khn ny ngi ta ó phỏt trin mt phng phỏp gi l phng phỏp
gii bi toỏn TTT cha tham. Phng phỏp ny xut phỏt t vic gii bi toỏn TTT i
vi mt giỏ tr xỏc nh ca tham s cn kho sỏt bng phng phỏp n hỡnh thụng thng,
Sau ú s tỡm khong bin thiờn ca tham s cho phng ỏn hin cú vn cũn l phng ỏn
ti u ca bi toỏn mi hoc s trc tip tỡm ra phng ỏn ti u mi da trờn phng ỏn ti
u hin cú. Bng cỏch y ngi ta s tỡm ra phng ỏn ti u ca cỏc bi toỏn TTT ng vi
tng giỏ tr khỏc nhau ca tham s cn kho sỏt.
Ngi ta phõn bit thnh bi toỏn qui hoch tuyn tớnh cha mt tham s h s hm
mc tiờu (c
j
), v phi (b
i
), h s cỏc rng buc (a
ij
), cha mt tham s c hm mc tiờu
v v phi hoc cha hai tham s cựng bin thiờn c lp v.v.Trong phm vi giỏo trỡnh
ny chỳng tụi ch xột hai loi bi toỏn u tiờn.

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


u t v (2.4)
Trong ú c
j
, d
j
, a
ij
, b
i
, i = 1,2,,m; j = 1,2,,n v u, v l cỏc s cho trc; t l tham s; u cú
th l -, v cú th l + ; tc tham s t cú th khụng b chn di hoc khụng b chn trờn.
thy rng ng vi mi giỏ tr c nh ca tham s t = t
0
[u,v] bi toỏn ti u
chatham s (2.1) (3.3) tr thnh bi toỏn TTT bỡnh thng. Vỡ vy, ngi ta gi bi toỏn
(2.1) - (2.4) l bi toỏn TTT cha tham s (hay, ngn gn, bi toỏn ti u tham s). Ngoi
ra, cho bi toỏn tham s cú ý ngha thỡ ngoi cỏc gi thit cn cú ca bi toỏn TTT thụng
thng ngi ta cũn gi thit rng ớt nht mt h s d
j
, 1 j n, l khỏc khụng, bi vỡ, nu d

tương ứng dưới dạng: a
m+1,j
= h
j
+ g
j
t ,j = 0,1,2,…,n (trong đó h
j
được tính theo c
j
và g
j
theo
d
j
). Có 3 trường hợp xảy ra:
• Trường hợp 1: Bài toán P(0,t
0
) không có lời giải chấp nhận được.
• Trường hợp 2: Bài toán P(0,t
0
) không có lời giải tối ưu; tức là hàm mục tiêu (2.1) ứng với
t = t
0
không bị chặn dưới trên tập hợp chấp nhận được.
• Trường hợp 3: Bài toán P(0,t
0
) có lời giải cơ sở tối ưu là x
0
.

n
m j j m
j m
Z a t x b t
+ +
= +
+ =
∑
(2.5)
Giá trị các biến cơ sở x
0
i
= a
i0
≥ 0, i =1,2,…,m, và giá trị các biến phi cơ sở x
j
j = m+1, 2, . . .,
n, đều bằng 0; tức là x
m+k
= 0. Đồng thời giá trị hàm mục tiêu tương ứng Z
0
= b
m+1
. Theo qui
ước như trên các các hệ số đặc trưng a
m+1,j
có dạng
a
m+1,j
(t) = h

toán P(0,t
0
).
Lê Văn Phi
Lyù thuyeát qui hoaïch tuyeán tính
Giá trị hàm mục tiêu ứng với phương án cơ sở x
0
là
b
m+1
(t
0
) = h
0
+ g
0
.t
0
, (2.9)
Theo thuật toán đơn hình, trường hợp 2 xảy ra khi tồn tại một hệ số đặc trưng a
m+1,l
= h
l,
+
g
l
.t
0
> 0, m+1≤ l ≤ n, và y
i,l

m+1,l
(t) = h
l,
+ g
l
.t

> 0 ứng với mọi giá trị của t > t’, với

0
l
l
t
g
h
't <−=
(2.10)
Suy ra ∀t > t’ bài toán P(0,t) có hàm mục tiêu không bị chặn dưới và, do đó, không
giải được. Nếu t’< u, thì bài toán P(0,t) không giải được với mọi t∈[u,v]. Khi t’≥ u thì
còn phải xét bài toán P(0,t) ứng với t ∈[u,t’]. Để làm việc này ta xuất phát từ bảng
đơn hình hiện có, đặt t
0
= t’ và tính lại các hệ số đặc trưng a
m+1,j
(t’) = h
j
+g
j
.t’,j =1,2,
…,n cũng như giá trị hàm mục tiêu b

Suy ra ∀t < t” bài toán P(0,t) có hàm mục tiêu không bị chặn dưới và do đó không
giải được. Nếu t”> v, thì bài toán P(0,t) không giải được với mọi t∈[u,v]. Khi t”≤ v
còn phải xét bài toán P(0,t) ứng với t ∈[t”,v]. Để làm việc này ta xuất phát từ bảng
đơn hình hiện có, đặt t
0
= t” và tính lại các hệ số đặc trưng a
m+1,j
(t”) = h
j
+ g
j
.t” =1,2,
…,n cũng như giá trị hàm mục tiêu b
m+1
(t”) = h
0
+g
0
t”. Sau đó sẽ xuất hiện hoặc
trường hợp 2 hoặc trường hợp 3 như trên.
3) Xét trường hợp 3:
Cũng không làm mất tính tổng quát, giả sử lời giải tối ưu x
0
tương ứng với bảng đơn hình
dạng (2.5). Khi đó các hệ số đặc trưng a
m+1,j
(t
0
) = h
j

, khi g
j
< 0.
Đặt
Lê Văn Phi
Lyù thuyeát qui hoaïch tuyeán tính
t
-1
=
n, ,1j,0g,u
)
g
h
(max
j
j
j
0g
j
=∀≥
−
<
(2.13)
và
t
1
=
n, ,1j,0g,v
)
g

–1
≤ u và t
1
≥ v thì việc giải bài toán tham số P(0,t) kết thúc. Ngược lại, nếu t
–
1
> u hoặc t
1
< v thì còn tiếp tục khảo sát bài toán P(0,t) ứng với t∈[u, t
-1
] hoặc t∈[t
1
, v]. Khi
đó x
0
có thể không còn là phương án tối ưu của các bài toán P(0,t) tương ứng. Ta khảo sát
từng trường hợp cụ thể:
a) Trường hợp t
1
< v: Giả sử
0g,
g
h
t
r
r
r
1
>−=
. Vì g

> 0. Tiếp tục
thực hiện phép biến đổi đơn hình với cột chuẩn là cột r. Từ đây sẽ xác định tiếp t
2
theo
(2.14). Phương án mới cũng sẽ tối ưu ứng với t∈[t
1
, t
2
]. Sau đó, hoặc thuật toán kết thúc
với kết luận P(0,t) ứng với t∈(t
2
, v] không giải được hoặc xác định tiếp t
3
, v.v…
b) Trường hợp t
-1
> u: Giả sử
0g,
g
h
t
r
r
r
1
<−=
−
. Vì g
m+r
< 0, nên,∀t < t

> 0.
Tiếp tục thực hiện phép biến đổi đơn hình với cột chuẩn là cột r. Từ đây sẽ xác định tiếp t
-
2
theo (2.13). Phương án mới cũng sẽ tối ưu ứng với t∈[t
-1
, t
-2
]. Sau đó, hoặc thuật toán kết
thúc với kết luận P(0,t) ứng với t∈[u, t
-2
) không giải được hoặc xác định tiếp t
-3
, v.v…
2.1.2 Ví dụ:
Giải bài toán QHTT chứa tham số sau đây:
2t3
7, ,2,1j,0x
5xx3x3x2x
5xx2xx3x2
0xxxx2x
minx)t21(x)t23(x)t2(x)t1()x(f
j
74321
64321
54321
4321
≤≤−



Ta có bảng đơn hình tương ứng
27
.
27
Để đơn giản, các cột ứng với các biến cơ bản không được trình bày trong bảng. Ta gọi đó là bảng đơn hình rút gọn.
Lê Văn Phi
Lyù thuyeát qui hoaïch tuyeán tính
Bảng 6.1:
Hệ số ẩn
cơ sở
c
j
d
j
b
i
x
1
x
2
x
3
x
4
c
j
1 2 3 1
d
j
-1 -1 -2 2

-1
như sau:
,
g
h
2
1
}
2
1
{max
g
h
maxt
4
4
j
j
0g
1
j
−=−=
−
−
−=






j
−==
−
−
−
−
−
−=










−=
>
Vậy là phương án x
0
= (0, 0, 0, 0, 0, 5, 5) là phương án tối ưu với mọi bài toán P(0,t) trong
khoảng [-1/2, 1]. Chúng ta còn phải xét P(0,t) trong các khoảng [-3, -1/2) và (1, 2].
Xét khoảng (1, 2]. Thực hiện phép biến đổi đơn hình với cột chuẩn r = 1ta có bảng 2.
Trong bảng này phương án tối ưu vẫn là x
0
, nhưng x
1
trở thành biến cơ bản, x

x
1
1 -1 0 1 -2 1 -1
x
6
0 0 5 -2 7 -3 4
x
7
0 0 5 1 0 4 -4
h
j
t
1
= 1 0 0 -4 -2 -2
g
j
0 0 3 1 -1
a
m+1,j
0 0 -1 -1 -3

2
2
j
j
0g
2
g
h
3

0
vẫn là phương án tối ưu của mọi bài toán P(0,t), t∈[1, 4/3]. Giá trị tối
ưu là hàm số của t có dạng ϕ(t) = ∆
0
(t) = 0+0.t = 0. Tiếp tục thực hiện phép biến đổi đơn
hình, đưa x
2
vào hệ ẩn cơ bản thay cho x
6
ta có Bảng 2.3.
Ở Bảng 2.3 ta có phương án tối ưu là x
1
= (10/7, 5/7, 0, 0, 0, 0, 5). Phương án này khác
với x
0
nhưng giá trị tối ưu vẫn bằng 0. Ta có
Lê Văn Phi
Lyù thuyeát qui hoaïch tuyeán tính

3
3
j
j
0g
3
g
h
8
13
}

bởi x
3
ta có bảng 4 với phương án tối ưu mới là x
2
= (5/4, 5/4, 5/4, 0, 0, 0, 0).
Bảng 6.3:
Hệ số ẩn
cơ sở
c
j
d
j
b
i
x
5
x
6
x
3
x
4
c
j
0 0 3 1
d
j
0 0 -2 2
x
1

6
x
7
x
4
c
j
0 0 0 1
d
j
0 0 0 2
x
1
1 -1 5/4 -1/28 2/7 11/28 2/7
x
2
2 -1 5/4 3/28 1/7 -5/28 1/7
x
3
3 -2 5/4 1/4 0 1/4 -1
h
j
t
3
= 13/8 15/2 13/14 4/7 11/14 -24/7
g
j
-5 -4/7 -3/7 -5/7 -3/7
a
m+1,j

x
7
0 0 25/2 2 13/2 3/2 3/2
h
j
t
-1
= -1/2 5/2 0 -1/2 -7/2 1/2
g
j
5 3 4 1 1
a
m+1,j
0 -3/2 -5/2 -4 0
Ở Bảng 2.4, vì g
j
≤ 0, ∀j, nên t
4
= v = 2. Vậy phương án x
2
là phương án tối ưu ứng với các
bài toán P(0,t), t∈[13/8, 2].
Trở lại Bảng 2.1, vì t
-1
= -1/2 > -3, nên còn phải xét các bài toán P(0,t) với t∈[-3, -1/2].
Do t
-1
= -h
4
/g

• t∈[13/8, 2]: Phương án tối ưu: x* = (5/4, 5/4, 5/4, 0, 0, 0, 0)
Giá trị tối ưu f
min
(x*) = ϕ(t) = 15/2 – 5t
Biểu diễn trên hệ trục toạ độ vuông góc, ta thấy hàm ϕ(t) là hàm lõm và tuyến tính từ
khúc:
Hình 6.1
-3 -2 -1 -1/2 0 1 4/3 3/8 2
t
-2
-5/2
ϕ(t)
-25/2
2.2 Bài toán tối ưu tuyến tính với tham số ở vectơ vế phải
2.2.1 Cơ sở lý thuyết và thuật toán
Ta xét bài toán TƯTT sau đây:
Tìm giá trị của x
1
, x
2
,…, x
n
làm cực tiểu hàm mục tiêu
∑
=
=
n
1j
jj
xc)x(Z

∑
=≥=+=∈=
=
n
1j
jiijij
n
n, ,2,1j,0x;m, ,2,1i,q.tpxa/Rx)t(X
(2.19)
Để cho bài toán QH tuyến tính chứa tham số ở vế phải (2.15) – (2.18) có ý nghĩa thì phải
có ít nhất một hệ số q
i
khác không. Nhằm phân biệt với bài toán TƯ tuyến tính chứa tham số
ở hàm mục tiêu P(0,t) người ta ký hiệu bài toán này là P(t,0).
Người ta có thể ứng dụng phương pháp đã trình bày ở Phần 2.1 để giải bài toán (2.15) –
(2.18) bằng cách thành lập bài toán đối ngẫu tương ứng P(0,t):
Tìm giá trị của y
1
, y
2
,…, y
m
làm cực đại hàm mục tiêu
∑
+=
=
m
1i
iii
y)tqp()y(W

Ax = b
x ≥ 0
(D) W(y) = b
T
y → max
A
T
y ≤ c

là những lời giải tối ưu thì điều kiện cần và đủ là giá trị hàm mục tiêu tương ứng bằng nhau,
tức là
Z(x
0
) = W(y
0
) (2.23)
Một lời giải của hệ phương trình Ax = b gọi là giả phương án của (P), nếu điều kiện tối ưu
thỏa mãn, tức là
a
m+1,j
≤ 0, ∀j (2.24)
Phương pháp đơn hình đối ngẫu xuất phát từ một giả phương án như vậy. Nếu không tồn tại
giả phương án nào như vậy thì bài toán (D) không có lời giải chấp nhận được. Suy ra bài toán
(P) cũng không giải được (có thể hàm mục tiêu không bị chặn). Trong quá trình thực hiện
phương pháp này, điều kiện (2.9) và (2.10) luôn luôn được đảm bảo. Khi một giả phương án
x
0
đồng thời là phương án (tức là thỏa mãn điều kiện không âm x
0
j

1
( ) , 1,2, ,
( ) ( )
n
i ij j i i i
j m
n
m k j j m
j m
x a x b t h g t i m
Z x a x b t h g t
= +
+ +
= +
+ = = + =
+ = = +


(2.25)
trong ú
a
m+j
0, j = 1,2,,n (2.26)
v

1 1
i i i i
h (A )'p, g (A )'q

= =

0
j 0
x (t ) 0, j m 1, ,n= = +
Giỏ tr hm mc tiờu bng Z(x
0
(t
0
)) = h
0
+
00
t.g
. Vỡ cỏc h s c trng y
m+1,j
, j = 1,2,, n,
c lp vi t nờn phng ỏn x
0
vn cũn l phng ỏn ti u chng no cỏc bin x
j
cũn tha
món iu kin khụng õm. Tc l
0
i i i
x (t) h g t,= +
0, i =1,2,,m (2.28)
Suy ra
0gkhi,
g
h
t

m, ,1i,0g,,u
g
h
max
t
i
i
i
0g
1
i
(2.29)
v





=







=
<
m, ,2,1i,0g,v
g

t
r
r
r
1
>=

. Khi ú
t.gh)t(x
rr
0
Br
+=
< 0 vi mi giỏ tr ca t < t
-1.
.
Nu y
rj
0, j = 1,2,,n thỡ x
Br
(t) = h
r
+ g
r
t < 0, t < t
-1
. Vỡ vy tp X(t) = , t < t
-1
.
29




=
+
<
+
rj
j,1m
0y
rs
s,1m
y
y
min
y
y
rj
(2.31)
Dễ thấy rằng phương án mới x
(1)
là tối ưu ứng với t = t
-1
. Tiếp tục xác định t
-2
, theo (2.29)
để cho x
(1)
là phương án tối ưu của các bài toán P(t,0) ứng với t∈[t
-2

≥ 0, j = 1,2,…,n thì x
Br
(t) = h
r
+ g
r
t < 0, ∀ t > t
1
. Vì vậy tập X(t) = ∅, ∀t > t
1
.
• Trong trường hợp ngược lại, ta sẽ tiến hành phép biến đổi đơn hình, trong đó biến x
r
được
thay bởi biến x
s
với cột s, s∈J, là cột chuẩn xác định theo (2.31). Dễ thấy rằng phương án
mới x
(2)
là tối ưu ứng với t = t
1
. Tiếp tục xác định t
2
, theo (2.29) để cho x
(2)
là phương án
tối ưu của các bài toán P(t,0) ứng với t∈[t
1
,t
2

+=++−+
−=+−+−
→+++−=
Bài giải: Bảng đơn hình xuất phát với t
0
= 0:
Bảng 6.6:
Hệ số ẩn
cơ sở
t
0
= 0
h
i
g
i
x
1
x
2
x
3
x
4
-2 3 1 4
x
0
x
5
0 1 -1 1 -2 1 -1 1

x
5
x
6
x
3
x
4
-2 3 1 4
x
0
x
1
-2 1 3/7 3/7 2/7 1/7 1/7 1
Lê Văn Phi
Lyù thuyeát qui hoaïch tuyeán tính
x
2
3 0 5/7 -2/7 1/7 -3/7 4/7 0
x
7
0 4 1 1 0 4 -4 4
a
m+1,j
-2 9/7 -12/7 -1/7 -18/7 -18/7 -2
Ta xác định

0
g
h

−
, t
1
= 2, vì g
i
≥ 0, ∀i
Như vậy, phương án x
0
= (1+(3/7)t, (5/7)t, 0, 0, 0, 0, 4+t) là phương án tối ưu ứng với mọi bài
toán P(t,0), t∈[0, 2]. Giá trị tối ưu tương ứng φ(t) = -2 + (9/7)t. Vì t
1
= (-p
2
/q
2
) nên hàng chuẩn
là i = 2. Ta tìm cột chuẩn theo (2.17) và có m+s = 1 hoặc 3. Chọn cột chuẩn là 1. Thực hiện
phép biến đổi đơn hình, thay x
2
bởi x
5
, ta có Bảng 6.8. Phương án tối ưu mới x
1
= (1 + (3/2)t,
0, 0, 0, (-5/2)t, 0, 4 +(7/2)t. Tiếp tục xác định t
-2
= max {-2/3, -8/7} = -2/3 = -p
1
/q
1

7
0 4 7/2 1/2 1/2 5/2 -2 4
a
m+1,j
-2 -3 -6 -1 0 -6 0
Chọn hàng chuẩn là hàng 1, thay x
1
bởi x
3
, ta có bảng 9 với phương án tối ưu là x
2
= (0, 0, -2
–3t, 0, 3 +2t, 0, 9+11t) và giá trị tối ưu vẫn là φ(t) = -2 -3t. Phương án này tối ưu trong
khoảng t∈[-9/11, -2/3] với
t
-3
= max {-3/2, -9/11} = -9/11 = h
3
/g
3
.
Bảng 6.9:
Hệ số ẩn
cơ sở
t
-2
= -9/11
p
j
q

• t < -9/11: Bài toán P(t,0) không giải được;
• -9/11 ≤ t ≤ -2/3: Phương án tối ưu là x
2
= (0, 0, -2 –3t, 0, 3 +2t, 0, 9+11t); giá trị tối ưu
φ(t) = -2 -3t
• -2/3 ≤ t ≤ 0: Phương án tối ưu là x
1
= (1 + (3/2)t, 0, 0, 0, (-5/2)t, 0, 4 +(7/2)t; giá trị
tối ưu φ(t) = -2 -3t
• 0 ≤ t ≤ 2: Phương án tối ưu là x
0
= (1+(3/7)t, (5/7)t, 0, 0, 0, 0, 4+t) ; giá trị tối ưu
φ(t) = -2 + (9/7)t.
Lê Văn Phi
Lyù thuyeát qui hoaïch tuyeán tính
Hình 6.2
φ(t) 1

4/7
5/11

–2 -1 –9/11 –2/3 0 1 2 t

-2
Rõ ràng φ(t) là các hàm lồi (ss. Hình 6.2).
*
* *
Lê Văn Phi
φ
(

φ
(
t
)

=

-
2-
3
t
φ(t) = -2 + (9/7)t.