Bài giảng Quy hoạch tuyến tính - Phan Bá Trình
Nội dung “ Bài giảng Quy hoạch tuyến tính” gồm 5 chương:
Chương 1. Bài toán quy hoạch tuyến tính
Chương 2. Tính chất của tập phương án và tập phương án tối ưu của bài toán quy
hoạch tuyến tính
Chương 3. Phương pháp đơn hình và các thuật toán của nó
Chương 4. Bài toán đối ngẫu, thuật toán đơn hình đối ngẫu
Chương 5. Bài toán vận tải, thuật toán thế vị
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Quy hoạch tuyến tính - Phan Bá Trình", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
Tóm tắt nội dung tài liệu: Bài giảng Quy hoạch tuyến tính - Phan Bá Trình
![Bài giảng Quy hoạch tuyến tính - Phan Bá Trình Bài giảng Quy hoạch tuyến tính - Phan Bá Trình](https://s1.tailieuvn.net/xb70nb5jd4llaq8g/thumb/2021/12/02/bai-giang-quy-hoach-tuyen-tinh-phan-ba-trinh_ZNX40dKJpI.jpg)
1 UBND TỈNH QUẢNG NGÃI TRƯỜNG ĐẠI HỌC PHẠM VĂN ĐỒNG BÀI GIẢNG QUY HOẠCH TUYẾN TÍNH Biên soạn : ThS. PHAN BÁ TRÌNH Quaûng Ngaõi, Thaùng 5 - 2014 2LỜI NÓI ĐẦU Quy hoạch tuyến tính là lĩnh vực toán học nghiên cứu các bài toán tối ưu trên hữu hạn biến mà hàm mục tiêu và các ràng buộc đều là hàm số và các phương trình hoặc bất phương trình tuyến tính. Khi Dantzig công bố phương pháp đơn hình để giải các bài toán lập kế hoạch cho không quân Mỹ năm 1947 là xuất phát từ yêu cầu về quản lý và cũng từ đó các dạng bài toán khác nhau đều tìm cách đưa về quy hoạch tuyến tính và dùng phương pháp đơn hình để giải. Người ta cũng dùng quy hoạch tuyến tính để phân tích các mô hình lý thuyết kinh tế cổ điển của Walras được đề xuất từ năm 1874 một cách hoàn chỉnh. Các nhà toán học như Kantorovich và Koopmans là những nhà toán học có nhiều công trình nghiên cứu và ứng dụng quy hoạch tuyến tính thành công nhất trong lĩnh vực kinh tế mà chúng ta thường gọi là toán kinh tế. Năm 1975, Kantorovich và Koopmans được giải thưởng Nobel về khoa học kinh tế. Quy hoạch tuyến tính là môn học bắt buộc đối với các trường thuộc khối ngành khoa học tự nhiên, kinh tế, sư phạm Bài giảng Quy hoạch tuyến tính dành cho sinh viên các lớp thuộc ngành sư phạm Toán, ngành kinh tế, Nội dung “ Bài giảng Quy hoạch tuyến tính” gồm 5 chương: Chương 1. Bài toán quy hoạch tuyến tính Chương 2. Tính chất của tập phương án và tập phương án tối ưu của bài toán quy hoạch tuyến tính Chương 3. Phương pháp đơn hình và các thuật toán của nó Chương 4. Bài toán đối ngẫu, thuật toán đơn hình đối ngẫu Chương 5. Bài toán vận tải, thuật toán thế vị Bài giảng đã trình bày những nội dung căn bản nhất của quy hoạch tuyến tính như cấu trúc đa dạng của bài toán và cách chuyển đổi sang cấu trúc chính tắc, chuẩn tắc của bài toán quy hoạch tuyến tính, cấu trúc bài toán đối ngẫu, các phương pháp giải 3bài toán quy hoạch tuyến tínhĐặc biệt, sau mỗi chương có phần bài tập rất phong phú để củng cố kiến thức và rèn luyện kỹ năng tính toán. Bài giảng đã giới thiệu các ví dụ minh hoạ, những bài toán ứng dụng trong nhiều lĩnh vực khác nhau sẽ giúp ích cho các bạn sinh viên các nhà quản lý, các nhà kinh tế Chúng tôi hy vọng rằng “Bài giảng Quy hoạch tuyến tính” là một tài liệu học tập bổ ích cho sinh viên và là nguồn tư liệu phong phú cho quý Thầy, Cô giáo tham khảo, nghiên cứu. Là lần viết đầu tiên, nên chắc chắn bài giảng còn nhiều thiếu sót. Chúng tôi hết sức chân thành cảm ơn sự góp ý, nhận xét của bạn đọc về nhiều phương diện để bài giảng ngày càng được tốt hơn. Mọi góp ý xin gửi về: Phan Bá Trình, Khoa Cơ bản - Trường Đại học Phạm Văn Đồng. Email: pbtrinh@pdu.edu.vn 4Chương 1. BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 1.1. Một vài bài toán thực tế 1.1.1. Xây dựng mô hình toán học cho một số vấn đề thực tế Các bước thực hiện để lập mô hình toán học cho vấn đề thực tế Bước 1. Tìm kiếm thông tin gốc Đây là quá trình thu thập các số liệu kinh tế - kỹ thuật. Bước này khá quan trọng vì tất cả các bước sau dựa vào các số liệu này để tính toán. Nó quyết định tính chính xác của kết quả thu được. Mỗi bài toán kinh tế cụ thể đòi hỏi các thông tin gốc khác nhau. Bước 2. Xử lý số liệu Bước này có thể chia thành hai giai đoạn i) Lập mô hình bài toán Từ những số liệu và các yêu cầu về kinh tế - kỹ thuật, ta chuyển thành mô hình toán học. Đòi hỏi ở bước này là phải thiết lập chính xác và đầy đủ các điều kiện của bài toán. ii) Lựa chọn thuật toán thích hợp và giải bài toán Đây là quá trình tính toán trên mô hình toán dựa vào các thành tựu và toán học đã có. Kết quả ở bước này chính là lời giải cơ bản để đưa ra giải pháp tối ưu về mặt kinh tế. Vì vậy đây là bước quan trọng. Bước 3. Thông tin kết quả Thực chất của bước này là sự diễn giải các thông tin về mặt toán học thành các thông tin về mặt kinh tế. Nghĩa là, dựa vào các kết quả tính toán đã có để những nhà làm chính sách đưa ra các quyết định kinh tế. 1.1.2. Một vài bài toán thực tế 1.1.2.1. Bài toán lập kế hoạch sản xuất Bài toán tổng quát: Trong một chu kì sản xuất một doanh nghiệp sử dụng m loại nhân tố sản xuất khác nhau để sản xuất ra n loại sản phẩm khác nhau E1, E2, , En. 5Tiềm năng về các nhân tố sản xuất này của doanh nghiệp là có hạn cho bởi vec tơ b = (b1, b2, , bm). Biết rằng để sản xuất ra một đơn vị sản phẩm Ej njj ,1: cần chi phí hết aij đơn vị nhân tố sản xuất thứ i mii ,1: lợi nhuận khi bán sản phẩm được cho bởi vectơ c = (c1, c2, ..., cn). Đặt: nmijaA . Vậy doanh nghiệp cần phải lập kế hoạch sản xuất bao nhiêu để không bị động về tiềm năng các nhân tố sản xuất và thu được lợi nhuận lớn nhất. Phân tích: Gọi x1, x2 ,, xn lần lượt là số sản phẩm E1, E2 ,, En (trong kế hoạch cần sản xuất) Theo đề bài ta có mô hình toán học như sau: Tìm x = (x1, x2, , xn) thỏa mãn: f(x) = c1x1 + c2x2 + + cnxn max (1) a11x1 + a12x2 + + a1nxn b1 a21x1 + a22x2 + + a2nxn b2 (2) . am1x1 + am2x2 + + amnxn bm xj 0 njj ,1: (3) hay ta viết gọn dưới dạng ma trận f(x) = cTx max (1/) Ax b (2/) x 0 (3/) Ví dụ 1: Một công ty phần mềm chuyên sản xuất 2 loại phần mềm A và B. Với đội ngũ gồm 6 thạc sỹ và 8 kỹ sư tin học. Biết rằng: Để sản xuất hoàn thành 1 phần mềm A cần 2 thạc sỹ và 1 kỹ sư, để sản xuất hoàn thành 1 phần mềm B cần 1 thạc sĩ và 3 kỹ sư. Qua tiếp thị trên thị trường được biết nhu cầu cực đại của cả 2 phần mềm. Giá bán ra cho một loại phần mềm A là 2000USD và cho một loại phần mềm B là: 3000USD. 6Hãy lập kế hoạch sản xuất cho mỗi tháng để thỏa mãn yêu cầu thị trường, không bị động về đội ngũ, doanh thu đem về cho công ty lớn nhất. Giải: Gọi x1, x2 lần lượt là số lượng phần mềm A và B cần sản xuất. Theo để bài ta có mô hình toán học: Tìm x = (x1, x2): f(x) = 2x1 + 3x2 max (Đơn vị tính: 1.000USD) (1) 83 62 21 21 xx xx (2) x1 0; x2 0 (3) 1.1.2.2. Bài toán vận tải Bài toán: Ta cần vận chuyển một loại mặt hàng nào đó (Chẳng hạn: máy tính, linh kiện điện từ, gạo, gỗ, xi măng, xăng dầu,) gồm có m trạm phát hàng A1, A2, , Am với lượng hàng yêu cầu phát đi tương ứng là a1, a2, , am đơn vị hàng, n trạm thu hàng B1, B2, , Bn với lượng hàng yêu cầu chuyển đến tương ứng là b1, b2, , bn đơn vị hàng và ma trận cước phí vận chuyển (Chi phí vận chuyển một đơn vị hàng) c11 c12 c1n c21 c22 c2n C = . viết gọn là: nmij cC . . cm1 cm2 cmn Ở đây cij njmiji ,1 ;,1:, : là cước phí vận chuyển cho mỗi đơn vị hàng hóa được chuyển từ trạm phát Ai đến trạm thu Bj. Bài toán đặt ra với điều kiện 1 1 m n i j i j a b (*) (*) gọi là điều kiện cân bằng thu phát tức là: Tổng lượng hàng phát đáp ứng đầy đủ cho tổng lượng hàng thu (cung bằng cầu). Hãy lập kế hoạch vận chuyển hàng sao cho: - Các trạm phát (cung) hết lượng hàng hiện có. 7- Các trạm thu (cầu) nhận đủ lượng hàng yêu cầu. - Tổng chi phí vận chuyển nhỏ nhất. Phân tich: Gọi xij njmiji ,1 ;,1:, : là lượng hàng vận chuyển từ Ai đến Bj Thấy rằng xij 0; njmiji ,1 ;,1:, trong đó xij > 0 khi Ai phát hàng cho Bj; còn xij = 0 khi Ai không phát hàng cho Bj. Khi đó mô hình của bài toán nói trên là: Tìm một ma trận phân phối và vận chuyển hàng: x11 x12 x1n x21 x22 x2n X = . viết gọn nmij xX . . xm1 xm2 xmn thỏa mãn các điều kiện sau: f(x) = 1 1 m n ij ij i j c x min (tổng chi phí vận chuyển bé nhất) (1) i n j ij ax 1 (tổng lượng hàng phát đi từ trạm Ai) mii ,1: ; j m i ij bx 1 (tổng lượng hàng chuyển đến trạm Bj) njj ,1: . xij 0; njmiji ,1 ;,1:, (3) Ví dụ 2: Ta cần vận chuyển máy tính từ 2 công ty (trạm phát): P1, P2 đến 3 nơi tiêu thụ (trạm thu) T1, T2 và T3. Số lượng máy tính ở mỗi công ty cần chuyển, nhu cầu máy tính tại các nơi tiêu thụ cũng như cước phí vận chuyển cho mỗi máy tính được chuyển từ công ty Pi đến nơi tiêu thụ Tj 3,1 ;2,1:, jiji được cho trong bảng sau: T1: 15 (máy) T2: 20 (máy) T3: 25 (máy) P1: 20 (máy) 5 (nghìn đồng) 7 (nghìn đồng) 2 (nghìn đồng) P2: 40 (máy) 4 (nghìn đồng) 4 (nghìn đồng) 6 (nghìn đồng) Hãy lập kế hoạch vận chuyển như thế nào để: (2) Cước phí Công ty Trạm thu 8- Các công ty phải phân phối hết số máy tính hiện có. - Các nơi tiêu thụ nhận đủ số máy theo nhu cầu. - Tổng cước phí vận chuyển là thấp nhất. Giải: Gọi xij là số máy tính sẽ vận chuyển từ công ty (Pi) đến nơi tiêu thụ (Tj) njmiji ,1 ;,1:, Với điều kiện: xij 0 njmiji ,1 ;,1:, . Số máy tính vận chuyển từ P1 đến 3 nơi tiêu thụ là: x11 + x12 + x13 Số máy tính vận chuyển từ P2 đến 3 nơi tiêu thụ là: x21 + x22 + x23 Số máy tính vận chuyển đến tiêu thụ T1 từ 2 công ty là: x11 + x21 Tổng số máy tính vận chuyển đến tiêu thụ T2 từ 2 công ty là: x12 + x22 Tổng số máy tính vận chuyển đến tiêu thụ T3 từ 2 công ty là: x13 + x23 Tổng cước phí phải chi trả là: (Tổng này càng nhỏ càng tốt) 5x11 + 7x12 + 2x13 + 4x21 + 3x22 + 6x23 Theo đề bài ta có mô hình toán học của bài toán là: Tìm x = (xij) 3,1 ;2,1:, jiji thỏa mãn: f(x) = 5x11 + 7x12 + 2x13 + 4x21 + 3x22 + 6x23 min (1) x11 + x12 + x13 = 20 x21 + x22 + x23 = 40 x11 + x21 = 15 (2) x12 + x22 = 20 x13 + x23 = 25 xij 0 3,1 ;2,1:, jiji . (3) 9Ma trận hệ số 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 A ; 25 20 15 40 20 B ; 11 12 13 21 22 23 x x x x x X x Ở đây thay vì viết x = (x11, x12, x13, x21, x22, x23) ta viết thành ma trận như trên đề mỗi hàng ứng với một trạm phát và mỗi cột ứng với một trạm thu cho dễ hình dung. 1.1.2.3. Bài toán khẩu phần thức ăn Bài toán: Giả sử ta đã biết được nhu cầu tối thiểu hằng ngày về các chất dinh dưỡng (đường, đạm, béo, khoáng...) cần cho một loại đối tượng nào đó (trẻ con, người lớn, heo, gà,...). Để cung cấp các chất dinh dưỡng này hiện có một số thức ăn có thể mua được trên thị trường và cũng biết tỉ lệ các chất dinh dưỡng trong mỗi loại thức ăn cũng như giá cả của chúng. Vấn đề đặt ra là cần xác định số lượng thức ăn mỗi loại trong khẩu phần thức ăn hàng ngày sao cho vừa đảm bảo cung cấp đủ chất dinh dưỡng đồng thời giá thành là rẻ nhất. Bài toán khẩu phần thức ăn là một bài toán cụ thể nhưng mô hình của nó có thể dùng cho các bài toán khác. Thực chất đây là bài toán hỗn hợp nhiều thành phần để đạt được yêu cầu nào đó về chất lượng sản phẩm, đồng thời có giá thành rẻ nhất. Có thể áp dụng mô hình này cho các ngành như luyện kim, hoá chất,... Phân tích: Ký hiệu: n là số loại thức ăn. m là số loại dinh dưỡng cần cho khẩu phần. aij là hàm lượng chất dinh dưỡng i có trong một đơn vị thức ăn j njmiji ,1 ;,1:, . bi là số đơn vị chất dinh dưỡng i cần cho 1 khẩu phần thức ăn mii ,1: 10 cj là đơn giá 1 đơn vị thức ăn j njj ,1: . xj là số lượng thức ăn j cần mua cho 1 khẩu phần thức ăn njj ,1: . Hàm mục tiêu là: nn xcxcxcxf ...2211 . Bài toán có thể phát biểu như sau: Xác định các giá trị x1, x2, , xn sao cho hàm mục tiêu f đạt giá trị nhỏ nhất đồng thời đảm bảo yêu cầu dinh dưỡng cho mỗi khẩu phần thức ăn. Mô hình toán học của bài toán là: min...2211 nn xcxcxcxf (1) mnmnmm nn nn bxaxaxa bxaxaxa bxaxaxa ... ................................................ ... ... 2211 22222121 11212111 (2) 0...;;0 ;0 21 nxxx (3) Ví dụ 3: Có 3 loại thức ăn I, II, III dùng trong chăn nuôi. Các chất dinh dưỡng cơ bản là chất đạm, chất béo và Albumin. Mức độ yêu cầu các chất dinh dưỡng trong một ngày, hàm lượng các chất dinh dưỡng trong mỗi loại thức ăn và giá cả của chúng cho ở bảng sau: Thức ăn Dinh dưỡng I II III Đạm 0,5 10 0,4 20 Béo 3,0 0,5 0,7 10 Albumin 0,3 0,8 2,0 15 0,8 1,5 3,0 Yêu cầu Đơn giá Các số liệu được hiểu như sau: Một đơn vị thức ăn loại I có 0,5 đơn vị chất đạm, 3 đơn vị chất béo và 0,3 đơn vị Albumin. 11 Mỗi đơn vị thức ăn loại I; II; III lần lượt có giá trị tương ứng là: 0,8; 1,5 và 3,0 đơn vị tiền. Yêu cầu tối thiểu của chất đạm là 20 đơn vị, của chất béo là 10 đơn vị và của Albumin là 15 đơn vị. Xác định số liệu để ghi vào bảng trên là công việc của các nhà kinh tế, chuyên môn, không thuộc phạm vi quy hoạch tuyến tính. Nhiệm vụ đặt ra là: cần xác định số liệu thức ăn mỗi loại sao cho đảm bảo yêu cầu về dinh dưỡng, đồng thời giá thành khẩu phần thức ăn là nhỏ nhất. Ta cần thành lập mô hình của bài toán này: Gọi x1, x2, x3 lần lượt là số lượng thức ăn loại I, II, III cần mua. Đây là những số cần tìm. Hàm mục tiêu sẽ là: min35,18,0 321 xxxxf (1) Hệ ràng buộc là: 152 8,03,0 107,05,03 204,010 5,0 321 321 321 xxx xxx xxx (2) 0 ;0 ;0 321 xxx . (3) Điều kiện (3) có được là vì số lượng thức ăn không thể âm. Nhiệm vụ của bài toán là tìm bộ giá trị (x1, x2, x3) thoả mãn các ràng buộc (2), (3) và sao cho hàm mục tiêu f(x) đạt giá trị nhỏ nhất. Nhận định chung: Qua các ví dụ được trình bày ở phần trên, ta thấy rằng trong nhiều lĩnh vực khác nhau có những yêu cầu khác nhau trong việc đề ra các quyết định định lượng nhằm tối ưu hóa sản xuất. Nhưng những yêu cầu này có thể được diễn giải thành mô hình toán học và tổng quát hóa như sau: (1) Điều kiện tối ưu hóa: Đòi hỏi thỏa mãn yêu cầu về mặt kinh tế bao gồm 2 trường hợp cực đại hóa hoặc cực tiểu hóa. 12 (2) Điều kiện ràng buộc: Bao gồm một hệ gồm các phương trình họăc bất phương trình bậc nhất. Hệ thống các ràng buộc này xuất phát từ những đòi hỏi cần được thỏa mãn về mặt kỹ thuật. (3) Điều kiện về dấu: Xuất phát từ yêu cầu thực tiển là các quyết định đỏi hỏi không âm. Các cách biểu diễn của bài toán quy hoạch tuyến tính như sau: Tìm x = (x1, x2, , xn) R n thỏa mãn: f(x) = x1c1 + x2c2 + + xncn min/ (max) (1) a11x1 + a12x2 + + a1nxn b1 a21x1 + a22x2 + + a2nxn b2 (2) am1x1 + am2x2 + + amnxn bm xj 0 njj ,1: (3) Hay viết gọn: Tìm x = (x1, x2, , xn) với xj R njj ,1: thỏa mãn: f(x) = 1 n j j j c x min/ (max) (1) 1 n ij j j a x ; mii ,1: (2) xj 0; njj ,1: (3) Dạng ma trận của bài toán: Gọi nmij aA . ; c = (c1 c2 cn) T, x = (x1 x2 xn) T, b = (b1 b2 bm) T. Khi đó: Bài toán quan hệ tuyến tính tổng quát có thể viết: f(x) = cTx min/ (max) (1/) Ax b (2/) x 0 (3/) 13 Trong đó các aij, bj và các cj đều đã biết, còn xj njj ,1: là các ẩn số njmiji ,1 ;,1:, . 1.2. Các dạng bài toán quy hoạch tuyến tính 1.2.1. Bài toán quy hoạch tuyến tính tổng quát Bài toán quy hoạch tuyến tính tổng quát được định nghĩa như sau: (max)min/...2211 nn xcxcxcxf (1) m1,i:i ...2211 ininii bxaxaxa (2) 0 jx hoặc tuỳ ý njj ,1: (3) (Ký hiệu: nghĩa là lấy một trong 3 dấu trong ngoặc; nghĩa là lấy một trong 2 dấu trong ngoặc). - Hàm f gọi là hàm mục tiêu của bài toán - Phương án của bài toán là vectơ nxxxx ...,,, 21 thoả mãn ràng buộc (2) và (3). Ký hiệu S là tập tất cả các phương án của bài toán. - Phương án tối ưu của bài toán là **2*1* ...,,, nxxxx làm cho hàm mục tiêu f đạt giá trị nhỏ nhất đối với bài toán min và lớn nhất đối với bài toán max, tức là phương án thoả mãn điều kiện (1). Ký hiệu S* là tập tất cả các phương án tối ưu của bài toán. - Trị tối ưu của bài toán là: * ... ảng cũng là phương án tối ưu của bài toán. 1 1 1 1 1 1 107 5.5.3. Bài toán vận tải có ô cấm 5.5.3.1. Nội dung phương pháp Trong thực tế cũng thường xảy ra trường hợp: Hàng từ trạm phát Ah mh 1 không thể chở đến trạm thu Bk nk 1 có nhiều lý do khác nhau, chẳng hạn từ trạm phát Ah đến trạm thu Bk không có đường đi hoặc trạm thu Bk không có nhu cầu về hàng hoá của trạm phát Ah. Ô (h, k) gọi là ô cấm. Vì vậy ta có bài toán vận tải có ô cấm. Để giải bài toán vận tải có ô cấm ta thực hiện như sau: - Gán cho các ô cấm (h, k) hệ số chi phí Chk = M, với M là một số rất lớn . - Giải bằng phương pháp thế vị một cách bình thường. Lưu ý Khi xét tiêu chuẩn tối ưu, biểu thức ijjiij cvu sẽ dương (âm) nếu chứa M với dấu dương (âm). 5.5.3.2. Ví dụ Giải bài toán vận tải có ô cấm sau: Bj Ai b1 45 b2 100 b3 50 b4 60 a1 70 M 16 15 11 a2 100 10 17 9 M a3 85 12 14 10 13 Giải. Mục đích của chúng ta là phân phối sao cho chi phí đạt giá trị nhỏ nhất (min) cho nên chi phí cho các ô cấm sẽ được gán là M > 0, rất lớn. Sử dụng phương pháp chi phí nhỏ nhất để tìm phương án cơ bản ban đầu, ta được: 108 Bj Ai b1 45 b2 100 b3 50 b4 60 a1 70 M 16 10 15 11 60 a2 100 10 45 17 5 9 50 M a3 85 12 14 85 10 13 Phương án cơ bản ban đầu: 0 0 85 0 0 50 5 45 60 0 10 0 0X . Số ô chọn của X0 là 6 = 3 + 4 -1, nên X0 không suy biến. Hàng 2 và cột 2 cùng có số ô chọn nhiều nhất. Ở đây chúng ta chọn hàng 2, nên ta gán u2 = 0, sau đó tính các thế vị còn lại như bảng sau: Bj Ai b1 45 b2 100 b3 50 b4 60 ui a1 70 M 9-M 16 10 15 -7 11 60 -1 a2 100 10 45 17 5 9 50 M 12-M 0 a3 85 12 -5 14 85 10 -4 13 -4 -3 vj 10 17 9 12 Với hệ thống thế vị vừa tìm được, chúng ta tiến hành tính các hệ số ước lượng. 109 Từ bảng trên ta có: do M > 0, rất lớn nên jiij ,,0 . Do đó phương án đang xét là phương án tối ưu của bài toán. Vậy phương án tối ưu của bài toán là: 0 0 85 0 0 50 5 45 60 0 10 0 *X và trị tối ưu là: 2995* Xf . 5.5.4. Bài toán xe không 5.5.4.1. Nội dung phương pháp Đối với các doanh nghiệp kinh doanh vận tải thì việc bố trí các xe chạy theo các tuyến là rất quan trọng. Cần bố trí sao cho tổng số tấn - km xe chạy không là nhỏ nhất. Ở trên ta xét bài toán phân phối hàng hoá từ các trạm phát Ai đến các trạm thu Bj. Giải bài toán này ta mới biết lượng xij trong phương án tối ưu là bao nhiêu (tấn), nhưng ta chưa bố trí được các xe tải đi theo các tuyến này như thế nào cho hợp lý (trên quan điểm của xí nghiệp vận tải) để cho xe ít phải chạy không hàng (tức tổng số tấn - km xe chạy không là nhỏ nhất). Bài toán đặt ra như sau: Có những loại hàng khác nhau cần chở từ một số trạm này đến một số trạm khác. Lượng hàng cần vận chuyển và hệ thống đường sá nối liền các trạm đã biết. Cần xác định hành trình của các xe sao cho tổng số tấn - km là nhỏ nhất. Gọi một T - km xe không là số đo của một xe có trọng tải 1 tấn chạy không hàng trên đoạn đường 1 km. Chú ý rằng trạm thu hàng lúc này trở thành trạm phát xe không và trạm phát hàng trở thành trạm thu xe không. Có bao nhiêu xe chở hàng đến trạm thu thì có bấy nhiêu xe không trả về các trạm phát nên bài toán bao giờ cũng cân bằng thu phát. Như vậy bài toán hoàn toàn tương tự như bài toán phân phối hàng, chỉ cần đổi vai trò trạm thu thành trạm phát và ngược lại. Các thuật giải đều như cũ. Chú ý rằng ở đây những đoạn đường chở hàng là hoàn toàn xác định, số lượng hàng phải chở cũng như vậy nên không có vấn đề giảm tổng số T-km xe chạy có 110 hàng, mà chỉ có khả năng xác định hành trình của các xe sao cho tổng số T-km xe không là nhỏ nhất. Ký hiệu: là tuyến xe chạy có tải; là tuyến xe chạy không có tải . [ xi j ] : khối lượng hàng phải vận chuyển; ( xi j ) : ứng với phương án tối ưu của bài toán xe không. Nếu trong một ô có 2 số: [ xi j ] và ( xi j ), ta chọn số nhỏ nhất (đó là số tấn trọng tải xe cần điều động). Sau khi giải bài toán có phương án vận chuyển với tổng số T-km xe không là nhỏ nhất. Sau đó ta còn phải bố trí cụ thể hành trình chi tiết cho từng xe. 5.5.4.2. Ví dụ Một xí nghiệp vận tải thực hiện kế hoạch vận tải sau đây: Nơi cấp hàng Loại hàng Trọng tải xe (tấn) Nơi nhận hàng A1 Sắt 40 20 35 B1 B3 B4 A2 Xi măng 10 15 40 B1 B2 B4 A3 Gạch 30 40 B2 B3 Ma trận khoảng cách từ nơi cấp hàng đến nơi nhận hàng: 3 2 5 4 6 1 4 3 1 4 3 2 . Yêu cầu lập kế hoạch điều động xe sao cho thực hiện được kế hoạch vận tải với tổng số tấn x km xe chạy không tải là ít nhất. Giải. Giả thiết các xe có thể chở được tất cả loại hàng trên. 111 A1: 40 + 20 + 35 = 95; A2: 10 + 15 + 40 = 65 ; A3: 30 + 40 = 70; B1: 40 + 10 = 50; B2: 15 + 30 = 45; B3: 20 + 40 = 60; B4: 35 + 40 = 75. a) Thực hiện phương pháp thế vị giải bài toán thu phát xe không: Phát Thu 50 45 60 75 ui 95 2 20 3 4 1 75 u1 = 0 65 3 5 4 1 60 6 u2 = 1 70 4 25 5 45 2 3 u3 = 2 vj v1 = 2 v2 = 3 v3 = 0 v4 = 1 jiCvu ijjiij ,;0 . Nên phương án tối ưu là: 0 0 45 25 0 60 0 5 75 0 0 20 *X và trị tối ưu là: 515*min Xf . b) Kết hợp với kế hoạch vận chuyển, ta có bảng: [40] (20) [20] [35] (75) [10] (5) [15] (60) [40] (25) [30] (45) [40] 112 Trên bảng ta có 4 ô vừa có ô tròn, vừa có ô vuông là: (1,1); (1,4); (2,1); (3,2) tương ứng ta có 4 tuyến điều động: TABA 20:111 TABA 35:141 TABA 5:212 TABA 30:323 . Sau khi giảm lượng chênh lệch giữa ô tròn và ô vuông giữa, ta có bảng mới: [20] [20] (40) [5] [15] (60) [40] (25) (15) [40] TABABA 20:14231 [20] (20) [5] [15] (40) [20] (25) (15) [40] TABABA 5:23312 [20] (20) [15] (35) [20] (20) (15) [35] TABABA 15:23322 113 [20] (20) [15] (20) [20] (20) [20] TABABABA 20:1423311 . Tóm lại: TABA 20:111 TABA 35:141 TABA 5:212 TABA 30:323 TABABA 5:23312 TABABA 15:23322 TABABABA 20:1423311 . 114 Bài tập chương 5. BÀI TOÁN VẬN TẢI, THUẬT TOÁN THẾ VỊ Bài 1. Giải bài toán vận tải 30 40 50 60 30 5 4 6 4 40 4 3 5 3 110 2 2 1 7 Bài 2. Giải bài toán vận tải 110 40 30 60 7 3 4 50 1 5 6 40 2 3 4 30 2 4 5 Bài 3. Giải bài toán vận tải 104 22 40 118 31 1 4 2 2 50 3 4 2 4 75 4 3 2 3 128 2 4 4 4 Bài 4. Giải bài toán vận tải cij A B cij A B cij A B 115 60 25 15 20 30 4 3 2 1 40 2 8 6 5 50 3 5 7 9 Bài 5. Giải bài toán vận tải 60 60 80 50 100 5 4 6 2 20 3 1 4 7 130 4 5 6 3 Bài 6. Giải bài toán vận tải tìm max: Bj Ai b1 76 b2 62 b3 88 b4 45 b5 40 a1 79 10 19 15 6 7 a2 102 13 11 8 7 4 a3 70 12 17 10 5 3 a4 60 12 18 18 9 10 cij A B cij A B 116 Bài 7. Giải bài toán vận tải có ô cấm sau: Bj Ai b1 70 b2 80 b3 40 b4 30 a1 100 M 30 45 M a2 80 55 40 30 50 a3 40 50 35 35 45 Bài 8. Giải bài toán vận tải có ô cấm sau: Bj Ai b1 50 b2 80 b3 35 b4 65 a1 55 7 11 14 101 a2 115 10 M 9 M a3 60 12 10 11 14 Bài 9. Giải bài toán vận tải có ô cấm sau: Bj Ai b1 140 b2 155 b3 170 a1 110 5 7 10 a2 125 8 5 9 a3 120 12 6 11 a4 135 9 8 13 Với điều kiện trạm a2 và trạm a4 phát hết hàng. 117 Bài 10. Giải bài toán vận tải có ô cấm sau: Bj Ai b1 45 b2 55 b3 40 b4 75 a1 70 5 6 6 8 a2 65 4 5 8 7 a3 55 3 4 7 3 Với điều kiện trạm b1 và trạm b3 thu đủ hàng. Bài 11. Giải bài toán không cân bằng thu phát sau: Bj Ai b1 25 b2 35 b3 60 b4 30 a1 20 2 3 1 4 a2 40 4 5 3 2 a3 60 1 2 7 6 Bài 12. Giải bài toán không cân bằng thu phát sau: Bj Ai b1 20 b2 30 b3 45 b4 50 a1 40 5 8 6 11 a2 30 6 7 7 12 a3 55 8 8 9 10 118 Bài 13. Giải bài toán không cân bằng thu phát sau: Bj Ai b1 50 b2 35 b3 65 b4 75 a1 90 2 3 1 4 a2 75 4 5 3 2 a3 80 1 2 7 6 Bài 14. Giải bài toán không cân bằng thu phát sau: Bj Ai b1 50 b2 70 b3 75 a1 40 12 14 25 a2 65 26 17 13 a3 45 15 18 19 a4 60 16 23 22 Bài 15. Một xí nghiệp vận tải thực hiện kế hoạch vận tải sau đây: Nơi cấp hàng Loại hàng Trọng tải xe (tấn) Nơi nhận hàng A1 Đường 50 20 B1 B4 A2 Đậu 45 5 30 B2 B3 B4 A3 Hạt điều 35 55 B1 B3 Ma trận khoảng cách từ nơi cấp hàng đến nơi nhận hàng: 5 2 5 4 3 1 4 3 2 4 3 2 . 119 Yêu cầu lập kế hoạch điều động xe sao cho thực hiện được kế hoạch vận tải với tổng số tấn x km xe chạy không tải là ít nhất. Bài 16. Một xí nghiệp vận tải thực hiện kế hoạch vận tải sau đây: Nơi cấp hàng Loại hàng Trọng tải xe (tấn) Nơi nhận hàng A1 Gạo 30 40 50 B1 B2 B3 A2 Đường 75 55 B3 B4 A3 Sữa 20 50 15 B1 B2 B4 Ma trận khoảng cách từ nơi cấp hàng đến nơi nhận hàng: 2 4 1 3 3 5 2 1 4 1 3 6 . Yêu cầu lập kế hoạch điều động xe sao cho thực hiện được kế hoạch vận tải với tổng số tấn x km xe chạy không tải là ít nhất. Bài 17. Một xí nghiệp vận tải thực hiện kế hoạch vận tải sau đây: Nơi cấp hàng Loại hàng Trọng tải xe (tấn) Nơi nhận hàng A1 Gạo 50 30 B2 B4 A2 Mì 25 40 B1 B3 A3 Đường 10 15 B1 B2 Ma trận khoảng cách từ nơi cấp hàng đến nơi nhận hàng: 60 50 60 30 40 60 30 40 30 70 50 20 . 120 Yêu cầu lập kế hoạch điều động xe sao cho thực hiện được kế hoạch vận tải với tổng số tấn x km xe chạy không tải là ít nhất. Bài 18. Một xí nghiệp vận tải thực hiện kế hoạch vận tải sau đây: Nơi cấp hàng Loại hàng Số lượng (tấn) Nơi nhận hàng A1 Cam 50 20 B1 B2 A2 Bưởi 10 40 B1 B3 A3 Sầu riêng 50 30 B4 B2 Ma trận khoảng cách từ nơi cấp hàng đến nơi nhận hàng: 50 20 40 50 20 10 30 40 50 40 20 30 . Yêu cầu lập kế hoạch điều động xe sao cho thực hiện được kế hoạch vận tải với tổng số tấn x km xe chạy không tải là ít nhất. Bài 19. Một xí nghiệp vận tải thực hiện kế hoạch vận tải sau đây: Nơi cấp hàng Loại hàng Trọng tải xe (tấn) Nơi nhận hàng A1 Gạo 100 50 B1 B2 A2 Bắp 10 50 B1 B3 A3 Bột mì 100 80 B4 B2 Ma trận khoảng cách từ nơi cấp hàng đến nơi nhận hàng: 60 50 65 30 45 65 30 40 35 70 55 25 . Yêu cầu lập kế hoạch điều động xe sao cho thực hiện được kế hoạch vận tải với tổng số tấn x km xe chạy không tải là ít nhất. 121 TÀI LIỆU THAM KHẢO [1] Trần Đình Ánh (2007), Bài tập Quy hoạch tuyến tính, NXB Giáo dục, Hà Nội. [2] Phí Mạnh Ban (1998), Quy hoạch tuyến tính, NXB Giáo dục, Hà Nội. [3] Trần Quốc Chiến (2007), Giáo trình quy hoạch tuyến tính, Đại học Đà Nẵng, (Lưu hành nội bộ).. [4] Võ Văn Tuấn Dũng (2007), Giáo trình quy hoạch tuyến tính, NXB Thống kê. [5] Hoàng Đức Hải -Vũ Thị Bích Liên - Trần Gia Tùng (2000), Giáo trình Toán kinh tế , NXB Giáo dục, Hà Nội. [6] Đặng Hấn (1995), Quy hoạch tuyến tính (Lý thuyết & Bài tập có lời giải), Trường ĐH Kinh tế Tp Hồ Chí Minh, (Lưu hành nội bộ). [7] Nguyễn Đức Hiền (2009), Giáo trình quy hoạch tuyến tính, NXB Thông tin và truyền thông, Hà nội. [8] Lê Khánh Luận (2006), Lý thuyết-Bài tập-Bài giải Quy hoạch tuyến tính tối ưu hóa, NXB Lao động. [9] Nguyễn Đức Nghĩa (1996),Tối ưu hóa (Quy hoạch tuyến tính và rời rạc), NXB Giáo dục, Hà Nội. [10] Lê Văn Phi (2004), Quy hoạch tuyến tính và ứng dụng trong kinh tế, NXB Giáo dục, Hà Nội. [11] Nguyễn Xuân Thủy (1995), Bài tập Quy hoạch tuyến tính, NXB Giáo dục, Hà Nội. [12] Trần Túc (2001), Bài tập quy hoạch tuyến tính, NXB Khoa học Kỹ thuật. [13] Hoàng Tụy (1967), Lý thuyết quy hoạch, NXB Giáo dục, Hà Nội. [14] G.Dantzig (1963), Linear programming and extensions, Jersey. [15] Kuzexov A.B., Cholod N.I., Koxtevich L.X. (1978), Hướng dẫn giải bài toán quy hoạch tuyến tính, NXB Đại học (Tiếng Nga). Minsk. [16] Achmanov S. (1984), Programmation Linéeire. Edition Mir. Moscou. [17] Gass S.I. (1969), Linear Programming – Methols and Applications. McGraw-Hill Book Co. New York. 122 MỤC LỤC Lời nói đầu 2 Chương 1. BÀI TOÁN QUY HOẠCH TUYẾN TÍNH... 4 1.1. Một vài bài toán thực tế 4 1.1.1. Xây dựng mô hình toán học cho một số vấn đề thực tế 4 1.1.2. Một vài bài toán thực tế.. 4 1.2. Các dạng bài toán quy hoạch tuyến tính 13 1.2.1. Bài toán quy hoạch tuyến tính tổng quát..... 13 1.2.2. Bài toán quy hoạch tuyến tính dạng chuẩn tắc 15 1.2.3. Bài toán quy hoạch tuyến tính dạng chính tắc 16 1.3. Phương pháp hình học giải bài toán quy hoạch tuyến tính hai biến . 18 1.3.1. Nội dung phương pháp...... 18 1.3.2. Các ví dụ............ 19 Bài tập chương 1.. 23 Chương 2. TÍNH CHẤT CỦA TẬP PHƯƠNG ÁN VÀ TẬP PHƯƠNG ÁN TỐI ƯU CỦA BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 27 2.1. Tập hợp lồi... 27 2.1.1. Tổ hợp lồi.. 27 2.1.2. Tập hợp lồi 27 2.1.3. Điểm cực biên của một tập hợp lồi.. 28 2.1.4. Bao lồi . 28 2.1.5. Đa diện lồi và tập lồi đa diện 29 2.2. Tính chất của tập phương án và tập phương án tối ưu của bài toán quy hoạch tuyến tính.. 30 2.2.1. Định lý 1 (Tính lồi của tập phương án). 30 2.2.2. Định lý 2 (Sự tồn tại lời giải của bài toán quy hoạch tuyến tính). 30 2.2.3. Định lý 3 31 2.3. Tính chất của bài toán quy hoạch tuyến tính dạng chính tắc.. 31 2.3.1. Định lý 1 (Tính chất đặc trưng của phương án cực biên) . 31 2.3.2. Hệ quả 1. .. 33 123 2.3.3. Hệ quả 2 33 2.3.4. Định lý 2 35 2.3.5. Định lý 3 35 Bài tập chương 2. 36 Chương 3. PHƯƠNG PHÁP ĐƠN HÌNH VÀ CÁC THUẬT TOÁN CỦA NÓ .. 37 3.1. Cơ sở lý luận của phương pháp đơn hình 37 3.1.1. Định nghĩa 37 3.1. 2. Các tính chất cơ bản 38 3.2. Công thức đổi cơ sở 40 3.2.1. Phép biến đổi Jordan 40 3.2.2. Giải hệ phương trình tuyến tính 41 3.2.3. Phương pháp tìm phương án . 44 3.3. Thuật toán đơn hình gốc 47 3.3.1. Thuật toán đơn hình giải bài toán quy hoạch tuyến tính.. 47 3.3.2. Các ví dụ 49 3.4. Thuật toán đơn hình với cơ sở giả. 53 3.4.1. Nội dung phương pháp 53 3.4.2. Ví dụ 54 Bài tập chương 3. 57 Chương 4 BÀI TOÁN ĐỐI NGẪU, THUẬT TOÁN ĐƠN HÌNH ĐỐI NGẪU 59 4.1. Bài toán đối ngẫu. 59 4.1.1. Định nghĩa. 59 4.1.2. Mối quan hệ giữa bài toán gốc và bài toán đối ngẫu. 62 4.1.3. Tìm phương án tối ưu của bài toán đối ngẫu 63 4.2. Thuật toán đơn hình đối ngẫu.. 66 4.2.1. Nội dung thuật toán đơn hình đối ngẫu . 66 4.2.2. Thuật toán đơn hình đối ngẫu.. 68 4.2.3. Ứng dụng. 72 124 4.3. Ý nghĩa của bài toán đối ngẫu. 74 4.3.1. Ý nghĩa toán học... 74 4.3.2. Ý nghĩa kinh tế.. 77 Bài tập chương 4.. 79 Chương 5. BÀI TOÁN VẬN TẢI, THUẬT TOÁN THẾ VỊ .. 82 5.1. Một số tính chất của bài toán vận tải... 82 5.1.1. Thành lập bài toán .. 82 5.1. 2. Một số định nghĩa khác... 83 5.1. 3. Các tính chất. 84 5.2. Một số phương pháp xây dựng phương án cực biên ban đầu.. 86 5.2.1. Phương pháp góc Tây Bắc .. 86 5.2.2. Phương pháp chi phí nhỏ nhất .. 87 5.2.3. Phương pháp Foghen . 89 5.3. Thuật toán thế vị 90 5.3.1. Nội dung thuật toán thế vị 90 5.3.2. Ví dụ . 91 5.4. Bài toán vận tải suy biến . 96 5.4.1. Khái niệm về bài toán vận tải suy biến 96 5.4.2. Ví dụ . 96 5.5. Một số bài toán quy về bài toán vận tải chính tắc. 99 5.5.1. Bài toán vận tải không cân bằng thu phát.. 99 5.5.2. Bài toán vận tải tìm max. 105 5.5.3. Bài toán vận tải có ô cấm.. 107 5.5.4. Bài toán xe không ..... 109 Bài tập chương 5 114 Tài liệu tham khảo .. 121 Mục lục 122
File đính kèm:
bai_giang_quy_hoach_tuyen_tinh_phan_ba_trinh.pdf