›

Bài giảng Mô hình toán kinh tế - Chương III: Mô hình tối ưu tuyến tính (qhtt)

pdf 67 trang vanle 4600
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Mô hình toán kinh tế - Chương III: Mô hình tối ưu tuyến tính (qhtt)", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_mo_hinh_toan_kinh_te_chuong_iii_mo_hinh_toi_uu_tuy.pdf

Nội dung text: Bài giảng Mô hình toán kinh tế - Chương III: Mô hình tối ưu tuyến tính (qhtt)

  1. CHƯƠNG III MÔ HÌNH TỐI ƯU TUYẾN TÍNH (QHTT) I. Thí dụ mở đầu II. Mô hình bài toán QHTT III. Các tính chất chung của bài toán QHTT IV. Phương pháp đơn hình V. Bài toán đối ngẫu
  2. I. Thí dụ mở đầu • Thí dụ 1: Bài toán lựa chọn danh mục đầu tư - Nội dung: Một công ty đầu tư dự định dùng khoản quỹ đầu tư 500 tỷ đồng để mua một số cổ phiếu trên thị trường chứng khoán. Để phòng ngừa rủi ro công ty đưa ra các yêu cầu về đa dạng hoá danh mục đầu như sau: + Loại cổ phiếu và giới hạn mua: Loại CK Lợi tức Giới hạn mua A 7%/năm 100 tỷ B 8,5%/năm 300 tỷ C 7,8%/năm 250 tỷ D 8,2%/năm 320 tỷ + Tỷ lệ đầu tư vào cổ phiếu A và C phải chiếm ít nhất 55% và cổ phiếu B phải chiếm ít nhất 15% tổng số vốn đầu tư thực hiện - Bài toán: Với số tiền dự kiến đầu tư, hãy xác định một danh mục đầu tư sao cho đảm bảo về đa dạng hoá danh mục đầu tư và đem lại mức lợi tức lớn nhất.
  3. - Mô hình hoá: + Gọi xA, xB, xC, xD là các khoản tiền đầu tư vào các loại chứng khoán A, B, C, D + Các điều kiện về đa dạng hoá danh mục đầu tư: 0 xA 100; 0 xB 300 (1) 0 xC 250, 0 xD 320 (2) xA + xC 0,55(xA + xB+ xC + xD) (3) xB 0,15(xA + xB+ xC + xD) (4) xA + xB+ xC + xD 500 (5) + Mức lợi tức ứng với danh mục đầu tư: Z = 0,07xA + 0,085xB+ 0,078xC + 0,082xD (tỷ đồng) - Xác định x = (xA, xB, xC, xD) sao cho: Z Max; với các điều kiện (1), (2), (3), (4), (5). - Bài toán này gọi là bài toán QHTT
  4. • Thí dụ 2: Bài toán vận tải - Nội dung: Một công ty kinh doanh xăng dầu tại khu vực Z hàng tuần cần cung ứng xăng cho 3 trạm bán lẻ A, B và C. Công ty có thể đưa xăng đến các trạm từ tổng kho I và II. Lượng xăng dự trù cung ứng cho các trạm của kho I là 20 tấn, kho II là 40 tấn. Nhu cầu tiêu thu xăng hàng tuần của các trạm A, B, C lần lượt là 20, 15, 15 (tấn). Chi phí cho việc cung ứng xăng được cho dưới bảng sau: Đơn vị: nghìn đồng/tấn Kho\ Trạm A B C I 500 400 700 II 600 500 500 - Bài toán: Cần lập một kế hoạch cung ứng xăng từ các kho đến các trạm để đảm bảo đáp ứng đủ nhu cầu của các trạm với tổng chi phí vận chuyển là nhỏ nhất.
  5. - Mô hình hoá: + Gọi x1A, x1B, x1C, x2A, x2B, x2C (tấn) lần lượt là các lượng xăng vận chuyển từ kho I, kho II đến các trạm A, B, C. + Điều kiện để đáp ứng đầy đủ nhu cầu của các trạm: x1A + x2A = 20 (1) x1B + x2B = 15 (2) x1C + x2C = 15 (3) + Điều kiện về lượng xăng dự trù cung ứng của các kho: x1A + x1B + x1C 20 (4) x2A + x2B + x2C 40 (5) + Tổng chi phí vận chuyển: Y = 500x1A+400x1B+700x1C+600x2A+500x2B+500x2C (nghìn đồng) - Xác định x1A, x1B, x1C, x2A, x2B, x2C 0 sao cho: Y Min; với các điều kiện (1), (2), (3), (4), (5) Bài toán này gọi là bài toán QHTT
  6. II. Mô hình bài toán QHTT 1. Bài toán dạng tổng quát 2. Một số khái niệm và định nghĩa 3. Các dạng đặc biệt
  7. 1. Bài toán dạng tổng quát - Là bài toán tìm cực trị (cực đại hoặc cực tiểu) của một hàm tuyến tính xác định trên tập hợp nghiệm của một hệ thống hỗn hợp các phương và (hoặc) các bất phương trình tuyến tính. - Xác định véc tơ x = (x1, x2, , xn) sao cho: n f()() x  cj x j Min Max j 1 n aij x j b i () i I1 j 1 n axbiIij j i ( 2 )(*) III 1  2  3  , IIII 1  2  3 j 1 n aij x j b i () i I3 j 1
  8. 2. Một số khái niệm và định nghĩa - Hàm f(x) cần tìm cực trị gọi là hàm mục tiêu của bài toán - Hệ (*) gọi là hệ điều kiện của bài toán - Mỗi phương trình hoặc bất phương trình trong hệ điều kiện gọi là một ràng buộc của bài toán và hệ điều kiện còn gọi là hệ ràng buộc - Véc tơ x thoả mãn mọi ràng buộc của bài toán gọi là một phương án (PA) của bài toán - Tập hợp các PA có thể có của bài toán gọi là tập PA của bài toán, ký hiệu: D = {x: t/m (*)} - Xét bài toán QHTT có f(x) Min và hai PA xA, xB. Khi đó: + Nếu f(xA) f(xB) thì PA xA gọi là không xấu hơn PA xB + Nếu f(xA) < f(xB) thì PA xA gọi là tốt hơn PA xB - Một PA mà tại đó hàm mục tiêu đạt cực trị gọi là PA tối ưu (PATƯ), ký hiệu: x* và f* = f(x*) gọi là trị tối ưu, f(x*) f(x) với mọi PA x của bài toán.
  9. - Một bài toán có ít nhất một PATƯ gọi là bài toán giải được - Một bài toán không có PA TƯ gọi là bài toán không giải được + Bài toán không có PA không có PATƯ + Bài toán có PA nhưng hàm mục tiêu không bị chặn trên tập PA - Xét với PA x: + Nếu ràng buộc i (i I) thoả mãn với dấu “=“ thì PA x gọi là thoả mãn “chặt” ràng buộc i hay ràng buộc i là chặt đối với PA x + Nếu ràng buộc i (i I) thoả mãn với dấu “>” hoặc “<“ thì PA x gọi là thoả mãn “lỏng” ràng buộc i hay ràng buộc i là lỏng đối với PA x - Nếu một ràng buộc có dạng dấu “=“ thì nó là chặt với mọi PA của bài toán - Nếu một ràng buộc có dạng dấu “ “ hoặc “ “ thì nó có thể là lỏng đối với PA này nhưng lại là chặt đối với PA khác
  10. * - Với ràng buộc i ta ký kiệu véc tơ A i = (ai1, ai2, , ain) và tập * * hợp các véc tơ A i (i I) tạo thành một ma trận, ký hiệu: A và gọi là ma trận hệ ràng buộc của bài toán * - Gọi một nhóm các ràng buộc có hệ véc tơ A i tương ứng độc lập tuyến tính gọi là các ràng buộc độc lập tuyến tính - Một PA thoả mãn chặt n ràng buộc độc lập tuyến tính gọi là PA cực biên (PACB) + PACB thoả mãn đúng n ràng buộc gọi là PACB không suy biến + PACB thoả mãn hơn n ràng buộc gọi là PACB suy biến - Một bài toán có tất cả các PACB đều không suy biến gọi là bài toán không suy biến - Một bài toán có ít nhất một PACB suy biến gọi là bài toán suy biến
  11. Ví dụ 1 f( x ) 2 x1 x 2 M in x1 2 x 2 6 (1) x1 x 2 3 (2) x1 0 (3) x 2 0 (4)
  12. 3. Các dạng đặc biệt 3.1. Bài toán dạng chính tắc - Xác định véc tơ x = (x1, x2, , xn) sao cho: n f()() x  cj x j Min Max j 1 n aij x j b i ( i 1  m ) (1) j 1 xj 0( j 1  n ) (2) - Bài toán dạng chính tắc có một hệ phương trình ràng buộc và các biến số đều không âm + (1) là nhóm các ràng buộc dạng phương trình gọi là các phương trình ràng buộc + (2) là nhóm các ràng buộc dạng bất phương trình gọi là các ràng buộc về dấu đối với các biến
  13. - Ký hiệu: A = ((aij))m n gọi là ma trận điều kiện của bài toán Aj là véc tơ cột j của ma trận A- gọi là véc tơ điều kiện j c là véc tơ hệ số của các biến trong hàm mục tiêu b là véc tơ vế phải của hệ phương trình ràng buộc - Khi đó bài toán dạng chính tắc có thể viết dưới dạng n f()() x  cj x j Min Max f()(,)() x c x Min Max j 1 Ax b n x A b hoặc  j j x 0 j 1 xj 0( j 1  n )
  14. Mệnh đề - Mọi bài toán QHTT đều có thể quy về bài toán dạng chính tắc tương đương theo nghĩa trị tối ưu của hai bài toán là như nhau và từ PATƯ của bài toán này có thể suy ra PATƯ của bài toán kia. - Các phép biến đổi tương đương như sau: ’ + Nếu xj 0 thì đặt: xj = - xj 0 ' '' xj x j x j + Nếu xj không có ràng buộc về dấu thì đặt: ' '' xj, x j 0 n p n a x x b + Nếu ràng buộc i có dạng thì biến đổi:  ij j i i  aij x j b i j 1 j 1 p xi 0 n p n a x x b + Nếu ràng buộc i có dạng thì biến đổi:  ij j i i  aij x j b i j 1 j 1 p xi 0
  15. Ví dụ 2 - Cho bài toán QHTT: f( x ) 2 x1 x 2 3 x 3 M in x1 2 x 2 x 3 6 (1) x1 4 x 2 x 3 10 (2) x2 x 3 4 (3) x 0 (4) 1 x 2 0 (5) - Đưa bài toán về dạng chính tắc tương đương
  16. Định lý 1 - PA x của bài toán dạng chính tắc là PACB khi và chỉ khi hệ thống các véc tơ {Aj: xj > 0} là độc lập tuyến tính - Ví dụ 3: Cho bài toán QHTT f( x ) 2 x1 4 x 2 6 x 3 M in 3x1 4 x 2 4 x 3 10 (1) x1 x 2 4 x 3 1 (2) xj 0( j 1  3) Chứng tỏ véc tơ x0 = (2, 1, 0) là PACB bằng hai cách
  17. Nhận xét - Với bài toán dạng chính tắc, không làm mất tính chất tổng quát ta giả thiết hệ phương trình ràng buộc gồm m phương trình độc lập và m n thì bằng phép biến đổi tương đương ta có thể đưa về hệ chỉ có n phương trình và hệ này cũng là hệ Cramer - Từ định lý 1 ta thấy: + Một PACB có tối đa m thành phần dương (?) + Một PACB không suy biến có đúng m thành phần dương (?) + Một PACB suy biến có ít hơn m thành phần dương (?)
  18. Định nghĩa cơ sở của PACB - Xét bài toán dạng chính tắc và PACB x - Gọi m véc tơ {Aj} độc lập tuyến tính bao hàm hệ thống các véc tơ {Aj: xj > 0} là cơ sở của PACB x, ký hiệu một cách quy ước là J - Cơ sở J của PACB x bao hàm 3 nội dung: + Số phần tử của J là m + Hệ véc tơ {Aj: j J} độc lập tuyến tính + {Aj: j J}  {Aj: xj > 0} - Nếu PACB x không suy biến thì có một cơ sở duy nhất: {Aj: j J}  {Aj: xj > 0} - Nếu PACB x suy biến thì có thể có nhiều cơ sở khác nhau mà phần chung của chúng là các véc tơ {Aj: xj > 0} - Với PACB x ta gọi: xj (j J) gọi là thành phần cơ sở của PACB x: xj > 0 j J xk(k J) gọi là thành phần phi cơ sở của PACB x: k J xk = 0
  19. 3.2. Bài toán dạng chuẩn - Là bài toán dạng chính tắc có bi 0 (i) và mỗi phương trình ràng buộc đều có một biến với hệ số bằng 1 và không có mặt ở các phương trình khác. - Xác định véc tơ x = (x1, x2, , xn) sao cho: n f()() x  cj x j M in M ax j 1 x1 a1m 1 x m 1 a 1 n x n b 1 x 2 a2m 1 x m 1 a 2 n x n b 2 x a x a x b m m m 1 m 1 m n n m xj 0( j 1  n ) 0 - Bài toán dạng chuẩn cho ta PACB x = (b1, b2, , bm, 0, , 0) j với cơ sở {Aj: j J}  {e : j = 1m} gọi là cơ sở đơn vị 0 + Nếu bi > 0 (i) thì PACB x là PACB không suy biến 0 + Nếu có ít nhất một bi = 0 thì PACB x PACB suy biến
  20. Ví dụ 4 - Cho bài toán QHTT: f( x ) 2 x1 5 x 2 x 3 M ax 3x1 2 x 3 3 x 4 12 (1) 2x1 x 2 x 3 2 x 4 4 (2) 3x1 4 x 3 x 4 8 (3) xj 0( j 1  4) - Đưa bài toán về dạng chính tắc và dạng chuẩn - Xác định một PACB của bài toán và cho biết tính chất của PACB
  21. III. Các tính chất chung của bài toán QHTT 1. Sự tồn tại của PACB - Nếu bài toán có PA và hạng của ma trận hệ ràng buộc (A*) bằng n thì bài toán có PACB. - Nếu bài toán dạng chính tắc có PA thì chắc chắn có PACB (vì hạng của ma trận hệ ràng buộc luôn bằng n). 2. Tính hữu hạn của số PACB: Số PACB của mọi bài toán QHTT đều hữu hạn. 3. Sự tồn tại PATƯ - Nếu bài toán có PA và f(x) M (bị chặn dưới) với bài toán có f(x) Min và f(x) M (bị chặn trên) với bài toán có f(x) Max trên tập PA thì bài toán có PATƯ, tức là giải được. - Nếu bài toán có PACB và giải được thì phải có PACB tối ưu. Do đó nếu bài toán dạng chính tắc giải được thì có PACB tối ưu. - Nếu bài toán có hơn một PATƯ thì sẽ có vô số PATƯ (?)
  22. IV. Phương pháp đơn hình 1. Nội dung 2. Cơ sở lý thuyết 3. Thuật toán đơn hình 4. Áp dụng thuật toán đơn hình tìm PACB
  23. 1. Nội dung - Xét bài toán không suy biến dạng chính tắc và biết một PACB. - Xuất phát từ PACB, tìm cách đánh giá nó, nếu chưa tối ưu thì tìm cách di chuyển sang một PACB khác tốt hơn. Vì số PACB của bài toán QHTT là hữu hạn nên sau một số hữu hạn bước hoặc sẽ kết luận bài toán không giải được vì trị số hàm mục tiêu không bị chặn trên tập PA hoặc sẽ tìm được PACB tối ưu.
  24. 2. Cơ sở lý thuyết 0 - Xét bài toán dạng chính tắc có PACB x và cơ sở J0: n f() x  cj x j Min j 1 n  xj A j b (1) j 1 xj 0( j 1  n ) (2) 0 0 x j (j J0) là thành phần cơ sở: x j > 0 (j J0) 0 0 x k (k J0) là thành phần phi cơ sở: k J0 x k = 0 - Với PACB x0, ta có: n 0 0 0 0 b  xj A j  x j A j  x k A k  x j A j (*) j 1 j J0 k J 0 j J 0
  25. - Ta có: Ak  x jk A j () k J0 j J0 - Ký hiệu: k  c j x jk c k () k J 0 j J0 - Với x là PA bất kỳ của bài toán, ta có: n b  x A  x A  x A j jj J j j k k j 1 0 k J0 b  x A  x()  x A j Jj jk j J jk j 0k J0 0 b  x A  A  x x j Jj j j J j k jk 0 0 k J0 b ( x  x x ) A ( ) j J jk jk j 0 k J0
  26. Định lý 2: Dấu hiệu tối ưu 0 - Nếu đối với PACB x có cơ sở J0 của bài toán dạng 0 chính tắc mà k 0( k J0 ) thì x là PATƯ 0 + Nếu k 0( k J0 ) thì x là PATƯ duy nhất 0 + Đối với PACB x , cơ sở J0 thoả mãn định lý 2 mà 0 tồn tại k 0( k J 0 ) thì x có thể không phải là PATƯ duy nhất.
  27. Chứng minh - Từ (*) và ( ), ta có 0 0 xj x j  x kx jk x j x j  x k x jk () j J0 k J0 k J 0 n f() x  cj x j c j x j  c k x k j 1 j J0 k J 0 0 f() x cj() x j  x kx jk  c k x k j J0 k J 0 k J 0 0 f() x cj x j  c j  x k x jk  c k x k j J0 j J 0 k J 0 k J 0 0 f() x cj x j ()  c j x jk c k x k j J0 k J 0 j J 0 0 f ()()x f x  k x k k J0
  28. - Như vậy: 0 k 0( k J0 )  k x k 0 f ( x ) f ( x ) k J0 - Bài toán chính tắc có thể quy về bài toán dạng chuẩn: 0 f()() x f x  k x k Min k J0 x  xx x0 () j J j k jk j 0 k J0 xj 0( j 1  n )
  29. - Định lý 3: Dấu hiệu bài toán không giải được 0 Nếu đối với PACB x , cơ sở J0 của bài toán dạng chính tắc mà  k > 0 (k J0) mà xjk 0 (j J0) thì bài toán không giải được vì trị số hàm mục tiêu giảm vô hạn trên tập PA. - Định lý 4: Dấu hiệu cải tiến PA Nếu với mỗi k > 0 (k J0) đều có ít nhất một xjk > 0 (j J0) thì ta có thể chuyển sang một PACB mới, ký hiệu: x1 tốt hơn x0, tức là f(x1) < f(x0).
  30. Chứng minh 0 0 + Với PACB x , cơ sở J0 mà  k 0( k J 0 ) thì theo dấu hiệu tối ưu x chưa phải là PATƯ k k + Với mỗi chỉ số k J0 xác định một véc tơ Z = {zj : j =1m) và gọi là k phương Z theo công thức: xjk () j J 0 k Zj 0( j J0 & j k ) 1(j J0 & j k ) + Xuất phát từ PACB x0 di chuyển theo phương Zk với bước di chuyển 0 k 0  > 0 ta có véc tơ x() = x + Z f(x()) = f(x ) -  k + Ảnh hưởng của phương Zk đến giá trị hàm mục tiêu được đánh giá thông qua k như sau: 0 k +> Nếu k f(x ) Z gọi là phương tăng 0 k +> Nếu k = 0 thì f(x()) = f(x ) thì Z gọi là phương không đổi 0 k +> Nếu k > 0 thì f(x()) < f(x ) Z gọi là phương giảm
  31. k +> Nếu  k > 0 (k J0) và xjk 0 (j J0) thì Z gọi là phương giảm vô hạn của hàm mục tiêu. k +>Nếu với mỗi k > 0 (k J0) đều xjk > 0 (j J0) thì Z gọi là phương giảm hữu hạn của hàm mục tiêu. + Xét Zk là phương giảm hữu hạn: 0 x j  +> Với các x > 0 ta xác định 0 Min , x jk 0  0 jk j J 0 x jk  1 +> Với bước di chuyển 0 ta xác định PA x : 1 0 1 0 0 x = x(0) = x + 0 k và f(x ) = f(x ) - 0 k < f(x ) + PA x1 là PACB mới tốt hơn PACB x0
  32. 3. Thuật toán đơn hình - Áp dụng cho bài toán dạng chính tắc đã biết PACB 0 x , cơ sở J0 ={1,2, ,m}, tức là cơ sở bao gồm m véc tơ {A1, A2, ,Am}. - Thuật toán bao gồm 5 bước như sau: + Bước 1: Lập bảng đơn hình ứng với PACB x0, cơ sở J0 là bảng ghi các hệ số phân tích của véc tơ b và các véc tơ điều kiện qua cơ sở J0 theo mẫu sau:
  33. Bảng đơn hình Hệ Cơ PACB C1 C Cr Cm Cm+1 Ck Cs Cn số sở 2 x1 x2 xr xm xm+1 xk xs xn 0 C1 x1 x 1 1 0 0 0 x1m+1 x1k x1s x1 n 0 C2 x2 x 2 0 1 0 0 x2m+1 x2k x2s x2 n 0 Cr xr x r 0 0 1 0 xrm+1 xrk [xrs] xrn 0 Cm xm x m 0 0 0 1 xmm+1 xmk xms xm n 0 f(x) f(x ) 0 0 0 0 m+1 k s n
  34. + Bước 2: Kiểm tra dấu hiệu tối ưu 0 +> Nếu k 0 (k J0) thì PACB x là PACB tối ưu 0 -> Nếu k Nếu  k = 0 (k J0) thì PACB x có thể là PACB không duy nhất +> Nếu  k > 0 (k J0) thì chuyển sang bước 3 + Bước 3: Kiểm tra tính không giải được của bài toán +> Nếu  k > 0 (k J0) mà xjk 0 (j J0) thì bài toán không giải được vì trị số hàm mục tiêu giảm vô hạn trên tập PA +> Nếu với mỗi k > 0 (k J0) đều có ít nhất một xjk > 0 (j J0) thì chuyển sang bước 4 + Bước 4: Chọn véc tơ đưa vào cơ sở và xác định véc tơ loại khỏi cơ sở +> Giả sử: Max k s khi đó ta đưa véc tơ A vào cơ sở 0 s k 0  0 +> Xác định: x j xr 0 Min , xjs 0  ( r J 0 , x rs 0) j J 0 xjs  x rs khi đó loại véc tơ Ar ra khỏi cơ sở
  35. + Bước 5: Biến đổi bảng đơn hình +> Trong cột cơ sở thay xr bằng xs và trong cột hệ số thay cr bằng cs; dòng r gọi là dòng xoay, cột s gọi là cột xoay, phần tử [xrs] gọi là phần tử trục xoay. +> Chia lần lượt các phần tử nằm trên dòng xoay cho phần tử trục xoay ta thu được một dòng tương ứng ở bảng đơn hình mới gọi là dòng chuẩn. +> Tìm trên dòng cần biến đổi còn lại phần tử thuộc cột xoay, đổi dấu nó, rồi đem nhân với dòng chuẩn, sau đó cộng với chính dòng đó ở bảng đơn hình cũ ta thu đợc một dòng mới tương ứng ở bảng đơn hình mới. +> Dòng ước lượng cũng được biến đổi như một dòng bình thường hoặc xác định lại theo công thức đã có. + Sau bước 5 quay trở lại bước bước 2 và tiếp tục thuật toán với 1 PACB mới x , cơ sở J1. Sau một số hữu hạn bước hoặc sẽ kết luận bài toán không giải được vì trị số hàm mục tiêu giảm vô hạn trên tập PA hoặc sẽ tìm được được PACB tối ưu.
  36. Chú ý - Khi 0 = 0 ta vẫn thực hiện thuật toán một cách bình thường, khi đó kết quả của việc biến đổi sẽ cho ta chuyển sang một cơ sở khác của cùng một PACB suy biến. - Tại bước 4, nếu khi chọn véc tơ đưa vào cơ sở và xác định véc tơ loại khỏi có sở mà có nhiều véc tơ thuộc diện lựa chọn thì ta chọn ngẫu nhiên một trong các véc tơ đó. - Với bài toán có g(x) Max ta đưa về bài toán có f(x) Min bằng cách đổi dấu toàn bộ các hệ số trong hàm mục tiêu. Sau đó áp dụng thuật toán một cách bình thường, tuy nhiên: gmax = - fmin.
  37. Ví dụ 5 - Cho bài toán QHTT: 1 f( x ) 2 x 3 x x x M in 1 2 32 4 1 x x x x 1 8 (1) 1 2 32 4 x 4 x 8 x 8 (2 ) 2 3 4 2x 2 x 3 x 2 0 (3) 2 3 4 xj 0 ( j 1  4 ) - Giải bài toán sau bằng phương pháp đơn hình
  38. Ví dụ 6 - Cho bài toán QHTT: f( x ) x1 4 x 2 3 x 3 Min 2x1 x 2 2 x 3 16 (1) 4x1 2 x 3 28 (2) x 2 x x 12 (3) 1 2 3 xj 0( j 1  3) - Giải bài toán sau bằng phương pháp đơn hình
  39. Ví dụ 7 - Cho bài toán QHTT: f( x ) 2 x1 3 x 2 5 x 3 M in 4x1 x 2 2 x 3 1 2 (1) 1 2x x x 8 ( 2 ) 12 2 3 3 2x x x 2 0 (3 ) 12 2 3 xj 0 ( j 1  3 ) - Giải bài toán sau bằng phương pháp đơn hình
  40. 4. Áp dụng thuật toán đơn hình tìm PACB - Nội dung: Áp dụng cho bài toán dạng chính tắc chưa biết thông tin về PACB. Để áp dụng thuật toán đơn hình cần tìm một PACB và cơ sở tương ứng của nó. - Xét bài toán dạng chính tắc có bi 0 (i): n f() x  cj x j Min j 1 n aij x j b i ( i 1  m ) (1) j 1 ()I xj 0( j 1  n ) (2)
  41. - Từ bài toán này xây dựng bài toán phụ (P): m g g P(,) x x  xi Min i 1 n g  aij x j x i b i ( i 1  m ) j 1 x j 0 (j 1  n ) g xi 0 (i 1  m ) g Trong đó: xi là các biến giả
  42. Nhận xét - Véc tơ x là PA, PACB của bài toán (I) khi và chỉ khi (x, xg = 0) là PA, PACB của bài toán (P). - Bài toán (P) là bài toán chuẩn và P(x, xg) 0 nên luôn giải được. - Ký hiệu PACB tối ưu của bài toán (P) là (,)x xg và g trị tối ưu Pmin = P(,)x x - Có hai trường hợp xảy ra: m g g + Pmin 0  xi 0  x i 0 bài toán (I) không có PA, tức lài 1 không giải. m g g + Pmin 0  xi 0 x i 0(  i ) x là PACB của bài toán (I) i 1
  43. - Ta cần tìm cơ sở của PACB của bài toán (I): + Nếu trong cơ sở của PACB tối ưu của bài toán (P) không có các véc tơ tương ứng với các biến giả thì đó cũng là cơ sở của PACB của bài toán (I). + Nếu trong cơ sở của PACB tối ưu của bài toán (P) có ít nhất một véc tơ tương ứng với các biến giả thì ta loại các cột ứng với các k(P) < 0 và tính lại dòng ước lượng k theo hàm f(x) và tiếp tục thuật toán. - Chú ý: + khi xây dựng bài toán (P) chỉ cần cộng biến giả vào những phương trình cần thiết sao cho bài toán (P) trở thành bài toán chuẩn. + Một biến giả đã bị loại ra khỏi cơ sở thì không cần tính ở các bước tiếp sau.
  44. Thuật toán đơn hình mở rộng - Bước 1: Đưa bài toán QHTT về dạng chính tắc có vế phải không âm + Nếu bài toán dạng chuẩn thì áp dụng thuật toán để giải + Nếu bài toán chưa phải dạng chuẩn thì chuyển sang bước 2 - Bước 2: Xây dựng bài toán phụ (P) tương ứng - Bước 3: Giải bài toán (P) bằng phương pháp đơn hình + Nếu Pmin > 0 thì kết luận bài toán gốc không có PA + Nếu Pmin = 0 thì chuyển sang bước 4 - Bước 4: Tìm cơ sở của PACB của bài toán gốc + Nếu trong cơ sở của PACB tối ưu của bài toán (P) không có các véc tơ tương ứng với các biến giả thì đó cũng là cơ sở của PACB của bài toán (I). + Nếu trong cơ sở của PACB tối ưu của bài toán (P) có ít nhất một véctơ tương ứng với các biến giả thì ta loại các cột ứng với các k(P) < 0 và tính lại dòng ước lượng k theo hàm f(x) và tiếp tục thuật toán.
  45. Ví dụ 7 - Cho bài toán QHTT: f( x ) 2 x1 3 x 2 5 x 3 M in 4x1 x 2 2 x 3 1 2 (1) 1 2x x x 8 ( 2 ) 12 2 3 3 2x x x 2 0 (3 ) 12 2 3 xj 0 ( j 1  3 ) - Giải bài toán sau bằng phương pháp đơn hình
  46. Ví dụ 8 - Cho bài toán QHTT: f( x ) 3 x1 4 x 2 2 x 3 2 x 4 M in 2x1 2 x 2 x 4 2 8 (1) x1 5 x 2 2 x 3 2 x 4 3 1 ( 2 ) 2x 2 x 3 x x 1 6 (3) 1 2 3 4 xj 0 ( j 1  4 ) - Giải bài toán sau bằng phương pháp đơn hình
  47. Ví dụ 9 - Cho bài toán QHTT: 1 f( x ) 2 x 4 x x 3 x M in 1 22 3 4 2x1 2 x 2 2 x 3 3 x 4 5 0 (1) 4x1 8 x 2 2 x 3 3 x 4 8 0 ( 2 ) 4x 4 x x 2 x 4 0 (3) 1 2 3 4 xj 0 ( j 1  4 ) - Giải bài toán sau bằng phương pháp đơn hình
  48. Sơ đồ giải bài toán QHTT BÀI TOÁN KHÔNG CHÍNH TẮC Bài toán chính tắc với bi không âm Kiểm tra Giải bằng thuật Dạng chuẩn toán đơn hình Bài toán phụ (P)  k 0 Xác định Pmin = 0 và mọi ẩn giả được PA tối đều là phi cơ sở Thu ưu Giải bằng hẹp P = 0 và có ẩn giả bài đơn hình min  > 0 và x 0 Bài trong cơ sở toán k jjk với bài toán toán không giải được (P) Pmin > 0 Bài toán chính không có PA (không giải được)
  49. V. Bài toán đối ngẫu 1. Đặt vấn đề 2. Cách thành lập bài toán đối ngẫu 3. Phân tích quan hệ trong cặp bài toán đối ngẫu 4. Các ứng dụng
  50. 1. Đặt vấn đề - Với mỗi bài toán QHTT, theo các quy tắc nhất định ta xây dựng một bài toán QHTT thứ hai và gọi là bài toán đối ngẫu của bài toán đã cho. - Quan hệ giữa hai bài toán này rất chặt chẽ, nếu biết kết quả của bài toán này có thể suy ra được kết quả của bài toán kia.
  51. 2. Cách thành lập bài toán đối ngẫu - Xét bài toán dạng chính tắc và gọi là bài toán gốc n f()() x  cj x j Min Max j 1 n aij x j b i ( i 1  m ) (1) j 1 ()I xj 0( j 1  n ) (2) - Dựa vào bài toán (I) ta xây dựng bài toán QHTT sau: m f()() y  bi y i Max Min i 1 m   aij y i ( ) c j ( j 1  n ) ( I ) i 1 - Bài toán (I  ) gọi là bài toán đối ngẫu của bài toán (I)
  52. Nhận xét - Nếu f(x) Min thì f () y M ax và hệ ràn buộc của bài toán đối ngẫu có dạng “ ” - Nếu f(x) Max thì f () y M in và hệ ràn buộc của bài toán đối ngẫu có dạng “ ” - Số ràng buộc không kể các ràng buộc dấu trong bài toán này bằng số biến số trong bài toán kia - Các hệ số trong hàm mục tiêu của bài toán này là các hệ số ở vế phải của hệ ràng buộc trong bài toán kia - Ma trận điều kiện trong hai bài toán là chuyển vị của nhau. Bài toán gốc Bài toán đối ngẫu c b A b AT c
  53. Cặp ràng buộc đối ngẫu - Gọi hai ràng buộc bất đẳng thức (kể cả rang buộc về dấu) trong hai bài toán cùng tương ứng với một chỉ số là một cặp ràng buộc đối ngẫu. - Các cặp ràng buộc đối ngẫu trong hai bài toán (I) và ( I ) m xj 0  a ij y i c j ( j 1  n ) i 1
  54. Ví dụ 10 - Cho bài toán QHTT sau: f( x ) 5 x1 2 x 2 7 x 3 M in x1 2 x 2 3 x 3 5 (1) 2x1 x 2 2 x 3 6 (2) xj 0( j 1  3) - Viết bài toán đối ngẫu của bài toán trên và chỉ ra các cặp ràng buộc đối ngẫu.
  55. Hai cách viết bài toán đối ngẫu - Cách 1: Đưa bài toán QHTT về dạng chính tắc tương đương, sau đó viết bài toán đối ngẫu của bài toán chính tắc và qui ước gọi đó là bài đối ngẫu của bài toán ban đầu. - Cách 2: Sử dụng lược đồ tổng quát
  56. Lược đồ tổng quát STT Bài toán gốc Bài toán đối ngẫu f( x ) M in ( M ax ) f()() y M ax M in n 1 aij x j b i yi không ràng buộc dấu i 1 n 2 y 0 aij x j () b i i i 1 n 0 3 aij x j () b i yi i 1 m 4 xj 0 aij y i () c j i 1 m 5 x 0 j aij y i () c j i 1 m 6 x không ràng buộc dấu j aij y i c j i 1
  57. Ví dụ 11 - Cho bài toán QHTT: f( x ) 2 x1 x 2 3 x 3 M in x1 2 x 2 x 3 6 (1) x1 4 x 2 x 3 10 (2) x2 x 3 4 (3) x 0 (4) 1 x 2 0 (5) - Viết bài toán đối ngẫu của bài toán trên bằng 2 cách và chỉ ra các cặp ràng buộc đối ngẫu
  58. 3. Mối quan hệ giữa hai bài toán đối ngẫu 3.1. Các tính chất và định lý đối ngẫu - Tính chất 1: Với mọi PA x và y của hai bài toán đối ngẫu có f(x) min và f () y M ax ta luôn có: f()() x f y - Chứng minh: + Xét hai PA x và y bất kỳ của hai bài toán đối ngẫu. + Ta có: m m aij y i c j ( j 1  n ) i 1 xj a ij y i c j x j ( j 1  n ) i 1 xj 0( j 1  n ) n m n m n n xayj  iji  cx jj  axy ijji  cx jj fyfx()() j 1i 1 j 1 i 1 j 1 j 1
  59. - Tính chất 2: Nếu đối với hai PA x* và y* của một cặp bài toán đối ngẫu mà thoả mãn: f ()() x f y thì x* và y* tương ứng là hai PA tối ưu. - Chứng minh: + Xét cặp bài toán f(x) Min và f() y M ax + Lấy một PA x bất kỳ của bài toán gốc + Theo tính chất 1, ta có: f()()() x f y f x x là PA tối ưu + Lấy một PA y bất kỳ của bài toán đối ngẫu + Theo tính chất 1, ta có: f()()() y f x f y y là PA tối ưu
  60. - Định lý 1: Nếu một trong hai bài toán giải được thì bài toán kia cũng giải được và khi đó với mọi cặp PATƯ x* và y* ta luôn có: f()() x f y - Hệ quả 1: Điều kiện cần và đủ để hai bài toán đối ngẫu giải được là mỗi bài toán có ít nhất một PA. - Chứng minh: + Giả sử: Hai bài toán giải được, khi đó hai bài toán có PATƯ, tức là mỗi bài toán có ít nhất một PA. (đpcm) + Giả sử: Mỗi bài toán có một PA x0 và y0. + Khi đó: với mỗi PA x bất (nếu có) của bài toán gốc ta có: f()() x f y 0 tức là hàm mục tiêu bị chặn. Như vậy, bài toán gốc giải được và theo định lý 1 bài toán đối ngẫu cũng giải được (đpcm).
  61. - Hệ quả 2: Điều kiện cần và đủ để một bài toán có PA còn một bài toán không có PA là trị số hàm mục tiêu của bài toán có PA không bị chặn trên tập PA của nó. - Chứng minh: + Giả sử: bài toán gốc có PA còn bài toán đối ngẫu không có PA, tức là bài toán đối ngẫu không giải được và theo định lý 1 bài toán gốc không giải đươc vì trị số hàm mục tiêu không bị chặn trên tập PA (đpcm). + Giả sử: bài toán gốc có PA và trị số hàm mục tiêu không bị chặn, tức là bài toán gốc không giải được và theo định lý 1 bài toán đối ngẫu không giải được vì không có, bởi vì, nếu bài đối ngẫu có PA thì theo hệ quả 1 hai bài toán đều giải được (trái với GT) (đpcm).
  62. Nhận xét Với một cặp bài toán đối ngẫu chỉ xảy ra một trong ba trường hợp - Trường hợp 1: Cả hai bài toán đều không có PA thì hai bài toán cùng không giải được - Trường hợp 2: Một bài toán có PA và một bài toán không có PA thì cả hai bài toán cùng không giải được - Trường hợp 3: Cả hai bài toán đều có PA thì cả hai bài toán cùng giải được
  63. - Định lý 2: Điều kiện cần và đủ để hai PA x và y của một cặp bài toán đối ngẫu tối ưu là trong các cặp ràng buộc đối ngẫu, nếu một ràng buộc thoả lỏng thì ràng buộc kia phải thoả mãn chặt. m m a y c - Nếu xj > 0 thì  a ij y i c j hoặc  ij i j thì xj = 0 i 1 i 1 - Hệ quả: Nếu một ràng buộc là lỏng đối với PATƯ của bài toán này thì ràng buộc đối ngẫu với nó phải là chặt đối với mọi PATƯ của bài toán kia.
  64. 3.2. Các ứng dụng - Khảo sát sự tồn tại của PA và PA tối ưu: + Sử dụng các tính chất và định lý 1 ta có thể khảo sát sự tồn tại của PA, PATƯ của cặp bài toán đối ngẫu mà không cần thiết phải giải. + Ví dụ 12: Cho bài toán QHTT f( x ) 2 x1 x 2 x 3 2 x 4 M in x1 x 2 15 (1) x3 x 4 8 (2) xj 0( j 1  4) Hãy viết bài toán đối ngẫu của bài toán trên và chứng tỏ bài toán đối ngẫu đó có PATƯ.
  65. + Ví dụ 13: Cho bài toán QHTT fx( ) 2 x1 2 x 2 px 3 2 xx 4 5 Max 2x1 x 2 x 4 x 5 4 p 1 (1) x2 x 3 2 x 4 x 5 32 (2) x1 x 2 x 3 x 5 18 (3) x3, x 4 0 Trong đó: p là tham số Hãy viết bài toán đối ngẫu của bài toán trên và dựa vào bài toán này để biện luận theo p về sự tồn tại PATƯ của bài toán gốc.
  66. - Phân tích tính chất của véc tơ x đối với bài toán: + Sử dụng hệ quả của định lý 2 để phân tích tính chất tối ưu của một PA. Ví dụ: cần phân tích xem x có phải là PATƯ của bài toán gốc hay không. + Các phân tích như sau: +> Giả sử x là PATƯ của bài toán gốc thì theo định lý 2 mọi PATƯ của bài toán đối ngẫu phải thoả mãn chặt các ràng buộc đối ngẫu với các ràng buộc mà x thoả mãn lỏng. Tập hợp các ràng buộc chặt này tạo thành một hệ phương trình đối với véc tơ y +> Giải hệ phương trình này: -> Nếu hệ vô nghiệm thì x không phải là PATƯ -> Nếu hệ có nghiệm thì ta thử lần lượt các nghiệm này vào các ràng buộc còn lại của bài toán đối ngẫu TH1: Nếu mọi nghiệm đều không thoả mãn thì x không phải là PATƯ TH2: Nếu có nghiệm y thoả mãn thì y là PATƯ của bài toán đối ngẫu vã cũng là PATƯ của bài toán gốc
  67. + Ví dụ 14: Cho bài toán QHTT (I) f( x ) 3 x1 x 2 px 3 M in 2x1 2 x 2 x 3 6 x1 2 x 2 2 x 3 2 ( I ) xj 0( j 1, 2, 3) Trong đó: p là tham số +> Hãy viết bài toán đối ngẫu của bài toán (I) và chỉ ra các cặp ràng buộc đối ngẫu +> Tìm P để véc tơ y = (0, ½) là PATƯ