NGÂN HÀNG MÔN QUY HOẠCH TUYẾN TÍNH

TRƢỜNG ĐH CÔNG NGHIỆP TPHCM

KHOA KHOA HỌC CƠ BẢN

NGÂN HÀNG MÔN QUY HOẠCH TUYẾN TÍNH

Câu 1. Cho bài tóan Quy họach tuyến tính mà ta gọi là bài tóan (P)

là phƣơng án cực biên tối ƣu của bài tóan (P).

1) Chứng minh 2) Viết bài tóan đối ngẫu của bài tóan (P) và tìm phƣơng án tối ƣu của bài tóan đối ngẫu.

Câu 2. 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 II III

I NL SP A B C 1 1 2 1 2 3 3 2 1

Xí nghieäp muoán leân moät 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.

1) Lập mô hình bài toán Quy hoạch tuyến tính. 2) Bằng phƣơng pháp đơn hình, hãy giải bài toán trên. Câu 3. Cho bài tóan Quy họach tuyến tính mà ta gọi là bài tóan (P)

là phƣơng án cực biên tối ƣu của bài tóan (P).

1) Chứng minh 2) Viết bài tóan đối ngẫu của bài tóan (P) và tìm phƣơng án tối ƣu của bài tóan đối ngẫu.

Câu 4. 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à 50, 55, 60. 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 II III

I NL SP A B C 2 3 2 3 2 3 3 5 1

Xí nghieäp muoán leân moät 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 4 triệu đồng cho một đơn vị sản phẩm loại A, lãi 5 triệu đồng cho một đơn vị sản phẩm loại B, lãi 3 triệu đồng cho một đơn vị sản phẩm loại C.

1) Lập mô hình bài toán Quy hoạch tuyến tính. 2) Bằng phƣơng pháp đơn hình, hãy giải bài toán trên.

Câu 5. Cho bài tóan Quy họach tuyến tính mà ta gọi là bài tóan (P)

1) Liệt kê tất cả các phƣơng án cực biên của bài toán (P). 2) Chứng tỏ bài toán có phƣơng án tối ƣu. Từ đó chỉ ra phƣơng án cực biên tối ƣu. 3) Phát biểu bài toán đối ngẫu của bài toán (P), và tìm phƣơng án tối ƣu của bài toán đối ngẫu.

Câu 6. Một Xí nghiệp chăn nuôi cần mua một lọai 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 lọai 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.

Câu 7. Cho bài tóan Quy họach tuyến tính (P)

Câu 8. Một Xí nghiệp chăn nuôi cần mua một lọai 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 lọai 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à 15 ngàn đồng, 1 kg T2 có giá là 17 ngàn đồng, 1 kg T3 có giá là 19 ngàn đồng.

Câu 9. 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, Dầu thực vật, với trữ lƣợng 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. Để sản xuấ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 ?

Câu 10. Cho bài toán Quy họach tuyến tính (với n là số nguyên dƣơng tùy ý ).

1) Phát biểu bài toán đối ngẫu của bài toán trên . 2) 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.

Câu 11. Cho bài toán Quy họach tuyến tính (P)

Câu 12. Cho bài toán Quy họach tuyến tính, mà ta gọi là bài toán (P).

Câu 13. 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 xƣởng bao nhiêu tiền để xí nghiệp thỏa

Hoàn thành công việc. Giá tiền đầu tƣ là nhỏ nhất.

Câu 14. Một Xí nghiệp chăn nuôi cần mua một lọai 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 3 đơn vị dinh dƣỡng D1, 1 đơn vị dinh dƣỡng D2; 1 kg T2 chứa 4 đơn vị dinh dƣỡng D1, 2 đơn vị dinh dƣỡng D2; 1 kg T3 chứa 2 đơn vị dinh dƣỡng D1, 3 đơn vị dinh dƣỡng D2. Mỗi bữa ăn, gia súc cần tối thiểu 160 đơn vị D1, 140 đơn vị D2. Hỏi Xí nghiệp phải mua bao nhiêu kg T1, T2, T3 mỗi lọai 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à 15 ngàn đồng, 1 kg T2 có giá là 12 ngàn đồng, 1 kg T3 có giá là 10

ngàn đồng.

