Nghiệm tối ưu của bài toán gốc - Sự hội tụ của thu- 123docz.net

2.4 Sự hội tụ của thuật toán

2.4.2 Nghiệm tối ưu của bài toán gốc

Nhắc lại rằng, nếu ta biết được nghiệm tối ưu t¯của bài toán (M PT) thì, theo Mệnh đề 2.1, ta có thể nhận được nghiệm tối ưuxt¯của bài toán(M PG) bằng cách giải quy hoạch lồi

min n

f0(x) + 1

j=1

t¯jfj(x) p

x ∈ G o

(P2(¯t)).

Nghiệm tối ưu của bài toán (P2(¯t)) chính là nghiệm x¯t của (M PG). Tuy nhiên, nếu t¯chỉ là nghiệm tối ưu ε của bài toán (M PT) thì giá trị tối ưu ϕ(¯t) của bài toán (P2(¯t)) vẫn là giá trị tối ưu ε của bài toán (M PG), nhưng nghiệm tối ưu x¯t của bài toán (P2(¯t)) không nhất thiết là nghiệm tối ưu ε của bài toán (M PG).

Trong [12], các tác giả khẳng định rằng ta có thể xác định được nghiệm tối ưu ε của bài toán (M PG) bằng việc cải biên Bước 2 (Bước tính cận) của Thuật toán SM P. Cụ thể, thuật toán xác định nghiệm tối ưu ε của (M PG) như sau:

Thuật toán SM Pcải biên

♦ Bước 0: (Bước khởi tạo) (như Thuật toán SM P);

♦ Bước 1: (Chia nhánh) (như Thuật toán SM P);

♦ Bước 2: (Tính cận)

Với mỗi K ∈ L, tính cận dưới ϕ(K) bằng cách:

2.1. Xỏc định ˆt= (ˆt1,ˆt2,ã ã ã ,ˆtp) (Theo Cụng thức (2.17));

2.2. Xác định siêu phẳng Hˆt: Htˆ=

t ∈ Rp :

i=1

ti tˆi

= p o

2.3. Xác định các giao điểm s1ˆ

t,ã ã ã , spˆ

t của Htˆ với K;

2.4. Đặt ϕ(K) = min{ϕ(s1ˆt),ã ã ã , ϕ(spˆ

t)};

2.5. Đặt w(K) = ˆt;

2.6. Giải bài toán quy hoạch tuyến tính (P2(w(K))) tìm nghiệm tối ưu xw(K) ∈ G;

2.7. Nếu g(xw(K)) < ϕ thì

ϕ := g(xw(K)), x := xw(K);

♦ Bước 3: (Loại bỏ tập con) (như Thuật toán SM P);

♦ Bước 4: (Kiểm tra điều kiện dừng)

Nếu P = ∅ thì x¯ là nghiệm tối ưu ε của bài toán (M PG), ngược lại, Quay về Bước 1.

Lưu ý rằng giá trị tối ưu ϕ(w(K)) bằng giá trị g(xw(K)). Để người đọc tiện theo dõi, trong Thuật toán SM Pcải biên có trình bày chi tiết Bước 2.

Tuy nhiên, việc cải biên chỉ thực hiện từ Bước 2.6 đến Bước 2.7.

Định lý 2.3. Thuật toán SM Pcải biên tìm nghiệm tối ưu của bài toán (M PG) cũng hội tụ khi ε 6= 0.

Chứng minh. Theo chứng minh Định lý 2.2, ta có wh −→bt∗.

Gọi xwh ∈ G là nghiệm tối ưu của bài toán (P2(wh)), ta có:

xwh −→ x

bt∗.

Do đó,

ϕ(t∗) =g(xtˆ∗) = lim

h→+∞g(xwh) ≥ lim

h→+∞g(xh) = g(¯x).

Phần chứng minh còn lại lập luận hoàn toàn tương tự như chứng minh Định lý 2.2.

