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

 0, j=1,2,,n. với bi  0, i=1,2,,m và có sẵn ma trận đơn vị. 2  Bài toán quy hoạch tuyến tính  Tìm phương án cực biên ban đầu  0 0 0 01 2, ,..., mx x x x  Đánh giá phương án hiện có  Lập bảng đơn hình: Biến cơ sở Hệ số Phương án x1 x2 xn  c1 c2 cn x1 c1 z11 z12 z1n x2 c2 z21 z22 z2n xm cm zm1 zm2 zmn f(x0) 1 2 n 0 1x 0 2x 0 mx Trong đó: • zij là hệ số biểu diễn của Aj qua hệ vectơ cơ sở. 3  Bài toán quy hoạch tuyến tính • f(x0) là giá trị của hàm mục tiêu tại x0 0 0 0 0 0 1 1 2 2( ) m m i if x c x c x c x c x     Nếu với mọi k ta có k  0 thì phương án đang xét là phương án tối ưu. Ngược lại nếu tồn tại k > 0 với k nào đó thì phương án đang xét chưa tối ưu, ta tiến hành xây dựng phương án mới. • k là ước lượng của biến xk 1 1 2 2k k k m mk k i ik kc z c z c z c c z c         Xây dựng phương án mới – Phương pháp phần tử trục quay • Xác định cột quay s là cột mà s > 0 lớn nhất, biến cơ sở tương ứng xs là biến cơ sở đưa vào. 4  Bài toán quy hoạch tuyến tính • Phần tử quay zrs là phần tử giao giữa dòng quay r và cột quay s. • Dòng quay r là dòng mà r nhỏ nhất, biến cơ sở tương ứng xr là biến cơ sở đưa ra. 0 , 0kr ks ks x z z    • Xác định các thành phần phương án x1 mới. 1 1 1 1 i rs i i rs r is rs x i r z x x z x z i r z      Lưu ý nếu trên cột quay, các phần tử zks  0 thì ta không tìm được biến cơ sở đưa ra và khi đó bài toán không có lời giải. 5  Bài toán quy hoạch tuyến tính • Xác định các hệ số biểu diễn zij mới. ij rs ij ij rs rj is rs z i r z z z z z z i r z       VD15: Giải bài toán quy hoạch tuyến tính 1 2 4 5 6 1 4 5 6 2 4 6 3 4 5 6 2 2 3 min 2 12 2 4 3 9 0, 1,6j f x x x x x x x x x x x x x x x x x j                    6  Bài toán quy hoạch tuyến tính Phương án cực biên ban đầu x0 = (2, 12, 9, 0, 0, 0) Lập bảng đơn hình: Biến cơ sở Hệ số Phương án x1 x2 x3 x4 x5 x6  1 -1 0 -2 2 -3 x1 1 2 1 0 0 [1] 1 -1 (2) x2 -1 12 0 1 0 1 0 1 12 x3 0 9 0 0 1 2 4 3 9/2 Bảng 1 -10 0 0 0 (2) -1 1 7  Bài toán quy hoạch tuyến tính x4 -2 2 1 0 0 1 1 -1 x2 -1 10 -1 1 0 0 -1 2 5 x3 0 5 -2 0 1 0 2 [5] (1) Bảng 2 -14 -2 0 0 0 -3 (3) x4 -2 3 3/5 0 1/5 1 7/5 0 x2 -1 8 -1/5 1 -2/5 0 -9/5 0 x6 -3 1 -2/5 0 1/5 0 2/5 1 Bảng 3 -17 -4/5 0 -3/5 0 -21/5 0 Phương án tối ưu x* = (0, 8, 0, 3, 0, 1) Giá trị tối ưu fmin = f(x*) = 17 8  Bài toán quy hoạch tuyến tính VD16: Giải bài toán quy hoạch tuyến tính 1 2 3 4 5 6 1 2 5 1 2 3 6 2 3 4 2 4 0 0 min 3 4 2 3 4 3 0, 1,6.j f x x x x x x x x x x x x x x x x x j                     9  Bài toán quy hoạch tuyến tính Phương án cực biên ban đầu x0 = (0, 0, 0, 3, 4, 3) Lập bảng đơn hình: Biến cơ sở Hệ số Phương án x1 x2 x3 x4 x5 x6  -2 -4 1 -1 0 0 x5 0 4 1 (3) 0 0 1 0 [4/3] x6 0 3 2 1 -1 0 0 1 3 x4 -1 3 0 1 4 1 0 0 3 Bảng 1 -3 2 [3] -5 0 0 0 10  Bài toán quy hoạch tuyến tính x2 -4 4/3 1/3 1 0 0 1/3 0 4 x6 0 5/3 (5/3) 0 -1 0 -1/3 1 [1] x4 -1 5/3 -1/3 0 4 1 -1/3 0 Bảng 2 -7 [1] 0 -5 0 -1 0 x2 -4 1 0 1 1/5 0 2/5 -1/5 x1 -2 1 1 0 -3/5 0 -1/5 3/5 x4 -1 2 0 0 19/5 1 -2/5 1/5 Bảng 3 -8 0 0 -22/5 0 -4/5 -3/5 Phương án tối ưu x* = (1, 1, 0, 2, 0, 0) Giá trị tối ưu fmin = f(x*) = 8 11  Bài toán quy hoạch tuyến tính VD17: Giải bài toán quy hoạch tuyến tính Lưu ý: Trường hợp bài toán với bi  0, i=1,2,,m và không có sẵn ma trận đơn vị ta thực hiện biến đổi ma trận hệ số mở rộng của hệ điều kiện ràng buộc để có ma trận đơn vị. 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 3 3 min 2 2 2 6 3 3 9 6 0, 1,4.j f x x x x x x x x x x x x x x x x x j                     12  Bài toán quy hoạch tuyến tính Bài toán với bi  0, i=1,2,,m và không có sẵn ma trận đơn vị ta thực hiện biến đổi ma trận hệ số mở rộng: 2 2 1 3 3 1 2 1 2 1 1 2 1 2 1 1 2 2 6 3 3 9 0 10 5 1 5 1 1 1 1 6 0 3 2 2 4 d d d d d d                           2 3 2 1 1 2 3 3 2 3 2 3 1 2 1 1 2 1 0 3 15 12 0 1 1 7 7 0 1 1 7 7 0 3 2 2 4 0 0 5 23 25 d d d d d d d d d                              13  Bài toán quy hoạch tuyến tính Khi đó bài toán trở thành 1 2 3 4 1 4 2 4 3 4 3 3 min 6 5 3 12 5 2 23 5 5 0, 1,4.j f x x x x x x x x x x x j               3 3 1 1 3 2 2 3 1 35 1 0 3 15 12 1 0 0 6 5 3 0 1 1 7 7 0 1 0 12 5 2 0 0 1 235 5 0 0 1 235 5 d d d d d d d d                           14  Bài toán quy hoạch tuyến tính Phương án cực biên ban đầu x = (3, 2, 5, 0) Lập bảng đơn hình: Biến cơ sở Hệ số Phương án x1 x2 x3 x4  -3 1 3 -1 x1 -3 3 1 0 0 6/5 x2 1 2 0 1 0 -12/5 x3 3 5 0 0 1 -23/5 Bảng 1 8 0 0 0 -94/5 Phương án tối ưu x* = (3, 2, 5, 0) Giá trị tối ưu fmin = f(x*) = 8 15  Bài toán quy hoạch tuyến tính VD18: Giải bài toán quy hoạch tuyến tính 1 2 3 4 1 2 3 4 1 2 4 2 3 4 3 4 5 6 min 13 14 2 14 11 3 14 16 0, 1,4.j f x x x x x x x x x x x x x x x j                  2 2 12 1 1 1 13 14 1 1 1 13 14 2 1 0 14 11 0 1 2 12 17 0 3 1 14 16 0 3 1 14 16 d d d                      16  Bài toán quy hoạch tuyến tính 2 2 1 1 2 3 3 23 1 1 1 13 14 1 0 1 1 3 0 1 2 12 17 0 1 2 12 17 0 3 1 14 16 0 0 5 22 35 d d d d d d d d                          3 3 1 1 3 2 2 3 1 5 2 1 0 1 1 3 1 0 0 27 5 4 0 1 2 12 17 0 1 0 16 5 3 0 0 1 22 5 7 0 0 1 22 5 7 d d d d d d d d                        Khi đó bài toán trở thành 1 2 3 4 1 4 2 4 3 4 3 4 5 6 min 27 5 4 16 5 3 22 5 7 0, 1,4.j f x x x x x x x x x x x j              17  Bài toán quy hoạch tuyến tính Phương án cực biên ban đầu x = (4, 3, 7, 0) Lập bảng đơn hình: Biến cơ sở Hệ số Phương án x1 x2 x3 x4  3 -4 -5 6 x1 3 4 1 0 0 27/5 x2 -4 3 0 1 0 16/5 x3 -5 7 0 0 1 22/5 Bảng 1 -35 0 0 0 -93/5 Phương án tối ưu x* = (4, 3, 7, 0) Giá trị tối ưu fmin = f(x*) = 35 18  Bài toán quy hoạch tuyến tính 1.7 Phương pháp phạt và bài toán M Ta gọi vectơ Xét bài toán quy hoạch tuyến tính f = cjxj  min aijxj = bi, i=1,2,,m. xj  0, j=1,2,,n. với bi  0, i=1,2,,m và chưa có sẵn ma trận đơn vị. Ta đưa về bài toán sau đây gọi là bài toán M g = cjxj + Mxn+1 + Mxn+2 + + Mxn+m  min aijxj + xn+i = bi, i=1,2,,m. xj  0, j=1,2,,n+m. bằng cách bổ sung thêm m biến xn+i, i=1,2,,m để có được 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. 19  Bài toán quy hoạch tuyến tính Ta gọi vectơ Ta dùng thuật toán đơn hình để giải bài toán M với một vài lưu ý:  Nếu đã có k vectơ đơn vị thì ta bổ sung vào m – k biến để có ma trận đơn vị cấp m.  Hàm mục tiêu g, ước lượng k của các biến xk có thể viết g = A + BM, k = k + kM.  Nếu bài toán M có phương án tối ưu (x, t) với t > 0 ở đây t = (xn+1, , xn+m) thì bài toán chính không có phương án. Nếu bài toán M có phương án tối ưu (x, 0) thì x là phương án tối ưu của bài toán chính và nếu bài toán M không có phương án tối ưu thì bài toán chính cũng không có phương án tối ưu. 20  Bài toán quy hoạch tuyến tính Ta gọi vectơ Để so sánh các ước lượng ta có 0 0 0, 0 k k k k          và , i j i j i j i j              VD19: Giải bài toán quy hoạch tuyến tính 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 3 3 min 2 2 2 6 3 3 9 6 0, 1,4.j f x x x x x x x x x x x x x x x x x j                     21  Bài toán quy hoạch tuyến tính Ta gọi vectơ Bằng cách bổ sung thêm 3 biến x5, x6, x7 và xét hàm mục tiêu g = 3x1 + x2 + 3x3 x4 + Mx5+ Mx6+ Mx7, ta đưa về bài toán M: 1 2 3 4 5 6 7 1 2 3 4 5 1 2 3 4 6 1 2 3 4 7 3 3 min 2 2 2 6 3 3 9 6 0, 1,7.j g x x x x Mx Mx Mx x x x x x x x x x x x x x x x x j                           Phương án cực biên ban đầu x = (0, 0, 0, 0, 2, 9, 6) Lập bảng đơn hình: 22  Bài toán quy hoạch tuyến tính Ta gọi vectơ Biến cơ sở Hệ số Phương án x1 x2 x3 x4 x5 x6 x7  -3 1 3 -1 M M M x5 M 2 [1] 2 -1 1 1 0 0 (2) x6 M 9 2 -6 3 3 0 1 0 9/2 x7 M 6 1 -1 1 -1 0 0 1 6 Bảng 1 17 (4) -5 3 3 0 0 0 0 3 -1 -3 1 0 0 0 x1 -3 2 1 2 -1 1 0 0 x6 M 5 0 -10 [5] 1 1 0 (1) x7 M 4 0 -3 2 -2 0 1 2 Bảng 2 9 0 -13 (7) -1 0 0 -6 0 -7 0 -2 0 0 23  Bài toán quy hoạch tuyến tính Ta gọi vectơ x1 -3 3 1 0 0 6/5 0 x3 3 1 0 -2 1 1/5 0 x7 M 2 0 [1] 0 -12/5 1 (2) Bảng 3 2 0 (1) 0 -12/5 0 -6 0 -7 0 -2 0 x1 -3 3 1 0 0 6/5 x3 3 5 0 0 1 -23/5 x2 1 2 0 1 0 -12/5 Bảng 4 0 0 0 0 0 8 0 0 0 -94/5 Phương án tối ưu x* = (3, 2, 5, 0) Giá trị tối ưu fmin = f(x*) = 8 24  Bài toán quy hoạch tuyến tính Ta gọi vectơ VD20: Giải bài toán quy hoạch tuyến tính 1 2 3 4 1 2 3 4 1 2 4 2 3 4 3 4 5 6 min 13 14 2 14 11 3 14 16 0, 1,4.j f x x x x x x x x x x x x x x x j                  1 2 3 4 5 6 7 1 2 3 4 5 1 2 4 6 2 3 4 7 ( ) 3 4 5 6 min 13 14 2 14 11 3 14 16 0, 1,7.j g x x x x x Mx Mx Mx x x x x x x x x x x x x x x j                        Ta đưa về bài toán M: Phương án cực biên ban đầu x = (0, 0, 0, 0, 14, 11, 16) 25  Bài toán quy hoạch tuyến tính Ta gọi vectơ Biến cơ sở Hệ số Phương án x1 x2 x3 x4 x5 x6 x7  3 -4 -5 6 M M M x5 M 14 1 1 1 13 1 0 0 14/13 x6 M 11 2 1 0 (14) 0 1 0 [11/14] x7 M 16 0 3 1 14 0 0 1 16/14 Bảng 1 41 3 5 2 [41] 0 0 0 0 -3 4 5 -6 0 0 0 x5 M 53/14 -6/7 1/14 1 0 1 0 53 x4 6 11/14 2/14 1/14 0 1 0 0 11 x7 M 5 -2 (2) 1 0 0 1 [5/2] Bảng 2 123/14 -20/7 [29/14] 2 0 0 0 33/7 -15/7 31/7 5 0 0 0 26  Bài toán quy hoạch tuyến tính Ta gọi vectơ x5 M 101/28 -11/14 0 (27/28) 0 1 [101/27] x4 6 17/28 3/14 0 -1/28 1 0 x2 -4 5/2 -1 1 1/2 0 0 5 Bảng 3 101/28 -11/14 0 [27/28] 0 0 -99/14 16/7 0 29/14 0 0 x3 -5 101/27 -22/27 0 1 0 x4 6 20/27 (5/27) 0 0 1 4 x2 -4 17/27 -16/27 1 0 0 Bảng 4 0 0 0 0 0 -151/9 [41/9] 0 0 0 27  Bài toán quy hoạch tuyến tính Ta gọi vectơ x3 -5 7 0 0 1 22/5 x1 3 4 1 0 0 27/5 x2 -4 3 0 1 0 16/5 Bảng 5 0 0 0 0 0 -35 0 0 0 -93/5 Phương án tối ưu x* = (4, 3, 7, 0) Giá trị tối ưu fmin = f(x*) = 35