Câu 15. Một Xí nghiệp chăn nuôi cần mua một lọai thức ăn tổng hợp T1, T2 cho gia súc với tỷ lệ chất dinh dƣỡng nhƣ sau: 1 kg T1 chứa 3 đơn vị dinh dƣỡng D1, 1 đơ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, 1 đơn vị dinh dƣỡng D2, và 2 đơn vị dinh dƣỡng D3. Mỗi bữa ăn, gia súc cần tối thiểu 60 đơn vị D1, 40 đơn vị D2 và 60 đơn vị D3.

Hỏi Xí nghiệp phải mua bao nhiêu kg T1, T2 mỗi lọai 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à 20 ngàn đồng, 1 kg T2 có giá là 15 ngàn đồng. Câu 16. Cho bài toán Quy họach tuyến tính

1) Phát biểu bài toán đối ngẫu của bài toán trên . 2) 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.

Câu 17. Cho bài toán Quy họach tuyến tính

1) Phát biểu bài toán đối ngẫu của bài toán trên . 2) 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. Câu 18. Cho bài toán

1) Phát biểu bài toán đối ngẫu của bài toán trên . 2) 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.

Câu 19. Cho bài toán Quy họach tuyến tính

1) Phát biểu bài toán đối ngẫu của bài toán trên . 2) 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.

Câu 20. Một xí nghiệp dự định sản xuất hai loại sản phẩm A và B. 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à 8, 21, 10. 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 cho ở bảng sau đây.

NL I II III

SP A 3 0 5

B 2 6 0

(Nghĩa là khi sản xuất một đơn vị sản phẩm loại A cần 3 đơn vị nguyên liệu I, không cần nguyên liệu loại II, cần 5 đơn vị nguyên liệu loại III. Khi sản xuất một đơn vị sản phẩm loại B cần 2 đơn vị nguyên liệu I, 6 đơn vị nguyên liệu loại II, không cần nguyên liệu loại III).

Cần lập một kế hoạch sản xuất,( tức là tính xem nên sản xuất bao nhiêu đơn vị sản phẩm từng loại) để lãi thu đƣợc là nhiều nhất. Biết sản phẩm A lãi 4 triệu đồng cho một đơn vị sản phẩm, sản phẩm B lãi 5 triệu đồng cho một đơn vị sản phẩm.

Câu 21. 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 ?

Câu 22. Một Xí nghiệp xử lý giấy , có ba phân xƣởng I, II, III cùng xử lý ba loại giấy A, B, C. Do ba 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, 1 tạ giấy loại B, 3 tạ giấy loại C. Trong khi đó phân xƣởng II xử lý đƣợc 2 tạ giấy loại A, 7 tạ giấy loại B, 1 tạ giấy loại C. Phân xƣởng III xử lý đƣợc 1 tạ giấy loại A, 3 tạ giấy loại B, 8 tạ giấy loại C. Theo yêu cầu lao động thì cuối kỳ Xí nghiệp phải xử lý ít nhất 2 tấn giấy loại A, 2.5 tấn giấy loại B, 3 tấn giấy loại C. Hỏi cần đầu tƣ vào mỗi phân xƣởng bao nhiêu tiền để xí nghiệp thỏa: hoàn thành công việc và giá tiền đầu tƣ là nhỏ nhất. Câu 23. 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, Dầu thực vật, với trữ lƣợng tƣơng ứng là 30 tấn,18 tấn, 6 tấn . Để sản xuất 1 tấn thực phẩm loại A cần 0.8 tấn Bột, 0.5 tấn Đƣờng, 0.2 tấn Dầu thực vật. Để sản xuất 1 tấn thực phẩm loại B cần 0.7 tấn Bột, 0.4 tấn Đƣờng, 0.3 tấn Dầu thực vật. Qua khảo sát sở thích ngƣời tiêu dùng công ty biết rằng nhu cầu về thực phẩm A không hơn thực phẩm B quá 2 tấn. 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à 3000 USD. Khi sản xuất 1 tấn thực phẩm A phải bỏ ra một chi phí là 1300 USD, khi sản xuất 1 tấn thực phẩm B phải bỏ ra một chi phí là 1000 USD.

Hỏi cần sản xuất mỗi loại thực phẩm bao nhiêu tấn để có lợi nhuận lớn nhất ?

Câu 24. Một xí nghiệp dự định sản xuất hai loại sản phẩm A và B. 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à 10, 12, 15. 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 cho ở bảng sau đây

N I II III

L SP

A B 1 2 2 1 1 3

