Đề thi cuối kỳ học kỳ I năm học 2015 - 2016 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 Cơ bản Bộ môn Toán ĐỀ THI CUỐI KỲ HỌC KỲ I NĂM HỌC 2015-2016 MÔN: QUY HOẠCH TOÁN HỌC Mã môn học: MATH131001 Thời gian : 90 phút (12/1/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 cần sản xuất 3 loại sản phẩm may mặc là A, B, C và mỗi sản phẩm này đều phải qua 3 công đoạn là công đoạn 1, công đoạn 2, công đoạn 3. Chi phí sản xuất trung bình (gồm tất cả chi phí như nguyên liệu, nhân lực,) đối với mỗi sản phẩm, giá bán tương ứng của mỗi sản phẩm, tổng số giờ lao động ứng với mỗi công đoạn mà công ty có được trong một tuần và định mức tiêu hao số giờ lao động của mỗi sản phẩm ứng với mỗi công đoạn được cho trong bảng sau: Định mức tiêu hao số giờ lao động của mỗi sản phẩm ứng với mỗi công đoạn A B C Tổng số giờ lao động ứng với mỗi công đoạn mà công ty có được trong 1 tuần Công đoạn 1 3 2,5 2 350 giờ (CĐ1) Công đoạn 2 5 3 5 650 giờ (CĐ2) Công đoạn 3 4 2 3 400 giờ (CĐ3) Chi phí sản xuất trung bình mỗi sản phẩm $6 $5,5 $5 Giá bán mỗi sản phẩm $11 $9 $8,5 Biết các sản phẩm sản xuất ra đều có thể bán hết với điều kiện số sản phẩm A không được vượt quá tổng của số sản phẩm B và C. Hỏi mỗi tuần công ty cần sản xuất mỗi loại sản phẩm là A, B, C với số lượng tương ứng bao nhiêu để lợi nhuận trung bình lớn nhất? Câu 2 (3 điểm) Cho bài toán (P) (1) 32 → max 1 38)( xxxxf −+= (2) ⎪⎩ ⎪⎨ ⎧ ≥− ≤++ =+ 9-32 14322 4 -4 321 321 321 xxx xxx xxx (3) 01 ≥x , 02 ≥x , 03 ≥x 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 3 (2,5 điểm) Một công ty may mặc cần sản xuất 15000 đơn vị sản phẩm loại A1, 13000 đơn vị sản phẩm loại A2 thông qua ba xí nghiệp B1, B2, B3 với khả năng 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à 12000, 11000, 8000 đơn vị sản phẩm. Chi phí (đơn vị tính 10.000 đồng/1sản phẩm) khi sản xuất mỗi sản phẩm tại mỗi xí nghiệp được cho trong bảng sau Xí nghiệp Sản phẩm B1 12000 B2 11000 B3 8000 A1:15000 7,5 6,5 7 A2:13000 7 8 6,5 - 1 - - 2 - Vì chiến lược phát triển công ty, nên xí nghiệp B1 phải thu đủ 12000 đơ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 đó? Câu 4 (2,5 điểm) Một công ty đồ gỗ ký hợp đồng giao cho một hệ thống khách sạn 350 bộ bàn ghế giường (mỗi bộ gồm 1 bàn, 3 ghế, 2 giường). Công ty có hai xí nghiệp I và II với năng suất trung bình của mỗi xí nghiệp khi sản xuất bàn, ghế, giường được cho trong bảng sau ( bàn/ngày, ghế/ngày, giường/ ngày) S.Phẩm X.Nghiệp Bàn 1 Ghế 3 Giường 2 XN I: 1 40 90 32 XN II: 1 34 81 28 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ộ bàn ghế giường nhất? Ước tính thời gian trung bình để công ty sản xuất đủ số bàn ghế giường 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 bàn ghế giường trong tất cả các ngày làm việc, mà phải sản xuất bàn (hoặc ghế, hoặc giường) xong rồi mới chuyển sang sản xuất ghế (hoặc bàn, hoặc giường). Hỏi phải phân công trình tự sản xuất bàn ghế giường 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 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. G1: 1.1, 1.2, G2:2.1, 2.3 2.4.2 Câu 2 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 3 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 4 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 11 tháng 1 năm 2016 Thông qua Bộ môn Toán Đáp Án QUY HOẠCH TỐN HỌC (12/1/2016) Câu 1 Gọi zyx ,, là số sản phẩm loại A, B, C mà cơng ty cần sản xuất mỗi tuần. (0,5 đ) Lợi nhuận lớn nhất: max)55,8()5,59()611(),,( →−+−+−= zyxzyxf (0,25 đ) Số giờ lao động sử dụng mỗi cơng đoạn khơng vượt quá tổng số giờ lao động mỗi cơng đoạn mà cơng ty cĩ được trong 1 tuần: Công đoạn 1: 35025,23 ≤++ zyx Công đoạn 2: 650535 ≤++ zyx (0,5 đ) Công đoạn 3: 400324 ≤++ zyx Số sản phẩm loại A khơng vượt quá tổng số sản phẩm loại B và C: zyx +≤ (0,25 đ) Số sản phẩm mỗi loại khơng âm và nguyên: và 0,0,0 ≥≥≥ zyx zyx ,, nguyên (0,25 đ) Tĩm lại ta cĩ mơ hình bài tốn là là tìm các số zyx ,, sao cho: (1) max5,25,35),,( →++= zyxzyxf (2) ⎪⎪⎩ ⎪⎪⎨ ⎧ +≤ ≤++ ≤++ ≤++ zyx zyx zyx zyx 400324 650535 35025,23 (3) và 0,0,0 ≥≥≥ zyx zyx ,, nguyên (0,25 đ) Câu 2 a) Bài tốn đối ngẫu tương ứng (D): (1) (0,25 đ) min9144)( 321 →++= yyyyg (2) (0,5 đ) ⎪⎩ ⎪⎨ ⎧ −≥−+− ≥−+ ≥++ 33 8324 122 321 321 321 yyy yyy yyy (3) tùy ý, , 1y 02 ≥y 03 ≤y (0,5 đ) b) Trong hai bài toán thì bài toán gốc đơn giản hơn vì: Để giải bài toán gốc chúng ta chỉ cần đưa vào hai ẩn phụ và hai ẩn giả; để giải bài toán đối ngẫu chúng ta phải đổi dấu một ẩn âm, nhân hai vế bất phương trình thứ ba cho -1, đổi biến một ẩn tùy ý thành 2 ẩn và đưa vào 3 ẩn phụ, 2 ẩn giả. - 1 - Đưa bài toán đối ngẫu (P) về dạng chuẩn )( MP (1) )(0038)( 7654321 xxMxxxxxxf +−++−+= → max (với M là số dương lớn tùy ý) (2) ⎪⎩ ⎪⎨ ⎧ =+−−− =+++ =+−+ 9 32 14 322 4 4 65321 4321 7321 xxxxx xxxx xxxx (3) , , , , , , 01 ≥x 02 ≥x 03 ≥x 04 ≥x 05 ≥x 06 ≥x 07 ≥x Lập bảng đơn hình (có thể không cần lập cột ), 76 xx 1 8 -3 0 0 -M -M Hệ số Hệ ẩn cơ bản PA CB x1 x2 x3 x4 x5 6x 7x λi -M 7x 4 1 4 -1 0 0 0 1 4 0 4x 14 2 2 3 1 0 0 0 7 -M 6x 9 2 -3 -1 0 -1 1 0 2 9 Bảng 1 MxfM 13)( −= -3M-1 -M-8 2M-3 0 -M 0 0 (0,25 đ) 1x 4 1 4 -1 0 0 0 1 4x 6 0 -6 5 1 0 0 -2 1 0 -M 6x 1 0 -11 1 0 -1 1 -2 Bảng 2 4)( +−= MxfM 0 11M-4 -M+2 0 M 0 3M+1 1x 5 1 -7 0 0 -1 1 -1 4x 1 0 49 0 1 5 -5 8 1 0 -3 3x 1 0 -11 1 0 -1 1 2 Bảng 3 2)( =xfM 0 18 0 0 2 -2+M -7+M (0,5 đ) Trong bảng 3, vì M là số dương lớn nên Δj ≥ 0 ∀ j = 7,1 . PACB hiện có của bài toán là = tối ưu. Trong hệ ẩn cơ bản không còn ẩn giả nên các ẩn giả y6 = y7 = 0 nên bài toán (P) có PATƯ là )( MP ),,,,,,( 7654321 xxxxxxx )0,0,0,1,1,0,5( =),,( 321 xxx )1,0,5( , 2max =f . Theo định lý độ lệch bù yếu ta có: ⎪⎩ ⎪⎨ ⎧ =−×+×+× =+−+− =−++ 0)14130252( 0)33(1 0)122(5 2 321 321 y yyy yyy ⇔ ⎪⎩ ⎪⎨ ⎧ −= = = 2 0 5 3 2 1 y y y , 2min =g Phương án tối ưu bài toán gốc là: )(P ),2,0,5(),,( 321 −=yyy 2min =g (0,5 đ) - 2 - 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à 3000)1300015000()12000110008000( =+−++ . 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à 3A 30003 =a 1B 3A 1B )1,3( min→f )1,3( M (với M là số dương lớn tùy ý). (0,75 đ) Lần lượt phân phối như sau: ô 8000 ; ô 11000; ô 500; ô 400; ô 300 )3,2( )2,1( )3,2( )3,1( )3,3( 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ộ rồi tiếp theo tính kij = ui + vj - cij ta được được: Xí nghiệp Sản phẩm B1 12000 B2 11000 B3 8000 A1:15000 7,5 × 0 4000 6,5 × 0 1100 7 0 5,71 =u A2:13000 7 × 0 5000 8 2 6,5 × 0 8000 72 =u A3: 3000 M × 0 Đưa ra 3000 0 M-1 0 × M-0,5 Đưa vào Mu =3 01 =v 12 −=v 5,03 −=v Còn ô có nên phương án cơ bản hiện có không tối ưu. (0,75 đ) )3,3( 05,033 >−= Mk Ô đưa vào là ô (3,3). Vòng điều chỉnh là V , { } { })1,3(),3,2(=CV , { })3,3(),1,2(=LV . )3,3(),1,3(),3,2(),1,2(= Ô đưa ra là ô và lượng điều chỉnh là )1,3( 300031 =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 12000 B2 11000 B3 8000 A1:15000 7,5 × 0 4000 6,5 × 0 1100 7 0 5,71 =u A2:13000 7 × 0 8000 8 2 6,5 × 0 5000 72 =u A3: 3000 M 0,5-M 0 -0,5 0 × M-0,5 3000 5,03 =u 01 =v 12 −=v 5,03 −=v - 3 - 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ị 0 nên bài toán có phương án tối ưu là: 0≤ijk )1,3( Xí nghiệp Sản phẩm B1 12000 B2 11000 B3 8000 A1:15000 7,5 4000 6,5 1100 7 0 A2:13000 7 8000 8 0 6,5 5000 Tổng chi phí bé nhất: =minf 50005,680007110005,640005,7 ×+×+×+× = 000.10(000.190 × đồng) (0,25 đ) Chú ý: Có thể giải bằng thuật toán quy 0 cước phí. Câu 4 Đây là bài toán dạng “Bài toán sản xuất đồng bộ”, mỗi bộ gồm 1 bàn, 3 ghế và 2 giường. Đưa bài toán về dạng bài toán SXĐB dạng chuẩn S.Phẩm X.Nghiệp Bàn 1 Ghế(quy ước) 1 Giường(quy ước) 1 XN I: 1 40 × 30 16 × 401 =u XN II: 1 34 × 27 × 14 362 =u 11 =v 3 4 2 =v 2 5 3 =v (0,75 đ) 1a) { } 11403,2,1;2,1:max cjicij ==== nên ô chọn đầu tiên là ô (1,1), , 401 =u 11 =v 1b) : 1=k { } { } 121 3016,30max3,2:max cjc j ==== Nhân tử cột 2 là 3 4 30 40min 12 1 2 ==⎭⎬ ⎫ ⎩⎨ ⎧= c uv ; ô (1,2) là ô chọn tiếp theo 1c) Chỉ còn hàng 2 chưa có nhân tử nên 2=r và nhân tử hàng 2 là { } 22222 363427,34max2,1:max vcjvcu jj ==⎭⎬⎫⎩⎨⎧ ×=== . Ô (2,2) là ô chọn tiếp theo. 1b) Chỉ còn cột 3 chưa có nhân tử nên 3=t và nhân tử cột 3 là 13 1 23 2 13 1 3 2 5 14 36, 16 40min,min c u c u c uv ==⎭⎬ ⎫ ⎩⎨ ⎧= ⎭⎬ ⎫ ⎩⎨ ⎧= Ô (1,3) là ô chọn tiếp theo. - 4 - Tính được : 29 456 2 5 3 41 3640 = ++ +=z ≈ 7241,15 S.Phẩm X.Nghiệp Bàn 1 Ghế(quy ước) 1 Giường(quy ước) 1 XN I: 1 40 × 145 57 11 =x 30 đưa ra × 290 109 12 −=x 16 × 58 57 13 =x 401 =u (+) XN II: 1 34 021 =x 27 × 122 =x 14 đưa vào 023 =x 362 =u (-) 11 =v (+) 3 4 2 =v (-) 2 5 3 =v (+) Dựa vào ⎪⎪⎩ ⎪⎪⎨ ⎧ ∉= ∈ ⎪⎭ ⎪⎬ ⎫ == == ∑ ∑ = = S j)(i, voi,0 Sj)(i, voi 1,3 j , 2,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 145 57 11 =x ≥ 0, 290 109 12 −=x < 0, 58 57 13 =x 0≥ , 021 =x 0≥ , 122 =x > 0, nên giả phương án này không là phương án tối ưu. (0,75 đ) 023 =x 0≥ λ = min ⎭⎬ ⎫ ⎪⎪⎩ ⎪⎪⎨ ⎧ ×× 2 514 36, 134 36 = 35 36 = 323 2 vc u . Ô đưa vào là ô (2,3). Sửa nhân tử S.Phẩm X.Nghiệp Bàn 1 Ghế(quy ước) 1 Giường(quy ước) 1 XN I: 1 40 × 1036 405 11 =x 30 012 =x 16 × 1036 631 13 =x 7 288 1 =u XN II: 1 35 021 =x 27 × 259 150 22 =x 14 × 259 109 23 =x 362 =u 35 36 1 =v 3 4 2 =v 7 18 3 =v Tính được : 259 4050 7 18 3 4 35 36 36 7 288 = ++ + =z ≈ 6370,15 - 5 - Dựa vào ⎪⎪⎩ ⎪⎪⎨ ⎧ ∉= ∈ ⎪⎭ ⎪⎬ ⎫ == == ∑ ∑ = = S j)(i, voi,0 Sj)(i, voi 1,3 j , 2,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 1036 405 11 =x ≥ 0, , 0012 ≥=x 1036 631 13 =x 0≥ , 021 =x 0≥ , 259 150 22 =x > 0, 259 109 23 =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ố bàn ghế giường hoàn thành hợp đồng: 38,22 81 1813 259 4050 350 ≈==T ngày (0,5 đ) b) 75,8 4 35 1111 ==×= TxX ; 01212 =×= TxX ; 324 4417 1313 =×= TxX ; 02121 =×= TxX ; ...9629,12 27 350 2222 ≈=×= TxX , ..4197,981 763 2323 ≈=×= TxX S.Phẩm X.Nghiệp Bàn 1 Ghế 3 Giường 2 XN I: 1 40 75,8 4 35 11 ==X 90 012 =X 32 6327,13 324 4417 13 ≈=X XN II: 1 35 021 =X 81 ...9629,12 27 350 22 ≈=X 28 ..4197,9 81 763 23 ≈=X Phân công trình tự sản xuất bàn ghế giường cho các xí nghiệp như sau: Xí nghiệp I sản xuất bàn trước (khoảng ngày-đủ 350 bàn), sau khi sản xuất bàn xong sẽ chuyển sang sản xuất giường (khoảng ngày); xí nghiệp II sản xuất ghế trước (khoảng ngày- đủ 1050 ghế), sau khi sản xuất ghế xong sẽ chuyển sang sản xuất giường (khoảng ngày- cùng xí nghiệp I sản xuất đủ 700 giường). (0,5 đ) 75,8 6327,13 9629,12 4197,9 Hết - 6 -