Bài toán quy hoạch tuyến tính

2.Bài tốn quy hoạch tuyến tính (QHTT) Tình huống: Một cơng ty cần lên một kế hoạch quảng cáo cho sản phẩm củ mình trên sĩng phát thanh và sĩng truyền hình. Chi phí cho 1 phút quảng cáo trên sĩng phát thành là 80.000 đ, trên sĩng truyền hình là 400.000 đ. ðài phát thanh chỉ nhận quảng cáo các chương trình dài ít nhất 5 phút. Cịn đài truyền hình chỉ nhận phát các chương trình tối đa 4 phút. Theo các phân tích xã hội hoc, cùng một thời lượng 1 phút quảng cáo trên truyền hình sẽ cĩ hiệu quả gấp 6 lần trên sĩng phát thanh. Cơng ty dự định chỉ chi tối đa là 1.600.000 đ cho quảng cáo. Hỏi cần đặt thời lượng quảng cĩ trên sĩng phát thanh và sĩng truyền hình như thế nào cho đạt hiệu quả nhất? Mơ hình hĩa: Gọi thời lượng cơng ty đặt quảng cáo trên sĩng phát thanh là a phút. Trên sĩng truyền hình là b phút . chi phí cho việc này là 80.000*a + 400.000*b ≤ 1.600.000 đ. Trong đĩ; a ≥ 5; b ≤ 4; a ≥ 0; b ≥ 0. Hiệu quả chung của quảng cáo là a + 6.b Bài tốn: Xác đinh a; b sao cho a + 6b
Max Với điều kiện : 80.000*a + 400.000*b ≤ 1.600.000 đ. a ≥ 5; b ≤ 4 và: a ≥ 0; b ≥ 0. Bài tốn cĩ cấu trúc như trên là một ví dụ về bài tốn QHTT. Chú ý : do Maxf(x) = -Minf(x) nên từ nay về sau ta chỉ nĩi tới bài tốn tìm Minf(x) 2.1Các định nghĩa: Bài tốn: Xác định véc tơ );...;;( 21 nxxxx = sao cho Trong đĩ 321 ;; III là tập các chỉ số khơng giao nhau kí hiệu i = 321 III ∪∪ ; jiiii cba ;; là các hệ số; xj j:=1,2,…,n là các biến. +Hàm f(x) gọi là hàm mục tiêu +Hệ (1.1) đến (1.4) gọi là hệ ràng buộc ( hệ điều kiện) của bài tốn . Với mỗi chỉ số i ta cĩ một phương trình hoặc bất phương trình tương ứng và được gọi là ràng buộc thứ i.Các hệ số ở vế trái trong mỗi ràng buộc thứ i là một véc tơ dịng A *i =(ai1; ai2;….;ain) . Một nhĩm ràng buộc cĩ hệ véc tơ *iA độc lập tuyến tính được gọi là các ràng buộc độc lập tuyến tính. xj ≥ 0; xj ≤ 0 gọi là các ràng buộc về dấu đối với xj + Trong hệ từ (1.1) đến (1.4) xét các ràng buộc khơng phải là ràng buộc về dấu các hệ số ở vế trái tương ứng với mỗi ràng buộc này là một ma trận, ký hiệu là A. Ma trận A cĩ n cột, mỗi cột này là một véc tơ, ký hiệu là Aj – chính là véc tơ các hệ số của biến xj Aj gọi là véc tơ điều kiện ứng với biến xj + Phương án: một véc tơ x thỏa mãn hệ ràng buộc của bài tốn gọi là một phương án của bài tốn. Trong ràng buộc thứ i nếu dấu “=” xảy ra thì ta nĩi phương án x thỏa mãn chặt đối với ràng buộc thứ i; cịn nếu xảy ra dấu ≤ hoặc (≥ ) thì phương án x là lỏng đối với ràng buộc thứ i + Phương án tối ưu: là phương án mà hàm mục tiêu đạt được Min + Phương án tốt hơn Nếu f(x1) ≤ f(x2) thì phương án x1 gọi là tốt hơn phương án x2 Một bài tốn tồn tại phương án tối ưu gọi là bài tốn giải được, nếu khơng cĩ phương án tối ưu gọi là bài tốn khơng giải được. +Phương án cực biên: Một phương án thỏa mãn chặt n ràng buộc độc lập tuyến tính được gọi là phương án cực biên (PACB) * phương án cực biên thỏa mãn chặt đúng n ràng buộc gọi là phương án cực biên khơng suy biến, thỏa mãn chặt hơn n ràng buộc gọi là phương án cực biên suy biến. Thí dụ 1: Cho .f(x) = x1 + x2 – 2x3 + x4 + x5
Min .x1 + x2 + x3 - x5 ≤ 40 (1) .-2x1 – 2x2 + 5x3 + 2x5 = 65 (2) .x2 + x3 +x4 + 2x5 ≥ 12 (3) .xj ≥ 0 với j:=1,2,..,5 Ta cĩ: )2;1;1;1;0( )2;0;5;2;2( )1;0;1;1;1( * 3 * 2 * 1 = −−= −= A A A          − =           =           =           −=           −= 2 2 1 ; 1 0 0 ; 1 5 1 ; 1 2 1 ; 0 2 1 54321 AAAAA Ma trận           −− − = 21110 20522 10111 A Với x1 = ( 0; 0; 13; 0; 0) ; x2 = ( 0; 0; 1; 0; 30) đây là hai phương án của bài tốn. Phương án x1 thỏa mãn chặt đối với ràng buộc (2) và là lỏng đối với (1) và (3) và x3 ≥ 0 Phương án x2 thỏa mãn chặt đối với (2) và lỏng đối với (1); (3) và x3 ≥ 0; x5 ≥ 0 Do f(x1) < f(x2) nên phương án x1 tốt hơn thực sự phương án x2 Thí dụ 2: f(x) = - x1 - 6x2
Min 80.000.x1 + 400.000x2 ≤ 1.600.000 .x1 ≥ 5; x2 ≤ 4 .x1 ≥ 0; x2 ≥ 0 Các phương án x1 = ( 5;3); x2 = ( 0;4); x3 = (20;0) là các phương án cực biên của bài tốn • Nếu tất cả các phương án cực biên của bài tốn đều khơng suy biến thì bài tốn gọi là khơng suy biến; trái lại, gọi là bài tốn suy biến. 2.2.Các dạng đặc biệt của bài tốn QHTT a. Dạng chính tắc: njx mibxa Minxcxf j n j ijij n j jj ,..,2,10 ,...,2,1 )( 1 1 =≥ == ⇒= ∑ ∑ = = * Nhận xét : Mọi bài tốn QHTT đều cĩ thể đưa về bài tốn QHTT dạng chính tắc tương đương ( bằng cách thêm, bớt một lượng khơng âm vào mỗi ràng buộc để cĩ dấu “ =” trong ràng buộc đĩ). Khi ấy trị tối ưu của hàm mục tiêu trong hai bài tốn là trùng nhau, từ phương án, phương án tối ưu của bài tốn này suy ra phương án, phương án tối ưu của bài tốn kia. Thí dụ 3: Bài tốn ở thí dụ 1 tương đương với bài tốn chính tắc sau: f(x) = - x1 - 6x2
Min 80.000.x1 + 400.000x2 + x3 = 1.600.000 .x1 - x4 = 5 .x2 + x5 = 4 .xj ≥ 0; j =1,2,..,5 b.ðặc điểm của phương án cực biên của bài tốn dạng chính tắc ðịnh lý 1: Phương án x của bài tốn dạng chính tắc là cực biên khi và chỉ khi hệ thống các véc tơ {Aj } tương ứng với các thành phần dương của phương án là độc lập tuyến tính. ( Hiển nhiên vì khi đĩ hệ các ràng buộc là hệ Crame nên cĩ nghiêm duy nhất, hay nghiệm đĩ chính là một phương án cực biên của bài tốn) Trong thí dụ 3 phương án x1 = ( 5;3;0;0;1) cĩ           =           =           = 1 0 0 ; 1 0 000.400 ; 0 1 000.80 521 AAA là ba véc tơ độc lập tuyến tính nên x1 là phương án cực biên. c. Cơ sở của phương án cực biên: ( với bài tốn dạng chính tắc) Một hệ gồm m véc tơ {Aj} độc lập tuyến tính bao hàm hệ thống các véc tơ tương ứng với các thành phần dương của phương án cực biên x là cơ sở của phương án cực biên ấy, ký hiệu một cách quy ước là j, trong đĩ J = {J: Aj thuộc cơ sở } + Với phương án x = (x1;x2;,…,xn) gọi thành phần xj ( j )J∈ là thành phần cơ sở; xk ( Jk ∉ ) là thành phần phi cơ sở .Dễ nhận thấy các thành phần phi cơ sở của phương án cực biên luơn bằng 0. Một phương án cực biên khơng suy biến thì mọi thành phần cơ sở đều dương, cịn phương án cực biên suy biến thì cĩ ít nhất một thành phần cơ sở bằng 0 Trong thí dụ 3 ở trên phương án x1 là phương án cực biên (PACB) khơng suy biến d. Bài tốn dạng chuẩn: Nếu bài tốn dang chính tắc trong đĩ bi ≥ 0 với mọi i:=1,2,…,m và mỗi phương trình trong hệ ràng buộc đều cĩ một biến số với hệ số bằng 1 đồng thời biến này khơn gcos trong các phương trình khác gọi là bài tốn cĩ dạng chuẩn. 2.3. Các tính chất của bài tốn QHTT Tính chất 1: Nếu bài tốn cĩ phương án và hạng của ma trân hệ ràng buộc bằng n ( n là số biến số) thì bài tốn cĩ phương án cực biên. Thí dụ 1: Cho bài tốn QHTT: .f(x) = 3x1 + x2 + 2x3 + 6x4
Min -3x1 + 2x2 + 5x3 – x4 ≥ -16 3x2 + 2x3 + 7x4 = 0 .x1 – 4x2 + 3x4 – x5 ≤ 34 2x1 - 6x3 + 2x4 ≥ -2 .x1 ≥ 0 .x2 ≥ 0 .x3 ≥ 0 .x4 ≥ 0 .x5 ≥ 0 Chứng tỏ rằng bài tốn cĩ PACB. Giải: Dễ thấy hạng của ma trân hệ ràng buộc bằng 5, thêm nữa x = ( 0; 0;0;0;0) là một phương án vậy theo tính chất 1 suy ra bài tốn cĩ PACB. Tính chất 2: Nếu bài tốn cĩ phương án và trị số của hàm mục tiêu bị chặn dưới khi f(x)
Min trên tập phương án thì bài tốn cĩ phương án tối ưu. Thí du 2. Chứng tỏ bài tốn trong thí dụ 1 cĩ PACB tối ưu. Giải: theo thí dụ 1 ta đã chứng tỏ bài tốn cĩ PACB thêm nữa do ràng buộc về dấu ta suy ra f(x) ≥ 0 trên tâp phương án. Vậy theo tính chất 2 chứng tỏ bài tốn cĩ PACB tối ưu. Tính chất 3: Số phương án cực biên của bài tốn QHTT là hữu hạn. 3. Phương pháp đơn hình giải bài tốn QHTT 3.1.Nội dung của phương pháp. Xuất phát từ một PACB, ta tìm cách đánh giá PACB đĩ, nếu nĩ chưa tối ưu thì tìm cách di chuyển sang một phương án cực biên mới tốt hơn, quá trình này được tiếp tục lặp. Vì số phương án cực biên là hữu hạn, nên sau một số hữu hạn bước lặp, hoặc ta tìm được phương án cực biên tối ưu, hoặc là ta kết luận bài tốn khơng giải được vì hàm mục tiêu khơn gbij chặn. ðĩ là nội dung cơ bản của phương pháp đơn hình. 3.2. ðặc điểm của phương án cực biên của bài tốn dạng chính tắc. a. Quan hệ giữa phương án cực biên và phương án của bài tốn: Xét bài tốn dạng chính tắc njx mibx xcxf j i j j n j jj ,...,2,1:0 ,..,1:a Min)( n 1 ij 1 =≥ == ⇒= ∑ ∑ = = Và cho x0 là PACB với cơ sở J0 Ta ký hiệu véc tơ gồm các thành phần cơ sở của PACB x0 là 0jX (viết theo cột) và ma trân các véc tơ cơ sở là ]:[ 00 JjAA jj ∈= khi đĩ )(0 00 Jkxk ∉∀= Do đĩ : bAXbXA jjjj 10000 −=→= Các véc tơ phi cơ sở Ak với k 0J∉ cũng phân tích được qua cơ sở J0 Gọi các hệ số phân tích của Ak là xjk véc tơ hệ số phân tích tương ứng là Xk như vậy: kJ Jj jjkk XAAxA 0 0 == ∑ ∈ do đĩ Xk = kJ AA 1 0 − . Ước lượng của biến xk theo cơ sở J0 ký hiệu và được xác định bởi: ∑ ∈ −=∆ 0Jj kjkjk cxc với: cj { }0: Jjc j ∈= Với những xj ( j 0J∈ ) thì ước lượng của nĩ 0=∆ j ðối với cơ sở J0 nếu phương án đang xét khơng là PACB tối ưu thì bằng phép đổi cơ sở ta sẽ đi tới một phương án xự biên tốt hơn. 3.3.Dấu hiệu tối ưu và các định lý cơ bản. ðịnh lý 2: Dấu hiệu tối ưu của phương án cực biên Nếu đối với PACB x0 với cơ sở J0 của bài tốn dạng chính tắc mà: )(0 0Jkk ∉∀≤∆ với bài tốn f(x)
Min thì x0 là phương án tối ưu. Chú ý : ðịnh lý 2 là điều kiện đủ, tuy nhiên nếu x0 là PACB khơng suy biến thì đĩ cũng là điều kiền cần để x0 là phương án tối ưu. ðịnh lý 3: Dấu hiệu bài tốn khơng giải được Nếu đối với phương án cực biên x0 với cơ sở J0 của bài tốn dạng chính tắc mà: Tồn tại 000 Jkxmà jkk ∉∀≤>∆ với bài tốn f(x)
Min Thì bài tốn khơng giải được ( Hàm mục tiêu khơng bị chặn dưới) ðịnh lý 4: Dấu hiệu điều chỉnh phương án cực biên. Nếu đối với một phương án cực biên x0 với cơc sở J0 của bài tốn dạng chính tắc mà : với mỗi 0>∆k đều tồn tại xjk > 0 với bài tốn f(x)
Min thì ta cĩ thể điều chỉnh phương án cực biên x0 chuyển sang một phương án cực biên tốt hơn. 3.4.Cơng thức đổi cơ sở: Trong khơng gian Rn cho véc tơ x0 cho hai cơ sở α 1;α 2;….;α n (1) β r 1; β r 2;….; β r n (2) Giả sử ∑∑ == == n j jj n i ii yxxx 1 0 1 0 βα Tìm mối liên hệ giứa các tọa độ xj ; yj Gọi T = (tij) là ma trận chuyển từ cơ sở (1) sang cơ sở (2) khi ấy njt n i iijj ,..,2,1 1 ==∑ = αβ Do đĩ ∑ ∑∑ ∑ ∑ ∑ = == = = = ==== n i n j ijij n i n j n j n i iijjjjii yttyyxx 1 11 1 1 1 0 )( ααβα Vậy: ∑ = = n j jiji ytx 1 3.4.Thuật tốn của phương pháp đơn hình: Giả sử bài tốn phải giải là bài tốn QHTT ở dạng chính tắc, đã biết một phương án cực biên x 0 và cơ sở J0 . khơng mất tính tổng quát ta giả sử J0 gồm m véc tơ đầu tiên, tứ là cơ sở gồm m véc tơ A1,A2,…..,Am. Bước 1: Lập bảng đơn hình ứng với phương án cực biên x0 Hệ Số cj Cơ Sở J0 Phương án .c1 c2………cr………..cm cm+1 cm+2 … ..ck……..cs……....cn .x1 x2………xr…….xm xm+1 xm+2…….xk……..xs………xn .c1 . c2 … .cr … .cm .x1 . x2 … .xr … .xm 0 1x 0 2x …. 0 rx …. 0 mx 1 0 …… 0……..0 x1m+1 x1m+2……x1k…….x1s……..x1n 0 1………..0……..0 x2m+1 x2m+2……x2k…….x2s……..x2n ……………… …… ..……………………………. 0 0………..1……..0 xrm+1 xrm+2……xrk……..xrs……...xrn ………………………… ………………………………………. 0 0………..0…… 1 xmm+1 xmm+2 …….xmk…….xms……..xmn .f(x) .f(x0) 0 0 ……….0……...0 1+∆m 2+∆m k∆ s∆ n∆ - Dịng cj là các hệ số của các biến trong hàm mục tiêu f(x) - Cột cj là hệ số của biến xj ứng với véc tơ cơ sở Ajx - ∑ ∈ −=∆ 0Jj kjkjk cxc thí dụ smsmrsrsss cxcxcxcxc −+++++=∆ ).......( 2211 Bước 2: Kiểm tra dấu hiệu tối ưu của PACB - Nếu 00 Jkk ∉∀≤∆ với bài tốn f(x)
Min thì x0 là phương án tối ưu - Nếu 0>∆∃ k thì x 0 khơng là phương án tối ưu, chuyển sang bước 3 Bước 3: kiểm tra tính khơng giải được của bài tốn. - Nếu 0>∆∃ k mà xjk ≤ 0 với mọi j 0J∈ với bài tốn f(x)
min thì bài tốn khơng giải được vì hàm mục tiêu cĩ trị khơng bị chặn dưới - Nếu với mỗi 0>∆k đều cĩ ít nhất xjk > 0 thì chuyển sang bước 4 Bước 4: ðiều chỉnh PACB và lập bảng đơn hình mới. - Chọn phương án đưa vào cơ sở: Tìm max 0>∆∀∆ kk giả sử max sk ∆=∆ thì véc tơ As được đưa vào cơ sở - Tìm Min js j x x0 với mọi xjs > 0 ; j 0J∈ giải sử Min js j x x0 = rs r x x0 khi ấy véc tơ Ar bị loại khỏi cơ sở . phần tử xrs gọi là phần tử trục và được đĩng khung trong bảng - Biến đổi bảng: + Lập bảng đơn hình mới. thay véc tơ cơ sở vừa lựa chon ở trên cs thay cho cr trong cột cj .xs thay cho xr trong cột cơ sở + Tính các dịng mới ( bắt đầu từ cột thứ 3 trở đi) ðể tính dịng ứng với dịng cĩ véc tơ .xs mới đưa vào trong bảng mới ta lấy dịng ứng với véc tơ lấy ra xr trong bảng cũ chia cho phần tử trục. Dịng này gọi là dịng chuẩn. ðể tính dịng xj trong bảng mới ta lấy dịng xj trong bảng cũ trừ đi dịng chuẩn sau khi đã nhân dịng nĩ ( dịng chuẩn) với xjs ðể tính dịng cuối của bảng mới, ta lấy dịng cuối của bảng cũ trừ đi dịng chuẩn sau khi nhân nĩ (dịng chuẩn) với s∆ Tiến trình trên được lặp lại sau hữu hạn bước ta cĩ kết luận về lời giải của bài tốn đang xét. Thí dụ 1: Giải bài tốn QHTT sau: Bài tốn đã cho cĩ dạng chuẩn, các biến cơ lập là x4;x6;x7 nên phương án cực biên là x 0 =(0;0;0;16;0;52;24) cơ sở J0 là A4; A6; A7 ta lập ngay được bảng đơn hình sau Bảng đơn hình x0 0 0 0 16 0 52 24 x0' 4 -2 1 -3 0 0 0 Cj J Xj x1 x2 x3 x4 x5 x6 x7 -3 x4 16 1 0 1 1 3 0 0 0 x6 52 2 -3 -2 0 2 1 0 0 x7 24 0 [1] 1 0 -2 0 1 f(x) -48 -7 2 -4 0 -9 0 0 -3 x4 16 1 0 1 1 3 0 0 0 x6 52 2 0 1 0 -4 1 3 -2 x2 24 0 1 1 0 -2 0 1 f(x) -96 -7 0 -6 0 -5 0 -2 Phương án mới .x1= (0; 24; 0; 16; 0; 52) Sau khi kết thúc bảng 1 từ dịng cuối ta thấy phương án x0 chưa tối ưu do cĩ ∆2 > 0 véc tơ A2 được đưa vào cơ sở Thêm nữa Min{ 72 7 x x } =24/1 nên véc tơ A7 được đưa ra khỏi cơ sở phần tử trục là [1] trong bảng 1 Note: Thực chất trong bảng 1 ở các cột xj là tọa độ của véc tơ Aj đối với cơ sở chính tắc khi chuyển sang bảng 2 ta đã đổi cơ sở{A4;A6;A2} trong bảng 2 các cột xj là tọa độ của véc tơ Aj qua cơ sở mới. Do đĩ muốn tìm tọa độ của các Aj qua cơ sở mới ta chỉ việc.Tìm ma trận chuyển từ cơ sở mới sang cơ sở chính tắc ( biểu thị tuyến tính các véc tơ chính tắc qua cơ sở mới rồi lấy ma trận chuyển vị của ma trân các hệ số trong sự biểu thị trên), gọi nĩ là ma trân T=(tij) ; khi ấy T.Aj =A’j trong đĩ A’j là tọa độ của Aj đối với cơ sở mới. Từ bảng 2 ta thấy ∆k <0 với mọi k 0J∉ nên phương án x 1 là tối ưu duy nhất. f(x1) = -96 Thí dụ 2: Giải bài tốn sau bằng phương pháp đơn hình 7,...,3,2,1,0 242 522232 163 min3.2.4)( 7532 65321 5431 4321 =≥ =+−+ =++−− =+++ ⇒−+−= jx xxxx xxxxx xxxx xxxxxf j .f(x) = 2x1-3x2-x3
Min 2x1 – x2 + x3 ≤ 18 3x1 + x2 -2x3 ≤ 20 .x1 +2x2 ≤ 12 .x1≥ 0; .x2 ≥ 0; x3 ≥ 0 Ta đưa về bài tốn chính tắc sau: Bài tốn cĩ dạng chuẩn, các biến cơ lập x4; x5; x6 nên phương án cực biên x 0 = ( 0;0;0;18;20;12) cơ sở J0={A4;A5;A6} Bảng đơn hình H I J K L M N O P x0 0 0 0 18 20 12 26 2 -3 -1 0 0 0 27 Cj J Xj x1 x2 x3 x4 x5 x6 28 0 x4 18 2 -1 1 1 0 0 29 0 x5 20 3 1 -2 0 1 0 30 0 x6 12 1 [2] 0 0 0 1 31 f(x) 0 -2 3 1 0 0 0 32 0 x4 18 2.5 0 [1] 1 0 0.5 33 0 x5 20 2.5 0 -2 0 1 -0.5 34 -3 x2 -18 0.5 1 0 0 0 0.5 35 f(x) -18 -3.5 0 1 0 0 -1.5 36 -1 x3 24 2.5 0 1 1 0 0.5 37 0 x5 62 7.5 0 0 2 1 0.5 38 -3 x2 6 0.5 1 0 0 0 0.5 39 f(x) -42 -6 0 0 -1 0 -2 Phương án x2 =( 0;6;24;0;62;0) là phương án tối ưu duy nhất. Trên bảng tính Excel: dịng 34(dịng chuẩn) từ cột K trở đi được thiết lập nhờ cơng thức K34= K30/$L$30 rê chuột tuyến tính theo dịng K34 ta cĩ kết quả ở L34;M34:…P34. Dịng 32 :K32 = K28 –K34*$L$28 rê chuột như trên để cĩ các kết quả của các cột cùng dịng Dịng 33 Tương tự như trên Dịng 35: K35 = K31-K34*$L$31 ðể tính x2;x3;x5 phải giải hệ phương trình tương ứng ở hệ ràng buộc ( các biến khác đều bằng 0) 3.5.Các chú ý khi áp dụng thuật tốn: + khi cần giải bài tốn f(x)
Max thì ta giải bài tốn –f(x)
Min + nếu khi chon vecto đưa vào cơ sở hoặc đưa ra khỏi cơ sở cĩ nhiều véc tơ thuộc diện lựa chọn thì tùy chọn một trong số đĩ 6,...,2,1:0 122 2023 182 32)( 621 5321 4321 321 jx xxx xxxx xxxx Minxxxxf j ∀≥ =++ =+−+ =++− ⇒−−= +Trường hợp bài tốn suy biến cĩ thể dẫn tới min js j x x0 = 0 với mọi xjs > 0 ; j 0J∈ vẫn thực hiện thuật tốn một cách bình thường + Khi áp dụng thuật tốn cần lưu ý: i) Phương án x0 cĩ cơ sơt J0 là cơ sở đơn vị ( cịn gọi là cơ sở chính tắc), ma trận các hệ số ở vế trái trong hệ ràng buộc cĩ các cột tương ứng là tọa độ của vecto Aj theo cơ sở đĩ. Ta lập ngay được bảng đơn hình. ðây là bài tốn dạng chuẩn ii) Khi J0 khơng phải là cơ sở chính tắc ta phải tìm ma trận các hệ số trong hệ ràng buộc phân tích qua cơ sở chính tắc J0 bằng cách biến đổi các dịng của ma trận bổ sung của hệ ràng buộc làm xuất hiện cơ sở J0. 4. Phương pháp tìm phương án cực biên: Cĩ những bài tốn cĩ dạng chính tắc, nhưng khơng phải dạng chuẩn, đồng thời ta chưa biết PACB, do đĩ muốn áp dụng thuận tốn đơn hình ta phải tìm được một PACB của nĩ. Xét bài tốn dạng chính tắc: njx mibx xcxf j i j j n j jj ,...,2,1:0 ,..,1:a Min)( n 1 ij 1 =≥ == ⇒= ∑ ∑ = = (I) Khơng mất tính tổng quát giả sử bi ≥ 0 mọi i = 1,2,…,m.(nếu bi <0, nhân hai vế với -1) Xây dựng bài tốn phụ P bằng cách cộng vào vế trái phương trình ràng buộc i một biến giả x gi ≥ 0 (i=1,2,..,m) với hàm mục tiêu là tổng các biến giả đã thêm vào và hàm mục tiêu này phải đạt cực tiểu. Ký hiệu véc tơ các biến giả là xg = ( ),...,, 21 gmgg xxx và hàm mục tiêu là P(x;xg) Ta cĩ bài tốn phụ: mix njx mibxxa MinxxxP g i j n j i g ijij m i g i g ,....,2,10 ,...,2,10 ,...,2,1 );( 1 1 =∀≥ =∀≥ ==+ ⇒= ∑ ∑ = = Bài tốn này cĩ dạng chuẩn và hàm mục tiêu luơn bị chặn dưới nên luơn giải được bằng phương pháp đơn hình, giả sử );( gxx là phương án tối ưu của bài tốn phụ và P );( gxx =Pmin i). nếu Pmin > 0 Khi đĩ bài tốn (I) khơng cĩ phương án. ii) nếu Pmin = 0 khi đĩ x là phương án cự biên của bài tốn (I). ðể áp dụng thuật tốn cho bài tốn (I) ta cần biết cơ sở J0 của nĩ. Cĩ hai trường hợp sau: a).Trong cơ sở của phương án cực biên )0;( =gxx khơng cĩ các vectơ tương ứng với các biến giả, khi đĩ cơ sở này cũng là cơ sở của phương án cực biên x . Tiến hành thuật tốn bình thường. b). Trong cơ sở của phương án cực biên )0;( =gxx cĩ ít nhất một vectơ tương ứng với các biến giả, lúc này PACB là suy biến. ðể tiếp tục giải bài tốn (I) ta loại các cột ứng với 0)( <∆ Pj và các cột gix phi cơ sở ra khỏi bảng, sau đĩ tính lại các ước lượng ∆k theo hàm f và tiếp tục thuật tốn. Chú ý: - Khi xây dựng bài tốn phụ ta chỉ cộng thêm biến giả vào những phương trình ràng buộc cần thiết để tạo ra cơ sở đơn vị trong ma trận điều kiện. - Nếu trong quá trình giải bài tốn P, ở một bước điều chỉnh nào đĩ mà tất cả các biến giả đều bị loại ra khỏi cơ sở thì kết thúc việc giải bài tốn phụ P ( vì PACB bài tốn (I) đã tìm được). Tiếp tục giải bài tốn (I) với PACB vừa cĩ. Thí dụ 1: Giải bài tốn sau bằng phương pháp đơn hình: .f(x) = 3x1 +4x2 +2x3 + 2x4
Min 2x1 + 2x2 + x4 = 28 .x1 +5x2 + 3x3 – 2x4 ≤ 31 2x1 – 2x2 +2x3 + x4 = 16 .xj ≥ 0 ( j=1,..,4) Giải: ðưa bài tốn đã cho về dạng chính tắc: . f(x) = 3x1 +4x2 +2x3 + 2x4
Min 2x1 + 2x2 + x4 = 28 .x1 +5x2 + 3x3 – 2x4 + x5 = 31 2x1 – 2x2 +2x3 + x4 = 16 .xj ≥ 0 ( j=1,..,5) Bài tốn khơng cĩ dạng chuẩn nên ta đưa ra bài tốn phụ (P) P(x,xg) = xg1 + xg3
Min 2x1 + 2x2 + x4 + xg1 = 28 .x1 +5x2 + 3x3 – 2x4 + x5 = 31 2x1 – 2x2 +2x3 + x4 xg3 = 16 .xj ≥ 0 ( j=1,..,5) xg1≥ 0; xg2 ≥ 0 Bảng đơn hình hai pha H I J K L M N O P Q 46 f 3 4 2 2 0 47 P 0 0 0 0 0 1 1 48 Cj J Xj x1 x2 x3 x4 x5 xg1 xg3 49 1 xg1 28 2 2 0 1 0 1 0 50 0 x5 31 1 5 3 -2 1 0 0 51 1 xg3 16 [2] -2 2 1 0 0 1 52 P 44 4 0 2 2 0 0 0 53 1 xg1 12 0 [4] -2 0 0 1 54 0 x5 23 0 6 2 -2.5 1 0 55 0 x1 8 1 -1 1 0.5 0 0 56 P 12 0 4 -2 0 0 0 57 4 x2 3 0 1 -0.5 0 0 58 0 x5 5 0 0 5 -2.5 1 59 3 x1 11 1 0 0.5 0.5 0 60 f 45 0 0 -2.5 -0.5 0 Một biến giả bị loại khỏi cơ sở ta bỏ qua nĩ ở bảng đơn hình tiếp theo. Dịng 60 do khơng cịn phụ thuộc biến giả ta tính ∆k theo hàm f ( chẳng hạn K60 = ($h$57*k57+$h$58*k58+$h$59*k59)-k46) tương tự cho các cột cịn lại của dịng 60. CHƯƠNG VI: BÀI TỐN ðỐI NGẪU (3) Trong thực tế cĩ những cặp bài tốn QHTT cĩ mối quan hệ mật thiết với nhau, do vậy từ các kết quả nghiên cứu được của bài tốn này cĩ thể suy ra các kết quả tương ứng của bài tốn kia và ngược lại. người ta gọi cắc cặp bài tốn như thế là cặp các bài tốn đối ngẫu nhau. ðặc biệt các cặp bài tốn đối ngẫu cĩ nội dung thực tế, việc phân tích mối quan hệ giữa bài tốn ban đầu và bài tốn đối ngẫu cịn đem lại những thơng tin cĩ ý nghĩa lý luận và thực hành. 1.Cách thành lập bài tốn đối ngẫu: Bài tốn ban đầu Bài tốn đối ngẫu )()( 1 MaxMinxcxf n j jj ⇒=∑ = 1 1 Iibxa n i ijij ∈=∑ = 2 1 )( Iibxa n i ijij ∈≤≥∑ = 3 1 )( Iibxa n i ijij ∈≥≤∑ = .xj khơng ràng buộc về dấu 1Jj ∈ 20 Jjx j ∈≥ 30 Jjx j ∈≤ )()(~ 1 MinMaxybyf m i ii ⇒=∑ = .yi khơng cĩ ràng buộc về dấu 20 Iiyi ∈≥ 30 Iiyi ∈≤ ∑ = ∈= m i jiij Jjcya 1 1 ∑ = ∈≥≤ m i jiij Jjcya 1 2)( ∑ = ∈≤≥ m i jiij Jjcya 1 3)( Thí dụ 1: Viết bài tốn đối ngẫu của bài tốn sau và chỉ ra các cặp ràng buộc đối ngẫu: .f(x) = -4x1 + x2 + 5x3 + 3x5
Min 3x1 – 6x2 – x3 + 2x4 – 4x5 ≥ -15 (1) -2x1 +3x2 +4x3 +5x4 – x5 ≤ 8 (2) -6x2 + 3x3 +8x4 - 4x5 = 9 3x1+2x2 -3x4 + x5 ≥ 24 (3) .x1 ≥ 0 (4); x3 ≤ 0 (5) x5 ≥ 0 (6) Giải: Bài tốn đối ngẫu: )12(0 )11(0 )10(0 )9(344 03852 )8(534 12636 )7(4323 249815)(~ 4 2 1 4321 4321 321 4321 421 4321 ≥ ≤ ≤− ≤+−−− =−++ ≥++− =+−+− −≤+− ⇒+++−= y y y yyyy yyyy yyy yyyy yyy Maxyyyyyf Các cặp ràng buộc đối ngấu là: (1-10);(2-11); (3-12);(4-7);(5-8);(6-9) Thí dụ 2: Viết bài tốn đối ngẫu của bài tốn sau: .f(x) = -3x1 +5 x2 + 4x3 -2x4 + x5
Max 2x1 – 3x2 – x3 + 6x4 – 2x5 +2x6 = -14 -x1 + 2x2 + 5x3 + 3x5 – 4x6 = 8 6x1- 3x2 + 2x3 - x4 + x5 + 3x6 = 12 3x1+2x2 -3x4 + x5 ≥ 24 .xj ≥ 0 j=1,2,…,6 2. Các tính chất và định lý đối ngẫu: 2.1.Xét cặp bài tốn đối ngẫu với các hàm mục tiêu: )()(~)()( MinMaxyfMaxMinxf ⇒⇒ Tính chất 1: Với mọi cặp phương án x và y của hai bài tốn đối ngẫu ta luơn cĩ )(~)()( yfxf ≥≤ Tính chất 2: Nếu đối với hai phương án x* và y* của một cặp bài tốn đối ngẫu mà: **** )(~)( yvàxthìyfxf = tương ứng là hai phương án tối ưu. ðịnh lý 1: Nếu một trong hai bài tốn đối ngẫu mà giải được thì bài tốn kia cũng giải được và khi đĩ với mọi phương án tối ưu x* , y* ta luơn cĩ: )(~)( ** yfxf = Hệ quả 1: ðiều kiện cần và đủ để hai bài tốn đối ngẫu giải được là mỗi bài tốn cĩ ít nhất một phương án. Hệ quả 2: ðiều kiện cần và đủ để một bài tốn cĩ phương án cịn một bài tốn khơng cĩ phương án là trị số của hàm mục tiêu của bài tốn cĩ phương án khơng bị chặn trên tập các phương án của nĩ. ðịnh ly 2: ðiều kiện cần và đủ để hai phương án x và y của một cặp bài tốn đối ngẫu tối ưu là trong các cặp ràng buộc đối ngẫu nếu một ràng buộc thỏa mãn với dấu bất đẳng thức thực sự (lỏng) thì ràng buộc kia phải thỏa mãn với dấu bằng (chặt) Hệ quả 1: Nếu một ràng buộc là lỏng với một phương án tối ưu của bài tốn này thì ràng buộc đối ngẫu của nĩ phải là chặt đối với phương án tối ưu của bài tốn kia. 2.2. Một số ứng dụng của tính chất và các định lý đối ngẫu: a) Khảo sát sự tồn tại phương án, phương án tối ưu: Thí dụ 1: Cho bài tốn QHTT .f(x) = 2x1 – x2 + 3x3 – 2x4
Min .x1 – x2 = 15 .x3 – x4 = 8 .xj ≥ 0 mọi j=1,2,3,4 Hãy viết bài tốn đối ngẫu và chứng tỏ nĩ cĩ phương án tối ưu. Giải: Bài tốn đối ngẫu: 2 3 1 2 815)(~ 4 3 1 1 21 −≤− ≤ −≤− ≤ ⇒+= y y y y Maxyyyf Ta nhận thấy x* = ( 15;0;8;0) là một phương án của bài tốn gốc .y* = ( 1;2 ) là một phương án của bài tốn đối ngẫu . Vậy theo hệ quả 1 định lý 1 suy ra hai bài tốn này là giải được, hay cặp bài tốn cĩ phương án tối ưu. Thêm nữa hạng của ma trận hệ ràng buộc trong bài tốn đối ngẫu bằng 2 nên nĩ cĩ PACB tối ưu. Thí dụ 2: Cho bài tốn QHTT .f(x) = x1 +2x2 + px3 – 2x4 + x5
Max 2x1 – x2 + x4 – x5 ≥ 4p +1 . x2 - x3 + 2x4 – x5 ≤ 32 .x1 - x2 + x3 + x5 = 18 .x3 ≥ 0; x4 ≥ 0 với p là tham số. Hãy viết bài tốn đối ngẫu và dựa vào bài tốn này để biện luận theo tham số p về sự tồn tại phương án tối ưu của bài tốn gốc. Giải: Bài tốn đối ngẫu: )7(0)6(;0 )5(1 )4(22 )3( )2(2 )1(12 1832)14()(~ 21 321 21 32 321 31 321 ≥≤ =+−− −≥+ ≥+− =−+− =+ ⇒+++= yy yyy yy pyy yyy yy Minyyypyf Hệ phương trình tạo bới các ràng buộc (1-2-5) cho ta hệ phương trình cĩ nghiệm duy nhẩt .y0 =( 0;3;1) nghiệm này thỏa mãn các ràng buộc (4-6-7 ) cho nên nĩ trở thành một phương án duy nhất nếu thỏa mãn ràng buộc (3) và ta cĩ đĩ là phương án tối ưu. Thay vào (3) suy ra : p ≤ -2 b)Phân tích tính chất tối ưu của một phương án và xác định tập phương án tối ưu: Giả sử với một phương án x của bài tốn gốc, ta cần phân tích xem đĩ cĩ phải là phương án tối ưu khơng? Giả sử x là phương án tối ưu. vậy theo định lý 2 (đối ngẫu) mọi phương án tối ưu y của bài tốn đối ngẫu phải thỏa mãn chặt các ràng buộc đối ngẫu với các ràng buộc lỏng của phương án x ở bài tốn gốc. Tập hợp các ràng buộc chặt này tạo thành một hệ phương trình đối với y. giải hệ này, nếu hệ vơ nghiệm thì x khơng thể là phương án tối ưu. Nếu hệ cĩ nghiệm thì phải thử các nghiệm này vào các ràng buộc cịn lại của bài tốn đối ngẫu, nếu mọi nghiệm đều khơng phải là phương án thì x khơng là phương án tối ưu. Nếu cĩ một nghiêm y của hệ là phương án của bài tốn đối ngẫu thì x là phương án tối ưu, đồng thời phương án y cũng tối ưu. Thí du 3: Cho bài tốn: f(x) = 7x1 + 6x2 – 12x3 + x4
Max. 2x1 – 2x2 - 3x3 +2x4 = 8 (1) 3x2 + 2x3 – 2x4 ≤ -1 (2) 2x1 - 3x3 + x4 = 10 (3) .x1 ≥ 0 j=1,2,3,4 (4) Và vecto x0 = ( 0;6;0;10) Viết bài tốn đối ngẫu. phân tích các tính chất của x0 đối với bài tốn đã cho. Xác định tập phương án tối ưu của bài tốn. Chỉ ra một phương án tối ưu khơng cực biên củ bài tốn gốc. Giải: Bài tốn đối ngẫu )9(0 )8(122 )7(12323 )6(632 )5(722 108)(~ 2 321 321 21 31 321 ≥ ≥+− −≥−+− ≥+− ≥+ ⇒+−= y yyy yyy yy yy Minyyyyf .x 0 thỏa mãn các ràng buộc của bài tốn gốc, nên nĩ là một phương án, thêm nữa x0 thỏa mãn chặt các rang buộc(1-3) và hai ràng buộc dấu ( x1=0; x3 = 0) , x0 thỏa mãn chặt 4 ràng buộc và những ràng buộc này độc lập tuyến tính nên x0 là PACB khơng suy biến. phương án x0 thỏa mãn lịng ràng buộc (2) và hai ràng buộc dấu ( x2; x4). Giả sử x0 là phương án tối ưu theo định lý 2 mọi phương án tối ưu của bài tốn đối ngẫu phải thảo mãn: (chú ý: các cặp ràng buộc đối ngấu là (2-9);(dấu x2--6) ;( dấu x4- 8)) -2y1 + 3y2 = 0 2y1 - 2y2 + y3 = 0 .y2 = 0 hệ cĩ nghiệm duy nhất y0 = ( -3;0;7) thử y0 vào ràng buộc (5-7) ta thấy nĩ thỏa mãn, y0 là phương án suy ra x0 là phương án tối ưu đồng thừi y0 là phương án tối ưu và hơn nữa là phương án tối ưu duy nhất. Phương án y0 chỉ thỏa mãn lỏng ràng buộc 5 nên mọi phương án tối ưu x phải thỏa mãn 103 8232 0 43 321 1 =+− =+−− = xx xxx x gán cho x4 tham số và giải hệ cĩ .x = ); 3 1 3 10 ; 2 11;0( 4 44 x xx +−+ Thử x vào ràng buộc (2) cịn lại: 3x2 +2x3 -2x4 ≤ -1 suy ra 3 +3/2.x4 -20/3 +2/3.x4 -2x4 ≤ -1 hay x4 ≤ 16 Thêm nữa x2 = 1 +1/2.x4 ≥ 0 suy ra x4 ≥ -2; x3 = -10/3 +1/3.x4 ≥ 0 suy ra x4 ≥ 10 Tĩm lại : 10 ≤ x4 ≤ 16. Với điều kiện này x là phương án đồng thời là phương án tối ưu của bài tốn gốc. Một phương án tối ưu khơng cực biên của bài tốn gốc là PACB mà các véc tơ cột trong hệ ràng buộc tương ứng với các thành phần dương của phương án khơng độc lập tuyến tính. chẳng hạn; x = (0;15/2;1;13) .x4 = 0;16 cĩ hai PACB tối ưu tương ứng CHƯƠNG VII: BÀI TỐN VẬN TẢI (9+2+1) 1.Nội dung và các đặc điểm: 1.1.Nội dung kinh tế và dạng tốn học: a)Bài tốn: Giả sử ta cần vận chuyển một loại hàng hĩa thuần nhất từ m địa điểm nào đĩ tới n vị trí khác nhau cĩ nhu cầu về loại hàng hĩa đĩ ( ta hiểu hàng hĩa ở đây cĩ thể là các dạng vật chất thơng thường, cũng cĩ thể là loại đặc thù như vốn, lao động, thơng tin,…). Ta ký hiệu nơi cung cấp hàng là Ai ( i=1,2,…,m) và gọi chúng là các trạm phát, n nơi cĩ nhu cầu là Bj j=1,2,…,n và gọi chúng là các trạm thu. Lượng hàng hĩa cung ứng ở trạm phát Ai là ai đơn vị, lượng hàng hĩa yêu cầu ở trạm thu Bj là bj đơn vị. Giả sử chi phí vận chuyển một đơn vị hàng hĩa từ trạm phát Ai tới trạm thu Bj là cij ≥ 0 ( khái niệm chi phí hiểu theo nghĩa rộng cĩ thể là chi phí thực, cĩ thể là độ dài quãng đường từ Ai đến Bj , hoặc sự hao phí nhiên liệu, hoặc thời gian cần thiết để vận chuyển,…. Bài tốn đặt ra là tìm phương án thực hiện việc vận chuyển hàng hĩa nĩi trên sao cho chi phí là nhỏ nhất. Gọi xij là lượng hàng hĩa chuyển từ trạm phát Ai đến trạm thu Bj ( xij ≥ 0). Yêu cầu của trạm thu đều thỏa mãn đầy đủ nghĩa là njbx m i jij ,..,2,1 1 ==∑ = ; hàng hĩa ở tất cả các trạm phát đều được sử dụng hết để đáp ứng yêu cầu của các trạm thu nên miax n j iij ,..,2,1 1 ==∑ = . Khi đĩ tổng chi phí vận chuyển sẽ là :∑∑ = = m i n j ijij xc 1 1 Bài tốn cĩ mơ hình như sau gọi là bài tốn vận tải: Tìm hệ thống {xij} ( i=1,2,..,m; j=1,2,…,n) sao cho: ∑∑ = = ⇒= m i n j ijij Minxcxf 1 1 )1()( miax n j iij ,..,2,1 1 ==∑ = (2) njbx m i jij ,..,2,1 1 ==∑ = (3) .xij ≥ 0 mọi i;j (4) Nếu : ∑ = n j jb 1 =∑ = m i ia 1 Ta cĩ bài tốn cân bằng thu phát (bài tốn cĩ dạng chính tắc) Nếu ∑ = m i ia 1 >∑ = n j jb 1 Thì (2) thay bởi: miax n j iij ,..,2,1 1 =≤∑ = Nếu ∑ = m i ia 1 <∑ = n j jb 1 Thì (3) thay bởi njbx m i jij ,..,2,1 1 =≤∑ = Bằng cách thêm biến phụ mọi bài tốn đều cĩ thể đưa về bài tốn cân bằng thu phát. ( cĩ thể dùng thuật tốn đơn hình để giải, song do cĩ nhiều biến nên phức tạp.) b. Các đặc điểm của bài tốn: * Bài tốn cân bằng thu phát luơn cĩ phương án cực biên tối ưu * Mơ tả bài tốn dưới dạng bảng: Thu Phát .b1 .b2 ………………….. .bn .a1 .c11 .c12 ……………….. .c1n .a2 .c21 .c22 …………………. .c2n …………. …… ……. ………………… ….. .am .cm1 .cm2 ………………. .cmn Cho x ={xij} ( i=1,2,…,m; j=1,2,…,n) là phương án của bài tốn. Nếu xij > 0 thì ta gi giá trị này vào gĩc dưới phía phải của ơ (i;j); nếu xij = 0 thì khơng ghi. Vậy ứng với một phương án ta cĩ một tập hợp các ơ tương ứng với các thành phần dương của phương án. Nếu phương án x là cực biên thì hệ véc tơ điều kiện {Aij } tương ứng với thành phần xij >0 sẽ độc lập tuyến tính. Ta gọi là vịng một tập hợp ơ trên bảng mà trong đĩ mỗi ơ đều nằm cùng hàng (cùng cột) chỉ với một ơ đứng trước đĩ, đồng thời nằm cùng cột ( cùng hàng) chỉ với một ơ đứng sau nĩ. Như vậy một hàng hoặc một cột mà vịng đi qua thì phải chỉ qua hai ơ, do đĩ tổng số ơ trong vịng là một số chẵn ( ít nhất là 4 ơ) .Một tập hợp ơ khơng chứa vịng gọi là tập ơ khơng tạo thành vịng. Người ta chứng minh được rằng: ðịnh lý : ðặc điểm của phương án cự biên Phương án x={xij} ( i=1,2,…,m; j=1,2,…,n) là phương án cực biên khi và chỉ khi tập hợp các ơ (i;j) tương ứng với xiJ > 0 khơng tạo thành vịng. Do hạng của ma trận hệ ràng buộc là m + n -1nên một phương án cực biên tối ưu cĩ tối đa m +n -1 thành phần dương và do đĩ số tối đa các ơ trong bảng khơng tạo thành vịng cũng bằng m +n -1. Nếu x là phương án cực biên ta gọi m +n -1 ơ khơng tạo thành vịng là tập hợp ơ cơ sở ( ơ chọn), các ơ cịn lại gọi là ơ phi cơ sở ( ơ loại) của phương án cự biên x. 2. Xây dựng phương án cực biên: 2.1. Nguyên tắc phân phối tối đa: Khi xây dựng PACB ứng với một ơ ij nào đĩ ta gán cho xil = α . ta nĩi đã phân phối cho ơ (i,j) một lượng hàng hĩa là α và gi α vào ơ này. - Lấy một ơ (i,j) tùy ý và phân phối cho nĩ lượng hàng hĩa tối đa cĩ thể, tức là α = min{ai;bj}. khi đĩ : + Nếu xiJ = α = ai yêu cầu của trạm phát Ai được thỏa mãn, loại hàng i ra khỏi bảng, sửa lại yêu cầu của tram thu b’j = bj – α + Nếu xij = α = bj yêu cầu của trạm thu Bj được thỏa mãn, loại cột j ra khỏi bảng, sửa lại yêu cầu của trạm phát a’i = ai – α + Nếu xij = α =ai = bj thì yêu cầu của trạm phát và thu đều thỏa mãn, loại hàng i cột j ra khỏi bảng. Tiếp tục như trên cho tới khi yêu cầu của mọi trạm thu, phát đều thỏa mãn. Các ơ được phân phối cĩ xij > 0 khi đĩ tập hợp x ={xij} ( i=1,2,…,m; j=1,2,…,n) là một phương án của bài tốn vì chúng thỏa mãn mọi ràng buộc. hơn nữa nĩ cịn là phương án cực biên, tập hợp các ơ được phân phối chính là tập hợp ơ cơ sở. Nếu phân phối được đúng m +n - 1 ơ thì PACB tương ứng khơng suy biến, nếu ít hơn m+n-1 ơ thì đĩ là PACB suy biến, để cĩ được tập hợp ơ cơ sở cần bổ sung số ơ cho tới khi đủ m+n-1 ơ, ơ bổ sung cĩ xij =0 và khơng tạo thành vịng với những ơ cơ sở đã cĩ. 2.2.Các phương pháp xây dưng phương án cực biên: Sử dụng nguyên tắc phân phối tối đa, tùy thuộc vào cách ưu tiên phân phối ta cĩ những phương pháp khác nhau để xây dựng phương án cực biên. - phương pháp gĩc tây – bắc: Luơn ưu tiên phân phối cho ơ nằm ở gĩc tây-bắc của bảng ( gĩc trên bên trái bảng). Phương pháp này khơng quan tâm tới chi phí mà thực hiện máy mĩc theo sự phân bố của các trạm trên bảng. - Phương pháp chi phí nhỏ nhất (đường gần) Luơn ưu tiên phân phối cho ơ cĩ ciJ nhỏ nhất trong bảng đang xét. Phương án cực biên thu được từ phương pháp này gần với phương án tối ưu hơn. Thí dụ 2: Thu Phát 30 20 25 35 40 30 13 7 6 2 [30] 12 20 5 1 [20] 10 5 11 40 10 5 [0] 3 7 [5] 14 [35] 60 6 [30] 3 2 [25] 11 10 [5] Ơ (2;2) cĩ cước phí c22 =1 nhỏ nhất nên ưu tiên phân phối thỏa yêu cầu thu và phát, loại dịng 2, cột 2 . Ơ (1;4) cĩ c14 = 2 được ưu tiên thứ hai lấy của trạm phát A1 là a1 = 30 , trạm thu B4 cịn cần lượng hàng là 35 -30 =5 Chỉ cĩ thể lấy từ các trạm phát cịn hàng do ơ (3;4) cĩ cước phí nhỏ nhất trong các ơ cùng cột, lấy 5 đơn vị hàng hĩa từ trạm phát A3,…… Kết quả trên đã phân phối cho 7 ơ ta được một phương án cực biên suy biến. ðể cĩ tập ơ là cơ sở cần bổ sung thêm một ơ với xịj = 0 chẳng hạn ơ (3;2) 3. Phương pháp thế vị giải bài tốn vận tải. 3.1. Bài tốn đối ngẫu và tiêu chuẩn tối ưu: Xét bài tốn vận tải: ∑∑ = = ⇒= m i n j ijij Minxcxf 1 1 )1()( miax n j iij ,..,2,1 1 ==∑ = (2) njbx m i jij ,..,2,1 1 ==∑ = (3) .xij ≥ 0 mọi i;j (4) Ký hiệu ui; vj là các biến đối ngẫu đối với hệ ràng buộc (2) và (3); u = {ui}; v = {vj}; );(~ vuf là hàm mục tiêu của bài tốn đối ngẫu, để tiện cho việc giải thích ý nghĩa kinh tế ta đổi dấu hệ ràng buộc (2). Khi đĩ bài tốn đối ngẫu cĩ dạng: jicuv Maxuavbvuf ijij m i ii n j jj ; );(~ 11 ∀≤− ⇒−= ∑∑ == Trong cặp bài tốn đối ngẫu này cĩ m*n cặp ràng buộc đối ngẫu: xij ≥ 0 và vj – ui ≤ cij i=1,2,..,m; j =1,2,..,n ðịnh lý: Tiêu chuẩn tối ưu ðiều kiện cần và đủ để phương án x = {xij} của bài tốn vận tải tối ưu là tồn tại hệ thống {ui;vj} thỏa mãn điều kiện: i) vj – ui ≤ cij ( với mọi i, j) ii) vj –ui = cij nếu xij > 0 Trị số của các ui; vj trong tiêu chuẩn gọi là các thế vị hàng và cột Bài tốn đối ngẫu cĩ ý nghĩa kinh tế hiểu như sau: xem thế vị hàng ui là giá trị một đơn vị hàng hĩa tại nơi sản xuất Ai , cịn thế vị vj là giá trị một đơn vị hàng hĩa tại nơi tiêu thụ Bj . ðiều kiện ii) cho thấy trong một phương án vận chuyển tối ưu một đơn vị hàng hĩa tại nơi tiêu thụ cĩ giá trị bằng giá trị một đơn vị hàng hĩa tại nơi sản xuất cộng thêm chi phí vận chuyển cịj. ðiều kiện i) cho thấy chênh lệch về giá trị hàng hĩa giữa nơi tiêu thụ và nơi sản xuất bất kỳ đều khơng vượt quá chi phí vận chuyển giữa hai nơi ấy. 3.2. Thuật tốn của phương pháp thế vị: Bước 1: xây dựng phương án cực biên Sử dụng một trong các phương pháp xây dựng phương án cực biên đã biết ( chẳng hạn phương án chi phí nhỏ nhất) ký hiệu phương án là x0 ( cĩ đủ m + n -1 thành phần cơ sở) Bước 2: Xây dựng hệ thống thế vị {ui, vi}: -Lấy một hàng i bất kỳ, cho nĩ một thế vị tùy ý ( thường là ui = 0 ). Các thế vị hàng, cột cịn lại xác định theo cơng thức: vj = ui + ciJ ; ui đã biết và (i,j) 0S∈ .ui = vj – cij , vj đã biết và (i,j) 0S∈ Bước 3: kiểm tra tiêu chuẩn tối ưu Theo cách xây dựng, hệ thống thế vị {ui, vj } thỏa mãn điều kiện ii) đối với các ơ cơ sở (i,j) 0S∈ do đĩ chỉ cần kiểm tra điều kiện i) đối với các ơ phi cơ sở (i,j) 0S∉ nếu chúng thỏa mãn điều kiện i) thì phương án x0 tương ứng là phương án tối ưu. Nếu cĩ một ơ phi cơ sở (i,j) 0S∉ mà vj – ui > cij thì hiển nhiên x 0 chưa là phương án tối ưu. Gọi những ơ này là ơ vi phạm. Tính đại lượng: ijijij uuv −−=∆ . Bước 4: ðiều chỉnh phương án. Giả sử 00 ),( SkrMax rkijij ∉∆=∆>∆ ơ (r,k) được chọn làm ơ điều chỉnh , ơ (r,k) sẽ tạo thành vịng duy nhất với một số ơ thuộc S0. Tìm vịng này và ký hiệu là V . Trên vịng đánh dấu ơ lẻ, chẵn sen kẽ nhau bắt đầu từ ơ (r,k) là ơ lẻ. ký hiệu là Vl; Vc -Tìm cij VjixMin ∈),(;0 Giả sử cstiJ VjiqxxMin ∈== ),(00 rõ ràng q ≥ 0 và q gọi là lượng điều chỉnh. -Thực hiện phép biến đổi trên vịng V theo cơng thức:       ∈− ∈+ ∉ = Cij Lij ij Vjiqx Vjiqx Vjix x ,( ,( ),( 0 0 0 1 0 Sau khi điều chỉnh ơ điều chỉnh (r,k) sẽ trở thành ơ cơ sở cịn (s,t) ứng với q sẽ thành ơ phi cơ sở. ta được phương án cự biên x1 tốt hơn phương án cực biên x0 . ðối với phương án x1 ta quay lại bước 2 và quá trình được lặp lại sau một số hữu hạn bước sẽ tìm được phương án cự biên tối ưu. Chú ý: - Khi cĩ nhiều ơ cĩ thể được chon làm ơ điều chỉnh thì ta chon một ơ tùy ý trong các ơ đĩ - Trường hợp bài tốn suy biến thì cĩ thể q = 0 . khi ấy vẫn thực hiện thuật tốn bình thường - Nếu PACB tối ưu x* cos vj – ui < cij với mọi ơ phi cơ sở thì đĩ là phương án tối ưu duy nhất. Thí dụ 2: Bằng phương pháp thế vị giải bài tốn vận tải cho bởi bảng sau: Thu Phát 76 62 88 45 40 79 10 [64] 19 9 6 [15] 8 102 13 11 [14] 8 [88] 7 4 70 12 17 10 5 [30] 3 [40] 60 12 [12] 18 [48] 18 7 9 ðiều chỉnh: vj = ui + ciJ ; ui đã biết và (i,j) 0S∈ .ui = vj – cij , vj đã biết và (i,j) 0S∈ 12 18 15 8 6 Thu Phát 76 62 88 45 40 2 79 10 C [64] 19 9 L +4 [] 6 [15] 8 7 102 13 11 L [14] 8 C [88] 7 4 3 70 12 17 10 +2 5 [30] 3 [40] 0 60 12 L [12] 18 C [48] 18 7 +1 9 12 14 11 8 6 Thu Phát 76 62 88 45 40 2 79 10 [16] 19 9 [84] 6 [15] 8 3 102 13 11 [62] 8 [40] 7 4 3 70 12 17 10 5 [30] 3 [40] 0 60 12 [60] 18 18 7 +1 9 12 14 11 7 5 Thu Phát 76 62 88 45 40 2 79 10 L [31] 19 9 [84] 6 C [] 8 3 102 13 11 [62] 8 [40] 7 4 2 70 12 17 10 5 [30] 3 [40] 0 60 12 C [45] 18 18 7 L [15] 9 Sau khi điều chỉnh ta thấy phương án cuối thỏa mãn vj – ui ≤ cij với mọi (i,j) S∉ . Phương án là tối ưu duy nhất. Trị tối ưu là f(x*) = 31*10 + 9*84 + 11*62 + 8*40 + 5*30 + 3*40 + 12*45 + 7*15 =2659