Qua tìm hiểu thị trƣờng xí nghiệp biết tổng số cả hai sản phẩm A, B mà thị trƣờng cần không quá 13 tấn.

Lập mô hình bài toán Quy hoạch tuyến tính.

Câu 25. 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à 15, 12, 18. 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 và đƣợc cho ở bảng sau đây

I I I S I II P NL

1 2 1 A

2 1 3 B

0 2 5 C

Qua tìm hiểu thị trƣờng xí nghiệp biết cả ba sản phẩm A, B và C mà thị trƣờng cần ít nhất là 2 đơn vị cho mỗi sản phẩm.

Xí nghieäp muoán leân moät 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 7 triệu đồng cho một đơn vị sản phẩm loại A, lãi 5 triệu đồng cho một đơn vị sản phẩm loại B, lãi 10 triệu đồng cho một đơn vị sản phẩm loại C.

Lập mô hình bài toán Quy hoạch tuyến tính. Câu 26. Giải bài toán Quy hoạch tuyến tính (có thể giải bằng phƣơng pháp hình học)

Câu 27. Giải bài toán sau đây và từ đó suy ra phƣơng án tối ƣu (nếu có) của bài toán đối ngẫu của nó

Câu 28. Giải bài toán sau đây và từ đó suy ra phƣơng án tối ƣu (nếu có) của bài toán đối ngẫu của nó

Câu 29. Giải bài toán sau đây và từ đó suy ra phƣơng án tối ƣu (nếu có) của bài toán đối ngẫu của nó

Câu 30. Giải bài toán sau đây và từ đó suy ra phƣơng án tối ƣu (nếu có) của bài toán đối ngẫu của nó

Câu 31. Giải bài toán sau đây và từ đó suy ra phƣơng án tối ƣu (nếu có) của bài toán đối ngẫu của nó

Câu 32. Giải bài toán sau đây và từ đó suy ra phƣơng án tối ƣu (nếu có) của bài toán đối ngẫu của nó

Câu 33. Giải bài toán sau đây và từ đó suy ra phƣơng án tối ƣu (nếu có) của bài toán đối ngẫu của nó

Câu 34. Giải bài toán sau đây và từ đó suy ra phƣơng án tối ƣu (nếu có) của bài toán đối ngẫu của nó

Câu 35. Giải bài toán sau đây và từ đó suy ra phƣơng án tối ƣu (nếu có) của bài toán đối ngẫu của nó

Câu 36. Giải bài toán sau đây và từ đó suy ra phƣơng án tối ƣu (nếu có) của bài toán đối ngẫu của nó

Câu 37. Giải bài toán sau đây và từ đó suy ra phƣơng án tối ƣu (nếu có) của bài toán đối ngẫu của nó

Câu 38. Giải bài toán sau đây và từ đó suy ra phƣơng án tối ƣu (nếu có) của bài toán đối ngẫu của nó

Câu 39. Giải bài toán sau đây và từ đó suy ra phƣơng án tối ƣu (nếu có) của bài toán đối ngẫu của nó

Câu 40. Giải bài toán sau đây và từ đó suy ra phƣơng án tối ƣu (nếu có) của bài toán đối ngẫu của nó

Câu 41. Giải bài toán sau đây và từ đó suy ra phƣơng án tối ƣu (nếu có) của bài toán đối ngẫu của nó

Câu 42. Giải bài toán sau đây và từ đó suy ra phƣơng án tối ƣu (nếu có) của bài toán đối ngẫu của nó

Câu 43. Giải bài toán sau đây và từ đó suy ra phƣơng án tối ƣu (nếu có) của bài toán đối ngẫu của nó

Câu 44. Một Xí nghiệp xử lý giấy , có ba phân xƣởng I, II, III cùng xử lý ba loại giấy A, B, C. Do ba 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 7 tạ giấy loại A, 2 tạ giấy loại B, 3 tạ giấy loại C. Trong khi đó phân xƣởng II xử lý đƣợc 3 tạ giấy loại A, 6 tạ giấy loại B, 1 tạ giấy loại C. Phân xƣởng III xử lý đƣợc 1 tạ giấy loại A, 3 tạ giấy loại B, 8 tạ giấy loại C. Theo yêu cầu lao động thì cuối kỳ Xí nghiệp phải xử lý ít nhất 3 tấn giấy loại A, 3 tấn giấy loại B, 4 tấn giấy loại C. Hỏi cần đầu tƣ vào mỗi phân xƣởng bao nhiêu tiền để xí nghiệp thỏa

