TRƯỜNG ĐẠI HỌC SÀI GÒN                ĐỀ THI KẾT THÚC MÔN HỌC         

PHÒNG ĐÀO TẠO TẠI CHỨC & TNGV   Môn thi: Qui hoạch tuyến tính                                                             Lớp: DKE31115                             

                                                                             Thời gian làm bài: 60 phút

Câu 1. Một xí nghiệp sản xuất ba loại sản phẩm A, B và C bằng ba loại dự trữ D, E và F với số lượng hiện có lần lượt là 60, 80 và 120 đơn vị. Để sản xuất ra mỗi đơn vị sản phẩm A cần sử dụng 2 đơn vị dự trữ D, 6 đơn vị dự trữ E và 1 đơn vị dự trữ F. Các chỉ số đó cho mỗi đơn vị sản phẩm B và C theo thứ tự trên là 4; 0; 2 và 6; 2; 4. Cho biết lợi nhuận thu được trên mỗi đơn vị sản phẩm A, B và C là 4 triệu đồng, 6 triệu đồng và 8 triệu đồng.

1.     Hãy thiết lập bài toán qui hoạch tuyến tính nhằm đạt tổng lợi nhuận tối đa và tìm phương án sản xuất tối ưu bằng phương pháp thích hợp.

2.     Viết bài toán đối ngẫu của bài toán qui hoạch tuyến tính trên; nêu ý nghĩa kinh tế của bài toan đối ngẫu và tìm phương án tối ưu của nó.

Câu 2. Một công ty có ba xí nghiệp cùng sản xuất một loại sản phẩm. Năng suất trong tháng của ba xí nghiệp lần lượt là  sản phẩm. Hợp đồng công ty phải giao cho bốn nhà phân phối là  sản phẩm. Đơn giá (đơn vị tính: 1000 đồng) của mỗi sản phẩm tương ứng với các nhà phân phối được cho bởi ma trận sau:

Hãy tìm kế hoạch phân phối hàng sao cho công ty đạt doanh số lớn nhất.

Đề 01

Câu 1.

1.     Gọi  là số đơn vị sản phẩm loại A, B, C cần sản xuất. Ta có mô hình bài toán:

·        Đưa bài toán về dạng chính tắc và bảng đơn hình đầu các bảng trung gian và cuối.

·        .

2.     Bài toán đối ngẫu:

·        Dựa vào bảng tối ưu của bài toán 1, ta có  và

Câu 2.

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

·        Ta thêm một trạm phát giả  và .

·        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à

      TRƯỜNG ĐẠI HỌC SÀI GÒN                ĐỀ THI KẾT THÚC MÔN HỌC         

PHÒNG ĐÀO TẠO TẠI CHỨC & TNGV   Môn thi: Qui hoạch tuyến tính                                                             Lớp: DKE31115                             

                                                                             Thời gian làm bài: 60 phút

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. Cho bài toán vận tải có số lượng phát , số lượng thu  và ma trận cước phí  có dạng sau:

và

a)     Giải bài toán vận tải trên;

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ó.

Baøi toaùn ôû daïng chuaån:

F(x) =  2x₁ + 3x₂ + 4x₃ => MAX          

Caùc raøng buoäc:

            3x₁      + 4x₂    + 2x₃    + x₄      = 120

            2x₁      + x₂      + 2x₃    + x₅      = 80

            x₁        + 3x₂    + 2x₃    + x₆      = 160

Trong ñoù:

            x₄, x₅, x₆ laø bieán phuï

            x₁ >=0, x₂ >=0, x₃ >=0, x₄ >=0, x₅ >=0, x₆ >=0

Do coøn toàn taïi giaù trò Delta nhoû hôn 0 neân chöa coù phöông aùn toái öu ta caàn tìm bieán ñöa vaøo 

 Coät coù giaù trò nhoû nhaát öùng vôùi x₃ vaäy bieán ñöa vaøo laø : x₃

 Haøng coù giaù trò Lamda nhoû nhaát öùng vôùi coät ñoù laø haøng 2

Do coøn toàn taïi giaù trò Delta nhoû hôn 0 neân chöa coù phöông aùn toái öu ta caàn tìm bieán ñöa vaøo 

 Coät coù giaù trò nhoû nhaát öùng vôùi x₂ vaäy bieán ñöa vaøo laø : x₂

 Haøng coù giaù trò Lamda nhoû nhaát öùng vôùi coät ñoù laø haøng 1

Phöông aùn toái öu cuûa baøi toaùn laø : (0,40/3,100/3,0,0,160/3)

Giaù trò haøm muïc tieâu ñaït ñöôïc laø : F(x) = 520/3

Baøi toaùn ôû daïng chuaån:

F(x) =  120x₁ + 80x₂ + 160x₃ + Mx₇ + Mx₈ + Mx₉ => MIN        

Caùc raøng buoäc:

            3x₁      + 2x₂    + x₃      - x₄       = 2

            4x₁      + x₂      + 3x₃    - x₅       = 3

            2x₁      + 2x₂    + 2x₃    - x₆       = 4

Phöông aùn toái öu cuûa baøi toaùn môû roäng laø : (1/3,5/3,0,7/3,0,0,0,0,0)

Giaù trò haøm muïc tieâu ñaït ñöôïc laø : F(x) = 520/3