Kết luận: Chương này đã trình bày chi tiết thuật toán nhánh cận theo phân hoạch nón để giải bài toán tương đương (M PT) của bài toán quy hoạch tích lồi mở rộng (M PG). Cách xây dựng nón khởi tạo, cách chia nón, tính cận trên, cận dưới tại mỗi nhánh,... cũng được trình bày đầy đủ.

Trường hợp may mắn ta sẽ tìm được nghiệm tối ưu chính xác, còn thông thường, ta chỉ tìm được nghiệm tối ưu ε của bài toán (M PG). Sự hội tụ của thuật toán trong cả hai trường hợp cũng được chỉ rõ.

Chương 3

Thuật toán Heuristic giải bài toán quy hoạch tích tuyến tính

Chương này dành để trình bày thuật toán Heuristic do H.P. Benson và G.

M. Boger[4] đề xuất, để giải bài toán quy hoạch tích các hàm tuyến tính - một trường hợp đặc biệt của bài toán quy hoạch tích lồi.

Xét bài toán quy hoạch tích các hàm tuyến tính ming(x) =

j=1

fj(x) (M LP)

v.đ.k. x ∈ G,

trong đó G = {x ∈ Rn|Ax ≤ b}là đa diện, A là ma trận cấp m×n, b ∈ Rm, số nguyên p ≥ 2 và fj(x) = hcj, xi là các hàm tuyến tính, cj ∈ Rn, j = 1,2,ã ã ã , p. Ta vẫn giả thiết rằng với mỗi j ∈ {1,2,ã ã ã , p} thỡ fj(x) > 0 với mọi x ∈ G.

Thuật toán Heuristic giải bài toán (M LP) được xây dựng dựa trên mối quan hệ của bài toán này với bài toán quy hoạch đa mục tiêu tuyến tính tương ứng. Cơ sở lý thuyết của thuật toán được trình bày ở Mục 3.1. Mục 3.2 trình bày chi tiết thuật toán Heuristic tìm nghiệm tối ưu xấp xỉ của bài toán (M LP).

3.1 Cơ sở lý thuyết

3.1.1 Bài toán quy hoạch đa mục tiêu tuyến tính

Bài toán quy hoạch tuyến tính đa mục tiêu tương ứng với bài toán (M LP) là

Vmin Cx, v.đ.k. x ∈ G, (M OLP) trong đú, C là ma trận cấp pìn với cỏc hàng cj, j = 1,2,ã ã ã , p.

Điểm x0 là nghiệm hữu hiệu của bài toán(M OLP) nếux0 ∈ Gvà không tồn tại x ∈ G sao cho

Cx0 ≥ Cx và Cx0 6= Cx.

Tập tất cả các nghiệm hữu hiệu của bài toán (M OLP) được gọi là tập nghiệm hữu hiệu, kí hiệu là GE. Kí hiệu Gex là tập đỉnh của G.

Ta gọi

Y = {y ∈ Rp : y = Cx, x ∈ G}, (3.1) là tập ảnh của G qua ánh xạ C. Theo Mệnh đề 1.5, ta có Y ⊂ Rp là đa diện. Kí hiệu MinY là tập các điểm hữu hiệu của Y.

Kết quả sau đây là hiển nhiên.

Mệnh đề 3.1. Nếu x∗ ∈ GE thì y∗ = Cx∗ ∈ MinY.

Định lý dưới đây cho phép xác định được một nghiệm hữu hiệu của bài toán (M OLP) thông qua việc giải một bài toán quy hoạch tuyến tính.

Định lý 3.1. (Định lý vô hướng hóa)[9] Điểm x∗ ∈ G được gọi là nghiệm hữu hiệu của bài toán quy hoạch tuyến tính đa mục tiêu (M OLP) khi và chỉ khi tồn tại w ∈ Rp, w 0, sao cho x∗ là nghiệm tối ưu của bài toán

