Bài tập phương pháp tối ưu có giải năm 2024
|
Dưới đây là tổng hợp các file tài liệu nhập môn phương pháp tối ưu mà mình sưu tầm được. Các bạn nhấn vào nút để tải file về nhé, File trên Scribd chỉ là để xem trước file. Show
1. Giáo trình các phương pháp tối ưu – cô Kim3. Đề thi cuối kỳ và giữa kỳ nhập môn phương pháp tối ưuMình thấy môn này có rất nhiều điểm tương đồng với môn Toán kinh tế tại trường nên các bạn có thể tham khảo Tài liệu môn Toán Kinh Tế
Ci Xi Yi X 1 X 2 X 3 X 4 X 5 X 6 Lamda 0 X 5 8 1 1 -3 1 1 0 8 M X 7 8 2 2 1 2 0 0 4 0 X 6 12 1 2 2 1 0 1 12 M 8 2 2 1 2 0 0 0 -2 -6 -10 1 0 0 Ci Xi Yi X 1 X 2 X 3 X 4 X 5 X 6 Lamda 0 X 5 4 0 0 -7/2 0 1 0 - -1 X 4 4 1 1 1/2 1 0 0 - 0 X 6 8 0 1 3/2 0 0 1 - F(x) -4 -3 -7 -21/2 0 0 0 Ta có ∆𝑖𝑗≤ 0∀ ô (𝑖,𝑗) nên PA đang xét là PATƯ của bài toán dạng chuẩn : y*=(0,0,0,4,4,8,0); F(x*) = - X 7 =0 với X 7 là ẩn giả nên bài toán gốc ban đầu có PATƯ là: y*=(0,0,0,4); G(y*) = - Tìm PATƯ của bài toán đối ngẫu (D): x 4 = 4 >0 => y 1 + 2y 2 + y 3 = -1 (1) Thay X* vào các ràng buộc ta có:TRƯỜNG ĐẠKHOA ĐÀO TẠI HỌC SPKT TPHCM O CLC Đáp ánMã môn h môn: Tọc: MAOP230706 ối ưu hóa Thời gian: 90 phút Đượ c phép sử dụng tài liệu 0. 5đ 1đ 1 đ 0. 5đ 0. 2 5đ 0. 2 5đ x 1 + x 2 -3x 3 + x 4 = 4 < 8 => y 1 = 0 (2) x 1 + 2x 2 + 2x 3 + x 4 = 4 < 12 => y 3 = 0 (3) Từ (1), (2) va (3) ta có: Y* = (0,-1/2, 0) G(Y*) = - Câu 2: (3 điểm) a. Mô hình bài toán: Tổng hàng phát ra = 300 > tổng thu = 240, đặt trạm thu giả B 3 = Gọi xij là lượng hàng vận chuyển từ nhà máy Ai đến của hàng Bj (i=1,2,3; j=1,2,3) Tìm xij sao cho: F(x)= 12x 11 +11x 12 + 9x 21 +8x 22 +11x 31 +6x 32 →Max x 11 +x 12 +x 13 =1 00 x 21 +x 22 +x 23 =1 20 x 31 +x 32 +x 13 = x 11 +x 21 +x 31 = x 12 +x 22 +x 32 = x 13 +x 23 +x 33 = xij>=0, (i=1,2,3; j=1,2,3) (Hoặc Sv có thể không thêm trạm thu giả thì dấu<= ở ràng buộc 1,2,3 thì vẫn được trọn điểm) b. Giải bài toán 𝐴 1 + A2 + A3 =300; B1 + B2 =240 ⇒Thêm trạm phát giả: B3=60. Do ban giám đốc yêu cầu A 1 phaûi thu ñuû haøng nên c 13 = - M (M>0, rất lớn) Cửa hàng Nhà máy B 1 :90 B 2 :150 B 3 :60 UA 1 :10 012 11 -M M+_ U 1 =90+10A 2 :120 9 0 8 120 0 2 U 2 = -A 3 :80 11 -4 6 0 U 3 = -+ - 20 60V V 1 =12 V 2 =11 V 3 =0đ 1 đ 0đ Câu 3: (3 điểm) a. Mô hình bài toán: Xét quỹ thời gian sản xuất là 1 ngày. Gọi xij là phần thời gian trong 1 ngày phân công máy Mi sản xuất chi tiết Cj (xij >=0) Gọi z là số sản phẩm sản xuất ra trong 1 ngày : z ≥ 0 Tìm xij sao cho: z → max x 11 + x 12 +x 13 =1 (ngày) x 21 + x 22 +x 23 =1 (ngày) z ≤ 200x 11 +40x 21 z ≤ 280x 12 +180x 22 z ≤ 240x 13 +140x 23 z ≥0 ; xij ≥ b. Giải bài toán M/C C 1 : 1 C 2 : 1 C 3 : 1 U i M 1 : 1 200 ***** 280 ***** 240 ***** 280 M 2 : 1 40 180 ***** 140 180 Vj 1 1 1. Z = 128. Lập hệ phương trình và giải phương trình Ta có có X 22 = -0, 18 nên giả phương án này chưa phải là PATƯ → Ô đưa ra là ô (2,2) Lượng điều chỉnh: 1. Ô đưa ra: (1 ,2) Ô đưa vào: (2,3) M/C C 1 : 1 C 2 : 1 C 3 : 1 U i M 1 : 1 200 ***** 280 240 ***** 308. M 2 : 1 40 180 ***** 140 ***** 180 Vj 1 1 1. Z = 127, Lập hệ phương trình và giải phương trình Do moïi giaù trò x ñeàu >= 0 neân phöông aùn tìm ñöôïc laø toái öu. 0đ 0đ 1 đ M/C C 1 : 1 C 2 : 1 C 3 : 1 M 1 : 1 0 0 0. M 2 : 1 0 0 0. Như vậy theo bảng trên nhà máy cần bố trí các máy làm việc trong một ngày như sau: + Bố trí máy M 1 dành 0,58 thời gian sản xuất chi tiết C 1 và 0,42thời gian sản xuất chi tiết C 3. + Bố trí máy M 2 dành 0,39 thời gian sản xuất chi tiết C 1 và 0,61 thời gian sản xuất chi tiết C3. Khi đó số lượng sản phẩm sản xuất được là z = 127, Thời gian trung bình để hoàn thành hợp đồng là: T= 6000 / 127,61 = 47,02ngày ( 48 ngày) c. Phân công trình tự sản xuất để hoàn thành hợp đồng sớm nhất: + Bố trí máy M 1 dành 0,64* 48= 30,72 ngày thời gian sản xuất Quần trước và 0,36* 48= 17,28 ngày thời gian sản xuất Găng tay sau + Bố trí máy M 2 dành 0,71* 48= 34,08 ngày thời gian sản xuất Áo trước và 0,29 *48= 13,92 ngày thời gian sản xuất Găng tay sau 0đ 0đ Câu 2 : (4đ) a. Lập mô hình (1đ) Gọi xij là phần thời gian trong 1 ngày phân công máy Mi sản xuất chi tiết Cj (xij ≥0) Các máy phải hoạt động liên tục trong suốt quỹ thời gian sản xuất. Do đó, điều kiện về thời gian hoạt động của các máy là: M 1 : x 11 + x 12 +x 13 =1 (giờ) M 2 : x 21 + x 22 +x 23 =1 (giờ) Số sản phẩm các loại được sản xuất trong 1 ngày là: Quần : z 1 = 60x 11 +250x 21 Áo : z 2 = 36x 12 +230x 22 Găng tay : z 3 = 150/2x 13 +120/22x 23 Gọi z là số bộ đồ bảo hộ sản xuất ra trong 1 ngày : z ≥ 0 Để tạo ra z bộ đồ bảo hộ thì số sản phẩm quần, áo, găng tay phải có ít nhất là z chi tiết : z ≤ z 1 ; : z ≤ z 2 ; z ≤ z 3 Vấn đề đặt ra là: Tìm (xij) sao cho z cực đại? Mô hình bài toán: Tìm (xij) sao cho : z → max x 11 + x 12 +x 13 =1 (ngày) x 21 + x 22 +x 23 =1 (ngày) z ≤ 60x 11 +100x 21 z ≤ 36x 12 +60x 22 z ≤ 75x 13 +120*x 23 z ≥0 ; xij ≥0 (i=1,2,3; j=1,2) b. Giải mô hình bằng thuật toán nhân tử (3đ) M/C C 1 : 1 C 2 : 1 C 3 : 2 U i M 1 : 1 60 36 75 ***** 75 - M 2 : 2 100 ***** 60 ***** 120 ***** 120 + Vj 1 2 + + - Z = 46. Lập hệ phương trình: {75 100 46 , 43 60 46 , 43 100 46 , 43 1 1 13 23 22 21 21 22 23 13 x x x x x x x x {,0 77 ,0 47 ,0 24 1 22 21 23 13 x x x x Ô (2,3) có x 23 ,0 24 nên giả phương án này chưa phải là PATƯ → Ô đưa ra là ô (2,3) 0. 5đ 0. 5đ 1 đ Lượng điều chỉnh: Ô đưa ra: (2 ,3) Ô đưa vào : (1 ,1) (Trường hợp SV chọn ô đưa vào là ô (1 ,2) mà phần sau làm đúng vẫn đượ c điểm) M/C C 1 : 1 C 2 : 1 C 3 : 2 U i M 1 : 1 60 ***** 36 75 ***** 75 M 2 : 2 100 ***** 60 ***** 120 125 Vj 1 2 1 Z = = 46. {75 46 , 15 60 46 , 15 60 100 46 , 15 1 1 13 22 11 21 21 22 11 13 x x x x x x x x {,0 77 ,0 23 ,0 62 ,0 38 22 21 13 11 x x x x Ta có xij (0 i ;2,1 j )3,1 nên giả phương án này là PATƯ của bài toán ĐBSX. Vậy PATƯ của bài toán ĐBSX là: M/C C 1 : 1 C 2 : 1 C 3 : 2 M 1 : 1 0 0 0. M 2 : 2 0 0 0 Tổng sản phẩm sản xuất được trong ca là: z = 46, Đeå trong moät ngaøy taïo ra ñöôïc nhieàu boä ñoà baûo hoä lao ñoäng nhaát, ta cần phaân coâng thôøi gian saûn xuaát cuûa caùc máy nhö sau: Máy 1 dùng 0,38 ngày sản xuất quần và 0,62 ngày sản xuất găng tay Máy 2 dùng 0,23 ngày sản xuất quần và 0,77 ngày sản xuất áo Öôùc tính thôøi gian trung bình ñeå hoaøn thaønh hôïp ñoàng: T= Câu 3: (4đ) a. Lập mô hình (1,5đ) Gọi x 1 , x2, x 3 tương ứng là số máy tính xách tay (MT), ti vi (TV) và điện thoại (ĐT) cần sản xuất (x 1 ≥0, x 2 ≥0, x 3 ≥0) Ta có hệ ràng buộc về mức quy định của các mục tiêu: Lao động: 6x 1 + 4x 2 + 2x 3 = 100 (người) Lợi nhuận: 10x 1 + 8x 2 + 4x 3 ≥ 200 (triệu đồng) Đặt: 11 1 ) ,1 04 1 36 2 ; 75 60 2, min( 75 c v u 1 đ 0. 5 đ 0. 5 đ 0. 5 đ Câu 1: aài toán đối ngẫu: G(y) =10y 1 + 8y 2 + 8y 3 => MAX 3y 1 + 2y 2 + 2y 3 <= 4 2y 1 + 2y 2 + 3y 3 <= 2 3y 1 + 4y 2 + y 3 <= 1 y 1 <=0, y 2 tuyø yù, y 3 <= b. Giải bài toán (P): Baøi toaùn ôû daïng chuaån: F(x) = 4x 1 + 2x 2 + x 3 + Mx 6 => MIN 3x 1 + 2x 2 + 3x 3 + x 4 = 10 2x 1 + 2x 2 + 4x 3 + x 6 = 8 2x 1 + 3x 2 + x 3 + x 5 = 8 x 1 >=0, x 2 >=0, x 3 >=0, x 4 >=0, x 5 >=0, x 6 >= Ci Xi Yi X 1 4 X 2 2 X 3 1 X 4 0 X 5 0 Lamda 0 X 4 10 3 2 3 1 0 10/ M X 6 8 2 2 4 0 0 2 0 X 5 8 2 3 1 0 1 8 M 8 2 2 4 0 0 0 -4 -2 -1 0 0 0 X 4 4 3/2 1/2 0 1 0 - 1 X 3 2 1/2 1/2 1 0 0 - 0 X 5 6 3/2 5/2 0 0 1 - 2 -7/2 -3/2 0 0 0 Ta có ∆𝑖𝑗≤ 0∀ ô (𝑖, 𝑗) nên PA đang xét là PATƯ của bài toán dạng chuẩn : x*=(0,0,2,4,6,0); F(x*) = 2 X 6 =0 với X 6 là ẩn giả nên bài toán gốc ban đầu có PATƯ là: x*=(0,0,2); F(x*) = 2 Tìm PATƯ của bài toán đối ngẫu (D): TRƯỜNG ĐẠKHOA KINH TI HỌC SPKT TPHCM Ế Đáp ánMã môn h môn: Tọc: MAOP230706 ối ưu hóa BM QTKD Đề số: 1 Th Đượ ời gian: 60 phút c phép sử dụng tài liệu 0đ 0đ 1 đ 0đ 0đ 0đ X 3 = 2 >0 → 3y 1 + 4y 2 + y 3 = 1 (1) 30+ 20+ 3 2 = 6 <10 → y 1 =0 (2) 20+ 30+ 2= 2<8 → y 3 = 0 (3) Kết hợp (1), (2), (3): y 1 =0; y 2 =1/4; y 3 = Kết luận: Y*=(0, 1/4, 0); G(y) = 2 Câu 2: a. Mô hình bài toán: Gọi xij là lượng hàng vận chuyển từ nhà máy Ai đến của hàng Bj (i=1,2,3; j=1,2,3) Tìm xij sao cho: F(x)= 7x 11 +3x 12 +Mx 13 +4x 21 +7x 22 + Mx 23 +8x 31 +2x 32 →Min x 11 +x 12 +x 13 = x 21 +x 22 +x 23 = x 31 +x 32 +x 13 = x 11 +x 21 +x 31 = x 12 +x 22 +x 32 = x 13 +x 23 +x 33 = xij>=0, (i=1,2,3; j=1,2,3) b. Giải bài toán 𝐴 1 + A2 +A3 = 300; B1 + B2 =230 ⇒Thêm trạm thu giả: B 3 =70. Do ban giaùm ñoác coâng ty yeâu caàu sản phẩm nhà máy A 1 ; A 2 phaûi được phân phối hết sản phẩm nên c 13 =M; c 33 =M (M>0, rất lớn) Cửa hàng Nhà máy B 1 : 15 0 B 2 :80 B 3 :A 1 :11 0 7 -3 3 + 50 M - 60 U 1 =A 2 :16 0 4 150 7 -4 M 10 U 2 =A 3 :30 8 -5 2 0 M-1 U 3 =-- 30 +V 1 =4 V 2 =3 V 3 =MÔ đưa vào (3,3); ô đưa ra (3,2); lượng đưa ra: d=3 0 Cửa hàng Nhà máy B 1 : 15 0 B 2 :80 B 3 :0đ 1 đ ( Đường găng : Y 1 - Y 4 - Y 6 - Y 8 Thời gian trung bình mong muốn hoàn thành toàn bộ dự án: 17 ngày Phương sai của dự án: Var = Var (Y 1 ) + Var( Y 4 ) + Var( Y 6 ) + Var( Y 8 ) = 3, (T) = 1,
0. 5 đ 0. 5 đ 0. 5 đ 0. 5 đ 1. 5 đ 0 X 5 0 1/2 0 0 -1/2 1 0 1/2 - F(x) 90 25 14 0 7 0 0 9 M 0 0 0 0 0 0 0 0 Ta có ∆𝑖𝑗≥ 0∀ ô (𝑖, 𝑗) nên PA đang xét là PATƯ của bài toán dạng chuẩn : x*=(0,0,5,0,0,5,0,0); F(x*) = 90 X 8 =0 với X 8 là ẩn giả nên bài toán gốc ban đầu có PATƯ là: x*=(0,0,5,0); F(x*) = 90 Tìm PATƯ của bài toán đối ngẫu (D): X 3 = 5 >0 → y 1 + y 2 + 2y 3 = 18 (1) 0+ 0+ 5+0 = 5 → y 1 < 0 20+ 20+ 5+0= 5< 10 → y 2 = 0 (2) 30+20+25+0=10→ y 3 > 0 Kết hợp (1), (2): y 1 =18-2a; y 2 =0; y 3 =a với a≥ 0 Hoặc y 1 =a; y 2 =0; y 3 =(18-a)/2 với a<= 0 Kết luận: Y*=(18-2a, 0, a); G(y) = 90 Câu 2: a. Mô hình bài toán: Gọi xij là lượng hàng vận chuyển từ nhà máy Ai đến của hàng Bj (i=1,2; j=1,2,3) Tìm xij sao cho: F(x)= 5x 11 +6x 12 +7x 13 +Mx 21 +12x 22 + 10x 23 +M*x 32 →Min x 11 +x 12 +x 13 = x 21 +x 22 +x 23 =1 20 x 31 + x 32 + x 33 = x 11 + x 21 +x 31 = x 12 + x 22 +x 33 =6 0 x 13 +x 23 +x 33 = xij>=0, (i=1,2; j=1,2,3) b. Giải bài toán 𝐴 1 + A2 =200; B1 + B2 +B3 = 260 ⇒Thêm trạm phát giả: A3=60. Do ban giám đốc yêu cầu traïm B 2 phaûi thu ñuû haøng. Cấm tuyến đường A 2 đến B 1 nên c 32 =M; c 21 =M (M>0, rất lớn) 0đ 0đ 1 đ Cửa hàng Nhà máy B 1 : 100 B 2 :60 B 3 :A 1 :80 5 - 80 6 + M-1 7 M-4 U 1 =A 2 :120 M12 -2M 1220 100 U 2 =7-MA 3 :60 0 M 0 M-2 U 3 =-+ 20 - 40V 1 =5 V 2 =M+5 V 3 =M+Ô đưa vào (1,2); ô đưa ra (3,2); d= Cửa hàng Nhà máy B 1 : 10 0 B 2 :60 B 3 :A 1 :80 5 40 6 40 7 -3 U 1 =A 2 :12 0 M 11 -M 12 20 10 100 U 2 =A 3 :60 0 M 1-M 0 -1 U 3 =-60V 1 =5 V 2 =6 V 3 =Ta có ∆𝑖𝑗≤ 0∀ ô (𝑖, 𝑗) nên PA đang xét là PATƯ của bài toán VT (M): 𝑥∗=( 40 40 00 20 10060 0 0)X 21 =0, X 32 = 0 với ô (2,1); (3,2) là ô cấm nên bài toán VT ban đầu có PATƯ là: 𝑥∗=( 40 40 00 20 100) ; F(x)= 1.680 (đồng) Câu 3: (4 điểm) aập mô hình: Gọi xij là phần thời gian trong 1 ngày phân công máy Mi sản xuất chi tiết Cj (xij ≥0) Các máy phải hoạt động liên tục trong suốt quỹ thời gian sản xuất. Do đó, điều kiện về thời gian hoạt động của các máy là: M 1 : x 11 + x 12 +x 13 =1 (giờ) M 2 : x 21 + x 22 +x 23 =1 (giờ) Số sản phẩm các loại được sản xuất trong 1 ngày là: Quần : z 1 = 230x 11 +30x 21 Áo : z 2 = 240x 12 +80x 22 Găng tay : z 3 = 2100/2x 13 +120/2*x 23 Gọi z là số bộ đồ bảo hộ sản xuất ra trong 1 ngày : z ≥ 0 0đ 0đ 0đ 0. 5đ
0đ 0đ Câu 1 ( 3,5 điểm) Cho bài toán gốc (P): (1) f(x) = 2x 1 + 6x 2 + 10x 3 – x 4 min (2 2 2 122 2 2 83 81 2 3 4 1 2 3 4 1 2 3 4 x x x xx x x xx x x x(3) x 1 0 , x 2 0 , x 3 0, x 4 0 a) Lập bài toán đối ngẫu (D) tương ứng của (P). (1 điểm) b) Giải 1 trong 2 bài toán rồi suy ra kết quả của bài toán còn lại. (2,5 điểm) Câu 2 ( 3 điểm ) Một công ty sản xuất ra 1 loại hàng, có 3 nhà máy sản xuất đặt tại 3 địa điểm khác nhau. Biết công suất ở các nhà máy cho ở bảng sau: Nhà máy Công suất (1000 sp/ tháng) A1 100 A2 120 A3 80 Sản phẩm của công ty được phân phối đến 2 thị trường với mức tiêu thụ hàng tháng như sau: Thị trường Khả năng tiêu thụ (1000 sp/ tháng) B1 90 B2 150 Biết lợi nhuận thu được khi một nhà máy sản xuất ra 1 sản phẩm và phân phối đến thị trường tương ứng như sau: (đơn vị: 1 đ/ sản phẩm) B1 B A1 12 11 A2 9 8 A3 11 6 Yêu cầu: a. Hãy lập mô hình xác định kế hoạch phân phối sao cho tổng lợi nhuận lớn nhất ( điểm) b. Hãy xác định kế hoạch phân phối sao cho tổng lợi nhuận lớn nhất với điều kiện nhà máy A1 phải sản xuất hết công suất. (2 điểm) Câu 3 : (3,5 điểm)TRƯỜNG ĐẠI HỌC SPKT TPHCM Đề thi môn: Tối ưu hóa KHOA KINH TẾ Mã môn học: MAOP BM QTKD Đề số: 2 Thời gian: 90 phút Được phép sử dụng tài liệu |
