zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Kinh Tế - Quản Lý

» Kinh tế học

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

Chia sẻ: 9 9 | Ngày: | Loại File: PDF | Số trang:47

Báo xấu

126
lượt xem 16
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Phần 2 của bài giảng tiếp tục giới thiệu tới các bạn những nội dung về bài toán vận tải, bài toán vận tải cân bằng thu phát, phương pháp cực biên của bài toán thu phát, lý thuyết mẫu, phương pháp góc Tây - Bắc, bài toán vận tải không cân bằng, thuật toán không quy ước. Mời các bạn cùng tham khảo

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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

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 HH SP x1 x2 xn HH NL dự trữ NL H 1 2 n HH 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.
3.1 Ví dụ dẫn đến bái toán đối ngẫ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 NL dự trữ NL HHHH 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.1 Ví dụ dẫn đến bái toán đối ngẫ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) z D c1x1 C C cnxn ! max z D b1 y1 C C bm ym ! min 0 ai1 x1 C ai 2 x2 C C ai nxn bi yi 0 ai1 x1 C ai 2 x2 C C ai nxn bi yi 0 ai1x1 C ai 2 x2 C C ai nxn D bi yi 2 R xj 0 a1j y1 C a2j y2 C C amj ym cj xj 0 a1j y1 C a2j y2 C C amj ym cj xj 2 R a1j y1 C a2j y2 C C 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 8 < 7x1 C 4x2 C 2x3 28 3x1 x2 C 3x3 D 10 : 2x1 C 3x2 x3 15 x1 0; x2 0 Giải.
3.1 Ví dụ dẫn đến bái toán đối ngẫ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 8 < 3x1 C 2x2 2 x1 C 2x2 5 : 4x1 C x2 1 x1 0; x2 0 Giải.
3.1 Ví dụ dẫn đến bái toán đối ngẫ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) z D c1x1 C C cnxn ! min z D b1y1 C C bm ym ! max 0 ai1 x1 C ai 2 x2 C C ai nxn bi yi 0 ai1 x1 C ai 2 x2 C C ai nxn bi yi 0 ai1x1 C ai 2 x2 C C ai nxn D bi yi 2 R xj 0 a1j y1 C a2j y2 C C amj ym cj xj 0 a1j y1 C a2j y2 C C amj ym cj xj 2 R a1j y1 C a2j y2 C C 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 8 ˆ ˆ 12x1 C 5x2 3x5 5 < x1 x3 4x4 5x5 2 ˆ ˆ 2x1 C x2 C x3 2x4 1 : 3x1 C 4x2 5x3 C x4 D 17 x1 ; x3 0I x2 2 RI x4 ; x5 0
3.1 Ví dụ dẫn đến bái toán đối ngẫ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 8 < x1 C x2 C x3 6 3x C 2x3 2 : 1 x1 C 2x2 C 5x3 5 x1 ; x2 ; x3 0 Giải.
3.1 Ví dụ dẫn đến bái toán đối ngẫu 70
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 x0 trong đó c 0 thì bài toán đối ngẫu có dạng chuẩn z D bT y ! max 0 Với các ràng buộc AT y c y0 đượ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) z D c1x1 C C cnxn ! min z D b1y1 C C bm ym ! max 0 ai1 x1 C ai 2 x2 C C ai nxn bi yi 0 ai1 x1 C ai 2 x2 C C ai nxn bi yi 0 ai1x1 C ai 2 x2 C C ai nxn D bi yi 2 R xj 0 a1j y1 C a2j y2 C C amj ym cj xj 0 a1j y1 C a2j y2 C C amj ym cj xj 2 R a1j y1 C a2j y2 C C amj ym D cj Định lý 3.1 (Đối ngẫu yếu). Nếu xT D .x1 ; : : : ; xn / là phương án chấp nhận được của bài toán gốc và yT D .y1; : : : ; yn / là phương án chấp nhận được của bài toán đối ngẫu thì c1x1 C C cnxn b1y1 C C bm ym (3.1)
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 ai 2x2 C C ai nxn bi /yi 0 vj D xj Œcj .a1j y1 C a2j y2 C C amj ym/ 0 Cho nên m X n X ui D .ai1x1 C ai 2 x2 C C ai n xn bi /yi 0 i D1 i D1 X n X n vj D xj Œcj .a1j y1 C a2j y2 C C amj ym/ 0 j D1 j D1 Do đó m X n X 0 ui C vj D .c1x1 C C cnxn / .b1 y1 C C bm ym/ i D1 j D1 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 giới nội dưới tức tồn các phương án chấp nhận được xk D .x1k ; : : : ; xnk / sao cho giá trị hàm mục tiêu z D c1 x1k C C cnxnk ! 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 nhận được yT D .y1; : : : ; ym /. Khi đó, do định lý đối ngẫu yếu b1y1 C C bm ym c1x1k C C cnxnk với mọi xT D .x1k ; : : : ; xnk /
3.2 Các định lý về đối ngẫu 73 Cho k ! 1 ta được điều vô lý b1 y1 C C 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 C C cnxn D b1 y1 C C bm ym (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 C C bm ym c1x1 C C cn xn do đó c1 x1 C C cnxn c1x1 C C 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 ai 2x2 C C ai nxn bi /yi D 0 8i (3.3) xj .a1j y1 C a2j y2 C C amj ym cj / D 0 8j (3.4) Chứng minh. Ta đặt ui D .ai1x1 C ai 2x2 C C ai nxn bi /yi 0 vj D xj Œcj .a1j y1 C a2j y2 C C amj ym/ 0
3.2 Các định lý về đối ngẫu 74 Cho nên m X n X ui D .ai1x1 C ai 2 x2 C C ai n xn bi /yi 0 i D1 i D1 X n X n vj D xj Œcj .a1j y1 C a2j y2 C C amj ym/ 0 j D1 j D1 Do đó m X n X 0 ui C vj D .c1x1 C C cnxn / .b1 y1 C C bm ym/ i D1 j D1 Theo định lý đối ngẫu mạnh, nếu xT D .x1; : : : ; xn / và yT 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 C C cnxn / D .b1 y1 C C bm ym/: 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 C C cnxn / D .b1 y1 C C bm ym/: 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 x2 C 2x3 D 5 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.
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 8 < 5x1 C x2 C x3 C 6x4 D 50 3x1 C x3 C 2x4 16 : 4x1 C 3x3 C x4 23 xj 0; j D 1; : : : ; 4 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.
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 zD 4x1 C 9x2 C 16x3 8x4 20x5 ! min Với các ràng buộc 8 < 5x1 C 4x2 x3 C 3x4 C x5 5 x1 C 2x2 C 4x3 2x4 5x5 9 : x1 2x2 x3 C 2x4 C 3x5 D 2 x1 ; x2 ; x3 0 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 1I 2I 3/ và tìm phương án tối ưu của bài toán đối ngẫu. Giải.
3.2 Các định lý về đối ngẫu 77
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 8 < 2x1 C x2 C x3 6 3x1 C 2x3 2 : x1 C 2x2 C 5x3 5 xj 0; j D 1; : : : ; 3 Giải.
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 2x1 C 6x2 C 3x3 24 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
3.3 Bài tập chương 3 80 Với các ràng buộc 8 < 6x1 C 2x2 C x3 20 x1 C 7x2 C 3x3 25 : 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 8 < x1 2x2 C x3 D 16 x2 C 4x3 C x4 8 : x2 2x3 C 3x4 20 xj 0; j D 1; : : : ; 4 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 zD 5x1 C x2 C x3 C 16x4 ! max Với các ràng buộc 8 < x1 C x2 C 2x3 3x4 D 5 2x1 x2 C x3 C 5x4 D 2 : 3x1 C 4x2 C 7x3 8x4 D 9 xj 0; j D 1; : : : ; 4 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
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 8 < x1 2x2 C x3 C 3x4 2x5 D 6 2x1 3x2 C 2x3 C x4 x5 4 : x1 C 3x3 4x5 8 x1 ; x3 ; x5 0 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 .5I 6I 1I 4I 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.
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 .5I 6I 1I 4I 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.
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ử: PP PP PP Thu PP b1 b2 bj bn Phát PP P a1 c11 c12 c1j c1n a2 c21 c22 c2j c2n :: :: :: :: :: : : : : : ai ci1 ci 2 cij ci n :: :: :: :: :: : : : : : 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 X n X ai D bj (4.1) i D1 j D1 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 :

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.