Chuyên đề 4: QUY HOẠCH TUYẾN TÍNH

Chia sẻ: Minh Nhí | Ngày: | Loại File: PDF | Số trang:21

Thêm vào BST

Báo xấu

233
lượt xem 40
download

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

Điều kiện tiên quyết: Đã học xong chương trình toán C2. Mục đích của học phần: Trang bị cho sinh viên các kiến thức về một số mô hình tối ưu trong kinh tế.  Về kiến thức:  Hiểu biết các khái niệm về bài toán quy hoạch tuyến tính, bài toán đối ngẫu, bài toán vận tải.  Nắm vững các phương pháp giải toán: phương pháp đơn hình, đơn hình đối ngẫu, phương pháp thế vị.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Chuyên đề 4: QUY HOẠCH TUYẾN TÍNH

QUY HOẠCH TUYẾN TÍNH 02/09/2012 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH  Số tín chỉ: 2 (30 tiết).  Điều kiện tiên quyết: Đã học xong chương trình toán C2. MÔN QUY HOẠCH TUYẾN TÍNH  Mục đích của học phần: Trang bị cho sinh viên các kiến thức về một số mô hình tối ưu trong kinh tế.  Về kiến thức: Giảng viên : Ths. NGUYỄN NGỌC CHƯƠNG  Hiểu biết các khái niệm về bài toán quy hoạch tuyến tính, bài toán đối ngẫu, bài toán vận tải.  Nắm vững các phương pháp giải toán: phương pháp đơn hình, đơn hình đối ngẫu, phương pháp thế vị. 1 2 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH  Tài liệu tham khảo: Về kỹ năng: [1] GS. Đặng Hấn, Quy hoạch tuyến tính, ĐHKT  Biết vận dụng các phương pháp vào giải một TP.HCM. số bài toán cụ thể trong thực tế. [2] GS. Phan Quốc Khánh, Quy hoạch tuyến tính,  Nội dung của học phần: NXBGD 1998.  Chương 1: Bài toán quy hoạch tuyến tính.  Tiêu chuẩn và hình thức đánh giá kết quả :  Chương 2: Bài toán đối ngẫu.  Dự lớp: Từ 80% số tiết trở lên.  Chương 3: Bài toán vận tải.  Tiểu luận: (tuần thứ 6)  Giáo trình:  Thi giữa kỳ: Tự luận (tuần thứ 6) [1] TS Nguyễn Phú Vinh, Giáo trình Quy hoạch  Thi kết thúc học phần: Tự luận tuyến tính, Trường ĐHCN TP.HCM.  Thang điểm: Theo học chế tín chỉ. 3 4 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Bài toán lập kế hoạch sản xuất Một công ty sản xuất n loại sản phẩm Sj (j=1,2, ..,n) Chương1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH sử dụng m loại nguyên liệu N i (i = 1,2, ..,m). Biết: + Lượng nguyên liệu Ni cần thiết dùng để sản xuất MỘT SỐ BÀI TOÁN DẪN ĐẾN một đơn vị sản phẩm Sj là: aij BÀI TOÁN QUY HOẠCH TUYẾN TÍNH + Trữ lượng nguyên liệu loại Ni là: bi + Tiền lãi một đơn vị sản phẩm Sj là: cj Hãy xây dựng kế hoạch sản xuất cho công ty để có lợi nhuận nhiều nhất. 6 5 Chuongnn-hui.blogspot.com 1
QUY HOẠCH TUYẾN TÍNH 02/09/2012 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Minh hoạ dữ liệu bài toán: Giải: Gọi xj là lượng Sj (j=1,2, ..,n) cần sản xuất. xj ≥ 0. Sản phẩm Số nguyên S1 S2 … Sn Lượng nguyên liệu N1 dùng cho sản xuất: Nguyên liệu liệu tối đa a11x1 + a12x2 + … + a1nxn ≤ b1 N1 a11 a12 … a1n b1 Lượng nguyên liệu N2 dùng cho sản xuất: a21x1 + a22x2 + … + a2nxn ≤ b2 N2 a21 a22 … a2n b2 ………………………………………………………….. … … … … … … Lượng nguyên liệu Nm dùng cho sản xuất: Nm am1 am2 … amn bm am1x1 + am2x2 + … + amnxn ≤ bm Số tiền lãi mà công ty thu được là: Tiền lãi/đơn vị c1 c2 … cn f = f(x1, x2, … , xn) = c1x1 + c2x2 + … + cnxn sản phẩm 7 8 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Bài toán vốn đầu tư Mô hình toán học của bài toán Tìm x = (x1, x2, …, xn) sao cho Một xí nghiệp xử lý giấy có n phân xưởng Sj f(x) = c1x1 + c2x2 + … + cnxn ⟶ max (j=1,2,…,n) xử lý m loại giấy Ni (i=1,2,…,m). với các ràng buộc Biết: a11x1 + a12x2 + … + a1nxn ≤ b1 . + Lượng giấy loại Ni mà cuối năm phân xưởng Sj có a21x1 + a22x2 + … + a2nxn ≤ b2 .. thể xử lý (nếu cùng đầu tư một đơn vị vốn vào các ……........................................................... phân xưởng) là: aij am1x1 + am2x2 + … + amnxn ≤ bm + Lượng giấy Ni tối thiểu cần phải xử lý theo hợp x1, x2, …, xn ≥ 0 . đồng lao động là: bi Đây là một bài toán quy hoạch tuyến tính. Lập kế hoạch đầu tư để xí nghiệp hoàn thành hợp đồng lao động với tổng vốn đầu tư là nhỏ nhất. 9 10 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Minh hoạ dữ liệu bài toán: Giải: Gọi xj là lượng vốn đầu tư cho Sj (j=1,2, ..,n). xj ≥ 0. Phân xưởng Lượng rác xử S1 S2 … Sn Lượng giấy N1 xử lý được: Loại rác thải lý tối thiểu a11x1 + a12x2 + … + a1nxn ≥ b1 N1 a11 a12 … a1n b1 Lượng giấy N2 xử lý được: a21x1 + a22x2 + … + a2nxn ≥ b2 N2 a21 a22 … a2n b2 ……………………………………… … … ……… … Lượng giấy Nm xử lý được: Nm am1 am2 … amn bm am1x1 + am2x2 + … + amnxn ≥ bm Số vốn mà xí nghiệp cần đầu tư là: f = f(x1, x2, … , xn) = x1 + x2 + … + xn 11 12 Chuongnn-hui.blogspot.com 2
QUY HOẠCH TUYẾN TÍNH 02/09/2012 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Bài toán vận tải Mô hình toán học của bài toán Tìm x = (x1, x2, …, xn) sao cho Xí nghiệp cần vận chuyển hàng hoá từ m điểm phát f(x) = x1 + x2 + … + xn ⟶ min Pi (i=1,2,…,m) đến n điểm thu Tj (j=1,2,…,n). Biết với các ràng buộc + Lượng hàng có ở điểm phát Pi là: ai a11x1 + a12x2 + … + a1nxn ≥ b1 . + Lượng hàng cần ở mỗi điểm thu Tj là: bj a21x1 + a22x2 + … + a2nxn ≥ b2 . + Phí chuyển một đơn vị hàng từ Pi đến Tj là: cij …………………………………………….. Giả sử tổng lượng hàng có ở các điểm phát bằng am1x1 + am2x2 + … + amnxn ≥ bm tổng lượng hàng cần ở các điểm thu. x1, x2, …, xn ≥ 0 . Hãy lập kế hoạch vận chuyển hàng hoá với tổng chi Đây là một bài toán quy hoạch tuyến tính. phí là nhỏ nhất và đảm bảo yêu cầu thu phát. 13 14 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Minh hoạ dữ liệu bài toán: Giải: Gọi xij là lượng hàng cần chuyển từ Pi (i=1,2, ..,m) Điểm thu T1:b1 T2:b2 … Tn:bn đến Tj (i=1,2, ..,m). xij ≥ 0. Điểm phát Lượng hàng chuyển đi từ Pi là: c11 c12 c1n P1:a1 … xi1 + xi2 + … + xin = ai …………………………………………… c21 c22 c2n Lượng hàng chuyển đến Tj là: P2:a2 … x1j + x2j + … + xmj = bj … … … … … …………………………………………… Tổng chi phí vận chuyển là: cm1 cm2 cmn Pm:am … f = f(x11, x12, …, xmn) = c11x11 + c12x12 + … + cmnxmn 15 16 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Bài tập: Mô hình toán học của bài toán Tìm x = (x11, x12, …, xmn) sao cho Lập mô hình toán học của các bài toán sau: f(x) = c11x11 + c12x12 + … + cmnxmn ⟶ min 1. Một xí nghiệp sản xuất ba loại sản phẩm A, B và C chế tạo từ ba loại nguyên liệu I, II và III . Lượng với các ràng buộc nguyên liệu I, II và III mà xí nghiệp có lần lượt là x11 + x12 + … + x1n = a1 20, 40, 30. Lượng nguyên liệu I, II, III cần cho một ……………………………………. đơn vị sản phẩm loại A lần lượt là 3, 3, 2, loại B lần xm1 + xm2 + … + xmn= am lượt là 3, 2, 1, loại C lần lượt là 2, 1, 1 đơn vị. x11 + x21 + … + xm1 = b1 Hãy lập kế hoạch sản xuất để xí nghiệp thu tiền lãi ……………………………………. nhiều nhất, biết tiền lãi một đơn vị sản phẩm loại A x1n + x2n + … + xmn = bn lãi 2 triệu đồng, loại B lãi 4 triệu đồng và loại C lãi x11, x12, …, xmn ≥ 0 . 3 triệu đồng. 17 Chuongnn-hui.blogspot.com 3
QUY HOẠCH TUYẾN TÍNH 02/09/2012 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH 2. Một Xí nghiệp chăn nuôi cần mua thức ăn tổng 3. Một Xí nghiệp xử lý giấy có ba phân xưởng I, II, hợp T1, T2, T3 cho gia súc với tỷ lệ chất dinh III cùng xử lý ba loại giấy A, B, C. Nếu đầu tư 10 dưỡng là: 1 kg T1 chứa 3 đơn vị D1, 3 đơn vị D2 và triệu đồng vào mỗi phân xưởng thì cuối năm phân 2 đơn vị D3; 1 kg T2 chứa 3 đơn vị D1, 2 đơn vị D2 xưởng I xử lý được 3 tạ giấy A, 3 tạ giấy B, 2 tạ giấy và 1 đơn vị D3; 1 kg T3 chứa 2 đơn vị D1, 1 đơn vị C, phân xưởng II xử lý được 3 tạ giấy A, 2 tạ giấy B, D2 và 1 đơn vị D3. Mỗi bữa ăn, gia súc cần tối thiểu 1 tạ giấy C, phân xưởng III xử lý được 2 tạ giấy A, 1 20 đơn vị D1, 40 đơn vị D2 và 30 đơn vị D3. Biết tạ giấy B, 1 tạ giấy C. rằng 1 kg T1 có giá là 2 ngàn đồng, 1 kg T2 có giá là Theo yêu cầu Xí nghiệp phải xử lý ít nhất 2 tấn giấy 4 ngàn đồng, 1 kg T3 có giá là 3 ngàn đồng. loại A, 4 tấn giấy loại B, 3 tấn giấy loại C. Hỏi cần Hỏi Xí nghiệp phải mua bao nhiêu kg T1, T2, T3 đầu tư vào mỗi phân xưởng bao nhiêu tiền để xí cho một bữa ăn để bảo đảm tốt về chất dinh dưỡng nghiệp hoàn thành công việc với giá tiền đầu tư là và tổng số tiền mua là nhỏ nhất? nhỏ nhất. Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH 4. Một xí nghiệp chế biến đồ gỗ dùng 3000 đơn vị 5. Một xí nghiệp có thể sử dụng tối đa 510 giờ máy gỗ nguyên liệu nhóm I, 5000 đơn vị gỗ nguyên liệu cán, 360 giờ máy tiện và 150 giờ máy mài để chế nhóm II và 2000 đơn vị gỗ nguyên liệu nhóm III để tạo 3 sản phẩm A, B và C. Để chế tạo một sản phẩm sản xuất tủ trang trí, bàn ghế và giường cao cấp. A cần 9 giờ máy cán, 5 giờ máy tiện và 3 giờ máy Một bộ tủ trang trí bán giá 500000đ dùng 30 đơn mài; một sản phẩm B cần 3 giờ máy cán, 4 giờ máy vị nhóm I, 10 đơn vị nhóm II và 10 đơn vị nhóm III. tiện; một sản phẩm C cần 5 giờ máy cán, 3 giờ máy Một bộ bàn ghế bán giá 800000đ dùng 40 đơn vị tiện và 2 giờ máy mài. Mỗi sản phẩm A trị giá 48 nhóm I, 20 đơn vị nhóm II và 50 đơn vị nhóm III. ngàn đồng, mỗi sản phẩm B trị giá 16 ngàn đồng và Một bộ giường bán giá 400000đ dùng 10 đơn vị nhóm I, 50 đơn vị nhóm II và 80 đơn vị nhóm III. mỗi sản phẩm C trị giá 27 ngàn đồng. Hãy cho biết Hãy xác định số lượng các sản phẩm cần sản xuất xí nghiệp cần chế tạo mỗi loại bao nhiêu sản phẩm sao cho xí nghiệp đạt lợi nhuận nhiều nhất? để có tổng giá trị sản phẩm lớn nhất . Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH 6. Một người nông dân muốn sản xuất lúa gạo và 7. Một xưởng làm cửa sắt có những thanh thép dài lúa mì trên 50 ha đất của ông ta với nguồn nước 12 m, cần cắt thành 8 đoạn dài 4m, 5 đoạn dài 5m dự trữ là 90 ngàn m3 nước và nguồn nhân lực gổm và 3 đoạn dài 7m. Có 5 mẫu cắt sau. Mẫu 1: 3 đoạn 250 công. Biết rằng để sản xuất 1 tấn lúa gạo cần dài 4m, không thừa. Mẫu 2: 1 đoạn 4m, 1 đoạn 5m, sử dụng 3 ha đất, 5 ngàn m3 nước và 15 công với thừa 3m. Mẫu 3: 1 đoạn 4m, 1 đoạn 7m, thừa 1m. lợi nhuận là 18 USD, để sản xuất một tấn lúa mì Mẫu 4: 2 đoạn 5m, thừa 2m. Mẫu 5: 1 đoạn 5m, 1 cần sử dụng 3 ha đất, 4 ngàn m3 nước và 12 công đoạn 7m, không thừa. với lợi nhuận là 21 USD. Hỏi cần dùng những mẫu cắt nào để tiết kiệm nhất. Hỏi người nông dân phải sản xuất bao nhiêu tấn lúa mỗi loại để đạt lợi nhuận cao nhất . Chuongnn-hui.blogspot.com 4
QUY HOẠCH TUYẾN TÍNH 02/09/2012 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH 8. Một xưởng sản xuất dự định mua hai loại máy để in hình vẽ trên vải. Máy A có thể in 100m/phút và chiếm 50 mét vuông diện tích sàn, còn máy B có thể in 200m/phút và chiếm 140 mét vuông diện tích sàn. Xưởng cần in ít nhất 600m/phút và có BÀI TOÁN QUY HOẠCH TUYẾN TÍNH diện tích sàn để đặt máy in tối đa là 350 mét VÀ Ý NGHĨA HÌNH HỌC vuông. Mỗi máy A có giá là 22 triệu đồng và mỗi máy B có giá 42 là triệu đồng. Hỏi cần mua bao nhiêu máy in mỗi loại sao cho tốn ít chi phí nhất . 26 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Bài toán quy hoạch tuyến tính tổng quát V í dụ: + f(x) = x1 – 2x3 – x4 – 2x6 ⟶ max Tìm x = (x1, x2, … , xn) sao cho x1 + 2 x 2 – x4 + x5 ≤ 8 f(x) = c1x1 + c2x2 + … + cnxn ⟶ max(min) (1) x1 – 3 x 3 – x4 + 3 x 6 ≥ 2 với các ràng buộc 2 x1 + x2 + x3 – x4 = 5 ai1x1 + ai2x2 + … + ainxn ≤ bi, i ∊ I1 (2) – x1 + x3 + 2 x 4 – 3 x 5 ≥ 6 ai1x1 + ai2x2 + … + ainxn ≥ bi, i ∊ I2 (3) 2 x2 – 2 x3 – x4 – 2 x6 ≤ 1 1 ai1x1 + ai2x2 + … + ainxn = bi, i ∊ I3 (4) x1, x4 ≥ 0 xj ≥ 0, j ∊ J1 (5) Với I1∪I2∪I3={1,2,…,m}, . x2, x3, x6 ≤ 0 xj ≤ 0, j ∊ J2 (6) I1∩I2∩I3=∅ . x5 ∊ ℝ xj ∊ ℝ, j ∊ J3 (7) và J1∪J2∪J3={1,2,…,n},. J1∩J2∩J3=∅ Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Một số khái niệm Dạng chính tắc của bài toán quy hoạch tuyến tính Tìm x = (x1, x2, … , xn) sao cho Hàm mục tiêu: hàm f(x) = c1x1 + c2x2 + … + cnxn f(x) = c1x1 + c2x2 + … + cnxn ⟶ max(min) Phương án : vectơ x = (x1, x2, … , xn) thoả mãn các ai1x1 + ai2x2 + … + ainxn = bi, i = 1, 2, …, m điều kiện ràng buộc từ (2) đến (7). xj ≥ 0, j = 1, 2, …, n . Phương án tối ưu: phương án làm cho hàm mục hay tiêu đạt max hay min nghĩa là thoả mãn (1). f(x) = ∑cjxj ⟶ max(min) Tập phương án tối ưu : tập hợp tất cả các phương ∑aijxj = bi, i = 1, 2, …, m án của bài toán. xj ≥ 0, j = 1, 2, …, n . Giải bài toán quy hoạch tuyến tính : là tìm phương Lưu ý: Mọi bài toán quy hoạch tuyến tính đều có án tối ưu cho bài toán. thể biến đổi đưa về dạng chính tắc. Chuongnn-hui.blogspot.com 5
QUY HOẠCH TUYẾN TÍNH 02/09/2012 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH V í dụ: Biến đổi về dạng chính tắc Để biến đổi bài toán về dạng chính tắc tìm min ta + f(x) = x1 – 3x2 + 2x3 – x4 ⟶ max thực hiện như sau: 2 x1 + x 2 + x3 – x4 ≤ 8 + Biến hàm mục tiêu f ⟶ max thành g ⟶ min, với x1 – x3 + x4 = 5 g =  f. x1 – 2 x 2 – x3 + 3 x4 ≥ 7 + Biến ràng buộc ∑aijxj ≤ bi thành ∑aijxj + xn+i = bi x1, x3 ≥ 0 bằng cách bổ sung thêm biến xn+i ≥ 0. x2 ≤ 0 g(x) = – x – 2x – 3x + x – x ⟶ min + Biến ràng buộc ∑aijxj ≥ bi thành ∑aijxj – xn+i = bi 1 3 7 8 9 x4 ∊ ℝ bằng cách bổ sung thêm xn+i ≥ 0. 2 x1 + x3 + x5 – x 7 – x8 + x9 = 8 + Đổi biến xj ≤ 0 thành biến x′j ≥ 0 với x′j =  xj x1 – x3 + x8 – x9 = 5 + Đổi biến xj  ℝ thành hiệu x′j  x″j với x′j , x″j ≥ 0 x1 – x3– x6 + 2x7 + 3x8 – 3x9= 7 và x′j  x″j = xj xj ≥ 0, j=1,2,…,9 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Phương án cực biên + f(x) = 2x1 – x2 + x3 – 3x4 ⟶ min x1 + 2 x 2 + 2 x3 – x4 ≥ 6 Xét bài toán 2 x 1 – x2 – 2 x3 + x 4 = 9 f(x) = ∑cjxj ⟶ min 3x1 –x2 + x3 + 2x4 ≤ 12 ∑aijxj = bi, i = 1, 2, …, m x2, x4 ≥ 0 xj ≥ 0, j = 1, 2, …, n . x1 ≤ 0 f(x) = – x2 – 3x4 – 2x7 + x8 – x9 ⟶ min Vectơ liên kết với biến xj là vectơ cột Aj = [aij]m1 2x2– x4 – x5 – x7 + 2x8 – 2x9 = 6 x3 ∊ ℝ có các thành phần là hệ số tương ứng của biến xj. – x2 + x4 – 2 x7 – 2 x 8 + 2 x9 = 9 Phương án cực biên: phương án mà hệ vectơ liên –x2 + 2x4 + x6 – 3x7 + x8 – x9 = 12 kết với các biến xj > 0 tạo thành một hệ vectơ độc xj ≥ 0, j=1,2,…,9 lập tuyến tính. Lưu ý: Từ đây ta chỉ xét các bài toán dạng chính tắc tìm min. Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Biến cơ sở là biến xj > 0, vectơ Aj tương ứng với V í d ụ: biến cơ sở gọi là vectơ cơ sở, biến phi cơ sở là biến + Xét bài toán xj = 0 . f(x) = 4x1 + x2 + x3 ⟶ min x1 +2x2  x3 = 5 Phương án cực biên không suy biến là phương án x1  x 2 + 2 x3 = 5 có đúng m biến cơ sở, nếu số biến cơ sở bé hơn m ta có phương án cực biên suy biến. xj ≥ 0, j=1,2,3 Số các phương án cực biên của một bài toán quy Vectơ nào sau là phương án cực biên không suy hoạch tuyến tính là hữu hạn. biến: x0 = (1, 4, 4), x1 = (5, 0, 0), x2 = (0, 5, 5)? ĐS: x2 = (0, 5, 5) Chuongnn-hui.blogspot.com 6
QUY HOẠCH TUYẾN TÍNH 02/09/2012 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH + Xét bài toán Lưu ý: Cách thành lập một phương án cực biên của f(x) = x1 + 2x2  x3 ⟶ min bài toán quy hoạch tuyến tính dạng chính tắc: x 1 + x2 + x3 = 4 + Xác định hệ vectơ liên kết với n biến. x 1  x2 = 0 + Tìm các hệ con {Ai}, i = 1, 2, …,m gồm m véctơ xj ≥ 0, j=1,2,3 độc lập tuyến tính của hệ vectơ Số hệ con này hữu Vectơ nào sau là phương án cực biên không suy hạn. biến: x0 = (1, 1, 2), x1 = (2, 2, 0), x2 = (0, 0, 4)? + Biểu diễn vectơ b theo hệ con {Ai} ở trên, ta ĐS: x1 = (2, 2, 0) được các hệ số biểu diễn. Thành lập vectơ x có các thành phần là hệ số biểu diễn. + Loại đi những vectơ x có thành phần âm, các véctơ còn lại là các phương án cực biên. 38 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH V í dụ: Tìm các phương án cực biên của bài toán Lưu ý: + f(x) = 2x1 + x3 + 5x4 ⟶ min Do số thành phần dương của một phương án cực biên không suy biến là bằng m nên suy ra số thành x 1 + x3 + x4 = 5 phần bằng 0 sẽ là n – m. 9 1 ĐS: (5, 1, 0, 0), ( , 0, 0, ), x 2  x3 + 2 x4 = 1 2 2 Từ đó suy ra muốn tìm phương án cực biên ta có (0, 6, 5, 0), (0, 0, 3, 2) xj ≥ 0, j=1,2,3,4 thể cho n – m thành phần bằng 0 rồi tính giá trị của + f(x) = 2x1  x3 + 2x4 ⟶ min m thành phần còn lại bằng cách giải hệ m phương x 1 + x2 + x3 + x 4 = 1 0 trình m ẩn. 16 14 2 x 2 + x3  x4 = 6 ĐS: (0, 0, 8, 2), (0, , 0, ), 3 3 xj ≥ 0, j=1,2,3,4 (4, 0, 6, 0), (7, 3, 0, 0) 39 40 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Các tính chất chung của bài toán quy hoạch V í dụ: Tìm các phương án cực biên của bài toán tuyến tính + f(x) = x1 + 6x3  5x4 ⟶ min + Tập các phương án của bài toán quy hoạch tuyến x 1 + 2 x3 + 3 x4 = 5 8 75 ĐS: (5, , 0, 0), (0, , , 0), tính là một tập lồi nghĩa là nếu x, y là hai phương 3 x 2  x3 + 2 x4 = 8 3 22 án bất kỳ của bài toán thì mọi tổ hợp x + (1 )y, 14 5 (0, , 0, ) xj ≥ 0, j=1,2,3,4  ∊ ℝ: 0 ≤  ≤ 1 cũng là một phương án của bài 9 3 + f(x) = x1  6x3 + x4  x5 ⟶ max toán. x 1 + 2 x4 + x5 = 8 + Tập các phương án tối ưu của bài toán quy hoạch tuyến tính cũng là một tập lồi. x 2 + x4  x5 = 4 ĐS: (8,4,6,0,0), (2,10,0,0,6), + Nếu bài toán quy hoạch tuyến tính dạng chính (0,0,2,4,0), (0,6,0,2,4) x 3 + x4 + x5 = 6 tắc có tập phương án khác rỗng thì nó có ít nhất xj ≥ 0, j=1,2,…,5 một phương án cực biên. 41 42 Chuongnn-hui.blogspot.com 7
QUY HOẠCH TUYẾN TÍNH 02/09/2012 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH V í dụ: Giải các bài toán quy hoạch tuyến tính + Điều kiện cần và đủ để bài toán quy hoạch tuyến + f(x) = x1 + 6x3  5x4 ⟶ min tính dạng chính tắc có phương án tối ưu là nó có tập phương án khác rỗng và hàm mục tiêu bị chặn. x1 + 2 x3 + 3 x4 = 5 14 5 ĐS: x* = (0, , 0, ), + Nếu bài toán quy hoạch tuyến tính dạng chính 3 x2  x3 + 2 x4 = 8 9 3 tắc có phương án tối ưu thì nó có ít nhất một 25 fmin =  xj ≥ 0, j=1,2,3,4 phương án cực biên là phương án tối ưu. 3 + f(x) = x1  6x3 + x4  x5 ⟶ max Lưu ý: Từ đây, ta có thể giải bài toán quy hoạch x1 + 2 x4 + x5 = 8 tuyến tính dạng chính tắc nếu biết nó có phương x2 + x 4  x5 = 4 án tối ưu bằng cách tìm tất cả các phương án cực ĐS: x* = (0,6,0,2,4), biên của bài toán, phương án tối ưu là phương án fmax = 2 x3 + x 4 + x5 = 6 mà giá trị hàm mục tiêu lớn nhất (hay nhỏ nhất). xj ≥ 0, j=1,2,…,5 43 44 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Giải bài toán quy hoạch tuyến tính hai + f(x) = x + 3y ⟶ max biến bằng phương pháp hình học x + 2y ≤ 6 2x + y ≤ 10 V í dụ: ‒x + y ≤ 4 + f(x) = 2x +3y ⟶ min x ≥ 0, y ≥ 0 3x + y ≥ 3 ĐS: fmax = 9 tại A (0;3) x  4y ≤ 6 x + 2y ≤ 6 x ≥ 0, y ≥ 0 ĐS: fmin = 2 tại C(1; 0) 45 46 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Cơ sở của phương pháp đơn hình Dựa vào phương án hiện có, ta tìm cách đánh giá phương án đó có là phương án tối ưu hay chưa, nếu phương án đang xét đã là phương án tối ưu thì mục đích của ta đã đạt được nếu chưa là phương PHƯƠNG PHÁP ĐƠN HÌNH án tối ưu thì ta thay thế bởi nó một phương án mới GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH tốt hơn. Xét bài toán dạng chính tắc (P) f(x) = ∑cjxj ⟶ min ∑aijxj = bi, i = 1, 2, …, m xj ≥ 0, j = 1, 2, …, n 47 48 Chuongnn-hui.blogspot.com 8
QUY HOẠCH TUYẾN TÍNH 02/09/2012 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH 00 0 0 Định lý: ( Dấu hiệu tối ưu) Giả sử ta có phương án x = x1 , x 2 , … , x m , 0 , … , 0 với các biến cơ sở tương ứng x1, x2, …, xm và hệ 00 0 Nếu x = x1 , x2 , … , xm , 0, … , 0 là một phương án vectơ cơ sở liên kết là {Ai}, i = 1,2,…,m. cực biên của (P) sao cho ∆j ≤ 0 với mọi j = 1,2,…,n 0 0 Giá trị mục tiêu f x 0 = c1 x1 + c2 x2 + ⋯ + cm xm. 0 thì x là phương án tối ưu. Định lý: ( Dấu hiệu không có phương án tối ưu) Đặt ∆j = c1 x1j + c2 x2j + ⋯ + cm xmj − cj Nếu ngoài cơ sở liên kết của phương án cực biên với xj = (x1j, x2j, …, xmj) là toạ độ của các vectơ Aj tồn tại j sao cho ∆j > 0 và xj ≤ 0 nghĩa là xij≤ 0 với đối với hệ cơ sở {Ai}, gọi là ước lượng của biến xj. mọi i = 1,2,…,m thì (P) không có phương án tối ưu. Lưu ý: Nếu ma trận cột tạo bởi hệ vectơ cơ sở {Ai} Rõ hơn là hàm mục tiêu không bị chặn dưới trên là ma trận đơn vị thì xij = aij. tập phương án. 49 50 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH V í dụ: + Xét bài toán + Xét bài toán f(x) = 7x1 ‒ 26x2 + 9x3 ⟶ min f(x) = x1 + 6x2 + 9x3 ⟶ min x1 ‒ 2 x 2 = 5 x 1 + 2 x3 = 6 ‒x2 + x3 = 7 x 2 + x3 = 8 xj ≥ 0, j = 1, 2, 3. xj ≥ 0, j = 1, 2, 3. Vectơ x = (5, 0, 7) có phải là phương án tối ưu hay không? Vectơ x = (6, 8, 0) có phải là phương án tối ưu hay không? ĐS: x không phải là phương án tối ưu. ĐS: x là phương án tối ưu. fmin = 54. 51 52 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Thuật toán đơn hình Định lý: Xét bài toán Nếu ngoài cơ sở liên kết của phương án cực biên tồn tại j sao cho ∆j > 0 và có ít nhất một xij > 0 với i f(x) = ∑cjxj ⟶ min nào đó thì ta luôn có thể tìm được một phương án ∑aijxj = bi, i = 1, 2, …, m cực biên mới tốt hơn x, nghĩa là phương án này xj ≥ 0, j = 1, 2, …, n làm cho hàm mục tiêu nhỏ hơn phương án x. bi ≥ 0, i=1,2,…,m và có sẵn ma trận đơn vị. + Tìm phương án cực biên ban đầu: Giả sử ma trận đơn vị tạo bởi các vectơ cột Ai, i = 1,2,…,m thì ta có phương án cực biên ban đầu 00 x 0 = x1 , x 2 , … , x m , 0 , … , 0 0 53 54 Chuongnn-hui.blogspot.com 9
QUY HOẠCH TUYẾN TÍNH 02/09/2012 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH + Đánh giá phương án hiện có: lập bảng đơn hình + Xây dựng phương án mới – Phương pháp phần như hình bên dưới và căn cứ vào đó để đánh giá tử trục quay: Xác định cột quay s là cột mà s > 0 lớn nhất, biến Biến Hệ Phương x1 x2 … xn  cơ sở tương ứng xs là biến cơ sở đưa vào. cơ sở số án c1 c2 … cn x0 0 x1 c1 x11 x12 … x1n x1 Dòng quay r là dòng mà r nhỏ nhất với θi = , i xis 0 x2 c2 x21 x22 … x2n x2 (xis > 0) biến cơ sở tương ứng xr là biến cơ sở đưa … … … … … … … ra. 0 xm cm xm xm1 xm2 … xmn Phần tử quay xrs là phần tử giao giữa dòng quay r 1 2 n f(x0) … và cột quay s. 55 56 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Xác định các thành phần phương án x1 mới: V í dụ: Giải các bài toán + f(x) = x1 ‒ x2 ‒ 2x4 + 2x5 ‒ 3x6 ⟶ min PA s↓ x0 r nếu i = r x1 + x 4 + x5 ‒ x6 = 2 i xrs 0 x1 = xi xis i x0 xrs − x0 xis x2 + x 4 + x6 = 1 2 r nếu i ≠ r i r 0 xr xrs xrs x3 + 2 x4 + 4 x5 + 3 x6 = 9 Xác định các hệ số biểu diễn xij mới xj ≥ 0, j = 1, 2, …,6. ĐS: Phương án tối ưu x* = (0, 8, 0, 3, 0, 1). Giá trị j↓ s↓ xrj nếu i = r tối ưu fmin = ‒17. i xrs ′ xij xis xij = xij xrs −xrj xis nếu i ≠ r r xrs xrj xrs 57 58 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Lưu ý: + f(x) = ‒2x1 ‒ 4x2 + x3 ‒ x4 ⟶ min + Nếu bài toán có bi ≥ 0, i=1,2,…,m và chưa có sẵn x 1 + 3 x2 + x5 = 4 ma trận đơn vị ta có thể thực hiện biến đổi ma trận 2 x 1 + x2 ‒ x3 + x6 = 3 hệ số mở rộng của hệ điều kiện ràng buộc để có ma x 2 + 4 x3 + x4 = 3 trận đơn vị. xj ≥ 0, j = 1, 2, …,6. V í dụ: Giải bài toán + f(x) = ‒ 3x1 + x2 + 3x3 ‒ x4 ⟶ min ĐS: Phương án tối ưu x* = (1, 1, 0, 2, 0, 0). Giá trị tối ưu fmin = ‒8. x1 + 2 x2 ‒ x3 + x4 = 2 2x1‒ 6x2 + 3x3 + 3x4 = 9 x1 ‒ x 2 + x3 ‒ x4 = 6 xj ≥ 0, j = 1,2,3,4. 59 60 Chuongnn-hui.blogspot.com 10
QUY HOẠCH TUYẾN TÍNH 02/09/2012 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH ĐS: Bài toán trở thành + f(x) = 3x1 ‒ 4x2 ‒ 5x3 + 6x4 ⟶ min f(x) = ‒ 3x1 + x2 + 3x3 ‒ x4 ⟶ min x1 + x 2 + x3 + 1 3 x4 = 1 4 6 2x1+ x2 + 14x4 = 11 x 1 + x4 = 3 5 3x2 + x3 + 14x4 = 16 12 x2 ‒ x= 2 xj ≥ 0, j = 1,2,3,4. 54 23 x3 ‒ x= 5 54 xj ≥ 0, j = 1, 2, 3, 4. 61 62 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Thuật toán đơn hình mở rộng ĐS: Bài toán trở thành Xét bài toán f(x) = 3x1 ‒ 4x2 ‒ 5x3 + 6x4 ⟶ min f(x) = ∑cjxj ⟶ min 27 x1 + x= 4 54 ∑aijxj = bi, i = 1, 2, …, m 16 xj ≥ 0, j = 1, 2, …, n x2 + x= 3 54 với bi ≥ 0, i=1,2,…,m và chưa có sẵn ma trận đơn vị 22 x3 + x= 7 (giả sử bài toán còn thiếu m vectơ đơn vị). 54 Ta bổ sung thêm m biến xn+i, i=1,2,…,m để có được xj ≥ 0, j = 1, 2, 3, 4. ma trận đơn vị và đưa về xét hàm mục tiêu g = ∑cjxj + Mxn+1 + Mxn+2 + … + Mxn+m với M là một số rất lớn, lớn hơn bất cứ số nào khác. 63 64 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Bài toán trở thành bài toán M sau đây Ta dùng thuật toán đơn hình để giải bài toán M với g(x) = ∑cjxj + Mxn+1 + Mxn+2 + … + Mxn+m ⟶ min một vài lưu ý: ∑aijxj + xn+i = bi, i = 1, 2, …, m + Nếu đã có k vectơ đơn vị thì ta bổ sung vào m – k xj ≥ 0, j = 1, 2, …, n+m biến để có ma trận đơn vị cấp m. Lưu ý: + Hàm mục tiêu g, ước lượng j của các biến xj có Nếu bài toán M có phương án tối ưu (x, t) với t > 0 thể viết dưới dạng g = AM + B, j = jM+ j. t = (xn+1, …, xn+m) thì bài toán chính không có + Để so sánh các ước lượng ta có phương án. Nếu bài toán M có phương án tối ưu αj > αk αj > 0 (x, 0) thì x là phương án tối ưu của bài toán chính ∆j ≥ 0 ⇔ , ∆ ≥ ∆k ⇔ và nếu bài toán M không có phương án tối ưu thì αj = 0, βj ≥ 0 j αj = αk , βj ≥ βk bài toán chính cũng không có phương án tối ưu . và các hệ số A, B, ,  được trình bày trên 2 dòng. 65 66 Chuongnn-hui.blogspot.com 11
QUY HOẠCH TUYẾN TÍNH 02/09/2012 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH V í d ụ: Giải bài toán + f(x) = 3x1 ‒ 4x2 ‒ 5x3 + 6x4 ⟶ min + f(x) = ‒ 3x1 + x2 + 3x3 ‒ x4 ⟶ min x1 + x 2 + x3 + 1 3 x4 = 1 4 x 1 + 2 x2 ‒ x3 + x4 = 2 2x1+ x2 + 14x4 = 11 2x1‒ 6x2 + 3x3 + 3x4 = 9 3x2 + x3 + 14x4 = 16 x 1 ‒ x2 + x3 ‒ x 4 = 6 xj ≥ 0, j = 1,2,3,4. xj ≥ 0, j = 1,2,3,4. ĐS: Phương án tối ưu x* = (4, 3, 7, 0). Giá trị tối ưu fmin = ‒35. ĐS: Phương án tối ưu x* = (3, 2, 5, 0). Giá trị tối ưu fmin = 8. 67 68 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Lưu ý: Với bài toán dạng chính tắc tìm max ta thực 2 17 39 ĐS: Phương án tối ưu x* = ( , , , 0, 0). Giá trị hiện tương tự, chỉ khác là nếu ∆j ≥ 0, ∀j = 1,2,…,n 36 2 88 thì phương án đang xét là tối ưu, nếu có ∆j < 0 mà tối ưu fmax = . 3 xj ≤ 0 thì bài toán không có lời giải, cột quay s là + f(x) = 3x1 ‒ x2 ‒ 2x3 ⟶ max cột tương ứng với ∆s < 0 nhỏ nhất. ‒x1 + 3x2 + x3 + x4 = 7 V í dụ: Giải bài toán 3x1‒ 4x2 + 8x3 + x5 = 10 + f(x) = 2x1 + 3x2 + x3 ⟶ max x 1 ‒ 5 x2 + x3 = 6 4x1‒ 2x2 + x6 = 12 2x1+ 2x2 + x4 = 7 xj ≥ 0, j = 1,2, …,6. ‒x1 + 2x2 + x5 = 5 ĐS: Phương án tối ưu x* = (5, 4, 0, 0, 11, 0). Giá trị xj ≥ 0, j = 1,2,3,4,5. tối ưu fmax = 11. 69 70 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Giải bài toán quy hoạch tuyến tính với EXCEL trong đó ở dòng phương án, ta gán các giá trị ban đầu là 1 (hay 0) cho các biến xj ≥ 0. Cài thêm công cụ Add-ins Solver + Options ⟶ Add-Ins ⟶ Excel Add-Ins. + Trong hộp thoại Add-Ins ta click chọn Solver Add-In. Tổ chức dữ liệu trên bảng tính Tiến hành nhập liệu trên bảng tính Excel như sau 71 72 Chuongnn-hui.blogspot.com 12
QUY HOẠCH TUYẾN TÍNH 02/09/2012 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Ta có thể sửa đổi, thêm bớt các ràng buộc. Muốn Tiến hành giải bài toán thêm vào ràng buộc ta click chọn nút Add. + Data ⟶ Solver + Trong hộp thoại Solver Parameters: Set Objective: click chọn ô chứa giá trị mục tiêu B8. Max/Min/Equal To: chọn loại bài toán để giải. trong hộp thoại Add Constraint: By Changing Cells: click chọn địa chỉ tuyệt đối của Cell Reference: click chọn địa chỉ chứa công thức. các ô ghi các giá trị ban đầu của biến. Ô dấu: lựa chọn dấu của các ràng buộc tương ứng. Subject to the Constraints: nhập các ràng buộc. Constraint: Ô chứa giá trị vế phải của các ràng buộc tương ứng (ta cũng có thể nhập trực tiếp giá trị vế phải của ràng buộc tương ứng). 73 74 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Select a solving method: click chọn phương pháp giải, ở đây là Simplex LP phương pháp đơn hình. Trong hộp thoại Solver Result: Keep Solver Solution: Lấy kết quả, in ra bảng tính. Restore Original Values: Huỷ kết quả vừa tìm được và trả các biến về tình trạng ban đầu. Save Scenario: Lưu kết quả vừa tìm được thành một tình huống để có thể xem lại sau này. Lưu ý: Có 3 loại báo cáo là Answer, Sensitivity và Limits. 75 76 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Định nghĩa bài toán đối ngẫu Xét bài toán quy hoạch tuyến tính gốc (P) f(x) = c1x1 + c2x2 + … + cnxn ⟶ max(min) Chương 2: BÀI TOÁN ĐỐI NGẪU ai1x1 + ai2x2 + … + ainxn ≤ bi, i ∊ I1 (1) ai1x1 + ai2x2 + … + ainxn ≥ bi, i ∊ I2 (2) BÀI TOÁN ĐỐI NGẪU VÀ MỘT SỐ TÍNH CHẤT ai1x1 + ai2x2 + … + ainxn = bi, i ∊ I3 (3) xj ≥ 0, j ∊ J1 (4) xj ≤ 0, j ∊ J2 (5) xj ∊ ℝ, j ∊ J3 (6) 77 78 Chuongnn-hui.blogspot.com 13
QUY HOẠCH TUYẾN TÍNH 02/09/2012 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Bài toán đối ngẫu của bài toán (P) là bài toán (Q): V í dụ: Viết bài toán đối ngẫu (Q) của bài toán (P): g(y) = b1y1 + b2y2 + … + bmym ⟶ min(max) + f(x) = 2x1 – x2 + 3x3 + x4 – 2x5 ⟶ min a1jy1 + a2jy2 + … + amjym ≤ cj, j ∊ J1 (4′) x1 + x 2 + 2 x 3 – x4 + x 5 ≤ 1 2 a1jy1 + a2jy2 + … + amjym ≥ cj, j ∊ J2 (5′) 2 x1 – x 3 + 3 x 4 + 2 x 5 ≥ – 5 a1jy1 + a2jy2 + … + amjym = cj, j ∊ J3 (6′) – x1 + 3 x2 – 2 x4 – x5 = 6 yi ≤ 0, i ∊ I1 (1′) 3 x1 + 2 x2 – x3 + x4 ≥ 3 yi ≥ 0, i ∊ I2 (2′) x1, x3 ≥ 0 yi ∊ ℝ, i ∊ I3 (3′) x5 ≤ 0 Các cặp ràng buộc (1)–(1), (2)–(2), .., (6)–(6) x2, x4 ∊ ℝ được gọi là các ràng buộc đối ngẫu với nhau. 79 80 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Cách thành lập bài toán đối ngẫu ĐS: Bài toán (Q): g(y) = 12y1 – 5y2 + 6y3 + 3y4 ⟶ max Bài toán gốc Chỉ số Bài toán đối ngẫu y1 + 2y2 – y3 + 3y4 ≤ 2 f(x) = cjxj ⟶ min g(y) = biyi ⟶ max y1 + 3y3 + 2y4 = – 1 aijyi ≤ cj xj ≥0 j ∊ J1 2y 1 – y2 – y4 ≤ 3 aijyi ≥ cj xj ≤ 0 j ∊ J2 – y1 + 3y2 – 2y3 + y4 = 1 aijyi = cj xj ∊ ℝ j ∊ J3 y1 + 2y2 – y3 ≥ – 2 y1 ≤ 0 aijxj ≤ bi i ∊ I1 yi ≤ 0 y2, y4 ≥ 0 aijxj ≥ bi i ∊ I2 yi ≥ 0 y3 ∊ ℝ aijxj = bi i ∊ I3 yi ∊ ℝ 81 82 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH ĐS: Bài toán (Q): V í dụ: Viết bài toán đối ngẫu (Q) của bài toán (P): g(y) = 4y1 + 7y2 + 6y3 + 3y4 ⟶ min + f(x) = x1 + x2 + x4 – 3x5 ⟶ max y1 – y2 + 2y3 + y4 = 1 x1 + 2x2– 2x4 + x5 = 4 2y1 – 3y3 – 2y4 ≤ 1 – x1 + 3 x 3 + x4 – 2 x5 ≤ 7 3y2 – y3 + 4y4 ≥ 0 2 x 1 – 3 x2 – x3 – x4 + 3 x5 = 6 –2y1 + y2 – y3 – y4 ≥ 1 x1 – 2x2 + 4x3 – x4 – x5≥ 3 y1 – 2y2 + 3y3 – y4 ≤ – 3 x2, x5 ≥ 0 y2 ≤ 0 x3, x4 ≤ 0 y4 ≥ 0 x1 ∊ ℝ y1,y3 ∊ ℝ 83 84 Chuongnn-hui.blogspot.com 14
QUY HOẠCH TUYẾN TÍNH 02/09/2012 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Mối liên hệ giữa bài toán gốc và bài toán đối ngẫu Định lý 2 (Đối ngẫu mạnh) Nếu một trong hai bài toán có phương án tối ưu thì Xét bài toán quy hoạch tuyến tính gốc dạng chính bài toán đối ngẫu của nó cũng có phương án tối ưu tắc tìm min. và giá trị tối ưu của các hàm mục tiêu của chúng là Định lý 1 (Đối n gẫu yếu) bằng nhau. Cho x, y theo thứ tự là phương án của bài toán gốc Định lý 3 (Định lý tồn tại) và đối ngẫu ta có f(x) ≥ g(y). Một cặp bài toán và bài toán đối ngẫu của nó chỉ có Lưu ý: Từ định lý nếu ta có phương án của bài toán thể xảy ra một trong 3 khả năng loại trừ sau: gốc và đối ngẫu theo thứ tự là x, y mà f(x) = g(y)  Cả hai bài toán đều không có phương án. thì x, y lần lượt là phương án tối ưu của bài toán gốc và bài toán đối ngẫu. 85 86 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH  Cả hai bài toán đều có phương án, khi đó cả hai n cùng có phương án tối ưu và giá trị tối ưu của hai bi − aij xj yi = 0, i = 1, m hàm mục tiêu là bằng nhau. j= 1  Một bài toán có phương án còn bài toán kia m không có phương án, khi đó bài toán có phương án cj − aij yi xj = 0, j = 1, n sẽ không có phương án tối ưu và hàm mục tiêu i =1 không bị chặn trong miền ràng buộc. Lưu ý: bi – aijxj là độ lệch ở ràng buộc thứ i ở bài Định lý 4 (Độ l ệch bù) toán gốc và cj – aijyi là độ lệch ở ràng buộc thứ j ở Một cặp phương án x, y của bài toán gốc và đối bài toán đối ngẫu của nó. ngẫu là phương án tối ưu khi và chỉ khi chúng nghiệm đúng hệ thức sau: 87 88 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH ĐS: Phương án tối ưu của bài toán đối ngẫu là Giải bài toán đối ngẫu 3 y* = (1, − ) và gmax = 6 = fmin Áp dụng định lý độ lệch bù 2 V í dụ: + Cho bài toán gốc + Cho bài toán gốc f(x) = x1 + x2 + x3 + x4 + x5 ⟶ min 3 x1 + x2 + x3 = 1 f(x) = x1  2x2 + 2x3 ⟶ min 5 x1 + x2 + x3 + x4 = 3 x 1 + x2 + 4 x4 = 6 2 x1 + 5 x2 + x3 + x5 = 8 2 x 2 + x3 + 5 x4 = 8 xj ≥ 0, j=1,2,3,4,5 xj ≥ 0, j=1,2,3,4 có phương án tối ưu là x* = (0, 1, 0, 2, 3), fmin = 6. có phương án tối ưu là x* = (2, 4, 0, 0 ), fmin = 6. Tìm phương án tối ưu của bài toán đối ngẫu. Tìm phương án tối ưu của bài toán đối ngẫu. 89 90 Chuongnn-hui.blogspot.com 15
QUY HOẠCH TUYẾN TÍNH 02/09/2012 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH ĐS: phương án tối ưu của bài toán đối ngẫu là ĐS: Phương án tối ưu của bài toán đối ngẫu là y* = (5, 1, 1) và gmax = 6 = fmin 3 y* = (1, − ) và gmax = 6 = fmin Dùng bảng đ ơn h ình của bài toán gốc 2 + Giải bài toán gốc V í dụ: f(x) = x1 + x2 + x3 + x4 + x5 ⟶ min + Giải bài toán gốc 3 x1 + x2 + x3 = 1 f(x) = x1  2x2 + 2x3 ⟶ min x 1 + x2 + 4 x4 = 6 5 x1 + x2 + x3 + x4 = 3 2 x 2 + x3 + 5 x4 = 8 2 x1 + 5 x2 + x3 + x5 = 8 xj ≥ 0, j=1,2,3,4 xj ≥ 0, j=1,2,3,4,5 Suy ra phương án tối ưu của bài toán đối ngẫu. Suy ra phương án tối ưu của bài toán đối ngẫu. 91 92 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Phương pháp đơn hình đối ngẫu ĐS: phương án tối ưu của bài toán đối ngẫu là y* = (5, 1, 1) và gmax = 6 = fmin + Tìm một “giả phương án” *Quy tắc: Nếu cơ sở ban đầu là ma trận đơn vị thì + Lập bảng đơn hình đối ngẫu. Nếu các phần tử để tìm lời giải của bài toán đối ngẫu, ta chọn ra từ trong cột giả phương án đều không âm thì ta có bảng đơn hình cuối cùng các ước lượng j của các phương án tối ưu. biến cơ sở xj ở bảng đơn hình đầu tiên rồi cộng + Dòng quay r là dòng có chứa phần tử âm nhỏ thêm hệ số cj tương ứng. nhất trong cột giả phương án. Ta đã giải quyết các bài toán có sẵn ma trận đơn vị + Cột quay là cột s tương ứng với tỷ số nhỏ nhất với hệ số bi ≥ 0 cũng như bài toán chưa có sẵn ma ∆j trong các tỷ số với xrj < 0. trận đơn vị. Với các bài toán có sẵn ma trận đơn vị xrj nhưng có hệ số bi < 0 ta thường áp dụng phương Tiếp tục biến đổi bảng đơn hình bình thường… pháp đơn hình đối ngẫu sau đây 93 94 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH V í d ụ: Dùng phương pháp đơn hình đối ngẫu, giải + f(x) = 15x1 + 12x2 + 10x3 ⟶ min bài toán 3x1 + 4x2 + 2x3 ≥ 160 + f(x) = x1 + 2x2 + 3x3 + 4x4 ⟶ min x1 + 2x2 + 3x3 ≥ 140 x 1 + x2 + x3 + 4 x4 ≥ 6 xj ≥ 0, j=1,2,3. 4 x1 + x2 + x3 + x4 ≥ 9 ĐS: Phương án tối ưu là x* = (0, 25, 30), giá trị tối xj ≥ 0, j=1,2,3,4. ưu fmin = 600. ĐS: Phương án tối ưu là x* = (2, 0, 0, 1), giá trị tối ưu fmin = 6. 95 96 Chuongnn-hui.blogspot.com 16
QUY HOẠCH TUYẾN TÍNH 02/09/2012 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Định nghĩa bài toán vận tải Xí nghiệp cần vận chuyển hàng hoá từ m kho (điểm Chương 3: BÀI TOÁN VẬN TẢI phát) Pi, i=1,2,…,m đến n nơi tiêu thụ (điểm thu) Tj, j=1,2,…,n. Lượng hàng có ở mỗi kho Pi là ai, i=1,2,…,m. Lượng hàng cần ở mỗi nơi tiêu thụ Tj là BÀI TOÁN VẬN TẢI VÀ MỘT SỐ KHÁI NIỆM bj, j=1,2,…,n. Chi phí vận chuyển một đơn vị hàng từ kho Pi đến nơi tiêu thụ Tj là cij, i=1,2,…m, j=1,2,…,n. Cho biết tổng lượng hàng ở các kho bằng tổng lượng hàng cần tiêu thụ. Hãy lập kế hoạch vận chuyển hàng hoá sao cho tổng chi phí là nhỏ nhất và đảm bảo yêu cầu thu phát. 97 98 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Mô hình toán học của bài toán Ta trình bày dưới dạng bảng vận tải như sau: Tìm x = (x11, x12, …, xmn) sao cho Thu b1 b2 … bn f(x) =  cijxij ⟶ min Phát xij = ai, i=1,2,…,m. c11 c12 c1n a1 … xij = bj, j=1,2,…,n. x11 x12 x1n xij  0, i=1,2,…,m, j=1,2,…,n. c21 c22 c2n a2 … x21 x22 x 2n trong đó ai = bj (điều kiện cân bằng thu phát) … … … … … Lưu ý: Bài toán vận tải cân bằng thu phát luôn có phương án tối ưu và ta cũng có thể giải bằng cm1 cm2 cmn am … xm1 xm2 xmn phương pháp đơn hình. 99 1 00 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Một số khái niệm + Chu trình là một dây chuyền khép kín. Số các ô Xét bảng vận tải m  n. trong một chu trình là số chẵn. Số các ô tối đa trong bảng không tạo thành chu trình là m + n  1. + Ô chọn là ô (i, j) nằm trên dòng i, cột j mà lượng Với m + n  1 ô không tạo thành chu trình ta có thể hàng xij > 0, ô loại là ô (i, j) mà xij = 0. bổ sung thêm một ô bất kỳ để có ít nhất một chu + Dây chuyền là một tập hợp các ô chọn sao cho không có quá hai ô liên tiếp nằm trên cùng một trình. dòng hoặc cột.                             Một số chu trình thường gặp Dây chuyền Không là dây chuyền 1 01 1 02 Chuongnn-hui.blogspot.com 17
QUY HOẠCH TUYẾN TÍNH 02/09/2012 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH T ìm phương án cực biên ban đầu + Ma trận cước phí là ma trận (cij) với cij là cước phí vận chuyển một đơn vị hàng từ Pi đến Tj. Phương pháp “min” cước + Phương án hay ma trận phương án là ma trận + Tìm ô có cước phí bé nhất, (xij) với xij là lượng hàng vận chuyển từ Pi đến Tj. + Phân phối lượng hàng tối đa có thể vào ô đó. + Phương án cực biên là phương án có số ô chọn + Loại bỏ dòng hay cột đã phân phối đủ hàng. tối đa không tạo thành chu trình là m + n  1, nếu Tiếp tục quá trình cho đến khi phân phối hết hàng . số ô này bằng đúng m + n  1 ta có phương án cực biên không suy biến, ngược lại ta có phương án cực biên suy biến. Trường hợp suy biến ta có thể bổ sung thêm một số “ô chọn 0” để có m + n  1 ô không tạo thành chu trình. 1 03 1 04 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH V í dụ: Tìm phương án cực biên ban đầu + + 130 140 120 160 ĐS: Phương án ban đầu ĐS: 30 60 50 40 20 18 22 25 180 0 140 40 0 Phương án ban đầu 1 5 7 2 130 0 0 40 45 30 0 0 15 15 25 30 15 0 0 80 120 170 0 5 50 25 Giá trị mục tiêu 5 7 4 9 80 0 55 0 0 45 30 40 35 f = 13350 200 Giá trị mục tiêu 12 2 3 6 f = 630 55 1 05 1 06 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Phương pháp Vogel V í dụ: Tìm phương án cực biên ban đầu + Tính hiệu số cước phí của hai ô có cước phí bé + nhất trên các dòng và cột. ĐS: 30 60 50 40 + Trên dòng hay cột có hiệu số lớn nhất tìm ô có Phương án ban đầu 1 5 7 2 cước phí bé nhất 30 0 0 15 45 + Phân phối lượng hàng tối đa vào ô có cước phí 0 5 50 25 5 7 4 9 bé nhất đó. 0 55 0 0 80 Giá trị mục tiêu + Loại bỏ dòng hay cột đã phân phối đủ hàng. 12 2 3 6 f = 630 55 + Tính lại hiệu số cước phí trên cột hay dòng. Tiếp tục quá trình cho đến khi phân phối hết hàng. 1 07 1 08 Chuongnn-hui.blogspot.com 18
QUY HOẠCH TUYẾN TÍNH 02/09/2012 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Giải bài toán vận tải + 130 140 120 160 ĐS: T ìm p hương án cực biên không s uy biến ban đ ầu. Phương án ban đầu Áp dụng phương pháp ‘min’ cước hay Vogel. 20 18 22 25 180 120 0 60 0 Đánh giá phương án hiện có – Thuật toán quy 0 10 0 0 160 15 25 30 15 cước p hí ô chọn 0 140 60 0 170 Giá trị mục tiêu + Tìm hệ thống thế vị ui và vj trên các dòng i, cột j 45 30 40 35 f = 12870 sao cho tại các ô chọn (i, j) ta có ui + vj = cij. 200 + Biến đổi ma trận cước phí (cij) thành ma trận cước phí mới (cij) với cij = cij  (ui + vj). 1 09 1 10 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH + Nếu cij  0 với mọi i, j thì phương án đang xét là + Gọi h = min{xij  (i, j)  U}, biến đổi ma trận phương án tối ưu, trái lại ta chuyển sang xây dựng phương án (xij) thành ma trận phương án mới (xij) sao cho: phương án mới. nếu (i, j)  U Xây d ựng p hương án mới xij xij = xij + h nếu (i, j)  U+ + Gọi ô (r, s) là ô sao cho crs < 0, bé nhất, tìm một chu trình U qua ô (r, s) và tập hợp T các ô chọn. xij  h nếu (i, j)  U + Đánh dấu +/ các ô trong U, bắt đầu là ô (r, s), Tiếp tục quá trình trên cho đến khi tìm được phân chia U = U+  U, với U+ là tập hợp các ô phương án tối ưu. mang dấu + và U là tập hợp các ô mang dấu  . 1 11 1 12 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH + V í dụ: Giải các bài toán vận tải + 130 140 120 160 ĐS: Phương án tối ưu ĐS: 30 60 50 40 20 18 22 25 180 60 0 120 0 Phương án tối ưu 70 0 0 100 1 5 7 2 5 0 0 40 45 15 25 30 15 0 140 0 60 170 25 5 50 0 Giá trị mục tiêu 5 7 4 9 0 55 0 0 80 45 30 40 35 fmin = 12690 200 Giá trị mục tiêu 12 2 3 6 fmin = 555 55 Lưu ý: + Với phương án suy biến ta bổ sung thêm các “ô chọn 0” để có m+n1 ô không tạo thành chu trình. 1 13 1 14 Chuongnn-hui.blogspot.com 19
QUY HOẠCH TUYẾN TÍNH 02/09/2012 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH + Trường hợp ai < bj hay cung nhỏ hơn cầu, ta + Trường hợp ai > bj hay cung lớn hơn cầu, ta bổ sung dòng phát giả Pm+1 với am+1= bj ‒ ai và bổ sung cột thu giả Tn+1 với bn+1= ai ‒ bj và cm+1j= 0 đối với các ô giả (m+ 1, j), j = 1,…,n. cin+1= 0 đối với các ô giả (i, n+ 1), i = 1,…,m. V í d ụ: Giải bài toán vận tải V í d ụ: Giải bài toán vận tải ĐS: ĐS: 65 45 50 30 100 65 95 Phương án tối ưu Phương án tối ưu 10 9 12 7 7 5 2 60 80 30 0 0 30 0 0 80 30 0 25 0 70 0 0 9 11 10 15 3 4 5 55 70 5 45 0 0 30 65 15 Giá trị tối ưu Giá trị tối ưu 8 7 14 12 9 2 7 fmin = 1385 fmin = 875 50 150 1 15 1 16 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH + Trường hợp có ô cấm, ta bỏ ô cấm và đưa vào đó + Trường hợp bài toán vận tải tìm max: cước phí M rất lớn và tiến hành làm bình thường. Nếu tìm phương án cực biên bằng ‘max’ cước ta ưu Phương án tối ưu không có giá trị trong ô cấm. tiên cho các ô có cước phí lớn nhất, bằng Vogel ta V í d ụ: Giải bài toán vận tải ưu tiên cho các ô có cước phí lớn nhất trên dòng hay cột có hiệu số cước phí lớn nhất của hai ô có ĐS: 100 65 95 40 cước phí lớn nhất rồi tiến hành làm bình thường. Phương án tối ưu 6 5 11 10 80 15 65 0 0 Dấu hiệu để phương án tối ưu là cij ≤ 0 với mọi i, j 0 0 30 40 sau khi quy 0 cước phí ô chọn. Nếu phương án 10 5 7 70 85 0 65 0 chưa tối ưu ta bổ sung ô (i, j) mà cij > 0 lớn nhất Giá trị tối ưu rồi điều chỉnh phương án bình thường. 9 8 7 fmin = 2065 150 1 17 1 18 Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Toán chuyên đề 4: QUY HOẠCH TUYẾN TÍNH Giải bài toán vận tải với EXCEL V í dụ: Giải bài toán vận tải tìm ‘max’ V ì bài toán vận tải cũng là bài toán quy hoạch 140 160 120 140 ĐS: tuyến tính nên ta cũng có thể sử dụng EXCEL để Phương án tối ưu 15 13 17 20 0 30 0 140 170 giải, chỉ có khác biệt ở cách trình bày dữ liệu trên 0 130 70 0 bảng tính. 10 20 25 10 140 0 50 0 200 Cài thêm công cụ Add-ins Solver Giá trị tối ưu fmax = 14890 Tương tự, trước hết ta phải cài thêm công cụ 40 25 35 30 190 Slover để gỉi bài toán. Tổ chức dữ liệu trên bảng tính Tiến hành nhập liệu trên bảng tính Excel như sau 1 19 1 20 Chuongnn-hui.blogspot.com 20