quy hoạch tuyến tính vô hướng.

Vmin hwTC, xi (LP(w))

v.đ.k. x ∈ G.

Chứng minh. (=⇒) Giả sử x∗ là nghiệm hữu hiệu của bài toán quy hoạch tuyến tính đa mục tiêu (M OLP). Khi đó, không tồn tại x ∈ G sao cho Cx∗ ≥ Cx và Cx∗ 6= Cx. Theo Mệnh đề 3.1, y∗ = Cx∗ ∈ MinY. Vì Y là tập lồi đa diện và C là ánh xạ tuyến tính nên ta có

A= Y −y∗

cũng là tập lồi đa diện. Theo định nghĩa, tập A không chứa bất kì một véc tơ v < 0.

Xét nón A0 sinh bởi A:

A0 = {ta : a ∈ A, t ≥0}.

Vì A không chứa véc tơ v < 0 và t ≥ 0 nên A0 cũng không chứa véc tơ v < 0. Đặt

B = {v ∈ Rp :

i=1

vi = −1, vi ≤ 0}.

Ta có tập A0 −B là tập lồi đóng và không chứa gốc O của không gian Rp. Theo Định lý tách tập lồi [10], tồn tại véc tơ w ∈ Rp\ {0} sao cho

hw, zi > hw,0i, ∀z ∈ (A0 −B), hay

hw, a−bi > 0, ∀a ∈ A0, b ∈ B. (3.2) Chọn a = 0, ta có

hw, bi < 0, ∀b ∈ B. (3.3)

Trong (3.3), lần lượt lấy cỏc vộc tơ bi = (0,0,ã ã ã ,0, −1

|{z}

,0,ã ã ã ,0) ∈ B, ta được wi > 0. Vậy w 0.

Ta sẽ chứng minh x∗ là nghiệm tối ưu của bài toán (LP(w)). Thật vậy, giả sử phản chứng rằng tồn tại x0 ∈ G sao cho

hwTC, x∗i > hwTC, x0i ⇒ hw, Cx∗i > hw, Cx0i ⇒ hw, Cx0 −Cx∗i < 0.

Vì Cx0−Cx∗ ∈ A nên véc tơ

at = t(Cx0−Cx∗) ∈ A0, ∀t ≥ 0.

Ta có

hw, ati = hw, t(Cx0−Cx∗)i = thw, Cx0 −Cx∗i → −∞khit →+∞.

Điều này mâu thuẫn với (3.2). Vậy x∗ là nghiệm tối ưu của bài toán (LP(w)).

(⇐=) Ngược lại, giả sử tồn tại w ∈ Rp, w 0sao cho x∗ là nghiệm của bài toán (LP(w)). Ta sẽ chứng minh rằng x∗ là nghiệm hữu hiệu của bài toán (M OLP). Thật vậy, giả sử phản chứng rằng x∗ không là nghiệm hữu hiệu của (M OLP), tức là tồn tại x0 ∈ G sao cho

Cx∗ > Cx0 và Cx∗ 6= Cx0. Vì w 0 và có giả thiết Cx > 0, ∀x ∈ G nên

hw, Cx∗i > hw, Cx0i ⇒ hwTC, x∗i > hwTC, x0i.

Điều này mâu thuẫn với giả thiết x∗ là nghiệm tối ưu của bài toán (LP(w)).

Do đó, x∗ là nghiệm hữu hiệu của bài toán (M OLP).

Sau đây là các hệ quả trực tiếp của Định lý vô hướng hóa.

Hệ quả 3.1. Cho một diện khác rỗng F ⊂ G. Nếu điểm x0 ∈ GE và x0 ∈ riF thì F ⊂ GE.

Hệ quả 3.2. Nếu G là đa diện thì GE khác rỗng.

Cấu trúc tập nghiệm của bài toán quy hoạch tuyến tính đa mục tiêu được mô tả ở định lý sau.

