Bài giảng Tối ưu hóa - Chương 3: Bài toán vận tải

BÀI TOÁN QUY HOẠCH TUYẾN TÍNHTHIẾT LẬP MÔ HÌNH BÀI TOÁN (Xem)CÁC DẠNG CỦA BÀI TOÁN QUY HOẠCH TUYẾN TÍNH (Xem)CÁC KHÁI NIỆM CƠ BẢN VỀ BÀI TOÁN QUY HOẠCH TUYẾN TÍNH (Xem)CÁC PHƯƠNG PHÁP GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH (Xem)BÀI TẬP (Xem)CHƯƠNG 1MỘT VÀI VÍ DỤ VỀ BÀI TOÁN QHTTVí dụ 1.1. BÀI TOÁN LẬP KẾ HOẠCH SẢN XUẤTMột xí nghiệp dùng 3 loại nguyên liệu: N1; N2; N3 để sản xuất ra một loại sản phẩm theo 3 phương pháp khác nhau: PP1; PP2; PP3. Định mức nguyên liệu và số lượng sản phẩm sản xuất ra trong 1 giờ được cho ở bảng sau:Hãy lập mô hình bài toán sao cho xí nghiệp sản xuất ra nhiều sản phẩm nhất?NguyeânLieäuSoá löôïnghieän coù (ñv)Ñònh möùc nguyeân lieäuPP1PP2PP3N1250453N2350241N3450364Soá saûn phaåm (sp/giôø)10129MỘT VÀI VÍ DỤ VỀ BÀI TOÁN QHTTGọi x1, x2, x3 lần lượt là thời gian sản xuất ra sản phẩm theo 3 phương pháp PP1, PP2, PP3.Tổng sản phẩm sản xuất (cần làm cực đại)f(x) = 10x1 + 12x2 + 9x3  maxDo xí nghiệp chỉ có 250 nguyên liệu N1 nên x1, x2, x3 phải thỏa mãn 4x1 + 5x2 + 3x3 ≤ 250Tương tự cho các nguyên liệu N2, N3 ta có 2x1 + 4x2 + x3 ≤ 350 và 3x1 + 6x2 + 4x3 ≤ 450Dĩ nhiên ta phải có x1, x2, x3 không âmMỘT VÀI VÍ DỤ VỀ BÀI TOÁN QHTTVậy mô hình bài toán được phát biểu như sau:Tìm các biến x1, x2, x3 sao chof(x)= 10x1 + 12x2 + 9x3  max, thỏa các điều kiện4x1 + 5x2 + 3x3 ≤ 250 2x1 + 4x2 + x3 ≤ 350 3x1 + 6x2 + 4x3 ≤ 450x1  0 x2  0 x3  0MỘT VÀI VÍ DỤ VỀ BÀI TOÁN QHTTVí dụ 1.2. BÀI TOÁN PHA CẮT VẬT LIỆUMột xí nghiệp may mặc cần sản xuất đúng 2.000 quần và ít nhất 1.000 áo. Mỗi tấm vải có 6 cách cắt như sau:Hãy tìm phương án cắt quần áo sao cho tổng số tấm vải là ít nhất?Caùch caétQuaànAÙo190352805537070460905120060100MỘT VÀI VÍ DỤ VỀ BÀI TOÁN QHTTGọi xj (j = 1, 2, ..., 6) là số tấm vải được cắt theo cách thứ j.Tổng số tấm vải dùng để sản xuất (cần làm cực tiểu) là f(x) = x1 + x2 + x3 + x4 + x5 + x6  minDo xí nghiệp cần sản xuất đúng 2.000 quần nên các xj phải thỏa mãn 90x1 + 80x2 + 70x3 + 60x4 + 120x5 = 2000Tương tự cho điều kiện về sản xuất áo, ta có35x1 + 55x2 + 70x3 + 90x4 + 100x6  1000Dĩ nhiên ta phải có xj (j = 1, 2, ..., 6) không âmMỘT VÀI VÍ DỤ VỀ BÀI TOÁN QHTTVậy mô hình bài toán được phát biểu như sau:Tìm các biến xj (j = 1, 2, ..., 6) sao chof(x)= xj  min, thỏa các điều kiện90x1 + 80x2 + 70x3 + 60x4 + 120x5 = 200035x1 + 55x2 + 70x3 + 90x4 + 100x6  1000xj  0, (j = 1, 2, ..., 6).MỘT VÀI VÍ DỤ VỀ BÀI TOÁN QHTTVí dụ 1.3. BÀI TOÁN XÁC ĐỊNH KHẨU PHẦNĐể nuôi một loại gia súc có hiệu quả, mỗi ngày cần phải có khối lượng tối thiểu 700 gram protit, 300 gram glucit, khoáng 4200 gram. Tỷ lệ (%) theo khối lượng các chất trên có trong các loại thức ăn A, B, C như sau:Giá 1gram thức ăn A, B tương ứng là 40 đồng, 60 đồng. Hãy lập mô hình bài toán xác định khối lượng thức ăn cần thiết sao cho chi phí nuôi gia súc là thấp nhất? Thöùc aênChaát dinh döôõng (%)ProtitGlucitKhoaùngA117B216MỘT VÀI VÍ DỤ VỀ BÀI TOÁN QHTTGọi xj (j = 1, 2) là số gram thức ăn A, B cần mua mỗi ngày.Tổng chi phí dùng để mua thức ăn (cần làm cực tiểu) là f(x) = 40x1 + 60x2  min (đồng)Do các tỷ lệ các chất protit, glucit và khoáng có trong thức ăn A nên các xj phải thỏa mãn x1 + 2x2  700Tương tự cho điều kiện của thức ăn B và C, ta cóx1+x2 300 và 7x1+6x24200 MỘT VÀI VÍ DỤ VỀ BÀI TOÁN QHTTVậy mô hình bài toán được phát biểu như sau:Tìm các biến xj (j = 1, 2) sao chof(x) = 40x1 + 60x2  min , thỏa các điều kiệnx1 + 2x2  700x1+x2 300 7x1+6x24200 xj  0, (j = 1, 2, 3).CÁC DẠNG CỦA BÀI TOÁN QHTT2.1. DẠNG TỔNG QUÁTTìm x = (x1, x2,..., xn) sao cho:(2.1) gọi là hàm mục tiêu. (2.2) gọi là hệ ràng buộc. (2.3) gọi là ràng buộc về dấu của ẩn số.Ví dụ 1.1, Ví dụ 1.2 và Ví dụ 1.3 là các bài toán QHTT có dạng tổng quát. CÁC DẠNG CỦA BÀI TOÁN QHTTMột vectơ x = (x1, x2,..., xn) thỏa mãn điều kiện (2) và (3) được gọi là một phương án (P.A) của bài toán quy hoạch tuyến tính (QHTT).Tập các P.A của bài toán được gọi là miền ràng buộc hay miền xác định. Ký hiệu là D.Phương án tối ưu (P.A.T.Ư) hay nghiệm của bài toán, ký hiệu là Xopt (optimality), nếu vectơ X là một P.A và hàm mục tiêu (2.1) bị chặn.CÁC DẠNG CỦA BÀI TOÁN QHTTBài toán được gọi là giải được hay có lời giải hay có nghiệm nếu nó có ít nhất một P.A.T.Ư.Bài toán không giải được hay vô nghiệm nếu D =  hay nó có P.A nhưng không có PA.T.Ư.CÁC DẠNG CỦA BÀI TOÁN QHTT2.2. DẠNG CHÍNH TẮCTìm x = (x1, x2,..., xn) sao cho:Nhận xét: Hệ ràng buộc của bài toán dạng chính tắc đều là các đẳng thức và mọi biến của bài toán đều không âm. Ví dụ BÀI TOÁN VẬN TẢI có dạng chính tắc.CÁC DẠNG CỦA BÀI TOÁN QHTT2.3. DẠNG CHUẨNTìm x = (x1, x2,..., xn) sao cho:Nhận xét: Bài toán dạng chuẩn là bài toán ở dạng chính tắc với hệ ràng buộc chứa ma trận con Im là ma trận đơn vị cấp m.Trong đó các xi (i = 1, 2,..., m) được gọi là ẩn cơ bản (A.C.B), còn các ẩn xi,m+k, (k = 0, 1,..., n – m) được gọi là ẩn không cơ bản.CÁC DẠNG CỦA BÀI TOÁN QHTT2.4. CHUYỂN ĐỔI DẠNG BÀI TOÁN QHTT1) Nếu ràng buộc thứ i có dạng aijxj ≤ bi thì thêm vào một ẩn phụ xn+1  0, sao cho aijxj + xn+1 = bi.2) Nếu ràng buộc thứ i có dạng aijxj  bi thì thêm vào một ẩn phụ xn+1  0, sao cho aijxj – xn+1 = bi.3) Nếu ẩn xj ≤ 0 thì được thay bằng x/j = – xj  0.4) Nếu ẩn xj không ràng buộc về dấu thì thay xj bằng hai ẩn phụ x/j và x//j sao cho xj = x/j – x//j, với x/j  0, x//j  0.CÁC DẠNG CỦA BÀI TOÁN QHTTĐể bài toán gọn hơn, chúng ta dùng các ký hiệuTrong đó A là ma trận mn gồm các hệ số ở vế trái của hệ ràng buộc; Aj là vectơ cột thứ j của ma trận A; b là vectơ hệ số ở vế phải của hệ ràng buộc; c là vectơ hệ số ở hàm mục tiêu; x là vectơ ẩn số; 0 là vectơ không.CÁC DẠNG CỦA BÀI TOÁN QHTTKhi đó bài toán QHTT ở dạng chính tắc có dạngf(x) = cTx  min (hay max) Ax = b, x  0CÁC DẠNG CỦA BÀI TOÁN QHTTVí dụ 1.5. Đưa bài toán QHTT sau đây về dạng chính tắc và viết bài toán chính tắc dưới dạng ma trậnThêm 2 ẩn phụ x4, x5  0 vào ràng buộc thứ nhất và ràng buộc thứ ba.Thay x/3 = –x3  0Thay x2 = x/2 –x//2  0, với x/2, x//2  0CÁC DẠNG CỦA BÀI TOÁN QHTTBài toán QHTT có dạng chính tắc như sauBài toán QHTT dưới dạng ma trận như sauf(x) = (1, 3, – 3, 2, 0, 0)T(x1, x/2, x//2, x/3, x4, x5)  min (x1, x/2, x//2, x/3, x4, x5)  (0, 0, 0, 0, 0, 0)CÁC DẠNG CỦA BÀI TOÁN QHTTVí dụ 1.6. Cho bài toán QHTT:Ta có ma trận hệ số của hệ ràng buộc:chứa I3 nên bài toán quy hoạch tuyến tính trên có dạng chuẩn.Một phương án x* = (x1*, x2*,..., xn*) của bài toán QHTT dạng tổng quát là phương án cực biên (P.A.C.B) nếu x* = (x1*, x2*,..., xn*) thỏa mãn chặt n ràng buộc độc lập tuyến tính. Tức là:Trong đó A là ma trận con cấp n của hpt (*). Một P.A.C.B không suy biến là một P.A.C.B thỏa mãn đúng n ràng buộc chặt. Một P.A.C.B suy biến là một P.A.C.B thỏa mãn hơn n ràng buộc chặt.P.A.C.B còn được gọi là phương án cơ bản.ĐỊNH NGHĨA PHƯƠNG ÁN CỰC BIÊNVí dụ 1.7. Cho bài toán QHTTCác vectơ nào sau đây là phương án cực biên?ĐỊNH NGHĨA PHƯƠNG ÁN CỰC BIÊNº Dễ dàng kiểm tra X không phải là phương án. Y, Z là phương án của bài toán.º Y thỏa 2 ràng buộc chặt (2 ràng buộc về dấu) nên Y chỉ là P.A.º Z thỏa 3 ràng buộc chặt (ràng buộc 2, ràng buộc 3, ràng buộc 4) và Vậy Z là phương án cực biên của bài toán.ĐỊNH NGHĨA PHƯƠNG ÁN CỰC BIÊNĐỊNH LÝ 1. (TÍNH ĐẶC TRƯNG CỦA P.A.C.B)Một phương án X* = (x1*, x2*,, xn*) của bài toán QHTT dạng chính tắc là phương án cực biên nếu và chỉ nếu hệ vectơ cột Aj ứng với thành phần xj* > 0 là độc lập tuyến tính.Ví dụ 1.8. Cho bài toán QHTTCác vectơ nào sau đây X = (2, 2, 0), Y = (0, 0, 4), Z = (1, 1, 2), là P.A.C.B của bài toán. CÁC TÍNH CHẤT CỦA BÀI TOÁN QHTT X, Y, Z thỏa các ràng buộc nên chúng là P.A. Mặt khác ta có Với X = (2, 2, 0), nên X là P.A.C.B. Với Y = (0, 0, 4), hệ chỉ gồm một vectơ A3 nên Y cũng là P.A.C.B. Với Z=(1, 1, 2), ta thấy hệ {A1, A2, A3} phụ thuộc tuyến tính vì A1+A2–2A3=0 nên Z không là P.A.C.B.CÁC TÍNH CHẤT CỦA BÀI TOÁN QHTTHỆ QUẢ 1. (tính hữu hạn của P.A.C.B). Sốù phương án cực biên của bài toán QHTT dạng chính tắc là hữu hạn.HỆ QUẢ 2. Sốù thành phần dương trong mỗi phương án cực biên của bài toán quy hoạch tuyến tính dạng chính tắc tối đa bằng m (m là số dòng của ma tận A).CÁC TÍNH CHẤT CỦA BÀI TOÁN QHTTĐỊNH LÝ 2. (SỰ TỒN TẠI CỦA PHƯƠNG ÁN TỐI ƯU)Nếu bài toán quy hoạch tuyến tính có phương án và hàm mục tiêu bị chặn dưới (đối với f(x) min) hoặc hàm mục tiêu bị chặn trên (đối với f(x) max) trên tập các phương án thì bài toán có phương án tối ưu.ĐỊNH LÝ 3. (SỰ TỒN TẠI CỦA P.A.C.B. TỐI ƯU)Nếu bài toán QHTT dạng chính tắc có P.A.T.Ư thì bài toán có P.A.C.B tối ưu (P.A.C.B.T.Ư).CÁC TÍNH CHẤT CỦA BÀI TOÁN QHTTĐỊNH LÝ 4. (SỰ TỒN TẠI NHIỀU P.A.C.B.T.Ư)Nếu bài toán có P.A.T.Ư là Xopt và X(1), X(2) là 2 phương án khác nhau của bài toán thoả Xopt = X(1) + (1–)X(2), 0    1 thì X(1), X(2) là P.A.T.Ư.NHẬN XÉT Ta có thể tìm P.A.T.Ư của bài toán QHTT trong số các P.A.C.B của bài toán và có thể xác định ngay P.A.C.B của bài toán dạng chuẩn bằng cách cho các ẩn không cơ bản bằng không (xem Ví dụ 1.9). Trong bài toán QHTT dạng chính tắc. Nếu hạng của ma trận hệ số A là m thì P.A.C.B được gọi là không suy biến nếu nó có đúng m thành phần dương. Nếu P.A.C.B có ít hơn m thành phần dương thì được gọi là P.A.C.B suy biến (xem Ví dụ 1.10).CÁC TÍNH CHẤT CỦA BÀI TOÁN QHTTVí dụ 1.9 .Với bài toán quy hoạch tuyến tínhTa có phương án X = (1, 0, 3, 2, 0) là phương án cực biên của bài toán vì các ẩn x1, x3, x4 là các ẩn cơ bản của bài toán dạng chuẩn.CÁC TÍNH CHẤT CỦA BÀI TOÁN QHTTVí dụ 1.10 . Với bài toán quy hoạch tuyến tínhKiểm tra vectơ X = (11, 3, 0, 0) có phải là P.A.C.B? Kiểm tra trực tiếp, ta có X là P.A của bài toán. Hạng của ma trận hệ số của hệ ràng buộc tuyến tính bằng 3 và X có 2 thành phần dương là x1 =11, x2 = 3 nên X là P.A.C.B suy biến.CÁC TÍNH CHẤT CỦA BÀI TOÁN QHTTCÁC PHƯƠNG PHÁP GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH1. PHƯƠNG PHÁP HÌNH HỌC (Xem)2. PHƯƠNG PHÁP ĐƠN HÌNH (Xem)3. PHƯƠNG PHÁP ĐƠN HÌNH MỞ RỘNG  (BÀI TOÁN M) (Xem)ax+by=cPHƯƠNG PHÁP HÌNH HỌCXét bài toán QHTT có 2 biến.ax+by>cax+by 0 mà aij ≤ 0, i thì bài toán không có P.A.T.Ư. (xem Ví dụ 1.14) CƠ SỞ PHƯƠNG PHÁP ĐƠN HÌNH Dấu hiệu bài toán có P.A.C.B. khác tốt hơnĐịnh lý. Với một P.A.C.B, nếu j>0, i: aij > 0 thì bài toán có P.A.C.B khác tốt hơn P.A.C.B đang xét.CƠ SỞ PHƯƠNG PHÁP ĐƠN HÌNHBẢNG ĐƠN HÌNHj ≤ 0,j?THUẬT GIẢI ĐƠN HÌNHSaiĐúngSaiĐúngLẬP BẢNG ĐƠN HÌNHXÁC ĐỊNH PHƯƠNG ÁN MỚIAån vào: Aån ra: P.A.T.ƯKẾT THÚC THUẬT GIẢIaij ≤ 0,i?BÀI TOÁN KHÔNG CÓ P.A.T.ƯBIẾN ĐỔI BẢNG ĐƠN HÌNHSỐ BƯỚC LẶP LÀ HỮU HẠNTHUẬT GIẢI ĐƠN HÌNHThuật giải gồm 4 bước:Bước 1: Lập bảng đơn hìnhBài toán phải ở dạng chuẩn, đưa các số liệu vào bảng đơn hình.Bước 2: Kiểm tra tính tối ưu của bài toánTính j = ∑aijci(hệ số cơ sở) – cj  Nếu j ≤ 0: bài toán có P.A.T.U.  Nếu j > 0: chuyển sang bước 3.Bước 3: Kiểm tra tính giải được của bài toán  Nếu aij ≤ 0, i: bài toán không có P.A.T.U.  Nếu aij > 0: chuyển sang bước 4.THUẬT GIẢI ĐƠN HÌNHBước 4: Tìm P.A.C.B mới của bài toán  Chọn ẩn vào: Chọn Maxj (j > 0), ẩn xj sẽ được chọn đưa vào hệ ẩn cơ bản ứng với j đã được chọn.  Chọn ẩn ra: Chọn  = Min{bi/aij} (aij > 0), ẩn xi sẽ được chọn đưa ra khỏi hệ ẩn cơ bản ứng với  nhỏ nhất. Phần tử aij (ứng với ẩn vào xi và ẩn ra xj) được gọi là phần tử trục.  Dùng phương pháp biến đổi sơ cấp dòng trên ma trận hệ số để biến đổi ẩn mới đưa vào trở thành ẩn cơ bản. Sau đó quay về bước 2.THUẬT GIẢI ĐƠN HÌNHNHẬN XÉT. Dấu hiệu bài toán có nhiều P.A.T.Ư. Với P.A.C.B.T.Ư Xopt tìm được, nếu j = 0, mà xj không là P.A.C.B thì bài toán có P.A.C.B.T.Ư khác X/opt (xem Ví dụ 1.15).Tập phương án tối ưu: Trường hợp có hai P.A.C.B.T.Ư là Xopt và X/opt Topt = {Xopt + (1 – )X/opt, [0, 1]} Trường hợp có 3 P.A.C.B.T.Ư X(1)opt, X(2)opt, X(3)opt Topt = { X(1)opt + X(2)opt + X(3)opt, }, với , ,   0 và  +  +  = 1. Ví dụ 1.14. Giải bài toán quy hoạch tuyến tính THUẬT GIẢI ĐƠN HÌNH BT không có P.A.T.Ư vì 4= 1 > 0 mà ai4 0 vô cùng lớn (xem Ví dụ 1.19).CƠ SỞ THUẬT GIẢI ĐƠN HÌNH MỞ RỘNGĐúngSaiaij ≤ 0?SaiĐúngKhôngCóĐúngj ≤ 0?THUẬT GIẢI ĐƠN HÌNH MỞ RỘNGSaiLẬP BẢNG ĐƠN HÌNHXác định phương án mớiAån vào: Aån ra: CÓ P.A.T.ƯĐƯA BÀI TOÁN VỀ DẠNG CHUẨNKHÔNGCÓ P.A.T.ƯKẾT THÚC THUẬT GIẢICÓ P.A.T.ƯBIẾN ĐỔI BẢNG ĐƠN HÌNHKHÔNGCÓ P.A.T.ƯSỐ BƯỚC LẶP LÀ HỮU HẠNVí dụ 1.17. (trường hợp a). Giải bài toán QHTT Nhân (– 1) vào ràng buộc thứ nhất, bài toán có dạng chính tắc như sauTHUẬT GIẢI ĐƠN HÌNH MỞ RỘNGĐưa bài toán về dạng chuẩn:Thêm hai ẩn giả x4 ≥ 0 và x5 ≥ 0 vào lần lượt vào ràng buộc thứ nhất và thứ hai của bài toánBài toán có dạng chuẩn như sau:Ta có bảng đơn hình mở rộngTHUẬT GIẢI ĐƠN HÌNH MỞ RỘNG Bài toán có P.A.T.Ư Xopt=(5/2, 2, 0), f(Xopt)= –8. HỆSỐẨNC.BP.ATHUẬT GIẢI ĐƠN HÌNH MỞ RỘNGVí dụ 1.18. (trường hợp b). Giải bài toán QHTT Thêm ẩn phụ x4  0 vào ràng buộc thứ nhấtTHUẬT GIẢI ĐƠN HÌNH MỞ RỘNGThêm hai ẩn giả x5 ≥ 0, x6 ≥ 0 lần lượt vào ràng buộc thứ hai và ràng buộc thứ ba.Ta có bài toán dạng chuẩn như sauTa có bảng đơn hình mở rộngTHUẬT GIẢI ĐƠN HÌNH MỞ RỘNG HỆSỐẨNC.BP.ATHUẬT GIẢI ĐƠN HÌNH MỞ RỘNG P.A.T.Ư của BTM làvới ẩn giả x5 = 0 P.A.T.Ư của BT gốc là xopt = (0, 0, 8) và f(xopt) = 8.HỆSỐẨNC.BP.ATHUẬT GIẢI ĐƠN HÌNH MỞ RỘNGVí dụ 1.19. (trường hợp c). Giải bài toán QHTT Thêm 2 ẩn phụ x4, x5 ≥ 0 vào ràng buộc (1) & (2)THUẬT GIẢI ĐƠN HÌNH MỞ RỘNGThêm 2 ẩn giả vào x6, x7  0 lần lượt vào ràng buộc (1) & (3).Ta có bài toán dạng chuẩn như sauTa có bảng đơn hình mở rộngTHUẬT GIẢI ĐƠN HÌNH MỞ RỘNG P.A.T.Ư Xopt = (0, 0, 6, 0, 16, 0, 13), với x7 = 13  0 nên bài toán gốc không có P.A.T.Ư. HỆSỐẨNC.BP.ATHUẬT GIẢI ĐƠN HÌNH MỞ RỘNGBÀI TẬP CHƯƠNG 1LẬP MÔ HÌNH BÀI TOÁN[1] [2] [3] [4]BÀI TOÁN QHTT DẠNG CHÍNH TẮC[5a] [5b]XÁC ĐỊNH P.A – P.A.C.B VÀ P.A.T.Ư.[6] [7a] [7b] [7c]GIẢI BÀI TOÁN QHTT BẰNG PP HÌNH HỌC[8a] [8b] [8c]GIẢI BÀI TOÁN QHTT BẰNG PP ĐƠN HÌNH[9] [10] [11] [12] [13][14] [15] [16] [17]