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: QUY HOẠCH TUYẾN TÍNH                                                                            Lớp: DKE 31012                                               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. Yêu cầu: 

1.     Xây dựng mô hình sao cho tổng số giấy sản xuất trong năm của xí nghiệp là nhiều nhất.

2.     Xây dựng mô hình bài toán đối ngẫu với mô hình toán của 1.

3.     Tìm phương án tối ưu ứng với mô hình toán ở 1. Từ đó suy ra số tấn giấy của mỗi phân xưởng cần sản xuất trong năm.

4.     Áp dụng kết quả bài toán đối ngẫu để từ bảng đơn hình tối ưu 3. suy ra phương án tối ưu cho bài toán đối ngẫu 2.

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:

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.

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: QUY HOẠCH TUYẾN TÍNH                                                                            Lớp: DKE 31012                                               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 mặt hàng . Việc sản xuất được thực hiện theo dây chuyền trên ba máy . Tiền khấu hao mỗi giờ (tính bằng USD) trên mỗi loại máy lần lượt là 2, 1, 3. Thời gian hoạt động tối đa của các máy trong tuần (tính theo giờ) lần lượt là 120, 100 và 80. Thời gian cần thiết đối với các máy (tính theo giờ) để sản xuất một đơn vị mặt hàng được cho bởi bảng sau:

Nguyên liệu được cung cấp tối đa để sản xuất là 250 đơn vị (đv). Lượng nguyên liệu cần thiết để sản xuất một đơn vị mặt hàng các loại lần lượt là 5đv, 3đv, 4đv. Chi phí về chuyên chở, về tiền công và giá bán mỗi đơn vị mặt hàng các loại (tính bằng USD) được cho trong bảng sau:

Yêu cầu:

1.     Tính lợi nhuận thu được trên mỗi đơn vị mặt hàng.

2.     Lập bài toán qui hoạch tuyến tính để xí nghiệp sản xuất đạt lợi nhuận cao nhất trong tuần.

3.     Lập bài toán đối ngẫu của bài toán trên.

4.     Tìm phương án tối ưu của cả hai bài toán.

Bài 2. Cần vận chuyển một loại hàng từ bốn kho hàng đến 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:

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.

Đáp án đề 1

1.     Tính lợi nhuận thu được trên mỗi đơn vị mặt hàng

Lợi nhuận = Giá bán – Tổng các chi phí

LN1=25 – (2.4+1.1+3.2+3+2)=5

LN2=21 – (2.3+1.3+3.1+1+2)=6

LN3=20 – (2.1+1.2+3.1+2+3)=8

2.     Lập bài toán quy hoạch tuyến tính

Gọi  lần lượt là số lượng các mặt hàng cần sản xuất ()

Lợi nhuận thu được cao nhất khi  đạt max

Thời gian sử dụng máy

          :  không vượt quá 120

          :  không vượt quá 100

          :  không vượt quá 80

Nguyên liệu sử dụng

          không vượt quá 250

Mô hình: Tìm  thoả

                                                                       (P)

3.     Lập bài toán đối ngẫu

(D)

4.     Tìm phương án tối ưu của cả hai bài toán.

Chọn bài toán (P) để giải

Đưa bài toán về dạng chính tắc

          Lập bảng đơn hình

Phương án tối ưu của bài toán (P) là  và .

Suy ra phương án tối ưu của bài toán (D):   và .

Bài 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ệ.

Đề 02

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:

.

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

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

3.     Giải bài toán 1 bằng phương pháp đơn hình

4.     Từ bảng đơn hình ta có kết quả của bài toán 2, 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ệ.