Đề thi học kỳ 2009-2010 môn Lý thuyết tối ưu

Chia sẻ: AN TON | Ngày: | Loại File: DOCX | Số trang:5

Thêm vào BST

Báo xấu

350
lượt xem 71
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

ĐH KHOA HỌC TỰ NHIÊN HÀ NỘI Khoa Toán - Cơ -Tin học (Lớp K52A3) ĐỀ THI HỌC KÌ 2009-2010 Môn thi: Lý thuyết tối ưu Thời gian làm bài: 90 phút Câu 1. (2 điểm) 1. Viết mô hình toán học bài toán quy hoạch tuyến tính dạng chính tắc theo vectơ với A là ma trận hệ số của miền ràng buộc. 2. Chứng minh rằng tập hợp K = {x ∈ Rn |Ax ≥ 0} là một nón lồi đã diện. Câu 2. (3 điểm) Giải bài toán sau bằng phương pháp đơn hình L(x) = 8x1 − 6x2 −...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đề thi học kỳ 2009-2010 môn Lý thuyết tối ưu

ĐỀ THI HỌC KÌ 2009-2010 ĐH KHOA HỌC TỰ NHIÊN HÀ NỘI Môn thi: Lý thuyết tối ưu Khoa Toán - Cơ -Tin học (Lớp K52A3) Thời gian làm bài: 90 phút Câu 1. (2 điểm) 1. Viết mô hình toán học bài toán quy hoạch tuyến tính dạng chính tắc theo vectơ với A là ma trận hệ số của miền ràng buộc. 2. Chứng minh rằng tập hợp K = {x ∈ Rn |Ax ≥ 0} là một nón lồi đã diện. Câu 2. (3 điểm) Giải bài toán sau bằng phương pháp đơn hình L(x) = 8x1 − 6x2 − 2x3 → max  4x1 + 3x2 + 4x3 =4  4x + x2 − 3x3 =4 1 xi ≥ 0(i = 1, 2, 3)  Câu 3. (2 điểm) Viết mô hình bài toán vận tải với hàm mục đích lấy max. 1. Chuyển bài toán trên về dạng bài toán quy hoạch tuyến tính chính tắc? 2. Bảng vận tải bài toán trên khi chuyển về dạng chính tắc có đặc điểm gì (không cần kẻ lại bảng)? Câu 4. (3 điểm) Một công ty vận tải biển cần tuyển 110 người để bố trí 10 người làm Máy trưởng, 25 Thợ việc 1, 30 Thợ việc 2 và 45 Thợ việc 3. Phòng nhân sự tìm được 90 người gồm 25 Kỹ sư, 20 Trung cấp và 45 Công nhân. Khả năng cán bộ được đánh giá theo công việc qua bảng sau Công việc Trình độ Máy trưởng Thợ 1 Thợ 2 Thợ 3 Kỹ sư 5 4 0 0 Trung cấp 3 5 4 0 Công nhân 0 1 5 4 Cần bố trí cán bộ với công việc sao cho sử dụng khả năng tối đa năng lực của mọi người. Chú ý: Sinh viên không được mang sách giáo trình và vở ghi chép vào phòng thi.
LỜI GIẢI Lời giải 1. (2 điểm) 1. Bài toán quy hoạch tuyến tính có dạng chính tắc L(x) = cT x → min =b Ax x ≥ 0, 2. Định lý 1.5.1 trang 17 Giáo trình"Quy hoạch tuyến tính". Lời giải 2. (3 điểm) Ta đưa về bài toán M dạng chính tắc tương ứng g (x) = − 1 + 6x2 + 2x3 + Mx4 + Mx5 → min 8x 4x1 + 3x2 + 4x3 + x4 = 4  4x + x2 − 3x3 + x5 =4 1 xi ≥ 0(i = 1, 2, 3, 4, 5)  Trong đó x4 , x5 là các ẩn phụ. Đây là bài toán chính tắc nên ta đưa vào bảng đơn hình để giải. Biến Phương x1 x2 x3 x4 x5 cơ sở án -8 6 2 Cn M M M 4 4 3 4 1 0 x4 M 4 4 1 -3 0 1 x5 Bảng 1 0 0 0 8M + 8 4M − 6 M −2 -8 1 1 3/4 1 1/4 0 x1 M 0 0 -2 -7 -1 1 x5 Bảng 2 -8 0 0 −2M − 12 −7M − 10 −2M − 2 Nghiệm của bài toán M là x∗ = (1, 0, 0, 0, 0, 0) và gmin = −8. Ẩn giả x5 còn là cơ sở nhưng nó nhận giá trị 0. Do đó x∗ = (1, 0, 0, 0) và Lmax = 8 là nghiệm bài toán đã cho. Lời giải 3. (2 điểm) 1. Bài toán vận tải có hàm mục đích max là m n cij xij → max i=1 j =1 n = ai (i = 1, m) xij       j =1  m xij = bj (j = 1, n)     i=1   xij ≥ 0 (i = 1, m, j = 1, n)  2
Chuyển về dạng chính tắc m n (−cij )xij → min i=1 j =1 n = ai (i = 1, m) xij       j =1  m xij = bj (j = 1, n)     i=1   xij ≥ 0 (i = 1, m, j = 1, n)  2. Đặc điểm là chỉ có giá chi phí âm và 0. Lời giải 4. 1. Đây là bài toán vận tải dạng max. Những người mới tuyển là nơi phát với số lượng a1 = 25, a2 = 20, a3 = 45,và người cần bố trí là nơi thu b1 = 10, b2 = 25, b3 = 30, b4 = 45. Dễ thấy đây là bài toán vận tải không cân bằng thu phát, nên ta thêm vào a4 = 110 − 90 = 20. 2. Mặt khác ta đưa về dạng chính tắc của bài toán vận tải thì các chi phí là những số âm vậy ta có bảng 1. 2. Vòng lặp thứ nhất: Bước 1. Tìm phương án xuất phát bằng phương pháp cực tiểu cước phí trong toàn bảng. Ta được phương án cực biên x (xem bảng 1). b4 b1 b3 b2 Bj 25 10 45 Ai 30 −4 −5 0 a1 0 10 10 5 25 −5 −3 0 −4 a2 20 20 −4 −5 −1 0 a3 15 45 30 0 0 0 0 a4 20 20 Bảng 1: Phương án đầu tiên 3
Bước 2. Phương án x không thoái hóa vì |G| = m + n − 1 = 7. Tìm các thế vị u1 + v1 = −5 u1 + v2 = −4 u1 + v4 =0 u2 + v2 = −5 u3 + v3 = −5 u3 + v4 = −4 u4 + v4 =0 Cho u1 = 0 suy ra u2 = −1, u3 = −4, u4 = −0, và v1 = −5, v2 = −4, v3 = −1, v4 = 0. Tính ∆13 = −1, ∆21 = −1, ∆23 = 2, ∆24 = −1, ∆31 = −9 , ∆32 = −7, ∆41 = −5, ∆42 = −4, ∆43 = −1. Ô vi phạm dấu hiệu tối ưu (2,3) là ô đưa vào. Ta có vòng V = {(2, 3)+ , (3, 3)−, (3, 4)+ , (1, 4)− , (1, 2)+ , (2, 2)− } Lượng điều chỉnh q = min{x33 , x14 , x22 } = min{30, 10, 20} = 10. Tương ứng với ô (1,4) đây là ô loại ra ta có bảng mới bằng cách tính lại b4 b1 b3 b2 Bj 25 10 45 Ai 30 −4 −5 0 a1 0 10 15 25 −5 −3 0 −4 a2 20 10 10 −4 −5 −1 0 a3 25 45 20 0 0 0 0 a4 20 20 Bảng 2: Phương án đầu tiên Tìm các thế vị u1 + v1 = −5 u1 + v2 = −4 u2 + v2 = −5 u2 + v3 = −4 u3 + v3 = −5 u3 + v4 = −4 u4 + v4 =0 4
Cho u1 = 0 suy ra u2 = −1, u3 = −2, u4 = 2, và v1 = −5, v2 = −4, v3 = −3, v4 = −2. Tính ∆13 = −3, ∆14 = −2, ∆21 = −3, ∆24 = −3, ∆31 = −7 , ∆32 = −5, ∆41 = −3, ∆42 = −2, ∆43 = −1. Vậy phương án tối ưu phải tìm là   10 15 0 0 X ∗ =  0 10 10 0  0 0 20 25 Vậy phương án phân phối lao động tối ưu như sau: 10 Kỹ sư làm máy trưởng; 15 Kỹ sư làm thợ việc 1; 10 Trung cấp làm thợ việc 1; 10 Trung cấp làm thợ việc 2; 20 Công nhân làm thợ việc 2; 25 Công nhân làm thợ việc 3. 5