Giáo trình Toán kinh tế (Nghề: Kế toán - Cao đẳng): Phần 2 - Trường Cao đẳng Cộng đồng Đồng Tháp

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

Thêm vào BST

Báo xấu

21
lượt xem 7
download

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

Giáo trình Toán kinh tế trang bị một số kiến thức về cơ sở lý thuyết, các bài toán cơ bản và các phương pháp giải bài toán trong quy hoạch tuyến tính: Khái niệm và cách thiết lập bài toán quy hoạch tuyến tính, phương án, phương án cực biên, phương án tối ưu của một bài toán quy hoạch tuyến tính;... Mời các bạn cùng tham khảo nội dung phần 2 giáo trình!

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 Toán kinh tế (Nghề: Kế toán - Cao đẳng): Phần 2 - Trường Cao đẳng Cộng đồng Đồng Tháp

CHƢƠNG 3: BÀI TOÁN ĐỐI NGẪU  Giới thiệu Ở chƣơng 2, ta đã xét bài toán quy hoạch tuyến tính min-max nhƣ là hai bài toán tách biệt. Nhƣng thật sự đối với mỗi bài toán min luôn luôn tồn tại bài toán max tƣơng ứng và ngƣợc lại. Bài toán quy hoạch ban đầu đƣợc gọi là bài toán gốc còn bài toán tƣơng ứng của nó đƣợc gọi là bài toán đối ngẫu. Trong nhiều trƣờng hợp, nhờ Lý thuyết đối ngẫu mà các vấn đề phức tạp trong khi giải bài toán gốc sẽ trở nên đơn giản và dễ dàng hơn thông qua giải bài toán đối ngẫu của nó. Ta sẽ luôn tìm đƣợc phƣơng án tối ƣu của bài toán đối ngẫu từ phƣơng án của bài toán gốc và ngƣợc lại.  Mục tiêu - Về kiến thức: + Hiểu rõ về bài toán đối ngẫu là gì. + Ý nghĩa kinh tế của bài toán đối ngẫu, sự cần thiết phải đƣa về bài toán đối ngẫu. + Hiểu đƣợc mối quan hệ giữa bài toán gốc và bài toán đối ngẫu từ đó có những phƣơng pháp tìm ra phƣơng án tối ƣu nhanh hơn. - Về kỹ năng: + Lập đƣợc bài toán đối ngẫu từ bài toán gốc. + Từ phƣơng án tối ƣu của bài toán gốc suy ra đƣợc phƣơng án tối ƣu của bài toán đối ngẫu và ngƣợc lại. - Về năng lực tự chủ và trách nhiệm: Có thái độ nghiêm túc, tự giác học tập và chịu trách nhiệm với kết quả thực hiện. 54
1. Khái niệm 1.1. Bài toán đối ngẫu của bài toán dạng chính tắc Định nghĩa: Cho bài toán gốc (P): f (x) cj xj min (max) n (3.1.1) j1 a x  b i 1,m n ij j i (3.1.2) j1 xj 0, j 1,n (3.1.3) Bài toán (D) sau đây đƣợc gọi là bài toán đối ngẫu của nó: g(y)  by m i i max (min) (3.1.4) i1 a y  () c m ij i j ( j 1, n) (3.1.5) i1 yi tùy ý dấu ( i 1,m) (3.1.6)  Nhận xét - Hàm mục tiêu của (P) f (x) min thì hàm mục tiêu của (D) g(y) max và ngƣợc lại. - Các ràng buộc ở bài toán (D) đều là bất đẳng thức "" nếu f (x) max (hoặc "" nếu f (x) min ) - Số ẩn của bài toán này là số ràng buộc của bài toán kia và ngƣợc lại. - Các hệ số cj và các số hạng tự do bi ở hai bài toán đối ngược nhau. - Ma trận hệ số các ràng buộc ở hai bài toán là chuyển vị của nhau. Hàng a x  b , n i trong ma trận A(aij)mxn xác định ràng buộc thứ i của bài toán gốc ij j i j1 còn cột j trong ma trận A xác định ràng buộc thứ j của bài toán đối ngẫu: a y  () c . m ij i j i1 Ví dụ 1: Bài toán gốc: f (x)  2x1 4x2 3x3 min x1 2x2  x3  2 x 3x 5 2 3 xj 0, j 1,3 Bài toán đối ngẫu của bài toán này là: g(y) 2y1 5y2 max 55
y1  2 2y  y  4  1 2  y1 3y2 3 y1, y2 tùy ý. 1.2. Bài toán đối ngẫu của bài toán dạng tổng quát Quy tắc lập bài toán đối ngẫu đƣợc cho bởi bảng sau: Bài toán gốc P (D) Bài toán đối ngẫu D (P) cj xj max by min n m Hàm mục tiêu f (x)  Hàm mục tiêu g(y)  i i j1 i1     Ràng buộc thứ i: aijxj  bi , i 1, m Ẩn thứ i: yi    0, i 1, m   n j1  tùy ý     Ẩn thứ j: xj   0, j 1, n Ràng buộc thứ j: aij yi  cj , j 1, n m tùy ý i1   Nhận xét: Bài toán đối ngẫu của bài toán đối ngẫu chính là bài toán gốc. Vì vậy ngƣời ta nói cặp bài toán gốc – đối ngẫu là cặp bài toán đối ngẫu nhau.  Cách nhớ max  min Ẩn  Ràng buộc(cùng dấu) Ràng buộc  Ân (ngƣợc dấu) Ẩn  Ràng buộc (ngƣợc Ràng buộc  Ân (cùng dấu) min  max dấu) Ví dụ 2: Tìm bài toán đối ngẫu của bài toán f (x) 2x1 3x2 x3 x4 max 2x1 x2 x3  x4 5 (1) x  x 2x  x  7 1 2 3 4 (2) 5x1  x2 3x3  x4  20 (3)  x1, x2 0, x3 0 x4 tùy ý. Bài toán đối ngẫu của bài toán này là: g(y) 5y1 7y2 20y3 min (do f (x) max ) 56
2y1  y2 5y3  2 (do x1 0) y  y  y 3 (do x2  0)  1 2 3 y 2y 3y 1 (do x3  0)  1 2 3  y1  y2  y3 1 (do x4 tùy ý 0) y1  0 (do ràng buộc (1) ), y2 tùy ý (do ràng buộc (2) = ), y3  0 (do ràng buộc (3) ), Ví dụ 3: Tìm bài toán đối ngẫu của bài toán f (x)  2x1  x2 x3 min x1  x2 2x3 1 x  x 3x  2 1 2 3 x1  x2 2x3 3  x1 0, x2 0, x3 tùy ý. Bài toán đối ngẫu là: g(y)  y1 2y2 3y3 max y1  y2  y3  2 y  y  y 1  1 2 3 2y1 3y2 2y3 1  y2 0, y3 0 ? Lập bài toán đối ngẫu của bài toán sau: f (x) 2x1 x2 8x3 max 7x1 4x2 2x3  28 3x x 3x 10  1 2 3 2x1 3x2 x3 15  x1 0, x2 0 2. Quan hệ giữa bài toán gốc và bài toán đối ngẫu 2.1. Các định lý đối ngẫu Định lý 1: Với cặp bài toán P và D, chỉ xảy ra một trong ba trƣờng hợp sau: 1. Cả hai đều không có phƣơng án. 2. Cả hai đều có phƣơng án, lúc đó cả hai cùng có phƣơng án tối ƣu và giá trị hàm mục tiêu đối với phƣơng án tối ƣu bằng nhau. 3. Một trong hai bài toán không có phƣơng án, còn bài toán kia có phƣơng án. Khi đó bài toán có phƣơng án sẽ không có phƣơng án tối ƣu và hàm mục tiêu của nó không bị chặn. 57
Hệ quả 1: Nếu một trong hai bài toán có phƣơng án tối ƣu thì bài toán kia cũng có phƣơng án tối ƣu. Hệ quả 2: Điều kiện cần và đủ để hai phƣơng án x* của (P) và y* của (D) tối ƣu là: f (x*)  g(y*) Định lý 2: (Độ lệch bù yếu). Điều kiện cần và đủ để phƣơng án x* của (P) và y* của (D) tối ƣu là:   m   xj aij yi cj  0 (j 1,n) (3.1.7)   i1   n yi aijxj bi  0 (i 1,m) (3.1.8)   j1   Chú ý: Nếu trong các tích trên nếu thừa số này khác 0 thì thừa số kia bằng 0. 2.2. Tìm P.A.T.Ƣ của bài toán đối ngẫu qua P.A.T.Ƣ của bài toán gốc. Giả sử bài toán gốc có phƣơng án tối ƣu x (x1, x2,...xn) và giải đƣợc bài toán đối ngẫu. Theo định lý 2, ta có a y c . m  Nếu x*j  0 thì * ij i j i1 aijx*j  bi n (,)  Nếu thay x* vào ràng buộc của bài toán gốc mà xẩy ra j1 (đẳng thức thật sự) thì yi*  0. Từ đây ta đƣợc hệ phƣơng trình, giải hệ này ta tìm đƣợc nghiệm tối ƣu của bài toán đối ngẫu.  Nhận xét: Tìm P.A.T.Ƣ của bài toán gốc qua P.A.T.Ƣ của bài toán đối ngẫu ta tiến hành tƣơng tự. Ví dụ 4: Bài toán gốc f (x) 2x1 x2 x3 4x4 max 5x1  x2  x3 6x4 50 3x  x 2x 16  1 3 4 4x1 3x3  x4  23  xj  0, j 1,4 Có phƣơng án tối ƣu là x (0,14,6,5), f (x)  40. Viết bài toán đối ngẫu và tìm phƣơng án tối ƣu của bài toán đối ngẫu. Giải 58
Bài toán đối ngẫu: g(y) 50y1 16y2 23y3 min 5y1 3y2 4y3  2 (1) y 1 1 (2) y  y 3y 1 1 2 3 (3)  6y1 2y2  y3  4 (4) y1 tuỳ ý, y2 0, y3 0 Tìm phƣơng án tối ƣu của bài toán đối ngẫu: x2 140y1 1 (theo (2)) x3 60y1  y2 3y3 1 (theo (3)) x4 506y1 2y2  y3 4 (theo (4)) 6 Giải hệ trên ta tìm đƣợc: y1 1, y2  , y3  2 5 5 Vậy phƣơng án tối ƣu là y 1,  ,  62  5 5 với g(y*) 50.116. 23.   40  f (x) 6 2  5  5 Ví dụ 5: Bài toán gốc f (x)  2x1 5x2 4x3  x4 5x5 min x1 6x2 2x4 9x5 32  2x  x  1 x  3 x 30  2 3 2 4 2 5  3x2  x5 36  xj  0, j 1,5 Có phƣơng án tối ƣu là x (32,0,30,0,0), f (x) 184. Viết bài toán đối ngẫu và tìm phƣơng án tối ƣu của bài toán đối ngẫu. Giải Bài toán đối ngẫu của nó là: g(y) 32y1 30y2 36y3 max 59
  y1  2  6y1 2y2 3y3 5 y  4 2  2y1  1 y2 1  2   9y1  3 y2  y3 5  2 y1, y2 tuỳ ý, y3  0 Tìm phƣơng án tối ƣu của bài toán đối ngẫu: Thứ nhất: x1 320y1 2 x3 300y2 4 Thứ hai: Thay x (32,0,30,0,0) vào ràng buộc thứ 3 ta có 3x2  x5 36 360. Nên y3  0 Vậy phƣơng án tối ƣu là y 2,4,0 với g(y*) 32.230.436.0 184  f (x) ? Tìm phƣơng án tối ƣu của bài toán đối ngẫu, biết rằng bài toán gốc có phƣơng án tối ƣu là x (1/5,0,9/10), f (x) 12. f (x) 15x1 8x2 10x3 max 3x1 2x2 4x3 3 2x  x 2x  4  1 2 3 4x1 5x2 2x3 1  xj  0, j 1,3 Ví dụ 6: Bài toán gốc f (x) 52x1 60x2 36x3 min x1 32 2x 4x 3x  6  4x 2x  4 1 2 3  1 2 x2 2   x3 3 xj tùy ý ( j 1,3) a) Viết bài toán đối ngẫu của bài toán trên. 60