Định lý 3.2. (Cấu trúc tập nghiệm) Tập nghiệm hữu hiệu GE của bài toán (M OLP) là hợp của một số diện đóng của G và là tập liên thông đường gấp khúc.

Mặc dù tập nghiệm hữu hiệu GE của bài toán (M OLP) là tập liên thông đường gấp khúc, nhưng nói chung đó là tập không lồi và có cấu trúc phức tạp. Đây là nguyên nhân làm cho việc xác định được toàn bộ tập GE hoặc tập đỉnh hữu hiệu GE ∩Gex là khó khăn. Thời gian tính toán để xác định toàn bộ tập GE tăng rất nhanh khi số biến n, số hàm mục tiêu p, và số ràng buộc m tăng (xem [6]).

Ví dụ 3.1. Giả sử C =



 1 0 0 1



 và tập chấp nhận được G được cho như hình vẽ dưới đây.

Theo định nghĩa, x0 ∈ GE nếu

@x ∈ G sao cho Cx0 ≥Cx, Cx0 6= Cx. (3.4) Trong trường hợp này, (3.4) tương đương với

@x ∈ G sao cho x0 ≥ x, x0 6= x, tức

(x0 −R2+)∩G = {x0}.

Dễ thấy tập nghiệm hữu hiệu là phần được tô đậm trên hình vẽ. Tập này là liên thông đường gấp khúc, nhưng không lồi.

3.1.2 Mối quan hệ giữa hai bài toán (M LP) và (M OLP)

Mối liên hệ giữa bài toán quy hoạch tích tuyến tính (M LP) và bài toán quy hoạch đa mục tiêu tuyến tính (M OLP) được thể hiện qua các Mệnh đề sau.

Mệnh đề 3.2. Bất kì nghiệm tối ưu nào của bài toán (M LP) cũng đều thuộc tập nghiệm hữu hiệu GE của bài toán (M OLP).

Chứng minh. Giả sử phản chứng rằng điểm x0 ∈ Glà nghiệm tối ưu của bài toán (M LP) nhưng không phải là nghiệm hữu hiệu của bài toán (M OLP).

Khi đó, tồn tại x ∈ G sao cho

Cx≤ Cx0 và Cx6= Cx0. Nghĩa là

hcj, xi ≤ hcj, x0i, ∀j = 1,2,ã ã ã , p,

và tồn tại ớt nhất một chỉ số j0 ∈ {1,2,ã ã ã , p} sao cho hcj0, xi < hcj0, x0i.

Vì ta giả thiết rằng fj(x) =hcj, xi > 0 với mọi x ∈ G, nên

j=1

fj(x) <

j=1

fj(x0) ⇒g(x) < g(x0).

Biểu thức này chứng tỏx0 không phải là nghiệm tối ưu của bài toán(M LP).

Điều mâu thuẫn này chứng tỏ Mệnh đề là đúng.

Kí hiệu

GE,ex = GE ∩Gex

là tập điểm cực biên hữu hiệu của bài toán (M OLP). Ta có kết quả sau.

Bổ đề 3.1. Bài toán (M LP) có ít nhất một nghiệm tối ưu thuộc GE,ex. Chứng minh. Theo [5], hàm g(x) =Qp

j=1hcj, xi là tựa lõm. Theo Mệnh đề 1.4, bài toán (M LP) đạt nghiệm tối ưu tại ít nhất một điểm cực biên của G, tức nghiệm thuộc tập Gex. Kết hợp điều này với Mệnh đề 3.1, bài toán (M LP) có ít nhất một nghiệm thuộc GE,ex.

