Xem mẫu
- Lyù thuyeát qui hoaïch tuyeán tính
C HƯƠNG VI: TỐI ƯU TUYẾN TÍNH CHỨA THAM SỐ
Trong thực tế, ở một số mô hình bài toán tối tuyến tính, các hệ số ban đầu như a ij, bi,
cj, i = 1,2,…,m; j = 1,2,…,n, có thể không được cho biết một cách chính xác hoặc giá trị
của chúng thường phụ thuộc vào sự thay đổi của một hay nhiều tham số như thời gian,
thời tiết, chất lượng nguyên liệu, nhiên liệu v.v… Nếu phải tiến hành việc giải bài toán
ứng với từng giá trị khác nhau của các tham số ấy thì khối lượng và do đóchi phí tính toán
sẽ rất lớn và, do vậy, việc giải bài toán TƯTT tìm phương án tối ưu sẽ mất hết ý nghĩa
kinh tế.
Để khắc phục khó khăn này người ta đã phát triển một phương pháp gọi là phương
pháp giải bài toán TƯTT chứa tham. Phương pháp này xuất phát từ việc giải bài toán
TƯTT đối với một giá trị xác định của tham số cần khảo sát bằng phương pháp đơn hình
thông thường, Sau đó sẽ tìm khoảng biến thiên của tham số để cho phương án hiện có
vẫn còn là phương án tối ưu của bài toán mới hoặc sẽ trực tiếp tìm ra phương án tối ưu
mới dựa trên phương án tối ưu hiện có. Bằng cách ấy người ta sẽ tìm ra phương án tối ưu
của các bài toán TƯTT ứng với từng giá trị khác nhau của tham số cần khảo sát.
Người ta phân biệt thành bài toán qui hoạch tuyến tính chứa một tham số ở hệ số hàm
mục tiêu (cj), ở vế phải (bi), ở hệ số các ràng buộc (aij), chứa một tham số ở cả hàm mục
tiêu và ở vế phải hoặc chứa hai tham số cùng biến thiên độc lập v.v….Trong phạm vi giáo
trình này chúng tôi chỉ xét hai loại bài toán đầu tiên.
Tương tự như ở các chương trước chúng tôi không đi sâu vào phân tích cơ sở lý thuyết
của phương pháp giải, không trình bày kỹ phần chứng minh các định lý mà chú trọng trình
bày thuật toán giải và các ý nghĩa kinh tế cũng như thực tiễn. Để nghiên cứu thêm phần cơ
sở lý thuyết, tìm hiểu thêm các phương pháp giải bài toán TƯTT chứa tham số khác, bạn
đọc có thể tham khảo thêm ở [ ].
2.1 Phương pháp đơn hình giải bài toán TƯTT chứa tham số ở hàm mục tiêu
2.1.1. Cơ sở lý thuyết và thuật toán
Ta xét bài toán qui hoạch sau đây:
Tìm giá trị của x1, x2,…, xn làm cực tiểu hàm mục tiêu
n
Z( x ) = ∑ (c j + d j t ) x j (2.1)
j =1
ứng với các ràng buộc
n
∑ aij xj = bi , i = 1,2,..., m (2.2)
j=1
xj ≥ 0, j = 1,2,..., n ( 2.3)
u≤ t≤ v (2.4)
Trong đó cj, dj, aij, bi, i = 1,2,…,m; j = 1,2,…,n và u, v là các số cho trước; t là tham số; u có
thể là -∞, v có thể là + ∞; tức tham số t có thể không bị chặn dưới hoặc không bị chặn
trên.
Đễ thấy rằng ứng với mỗi giá trị cố định của tham số t = t 0∈[u,v] bài toán tối ưu
chứatham số (2.1) – (3.3) trở thành bài toán TƯTT bình thường. Vì vậy, người ta gọi bài
toán (2.1) - (2.4) là bài toán TƯTT chứa tham số (hay, ngắn gọn, bài toán tối ưu tham số).
Ngoài ra, để cho bài toán tham số có ý nghĩa thì ngoài các giả thiết cần có của bài toán
Lê Văn Phi 87
- Lyù t huyeát qui hoaï ch t uyeán tí nh
TƯTT thông thường người ta còn giả thiết rằng ít nhất một hệ số d j, 1 ≤ j ≤ n, là khác
không, bởi vì, nếu dj = 0, ∀j, thì bài toán (2.1)-(2.4) trở thành bài toán TƯTT thông thường.
Nhằm đơn giản cách trình bày bắt đầu từ đây chúng ta ký hiệu bài toán (2.1)-(2.4) là
P(0, t). Ta nhận thấy rằng các aij và bi, i = 1,2,…,m; j = 1,2,…, n, đều không phụ thuộc vào
tham số t nên tập các phương án chấp nhận được X là như nhau ứng với mọi giá trị của t.
Vì vậy, nếu ứng với một giá trị nào đó của tham số t mà miền chấp nhận được rỗng thì
hiển nhiên miền chấp nhận được của bài toán (2.1) – (2.4) cũng là rỗng với mọi giá trị của
t. Trong trường hợp này bài toán tối ưu tuyến tính tham số (2.1) – (2.4) không giải được
với mọi giá trị của t, đặc biệt với t∈[u,v].
Phương pháp giải bài toán tối ưu tham số (2.1) - (2.4) bắt đầu bằng việc cho tham số t
nhận giá trị t0 nào đó thuộc [u,v] (nếu u là hữu hạn, ta đặt t = u) 26. Sau đó áp dụng phương
pháp đơn hình (hoặc đơn hình mở rộng) giải bài toán P(0,t0). Để dễ dàng cho việc thực
hiện phương pháp giải về sau các hệ số đặc trưng am+1,j được tính tách riêng theo các hệ
số cj và dj tương ứng dưới dạng: am+1,j = h j + gjt ,j = 0,1,2,…,n (trong đó hj được tính theo cj
và gj theo dj). Có 3 trường hợp xảy ra:
• Trường hợp 1: Bài toán P(0,t0) không có lời giải chấp nhận được.
• Trường hợp 2: Bài toán P(0,t0) 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 = t0 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,t0) có lời giải cơ sở tối ưu là x0.
Ta lần lượt xét các trường hợp 1, 2 và 3.
1) Xét trường hợp 1:
Vì như nhận xét ở trên, tập chấp nhận được của bài toán P(0,t) là như nhau đối với
mọi giá trị của t nên, nếu tập này là rỗng ứng với một giá trị t = t 0 nào đó, thì nó cũng là tập
rỗng ứng với mọi giá trị của t. Tức là bài toán tổng quát P(0,t) không có lời giải chấp nhận
được ứng với mọi giá trị t.
2) Xét trường hợp 2:
Không làm mất tính tổng quát và để đơn giản cách trình bày, giả sử phương pháp đơn
hình giải bài toán P(0,t0) dừng lại ở bảng đơn hình ứng với phương án cơ bản x0 có dạng
chính tắc mở rộng như sau:
n
xi + ∑ aij xj = bi , i = 1,2,…,m
j= m+1
n
Z+ ∑ am+1, j (t0 )xj = bm+1 (t0 ) (2.5)
j= m+1
Giá trị các biến cơ sở x0i = ai0 ≥ 0, i =1,2,…,m, và giá trị các biến phi cơ sở xj j = m+1, 2, . .
., n, đều bằng 0; tức là xm+k = 0. Đồng thời giá trị hàm mục tiêu tương ứng Z 0 = bm+1. Theo
qui ước như trên các các hệ số đặc trưng am+1,j có dạng
am+1,j (t) = h j + g j.t, j = 0, 1,2,…,n (2.6)
Trong đó
m m
hj = ∑ aij cBi − cj , gj = ∑ aij dBi − dj , j = 1,2,...n (2.7)
i =1 i =1
26
Trên thực tế, người ta thường chọn t = t0 sao cho dễ dàng áp dụng phương pháp đơn hình tìm lời giải tối ưu của
bài toán P(0,t0).
Lê Văn Phi 88
- Lyù thuyeát qui hoaïch tuyeán tính
m m
h0 = ∑ ci bi , g0 = ∑ di bi (2.8)
i =1 i =1
Giá trị hàm mục tiêu ứng với phương án cơ sở x0 là
bm+1 (t0) = h 0 + g 0.t0, (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 =
hl, + gl.t0 > 0, m+1≤ l ≤ n, và yi,l ≤ 0, i =1,2,…, m và do đó hàm mục tiêu sẽ không bị chặn
dưới trên tập các phương án chấp nhận được của bài toán ứng với t = t0. Từ đó ta xét 3
trường hợp con như sau:
i) gl = 0: Khi đó hàm mục tiêu của bài toán P(0,t) không bị chặn dưới ứng với mọi giá
trị của t, vì
am+1,l (t) = hl, + gl.t = hl > 0, ∀t.
Kết hợp với điều kiện ai,l ≤ 0, i =1,2,…, m, suy ra bài toán không giải được ∀t.
ii) gl > 0: Khi đó am+1,l (t) = hl, + gl.t > 0 ứng với mọi giá trị của t > t’, với
h
t' = − l < t 0 (2.10)
gl
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 t0 = t’ và tính lại các hệ số đặc trưng am+1,j (t’) = hj+gj.t’,j
=1,2,…,n cũng như giá trị hàm mục tiêu bm+1(t’) = h0+g0t’. Sau đó sẽ xuất hiện hoặc
trường hợp 2 hoặc trường hợp 3.
iii) gl < 0: Khi đó am+1,l = hl, + gl.t > 0 ứng với mọi giá trị của t < t”, với
h
t" = − l > t 0 (2.11)
gl
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 t0 = t” và tính lại các hệ số đặc trưng am+1,j(t”) = hj + gj.t” =1,2,
…,n cũng như giá trị hàm mục tiêu bm+1(t”) = h0 +g0t”. 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 x0 tương ứng với bảng đơn
hình dạng (2.5). Khi đó các hệ số đặc trưng am+1,j (t0) = hj + gjt0 ≤ 0, j=1,2,…,n. Dễ thấy
rằng ứng với j, 1≤ j ≤ n, điều kiện
am+1,j (t) = hj + gjt ≤ 0 (2.12)
vẫn thỏa mãn với mọi giá trị t sao cho
hj
t≤ − , khi gj > 0,
gj
hj
hoặc t≥ − , khi gj < 0.
gj
Đặ t
Lê Văn Phi 89
- Lyù t huyeát qui hoaï ch t uyeán tí nh
hj
max (− )
t -1 = g j 0 gj (2.14)
v , g j ≤ 0, ∀j = 1,..., n
Khi đó dễ thấy rằng (2.12) thỏa mãn với mọi j = 1,2,…,n, ứng với các giá trị t ∈[t -1 , t1]
và t -1 ≤ t0 ≤ t1. Tức là phương án x0 hiện có là phương án tối ưu ứng với mọi bài toán
P(0,t) với t∈[t -1 , t1]. Nếu t –1 ≤ u và t1 ≥ 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 t1 < 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∈[t1 , v]. Khi đó x0 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ể:
hr
a) Trường hợp t1 < v: Giả sử t 1 = − , g r > 0 . Vì gm+r > 0, nên,∀t > t1, am+1,r(t) = hr + gr.t >
gr
am+1,r(t) = hr + gr.t1 = 0. Do đó điều kiện tối ưu ứng với x0 không còn thỏa mãn. Nếu air
≤ 0, i = 1,2,…,m thì hàm mục tiêu Z(t) không bị chặn dưới với mọi giá trị t > t 1. Do đó
P(0,t) ứng với mọi t∈(t1,v] không giải được. Ngược lại, giả sử ∃ p, 1≤ p ≤ m, với apr >
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 t2 theo (2.14). Phương án mới cũng sẽ tối ưu ứng với t∈[t1, t2]. Sau đó, hoặc
thuật toán kết thúc với kết luận P(0,t) ứng với t ∈(t2, v] không giải được hoặc xác định
tiếp t3, v.v…
hr
b) Trường hợp t-1 > u: Giả sử t −1 = − , g r < 0 . Vì gm+r < 0, nên,∀t < t-1, am+1,r(t) = hr + gr.t
gr
> am+1,r(t-1) = hr + gr.t-1 = 0. Do đó điều kiện tối ưu ứng với x0 không còn thỏa mãn. Nếu
air ≤ 0, i = 1,2,…,m thì hàm mục tiêu Z(t) không bị chặn dưới với mọi giá trị t < t -1. Do
đó P(0,t) ứng với mọi t∈(u, t-1] không giải được. Ngược lại, giả sử ∃ p, 1≤ p ≤ m, với
apr > 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:
f (x) = (1− t)x1 + (2 − t)x2 + (3 − 2t)x3 + (1+ 2t)x4 → min
x1 − 2x2 + x3 − x4 + x5 =0
2x1 + 3x2 − x3 + 2x4 + x6 =5
− x1 + 2x2 + 3x3 − 3x4 + x7 =5
x j ≥ 0, j = 12,...,
, 7
− 3≤ t ≤ 2
Lê Văn Phi 90
- Lyù thuyeát qui hoaïch tuyeán tính
Bài giải: Chọn t0 = 0. Phương án xuất phát với các biến cơ bản x 5 = 0, x6 = 5, x7 = 5 và các
biến không cơ bản x1 = x2 = x3 = x4 = 0. Đây đồng thời là phương án tối ưu với Z(x0,0) = 0.
Ta có bảng đơn hình tương ứng27.
Bảng 6.1:
Hệ số ẩn bi x1 x2 x3 x4
cơ sở cj 1 2 3 1
cj dj dj -1 -1 -2 2
x5 0 0 0 1 -2 1 -1
x6 0 0 5 2 3 -1 2
x7 0 0 5 -1 2 3 -3
hj t0 = 0 0 -1 -2 -3 -1
gj 0 1 1 2 -2
ym+1,j 0 -1 -2 -3 -1
Ở Bảng 2.1, phương án xuất phát đồng thời là phương án tối ưu khi t0 = 0, vì các hệ số
đặc trưng am+1,j ≤ 0, j = 1,2,…,n; Z(x0) = 0. Ta xác định các cận t 1 và t -1 như sau:
hj
−1 1 h
t −1 = max− = max − }= − = − 4 ,
{
gj < 0 g j
−2 2 g4
hj −1 − 2 − 3 h
t1 = min− = min{ − ,− ,− }= 1 = − 1 ,
gj > 0 g j
1 1 2 g1
Vậy là phương án x0 = (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à x0, nhưng x1 trở thành biến cơ bản, x5 là biến phi
cơ sở. Để tìm khoảng biến thiên của t sao cho x0 vẫn còn là phương án tối ưu ta tính t2 như
sau:
Bảng 6.2:
Hệ số ẩn bi x5 x2 x3 x4
cơ sở cj 0 2 3 1
cj dj
dj 0 -1 -2 2
x1 1 -1 0 1 -2 1 -1
x6 0 0 5 -2 7 -3 4
x7 0 0 5 1 0 4 -4
hj t1 = 1 0 0 -4 -2 -2
gj 0 0 3 1 -1
am+1,j 0 0 -1 -1 -3
hj −4 −2 4 h
t2 = min− = min{− ,− }= = − 2
gj > 0 gj 3 1 3 g2
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 91
- Lyù thuyeát qui hoaïch tuyeán tính
Do vậy phương án x0 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 x2 vào hệ ẩn cơ bản thay cho x6 ta có Bảng 2.3.
Ở Bảng 2.3 ta có phương án tối ưu là x1 = (10/7, 5/7, 0, 0, 0, 0, 5). Phương án này khác
với x0 nhưng giá trị tối ưu vẫn bằng 0. Ta có
hj
− 26/ 7 13 h
t3 = min− = min{− }= =− 3
gj > 0 gj 16/ 7 8 g3
Như vậy, phương án x1 = (10/7, 5/7, 0, 0, 0, 0, 5) là phương án tối ưu ứng với các bài toán
P(0,t), t∈[4/3, 13/8]. Giá trị tối ưu là hàm số của t có dạng: ϕ(t) = ∆ 0(t) = 20/7 – (15/7)t.
Thay x7 bởi x3 ta có bảng 4 với phương án tối ưu mới là x2 = (5/4, 5/4, 5/4, 0, 0, 0, 0).
Bảng 6.3:
Hệ số ẩn bi x5 x6 x3 x4
cơ sở cj 0 0 3 1
cj dj dj 0 0 -2 2
x1 1 -1 10/7 3/7 2/7 1/7 1/7
x2 2 -1 5/7 2/7 1/7 -3/7 4/7
x7 0 0 5 1 0 4 -4
hj t2 = 4/3 20/7 -1/7 2/7 -26/7 2/7
gj -15/7 -1/7 -3/7 16/7 -19/7
am+1,j 0 -1/3 0 -2/7 -10/3
Bảng 6.4:
Hệ số ẩn bi x5 x6 x7 x4
cơ sở cj 0 0 0 1
cj dj dj 0 0 0 2
x1 1 -1 5/4 -1/28 2/7 11/28 2/7
x2 2 -1 5/4 3/28 1/7 -5/28 1/7
x3 3 -2 5/4 1/4 0 1/4 -1
hj t3 = 13/8 15/2 13/14 4/7 11/14 -24/7
gj -5 -4/7 -3/7 -5/7 -3/7
am+1,j -5/8 0 -1/8 -1/8 -33/8
Bảng 6.5:
Hệ số ẩn bi x1 x2 x3 x6
cơ sở cj 1 2 3 0
cj dj dj -1 -1 -2 0
x5 0 0 5/2 2 -1/2 1/2 1/2
x4 1 2 5/2 1 3/2 -1/2 1/2
x7 0 0 25/2 2 13/2 3/2 3/2
hj t-1 = -1/2 5/2 0 -1/2 -7/2 1/2
gj 5 3 4 1 1
am+1,j 0 -3/2 -5/2 -4 0
Ở Bảng 2.4, vì gj ≤ 0, ∀j, nên t4 = v = 2. Vậy phương án x2 là phương án tối ưu ứng với
các bài toán P(0,t), t∈[13/8, 2].
Lê Văn Phi 92
- Lyù t huyeát qui hoaï ch t uyeán tí nh
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 = -h4/g4, nên thực hiện phép biến đổi đơn hình bằng cách thay x 6 bởi x4. Ta có Bảng
2.5 với phương án tối ưu là x3 = (0, 0, 0, 5/2, 5/2, 0, 25/2). Giá trị tối ưu có dạng ϕ(t) = 5/2
+ 5t. Ở bảng này do gj ≥ 0, ∀j, nên theo (1.13), t -2 = -3. Như vậy là phương án tối ưu cho
mọi bài toán P(0,t), t∈[-1/2, -3].
Kết luận: Lời giải tối ưu của các bài toán qui hoạch tham số P(0,t) đã cho như sau:
• t∈[-3, -1/2]: Phương án tối ưu: x* = (0, 0, 0, 5/2, 5/2, 0, 25/2)
Giá trị tối ưu fmin(x*) = ϕ(t) = 5/2 +5t
• t∈[-1/2, 4/3]: Phương án tối ưu: x* = (0, 0, 0, 0, 0, 5, 5)
Giá trị tối ưu fmin(x*) = ϕ(t) = 0
• t∈[4/3, 13/8]:Phương án tối ưu: x* = (10/7, 5/7, 0, 0, 0, 0, 5)
Giá trị tối ưu fmin(x*) = ϕ(t) = 20/7 – (15/7).t
• 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 fmin(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 x1, x2,…, xn làm cực tiểu hàm mục tiêu
Lê Văn Phi 93
- Lyù t huyeát qui hoaï ch t uyeán tí nh
n
Z( x ) = ∑ c j x j (2.15)
j=1
ứng với các ràng buộc
n
∑ aij xj = pi + t.qi , i = 1, 2,..., m (2.16)
j=1
xj ≥ 0, j = 1,2,..., n ( 2.17 )
u≤ t≤ v (2.18).
trong đó t là tham số.
Tương tự như bài toán TƯ tuyến tính chứa tham số ở hàm mục tiêu, (2.15)-(2.18) biểu
diễn một lớp các bài toán qui hoạch tuyến tính ứng với các giá trị t khác nhau. Các bài toán
này có hàm mục tiêu (2.15) như nhau. Chúng chỉ phân biệt nhau bởi các tập chấp nhận
được:
n
X (t) = x ∈ R n / ∑ aij x j = pi + t.qi , i = 12,...,m; x j ≥ 0, j = 12,..,n
, , (2.19)
j=1
Để 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ố qi 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 y1, y2,…, ym làm cực đại hàm mục tiêu
m
W ( y) = ∑ (p i + q i t ) y i (2.20)
i =1
ứng với các ràng buộc
m
∑ aij yi ≤ cj , j = 1,2,..., n (2.21)
i =1
u≤ t≤ v (2.22)
Sau đó giải bài toán đối ngẫu P(0,t) và ứng dụng định lý độ lệch bù yếu để tìm lời giải tối
ưu của P(t,0) ứng với từng phương án tối ưu cho từng khoảng biến thiên của t trong bài
toán P(0,t).
Tuy nhiên người ta cũng có thể ứng dụng phương pháp đơn hình đối ngẫu để giải trực
tiếp bài toán P(t,0). Để bạn đọc có cơ sở hiểu được các bước giải, sẽ trình bày ở phần
dưới đây, chúng tôi nhắc lại những điểm cơ bản về lý thuyết đối ngẫu 28. Đó là 3 tính chất
của cặp bài toán TƯTT đối ngẫu, đặc biệt là tính chất 3. Theo tính chất này, để x0, y0 là
hai lời giải chấp nhận được của cặp bài toán TƯTT đối ngẫu tương ứng
(P) Z(x) = cTx → min (D) W(y) = bTy → max
Ax = b ATy ≤ c
x≥ 0
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(x0) = W(y0) (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à
28
Xem chương I
Lê Văn Phi 94
- Lyù thuyeát qui hoaïch tuyeán tính
am+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 x0 đồng thời là phương án (tức là thỏa mãn điều kiện không âm x 0j ≥ 0 ∀j),
thì đây cũng chính là phương án tối ưu. Sau đây là các bước giải bài toán P(t,0).
Trước hết cho t = t0. Ap dụng phương pháp đơn hình mở rộng giải bài toán P(t 0,0). Ta
xét 3 trường hợp:
I) Phương pháp đơn hình mở rộng kết thúc bằng nhận định hàm mục tiêu (2.15) ứng với t
= t0 không bị chặn dưới trên X(t0) ≠ ∅. Khi đó tập chấp nhận được Y của bài toán đối
ngẫu P(0,t0) là tập trống. Vì Y độc lập với t, nên Y(t) = ∅ với mọi giá trị của t, đặc biệt
với t∈[u,v]. Vậy bài toán P(t, 0) không giải được với mọi t∈∈[u,v].
II) Không giảm tổng quát, giả sử phương pháp đơn hình mở rộng giải P(t 0,0) cho phương
án tối ưu là x0 ứng với dạng chính tắc cho bởi
n
xi + ∑ aij xj = bi (t0 ) = hi + gi t0 , i = 1,2,..., m
j= m+1
n
(2.25)
Z(x) + ∑ am+ k, j xj = bm+1 (t0 ) = h0 + g0 t0
j= m+1
trong đó
am+j ≤ 0, j = 1,2,…,n (2.26)
và
h i = (A i−1 )'p, g i = (A i−1 )'q
m m
h 0 = ∑ c Bi h i , g 0 = ∑ c Bi g i (2.27)
i =1 i =1
−1
với A i ký hiệu vectơ hàng i của ma trận B-1 (là nghịch đảo của ma trận cơ sở B ứng với
x0)29; Giá trị các biến cơ cơ sở và các biến phi cơ sở j = m+1, …, n bằng
x 0 (t 0 ) = h i + g i t 0 ,
i
i = 1, 2,..., m
x 0j (t 0 ) = 0, j = m + 1,...,n
Giá trị hàm mục tiêu bằng Z(x0(t0)) = h0 + g 0 .t 0 . Vì các hệ số đặc trưng ym+1,j, j = 1,2,…, n,
độc lập với t nên phương án x0 vẫn còn là phương án tối ưu chừng nào các biến xj còn
thỏa mãn điều kiện không âm. Tức là
x 0 (t) = h i + g i t, ≥ 0, i =1,2,…,m
i (2.28)
hi h
Suy ra t ≥− , khi g i > 0 , và t ≤ − i , khi g i < 0
gi gi
hi
max −
Đặ t t −1 = g >0
i
gi (2.29)
u , , g i ≤ 0, i = 1,..., m
29
Nếu B là ma trận đơn vị thì B-1 cũng vậy, và do đó hàng i của B-1 là vectơ đơn vị thứ i. Khi
đó hi = pi v gi = qi. i = 1, 2, …, m.
Lê Văn Phi 95
- Lyù huyeát quihoaï t
t ch uyeán í
t nh
hi
min −
và t1 = g u, thì còn phải xét P(t,0) ứng với t∈[u,t-1). Giả sử t−1 = − g , gr > 0 . Khi đó
r
a)
r
x ( t ) = h r + g r .t < 0 với mọi giá trị của t < t -1..
0
Br
• Nếu yrj ≥ 0, j = 1,2,…,n thì xBr (t) = hr + gr 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 xr
được thay bởi biến xs với cột s là cột chuẩn, s∈J, xác định như sau:
y m +1,s y m +1, j
= min (2.31)
y rs y t1 ..
r
• Nếu yrj ≥ 0, j = 1,2,…,n thì xBr (t) = hr + gr t < 0, ∀ t > t1. Vì vậy tập X(t) = ∅, ∀t > t1.
• 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 xr
được thay bởi biến xs 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 = t1. Tiếp tục xác định t2, 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∈[t1,t2] v.v…
III) Phương pháp đơn hình mở rộng cho thấy tập X(t 0) = ∅; tức là vẫn còn ẩn giả nhận
giá trị dương. Ở đây ta áp dụng phương pháp đã trình bày ở Phần II để giải bài toán mở
rộng cho đến khi nào tìm được phương án tối ưu của bài toán mở rộng, trong đó không còn
ẩn gia nữa, hoặc xác định rằng X(t) = ∅ ∀t.
2.2.2 Ví dụ:
Giải bài toán TƯTT chứa tham số sau đây:
Z( x ) = −2x 1 + 3x 2 + x 3 + 4x 4 → min
x 1 − 2 x 2 + x 3 − x 4 + x 5 =1− t
2 x 1 + 3x 2 − x 3 + 2 x 4 + x 6 = 2 + 3t
− x 1 + 2 x 2 + 3x 3 − 3x 4 + x7 = 3 + 2t
x j ≥ 0, j = 1,2,...,7
−2≤t≤2
Bài giải: Bảng đơn hình xuất phát với t0 = 0:
Bảng 6.6:
H ệ số hi gi x1 x2 x3 x4
ẩn cơ sở
t0 = 0 -2 3 1 4 x0
x5 0 1 -1 1 -2 1 -1 1
Lê Văn Phi 96
- Lyù thuyeát qui hoaïch tuyeán tính
x6 0 2 3 2 3 -1 2 2
x7 0 3 2 -1 2 3 -3 3
am+1,j 0 0 2 -3 -1 -4 0
Thực hiện hai phép biến đổi đơn hình, lần lượt thay x5, x6 bằng x1, x2, ta có phương án tối
ưu ứng với t0 = 0 cho ở Bảng 2.7:
Bảng 6.7:
H ệ số x5 x6 x3 x4
ẩn cơ sở
t0 = 0 pj qj -2 3 1 4 x0
x1 -2 1 3/7 3/7 2/7 1/7 1/7 1
x2 3 0 5/7 -2/7 1/7 -3/7 4/7 0
x7 0 4 1 1 0 4 -4 4
am+1,j -2 9/7 -12/7 -1/7 -18/7 -18/7 -2
Ta xác định
h 7 h
t −1 = max − i = max − , 0, − 4 = − 2 = 0 , t1 = 2, vì gi ≥ 0, ∀i
g >0
i
gi 3 g2
Như vậy, phương án x0 = (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ì t1= (-p2/q2) 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 x2 bởi x5, ta có Bảng 6.8. Phương án tối ưu mới x1
= (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 = -
p1/q1. Từ đây suy ra phương án x tối ưu trong khoảng [-2/3, 0]. Giá trị tối ưu tươg ứng là
φ (t) = -2 -3t.
Bảng 6.8
Hệ số x2 x6 x3 x4
ẩn cơ sở
t-2 = -2/3 pj qj -2 3 1 4 x0
x1 -2 1 3/2 3/2 1/2 -1/2 1 1
x5 0 0 -5/2 -7/2 -1/2 3/2 -2 0
x7 0 4 7/2 1/2 1/2 5/2 -2 4
am+1,j -2 -3 -6 -1 0 -6 0
Chọn hàng chuẩn là hàng 1, thay x1 bởi x3, 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 = h3/g3.
Bảng 6.9:
Hệ số ẩn x2 x6 x3 x4
c ơ sở
t-2 = -9/11 pj qj -2 3 1 4 x0
x3 1 -2 -3 -3 -1 -2 -2 0
x5 0 3 2 1 1 3 1 8/3
x7 0 9 11 8 3 5 3 5/3
am+1,j -2 -3 -6 -1 0 -6 5/11
Lê Văn Phi 97
- Lyù thuyeát qui hoaïch tuyeán tính
Do ở Bảng 2.9 các hệ số a3j ≥ 0, ∀j, nên x7(t) < 0 ∀t < -9/11. Suy ra X(t) = ∅ ∀t ∈[-2,
-9/11].
Kết luận: Phương án tối ưu của bài toán đã cho như sau:
• 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à x2 = (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à x1 = (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à x0 = (1+(3/7)t, (5/7)t, 0, 0, 0, 0, 4+t) ; giá trị tối ưu φ (t) =
-2 + (9/7)t.
Hình 6.2
φ (t) 1
4/7
5/11
–2 -1 –9/11 –2/3 0 1 2 t
– φ (t) = -2 -3t
φ (t) = -2
(9/7)t
φ (t) = -2 +
3t
φ (t) = -2 + (9/7)t.
-2
Rõ ràng φ (t) là các hàm lồi (ss. Hình 6.2).
*
* *
Lê Văn Phi 98
nguon tai.lieu . vn