Nội dung

Bài giảng Quy hoạch toán học Trang 41 ________________________________________________________________________ 4.4.3. Dạng cực đại Xét bài toán vận tải dạng max: f(x) = m n i =1 j =1 ∑ ∑ qijxij → max ⎧n ⎪∑ xij = ai (i = 1..m) ⎪ j =1 ⎪⎪ m ⎨∑ xij = b j ( j = 1..n) ⎪ i =1 ⎪ xij ≥ 0 (i = 1..m, j = 1..n) ⎪ ⎪⎩ Đưa về dạng chính tắc tương đương bằng cách đặt cij = - qij (i=1..m, j=1..n) g(x)= m n i =1 j =1 ∑ ∑ qijxij → min ⎧n ⎪∑ xij = ai (i = 1..m) ⎪ j =1 ⎪⎪ m ⎨∑ xij = b j ( j = 1..n) ⎪ i =1 ⎪ xij ≥ 0 (i = 1..m, j = 1..n) ⎪ ⎪⎩ Có fmax= -gmin. Ví dụ 4.5 Phân phối lao động. Một công ty vận tải biển cần tuyển 110 người để bố trí 10 người làm máy trưởng (MT), 25 thợ 1, 30 thợ 2 và 45 thợ 3. Phòng tổ chức tìm được 90 người gồm 25 kỹ sư (KS), 20 trung cấp (TC) và 45 công nhân (CN). Khả năng cán bộ được đánh giá theo công việc qua bảng sau Công việc Trình độ MT Thợ 1 4 KS 5 5 TC 3 1 CN 0 Thợ 2 0 4 5 Thợ 3 0 0 4 Cần bố trí sao cho sử dụng tối đa năng lực của mọi người. Đây là bài toán vận tải dạng max. Khồng cân bằng thu phát. Đưa vào trạm phát giả: a4= 110 - 90 = 20 ________________________________________________________________________ GV: Phan Thanh Tao Bài giảng Quy hoạch toán học Trang 42 ________________________________________________________________________ ai\bj 10 25 10 5 10 -5 -4 0 0 20 + -3 -5 -4 0 30 15 0 -1 -5 -4 20 0 0 0 0 20 45 20 25 30 45 ui -5 -4 -1 0 ai\bj 10 25 30 45 25 10 5 10 -5 -4 0 0 10 10 -3 -5 -4 0 20 25 0 -1 -5 -4 20 0 0 0 0 20 45 20 ui -5 -4 -3 vj 0 1 4 0 vj 0 1 2 -2 -2 Đây là phương án tối ưu Vậy có phương án phân phối lao động tối ưu như sau: 10 kỹ sư làm Máy trưởng 15 kỹ sư làm Thợ 1 10 Trung cấp làm Thợ 1 10 Trung cấp làm Thợ 2 20 Công nhân làm Thợ 2 25 Công nhân làm Thợ 3 Ví dụ 4.6 Bài toán phân phối đất trồng Có 3 loại ruộng A, B, C với diện tích tương ứng là 20, 25, 30 ha để trồng 3 loại lúa I, II, III với diện tích theo kế hoạch là 15, 30, 30 ha tương ứng. Hãy tìm phương án phân phối đất trồng sao cho tổng sản lượng cao nhất đồng thời đảm bảo kế hoạch. Biết sản lượng lúa trên từng loại đất cho trong bảng sau (tấn/ha) ________________________________________________________________________ GV: Phan Thanh Tao Bài giảng Quy hoạch toán học Trang 43 ________________________________________________________________________ lúa đất A(25) B(25) C(30) I 15 12 8 8 II 30 8 10 10 III 30 8 9 10 Đây là bài toán vận tải dạng max ai\bj 15 25 15 5 -12 -8 -8 25 -8 -10 -9 5 25 -8 -10 -10 20 45 ui -12 30 -8 30 vj 0 2 2 -8 fmax=770 Ví dụ 4.7 Bài toán bổ nhiệm Cần phân n việc cho n người. Người i làm việc j thì năng suất là cij (i,j=1..n). Hãy phân công việc cho n người để tổng năng suất cao nhất. Đặt xij=1 nếu người i làm việc j; ngược lại đặt xij=0. Bài toán này còn gọi là bài toán quy hoạch nguyên 0-1. Vì suy biến nên có thuật toán khác tiện hơn. Bảng năng suất được cho như sau Việc Ng A B C D 1 2 3 4 5 3 4 8 2 7 1 6 6 5 5 7 4 6 2 3 ________________________________________________________________________ GV: Phan Thanh Tao Bài giảng Quy hoạch toán học Trang 44 ________________________________________________________________________ ai\bj 1 1 1 -5 -2 -6 1 1 1 -3 -7 -4 -1 1 vj 0 -4 1 0 -5 + -5 1 ui 1 1 -6 1 0 2 -2 -2 1 0 -8 -6 -7 -3 -7 -5 -6 -4 1 1 1 1 f(x)=23 ai\bj 1 1 -5 -2 1 -6 -7 0 -5 1 -6 1 0 0 2 -2 -2 -7 -3 0 -5 -7 -4 1 1 1 -4 ui -4 1 -3 1 vj -1 1 + -8 -6 -5 -8 1 0 f(x)=24 ai\bj 1 1 -5 -2 -3 -7 1 -6 -4 -5 -6 1 0 1 1 -4 1 ui vj -1 1 0 0 2 -5 -2 -2 1 0 -8 -6 -7 -3 -7 -5 -7 -4 fmax=24 ________________________________________________________________________ GV: Phan Thanh Tao Bài giảng Quy hoạch toán học Trang 45 ________________________________________________________________________ 4.4.4. Bài toán xe rỗng Bài toán xe rỗng ứng dụng thường xuyên trong thực tế, nên được xem là một dạng đặc biệt của bài toán vận tải Ví dụ 4.8 Công ty vận tải cần hoàn thành hợp đồng chở hàng sau: 1) Than: Kim Liên → Ngọc Hồi: 50 tấn 2) Xi măng: Ga Hà Nội → Chuông: 24 tấn 3) Xi măng: Ga Hà Nội → Ba thá: 10 tấn 4) Sắn: Mai Lĩnh → Hà Đông: 8 tấn 5) Muối: Thường Tín → Hà Đông: 42 tấn Thường Tín → Trúc Sơn : 8 tấn 6) Muối: 7) Ngô: Kim bài → Hà Đông: 34 tấn Hãy lập kế hoạch vận chuyển sao cho tổng số tấn xe rỗng ít nhất. Với cự ly các địa điểm như sau: Kim Liên Ga Hà Nội Mai Lĩnh Thường Tín Kim Bài Ngọc hồi Chuông Ba thá Hà Đông Trúc Sơn 11 12 18 6 26 27 28 18 34 2 10 11 7 17 15 21 22 4 28 20 40 41 31 35 15 Cước phí là cự ly Nơi có hàng là nơi thu xe rỗng Nơi cần hàng là nơi phat xe rỗng Trạm thu xe rỗng Kim liên: 50 Ga Hà Nội: 34 Mai Lĩnh: 8 Thường Tín: 50 Kim Bài: 34 Trạm phát xe rỗng Ngọc Hồi: 50 Chuông: 24 Ba Thá: 10 Hà Đông: 84 Trúc Sơn: 8 Đây là bài toán vận tải dạng cực tiểu cân bằng thu phát. ________________________________________________________________________ GV: Phan Thanh Tao Bài giảng Quy hoạch toán học Trang 46 ________________________________________________________________________ ai\bj 50 34 8 50 50 50 11 24 10 84 8 ui 34 12 18 6 25 24 27 28 18 34 2 10 40 41 31 35 15 + 50 34 0 10 11 7 17 15 8 0 0 21 22 4 28 20 6 7 3 6 13 50 34 8 50 34 vj 0 11 -2 -4 -1 F(x)= 1404 ai\bj 50 50 11 24 10 84 8 ui 25 24 27 28 18 34 2 10 40 41 31 35 15 50 34 0 10 11 7 17 15 8 0 0 21 22 4 28 20 8 12 9 18 3 6 6 vj 0 11 -2 -2 -1 13 Fmin= 1404 Bảng phân phối xe rỗng với tổng tấnxkm xe rỗng ít nhất là: Tuyến đường Số tấn xe rỗng Ngọc hồi →Thường tín 50 Chuông → Kim bài 24 Ba thá → Kim bài 10 Hà đông → Kim liên 50 Hà đông → Ga Hà nội 34 Trúc sơn → Mai lĩnh 8 ________________________________________________________________________ GV: Phan Thanh Tao Bài giảng Quy hoạch toán học Trang 47 ________________________________________________________________________ Kết hợp các trạm có nguồn xe (Ga Hà nội, Bến xe Kim liên), có thể phân phối lộ trình tối ưu như sau: 1. Ga Hà nội (24 xi măng) → Chuông → Kim bài (24 ngô) → Hà đông → Ga Hà nội. 2. Ga Hà nội (10 xi măng) → Ba thá → Kim bài (10 ngô) → Hà đông → Ga Hà nội. 3. Kim liên (42 than) → Ngọc hồi → Thường tín (42 muối) → Hà đông → Kim liên. 4. Kim liên (8 than) → Ngọc hồi → Thường tín (8 muối) → Trúc sơn → Mai lĩnh (8 sắn) → Hà đông → Kim liên. 4.4.5. Bài toán ô cấm Do yêu cầu kỹ thuật, phải hạn chế không được vận chuyển trên một số tuyến đường nào đó. Khi đó ta xem cước phí của ô (i,j) bị cấm là cij= M khá lớn( M→∞). Tiếp tục thuật toán thế vị bình thường. Ví dụ 4.9 ai\bj 72 45 22 9 vj 7 0 M 1 22 5 60 3 60 1 0 2 5 5 4 1 M 2 12 + 3 3 5 1 ui 2 3 5 ai\bj 72 45 9 vj 3 7 0 2 M 1 M 3 23 16 23 22 4 6 22 5 60 60 1 5 5 M 3 4 23 23 16 M 2 5 12 0 4 3 3 6 ui 2 3 -1 1 1 -1 5 ________________________________________________________________________ GV: Phan Thanh Tao Bài giảng Quy hoạch toán học Trang 48 ________________________________________________________________________ 4.5. Cài đặt thuật toán thế vị 4.5.1. Khai báo dữ liệu a) Ma trận cước phí C=(cij)mxn , mảng hàng phát A=(ai)m, mảng hàng thu B=(bj)n , phương án X=( xij)mxn int a[m], b[n], c[m][n], x[m][n]; b) Hệ thống thế vị {ui, vj}. int u[m], v[n]; c) Mảng S các ô chọn và vòng điều chỉnh V được khai báo là các ma trận 0/1 để đánh dấu như sau: int S[m][n], V[m][n]; với ý nghĩa: S[i][j]=1 ⇔ ô (i,j) ∈ S và V[i][j]=1 ⇔ ô (i,j) ∈ V 4.5.2. Xây dựng phương án cơ bản ban đầu Tìm phương án cơ bản ban đầu bằng nguyên tắc phân phối tối đa và phương pháp góc tây bắc. Các mảng đánh dấu các trạm đã thỏa mãn chưa (đã loại khỏi bảng phân phối). int aa[m], bb[n];. với ý nghĩa: Trạm Ai đã thỏa mãn ⇔ aa[i]=0 và Trạm Bj đã thỏa mãn ⇔ bb[j]=0 void phanphoi() { int i, j, dem=0; for (đem=0; demdrk){ r=i; k=j; drk= v[j]-[u[i]-c[i][j]; } } return drk>0; ________________________________________________________________________ GV: Phan Thanh Tao Bài giảng Quy hoạch toán học Trang 50 ________________________________________________________________________ 4.5.5. Tìm vòng điều chỉnh Ô treo trong tập V là ô ở một mònh trên dòng hoặc cột. Thuật toán tìm vòng điều chỉnh V duy nhất trên tập S bằng cách xóa tất cả các ô treo cho đến khi không còn thì tập ô còn lại là vòng V cần tìm. int TimVongDC( ) { int i,j,done=0,dem; for (i=0; i

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.