Đề thi tối ưu hóa - ThS. Phạm Trí Cao

Nội dung text: Đề thi tối ưu hóa - ThS. Phạm Trí Cao

1. ĐỀ THI TỐI ƯU HÓA - K31 CHÍNH QUY ĐỀ 1 Câu 1 (2,5đ): Một xí nghiệp cơ khí cần cắt những thanh sắt dài 2m thành 400 đoạn dài 0,8m; 500 đoạn dài 0,6m; 600 đoạn dài 0,5m. Hãy lập mô hình bài toán tìm phương án cắt sao cho số sắt thừa ít nhất (Chỉ lập mô hình, không giải). Câu 2 (4đ): Cho bài toán QHTT (A) sau: f(x)= x1+3x2-x3+3x4  min x1+ x2-2x3 +x4 >=4 -x1 +x3 =0, j=1,4 a) (2,5đ) Giải bài toán (A) trên b) (1,5đ) Viết bài toán đối ngẫu của (A) và tìm patư của bài toán đối ngẫu Câu 3 (3,5đ): (3đ) Giải bài toán vận tải sau. (0,5đ) Tìm patư khác, nếu có. T 50 75 95 F 50 5 7 6 100 6 8 9 50 6 9 9 Các sai sót “chết người” !: Câu 1: Đặt biến gọi sai. Không có điều kiện cho biến gọi. Thiếu điều kiện xj nguyên. Không diễn giải mô hình (giải thích ý nghĩa các điều kiện ràng buộc). Câu 2: Không đưa bài toán về dạng chuẩn. Không xác định pacb ban đầu. Không ghi xj>=0, j=1,8 mà chỉ ghi xj>=0, j=1,4 ; thậm chí không thèm ghi điều kiện của xj. Không có điều kiện M>0 rất lớn. Ghi M ở ràng buộc chung. Kết quả thay vì ghi cột patư x thì lại ghi cột c. Không ghi cột ứng với biến phụ trong bảng đơn hình, “tưởng” có thể bỏ được giống như biến giả! Không ghi giá trị tối ưu f, chỉ ghi patư x. Không xác định patư của bài toán gốc mà chỉ có patư của bài toán chuẩn. Không ghi các cặp ràng buộc đối ngẫu ra. Không ghi giá trị tối ưu của bài toán đối ngẫu. Câu 3: Không ghi patư x của bài toán gốc, chỉ ghi patư của bài toán CBTP. Không ghi giá trị tối ưu f. Tại sao tôi làm “quá trời” mà tôi lại rớt ! híc híc híc 1 Đề thi Tối ưu hóa – K31 CQ * ThS. Phạm Trí Cao
2. ĐỀ 2 Câu 1 (2đ): Trong các mệnh đề sau, mệnh đề nào đúng, mệnh đề nào sai? Nếu sai hãy giải thích vì sao? 1) (1đ) Bài toán vận tải không cân bằng thu phát cũng có thể không có patư. 2) (1đ) Phương án X=(xij)m*n của bài toán vận tải CBTP có đúng m+n-1 thành phần xij >0 là phương án cơ bản (pa cực biên). Câu 2 (4đ): Cho bài toán QHTT sau: f= 12x1+3x2+5x3+8x4 min 3x1+2x2+ x3+ x4 =24 xj >=0, j=1,4 1) (3đ) Giải bài toán trên 2) (1đ) Viết bài toán đối ngẫu và chỉ ra các cặp ràng buộc đối ngẫu Câu 3 (4đ): (3,5đ) Giải BTVT sau. (0,5đ) Tìm patư khác, nếu có. T 60 10 50 F 30 1 2 3 40 2 7 9 40 6 3 7 25 7 4 8 ĐỀ 3 Câu 1 (2đ): Người ta trồng 3 giống lúa R1, R2, R3 trên 3 mảnh ruộng I, II, III. Do tính chất của từng mảnh ruộng và của đặc điểm từng giống lúa nên năng suất của các giống lúa trên các mảnh ruộng là khác nhau và được cho ở bảng: Ruộng I II III Giống lúa R1 6 5 7 R2 4 6 - R3 5 6 4 Biết rằng: - Diện tích các mảnh ruộng I, II, III tương ứng: 30ha, 60ha, 40ha. - Diện tích các giống lúa R1, R2, R3 cần trồng lần lượt là 50ha, 40ha, 40ha. - Lúa R2 không trồng được ở mảnh ruộng III. Hãy lập mô hình bài toán tìm kế hoạch trồng lúa để thu được tổng sản lượng lớn nhất. 2 Đề thi Tối ưu hóa – K31 CQ * ThS. Phạm Trí Cao
3. Câu 2 (4,5đ): Cho bài toán QHTT sau: f(x)= x1-3x2+2x3+6x4 min -3x1 +x2 +2x4 =23 -x1 +x2+x3 -x4 =8 xj >=0, j=1,4 a) (3đ) Giải bài toán trên b) (1,5đ) Viết bài toán đối ngẫu (D) và tìm patư của (D) Câu 3 (3,5đ): Giải bài toán vận tải với số liệu sau. Tìm patư khác, nếu có. T 60 10 50 F 30 1 2 3 40 2 7 9 40 6 3 7 25 7 4 8 ĐỀ 4 Câu 1 (2đ): Lập mô hình cho bài toán sau: Một doanh nghiệp cần mua thiết bị mới đưa vào kinh doanh sản xuất với số tiền đầu tư để mua thiết bị dự tính là 200 ngàn $. Có hai loại thiết bị có thể mua với các thông tin như sau: Thiết bị A: đơn giá 10 ngàn $, thông số kỹ thuật cho biết trong 1 giờ hoạt động tiêu hao nhiên liệu là 30 đơn vị, năng suất trung bình là 60 sản phẩm/giờ. Mỗi thiết bị chiếm diện tích 4m2. Thiết bị B: đơn giá 15 ngàn $, thông số kỹ thuật cho biết trong 1 giờ hoạt động tiêu hao nhiên liệu là 45 đơn vị, năng suất trung bình là 70 sản phẩm/giờ. Mỗi thiết bị chiếm diện tích 6m2. Theo bạn, doanh nghiệp sẽ chọn mua thiết bị như thế nào để có lợi nhất (tiêu hao nhiên liệu ít nhất), biết rằng kế hoạch của doanh nghiệp là phải đạt ít nhất 800 sản phẩm/giờ, và diện tích phân xưởng là 100m2. Câu 2 (4đ): Cho bài toán QHTT sau: f(x)= 12x1+9x2+7x3+8x4 min 3x1+2x2 +x3 +x4 =24 xj >=0, j=1,4 a) (3đ) Giải bài toán trên. b) (1đ) Viết bài toán đối ngẫu và chỉ ra các cặp ràng buộc đối ngẫu. 3 Đề thi Tối ưu hóa – K31 CQ * ThS. Phạm Trí Cao
4. Câu 3 (4đ): Cho bài toán vận tải sau: T 60 40 30 F 20 6 4 5 60 10 3 5 40 7 6 4 50 13 6 5 a) (3,5đ) Giải bài toán trên. b) (0,5đ) Patư tìm được ở câu a) có duy nhất? Nếu không hãy tìm patư khác? ĐỀ 5 Câu 1 (2đ): Trong các mệnh đề sau, mệnh đề nào đúng, mệnh đề nào sai? Nếu sai hãy giải thích vì sao? 1) (1đ) Bài toán vận tải không cân bằng thu phát cũng có thể không có patư. 2) (1đ) Phương án X=(xij)m*n của bài toán vận tải CBTP có đúng m+n-1 thành phần xij >0 là phương án cơ bản (pa cực biên). Câu 2 (4,5đ): Cho bài toán QHTT (A) sau: f(x)= x1+3x2-x3+3x4  min x1 +x2-2x3+x4 >=4 -x1 +x3 =0, j=1,4 a) (3đ) Giải bài toán (A) trên. b) (1,5đ) Viết bài toán đối ngẫu của (A) và tìm patư của bài toán đối ngẫu. Câu 3 (3,5đ): Giải bài toán vận tải với số liệu sau. T 60 10 50 F 30 1 2 3 40 2 4 9 40 6 3 7 25 7 5 8 Tìm pa vận chuyển sau cho tổng chi phí vận chuyển là nhỏ nhất, đồng thời trạm phát thứ 2 phải phát hết hàng. 4 Đề thi Tối ưu hóa – K31 CQ * ThS. Phạm Trí Cao
5. ĐỀ 6 Câu 1 (2đ): Lập mô hình cho bài toán sau: Để chế tạo 1 loại hợp chất, người ta cần sử dụng 3 loại đơn chất A, B, C. Có 3 loại quặng có khả năng cung cấp các loại đơn chất này, ký hiệu là Q1, Q2, Q3. Bảng sau đây cho ta biết hàm lượng các đơn chất có trong một đơn vị quặng mỗi loại: Loại quặng Q1 Q2 Q3 Đơn chất A 2 4 B 1 2 6 C 5 3 Để chế tạo một đơn vị hợp chất, người ta cần sử dụng ít nhất 2,5 đơn vị chất A, 3 đơn vị chất B và 4 đơn vị chất C. Chi phí khai thác mỗi một đơn vị quặng mỗi loại lần lượt là 3, 6, 5 ngàn đ. Xác định lượng quặng mỗi loại cần khai thác để có thể thực hiện chế tạo được loại hợp chất cần thiết và chi phí khai thác là ít nhất. Câu 2 (4đ): Cho bài toán QHTT (P) sau: f(x)= 2x1+x2+2x3 min x1 +x2-2x3 >=18 2x2 +x3 >=12 xj >=0, j=1,3 a) (2,5đ) Giải bài toán (P). b) (1,5đ) Viết bài toán đối ngẫu của (P) và tìm patư của bài toán đối ngẫu. Câu 3 (4đ): Cho bài toán vận tải sau: T 70 30 40 60 F 50 7 4 5 0 40 7 6 5 0 40 3 5 4 0 70 8 7 9 M Và pa cho trước: 20 0 0 30 0 0 20 20 X0= 30 0 0 10 20 30 20 0 Trong đó M>0 là giá trị vô cùng lớn. a) (0,5đ) Hãy cho biết pa X0 có phải là pacb không? Vì sao? (0,5đ) Xuất phát từ X0, bạn hãy cải tiến pa để được pacb. b) (3đ) Tìm pa vận chuyển sao cho tổng chi phí vận chuyển là nhỏ nhất. 5 Đề thi Tối ưu hóa – K31 CQ * ThS. Phạm Trí Cao
6. ĐỀ 7 Câu 1 (2đ): Một nhà máy chuyên sản xuất 3 loại thuyền: thuyền có mái chèo, ca nô, xuồng caiac. Lợi nhuận thu được trên một đơn vị sản phẩm của từng loại thuyền tương ứng là 300$, 180$, 150$. Để sản xuất 1 chiếc thuyền mỗi loại người ta cần phải sử dụng nguyên liệu nhôm và giờ công lao động ở các phân xưởng sản xuất (1 sản phẩm do 2 phân xưởng cùng sản xuất), được cho ở bảng sau: 1 thuyền có mái chèo 1 ca nô 1 thuyền caiac Nhôm (kg) 17 8 6 Phân xưởng 1 (giờ) 3 5 4 Phân xưởng 2 (giờ) 2 1 3 Nhà máy có khoảng 500kg nhôm, giờ công lao động hữu dụng ở phân xưởng 1 và 2 tương ứng là 150 giờ và 100 giờ. Hãy lập mô hình bài toán tìm kế hoạch sản xuất của nhà máy để đạt mức lợi nhuận tối đa. Câu 2 (4,5đ): Cho bài toán QHTT (A) sau: f(x)= x1+3x2-3x3+2x4 min x1 +x2-2x3 +x4 >=2 -x1 +x3 >=5 2x2-2x3 +x4 =10 xj >=0, j=1,4 a) (3,5đ) Giải bài toán (A). b) (1đ) Viết bài toán đối ngẫu của (A) và chỉ ra các cặp ràng buộc đối ngẫu. Câu 3 (3,5đ): Cho bài toán vận tải sau: T 60 60 80 100 F 80 4 7 6 8 60 5 3 6 5 110 6 4 7 9 (3đ) Tìm patư của bài toán. (0,5đ) Patư có duy nhất không, tại sao? 6 Đề thi Tối ưu hóa – K31 CQ * ThS. Phạm Trí Cao
7. ĐỀ 8 Câu 1 (2đ): Một tàu chở hàng có trọng tải 200 tấn và dung tích chứa là 80m3. Tàu có thể chở được 5 loại hàng với khối lượng, thể tích và giá trị như sau: Loại hàng 1 2 3 4 5 Khối lượng (tấn/đơn vị) 1,1 1,7 2,1 1,6 2,3 Thể tích (m3/đơn vị) 0,7 0,6 0,5 0,8 0,9 Giá trị (triệu đ/đơn vị) 7 8 9 10 13 Hãy lập mô hình bài toán tìm số lượng hàng tối ưu mỗi loại cần xếp lên tàu sao cho tổng giá trị là lớn nhất. Câu 2 (4,5đ): Cho bài toán QHTT sau: f(x)= 3x1+2x2+3x3+5x4 max x1 +x2+2x3+2x4 =10 xj >=0, j=1,4 a) (3đ) Giải bài toán trên và (0,5đ) tìm patư khác, nếu có. b) (1đ) Viết bài toán đối ngẫu và chỉ ra các cặp ràng buộc đối ngẫu. Câu 3 (3,5đ): (3đ) Giải bài toán vận tải với số liệu sau. (0,5đ) Tìm patư khác, nếu có. T 50 75 95 F 50 5 7 6 100 6 8 9 50 6 9 9 7 Đề thi Tối ưu hóa – K31 CQ * ThS. Phạm Trí Cao