Đề thi cuối kỳ học kỳ I năm học 2016 - 2017 môn: Quy hoạch toán học - Mã môn học: Math131001

Trường ĐH Sư phạm Kỹ thuật Tp.HCM KHOA KHOA HỌC ỨNG DỤNG BỘ MÔN TOÁN ĐỀ THI CUỐI KỲ HỌC KỲ I NĂM HỌC 2016-2017 MÔN: QUY HOẠCH TOÁN HỌC Mã môn học: MATH131001 Thời gian : 90 phút (22/ 12/2016) Đề thi gồm 02 trang Được phép sử dụng tài liệu Câu 1 (2 điểm) Hãy lập mô hình toán học của bài toán sau đây (chỉ lập mô hình, không giải) Một công ty may mặc ký hợp đồng giao cho khách hàng 160.000 bộ quần áo trong thời gian 1 tháng. Công ty có ba xí nghiệp A, B, C và quần áo phải được sản xuất và đóng gói thành bộ tại mỗi xí nghiệp. Năng lực sản xuất trong một tháng và chí phí trung bình đối với mỗi bộ quần áo (bao gồm chi phí phương tiện sản xuất, nguyên vật liệu, nhân cơng, quản lý) của các xí nghiệp trong thời gian thường trong thời gian tăng ca được cho trong bảng sau: Xí nghiệp A Xí nghiệp B Xí nghiệp C Xí nghiệp Thời gian SX Năng lực sản xuất Chi phí sản xuất Năng lực sản xuất Chi phí sản xuất Năng lực sản xuất Chi phí sản xuất Thời gian thường 60.000 bộ/tháng 180.000 đồng/bộ 50.000 bộ/tháng 182.000 đồng/bộ 40.000 bộ/tháng 183.000 đồng/bộ Thời gian tăng ca 25.000 bộ/tháng 184.000 đồng/bộ 20.000 bộ/tháng 186.000 đồng/bộ 18.000 bộ/tháng 187.000 đồng/bộ Biết rằng, số bộ quần áo sản xuất tại xí nghiệp A ít nhất 35000, tổng số bộ quần áo sản xuất tại hai xí nghiệp B và C phải ít nhất là 70.000 bộ. Hỏi phải phân công sản xuất cho các xí nghiệp như thế nào để hoàn thành hợp đồng với tổng chi phí bé nhất. Câu 2 (1,5 điểm) Tính tốn đầy đủ các chỉ tiêu trên đỉnh, xác định đường găng và cơng việc găng, lập bảng chỉ tiêu cơng việc cho sơ đồ PERT sau đây Y1 6 Y7 5 7 Y9 Y2 Y5 Y8 Y10 Y12 6 2 5 6 4 Y3 5 Y4 3 Y6 5 Y11 16 Câu 3 (2 điểm) Cho bài toán (P) (1) f(x) = 7x1+9x2+7x3 max (2)     68103 1 321 321 xxx xxx (3) 1x tùy ý, 02 x , 3x tùy ý a) Lập bài toán đối ngẫu (D) tương ứng của (P). b) Trong hai bài toán, xét xem bài toán nào đơn giản hơn thì giải bài toán đó rồi suy ra kết quả bài toán còn lại. Câu 4 (2,5 điểm) Một công ty may mặc cần phân phối 2800 đơn vị sản phẩm may mặc loại A1, 2400 đơn vị sản phẩm may mặc loại A2 vào ba xí nghiệp B1, B2, B3 để sản xuất, với năng lực sản xuất (số đơn vị sản phẩm loại A1 hay sản phẩm loại A2) lần lượt là 2000, 2500, 1600 đơn vị sản - 1 - - 2 - phẩm. Chi phí (đơn vị tính 10.000 đồng/1đơn vị sản phẩm) sản xuất của công ty khi phân phối mỗi đơn vị sản phẩm cho các xí nghiệp sản xuất được cho trong bảng sau Xí nghiệp Sản phẩm B1 2000 B2 2500 B3 1600 A1:2800 8 8,5 7,5 A2:2400 9 8 8,5 Vì chiến lược phát triển công ty, nên xí nghiệp B2 phải thu đủ 2500 đơn vị sản phẩm để sản xuất. Hỏi phải phân phối sản phẩm cho các xí nghiệp sản xuất như thế nào để tổng chi phí thấp nhất và tính tổng chi phí thấp nhất nhất đó? Câu 5 (2 điểm) Một công ty may mặc ký hợp đồng giao cho khách hàng 100.000 bộ quần áo (mỗi bộ gồm 1 quần, 1 áo). Công ty có ba xí nghiệp I, II và III với năng suất trung bình của mỗi xí nghiệp khi sản xuất quần, áo được cho trong bảng sau ( quần/ngày, áo/ngày) S.Phẩm X.Nghiệp Quần 1 Áo 1 XN I: 1 620 600 XN II: 1 560 520 XN III: 1 420 400 a) Hỏi phải phân công thời gian sản xuất của các xí nghiệp như thế nào để trong một ngày tạo ra được nhiều bộ quần áo nhất ? Ước tính thời gian trung bình để công ty sản xuất đủ số bộ quần áo hoàn thành hợp đồng. b) Trong thực tế của dây chuyền sản xuất, để thuận tiện cho việc cung cấp nguyên vật liệu và tổ chức sản xuất, mỗi xí nghiệp không thể vừa sản xuất quần áo trong tất cả các ngày làm việc, mà phải sản xuất quần (hoặc áo) xong rồi mới chuyển sang sản xuất áo (hoặc quần). Hỏi phải phân công trình tự sản xuất quần áo cho các xí nghiệp như thế nào để thuận tiện cho việc tổ chức sản xuất và hoàn thành hợp đồng sớm nhất?  Ghi chú : Cán bộ coi thi không được giải thích đề thi. CHUẨN ĐẦU RA Nội dung kiểm tra Chuẩn đầu ra của học phần (về kiến thức) Câu 1&2: Lập mô hình toán học của bài toán thực tế trong quản lý, sản xuất và đời sống. Biết lập và tối ưu kế hoặch trong quản lý , sản xuất. G1: 1.1, 1.2, 1.7 G2:2.1, 2.3 2.4.2,2.6;2.7 Câu 3: Lập bài toán đối ngẫu của 1 bài toán QHTT; xác định bài toán gốc và bài toán đối ngẫu xem bài toán nào có độ phức tạp ít hơn; áp dụng thuật toán đơn hình và định lý độ lệch bù yếu tìm nghiệm của cả hai bài toán gốc và đối ngẫu. G1: 1.1, 1.2, G2:2.1,2.3 2.4.2, 2.4.3, 2.4.4 Câu 4: Nhận dạng được bài toán trong quản lý sản xuất có dạng BTVT không cân bằng thu phát. Aùp dụng được thuật toán thế vị hoặc thuật toán quy 0 cước phí để tìm nghiệm BTVT. G1: 1.1, 1; G2:2,2.1,2.3 G2:2.1.1, 2.1.2, 2.4.2 Câu 5:Nhận dạng được bài toán trong quản lý sản xuất có dạng bài toán SXĐB. Aùp dụng thuật toán điều chỉnh nhân tử để tìm nghiệm bài toán SXĐB và biết cách áp dụng nghiệm bài toán SXĐB vào việc lập kế hoạch cho sản xuất. G1: 1.1, 1.2; G2:2.1,2.3 2.1.1, 2.1.2, 2.4.2 Ngày 20 tháng 12 năm 2016 Thông qua Bộ môn Toán Đáp Án QUY HOẠCH TỐN HỌC (22/12/2016) Câu 1 Gọi: lần lượt là số bộ quần áo sản xuất trong thời gian thường và thời gian tăng ca tại xí nghiệp A trong một tháng; lần lượt là số bộ quần áo sản xuất trong thời gian thường và thời gian tăng ca tại xí nghiệp B trong một tháng; lần lượt là số bộ quần áo sản xuất trong thời gian thường và thời gian tăng ca tại xí nghiệp C trong một tháng. (0,5 đ) 21 , xx 21 , yy 21 , zz Ta có:  Tổng chi phí sản xuất bé nhất:  21 000.184000.180 xx  21 000.186000.182 yy min000.187000.183 21  zz  Cần sản xuất đủ 160.000 để giao cho khách hàng:  21 xx  21 yy 000.160 (0,5 đ) 21  zz  Số bộ quần áo sản xuất phải không âm và nguyên: 01 x và 1x nguyên, 02 x và 2x nguyên, 01 y và 1y nguyên, 02 y và 2y nguyên, 01 z và 1z nguyên, 02 z và nguyên. 2z  Số bộ quần áo sản xuất trong thời gian thường và thời gian tăng ca tại mỗi xí nghiệp không vượt quá năng lực sản xuất của xí nghiệp đó: 000.601 x , 000.252 x , 000.50 , 000.20 , 000.40 , 000.18 . (0,5 đ) 1 y 2 y 1 z 2 z  Số bộ quần áo sản xuất tại hai xí nghiệp A ít nhất là 35.000 bộ: 000.3521  xx  Số bộ quần áo sản xuất tại hai xí nghiệp B và C phải ít nhất là 70.000 bộ: 000.70  21 yy 21  zz Tóm lại ta có mô hình bài toán là tìm , , sao cho: 21 , xx 21 , yy 21 , zz (1)  21 000.184000.180 xx  21 000.186000.182 yy min000.187000.183 21  zz (2)              000.70 000.35 000.18;000.40 000.20;000.50 000.25;000.60 000.160 2121 21 21 21 21 212121 zzyy xx zz yy xx zzyyxx (3) 0 , 02 x , 01 y , 0 , 0 , 02 z và 1x , 2x , 1y , 2y , 1z , 2z nguyên (0,5 đ) 1 x 2 y 1 z - 1 - Câu 2 Đánh số các đỉnh, tính toán các chỉ tiêu trên đỉnh, xác định các đường găng như hình vẽ. Sơ đồ PERT này có hai đường găng. (0,75 đ) Đường găng thứ nhất: ),7,,6,,4,,3,,2,,1( 1297543 YYYYYY Các cơng việc găng ứng với đường găng thứ nhất: 1297543 ,,,,, YYYYYY Đường găng thứ hai: ),7,,6,,4,,2,,1( 129763 YYYYY Các cơng việc găng ứng với đường găng thứ hai: (0,25 đ ) 129763 ,,,, YYYYY Bảng chỉ tiêu cơng việc Công việc ksijt hsijt kmijt hmijt cijd đlijd Nhân lực Y1 (1, 4) 0 6 4 10 4 4 Y2 (1, 3) 0 6 2 8 2 2 Y3 (1, 2) 0 5 0 5 0 0 Y4 (2, 3) 5 8 5 8 0 0 Y5 (3, 4) 8 10 8 10 0 0 Y6 (2, 4) 5 10 5 10 0 0 Y7 (4, 6) 10 15 10 15 0 0 Y8 (4, 5) 10 15 11 16 1 0 Y9 (6, 7) 15 22 15 22 0 0 Y10 (5, 7) 15 21 16 22 1 0 Y11 (2, 8) 5 21 10 26 5 5 Y12 (7,8) 24 26 22 26 0 0 (0,5 đ ) - 2 - Câu 3 a) Bài tốn đối ngẫu tương ứng (D): (1) (0,25 đ) min6)( 21  yyyg (2) (0,25 đ)       78 910 73 21 21 21 yy yy yy (3) , , (0,25 đ) 01 y 02 y 03 y b) Trong hai bài toán thì bài toán đối ngẫu đơn giản hơn vì: Để giải bài toán đối ngẫu chúng ta chỉ cần đưa vào một ẩn phụ và hai ẩn giả; để giải bài toán gốc chúng ta phải đổi dấu một ẩn âm, đổi biến hai ẩn tùy ý thành 4 ẩn không âm và đưa vào 2 ẩn phụ. Đưa bài toán đối ngẫu (D) về dạng chuẩn )( MD (1) min)(03)( 54321  yyMyyyyg (với M là số dương lớn tùy ý) (2)       78 910 73 521 321 421 yyy yyy yyy (3) , , , , (0,25 đ) 01 y 02 y 03 y 04 y 05 y - 3 - Lập bảng đơn hình (có thể không cần lập cột (0,25 đ) ), 54 yy 1 6 0 M M Hệ số Hệ ẩn cơ bản PA CB y1 y2 y3 y4 y5 i M 4y 7 1 -3 0 1 0 0 3y 9 1 10 1 0 0 10 9 M 5y 7 1 8 0 0 1 8 7 min Bảng 1 MygM 14)(  2M-1 5M-6 0 0 0 M 4y 8 77 8 11 0 0 1 8 3 7 0 3y 4 1 4 1 0 1 0 - 4 5 6 2y 8 7 8 1 1 0 0 8 1 7 Bảng 2 8 4277)(  MygM 8 211 M 0 0 0 8 65  M 1 1y 7 1 0 0 11 8 11 3 0 3y 2 0 0 1 11 2 - 11 13 6 2y 0 0 1 0 11 1 11 1 Bảng 3 7)( ygM 0 0 0 11 112 M 11 119 M (0,25 đ) Trong bảng 3, vì M là số dương lớn nên j 0,  j = 6,1 . PACB hiện có của bài toán là = tối ưu. Các ẩn giả y4 = y5 = 0 nên bài toán (D) có PATƯ là = , . (0,25 đ) )( MD ),,,,,( 654321 yyyyyy ),( 21 yy )0,7( ming )0,0,2,0,7( 7        tx x Rttx 1 0 , 3 1 , Theo định lý độ lệch bù yếu ta có:     0)90107( 0)1(7 2 321 x xxx 7max f - 4 - Phương án tối ưu bài toán gốc là: )(P Rtttxxx  ),1,0,(),,( 321 và (0,25 đ) 7max f Câu 4 Bài toán này có dạng bài toán vận tải không cân bằng thu phát với lượng phát ít hơn lượng thu là . Lập thêm trạm giả với lượng cần phát . Để trạm thu đủ thì lượng hàng giả trạm không được phát vào trạm nên ô là ô cấm, vì cần tổng chi phí thấp nhất nên đây là bài toán do đó “cước phí” ô là 900)24002800()160025002000(  3B 3A 3A 9003 a 2B )2,3( minf )2,3( M (với M là số dương lớn tùy ý). (0,5 đ) Lần lượt phân phối như sau: ô 1600; ô 1200; ô 2400; ô 800 và ô 100. Sau khi phân phối xong ta được phương án cơ bản ban đầu không suy biến, tìm các thế vị hàng và các thế vị cột rồi tiếp theo tính kij )3,1( )1,1( )2,2( )1,3( )2,3(  ui + vj - cij ta được được: Xí nghiệp Sản phẩm B1 2000 B2 2500 B3 1600 (0,5 đ) A1:2800 8  0 1200 8,5 M-0,5 Đưa vào 7,5  0 1600 01 cho u  A2:2400 9 -M-1 8  0 2400 8,5 -M-1 Mu 2 A3: 900 0  0 800 M  0 ô cấm Đưa ra 100 0 0,5 83 u 81 v 82  Mv 5,73 v Còn ô có nên phương án cơ bản này không tối ưu. )2,1( 05,012  Mk Ô đưa vào . )2,1( Vòng điều chỉnh là ,  )2,3(),1,3(),2,1(),1,1(V   )2,3(),1,1(CV ,  )2,1(),1,3(LV . Ô đưa ra là ô và lượng điều chỉnh là )2,3( 10032 x . Lập phương án mới và tìm hệ thống thế vị mới ta được: Xí nghiệp Sản phẩm B1 2000 B2 2500 B3 1600 (0,5 đ) A1:2800 8  0 1100 8,5  0 Đưa vào 100 7,5  0 1600 01 cho u  A2:2400 9 -1,5 8  0 2400 8,5 -1,5 5,02 u A3: 900 0  0 900 M 0,5-M Đưa ra 0 0 -0,5 83 u 81 v 5,82 v 5,73 v - 5 - Tất cả các ô đều có nên phương án cơ bản này tối ưu. Vì ô cấm nhận giá trị phân phối nên bài toán có phương án tối ưu. Phương án tối ưu bài toán ban đầu là: 0ijk )2,3( 032 x Xí nghiệp Sản phẩm B1 2000 B2 2500 B3 1600 A1:2800 8 1100 8,5 100 7,5 1600 A2:2400 9 0 8 2400 8,5 0 Tổng chi phí bé nhất: 000.500.408100004085010000]2400816005,71005,811008[min f đồng Chú ý: Có thể giải bằng thuật toán quy 0 cước phí. (0,5 đ) Câu 5 Đây là bài toán dạng “Bài toán sản xuất đồng bộ”, mỗi bộ gồm 1 quần và 1 áo. 1a)   116202,1;3,1:max cjicij  nên ô chọn đầu tiên là ô (1,1), 6201 u , 11 v 1b) Trong các cột, chỉ còn cột 2 chưa có nhân tử nên 2t . Nhân tử cột 2 là 30 31 600 6201:min 2 2      i c u v i i ; ô (1,2) là ô chọn tiếp theo. 1c) Chọn : 1s     2111 520400,520max3,2:max cicc ir  Nhân tử hàng 2:   12122 5603031520;1560max2,1:max vcjvcu jj   . Ô là ô chọn tiếp theo. )1,2( 1c) Chỉ còn hàng 3 chưa có nhân tử nên 3r và nhân tử hàng 3 là   13133 4203031400;1420max2,1:max vcjvcu jj   Ô là ô chọn tiếp theo. (0,5 đ) )1,3( - 6 - S.Phẩm X.Nghiệp Quần 1 Áo 1 XN I: 1 620  Đưa ra 61 19 11 x 600  61 80 12 x 6201 u (+) XN II: 1 560  121 x 520 022 x 5602 u (-) XN II: 1 420  131 x 400 032 x 4203 u (-) 11 v (-) 30 31 2 v (+) Tính được : 787 61 48000 30 311 420560620   z ,  )1,3(),1,2(),2,1(),1,1(S Dựa vào               S j)(i, voi,0 Sj)(i, voi 1,2 j , 3,1 ,1 1 1 ij m i ijij n j ij x zxc ix , với S là tập các ô chọn " " tính được 61 19 11 x < 0, 61 80 12 x > 0, 121 x 0 , 022 x 0 , 032 x 0 , . Vì 131 x 0 61 19 11 x < 0 nên giả phương án này không là phương án tối ưu. (0,5 đ) Ô đưa ra . Đánh dấu các hàng, cột như trong bảng. )1,1( Hệ số điều chỉnh nhân tử  = min       30 31400 420, 30 31520 560 = 62 63 = 232 3 vc u . Ô đưa vào là ô (3,2). Sửa nhân tử S.Phẩm X.Nghiệp Quần 1 Áo 1 XN I: 1 620 011 x 600  112 x 6301 u XN II: 1 560  121 x 520 022 x 5602 u XN II: 1 420  41 22 31 x 400  41 19 32 x 4203 u 11 v 20 21 2 v (0,25 đ) - 7 - Tính được : 785 41 32200 20 211 420560630   z ,  )2,3(),1,3(),1,2(),2,1((S Dựa vào               S j)(i, voi,0 Sj)(i, voi 1,2 j , 3,1 ,1 1 1 ij m i ijij n j ij x zxc ix , với S là tập các ô chọn " " Tính được , , ,011 x 112 x 121 x 0 022 x 0 , 41 22 31 x 0 , 41 19 32 x 0 nên giả phương án này là phương án tối ưu. Thời gian trung bình để công ty sản xuất đủ số quần áo hoàn thành hợp đồng: 3,127 161 20500 41 32200 000.100 T ngày (0,25 đ) b) ; 01111  TxX 3,1271212  TxX ; 3,1272121  TxX ; 02222  TxX , , 3,6831 Tx 32X31 X 59T32 x S.Phẩm X.Nghiệp Quần 1 Áo 1 XN I: 1 620 011 X 600 3,12712 X XN II: 1 560 3,12721 X 520 022 X XN III: 1 420 3,6831 X 400 5932 X Phân công trình tự sản xuất quần áo cho các xí nghiệp như sau: Xí nghiệp I chỉ sản xuất áo (khoảng 127,3 ngày), xí nghiệp II chỉ sản xuất quần (khoảng 127,3 ngày); xí nghiệp III sản xuất áo (khoảng 59 ngày) rồi chuyển sang sản xuất quần (khoảng ngày) 3,68 hoặc xí nghiệp III sản xuất quần (khoảng ngày) rồi chuyển sang sản xuất áo (khoảng ngày). (0,5 đ) 3,68 59 Hết - 8 -