Bổ đề 3.1 khẳng định nghiệm tối ưu của bài toán (M LP) phải thuộc tập GE,ex. Vì GE,ex là hữu hạn, nên về mặt lý thuyết, ta có thể so sánh giá trị hàm mục tiêu tại các điểm thuộc GE,ex để tìm nghiệm của bài toán (M LP). Tuy nhiên, khi số ràng buộc xác định đa diện tăng lên thì số đỉnh cũng tăng theo cấp số mũ, vì vậy, cách làm này không hữu dụng trong thực tế. Thuật toán Heuristic trình bày trong chương này sẽ đi tìm nghiệm của bài toán (M LP) mà không cần duyệt toàn bộ tập GE,ex.

Kí hiệu

W = {w ∈ Rp|hw, ei ≤ M, w ≥e},

trong đú e = (1,1,ã ã ã ,1)T ∈ Rp, M > 0. Hỡnh vẽ 3.1 minh họa tập W trong trường hợp p= 2.

Với M có giá trị đủ lớn, ta có kết quả sau.

Định lý 3.3. Điểm x0 là nghiệm hữu hiệu của bài toán (M OLP) khi và chỉ khi tồn tại w = w0 ∈ W sao cho x0 là nghiệm tối ưu của bài toán

min{hwTC, xi : Ax ≤ b}. (LP(w)) Kí hiệu Gw là tập nghiệm tối ưu của bài toán (LP(w)). Với mỗiw ∈ W, tập nghiệm tối ưu Gw của bài toán (LP(w)) là một diện của tập chấp nhận được G. Như vậy, Gw cũng là tập lồi đa diện. Vì vậy, ta có thể biểu diễn GE bởi tập

GE = ∪{Gw|w ∈ W}.

Với mỗi w ∈ W cho trước, thuật toán Heuristic sẽ tìm diện hữu hiệu Gw,

từ đó tìm nghiệm tối ưu xấp xỉ của bài toán min

j=1

hcj, xi (LP0(w))

v.đ.k. x ∈ Gw với mỗi diện Gw tìm được.

Nghiệm tối ưu xấp xỉ ở đây được hiểu theo nghĩa: ta sẽ xấp xỉ hàm mục tiêu bởi một hàm tuyến tính. Bằng cách này, ta chỉ việc giải một bài toán quy hoạch tuyến tính thông thường để tìm nghiệm tối ưu của bài toán (LP0(w)). Cơ sở của việc xấp xỉ hàm mục tiêu là dựa trên khai triển Taylor cấp 1 của hàm.

Xét hàm số f : Rn −→ R khả vi liên tục tại lân cận nào đó của điểm x0 ∈ Rn. Khi đó, với p ∈ Rn và p đủ nhỏ, ta có khai triển

f(x0 +p) =f(x0) +h∇f(x0), pi+o(kpk),

trong đó kpk là kí hiệu chuẩn của véc tơ p, o(kpk) là một vô cùng bé bậc cao hơn kpk khi kpk → 0. Khai triển này được gọi là khai triển Taylor cấp 1 của hàm f tại x0. Tổng

f(x0) + h∇f(x0), pi

được gọi là xấp xỉ Taylor cấp 1 của hàm f tại x0, và ta viết f(x0 +p) ≈ f(x0) +h∇f(x0), pi.

Cụ thể, xét hàm

g(x) =

j=1

hcj, xi, với x ∈ Rn, cj ∈ Rn, j = 1,2,ã ã ã , p. Ta cú

∂g(x)

∂xi =

j=1

h Y

i6=j

hci, xii

cji. (3.5)

Do đó, nếu đặt ai = ∂g(x)

∂xi và kớ hiệu a = ∇g(x) = (a1,ã ã ã , ap) ∈ Rp thỡ ta có công thức xấp xỉ của hàm g(x) tại x0 = 0 là

g(x) ≈ ha, xi.

Kí hiệu

Y≥ = {y ∈ Rp|y ≥y,ˆ với yˆ∈ Y},

với Y là tập ảnh của G và được xác định như công thức (3.1). Dễ thấy Y≥ = Y +Rp+.

