Giáo trình Quy hoạch tuyến tính: Phần 2

Chia sẻ: Lê Na | Ngày: | Loại File: PDF | Số trang:82

Thêm vào BST

Báo xấu

172
lượt xem 53
download

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

Phần 1 giáo trình "Quy hoạch tuyến tính" gồm nội dung các chương: Chương 4 - Các phương pháp đơn hình đặc biệt, chương 5 - Một số vấn để khác liên quan bài toán quy hoạch tuyến tính. Sau mỗi chương đều có câu hỏi ôn tập và bài tập. Mời bạn đọc tham khảo.

Chủ đề:

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

Lưu

Nội dung Text: Giáo trình Quy hoạch tuyến tính: Phần 2

Chương 4 CÁC PHƯƠNG P H Á P ĐƠN HÌNH ĐẶC BIỆT Trên cơ sở phương pháp đơn hình, trong chương n à y chúng ta sẽ nghiên cứu một số phương p h á p đặc biệt của nó. § 1 . P h ư ơ n g phập đ ơ n h ì n h c ả i b i ê n * 4.1.1. Ý tưởng của phương pháp Phương p h á p đơn hình, thực chất là: Xây dựng các phương án cực biên t ố t dần theo hướng giảm. Ở mỗi bước, đi t ừ phương án cực biên Xo sang p h ư ơ n g á n cực biên X j (xem § 1 , chương 3) nhờ các phép tính: Xo* = B -'b Xj = B -'Aj 1 Aj = C*Vj - Cj = C*B- Aj - C j , j € J (dễ thấy r ằ n g với j e J t h ì Aj = 0). Ở đây Aj là cột j của ma t r ậ n A, B là ma t r ậ n các toa độ của vectơ cơ sở liên k ế t , J là tập chỉ s ố cơ sở, c * = (Cj)j6j 99
1 đã biết t ừ X . Như vậy nếu biết B 0 thì ta có t h ê tính được Xo, Vj và Aj. Nếu X chưa t ố i ưu, cần xây dựng X ] . Chú ý rằng ma 0 t r ậ n cơ sở của X Ị khác ma t r ậ n cơ sở của Xo chỉ bởi một vectơ (A thay cho A,). k Đe đơn giản, ta giả t h i ế t bài t o á n đã b i ế t trước một phương án cực biên xuất p h á t , ứng với cơ sở liên k ế t đơn vị. Trong trường hợp tổng q u á t có phức tạp hơn, bạn đọc quan t â m có t h ể xem [1], [7]. Xuất p h á t từ phương án cực biên Xo với ma t r ậ n cơ sở liên k ế t B = E đơn vị. K h i đó dễ d à n g tính được ma t r ậ n 1 nghịch đảo B = E. Giả sử ma t r ậ n liên k ế t của X! là g cz A. Ta cần t í n h X 1; Vj', Áy thì n h ư đã nêu, chủ yêu ta cần t í n h ? "\ Để ý rằng phương p h á p tính ma t r ậ n nghịch đảo trong đ ạ i số tuyến t í n h là: Ta viết ma t r ậ n (E ị ?), thực h i ệ n biến đ ổ i 1 theo h à n g để được ma t r ậ n (Ez \ E). K h i đó E chính là S ' . Do vậy, giả sử B = E = ( A ^ . - . A ^ - . A , , , ) và ĩ - (A!A ...A ...A ), thì g' chính là ma t r ậ n tương ứng 2 u m 1 (A]A ...A,...A ) trong bảng X i (chứ k h ô n g phải trong bảng 2 m Xo). (Bạn đọc h ã y tự kiểm tra nhận xét n à y trong ví d ụ đã nêu ở mục 3 chương 3). Tuy nhiên, để dễ tính toán ta ký h i ệ u f A (A tí = (tí.) = K ì ỉ { - c ĩ)' trong đó tí là ma t r ậ n gồm m +1 h à n g , n +1 cột. 100
Hàng thứ m +1 của ư là (- Cj - Cọ ... - c„ 1), cột thứ n T + 1 là (0 0 ... 0 1) . Ký hiệu f B 0^ * -c Ì, Rõ ràng ÍB là ma trận m +1 hàng, m +1 cột, có hạng m +1. Có thể trực tiếp kiểm tra được rằng ma trận ỐB có 1 dạng -Ì l 9> = B 0 * c B" Nhận xét rằng, từ công thức tính Aj = C*B l - Ảị - Cị, ta có quy tắc thực hành: 1 • Aj bằng tích hàng thứ m +1 của ma trận ÍB với cột ' A .j ^ « j = - c. trong ma trận tí. _1 • Xj bằng tích của m h à n g đầu của ma t r ậ n £B với ^ A. ) cót tí trong ma trận tì . - c. V ìJ Với nhận xét vừa nêu thì việc tính t t cả các cột của bảng đơn hình là không cần thiết. Do vậy phương pháp đơn hình cải biên được thực hiện trên các bảng đơn hình có những cải tiến, mô tả như sau (bảng 8). loi
B ả n g 8. Cơ s ở c*= X = B 1 x k Aj ( v ớ i A j n g o à i c ơ sở) Ai (c,) (Xi) í Ai hàng m +1 4.1.2. T h u ậ t t o á n đ ơ n h ì n h c ả i b i ê n Bước 0. + C h ọ n cơ sở đ ơ n vị, x á c đ ị n h p h ư ơ n g á n cực b i ê n X . 0 G h i ma t r ậ n tí + L ậ p b ả n g , x á c l ậ p ma t r ậ n ẾB 1 = B 0 trên cV bảng. + T í n h Àj v ớ i m ọ i A j n g o à i cơ sở theo quy t ắ c đ ã n ê u . Bước 1. K i ể m t r a , n ê u m ọ i Aj < 0, t h ì Xo t ố i ư u . Ngược l ạ i , sang bước 2. Bưốc 2. V ớ i Aj > 0, t í n h Yị theo quy t ắ c đ ã n ê u . N ế u có A > 0 v à m ọ i x k i k < 0, t h ì b à i t o á n k h ô n g có n g h i ệ m . Ngược l ạ i c h u y ể n sang bước 3. Bước 3. T í n h A = maxAj , v ớ i Aj > 0. G h i x k k v à o cột tường ứng. 102
X, Bước 4. Tìm x, k theo công thức Xo = min X , >0 X . , ik ik Bước 5. L ậ p bảng X, bằng việc biến đổi t r ê n cột X và ma t r ậ n B ' n h ư đã làm trong bảng đơn hình và t í n h h à n g m +1. Bước 6. G á n Xo := X j . Trở l ạ i bước 1. Ví dụ: G i ả i b à i t o á n sau đây bằng phương p h á p đơn h ì n h cải biên m i n (f = X j - x 2 + x 3 + x 4 + x 5 - x 6 ) + X , + 6x 6 =9 3x 1 + x 2 4x. + 2x 6 = 2 vối điêu k i ệ n + 2x„ 5 6 X x x x x x l ' 2 ' 3 ' 4 ' 5 ' 6 - °" Chọn C ơ S Ở liên k ế t A , A , A- là các vectơ đơn vị n ê n 4 2 a ta có Xịj = aý- và p h ư ơ n g á n cực biên xuất p h á t X - (0, 2, 0, 9, 6, 0), cùng với bảng đơn h ì n h cải biên (bảng 9). C h ú ý rằng theo bài t o á n , ta có ma t r ậ n í Ì 0 0 Ì 0 6 0 A 3 1-4 0 0 2 0 (í Ì 0 2 0 Ì 2 0 •Ì Ì -Ì -Ì -Ì Ì Ì 103
B ả n g 9. 1 Ai Xi B Ai Ci Xu A 4 1 9 1 0 0 0 6 1 3 6 j A 2 -1 2 0 1 0 0 Ổ) -2 5 TỪ A 5 1 6 0 0 1 0 2 13 1 -1 1 1 7 A 4 1 3 1 -3 0 0 © í 1 2 3 -1 1 0 1/2 0 0 -2 K -25/2 -7/2 191Ì Aặ 1 4 0 -1 1 0 6 6 1 1 1 19 9/2 A 1 1/4 1/12 - 0 0 - 1 2 4 3 .í A 6 -1 3/2 1/6 1/4 0 0 1/4 1/6 5/4ÍÌ -3/4 A 1 5/2 -1/2 1 0 0 5 0 1/2 (Ồ 5/4 -7/12 1/4 1 1 5/4 A 3 1 3/2 -1/6 0 1/2 0 Ì 1 4 s ít À* -1 3/2 1/6 0 0 0 Ai -29/6 -1/3 -5/2 A 2 -1 5 -1 1 2 0 -5 2/3 -1 1 3/2 T ạ i b ả n g I V , m ọ i Aj < 0, được p h ư ơ n g á n t ố i ư u là x, ư = (0, 5, 3/2, 0, 0, 3/2) v ớ i f m i n = - 5. §2. Phương pháp đơn hình đôi ngẫu Cho b à i t o á n góc m i n { f = CX} 104
với điều k i ệ n 0. Ta có b à i t o á n đ ố i n g ẫ u max(g = Yb) với điều k i ệ n { YA < c. T r o n g c h ư ơ n g 2, c h ú n g ta đ ã b i ế t m ố i l i ê n h ệ của cặp b à i t o á n đ ố i n g ẫ u . Ý t ư ở n g của p h ư ơ n g p h á p n à y l à n g h i ê n cứu giải bài toán đối ngẫu (về lý l u ậ n ) , sau đ ó suy ra p h ư ơ n g á n t ố i ư u của b à i t o á n gốc. V i ệ c g i ả i b à i t o á n đ ố i n g ẫ u được m ô t ả t r ê n b ả n g đơn h ì n h , d i ễ n t ả c á c bước đ ơ n h ì n h theo n g ô n n g ữ b à i t o á n gốc. T a h ã y x u ấ t p h á t t ừ h ệ cơ sở B = (Aj)je J n à o đó của ma t r ậ n A . 1 K ý h i ệ u c* = (c,) 1Ễ J . X é t Y = C*B - . D ễ d à n g c h ứ n g m i n h được r ằ n g Y = C*B là p h ư ơ n g á n của b à i t o á n đ ố i n g ẫ u k h i v à chỉ k h i A, = C*Yj - Cj < 0 v ớ i m ọ i j. Do v ậ y , t ừ nay v ề sau, k h i nói đ ế n p h ư ơ n g á n Y t h ì t a h i ể u Áy < 0. T ừ đó ta suy r a được các đ ị n h lý: Đ ị n h l ý 4.1. N ế u t ạ i p h ư ơ n g á n Y = C*B 1 (tức l à có m ọ i Aj < 0) có được X = B 'b > 0, t h ì X l à p h ư ơ n g "án t ố i ư u của b à i t o á n gốc (và Y là p h ư ơ n g á n t ố i ư u của b à i t o á n đ ố i ngẫu). N ê u ngược l ạ i , đ i ề u k i ệ n của đ ị n h lý 4.1 c h ư a được t h o a m ã n , t r o n g t r ư ờ n g hợp n à y ta g ọ i X = B *b l à m ộ t giả phương án tối ưu (có m ọ i Aj < 0). K ý h i ệ u co, là h à n g i của ma t r ậ n B '. 105
Đ ị n h lý 4.2. Y' = Y - Pcơị sẽ là p h ư ơ n g á n của b à i t o á n đối ngẫu nêu p thoa mãn: p > 0 và Px;j > Aj, m ọ i j . Chứng minh: Ta có TA, = YAj - pcoẠ = C*B 'A, - pdOjAj. l Nhưng C*B ' A j = Aj + Cj và co,Aj = Xi) , n ê n 1 Y'Aj = C*B Aj - Pco,Aj = l = C*B A ì - Px,j = A, + Cj - P x j j < Cj o Aj - Ị3x < 0, với p > 0. lj Tức là Y' phương án k h i và chỉ k h i Aj < pXij, p > 0. • Từ k ế t quả định lý 4.2 và chứng minh của nó ta có Y'b = Yb - PXị, trực tiếp ta suy ra được định lý sau đây: Đ ị n h lý 4.3. Nếu t ạ i phương án Y = C*B (tức là có 1 mọi Aj < 0) tồn t ạ i X, < 0 (trong X = B 'b) và X,, > 0, j = Ì, 2, n, thì hàm mục tiêu của bài toán đ ố i ngẫu không bị chặn t r ê n tập phương án (bài toán góc không có phương án tối ưu). Định lý 4.4. N ế u t ạ i phương án Y = C*B \ t ồ n t ạ i X, < 0 và tồn t ạ i X f j < 0 thì xây dựng được p h ư ơ n g án mới Y' tốt hơn Y. Chứng minh: Theo định lý 4.2 và định lý 4.3, giả sử trong X = B ^b, có X, < 0, ta có Y' là phương án k h i và chỉ khi p>0 và px,j > A, , j = l , 2, . . . , n . Nghĩa là k h i và chỉ k h i A. 0 < (3 < —Ì- , vối x,j < 0. 106
í a h C h ọ n Po = min — = —í- . x,
+ Nêu có, bài toán không có phương á n t ố i ưu. + Ngược l ạ i , sang bước 3. Bước 3. Tồn t ạ i X, < 0, tồn t ạ i Xi, < 0. Chọn xỹj= min X . , A, ra khỏi cơ sở. 1 x
N ế u chọn cơ sở A A A , ta được giả phương : i 6 2 án X = (0, 5, 6, 0, 0, - 3). Ta có b á n g đ ơ n h ì n h đ ố i n g ẫ u ( b ả n g 10). B ả n g 10. Cơ Hệ Toa 1 -1 1 1 1 0 sở SốCj độ X i A, A 2 A 3 A 4 A5 A 6 A 3 1 6 2 0 1 -1 3 0 ì 0 -3 -1 0 0 Q 0 1 A 2 -1 5 4 1 0 -ĩ 2 0 -3 0 0 -lữ 0 0 A 3 1 9 3 0 1 0 3 -1 li A 4 1 3 1 0 0 1 0 -1 A 2 -1 8 5 1 0 0 2 -1 -2 0 0 0 0 -1 T ạ i đ â y ta có X > 0 n ê n n ó l à p h ư ớ n g á n t ố i ư u , v ớ i X = (0, 8, 9, 3, 0), f M i n = 4. 4.2.2. C h ú ý 1) T ừ c ô n g t h ứ c Y = C * B ' \ p h â n t í c h t r ự c t i ế p ta có được Y i = Aj + C j , t r o n g đó j chỉ cột t h ứ j , ở b ả n g ì vectơ A j là v e c t ơ cơ sở đ ơ n vị (số Ì n ụ m ở h à n g t h ứ i cột j của bảng). C h ẳ n g h ạ n , t r o n g ví d ụ t r ê n ta có Y = (A + 3 Ca, A + c , A + c ) = ( Ì , - Ì , -1). 6 6 2 2 N h ư v ậ y , ta có được 3 c á c h x á c đ ị n h n g h i ệ m b à i t o á n đ ố i n g ẫ u ( B ạ n đọc t h ử n ê u ra 3 c á c h t í n h đó?). 2) T h u ậ t t o á n đ ã n ê u sẽ r ấ t t i ệ n l ợ i t r o n g t r ư ồ n g hợp k h i c h ú n g ta đ ã g i ả i b à i t o á n 109
min cx 3:í. , • ;AX - b VỚI điêu k i ệ n ị (ì) w [x>0. Bây giờ ta giải bài toán min cx ~. , ÍAX = b' VỚI đ i ê u k i ệ n •{ (li) ; [x>0, trong đó b * b'. Như chúng ta đã biết khi bài toán (ì) giải được thì bài toán (li) cũng giải được (nếu tập phướng án khác rỗng). Việc giải bài toán (li) có thể dựa vào bảng đơn hình của bài toán (ì) mà không cần tính toán lại từ đầu. Giả sử bài toán (ì) có phương án tối ưu Xo với cơ sỏ B, khi đó ta có B 1 trong bảng đơn hình cuối cùng của X . Sử dụng bảng 0 đơn hình cuối cùng cho bài toán (li), ta có X = B 'b'. Do mọi Aj < 0, nên nếu X > 0 thì X tối ưu, nếu tồn tại X, < 0 thì X là giả phương án tối ưu. Khi đó áp dụng thuật toán đơn hình đối ngẫu cho bài toán (li) kể từ bảng đơn hình cuối cùng vừa nêu. Việc giải bài toán (li) dựa vào kết quả bài toán (ì) như đã nêu gọi là phương pháp tái tối ưu. Ví dụ: Giải bài toán min (f = Xj -x +x + x + x) 2 3 4 5 no
+ x„ - X, + 3x- .J -4 o + x 6 =-3 với điều kiên 4 x i + x 2 - X. +2x_ 4 5 , x , x . , . x . , x , x „ > 0. 0 c 1 2 3 4 5 6 Bài toán này có khác bài t o á n vừa g i ả i chỉ ở vectơ b. Dựa vào bảng đơn hình cuối cùng ta có B = (A3A4A2) và Ì -Ì Oi 1 B = Ì 0 Ì Ì K h i đó ta có giả phương án ri -1 °1 í 6^ í 9Ì X = B 'b = 0 -1 0 -3 = 3 -1 lo ĩ J 1-5; 1-2J X = (0, -2, 9, 3, 0, 0) và bảng đơn hình đối ngẫu (bảng l i ) . Bảng l i . Cơ 1 -1 1 1 1 0 số c, X, Ai A 2 A 3 A 4 A 5 Ae A3 1 9 3 0 1 0 3 -1 ì A, 1 3 1 0 0 1 0 -1
Bạn đọc có t h ể trực tiếp giải bài toán vừa nêu bằng t h u ậ t toán đơn hình để k i ể m tra l ạ i k ế t quả. §3. P h ư ơ n g p h á p p h â n p h ô i 4.3.1. Bài t o á n vận tải c ổ đ i ể n . c ầ n tô chức vận t ả i một loại hàng từ n nơi phát đến m nơi thu. Nơi p h á t thứ j có số lượng hàng là ãị, nơi nhận thứ i cần số lượng h à n g là bị. Cước phí vận t ả i một đơn vị hàng từ j tối i là Cy. Nên tổ chức vận t ả i như t h ế nào đê bảo đảm phát hết và nhận đủ số hàng mà có tổng cước phí bé nhất. Đây là bài toán r ấ t hay gặp trong thực t ế . Chú ý r ằ n g "hàng" ở đây có thề là h à n g hoa thông thường, có t h ể là lượng thông t i n cần chuyển t ả i , có t h ể là sự p h â n phối lao động nào đó, ... Tạm bỏ qua điều k i ệ n nguyên, ta h ã y xác lập bài toán. Gọi Xy là số lượng h à n g vận t ả i t ừ í tói ì. K h i đó ta có bài toán quy hoạch tuyến tính dạng chính tắc: n m m i n i 4 A ) Z X Vij j=l i = l 112
c n (4.2) b XX, = . j=l 111 (4.3) với điểu kiện 1=1 (4.4) X,J > 0 , ì = 1, n i = 1, m. Ở đây mọi Cjj > 0, a j; b, > 0. 4.3.2. T í n h c h ấ t Đ ị n h lý 4.5. Bài toán v ậ n t ả i đã cho có phương án t ố i ưu k h i và chỉ k h i cân bằng thu - p h á t , nghĩa là n m j=l i=l Chứng minh: Theo điều k i ệ n (4.2) và (4.3), ta có tập phương án là bị chặn. Đồng thời có t h ể kiểm tra trực tiếp thấy rằng a.b. X = (x ) , với Xi, = J ì". y là phương án k h i và chỉ k h i / ạ . = y^ b. • j=i i=i Từ đó suy ra k ế t l u ậ n của định lý. • Trong trường hợp bài toán chưa cân bằng t h u p h á t thì ta lập các t r ạ m giả n h ư sau: 113
n m + Nếu a. > ^ b. (phát nhiều hơn thu) thì ta j=l i=l l ậ p nơi t h u g i ả (tồn kho) t h ứ m + 1 , v ố i l ư ợ n g t h u v à o là n m b m +1 = 2 ãị - ^ bị v à cước p h í c m+1 ị = 0. j=i i=i n m + Nếu / a. 1 < 2J b. ( p h á t í t hớn t h u ) t h ì ta l ậ p n ơ i j=i i=i p h á t g i ả (ghi nợ) t h ứ n + 1 , v ớ i l ư ợ n g p h á t r a là m n b a v à c ư ớ c p h í c n + 1 = a n + 1 = X i ~ 2 j ' °' i=l j=l N h ư v ậ y có t h ể t h ấ y r ằ n g bao giò ta c ũ n g t ạ o r a được điều k i ệ n cân bằng thu - phát. Định l ý 4.6. Ma trận Ả = (Aịj) = (a ) có hạng :j bằng m + n - 1. Chứng minh: C h ú n g ta c h ú ý r ằ n g ma t r ậ n A = (A.j) cấp ( m + n ) x ( m . n ) , t r o n g đó cột Ajj chỉ có h a i s ố Ì ở h à n g t h ứ i v à h à n g t h ứ m + j , còn l ạ i là s ố 0. r Áy = (0 0 ^ 0 . . . Ì 0...0) . thứ í thứm+ị Do v ậ y , ta có đ ị n h t h ứ c con cấp m + n - Ì , l ấ y m + n -Ì h à n g đ ầ u của các cột A A l n 2 n ...A m n A A, ...A u 2 l n .1, k h á c 0. N h ư n g đ ị n h thức cấp m + n b ấ t k ỳ của A b ằ n g 0. 114
T h ậ t v ậ y , k ý h i ệ u Hi là h à n g t h ứ i của A (i = Ì, .... m+n). K h i đó ta có Hi + H 2 + ... + H m = H m + 1 + ... + H m + n , tức là m ộ t h à n g sẽ là t ổ hợp t u y ê n t í n h của các h à n g còn l ạ i . V ậ y A có h ạ n g b ằ n g m + n - 1. T ừ đ â y t a có được h ệ q u ả q u a n t r ọ n g v ề p h ư ơ n g á n cực b i ê n của b à i t o á n v ậ n t ả i . H ệ q u ả . S ố t ọ a độ d ư ơ n g của p h ư ơ n g á n cực b i ê n b à i t o á n v ậ n t ả i có k h ô n g q u á m + n - 1. Ta g i ả t h i ế t r ằ n g b à i t o á n v ậ n t ả i k h ô n g suy b i ế n , tức là m ọ i p h ư ơ n g á n cực b i ê n có đ ủ m + n - Ì t ọ a độ d ư ơ n g . Đ ể t i ệ n sử d n g , ta b i ể u d i ễ n b à i t o á n d ư ớ i d ạ n g b ả n g n h ư sau, g ọ i l à bảng phân phối ( b ả n g 13). B ả n g 13. ^Cướcphí ai a„ bi Xu y / x l j ỵ / / Cu / c ln b, Xil ý / / Cu / c,n b m x ml c ml / ọ ^ n i Ĩ1 115
Khi đó ta có sự tương ứng Ì - Ì trên bảng như sau: Ô (i, j) o Cjj Xjj Áy Đ ị n h nghĩa 4.1. 0 (i, j) có Xjj > 0 gọi là ổ chọn. Các ô không chọn gọi là ó loại. Như vậy, một phương án cực biên không suy biến có m + n - Ì ô chọn. Một dãy ô liên tiếp, sao cho hai ô viết liền nhau cùng h à n g hoặc cùng cột, không có ba ô nào viết l i ề n cùng hàng hoặc cùng cột gọi là một dây chuyền. Một dây chuyền khép kín gọi là một vòng. Như vậy một vòng V được ký h i ệ u là V = {(iu h) (i„ j ) ( i j ) ... ( i , 2 2> 2 k Đ ị n h lý 4.7. Phương án X = (x,j) là cực biên k h i và chỉ k h i các ô chọn không lập t h à n h vòng. Chứng minh: Ta đã biết phương án X là cực biên khi và chỉ khi tương ứng với j G J = {j : X j > 0} là hệ vectơ { A j } je j độc lập tuyến tính. Ký h i ệ u H là tập các ô chọn của X. Như vậy ta chỉ cần chứng minh hệ vectơ { A j j } j H , độc lập (i )e tuyến tính k h i và chỉ khi H không có vòng. Giả sử cho H không có vòng, nhưng hệ các vectơ {Ay}(i.j)e H» phụ thuộc tuyến tính, tức là tồn t ạ i (Xjj * 0 sao cho (*) (i,j)sH Giả sử A . . * 0. K h i đó do tọa độ thứ Ì, của vectơ A. . bằng Ì, nên ắ t có trong oi vectơ A. . đê v ế p h ả i của (*) bằng 0. Cứ lý l u ậ n n h ư vậy, suy ra trong có các vectơ 116
A. . A . . ... A . . . Đ i ề u đ ó hoa ra H có v ò n g . M â u thuẫn Vi ' - i , ỤI vói g i ả t h i ế t H không có v ò n g . V ậ y h ệ {A;j} ( l j ) e H phải độc lập tuyến tính. N g ư ợ c l ạ i , cho h ệ { A , j } ( l j ) e H độc l ậ p t u y ế n t í n h , ta cần chỉ r a H k h ô n g có v ò n g . G i ả sử H có v ò n g V = { ( i , , h ) , ( i n j ) , .... (ik. h ) } - 2 Khi đó r õ r à n g ta có A. - A. + A. = 0. Như vậy hệ {A j} i ( i j ) e H phụ thuộc tuyên tính, mâu t h u ẫ n . V ậ y H k h ô n g có v ò n g . Đ ị n h lý được c h ứ n g m i n h . • Định l ý 4 . 8 . C h o p h ư ơ n g á n cực b i ê n X v ớ i t ậ p h ợ p H g ồ m m + n - Ì ô c h ọ n k h ô n g l ậ p t h à n h v ò n g , ự, k ) Ể H . K h i đó t ậ p hợp H , = H u {ự, k)} lập n ê n một vòng V duy nhất. Đ ồ n g t h ờ i n ế u ( p , q) e V t h ì H 2 = H , \ { ( p , q)} g ồ m đ ú n g m + n - Ì ô k h ô n g có v ò n g . V i ệ c c h ứ n g m i n h đ ị n h l ý n à y x i n d à n h cho b ạ n đọc. T h ô n g t h ư ờ n g c h ú n g ta hay g ặ p c á c l o ạ i v ò n g cơ bản (có t h ể m ỏ r ộ n g n h i ề u b ậ c ) n h ư s a u ( h ì n h 5): $ Hình 5. 117
4.3.3. Cơ sở lý luận của thuật toán Cho bài toán n m (4.1) j=l 1=1 n x = b (4.2) X ' i > j=l vối điều k i ệ n (4.3) 1=1 l Xjj > 0, j = Ì,..., n; Ì = Ì,..., m. (4.4) Theo các đặc điểm đã nêu trong chứng minh định lý 4.6, ta suy ra bài toán đối ngẫu là m n raax(^ b,u,+^ ajVj) (4.5) i=i j=l vối điều kiện: U i + Vj < Cij , i = Ì,..., m; j = Ì,..., n, (4.6) trong đó u, là biến đối ngẫu ở h à n g i , Vj là b i ế n đối ngẫu ỏ h à n g j+m. Ký hiệu Áy = Ui + V j -c ir (4.7) Đ ị n h lý 4.9 (Dấu h i ệ u t ố i ưu). Nếu t ạ i phương án cực biên X tồn t ạ i các số U i , Vj sao cho A,j = 0 t ạ i ô chọn và Ajj < 0 với mọi (i, j ) , thì X là phương án t ố i ưu. 118