Bài tập toán ứng dụng

Phần bài tập BÀI TẬP CHƯƠNG I 1. Với ví dụ trong mục 1.2 chương I, hãy áp dụng phương pháp đơn hình để đi theo quy trình 0 → A→ B nhằm đạt tới zmax. 2. Giải BTQHTT sau đây: z = 6x1 + 8x2 → Max với các ràng buộc 3x1 + 3x2 ≤ 6 5x1 + 3x2 ≤ 8 x1, x2 ≥ 0 3. Giải BTQHTT sau đây: z = 40x1 + 30x2 → Max với các ràng buộc 1 2 2 1 2 1 2 1 2 2 1x x 2 5 2 1 x 5 2 3 3x x 2 5 4 x 30 x 5 (x , x 0) ⎧ + ≤⎪⎪⎪ ≤⎪ 0 8+ ≤⎪⎪ ≥⎪⎪ ≥⎪ ≥⎩ ⎪⎨ Hướng dẫn: Để đưa về dạng chính tắc, ta cần 5 biến bù (3 biến bù thiếu và 2 biến bù thừa) và 2 biến giả (số biến giả bằng số biến bù thừa). 1 2 3 2 4 1 2 5 1 6 7 2 8 9 1 2 3 9 2 1x x x 2 5 2 1 x x 5 2 3 3x x x 2 5 4 x x x 30 x x x 5 x , x , x ..., x 0 ⎧ + + =⎪⎪⎪ + =⎪⎪⎨ + + =⎪⎪ − + =⎪⎪ − + =⎪ ≥⎪⎩ 0 8 Hàm mục tiêu sẽ là z = 40x1 + 30x2 + 0x3 + 0x4 + 0x5 + 0x6 − Mx7 + 0x8 − Mx9. 4. Chúng ta xem xét một dự án thiết kế nâng cấp mạng điện bằng hệ thống cáp ngầm cho một trường đại học. Mạng điện được thiết kế cho ba tuyến sau: khu hành chính, khu giảng đường và đường dây bảo vệ. Do yêu cầu về mặt kĩ thuật giá một mét cáp ở các tuyến trên là khác nhau và lần lượt như sau: 500, 400 và 200 nghìn đồng. Gọi xi là chiều dài các tuyến trên, theo điều kiện thiết kế có các ràng buộc như sau: x1 + x2 + x3 ≥ 1900, x1 + x2 ≥ 1500, x1 + x3 ≥ 1400, x2 + x3 ≥ 900, x1, x2, x3 ≥ 0. Hãy lập phương án thiết kế có tổng chi phí mua cáp nhỏ nhất với các ràng buộc trên và hàm mục tiêu sau: z = 500x1 + 400x2 + 200x3 → Min. 5. Phát biểu một mô hình tối ưu đa mục tiêu (tuyến tính hoặc phi tuyến, từ hai đến bốn mục tiêu) ứng dụng trong quản lí sử dụng hay thiết kế hệ thống kĩ thuật điện. 6. Xét bài toán tối ưu phi tuyến ba mục tiêu phát sinh trong quá trình nghiên cứu các ảnh hưởng của các yếu tố nhiệt độ X1 (0C) và bề dày lớp sấy X2 (cm) tới các chỉ tiêu về hàm lượng tinh dầu Y1, chi phí năng lượng Y2 và tốc độ sấy Y3. Sau đây là phát biểu toán học của bài toán căn cứ kết quả quy hoạch thực nghiệm đã tiến hành: Y1= 9,147247 – 0,609964X1 – 0,679045X2 – 0,005767X1X2 – 0,003268X12 – 0,007967X22 (%) → Max Y2 = 38,2168 – 1,1324X1 – 0,9554X2 + 0,004166X1X2 + 0,01097X12 + 0,03909X22 (Kwh/kg) → Min Y3 = − 4,760179 + 0,110704X1 + 0,023387X2 + 0,0013666X1X2 – 0,002884X12 – 0,006722X22 (KgH2O/h) → Max. Hãy giải bài toán trên bằng phần mềm tính toán thích hợp và kiểm tra kết quả các giải giá trị thích hợp cho X1 là từ 440C tới 510C, X2 từ 9,5cm tới 13,5cm. BÀI TẬP CHƯƠNG II 1. Giải bài toán vận tải cho trong bảng sau: 7 11 8 13 21 17 12 10 8 18 13 16 50 70 60 80 2. Giải bài toán phân công nhiệm vụ với thời gian thực hiện (của mỗi kĩ sư đối với từng nhiệm vụ được ghi theo hàng) cho trong bảng sau: 110 100 50 Σ = 260 32 18 32 16 22 14 12 16 24 30 26 24 26 30 28 20 1 1 1 1 1 1 1 1 Tìm cách phân công nhiệm vụ (mỗi một trong số bốn kĩ sư chỉ được giao đúng một nhiệm vụ) để cực tiểu hoá tổng thời gian thực hiện. Hướng dẫn: Bài toán trên có thể giải dựa trên phương pháp phân phối (có bốn điểm cung cũng như bốn điểm cầu, với tổng cung bằng tổng cầu và bằng 4). 3. Hai máy biến áp có dung lượng 580KVA và 650KVA hoà điện lên thanh cái để cung cấp điện cho bốn nhóm máy A, B, C và C có công suất tối đa lần lượt là 180, 270, 420 và 320. Qua khảo sát, chúng ta có các số liệu sau: − Chi phí truyền tải một đơn vị công suất từ máy biến áp thứ nhất đến các nhóm máy là: C1A = 250, C1B = 300, C1C = 320 và C1D = 310 đồng / đơn vị công suất. − Chi phí truyền tải một đơn vị công suất từ máy biến áp thứ hai đến các nhóm máy là: C2A = 350, C2B = 380, C2C = 330 và C2D = 340 đồng / đơn vị công suất. Hãy tìm công suất mà mỗi nhóm máy có thể nhận từ các máy biến áp để đảm bảo tổng chi phí truyền tải là nhỏ nhất. 4. Lập mạng PERT cho dự án với các hoạt động sau đây: Hoạt động Thứ tự Thời gian (tuần) A B C D E F I − − − A B D, E C, F 3 4 4 5 2 7 6 Hãy tìm thời gian tối thiểu để hoàn thành dự án và xác định các hoạt động cần chú trọng. Hướng dẫn: Kiểm tra kết quả tìm đường găng A → D → F → I. 5. Xem xét một dự án với các dữ kiện như sau: Thời gian ước tính (ngày) Hoạt động Hoạt động kề trước a m b A B C D E F G − − A B B C, D E 3 2 2 2 1 4 1 6 5 4 3 3 6 5 9 8 6 10 11 8 15 Hãy giải quyết các vấn đề sau đây: − Vẽ sơ đồ mạng. − Tính thời gian (trung bình) hoàn thành dự án sớm nhất. − Tìm xác suất để dự án thực hiện trong vòng 20 ngày. 6. Xác định cây khung tối thiểu cho mạng đường dẫn sau và phát biểu ý nghĩa thực tiễn của nó: 120 47 33 F G E D C B 20 23 43 70 33 52 70 12 A 7. Cho một lượng đầu tư có 15 (đơn vị tiền) có thể đầu tư vào các dự án sau: I, II, III theo các mức 0, 3, 6, 9, 12, 15 với mức lợi nhuận như sau: Mức lợi nhuận Số tiền đầu tư I II III 0 3 6 9 12 15 0 1 4 6 8 10 0 2 5 6 7 9 0 2 5 6 7 8 Xác định phương án chọn danh mục đầu tư và mức đầu tư sao cho tổng lợi nhuận là lớn nhất. 8. Hãy tìm phương án tối ưu phân phối công suất của ba nhà máy 1, 2 và 3 với phụ tải và tổn thất cố định. Biết chi phí của các nhà máy là hàm phụ thuộc vào công suất fi(pi), trong đó pi là công suất thực tế của nhà máy i, với i = 1, 2, 3. Giả sử chúng ta đã khảo sát được các số liệu sau: − Tổng công suất cả ba nhà máy cần cung cấp là 18 (đơn vị công suất). − f1(p1) = 4p1, f2(p2) = 3P2, f3(p3) = 3P3. − 0 ≤ p1 ≤ P1MAX = 7, 0 ≤ p2 ≤ P2MAX = 8, 0 ≤ p3 ≤ P3MAX = 6. Hướng dẫn: Áp dụng quy hoạch động. 9. Xác định tuyến đường đi của đường dây truyền tải điện từ điểm A đến điểm B, với các chướng ngại vật khác nhau, sao cho tổng chi phí là nhỏ nhất. Các dữ kiện của bài toán như sau: B 8 9 13 10 9 8 11 8 15 7 13 10 7 11 16 4 12 2 612 9 10 8 2 15 10 11 12 15 6 10 A Như vậy để thiết lập sơ đồ đường truyền tải điện thì xuất phát từ A ta có thể định tuyến đi của đường truyền tải điện trước hết qua một trong hai điểm sát gần, theo hướng bắc hay hướng đông, với các chi phí là 15 và 12. Từ một trong hai điểm này, chúng ta lại tiếp tục xác định tuyến đi cho đường truyền tải điện, với các chi phí đã biết,... Vậy ta có bài toán tìm đường đi với chi phí nhỏ nhất. Hướng dẫn: Chia bài toán thành nhiều giai đoạn nhỏ và áp dụng phương pháp quy hoạch động. BÀI TẬP CHƯƠNG III 1. Khảo sát 200 xung tín hiệu qua các van điện đến điều khiển cơ cấu chấp hành, người ta thấy trung bình 2 giây có một chuỗi xung. Số liệu đã khảo sát được về thời gian xung của các chuỗi xung như sau: Thời gian xung (giây) Số lần Tần suất 3 50 0,25 4 40 0,20 5 50 0,25 6 60 0,30 Bằng phương pháp mô phỏng ngẫu nhiên (nếu có thể, lập chương trình tính toán trên máy tính) hãy xác định số van điện (tối thiểu) cần mở sao cho việc điều hành cơ cấu chấp hành được liên tục (nói cách khác, các chuỗi xung luôn được phục vụ kịp thời). 2. Xét mô hình một kênh phục vụ thoả mãn: số tín hiệu đến có phân phối Poat−xông, thời gian phục vụ có phân phối mũ. Giả sử A = 3 tín hiệu đến trung bình trong một phút, S = 4 tín hiệu được phục vụ trung bình trong một phút. Hãy kiểm tra lại các kết quả sau và phân tích ý nghĩa của chúng: Lq = ; L25,2)34(4/9 =− s = 31/3 = ; Wq = 75,04/3 = ; Ws = 1; Pw = . 75,04/3 = Tuy nhiên, với Pw = , ta thấy 75% số tín hiệu phải chờ trước khi được phục vụ. Điều này có nghĩa là cần tiếp tục cải thiện hệ thống hàng chờ để hiệu quả phục vụ được tốt hơn. Một trong các biện pháp để đem lại hiệu quả phục vụ được tốt hơn là nâng cao tốc độ phục vụ. Hãy lập bảng tính và so sánh khi các tham số khác của hệ thống cố định, riêng S nhận các giá trị khác nhau S = 4, 6, 8 và 10. 75,0 3. Xét mô hình nhiều kênh phục vụ với các giả thiết như trong bài tập trên (A = 3 và S = 4). Hãy tính các chỉ số của mô hình khi số kênh phục vụ k = 2, 3. Từ đó phân tích ý nghĩa của các kết quả đạt được và so sánh với kết quả khi sử dụng mô hình một kênh phục vụ. 4. Một trạm bưu điện viễn thông có 13 cổng. Thời gian phục vụ mỗi khách hàng trung bình là 5 phút. Kết quả khảo sát thống kê cho biết số lượng tín hiệu khách hàng trung bình đến trong một giờ, còn kết quả thu thập phiếu thăm dò ý kiến khách hàng cho biết thời gian trung bình (số phút) một khách hàng có thể đợi trước khi được phục vụ như sau: Các giai đoạn Số tín hiệu / giờ Thời gian có thể đợi tối đa Nhu cầu cao 120 5 Nhu cầu trung bình 60 5,5 Nhu cầu thấp 30 6 Sử dụng mô phỏng ngẫu nhiên, hãy xác định quy trình tính toán tìm số cổng tối thiểu cần mở trong mỗi giai đoạn để đáp ứng được yêu cầu của khách hàng (những giả thiết nào cần đề ra để giải quyết vấn đề này). BÀI TẬP CHƯƠNG IV 1. Chỉ số tiêu thụ điện là một lượng ngẫu nhiên có phân phối tại thời điểm ban đầu như sau: X0 Dưới 50 số 50 tới 100 100 tới 150 Trên 150 Tỉ lệ % 5% 40% 40% 15% Biết ma trận xác suất chuyển trạng thái là: P = ⎢⎢ ⎢⎢ ⎣ ⎡ 05,0 02,0 05,0 85,0 05,0 03,0 85,0 10,0 10,0 90,0 08,0 05,0 ⎥⎥ ⎥⎥ ⎦ ⎤ 80,0 05,0 02,0 0 − Hãy giải thích ý nghĩa của ma trận P. − Tìm phân phối dừng của xích Markov thời gian rời rạc trên đây và cho biết ý nghĩa của kết quả thu được. 2. Cho Xn là một xích Markov với không gian trạng thái S = {1, 2, 3, …} và ma trận xác suất chuyển trạng thái: P = ⎢⎢ ⎢⎢ ⎣ ⎡ ... 0 4/3 2/1 ... 8/7 0 2/1 ... 0 4/1 0 ... 8/1 0 0 ⎥⎥ ⎥⎥ ⎦ ⎤ ... ... ... ... Hãy tìm véc tơ phân phối bất biến Π = [π1, π2, π3, π4, …] sao cho Π× P = Π. Chú ý: Để tính π0 cần áp dụng phương pháp tính gần đúng. 3. Cho {Xt}t ≥ 0 là một xích Markov với ma trận cường độ sau đây: Q = ⎢⎢ ⎢⎢ ⎣ ⎡− 0 0 1 1 0 1 3 1 − 1 2 2 0 − ⎥⎥ ⎥⎥ ⎦ ⎤ −1 1 0 0 Hãy tìm phân phối giới hạn cho xích Markov trên đây. 4. Một hệ thống dịch vụ kĩ thuật có hai kênh. Giả sử rằng thời gian phục vụ tín hiệu đến của hai kênh này có phân phối mũ độc lập với nhau với kì vọng là 20 (giây), tức là µ = 1/20, khi trong hệ thống không có quá hai tín hiệu. Nếu trong hệ thống có từ ba tín hiệu trở lên thì µ = 1/30. Ngoài ra cũng giả sử rằng dòng tín hiệu đến là dòng Poát−xông với tham số λ = 1/10 khi hệ thống có ít hơn ba tín hiệu và λ = 1/30 nếu hệ thống có từ ba tín hiệu trở lên. Tìm phân phối giới hạn của xích Markov Xt và tìm xác suất giới hạn mà một tín hiệu phải chờ trước khi được phục vụ. 5. Xét xích Markov thời gian rời rạc thuần nhất với không gian trạng thái S0, S1, S2, S3, S4, S5. Giả sử qua khảo sát các mẫu thống kê đã biết được ma trận xác suất chuyển trạng thái (sau mỗi đơn vị thời gian, có thể là phút, tuần, năm, thế hệ…) như sau: P = ⎢⎢ ⎢⎢ ⎢⎢ ⎢⎢ ⎣ ⎡ 0 09,0 03,0 01,0 0 1 19,0 0 0 0 1 0 0 0 0 8,0 0 0 0 0 76,0 19,0 0 0 0 74,0 21,0 0 0 0 ⎥⎥ ⎥⎥ ⎥⎥ ⎥⎥ ⎦ ⎤ 81,0 17,0 0 0 0 0 Hãy trả lời các câu hỏi sau: − Các trạng thái nào là trạng thái hấp thụ, các trạng thái nào là trạng thái truyền ứng? Hãy tìm xác suất để quá trình bị hấp thụ vào mỗi một trạng thái hấp thụ khi quá trình xuất phát từ một trong các trạng thái truyền ứng. − Tìm thời gian trung bình (kì vọng thời gian) từ lúc quá trình xuất phát (từ một trạng thái truyền ứng nào đó) cho tới khi bị hấp thụ. − Tính thời gian trung bình quá trình rơi vào một trạng thái truyền ứng đã chọn nào đó trước khi nó rơi vào trạng thái hấp thụ. Hướng dẫn: Xem lại mục 2.3. Cần chú ý rằng, vấn đề như mô tả trong bài tập này có thể phát sinh trong nhiều lĩnh vực như trong hệ thống kĩ thuật điện − điện tử, kinh tế nông nghiệp (chuyển dịch các loại hình sử dụng đất, quy mô sử dụng đất, hay kinh tế hộ), sinh học (chuyển dịch tần số gene qua các thế hệ), xã hội học, và nhiều lĩnh vực khác … 6. Hãy phát biểu thuật giải để mô phỏng xích Markov trong các ví dụ được trình bày tại các mục 2.4 và 2.5.