b) Tìm phƣơng án tối ƣu của bài toán gốc biết P.A.T.Ƣ của bài toán đối ngẫu là y 0, 34, 22,0,2 và g(y*)  310 .  3 3  3 Giải Bài toán đối ngẫu của nó là: g(y) 32y1 6y2 4y3 2y4 3y5 max y1 2y2 4y3 52 4y 2y  y  60  2 3 4 3y2  y5 36  yi  0 i 1,5 Tìm phƣơng án tối ƣu của bài toán gốc Thứ nhất: y2  34 02x1 4x2 3x3 6 3 y3  22 04x1 2x2  4 3 y5 20x3 3 Thứ hai: Mọi ràng buộc trong bài toán đối ngẫu đều là phƣơng trình nên không cho ta điều gì về xj x 11 1 2x1 4x2 3x3 6  6 Giải hệ phƣơng trình 4x1 2x2  4 x2 5 x3 3  3  x3 3  Vậy phƣơng án tối ƣu của bài toán gốc là x  ,  ,3 11 5 6 3  với f (x*) 52. 60. 36.3 11 5 310  g(y) 6  3 3 3. Ý nghĩa bài toán đối ngẫu Một bài toán quy hoạch tuyến tính gốc đƣợc lập nên từ những vấn đề của sản xuất và kinh doanh, khi đó mọi tham số (aij ,b,c i j ), ẩn số, hàm mục tiêu, các ràng buộc đều chứa đựng những nội dung rõ rệt về kinh tế. Khi chuyển sang bài toán đối ngẫu đôi lúc ta sẽ khó có thể giải thích ý nghĩa kinh tế của các yếu tố trong bài toán đối ngẫu. Tuy nhiên không phải vì vậy mà bài toán đối ngẫu không có tầm quan trọng to lớn. 61
Theo các khái niệm trên ta thấy: giải đƣợc một trong hai bài toán coi nhƣ đã giải đƣợc bài toán kia. Vì vậy nếu gặp bài toán khó giải thì rất có thể bài toán đối ngẫu sẽ dễ giải hơn. Ví dụ 7: Bài toán sau. f(x)  cjxj min aijxj bi (i 1,m) xj 0 ( j 1,n) Giả thiết cj 0 ( j 1,n) Nếu giải trực tiếp, ta cần đƣa vào m ẩn phụ với hệ số -1, rồi lại thêm m ẩn giả với hệ số 1 mới đƣa về dạng chuẩn để giải bằng thuật toán đơn hình. Còn nếu đƣa về bài toán đối ngẫu: g( y)  bi yi max aij yi cj ( j 1,n) yi 0 (i 1,m) thì chỉ cần đƣa m ẩn phụ vời hệ số 1 là có ngay bài toán dạng chuẩn để giải. Ngoài ra ngƣời ta còn chứng minh đƣợc: khi đã có phƣơng án tối ƣu của bài toán đối ngẫu, tức là ở bảng j 0 j . Lúc đó x*( m1,m2,...,mn ) chính là phƣơng án tối ƣu của bài toán gốc. (Trong đó m j là ƣớc lƣợng của ẩn phụ ym j ). Bẳng lý thuyết của bài toán đối ngẫu ngƣời ta đã đƣa ra các thuật toán giải một số bài toán quan trọng trong kinh tế nhƣ “phƣơng pháp thế vị” giải bài toán vận tải và phƣơng pháp “ Điều chỉnh nhân tữ” giải bài toán sản xuất đồng bộ. 62
BÀI TẬP CHƢƠNG 3 1. Lập bài toán đối ngẫu của các bài toán sau:  f (x)  2x1  x2  x3 min  f (x) x1  x2  x3 max x  x 2x 1 x 3x  x  4   b)  1 2 3 a) x1  x2 3x3  2 1 2 3 2x  x 2x 1 x1  x2 2x3 3  1 2 3   xj 0, j 1,3  x1  0, x2  0 2. Lập bài toán đối ngẫu của các bài toán sau:  f (x)  2x1 3x2 2x3 4x5 min x  x 3x  7   2 4 5 a) 4x1 2x3  x5 3 x1 3x3  x4  x5 10   x1  0, x2, x3  0, x4, x5 R  f (x)  25x1 20x2 30x3 max 3x  x  x 12  1 2 3 x1  x2  x3 8 b)  x 2x 2x 12 1 2 3 2x1 3x2  x3 9  xj  0, j 1,3  3. Cho bài toán gốc:  f (x)  27x1 50x2 18x3 max x 2x  x  2  2x  x  x  4 1 2 3  1 2 3 x1 2x2  x3 2   x1, x2 R, x3  0 a) Lập bài toán đối ngẫu b) Giải bài toán đối ngẫu và suy ra kết quả của bài toán gốc. 4. Tìm phƣơng án tối ƣu của bài toán đối ngẫu. Biết bài toán gốc có phƣơng án tối ƣu là x (0,7/2,1) và có dạng: f (x) 12x1 8x2  x3 min  x1 2x2  x3 8  2x1 2x2 3x3 10  2x1 3x2  3 x3 12  2 63
xj  0, j 1,3 5. Cho bài toán gốc  f (x) 2x1  x2  x4 min  x1  x2 x3 15 x  x  x  x  27 1 2 3 4 2x1 x2 x3 18   xj 0, j 1,4 Có phƣơng án tối ƣu là X (15,0,12,0) , f (X) 30 Viết bài toán đối ngẫu và tìm phƣơng án tối ƣu của bài toán đối ngẫu. 6. Cho bài toán (P)  f (x) 3x1  x2 2x3 3x4 2x5 4x6 min  2x1  x3  x4 2x6 5 3x  x 2x  x 11  1 2 4 6 x1 2x4  x5  x6 5   xj 0, j 1,6 Kiểm tra tính tối ƣu của phƣơng án x(5/2,7/2,0,0,5/2,0) của bài toán (P). 7. Cho bài toán gốc  f (x)  x1 2x2 3x3 3x4 max  2x1  x2  x3 2x4  20 x 2x 3x 4x 18 1 2 3 4 2x1  x2 2x3  x4 16   xj 0, j 1,4 a) Giải bài toán trên bằng phƣơng pháp đơn hình. b) Viết bài toán đối ngẫu và tìm phƣơng án tối ƣu của bài toán đối ngẫu. 64
CHƢƠNG 4: BÀI TOÁN VẬN TẢI - BÀI TOÁN THẾ VỊ  Giới thiệu Bài toán vận tải là bài toán quan trọng nhất trong các bài toán quy hoạch tuyến tính. Thuật ngữ bài toán vận tải thƣờng đƣợc hiểu là bài toán vận chuyển sao cho cƣớc phí nhỏ nhất. Trong chƣơng này, sinh viên sẽ làm quen các nội dung sau: bài toán vận tải cân bằng thu phát và các dạng đặt biệt khác (nhƣ không cân bằng thu phát, bài toán vận tải ô cấm, bài toán vận tải có hàm mục tiêu max) để từ đó đó ra phƣơng pháp giải phù hợp, cách đặt bài toán dƣới dạng bảng, một số phƣơng pháp giải bài toán vận tải.  Mục tiêu - Về kiến thức: + Nhận biết dạng bài toán vận tải cân bằng thu phát và các dạng đặt biệt khác (nhƣ không cân bằng thu phát, bài toán vận tải ô cấm, bài toán vận tải có hàm mục tiêu max) để từ đó đó ra phƣơng pháp giải phù hợp. + Hiểu đƣợc cách đặt bài toán dạng bảng. + Hiểu đƣợc các phƣơng pháp giải bài toán vận tải. - Về kỹ năng: + Biết cách đặt bài toán dƣới dạng bảng. + Thành thạo phƣơng pháp chi phí bé nhất đề tìm phƣơng án cơ bản ban đầu cho bài toán vận tải. + Phân tích vững thuật toán “Quy 0 cƣớc phí các ô chọn” và phƣơng pháp thế vị để tìm phƣơng án tối ƣu cho bài toán vận tải. - Về năng lực tự chủ và trách nhiệm: Có thái độ nghiêm túc, tự giác học tập và chịu trách nhiệm với kết quả thực hiện. 65
1. Bài toán vận tải cân bằng thu phát (bài toán cổ điển) 1.1. Thiết lập bài toán Giả sử có m địa điểm A1, A2,..., Am cung cấp một loại hàng hóa (xi măng, sắt, thép,…) với khối lƣợng lần lƣợt là a1, a2,, am. Cùng lúc đó có n địa điểm tiêu thụ hàng hóa đó là B1, B2,..., Bn với khối lƣợng yêu cầu lần lƣợt là b1,b2,,bn (đơn vị khối lƣợng tính bằng tấn). Gọi Ai là trạm phát hàng thứ i ( i 1,m) Bj là trạm thu hàng thứ j ( i 1, n) Giả sử chi phí chuyên chở một tấn hàng từ Ai đến Bj là cij đồng. Ma trận C cij mxn gọi là ma trận cƣớc phí. Hãy lập kế hoạch vận chuyển hàng hóa sao cho tổng chi phí vận tải thấp nhất và thỏa mãn yêu cầu thu-phát. (Để đơn giản, ta giả thiết tổng lượng hàng cần phát đi ở các trạm phát m   i bj . Điều kiện này gọi là n bằng tổng lượng hàng thu về ở các trạm thu  a   i1 j1  cân bằng thu phát)  Mô hình bài toán vận tải Đặt xij là số tấn hàng chuyển từ trạm phát Ai đến trạm thu Bj c x min m n Tổng chi phí vận tải: f (x)  ij ij (4.1.1) i1 j1 x a , i 1,m n (1) Trạm phát, phát hết hàng: ij i (4.1.2) j1 x b , ( j 1,n) m (2) Trạm thu, thu đủ hàng: ij j (4.1.3) i1 (3) Yêu cầu trạm phát và trạm thu đƣợc thỏa ai bj (cân bằng thu phát) m n (4.1.4) i1 j1 (4) Hiển nhiên xij  0 (i 1, m; j 1, n) . (4.1.5) Từ các phân tích trên, ta có mô hình bài toán vận tải (BTVT) nhƣ sau: f (x) cijxij min m n (4.1.6) i1 j1 x a (i 1,m) n ij i (4.1.7) j1 66
x b m ij j ( j 1, n) (4.1.8) i1 xij 0; cij 0; ai 0; bj 0; ai bj m n (4.1.9) i1 j1 Một ma trận X  xij   mxn thỏa (4.1.7), (4.1.8) và (4.1.9) gọi là một phƣơng án, thỏa thêm (4.1.6) gọi là phƣơng án tối ƣu. 1.2. Đặt bài toán dƣới dạng bảng Bài toán vận tải là bài toán QHTT nên có thể dùng thuật toán đơn hình để giải. Nhƣng do tính chất đặc biệt của bài toán vận tải, nên ta có thể có một phƣơng pháp giải đơn giản và hiệu quả hơn. Trƣớc hết ta trình bày bài toán dƣới dạng bảng: Thu Bj b1 b2 … bn Phát Ai c11 c12 c1n A1 x11 x12 x1n c21 c22 c2n A2 x21 x22 x2n … cm1 cm2 cmn am xm1 xm2 xmn Mô tả bảng vận tải - Mỗi hàng đặc trƣng cho một trạm phát và mỗi cột đặc trƣng cho một trạm thu. - Mỗi ô nằm trên hàng i và cột j đặc trƣng cho tuyến đƣờng từ Ai đến Bj gọi là ô (i, j) + Chi phí vận chuyển: cij đƣợc ghi ở góc bên trái của ô (i, j) . + Lƣợng hàng hóa cần vận chuyển: xij đƣợc ghi ở góc bên phải của ô (i, j). - Một ô đƣợc gọi là ô treo nếu nó là ô duy nhất trên dòng hay cột. - Những ô ứng với xij  0 trong Bảng vận tải đƣợc gọi là ô chọn. Những ô còn lại đƣợc gọi là ô loại. Ô chọn đặc trƣng cho tuyến đƣờng có vận tải. 67
- Một dãy các ô chọn, trong đó 3 ô liên tiếp không nằm trong cùng 1 dòng hay một cột đƣợc gọi là một dây chuyền. (i1, j1)(i1, j2)(i2, j2)...(ik1, jk )(ik , jk ) (Số ô trong một dây chuyền là một số chẵn, không nhỏ hơn 4) - Một dây chuyền khép kín đƣợc gọi là một vòng (lƣu ý: tổng số ô trên vòng luôn là số chẵn và ít nhất là 4 ô) (i1, j1)(i1, j2)(i2, j2)...(ik1, jk )(ik , jk )(ik , j1) Ví dụ 1 - Các ô chọn có dấu “x”, tạo thành dây chuyền; hình 2 tạo thành một vòng. - Hình 1, ô (3,1) là ô treo; hình 2, không có ô treo. x x X x x x x x x x x x (hình 1) (hình 2) Định nghĩa - Một phƣơng án mà các ô chọn không tạo thành vòng gọi là P.A cơ bản. - Một phƣơng án cơ bản có đủ mn1 ô chọn gọi là P.A cơ bản không suy biến, nếu ít hơn mn1 ô chọn gọi là P.A cơ bản suy biến. 1.3. Các tính chất 1.3.1. Tính chất 1 Bài toán vận tải cân bằng thu phát luôn có phương án tối ưu. j bj Thật vậy: Đặt ab xij  i j ; xij  0 và ai j xij j ai ai ai ai ab i j i i i  ai  i xij  ab i j i ai bj ai j i b i i Vậy bài toán có phƣơng án. Ngoài ra f (x)  c x 0 i j ij ij Bài toán vận tải có phƣơng án và hàm mục tiêu luôn bị chặn dƣới nên nó có phƣơng án tối ƣu. 68
1.3.2. Tính chất 2 Trong một phƣơng án cơ bản bất kỳ, số ô chọn không bao giờ vượt quá tổng số các trạm phát và các trạm thu trừ đi một. Ký hiệu:  số ô chọn thì mn1. 1.3.3. Tính chất 3 Với một phƣơng án cơ bản có đủ mn1 ô chọn thì một ô loại bất kỳ đƣợc đƣa vào P.A sẽ tạo nên một vòng duy nhất với một số ô chọn.  Chú ý: Trƣờng hợp P.A cơ bản suy biến, ta có thể bổ sung một số ô loại sao cho P.A cơ bản có mn1 ô chọn. Các ô loại đƣợc bổ sung này gọi là các “ô chọn 0”. Ví dụ 2: Trong bảng dƣới đây có tập F gồm mn14317 ô chọn không chứa vòng có đánh dấu “x”. Ô (4, 4) của bảng không thuộc F. Khi bổ sung ô (4, 4) vào F ta sẽ có vòng duy nhất: (1,3) (1,4) (4,4) (4,3) X x x x x X x (4,4) 2. Thuật toán thế vị giải bài toán vận tải cân bằng thu phát 2.1. Lập phƣơng án cơ bản ban đầu Áp dụng phương pháp chi phí bé nhất cho trƣờng hợp cân bằng thu phát a b m n  Bƣớc 1: Kiểm tra i j (cân bằng thu phát) (4.2.1) i1 j1  Bƣớc 2: Chọn ô đầu tiên có cƣớc phí vận chuyển bé nhất (i, j). ai   Bƣớc 3: Chọn xij nhƣ sau: xij  min(ai ,bj )  bj (4.2.2) a b i j - Nếu xij  ai thì trạm phát i đã phát hết hàng, xóa hàng i của bảng và số lượng thu còn lại tại trạm thu j chỉ còn là bj ai ; 69
- Nếu xij  bj thì trạm thu j đã nhận đủ hàng, xóa cột j của bảng và số lượng phát còn lại tại điểm phát i là ai bj . - Nếu xij  ai  bj thì trạm phát i và trạm thu j đều phát và nhận đủ hàng, xóa hàng i và cột j của bảng.  Bƣớc 4: Trong bảng còn lại với số hàng và số cột ít hơn, ta lại tiếp tục phân phối nhƣ trên cho đến khi hết hàng.  Bƣớc 5: Kiểm tra lại các ô chọn - Nếu mn1 “số ô chọn” là P.A C.B của bài toán. - Nếu mn1 “số ô chọn” thì ta bổ sung thêm một số “ô chọn 0” cho đủ mn1 ô không tạo thành vòng. Ví dụ 3: Tìm phƣơng án cơ bản ban đầu của bài toán vận tải với các số liệu sau đây: 5 4 1  (cij) 3 2 6  ; (ai ) 50 40 70; (bj ) 80 20 60. 7 9 11 a b 160 (cân bằng thu phát) m n Giải: Ta thấy: i j i1 j1 Ta đặt bài toán dƣới dạng bảng: bj 80 20 60 ai 5 4 1 50 3 2 6 40 7 9 11 70 Thứ tự phân phối nhƣ sau: Ô (1,3) đƣợc phân vào 50. Hàng 1 bị xóa, cột 3 còn cần 10. Ô (2,2) đƣợc phân vào 20. cột 2 bị xóa, hàng 2 còn 20. Ô (2,1) đƣợc phân vào 20. Hàng 2 bị xóa, cột 1 còn cần 60. Ô (3,1) đƣợc phân vào 60. cột 1 bị xóa, hàng 3 còn 10. Ô (3,3) đƣợc phân vào 10. Hết hàng. 70
bj 80 20 60 ai 5 4 1 50 50 3 2 6 40 20 20 7 9 11 70 60 10 Ta thấy có 5 ô chọn và mn1331 “số ô chọn” nên chúng tạo thành một phƣơng án cơ bản không suy biến. Phƣơng án cơ bản ban đầu là:  0 0 50   X 20 20 0    60 0 10  2.2. Thuật toán “Quy 0 cƣớc phí các ô chọn” Định lý: Nếu ta cộng vào hàng i và cột j của ma trận cƣớc phí C  cij   mxn một số tuỳ ý ri (i 1, m) và sj ( j 1, n) , ta sẽ có bài toán vận tải mới với ma trận cƣớc phí C' cij' mxn cij' cij ri sj  tƣơng đƣơng với bài toán ban đầu.  Thuật toán: gồm 3 bƣớc:  Bƣớc 1: Quy 0 cƣớc phí các ô chọn - Xác định đƣợc một phƣơng án cơ bản ban đầu. (xem mục 4.3.1) - Với mn1 ô chọn, ta cộng vào hàng i và cột j của ma trận cƣớc   phí C  cij mxn một số tuỳ ý ri (i 1, m) và sj ( j 1, n) sao cho ma trận cƣớc phí mới C’ thỏa cij'  0 (tức ri sj cij  0 ).  Bƣớc 2: Kiểm tra tính tối ƣu 1. Sau khi quy 0 cƣớc phí các ô chọn, nếu các ô loại đều có cƣớc phí 0 thì phương án đang xét là tối ưu. 2. Sau khi quy 0 cƣớc phí các ô chọn, nếu có ít nhất một ô loại có cƣớc phí < 0 thì phƣơng án đang xét không phải tối ưu. Ta chuyển sang bƣớc 3.  Bƣớc 3: Xây dựng phƣơng án mới tốt hơn 1. Chọn ô đưa vào: Ô đƣa vào là ô (i*,j*) có cước phí âm nhỏ nhất. 71
2. Tìm vòng điều chỉnh: Bổ sung (i*,j*) vào mn1 ô chọn ban đầu sẽ xuất hiện vòng duy nhất, gọi là vòng điều chỉnh V. 3. Phân ô chẵn lẻ của vòng điều chỉnh V: Ta đánh số thứ tự các ô của vòng V bắt đầu từ ô (i*,j*). Khi đó, V phân thành hai lớp: VC: các ô có số thứ tự chẵn VL: các ô có số thứ tự lẻ 4. Chọn ô đưa ra và lƣợng điều chỉnh: - Tính giá trị nhỏ nhất trong 2 ô chẵn : min(c21,c33) - Ô nào có phân ít hàng nhất làm ô đưa ra, còn lƣợng hàng ở ô này là lƣợng điều chỉnh. 5. Lập phương án mới: Phƣơng án mới đƣợc tính nhƣ sau: - Ô có thứ tự chẵn đƣợc bớt đi lƣợng điều chỉnh - Ô có thứ tự lẻ đƣợc cộng thêm lƣợng điều chỉnh - Ô ngoài vòng điều chỉnh không thay đổi. Ví dụ 4: Giải bài toán vận tải đƣợc cho trong ví dụ trên.  Bƣớc 1: Quy 0 cƣớc phí các ô chọn - Phƣơng án cơ bản ban đầu của bài toán (xem ví dụ 3) - Ta thấy: bj 80 20 60 ai 5 4 1 50 r1 6 50 3 2 6 40 r2 0 20 20 7 9 11 70 r3 4 60 10 s1 3 s2 2 s3 7 Các giá trị ri và sj cộng vào phải thoả hệ phƣơng trình: 1r1 s3  0 3r s  0  2 1 2r2 s2  0 (I) 7r3 s1  0  11r3 s3  0 72
Cho r2 0, giải hệ (I) ta đƣợc kết quả trong bảng trên. Áp dụng công thức cij' cij ri sj ta có ma trận cƣớc phí mới sẽ là: 8 8 0 50 0 0 -1 20 20 0 3 0 60 10  Bƣớc 2: Kiểm tra tính tối ƣu Phƣơng án chƣa tối ƣu vì còn ô loại (2, 3) có cƣớc phí 10. Ta chuyển sang bƣớc 3.  Bƣớc 3: Xây dựng phƣơng án mới tốt hơn 1. Chọn ô đưa vào: Ô loại (2, 3) là ô đƣợc đƣa vào (do (2, 3) có cước phí 10 nhỏ nhất) 2. Tìm vòng điều chỉnh: Vòng điều chỉnh là: V: (2,3)(3,3)(3,1)(2,1)(2,3) 3. Phân ô chẵn lẻ của vòng điều chỉnh V. VC (2,1)(3,3) VL (2,3)(3,1) 4. Chọn ô đưa ra và lƣợng điều chỉnh: Ta có : min(c21,c33)  min(20,10) 10c33  Ô đƣa ra là (3,3), lƣợng điều chỉnh là 10. 5. Lập phƣơng án mới. Những ô trong vòng điều chỉnh có sự thay đổi nhƣ sau: Ô (2,3) đƣợc thêm 10 trở thành 10 Ô (3,3) đƣợc bớt 10 trở thành 0 Ô (3,1) đƣợc thêm 10 trở thành 70 Ô (2,1) đƣợc bớt 10 trở thành 10 Khi đó, phƣơng án mới là: 8 8 0 50 0 0 -1 10 20 10 73