Bài giảng Quy hoạch tuyến tính

1  Bài toán vận tải 3.1 Bài toán vận tải Ta gọi vectơ 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. 2  Bài toán vận tải 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 Lượng hàng vận chuyển đi 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 3  Bài toán vận tải Bài toán vận tải là bài toán quy hoạch tuyến tính nên ta cũng có thể giải bằng phương pháp đơn hì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. trong đó ai = bj (điều kiện cân bằng thu phát) Ta trình bày dưới dạng bảng sau còn gọi là bảng vận tải: 4  Bài toán vận tải Thu Phát b1 b2 … bn a1 c11 x11 c12 x12 … c1n x1n a2 c21 x21 c22 x22 … c2n x2n … … … … … am cm1 xm1 cm2 xm2 … cmn xmn 5  Bài toán vận tải 3.2 Một số khái niệm Ta gọi vectơ  Ô (i, j) là ô nằm trên dòng i, cột j cho ta xác định lượng hàng cũng như cước phí vận chuyển một đơn vị hàng từ Pi đến Tj. Ô chọn là ô (i, j) mà xij > 0, ô loại là ô (i, j) mà xij = 0.  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 dòng hoặc cột.  Chu trình là một dây chuyền khép kín. Số các ô 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. Với m + n  1 ô không tạo thành chu trình ta có thể bổ sung thêm một ô bất kỳ để có ít nhất một chu trình. Xét bảng vận tải m  n. 6  Bài toán vận tải Ta gọi vectơ             Dây chuyền Không là dây chuyền                 Một số chu trình thường gặp 7  Bài toán vận tải Ta gọi vectơ  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 án hay ma trận phương án là ma trận (xij) với xij là lượng hàng cần vận chuyển từ Pi đến Tj. Một phương án cực biên là phương án có số ô chọn tương ứng không tạo thành chu trình tối đa là m + n  1, nếu 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 phương án cực biên 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. 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. 8  Bài toán vận tải 3.3 Tìm phương án cực biên ban đầu Ta gọi vectơ  Tìm ô có cước phí bé nhất, phân phối lượng hàng tối đa có thể vào ô đó.  Loại bỏ dòng hay cột đã phân phối đủ hàng, tiếp tục quá trình cho đến khi phân phối hết hàng. 3.3.1 Phương pháp “min” cước VD29: Tìm phương án cực biên ban đầu 30 60 50 40 45 1 5 7 2 80 5 7 4 9 55 12 2 3 6 9  Bài toán vận tải Ta gọi vectơ VD30: Tìm phương án cực biên ban đầu 130 140 120 160 180 20 18 22 25 170 15 25 30 15 200 45 30 40 35 30 60 50 40 45 1 30 5 7 2 15 80 5 7 5 4 50 9 25 55 12 2 55 3 6 Phương án cực biên 30 0 0 15 x = 0 5 50 25 0 55 0 0 Giá trị mục tiêu f = 630 10  Bài toán vận tải Ta gọi vectơ 130 140 120 160 180 20 18 140 22 40 25 170 15 130 25 30 15 40 200 45 30 40 80 35 120  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. 3.3.2 Phương pháp Vogel Phương án cực biên 0 140 40 0 x = 130 0 0 40 0 0 80 120 Giá trị mục tiêu f = 13350 11  Bài toán vận tải Ta gọi vectơ  Loại bỏ dòng hay cột đã phân phối đủ hàng 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. VD31: Tìm phương án cực biên ban đầu 30 60 50 40 45 1 5 7 2 80 5 7 4 9 55 12 2 3 6  Trên dòng hay cột có hiệu số lớn nhất tìm ô có cước phí bé nhất và phân phối lượng hàng tối đa vào đó. 12  Bài toán vận tải Ta gọi vectơ 30 60 50 40 45 1 30 5 7 2 15 1 3 80 5 7 5 4 50 9 25 1 3 55 12 2 55 3 6 1 1  3  1 1  3 VD32: Tìm phương án cực biên ban đầu 130 140 120 160 180 20 18 22 25 170 15 25 30 15 200 45 30 40 35 Phương án cực biên 30 0 0 15 x = 0 5 50 25 0 55 0 0 Giá trị mục tiêu f = 630 13  Bài toán vận tải Ta gọi vectơ 130 140 120 160 180 20 120 18 22 60 25 2 2 4 170 15 10 25 30 15 160 0 10 200 45 30 140 40 60 35 5 10 10 5 25 7 12 8 18 10 Phương án cực biên 120 0 60 0 x = 10 0 0 160 0 140 60 0 Giá trị mục tiêu f = 12870 Lưu ý: Ngoài hai phương pháp nêu trên còn có phương pháp góc Tây –Bắc tuy nhiên phương pháp này ít hiệu quả, nó chỉ thuận tiện khi lập trình trên máy tính. 14  Bài toán vận tải 3.4 Giải bài toán vận tải Ta gọi vectơ  Tìm phương án cực biên không suy biến ban đầu.  Đánh giá phương án hiện có – Thuật toán quy 0 cước phí ô chọn + Xây dựng hệ thống thế vị ui và vj trên các dòng i và các cột j sao cho với các ô chọn (i, j) ta có ui + vj = cij. + Biến đổi ma trận cước phí (cij) thành ma trận cước phí mới (cij) sao cho với các ô chọn cij = cij  (ui + vj). + Nếu trong ma trận cước phí mới (cij) ta có cij  0 với mọi i, j thì phương án đang xét là phương án tối ưu, trong trường hợp trái lại ta chuyển sang xây dựng phương án mới. 15  Bài toán vận tải Ta gọi vectơ  Xây dựng phương án mới + 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. + Đánh dấu +/ các ô trong U, bắt đầu là ô (r, s), phân chia U = U+  U, với U+ là tập hợp các ô mang dấu + và U là tập hợp các ô mang dấu  . + Gọi h = min{xij  (i, j)  U}, biến đổi ma trận phương án (xij) thành ma trận phương án mới (xij) sao cho: xij nếu (i, j)  U xij = xij + h nếu (i, j)  U+ xij  h nếu (i, j)  U Tiếp tục quá trình cho đến khi tìm được phương án tối ưu 16  Bài toán vận tải Ta gọi vectơ VD33: Giải bài toán vận tải 30 60 50 40 45 1 5 7 2 80 5 7 4 9 55 12 2 3 6 Dùng phương pháp min cước ta có phương án cực biên ban đầu 1 30 5 7 2 15 5 7 5 4 50 9 25 12 2 55 3 6 30 0 0 15 x = 0 5 50 25 0 55 0 0 Giá trị mục tiêu f = 630 17  Bài toán vận tải Ta gọi vectơ Biến đổi ma trận cước phí 1 30 5 7 2 15 u1 = 1 5 7 5 4 50 9 25 u2 = 8 12 2 55 3 6 u3 = 3 v1 = 0 v2 = 1 v3 = 4 v4 = 1 Xây dựng hệ thống thế vị 0 30 5 10 0 15 3 0 5 0 50 0 25 9 0 55 4 2 +  +  Phương án đang xét chưa tối ưu vì còn c21 = 3 < 0 18  Bài toán vận tải Ta gọi vectơ Biến đổi ma trận cước phí Biến đổi ma trận phương án. Xây dựng hệ thống thế vị Phương án mới là phương án tối ưu vì ta có cij  0 với mọi i, j. 0 5 2 7 0 40 0 25 0 5 0 50 3 12 0 55 4 5 0 5 5 10 0 40 u1 = 0 3 25 0 5 0 50 0 u2 = 3 9 0 55 4 2 u3 = 3 v1 = 0 v2 = 3 v3 = 3 v4 = 0 Phương án mới 5 0 0 40 x = 25 5 50 0 0 55 0 0 Giá trị mục tiêu f = 555 19  Bài toán vận tải Ta gọi vectơ VD34: Giải bài toán vận tải 130 140 120 160 180 20 18 22 25 170 15 25 30 15 200 45 30 40 35 Dùng phương pháp min cước ta có phương án cực biên ban đầu 0 140 40 0 x = 130 0 0 40 0 0 80 120 Giá trị mục tiêu f = 13350 20 18 140 22 40 25 15 130 25 30 15 40 45 30 40 80 35 120 20  Bài toán vận tải Ta gọi vectơ Biến đổi ma trận cước phí 20 18 140 22 40 25 u1 = 17 15 130 25 30 15 40 u2 = 15 45 30 40 80 35 120 u3 = 35 v1 = 0 v2 = 1 v3 = 5 v4 = 0 Xây dựng hệ thống thế vị 3 0 140 0 40 8 0 130 9 10 0 40 10 -6 0 80 0 120 + Phương án đang xét chưa tối ưu vì còn c32 = 6 < 0 +   21  Bài toán vận tải Ta gọi vectơ Biến đổi ma trận cước phí Biến đổi ma trận phương án. Xây dựng hệ thống thế vị Phương án đang xét chưa tối ưu vì còn c11 = 3 < 0 -3 0 60 0 120 2 0 130 15 16 0 40 10 0 80 6 0 120 3 0 60 0 120 8 u1 = 6 0 130 9 10 0 40 u2 = 0 10 -6 80 0 0 120 u3 = 0 v1 = 0 v2 = -6 v3 = -6 v4 = 0 Phương án mới 0 60 120 0 x = 130 0 0 40 0 80 0 120 Giá trị mục tiêu f = 12870 + + +    22  Bài toán vận tải Ta gọi vectơ Biến đổi ma trận cước phí Biến đổi ma trận phương án. Xây dựng hệ thống thế vị Phương án mới là phương án tối ưu vì ta có cij  0 với mọi i, j. 0 60 3 0 120 5 0 70 15 13 0 100 10 0 140 3 0 60 -3 60 0 0 120 2 u1 = -3 0 70 15 16 0 100 u2 = 0 10 0 140 6 0 60 u3 = 0 v1 = 0 v2 = 0 v3 = 3 v4 = 0 Phương án mới 60 0 120 0 x = 70 0 0 100 0 140 0 60 Giá trị mục tiêu f = 12690