Giáo trình Tối ưu tuyến tính và ứng dụng: Phần 2

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:232

Thêm vào BST

Báo xấu

11
lượt xem 5
download

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

Nối tiếp nội dung phần 1, phần 2 cuốn giáo trình "Tối ưu tuyến tính và ứng dụng" trình bày các nội dung: Bài toán vận tải, các bài toán dạng vận tải, bài toán quy hoạch nguyên, bài toán trò chơi ma trận, tối ưu tuyến tính nhiều mục tiêu, lời giải và gợi ý bài tập. Mời các bạn cùng tham khảo nội dung chi tiết.

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 Tối ưu tuyến tính và ứng dụng: Phần 2

, , CHUONG 6 , ` ´ BAI TOAN VÂN TAI . ´ . ˘ ` ´ ¯´ ˜ 4.1. Mô h`nh toan hoc cap bai toan QHTT dôi ngâu . . . . . . . . . . . . . . . . . . ı . 138 ` ´ ´ ` ` ´ ¯´ ˜ 4.2. Bai toan gôc va bai toan dôi ngâu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 , ´ ı ´ ˘ ` ´ ¯´ ˜ 4.3. Cac t´nh chât cua cap bai toan dôi ngâu . . . . . . . . . . . . . . . . . . . . . . . . . 147 ,, ´ , ˜ ı ´ ˘ ¯´ 4.4. T`m phuong an tôi uu cap dôi ngâu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 ` . 4.5. Bai tâp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 , ` ´ 6.1. Mô h`nh bai toan vân tai ı . , ı . ` . ˘ `, ´, V´ du 6.1. Cân vân chuyên xi mang tu 3 kho A 1 , A 2 , A 3 toi 4 công ,`, , ,, ˜ ´ , ., ˘ truong xây dung B1 , B2 , B3 , B4 . Cho biêt luong xi mang c´ o môi . o ,, , ,`, , ˘ ` , ˜ ` ´ , ´, . kho, luong xi mang cân o môi công truong va gia cuoc vân chuyên . ` ¯` ´ ˘ `, ˜ ´, ˜ ,`, (ngan dông) môt tân xi mang tu môi kho toi môi công truong nhu . , sau: B1 : 130 B2 : 160 B3 : 120 B4 : 140 A 1 : 170 20 18 22 25 A 2 : 200 15 25 30 15 A 3 : 180 45 30 40 35 , ´ ¯` ` ı ´ . ˘ `, ´ ´, ´ Vân dê la t`m kê hoach vân chuyên xi mang tu cac kho toi cac . ,`, ´ ´ , ., ˘ công truong sao cho moi kho phat hêt luong xi mang c´ , moi công o ,`, , ,, . , . , ˘ ` ` truong nhân du luong xi mang cân va tông chi ph´ vân chuyên la . ¯ . ı . ` , nho nhât?´ , , . ı ´ ¯` o ı ´ Lâp mô h`nh. Vân dê nêu trên c´ thê mô h`nh hoa nhu sau: Ðat ˘ . ,, , , , ` . ˘ ` ` ´ x i j la luong xi mang cân vân chuyên tu kho i ( i = 1, 2, 3) toi công .
, ı ` ´ 6.1. Mô h`nh bai toan vân tai . 215 ,`, , ´ ´ ´ ` ˜ ´ ¯ ` truong j ( j = 1, 2, 3, 4). Cac biên sô cân thoa man cac diêu kiên sau: . ´ , .,   x11 + x12 + x13 + x14 = 170  ( A 1 giao hêt luong xi mang), ˘ ,,    x21 + x22 + x23 + x24 = 200    ´ ( A 2 giao hêt luong xi mang), . ˘   x + x + x + x = 180 ´ ,, ˘ ( A 3 giao hêt luong xi mang),   31 32 33 34 . ,   ´ `   x + x + x = 130 11 21 31 (B1 nhân du sô xi mang cân), . ¯ ˘ ,  x12 + x22 + x32 = 160 (B2 nhân du sô xi mang cân), . ¯ ´ ˘ ` ,     x13 + x23 + x33 = 120   (B3 nhân du sô xi mang cân), . ¯ ´ ˘ `   ,  x + x + x = 140   14  24 34 (B4 nhân du sô xi mang cân), . ¯ ´ ˘ ` ,,    x ≥ 0, i = 1, 2, 3; j = 1, ..., 4 (luong xi mang không âm). ij . ˘ (6.1) , , , , ı . ` ` Tông chi ph´ vân chuyên (cân lam cuc tiêu): f = 20 x11 + 18 x12 + . 22 x13 + 25 x14 + 15 x21 + 25 x22 + 30 x23 + 15 x24 + 45 x31 + 30 x32 + 40 x33 + ,, , ` ´ ` 35 x34 . Vây bai toan tro thanh: T`m cac biên sô x i j thoa man cac . ı ´ ´ ´ ˜ ´ , , diê ¯ `u kiên (6.1) sao cho ham f dat cuc tiêu ( f → min). . ` ¯. . , , ` ` ´ Ðây la bai toan QHTT dang dac biêt, c´ thê giai bang cac . ¯˘ . . o ` ˘ ´ ,, ,, ,, , ´, , ´, , ´ ¯˜ . phuong phap da hoc o chuong truoc. Truoc khi xem x´ t cach giai e ´ , , ´, . ` ´ ` moi loai bai toan vân tai nay ta xem x´ t bai toan tông quat. . e ` ´ ´ , , ` ´ Bai toan vân tai tông quat . ´ , Cho m diêm A 1 , A 2 , ..., A m cung câp môt loai mat hang nao ¯ ´ . . ˘ . ` ` ´ ,, ,, ´, d´ c´ khôi luong tuong ung a 1 , a 2 , ..., a m , (a i ≥ 0, i = 1, m). C´ n ¯o o . o , , ,, , . , ` diêm tiêu thu B1 , B2 , ..., B n loai hang trên voi sô luong d` i hoi ¯ . ´ ´ . ¯o ,, , , b 1 , b 2 , ..., b n , ( b j ≥ 0, j = 1, n). Gia su ph´ vân chuyên môt don vi ı . . ¯ . ` `, ¯´ hang tu A i , ( i = 1, m) dên B j , ( j = 1, n) la c i j don vi tiên. ` ¯ , . ` , , ˜ , , ˜ . Hay lâp kê ´ hoach vân chuyên tu môi diêm cung câp toi diêm . . ` ¯ ´ ´, ¯ , tiêu thu bao nhiêu don vi hang h´ a sao cho . ¯ . ` o ´ , ´ ` ´ ´ ` - Cac noi cung câp hang giao hêt sô hang c´ . o , , ´ ¯ . ¯` - Cac diêm tiêu thu dêu nhân du hang yêu câu. . ¯ ` ` , , ´, , , - Tông cuoc ph´ vân chuyên la nho nhât. ı . ` ´ ´ ´ ˜ , , Ta thông nhât thuât ngu nhu sau: . , , ´ ` Noi cung câp hang A i la diêm phat thu i . ` ¯ ´ ´, , , . ` Noi tiêu thu hang B J la diêm thu thu j . ` ¯ ´, , Nguyên Hu,u Ðiên ˜ ˜ https://vietex.blog.fc2.com/
,, , 216 ` ´ Chuong 6. Bai toan vân tai . ´, . ` ´ X´ t gioi han bai toan e m n ai = bj i =1 j =1 , , , , ` ´ `˘ tông hang h´ a noi phat bang tông hang h´ a noi tiêu thu. Ðiêu kiên o o . ` . ` . ` ¯ nay goi la diê . ˘` `u kiên cân bang thu-phat.´ Ma trân C = ( c i j )m×n goi la ma trân cu,o,c ph´. . . ` . ´ ı , . ı ` Lâp mô h`nh bai toan vân tai. ´ . , , , ` ´ don vi hang h´ a cân chuyên tu A i dên B j . Tât nhiên Goi x i j la sô ¯ . . ` o ` ` ¯´ ´ ` x i j ≥ 0, i = 1, m va j = 1, n. , ,, ` ´ ¯ `, ¯´ Tông luong hang h´ a phat di tu A i dên moi B j la a i : . o . ` x i1 + x i2 + · · · + x in = a i , ( i = 1, m). , ,, ` ` `, . ` ˘ Tông luong hang thu vê B j tu moi A i , ( i = 1, m) bang b j : . x1 j + x2 j + · · · + xm j = b j , ( j = 1, n). , , ´, , , m n , ` Tông cuoc ph´ phai tra la ı ` ` ´ c i j x i j cang nho cang tôt. i =1 j =1 , ,, , ` ´ ´ . Mô h`nh bai toan vân tai duoc thiêt lâp nhu sau: ı . ¯ . m n f ( x) = c i j x i j → min (6.2) i =1 j =1   x i1 + x i2 + · · · + x in = a i , i = 1, m  (6.3)  D x1 j + x2 j + · · · + xm j = b j , j = 1, n (6.4)   x i j ≥ 0, ( i = 1, m, j = 1, n) (6.5)  , . ı . ˜ Ðinh ngh˜a 6.1. Ma trân x = ( x i j )m×n thoa man (6.3)-(6.5) goi la . ` , , ,o,ng an cua bai toan vân tai (BTVT); môt phu . ´ ` ´ . m n , ´ ` Nêu x lam cho f ( x) = ´ . ´ ı . ` c i j x i j dat gia tri nho nhât th` goi la ¯. i =1 j =1 , phu,o,ng an tôi u,u cua BTVT. ´ ´ , , , ` ´ ` o ¯˘ ´, ` . ` Bai toan vân tai c´ n × m ân va c´ m + n dang thuc rang buôc va . o , , ,, ` . ` ´ ` ˘ ´ la môt bai toan QHTT, nên ta c´ thê giai bang cac phuong phap da o ´ ¯˜ , , , ` ´ ´ ´ ¯˘ ` giai cho bai toan QHTT. Nhung do câu truc dac biêt cua bai toan . . ´ ,, , , , o ´ . ` ´ ¯o ` . ¯ı ´ ta c´ phuong phap gon va tôt hon, d´ la muc d´ch nghiên cuu cua ,, ` chuong nay. , Nguyên Hu,u Ðiên ˜ ˜ https://www.facebook.com/groups/vietex/
, , ´ ` ´ 6.2. T´nh chât cua bai toan vân tai ı . 217 , , ´ ` ´ 6.2. T´nh chât cua bai toan vân tai ı . , , ` , ` , ´, `, ` ´ ¯˘ Tu mô h`nh bai toan vân tai, ta dat dang vecto vê ân va cuoc ı . . . ph´: ı x = ( x11 , x12 , ..., x1n , x21 , x22 , ..., x2n , ......, xm1 , xm2 , ..., xmn )T , c = ( c 11 , c 12 , ..., c 1n , c 21 , c 22 , ..., c 2n , ......, c m1 , c m2 , ..., c mn )T , b = (a 1 , a 2 , ..., a m , b 1 , b 2 , ..., b n )T .   1 1 ... 1 0 0 ... 0 ... 0 0 ... 0    0 0 ... 0 1 1 ... 1 ... 0 0 ... 0      m   ... ... ... ...      0 0 ... 0 0 0 ... 0 ... 1 1 ... 1    A=  1 0 ... 0 1 0 ... 0 ... 1 0 ... 0         0 1 ... 0 0 1 ... 0 ... 0 1 ... 0      n  ... ... ... ...     0 0 ... 1 0 0 ... 1 ... 0 0 ... 1 , , , ` ´ ` . Bai toan vân tai dua vê dang matrân nhu sau: . ¯ . f ( x) = c T x → min Ax = b, x ≥ 0. ˜, , ` Co cua matrân A la ( m × n) × ( m + n). ´ Ky hiêu A 11 , A 12 , ..., A 1n , A 21 , A 22 , ...., A 2n , ...., A m1 , A m2 , ..., A mn . , , . `, ´ la cac vecto, côt cua A tu trai qua phai va d i , i = 1, 2, ..., m + n la cac ` ´ ` ` ´ , , , d` ng thu i cua A . vecto o ´ , , Ðinh ly 6.1. Ma trân hê rang buôc cua bai toan vân tai c´ hang la . ´ . . ` . ` ´ . o . ` m + n − 1, ngh˜a la rank A = m + n − 1. ı ` ´, ˜ ´ ` ˘ , ` , Chung minh. Dê thây rang vecto A i j la vecto côt c´ m + n thanh . o , ` ` ´ , ` ` ´ , ` ´ o ´ . ´ ` phân voi thanh phân thu i va m + j c´ gia tri 1, c` n tât ca cac thanh o ` ´ ` ˘ ˜ phân khac bang 0. Ta cung thây´ A = ( A 11 ...A 1n A 21 ...A 2n ...A m1 ...A mn ) ` ´, Ta cân chung minh rank A = m + n − 1. , Nguyên Hu,u Ðiên ˜ ˜ https://vietex.blog.fc2.com/
,, , 218 ` ´ Chuong 6. Bai toan vân tai . , X´ t m+ n−1 vecto A 1n , A 2n , ..., A mn , A 11 , A 12 , ..., A 1(n−1) . Ma trân e . `, ´ , ` tao nên tu cac vecto nay c´ dang . o .   1 0 ··· ··· 1 0 1 1 1 0 1 ··· 0 0 0 0 0  2  . . . .. . . . . . ··· . .. . . . . . . .. . . . 0 0 ··· 1 0 0 · · · 0 m  0 0 ··· 0 1 0 · · · 0 m + 1   0 0 ··· 0 0 1 · · · 0 m + 2   . . . .. . . . . ··· . .. . . . . . . . .. . . .   0 0 ··· 0 0 0 ··· 1 m+n−1 1 1 ··· 1 0 0 ··· 0 m , ´ ´ o ¯` Chu y m + n − 1 d` ng dâu tiên cua ma trân trên tao ra ma trân . . . ´ ´ ´, ` ˘ ` ı vuông câp m + n − 1 không suy biên (c´ dinh thuc bang 1) va v` ma o ¯. , ` ` trân nay la ma trân con cua A nên rank A ≥ m + n − 1. . , ,, ˘ ´ ` . ¯` Mat khac, gia su ta c´ m + n − 1 rang buôc dâu . o n xi j = a i , i = 1, 2, ..., m. j =1 m xi j = b j , j = 1, 2, ..., ( n − 1). i =1 Khi d´ suy ra ¯o m m n−1 m m n−1 x in = ai − xi j = ai − xi j i =1 i =1 j =1 i =1 i =1 j =1 m n−1 m m n−1 = ai − xi j = ai − b j = bn. i =1 j =1 i =1 i =1 j =1 , ` ´ ` ´ ı ` Nhu vây, rang buôc cuôi cung phu thuôc tuyên t´nh vao m + n − 1 . . . . ` . ¯` rang buôc dâu. Do d´ rank A ≤ m + n − 1. ¯o , , ´ ., ˘ ¯˜ Kêt hop hai kha nang da chı ra rank A = m + n − 1. , ,, ` ´ ` ` ´ Do bai toan vân tai la bai toan QHTT. Do d´ Phuong an x la . ¯o ´ ` ,, ,, , , , ,o,ng an co, so (phuong an cuc biên) khi va chı khi cac vecto côt phu ´ ´ . ` ´ . , , , ´ ´ ` ¯. . ´ ı A i j cua ma trân A ung voi x i j > 0 la dôc lâp tuyên t´nh. . , Nguyên Hu,u Ðiên ˜ ˜ https://www.facebook.com/groups/vietex/
, , ´ ` ´ 6.2. T´nh chât cua bai toan vân tai ı . 219 ,, ´ , ,, , Do rank A = m + n − 1, nên môt phuong an co so cua BTVT . ` ´ ` ` ` ,, ,, ´ , c´ nhiêu nhât la m + n − 1 thanh phân duong. Môt phuong an co o . ,, , ,, , , . ` ´ ´ ´ so cua BTVT goi la không suy biên nêu sô phân tu cua tâp hop ` . . ` ˘ . ` ´ ´ G = {( i, j ) : x i j > 0} bang m + n − 1, goi la suy biên nêu |G | < m + n − 1. ` ˜ ,, ´ ´ , ´, ˜, Sau nay môi phuong an ta viêt duoi dang ma trân co . . , ´, , ˜ m × n, x = ( x i j )m×n . Ta cung c´ ma trân cuoc ph´ co m × n, c = o . ı ˜ ( c i j ) m× n . , , ,, , ,, ` ´ ` ¯˜ Nhu vây, bai toan vân tai duoc coi la da cho nêu biêt vecto luong . . ¯ . ´ ´ . ´ , ,, ` phat a = (a 1 , a 2 , ..., a m ), vecto luong thu b = ( b 1 , b 2 , ..., b n ) va ma , ´, ,, ,. , ı ` ´, trân cuoc ph´ va tuong ung cac ân phai t`m: . ´ ı     c 11 c 12 · · · c 1n x11 x12 · · · x1n  c 21 c 22 · · · c 2n   x21 x22 · · · x2n  c= . x= .     . . . . . .  .  . . . . . .  .   . . . .  . . . . c m1 c m2 · · · c mn xm1 xm2 · · · xmn m n . ´ ` . ` Ðinh ly 6.2. Ðiêu kiên cân bang thu phat ˘ ´ ai = ` ¯ ` b j la diêu kiên . i =1 j =1 , , , cân va du dê bai toan vân tai c´ phu,o,ng an tôi u,u. ` ` ¯ ¯ ` ´ . o ´ ´ , ,, ´, ,, ´ ´ , Chung minh. (⇒) Gia su BTVT c´ phuong an tôi uu o x∗ = ( x∗j ). Vây i . n m x∗j = a i , ( i = 1, 2, ..., m) va i ` x∗j = b j , ( j = 1, 2, ..., n). i j =1 i =1 m m n n m n Do d´ ¯o ai = x∗j = i x∗j = i b j. i =1 i =1 j =1 j =1 i =1 j =1 ,, , ,, m n (⇐) Nguoc lai, gia su ta c´ . . o ` ´, ai = b j . Cân chung minh BTVT i =1 j =1 ,, ´ , , ,, ´ , c´ phuong an tô o ´i uu? Ngh˜a la chung minh phuong an cua bai toan ı ` ´ ` ´ ´ ˜ ` ` , ´, . . ˘ khac rông va ham muc tiêu bi chan duoi. . m n . . ¯˘ Thât vây, dat Q = . ai = b j > 0; x´ t ma trân e . i =1 j =1 ai b j ai b j x′ = , ( i = 1, 2, .., m; j = 1, 2, ..., n) thanh phân x′i j = ` ` . Q Q , Nguyên Hu,u Ðiên ˜ ˜ https://vietex.blog.fc2.com/
,, , 220 ` ´ Chuong 6. Bai toan vân tai . Ta c´ o n n ai b j n bj x′i j = = ai = a i , ( i = 1, 2, ..., m). j =1 j =1 Q j =1 Q m m ai b j m bj x′i j = = bj = b j , ( j = 1, 2, ..., n). i =1 i =1 Q i =1 Q ˜ Dê thây x′i j ≥ 0, ( i = 1, 2, ..., m; j = 1, 2, ..., n). Suy ra x′ la môt ´ ` . ,, ´ , ,, ´ phuong an cua BTVT; vây tâp phuong an khac rông. . . ´ ˜ e ` ´ ´ ` Ta x´ t bai toan bât ky x = ( x i j ) ( i = 1, 2, ..., m; j = 1, 2, ..., n). Tu`, n ¯ ` ` diêu kiên x i j ≥ 0 va . x i j = a i suy ra j =1 0 ≤ x i j ≤ a i , ( i = 1, 2, ..., m; j = 1, 2, ..., n). Vây . c i j xi j ≥ 0 ´ nêu c i j ≥ 0, c i j xi j ≥ c i j a i ´ nêu c i j < 0. Suy ra c i j x i j ≥ min{0, c i j a i }, ( i = 1, 2, ...m; j = 1, 2, .., n). m n m n Do d´ f ( x) = ¯o c i j xi j ≥ ` ˘ min{0, c i j a i } = const (hang). i =1 j =1 i =1 j =1 , ´, ¯o ` . ˘ Do d´ ham muc tiêu bi chan duoi. . . , , , ` ı ´ ´ 6.3. Bang vân tai va t´nh chât cua no . , , ˜, . ` ´ Du liêu cua bai toan vân tai la sô liêu cac tram phat . ` ´ . ´ . ´ , ` , ´, a = (a 1 , a 1 , ..., a m ), noi thu b = ( b 1 , b 2 , ..., b n ) va cuoc ph´ ı ,, , , ` ´ c = ( c i j )m×n va phuong an vân chuyên x = ( x i j )m×n . Ta xây dung . . , , o ` bang m + 1 d` ng va n + 1 côt nhu sau: . , , , ˜ ` ¯˘ ´ Môi hang dac trung cho 1 diêm phat; môi côt dac trung cho môt . ¯ ˜ . ¯˘ . , . , ` ` ` . ¯` diêm thu. Hang dâu tiên va côt dâu tiên ghi cac kha nang thu va ¯ ¯ ´ ˘ ` , , , ˘ ´ ` o . kha nang cung câp cua BTVT. Phân c` n lai tru côt dâu va hang dâu ` . ¯` ` ` ¯` , , , . ` ` goi la phân ch´nh cua bang vân tai. ı . , , ` ˘ ` ` . ` ¯˘ Ô nam trên hang i va côt j la dac trung tuyên duong vân chuyên . ´ ¯ ,`, . `, ¯´ o ´ ,, ı o ´ tu A i dên B j c´ cuoc ph´ c i j (g´ c bên trai ph´a trên) va sô luong cân ı ` ´ , ., ` , , , , ´, ı ¯ ` t`m dê chuyên la x i j (ghi g´ c bên phai ph´a duoi). o ı , Nguyên Hu,u Ðiên ˜ ˜ https://www.facebook.com/groups/vietex/
, , , . ` ı ´ 6.3. Bang vân tai va t´nh chât cua n´ o 221 bj b1 b2 · · · b j ··· bn ai c 11 c 12 ··· c1 j ··· c 1n a1 x11 x12 · · · x1 j · · · x1n c 21 c 22 ··· c2 j ··· c 2n a2 x21 x22 · · · x2 j · · · x2n . . . . .. .. .. .. . . .. . .. . . . . . .. .. . .. . . c i1 c i2 · · · ci j · · · c in ai x i1 x i2 · · · xi j · · · x in . . . . .. .. .. . .. . .. . .. . . . . . .. .. . .. . . c m1 c m2 · · · cm j · · · c mn am xm1 xm2 · · · xm j · · · xmn , , , , Bang 6.1: Bang vân tai tông quat . ´ bj 130 160 120 140 ai ` ´ V´ du 6.2. Bai toan V´ du 6.1 ı . ı . 20 18 22 25 c´ a = (170, 200, 180), o 170 x11 x12 x13 x14 b =(130, 160, 120, 140) va` 20 18 22 25  15 25 30 15 c = 15 25 30 15 200 x21 x22 x23 x24 45 30 40 35 45 30 40 35 , , 180 x31 x32 x33 x34 Ta c´ bang vân tai o . , , , ´ . ´ ` Ta ky hiêu cac ô phân ch´nh cua bang vân tai la ı . ` U = {( i, j ) : i = 1, m, j = 1, n}. ˜, ´, . ` ˜, Ðinh ngh˜a 6.2. Nhung ô ( i, j ) ∈ U voi x i j > 0 goi la nhung ô chon . ı . ´, ´, ,, ´ ˜, o . . ` ´ ung voi phuong an x. Nhung ô c` n lai goi la cac ô loai.. ,, , , , ı . . ´ . o ´ . ` V´ du 6.3. Môt phuong an phân bô bang vân tai c´ cac ô chon va ` ´ không chon trong bai toan v´ du trên. . ı . , Nguyên Hu,u Ðiên ˜ ˜ https://vietex.blog.fc2.com/
,, , 222 ` ´ Chuong 6. Bai toan vân tai . bj 130 160 120 140 ai 20 18 22 25 170 130 40 15 25 30 15 200 120 80 45 30 40 35 180 40 140 , , . ` ¯˘ . ´ ¯ ,`, ` ` Ô chon la dac trung tuyên duong cân chuyên hang h´ a di qua. o ¯ ˜ ´ Ðinh ngh˜a 6.3. Môt day cac ô {( i 1 , j 1 ), ( i 2 , j 2 ), ...( i k , j k )} ⊂ U ma . ı . ` , ` ´ hai ô (va không qua 2 ô) liên tiê ˜ ` ´p cua day luôn nam trên cung môt ˘ ` . ` ˘ ` . . . ` hang hoac cung môt côt goi la dây truyê . `n. V´ du 6.4. H`nh 6.1 ı . ı bj bj 60 20 70 60 60 70 ai ai 6 4 3 6 4 3 50 20 30 50 20 30 5 1 2 5 1 2 60 20 40 90 50 40 3 7 8 3 7 8 40 40 50 10 40 (a) (b) ` ´ H`nh 6.1: Dây chuyên cac ô ı ˜ ´ ` (a) Day cac ô {(1, 2), (1, 3), (2, 3), (2, 1), (3, 1)} tao ra môt dây chuyên. . . ˜ ´ (b) Day cac ô {(3, 2), (1, 2), (1, 3), (2, 3), (2, 1), (3, 1)} tao ra môt dây . . ` chuyên. . ı . ` ı . ` . o ˘ Ðinh ngh˜a 6.4. Môt dây truyên kh´ p k´n goi la môt v` ng (hoac e . môt chu tr`nh). . ı V´ du 6.5. H`nh 6.2 ı . ı , Nguyên Hu,u Ðiên ˜ ˜ https://www.facebook.com/groups/vietex/
, , , . ` ı ´ 6.3. Bang vân tai va t´nh chât cua n´ o 223 bj bj 60 20 70 60 60 70 ai ai 6 4 3 6 4 3 50 20 30 50 20 30 5 1 2 5 1 2 60 20 40 90 50 40 3 7 8 3 7 8 40 20 20 50 10 40 (a) (b) ı ı ´ H`nh 6.2: Chu tr`nh cac ô (môt v` ng). . o ˜ ´ ` (a) Day cac ô {(1, 1), (1, 3), (2, 3), (2, 1), (1, 1)} tao thanh v` ng. . o ˜ ´ ` (b) Day cac ô {(3, 2), (1, 2), (1, 3), (2, 3), (2, 1), (3, 1)} tao thanh v` ng. . o , , ` ´ ı Môt vong trong bang vân tai co t´nh chât sau: . . ´ ` ˘ ` ` - Hai ô canh nhau nam trên cung môt hang hoac môt côt; . . ˘ . . . ` ` ˘ ` . ` ˘ - Không c´ ba ô nao nam trên cung môt hang hoac môt côt; o . . . ` , ¯` ˘ ` ` ˘ ` . ´ ´ ` - Ô dâu tiên nam trên cung hang hoac cung côt voi ô cuôi cung. . , ,, , ´ , , , ` . . ` ¯o Gia su L ⊂ U la môt tâp hop cac ô nao d´ cua bang vân tai. . . , . , ı o `˘ ´ o ´ `, ´ Ðinh ngh˜a 6.5. Ta n´ i rang L chu,a v` ng nêu tu cac ô cua L ta , ,, ´ ,, ,, c´ thê xây dung duoc ´t nhât 1 v` ng. Nguoc lai L duoc goi la không o . ¯ . ı o . . ¯ . . ` chu,a v` ng. ´ o , V´ du 6.6. Tâp hop ı . . . L = {(1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (3, 1), (3, 2), (3, 4)} c´ v` ng. o o ˜ o , , , . ´ ´ Ðinh ly 6.3. Nêu trong môi d` ng va côt cua bang vân tai hoac ` . . ˘ . , , ,a v` ng. ` ˘ oı . ´ ı ´ không c´ ô nao cua L hoac c´ ´t nhât hai ô cua L th` L chu o o ´, ´ ¯ ` `, . ˘ ` ¯o Chung minh. Bat dâu tu môt ô nao d´ ( i 1 , j 1 ) ∈ L. V` trên d` ng i 1 ı o ´ ˜, , , (hoac j 1 ) c´ ´t nhât môt ô khac nua cua L: ( i 1 , j 2 ) ta chuyên theo ˘ . oı . ´ , , o ˘ . . ¯´ ¯o ` oı ´ d` ng i 1 (hoac côt j 1 ) dên ô d´ . Tu ô nay ( i 1 , j 2 ) phai c´ ´t nhât môt ` . ,, ,, ´ ˘ ` ô khac o côt (hoac o hang): ( i 2 , j 2 ) ∈ L. . . , Nguyên Hu,u Ðiên ˜ ˜ https://vietex.blog.fc2.com/
,, , 224 ` ´ Chuong 6. Bai toan vân tai . Bj 60 55 50 30 Ai 4 1 3 2 80 40 30 10 6 4 5 3 55 35 20 3 2 4 6 60 25 15 20 , H`nh 6.3: V` ng trong tâp hop ô L. ı o . . , ´ . . ´, ´ ˘ Tiêp tuc lai chuyên theo d` ng i 2 toi ô khac thuôc L,... lap lai o . . . , , ¯` ´ ı ` ` nhu ô ban dâu. Qua tr`nh nay không thê k´ o dai vô han v` L ⊂ U e . ı ˜, . ´ ´ . ´ ` ¯o . ¯˜ ¯ huu han sô ô. Ðên môt luc nao d´ ta quay lai ô da di qua. , , , ˜ ı ´ V´ du 6.6 L thoa man t´nh chât cua dinh ly trên va c´ thê c´ ı . ¯. ´ ` o o ` o ´ , ´ ı ´ ı nhiêu v` ng. Khai niêm v` ng liên quan toi t´nh dôc lâp tuyên t´nh o ¯. . , , ,. , cua vecto côt A i j cua ma trân A trong bai toan vân tai. Ta dinh . . ` ´ . ¯. ngh˜a. ı , , , ,, . . ´ Ðinh ngh˜a 6.6. Tâp L ⊂ U cac ô cua bang vân tai duoc goi la ı . ¯ . . ` ´ ı ´ ı ´ . , ´ , dôc lâp tuyên t´nh (phu thuôc tuyên t´nh) nêu tâp hop cac vecto ¯. . . . . , , . . ` { A i j : ( i, j ) ∈ L} cua ma trân A lâp thanh hê vecto dôc lâp tuyên t´nh . ¯. . ´ ı , ´ ı (hê vec to phu thuôc tuyên t´nh). . . . , , , Ðinh ly 6.4. Tâp ho,p L ⊂ U cac ô cua bang vân tai la dôc lâp tuyên . ´ . . ´ . ` ¯. . ´ , ,a v` ng. t´nh khi va chı khi n´ không chu o ı ` o ´ , ,, ´ ` ¯. . ` ´, Chu,ng minh. (⇒) Gia su L la dôc lâp tuyên t´nh. Cân chung minh ´ ı , ,, ´, o ,, ´, o ` L không chua v` ng? Gia su nguoc lai, L chua v` ng va V la môt . . ` . , v` ng trong n´ . Ðiê o o `n vao cac ô cua v` ng sô +θ va −θ xen k˜ nhau, ` ´ o ´ ` e ´ ´ o cac ô khac v` ng diê ¯ `n sô 0. ´ Nêu cho θ = 1, rôi công theo cac hang hoac công theo cac côt th` ´ ` . ´ ` ˘ . . ´ . ı ,, , ,, ¯` ¯ . ´ ´ ` ` . ¯o ı ` dêu duoc kêt qua 0 trên cac hang va côt d´ . Ngh˜a la ta nhân duoc . ¯ . , môt vecto 0. . `, ´, Bây gio ta nhân voi 1 ô c´ +θ va −1 ô c´ −θ . Cac côt c` n lai nhân o ` o ´ . o . , , , , ı . . . ´ ´ . ` 0 th` tao ra hê vecto côt A i j cua A ung voi ( i, j ) ∈ L lâp thanh hê vec . , Nguyên Hu,u Ðiên ˜ ˜ https://www.facebook.com/groups/vietex/
, , , . ` ı 6.3. Bang vân tai va t´nh chât cua n´ ´ o 225 , , . . ´ ı ´ ´, ´ ` ¯. . ´ ı to phu thuôc tuyên t´nh trai voi gia thiêt L la dôc lâp tuyên t´nh. , ,, , , ´ ` ´ (⇐) Gia su L không chua v` ng, cân chung minh L dôc lâp o ¯. . ´n t´nh. tuyê ı , , ,, . . . . . . . ´ ı Thât vây, gia su nguoc lai, L phu thuôc tuyên t´nh, khi d´ ¯o , ` tôn tai bô sô λ i j , ( i, j ) ∈ L không dông thoi bang không sao cho ` . . ´ ¯` ` ˘ λ i j A i j = 0. (i, j)∈L ,, , , , ¯ ` ` ´ ´, Nêu ta diên λ i j , ( i, j ) ∈ L vao cac ô tuong ung cua bang vân tai, ´ . o ´ ˜ ´ `˘ ı . ´ ` ˘ ´ . c` n cac chô khac bang 0, th` khi công cac hang hoac theo cac côt th` . ı ,, , ¯` dêu nhân duoc vecto 0. . ¯ . Ky hiêu K = {( i, j ) : λ i j ̸= 0}. ´ . , , ˜ ` ˘ ˜ . ¯` ` ˘ Do tông cua môi hang hoac môi côt dêu bang 0, nên môi d` ng . ˜ o , , , ´ ` ˜ . ˘ ´ ` ˘ ´ ´ ` va môi côt hoac không chua ô nao cua K hoac chua ıt nhât la 2 ô . . , , ´ ` cua K . Theo dinh ly trên suy ra K phai c´ v` ng; ma K ⊂ L suy ra L ¯. o o , ´ c´ v` ng vô ly vo o o ´,i gia thiêt. ´ , , , ,, ´ . ` . , ´, ´, Ky hiêu G ( x) la tâp hop ô chon cua bang vân tai tuong ung voi . . . ,, ´ phuong an x, G ( x) = {( i, j ) ∈ U : x i j > 0}. , , , Hê qua 6.1. Phu,o,ng an x = ( x i j )m×n cua bai toan vân tai la phu,o,ng . ´ ` ´ . ` an co ´ , so, châp nhân du,o,c khi va chı, khi tâp cac ô chon G ( x) tu,o,ng , ´ ` ´ . ¯ . . . ´ u ,ng vo,i n´ không chu,a v` ng. ´ o ´ o , ´, ´ `˘ ,, ´ Chung minh.. Ta biêt rang phuong an x = ( x i j )m×n cua BTVT la ` ,, , ,, ,, , , ´ phuong an co so châ ´p nhân duoc khi va chı khi hê cac vecto côt . ¯ . ` . ´ . , , cua A u´,ng voi cac thanh phân khac không cua chung lâp thanh hê ´, ´ ` ` ´ ´ . ` . ,, ,, ´, ´, ´n t´nh. Ðinh ly 6.4 tuong duong voi G ( x) không chua ´ dôc lâp tuyê ı ¯. . . ¯ v` ng. o , ,, ´ ,, ´ V` rank A = m + n − 1 nên co so châp nhân duoc không suy biên ı . ¯ . ,`, , , ´ ´ ` ´ nêu sô ô chon la m + n − 1. Trong truong hop suy biên ta c´ thê . . o , ,, , ,, ,, ´ ´ ´ bô sung môt sô ô loai sao cho phuong an co so châp nhân duoc c´ . . . ¯ . o m + n − 1 ô chon. . , Nguyên Hu,u Ðiên ˜ ˜ https://vietex.blog.fc2.com/
,, , 226 ` ´ Chuong 6. Bai toan vân tai . , , , , , Hê qua 6.2. Gia su, ta c´ bang vân tai c´ m hang va n côt va L la . o . o ` ` . `, ` , , , , ,a v` ng. Gia su, ô . . , `, môt tâp gôm m + n − 1 ô cua bang vân tai không chu o . , ´ ( i, j ) cua bang không thuôc L. Nêu ta bô xung ô ( i, j ) vao L du,o,c L 1 . ´ ` ¯ . , ,a v` ng duy nhât V . Nêu loai khoi L môt ô tuy y cua v` ng , th` L 1 chu o ı ´ ´ ´ . , 1 . ` ´ o , ,o,c L th` L lai gôm m + n − 1 ô cua bang không chu,a v` ng. V du .¯ 2 ı 2 . ` ´ o bj b1 b2 b3 b4 ai a1 (1, 1) (1, 2) (1, 3) (1, 4) a2 (2, 3) a2 (3, 2) a1 ∗ (4, 3) (4, 4) , , ´, o ´, o H`nh 6.4: Bang vân tai không chua v` ng L, chua v` ng L 1 . ı . , ` . ` . ` V´ du 6.7. Cho bang 4 hang, 4 côt va tâp L gôm 4 + 4 − 1 = 7 ô chon ı . . ´, ´ không chua v` ng dâu X , Ô (4, 4) ̸∈ L (H`nh 6.4). o ı L = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 3), (3, 2), (4, 3)}. L 1 = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 3), (3, 2), (4, 3), (4, 4)}. ¯o ´, o Khi d´ L 1 chua v` ng V = {(1, 3), (1, 4), (4, 4), (4, 3)}. V` V la v` ng ı o , ´ ı e ´ o duy nhât bo di 1 ô th` s˜ mât v` ng nên L 2 c´ 7 ô. ¯ o , , , . ` 6.4. Xây dung vong trong bang vân tai . ,, , , ` ´ ` ´ Cho x = ( x i j )m×n la môt phuong an cua bai toan vân tai. Lâp . . . , , ,, ´, bang vân tai tuong ung voi x. . ´, ´ . ´ ´, o ` ,, ´ • Nêu tâp cac ô chon G ( x) không chua v` ng th` x la phuong an co . ı , ,, ,, ´ so châp nhân duoc. . ¯ . , , ´ ´, o ´ ´ ˜, o • Nêu G ( x) chua v` ng th` ta phai t`m cach pha vo v` ng trong x dê ı ı ¯ , ,, ´ ´, ´, o xây dung phuong an moi không chua v` ng. . , Nguyên Hu,u Ðiên ˜ ˜ https://www.facebook.com/groups/vietex/
, , , 6.4. Xây dung v` ng trong bang vân tai . o . 227 , , , , Ðinh ly 6.5. Gia su, x la 1 phu,o,ng an cua bai toan vân tai va G ( x) . ´ ` ´ ` ´ . , ` ´,a v` ng. Khi d´ tu, phu,o,ng an x ta luôn c´ thê, chuyên sang môt chu o ¯o ` ´ o . phu ,o,ng an mo,i x′ không tôi ho,n x (tu,c la f ( x′ ) ≤ f ( x)) vo,i tâp cac ô ´ ´ ` ´ ` ´ . ´ chon G ( x′ ) không chu,a v` ng. . ´ o , ,, ´, ´, o ´ ´ ´ Chung minh.. Gia su G ( x) chua v` ng V . Ðanh dâu cac ô trong V ,, ´ ` ` boi dâu + va − xen k˜ nhau sao cho không c´ 2 ô nao canh nhau e o . ` ´ . ` . ´ ,, ´ ´u. Ky hiêu V + la tâp cac ô trong V duoc danh dâu công. Ky ´ . ´ cung dâ ¯ . ¯ − ,, ´ , , . ` . ´ hiêu V la tâp cac ô trong V duoc danh dâ ¯ . ¯ ´u tru. Không mât tông ` ´ , ´ o quat c´ thê coi ci j ≤ ci j (6.6) (i, j)∈V + (i, j)∈V − , , ´, Xây dung vecto x′ = ( x′i j ) theo công thuc .   x i j + θ nêu ( i, j ) ∈ V +  ´  x′i j = x i j − θ nêu ( i, j ) ∈ V − ´ (6.7)  x ´ nêu ( i, j ) ̸∈ V  ij trong d´ θ = min{ x i j : ( i, j ) ∈ V − }. ¯o o ` ´, R˜ rang x′i j ≥ 0 voi moi i, j va do V la v` ng va (6.7) ta c´ . ` ` o ` o n n x′i j = x i j = a i , ( i = 1, 2, ..., m), j =1 j =1 m m x′i j = x i j = b j , ( j = 1, 2, ..., n). i =1 i =1 ,, ´ , , Vây x′ la phuong an cua bai toan vân tai. . ` ` ´ . Ta lai c´ . o m n m n f ( x′ ) = c i j x′i j = c i j xi j + θ ci j − ci j i =1 j =1 i =1 j =1 (i, j)∈V + (i, j)∈V − m n ≤ c i j x i j = f ( x). i =1 j =1 `, Tu (6.7) va cach xac dinh θ nên s˜ c´ ´t nhât môt ô ( i 0 , j 0 ) ∈ V − ` ´ ´ ¯. e oı ´ . , ¯ ¯o ′ ` − e ` . ˜, dê θ = x i 0 j 0 , do d´ x i 0 j 0 = 0 va ô ( i 0 , j 0 ) ∈ V s˜ không la ô chon nua. ´, o Nên G ( x′ ) không chu v` ng V nua. ˜, , Nguyên Hu,u Ðiên ˜ ˜ https://vietex.blog.fc2.com/
,, , 228 ` ´ Chuong 6. Bai toan vân tai . ´ ˜ o ´, o ı ` Nêu G ( x′ ) vân c` n chua v` ng th` thay x bang x′ va lam lai thao ˘ ` ` . ´ `, ˜, , ´, ,, ´n phuong an không tôi ´ ` tac vua nêu trên th` sau huu han buoc dê ı . ¯ , ,, ´ ´, ¯˜ ` . hon phuong an da qua va tâp ô chon d´ không chua v` ng. . ¯o o ,, , , , , ´ ` ´ ¯˜ V´ du 6.8. Môt phuong an cua bai toan vân tai da cho nhu bang ı . . . , ´, ` ´, o duoi dây va chua v` ng ¯ bj 70 50 40 40 ai 2 1 3 4 50 50 3 2 1 2 75 55 20 3 5 4 1 25 15 10 2 2 3 6 50 30 20 , ,, ´ ´, ´ , Hay xây dung môt phuong an moi x1 c´ ham muc tiêu tôt hon? ˜ . . o ` . , `, ,, ´ Loi giai. Phuong an da cho ¯˜ ` ` x = (0, 50, 0, 55, 0, 0, 20, 15, 0, 10, 0, 0, 0, 30, 20) va ham chi ph´ ı f ( x) = 50 × 1 + 55 × 3 + 20 × 2 + 15 × 3 + 10 × 4 + 30 × 3 + 20 × 6 = 550. o o ´ Ta c´ v` ng cac ô chon . V = {(2, 1), (2, 4), (4, 4), (3, 4), (3, 3), (3, 1)} V + = {(2, 4), (3, 4), (3, 1)}, V − = {(2, 1), (4, 4), (3, 3)}, ,, ´, min{ x i j : ( i, j ) ∈ V − } = 10 = x33 . T´nh phuong an moi x12 = 50, x21 = ı ´ ,, ´ 45, x24 = 30, x44 = 10, x43 = 40, x33 = 0, x31 = 25. Ta c´ phuong an o ´, moi , Nguyên Hu,u Ðiên ˜ ˜ https://www.facebook.com/groups/vietex/
, , , 6.4. Xây dung v` ng trong bang vân tai . o . 229 bj 70 50 40 40 ai 2 1 3 4 50 50 3 2 1 2 75 45 30 3 5 4 1 25 25 2 2 3 6 50 40 10 x1 = (0, 50, 0, 45, 0, 0, 30, 25, 0, 0, 0, 0, 0, 40, 10) va ham chi ph´ ` ` ı 1 ˜ ´ f ( x ) = 50 × 1 + 45 × 3 + 30 × 2 + 25 × 3 + 40 × 3 + 10 × 6 = 500. Dê thây ` ,, ´ , rang Phuong an x1 không chua v` ng, va f ( x1 ) < f ( x). ˘ ´ o ` , , , Ðinh ly 6.6. Gia su, m, n ≥ 2. Khi d´ tâp L gôm m + n ô bât k` cua . ´ ¯o . ` ´ y , , bang vân tai luôn chu,a v` ng. . ´ o , ´, Chung minh.. V` rank A = m + n − 1 nên tâp L gôm m + n ô cua ı . ` , , . . . ´ ı bang vân tai th` phu thuôc tuyên t´nh, do d´ theo dinh ly 6.4 n´ ı ¯o ¯. ´ o , , , , , chu o ´ ` ´ v` ng. Ta chung minh bang xây dung dinh ly nay dê suy ra thu ˘ . ¯. ´ ` ¯ , , , , . . `, tuc xây dung v` ng tu m + n cua bang vân tai. o . , Khi m = n = 2 th` n + m = 4 ô cua n´ lâp thanh môt v` ng. ı o . ` . o ´, Khi m > 2, n > 2 ta chung minh bang phuong phap quy nap theo` ˘ ,, ´ . , ` . tông d` ng va côt k = m + n. o , ,, ¯. ´ ¯´ ´, Gia su dinh ly dung voi k = m + n − 1, ta cân chung minh n´ ` ´, o ´, ,`, , ¯´ dung voi k = m + n: C´ 2 truong hop. o . Tru `,o,ng ho,p 1. Trong sô m + n ô c´ môt ô nao d´ nam 1 m`nh ´ o . ` ¯o ` ˘ ı . , ` ˘ ˘ . ´, trên 1 hang hoac trên 1 côt. Khi d´ loai bo d` ng hoac côt chua ô d´ . ., . ¯o . o . ¯o , ` o . ` ´ Phân c` n lai chı c´ m + n − 1 ô va ta ap dung gia thiêt quy nap. Ðinh o . ´ . . ´ ¯ . ,, ´, ly duoc chung minh. , , Tru,o,ng ho,p 2. Trong môi d` ng va côt cua bang hoac không chua ` . ˜ o ` . ˘ . ´, , , ˘ . ´, ı ´ ô nao cua L hoac chua ´t nhât 2 ô cua L, theo dinh ly 6.3 tâp L chua ` ¯. ´ . ´, ´ ˜ ,, ´, v` ng. Ðinh ly cung duoc chung minh. o . ¯ . , Nguyên Hu,u Ðiên ˜ ˜ https://vietex.blog.fc2.com/
,, , 230 ` ´ Chuong 6. Bai toan vân tai . , `, ¯. ´ , `, . ` Tu dinh ly 6.6 ta c´ thu tuc xây dung v` ng tu tâp L gôm m + n o . . o , , , ô cua bang vân tai . , , , , , ´ ´ o ` . ´, (1) X´ a bo khoi bang vân tai tât ca cac d` ng va côt chua không qua o . ´ , , ´ ˘ . ´ ¯´ ˜ o ` . 1 ô cua L. Lap lai thao tac cho dên khi môi d` ng va côt chua ıt ´ , . ´ nhât 2 ô cua L. , , , , `, ,, ¯ . o o . , (2) Tu bang thu duoc v` ng c´ thê xây dung theo thu tuc mô ta trong . ´ dinh ly 6.3. ¯. , , `, ´ ,, ¯ . ¯´ ´ V´ du 6.9. Xây dung v` ng tu cac ô duoc danh dâu ı . . o trong bang sau: B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 A1 A2 A3 A4 , , , ´ ¯´ ´ , ´ . ı ˜ . 1. Bo cac danh dâu o cac côt B1 , B2 , B4 , B5 , B6 , B7 v` môi côt chı c´ o . ¯´ ´ môt danh dâu . B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 A1 A2 A3 A4 , , ,, ¯´ ´ ` 2. Bo danh dâu hang 2 v` chı c` n môt ı o . , ta duoc ¯ . B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 A1 A2 A3 A4 , , ,, . ¯´ ´ . 3. Lai bo danh dâu côt 3 v` chı c` n môt ı o . , ta duoc ¯ . , Nguyên Hu,u Ðiên ˜ ˜ https://www.facebook.com/groups/vietex/
,, ´ ´ ´ 6.5. T`m phuong an xuât phat ı 231 B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 A1 A2 A3 A4 ,, Ta duoc v` ng V = {(1, 8), (1, 9), (4, 9), (4, 10), (3, 10), (3, 8)}. ¯ . o ,, ´ ´ ´ 6.5. T`m phuong an xuât phat ı ,, , ,, , , ,, ´ ` T`m phuong an co so cua bai toan vân tai c´ rât nhiêu phuong ı ´ . o ´ ` , , ´ ` phap hiêu qua va nhanh hon trong bai toan quy hoach tuyên t´nh . ` ´ . ´ ı n´ i chung. o , , ,, ´, 1. Lâp bang vân tai voi b = ( b 1 , b 2 , ..., b n ) o hang thu nhât, . . ` ´, ´ ,, , , ´ ´ ´ a = (a 1 , a 2 , ..., a m ) o côt thu nhât. Cac gia chi ph´ diên vao tung ô . ´ ı ¯ ` ` ` ´ ,, ( i, j ) g´ c trên bên trai tuong ung gia tri c i j . o ´, ´ . ´ ` ,, ´ , ,, ´ ´ , 2. Khi tiên hanh t`m phuong an co so xuât phat ta thuc hiên: ı . . ´ Nguyên tac phân phôi tôi da ˘ ´ ´ ¯ , ,, ,, ´ ` Gia su phân phôi vao ô ( i, j ). Ta c´ luong hang tôi da o . ` ´ ¯ , , ¯o ¯ ` x i j = min{a i , b j }. Sau d´ diêu chınh lai yêu câu nhu sau: . `  a i   loai d` ng i, b′j = b j − a i ; . o x i j = min{a i , b j } = b j loai côt j, a′i = a i − b j ; . . (6.8)  ` .  a = b i j loai d` ng i va côt j . . o , ˜ ` , , ´, ´ ` ´ Nhu vây, sau môi lân thuc hiên k´ch thuoc cac ô cân phân phôi . . . ı , . . ` ` thu hep lai va trong phân bang c` n lai ta lai tiên hanh chon ô o . . ´ ` . , ,, , phân phô ` ¯ ´i va diêu chınh yêu câu tuong ung,... cho dên khi tât ` ` ´ ¯´ ´ , , , ` ´ ,, ` o ` . ˜ ca yêu câu d` ng va côt thoa man (tuc la, cac khôi luong hang da ´ ´ ., ` ¯˜ ,, ´ ,, , duoc lây di hê ¯ . ¯ ´t o tram phat va thu du theo yêu câu cua cac tram . ´ ` ¯ ` ´ . ,, ´i goi la cac ô loai, c´ x i j = 0. Do thu). Cac ô không duoc phân phô . ` ´ ´ ¯ . . o ,, ´ , d´ ta c´ môt phuong an vân tai. ¯o o . . , ´ ´ ¯´ ` ´ Trong thuc tê ta danh dâu (-) vao cac hang va cac côt da bi loai . ` ` ´ . ¯˜ . . không phân phô ` ´ ´i vao cac ô d´ nua. ¯o ˜, Ðinh ly 6.7. Môt phu,o,ng an thu,c hiên theo "Nguyên tac phân . ´ . ´ . . ´ ˘ , ,o,ng an co, so, (phu,o,ng an cu,c biên). ´ ´ ¯ phôi tôi da" la môt phu ` . ´ ´ . , Nguyên Hu,u Ðiên ˜ ˜ https://vietex.blog.fc2.com/
,, , 232 ` ´ Chuong 6. Bai toan vân tai . , ,, , ´, ,, ´ ,, Chung minh.. Gia su phuong an thu duoc không phai la ¯ . ` ,, ´ , ,, ´ cac ô chon tôn tai v` ng ` . o phuong an co so. Ngh˜a la trong sô ´ ı ` . ( i 1 , j 1 ), ( i 1 , j 2 ), ( i 2 , j 2 ), ( i 2 , j 3 ) . . . , ( i k−1 , j k ), ( i k , j k )( i k , j 1 ). , , ` ´ ´ Ta x´ t ( i 1 , j 1 ). V` x i 1 , j 1 > 0 la kêt qua cua nguyên ly phân phôi e ı ´ ´ ¯ tôi da, nên ta c´ o , ´ • Nêu a i 1 < b j 1 , ta c´ d` ng i 1 bi loai, do d´ không thê phân phôi o o . . ¯o ´ ` ı ` vao ( i 1 , J2 ). Ngh˜a la x i 1 j 2 = 0. Vô ly. ´ , ´ • Nêu a i 1 > b j 1 , ta c´ d` ng j 1 bi loai, do d´ không thê phân phôi o o . . ¯o ´ ` ı ` vao ( i k , J1 ). Ngh˜a la x i k j 2 = 0. Vô ly. ´ , ´ o o ` . • Nêu a i 1 = b j 1 , ta c´ d` ng i 1 va côt j 1 bi loai, do d´ không thê . . ¯o ´ ` ` ı ` phân phôi vao ( i 1 , j 2 ) va ( i k , j 1 ). Ngh˜a la x i 1 j 2 = x i k j 1 = 0. Vô ´ ly ,`, , ˜ . . . ¯` o ¯ ` T´ m lai trong moi truong hop ta dêu c´ diêu mâu thuân. o , ´ ˘ ´ ´ ¯ ` ´ ´, ´ ¯. ´ Dua theo nguyên tac phân phôi tôi da va cach thuc xac dinh cac . , ,, ´i, ta c´ cac phuong phap phân phôi sau dây. ´ ô uu tiên phân phô o ´ ´ ¯ ,, ,, , ´ ´ ´ 6.5.1. Phuong phap cuoc ph´ nho nhât ı , Theo phu,o,ng phap nay ta u,u tiên phân vao ô c´ cu,o,c ph´ nho ´ ` ` o ´ ı , ´ nhât trên toan bang. ` , , ´ ¯ ` `, ˘ o ´ ,, ı ´ ` , 1. Bat dâu tu ô c´ cuoc ph´ nho nhât trên toan bang:Thuc hiên . . nguyên tac´ phân phôi tôi da. ˘ ´ ´ ¯ ˘ . ´ ı ´ ´ 2. Lap lai qua tr`nh cho cac ô c` n lai theo nguyên tac phân phôi . o . ˘ ´ , ,, , ´ ¯ ¯´ ´ ` ´ tôi da dên khi yêu câu cua tram phat, tram thu duoc thoa man. . . ¯ . ˜ ,, ´ ,, ` ˘ ,, ´ ` ` ,, ´ , ,, Phuong an thu duoc bang phuong phap nay la phuong an co so. ¯ . , , ´ ` ˜ o ´ ´ ´ Cach nay cung c´ không qua m + n − 1 khac không, nêu chua du ¯ , ` ta thêm ô 0 vao cho du m + n − 1. ¯ , Nguyên Hu,u Ðiên ˜ ˜ https://www.facebook.com/groups/vietex/
,, ´ ´ ´ 6.5. T`m phuong an xuât phat ı 233 ´ bj ˜ V´ du 6.10. Hay phân phôi ı . 30 40 50 60 ,, ´ , ´, ai theo phuong phap cuoc ph´ ı , , 1 5 7 2 ´ ` ´ nho nhât bai toan vân tai sô . ´ , , ´, 80 liêu nhu v´ du truoc . ı . 5 7 4 9 45 12 2 3 6 55 , `, ´ ` Loi giai. Ta tiên hanh theo cac buoc sau ´ , ´, , ´, ´ bj 1. Ô (1,1) c´ cuoc ph´ thâp o ı 30 40 50 60 ´ nhât nên ta phân vao ô nay ` ` ai ,, ` ´ ` 1 5 7 2 môt luong nhiêu nhât la 30. . . Khi d´ : ¯o 50 80 30 , , 5 7 4 9 ´ - Tram thu thu nhât nhân du . ´ . ¯ ` hang, x´ a côt 1. o . 45 ´ ´ , ´ o , 12 2 3 6 - Tram phat thu nhât c` n du . 55 ´ 50, ta ghi nhap 50. ´ 2. Trong cac ô c` n lai, c´ hai o . o 10 ` , ´, bj o ` ô: (1,4) va (3,2) c´ cung cuoc 30 40 50 60 ph´ thâ ı ´p nhât la 2. Tuy nhiên ´ ` ai ´ nêu chon ô (1,4) lam ô chon ` 1 5 7 2 . . ,, ` ` 50 80 30 50 th` luong hang phân qua ô nay ı . ` ` , 5 7 4 9 la 50 s˜ nhiêu hon khi chon ô e . (3,2) 45 ´ ´, - Tram phat thu nhât phat hêt . ´ ´ ´ 12 2 3 6 55 ` hang, x´ a d` ng 1. o o ´, ´ ` - Tram thu thu 4 thiêu hang, ta ghi nhap 10. . ´ 10 bj ,, 30 40 50 60 o ´ ´ 3.Ô (3,2) c´ cuoc ph´ thâp nhât ı ´ ai ` ,, ` 1 5 7 2 la 2, ta phân môt luong 40 vao . . ` ô nay: 80 30 50 , ´, - Tram thu thu 2 nhân du . . ¯ 5 7 4 9 ` hang, x´ a côt 2. o . 45 ´ ´, - Tram phat thu 3 c` n du 15, . o , 12 2 3 6 15 55 40 ´ ta ghi nhap 15. , Nguyên Hu,u Ðiên ˜ ˜ https://vietex.blog.fc2.com/