Hoàn thành công việc. Giá tiền đầu tƣ là nhỏ nhất.

Câu 45. 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, III và IV. Số lƣợng các nguyên liệu I, II, III và IV mà xí nghiệp có tối đa lần lƣợt là 380, 204, 120, 180. 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. II III IV

12 0 1 4

11 26 0 3

8 9 15 2 I NL SP A B C

Xí nghieäp muoán leân moät kế hoạch sản xuất để thu đƣợc tổng số lãi nhiều nhất (với giả thiết rằng các sản phẩm làm ra đều bán hết). Nếu biết rằng lãi 3 triệu đồng cho một đơn vị sản phẩm loại A, lãi 5 triệu đồng cho một đơn vị sản phẩm loại B và C.

Lập mô hình bài toán. Tìm một phƣơng án sao cho xí nghiệp có lãi nhiều nhất.

Câu 46. 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 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 ?

Câu 47. Giải bài toán sau đây và từ đó suy ra phƣơng án tối ƣu (nếu có) của bài toán đối ngẫu của nó

Câu 48. Giải bài toán sau đây và từ đó suy ra phƣơng án tối ƣu (nếu có) của bài toán đối ngẫu của nó

Câu 49. Giải bài toán sau đây và từ đó suy ra phƣơng án tối ƣu (nếu có) của bài toán đối ngẫu của nó

Câu 50. Tìm phƣơng án tối ƣu của bài toán Quy hoạch tuyến tính

Câu 51. Cho bài toán Quy hoạch tuyến tính

1) Phát biểu bài toán đối ngẫu của bài toán trên . 2) 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 (có thể giải bằng phƣơng pháp hình học). Câu 52. Cho bài toán Quy hoạch tuyến tính

1) Phát biểu bài toán đối ngẫu của bài toán trên . 2) 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. Câu 53. Cho bài toán Quy hoạch tuyến tính

1) Phát biểu bài toán đối ngẫu của bài toán trên . 2) 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. Câu 54. Cho bài toán Quy hoạch tuyến tính

1) Phát biểu bài toán đối ngẫu của bài toán trên . 2) 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. Câu 55. Cho bài toán Quy hoạch tuyến tính

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 bài toán gốc bằng thuật toán đơn hình và tìm phƣơng án tối ƣu của bài toán đối ngẫu. Câu 56. Cho bài toán Quy hoạch tuyến tính

1) Phát biểu bài toán đối ngẫu của bài toán trên . 2) Hãy giải bài toán gốc bằng thuật toán đơn hình và tìm phƣơng án tối ƣu của bài toán đối ngẫu. Câu 57. Cho bài toán Quy hoạch tuyến tính mà ta gọi là bài tóan (P)

là phƣơng án tối ƣu của bài tóan (P). Viết bài tóan đối ngẫu của

Cho biết bài tóan (P) và tìm phƣơng án tối ƣu của bài tóan đối ngẫu. Câu 58. Cho bài toán Quy hoạch tuyến tính mà ta gọi là bài tóan (P)

1) Hỏi có phải là phƣơng án tối ƣu của bài tóan (P)?

2) Viết bài tóan đối ngẫu của bài tóan (P) và tìm phƣơng án tối ƣu của bài tóan đối ngẫu.

Câu 59. Cho bài toán Quy hoạch tuyến tính mà ta gọi là bài tóan (P)

1) Hỏi có phải là phƣơng án tối ƣu của bài tóan (P)?

2) Viết bài tóan đối ngẫu của bài tóan (P) và tìm phƣơng án tối ƣu của bài tóan đối ngẫu.

Câu 60. Cho bài toán Quy hoạch tuyến tính mà ta gọi là bài tóan (P)

là phƣơng án tối ƣu của bài tóan (P). Viết bài tóan đối ngẫu của

Cho biết bài tóan (P) và tìm phƣơng án tối ƣu của bài tóan đối ngẫu. Câu 61. Cho bài toán Quy hoạch tuyến tính mà ta gọi là bài tóan (P)

là phƣơng án tối ƣu của bài tóan (P). Viết bài tóan đối ngẫu của

Cho biết bài tóan (P) và tìm phƣơng án tối ƣu của bài tóan đối ngẫu. Câu 62. Giải bài toán Quy hoạch tuyến tính