Hình 3.2 minh họa một tập Y≥ trong trường hợp p= 2.

Cho w = w0 ∈ W và y ∈ Y≥. Xét bài toán

minhwTC, xi (P(y))

v.đ.k. Cx≤ y, Ax ≤b.

Dễ thấy, tập chấp nhận được của bài toán (P) là Y ∩(y −Rp+), y ∈ Y≥.

Hình 3.3 minh họa tập chấp nhận được của một bài toán (P(y)) trong trường hợp p= 2.

Sau đây là một số kết quả mô tả mối liên hệ giữa bài toán (P(y)) và bài toán quy hoạch tuyến tính đa mục tiêu (M OLP).

Định lý 3.4. Giả sử x0 ∈ Rn và đặt y0 = Cx0. Khi đó x0 là nghiệm hữu hiệu của bài toán (M OLP) khi và chỉ khi x0 là một nghiệm tối ưu của bài toán (P(y)) với y = y0 và với mỗi w ∈ W.

Định lý 3.5. Cho y ∈ Y≥ và w ∈ W. Khi đó, bài toán (P(y)) có ít nhất một nghiệm tối ưu và bất kì nghiệm tối ưu nào của bài toán (P(y)) đều là nghiệm hữu hiệu của bài toán (M OLP).

Định lý 3.6. Giả sử w = w0 ∈ W và y = y0 = Cx0, trong đó x0 là nghiệm hữu hiệu của bài toán (M OLP). Kí hiệu (u0T, z0T) là một nghiệm tối ưu

của bài toán quy hoạch tuyến tính đối ngẫu của bài toán (P(y)), trong đó u0 là biến đối ngẫu tương ứng với ràng buộc Cx ≤ y0. Đặt

w0 = u0 + w0 và v0 = ( ¯w0)TCx0.

Khi đó, x0 thuộc diện hữu hiệu Gw¯0 ⊂ G và Gw¯0 có thể được biểu diễn dưới dạng

Gw¯0 = {x ∈ G|( ¯w0)TCx = v0}.

Chứng minh. Để chứng minh định lý này, ta chứng minh rằng với w = ¯w0 thì x0 là một nghiệm tối ưu của bài toán (LP(w)).

Xét bài toán (P(y)) với w = w0 ∈ W và y = y0 = Cx0, trong đó x0 là nghiệm hữu hiệu của bài toán quy hoạch tuyến tính đa mục tiêu (M OLP).

Bài toán đối ngẫu với bài toán (P(y)) là

max−hy0, ui − hb, zi (DP) v.đ.k. −CTu−ATz = CTw0

u, z ≥ 0.

Theo Định lý 3.4, x0 là nghiệm tối ưu của bài toán (P(y)) khi w = w0 và y = y0. Do (u0T, z0T) là nghiệm tối ưu của bài toán (DP) nên theo Định lý đối ngẫu (xem [1]), giá trị tối ưu của bài toán (P(y)) và bài toán (DP) bằng nhau

h(w0)TC, x0i = −hy0, u0i − hb, z0i

⇔ h(w0)TC, x0i = −hCx0, u0i − hb, z0i

⇔ h(w0)TC, x0i +h(u0)TC, x0i = −hb, z0i

⇔ h( ¯w0)TC, x0i = −hb, z0i. (3.6)

Với w = ¯w0, bài toán đối ngẫu của bài toán (LP(w)) có thể viết dưới dạng

max−hb, zi (DLP(w))

v.đ.k. −ATz = CTw¯0, z ≥0.

Chọnz là một phương án chấp nhận được bất kì của bài toán (DLP(w)).

Khi đó, (u0T, zT) là phương án chấp nhận được của bài toán (DP). Do (u0T, z0T) là nghiệm tối ưu của bài toán (DP) nên ta có

−hy0, u0i − hb, z0i ≥ −hy0, u0i − hb, zi, tức là

