TRƯỜNG ĐẠI HỌC SÀI GÒN        ĐỀ THI KẾT THÚC MÔN HỌC     KHOA TOÁN - ỨNG DỤNG HỆ CAO ĐẲNG CHÍNH QUI

                                                                            Môn thi: Qui hoạch tuyến tính                     

                                                                            Học kì I  –  Năm học 2010- 2011

                                                             Lớp: CKE. Thời gian làm bài: 60 phút

(Sinh viên không được tham khảo tài liệu để làm bài)

Câu 1. Một xí nghiệp sản xuất ba loại sản phẩm A, B và C từ ba loại nguyên liệu dự trữ I, II và III với số lượng đơn vị từ các nguyên liệu dự trữ hiện có lần lượt là 120, 80 và 160. Để sản xuất ra mỗi đơn vị sản phẩm loại A cần sử dụng 3 đơn vị nguyên liệu dự trữ loại I, 2 đơn vị nguyên liệu dự trữ loại II và 1 đơn vị nguyên liệu dự trữ loại III. Các số liệu tương tự cho mỗi đơn vị sản phẩm loại B và C lần lượt là 4, 1, 3 và 2, 2, 2. Biết lợi nhuận thu được trên mỗi đơn vị sản phẩm loại A, B và C lần lượt là 2 triệu đồng, 4 triệu đồng và 3 triệu đồng. Anh (chị) hãy

a)     Thiết lập bài toán quy hoạch tuyến tính (P) để xí nghiệp sản xuất đạt lợi nhuận tối đa và tìm phương án tối ưu của bài toán;

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

Câu 2. Cần vận chuyển một loại hàng từ bốn kho hàng đến năm nơi tiêu thụ (cửa hàng). Số lượng đơn vị hàng ở các kho tương ứng là , số lượng đơn vị hàng cần có ở các cửa hàng là  và cước phí vận chuyển một đơn vị hàng từ kho thứ i đến cửa hàng thứ j cho bởi ma trận sau:

a)     Hãy lập kế hoạch vận chuyển hàng sao cho đảm bảo cung cầu và cước phí vận chuyển nhỏ nhất (phương án tối ưu).

b)     Ngoài phương án tối ưu tìm được ở câu a) bài toán trên còn có phương án tối ưu khác hay không? Nếu có, hãy chỉ ra tập phương án tối ưu của nó.

   TRƯỜNG ĐẠI HỌC SÀI GÒN        ĐỀ THI KẾT THÚC MÔN HỌC     KHOA TOÁN - ỨNG DỤNG HỆ CAO ĐẲNG CHÍNH QUI

                                                                            Môn thi: Qui hoạch tuyến tính                     

                                                                            Học kì I  –  Năm học 2010- 2011

                                                             Lớp: CKE. Thời gian làm bài: 60 phút

(Sinh viên không được tham khảo tài liệu để làm bài)

Câu 1. Xí nghiệp sản xuất giấy có 3 phân xưởng. Do trang bị kỹ thuật khác nhau nên mức hao phí tre gỗ, axit để sản xuất một tấn giấy thành phẩm cũng khác nhau. Mức hao phí được cho trong bảng dưới đây:

Số lượng tre gỗ có trong năm là 1.500.000 tấn, Axit là 100.000 tấn. Anh (chị) hãy  

a)     Thiết lập bài toán quy hoạch tuyến tính (P) sao cho tổng số giấy sản xuất trong năm của xí nghiệp là nhiều nhất và tìm phương án tối ưu của bài toán;

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

Câu 2. Cần vận chuyển một loại hàng từ bốn kho hàng đến năm nơi tiêu thụ (cửa hàng). Số lượng đơn vị hàng ở các kho tương ứng là , số lượng đơn vị hàng cần có ở các cửa hàng là  và cước phí vận chuyển một đơn vị hàng từ kho thứ i đến cửa hàng thứ j cho bởi ma trận sau:

a)     Hãy lập kế hoạch vận chuyển hàng sao cho đảm bảo cung cầu và cước phí vận chuyển nhỏ nhất (phương án tối ưu).

b)     Ngoài phương án tối ưu tìm được ở câu a) bài toán trên còn có phương án tối ưu khác hay không? Nếu có, hãy chỉ ra tập phương án tối ưu của nó.

Đáp án

Câu 1.

a)     Gọi : là số lượng sản phẩm loại A, B, và C (j=1,2,3)

Ta có mô hình bài toán (P):

.

Giải bài toán (P) bằng phương pháp đơn hình

Câu 1.

1.     Gọi : là số lượng giấy do phân xưởng thứ j sản xuất, j=1,2,3.

Ta có mô hình bài toán:

.

Giải bài toán (P) bằng phương pháp đơn hình

2.     Gọi : là giá trị của tre gỗ và axit.

Ta có mô hình bài toán (D):

Từ bảng đơn hình ta có kết quả của bài toán (D), như sau:

và .

Câu 2.

·        Kiểm tra điều kiện cân bằng thu phát, ta có .

·        Xây dựng phương án ban đầu:

·        Kiểm tra tính tối ưu, ta thấy .

·        Xây dựng phương án mới:

·        Kiểm tra tính tối ưu, ta thấy . Ta có phương án tối ưu của bài toán:

, và đơn vị tiền tệ.