là phƣơng án tối ƣu của bài

Câu 63. Cho biết toán Quy hoạch tuyến tính gốc sau:

1) Phát biểu bài toán đối ngẫu của bài toán trên. 2) Hãy suy ra phƣơng án tối ƣu của bài toán đối ngẫu từ phƣơng án tối ƣu đã cho của bài tóan gốc. Câu 64. Cho bài toán Quy hoạch tuyến tính

1) Giải bài toán trên. 2) Phát biểu bài toán đối ngẫu của bài toán trên . Câu 65. Giải bài toán Quy hoạch tuyến tính

Câu 66. Giải bài toán sau đây và từ đó suy ra phƣơng án tối ƣu (nếu có) của bài toán đối ngẫu của nó

Câu 67. Cho biết là phƣơng án tối ƣu của bài

toán Quy hoạch tuyến tính gốc sau:

1)Phát biểu bài toán đối ngẫu của bài toán trên . 2)Hãy suy ra phƣơng án tối ƣu của bài toán đối ngẫu từ phƣơng án tối ƣu đã cho của bài tóan gốc. Câu 68. Cho bài toán Quy hoạch tuyến tính

1) Phát biểu bài toán đối ngẫu của bài toán trên . 2) 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. Câu 69. Cho bài toán Quy hoạch tuyến tính

1) Phát biểu bài toán đối ngẫu của bài toán trên .

2) 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.

Câu 70. Giải bài toán sau đây và từ đó suy ra phƣơng án tối ƣu (nếu có) của bài toán đối ngẫu của nó

Câu 71. Cho bài tóan vận tải cân bằng thu phát và phƣơng án (phƣơng án đƣợc xây dựng bằng phƣơng pháp góc Tây – Bắc) 30 40 50 60

1 30 5 5 40 7

12 2 7 10 4 40 3 80 45 55 9 5 6 55

1) Tính cƣớc phí vận chuyển của phƣơng án trên và chứng tỏ phƣơng án này không phải là phƣơng án tối ƣu. 2) 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).

Câu 72. Cho bài tóan vận tải cân bằng thu phát và phƣơng án (phƣơng án đƣợc xây dựng bằng phƣơng pháp góc Tây – Bắc) 40 50 60 60 2

10 50 5 10 12 5 7 40 12 50 75 85 17 5 4 25 6 1 60 25

Phƣơng án (1) đƣợc xây dựng bằng phƣơng pháp góc Tây – Bắc Câu 73. Cho bài tóan vận tải cân bằng thu phát và hai phƣơng án. 160 120 140 130 25

20 130 15 45 18 40 25 120 30 170 200 180 22 30 80 40 40 15 35 140

Phƣơng án (2) đƣợc xây dựng bằng phƣơng pháp cực tiểu theo bảng cƣớc phí 160 120 140 130

18 160 25 30 170 200 180 20 15 130 45 22 10 30 40 110 15 70 35 70

1) Hỏi phƣơng án nào tốt hơn. 2) Xuất phát từ phƣơng án (1) 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)

Câu 74. Cho bài tóan vận tải cân bằng thu phát và một phƣơng án đƣợc xây dựng bằng phƣơng pháp cực tiểu theo bảng cƣớc phí (tức phƣơng pháp “min cƣớc”) nhƣ sau 40 30 20 1 3 20 10 5 2

4 5 30 25 35 5 8 25 4 5 30

1) Hỏi phƣơng án này có phải là phƣơng án tối ƣu không. 2) Xuất phát từ phƣơng án này 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).

Câu 75. Cho bài tóan vận tải và một phƣơng án đƣợc xây dựng bằng phƣơng pháp cực tiểu theo bảng cƣớc phí (tức phƣơng pháp “min cƣớc”) nhƣ sau 25 10 25 5

7 3 6 1 10 8 25 5 2 2 10 30 20 3 20

1) Hỏi phƣơng án này là phương án cực biên không suy biến có phải không? 2) Xuất phát từ phƣơng án này 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).

Câu 76. Cho bài tóan vận tải cân bằng thu phát và một phƣơng án đƣợc xây dựng bằng phƣơng pháp cực tiểu theo bảng cƣớc phí (tức phƣơng pháp “min cƣớc”) nhƣ sau

20 60 80 5

3 1 50 6 4 2 20 20 7 9 50 40 70 60 11 10