−hb, z0i ≥ −hb, zi. (3.7)

Vì (u0T, v0T) là một nghiệm tối ưu của bài toán (DP) nên z0 là nghiệm chấp nhận được của bài toán (DLP(w)). Vì ta chọn z là một phương án chấp nhận được bất kì của bài toán (DLP(w)) nên từ biểu thức (3.7) suy ra z0 là nghiệm tối ưu của bài toán (DLP(w)).

Mặt khác, theo giả thiết x0 là một nghiệm hữu hiệu của bài toán (M OLP), nên với w = ¯w0 thìx0 là một phương án chấp nhận được của bài toán (LP(w)). Từ biểu thức (3.6) ta có x0 là nghiệm tối ưu của bài toán (LP(w)).

Chú ý rằng, trong Định lý 3.6, với bất kì t > 0, Gtw¯0 = Gw¯0. Do đó, nếu

w0 ∈/ W thì tồn tại t ∈ (0,1) sao cho tw¯0 ∈ W và Gtw¯0 = Gw¯0. Vì vậy, khi

w0 ∈/ W thì ta có thể chọn một giá trị w¯¯0 ∈ W sao cho Gw¯0 = Gw¯¯0. Như vậy, không mất tính tổng quát, trong Định lý 3.6, ta luôn có thể giả sử rằng w¯0 ∈ W.

Theo Định lý 3.5, với mỗi y ∈ Y≥, ta được một diện hữu hiệu của bài toán (M OLP). Như vậy, bằng cách thay đổi điểm y ∈ Y≥ và giải bài toán quy hoạch tuyến tính (P(y)), ta có thể nhận được các diện hữu hiệu khác nhau. Sau đây là cách xác định các điểm y ∈ Y≥ dựa vào hai điểm đặc biệt là yI và yAI.

Với mỗi j ∈ {1,2,ã ã ã , p}, kớ hiệu yjI là giỏ trị tối ưu của bài toỏn

minyj, v.đ.k. y ∈ Y, (Pm(j)) và yAIj là giá trị tối ưu của bài toán

maxyj, v.đ.k. y ∈ Y. (PM(j)) Lưu ý rằng, với mỗi j ∈ {1,ã ã ã , p}, giỏ trị tối ưu yjI của bài toỏn (Pm(j)) cũng chính là giá trị tối ưu của bài toán quy hoạch tuyến tính

minhcj, xi, v.đ.k. x ∈ G,

tương tự, giá trị tối ưu yjAI của bài toán (PM(j)) cũng chính là giá trị tối ưu của bài toán quy hoạch tuyến tính

maxhcj, xi, v.đ.k. x ∈ G.

Đặt

yI = (y1I,ã ã ã , ypI), yAI = (y1AI,ã ã ã , ypAI).

Như thường lệ, điểm yI được gọi làđiểm lý tưởng của tập Y. NếuyI ∈ Y thì ta có tập điểm hữu hiệu YE = {yI}. Vì vậy, ta xét với trường hợp yI ∈/ Y. Xem minh họa ở Hình 3.4.

Tương tự, nói chung yAI không thuộc tập ảnh Y. Từ hai điểm này, ta có thể xác định được một dãy S điểm thuộc Y≥ nằm trong đoạn thẳng [yI, yAI] theo công thức

yi = yAI + i

S(y∗ −yAI), i = 0,1,ã ã ã , S, trong đó

y∗ = yAI +α∗(yI −yAI), với α∗ là giá trị tối ưu của bài toán

maxα

v.đ.k. Cx ≤yAI +α(yI −yAI) Ax≤ b, α ≥ 0.

Hình 3.5 minh họa điểm y∗ và dãy điểm y1, y2, y3 ∈ Y≥ với p= 2.

3.2 Chi tiết thuật toán

Thuật toán Heuristic kí hiệu là Thuật toán HES giải bài toán quy hoạch tích tuyến tính gồm có hai pha, cụ thể như sau:

