›
›

Giáo trình Quy hoạch tuyến tính - Chương 3: Lý thuyết đối ngẫu

pdf 47 trang ngocly 4070
Download
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Quy hoạch tuyến tính - Chương 3: Lý thuyết đối ngẫu", để 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:

  • pdfgiao_trinh_quy_hoach_tuyen_tinh_chuong_3_ly_thuyet_doi_ngau.pdf

Nội dung text: Giáo trình Quy hoạch tuyến tính - Chương 3: Lý thuyết đối ngẫu

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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
  6. 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.
  7. 3.1Vídụdẫnđếnbáitoánđốingẫu 70
  8. 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)
  9. 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 /
  10. 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
  11. 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.
  12. 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.
  13. 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.
  14. 3.2 Các định lý về đối ngẫu 77
  15. 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.
  16. 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
  17. 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
  18. 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.
  19. 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.
  20. 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 :
  21. 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.
  22. 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.
  23. 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.
  24. 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.
  25. 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.
  26. 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.
  27. 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.
  28. 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.
  29. 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
  30. 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:
  31. 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.
  32. 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.
  33. 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.
  34. 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.
  35. 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.
  36. 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.
  37. 4.4Thuậttoánthếvịgiảibàitoánvậntải 100
  38. 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:
  39. 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.
  40. 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.
  41. 4.5Mộtsốtrườnghợpđặcbiệtcủabàitoánvậntải 104
  42. 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.
  43. 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
  44. 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
  45. 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
  46. 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.
  47. 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.