Câu 77. Cho bài tóan vận tải cân bằng thu phát sau 70 40 30 60 2 3

5 4 2 6

6 5 1 100 3 80 1 20 2

1) Xây dựng một phƣơng án cực biên. 2) Xuất phát từ phƣơng án cực biên này hãy giải bài tóan vận tải trên.

Câu 78. Cho bài tóan vận tải cân bằng thu phát và hai phƣơng án. Phƣơng án (1) đƣợc xây dựng bằng phƣơng pháp cực tiểu theo bảng cƣớc phí (tức phƣơng pháp “min cƣớc”): 80 120 45 30 25 7 12 6 70 3 9 4 9 45 8 5 2 6 3 40 6 25 10 11 5 10 7 8 11 1 70 85 35 110 80 30

Phƣơng án (2) đƣợc xây dựng bằng phƣơng pháp góc Tây – Bắc: 80 120 45 30 25

7 12 6 45 2 25 6 9 4 3 9 35 8 5 50 6

11 3 5 7 35 8 10 11 1 70 85 35 110 35 45 30

1) Phƣơng án (1) và phƣơng án (2) có phải là các phương án cực biên không suy biến? 2) Trong hai phƣơng án đã cho, phƣơng án nào là phƣơng án tốt hơn và phƣơng án tốt hơn đó có phải là phƣơng án tối ƣu không?

Câu 79. Cho bài tóan vận tải cân bằng thu phát: 45 76 20 52 46 10 13 8 5 1 6 10 8 13

5 3 8 6

13 2 5 7 9 10 13 79 50 60 50

1) Bằng phƣơng pháp “min cƣớc”, hãy xây dựng một phƣơng án cực biên. 2) Hỏi phƣơng án có đƣợc từ câu (1) có phải là phƣơng án tối ƣu không?

Câu 80. Cho bài tóan vận tải cân bằng thu phát : 80 65 35 95 95 7 14 9 13

6 2 9 8 10

10 5 9 12

14 5 3 12 6 4 18 110 100 60 100

1) Bằng phƣơng pháp “min cƣớc”, hãy xây dựng một phƣơng án cực biên.

2) Xuất phát từ phƣơng án này 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)

Câu 81. Giải bài tóan vận tải không cân bằng thu phát sau: 40 60 20 3

4 1 3

4 2 5 6 80 30 50 1

Câu 82. Cho bài tóan vận tải không cân bằng thu phát sau: 30 50 10 7

2 5 4

6 1 5 2 25 10 45 3

1) Giải bài tóan. 2) Giải bài tóan với điều kiện trạm thu thứ hai phải nhận đủ hàng. Câu 83. Đại hội thế vận đƣợc tổ chức đồng loạt cùng ngày ở 4 địa điểm. Các nhu cầu vật chất (tấn) đƣợc phát đi từ 3 địa điểm. Các dữ liệu về yêu cầu thu phát và cự ly (km) đƣợc cho trong bảng dƣới đây. Do đặc điểm của các phƣơng tiện vật chất, thời gian và phƣơng tiện vận tải, nên không thể chuyển quá xa trên 150 km. Tìm phƣơng án chuyên chở sao cho tổng số chiều dài quãng đƣờng là nhỏ nhất. 10 17 18

15 160 70 50 100 200 100 30 60

40 50 20 30 10 30 50

Câu 84. Cho bài tóan vận tải: 20 60 80 50 5 4 2

7 40 70 3 9

Trong đó ô(2,1) và ô(3,3) là ô cấm, tức là tuyến đƣờng từ nơi phát hàng thứ 2 đến nơi nhận hàng thứ 1 và tuyến đƣờng từ nơi phát hàng thứ 3 đến nơi nhận hàng thứ 3 không thể đi qua đƣợc.

1) Xây dựng một phƣơng án cực biên. 2) Xuất phát từ phƣơng án này 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)

Câu 85. Giải bài tóan vận tải cân bằng thu phát: 40 50 60 30 1 2

5 7 4 9

5 7 2 3 80 45 55 6 12

Câu 86. Cho bài tóan vận tải cân bằng thu phát: 40 70 50 5

7 12 11

5 9 2 3 80 20 60 4

1) Bằng phƣơng pháp “min cƣớc”, hãy xây dựng một phƣơng án cực biên. Tính cƣớc phí vận chuyển của phƣơng án này. 2) Xuất phát từ phƣơng án này 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). Tính sự chênh lệch cƣớc phí giữa 2 phƣơng án này.

