ĐỀ THI MÔN QUY HOẠCH TUYẾN TÍNH TRTRƯỜNG ĐH CÔNG NGHIỆP TPHCM KHOA KHOA HỌC CƠ BẢN ĐỀ THI MÔN QUY HOẠCH TUYẾN TÍNH (Lớp ĐH-15-3-2011 - Thôøi gian 60 phút - Đề 1 -Không dùng tài liệu) Câu I: (2.5 điểm) Cho bài tóan Quy họach tuyến tính mà ta gọi là bài tóan (P) 1) Chứng minh là phương án cực biên, nhưng không phải là phương án tối ưu của bài tóan (P). 2) Hãy xây dựng một phương án cực biên mới tốt hơn phương án x nói ở trên. Câu II: (4.5 điểm) 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. 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. Xí nghiệp muốn mua các loại thức ăn T1, T2, T3 để bảo đảm tốt về chất dinh dưỡng cho một bữa ăn và tổng số tiền mua là nhỏ nhất. 1) Hãy lập bài toán quy hoạch tuyến tính, ta gọi đây là bài toán (P). 2) Viết bài toán đối ngẫu (Q) của bài toán (P). 3) Giải bài toán (Q), từ đó suy ra phương án tối ưu của bài toán (P). Câu III: (3 điểm) Cho bài toán vận tải (min hàm mục tiêu cước phí) cân bằng thu phát như sau: j i 25 35 120 50 110 9 6 5 7 80 2 8 10 6 40 5 7 9 4 1) Hãy xây dựng một phương án ban đầu bằng phương pháp Fogel. 2) Hỏi phương án vừa xây dựng ở câu 1) có phải là phương án tối ưu? Nếu chưa tối ưu, hãy xây dựng một phương án mới tối hơn (chỉ cần một phương án mới tốt hơn). KHOA KHCB TRƯỞNG BỘ MÔN ĐÁP ÁN Câu I: (2.5 điểm) 1) Phương án có hệ véctơ liên kết là A2 ,A3. Ta có nên x là phương án cực biên. Lại có c=(5, 7) và . . Từ đó , lần lượt thay j=1, 2 3 ta được: . Vì ước lượng nên x là phương án không tối ưu. 2) Xây dựng phương án mới như sau: Véctơ đưa vào thay thế là , vì: Véctơ thay ra là , vì . Ta có cơ sở mới là: , . Phương án cực biên có hệ véctơ liên kết , là . Đây là phương án tốt hơn. >. Câu II. 1) Gọi (kg) là số lượng thức ăn T1; T2; T3 cần mua. Tổng số tiền mua là: . Số đơn vị dinh dưỡng D1 có trong bữa ăn là . Số đơn vị dinh dưỡng D2 có trong bữa ăn là . Số đơn vị dinh dưỡng D3 có trong bữa ăn là . Theo đề bài ta có bài toán QHTT 2) Bài toán đối ngẫu (Q) là: 3) Giải bằng phương pháp đơn hình bài toán (Q) ta có kết quả sau đây: 20 25 30 0 0 0 ---------------------------------------------------------------------------------------- Co So CJ Ph.An A1 A2 A3 A4 A5 A6 ---------------------------------------------------------------------------------------- A4 0 10 4 2 1 1 0 0 A5 0 12 1 7 3 0 1 0 A6 0 14 3 1 4 0 0 1 ---------------------------------------------------------------------------------------- -20 -25 -30 0 0 0 ---------------------------------------------------------------------------------------- A4 0 1 3/2 13/4 7/4 0 1 0 -1/4 A5 0 3/2 -5/4 25/4 0 0 1 -3/4 A3 30 7/2 3/4 1/4 1 0 0 1/4 ---------------------------------------------------------------------------------------- 5/2 -35/2 0 0 0 15/2 ---------------------------------------------------------------------------------------- A4 0 152/25 18/5 0 0 1 -7/25 -1/25 A2 25 6/25 -1/5 1 0 0 4/25 -3/25 A3 30 86/25 4/5 0 1 0 -1/25 7/25 ---------------------------------------------------------------------------------------- -1 0 0 0 14/5 27/5 ---------------------------------------------------------------------------------------- A1 20 76/45 1 0 0 5/18 -7/90 -1/90 A2 25 26/45 0 1 0 1/18 13/90 -11/90 A3 30 94/45 0 0 1 -2/9 1/45 13/45 ---------------------------------------------------------------------------------------- 0 0 0 5/18 49/18 97/18 ---------------------------------------------------------------------------------------- Phương án tối ưu của bài toán đối ngẫu là: y = ( 76/45, 26/45, 94/45) Giá trị tối ưu: f = 998/9 Phương án tối ưu của bài toán đối gốc là: x= ( 5/18, 49/18, 97/18) Câu III: Trường hợp xây dựng bằng phương pháp Fogel 1) Phương án ban đầu được xây dựng bằng phương pháp Fogel như sau: j i 25 35 120 50 110 9 6 5 110 7 1 1 K 80 2 25 8 35 10 10 6 10 4 2 2 40 5 7 9 4 40 1 3 3 3 K K 1 1 1 4 4 1 2 2 2 2) Đây là phương án cực biên, vì tập các ô chọn không chứa chu trình. Ta kiểm tra tính tối ưu của phương án: Chọn các số ri và sj như sau: 9 6 5 110 7 R1=0 2 25 8 35 10 10 6 10 R2=-5 5 7 9 4 40 R3=-3 S1=3 S2 = -3 S3 = -5 S4 = -1 Ta được ma trận cước phí mới 12 3 0 110 6 0 25 0 35 0 10 0 10 5 1 1 0 40 Đay là phương án tối ưu. Trường hợp xây dựng bằng phương pháp min-cước: Kết quả trùng với phương pháp Fpgel. ĐỀ THI MÔN QUY HOẠCH TUYẾN TÍNH TR TRƯỜNG ĐH CÔNG NGHIỆP TPHCM KHOA KHOA HỌC CƠ BẢN ĐỀ THI MÔN QUY HOẠCH TUYẾN TÍNH (Lớp ĐH-15-3-2011 - Thôøi gian 60 phút - Đề 1 ... Read more » 11:09 AM