Qui hoạch tuyến tính _CKE

11:40:00 AM Được đăng bởi Trang Anh Nam

  TRƯỜNG ĐẠI HỌC SÀI GÒN          ĐỀ THI KẾT THÚC MÔN HỌC                         Môn thi: Qui hoạch tuyến tính                                    Lớp: CKE
                                                             Thời gian làm bài: 90 phút
Sinh viên không được tham khảo tài liệu để làm bài
Bài 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ờ) để sản xuất một đơn vị mặt hàng được cho bởi bảng sau:

4
1
2
3
3
1
1
2
1
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:

Chuyên chở
Tiền công
Giá bán
3
2
25
1
2
21
2
3
20
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ă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                         Môn thi: Qui hoạch tuyến tính                                    Lớp: CKE
                                                             Thời gian làm bài: 90 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 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 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.


Bài giải.
ĐỀ 01
Bài 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+3)=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

Hệ số
A.C.B
P.A.C.B
5
6
8
0
0
0
0
0
120
4
3
1
1
0
0
0
0
100
1
3
2
0
1
0
0
0
80
2
1
1
0
0
1
0
0
250
5
3
4
0
0
0
1


0
-5
-6
-8
0
0
0
0
0
4
70
7/2
3/2
0
1
-1/2
0
0
8
3
50
½
3/2
1
0
½
0
0
0
6
30
3/2
-1/2
0
0
-1/2
1
0
0
7
50
3
-3
0
0
-2
0
1


400
-1
6
0
0
4
0
0
0
4
35/3
0
5
0
1
11/6
0
-7/6
8
3
125/3
0
2
1
0
5/6
0
-1/6
0
6
5
0
1
0
0
½
1
-1/2
5
1
50/3
1
-1
0
0
-2/3
0
1/3


1250/3
0
5
0
0
10/3
0
-1/3

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

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


Tags: , ,


No comments:

Subscribe to: Post Comments (Atom)
 

© 2012 Học Để ThiBlog tài liệu