Câu 87. Giải bài tóan vận tải không cân bằng thu phát: 55 65 70 5

70 90 7 8 1 3 4

9 60 13 4

Câu 88. Giải bài tóan vận tải cân bằng thu phát: 70 90 40 5

4 9 10

6 2 5 100 45 55 4

Trong đó ô(2,2) là ô cấm, tức là tuyến đƣờng từ nơi phát hàng thứ 2 đến nơi nhận hàng thứ 2 không thể đi qua đƣợc. Câu 89. Giải bài tóan vận tải sau cân bằng thu phát: 55 60 45 5

2 3 4 70 90 2 1

Câu 90. Giải bài tóan vận tải cân bằng thu phát sau: 20 30 50 6

5 2 3 60 40 1 4

Câu 91. Giải bài tóan vận tải cân bằng thu phát: 40 70 50 5

7 12 11

4 5 9 2 3 80 20 60

Câu 92. Giải bài tóan vận tải cân bằng thu phát: 55 60 80 30 45 5 6 10

2 1 3 4 9 4

2 6 5 6

1 5 12 13 8 7 7 70 90 50 60

Câu 93. Giải bài tóan vận tải cân bằng thu phát: 40 70 50 5

7 12 11

5 9 2 3 80 20 60 4

Câu 94. Giải bài tóan vận tải cân bằng thu phát: 40 50 60 30 1 2

5 7 4 9

5 7 2 3 6 80 45 55 12

Câu 95. Giải bài tóan vận tải cân bằng thu phát: 20 60 80 5

4 2 1 6

50 40 70 7 9

Trong đó ô(2,1) và ô(3,3) là ô cấm, tức là tuyến đƣờng từ nơi phát hàng thứ 2 đến nơi nhận hàng thứ 1 và tuyến đƣờng từ nơi phát hàng thứ 3 đến nơi nhận hàng thứ 3 không thể đi qua đƣợc. Câu 96. Giải bài tóan vận tải cân bằng thu phát: 80 65 35 95 95 7 14 9 13

6 2 9 8 10

10 5 9 12

14 5 3 12 6 4 18 110 100 60 100

Câu 97. Giải bài tóan vận tải cân bằng thu phát: 45 76 20 52 46 10 13 8 5 1 6 10 8 13

5 3 8 6

13 2 5 7 9 10 13 79 50 60 50

Câu 98. Giải bài tóan vận tải cân bằng thu phát: 70 40 30 60 2 3

5 4 2 6

6 5 1 100 3 80 20 1 2

Câu 99. Giải bài tóan vận tải cân bằng thu phát:

20 60 80 5

3 1 6

7 50 40 70 11 4 2 9

Câu 100. Giải bài tóan vận tải cân bằng thu phát: 25 10 25 5

7 1 8

3 6 2 2 10 30 20 3

Câu 101. Giải bài tóan vận tải cân bằng thu phát: 40 30 20 1

5 2

3 4 5 4 30 25 35 5 8

Câu 102. Cho bài tóan vận tải cân bằng thu phát và hai phƣơng án. Phƣơng án (1) đƣợc xây dựng bằng phƣơng pháp cực tiểu theo bảng cƣớc phí (tức phƣơng pháp “min cƣớc”): 40 70 20

9 60 3 10 6 2 1 20 2 80 30 20 10 20 4 2 20

Phƣơng án (2) đƣợc xây dựng bằng phƣơng pháp Voghen 70 20 40

9 60 3 10 6 2 20 1 2 80 30 20 10 20 4 2 20

1) Hỏi các phƣơng án này có phải là các phương án cực biên không suy biến? 2) Hỏi phƣơng án nào là phƣơng án tốt hơn? 3) Kiểm tra tính tối ƣu của các phƣơng án.

Giáo trình tham khảo: 1) Qui hoạch tuyến tính, TS.Nguyễn Phú Vinh và Ths.Nguyễn Đình Tùng, ĐHCN Tp.HCM. 2) Qui hoạch tuyến tính, TS.Võ Văn Tuấn Dũng, ĐHCN Tp.HCM. 3) Bài tập qui hoạch tuyến tính, GS.Trần Túc, ĐH kinh tế quốc dân Tp.HCM. 4) Qui hoạch tuyến tính, GS.Đặng Hấn, ĐH kinh tế TPHCM.