Bài giảng môn Tối ưu hóa - Chương 1 bài toán quy hoạch tuyến tính

ThS. Phạm Trí Cao * Chương 1 03/01/2014 1 1 CHƯƠNG 1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH I) CÁC VÍ DỤ THỰC TẾ 2 Ví dụ 1.1: Bài toán lập kế hoạch sản xuất Một xí nghiệp có 3 loại nguyên liệu A (đường), B (sữa), C (hương trái cây) với lượng dự trữ tối đa trong kho lần lượt là 10, 15, 13 tấn. Xí nghiệp dùng các loại nguyên liệu này để sản xuất ra 4 loại sản phẩm kẹo mút: K1 (mum mum dâu), K2 (mum mum bạc hà), K3 (mum mum mật ong), K4 (mum mum dứa). Tiền lời thu được khi bán các loại sản phẩm kẹo lần lượt là 4, 6, 5, 8 triệu đ/tấn. 3  Tỷ lệ pha chế các loại nguyên liệu với nhau để sản xuất ra các loại sản phẩm cho trong bảng sau:  . Hãy lập kế hoạch sản xuất các loại sản phẩm sao cho: thỏa mãn yêu cầu hạn chế về nguyên liệu, đồng thời tổng số tiền lời thu được lớn nhất? 4 Loại nguyên liệu Dự trữ Tỷ lệ pha chế K1 (tấn) K2 (tấn) K3 (tấn) K4 (tấn) A (tấn) 10 1 2 3 4 B (tấn) 15 3 1 4 2 C (tấn) 13 2 4 1 1 Tiền lời (triệu đ/tấn) 4 6 5 8 ThS. Phạm Trí Cao * Chương 1 03/01/2014 2 5 Gọi xj là lượng sản phẩm loại Kj cần sản xuất (tấn), j= 1,4 Vậy ta có mô hình bài toán là:  Tìm véc tơ x= (x1, x2, x3, x4) sao cho:  f(x)= 4x1 + 6x2 + 5x3 + 8x4 max  x1 + 2x2 + 3x3 + 4x4 <= 10  3x1 + x2 + 4x3 + 2x4 <= 15  2x1 + 4x2 + x3 + x4 <= 13  xj >= 0, j= 1,4  Giải bài toán trên ta được kết quả: x= (4, 1, 0, 1) và fmax= 30 6 Ví dụ 1.2: Bài toán định khẩu phần thức ăn Để nuôi 1 loại gia súc, một đội sản xuất dùng 3 loại thức ăn T1 (Tuctung), T2 (Cuncon), T3 (Meoyeu). Trong 3 loại thức ăn này có chứa 3 loại chất dinh dưỡng A (DHA), B ( A+), C (Canxi @). 7 Số đơn vị chất dinh dưỡng (g) có trong 1 đơn vị thức ăn (kg): Chất dd Số đv chất dd có trong 1 đv thức ăn T1 T2 T3 A 7 2 6 B 5 1 7 C 6 3 4 8 Để gia súc phát triển tốt và thông minh thì nhu cầu tối thiểu về các chất dinh dưỡng A, B, C trong khẩu phần ăn hàng ngày của gia súc lần lượt là: 17, 14, 14 g. Giá thức ăn T1, T2, T3 lần lượt là 5, 4, 7 (chục ngàn đ/kg). Hãy xác định lượng thức ăn mỗi loại cần có trong khẩu phần ăn hàng ngày để đảm bảo yêu cầu về chất dinh dưỡng, đồng thời tổng số tiền mua thức ăn hàng ngày là nhỏ nhất? ThS. Phạm Trí Cao * Chương 1 03/01/2014 3 9 Gọi xj là lượng thức ăn loại Tj cần cho ăn hàng ngày (kg), j= 1,3 Vậy mô hình bài toán là:  Tìm véc tơ x= (x1, x2, x3) sao cho:  f(x)= 5x1 + 4x2 + 7x3 min  7x1 + 2x2 + 6x3 >= 17  5x1 + x2 + 7x3 >= 14  6x1 + 3x2 + 4x3 >= 14  xj >=0, j= 1,3 Giải bt trên ta được: x= (21/11, 0, 7/11) và fmin= 14 10 11  – f(x) gọi là hàm mục tiêu.  Các cj gọi là các hệ số hàm mục tiêu.  – Số (2) gọi là ràng buộc chung.  Số (3) gọi là ràng buộc biến.  Hệ (*) gọi là hệ ràng buộc (miền ràng buộc).  – Các bi gọi là các hệ số tự do.  – Các aij gọi là các hệ số của ràng buộc chung.  – Một véc tơ x gọi là 1 phương án (PA) của bài toán nếu x thỏa hệ ràng buộc (*).  – Tập hợp tất cả các PA của bài toán gọi là tập phương án. Ký hiệu D, X, Y, 12  – Khái niệm phương án tối ưu (patư):  Bài toán minf: Một PA làm cho hàm mục tiêu đạt cực tiểu gọi là phương án tối ưu (patư). Ký hiệu là x*.  Nghĩa là: xD: f(x) >= f(x*)  Bài toán maxf: Một PA làm cho hàm mục tiêu đạt cực đại gọi là phương án tối ưu (patư). Ký hiệu là x*.  Nghĩa là: xD: f(x) <= f(x*)  – Bài toán QHTT có patư gọi là bài toán giải được.  – Giải bài toán QHTT là tìm các patư của nó (nếu có) hoặc chứng tỏ nó không có patư.  – Hai bài toán QHTT gọi là tương đương nhau nếu chúng có chung tập patư. ThS. Phạm Trí Cao * Chương 1 03/01/2014 4 13  Chuyển bài toán max về bài toán min:  f(x) max  g(x)= f(x) min xD xD Ta có 2 bài toán là tương đương nhau. 14 Phương án cực biên (phương án cơ bản) của bài toán QHTT tổng quát Khái niệm ràng buộc chặt, lỏng.  Một ràng buộc gọi là chặt đối với pa x nếu khi ta thay x vào ràng buộc này thì xảy ra dấu bằng, thí dụ ib n j j xija 1  Một ràng buộc gọi là lỏng đối với pa x nếu khi ta thay x vào ràng buộc này thì xảy ra dấu bất đẳng thức thực sự, thí dụ ib n j j xija 1 hoặc ib n j j xija 1 Khái niệm chặt, lỏng xét cho cả ràng buộc chung và ràng buộc biến. 15  Khái niệm phương án cực biên (pacb). Một pa có số ràng buộc chặt độc lập tuyến tính bằng n (số biến) gọi là pacb.  Một pacb có số ràng buộc chặt bằng số ràng buộc chặt độc lập tuyến tính gọi là pacb không suy biến.   Một pacb có số ràng buộc chặt nhiều hơn số ràng buộc chặt độc lập tuyến tính gọi là pacb suy biến. Một pa có số ràng buộc chặt độc lập tuyến tính ít hơn n gọi là pa không cực biên.  Lưu ý:  Số ràng buộc chặt đltt <= n (số biến)  Số ràng buộc chặt đltt <= số ràng buộc chặt 16  Ví dụ 1:  f= 3x1 + 4x2 6x3 + 7x4 min  2x1 + x2 + x3  x4 <= 3  x1 + x2  x3 + 2x4 >= 1  x1>=0, x2>=0, x3>=0, x4<=0   Chứng minh các kết quả sau:  1) x= (0, 1, 2, 0) là pacbksb?  2) x= (0, 2, 1, 0) là pakcb?  Bài giải chi tiết xem trong sách. VD2: pacbsb : xem trong sách. ThS. Phạm Trí Cao * Chương 1 03/01/2014 5 17 2) Bài toán QHTT dạng chính tắc * Dạng đại số: f(x)=  n j j xjc1  min (max) (1) ib n j j xija 1 , i= 1,m (2) xj >=0 , j= 1,n (3) 18 * Dạng ma trận: Đặt:                  mnamama naaa naaa A ...21 ............ 2...2221 1...1211 ,                  mb b b b ... 2 1 ,                nx x x x ... 2 1     ncccc ...21 19 Ta viết bài toán (1)-(3) dưới dạng ma trận:  f(x)=  min (max)  A.x= b  x >= 0 Với quy ước: x= (x1, x2, ..., xn) >= 0 xj >= 0, j= 1,n 20 Cách chuyển bài toán tổng quát về dạng chính tắc: Bất kỳ bài toán QHTT tổng quát nào cũng có thể đưa về dạng chính tắc bằng các phép biến đổi tuyến tính sau: * Ràng buộc biến: Nếu xj =0 Nếu xj bất kỳ thì ta đặt xj = xj+ xj với xj+ , xj >=0 ThS. Phạm Trí Cao * Chương 1 03/01/2014 6 21 * Ràng buộc chung: Nếu ib n j j xija 1 thì thêm biến phụ yi >=0: ibiy n j j xija 1 Nếu ib n j j xija 1 thì thêm biến phụ yi >=0: ibiy n j j xija 1 22 Ví dụ 1.4: Bài toán tổng quát (P)  f(x)= 3x1 + 4x2 + 7x3 max  x1 + 3x2 - 2x3 <= 7  2x1 + x2 + 3x3 = 6  - x1 + 5x2 + 4x3 >= 3  xj >=0, j= 1,3 Viết bài toán dạng chính tắc (P*)? x*(P*)= (0, 3, 1, 0, 16) thì x*(P)= ? Nếu (P*) không có patư thì (P) cũng không có patư. Bài giải chi tiết xem trong sách. 23 Ví dụ 1.5: Bài toán (P)  f(x)= x1 +2x2 + x3 max  2x1 + x2 + 3x3 = 9  4x1 + 3x2 + x3 = 1  x1 >=0, x2 <=0, x3 tùy ý Viết bài toán dạng chính tắc (P*)? x*(P*) = (0, 3/4, 13/4, 0) thì x*(P) = ? Bài giải chi tiết xem trong sách.  24 VD 1.6: Bài toán (P)  f= x1 + 0x2 + 2x3 min  3x1 + x2 + 4x3 <= 17  x1 + 5x2 + 3x3 = 10  7x1 + x2 + x3 >= 4  x1 >=0 , x2 <=0 , x3 tùy ý Viết bài toán chính tắc (P*) ? x*(P*)= (1/10, 0, 33/10, 0, 35/10, 0) thì x*(P)= ? Bài giải chi tiết xem trong sách. ThS. Phạm Trí Cao * Chương 1 03/01/2014 7 25 Phương án cực biên của bài toán dạng chính tắc Bài toán chính tắc dạng ma trận:  f(x) =  min (max) (1)  A.x = b (2)  x >= 0 (3)  Ta có: A.x = b x1A1 + x2A2 +...+ xnAn = b Ký hiệu: Aj , j= 1,n là các véc tơ cột của ma trận hệ số A. 26  Cách xác định pacb:  x = (x1, x2, ... , xj , ... , xn) là pa của bt (1)-(3). Đặt: J(x)= {j / xj > 0} Ký hiệu: m(J) là số phần tử của tập J(x).  x là pa cực biên  hệ véc tơ cột tương ứng với các thành phần dương của x độc lập tuyến tính Nghĩa là: x= (x1,x2, ..., xn) là pacb  {Aj / j J(x)} đlập tt  x là pacb. Ta luôn có: m(J) <= r(A)  * Nếu m(J) = r(A) thì x là pacb không suy biến  * Nếu m(J) < r(A) thì x là pacb suy biến 27 Ví dụ 1:  f = x1 - 2x2 + x3 min  x1 + x2 + 2x3 = 14  x1 + x2 + x3 = 9  xj >=0, j= 1,3 Cmr x= (4, 0, 5) là pacbksb? Bài giải chi tiết xem trong sách. 28 Ví dụ 2:  f = x1 + x3 max  x1 - x2 + 3x3 = 2  -x1 + x2 - x3 = 2  xj >=0, j= 1,3 Cmr x= (2, 4, 0) không là pacb? Bài giải chi tiết xem trong sách. ThS. Phạm Trí Cao * Chương 1 03/01/2014 8 29 Ví dụ 3:  f = x1 + 4x2 + x3 max  x1 + x2 - x3 = 7  -x1 + 2x2 +x3 = 14  xj >=0, j= 1,3 Cmr x= (0,7,0) là pacbsb? Bài giải chi tiết xem trong sách. 30  Ta có các kết quả cho bài toán dạng chính tắc:  Bài toán có thể có pa hoặc không.  Nếu bài toán có pa thì nó có pacb.  Bài toán có mọi pacb đều không suy biến gọi là bài toán không suy biến. Nếu có ít nhất 1 pacb suy biến thì gọi là bài toán suy biến.  Bài toán minf : Nếu bài toán có pa và hàm mục tiêu bị chận dưới thì bài toán có patư. Nếu f không bị chặn dưới thì f - .  Bài toán maxf : Nếu bài toán có pa và hàm mục tiêu bị chận trên thì bài toán có patư. Nếu f không bị chặn trên thì f + .  Nếu bài toán có patư thì bài toán có pacbtư. Một pa gọi là pacbtư nếu nó vừa là pacb và vừa là patư. 31 Nếu bài toán có 2 patư x1, x2 với x1 x2 thì .x1 +(1-).x2 , [0,1] cũng là patư  bài toán có vô số patư. x là pacb. Nếu x không là patư thì luôn tìm được pacb x' tốt hơn x. Nghĩa là: Bài toán minf: f(x') <= f(x) Bài toán maxf: f(x’) >= f(x) Số pacb của bài toán là hữu hạn. 32  3) Bài toán QHTT dạng chuẩn tắc  Bài toán QHTT dạng chuẩn tắc là bài toán QHTT dạng chính tắc thỏa thêm các điều kiện sau:  - Các hệ số tự do bi bên vế phải của các ràng buộc chung phải >=0.  -Mỗi ràng buộc chung phải có biến cơ sở tương ứng.  - Biến cơ sở: là biến có hệ số là 1 ở một ràng buộc chung và có hệ số là 0 ở các ràng buộc chung còn lại.  - Các biến không phải là biến cơ sở (biến cơ bản) thì gọi là biến tự do.  - Biến cơ sở tương ứng với véc tơ cơ sở, biến tự do tương ứng với véc tơ tự do. ThS. Phạm Trí Cao * Chương 1 03/01/2014 9 33 Ví dụ 1.7:  f= x1 + 2x2 + x3 - x4 min  x1+ x2 - x3 = 7  2x2 + x3 + x4= 5  xj >= 0 , j= 1,4 Hướng dẫn: Đây là bài toán dạng chuẩn tắc.  Ta có x1, x4 là biến cơ sở, x2, x3 là biến tự do.  Ta cho x2, x3 = 0 (các biến tự do) thì ta có: x1 = 7, x4 = 5 (biến cơ sở). Vậy ta có pa x= (7, 0, 0, 5) là pacb không suy biến. 34 Ví dụ 1.9:  f(x)= x1 + x2 – x3 max  x1 + x3 + x4= 4   x2 + 2x3 = 7  xj >=0, j= 1,4  Xét xem BT có chuẩn tắc không?  Bài giải chi tiết xem trong sách. 35 Ví dụ 1.9bis:  f(x)= x1 + x2 – x3 +6x6 max x1 + x3 + x4 = 4  x2+ 2x3 + x5 = 7  -5x3 + 3x5 + x6 = 0  xj >=0, j= 1,6 Xét xem BT có chuẩn tắc không? 36 III) PHƯƠNG PHÁP HÌNH HỌC GIẢI BÀI TOÁN QHTT Với bài toán QHTT 2 biến tổng quát, ta có thể dùng pp hình học để giải. Các kết quả sử dụng để giải bài toán theo pp hình học: Đường thẳng (D): ax+by=c chia mặt phẳng Oxy thành 2 miền: miền có ax+by>c và miền có ax+by<c. Muốn biết miền nào thỏa ax+by>c thì ta lấy 1 điểm bất kỳ thay vào, thí dụ điểm (0,0) thay vào : a.0+b.0 = 0, nếu 0 > c thì miền chứa điểm (0,0) thỏa ax+by>c. ThS. Phạm Trí Cao * Chương 1 03/01/2014 10 37  Đường thẳng (D): ax+by=c gọi là đường đẳng mức, có pháp véc tơ là n =(a,b). * Nếu di chuyển (D) theo cùng chiều n thì giá trị mức c tăng lên. * Nếu di chuyển (D) theo ngược chiều n thì giá trị mức c giảm xuống. 38  Ví dụ 1:  f(x)= 7x - 2y  5x - 4y >= -3 (qua A, C)  2x - 7y <= -12 (qua A, B)  -x - y >= -12 (qua B, C)  3x - 5y >= -20 (qua C, (0,4))  1) Vẽ tập pa D?  3) Tìm minf, maxf? Hướng dẫn:  1) Tập pa là 1 tam giác có các đỉnh là A(1,2), B(8,4), C(5,7). VD1 39 VD2 40 ThS. Phạm Trí Cao * Chương 1 03/01/2014 11 VD3 41 VD4 42 VD6 43 44  IV) PHƯƠNG PHÁP ĐƠN HÌNH GIẢI BÀI TOÁN QHTT  Bước 1: Lập bảng đơn hình xuất phát  Từ bài toán dạng chuẩn ta xác định các biến cơ sở và véc tơ cơ sở tương ứng. Các biến không phải biến cơ sở là biến tự do, và xác định các véc tơ tự do tương ứng. Xác định pacb ban đầu xuất phát: x= (x1, x2 , ... , xn).  Ta có: J(x)= {j / xj >0} tập các chỉ số của véc tơ cơ sở. ThS. Phạm Trí Cao * Chương 1 03/01/2014 12 45 Lập bảng đơn hình xuất phát sau: Cơ sở Hệ số PA c1 c2 ..... cn A1 A2 ..... An JJ(x) Aj cj xj zj1 zj2 zjn f 1 2 n f= f(x)= cột Hệ số * cột PA =  )(xJj j xjc : giá trị hàm mục tiêu ứng với x. k= cột Hệ số * cột Ak –ck =  )(xJj kcjkzjc : hệ số ước lượng của biến xk , k= 1,n 46 Ví dụ 1.10:  f(x)= 6x1 + 2x2 + x3 + 3x4 + x5 - 7x6 min  - x1 + x2 + 2x4 + x6 = 15  4x1 + 2x4 + x5 -3x6 = 2  2x1 + x3 + x4 + 2x6 = 9  xj >=0 , j= 1,6  Ta có các biến cơ sở là x2, x3, x5 và véc tơ cơ sở là A2, A3, A5.  các biến tự do là x1, x4, x6 và véc tơ tự do là A1, A4, A6.  x= (0, 15, 9, 0, 2, 0) là pacb ban đầu. 47 Bảng đơn hình xuất phát Cơ sở Hệ số PA 6 2 1 3 1 -7 A1 A2 A3 A4 A5 A6 A2 2 15 -1 1 0 2 0 1 A5 1 2 4 0 0 2 1 -3 A3 1 9 2 0 1 1 0 (2) B1 (dòng f) 41 -2 0 0 4 0 (8) 48  Bước 2: Xét dấu hiệu tối ưu  Xem dòng ghi các hệ số ước lượng 1, 2 , ... , n .  - Nếu có k <=0, k : pa đang xét là patư. Thuật toán kết thúc.  - Nếu không: qua bước 3.  Bước 3: Xét dấu hiệu không tối ưu  Xét xem có cột Ak thỏa: k>0 và mọi phần tử thuộc cột này (ở bước lặp đang xét) đều <=0 không?  - Nếu có: BT không có patư (hàm mục tiêu f không bị chận dưới). Thuật toán kết thúc.  - Nếu không: qua bước 4. ThS. Phạm Trí Cao * Chương 1 03/01/2014 13 49  Bước 4: Cải tiến pa (Tìm một pacb mới tốt hơn)  Ta tìm pacb mới x’= (x1’ , , xn’) tốt hơn pacb x: f(x’) <= f(x)  Pacb x ứng với bảng đơn hình cũ, pacb x’ ứng với bảng đơn hình mới.  Lập bảng đơn hình mới từ bảng đơn hình cũ như sau:  4.1) Chọn cột chủ yếu:  Chọn cột chủ yếu là cột có  dương lớn nhất.  Tức là: chọn s sao cho s = max{k / k >0}, cột chủ yếu ký hiệu là As. 50  4.2) Chọn dòng chủ yếu:   = min{ (cột PA/ cột CY) / với các thành phần dương của cột CY}   = xr / zrs = min{ (xj / zjs ) / jJ(x) và zjs >0} , dòng chủ yếu là Ar.   gọi là tỷ số đơn hình.  4.3) Xác định phần tử chủ yếu:  Phần tử CY là phần tử nằm ở vị trí: dòng chủ yếu, cột chủ yếu, ký hiệu là zrs .  Lưu ý: Giá trị hàm mục tiêu khi chuyển từ bảng cũ sang bảng mới sẽ giảm 1 lượng là .s :  f(x’) = f(x) – .s 51  4.4) Lập ra bảng mới dựa vào bảng cũ:  4.4.1) Trên cột cơ sở: Thay Ar bởi As , giữ nguyên các phần tử còn lại.  Trên cột Hệ số: Thay cr bởi cs , giữ nguyên các phần tử còn lại.  4.4.2) Các phần tử còn lại của bảng:  Có nhiều cách để xác định các phần tử còn lại của bảng mới, mỗi tác giả đưa ra một cách làm riêng. Tôi đưa ra 1 cách làm dựa vào các phép biến đổi sơ cấp Gauss trong Đại số tuyến tính, tạm gọi là Gauss Lovely. 52 Ta nhận thấy, từ bảng cũ chuyển sang bảng mới trong cột Cơ sở: ta loại ra 1 véc tơ (Ar) và thay bằng 1 véc tơ mới (As), các véc tơ còn lại giữ nguyên. Do đó, ta biến đổi sao cho ở bảng mới cột As có dạng (0, , 1, , 0)T, với số 1 ở vị trí dòng As (mới).  Sau khi có được bảng mới, ta quay lại bước 2. ThS. Phạm Trí Cao * Chương 1 03/01/2014 14 53 Cơ sở Hệ số PA 6 2 1 3 1 -7 A1 A2 A3 A4 A5 A6 A2 2 15 -1 1 0 2 0 1 A5 1 2 4 0 0 2 1 -3 A3 1 9 2 0 1 1 0 (2) B1 (dòng f) 41 -2 0 0 4 0 (8) Cơ sở Hệ số PA 6 2 1 3 1 -7 A1 A2 A3 A4 A5 A6 A2 2 21/2 -2 1 -1/2 3/2 0 0 A5 1 31/2 7 0 3/2 7/2 1 0 A6 -7 9/2 1 0 ½ ½ 0 1 B2 (dòng f) 5 -10 0 -4 0 0 0 54 Kết luận? 55 Lưu ý: Ta phải canh theo dòng chủ yếu để biến đổi. Ở bảng 1 không được lấy dòng A5 + 3 lần dòng A2 rồi kết quả cất vào dòng A5 ở bảng 2. Bởi vì nếu làm như vậy thì cột A2 ở bảng mới không có dạng (1, 0, 0)T. 56 Cơ sở Hệ số PA 6 2 1 3 1 -7 A1 A2 A3 A4 A5 A6 A2 2 21/2 -2 1 -1/2 3/2 0 0 A5 1 47 1 3 0 8 1 0 A6 -7 9/2 1 0 ½ ½ 0 1 B2 (dòng f) 5 -10 0 -4 0 0 0 ThS. Phạm Trí Cao * Chương 1 03/01/2014 15 57 Ví dụ 1.12: f(x) = x1 - 2x2 + 2x3 - x4 + x5 - 2x6  min 2x1 - x2 - 5x3 + x4 = 5 x1 - 2x2 + 2x3 + x5 = 4 -4x1 + x2 + x3 + x6 = 2 xj >=0 , j= 1,6 Cơ sở Hệ số PA 1 -2 2 -1 1 -2 A1 A2 A3 A4 A5 A6 A4 -1 5 (2) -1 -5 1 0 0 A5 1 4 1 -2 2 0 1 0 A6 -2 2 -4 1 1 0 0 1 B1 -5 (6) -1 3 0 0 0 58 Cơ sở Hệ số PA 1 -2 2 -1 1 -2 A1 A2 A3 A4 A5 A6 A4 -1 5 (2) -1 -5 1 0 0 A5 1 4 1 -2 2 0 1 0 A6 -2 2 -4 1 1 0 0 1 B1 -5 (6) -1 3 0 0 0 A1 1 5/2 1 -1/2 -5/2 1/2 0 0 A5 1 3/2 0 -3/2 9/2 -1/2 1 0 A6 -2 12 0 -1 -9 2 0 1 B2 -20 0 2 18 -3 0 0 59 Kết luận? VD1.13: Xem chi tiết trong sách. Cách 2: Tìm lượng giảm lớn nhất của hàm mục tiêu Qua mỗi bước lặp, giá trị hàm mục tiêu giảm 1 lượng là .s , f(x’) = f(x)–.s . Vậy ta có thể đưa ra cách 2: tìm lượng giảm lớn nhất của f(x) qua mỗi bước lặp. 60 Lưu ý:  Nếu có nhiều cột có cùng  dương lớn nhất thì ta làm thế nào?  Nếu có nhiều dòng để chọn thì ta làm thế nào? Xem chi tiết ở trong sách. ThS. Phạm Trí Cao * Chương 1 03/01/2014 16 61 VII) BÀI TOÁN (M) – VẤN ĐỀ TÌM PA CỰC BIÊN BAN ĐẦU  Thuật toán đơn hình chỉ áp dụng cho bài toán dạng chuẩn. Bài toán dạng chuẩn tắc cho ta pacb ban đầu, có pacb này ta mới lập được bảng đơn hình xuất phát. Nếu bài toán dạng chính tắc, chưa chuẩn thì ta phải biến đổi để đưa về dạng chuẩn.  - Nếu bài toán dạng chính tắc, có hệ số tự do bi bên vế phải ràng buộc chung <0 thì ta biến đổi sao cho bi >=0. 62  - Nếu bài toán dạng chính tắc (các hệ số vế phải ràng buộc chung bi >= 0) chưa có đủ các biến cơ sở tương ứng ở mỗi ràng buộc chung thì ta thêm một số biến giả vào để đóng vai trò là biến cơ sở. Bài toán có biến giả gọi là bt (M). Để biết thêm bao nhiêu biến giả vào và thêm vào ràng buộc chung nào ta làm như sau: Xét các ràng buộc chung từ trên xuống dưới, nếu ràng buộc chung nào có biến cơ sở rồi thì thôi, còn chưa có biến cơ sở thì ta thêm 1 biến giả vào. 63 Ví dụ 1.19:  Bài toán (P):  f(x) = x1 - 2x2 + 3x3 + x4 min  4x1 + 2x3 + 2x4 = 1  x1 + x2+ 5x3 - 4x4 = 6  xj >=0 , j= 1,4  Hãy viết bài toán (M) tương ứng?  Bài giải chi tiết xem trong sách. 64 Định lý: 1) Nếu bài toán (M) không có patư thì bài toán (P) không có patư. 2) Nếu bài toán (M) có patư thì có 2 trường hợp:  * Nếu tất cả các biến giả trong patư của (M) đều bằng 0 thì (P) có patư, chính là patư của (M) mà loại ra các biến giả.  * Nếu trong patư của (M) có biến giả khác 0 thì (P) không có patư (vì ta không thể bỏ biến giả này được). ThS. Phạm Trí Cao * Chương 1 03/01/2014 17 65 VD 1.19 Bài toán (M) là: f(x) = x1 - 2x2 + 3x3 + x4 + Mx5  min 4x1 + 2x3 + 2x4 + x5 = 1 x1 + x2 + 5x3 - 4x4 = 6 xj >=0 , j= 1,5 Cơ sở Hệ số PA 1 -2 3 1 M A1 A2 A3 A4 A5 A5 M 1 (4) 0 2 2 1 A2 -2 6 1 1 5 -4 0 B1 (dòng f) M-12 (4M-3) 0 2M-13 2M+7 0 66 Cơ sở Hệ số PA 1 -2 3 1 M A1 A2 A3 A4 A5 A5 M 1 (4) 0 2 2 1 A2 -2 6 1 1 5 -4 0 B1 (dòng f) M-12 (4M-3) 0 2M-13 2M+7 0 A1 1 1/4 1 0 1/2 (½) ¼ A2 -2 23/4 0 1 9/2 -9/2 - ¼ B2 (dòng f) -45/4 0 0 -23/2 (17/2) -M+3/4 A4 1 1/2 2 0 1 1 ½ A2 -2 8 9 1 9 0 2 B3 (dòng f) -31/2 -17 0 -20 0 -M-7/2 67 Kết luận? 68 Ví dụ 1.20: Bài toán (P)  f= x1 + x2 – x3 + 2x4 + 3x5 min  x1 – x3 + 2x4 + x5 =1  x2 – x4 + x5 = 3  x3 – 2x5 = 2  xj >=0, j= 1,5 ThS. Phạm Trí Cao * Chương 1 03/01/2014 18 69 Bài toán (M) f= x1 + x2 – x3 + 2x4 + 3x5 + Mx6  min x1 – x3 + 2x4 + x5 = 1 x2 – x4 + x5 = 3 x3 – 2x5 + x6 = 2 xj >=0, j= 1,6 Trong đó: x6 là biến giả và M>0 (rất lớn) Cơ sở Hệ số PA 1 1 –1 2 3 A1 A2 A3 A4 A5 A1 A2 A6 1 1 M 1 3 2 1 0 0 0 1 0 –1 0 (1) 2 –1 0 1 1 –2 B1 2M+4 0 0 (M) –1 –2M–1 70 Cơ sở Hệ số PA 1 1 –1 2 3 A1 A2 A3 A4 A5 A1 A2 A6 1 1 M 1 3 2 1 0 0 0 1 0 –1 0 (1) 2 –1 0 1 1 –2 B1 2M+4 0 0 (M) –1 –2M–1 A1 A2 A3 1 1 –1 3 3 2 1 0 0 0 1 0 0 0 1 2 –1 0 –1 1 –2 B2 4 0 0 0 –1 –1 71 Kết luận? Xem chi tiết trong sách. 72 Ví dụ 1.21: Bài toán (P)  f= x1 - 2x2 + 3x3 + x4 min  4x1 + x2 + 2x3 + 2x4 = 2  x1 + 5x3 - 4x4 = 12  xj >=0 , j= 1,4 Viết và giải bài toán (M) tương ứng? Bài giải chi tiết xem trong sách. ThS. Phạm Trí Cao * Chương 1 03/01/2014 19 73 Ví dụ 1.21: Cơ sở Hệ số PA 1 -2 3 1 A1 A2 A3 A4 A3 3 1 2 ½ 1 1 A5 M 7 -9 -5/2 0 -9 B2 7M+3 -9M +5 (-5/2)M +(7/2) 0 -9M +2 Kết luận? 74 VIII) BÀI TOÁN QHTT DẠNG CHUẨN, f max Cách 1 (gián tiếp):  f max  g = – f min  xD xD Ta đã biết: x* là patư của maxf x* là patư của ming  fmax = f(x*) = – gmin = – g(x*) 75  Cách 2 (trực tiếp):  Thuật toán giống thuật toán dạng chuẩn, f min. Chỉ thay đổi:  B2) Tiêu chuẩn tối ưu:  k >=0, k : pa đang xét là patư.  Thuật toán kết thúc.  B3) Tiêu chuẩn không tối ưu:  Nếu có cột Ak có k <0 và mọi phần tử thuộc cột này đều <=0 thì bài toán không có patư (do f không bị chận trên).  Thuật toán kết thúc. 76 Cách 2 (trực tiếp): B4) Chọn cột chủ yếu: s = min{k / k <0}  Cột chủ yếu là cột có  âm nhỏ nhất. Các phần giữ nguyên như cũ: giống min. B1) Bảng đơn hình xuất phát. B4) Dòng chủ yếu, phần tử chủ yếu.  Quá trình chuyển từ bảng cũ sang bảng mới. ThS. Phạm Trí Cao * Chương 1 03/01/2014 20 77 Ví dụ 1.22:  f(x)= -6x1 - 2x2 - x3 - 3x4 - x5 + 7x6 max  - x1 + x2 + 2x4 + x6 = 15  4x1 + 2x4 + x5 -3x6 = 2  2x1 + x3 + x4 + 2x6 = 9  xj >=0, j= 1,6 Cách 1: xem chi tiết trong sách. 78 Cách 2 (giải trực tiếp): f(x)= -6x1 -2x2 -x3 -3x4 -x5 +7x6  max - x1 + x2 + 2x4 + x6 = 15 4x1 + 2x4 + x5 -3x6 = 2 2x1 + x3 + x4 + 2x6 = 9 xj >=0, j= 1,6 Cơ sở Hệ số PA -6 -2 -1 -3 -1 7 A1 A2 A3 A4 A5 A6 A2 -2 15 -1 1 0 2 0 1 A5 -1 2 4 0 0 2 1 -3 A3 -1 9 2 0 1 1 0 (2) B1 (dòng f) -41 2 0 0 -4 0 (-8) 79 Cơ sở Hệ số PA -6 -2 -1 -3 -1 7 A1 A2 A3 A4 A5 A6 A2 -2 15 -1 1 0 2 0 1 A5 -1 2 4 0 0 2 1 -3 A3 -1 9 2 0 1 1 0 (2) B1 (dòng f) -41 2 0 0 -4 0 (-8) A2 -2 21/2 -2 1 -1/2 3/2 0 0 A5 -1 31/2 7 0 3/2 7/2 1 0 A6 7 9/2 1 0 ½ ½ 0 1 B2 (dòng f) -5 10 0 4 0 0 0 80 Kết luận? ThS. Phạm Trí Cao * Chương 1 03/01/2014 21 81 Ví dụ 1.23: Bài toán (P):  f(x)= –x1 + x2 + x3 + 2x5 max  2x1 – x2 – x4 = 6  3x1 – x4 + x5 + x6 = 10  x3 – 2x4 + 2x5 = 4  xj >=0, j= 1,6 Bài giải chi tiết xem trong sách. Hệ số của biến giả trong hàm mục tiêu là –M. 82 Cơ sở Hệ số PA –1 1 1 0 2 0 A1 A2 A3 A4 A5 A6 A1 A4 A3 –1 0 1 4 2 8 1 0 0 1 3 6 0 0 1 0 1 0 1 2 6 1 2 4 B3 4 0 4 0 0 3 3 Kết luận? 83  IX) GIẢI BÀI TOÁN QHTT TỔNG QUÁT Quá trình giải bài toán tổng quát là quá trình kết hợp các bước phân tích ta đã làm từ đầu chương cho đến đây. Phương pháp giải:  * Đưa bài toán tổng quát về dạng chính tắc.  * Nếu các hệ số tự do bi ở vế phải của các ràng buộc chung <0 thì ta phải biến đổi sao cho chúng >=0.  * Nếu bài toán chưa là dạng chuẩn (vì thiếu biến cơ sở) thì thêm biến giả vào, ta được bài toán (M). 84 ThS. Phạm Trí Cao * Chương 1 03/01/2014 22 85 Ví dụ 1.25: Bài toán (P)  f= x1 + 3x2 + x3 min  x1 + x2 + x3 >= 5  - x2 - 2x3 = -8  x1 + 2x2 + x3 <= 10  xj >=0, j= 1,3 86 Bài toán (P*)  f= x1 + 3x2 + x3 min  x1 + x2 + x3 - x4 = 5  x2 + 2x3 = 8  x1 + 2x2 + x3 + x5 = 10  xj >=0, j= 1,5 (x4 , x5 là biến phụ) 87  Bài toán (M)  f= x1 + 3x2 + x3 +M.x6 +M.x7  min  x1 + x2 + x3 - x4 + x6 = 5  x2 + 2x3 + x7 = 8  x1 + 2x2 + x3 + x5 = 10  xj >=0, j= 1,7 (x6 , x7 là biến giả)   với M>0 (rất lớn)  x*(M)= (1, 0, 4, 0, 5, 0, 0)  Kết luận? 88  Ví dụ 1.26: f(x)= x1 + x2 + 3x3 + 2x4 max  x1 + 2x2 + x3 + 2x4 <= 10  2x1 + x2 + 3x3 + 4x4 = 9  x1 + 2x2 + 2x3 + x4 >= 8  xj >=0, j= 1,4  Giải:  f(x)= x1 + x2 + 3x3 + 2x4 – M.x7– M.x8 max  x1 + 2x2 + x3 + 2x4 + x5 = 10  2x1 + x2 + 3x3 + 4x4 + x7 = 9  x1 + 2x2 + 2x3 + x4 –x6 + x8= 8  xj >=0, j= 1,8  x*(M)= (0, 3/2, 5/2, 0, 9/2, 0, 0, 0) . Kết luận? ThS. Phạm Trí Cao * Chương 1 03/01/2014 23 89 X) VẤN ĐỀ VỀ PATƯ DUY NHẤT CỦA BÀI TOÁN QHTT  1) Các khái niệm  * Véc tơ chỉ phương của cạnh vô hạn tối ưu (vtcp): Ví dụ 1.27:  f(x)= x1 + 3x3 + 4x4 - 2x5 + 2x6 min  - x2 + x3 - 2x4 + x6 = 5  x1 + x2 - 4x4 + 2x6 = 1  3x2 - 7x4 + x5+ 4x6 = 4  xj >=0, j= 1, 6 90 Cơ sở Hệ số PA 1 0 3 4 -2 2 A1 A2 A3 A4 A5 A6 A3 3 5 0 -1 1 -2 0 1 A1 1 1 1 1 0 -4 0 2 A5 -2 4 0 3 0 -7 1 4 8 0 -8 0 0 0 -5 t= (4, 0, 2, 1, 7, 0) t1 t3 t4 t5 91 2) Định lý (patư tổng quát) Bài toán có các pacbtư x1, x2 , ... , xk và các vtcp là t1 , t2 , tm thì patư tổng quát của bài toán là: x =   m j jtj k i ixi 11  ;  i >= 0,   k i i1 1 ;  j >=0 VD1: Bài toán có 2 pacbtư là x1, x2 thì patư tổng quát là: x= 1x1+2x2 với 1+2=1 , 0<= i <=1 Hay có thể viết: x= .x1 + (1–).x2 với 0<=  <=1 VD2: Bt có 3 pacbtư là x1, x2, x3 thì patư tổng quát là: x= 1x1 + 2x2 + 3x3 với 1+2+3 = 1 , 0<= i <=1 92 2) Định lý (patư tổng quát) VD3: Bài toán có 1 pacbtư là x* và 1 vtcp là t thì patư tổng quát là: x= x*+.t với  >=0 VD4: Bài toán có 1 pacbtư là x* và 2 vtcp là t1 và t2 thì patư tổng quát là: x= x* + 1t1 + 2t2 với 1, 2 >=0 VD5: Bài toán có 2 pacbtư là x1, x2 và 2 vtcp là t1 và t2 thì patư tổng quát là: x= x1 + (1–)x2 + 1t1 + 2t2 với 0=0 ThS. Phạm Trí Cao * Chương 1 03/01/2014 24 93  3) Cách xác định bài toán có patư duy nhất không  Để xác định bài toán có patư duy nhất hay không, ta làm như sau:  Xét bảng đơn hình tối ưu (là bảng mà từ đó ta lấy ra patư) của bài toán QHTT.  B1) Nếu k ≠ 0 với mọi biến tự do xk : bài toán có patư duy nhất.  B2) Nếu có j = 0 với xj là biến tự do: bài toán có thể có patư duy nhất hoặc không.  Ta xét tiếp như sau:  Lấy cột có hệ số ước lượng  bằng 0 (ứng với biến tự do) làm cột chủ yếu (As). 94  Tìm tỷ số đơn hình  :   = xr / zrs = min{(cột pa / cột chủ yếu) / các phần tử thuộc cột chủ yếu dương}  B21) Nếu  > 0: bài toán có patư không duy nhất.  Lấy dòng Ar làm dòng chủ yếu, tiếp tục biến đổi ta sẽ có pacbtư khác.  B22) Nếu  = 0: bài toán có patư duy nhất.  (patư không thay đổi nhưng cơ sở có thể thay đổi)  B23) Nếu không tồn tại  (do tất cả các phần tử trên cột As đều <=0) thì ta có véc tơ chỉ phương: bài toán có patư không duy nhất. 95  Ví dụ 1.32:  f= 2x1 + x2 + x3 min  x1 - x2 - x3 <= 2  2x1 - x2 + x3 >= 2  2x1 + x2 + 2x3 <= 8  xj >=0, j= 1,3  Giải:  f= 2x1 + x2 + x3 +Mx7 min  x1 - x2 - x3 + x4 = 2  2x1 - x2 + x3 – x5 + x7 = 2  2x1 + x2 + 2x3 + x6 = 8  xj >=0, j= 1,7 96 Cơ sở Hệ số PA 2 1 1 0 0 0 A1 A2 A3 A4 A5 A6 A4 0 2 1 -1 -1 1 0 0 A7 M 2 (2) -1 1 0 -1 0 A6 0 8 2 1 2 0 0 1 B1 2M (2M-2) -M-1 M-1 0 -M 0 A4 0 1 0 -1/2 -3/2 1 ½ 0 A1 2 1 1 -1/2 (1/2) 0 -1/2 0 A6 0 6 0 2 1 0 1 1 B2 2 0 -2 (0) 0 -1 0 A4 0 4 3 -2 0 1 -1 0 A3 1 2 (2) -1 1 0 -1 0 A6 0 4 -2 3 0 0 2 1 B3 2 (0) -2 0 0 -1 0 ThS. Phạm Trí Cao * Chương 1 03/01/2014 25 97 Pacbtư: x1 = (1, 0 , 0) , fmin = 2 Ta có pacbtư mới: x2 = (0, 0, 2). Vậy bài toán chỉ có 2 pacbtư là x1 và x2 . Patư tổng quát: x= .x1 + (1-).x2 với  [0,1] Trong trường hợp này: pacbtư không duy nhất, patư không duy nhất. 98 Ví dụ 1.34: f(x) = x1 + 3x3 - 3x4 - 2x5 + 2x6  min - x2 + x3 + 2x4 + x6 = 0 x1 + x2 + x4 + 2x6 = 1 3x2 + 5x4 + x5 + 4x6 = 4 xj >=0, j= 1,6 Giải: Cơ sở Hệ số PA 1 0 3 -3 -2 2 A1 A2 A3 A4 A5 A6 A3 3 0 0 -1 1 2 0 1 A1 1 1 1 1 0 1 0 2 A5 -2 4 0 3 0 5 1 4 -7 0 -8 0 0 0 -5 99 VD1.34  Bài toán có patư duy nhất không? Ví dụ 1.29: Xem lại VD 1.11, 1.13, 1.19, 1.20, 1.25 ta có k < 0 với mọi biến tự do xk : bài toán có patư duy nhất. Xem lại VD 1.23 ta có k > 0 với mọi biến tự do xk : bài toán có patư duy nhất.  Trong trường hợp này: pacbtư duy nhất, patư duy nhất. Mời ghé thăm trang web: 100  https://sites.google.com/a/ueh.edu.vn/phamtricao/  https://sites.google.com/site/phamtricao/