Giáo trình Quy hoạch tuyến tính - Chương 1: Bài toán quy hoạch tuyến tính

pháp vào giải một số bài toán cụ thể trong thực tế.  Giới thiệu 3 Nội dung của học phần:  Chương 1: Bài toán quy hoạch tuyến tính.  Chương 2: Bài toán đối ngẫu.  Chương 3: Bài toán vận tải. Giáo trình: [1] TS Nguyễn Phú Vinh, Giáo trình Quy hoạch tuyến tính, Trường ĐHCN TP.HCM. Tài liệu tham khảo: [1] GS. Đặng Hấn, Quy hoạch tuyến tính, ĐHKT TP.HCM. [2] GS. Phan Quốc Khánh, Quy hoạch tuyến tính, NXBGD 1998.  Giới thiệu 4 Tiêu chuẩn và hình thức đánh giá kết quả :  Dự lớp: Từ 80% số tiết trở lên.  Tiểu luận  Thi giữa kỳ  Thi kết thúc học phần Thang điểm: Theo học chế tín chỉ. Giảng viên phụ trách: Ths. NGUYỄN NGỌC CHƯƠNG ĐT: 0919307060 – Email: n2chuong@hotmail.com  Giới thiệu 5 Lịch giảng dạy học phần :  Giới thiệu Thứ tự Buổi giảng Nội dung giảng dạy Số tiết Người học/HSSV cần chuẩn bị Ghi chú 1 Chương 1: Bài toán quy hoạch tuyến tính 1.1 Một số ví dụ 1.2 Định nghĩa và phân loại 4 2 1.3 Phương án cực biên 4 3 1.4 Phương pháp đơn hình giải bài toán dạng chính tắc tìm min 4 4 1.5 Phương pháp đơn hình mở rộng giải bài toán dạng chính tắc 4 5 Chương 2: Bài toán đối ngẫu 2.1 Định nghĩa bài toán đối ngẫu 2.2 Quan hệ giữa bài toán đối ngẫu và bài toán gốc. Kiểm tra giữa kỳ 4 6 Lịch giảng dạy học phần :  Giới thiệu Thứ tự Buổi giảng Nội dung giảng dạy Số tiết Người học/HSSV cần chuẩn bị Ghi chú 6 2.4 Giải bài toán đối ngẫu 4 7 Chương 3: Bài toán vận tải 3.1 Một số khái niệm 3.2 Tìm phương án cực biên ban đầu 4 8 3.2 Giải bài toán vận tải cân bằng thu phát 2 9 Thi kết thúc học phần 4 7  Bài toán quy hoạch tuyến tính 1.1 Một số ví dụ Một xí nghiệp sản xuất n loại sản phẩm Sj, j=1,2,,n sử dụng m loại nguyên liệu Ni, i=1,2,,m. Muốn sản suất 1 đơn vị sản phẩm loại Sj cần phải sử dụng aij đơn vị nguyên liệu Ni, i=1,2,m, j=1,2,,n. Số lượng nguyên liệu Ni tối đa mà xí nghiệp hiện có là bi, i=1,2,,m. Giá bán 1 đơn vị sản phẩm Sj là cj. Hãy lập kế hoạch sản xuất sao cho xí nghiệp đạt doanh thu lớn nhất. 1.1.1 Bài toán lập kế hoạch sản xuất 8  Bài toán quy hoạch tuyến tính Sản phẩm Nguyên liệu S1 S2 Sn Lượng nguyên liệu tối đa N1 a11 a12 a1n b1 N2 a21 a22 a2n b2 Nm am1 am2 amn bm Đơn giá c1 c2 cn Ta trình bày dữ liệu của bài toán đã cho bởi bảng sau: 9  Bài toán quy hoạch tuyến tính Bài toán trên gọi là bài toán quy hoạch tuyến tính. Mô hình toán học của bải toán là: Tìm x = (x1, x2, , xn) sao cho f = cjxj  max với các điều kiện ràng buộc sau đây aijxj  bi, i=1,2,,m. xj  0, j=1,2,,n. Ngoài ra do lượng nguyên liệu của mỗi loại Ni, i=1,2,,m. là hạn chế nên ta có: ai1x1 + ai2x2 + + ainxn  bi hay aijxj  bi , i=1,2,,m. Gọi xj là lượng sản phẩm Sj, j=1,2,,n cần sản xuất, xj  0. Doanh thu của xí nghiệp là: f = c1x1 + c2x2 + + cnxn hay f = cjxj , j=1,2,,n 10  Bài toán quy hoạch tuyến tính Một xí nghiệp xử lý rác thải có n phân xưởng Sj, j=1,2,,n xử lý m loại rác thải Ni, i=1,2,,m. Nếu cùng đầu tư một đơn vị vốn vào các phân xưởng thì cuối năm mỗi phân xưởng Sj có thể xử lý aij đơn vị rác thải Ni, i=1,2,m, j=1,2,,n. Ngoài ra theo hợp đồng lao động thì cuối năm số lượng rác thải Ni tối thiểu mà xí nghiệp cần phải xử lý là bi , i=1,2,,m. Hãy lập kế hoạch đầu tư sao cho tổng vốn đầu tư của xí nghiệp nhỏ nhất mà vẫn đảm bảo hoàn thành hợp đồng lao động. 1.1.2 Bài toán vốn đầu tư 11  Bài toán quy hoạch tuyến tính Phân xưởng Loại rác thải S1 S2 Sn Lượng rác xử lý tối thiểu N1 a11 a12 a1n b1 N2 a21 a22 a2n b2 Nm am1 am2 amn bn Ta trình bày dữ liệu của bài toán đã cho bởi bảng sau: 12  Bài toán quy hoạch tuyến tính Bài toán trên cũng là bài toán quy hoạch tuyến tính. Mô hình toán học của bải toán là: Tìm x = (x1, x2, , xn) sao cho f = xj  min với các điều kiện ràng buộc sau đây aijxj  bi, i=1,2,,m. xj  0, j=1,2,,n. Ngoài ra theo hợp đồng lao động thì lượng rác thải loại Ni, i=1,2,,m. phải đảm bảo nên ta có: ai1x1 + ai2x2 + + ainxn  bi hay aijxj  bi , i=1,2,,m. Gọi xj là vốn đầu tư cho phân xưởng Sj, j=1,2,,n, xj  0. Tổng vốn đầu tư của xí nghiệp là: f = x1 + x2 + + xn hay f = xj , j=1,2,,n 13  Bài toán quy hoạch tuyến tính Cần vận chuyển hàng hoá từ m kho (điểm 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à bj, j=1,2,,n. Chi phí vận chuyển 1 đơ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. 1.1.3 Bài toán vận tải 14  Bài toán quy hoạch tuyến tính Điểm thu Điểm phát T1 : b1 T2 : b2 Tn : bn P1 : a1 c11 c12 c1n P2 : a2 c21 c22 c2n Pm : am cm1 cm2 cmn Ta trình bày dữ liệu của bài toán đã cho bởi bảng sau: Gọi xij là lượng hàng cần vận chuyển từ điểm phát Pi đến điểm thu Tj, xij  0. Tổng chi phí vận chuyển là: f = c11x11 + c12x12 + + cmnxmn hay f = cijxij 15  Bài toán quy hoạch tuyến tính Bài toán trên cũng là bài toán quy hoạch tuyến tính. Mô hình toán học của bải toán là: Tìm x = (x11, x12, , xmn) sao cho f = cijxij  min với các điều kiện ràng buộc sau đây xij = ai, i=1,2,,m. xij = bj, j=1,2,,n. xij  0, i=1,2,,m, j=1,2,,n. Lượng hàng vận chuyển từ kho Pi, i=1,2,,m: xi1 + xi2 + + xin = ai hay xij = ai , i=1,2,,m. Lượng hàng vận chuyển đến nơi tiêu thụ Tj, j=1,2,,n: x1j + x2j + + xmj = bj hay xij = bj , j=1,2,,n. Do lượng hàng phát ra bằng lượng hàng thu vào nên ta có: ai = bj , i=1,2,,m, j=1,2,,n 16  Bài toán quy hoạch tuyến tính 1.2 Định nghĩa và phân loại 1.2.1 Bài toán quy hoạch tuyến tính tổng quát Tìm x = (x1, x2, , xn) sao cho f =  cjxj  max(min) (1) với các điều kiện ràng buộc sau đây aijxj  bi, i  I1. (2) aijxj  bi, i  I2. (3) aijxj = bi, i  I3. (4) xj  0, j  J1. (5) xj  0, j  J2. (6) xj  R, j  J3. (7) Bài toán quy hoạch tuyến tính tổng quát là bài toán có dạng: trong đó I1I2I3={1,2,,m}, I1I2I3= và J1J2J3={1,2,,n}, J1J2J3= 17  Bài toán quy hoạch tuyến tính VD1: Xét bài toán quy hoạch tuyến tính f = 3x1 + x2 – 2x3 – x4 + 4x5 – 2x6  max x1 + 2x2 – x3 + x4 + x5  8 x1– 3x3 – x4 + 3x6  2 2x1 + 3x2 + x3 – x4 = 5 – x1 + x2 – x3 + 2x4 – 3x5  6 3x1+ 2x2 – 2x3 – x4 – 2x6  11 x1, x4  0 x2, x3, x6  0 x5 R thì I1={1, 5}, I2={2, 4}, I3={3} và J1={1, 4}, J2={2, 3, 6}, J3={5} 18  Bài toán quy hoạch tuyến tính 1.2.2 Một số khái niệm Phương án: vectơ x = (x1, x2, , xn) thoả mãn các điều kiện ràng buộc từ (2) đến (7). Giải bài toán quy hoạch tuyến tính: là tìm phương án tối ưu cho bài toán. Phương án tối ưu: phương án làm cho hàm mục tiêu đạt max hay min nghĩa là thoả mãn (1). Tập phương án tối ưu: tập hợp tất cả các phương án của bài toán. Hàm mục tiêu: hàm f =  cjxj. 19  Bài toán quy hoạch tuyến tính 1.2.3 Dạng chính tắc của bài toán quy hoạch tuyến tính Mọi bài toán quy hoạch tuyến tính đều có thể biến đổi đưa về dạng chính tắc. Bài toán quy hoạch tuyến tính có dạng chính tắc như sau: Tìm x = (x1, x2, , xn) sao cho f =  cjxj  max (min) với các điều kiện ràng buộc sau đây aijxj = bi, i=1,2,,m. xj  0, j=1,2,,n. hay Tìm x = (x1, x2, , xn) sao cho f = c, x  max (min) với các điều kiện ràng buộc sau đây Ax = b x  0 với A = (aij), x = (x1, x2, , xn)T, b = (b1, b2, , bm)T và x  0 nghĩa là xj  0, j=1,2,,n. 20  Bài toán quy hoạch tuyến tính VD2: Bài toán quy hoạch tuyến tính dạng chính tắc f = x1 + 2x2 – x3 – 3x4  max 2x1 + 3x2 + x3 – x4 = 5 x1 + 2x2 – x3 + x4 = 9 x1 – x2 – x3 + 3x4 = 7 xj  0, j=1,2,3,4 f = 2x1 – x2 + 3x3 + x4 – x5  min x1 + x2 + 2x3 – x4 + 2x5 = 12 – x1 + x2 – x3 + 2x4 – x5 = 8 3x1+ 2x2 – 2x3 – x4 + x5 = 11 x1 – 2x2 – x3 + 3x4 + 3x5 = 6 xj  0, j=1,2,3,4,5 21  Bài toán quy hoạch tuyến tính Để biến đổi bài toán về dạng chính tắc tìm min ta thực hiện như sau: Thay hàm mục tiêu f  max bởi hàm mục tiêu g =  f, khi đó ta có g  min. Từ ràng buộc aijxj  bi bổ sung thêm biến xn+i  0 để có ràng buộc aijxj + xn+i = bi. Từ ràng buộc aijxj  bi bổ sung thêm biến xn+i  0 để có ràng buộc aijxj  xn+i = bi. Thay biến xj  0 bởi biến xj =  xj  0 Thay biến xj  R bởi xj  xj = xj với xj , xj  0 22  Bài toán quy hoạch tuyến tính VD3: Biến đổi bài toán sau về dạng chính tắc tìm min f = x1 – 3x2 + 2x3 – x4  max 2x1 + x2 + x3 – x4  8 x1 – x3 + x4 = 5 x1 – 2x2 – x3 + 3x4  7 x1, x3  0 x2  0 x4  R Thay hàm mục tiêu f bởi hàm mục tiêu g = – f Bổ sung biến x5, x6  0 vào các ràng buộc thứ 1 và 3. Thay biến x2 bởi biến x7 = – x2  0. Thay biến x4 bởi biến x8 – x9 với x8, x9  0. 23  Bài toán quy hoạch tuyến tính Ta có bài toán dạng chính tắc tìm min sau đây g = – x1 – 2x3 – 3x7 + x8 – x9 min 2x1 + x3 + x5 – x7 – x8 + x9 = 8 x1 – x3 + x8 – x9 = 5 x1 – x3– x6 + 2x7 + 3x8 – 3x9= 7 xj  0, j=1,2,,9 VD4: Biến đổi bài toán sau về dạng chính tắc tìm min f = 2x1 – x2 + x3 – 3x4  min x1 + 2x2 + 2x3 – x4  6 2x1 – x2 – 2x3 + x4 = 9 3x1 –x2 + x3 + 2x4  12 x2, x4  0 x1  0 x3  R 24  Bài toán quy hoạch tuyến tính f = – x2 – 3x4 – 2x7 + x8 – x9  min 2x2– x4 – x5 – x7 + 2x8 – 2x9 = 6 – x2 + x4 – 2x7 – 2x8 + 2x9 = 9 –x2 + 2x4 + x6 – 3x7 + x8 – x9 = 12 xj  0, j=1,2,,9 Bổ sung biến x5, x6  0 vào các ràng buộc thứ 1 và 3. Thay biến x1 bởi biến x7 = – x1  0. Thay biến x3 bởi biến x8 – x9 với x8, x9  0. Ta có bài toán dạng chính tắc tìm min sau đây