›
›

Bài giảng Quy hoạch tuyến tính - Nguyễn Đức Phương

pdf 114 trang phuongnguyen 2410
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Quy hoạch tuyến tính - Nguyễn Đức Phương", để 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_quy_hoach_tuyen_tinh_nguyen_duc_phuong.pdf

Nội dung text: Bài giảng Quy hoạch tuyến tính - Nguyễn Đức Phương

  1. BỘ CÔNG THƯƠNG TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP TP. HCM Nguyễn Đức Phương Bài giảng Quy hoạch tuyến tính MSSV: Họtên: TP. HCM – Ngày 27 tháng 6 năm 2011
  2. Mục lục Mục lục i 1 Giới thiệu quy hoạch tuyến tính 1 1.1 Mộtsốvídụdẫnđếnbàitoánquyhoạchtuyếntính . . . . . 1 1.2 Cácdạngcủabàitoánquyhoạchtuyếntính . . . . . . . . . . 5 1.2.1 Bài toán quy hoạch tuyến tính dạng tổng quát . . . . . 5 1.2.2 Bàitoánquyhoạchtuyếntínhdạngchuẩn . . . . . . . 5 1.2.3 Bài toánquyhoạchtuyếntínhdạng chính tắc . . . . . 6 1.3 Quanhệdạngchuẩnvàchínhtắc . . . . . . . . . . . . . . . . 8 1.3.1 Đổichiềubấtđẳngthứccủacácràngbuộc . . . . . . . 8 1.3.2 Biếnkhôngràngbuộc . . . . . . . . . . . . . . . . . . 9 1.3.3 Quanhệdạngchuẩn,chínhtắc . . . . . . . . . . . . . 10 1.4 Dạngmatrậncủabàitoánquyhoạch . . . . . . . . . . . . . 13 1.5 Phươngánchấpnhậnđược . . . . . . . . . . . . . . . . . . . 14 1.6 Ý nghĩa hình họccủa bài toánquy hoạchtuyếntính . . . . . 16 1.6.1 Phươngphápđồthị 16 1.6.2 Tính chất của tập phương án chấp nhận được . . . . . 17 1.7 Điểmcựcbiên 21 1.8 Phươngáncơbảnchấpnhậnđược . . . . . . . . . . . . . . . 22 1.8.1 Nghiệm cơ bản của Ax D b 23 1.8.2 Thànhlậpphươngáncựcbiên. . . . . . . . . . . . . . 26 1.8.3 Phươngáncựcbiênvàphươngántốiưu . . . . . . . . 30
  3. MỤC LỤC ii 1.9 Bàitậpchương1 31 2 Phương pháp đơn hình 33 2.1 Phương pháp đơn hình cho bài toán quy hoạch dạng chuẩn . . 33 2.1.1 Phươngáncựcbiênbanđầu. . . . . . . . . . . . . . . 36 2.1.2 Dấuhiệutốiưu 37 2.1.3 Chọnbiếnvàocơsở 40 2.1.4 Chọnbiếnrakhỏicơsở . . . . . . . . . . . . . . . . . 41 2.1.5 Lậpbảngđơnhìnhmới. . . . . . . . . . . . . . . . . . 42 2.2 Thuậttoánđơnhìnhchobàitoánmin . . . . . . . . . . . . . 50 2.3 Bàitoánchínhtắckhôngcósẵnmatrậnđơnvị . . . . . . . . 52 2.4 Bàitậpchương2 58 3 Lý thuyết đối ngẫu 64 3.1 Vídụdẫnđếnbáitoánđốingẫu . . . . . . . . . . . . . . . . 64 3.1.1 Bàitoánđốingẫucủabàitoánmax. . . . . . . . . . . 66 3.1.2 Bàitoánđốingẫucủabàitoánmin . . . . . . . . . . . 68 3.2 Cácđịnhlývềđốingẫu 71 3.3 Bàitậpchương3 79 4 Bài toán vận tải 83 4.1 Bàitoánvậntảicânbằngthuphát . . . . . . . . . . . . . . . 83 4.2 Phươngáncựcbiêncủabàitoánvậntải . . . . . . . . . . . . 85 4.3 Cácphươngphápthànhlậpphươngáncựcbiên . . . . . . . . 89 4.3.1 Phươngphápcướcphíthấpnhất . . . . . . . . . . . . 89 4.3.2 PhươngphápgócTâyBắc . . . . . . . . . . . . . . . 90 4.3.3 PhươngphápVogel(Fogel) . . . . . . . . . . . . . . . 90 4.4 Thuậttoánthếvịgiảibàitoánvậntải . . . . . . . . . . . . . 92 4.4.1 Thuậttoánquykhôngcướcphíôchọn . . . . . . . . . 92 4.4.2 Xâydựngphươngáncựcbiênmới . . . . . . . . . . . 97
  4. MỤC LỤC iii 4.5 Mộtsốtrườnghợpđặcbiệtcủabàitoánvậntải . . . . . . . . 101 4.5.1 Bàitoánvận tảikhôngcânbằng thuphát . . . . . . . 101 4.5.2 Bàitoánvậntảicóôcấm . . . . . . . . . . . . . . . . 103 4.6 Bàitoánvậntảicựcđạicướcphí . . . . . . . . . . . . . . . . 105 4.7 Bàitậpchương4 106 Tài liệu tham khảo 110
  5. Chương 1 Giới thiệu quy hoạch tuyến tính 1.1 Một số ví dụ dẫn đến bài toán quy hoạch tuyến tính Ví dụ 1.1 (Bài toán lập kế hoạch sản xuất). Một trại cưa các khúc gỗ thành các tấm ván. Có hai loại ván: ván thành phẩm và ván sử dụng trong xây dựng. Giả sử, đối với:  Ván thành phẩm cần 2 giờ để cưa và 5 giờ để bào 10m ván.  Ván xây dưng cần 3 giờ để cưa và 3 giờ để bào 10m ván. Máy cưa làm việc tối đa 8 giờ trong ngày, và máy bào làm việc tối đa 15 giờ trong ngày. Nếu lợi nhuận của 10m ván thành phẩm là 120 (ngàn đồng), và lợi nhuận của 10m ván xây dựng là 100 (ngàn đồng). Trong ngày, trại cưa phải cưa bao nhiêu ván mỗi loại để lợi nhuận lớn nhất? Giải.
  6. 1.1Mộtsốvídụdẫnđếnbàitoánquyhoạchtuyếntính 2 Ví dụ 1.2 (Bài toán khẩu phần ăn). Chuyên gia dinh dưỡng định thành lập một thực đơn gồm 2 loại thực phẩm chính A và B. Cứ một (trăm gram):  Thực phẩm A chứa 2 đơn vị chất béo, 1 đơn vị carbohydrate và 4 đơn vị protein.  Thực phẩm B chứa 3 đơn vị chất béo, 3 đơn vị carbohydrate và 3 đơn vị protein. Nếu một (trăm gram) thực phẩm A giá 20 (ngàn đồng) và một (trăm gram) thực phẩm B giá 25 (ngàn đồng). Nhà dinh dưỡng muốn thức ăn phải cung cấp ít nhất 18 đơn vị chất béo, 12 đơn vị carbohydrate và 24 đơn vị protein. Bao nhiêu (trăm gram) thực phẩm mỗi loại để có giá nhỏ nhất nhưng vẫn cung cấp đủ dinh dưỡng? Giải.
  7. 1.1Mộtsốvídụdẫnđếnbàitoánquyhoạchtuyếntính 3 Ví dụ 1.3 (Bài toán vận tải). Một nhà sản xuất có 2 nhà máy: Một nhà máy ở Vĩnh Phúc và một nhà máy ở Bình Dương. Có 3 kho hàng phân phối sản phẩm đặt ở Hà Nội, TP. HCM và Cần Thơ. Nhà máy ở Vĩnh phúc; Bình Dương, có khả năng cung cấp tối đa 100; 140 tấn mỗi tuần. Lượng cầu của các kho ở Hà Nội, TP. HCM và Cần Thơ lần lượt từ 100; 60 và 80 tấn trở lên. Chi phí vận chuyển (trăm ngàn) mỗi tấn cho như bảng bên dưới. Hỏi cần vận chuyển bao nhiêu tấn hàng hóa từ nhà sản xuất đến các kho hàng ở Hà Nội, TP. HCM và ở cần thơ để chi phí nhỏ nhất nhưng vẫn đáp ứng đủ nhu cầu?
  8. 1.1Mộtsốvídụdẫnđếnbàitoánquyhoạchtuyếntính 4 ``` ``` ``` Trạm thu Hà Nội TP. HCM Cần thơ ``` ``` Trạm phát ``` W1:100 W2:60 W3:80 Vĩnh PhúcQ1: 100 5 7 9 Bình DươngQ2:140 8 7 10 Giải.
  9. 1.2Cácdạngcủabàitoánquyhoạchtuyếntính 5 1.2 Các dạng của bài toán quy hoạch tuyến tính 1.2.1 Bài toán quy hoạch tuyến tính dạng tổng quát Từ các ví dụ mục 1.1, bài toán quy hoạch tuyến tính tổng quát được phát biểu như sau: Tìm x1; x2;:::;xn sao cho z D c1x1 C c2x2 CC cnxn ! max .hay min/ (1.1) Với các ràng buộc a11x1 C a12x2 C  C a1nxn  ./.D/ b1 a x C a x C  C a x  ./.D/ b 8 21 1 22 2 2n n 2 : : : : (1.2) ˆ : : : : <ˆ am1x1 C am2x2 C  C amnxn  ./.D/ bm ˆ ˆ Hàm tuyến tính: (1.1) gọi là hàm mục tiêu. Hệ bất phương trình tuyến tính (1.2) gọi là các ràng buộc. Vế trái của các ràng buộc là các hàm tuyến tính với x1; x2;:::;xn là các biến số. 1.2.2 Bài toán quy hoạch tuyến tính dạng chuẩn Chúng ta nói bài toán quy hoạch tuyến tính có dạng chuẩn nếu nó có dạng như sau: Tìm x1; x2;:::;xn sao cho z D c1x1 C c2x2 CC cnxn ! max;.hay min/ (1.3) Với các ràng buộc a11x1 C a12x2 C  C a1nxn  b1 a x C a x C  C a x  b 8 21 1 22 2 2n n 2 : : : : (1.4) ˆ : : : : <ˆ am1x1 C am2x2 C  C amnxn  bm ˆxj  0;j D 1;2;:::;n (1.5) :ˆ
  10. 1.2Cácdạngcủabàitoánquyhoạchtuyếntính 6 1.2.3 Bài toán quy hoạch tuyến tính dạng chính tắc Chúng ta nói bài toán quy hoạch tuyến tính có dạng chính tắc nếu nó có dạng như sau: Tìm x1; x2;:::;n sao cho z D c1x1 C c2x2 CC cnxn ! max;.hay min/ (1.6) Với các ràng buộc a11x1 C a12x2 C  C a1nxn D b1 a x C a x C  C a x D b 8 21 1 22 2 2n n 2 : : : : (1.7) ˆ : : : : <ˆ am1x1 C am2x2 C  C amnxn D bm ˆxj  0;j D 1;2;:::;n (1.8) :ˆ Ví dụ 1.4. Cho biết dạng của các bài toán quy hoạch tuyến tính sau: a. z D 3x1 C 2x2 ! min Với các ràng buộc 2x1 C x2  4 3x 2x  6  1 2 x1  0; x2  0 b. z D 2x1 C 3x2 C 4x3 ! max Với các ràng buộc 3x1 C 2x2 3x3  4 2x C 3x C 2x  6 8 1 2 3 < 3x1 x2 C 2x3  8 x1  0; x2  0; x3  0 : c. z D 3x1 C 2x2 C 3x3 2x4 ! max Với các ràng buộc 2x1 C 6x2 C 2x3 4x4 D 7 3x C 2x 5x C x D 8 8 1 2 3 4 < 6x1 C 7x2 C 2x3 C 5x4  4 x1  0; x2  0; x3  0; x4  0 : d. z D 2x1 C 5x2 C x3 C x4 C 4x5 ! min Một số sách có định nghĩa khác về dạng chuẩn và dạng chính tắc. Các bạn cần đọc kỹ định nghĩa khi tham khảo các tài liệu khác.
  11. 1.2Cácdạngcủabàitoánquyhoạchtuyếntính 7 Với các ràng buộc 3x1 C 2x2 x3 C 2x5 D 4 4x C 5x C 3x C 2x D 7  1 2 3 4 x1  0; x2  0; x3  0; x4  0; x5  0 e. z D 2x1 C 5x2 ! max Với các ràng buộc 3x1 C 2x2  6 2x C 9x  8  1 2 x1  0 f. z D 2x1 C 3x2 ! min Với các ràng buộc 2x1 C x2 x3 D 4 3x C 2x C x D 8 8 1 2 3 < x1 x2 D 6 x1  0; x2  0 : Chú ý. Bài toán tìm giá trị nhỏ nhất của hàm mục tiêu có thể viết thành bài toán tìm giá trị lớn nhất của hàm mục tiêu và ngược lại. Điều này các bạn sẽ thấy qua quan hệ: n n min c x D max c x (1.9) j j 0 j j 1 j D1 j D1 X X tương đương @ A min z D max.z/ (1.10) Do đó, không mất tính tổng quát trong phần lý thuyết ta chỉ phát biểu bài toán tìm giá trị lớn nhất của hàm mục tiêu .max z/. Bài toán tìm giá trị nhỏ nhất hàm mục tiêu .min z/ thì có thể sử dụng (1.10). Ví dụ 1.5. Chuyển các bài toán quy hoạch tuyến tính tìm max hàm mục tiêu thành tìm min hàm mục tiêu hay ngược lại a. z D 2x1 C 3x2 C 4x3 ! max Với các ràng buộc 3x1 C 2x2 3x3  4 2x C 3x C 2x  6 8 1 2 3 < 3x1 x2 C 2x3  8 x1  0; x2  0; x3  0 :
  12. 1.3 Quan hệ dạng chuẩn và chính tắc 8 b. z D 3x1 C 2x2 ! min Với các ràng buộc 2x1 C x2  4 3x 2x  6  1 2 x  0;y  0 Giải. 1.3 Quan hệ dạng chuẩn và chính tắc 1.3.1 Đổi chiều bất đẳng thức của các ràng buộc Nếu ta nhân hai vế của bất phương trình k1x1 C k2x2 CC knxn  b với 1 ta được bất phương trình k1x1 k2x2  knxn b
  13. 1.3 Quan hệ dạng chuẩn và chính tắc 9 Ví dụ 1.6. Chuyển bài toán quy hoạch tuyến tính sau sang dạng chuẩn: z D 2x1 C 3x2 C 4x3 ! max Với các ràng buộc 3x1 C 2x2 3x3  4 2x C 3x C 2x  6 8 1 2 3 < 3x1 x2 C 2x3  8 x  0; x  0; x  0 :1 2 3 Giải. 1.3.2 Biến không ràng buộc Ta biết, một số bất kỳ chính là hiệu của hai số không âm. Giả sử xj không C có ràng buộc không âm, chúng ta có thể thay xj bằng hai biến xj  0 và xj  0 sao cho C xj D xj xj Với cách này chúng ta có thể chuyển bài toán không có ràng buộc không âm thành bài toán có ràng buộc không âm. Ví dụ 1.7. Chuyển bài toán quy hoạch tuyến tính sau sang dạng chuẩn z D 2x1 C 5x2 ! max (1.11) Với các ràng buộc 3x C 2x  6 1 2 (1.12) 2x C 9x  8  1 2 x1  0 (1.13)
  14. 1.3 Quan hệ dạng chuẩn và chính tắc 10 Giải. Nhận xét. Mọi bài toán quy hoạch tuyến tính đều có thể chuyển đổi thành dạng chuẩn bằng các cách như trên. 1.3.3 Biến đổi bài toán quy hoạch dạng chuẩn thành dạng chính tắc Xét ràng buộc thức i trong bài toán quy hoạch tuyến tính dạng chuẩn ai1x1 C ai2x2 CC ainxn  bi (1.14) Chúng ta có thể chuyển ràng buộc (1.14) thành phương trình tuyến tính bằng cách thêm vào biến phụ xnCi  0; và ai1x1 C ai2x2 CC ainxn C xnCi D bi (1.15) Bài toán quy hoạch tuyến tính dạng chuẩn chuyển thành dạng chính tắc có dạng như sau z D c1x1 C c2x2 CC cnxn ! max Với các ràng buộc a11x1 C  C a1nxn C xnC1 D b1 a x C  C a x C x D b 8 21 1 2n n nC2 2 : : : ˆ : : : <ˆ am1x1 C  C amnxn C xnCm D bm ˆx1  0;:::;xn  0; xnC1  0;:::;xnCm  0 :ˆ
  15. 1.3 Quan hệ dạng chuẩn và chính tắc 11 Ví dụ 1.8. Chuyển bài toán quy hoạch tuyến tính sau sang dạng chính tắc z D 120x1 C 100x2 ! max Với các ràng buộc 2x1 C 3x2  8 5x C 3x  15  1 2 x1  0; x2  0 Giải. Ví dụ 1.9. Chuyển các bài toán quy hoạch tuyến tính sau sang dạng chính tắc a. z D 3x1 C 2x2 ! min Với các ràng buộc 2x1 C x2  4 3x 2x  6  1 2 x1  0; x2  0
  16. 1.3 Quan hệ dạng chuẩn và chính tắc 12 b. z D 2x1 C 3x2 C 4x3 ! max Với các ràng buộc 3x1 C 2x2 3x3  4 2x C 3x C 2x  6 8 1 2 3 < 3x1 x2 C 2x3  8 x1  0; x2  0; x3  0 : c. z D 3x1 C 2x2 C 3x3 2x4 ! max Với các ràng buộc 2x1 C 6x2 C 2x3 4x4 D 7 3x C 2x 5x C x D 8 8 1 2 3 4 < 6x1 C 7x2 C 2x3 C 5x4  4 x1  0; x2  0; x3  0; x4  0 : d. z D 2x1 C 5x2 ! max Với các ràng buộc 3x1 C 2x2  6 2x C 9x  8  1 2 x1  0
  17. 1.4Dạngmatrậncủabàitoánquyhoạch 13 e. z D 2x1 C 3x2 ! min Với các ràng buộc 2x1 C x2 x3 D 4 3x C 2x C x D 8 8 1 2 3 < x1 x2 D 6 x1  0; x3  0 : 1.4 Dạng ma trận của bài toán quy hoạch Xét bài toán quy hoạch dạng chuẩn: z D c1x1 C c2x2 CC cnxn ! max Với các ràng buộc a11x1 C a12x2 C  C a1nxn  b1 a x C a x C  C a x  b 8 21 1 22 2 2n n 2 : : : : ˆ : : : : <ˆ am1x1 C am2x2 C  C amnxn  bm ˆxj  0;j D 1;2;:::;n :ˆ
  18. 1.5 Phương án chấp nhận được 14 Đặt a11 a12    a1n x1 b1 c1 a21 a22    a2n x2 b2 c2 A D 0 : : : 1 ; x D 0 : 1 ; b D 0 : 1 ; c D 0 : 1 : : : : : : B C B C B C B C B am1 am2    amn C B xn C B bm C B cn C B C B C B C B C Chúng@ ta có thể viết bàiA toán quy@ hoạchA trên thành@ dạngA ma trận:@ TìmA x 2 Rn sao cho z D cT x ! max Với các ràng buộc Ax  b x  0 Ví dụ 1.10. Viết bài toán quy hoạch tuyến tính sau dưới dạng ma trận. z D 120x1 C 100x2 ! max Với các ràng buộc 2x1 C 3x2  8 5x C 3x  15  1 2 x1  0; x2  0 Giải. 1.5 Phương án chấp nhận được Định nghĩa 1.1 (Phương án chấp nhận được). Véctơ x 2 Rn thỏa tất cả các ràng buộc của bài toán quy hoạch tuyến tính được gọi là phương án chấp nhận được.
  19. 1.5 Phương án chấp nhận được 15 Ví dụ 1.11. Cho bài toán quy hoạch tuyến tính: z D 120x1 C 100x2 ! max Với các ràng buộc 2x1 C 3x2  8 5x C 3x  15  1 2 x1  0; x2  0 và các phương án: 1 2 1 2 x D ; x D ; x D ; x D 1 2 2 1 3 3 4 2         Phương án nào là phương án chấp nhận được? Giải. Định nghĩa 1.2 (Phương án tối ưu). Phương án chấp nhận được làm cho hàm mục tiêu có giá trị lớn nhất (nếu là bài toán max) hay nhỏ nhất (nếu là bài toán min) thì được gọi là phương án tối ưu.
  20. 1.6 Ý nghĩa hình học của bài toán quy hoạch tuyến tính 16 1.6 Ý nghĩa hình học của bài toán quy hoạch tuyến tính Trong phần này ta xét đến phương pháp giải bài toán quy hoạch tuyến tính bằng hình học. Phương pháp hình học chỉ giải bài toán quy hoạch tuyến tính hai hoặc ba biến. Tuy nhiên, ý nghĩa của phương pháp này cho ta ý tưởng để xây dựng thuật toán đại số có thể giải được bài toán rất lớn sẽ được trình bày trong chương 2. 1.6.1 Phương pháp đồ thị giải bài toán quy hoạch tuyến tính Ví dụ 1.12. Giải bài toán quy hoạch tuyến tính z D 4x C 3y ! max Với các ràng buộc x C y  4 5x C 3y  15  x  0;y  0 Giải.
  21. 1.6 Ý nghĩa hình học của bài toán quy hoạch tuyến tính 17 Ví dụ 1.13. Giải bài toán quy hoạch tuyến tính z D 2x C 5y ! max Với các ràng buộc 3x C 2y  6 x C 2y  2  x  0;y  0 Giải. 1.6.2 Tính chất của tập phương án chấp nhận được Định nghĩa 1.3 (Đoạn thẳng). Đoạn thẳng nối hai điểm x1 và x2 được định nghĩa n fx 2 R jx D x1 C .1 /x2; 0    1g (1.16)
  22. 1.6 Ý nghĩa hình học của bài toán quy hoạch tuyến tính 18 Theo đó, nếu  D 0 chúng ta có x2, và nếu  D 1 chúng ta có x1. Những điểm thuộc đoạn thẳng với 0<<1 được gọi là các điểm trong của đoạn, và x1 và x2 được gọi là điểm biên của đoạn thẳng. x1 b x2 x D x1 C .1 /x2 Hình 1.1: x1; x2 là hai điểm biên, x là điểm trong Định lý 1.4. Cho x1 và x2 là hai phương án chấp nhận được của bài toán quy hoạch tuyến tính. Điểm x D x1 C .1 /x2;0    1, trên đoạn nối hai điểm x1 và x2: Khi đó i. x cũng là phương án chấp nhận được. T T T T T ii. Nếu các giá trị hàm mục tiêu c x1 D c x2 thì c x D c x1 D c x2: T T T T iii. Nếu các giá trị hàm mục tiêu c x1 < c x2 thì c x < c x2: Chứng minh. Giả sử bài toán quy hoạch tuyến tính có ràng buộc aT x  b: T T Vì x1 và x2 là hai phương án chấp nhận được cho nên a x1  b và a x2  b: i. Với x D x1 C.1/x2;0<<1, trên đoạn nối hai điểm x1 và x2; chúng ta có T T a x D a .x1 C .1 /x2/ T T D a x1 C .1 /a x2  b C .1 /b < b Do x thỏa ràng buộc cho nên x cũng là phương án chấp nhận được. Vậy, các điểm trên đoạn nối hai phương án chấp nhận được là các phương án chấp nhận được. ii. Theo i), x là phương án chấp nhận được. T T c x D c .x1 C .1 /x2/ T T D c x1 C .1 /c x2 T T D c x2 D c x1 Vậy các phương án chấp nhận được cùng thuộc một đoạn thẳng thì cùng giá trị hàm mục tiêu.
  23. 1.6 Ý nghĩa hình học của bài toán quy hoạch tuyến tính 19 iii. Với x D x1 C .1 /x2;0<<1, trên đoạn nối hai điểm x1 và x2; chúng ta có T T c x D c .x1 C .1 /x2/ T T D c x1 C .1 /c x2 T T T < c x2 C .1 /c x2 D c x2 Từ định lý này, xét tập các phương án chấp nhận được là đoạn thẳng nối bởi hai điểm x1; x2 thì một điểm biên có giá trị hàm mục tiêu lớn nhất và điểm biên còn lại có giá trị hàm mục tiêu nhỏ nhất. Ví dụ 1.14. Xem lại bài toán quy hoạch tuyến tính như ví dụ 1.12 trang 16. z D 4x C 3y ! max Với các ràng buộc x C y  4 5x C 3y  15  x  0;y  0 y y 4 A 4 A z=3 B b x1 B b x1 2 2 b b x x b x b 2 C x2 C x x 0 2 0 2 (a) (b) Hình 1.2: T T a. Ta thấy x1 D .1=2I 2/; x2 D .2I 1=2/ là phương án chấp nhận được và điểm x thuộc đoạn nối hai điểm x1; x2: Điểm x định bởi 2 x D x C .1 / x ;  D 1 2 3 cũng là phương án chấp nhận được, xem hình 1.2a.
  24. 1.6 Ý nghĩa hình học của bài toán quy hoạch tuyến tính 20 T T b. Cho hai phương án chấp nhận được x1 D .1=2I 7=3/ và x2 D .2I 1=3/ có cùng giá trị hàm mục tiêu là .z=3 D 3/ ; thì phương án x thuộc đoạn nối hai điểm x1x2: Điểm x định bởi 2 x D x C .1 / x ;  D 1 2 3 cũng cùng giá trị hàm mục tiêu là .z=3 D 3/ ; xem hình 1.2b. Định nghĩa 1.5 (Tập lồi). Tập S 2 Rn được gọi là tập lồi nếu với hai điểm phân biệt bất kỳ x1 và x2 thuộc S thì đoạn nối hai điểm x1 và x2 cũng nằm trong tập S: Ví dụ 1.15. Các tập con của R2 trong hình 1.3 là các tập lồi. Các tập con của R2 trong hình 1.4 không phải là tập lồi. C D C x1 b b x1 b x1 b x b A 2 x2 x2 b A B B (a) (b) (c) y y b x x1 x1 2 b b bb b x2 b x2 x1 x x (d) (e) (f) Hình 1.3: b x 2 b x2 b x2 b b x1 x1 b x1 (a) (b) (c) Hình 1.4: Định lý 1.6. Tập tất cả các phương án chấp nhận được S D fxjAx D b; x  0g của bài toán quy hoạch tuyến tính dạng chính tắc là một tập lồi.
  25. 1.7 Điểm cực biên 21 Chứng minh. Gọi x1; x2 2 S là hai phương án chấp nhận được, theo định lý 1.4(i) thì x D x1 C .1 /x2 cũng là phương chấp nhận được. Do đó x 2 S; hay S là tập lồi 1.7 Điểm cực biên Định nghĩa 1.7 (Tổ hợp lồi). Điểm x 2 Rn là tổ hợp lồi của r điểm n x1; x1;:::; xr trong R nếu tồn tại 1; 2;:::;r  0; 1 C 2 CC r D 1 sao cho x D 1x1 C 2x2 CC r xr: Định lý 1.8. Tập chứa tất các tổ hợp lồi của hữu hạn các điểm trong Rn là một tập lồi. Chứng minh. Gọi S là tập chứa tất cả các tổ hợp lồi của r điểm x1; x1;:::; xr trong Rn: Lấy x; y 2 S r x D 1x1 C 2x2 CC r xr; i D 1; i >0 iD0 X r 0 0 0 0 0 y D 1x1 C 2x2 CC r xr; i D 1; i >0 iD0 X Điểm thuộc đoạn nối hai điểm x; y có dạng z D x C .1 /y 0 0 0 0 0 0 D .1 C 1 1/x1I .2 C 2 2/x2I : : : I .r C r r /xr   r 0 0 0 0 Ta thấy i C i i D 1; i C i i > 0: Cho nên z 2 S; hay S iD1 là tập lồi.P Định nghĩa 1.9 (Điểm cực biên của tập lồi). Điểm x của tập lồi S được gọi là điểm cực biên của S nếu x không là tổ hợp lồi của hai điểm của S khác x: Ví dụ 1.16. Tập lồi như hình 1.5, các điểm A;B;C;D và E là điểm cực biên.
  26. 1.8 Phương án cơ bản chấp nhận được 22 C B A D E 0 Hình 1.5: Nhận xét. Từ định nghĩa điểm cực biên, ta thấy điểm x 2 S là điểm cực biên nếu x D x1 C .1 /x2; x1; x2 2 S; >0 thì x1 D x2 D x: Định nghĩa 1.10 (Phương án cực biên). Điểm cực biên của tập các phương án chấp nhận được còn gọi là phương án cực biên. 1.8 Phương án cơ bản chấp nhận được Trong phần này ta sẽ kết hợp ý tưởng của phương pháp hình học và phương án cực biên được trình bày trong phần 1.6 và 1.7 để giải bài toán quy hoạch tuyến tính bằng công cụ đại số. Ta sẽ thấy vai trò quan trọng của phương án cực biên trong việc tìm phương án tối ưu của hàm mục tiêu thông qua định lý 1.18. Do điểm cực biên rất khó xác định bằng phương pháp hình học khi bài toán quy hoạch có từ ba biến trở lên. Cho nên phần này sẽ trình bày phương pháp đại số để tìm phương án cực biên. Các khái niệm được trình bày trong phần này là nghiệm cơ bản, phương án cơ bản, phương án cơ bản chấp nhận được. Để có thể định nghĩa phương án cơ bản, trước hết ta xét bài toán quy hoạch tuyến tính dạng chính tắc z D cT x ! max (1.17) Với các ràng buộc Ax D b (1.18) x  0 (1.19)
  27. 1.8 Phương án cơ bản chấp nhận được 23 Trong đó A là ma trận cấp m  n; c 2 Rn; và b 2 Rm: Đặt các cột của ma trận A là A1; A2;:::; An: Ràng buộc (1.18) được viết thành x1A1 C x2A2 CC xnAn D b (1.20) Ta có hai giả sử về ma trận A W  Thứ nhất là m  n:  Thứ hai là ma trận A có m dòng độc lập tuyến tính. Nghĩa là hạng của A là m; khi đó trong n cột của A sẽ có m cột độc lập tuyến tính. Hai giả sử này đúng cho bài toán quy hoạch tuyến tính dạng chính tắc được biến đổi từ bài toán quy hoạch tuyến tính dạng chuẩn. 1.8.1 Nghiệm cơ bản của Ax D b Nghiệm cơ bản của Ax D b được xây dựng như sau: (1) ChọnŽ tập T gồm m cột độc lập tuyến tính của A (Chọn cơ sở cho Rm). (2) n m biến tương ứng với các cột còn lại cho bằng không. (3) Phương trình Ax D b được viết lại x1A1 C x2A2 CC xnAn D b (1.21) Trong đó Ai là cột thứ i của A: Đặt i1;i2;:::;im là chỉ số các biến không cho bằng bằng không. Hệ phương trình (1.21) được viết gọn xi1 Ai1 C xi2 Ai2 CC xim Aim D b (1.22) hệ này có m phương trình, m ẩn có duy nhất một nghiệm. (4) Nghiệm của hệ này kết hợp với n m thành phần ta cho bằng không ở trên được gọi là nghiệm cơ bản của Ax D b: Ví dụ 1.17. Cho hệ phương trình tuyến tính bốn ẩn như sau x1 C x2 C x3 D 4 5x C 3x C x D 15  1 2 4 Tìm tất cả nghiệm cơ bản. Ž m Sẽ có nhiều nhất Cn tập T
  28. 1.8 Phương án cơ bản chấp nhận được 24 Giải.
  29. 1.8 Phương án cơ bản chấp nhận được 25 Trong một nghiệm cơ bản bất kỳ, n m biến có giá trị cho bằng không được gọi là biến không cơ bản, và m biến giải được gọi là biến cơ bản. Nghiệm cơ bản là nghiệm của hệ phương trình Ax D b nên nó không cần phải thỏa điều kiện x  0; và do đó nghiệm cơ bản không nhất thiết phải là phương án chấp nhận được của bài toán quy hoạch tuyến tính. (1.17), (1.18) và (1.19). Định nghĩa 1.11 (Phương án cơ bản chấp nhận được). Xét bài toán quy hoạch tuyến tính dạng chính tắc có tập các ràng buộc S D fxjAx D b; x  0g, nghiệm cơ bản của Ax D b thỏa điều kiện x  0 được là phương án cơ bản chấp nhận được. Ví dụ 1.18. Tìm tất cả các phương án cơ bản chấp nhận được của z D 4x1 C 3x2 ! max Với các ràng buộc x1 C x2 C x3 D 4 5x C 3x C x D 15  1 2 4 xj  0; j D 1;:::;4 Giải.
  30. 1.8 Phương án cơ bản chấp nhận được 26 1.8.2 Thành lập phương án cực biên Tập m cột độc lập tuyến tính của A lập thành một cơ sở của Rm: Không mất tính tổng quát, ta giả sử m cột cuối của A độc lập tuyến tính. Gọi S D fxjAx D b; x  0g là tập lồi các phương án chấp nhận được của (1.17), (1.18) và (1.19). 0 0 0 Định lý 1.12. Giả sử m cột cuối của A; được ký hiệu A1; A2;:::; Am là độc lập tuyến tính và 0 0 0 0 0 0 x1A1 C x2A2 CC xmAm D b (1.23) 0 trong đó xi  0; 8i D 1;2;:::;m: Khi đó điểm 0 0 0 x D .0;0;:::;0;x1; x2;:::;xm/ là phương án cực biên (điểm cực biên của S). Chứng minh. Dễ dàng ta có x là phương án chấp nhận được của bài toán quy hoạch tuyến tính (1.17), (1.18) và (1.19). Giả sử x không là điểm cực biên của S: Khi đó x là điểm trong của một đoạn thuộc S: Nghĩa là có hai điểm phân biệt u; v 2 S khác x và số ;0<<1 sao cho x D u C .1 /v (1.24) Trong đó 0 0 0 u D .u1;u2;:::;unm;u1;u2;:::;um/  0 và 0 0 0 v D .v1;v2;:::;vnm;v1;v2;:::;vm/  0 Từ (1.24) chúng ta có 0 D ui C .1 /vi ; 1  i  n m 0 (1.25) xj D ui C .1 /vi ; 1  j  m Bởi vì ui ;vi và ;1  là các số dương cho nên ui D 0 và vi D 0 với i D 1;2;:::;n m: u là phương án chấp nhận được nên 0 0 0 0 0 0 u1A1 C u2A2 CC unAn D b (1.26) Lấy (1.23) trừ cho (1.26) ta được 0 0 0 0 0 0 0 0 0 .x1 u1/A1 C .x2 u2/A2 CC .xn un/An D b
  31. 1.8 Phương án cơ bản chấp nhận được 27 0 0 0 Bởi vì A1; A2;:::; Am độc lập tuyến tính, nên 0 0 xi D vi ; 81  i  m hay x D u; suy ra giả thiết x ¤ u là sai. Vậy x là điểm cực biên của S: Nhận xét. Chứng minh x D .x1;:::;xn/ là phương án cực biên:  Kiểm x là phương án chấp nhận được.  Đặt T D fAj jxj >0g; trong đó Aj là các véctơ cột của A:  Nếu các véctơ của T là độc lập tuyến tính thì x là phương án cực biên. Ví dụ 1.19. Chứng minh xT D .1;2;3;0/ là phương án cực biên của bài toán z D4x1 C 3x2 C 7x3 C 8x4 ! min Với các ràng buộc 3x1 C 3x2 C 4x3 C 5x4 D 21 7x x C x C 6x D 8 8 1 2 3 4 < 2x1 x2 C 5x3 C 2x4 D 15 x  0; j D 1;:::;4 :j Giải.
  32. 1.8 Phương án cơ bản chấp nhận được 28 Định nghĩa 1.13. 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 được gọi là không suy biến nếu số thành phần dương của nó là m: Nếu số thành phần dương ít hơn m thì gọi là phương án cực biên suy biến. Định lý 1.14. Nếu x D .x1; x2;:::;xn/ là phương án cực biên của tập các phương án S D fxjAx D b; x  0g thì các cột của A tương ứng xj > 0 độc lập tuyến tính. Chứng minh. Để đơn giản, ta sắp xếp và đánh số lại các cột của A và các 0 0 0 thành phần của x sao cho k thành phần cuối của x, ký hiệu x1; x2;:::;xk là các số dương. Vậy phương trình (1.20) được viết 0 0 0 0 0 0 x1A1 C x2A2 CC xkAk D b (1.27) 0 0 0 Ta cần chứng minh rằng A1; A2;:::; Ak là độc lập tuyến tính. Ta chứng minh bằng phản chứng, giả sử chúng không độc lập tuyến tính. Nghĩa là tồn tại c D .c1;c2;:::;ck/ ¤ 0 sao cho 0 0 0 c1A1 C c2A2 CC ckAk D 0 (1.28) Nhân (1.28) với hằng số d >0, đầu tiên cộng kết quả với (1.27) ta được phương trình (1.29), sau đó trừ kết quả với (1.27) ta được phương trình (1.30). 0 0 0 0 0 0 .x1 C dc1/A1 C .x2 C dc2/A2 CC .xk C dck/Ak D b (1.29) 0 0 0 0 0 0 .x1 dc1/A1 .x2 C dc2/A2 CC .xk dck/Ak D b (1.30) Bây giờ ta chọn hai điểm trong Rn, 0 0 0 v D .0;0;:::;0;x1 C dc1; x2 C dc2;:::;xk C dck/ và 0 0 0 w D .0;0;:::;0;x1 dc1; x2 dc2;:::;xk dck/ Bởi vì d là hằng số dương bất kỳ, ta chọn như sau: 0 xj 0<d< min ; cj ¤ 0 j jcj j
  33. 1.8 Phương án cơ bản chấp nhận được 29 Với cách chọn d như trên, ta thấy k thành phần sau của v; w là các số dương. Mặc khác, từ (1.29) và (1.30) ta cũng có v; w là phương án chấp nhận được. Nhưng ta lại có 1 1 x D v C w; 2 2 trái với giả thiết ban đầu x là điểm cực biên. Vậy giả sử k cột cuối của A độc lập tuyến tính là sai. Hệ quả 1.15. Số phương án cực biên của tập phương án chấp nhận được S D fxjAx D b; x  0g là hữu hạn. Chứng minh. Bởi vì số hệ có m véctơ cột độc lập tuyến tính là hữu hạn, nên theo định lý 1.14 thì số phương án cực biên của S là hữu hạn. Hệ quả 1.16. Số thành phần dương của một phương án cực biên tối đa là m: Chứng minh. Theo định lý 1.14, các cột của A tương ứng với các thành phần dương của phương án cực biên x 2 S là độc lập tuyến tính trong Rm. Nhưng không thể có nhiều hơn m véctơ độc lập tuyến tính trong Rm: Do đó số thành phần dương của một phương án cục biên tối đa là m: Định lý 1.17 (Tương đương giữa phương án cực biên và phương án cơ bản chấp nhận được). x là điểm cực biên của S D fxjAx D b; x  0g khi và chỉ khi x là phương án cơ bản chấp nhận được. Ví dụ 1.20. Tìm tất cả các phương án cực biên của z D 4x1 C 3x2 ! max Với các ràng buộc x1 C x2 C x3 D 4 5x C 3x C x D 15  1 2 4 xj  0; j D 1;:::;4 Giải.
  34. 1.8 Phương án cơ bản chấp nhận được 30 1.8.3 Quan hệ giữa phương án cực biên và phương án tối ưu Định lý 1.18. Nếu bài toán quy hoạch tuyến tính dạng chính tắc có phương án tối ưu thì sẽ có một phương án cực biên là phương án tối ưu. Nhận xét. Nhờ định lý 1.18, nếu ta chứng minh được bài toán quy hoạch tuyến tính dạng chính tắc có phương án tối ưu, thì nó sẽ có phương án cực biên là phương án tối ưu. Trên đây chúng ta có thể tìm được tất cả các phương án cực biên (vì số phương án cực biên là hữu hạn theo hệ quả). Do đó trong số các phương án cực biên vừa chỉ ra, lần lượt thử từng phương án ta được phương án tối ưu. Ràng buộc của bài toán quy hoạch tuyến tính dạng chính tắc Ax D b là một hệ m phương trình tuyến tính n ẩn. Định lý 1.12 và 1.14 cho ta mối quan hệ giữa điểm cực biên của tập các phương án chấp nhận được S D fxjAx D b; x  0g và sự độc lập tuyến tính các cột của A: Định lý 1.19. Điều kiện cần và đủ để bài toán quy hoạch tuyến tính dạng chính tắc có phương án tối ưu là tập các phương án không rỗng và hàm mục tiêu bị chặn trên (nếu là bài toán max) hoặc bị chặn dưới (nếu là bài toán min). Ví dụ 1.21. Giải bài toán quy hoạch tuyến tính z D 4x1 C 3x2 ! max Với các ràng buộc x1 C x2 C x3 D 4 5x C 3x C x D 15  1 2 4 xj  0; j D 1;:::;4 Giải. Bài toán quy hoạch này có các phương án cực biên
  35. 1.9 Bài tập chương 1 31 Nghiệm cơ bản Phương án cực biên Giá trị hàm mục tiêu x1 D .3=2I 5=2I 0I 0/ x1 D .3=2I 5=2I 0I 0/ x2 D .3I 0I 1I 0/ x2 D .3I 0I 1I 0/ x3 D .4I 0I 0I5/ x4 D .0I 5I1I 0/ x5 D .0I 4I 0I 3/ x5 D .0I 4I 0I 3/ x6 D .0I 0I 4I 15/ x6 D .0I 0I 4I 15/ 1.9 Bài tập chương 1 Bài tập 1.1. Bằng phương pháp hình học giải bài toán quy hoạch tuyến tính z D4x1 C 3x2 ! min Với các ràng buộc x1 C x2  6 2x C 3x  6 8 1 2 < x1 x2  2 x ; x  0 :1 2 Đáp án: Phương án tối ưu xT D .6I 0/ giá trị hàm mục tiêu z D10:
  36. 1.9 Bài tập chương 1 32 Bài tập 1.2. Cho bài toán quy hoạch tuyến tính: z D2x1 C 6x2 C 4x3 2x4 C 3x5 ! max Với các ràng buộc x1 C 2x2 C 4x3 D 52 4x C 2x C x D 60 8 2 3 4 < x1 C 3x2 C x5 D 36 x  0; j D 1;:::;5 :j Chứng minh xT D .0I 34=3I 22=3I 0I 2/ là phương án cực biên. Bài tập 1.3. Cho bài toán quy hoạch tuyến tính z D x1 2x2 C 2x3 ! min Với các ràng buộc x1 C x2 D 6 2x C x D 8  2 3 xj  0; j D 1;2;3 a. Tìm tất cả các phương án cực biên. b. Tìm phương án tối ưu. Đáp án: T T a. Phương án cực biên x1 D .2I 4I 0/ I x2 D .6I 0I 8/ b. Phương án tối ưu xT D .2I 4I 0/
  37. Chương 2 Phương pháp đơn hình 2.1 Phương pháp đơn hình cho bài toán quy hoạch dạng chuẩn Xét bài toán quy hoạch tuyến tính dạng chuẩn z D c1x1 C c2x2 CC cnxn ! max (2.1) Với các ràng buộc a11x1 C a12x2 C  C a1nxn  b1 a x C a x C  C a x  b 8 21 1 22 2 2n n 2 : : : : (2.2) ˆ : : : : <ˆ am1x1 C am2x2 C  C amnxn  bm ˆxj  0;j D 1;2;:::;n (2.3) :ˆ ta đặt a11 a12    a1n x1 b1 c1 a21 a22    a2n x2 b2 c2 A D 0 : : : 1 ; x D 0 : 1 ; b D 0 : 1 ; c D 0 : 1 : : : : : : B C B C B C B C B am1 am2    amn C B xn C B bm C B cn C B C B C B C B C @ A @ A @ A @ A Bài toán có dạng ma trận z D cTx ! max (2.4) Với các ràng buộc Ax  b (2.5) x  0 (2.6)
  38. 2.1 Phương pháp đơn hình cho bài toán quy hoạch dạng chuẩn 34 Trong phần này ta giả sử b  0; phần 2.3 sẽ trình bày bài toán cho trường hợp b không không âm. Bây giờ ta sẽ biến đổi bài toán sang dạng chính tắc bằng cách thêm m ẩn phụ. z D c1x1 C c2x2 CC cnxn ! max Với các ràng buộc a11x1 C  C a1nxn CxnC1 D b1 a x C  C a x Cx D b 8 21 1 2n n nC2 2 : : : ˆ : : : <ˆ am1x1 C  C amnxn CxnCm D bm ˆx1  0;:::;xn  0; xnC1  0;:::;xnCm  0 :ˆ Ta viết bài toán dưới dạng ma trận z D cTx ! max (2.7) Với các ràng buộc 0 A x D b (2.8) x  0 (2.9) 0 trong đó A là ma trân m  .m C n/ có dạng a11 a12    a1n 1 0    0 0 a21 a22    a2n 0 1    0 A D 0 : : : : : : 1 : : : : : : B C B am1 am2    amn 0 0    1 C B C 0 0 @ A Gọi S D fA x D b; x  0g là tập lồi các phương án chấp nhận được của bài toán quy hoạch tuyến tính (2.7), (2.8), (2.9). Theo 1.8 chương 1 thì phương án cơ bản chấp nhận được của bài toán quy hoạch tuyến tính là điểm cực 0 biên của S 0 Định nghĩa 2.1 (Cực biên liền kề). Hai điểm cực biên khác nhau trong S được gọi là liền kề nếu chúng chỉ khác nhau một cặp biến cơ bản. Ví dụ 2.1. Xem lại ví dụ 1.21 trang 31, các điểm cực biên .3=2I 5=2I 0I 0/;.3I 0I 1I 0/;.0I 4I 0I 3/;.0I 0I 4I 15/:
  39. 2.1 Phương pháp đơn hình cho bài toán quy hoạch dạng chuẩn 35 Hai điểm cực biên .3=2I 5=2I 0I 0/ và .3I 0I 1I 0/ là liền kề bởi vì biến cơ bản của điểm cực biên thứ nhất là x1; x2 và biến cơ bản của điểm cực biên thứ hai là x1; x3: Hai điểm cực biên .3I 0I 1I 0/;.0I 4I 0I 3/ không liền kề. Năm 1947, nhà toán học George Bernard Danzig đưa ra phương pháp đơn hình, là phương pháp bắt đầu xét từ một điểm cực biên ban đầu (phương án cơ bản chấp nhận được) lần lươt xét đến các điểm cực biên liền kề sao cho làm tăng giá trị hàm mục tiêu. Quá trình tiến hành đến lúc thu được phương án tối ưu hoặc giá trị hàm mục tiêu không hữu hạn. Phương pháp đơn hình có ba bước: (1) Thành lập một phương án cực biên (2) Xét xem phương án cực biên hiện hành đã là phương án tối ưu hay chưa. Nếu phương án cực biên này là phương án tối ưu thì kết thúc. Ngược lại sang bước (3) (3) Tìm phương án cực biên liền kề sao cho giá trị hàm mục tiêu lớn hơn hoặc bằng giá trị hàm mục tiêu của phương án cực biên trước đó. (4) Quay về bước (2). Để minh họa phương pháp đơn hình ta xét bài toán dạng chuẩn. z D 4x1 C 3x2 ! max (2.10) Với các ràng buộc x C x  4 1 2 (2.11) 5x C 3x  15  1 2 xj  0;j D 1;2 (2.12) Chuyển bài toán sang dạng chính tắc: Giải.
  40. 2.1 Phương pháp đơn hình cho bài toán quy hoạch dạng chuẩn 36 2.1.1 Phương án cực biên ban đầu Để bắt đầu phương pháp đơn hình, ta phải tìm một phương án cực biên chấp nhận được. Với giả sử bT D .4I 5/  0 ta tìm phương án cực biên rất dễ dàng, chỉ việc cho tất cả các biến không cơ bản bằng x1 D x2 D 0. Ta tìm: x3 D 4; x4 D 15 Phương án cực biên ban đầu là: .x1I x2I x3I x4/ D .0I 0I 4I 15/ Để thuận tiện cho việc lập bảng đơn hình, ta viết hàm mục tiêu 2.10 như sau 4x1 3x2 C z D 0 (2.13) Ở đây ta xem z là cũng một biến, mặc khác x1 D x2 D 0 nên giá trị hàm mục tiêu bây giờ z D 0: Bảng đơn hình cho như bảng 2.1 x1 x2 x3 x4 z x3 1 1 1 0 0 4 x4 5 3 0 1 0 15 4 3 0 0 1 0 Bảng 2.1: Nhận xét. Các dòng trong bảng đơn hình: i. Dòng đầu tiên liệt kê tên biến x1; x2; x3; x4 và z tương ứng cho từng cột. ii. Dòng hai và ba là các hệ số của hai ràng buộc (2.11). iii. Dòng cuối liệt kê hệ số cj của hàm mục tiêu (2.10). iv. Cột đầu tiên bên trái cho biết biến x3; x4 là biến cơ bản của dòng một và hai. v. Phần tử ở dòng cuối, cột cuối là giá trị hàm mục tiêu.
  41. 2.1 Phương pháp đơn hình cho bài toán quy hoạch dạng chuẩn 37 Chú ý. Trong bảng đơn hình, biến cơ bản có các tính chất: i. Biến cơ bản chỉ xuất hiện trong một phương trình (ràng buộc) và biến cơ bản này có hệ số là C1: ii. Cột có biến cơ bản toàn là số 0 trừ số C1 là hệ số của biến cơ bản. iii. Giá trị của biến cơ bản là giá trị nằm cùng dòng ở cột cuối. iv. Hệ số của biến cơ bản ở hàm mục tiêu , cj D 0. Đến đây bài toán quy hoạch đã được chuyển sang bảng đơn hình. Bảng đơn hình thể hiện tất cả thông tin của các ràng buộc, hàm mục tiêu, phương án cực biên và giá trị của hàm mục tiêu tương ứng. Bảng đơn hình tổng quát của bài toán quy hoạch (2.7), (2.8), (2.9) cho như bảng 2.8. x1 x2    xn xnC1 xnC2    xnCm z xnC1 a11 a12    a1n 1 0    0 0 b1 xnC2 a21 a22    a2n 0 1    0 0 b2 : : : : : : : : : : : : : : : : : : xnCm am1 am2    amn 0 0    1 0 bm c1 c2  cn 0 0    0 1 0 Bảng 2.2: 2.1.2 Dấu hiệu tối ưu Tiếp tục, ta sẽ tìm hiểu dấu hiệu để xác định phương án cực biên trong bảng có làm hàm mục tiêu tối ưu chưa? Trong ví dụ này, chúng ta có thể tăng giá trị của z D 4x1 C 3x2 C 0x3 C 0x4 không cơ bản cơ bản bằng cách tăng giá trị của biến„ khôngƒ‚ cơ„ bảnƒ‚ (hiện tai x1 D x2 D 0). Tổng quát, một hàm mục tiêu ta có thể viết z D cj xj C 0  xj (2.14) khôngX cơ bản cơX bản Bây giờ giá trị của z có thể được tăng lên bằng cách tăng giá trị của biến không cơ bản có hệ số hàm mục tiêu âm trong bảng đơn hình từ giá trị 0.
  42. 2.1 Phương pháp đơn hình cho bài toán quy hoạch dạng chuẩn 38 Nếu làm điều này thì phải có một biến cơ bản khác (giá trị biến này khác không) trở thành biến không cơ bản (giá trị bằng không) bởi vì số biến cơ bản không thay đổi. Việc đổi giá trị của một biến cơ bản về giá trị 0 thì không làm thay đổi giá trị của hàm mục tiêu bởi vì hệ số hàm mục tiêu của biến cơ bản là 0. Đến đây ta có dấu hiệu tối ưu như sau: Định lý 2.2 (Dấu hiệu tối ưu). Nếu hệ số hàm mục tiêu của bảng đơn hình là không .cj D 0/ đối với biến cơ bản và không âm .cj  0/ đối với biến không cơ bản thì phương án cực biên hiện thời trong bảng đơn hình là phương án ưu. Định lý 2.3 (Dấu hiệu có phương án cực biên tốt hơn). Nếu hệ số hàm mục tiêu của bảng đơn hình là không .cj D 0/ đối với biến cơ bản và âm .cj < 0/ đối với biến không cơ bản sẽ có phương án cực biên khác tốt hơn, nghĩa là làm giá trị hàm mục tiêu lớn hơn. Nhận xét. Nếu trong bảng đơn hình:  cj  0; 8j thì phương án cực biên hiện thời là phương án tối ưu.  Có cj < 0 thì phương án cực biên hiện thời không là phương án tối ưu. Ví dụ 2.2. Cho bài toán quy hoạch tuyến tính z D7x1 C 26x2 9x3 ! max Với các ràng buộc x1 2x2 D 5 x C x D 7  2 3 xj  0; j D 1;2;3 a. Chứng minh xT D .5I 0I 7/ là phương án cực biên. b. Xét xem xT có là phương án cực biên tối ưu của bài toán hay không. Giải.
  43. 2.1 Phương pháp đơn hình cho bài toán quy hoạch dạng chuẩn 39 Ví dụ 2.3. Cho bài toán quy hoạch tuyến tính z D 5x1 x2 19x3 16x4 ! max Với các ràng buộc x1 C x2 C 2x3 3x4 D 5 2x x C x C 5x D 2 8 1 2 3 4 < 3x1 C 4x2 C 7x3 8x4 D 9 x  0; j D 1;:::;4 :j Chứng minh xT D .25=13I 64=13I 0I 8=13/ là phương án cực biên, tối ưu của bài toán đã cho. Giải.
  44. 2.1 Phương pháp đơn hình cho bài toán quy hoạch dạng chuẩn 40 2.1.3 Chọn biến vào cơ sở Giả sử bảng đơn hình bây giờ có cj 0 hay trong bảng đơn hình thì cj < 0: Vậy ta chọn biến xv vào cơ sở nếu min cj Icj <0 Dcv Cột chứa biến vào cơ sở được˚ gọi là cột xoay # x1 x2 x3 x4 z x3 1 1 1 0 0 4 x4 5 3 0 1 0 15 4 3 0 0 1 0 Bảng 2.3:
  45. 2.1 Phương pháp đơn hình cho bài toán quy hoạch dạng chuẩn 41 2.1.4 Chọn biến ra khỏi cơ sở Giải (2.11) cho x3; x4 ta có x3 D 4 x1 x2 (x4 D 15 5x1 3x2 Ta tăng giá trị của x1 và giữ nguyên giá trị của x2 D 0 x3 D 4 x1 (2.15) (x4 D 15 5x1 Từ (2.15) cho thấy, khi tăng giá trị của x1 thì x3; x4 giảm. Vậy vấn đề là x tăng đến giá trị nào? Nhớ lại rằng x3; x4  0 do đó ta tăng giá trị x1 sao cho: x3 D 4 x1  0 (2.16) (x4 D 15 5x1  0 Giải (2.16) ta được x1  4=1 (x1  15=5 D 3 Ta thấy rằng, ta chỉ có thể tăng giá trị của x1 đến minf4I 3gD 3. Phương án cực biên bây giờ là x1 D 3; x2 D 0; x3 D 1; x4 D 0 Phương án này là phương án liền kề với phương án trước. Biến cơ bản bây giờ là x1 và x3; biến không cơ bản bây giờ là x2 và x4: Biến ra khỏi cơ sở trong trường hợp này là x4; xem bảng 2.4. # x1 x2 x3 x4 z x3 1 1 1 0 0 4 x4 5 3 0 1 0 15 4 3 0 0 1 0 Bảng 2.4:
  46. 2.1 Phương pháp đơn hình cho bài toán quy hoạch dạng chuẩn 42 Dòng chứa x4 của bảng đơn hình gọi là dòng xoay, phần tử nằm trên dòng xoay và cột xoay gọi là phần tử trực. Trong ví dụ của ta phần tử trực là (5). # x1 x2 x3 x4 z x3 1 1 1 0 0 4 x4 (5) 3 0 1 0 15 4 3 0 0 1 0 Bảng 2.5: Nhận xét. Giả sử xv là biến vào cơ sở. Nếu bi br min I a >0 D a iv a  iv  rv thì biến xr là biến ra khỏi cơ sở. 2.1.5 Lập bảng đơn hình mới Đến đây, ta đã xác định được biến mới vào cơ sở và biến ra khỏi cơ sở, lúc này:  Biến cơ bản là x1; x3  Biến không cơ bản là x2; x4 x1 x2 x3 x4 z x3 x1 Bảng 2.6: Vì x1 là biến cơ bản mới trong dòng hai của ràng buộc nên:  Hệ số của x1 trong ràng buộc thứ hai là 1. Ta chia hai vế của ràng
  47. 2.1 Phương pháp đơn hình cho bài toán quy hoạch dạng chuẩn 43 buộc thứ hai cho phần tử trực (là 5). 3 1 x C x C x D 3 (2.17) 1 5 2 5 4  Biến x1 không có mặt trong ràng buộc thứ nhất và hàm mục 3 1 tiêu. Để có điều này, ta thay x D 3 x x trong 2.17 vào ràng 1 5 2 5 4 buộc thứ nhất 3 1 3 x x C x C x D 4 (2.18) 5 2 5 4 2 4 tương đương 2 1 x C x x D 1 (2.19) 5 2 3 5 4 và hàm mục tiêu 3 4 x C x C z D 12 (2.20) 5 2 5 4 Ta có bảng đơn hình mới như bảng 2.7. x1 x2 x3 x4 z x3 0 2/5 1 1/5 0 1 x1 1 3/5 0 1/5 0 3 0 3/5 0 4/5 1 12 Bảng 2.7: Nhận xét. Tóm tắt thuật toán đơn hình: # x1    xv    xn xnC1    xnCm z xnC1 a11    a1v    a1n 1    0 0 b1 : : : : : : : : : : : : : : : : : : : : : : xr ar1    .arv/    arn 0    0 0 br : : : : : : : : : : : : : : : : : : : : : : xnCm am1    amv    amn 0    1 0 bm c1  cv  cn 0    0 1 0 Bảng 2.8:
  48. 2.1 Phương pháp đơn hình cho bài toán quy hoạch dạng chuẩn 44 Bước 1: Chọn biến vào cở sở. Nếu min cj Icj 0 với mọi j thì phương án cực biên hiện j ˚ thời là phương án tối ưu. Bước 2: Chọn biến ra cở sở. Nếu bi br min I a >0 D a iv a  iv  rv thì biến xr là biến ra khỏi cơ sở. Ngược lại, nếu không tìm được biến ra khỏi cơ sở thì bài toán không có phương án tối ưu. Bước 3: Lập bảng đơn hình mới. Ta đã xác định biến xv là biến vào và xr là biến ra khỏi cơ sở. Ta lập bảng đơn hình mới  Xác định phần tử trực arv:  Chia dòng chứa phần tử trực cho phần tử trực.  Các phần tử dòng i cột j khác của bảng được tính a a a D ij iv =a D a a a a =a ij a a rv ij rv rj iv rv ˇ rj rvˇ ˇ ˇ  ˇ ˇ Ví dụ 2.4. Giải lại chi tiếtˇ bài toánˇ z D 4x1 C 3x2 ! max Với các ràng buộc x1 C x2 C x3 D 4 5x C 3x C x D 15  1 2 4 xj  0; j D 1;:::;4 được minh họa trong ví dụ trên bằng thuật toán đơn hình. Giải.
  49. 2.1 Phương pháp đơn hình cho bài toán quy hoạch dạng chuẩn 45 Nhận xét. Trong các bảng đơn hình, cột chứa z không thay đổi qua các bước lặp. Do đó, để đơn giản ta sẽ không ghi cột z trong bảng đơn hình. Ví dụ 2.5. Giải bài toán quy hoạch tuyến tính z D 2x1 3x2 C x3 ! max Với các ràng buộc x1 5x2 C x3  15 3x C 2x 2x  20 8 1 2 3 < 4x1 C x3  10 x  0; j D 1;2;3 :j Giải.
  50. 2.1 Phương pháp đơn hình cho bài toán quy hoạch dạng chuẩn 46
  51. 2.1 Phương pháp đơn hình cho bài toán quy hoạch dạng chuẩn 47 Ví dụ 2.6. Giải bài toán quy hoạch tuyến tính z D 2x1 C 3x2 C x3 ! max Với các ràng buộc x1 5x2 C x3 D 6 2x C 2x  7 8 1 2 < x1 C 2x2  5 x  0; j D 1;2;3 :j Giải.
  52. 2.1 Phương pháp đơn hình cho bài toán quy hoạch dạng chuẩn 48 Ví dụ 2.7. Giải bài toán quy hoạch tuyến tính z D2x1 x2 C x3 C x4 ! max Với các ràng buộc x1 C x2 C 2x3 x4 D 2 2x 7x C 3x C x D 3 8 2 3 4 5 < 3x3 C 2x4 C x6 D 7 x  0; j D 1;:::;6 :j Giải.
  53. 2.1 Phương pháp đơn hình cho bài toán quy hoạch dạng chuẩn 49 Ví dụ 2.8. Giải bài toán quy hoạch tuyến tính dạng chuẩn z Dx1 C 2x2 2x3 C x4 x5 C 2x6 ! min Với các ràng buộc 2x1 x2 5x3 C x4 D 5 x 2x C 2x C x D 4 8 1 2 3 5 < 4x1 C x2 C x3 C x6 D 2 x  0; j D 1;:::;6 :j Giải.
  54. 2.2Thuậttoánđơnhìnhchobàitoánmin 50 2.2 Thuật toán đơn hình cho bài toán min Thuật toán đơn hình cho bài toán tìm giá trị nhỏ nhất của hàm mục tiêu về cơ bản giống với bài toán tìm giá trị lớn nhất. Ta có dấu hiệu tối ưu được phát biểu như sau: Định lý 2.4 (Dấu hiệu tối ưu). Nếu hệ số hàm mục tiêu của bảng đơn hình là không .cj D 0/ đối với biến cơ bản và không dương .cj  0/ đối với biến không cơ bản thì phương án cực biên hiện thời trong bảng đơn hình là phương án ưu. Định lý 2.5 (Dấu hiệu có hiệu phương án cực biên tốt hơn). Nếu hệ số hàm mục tiêu của bảng đơn hình là không .cj D 0/ đối với biến cơ bản và
  55. 2.2Thuậttoánđơnhìnhchobàitoánmin 51 dương .cj > 0/ đối với biến không cơ bản sẽ có phương án cực biên khác tốt hơn, nghĩa là làm giá trị hàm mục tiêu lớn nhỏ. Nhận xét. Nếu trong bảng đơn hình:  cj  0; 8j thì phương án cực biên hiện thời là phương án tối ưu.  Có cj >0 thì phương án cực biên hiện thời chưa là phương án tối ưu. Ví dụ 2.9. Giải bài toán quy hoạch tuyến tính z D x1 C x2 3x3 ! min Với các ràng buộc 2x1 x2 C x3  1 4x C 2x x  2 8 1 2 3 < 3x1 C x3  5 x  0; j D 1;2;3 :j Giải.
  56. 2.3Bàitoánchínhtắckhôngcósẵnmatrậnđơnvị 52 2.3 Bài toán chính tắc không có sẵn ma trận đơn vị Giả sử cần giải bài toán quy hoạch tuyến tính dạng chính tắc z D cT x ! max Với các ràng buộc Ax D b (2.21) x  0 Trong đó A không có ma trận đơn vị, b  0 . Chẳng hạn cần giải bài toán sau: Ví dụ 2.10. Giải bài toán quy hoạch tuyến tính z D3x1 C 4x2 C 5x3 6x4 ! max Với các ràng buộc x1 C x2 C x3 C 13x4 D 14 2x C x C 14x D 11 8 1 2 4 < C 3x2 C x3 C 14x4 D 16 x  0; j D 1;:::;4 :j
  57. 2.3Bàitoánchínhtắckhôngcósẵnmatrậnđơnvị 53 Giải. Do ma trận các hệ số A không có ma trận đơn vị nên chưa xác định được phương án cực biên ban đầu. Vì tập các phương án là hệ phương trình tuyến tính nên ta có thể biến đổi để có ba véctơ đơn vị 1 1 1 13 14 1 1 1 13 14 d Dd 2d d Dd 2 1 0 14 11 !2 2 1 0 1 2 12 17 !2 2 0 1 0 1 0 3 1 14 16 0 3 1 14 16 @ A @ A 1 1 1 13 14 1 0 1 1 3 d Dd d d3D1=5d3 0 1 2 12 17 !1 1 2 01 2 12 17 ! 0 1 d3Dd33d2 0 1 0 3 1 14 16 0 0 5 22 35 @ 1 0 1A 1 3 @ 1 0 0 27=5A 4 d Dd Cd 01 2 12 17 !1 1 3 0 1 0 16=5 3 0 1 d2Dd22d3 0 1 0 0 1 22=5 7 0 0 1 22=5 7 @ A @ A Bài toán lúc này là z D123=5x4 C 35 ! max Với các ràng buộc x1 C 27=5x4 D 4 x C 16=5x D 3 8 2 4 < x3 C 22=5x4 D 7 x  0; j D 1;:::;4 :j Với bài toán này ta có bảng đơn hình như sau x1 x2 x3 x4 x1 1 0 0 27/5 4 x2 0 1 0 16/5 3 x3 0 0 1 22/5 7 0 0 0 123/5 35 Phương án tối ưu x D .4I 3I 7I 0/; giá trị tối ưu z D 35 Nhưng có thể trong quá trình biến đổi sau khi đã có các véctơ đơn vị mà phương án không thỏa điều kiện không âm thì cách làm trên rất khó gặp một phương án cực biên ban đầu.
  58. 2.3Bàitoánchínhtắckhôngcósẵnmatrậnđơnvị 54 Ví dụ 2.11. Giải bài toán quy hoạch tuyến tính z D 2x1 x2 2x3 ! max Với các ràng buộc x1 C x2 x3 D 1 x C 2x C x D 2  1 2 3 xj  0; j D 1;2;3 Vì ma trận các hệ số A không có ma trận đơn vị nên chưa xác định được phương án cực biên ban đầu. Vì tập các phương án là hệ phương trình tuyến tính nên ta có thể biến đổi để có hai véctơ đơn vị. 1 1 1 1 1 1 1 1 1 0 3 4 ! ! 12 1 2 01 2 3 01 2 3       Bài toán lúc này là z D 6x3 11 ! max Với các ràng buộc x1 3x3 D 4 x C 2x D 3  2 3 xj  0; j D 1;2;3 Đến đây ta gặp khó khăn trong việc tìm phương án cực biên. Ta dùng phương pháp sau đây gọi là phương pháp đánh thuế để giải cho trường hợp này. Xét bài toán quy hoạch tuyến tính dạng chính tắc: z D c1x1 CC cnxn ! max (2.22) Với các ràng buộc a11x1 C  C a1nxn D b1 a x C  C a x D b 8 21 1 2n n 2 : : : : ˆ : : : : <ˆ am1x1 C  C amnxn D bm ˆxj  0;j D 1;:::;xn :ˆ
  59. 2.3Bàitoánchínhtắckhôngcósẵnmatrậnđơnvị 55 Thêm các ẩn y1;:::;ym  0 mà ta gọi là ẩn giả vào m ràng buộc khi đó bài toán có dạng z D c1x1 CC cnxn My1  Mym ! max (2.23) Với các ràng buộc a11x1 C  C a1nxn C y1 D b1 a x C  C a x C y D b 8 21 1 2n n 2 2 : : : : ˆ : : : : 0 aM C b>0 , a D 0;b >0  a c aM C b >cM C d , a D c;b >d  Ví dụ 2.12. Giả lại bài toán quy hoạch tuyến tính ví dụ 2.11 z D 2x1 x2 2x3 ! max Với các ràng buộc x1 C x2 x3 D 1 x C 2x C x D 2  1 2 3 xj  0; j D 1;2;3 Giải.
  60. 2.3Bàitoánchínhtắckhôngcósẵnmatrậnđơnvị 56
  61. 2.3Bàitoánchínhtắckhôngcósẵnmatrậnđơnvị 57 Ví dụ 2.13. Giải bài toán quy hoạch tuyến tính z D 2x1 C 5x2 ! max Với các ràng buộc 2x1 C 3x2  6 x C 2x  4  1 2 x1; x2  0 Giải.
  62. 2.4 Bài tập chương 2 58 2.4 Bài tập chương 2 Bài tập 2.1. Giải các bài toán quy hoạch tuyến tính: a. z D x1 2x2 C 2x3 ! min Với các ràng buộc x1 C x2 C 4x4 D 6 2x C x C 5x D 8  2 3 4 xj  0; j D 1;:::;4 Đáp án. Phương án tối ưu xT D .2I 4I 0I 0/ ; giá trị hàm mục tiêu z D6 b. z D 2x1 C 3x2 C x3 ! max Với các ràng buộc x1 5x2 C x3  6 2x C 2x 2x  7 8 1 2 3 < x1 C 2x2 C x3  5 xj  0; j D 1;2;3 : Đáp án. Phương án tối ưu xT D .125=12I 17=6I 39=4/; giá trị hàm mục tiêu z D 469=12: c. z D 2x1 C x2 C x3 C 3x4 ! max Với các ràng buộc x1 C 2x2 C x3 D 16 x C 4x C 2x  8  2 3 4 xj  0; j D 1;:::;4 Đáp án. Phương án tối ưu xT D .16I 0I 0I 4/ ; giá trị hàm mục tiêu z D 44: d. z Dx1 7x2 2x3 zx4 ! max
  63. 2.4 Bài tập chương 2 59 Với các ràng buộc x1 C 3x2 C x3 C x4  10 2x C 5x C x C 4x  15  1 2 3 4 xj  0; j D 1;:::;4 Đáp án: Phương án tối ưu xT D .10I 0I 0I 0/ ; giá trị hàm mục tiêu z D10: e. z D 15x1 C 19x2 ! min Với các ràng buộc 3x1 C x2  3 x C x  2 8 1 2 < 3x1 C 4x2  7 x1; x2  0 : Đáp án. Phương án tối ưu xT D .1I 1I 1/ ; giá trị hàm mục tiêu z D 34: Bài tập 2.2. Cho bài toán quy hoạch tuyến tính: z D4x1 5x2 7x3 ! max Với các ràng buộc 3x1 C x2 C x3 D 6 x C 2x C 3x D 14  1 2 3 xj  0; j D 1;2;3 a. Chứng minh xT D .0I 4I 2/ là phương án cực biên, nhưng không phải là phương án tối ưu. b. Hãy xây dựng một phương án cực biên mới tốt hơn phướng án cực biên ở câu a. Bài tập 2.3. Cho bài toán quy hoạch tuyến tính: z Dx1 C 2x2 2x3 ! max Với các ràng buộc x1 C x2 C 4x4 D 6 2x C x C 5x D 8  2 3 4 xj  0; j D 1;:::;4
  64. 2.4 Bài tập chương 2 60 a. Chứng minh xT D .0I 2=3I 0I 4=3/ là phương án cực biên, nhưng không phải là phương án tối ưu. b. Hãy xây dựng một phương án cực biên mới tốt hơn phướng án cực biên ở câu a. Bài tập 2.4. Cho bài toán quy hoạch tuyến tính: z D4x1 3x2 C 7x3 C 8x4 ! min Với các ràng buộc 2x1 C 3x2 C 4x3 C 5x4 D 20 8x x C x C 6x D 9 8 1 2 3 4 < 2x1 x2 C 5x3 C 2x4 D 15 x  0; j D 1;:::;4 :j Chứng minh xT D .1I 2I 3I 0/ là phương án cực biên, tối ưu của bài toán. Bài tập 2.5. Cho bài toán quy hoạch tuyến tính: z D x1 C x2 C mx3 ! min Với các ràng buộc 2x1 C x2 C x3 D 4 3x C 2x C 3x D 7  1 2 3 xj  0; j D 1;2;3 a. Chứng minh xT D .1I 2I 0/ là phương án cực biên của bài toán. b. Tìm m để x là phương án tối ưu. Bài tập 2.6. Một công ty sản xuất hai loại sơn: sơn nội thất và sơn ngoài trời. Nguyên liệu để sản xuất gồm hai loại A, B với trữ lượng tương ứng là 16 tấn và 18 tấn. Để sản xuất 1 tấn sơn nội thất cần 1 tấn nguyên liệu A và 2 tấn nguyên liệu B. Để sản xuất 1 tấn sơn ngoài trời cần 2 tấn nguyên liệu A và 3 tấn nguyên liệu B. Qua điều tra thị trường công ty biết rằng nhu cầu sơn nội thất không hơn sơn ngoài trời quá 1 tấn. Giá bán một tấn sơn nội thất là 4000 USD, giá bán một tấn sơn ngoài trời là 3000 USD. Khi sản xuất 1 tấn sơn nội thất phải bỏ ra một chi phí là 1300 USD, khi sản xuất 1 tấn sơn ngoài trời phải bỏ ra một chi phí là 1000 USD. Hỏi cần sản xuất mỗi loại sơn bao nhiêu tấn để có lợi nhuận lớn nhất? Đáp án. Phương án tối ưu xT D .21=5I 16=5/; giá trị hàm mục tiêu z D 17740
  65. 2.4 Bài tập chương 2 61 Bài tập 2.7. Một công ty sản xuất hai loại sơn nội thất và sơn ngoài trời. Nguyên liệu để sản xuất gồm hai loại A, B với trữ lượng là 6 tấn và 8 tấn tương ứng. Để sản xuất một tấn sơn nội thất cần 2 tấn nguyên liệu A và 1 tấn nguyên liệu B. Để sản xuất một tấn sơn ngoài trời cần 1 tấn nguyên liệu A và 2 tấn nguyên liệu B. Qua điều tra thị trường công ty biết rằng nhu cầu sơn nội thất không hơn sơn ngoài trời quá 1 tấn, nhu cầu cực đại của sơn nội thất là 2 tấn. Giá bán một tấn sơn nội thất là 2000 USD, giá bán một tấn sơn ngoài trời là 3000 USD. Hỏi cần sản xuất mỗi loại sơn bao nhiêu tấn để có doanh thu lớn nhất? Đáp án. Phương án tối ưu xT D .4=3I 10=3/; giá trị hàm mục tiêu z D 38000=3: Bài tập 2.8. Một công ty sản xuất hai loại thực phẩm A, B. Nguyên liệu để sản xuất gồm ba loại bột, đường và dầu thực vật. Với trữ lượng dự trự tương ứng là 30 tấn, 12 tấn, 6 tấn. Để sản xuất:  1 tấn thực phẩm loại A cần 0,5 tấn bột, 0,5 tấn đường, 0,2 tấn dầu thực vật.  1 tấn thực phẩm loại B cần 0,8 tấn bột, 0,4 tấn đường, 0,4 tấn dầu thực vật. Giá bán một tấn thực phẩm A là 4000 USD, giá bán một tấn thực phẩm B là 4500 USD. Hỏi cần sản xuất mỗi loại thực phẩm bao nhiêu tấn để có doanh thu lớn nhất? Đáp án. Phương án tối ưu xT D .20I 5/ ; giá trị hàm mục tiêu z D 102500 Bài tập 2.9. Một xí nghiệp dự định sản xuất ba loại sản phẩm A, B và C. Các sản phẩm này được chế tạo từ ba loại nguyên liệu I, II và III . Số lượng các nguyên liệu I, II và III mà xí nghiệp có lần lượt là 30, 50, 40. Số lượng các nguyên liệu cần để sản xuất một đơn vị sản phẩm A, B, C được cho ở bảng sau đây: HH HH NL H I II III H SP HH A 1 1 3 B 1 2 2 C 2 3 1
  66. 2.4 Bài tập chương 2 62 Xí nghiệp muốn lập kế hoạch sản xuất để thu được tổng số lãi nhiều nhất (với giả thiết các sản phẩm làm ra đều bán hết), nếu biết rằng lãi 5 triệu đồng cho một đơn vị sản phẩm loại A, lãi 3,5 triệu đồng cho một đơn vị sản phẩm loại B, lãi 2 triệu đồng cho một đơn vị sản phẩm loại C. a. Lập mô hình bài toán Quy hoạch tuyến tính. b. Bằng phương pháp đơn hình, hãy giải bài toán trên. Đáp án. Phương án tối ưu xT D .5=2I 25=2I 15=2/; giá trị hàm mục tiêu z D 285=4 Bài tập 2.10. Một Xí nghiệp chăn nuôi cần mua một loại thức ăn tổng hợp T1, T2, T3 cho gia súc với tỷ lệ chất dinh dưỡng như sau:  1 kg T1 chứa 4 đơn vị dinh dưỡng D1, 2 đơn vị dinh dưỡng D2, và 1 đơn vị dinh dưỡng D3.  1 kg T2 chứa 1 đơn vị dinh dưỡng D1, 7 đơn vị dinh dưỡng D2, và 3 đơn vị dinh dưỡng D3  1 kg T3 chứa 3 đơn vị dinh dưỡng D1, 1 đơn vị dinh dưỡng D2, và 4 đơn vị dinh dưỡng D3. Mỗi bữa ăn, gia súc cần tối thiểu 20 đơn vị D1, 25 đơn vị D2 và 30 đơn vị D3. Hỏi Xí nghiệp phải mua bao nhiêu kg T1, T2, T3 mỗi loại cho một bữa ăn để bảo đảm tốt về chất dinh dưỡng và tổng số tiền mua là nhỏ nhất? Biết rằng 1 kg T1 có giá là 10 ngàn đồng, 1 kg T2 có giá là 12 ngàn đồng, 1 kg T3 có giá là 14 ngàn đồng. Đáp án. Phương án tối ưu xT D .5=18I 49=18I 97=18/ ; giá trị hàm mục tiêu z D 998=9 Bài tập 2.11. Một Xí nghiệp xử lý giấy, có ba phân xưởng I, II, III cùng xử lý hai loại giấy A, B. Do hai phân xưởng có nhiều sự khác nhau, nên nếu cùng đầu tư 10 triệu đồng vào mỗi phân xưởng thì cuối kỳ phân xưởng I xử lý được 6 tạ giấy loại A, 5 tạ giấy loại B. Trong khi đó phân xưởng II xử lý được 4 tạ giấy loại A, 6 tạ giấy loại B. Phân xưởng III xử lý được 5 tạ giấy loại A, 4 tạ giấy loại B. Theo yêu cầu lao động thì cuối kỳ Xí nghiệp phải xử lý ít nhất 6 tấn giấy loại A, 8 tấn giấy loại B. Hỏi cần đầu tư vào mỗi phân
  67. 2.4 Bài tập chương 2 63 xưởng bao nhiêu tiền để xí nghiệp hoàn thành công việc với giá tiền đầu tư là nhỏ nhất. Đáp án. Phương án tối ưu xT D .5=2I 45=4I 0/ ; giá trị hàm mục tiêu z D 55=4 Bài tập 2.12. Một gia đình cần ít nhất 1800 đơn vị prôtêin và 1500 đơn vị lipit trong thức ăn mỗi ngày. Một kilôgam thịt bò chứa 600 đơn vị prôtêin và 600 đơn vị lipit, một kilôgam thịt heo chứa 600 đơn vị prôtêin và 300 đơn vị lipit, một kilôgam thịt gà chứa 600 đơn vị prôtêin và 600 đơn vị lipit. Giá một kilôgam thịt bò là 84 ngàn đồng, giá một kilôgam thịt heo là 71 ngàn đồng, giá một kilôgam thịt gà là 90 ngàn đồng. Hỏi một gia đình nên mua bao nhiêu kilôgam thịt mỗi loại để bảo đảm tốt khẩu phần ăn trong một ngày và tổng số tiền phải mua là nhỏ nhất? Đáp án. Phương án tối ưu xT D .2I 1I 0/ ; giá trị hàm mục tiêu z D 239
  68. Chương 3 Lý thuyết đối ngẫu 3.1 Ví dụ dẫn đến bái toán đối ngẫu Ví dụ 3.1. Có m loại nguyên liệu dự trữ dùng để sản xuất ra n loại sản phẩm. Để làm ra một sản phẩm j cần aij nguyên liệu i cho như bảng sau: H H H SP x1 x2    xn HH NL dự trữ H NL HH 1 2    n 1 a11 a12    a1n b1 2 a21 a22    a2n b2 : : : : : : : : : : : : m am1 am2    amn bm Giá bán c1 c2    cn Trong đó, lượng nguyên liệu dự trữ thứ i là bi và giá bán mỗi sản phẩm j là cj : Yêu cầu tìm số lượng sản phẩm x1; x2;:::;xn sao cho tổng doanh thu lớn nhất. Giải.
  69. 3.1Vídụdẫnđếnbáitoánđốingẫu 65 Ví dụ 3.2. Với giả thiết giống như ví dụ 3.1, giả sử có một người muốn mua lại toàn bộ nguyên liệu trên. HH HH SP x1 x2    xn HH NL dự trữ NL HH 1 2    n y1;1 a11 a12    a1n b1 y2;2 a21 a22    a2n b2 : : : : : : : : : : : : ym;m am1 am2    amn bm Giá bán c1 c2    cn Tìm giá bán nguyên liệu i;yi để:  Người bán không bị thiệt.  Người mua được mua với giá rẻ nhất. Giải.
  70. 3.1Vídụdẫnđếnbáitoánđốingẫu 66 3.1.1 Bài toán đối ngẫu của bài toán max Hai bài toán quy hoạch tuyến tính sau gọi là cặp bài toán đối ngẫu. Bài toán 1 gọi là bài toán gốc, bài toán 2 gọi là bài toán đối ngẫu. Một ràng buộc và điều kiện về biến trên cùng một dòng gọi là cặp ràng buộc đối ngẫu. Bài toán gốc (1) Bài toán đối ngẫu (2) 0 z D c1x1 CC cnxn ! max z D b1y1 CC bmym ! min ai1x1 C ai2x2 CC ainxn  bi yi  0 ai1x1 C ai2x2 CC ainxn  bi yi  0 ai1x1 C ai2x2 CC ainxn D bi yi 2 R xj  0 a1j y1 C a2j y2 CC amj ym  cj xj  0 a1j y1 C a2j y2 CC amj ym  cj xj 2 R a1j y1 C a2j y2 CC amj ym D cj Nhận xét. Quan sát cặp bài toán đối ngẫu trên ta có các nhận xét:  Trong cặp bài toán đối ngẫu trên, hệ số của ràng buộc thứ i của bài toán gốc trở thành hệ số của biến yi trong bài toán đối ngẫu. Ngược lại, hệ số của xj trong bài toán gốc chính là hệ số của dòng j trong bài toán đối ngẫu.  Hệ số của hàm mục tiêu của bài toán gốc trở thành hệ số vế phải của ràng buộc và ngược lại. Ví dụ 3.3. Viết bài toán đối ngẫu của bài toán gốc sau và cho biết các cặp ràng buộc đối ngẫu z D 2x1 C x2 8x3 ! max Với các ràng buộc 7x1 C 4x2 C 2x3  28 3x x C 3x D 10 8 1 2 3 < 2x1 C 3x2 x3  15 x  0; x  0 :1 2 Giải.
  71. 3.1Vídụdẫnđếnbáitoánđốingẫu 67 Ví dụ 3.4. Viết bài toán đối ngẫu của bài toán gốc sau và cho biết các cặp ràng buộc đối ngẫu z D 2x1 C 3x2 ! max Với các ràng buộc 3x1 C 2x2  2 x C 2x  5 8 1 2 < 4x1 C x2  1 x  0; x  0 :1 2 Giải.
  72. 3.1Vídụdẫnđếnbáitoánđốingẫu 68 3.1.2 Bài toán đối ngẫu của bài toán min Bài toán gốc (1) Bài toán đối ngẫu (2) 0 z D c1x1 CC cnxn ! min z D b1y1 CC bmym ! max ai1x1 C ai2x2 CC ainxn  bi yi  0 ai1x1 C ai2x2 CC ainxn  bi yi  0 ai1x1 C ai2x2 CC ainxn D bi yi 2 R xj  0 a1j y1 C a2j y2 CC amj ym  cj xj  0 a1j y1 C a2j y2 CC amj ym  cj xj 2 R a1j y1 C a2j y2 CC amj ym D cj Hai bài toán quy hoạch tuyến tính này gọi là cặp bài toán đối ngẫu. Bài toán 1 gọi là bài toán gốc, bài toán 2 gọi là bài toán đối ngẫu. Một ràng buộc và điều kiện về biến trên cùng một dòng gọi là cặp ràng buộc đối ngẫu. Ví dụ 3.5. Viết bài toán đối ngẫu của bài toán gốc sau và cho biết các cặp ràng buộc đối ngẫu z D 4x1 C 3x2 7x3 C x4 x5 ! min Với các ràng buộc 12x1 C 5x2 3x5  5 x x 4x 5x  2 8 1 3 4 5 ˆ 2x1 C x2 C x3 2x4  1 <ˆ 3x1 C 4x2 5x3 C x4 D 17 ˆx ; x  0I x 2 RI x ; x  0 :ˆ1 3 2 4 5
  73. 3.1Vídụdẫnđếnbáitoánđốingẫu 69 Giải. Ví dụ 3.6. Viết bài toán đối ngẫu của bài toán gốc sau và giải bài toán đối ngẫu bằng phương pháp đơn hình z D 10x1 C 8x2 C 19x3 ! min Với các ràng buộc x1 C x2 C x3  6 3x C 2x  2 8 1 3 < x1 C 2x2 C 5x3  5 x ; x ; x  0 :1 2 3 Giải.
  74. 3.1Vídụdẫnđếnbáitoánđốingẫu 70
  75. 3.2 Các định lý về đối ngẫu 71 Nhận xét. Bài toán quy hoạch tuyến tính gốc dạng z D cT x ! min Với các ràng buộc Ax  b x  0 trong đó c  0 thì bài toán đối ngẫu có dạng chuẩn 0 z D bT y ! max Với các ràng buộc AT y  c y  0 được giải trực tiếp bằng phương pháp đơn hình. Chú ý. Các phần sau, ta chỉ xét bài toán gốc dạng min : 3.2 Các định lý về đối ngẫu Cho cặp bài toán gốc, đối ngẫu như sau: Bài toán gốc (1) Bài toán đối ngẫu (2) 0 z D c1x1 CC cnxn ! min z D b1y1 CC bmym ! max ai1x1 C ai2x2 CC ainxn  bi yi  0 ai1x1 C ai2x2 CC ainxn  bi yi  0 ai1x1 C ai2x2 CC ainxn D bi yi 2 R xj  0 a1j y1 C a2j y2 CC amj ym  cj xj  0 a1j y1 C a2j y2 CC amj ym  cj xj 2 R a1j y1 C a2j y2 CC amj ym D cj T Định lý 3.1 (Đối ngẫu yếu). Nếu x D .x1;:::;xn/ là phương án chấp nhận T được của bài toán gốc và y D .y1;:::;yn/ là phương án chấp nhận được của bài toán đối ngẫu thì c1x1 CC cnxn  b1y1 CC bmym (3.1)
  76. 3.2 Các định lý về đối ngẫu 72 (Nghĩa là giá trị hàm mục tiêu của bài toán gốc luôn lớn hơn hoặc bằng giá trị hàm mục tiêu của bài toán đối ngẫu) Chứng minh. Ta đặt ui D .ai1x1 C ai2x2 CC ainxn bi /yi  0 vj D xj Œcj .a1j y1 C a2j y2 CC amj ym/  0 Cho nên m n ui D .ai1x1 C ai2x2 CC ainxn bi /yi  0 iD1 iD1 Xn Xn vj D xj Œcj .a1j y1 C a2j y2 CC amj ym/  0 j D1 j D1 X X Do đó m n 0  ui C vj D .c1x1 CC cnxn/ .b1y1 CC bmym/ iD1 j D1 X X Ta có điều cần chứng minh. Hệ quả 3.2 (Dấu hiệu không có phương án chấp nhận được). i. Nếu hàm mục tiêu của bài toán quy hoạch tuyến tính gốc không giới nội dưới, thì bài toán đối ngẫu không có phương án chấp nhận được. ii. Nếu hàm mục tiêu của bài toán quy hoạch tuyến tính đối ngẫu không giới nội trên, thì bài toán gốc không có phương án chấp nhận được. Chứng minh. Do sự tương tự ta chỉ chứng minh i). Giả sử bài toán gốc không k k k giới nội dưới tức tồn các phương án chấp nhận được x D .x1 ;:::;xn / sao cho giá trị hàm mục tiêu k k z D c1x1 CC cnxn ! 1 khi k ! 1 Ta chứng minh bằng phản chứng, giả sử bài toán đối ngẫu có phương án chấp T nhận được y D .y1;:::;ym/. Khi đó, do định lý đối ngẫu yếu k k T k k b1y1 CC bmym  c1x1 CC cnxn với mọi x D .x1 ;:::;xn /
  77. 3.2 Các định lý về đối ngẫu 73 Cho k ! 1 ta được điều vô lý b1y1 CC bmym  1 Vậy ta có điều cần chứng minh.      Hệ quả 3.3. Cho x D .x1 ;:::;xn / và y D .y1 ;:::;ym/ là phương án chấp nhận được tương ứng của bài toán gốc và bài toán đối ngẫu. Nếu giá trị hàm mục tiêu của hai bài toán này bằng nhau, nghĩa là     c1x1 CC cnxn D b1y1 CC bmym (3.2) thì x và y là phương án tối ưu tương ứng của hai bài toán. Chứng minh. Gọi x D .x1;:::;xn/ là một phương án chấp nhận được bất kỳ của bài toán gốc. Theo định lý đối ngẫu yếu ta có   b1y1 CC bmym  c1x1 CC cnxn do đó   c1x1 CC cnxn  c1x1 CC cnxn    Vậy x D x1 ;:::;xn là phương án tối ưu của bài toán gốc. Tương tự, ta có y là phương án tối ưu của bài toán đối ngẫu.  Định lý 3.4 (Đối ngẫu mạnh). Nếu một trong hai bài toán quy hoạch tuyến tính gốc hoặc đối ngẫu có phương án tối ưu thì: i. Bài toán quy hoạch kia cũng có phương án tối ưu. ii. Giá trị hàm mục tiêu tối ưu của hai bài toán bằng nhau. Định lý 3.5 (Độ lệch bù). Giả sử x; y tương ứng là phương án chấp nhận được của bài toán gốc, bài toán đối ngẫu. Khi đó x; y là tối ưu khi và chỉ khi .ai1x1 C ai2x2 CC ainxn bi /yi D 0 8i (3.3) xj .a1j y1 C a2j y2 CC amj ym cj / D 0 8j (3.4) Chứng minh. Ta đặt ui D .ai1x1 C ai2x2 CC ainxn bi /yi  0 vj D xj Œcj .a1j y1 C a2j y2 CC amj ym/  0
  78. 3.2 Các định lý về đối ngẫu 74 Cho nên m n ui D .ai1x1 C ai2x2 CC ainxn bi /yi  0 iD1 iD1 Xn Xn vj D xj Œcj .a1j y1 C a2j y2 CC amj ym/  0 j D1 j D1 X X Do đó m n 0  ui C vj D .c1x1 CC cnxn/ .b1y1 CC bmym/ iD1 j D1 X X T T Theo định lý đối ngẫu mạnh, nếu x D .x1;:::;xn/ và y D .y1;:::;ym/ là phương án tối ưu của bài toán gốc và bài toán đối ngẫu thì .c1x1 CC cnxn/ D .b1y1 CC bmym/: Do đó ui D vj D 0 với mọi i; j: Ngược lại nếu ui D vj D 0 với mọi i;j thì .c1x1 CC cnxn/ D .b1y1 CC bmym/: Theo hệ quả 3.3 thì x và y cũng là phương án tối ưu. Ví dụ 3.7. Cho bài toán quy hoạch tuyến tính z D 4x1 C 3x2 C 8x3 ! min Với các ràng buộc x1 C x3 D 2 x C 2x D 5  2 3 xj  0; j D 1;2;3 có phương án tối ưu của bài toán đối ngẫu là yT D .2I 3/: Hãy tìm phương án tối ưu của bài toán gốc. Giải.
  79. 3.2 Các định lý về đối ngẫu 75 Ví dụ 3.8. Cho bài toán quy hoạch tuyến tính z D 2x1 C 2x2 C x3 C 4x4 ! max Với các ràng buộc 5x1 C x2 C x3 C 6x4 D 50 3x C x C 2x  16 8 1 3 4 < 4x1 C 3x3 C x4  23 x  0; j D 1;:::;4 :j có phương án tối ưu xT D .0I 14I 6I 5/: Hãy tìm phương án tối ưu của bài toán đối ngẫu. Giải.
  80. 3.2 Các định lý về đối ngẫu 76 Ví dụ 3.9. Cho bài toán quy hoạch tuyến tính z D4x1 C 9x2 C 16x3 8x4 20x5 ! min Với các ràng buộc 5x1 C 4x2 x3 C 3x4 C x5  5 x C 2x C 4x 2x 5x  9 8 1 2 3 4 5 < x1 2x2 x3 C 2x4 C 3x5 D 2 x ; x ; x  0 :1 2 3 a. Phát biểu bài toán đối ngẫu của bài toán trên. b. Kiểm tra tính tối ưu của phương án xT D .2I 0I 1I2I 3/ và tìm phương án tối ưu của bài toán đối ngẫu. Giải.
  81. 3.2 Các định lý về đối ngẫu 77
  82. 3.2 Các định lý về đối ngẫu 78 Ví dụ 3.10. Giải bài toán quy hoạch tuyến tính z D 10x1 C 8x2 C 19x3 ! min Với các ràng buộc 2x1 C x2 C x3  6 3x C 2x  2 8 1 3 < x1 C 2x2 C 5x3  5 x  0; j D 1;:::;3 :j Giải.
  83. 3.3 Bài tập chương 3 79 3.3 Bài tập chương 3 Bài tập 3.1. Giải các bài toán qui hoạch tuyến tính a. z D 2x1 C 3x2 C 4x3 ! min Với các ràng buộc 6x1 C 3x2 C 2x3  19 2x C 6x C 3x  24  1 2 3 xj  0; j D 1;2;3 Đáp án. Phương án tối ưu xT D .7=5I 53=15I 0/ ; giá trị hàm mục tiêu z D 67=5 b. z D x1 C x2 C x3 ! min
  84. 3.3 Bài tập chương 3 80 Với các ràng buộc 6x1 C 2x2 C x3  20 x C 7x C 3x  25 8 1 2 3 < 3x1 C x2 C 8x3  30 xj  0; j D 1;2;3 : Đáp án. Phương án tối ưu xT D .131=60I 127=60I 8=3/; giá trị hàm mục tiêu z D 209=30 Bài tập 3.2. Cho bài toán quy hoạch tuyến tính z D 2x1 C x2 C x3 C 3x4 ! max Với các ràng buộc x1 2x2 C x3 D 16 x C 4x C x  8 8 2 3 4 < x2 2x3 C 3x4  20 x  0; j D 1;:::;4 :j a. Phát biểu bài toán đối ngẫu của bài toán trên. b. Hãy giải một trong hai bài toán rồi suy ra phương án tối ưu của bài toán còn lại. Bài tập 3.3. Cho bài toán quy hoạch tuyến tính z D5x1 C x2 C x3 C 16x4 ! max Với các ràng buộc x1 C x2 C 2x3 3x4 D 5 2x x C x C 5x D 2 8 1 2 3 4 < 3x1 C 4x2 C 7x3 8x4 D 9 x  0; j D 1;:::;4 :j a. Hỏi xT D .25=13I 64=13I 0I 8=13/ có phải là phương án tối ưu của bài toán trên không? b. Viết bài toán đối ngẫu của bài toán trên và tìm phương án tối ưu của bài toán đối ngẫu. Bài tập 3.4. Một Xí nghiệp xử lý giấy, có ba phân xưởng I, II, III cùng xử lý hai loại giấy A, B. Do hai phân xưởng có nhiều sự khác nhau, nên nếu
  85. 3.3 Bài tập chương 3 81 cùng đầu tư 10 triệu đồng vào mỗi phân xưởng thì cuối kỳ phân xưởng I xử lý được 6 tạ giấy loại A, 5 tạ giấy loại B. Trong khi đó phân xưởng II xử lý được 4 tạ giấy loại A, 6 tạ giấy loại B. Phân xưởng III xử lý được 5 tạ giấy loại A, 4 tạ giấy loại B. Theo yêu cầu lao động thì cuối kỳ Xí nghiệp phải xử lý ít nhất 6 tấn giấy loại A, 8 tấn giấy loại B. Hỏi cần đầu tư vào mỗi phân xưởng bao nhiêu tiền để xí nghiệp hoàn thành công việc với giá tiền đầu tư là nhỏ nhất. Đáp án. Phương án tối ưu xT D .5=4I 45=4I 0/ ; giá trị hàm mục tiêu z D 55=4: Bài tập 3.5. Một gia đình cần ít nhất 1800 đơn vị prôtêin và 1500 đơn vị lipit trong thức ăn mỗi ngày. Một kilôgam thịt bò chứa 600 đơn vị prôtêin và 600 đơn vị lipit, một kilôgam thịt heo chứa 600 đơn vị prôtêin và 300 đơn vị lipit, một kilôgam thịt gà chứa 600 đơn vị prôtêin và 600 đơn vị lipit. Giá một kilôgam thịt bò là 84 ngàn đồng, giá một kilôgam thịt heo là 71 ngàn đồng, giá một kilôgam thịt gà là 90 ngàn đồng. Hỏi một gia đình nên mua bao nhiêu kilôgam thịt mỗi loại để bảo đảm tốt khẩu phần ăn trong một ngày và tổng số tiền phải mua là nhỏ nhất? Đáp án. Phương án tối ưu xT D .2I 1I 0/ ; giá trị hàm mục tiêu z D 239: Bài tập 3.6. Cho bài toán quy hoạch tuyến tính. z D x1 2x2 C x3 x4 C x5 ! min Với các ràng buộc x1 2x2 C x3 C 3x4 2x5 D 6 2x 3x C 2x C x x  4 8 1 2 3 4 5 < x1 C 3x3 4x5  8 x ; x ; x  0 :1 3 5 a. Phát biểu bài toán đối ngẫu của bài toán trên, chứng tỏa tập phương án của bài toán đối ngẫu là tập rỗng. b. Kiểm tra tính tối ưu của phương án xT D .5I6I 1I4I 0/ cho bài toán gốc c. Chứng tỏa bài toán đã cho không có phương án tối ưu. Hướng dẫn giải. a. Chỉ ra không có phương án nào thỏa các ràng buộc của bài toán đối ngẫu.
  86. 3.3 Bài tập chương 3 82 b. Sử dụng định lý độ lệch bù, với phương án xT D .5I6I 1I4I 0/ thì không tồn tại phương án nào của bài toán đối ngẫu thỏa định lý độ lệch bù. c. Chứng minh bằng phản chứng. Giả sử bài toán gốc có phương án tối ưu thì bài toán đối ngẫu cũng có phương án tối ưu (theo định lý đối ngẫu mạnh 3.4). Điều này trái với câu a). Vậy ta được điều phải chứng minh.
  87. Chương 4 Bài toán vận tải 4.1 Bài toán vận tải cân bằng thu phát Giả sử: P PP PP Thu PP b b    b    b PP 1 2 j n Phát PP a1 c11 c12    c1j    c1n a2 c21 c22    c2j    c2n : : : : : : : :    :    : ai ci1 ci2    cij    cin : : : : : : : :    :    : am cm1 cm2    cmj    cmn  Có m nơi cung cấp hàng hóa (trạm phát), trạm phát i chứa ai đơn vị hàng hóa i D 1;:::;m:  Có n nơi tiêu thụ hàng hóa (trạm thu), trạm thu thứ j chứa bj đơn vị hàng hóa j D 1;:::;n:  Tổng lượng phát bằng tổng lượng thu, nghĩa là m n ai D bj (4.1) iD1 j D1 X X  Cước phí vận chuyển một đơn vị hàng hóa từ nơi cung cấp thứ i đến nơi tiêu thụ thứ j là cij :
  88. 4.1Bàitoánvậntảicânbằngthuphát 84 Yêu cầu của bài toán là tìm lượng hàng phân phối xij  0 từ trạm phát thứ i đến trạm thu thứ j sao cho:  Tổng chi phí vận chuyển thấp nhất m n z D cij xij ! min (4.2) iD1 j D1 X X  Giải tỏa kho n xij D ai ; i D 1;:::;m (4.3) j D1 X  Cửa hàng nhận đủ hàng m xij D bj j D 1;:::;n (4.4) iD1 X Bảng phân phối lượng hàng vận chuyển xij từ trạm phát thứ i đến trạm thu thứ j thường được trình bày như sau: bj b b    bj    b ai 1 2 n c11 c12 c1j c1n a1 x11 x12 x1j x1n c21 c22 c2j c2n a2 x21 x22 x2j x2n : : ci1 ci2 cij cin ai xi1 xi2 xij xin : : cm1 cm2 cmj cmn am xm1 xm2 xmj xmn Ma trận x11 x12    x1n x21 x22    x2n x D 0 : : : 1 (4.5) : : : B C Bxm1 xm2    xmnC B C thỏa các ràng buộc (4.3) và (4.4)@ được gọi là phươngA án chấp nhận được.
  89. 4.2Phươngáncựcbiêncủabàitoánvậntải 85 Tính chất 4.1. Bài toán vận tải cân bằng thu phát luôn có phương án tối ưu. Chứng minh. Ta cần chứng minh tập các phương án chấp nhận được khác rỗng và hàm mục tiêu luôn bị chặn dưới. Thật vậy ta có ai bj xij D m  0; 8i;j (4.6) ai iD1 P là phương án chấp nhận được vì n n n ai bj ai xij D m D m bj D ai ; i D 1;:::;m (4.7) j D1 j D1 ai ai j D1 X X iD1 iD1 X m m P P m ai bj bj xij D m D m ai D bj ; j D 1;:::;n (4.8) iD1 iD1 ai ai iD1 X X iD1 iD1 X Hàm mục tiêu bị chặn dướiP bởi khôngP m n z D cij xij  0 (4.9) iD1 j D1 X X Vậy theo tính chất của bài toán quy hoạch tuyến tính, bài toán vận tải luôn có phương án tối ưu. Tính chất 4.2. Ma trận hệ số các ràng buộc của bài toán vận tải có hạng bằng m C n 1: 4.2 Phương án cực biên của bài toán vận tải Định nghĩa 4.3 (Ô chọn, ô loại). i. Ta viết .iI j/ là ô ở dòng i cột j: ii. Trong bảng vận tải, những ô có xij >0 được gọi là ô chọn, những ô có xij D 0 gọi là ô loại.
  90. 4.2Phươngáncựcbiêncủabàitoánvậntải 86 Định nghĩa 4.4 (Đường đi). Ta gọi một đường đi là tập hợp các ô chọn sao cho:  Trên cùng một dòng hay một cột không có quá hai ô chọn.  Hai ôchọn liên tiếp thì nằm trên cùng một dòng hay một cột. Ví dụ 4.1. Dãy các ô chọn sau tạo thành một đường đi: b b b b b b b b Ví dụ 4.2. Các ô chọn sau có lập thành đường đi không, tại sao? b b b b Định nghĩa 4.5 (Chu trình). Một đường đi khép kín được gọi là một chu trình.
  91. 4.2Phươngáncựcbiêncủabàitoánvậntải 87 Ví dụ 4.3. Dãy các ô chọn sau tạo thành một chu trình b b b b b b b b b b b b b b Tính chất 4.6. Một bảng vận tải có m dòng, n cột thì tập các ô chọn không chứa chu trình có tối đa m C n 1 ô. Tính chất 4.7. Với một phương án có đủ m C n 1 ô chọn không chứa chu trình, thì với bất kỳ một ô loại nào được đưa vào phương án thì sẽ tạo thành một chu trình và chu trình này là duy nhất. Ví dụ 4.4. Xét bảng vận tải 3 dòng, 4 cột với một phương án có 3C41 D 6 ô chọn cho như sau b b b b b b Khi ta thêm một ô loại bất kỳ thì ô loại này kết hợp với một số ô chọn này tạo thành chu trình. Chẳng hạn, ta thêm ô loại .1;2/ vào phương án thì ô này sẽ kết hợp với các ô .3;2/I .3;3/I .2;3/I .2;1/I .1;1/ tạo thành chu trình.
  92. 4.2Phươngáncựcbiêncủabàitoánvậntải 88 b  b b b b b Định lý 4.8. Một phương án được gọi là phương án cực biên của bài toán vận tải khi và chỉ khi tập các ô chọn của nó không chứa chu trình. Định nghĩa 4.9. Một phương án cực biên có m C n 1 ô chọn được gọi là phương án cực biên không suy biến. Ngược lại, một phương án cực biên có ít hơn m C n 1 ô chọn được gọi là phương án cực biên suy biến. Ví dụ 4.5. Phương án sau là phương án cực biên không suy biến bj ai 30 40 50 60 1 5 7 2 80 30 50 5 7 4 9 45 35 10 12 2 3 6 55 40 15 Ví dụ 4.6. Phương án sau là phương án cực biên suy biến bj ai 40 100 60 50 1 2 4 3 80 40 40 2 4 5 1 70 20 50 4 1 2 5 100 100 Nhận xét. Một phương án cơ bản có các cô chọn có thể không lập thành một đường đi.
  93. 4.3 Các phương pháp thành lập phương án cực biên 89 4.3 Các phương pháp thành lập phương án cực biên 4.3.1 Phương pháp cước phí thấp nhất Ý tưởng chính của phương pháp này là phân phối lượng hàng lớn nhất có thể vào ô có cước phí thấp nhất. Phương pháp phân phối lượng hàng xij được thực hiện như sau: ai loại dòng i; bj D bj ai xij D minfai I bj gD 8bj loại cột j; ai D ai bj (4.10) ˆ <ai D bj loại dòng i cột j Lặp lại quá trình trên cho:ˆ các ô tiếp theo đến khi yếu cầu của trạm phát, trạm thu được thỏa mãn. Phương án thu được bằng phương pháp này là phương án cực biên. Ví dụ 4.7. Bằng phương pháp cước phí thấp nhất, thành lập một phương án cực biên của bài toán vận tải: bj ai 30 40 50 60 80 1 5 7 2 45 5 7 4 9 55 12 2 3 6 Giải.
  94. 4.3 Các phương pháp thành lập phương án cực biên 90 4.3.2 Phương pháp góc Tây Bắc Ta ưu tiên phân phối lượng hàng nhiều nhất vào ô ở góc Tây Bắc trên bảng vận tải. Khi đó nếu:  Trạm phát nào đã hết hàng thì ta xóa dòng chứa trạm phát đó.  Trạm thu nào đã nhận đủ hàng thì ta xóa cột chứa trạm thu đó. Sau đó lặp lại quá trình trên đối với những ô còn lại. Phương án được thành lập bằng phương pháp góc Tây Bắc là phương án cực biên Ví dụ 4.8. Bằng phương pháp góc Tây Bắc, thành lập phương án cực biên của bài toán vận tải bj ai 30 40 50 60 80 1 5 7 2 45 5 7 4 9 55 12 2 3 6 Giải. 4.3.3 Phương pháp Vogel (Fogel) Phương pháp Vogel cho ta một phương án cực biên khá tốt, theo nghĩa nó rất gần với phương án tối ưu.
  95. 4.3 Các phương pháp thành lập phương án cực biên 91 i) Trên mỗi dòng, mỗi cột của ma trận cước phí ta tính hiệu số giữa hai giá trị cước phí nhỏ nhất. ii) Chọn dòng hay cột có hiệu số này lớn nhất (nếu có nhiều dòng hay cột thỏa điều kiện này thì ta chọn một dòng hay một cột trong các dòng, cột này) iii) Phân lượng hàng nhiều nhất vào ô có cước phí nhỏ nhất trên dòng hay cột vừa chọn được. (Khi đó nếu nơi nào đã phát hết hàng thì ta xóa dòng chứa nơi phát đó. Nếu nơi nào nhận đủ hàng thì ta xóa cột chứa nơi nhận đó. Lúc đó cột (dòng) này hiệu số sẽ không tính cho bước sau). iv) Lặp lại ba bước nói trên với những ô còn lại cho đến hết. Ta thu được phương án cực biên. Ví dụ 4.9. Bằng phương pháp Vogel tìm phương án cực biên của bài toán vận tải: bj ai 30 40 50 60 80 1 5 7 2 45 5 7 4 9 55 12 2 3 6 Giải.
  96. 4.4Thuậttoánthếvịgiảibàitoánvậntải 92 4.4 Thuật toán thế vị giải bài toán vận tải Để giải bài toán vận tải, ta thực hiện bốn bước như sau: Bước 1. Thành lập phương án cực biên bằng một trong các phương pháp: cước phí thấp nhất, Tây Bắc, Vogel. Bước 2. Xét xem phương án cực biên hiện thời đã tối ưu hay chưa bằng thuật toán quy không cước phí ô chọn. Nếu phương án cực biên hiện thời là phương án tối ưu thì thuật toán kết thúc. Ngược lại sang bước 3. Bước 3. Xây dựng phương án cực biên mới tốt hơn xem 4.4.2. Bước 4. Quay về bước 2. 4.4.1 Thuật toán quy không cước phí ô chọn Xét bài toán quy hoạch tuyến tính có phương án cực biên ban đầu không suy biến (có m C n 1 ô chọn). Nếu bài toán có phương án cực biên suy biến (có ít hơn m C n 1 ô chọn) thì ta thêm ô chọn giả .i;j/ với xij D 0 vào sao cho các ô chọn giả này và các ô chọn ban đầu không tạo thành chu trình. Ví dụ 4.10. Xét bài toán vận tải có phương án cực biên suy biến bj ai 40 100 60 50 1 2 4 3 80 40 40 2 4 5 1 70 20 50 4 1 2 5 100 100 Ta thêm ô chọn giả .1;2/ với x12 D 0 thì bài toán có m C n 1 ô chọn
  97. 4.4Thuậttoánthếvịgiảibàitoánvậntải 93 bj ai 40 100 60 50 1 2 4 3 80 40 0 40 2 4 5 1 70 20 50 4 1 2 5 100 100 Thuật toán quy không cước phí thực hiện như sau: Lần lượt cộng vào các cước phí ở dòng 1;:::;m một lượng r1;:::;rm và vào cột 1;:::;n một lượng s1;:::;sn sao cho tổng cước phí trên các ô chọn bằng không. Ví dụ 4.11. Quy không cước phí các ô chọn của bảng vận tải. bj ai 30 40 50 60 1 5 7 2 80 30 50 5 7 4 9 45 35 10 12 2 3 6 55 40 15 sj ri 1 5 7 2 30 50 5 7 4 9 35 10 12 2 3 6 Giải. 40 15 Bài toán vận tải sau khi quy không cước phí ô chọn:
  98. 4.4Thuậttoánthếvịgiảibàitoánvậntải 94 bj ai 30 40 50 60 80 30 50 45 35 10 55 40 15 Định lý 4.10. Lần lượt cộng vào các cước phí ở dòng 1;:::;m một lượng r1;:::;rm và vào cột 1;:::;n một lượng s1;:::;sn tức thay cij bởi 0 cij D ri C sj C cij thì ta được bài toán mới có cùng phương án tối ưu với bài toán cũ. Nhận xét. Theo định lý 4.10, bài toán vận tải với phương án cực biên bj ai 30 40 50 60 1 5 7 2 80 30 50 5 7 4 9 45 35 10 12 2 3 6 55 40 15 và bài toán vận tải sau khi quy không cước phí các ô chọn với phương án cực biên bj ai 30 40 50 60 0 9 10 0 80 30 50 3 4 0 0 45 35 10 5 0 0 2 55 40 15 là tương đương nhau. Nghĩa bài toán quy không cước phí tối ưu thì bài toán ban đầu cũng tối ưu và chúng cùng phương án tối ưu. Ta nhận thấy, trong bài toán quy không cước phí trên dòng 2, có ô .2;1/ có cước phí “rẻ” hơn cước phí các ô chọn .2;3/ và .2;4/ nên phương án hiện thời chưa tối ưu.
  99. 4.4Thuậttoánthếvịgiảibàitoánvậntải 95 Định lý 4.11 (Dấu hiệu tối ưu). Bài toán vận tải sau khi quy không cước phí các ô chọn: 0  Nếu cij  0 với mọi .i;j/ thì phương án cực biên hiện thời là phương án tối ưu. 0  Nếu tồn tại cij < 0 thì có thể tìm một phương án mới tốt hơn phương án hiện thời. Ví dụ 4.12. Chứng minh phương án cực biên hiện thời của bài toán vận tải sau không phải là phương án tối ưu. bj ai 30 40 50 60 1 5 7 2 80 30 40 10 5 7 4 9 45 40 5 12 2 3 6 55 55 Giải.
  100. 4.4Thuậttoánthếvịgiảibàitoánvậntải 96 Ví dụ 4.13. Chứng minh phương án cực biên hiện thời của bài toán vận tải sau là phương án tối ưu. bj ai 30 40 50 60 1 5 7 2 80 20 60 5 7 4 9 45 10 35 12 2 3 6 55 40 15 Giải.
  101. 4.4Thuậttoánthếvịgiảibàitoánvậntải 97 4.4.2 Xây dựng phương án cực biên mới Trên bảng quy không cước phí tìm 0 Bước 1. Ô vào là ô loại có cij <0 nhỏ nhất. Bước 2. Xác định chu trình chứa ô vào vừa xác định bước 2. Ô vào đánh dấu (+), các ô còn lại xen kẻ dấu (), (+) trên chu trình. Bước 3. Xác định phương án cực biên mới.  Lượng điều chỉnh q D min xij j.i;j/ có dấu ()  Phương án cực biên mới: ˚ xij C q Ô có dấu (+) xij D 8xij q Ô có dấu () (4.11) ˆ <xij Ô không có dấu ˆ Ví dụ 4.14. Cho bài toán vận:ˆ tải có phương án cực biên bj ai 30 50 80 40 3 2 5 1 90 30 20 40 4 1 3 6 70 50 20 7 4 2 5 40 40 Chứng minh phương án cực biên hiện thời chưa tối ưu. Xây dựng một phương án khác tốt hơn. Giải.
  102. 4.4Thuậttoánthếvịgiảibàitoánvậntải 98 Ví dụ 4.15. Cho bài toán vận tải có phương án cực biên bj ai 25 25 10 5 3 5 10 10 7 6 8 30 25 5 3 2 2 20 20 Chứng minh phương án cực biên hiện thời chưa tối ưu. Xây dựng một phương án khác tốt hơn. Giải.
  103. 4.4Thuậttoánthếvịgiảibàitoánvậntải 99 Ví dụ 4.16. Giải bài toán vận tải bj ai 50 40 70 80 5 5 12 20 7 9 11 60 4 2 3 Giải.
  104. 4.4Thuậttoánthếvịgiảibàitoánvậntải 100
  105. 4.5Mộtsốtrườnghợpđặcbiệtcủabàitoánvậntải 101 4.5 Một số trường hợp đặc biệt của bài toán vận tải 4.5.1 Bài toán vận tải không cân bằng thu phát Trường hợp phát lớn hơn thu. Ta thêm trạm thu giả bnC1; với lượng hàng là m n bnC1 D ai bj ; cinC1 D 0; i D 1;:::;m iD1 j D1 X X Lúc này bài toán cân bằng thu phát. Trường hợp phát ít hơn thu. Ta thêm trạm phát giả amC1; với lượng hàng là n m amC1 D bj ai ; cmC1i D 0; j D 1;:::;n j D1 iD1 X X Lúc này bài toán cân bằng thu phát. Ví dụ 4.17. Giải bài toán vận tải không cân bằng thu phát cho bởi bảng vận tải sau:
  106. 4.5Mộtsốtrườnghợpđặcbiệtcủabàitoánvậntải 102 bj ai 100 65 95 80 7 5 2 70 3 4 5 150 9 2 7 Giải.
  107. 4.5Mộtsốtrườnghợpđặcbiệtcủabàitoánvậntải 103 4.5.2 Bài toán vận tải có ô cấm Đây là bài toán vận tải mà vì một lý do no đó có một nơi phát không thể chuyên chở hàng đến một nơi nhận nào đó được. Để giải quyết vấn đề này chúng ta cho cước phí ở ô đó là M; với M là số dương rất lớn, lớn hơn bất kỳ số nào cần so sánh. Sau đó chúng ta giải như những bài toán đã trình bày ở trên. Ví dụ 4.18. Giải bài toán vận tải với hai ô cấm cho như sau: bj ai 100 65 95 40 80 6 5 11 10 70 10 5 7 150 9 8 7 Giải.
  108. 4.5Mộtsốtrườnghợpđặcbiệtcủabàitoánvậntải 104
  109. 4.6Bàitoánvậntảicựcđạicướcphí 105 4.6 Bài toán vận tải cực đại cước phí Bước 1. Thành lập phương án cực biên bằng phương pháp cực đại cước phí, chúng ta phân phối lượng hàng nhiều nhất vào ô có cước phí lớn nhất. Bước 2. Xét xem phương án cực biên hiện thời đã tối ưu hay chưa bằng thuật toán quy không cước phí ô chọn. 0  Nếu cij  0 với mọi .i;j/ thì phương án cực biên hiện thời là phương án tối ưu, thuật toán kết thúc. 0  Nếu tồn tại cij > 0 thì có thể tìm một phương án mới tốt hơn phương án hiện thời, chuyển sang bước 3. Bước 3. Xây dựng phương án cực biên mới tốt hơn, chú ý ô vào là ô loại 0 có cij >0 lớn nhất, các bước tiếp theo làm giống bài toán min : Bước 4. Quay về bước 2. Ví dụ 4.19. Giải bài toán vận tải cực đại cước phí sau: bj ai 70 55 85 60 90 6 5 11 10 80 10 6 5 7 100 9 8 7 4 Giải.
  110. 4.7 Bài tập chương 4 106 4.7 Bài tập chương 4 Bài tập 4.1. Giải bài toán vận tải bj ai 30 50 80 40 90 3 2 5 1 70 4 1 3 6 40 7 4 2 5
  111. 4.7 Bài tập chương 4 107 Đáp án: Phương án tối ưu 30 20 0 40 x D 0 30 40 0 ; z D 400 0 1 0 0 40 0 @ A Bài tập 4.2. Giải bài toán vận tải: bj ai 40 100 60 50 80 1 2 4 3 70 2 4 5 1 100 4 1 2 5 Đáp án: Phương án tối ưu 20 60 0 0 x D 20 0 0 50 ; z D 390 0 1 0 40 60 0 @ A Bài tập 4.3. Giải bài toán vận tải: bj ai 20 30 45 50 40 5 8 6 11 30 6 7 7 12 55 8 8 9 10 Đáp án: Phương án tối ưu 0 0 40 0 x D 20 5 5 0 ; z D 930 0 1 0 25 0 30 @ A Bài tập 4.4. Giải bài toán vận tải có ô cấm
  112. 4.7 Bài tập chương 4 108 sj ri 45 100 50 60 70 16 15 11 100 10 17 9 85 12 14 10 13 Đáp án: Phương án tối ưu 0 10 0 60 x D 45 5 50 0 ; z D 2995 0 1 0 85 0 0 @ A Bài tập 4.5. Cho bài toán vận tải cân bằng thu phát và một phương án: bj ai 40 45 60 65 4 5 7 2 90 25 65 5 1 2 10 65 45 20 11 2 3 6 55 15 40 a. Tính cước phí vận chuyển của phương án này, chứng minh phương án cực biên đã cho không phải là phương án tối ưu. b. Xuất phát từ phương án trên hãy xây dựng một phương án mới tốt hơn (chỉ cần một phương án mới tốt hơn). Bài tập 4.6. Một nhà máy chế biến thịt, sản xuất ba loại thịt: bò, lợn, cừu, với tổng lượng mỗi ngày là 480 tấn bò; 400 tấn lợn; 230 tấn cừu. Mỗi loại đều có thể bán được ở dạng tươi hoặc nấu chín. Tổng lượng các loại thịt nấu chín để bán trong giờ làm việc là 420 tấn. Ngoài ra nấu thêm ngoài giờ 250 tấn (với giá cao hơn). Lợi nhuận thu được trên một tấn được cho bằng bảng sau: (với đơn vị là triệu đồng) @ Nấu chín @ Tươi @ Nấu chín @ Ngoài giờ Bò 8 11 14 Lợn 4 7 12 Cừu 4 9 13
  113. 4.7 Bài tập chương 4 109 Mục đích của nhà máy là tìm phương án sản xuất để làm cực đại lợi nhuận. Hãy tìm phương án tối ưu.
  114. Tài liệu tham khảo [1] Phan Quốc Khánh, Trần Huệ Nương. (2000). Quy hoạch tuyến tính. NXB Giáo dục. [2] Nguyễn Đình Tùng. (2010). Quy hoạch tuyến tính. [3] Lê Khánh Luận. (2006). Quy hoạch tuyến tính . NXB Lao động. [4] Bùi Phúc Trung. (2003). Quy hoạch tuyến tính. NXB Lao động Xã hội. [5] Bernard Kolman, Robert E. Beck. (1995). Elementary Linear Program ming with Applications. Elsevier Science & Technology Books. [6] Robert J. Vanderbei. (2007). Linear Programming, Foundations and Ex tensions Third Edition. Springer Publication. [7] George B. Dantzig, Mukund N. Thapa. (1997). Linear Programming, Introduction. Springer Publication.