zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

Chương 4: Các phương pháp hữu hạn giải quyết bài toán qui hoạch tuyến tính

Chia sẻ: Lê Văn Phi | Ngày: | Loại File: DOC | Số trang:53

Báo xấu

537
lượt xem 245
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tham khảo tài liệu 'chương 4: các phương pháp hữu hạn giải quyết bài toán qui hoạch tuyến tính', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Chương 4: Các phương pháp hữu hạn giải quyết bài toán qui hoạch tuyến tính

Lý thuyêt qui hoach tuyên tinh ́ ̣ ́ ́ CHƯƠNG IV: CÁC PHƯƠNG PHÁP HỮU HẠN GIẢI BÀI TOÁN QUI HOẠCH TUYẾN TÍNH §1 Phương pháp đơn hình 1.1 Bài toán QHTT dạng chuẩn Để 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ố n Z = Z(x) = ∑ c j x j j =1 (1.1) trên tập hợp các vec tơ x thỏa mãn các điều kiện: n ∑ a ij = bi ,i = 1, 2,..., m (1.2) j =1 x j ≥ 0, j = 1, 2,..., n (1.3) Trong đó cj, aij, bi, i = 1,2,…,m và j = 1,2,…,n là những số thực cho trước. Bài toán trên có thể viết dưới dạng ma trận: Tìm x* làm cực tiểu hàm số Z = 〈c, x〉 dưới các điều kiện Ax = b (1.4) x≥ 0 (1.5) Chú ý: Bài toán QHTT dạng chuẩn (1.1) – (1.3) chỉ khác bài toán QHTT dạng cơ bản ở chỗ các ràng buộc (1.2) cho ở dạng phương trình. Trong thực tế sản xuất, kinh doanh có nhiều bài toán có thể đưa về bài toán QHTT với nhiều dạng khác nhau. Bằng các phép biến đổi tương đương như trình bày trong chương III, phần 3.2, người ta có thể đưa về bài toán ở dạng chuẩn. n Đặt X = {x ∈ R / ∑ a ij x j = bi .i = 1, 2,..., m; x j ≥ 0, j = 1, 2,.., n} (1.6) n j =1 Hay cũng vậy X = {x∈Rn/ 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 Lê Văn Phi, Khoa Toan – Thông kê, Đai hoc Kinh tế Tp. HCM ́ ́ ̣ ̣ 76
Lý thuyêt qui hoach tuyên tinh ́ ̣ ́ ́ đ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 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. 1.2 Lý thuyết phương pháp đơn hình Để 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 X = {x ∈ R n / A i. , x = bi ,i = 1, 2,..., m; e j , x ≥ 0, j = 1, 2,..., n} (1.7) Trong đó Ai. là các vectơ hàng của ma trận A; ej là vectơ đơn vị thứ j của không gian tuyến tính Rn, i = 1,2,…, m; j = 1,2,…,n. Không làm mất tính tổng quát, có thể giả thiết rằng hạng của A, r[A] = m7 và m < n8). Đồng thời bài toán QHTT chỉ có ý nghĩa, nếu ít nhất có một cj ≠ 0. Như vậy tập X có dạng như tập M ở phần §5 chương I, tức là cho bởi hệ (5.1), (5.2). Vậy, nếu X ≠ ∅ thì đó là một tập lồi đa diện. Theo định lý 5.5, nếu hệ ràng buộc xác định X có hạng bằg n thi một điểm x0∈X là điểm cực biên khi và chỉ khi nó thỏa mãn chặt n ràng buộc độc lập tuyến tính. Theo tính chất TC3 của bài toán QHTT, người ta chỉ cần khảo sát các điểm cực biên của miền chấp nhận được tương ứng. Sau đây chúng ta sẽ khảo sát đặt trưng đại số của các điểm cực biên ứng với bài toán (1.1) – (1.3). Đlí 1.1: Giả sử X ≠ ∅ và x0∈X, A.j là các vectơ cột của ma trận A, j = 1,2, …,n. Để x0 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 xj > 0 là độc lập tuyến tính. Chứng minh: Do hệ ràng buộc xác định X (s.s. (1.7)) có chứa n vectơ đơn vị ej, nên hạng của hệ đó bằng n. Vì vậy, nếu x0 là điểm cực biên thì phải 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 điều kiện không âm thì đó là lời giải tối ưu. Nếu lời giải này khôg thỏa mãn (1.3) thì bài toán QHTT không có lời giải. Trong cả hai trường hợp việc giải bài toán QHTT không còn có ý nghĩa nữa. Lê Văn Phi, Khoa Toan – Thông kê, Đai hoc Kinh tế Tp. HCM ́ ́ ̣ ̣ 77
Lý thuyêt qui hoach tuyên tinh ́ ̣ ́ ́ 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ử x j > 0, j = 1, 2,...., k; x j = 0, j = k + 1,..., n . Ở bài toán QHTT dạng 0 0 chuẩn tất cả các ràng buộc đều là chặt. Vì vậy có thể giả thiết rằng x 0 là lời giải duy nhất của hệ phương trình vuông không suy biến sau đây:  A.i , x = bi ,i = 1, 2,..., k    e j , x = 0, j = k + 1,.., n  Hay cũng vậy  ∑ a x = b ,i = 1, 2,..., k n  j=1 ij j i  (1.8)  x j = 0, j = k + 1,.., n  Thay n-k phương trình cuối vào k phương trình đầu, ta có hệ tương đương: k ∑ a ij x j = bi ,i = 1, 2,..., k (1.9) j =1 Do x0 là lời giải duy nhất của hệ (1.8), nên x 0 = (x1 , x 0 ,..., x 0 ) cũng là lời 0 2 k giải duy nhất của hệ (1.9). Suy ra các vectơ cột rút gọn  a1 j    A. j =  ...  , j = 1,2,…,k (1.10) a   kj  là độc lập tuyến tính. Từ đây cũng dễ thấy rằng các vectơ đầy đủ A.j cũng độc lập tuyến tính (bài tậ ). Ngược lại, nếu x0∈ X và x j > 0, j = 1, 2,...., k; 0 và các A.j tương ứng độc lập tuyến tính. Khi đó theo giả thiết k ≤ m. Xét trường hợp k = m. Khi ấy các lập nên một cơ sở của Rm. Dễ thấy rằng các A. j ở (1.8) cũng độc lập tuyến tính. Do đó x 0 = (x1 , x 0 ,..., x 0 ) là lời giải 0 2 k duy nhất của hệ phương trình vuông không suy biến (1.9) và vectơ mở rộng x 0 = (x1 ,..., x 0 ,0,...,0) là lời giải duy nhất của hệ (1.8). Điều này 0 k chứng tỏ rằng các vectơ ràng buộc, A.j, j = 1,…,k và ej, j = k+1,…,n, trong (1.6) là độc lập tuyến tính. Do đó x0 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 x j = 0 để tạo thành 0 một cơ sở của Rm. Sau đó bằng lý luận tương tự cũng có thể chứng tỏ rằng x0 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 phần dương không thể vượt quá m = r[A]. Suy ra, một vectơ có nhiều hơn m thành phần dương không thể là điểm cực biên của X. Do đó, để kiểm Lê Văn Phi, Khoa Toan – Thông kê, Đai hoc Kinh tế Tp. HCM ́ ́ ̣ ̣ 78
Lý thuyêt qui hoach tuyên tinh ́ ̣ ́ ́ tra xem một điểm x thuộc X có phải là điểm cực biên hay không phải kiểm tra hai điều kiện: 1) số thành phần dương không vượt quá m; 2) các vectơ A.j ứng với các thành phần dương là độc lập tuyến tính. Đn 1.1: Điểm cực biên x0 của X được coi là không thoái hóa (không suy biến) nếu số thành phần dương của nó đúng bằng m = r[A]. Nếu số thành phần dương nhỏ hơn m thì x0 được gọi là thoái hóa (suy biến). Bây giờ, cho x0 là điểm cực biên của X bất kỳ và có k thành phần dương. Nếu k = m thì x0 là không thoái hóa. Theo định lý 1.1, các vecơ ứng với các thành phần dương của x0 là độc lập tuyến tính. Do đó chúng lập thành một cơ sở của Rm, chúng lập nên một ma trận cơ sở B. Do x0 cũng là lời giải của hệ phương trình tuyến tính Ax = b, nên x0 còn gọi là một lời giải cơ sở. Khi k < m, tức x0 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ì x0 có n-k thành phần bằng 0, nên  n−k  có Cn − k =  m −k  khả năng bổ sung như vậy. Suy ra, ứng với một điểm m − k cực biên thoái hóa có thể có nhiều ma trận cơ sở. Chúng chỉ phân biệt nhau ở những cột ứng với các thành phần bằng 0 của điểm cực biên tương ứng. Sau đây sẽ trình bày phần lý tuyết làm cơ sở cho các bước của thuật toán đơn hình giải bài toán QHTT dạng chuẩn. Cho x* là điểm cực biên bất kỳ của tập chấp nhận được X. Giả sử x* không thoái hóa 1. Ký hiệu B là ma trận cơ sở ứng với x* và giả sử B = [A.B1, A.B2,…, A.Bm] (1.11) Khi đó có thể tách A thành hai ma trận B và R: A = [B, R], với R bao gồm những cột của A không nằm trong cơ sở. Tương tự như vậy có thể tách x thành xB và xR, với xB là vectơ gồm các biến xBi ứng với các vectơ cơ sở A.Bi (gọi tắt là biến cơ sở) và xR là vectơ ứng với các xj mà A.j không nằm 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 Toan – Thông kê, Đai hoc Kinh tế Tp. HCM ́ ́ ̣ ̣ 79
Lý thuyêt qui hoach tuyên tinh ́ ̣ ́ ́ trong cơ sở (gọi tắt là biến phi cơ sở). Đặt J = {j/ xj 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:  xB  (B R)   = b  xR  Hay, cũng vậy BxB + RxR = b (1.12) Do B là ma trận cơ sở nên nó không suy biến. Vì vậy tồn tại B-1. Nhân hai vế ở (1.12) về bê trái với B-1 ta có phương trình (B-1B)xB + (B-1R)xR = (B-1b) (1.13) Vì (B-1B) = E (ma trận đơn vị) nên (1.11) tương đương với xB + (B-1R)xR = (B-1b) Hay x Bi + ∑ yij x j = yi 0 , i = 1,2,…,m (1.14) j∈J −1 −1 Trong đó yij = A Bi. , A. j , yio = A Bi. , b , và A −1 là vectơ hàng i của B-1, i = Bi. 1,2,…,m; j∈ J.2 Hệ (1.14) gọi là dạng chính tắc của hệ phương trình xuất phát Ax = b ứng với cơ sở B. Như vậy, nếu x* là không thoái hóa thì hệ (1.14) là hệ duy nhất. Khi x* thoái hóa thì ứng với nó có nhiều ma trận cơ sở B nên cũng có nhiều dạng chính tắc (1.12). Từ dạng này suy ra x Bi = yi 0 − ∑ yij x j , i = 1,2,…,m (1.15) j∈J Đối với x* thì x j = 0 , j∈J nên x * = yi 0 > 0, i = 1,2,…,m. Giá trị hàm mục * Bi tiêu ứng với x* bằng n m m Z* = ∑ c j x j = ∑ c Bi x Bi + ∑ c j x j = ∑ c Bi yi0 * * * j =1 i =1 j∈J (1.16) i =1 2 Dễ thấy rằng các hệ số yij và yi0 , 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. B1,….,A. Bm}, Lê Văn Phi, Khoa Toan – Thông kê, Đai hoc Kinh tế Tp. HCM ́ ́ ̣ ̣ 80
Lý thuyêt qui hoach tuyên tinh ́ ̣ ́ ́ 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 n m Z = ∑ c j x j = ∑ c Bi (yi 0 − ∑ yij x j ) + ∑ c j x j j =1 i =1 j∈J j∈J m m (1.17) = ∑ c Bi yi0 − ∑ ∑ (c Bi yij − c j )x j i =1 j∈J i =1 Đặt m m y m +1,0 = ∑ c Bi yi 0 = ∑ c Bi A −1 , b = c B , B−1b Bi i =1 i =1 ( ) m m y m +1, j = ∑ (c Bi yij − c j ) = ∑ c Bi A Bi. , A. j − c j −1 (1.18) i =1 i =1 y m +1, j , = c B , B−1A. j − c j , j∈ J Khi ấy giá trị hàm mục tiêu Z trở thành Z = y m +1,0 − ∑ y m +1, j x j j∈J Hay cũng vậy Z + ∑ y m +1, j x j = y m +1,0 (1.19) j∈J Giá trị ym+1,Rj được gọi là hệ số đặc trưng ứng với biến phi cơ sở xRj, j∈ J. Như vậy, với x = x* thì Z* = ym+1,0 Bổ sung (1.17) vào hệ (1.12) ta được dạng chính tắc mở rộng của bài toán QHTT x Bi + ∑ yij x j = yi 0 , i = 1,2,…,m j∈J Z + ∑ y m +1, j x j = y m +1,0 (1.20) j∈J Lê Văn Phi, Khoa Toan – Thông kê, Đai hoc Kinh tế Tp. HCM ́ ́ ̣ ̣ 81
Lý thuyêt qui hoach tuyên tinh ́ ̣ ́ ́ Hệ (1.20) tương đương hoàn toàn với hệ (1.4). Nếu yio ≥ 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ó x j = 0, j ∈ J và do đó x * = yi 0 ≥ 0,i = 1, 2,..., m ; Z* = * Bi ym+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: ym+1,j ≤ 0. Khi ấy, vì ∀x∈X: xj ≥ 0, j∈J, nên theo (1.20), Z = Z(x) ≥ ym+1,0 = Z* = Z(x*). Suy ra x* là lời giải tối ưu và Zmin = Z*. • Trường hợp 2: ∃ Rl, 1 ≤ l≤ l, để cho ym+1,l > 0 và ∀i, i = 1,2,…,m: yi,l ≤ 0. Khi ấy chọn x(λ), 0 ≤ λ, như sau: xl(λ) = λ, xj(λ) = 0, j ≠ l, j ∈J Từ (1.20) suy ra xBi(λ) = yi0 – yil.xl = yi0 – yil.λ ≥ 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(λ)] = ym+1,0 – ym+1,l.xl = ym+1,0 – ym+1,l.λ (1.22) Vì theo giả thiết ym+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ị Zmin 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 ym+1,l > 0 và ∃ k, 1≤ k ≤ m, ykl > 0. Khi ấy tương tự như (1.21) ứng với biến cơ sở xBk(λ) yk 0 = yk0 – ykl.λ. Để cho x(λ)∈X thì xBk(λ) ≥ 0. Tức là λ ≤ . Suy luận y kl tương tự, ta cũng thấy rằng để cho x(λ)∈X thì y λ ≤ i0 , với yil > 0 3) yil 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ì 3 Dễ thấy rằng ứng với các yil ≤ 0 điều kiện xBi(λ)∈X mặt nhiên thỏa mãn ∀λ ≥ 0. Lê Văn Phi, Khoa Toan – Thông kê, Đai hoc Kinh tế Tp. HCM ́ ́ ̣ ̣ 82
Lý thuyêt qui hoach tuyên tinh ́ ̣ ́ ́ yi 0 0 ≤ λ ≤ min i,yil >0 y il Khi ấy giá trị Z[x(λ)] cũng tính theo công thức (1.22) và Z(λ) < ym+1,0 = Z(x0), nếu λ > 0. Tuy nhiên để cho Z giảm nhiều nhất người ta chọn yi 0 λ = λ 0 = min (1.23) i,yil >0 y il Không giảm tính tổng quát, giả sử yi 0 y k 0 λ 0 = min = (1.24) i,yil >0 y y kl il Dễ thấy rằng x(λ 0) cũng là điểm cực biên của X. Thật vậy, trước hết đối với biến xBk: xBk(λ 0) = yk0 – ykl.λ 0 = yk0 – ykl.(yk0/ykl) = 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], ykl > 0 nên có thể thay thế vectơ A.Bk bởi vectơ A.l để có một cơ sở mới; đó là B’ = [A.B1, …, A.B(k-1), A.l , A.B(k+1),…, A.Bm]. Tức là biến xBk chuyển thành biến phi cơ sở với giá trị bằng 0, còn biến xl sẽ là biến cơ sở với giá trị λ 0. Giá trị các biến cơ sở xBi, i = 1,2,…,m, còn lại được tính như sau: xBi(λ 0) = yi0 – yil.xl = yi0 – yil.λ 0 = yi0 – yil(yk0/ykl) ≥ 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 ứng với các biến dương là độc lập tuyến tính (chúng là những vectơ cơ sở). Giá trị hàm mục tiêu tại x(λ 0), Z(λ 0), không lớn hơn giá trị hàm mục tiêu tại x0 (= ym+1,0), và sẽ nhỏ hơn, nếy λ 0 > 0. Ở điểm cực biên này cũng có một trong 3 trường hợp như trên. 4 Nếu yil ≤ 0 thì – yil(yk0/ykl) ≥ 0, nên xBi(λ 0) ≥ 0. Khi yil > 0, thì theo cách xác định λ 0 ở yi 0 y k 0 yi 0 (1.24), λ 0 = min = ≤ , nên xBi(λ 0)= yi0 – yil.λ 0 ≥ yi0 – yil(yi0/ykl) = 0. i,yil >0 y y kl yil il Lê Văn Phi, Khoa Toan – Thông kê, Đai hoc Kinh tế Tp. HCM ́ ́ ̣ ̣ 83
Lý thuyêt qui hoach tuyên tinh ́ ̣ ́ ́ Tuy nhiên, để nhận biết các trường hợp ấy, cần phải tính các hệ số ứng dạng chính tắc mở rộng như (1.20). Các hệ số trong dạng này là các tọa độ của các vectơ A.j và vectơ b theo cơ sở mới; chúng được tính tương tự theo công thức (1.10), trang 6, chương I, trực tiếp từ các hệ số ở dạng chính tắc mở rộng ứng với x0 (dạng (1.20)). Từ (1.20) x Bk = y k 0 − ∑ y kij x j − y kl x l j∈J, j ≠ l yk0 y 1 Hay xl = − ∑ kj x j − x Bk (1.25) y kl j∈J , j ≠ l y kl y kl Thay thế (khử) xl ở các phương trình còn lại ở (1.20) x Bi = yi 0 − ∑ yij x j − yil x l , i = 1,2,…,m, i ≠ k j∈J , j ≠ l yk 0 y 1 Hay x Bi = (yi 0 − yil ) − ∑ (yij − kj yil )x j + yil x Bk y kl j∈J , j ≠ l y kl y kl Hay cũng vậy 1 y kj y x Bi + ∑ (yij − yil )x j − yil x Bk = (yi 0 − yil k 0 ) j∈J , j ≠ l y kl y kl y kl Khử xl trong biểu thức hàm mục tiêu (so sánh với (1.20)), ta có Z + ∑ y m +1, j x j + y m +1,l x l = y m +1,0 j∈J , j ≠ l y kj 1 y Z + ∑ (y m +1, j − y m +1,l )x j − y m +1,l x Bk = y m +1,0 − k 0 y m +1,l j∈J , j ≠ l y kl y kl y kl Đặt y kj y'ij = yij − yil , i = 0,1, 2,..., m;i ≠ k y kl y kj y'kj = j = 0,1,2,…,n (1.26) y kl y kj y'm +1, j = y m +1, j − y m +1,l y kl Dạng chính tắc mở rộng ứng với phương án mới cho bởi x 'Bi + ∑ yij x ' j = yi' 0 ' j∈J' Z + ∑ y 'm +1, j x ' j = y 'm +1,0 , (1.27) j∈J' Lê Văn Phi, Khoa Toan – Thông kê, Đai hoc Kinh tế Tp. HCM ́ ́ ̣ ̣ 84
Lý thuyêt qui hoach tuyên tinh ́ ̣ ́ ́ Trong đó J’=[J \ {l}]∪{Bk}; x’Bi = xBi, i ≠ k, x’Bk = xl, x’j = xj, j ≠ l, x’l = xBk. 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à ykl, 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ác5. 1.2 Thuật toán Giả sử hệ ràng buộc (1.2) cho ở dạng chính tắc: x Bi + ∑ a ij x j = bi , i =1, 1,…, m j∈J và các hệ số vế phải đều không âm. Dễ thấy rằng, khi đó ma trận ràng buộc A chứa ma trận đơn vị B = E. Bước 1: Thành lập bảng đơn hình xuất phát ứng với (1.20) với yij = aij, yi0 = bi. i = 1,2,…,m; j∈J. y m +1, j = ∑ c Bi a ij − c j ; y m +1,0 = ∑ c Bi bi . Bảng j∈J j∈J đơn hình xuất phát có dạng:6 ̉ Bang 4.1 Biến Phươn x1 … xl … xn λ0 cơ sở g án c1 … cl … cn xB1 y10 y11 … y1l … y1n … … … … … … … xBk yk0 yk1 … ykl Hang chuân ̉ … ykn … … … … … … … xBm ym0 ym1 … ym,l … ym,n ̀ Z ym+1,0 ym+1,1 … ym+1,l ym+1,n 5 Một đơn hình S trong không gian Rn là một tập hợp lồi bị chặn có n+1 đỉnh. Ví dụ trong R1, đó 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 đỉnh của một đơn hình, người ta so sánh giá trị hàm mục tiêu ở đỉnh đó với các đỉnh kề với nó. Nếu đỉnh nào (trong số các đỉnh ấy) có giá trị hàm mục tiêu tốt hơn (trường hợp 3) thì chuyển sang đỉnh đó. Nếu giá trị hàm mục tiêu ở các đỉnh kề là không tốt hơn (trường hợp 1) 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ở xBi sẽ có dạng vectơ đơn vị ei = (0,0,…,0,1,0,…,0), i =1,2,…,m. Lê Văn Phi, Khoa Toan – Thông kê, Đai hoc Kinh tế Tp. HCM ́ ́ ̣ ̣ 85
Lý thuyêt qui hoach tuyên tinh ́ ̣ ́ ́ ̣ ̉ Côt chuân Bước 2: Xác định y m +1,l = max{y m +1, j } 1≤ j≤ n (1.28) • Nếu ym+1,l = 0, thì ym+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 = yio, i = 1,2, …,m; x*j = 0, xj là biến phi cơ sở. Zmin = ym+1,0. • Khi ym+1,l > 0 thì sang bước 3. (Vì theo chú thích 6, trang 99, thì do = 0, ∀xBi, nên chắc chắn xl là biến pi cơ sở). Bước 3: Xác định   yi 0  min   λ0 =  y >0 il  yil  (1.29)  ∞ , neáu yil ≤ 0, ∀i • 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 xl vào cơ sở thay cho xBk, cột chuẩn là cột xl, hàng chuẩn là hàng k, phần tử chuẩn ykl. Các hệ số ở bảng đơn hình mới tính theo (1.26). Sau đó trở về bước 2. Chú ý: Phương pháp đơn hình nêu trên khảo sát lần lượt các phương án cơ sở của tập chấp nhận được X và qua mỗi bước lặp sẽ có một phương án cơ sở được xét đến. Theo tính chất 1 của bài toán QHTT nếu tập chấp nhận được X là không rỗng thì số các phương án cơ sở là hữu hạn.7 Do đó, nếu các phương án cơ sở được xét đến trong thuật toán là không suy biến thì sau một số hữu hạn bước lặp thuật toán sẽ kết thúc hoặc là với một lời giải tối ưu hoặc là chứng tỏ rằng hàm mục tiêu không bị chặn dưới. 1.4 Ví dụ: Giải bài toán QH tuyến tính sau đây: Z = 4x1 + x3 + 2x4 + 2x5 + 3x6 + 4x7 → min 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 Toan – Thông kê, Đai hoc Kinh tế Tp. HCM ́ ́ ̣ ̣ 86
Lý thuyêt qui hoach tuyên tinh ́ ̣ ́ ́  1 1 1  x1 + 2 x 2 + 2 x 3 + 2 x 4 = 3000   2 2 2 2  x2 + x3 +x5 + x6 + x7 = 3000  3 3 3 3  1 1 1 1  x3 + x 4 + x 6 + x 7 + x 8 = 1000  4 2 4 2   x j ≥ 0, j = 1, 2,3,...,8 Bai giải: Vì ma trận hệ số A có đúng 3 vectơ đơn vị ứng với A .1, A.5 và ̀ A.8, và vectơ vế phải b = (3000, 3000, 1000) không âm nên có thể áp dụng phương pháp đơn hình trực tiếp với ma trận cơ sở xuất phát B = [A.1, A.5, A.8] Khi đó các biến cơ sở sẽ là xB1 = x1, xB2 = x5, xB3 = x8. Phương án xuất phát x0 = (3000, 0, 0, 0, 3000, 0, 0, 1000) và Z0 = 18000. Bảng đơn hình xuất phát có dạng: Bảng 4.2: Biến Phươn x1 x2 x3 x4 x5 x6 x7 x8 λ0 cơ g án 4 0 1 2 2 3 4 0 sở x1 3000 1 1/2 1/2 1/2 0 0 0 0 6000 x5 3000 0 2/3 1/3 0 1 2/3 1/3 0 4500 x8 1000 0 0 1/4 1/2 0 1/4 1/2 1 - Z 18000 0 10/3 5/3 0 0 -5/3 -10/3 0 • Xác định vectơ đưa vào cơ sở: Ở bảng 1 ta có: y4l = max y4j = y42 = 10/3. Vậy cột chuẩn l = 2. Ở bước sau A.2 sẽ được đưa vào cơ sở. • Xác định vectơ đưa ra khỏi cơ sở: Ta có λ 0 = min{bi/yi2, yi2 > 0}= min {6000, 4500} = 4500 = y22. 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ế x5 bởi x2 ta có bảng 2. Bảng 4.3: Biến Phươn x1 x2 x3 x4 x5 x6 x7 x8 λ0 cơ g án 4 0 1 2 2 3 4 0 sở x1 750 1 0 1/4 1/2 -3/4 -1/2 -1/4 0 x2 4500 0 1 1/2 0 3/2 1 1/2 0 x8 1000 0 0 1/4 1/2 0 1/4 1/2 1 - Z 3000 0 0 0 0 -5 -5 -5 0 Lê Văn Phi, Khoa Toan – Thông kê, Đai hoc Kinh tế Tp. HCM ́ ́ ̣ ̣ 87
Lý thuyêt qui hoach tuyên tinh ́ ̣ ́ ́ Ở bảng này, các hệ số đặt trưng y4j ≤ 0, ∀j, nên đây là phương án tối ưu. Vậy bài toán trên có phương án tối ưu là x* = (750, 4500, 0, 0, 0, 0, 0, 1000) và giá trị Zmin = 3000. Tuy nhiên, do các hệ số đặt trưng ứng với x4 và x5 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. Bảng 4.4: Biến Phươn x1 x2 x3 x4 x5 x6 x7 x8 λ0 cơ g án 4 0 1 2 2 3 4 0 sở x3 3000 4 0 1 2 -3 -2 -1 0 x2 3000 -2 1 0 -1 3 2 1 0 x8 250 -1 0 0 0 3/4 3/4 3/4 1 - Z 3000 0 0 0 0 -5 -5 -5 0 §2 Phương pháp cơ sở giả tạo (Phương pháp đơn hình hai thời kỳ) 2.1 Cơ sở lý thuyết 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. Lê Văn Phi, Khoa Toan – Thông kê, Đai hoc Kinh tế Tp. HCM ́ ́ ̣ ̣ 88
Lý thuyêt qui hoach tuyên tinh ́ ̣ ́ ́ 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 yi0 ≥ 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  Z = ∑ c x → min n  j =1 j j  n  (2.1)  ∑ a ij x j = bi ,i = 1, 2,...m  j=1  x j ≥ 0, j = 1, 2,..., n   Ở đây có thể giả thiết rằng, các b i, i = 1,2,…, m, đều không âm. Tuy nhiên, mặc dù có giả thiết này, người ta cũng không dễ dàng chuyển (2.1) về dạng chính tắc mở rộng. Đặc biết khi bài toán (2.1) không có phương án chấp nhận được, tức tập X = ∅. Thay thế cho bài toán (2.1), người ta khảo sát bài toán sau đây :  m ZG = ∑ x Gi → min  i =1  n  ____ (2.2)  ∑ a ij x j + x Gi = bi ,i = 1, m  j=1  ___ ____  x j ≥ 0, j = 1, n; x Gi ≥ 0,i = 1, m  Với aij, bi , xj như ở bài toán (2.1), i = 1,2,…,m ; j = 1,2,…,n. Bài toán (2.2) cũng là bài toán QHTT cho ở dạng chính tắc chấp nhận được, có n+m biến số và m ràng buộc. Để phân biệt, các biến số xj được gọi là các biến thực, các biến xGi gọi là các biên « giả ». Chúng là giả vì chúng không có ý nghĩa kinh tế ; chúng do người giải bài toán mới thêm vào. Dễ thấy rằng nếu x là phương án chấp nhận được của (2.1) thì x G = ( x , 0,…,0) là phương án chấp nhận được của (2.2). Hơn nữa, nếu gọi X G là tập chấp nhận được của (2.2) thì XG ≠ ∅. Thật vậy, phương án x0G với x0j = 0, j = 1,2,…,n và x0Gi = bi, 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 ZG ở (2.2) là bị chặn dưới (ZG ≥ 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. Lê Văn Phi, Khoa Toan – Thông kê, Đai hoc Kinh tế Tp. HCM ́ ́ ̣ ̣ 89
Lý thuyêt qui hoach tuyên tinh ́ ̣ ́ ́ Để 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 đó yij = aij, yi0 = bi, m m y m +1, j = ∑ a ij ; y m +1,0 = ∑ bi , i = 1,2,…,m ; j = 1,2,…,n : i =1 i =1 x n ____  Gi + ∑ yij x j = yi 0 ,i = 1, m j =1 (2.3)  n  ZG + ∑ y m +1, j x j = y m +1,0  j =1 Do đó ta có phương án cực biên xuất phát là x0G với x0G = (0, 0,…, 0, y10, y20, …, ym0). Cơ sở BG = [A.G1,…, A.Gm] là cơ sở giả tạo, ứng với các biến giả xG1,…, xGm.8 Giả sử bài toán (2.2) có phương án tối ưu là m x*G = ( x1 , x * ,..., x * , x * , x * 2 ,..., x * ) và ZGmin = ∑ x Gi * * 2 n G1 G Gm i =1 Giữa bài toán (2.1) và (2.2) có mối quan hệ sau đây: Đlí 2.1: 1) Nếu ZGmin > 0 thì bài toán (2.1) không có phương án chấp nhận được; tức là X = ∅. 2) Khi ZGmin = 0, thì x* với x* = ( x1 , x * ,..., x * ) là phương án tối ưu * 2 n của bài toán (2.1). Chứng minh: 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 ZG(x’, xG) = 0 < ZGmin. Mâu thuẩn với giả thiết rằng (x*, xG*) là phương án tối ưu của bài toán (PG). Vậy X = ∅. Khi ZGmin = 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 đó, xGk chẳng hạn, ta phân biệt hai trường hợp: a) ykj = 0, j = 0,1,2,…,n. Khi đó, theo phương pháp tìm hạng của một ma trận, ràng buộc k phụ thuộc tuyến tính vào các ràng buộc khác. Vì vậy có thể loại bỏ ràng buộc này. b) ∃ ykl ≠ 0. Trong trường hợp này, ta thực hiện phép biến đổi cơ sở thay biến xGk bởi buến xl. Cơ sở sẽ bớt được một biến giả. 8 Vì vậy phương pháp này còn có tên “Phương pháp cơ sở giả tạo” Lê Văn Phi, Khoa Toan – Thông kê, Đai hoc Kinh tế Tp. HCM ́ ́ ̣ ̣ 90
Lý thuyêt qui hoach tuyên tinh ́ ̣ ́ ́ Sau khi loại bỏ tất cả các biến giả khỏi cơ sở, ta tiếp tục giải bài toán (2.1) bằng phương pháp đơn hình với cơ sở vừa tìm được bằng việc tính lại các hệ số đặc trưng ym+1,j, j = 0,1,2,…,n. Như vậy phương pháp cơ sở giả tạo bao gồm việc sử dụng phương pháp đơn hình 2 lần: lần thứ nhất dùng để giải bài toán PG (Thời kỳ I) và lần thứ 2 dùng để giải bài toán (P) (Thời kỳ II). Vì vậy phương pháp này còn có tên là phương pháp đơn hình hai thời kỳ. Về việc thực hiện phương pháp, bảng đơn hình ban đầu không có gì thay đổi nhiều so với bảng đơn hình thông thường. Vì hàm mục tiên của PG rất đơn giản, các hệ số của các biến đều bằng 1, nên không cần phải ghi vào bảng đơn hình. Do đó cả hai thời kỳ đều có thể thực hiện trên cùng một bảng đơn hình. Dòng hệ số cj 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 xGi 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ả. 2.2 Ví dụ: Giản bài toán QHTT sau đây Z = x1 − 3x 2 + 3x 3 − 2x 4 + 4x 5 → min  x1 +4x 3 −2x 4 +5x 5 =3  8x −x3 −x 4 −2x 5 = 30  1  (P) 5 7 5 1  3 x1 +x 2 − x3 + x4 x5 =7 3 3 3  17x1  +2x 3 −4x 4 +x5 = 63 xj ≥ 0, j = 1,2,…,5 Bài toán (PG) có dạng ZG = x G1 + x G 2 + xG4 → min  x1 +4x 3 −2x 4 +5x 5 + x G1 =3  8x −x3 −x 4 −2x 5 + x G 2 = 30  1  (PG) 5 7 5 1  3 x1 +x 2 − x3 + x4 x5 =7 3 3 3  17x1  +2x 3 −4x 4 +x5 + xG 4 = 63 xj ≥ 0, j = 1,2,…,5; xGi ≥ 0, i = 1,2,4 Lê Văn Phi, Khoa Toan – Thông kê, Đai hoc Kinh tế Tp. HCM ́ ́ ̣ ̣ 91
Lý thuyêt qui hoach tuyên tinh ́ ̣ ́ ́ Ở đây bài toán (PG) 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 Phươn x1 x2 x3 x4 x5 λ0 cơ g án 1 -3 3 -2 4 sở xG1 3 1 0 4 -2 5 - xG2 30 8 0 -1 -1 -2 15/4 x2 7 5/3 1 -7/3 5/3 1/3 21/5 xG4 63 17 0 2 -4 1 63/17 ZG 96 26 0 5 -7 4 Bảng 4.6: (Thời kỳ I) Biến Phươn x1 x2 x3 x4 x5 λ0 cơ g án 1 -3 3 -2 4 sở x1 3 1 0 4 -2 5 - xG2 6 0 0 -33 15 -42 2/5 x2 2 0 1 -9 5 -8 2/5 xG4 12 0 0 -66 30 -84 2/5 ZG 18 0 0 -99 45 -126 Bảng 4.7: (Thời kỳ I/Thời kỳ II) Biến Phươn x1 x2 x3 x4 x5 λ0 cơ g án 1 -3 3 -2 4 sở x1 19/5 1 0 -2/5 0 -3/5 x4 2/5 0 0 -11/5 1 -14/5 x2 0 0 1 2 0 6 Z 3 0 0 -5 0 -17 Đến đây thời kỳ II kết thúc với phương án tối ưu là x* = (19/5, 0,0,2/5,0) va giá trị tối ưu Zmin = 3. 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. §3 Phương pháp đơn hình mở rộng Phương pháp bài toán M 3.1 Cơ sở lý thuyết Lê Văn Phi, Khoa Toan – Thông kê, Đai hoc Kinh tế Tp. HCM ́ ́ ̣ ̣ 92
Lý thuyêt qui hoach tuyên tinh ́ ̣ ́ ́ 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  Z = ∑ c x → min n  j =1 j j  n  (2.1)  ∑ a ij x j = bi ,i = 1, 2,...m  j=1  x j ≥ 0, j = 1, 2,..., n   và ký hiệu như thường lệ là bài toán (P) và vẫn giả thiết rằng các bi là không âm i = 1,2,…,m. Ứng với bài toán (P) như vậy ta thành lập bài toán mở rộng:  Z = ∑ c x + M.∑ x → min n m  M j =1 j j i =1 Gi   n ____ (3.1)  ∑ a ij x j + x Gi = bi ,i = 1, m  j=1  ___ ____  x j ≥ 0, j = 1, n; x Gi ≥ 0,i = 1, m  Trong đó các hệ số aij, bi, cj, 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 xj , j = 1,2,…,n, vẫn gọi là biến thực, còn các xGi là các biến giả, i = 1,2,…,m. Tương tự ta vẫn ký hiệu X là tập chấp nhận được của (2.1) và XG là tập chấp nhận được của (3.1) và gọi (3.1) là bài toán mở rộng PM. Giữa X và XG có mối quan hệ tương tự như ở phần phương pháp cơ sở giả tạo. Vì giả thiết các bi, i = 1,2,…,m là không âm, nên có thể áp dụng phương pháp đơn hình trực tiếp giải bài toán (3.1) với cơ sở (giả tạo) xuất phát là: xGi = bi, i = 1,2,…,m. Tuy nhiên, khác với bài toán PG, bài toán (3.1) có thể không có lời giải tối ưu. Giữa bài toán P và bài toán PM bài toán mở rộng PM có mối quan hệ như sau: Lê Văn Phi, Khoa Toan – Thông kê, Đai hoc Kinh tế Tp. HCM ́ ́ ̣ ̣ 93
Lý thuyêt qui hoach tuyên tinh ́ ̣ ́ ́ Đlí 3.1: Nếu bài toán (P) có lời giải tối ưu thì sẽ tìm thấy một số thực M0, sao cho, nếu (x*, x*G) là lời giải tối ưu của PM với mọi M ≥ M0 thì x* G = 0. Do đó x* là lời giải tối ưu của P. Chứng minh: a) Trước hết ta chứn minh rằng, nếu x0 là lời giải tối ưu của P thì sẽ tồn tại M0 để cho (x0, 0) là lời giải tối ưu của PM. Thật vậy, bài toán đối ngẫu của P có dạng W = 〈b, y〉 → max (D) ATy ≤ c Giả thiết P giải được kéo theo D giải được. Tức là tồn tại y0 để cho cặp (x0, y0) thỏa mãn hệ:  Ax = b, x ≥ 0   A y≤c T  c, x = b, y  Tức là 〈c, x0〉 = 〈b, y0〉 với AT y0 ≤ c Bài toán đối ngẫu của của PM có dạng WM = 〈b, y〉 → max (DM) ATy ≤ c yi ≤ M, i = 1,2,…,m Để cho cặp PM và DM có lời giải tối ưu thì điều kiện cần và đủ là tìm thấy (x, x G , y) để cho  Ax + x G = b  x ≥ 0; x G ≥ 0   (3.2)  A T y ≤ c, y ≤ M,i = 1,m ____  i  c, x + M ∑ x = b, y m   i =1 Gi Cặp (x0, y0) thỏa mãn (3.2) nên bộ ba (x0, 0, y0) cũng sẽ thỏa mãn (3.4) nếu chọn M0 = max { y1 , y 2 ,..., y m } 0 0 0 (3.5) Lê Văn Phi, Khoa Toan – Thông kê, Đai hoc Kinh tế Tp. HCM ́ ́ ̣ ̣ 94
Lý thuyêt qui hoach tuyên tinh ́ ̣ ́ ́ Tức (x0, 0) là lời giải tối ưu của PM, và y0 là lời giải tối ưu của DM với mọi giá trị M ≥ M0. a) Bây giờ ta sẽ chứng minh, nếu ∀M không nhỏ hơn M0 nào đó mà (x*, x*G) là lời giải tồi ưu của PM 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 0. Khi đó tồn tại lời giải tối ưu của D, giả sử đó là y0. Cặp (x0, y0) sẽ thỏa mãn (3.2). Nếu chọn M0 theo (3.5) thì theo a), điểm (x0, 0) là lời giải tối ưu của PM, với mọi giá trị M ≥ M0. Khi ấy, do theo giả thiết (x*, x* G) cũng là lời giải tối ưu của PM, nên m m ∀ M ≥ M0: 〈c, x0〉 = 〈c, x0〉 + M ∑ 0 = 〈c, x*〉 + M ∑ x Gi * (3.6) i =1 i =1 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 M0 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 PM, 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 PM 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 PM với cơ sở xuất phát là xGi = bi, i = 1,2,…,m. Ta phân biệt 3 trường hợp: 1) Bài toán PM có lời giải tối ưu là (x*, x*G) và có ít nhất một x*Gk > 0: Khi đó tập chấp nhận được của P, X=∅. Do đó P không giải được. Thật vậy, nếu X≠∅ , thì với x’∈X, (x’, 0)∈ XM. Do đó m ZM(x’,0) = 〈c,x’〉 ≥ ZM(x*,x*G) = 〈c, x*〉 + M. ∑ x Gi , ∀ M ≥ M0. * i =1 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 PM 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. 3) Với mọi giá trị của M, hàm mục tiêu của PM, ZM không bị chặn dưới trên XM. 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 ≤ ZM, ∀ M≥ 0. 3.2 Thực hiện phương pháp đơn hình mở rộng: 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 PM 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 hàng ấy nữa. Mặc khác, vì các biến x Gi là giả nên khi một biến giả được loại khỏi cơ sở thì không cần thiết phải đưa vào cơ sở nữa, nên trong bản đơn hình không cần thêm các cột ứng với các biến giả. Lê Văn Phi, Khoa Toan – Thông kê, Đai hoc Kinh tế Tp. HCM ́ ́ ̣ ̣ 95

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.