Giáo trình Toán kinh tế - Nguyễn Hoàng Anh Khoa

QUAN VỀ TOÁN KINH TẾ 1.1 Đối tượng nghiên cứu của môn học 1.1.1 Khái quát về tối ưu hóa Trong hoạt động thực tiễn, nhất là trong quá trình quản lý, điều hành hệ thống kinh tế - xã hội chúng ta luôn mong muốn đạt được những kết quả tốt nhất theo các tiêu chuẩn nhất định nào đó. Mỗi vấn đề khác nhau của thực tế dẫn đến các bài toán tối ưu khác nhau. Để giải quyết các bài toán đó, một loạt các lý thuyết toán học ra đời để dặt cơ sở lý luận, đề ra các phương pháp tìm lời giải, tính khả thi của các bài toán thực tế Từ đó hình thành một lớp các phương pháp toán học giúp ta tìm lời giải tốt nhất choa các bài toán thực tế, gọi là các phương pháp tối ưu. Lớp các phương pháp tối ưu bao gồm nhiều lý thuyết toán học khác nhau, tiêu biểu là: Quy hoạch toán học, lý thuyết đồ thị, lý thuyết trò chơi Trong quy hoạch toán học, tiêu biểu có Quy hoạch tuyến tính, Quy hoạch phi tuyến, Quy hoạch nguyên Trong lý thuyết đồ thị, tiêu biểu có Bài toán tối ưu trên mạng, sơ đồ Pert, các bài toán luồng Trong lý thuyết trò chơi, tiêu biểu có Lý thuyết lựa chọn quyết định, Bài toán trò chơi chiến lược 1.1.2 Nội dung nghiên cứu của môn học Chương trình học phần “Toán kinh tế” với 2 tín chỉ ta nghiên cứu các nội dung: - Quy hoạch tuyến - Bài toán vận tải - Bài toán tối ưu trên mạng. Sơ đồ Pert. 1.2 Cơ sở giải tích lồi 1.2.1 Không gian Rn Kí hiệu Rn = { x = (x1 ; x2 ;; xn) | xi  R, i = 1,2,..,n } là KGVT R n Với mọi x = (x1 ; x2 ;; xn); y = (y1 ; y2 ;; yn)  R n và k  R. Ta có các phép toán : Cộng x + y = (x1 + y1 ; x2 + y2 ;; xn + yn) Nhân một số kx = (kx1 ; kx2 ;; kxn) Tích vô hướng = x1y2 + x2y2 ++ xnyn 1.2.2 Đường thẳng, đoạn thẳng, siêu phẳng a) Đường thẳng, đoạn thẳng trong Rn Cho a, b  Rn. Ta gọi đường thẳng qua a, b là tập các điểm x  Rn có dạng: x = (1 – k). a + k.b với k  R Đoạn a, b kí hiệu [a,b] là tập các điểm x  Rn có dạng: x = (1 – k). a + k.b với k  [0;1] Th.s. Nguyễn Hoàng Anh Khoa 3 b) Siêu phẳng trong Rn Siêu phẳng là tập các x = (x1; x2;..;xn) thỏa mãn phương trình bậc nhất dạng: a1x1 + a2x2 ++ anxn = c 1.2.3 Tập lồi, đa diện lồi Tập D  Rn được gọi là tập lồi nếu với mọi a, b  Rn ta đều có [a,b]  D. Ví dụ: a) Chứng minh giao của 2 tập lồi là tập lồi. b) Chứng minh tập D = {(x1; x2;..;xn) | a1x1 + a2x2 ++ anxn ≤ c}. Nhận xét: Tập nghiệm của hệ bất phương trình dạng: 11 1 12 2 1n n 1 21 1 22 2 2n n 2 m1 1 m2 2 mn n m a x a x ... a x b a x a x ... a x b .......................................... a x a x ... a x b                 là một tập lồi. Hơn nữa, nếu bị chặn thì nó gọi là một đa diện lồi. 1.2.4 Điểm cực biên Cho D là tập lồi, x  D. Điểm x gọi là điểm cực biên nếu x không thể là điểm trong của đoạn [a,b]  D. Điểm cực biên của đa diện lồi gọi là đỉnh. Ví dụ: Kí hiệu D = {(x;y)  R2 | x – y ≥ 0; x + y ≥ 0; 2x + y ≤ 3} a) Biểu diễn D trong mặt phẳng Oxy b) Chứng minh D là đa diện lồi, xác định các điểm cực biên của D. Th.s. Nguyễn Hoàng Anh Khoa 4 CHƯƠNG 2. QUY HOẠCH TUYẾN TÍNH 2.1 Một số tình huống trong kinh tế và mô hình bài toán quy hoạch tuyến tính 2.1.1 Bài toán sản xuất: Một xí nghiệp có thể sản xuất n loại sản phẩm, ký hiệu S1, S2,, Sn từ m loại nguyên liệu khác nhau, ký hiệu N1, N2Nm. Biết aij, là khối lượng nguyên liệu loại Ni tiêu hao bởi một đơn vị sản phẩm loại Sj; bi là khối lượng nguyên liệu loại Ni mà xí nghiệp có thể huy động được ; cj là lợi nhuận thu được khi sản xuất và bán một đơn vị sản phẩm loại Sj, i = 1,,m ; j = 1,2,,n. Giả sử xí nghiệp có thể sản xuất và tiêu thụ sản phẩm không hạn chế. Hãy tìm số đơn vị sản phẩm mỗi loại mà trong phạm vi số nguyên liệu huy động được, xí nghiệp có lợi nhuận tối đa. Lập mô hình : Đặt xj là số đơn vị sản phẩm loại Sj mà xí nghiệp sản xuất j=,2,..,n. Ta có mô hình bài toán: n j j j 1 n ij j i j 1 j Z c x max a x b , i 1,2,...,m x 0, j 1,2,...,n              2.1.2 Bài toán lập kế hoạch vốn đầu tư cho sản xuất. Cần đầu tư vốn vào m xí nghiệp để sản xuất ra n loại sản phẩm. Qua phân tích, người ta biết rằng khi đầu tư một đơn vị tiền vào xí ngiệp i (i =1,2,..,m) trong một năm sẽ sản xuất ra được bij đơn vị sản phẩm loại j (j =1,2,..,n ). Tống số nguyên liệu và giờ công hằng năm có thể cung cấp là A và C. Hãy lập một kế hoạch sản xuất sao cho sản xuất được ít nhất Bj đơn vị sản phẩm loại j mà vốn đàu tư ít nhất. Biết các mức hao phí về nguyên liệu và lao động (giờ công) khi sản xuất ra một đơn vị sản phẩm j ở xí nghiệp i là bij và cij. Lập mô hình: Đặt xi là đơn vị tiền đầu tư vào xí nghiệp i (i = 1,2,..,n). Ta có mô hình bài toán: n j j 1 n ij i j i 1 m n ij ij i 1 j 1 m n ij ij i 1 j 1 j Z x min b x b a b A ,i 1,2,..,m; j 1,2,..,n. c b C x 0                         Th.s. Nguyễn Hoàng Anh Khoa 5 2.2 Bài toán quy hoạch tuyến tính dạng tổng quát 2.2.1 Bài toán Tìm min (max) của Z = n j j j 1 c x   = c1x1+ c1x1+..+ cnxn với các ràng buộc n ij j i j 1 j a x ( , , ) b , i 1,2,...,m x ( , ) 0 , j 1,2.....,n             trong đó cj, aij, bi là những số thực cho trước. 2.2.2 Các ký hiệu và khái niệm  Hàm Z gọi là hàm mục tiêu  Một vectơ x thoả mãn các ràng buộc gọi là một phương án  Tập hợp X gồm các phương án gọi là tập phương án.  Phương án x*  X tại đó hàm mục tiêu Z đạt giá trị nhỏ nhất (lớn nhất) gọi là một phương án tối ưu. 2.2.3 Giải bài toán QHTT hai biến bằng phương pháp hình học Bài toán: Z = c1x1 + c2x2  min(max) với các ràng buộc ci1x1 + ci2x2 (≤; ≥) bi , i=1,2,..,m. x1,2 (≤; ≥) 0 Phương pháp: Bước 1: Biểu diễn tập phương án X trên mặt phẳng tọa độ Bước 2: Biểu diễn hàm mục tiêu trên mặt phẳng tọa độ với Z là số thực nào đó Bước 3: Cho Z biến thiên trong khoảng có phần chung với X, từ đó xác định Zmin(max) và phương án tối ưu x* để Z nhận giá trị min(max) đó. Ví dụ: Giải bài toán Z = x1 + x2  min 1 2 1 2 1 2 x 2x 9 2x x 6 x ;x 0        2.2.4 Một số tính chất của bài toán QHTT Tính chất 1: Tập các phương án của bài toán QHTT là tập lồi. Tính chất 2: Nếu bài toán QHTT có phương án tối ưu thì nó có ít nhất một phương án tối ưu là điểm cực biên của tập phương án (gọi tắc là phương án cực biên). Th.s. Nguyễn Hoàng Anh Khoa 6 2.3. Bài toán quy hoạch tuyến tính dạng chính tắc 2.3.1 Bài toán QHTT dạng chính tắc Là bài toán dạng: Tìm min (max) của Z = n j j j 1 c x   = c1x1+ c1x1+..+ cnxn với các ràng buộc n ij j i j 1 j a x b , i 1,2,...,m x 0, j 1,2.....,n          trong đó cj, aij, bi là những số thực cho trước. bi ≥ 0. Viết dạng ma trận Z c,x min(max) Ax B x 0        Trong đó 1 111 12 1n 21 22 2n 2 2 m1 m2 mn n m x ba a ... a a a ... a x b A ;x ;B ... ... ... ... .. .. a a ... a x b                                  2.3.2 Chuyển đổi bài toán QHTT: Bài toán QHTT dạng tổng quát có thể đưa về dạng chính tắc bằng cách thêm vào một số ẩn phụ. 2.3.3 Hệ liên kết phương án Cho x = (x1 ; x2 ;; xn) là phương án của bài toán QHTT dạng chính tắc. Khi đó, ta có: x1A1 + x2 A2 + + xnAn = b trong đó, 1k 2k k mk a a A a             là cột thứ k của ma trận 11 12 1n 21 22 2n m1 m2 mn a a ... a a a ... a A ... ... ... ... a a ... a             Hệ {Ak | xk > 0} gọi là hệ liên kết của phương án x. Định lí: Giả sử x = (x1 ; x2 ;; xn) là một phương án khác không của bài toán QHTT dạng chính tắc. Khi đó, x là phương án cực biên khi và chỉ khi hệ liên kết của x độc lập tuyến tính Th.s. Nguyễn Hoàng Anh Khoa 7 Ví dụ: Xét bài toán 1 2 3 1 2 3 1 2 3 j Z 4x x x min 2x x x 5 x x 4x 2 x 0, j 1,3.                Chứng minh x = (7/3;1/3;0) là phương án cực biên. 2.4 Phương pháp đơn hình Trong mục này ta chỉ xét bài toán QHTT dạng chính tắc Z c,x min Ax B x 0        A cỡ mxn và rankA = m ≤ n Giả sử x0 = (x10; x20; ; xm0; 0; ;0) với xi0 >0, i =1,2,..,m là phương án cực biên Khi đó, A1,A2, ..., Am là hệ liên kết hay x10A1 + x20A2 + + xm0Am = B Với mỗi Aj tìm Xj = (x1j; x2j; ; xmj) sao cho x1jA1 + x2jA2 + + xmjAm = Aj Đặt j = c1x1j + c2x2j + + cmxmj – cj 2.4.1 Các định lí Định lý 1:(Dấu hiệu tối ưu) Nếu j ≤ 0, j thì x0 là phương án tối ưu, và ngược lại. Định lý 2: Nếu tồn tại j > 0 và xkj ≤ 0 với k =1,2,..,m, thì bài toán Quy hoạch tuyến tính dạng chính tắc không có phương án tối ưu. Định lí 3: Nếu tồn tại k, s sao cho   0 0max : 0 và min : 0              i s j j k ik s ik sk x x x x x  Xét cơ sở mới bằng cách thay As bởi Ak. Khi đó, phương án X ứng với cơ sở mới là phương án tốt hơn phương án X0 Ví dụ: Xét bài toán 1 2 3 1 2 4 2 3 4 ( ) 2 2 min 4 6 2 5 8 0, 1,2,3,4.                 j f x x x x x x x x x x x j Chứng minh x = (6;0;8;0) là phương án cực biên nhưng không là phương án tối ưu. Áp dụng định lí 3 tìm phương án tốt hơn, kiểm xem phương án mới có phải là phương án tối ưu không? Th.s. Nguyễn Hoàng Anh Khoa 8 2.4.2 Bài toán QHTT dạng chính tắc có sẵn ma trận đơn vị Xét bài toán ( ) , min 0        f x c x Ax b x Trong đó, b > 0 và A có sẵn một ma trận đơn vị cấp m. Không mất tính tổng quát có thể giả sử đó là m cột đầu A1, A2,..,Am. Lúc đó, phương án cực biên x trong bước lặp đầu tiên là: x0 = (b1,b2,...,bm, 0, ..,0) hệ liên kết là A1, A2,..,Am. Hơn nữa, Xj = (a1j; a2j; ; amj) Để thuận tiện ta sắp xếp dữ liệu lên bảng như sau (gọi là bảng đơn hình) Cơ sở H.số P.án c1 c2 ... cm cm+1 ... cn X1 X2 Xm Xm+1 Xn A1 A2 : Am c1 c2 : cm b1 b2 : bm 1 0 : 0 0 1 : 0 ... ... ... 0 0 : 1 a1m+1 a2m+1 : amm+1 a1n a2n : amn f(x0) 0 0 ... 0 m+1 n Áp dụng định lí 1,2,3 ta có thuật toán đơn hình Bước 1: Tính j , j = 1,2,..,n Nếu j ≤ 0 với j = 1,2,..,n. thì x0 là phương án tối ưu. Nếu tồn tại j > 0 và xkj ≤ 0 với k =1,2,..,m, thì bài toán không có phương án tối ưu. Bước 2: Xác định k,s sao cho   0 0max : 0 và min : 0              i s j j k ik s ik sk x x x x x  Bước 3: Thay As bởi Ak. Tìm phương án và các Xj ứng với hệ liên kết mới. Phương pháp: ij ' sk ij ik ij sj sk x khi i j x x x x x x         . Quay về bước 1 Ví dụ: Giải bài toán 1 2 3 4 5 1 3 4 5 2 4 5 3 4 5 6 j f (x) x x 2x 2x x min x x x x 2 x x x 6 4x 2x 3x x 9 x 0, j 1,6.                        Th.s. Nguyễn Hoàng Anh Khoa 9 Giải: Vì [A1,A2,A6] là ma trận đơn vị. Ta có bảng đơn hình 1 -1 2 -2 -1 0 CS HS PA X1 X2 X3 X4 X5 X6  A1 1 2 1 0 1 1 -1 0 2 A2 -1 6 0 1 0 1 1 0 6 A6 0 9 0 0 4 2 3 1 4,5 0 0 -1 2 -1 0 A4 -2 2 1 0 1 1 -1 0 A2 -1 4 -1 1 -1 0 2 0 2 A6 0 5 -2 0 2 0 5 1 1 -2 0 -3 0 1 0 A4 -2 3 0,6 0 1,4 1 0 0,2 A2 -1 2 -0,2 1 -1,8 0 0 -0,4 A5 -1 1 -0,4 0 0,4 0 1 0,2 -9 -1,6 0 -3,4 0 0 -0,2 Vậy phương án tối ưu là: x1 = 0; x2 = 2; x3 = 0; x4 = 2; x5 =1; x6 = 0 và fmin = – 9 2.4.3. Bài toán QHTT dạng chính tắc không có sẵn ma trận đơn vị Xét bai toán ( ) , min (*) 0       f x c x Ax b x trong đó A không có ma trận đơn vị Xét bài toán M 1 2( ) .. min ( ) 0          n n n mf x Mx Mx Mx Bx b M x trong đó B = [A|I] cỡ mx(n+m), M là số lớn nhất. Định lí 4: Nếu x0 = (x10;x20;..;xn0) là phương án tối ưu của bài toán (*) thì x=(x10;x20;..;xn0;0;..;0) là phương án tối ưu của bài toán M và ngược lại. Chú ý: 0, 0 0, 0           j j j j j j j M       0, 0 0, 0           j j j j j j j M       ; .              k j k j k k k j j j k j k j M M             Th.s. Nguyễn Hoàng Anh Khoa 10 BÀI TẬP CHƯƠNG 2 Câu 1. Một xí nghiệp có 2 máy A, B dùng để sản xuất ra 3 loại sản phẩm. Định mức thời gian (đơn vị: giờ) cho mỗi đơn vị sản phẩm đối với từng máy và quỹ thời gian (đơn vị: giờ) của từng máy được cho trong bảng sau: SP MÁY Định mức thời gian cho mỗi đơn vị sản phầm Quỹ thời gian SP1 SP2 SP3 A 1 2 1 120 B 2 1 1 90 Giá 1 SP (đv 1000 đ) 40 30 35 Hãy lập mô hình toán học cho bài toán: Tìm phương án sản xuất sao cho tổng thu nhập là lớn nhất mà vẫn đảm bảo an toàn cho máy. Câu 2. Hai địa phương Ninh Bình và Hưng Yên cung cấp Khoai với khối lượng 200 tấn và 300 tấn cho 3 địa phương tiêu thụ Khoai là Hải Phòng, Nghệ An và Nam Định với yêu cầu tương ứng là 170 tấn, 200 tấn và 130 tấn cước phí vận chuyển (nghìn/ tấn) cho trong bảng sau: Nơi tiêu thụ Hải Phòng Ngệ An Nam Định Ninh Bình 20 12 25 Hưng Yên 12 24 14 Hãy lập mô hình toán học cho bài toán: Tìm kế hoạch vận chuyển sao cho tổng chi phí nhỏ nhất. Câu 3. Giải các bài toán quy hoạch tuyến tính sau bằng phương pháp đơn hình: 1 2 3 4 5 1 3 4 5 2 3 5 3 4 5 6 j a) f (x) x x 2x 2x x min x x x x 1 x x x 6 2x 4x 3x x 2 x 0, j 1, 6.                        1 2 3 4 1 2 4 2 3 4 2 3 4 j b) f (x) 2x x 3x x min x 2x x 8 x x 4x 2 x 3 x 2x 4 x 0, j 1; 2;3; 4.                     1 2 3 4 1 3 4 1 2 3 4 1 4 j c) f (x) 3x 5x 2x x min x 2x 2x 4 2x x x x 5 x 2x 6 x 0, j 1; 2;3; 4.                    1 2 4 1 2 3 1 2 4 1 2 j d) f (x) 2x x x min 2x x x 1 x x x 4 x x 2 x 0, j 1; 2;3; 4.                     Th.s. Nguyễn Hoàng Anh Khoa 11 Chương 3. BÀI TOÁN VẬN TẢI 3.1. Các khái niệm 3.1.1. Bài toán vận tải a. Bài toán Có m địa điểm A1,A2,..,Am cùng sản xuất một loại hàng với lượng hàng là a1,a2,..,an. Có n địa điểm B1,B2,..,Bn cùng tiêu thụ loại hàng đó với lượng hàng là b1,b2,..,bn. Hàng một đơn vị hàng được vận chuyển từ Ai đến Bj với cước phí là cij. Gọi xij là lượng hàng vận chuyển từ Ai đến Bj. Xác định xij , i=1,2,,m ; j =1,2,..,n để tổng cước phí vận chuyển nhỏ nhất. (hàng được vận chuyển cho đến khi hết hàng hoặc nhu cầu) b. Mô hình bài toán vận tải     1 1 1 1 min (1) 1, (2) 1, (3) 0 (4)               m n ij ij i j n ij i j m ij j i ij Z c x x a i m x b j n x Bài toán vận tải là bài toán QHTT gồm m+n ràng buộc và mn biến số. Một ma trận X gồm các số thực xij không âm thỏa mãn m+n ràng buộc được gọi là một phương án vận tải. Một phương án vận tải cho tổng chi phí vận tải thấp nhất được gọi là phương án vận tải tối ưu (hay nói gọn là phương án tối ưu). c. Dạng bảng của bài toán vận tải Thu Phát b1 b2 bj bn a1 c11 x11 c12 x12 ... c1j x1j ... c1n x1n a2 c21 x21 c22 x22 ... c2j x2j ... c2n x2n : : : : : ai ci1 xi1 ci2 xi2 ... cij xij ... cin xin : : : : : am cm1 xm1 cm2 xm2 ... cmj xmj ... cmn xmn Th.s. Nguyễn Hoàng Anh Khoa 12 3.1.2. Bài toán cân bằng thu phát Bài toán vận tải cân bằng thu phát là bài toán vận tải có tổng lượng hàng thu bằng tổng lượng hàng phát. 1 1    m n i j i j a b Chú ý: Với điều kiện cân bằng thu phát bài toán vận tải trở thành bài toán QHTT dạng chuẩn     1 1 1 1 min (1) 1, (2) 1, (3) 0 (4)               m n ij ij i j n ij i j m ij j i ij Z c x x a i m x b j n x Nhận xét: rankA = m + n – 1 Định lí: Bài toán vận tải cân bằng thu phát luôn có phương án tối ưu. 3.2. Phương pháp tìm phương án cực biên ban đầu Trong mục này ta chỉ xét bài toán vận tải cân bằng thu phát + Ta gọi một đường đi là tập hợp các ô của bảng sao cho cứ hai ô liên tiếp thì nằm trên cùng một dòng hay một cột. Một đường đi khép kín được gọi là chu trình. + Giả sử x = (x11,x12,...,x1n, x21,x22,...,x2n,..., xm1,xm2,...,xmn) là một phương án của bài toán vận tải, nếu xịj > 0 thì ô (i,j) gọi là ô chọn. Định lí: Phương án x là một phương án cực biên của bài toán vận tải và chỉ khi tập các ô chọn tương ứng với nó không chứa chu trình. 3.2.1. Phương pháp góc Tây-Bắc Chúng ta ưu tiên phân phối lượng hàng nhiều nhất vào ô ở góc Tây Bắc. Nếu nơi nào đủ hàng thì ta xóa cột chứa nơi nhận đó; nếu nơi phát nào hết hàng thì ta xóa dòng chứa nơi phát đó. ( Đường đi) ( Chu trình ) X X X X X X X X X X X X Th.s. Nguyễn Hoàng Anh Khoa 13 3.2.2. Phương pháp cước phí cực tiểu Chọn ô cij có giá trị nhỏ nhất trong bảng chi phí vận chuyển. Tính và điền vào ô có giá trị xij = min (ai, bj). Sau đó, ta không xét hàng hoặc cột có dự trữ đã hết hay nhu cầu đã thoả mãn. Nếu ai = bj thì không xét đồng thời cả cột Bj lẫn hàng Ai. Từ phần còn lại của bảng ta lại chọn ô có giá trị nhỏ nhất và quá trình phân phối tiếp tục cho đến khi thoả mãn nhu cầu ở các điểm tiêu thụ. Ví dụ: Tìm phương án cực biên của bài toán vận tải cho bởi bảng 35 25 45 30 5 2 3 75 2 1 1 3.3. Phương pháp thế vị giải bài toán vận tải Định lí: Giả sử x = (x11,x12,...,x1n, x21,x22,...,x2n,..., xm1,xm2,...,xmn) là một phương án cực biên của bài toán vận tải. Tính  ij = u i + v j – c ij với  ij = 0 ở các ô chọn ký hiệu E (số ô chọn của E là m + n – 1) - Nếu  ij  0 với mọi (i,j) thì x là phương án tối ưu - Ngược lại, + Giả sử  ij là ô có giá trị lớn nhất, đặt E:=E U (i,j) + Gọi G là chu trình đi qua ô (i,j), tiến hành đánh dấu “+”, “-“ liên tiếp bắt đầu từ ô (i,j) được đánh dấu “+”. Kí hiệu G+ là tập các ô có dấu “+” và G - là ô có dấu “-“. + Giả sử min{xij |(i,j)G - } = xst và ( , ) ( , ) ( , )             ij ij ij ij x a i j G x x a i j G x i j G đặt E’:=E\(s,t). Khi đó, phương án x’ = (x’ij) là phương án cực biên mới tốt hơn phương án x. Các bước giải bài toán vận tải Bước 1: Thành lập một phương án cực biên ban đầu, số ô chọn là m+n-1, cũng có thể có ô chọn không. Bước 2: Xác định ui và vj Tính  ij. Nếu  ij  0 với mọi (i,j) thì x là phương án tối ưu Ngược lại, chuyển sang bước 3. Bước 3: Xây dựng phương án mới như định lí. Quay về bước 2. 3.4. Một số dạng của bài toán vận tải + Với bài toán vận tải có ô cấm, ta xem ô cấm như ô bình thường nhưng cước phí là M rất lớn rồi giải bình thường. + Với bài toán vận tải không cần bằng thu phát, ta thêm vào trạm thu hoặc trạm phát giả với cước phí bằng 0 rồi giải bình thường. Th.s. Nguyễn Hoàng Anh Khoa 14 BÀI TẬP CHƯƠNG 3 Câu 1: Giải bài toán vận tải sau: Thu Phát 5 10 15 10 1 2 1 8 3 4 2 12 3 1 3 Câu 2: Giải bài toán vận tải sau: Thu Phát 8 7 5 6 2 2 4 4 3 1 2 10 1 3 2 Câu 3: Giải bài toán vận tải sau: Thu Phát 10 8 12 15 1 3 2 10 3 4 1 Câu 4: Giải bài toán vận tải sau: Thu Phát 15 10 10 1 2 8 3 4 12 2 1 Câu 5: Giải bài toán vận tải sau: Thu Phát 20 15 25 10 1 3 3 20 2 1 30 1 2 3 Th.s. Nguyễn Hoàng Anh Khoa 15 Chương 4. BÀI TOÁN TỐI ƯU TRÊN MẠNG 4.1. Một số khái niệm cơ bản 4.1.1 Đồ thị, đồ thị có hướng Đồ thị: (Graph) là một cặp tập hợp, ký hiệu G = (X,A), trong đó X = {x1;x2;;xn} là tập các điểm (đỉnh, nút), A là tập các nhánh (cạnh, cung) nối tất cả hoặc một phần các điểm của đồ thị lại với nhau. Nhánh nối liền đỉnh i và j, ký hiệu là (i;j). Nhánh định hướng: Một nhánh được định hướng (ký hiệu mũi tên) gọi là cung. Đồ thị có hướng: Đồ thị G = (X,A) trong đó A là tập hợp các cung gọi là đồ thị định hướng (có hướng). 4.1.2 Biễu diễn đồ thị dưới dạng ma trận Xét đồ thị G = (X,A). Ma trận liên hệ trực tiếp của đồ thị được ký hiệu là A = [aij] và được xác định như sau: ij 1, Gcócung(i, j) a 0,G khôngcócung(i, j)     4.2 Mạng liên thông ngắn nhất. 4.2.1 Bài toán Cho đồ thị vô hướng G = (X,A) trên mỗi cạnh đồ thị có gắn một số không âm, gọi là độ dài của cạnh đó (độ dài cạnh (i,j) ký hiệu cij). Hãy tìm một cây (đường nối tất cả các đỉnh) của đồ thị sao cho tổng độ dài các cạnh là nhỏ nhất 4.2.2 Ý nghĩa bài toán Nếu coi các đỉnh của đồ thị là các trạm thông tin, trạm xăng thì nên đặt đường dây, hệ thống cáp, ống dẫn xăng dầu như thế nào để tiết kiệm chi phí nhất? 4.2.3 Thuật toán Prim Ký hiệu T là tập các đỉnh và cạnh của cây (cần xác định T) Bước 1: Giải sử ckl = min{cij| (i,j)  A}. T:= {(k,l)} Bước 2: Kiểm tra T là mạng liên thông . Kết luận T. Ngược lại, sang bước 3 Bước 3: Tìm cst = min {cij với xi  T và xj T}. T:=T{(s,t)}. Quay về Bước 2. Ví dụ : Tìm mạng liên thông ngắn nhất và tính độ dài của sơ đồ mạng 2 1 4 2 3 4 3 7 5 5 7 5 6 3 4 5 8 7 6 Th.s. Nguyễn Hoàng Anh Khoa 16 Giải Bước 1 : min(cij) = c12 = 2. T := {(1,2)} Bước 2 : min{c13 = 7; c14 = 5; c24 = 4 ;c25 = 7} = c24 = 4. T := {(1,2) ;(2,4)} Bước 3 : min{c13 = 7; c25 = 7 ; c43 =3 ; c45 = 5 ; c46 = 5; c47 = 8} = c43 = 3 T := {(1,2) ;(2,4) ;(4,3)} Bước 4 : min{ c25 = 7 ; c45 = 5 ; c46 = 5 ; c47 = 8 ; c36 = 6} = c45 = 5 T := {(1,2) ;(2,4) ;(4,3) ;(4 ;5)} Bước 5 : min{c46 = 5 ; c47 = 8 ; c36 = 6 ; c57 = 3} = c57 = 3 T := {(1,2) ;(2,4) ;(4,3) ;(4 ;5) ;(5 ;7)} Bước 6 : min{ c46 = 5; c36 = 6 ; c76 = 4} = c76 = 4 T := {(1,2) ;(2,4) ;(4,3) ;(4 ;5) ;(5 ;7) ; (7 ,6)} Vậy độ dài l(T) = 2 + 4 + 3+ 5 + 3 + 4 = 21 4.3 Bài toán đường đi ngắn nhất. 4.3.1 Bài toán Cho đồ thị G = (X,A), trên mỗi nhánh của A ta gắn một số không âm, biểu thị độ dài của nhánh đó (nhánh (i,j) ký hiệu cij). Trên X lấy xs gọi là đỉnh xuất phát (nguồn) và đỉnh xt gọi là đỉnh kết thúc (đích). Vấn đề đặt ra là: Hãy tìm đường đi ngắn nhất từ đỉnh xs đến đỉnh xt (cung (i,j) chỉ được phép đi từ xi đến xj). 4.3.2 Ý nghĩa bài toán Trong thực tê, việc di chuyển từ A đến B thông qua mạng lưới giao thông có sẵn là chuyện thường gặp (các cung tương ứng đường 1 chiều). Vần đề đặt ra là chọn đường đi ngắn nhất để đảm bảo việc tiết kiệm nhiên liệu, thời gian 4.3.3 Thuật toán Difkatra Bước 1: L(xi) := +∞ (khi i ≠ s) (nhãn tạm thời) L(xs) := 0 + (xs gán nhãn cố định 0 + ) xp:=xs Bước 2: Kiểm tra xp = xt kết luận L(xt) = L(xp). Ngược lại sang bước 3 Bước 3: Thay đổi nhãn tạm thời của các đỉnh xi G(xp) (các đỉnh có gốc xp) L(xi) := min{L(xi); L(xp) + cpi} Tìm xj sao cho L(xj) = min{L(xi) với L(xi) là nhãn tạm thời} L(xj):= L(xj) + (gán nhãn cố định cho xj) xp:=xj Quay về bước 2. Th.s. Nguyễn Hoàng Anh Khoa 17 Ví dụ: Xét sơ đồ mạng Bằng thuật toán Difkatra tìm đường đi ngắn nhất từ x1 đến x7 Giải Đỉnh x1 x2 x3 x4 x5 x6 x7 Vòng 1 0+ +∞ +∞ +∞ +∞ +∞ +∞ Vòng 2 2+ 9 5 +∞ +∞ +∞ Vòng 3 9 5+ 2+8 +∞ +∞ Vòng 4 5+3+ 2+8 5+5 5+8 Vòng 5 10 8+1+ 13 Vòng 6 10+ 9+2 Vòng 7 11+ Vậy đường đi ngắn nhất là x1 -> x4 -> x3 -> x6 -> x7 Tổng độ dài là 5 + 3 + 1 + 2 = 11 4.4. Phương pháp sơ đồ mạng lưới (Mạng Pert) 4.4.1. Sơ đồ mạng Pert Mạng Pert là đồ thị định hướng với hai yếu tố cơ bản là công việc và sự kiện . - C ông việc được biểu thị bằng một cạnh có hướng (cung ) - S ự kiện được biểu thị bằng một đỉnh, tại đỉnh có sự kết thúc một số công việc và sự bắt đầu một số công việc. Trình tự lập sơ đồ mạng  Liệt kê tất cả công việc: các công việc phải được liệt kê theo đúng quy trình công nghệ, theo thứ tự thời gian trước sau. Nên lập theo bảng  Xác định thời gian thực hiện các công việc  Lập sơ đồ Quy tắc lập sơ đồ mạng  Quy tắc 1 sơ đồ lập từ trái sang phải 2 1 4 2 3 4 3 9 5 5 7 5 6 3 2 5 8 8 1 Th.s. Nguyễn Hoàng Anh Khoa 18  Quy tắc 2 các công việc chỉ có thể đi ra khỏi một sự kiện khi các công việc đi vào đó đều hoàn thành.  Quy tắc 3 sơ đồ mạng thường không theo tỉ lệ  Quy tắc 4 tên các sự kiện không được trùng lắp  Quy tắc 5 trên sơ đồ không được có vòng kín  Quy tắc 6 trên sơ đồ không được có đường cụt Các đỉnh Đỉnh xuất phát (khởi công) đánh số 1, các đỉnh còn lại được đánh số nguyên liên tiếp , những đỉnh nào chỉ có cạnh ra mà không có cạnh vào thì đánh trước. Các cung 4.4.2. Đường găng (gant) Sơ đồ Pert cho ta đánh giá được những thông tin: a) Thời gian sớm nhất để hoàn thành công việc Là thời gian sớm nhất để hoàn thành công việc mà không ảnh hưởng đến yêu cầu kỹ thuật Thời gian sớm nhất để hoàn thành công việc tại đỉnh j được ký hiệu là tj s . Ta có t 1 s = 0 t j s = max{(ti s + tij ) | (i,j)  Nj} Trong đó, Nj là tập hợp các cung có ngọn là đỉnh j tij thời gian hoàn thành công việc giữa hai đỉnh i và j b) Thời gian muộn nhất để hoàn thành công việc Là thời gian muộn nhất để hoàn thành công việc mà không ảnh hưởng đến tiến độ của công trình. (kéo dài thời gian hoàn thành công trình) Thời gian muộn nhất để hoàn thành công việc tại đỉnh j được ký hiệu là ti m. Ta có tn m = tn s t i m = min