Thuật toán HES.

Pha I (Khởi tạo) Gồm có 5 bước:

Bước 1: Tìm các điểm yI và yAI của tập ảnh Y;

Bước 2: Tìm một nghiệm tối ưu [x∗T, α∗] ∈ Rn+1 của bài toán quy hoạch tuyến tính

maxα

v.đ.k. Cx≤ yAI +α(yI −yAI) Ax ≤ b

α ≥ 0.

và đặt

y∗ = yAI +α∗(yI −yAI);

Bước 3: Chọn số nguyờn dương S, với mỗi i = 0,1,ã ã ã , S, đặt yi = yAI + i

S(y∗ −yAI);

Bước 4: Chọn số nguyên dương N sao cho 1≤ N ≤ M −p+ 1 và chọn w0 = e ∈ Rp. Với mỗi j = 1,2,ã ã ã , p, wj được xỏc định như sau:

wji =







1, nếu i 6= j, N, nếu i = j;

Bước 5: Gán U B := +∞, i := 0, j := 0;

Pha II (Thuật toán tìm điểm hữu hiệu) Gồm 6 bước

Bước 1: Đặt y = yi, w = wj và tìm một nghiệm tối ưu x¯ij bất kì của bài toán (P(y)) :

minhwTC, xi (P(y))

v.đ.k. Cx≤ y, Ax ≤b;

Bước 2: Đặt y = Cx¯ij, w = wj và tìm một nghiệm tối ưu [(uij)T,(zij)T] của bài toán đối ngẫu (DP) :

max−hy, ui − hb, zi (DP)

v.đ.k.−CTu−ATz = CTw u, z ≥ 0,

trong đó uij là biến đối ngẫu tương ứng với ràng buộc Cx≤ y của bài toán (P(y));

Bước 3: Đặt w¯ij = uij +wj;

If w¯ij = λw¯i0j0 với λ >0, i0 ≤ i, j0 ≤ j sao cho (i0, j0) 6= (i, j), Then Chuyển Bước 6;

Bước 4: Đặt vij = ( ¯wij)TCx¯ij. Với mỗi h = 1,2,ã ã ã , n, tớnh giỏ trị ah theo biểu thức

ah =

k=1

h Y

t6=k

hct,x¯ijii [ckh],

và tìm một nghiệm tối ưu xij của bài toán minha, xi

v.đ.k. ( ¯wij)TCx = vij Ax ≤ b;

Bước 5: If

k=1

hck, xiji ≥ U B Then Chuyển Bước 6 Else Đặt

x = xij, U B =

k=1

hck,xi,¯ Chuyển Bước 6;

Bước 6: Đặt j := j + 1;

If j ≤ p Then Quay về Bước 1 Else Đặt i := i+ 1, j = 0;

If i ≤S Then Quay về Bước 1

Else Dừng thuật toán: lấy x¯ ∈ GE,ex và coi đó là nghiệm của bài toán quy hoạch tích tuyến tính (M LP).

Sau đây là một ví dụ đơn giản để minh họa các bước của thuật toán.

Ví dụ 3.2. Giải bài toán

ming(x) = (x1 +x2).x2, với tập chấp nhận được G là











1≤ x1 ≤ 4 x2 ≥ 1

−x1 + x2 ≤2.

Giải: Ta có

A =







−1 0

1 0

0 −1

−1 1







, b=







−1 4

−1 2







, C =



 1 1 0 1



.

Đặt f1(x) = x1 +x2, f2(x) = x2. Pha 1:

Bước 1. Giải bài toán

miny1

v.đ.k. fj(x) = yj, j = 1,2, Ax ≤ b,

tìm được nghiệm tối ưu (x1, x2, y1, y2) = (1,1,2,1).

Giải bài toán

miny2

v.đ.k. fj(x) = yj, j = 1,2,