Bài giảng Cơ sở tự động học

Cơ Sở Tự Động Học Phạm Văn Tấn Chương I Nhập Môn Trang I.1 Chương I: NHẬP MÔN • ĐẠI CƯƠNG. • CÁC ĐỊNH NGHĨA. • CÁC LOẠI HỆ THỐNG ĐIỀU KHIỂN Cơ Sở Tự Động Học Phạm Văn Tấn I. ĐẠI CƯƠNG Hồi tiếp (feedback) là một trong những tiến trình căn bản nhất trong tự nhiên. Nó hiện diện trong hầu hết các hệ thống động, kể cả trong bản thân sinh vật, trong máy móc, giữa con người và máy móc … Tuy nhiên, khái niệm về hồi tiếp được dùng nhiều trong kỹ thuật. Do đó, lý thuyết về các hệ thống tự điều khiển (automatic control systems) được phát triển như là một ngành học kỹ thuật cho việc phân tích, thiết kế các hệ thống có điều khiển tự động và kiểm soát tự động. Rộng hơn, lý thuyết đó cũng có thể áp dụng trực tiếp cho việc thiết lập và giải quyết các vấn đề thuộc nhiều lĩnh vực khác nhau, không những cho vật lý học, toán học mà còn cho cả các ngành khác như: sinh vật học, kinh tế học, xã hội học, … Hiện nay, hệ thống tự điều khiển đã đảm đương một vai trò quan trọng trong sự phát triển và tiến bộ của công nghệ mới. Thực tế, mỗi tình huống trong sinh hoạt hằng ngày của chúng ta đều có liên quan đến một vài loại điều khiển tự động: máy nướng bánh, máy giặt, hệ thống audio-video ... Trong những cơ quan lớn hay các xưởng sản xuất, để đạt hiệu suất tối đa trong việc tiêu thụ điện năng, các lò sưỡi và các máy điều hoà không khí đều được kiểm soát bằng computer. Hệ thống tự điều khiển được thấy một cách phong phú trong tất cả các phân xưởng sản xuất : Kiểm tra chất lượng sản phẩm, dây chuyền tự động, kiểm soát máy công cụ. Lý thuyết điều khiển không thể thiếu trong các ngành đòi hỏi tính tự động cao như : kỹ thuât không gian và vũ khí, người máy và rất nhiều thứ khác nữa. Ngoài ra, có thể thấy con người là một hệ thống điều khiển rất phức tạp và thú vị. Ngay cả việc đơn giản như đưa tay lấy đúng một đồ vật, là một tiến trình tự điều khiển đã xãy ra. Quy luật cung cầu trong kinh tế học, cũng là một tiến trình tự điều khiển … II. CÁC ĐỊNH NGHĨA. 1. Hệ thống điều khiển: Là một sự sắp xếp các bộ phận vật lý, phối hợp, liên kết nhau, cách sao để điều khiển, kiểm soát, hiệu chỉnh và sửa sai chính bản thân nó hoặc để nó điều khiển một hệ thống khác. Một hệ thống điều khiển có thể được miêu tả bởi các thành phần cơ bản (H.1_1). ™ Đối tượng để điều khiển (chủ đích). ™ Bộ phận điều khiển. ™ Kết quả. Chương I Nhập Môn Trang I.2 Kết quả Chủ đích Bộ phận Điều khiển (a) H.1_1 : Các bộ phận cơ bản của hệ thống điều khiển. Outputs c Inputs u Bộ phận Điều khiển (b) Cơ Sở Tự Động Học Phạm Văn Tấn Ba thành phần cơ bản đó có thể được nhận dạng như ở ( H.1_1). Các inputs của hệ thống còn được gọi là tín hiệu tác động (actuating signals ) và các outputs được hiểu như là các biến được kiểm soát (controlled variables ). Một thí dụ đơn giản, có thể mô tả như (H.1_1) là sự lái xe ôtô. Hướng của hai bánh trước được xem như là biến được kiểm soát c, hay outputs. Góc quay của tay lái là tín hiệu tác động u, hay input. Hệ thống điều khiển trong trường hợp này bao gồm các cơ phận lái và sự chuyển dịch của toàn thể chiếc xe, kể cả sự tham gia của người lái xe. Tuy nhiên, nếu đối tượng để điều khiển là vận tốc xe, thì áp suất tác động tăng lên bộ gia tốc là input và vận tốc xe là output. Nói chung, có thể xem hệ thống điều khiển xe ôtô là một hệ thống điều khiển hai inputs (lái và gia tốc) và hai outputs (hướng và vận tốc). Trong trường hợp này, hai inputs và hai outputs thì độc lập nhau. Nhưng một cách tổng quát, có những hệ thống mà ở đó chúng liên quan nhau. Các hệ thống có nhiều hơn một input và một output được gọi là hệ thống nhiều biến. 2.Hệ điều khiển vòng hở (open_loop control system). Còn gọi là hệ không hồi tiếp (Nonfeedback System), là một hệ thống trong đó sự kiểm soát không tuỳ thuộc vào output. Những thành phần của hệ điều khiển vòng hở thường có thể chia làm hai bộ phận: bộ điều khiển (controller) và thiết bị xử lý như (H.1_2). Tín hiệu tác động u Tham khảo r Controller Thiết bị Biến được kiểm soát c Hình H.1_2 : Các bộ phận của một hệ điều khiển vòng hở. Một tín hiệu vào, hay lệnh điều khiển hay tín hiệu tham khảo (Reference) r đưa vào controller. Tín hiệu ra của nó là tín hiệu tác động u, sẽ kiểm soát tiến trình xử lý sao cho biến c sẽ hoàn tất được vài tiêu chuẩn đặt trước ở ngõ vào. Trong những trường hợp đơn giản, controller có thể là một mạch khuếch đại, những cơ phận nối tiếp hoặc những thứ khác, tuỳ thuộc vào loại hệ thống. Trong các bộ điều khiển điện tử, controller có thể là một microprocessor. Thí dụ : Một máy nướng bánh có gắn timer để ấn định thời gian tắt và mở máy.Với một lượng bánh nào đó, người dùng phải lượng định thời gian nướng cần thiết để bánh chín, bằng cách chọn lựa thời gian trên timer. Đến thời điểm đã chọn trước, timer điều khiển tắt bộ nung. Chương I Nhập Môn Trang I.3 r (Độ chín mong muốn) Hình H.1_3: Thí dụ về hệ điều khiển vòng hở. Nhiễu Phá rối (Độ chín thực tế) Timer Bộ nung c (Chọn lựa Thời gian) Cơ Sở Tự Động Học Phạm Văn Tấn Dễ thấy ngay rằng một hệ thống điều khiển như vậy có độ tin cậy không cao.Tín hiệu tham khảo được đặt trước, còn đáp ứng ở ngõ ra thì có thể thay đổi theo điều kiện xung quanh, hoặc nhiễu. Muốn đưa đáp ứng c đến trị giá tham khảo r, người dùng phải qui chuẩn lại bằng cách chọn timer lại. 3. Hệ điều khiển vòng kín (closed – loop control system). Còn gọi là hệ điều khiển hồi tiếp (feedback control system). Để điều khiển được chính xác, tín hiệu đáp ứng c(t) sẽ được hồi tiếp và so sánh với tín hiệu tham khảo r ở ngỏ vào. Một tín hiệu sai số (error) tỷ lệ với sự sai biệt giữa c và r sẽ được đưa đến controller để sửa sai. Một hệ thống với một hoặc nhiều đường hồi tiếp như vậy gọi là hệ điều khiển vòng kín. (Hình H.1_4) H.1_4 : Hệ điều khiển vòng kín. _ + Controller Thiết bị Bộ chuyển năng C u e r Hồi tiếp Nhiễu phá rối Phân tích saibiệt Trở lại ví dụ về máy nướng bánh. Giả sử bộ nung cấp nhiệt đều các phía của bánh và chất lượng của bánh có thể xác định bằng màu sắc của nó. Một sơ đồ được đơn giản hoá áp dụng nguyên tắc hồi tiếp cho máy nướng bánh tự động trình bày như (H.1_5). Gương Đường hồi tiếp ~ SW Relay Bộ phân tích màu Nút chỉnh màu Bánh H.1_5 : Máy nướng bánh tự động Chương I Nhập Môn Trang I.4 Cơ Sở Tự Động Học Phạm Văn Tấn Ban đầu, máy nướng được qui chuẩn với chất lượng bánh, bằng cách đặt nút chỉnh màu. Không cần phải chỉnh lại nếu như không muốn thay đổi tiêu chuẩn nướng. Khi SW đóng, bánh sẽ được nướng, cho đến khi bộ phân tích màu "thấy" được màu mong muốn. Khi đó SW tự động mở, do tác động của đường hồi tiếp (mạch điện tử điều khiển relay hay đơn giản là một bộ phận cơ khí). H.1_6. là sơ đồ khối mô tả hệ thống trên. H.1_6 : Sơ đồ khối máy nướng bánh tự động C r Màu Mong muốn Phân Tích màu Mở Đóng u Máy nướng Bánh Màu Bánh Thực tế + - Controller Relay SW Gương Một thí dụ khác về hệ thống điều khiển vòng kín như hình H.1_7: hệ thống điều khiển máy đánh chữ điện tử (Electronic Typewriter). Hồi tiếp Bàn phím Vi Xử lý KĐ Công suất DC motor Mã hoá Vị trí Bánh xe in θr θc θr H.1_7: Hệ thống điều khiển máy đánh chữ điện tử. Bánh xe in (printwheel) có khoảng 96 hay 100 ký tự, được motor quay,đặt vị trí của ký tự mong muốn đến trước búa gõ để in. Sự chọn lựa ký tự do người sử dụng gõ lên bàn phím. Khi một phím nào đó được gõ, một lệnh cho bánh xe in quay từ vị trí hiện hành đến vị trí kế tiếp được bắt đầu. Bộ vi xử lý tính chiều và khoảng cách phải vượt qua của bánh xe, và gửi một tín hiệu điều khiển đến mạch khuếch đại công suất. Mạch này điều khiển motor quay để thúc bánh xe in. Vị trí bánh xe in được phân tích bởi một bộ cảm biến vị trí (position sensor). Tín hiệu ra được mã hóa của nó được so sánh với vị trí mong muốn trong bộ vi xử lý. Như vậy motor được điều khiển sao cho nó thúc bánh xe in quay đến đúng vị trí mong muốn. Trong thực tế, những tín hiệu điều khiển phát ra bởi vi xử lý sẽ có thể thúc bánh xe in từ một vị trí này đến vị trí khác đủ nhanh để có thể in một cách chính xác và đúng thời gian. Chương I Nhập Môn Trang I.5 Cơ Sở Tự Động Học Phạm Văn Tấn Chương I Nhập Môn Trang I.6 0 t1 t2 θr(t) θc(t) Định vị in Thời gian H.1_8: Input và output của sự điều khiển bánh xe in. Hình H.1_8 trình bày input và output tiêu biểu của hệ thống. Khi một lệnh tham khảo được đưa vào (gõ bàn phím), tín hiệu được trình bày như một hàm nấc (step function). Vì mạch điện của motor có cảm kháng và tải cơ học có quán tính, bánh xe in không thể chuyển động đến vị trí mong muốn ngay tức khắc. Nó sẽ đáp ứng như hình vẽ và đến vị trí mới sau thời điểm t1. Từ 0 đến t1 là thời gian định vị. Từ t1 đến t2 là thời gian in. Sau thời điểm t2, hệ thống sẵn sàng nhận một lệnh mới. 4. Hồi tiếp và các hiệu quả của nó : Trong những thí dụ ở trên, việc sử dụng hồi tiếp chỉ với chủ đích thật đơn giản, để giảm thiểu sự sai biệt giữa tiêu chuẩn tham khảo đưa vào và tín hiệu ra của hệ thống. Nhưng, những hiệu quả có ý nghĩa của hồi tiếp trong các hệ thống điều khiển thì sâu xa hơn nhiều. Sự giảm thiểu sai số cho hệ thống chỉ là một trong các hiệu quả quan trọng mà hồi tiếp có tác động lên hệ thống. Phần sau đây, ta sẽ thấy hồi tiếp còn tác động lên những tính chất của hệ thống như tính ổn định, độ nhạy, độ lợi, độ rộng băng tần, tổng trở. r + _ C b G H e H.1_9: Hệ thống có hồi tiếp. Xem một hệ thống có hồi tiếp tiêu biểu như (H.1_9). Trong đó r là tín hiệu vào. C là tín hiệu ra. G và H là các độ lợi. GH G r CM +== 1 (1.1) Cơ Sở Tự Động Học Phạm Văn Tấn a) Hiệu quả của hồi tiếp đối với độ lợi toàn thể (overall Gain). So với độ lợi của hệ vòng hở (G), độ lợi toàn thể của hệ vòng kín (có hồi tiếp) có thêm hệ số 1+GH. Hình H.1_9 là hệ thống hồi tiếp âm, tín hiệu hồi tiếp b có dấu (-). Lượng GH tự nó có thể bao gồm dấu trừ. Do đó, hiệu quả tổng quát của hồi tiếp là làm tăng hoặc giảm độ lợi. Trong một hệ điều khiển thực tế, G và H là các hàm của tần số f. Suất GH+1 có thể lớn hơn 1 trong một khoảng tần số nào đó và nhỏ hơn 1 ở một khoảng tần số khác . Như vậy, hồi tiếp sẽ làm tăng độ lợi hệ thống trong một khoảng tần số nhưng làm giảm nó ở khoảng tần số khác. b) Hiệu quả của hồi tiếp đối với tính ổn định. Nói một cách khác không chặt chẽ lắm, một hệ thống gọi là bất ổn khi output của nó thoát khỏi sự kiểm soát hoặc là tăng không giới hạn. Xem phương trình (1.1). nếu GH = -1, output của hệ thống sẽ tăng đến vô hạn đối với bất kỳ input hữu hạn nào. Như vậy, có thể nói rằng hồi tiếp có thể làm một hệ thống (mà lúc đầu ổn định) trở nên bất ổn. Hồi tiếp là một thanh gươm 2 lưỡi. Nếu dùng không đúng cách, nó sẽ trở nên tai hại. Nhưng cũng có thể chứng tỏ được rằng, mối lợi của hồi tiếp lại là tạo được sự ổn định cho một hệ thống bất ổn. Giả sử hệ thống hồi tiếp ở (H.1_9) bất ổn vì GH = -1. Bây giờ, nếu ta đưa vào một vòng hồi tiếp âm nữa, như (H.1_10) . c e r + _ G H + _ F Độ lợi toàn thể của hệ thống bây giờ sẽ là : GFGH G r c ++= 1 (1.2) Nếu do những tín chất của G và H làm cho vòng hồi tiếp trong bất ổn, vì G.H = -1. nhưng toàn thể hệ thống có thể vẫn ổn định bằng cách chọn lựa độ lợi F của vòng hồi tiếp ngoài. Chương I Nhập Môn Trang I.7 Cơ Sở Tự Động Học Phạm Văn Tấn c) Hiệu quả của hồi tiếp đối với độ nhạy. (Sensibility) Độ nhạy thường giữ một vai trò quan trọng trong việc thiết kế các hệ thống điều khiển. Vì các thành phần vật lý có những tín chất thay đổi đối với môi trường xung quanh và với từng thời kỳ , ta không thể luôn luôn xem các thông số của hệ thống hoàn toàn không đổi trong suốt toàn bộ đời sống hoạt động của hệ thống. Thí dụ, điện trở dây quấn của một động cơ điện thay đổi khi nhiệt độ tăng trong lúc vận hành. Một cách tổng quát, một hệ điều khiển tốt sẽ phải rất nhạy đối với sự biến đổi của các thông số này để có thể giữ vững đáp ứng ra. Xem lại hệ thống ở (H.1_9). Ta xem G như là một thông số có thể thay đổi. Độ nhạy toàn hệ thống được định nghĩa như sau: GG MMS MG / / δ δ= (1.3) M: độ lợi toàn hệ thống. Trong đó: δM chỉ sự thay đổi thêm của M G.δM/M và δG/G chỉ phần trăm thay đổi của M và G. Ta có: GHM G G MS MG +== 1 1 δ δ (1.4) Hệ thức này chứng tỏ hàm độ nhạy có thể làm nhỏ tuỳ ý bằng cách tăng GH, miễn sao hệ thống vẫn giữ được sự ổn định. Trong một hệ vòng hở, độ lợi của nó sẽ đáp ứng kiểu một - đối - một đối với sự biến thiên của G. Một cách tổng quát, độ nhạy toàn hệ thống của một hệ hồi tiếp đối với những biến thiên của thông số thì tuỳ thuộc vào nơi của thông số đó. Người đọc có thể khai triển độ nhạy của hệ thống (H.1_9) theo sự biến thiên của H. d) Hiệu quả hồi tiếp đối với nhiễu phá rối từ bên ngoài. Trong suốt thời gian hoạt động, các hệ thống điều khiển vật lý chịu sự phá rối của vài loại nhiễu từ bên ngoài. Thí dụ, nhiễu nhiệt (thermal noise) trong các mạch khuếch đại điện tử, nhiễu do tia lửa điện sinh từ chổi và cổ góp trong các động cơ điện … Hiệu quả của hồi tiếp đối với nhiễu thì tuỳ thuộc nhiều vào nơi mà nhiễu tác động vào hệ thống. Không có kết luận tổng quát nào. Tuy nhiên, trong nhiều vị trí, hồi tiếp có thể giảm thiểu hậu quả của nhiễu. Xem hệ thống ở (H.1_11) Chương I Nhập Môn Trang I.8 Cơ Sở Tự Động Học Phạm Văn Tấn Chương I Nhập Môn Trang I.9 Ở đó e = r ệu trên nhiễu (signal to noise ratio) được định nghĩa: n (nhiểu) r + _ e + + C G1 G2 H Hình H.1 11 Ouput của hệ có thể được xác định bằng nguyên lý chồng chất (super position) - Nếu không có hồi tiếp, H = 0 thì output nGeGGC ... 221 += (1 - 5) Tỷ số tín hi n eG nG eGG nhieudooutput uhitíndooutput N S .e 1 2 21 === (1.6) ể tăng tỷ số S/N hiển nhiên là phải tăng G1 hoặc e/n. Sự thay đổi G2 không ảnh hưởng Nếu có hồi tiếp, output của hệ thống khi r và n tác động đồng thời sẽ là : Đ đến tỷ số. - n HGG Gr HGG GGC 21 2 21 21 11 +++= (1.7) So sánh (1.5) và (1.7), ta thấy thành phần do nhiễu của (1.7) bị giảm bởi hệ số 1+ G- 1G2 H. Nhưng thành phần do tín hiệu vào cũng bị giảm cùng một lượng. Tỷ số S/N bây giờ là: n rGNS 1 212 2121 H) GG(1n / G H) GGr /(1 GG/ =+ += (1.8) à cũng bằng như khi không có hồi tiếp. Trong trường hợp này, hồi tiếp không có hiệu qu V ả trực tiếp đối với tỷ số S/N của hệ thống. Tuy nhiên , sự áp dụng hồi tiếp làm nảy ra khả năng làm tăng tỷ số S/N dưới vài điều kiện. Giả sử rằng suất G1 tăng đến G1’và r đến r’, các thông số khác không thay đổi , output do tín hiệu vào tác động riêng (một mình) thì cũng bằng như khi không có hồi tiếp. Nói cách khác ta có : Cơ Sở Tự Động Học Phạm Văn Tấn rGG HGG rGGC n 21 21 21 0 '1 '' =+== (1.9) Với sự tăng G1, G1’ output do nhiễu tác đông riêng một mình sẽ là: HGG nGC r 21 2 0 '1 +== (1.10) Nhỏ hơn so với khi G1 không tăng. Bây giờ tỷ số S/N sẽ la: H) GG'1( H) GG'(1n / G r GG 211 212 21 +=+ n rG (1.11). Nhận thấy nó lớn hơn hệ thống không hồi tiếp bởi hệ số (1+ G1’G2H) Một cách tổng quát, hồi tiếp cũng gây hiệu quả trên các tính chất của hệ thống, như độ rộng dãy tần, tổng trơ, đáp ứng quá độ ( Transient Response) và đáp ứng tần số. III. CÁC LOẠI HỆ THỐNG ĐIỀU KHIỂN TỰ ĐỘNG. Có nhiều cách phân loại hệ thống điều khiển. • Nếu dựa vào phương pháp phân tích , thiết kế thì chúng gồm các loại tuyến tính, phi tuyến thay đổi theo thời gian (time varying ), không thay đổi theo thời gian (time invariant). • Nếu dựa vào loại tín hiệu trong hệ thống thì chúng gồm các loại dữ liệu liên tục( continous – data), dữ liệu gián đoạn (discrete data), biến điệu và không biến điệu. • Nếu dựa vào loại của các thành phần của hệ thống , thì chúng gồm có các loại điện cơ , thủy lực, khí đông .Tùy vào mục đích chính của hệ mà người ta xếp loại chúng như kiểu nào . 1. Hệ tự điều khiển tuyến tính và phi tuyến. Nói một cách chặt chẽ, các hệ thống tuyến tính đều không có trong thực tế . Vì mọi hệ thống vật lý đều phi tuyến. Hệ điều khiển hồi tiếp tuyến tính chỉ là mô hình lý tưởng hóa để làm đơn giản việc phân tích và thiết kế. Khi độ lớn của tín hiệu của hệ được giới hạn trong một vùng mà ở đó các thành phần biểu lộ tính thẳng ( nghĩa là nguyên lý chồng chất áp dụng được ) thì hệ thống được xem là tuyến tính . Nhưng khi tín hiệu vượt quá vùng hoạt động tuyến tính, tùy vào sự nghiêm ngặt của tính phi tuyến, hệ thống sẽ không được xem là tuyến tính nữa. Thí dụ : các mạch khuếch đại được dùng trong hệ điều khiển thường bảo hòa khi tín hiệu đưa vào chúng trở nên quá lớn. Từ trường của một motor thường có tính bảo hòa. Hiệu ứng phi tuyến thường gặp trong các hệ điều khiển là vùng chết (dead zone ) giữa các bánh răng ; tính phi tuyến của lò xo ; lực ma sát phi tuyến …. Với các hệ tuyến tính, có một sự phong phú về các kỹ thuật giải tích và đồ họa giúp cho việc thiết kế được dễ dàng. Còn trong các hệ phi tuyến , một “liệu pháp”(treat ) toán học Chương I Nhập Môn Trang I.10 Cơ Sở Tự Động Học Phạm Văn Tấn thường là rất khó. Và không có phương pháp tổng quát để có thể giải quyết một số lớn các hệ phi tuyến. 2. Hệ thống có thông số thay đôi và không thay đôi theo thời gian. Khi các thông số của một hệ điều khiển được giữ nguyên không thay đôi trong suốt thời gian hoạt động của nó, thì hệ được gọi là hệ không thay đôi theo thời gian ( time invariant). Trong thực tế , hầu hết các hệ thống vật lý đều chứa những thành phần có thông số bị trôi, hay thay đôi theo thời gian. Thí dụ : điện trở dây quấn của một động cơ điện sẽ thay đổi khi t0 gia tăng. Thí dụ khác, hệ thống điều khiển đường đi của hỏa tiển, trong đó khối lượng của hỏa tiển giảm do sự tiêu thụ trên đường bay. Mặc dù một hệ có thông số thay đổi theo thời gian không phi tuyến thì vẫn là một hệ tuyến tính, nhưng sự phân tích và thiết kế loại hệ này thường là rất phức tạp so với các hệ tuyến tính có thông số không thay đổi . 3. Hệ điều khiển dữ liệu liên tục . Một hệ điều khiển số liệu liên tục là một hệ trong đó các tín hiệu ở những thành phần khác của hệ là các hàm liên tục của biến số thời gian t. Trong các hệ điều khiển số liệu liên tục, các tín hiệu có thể là AC hoặc DC. Không giống trong định nghĩa tổng quát của AC và DC dùng trong kỹ thuật điện, AC và DC của hệ điều khiển mang ý nghĩa chuyên biệt. Khi nói một hệ điều khiển AC, có nghĩa là các tín hiệu trong đó được biến điệu bởi một kiểu biến điệu nào đó, và khi nói một hệ điều khiển DC, có nghĩa là tín hiệu của nó không biến điệu nhưng chúng vẫn là tín hiệu AC. 4. Hệ điều khiển dữ liệu gián đoạn. Là hệ có tín hiệu không liên tục . a) Nếu tín hiệu có dạng một loạt chuỗi xung (pulse train ), thì hệ được gọi là hệ dữ liệu mẫu hóa ( sample data system ). b) Nếu tín hiệu là xung được mã hóa số thích hợp cho việc sử dụng digital computer thì gọi là hệ điều khiển digital. Thí dụ: Hệ điều khiển máy đánh chữ điện tử là một hệ điều khiển digital, vì bộ xử lý nhận và cho ra các số liệu digital. Một cách tổng quát, một hệ dữ liệu mẫu hóa chỉ nhận số liệu và thông tin một cách ngắt quãng tại những thời điểm riêng. Thí dụ: tín hiệu sai số trong hệ có thể được cung cấp ngắt quãng dưới dạng xung. Như vậy hệ sẽ không nhận thông tin về sai số suốt trong giai đoạn giữa hai xung liên tiếp. Điều khiển Giữ mẫur( t) e( t) e*( t) h( t) c( t) Bộ lấy mẫu (sampler ) + - Chương I Nhập Môn Trang I.11 Cơ Sở Tự Động Học Phạm Văn Tấn H.1_12 : Sơ đồ khối một hệ điều khiển dữ liệu mẫu hóa. Một tín hiệu vào liên tục r(t) được đưa vào hệ thống. Tín hiệu sai số e(t) được lấy mẫu ( sampling). Ngõ ra của bộ phận lấy mẫu ( sampler) là một loạt xung. Tần số lấy mẫu có thể đều hay là không. Hình H.1_13 là sơ đồ khối cơ bản của hệ thống điều khiển digital để hướng dẫn quỹ đạo tên lửa autopilot tự tìm mục tiêu. Chương I Nhập Môn Trang I.12 Digital computer DAC Air frame ADC Các bộ cảm biến Input mã hóa Tọa độ mục tiêu Tọa độ thực tế Thiết bị lái Được đều khiển H.1_13 : Sơ đồ khối cơ bản của hệ thống điều khiển quỹ đạo tên lửa tự tìm mục tiêu. 5. Chỉnh cơ tự động ( servomechanism). Một loại hệ thống điều khiển đáng được đặc biệt lưu tâm do tính thịnh hành của nó trong kỹ nghệ và ngôn ngữ điều khiển học. Đó là servomechanism. Một servomechanism là một hệ điều khiển tự động, trong đó biến số kiểm soát C là vị trí cơ học, hoặc đạo hàm theo thời gian của vị trí( vận tốc hay gia tốc). Thí dụ : Xem một bộ điều khiển tự đông đóng mở van nước. Servo ampli Servo motor + - P1 P2 + r - + b - r Bánh răng truyền động - e + Þb Þc van radians radians H.1_14: Servo mechanism điều khiển van. Ngõ vào của hệ thống là một biến trở loại quay P1, được đấu với nguồn điện. Chân thứ 3( con chạy) được quy chuẩn theo vị trí góc ( radians) và đấu vào một ngõ vào của mạch khuếch đại servo. Mạch khuếch đại này cung cấp đủ điện thế cho một động cơ điện gọi là Cơ Sở Tự Động Học Phạm Văn Tấn servo motor. Trục của motor được truyền ( cơ khí ) đến một van để mở hay khóa nước. Nếu trục motor quay 3600 thì van mở hoàn toàn. P2 gọi là biến trở hồi tiếp. Chân thứ 3 được nối ( cơ khí ) với trục motor nhờ một bánh răng và đấu ( điện ) với ngõ vào thứ hai của mạch khuếch đại servo. Tùy vị trí con chạy của hai biến trở, mà điện thế sai biệt e có thê dương, âm hay bằng zero. Điện thế này được khuếch đại, sau đó đặt vào motor đê điều khiển motor quay theo chiều mở van, đóng van hay vẩn giữ van ở vị trí củ ( e= 0; khi đo motor không quay). Giã sử van đang đóng, ta quay P1 một góc (để đặt một tiêu chuẩn tham khảo ở ngõ vào ). Điện thế e mất cân bằng ( khác 0), làm cho motor quay một góc ( thích ứng với góc quay của con chạy P1 ) làm van mở. Đồng thời, qua bộ bánh răng truyền động , con chạy P2 cũng quay một góc sao cho điện thế sai biệt e trở về 0 (motor không quay ). Van được giữ ở độ mở ấy. Hệ thống trên được trình bày bằng sơ đồ khối như sau : Chương I Nhập M Trang I.13 ôn Tiêu chuẩn Þr radians b e r + H.1_15 : Sơ đồ khối servomechamism điều khiển van. Một số thí dụ : 1. Xem một cầu phân thế như hình vẽ. Output là v2 và input là v1. Mạch thụ động này có thể mô hình hóa như là một hệ vòng hở hoặc như một hệ vòng kín. a. Từ các định luật Kirchhoff, ta có : v2 = R2. i i= v1/ (R1 + R2 ) Vậy v2 =( R2 / (R1 + R2 )).v1= f(v1,R1,R2) H.1_16 R2 R1+R2 V1 V2 H.1_17 R1 R2 V2v1 i Biến trở tham khảo Biến trở hồi tiếp Servo amp Servo motor Van P2 u P1 volt volt volt Þc Radians - Cơ Sở Tự Động Học Phạm Văn Tấn b. Nếu biết dòng i dưới dạng khác hơn: i = ( v1-v2 ) / R1 thì: v2 = R2 ( v1 – v2 ) / R1 = v1 . R2 / R1 –v2 .R2 /R1 = f (v1, v2, R1, R2 ) Chươ I.14 ng I Nhập Môn Trang R2 R1 V1-V2 V2 H.1_18 V1 + - 2. Hệ thống tự điều khiển để tay người chạm đến một đồ vật, có thể nhận dạng như sau : các bộ phận chính của hệ là óc, cánh tay, bàn tay và mắt. Hình 1.19 Bộ óc gởi tín hiệu thần kinh đến cánh tay. Tín hiệu này được khuếch đại trong các bắp thịt của cánh tay và bàn tay, và xem như các tín hiệu tác động của hệ thống. Mắt dùng như bộ cảm biến, hồi tiếp liên tục vị trí của cánh tay và vị trí vật đến óc. Vị trí tay là output của hệ, vị trí vật là input. Mục đích của hệ điều khiển là thu nhỏ khoảng cách của vị trí tay và vị trí vật đến zero. r Vị trí vật c + Mắt u Cánh tay, tay Óc Controller e Vị trí tay - Cơ Sở Tự Động Học Phạm Văn Tấn H.1_20 3. Định luật cung cầu của kinh tế học có thể được xem như một hệ điều khiển tự động. Giá bán ( giá thị trường ) của một hàng hóa nào đó là output của hệ. Mục tiêu của hệ là giữ cho giá ổn định. Định luật cung cầu cho rằng giá thị trường ổn định nếu và chỉ nếu cung bằng cầu. Ta chọn 4 bộ phận chính của hệ thống là người cung, người cầu, người định giá thị trường, ở đó hàng hóa được mua và bán. Input là sự ổn định của vật giá, hay tiện lợi hơn, là sự nhiễu loạn giá bằng zero. Output là giá thực tế của thị trường. Sự hoạt đông của hệ thống được giải thích như sau : Người định giá nhận một tín hiệu (zero) khi vật giá ổn định. Ông ta định một giá bán với sự giúp đỡ của những thông tin từ trí nhớ hay giá biểu của sự giao dịch trước đó. Giá này làm người cung sản xuất đưa vào thị trường một lượng hàng hóa nào đó, và người cầu mua một số trong số đó. Sự chênh lệch (sai số ) giữa cung và cầu được điều chỉnh bởi hệ thống này. Nếu cung không bằng cầu, người định giá sẽ thay đổi giá thị trường theo hướng sau cho cung bằng với cầu. Vậy cả cung và cầu đều có thê xem là hồi tiếp vì chúng xác định tác động kiểm soát . Hệ thống được biểu diễn như H.1_21. Người cầu Chương I Nhập Môn Trang I.15 ************* Giá Thị trường H.1_21 Người định giá Thị trường Người cung b2 - r=0 + u c Sự nhiễu loạn giá zero(giá ổn định) e + b1 CHƯƠNG I GIỚI THIỆU VỀ SỰ BIÊN DỊCH Nội dung chính: Để máy tính có thể hiểu và thực thi một chương trình được viết bằng ngôn ngữ cấp cao, ta cần phải có một trình biên dịch thực hiện việc chuyển đổi chương trình đó sang chương trình ở dạng ngôn ngữ đích. Chương này trình bày một cách tổng quan về cấu trúc của một trình biên dịch và mối liên hệ giữa nó với các thành phần khác - “họ hàng” của nó - như bộ tiền xử lý, bộ tải và soạn thảo liên kết,v.v. Cấu trúc của trình biên dịch được mô tả trong chương là một cấu trúc mức quan niệm bao gồm các giai đoạn: Phân tích từ vựng, Phân tích cú pháp, Phân tích ngữ nghĩa, Sinh mã trung gian, Tối ưu mã và Sinh mã đích. Mục tiêu cần đạt: Sau khi học xong chương này, sinh viên phải nắm được một cách tổng quan về nhiệm vụ của các thành phần của một trình biên dịch, mối liên hệ giữa các thành phần đó và môi trường nơi trình biên dịch thực hiện công việc của nó. Tài liệu tham khảo: [1] Trình Biên Dịch - Phan Thị Tươi (Trường Ðại học kỹ thuật Tp.HCM) - NXB Giáo dục, 1998. [2] Compilers : Principles, Technique and Tools - Alfred V.Aho, Jeffrey D.Ullman - Addison - Wesley Publishing Company, 1986. [3] Compiler Design – Reinhard Wilhelm, Dieter Maurer - Addison - Wesley Publishing Company, 1996. I. TRÌNH BIÊN DỊCH Nói một cách đơn giản, trình biên dịch là một chương trình làm nhiệm vụ đọc một chương trình được viết bằng một ngôn ngữ - ngôn ngữ nguồn (source language) - rồi dịch nó thành một chương trình tương đương ở một ngôn ngữ khác - ngôn ngữ đích (target languague). Một phần quan trọng trong quá trình dịch là ghi nhận lại các lỗi có trong chương trình nguồn để thông báo lại cho người viết chương trình. Trình biên dịch Chương trình đích Chương trình nguồn Hình 1.1 - Một trình biên dịch 1. Mô hình phân tích - tổng hợp của một trình biên dịch Chương trình dịch thường bao gồm hai quá trình : phân tích và tổng hợp - Phân tích → đặc tả trung gian - Tổng hợp → chương trình đích 1 Chương trình nguồn Phán têch Đặc tả trung gian Phán têch Tổng hợp Phân tích Chương trình đích Hình 1.2 - Mô hình phân tích - tổng hợp Trong quá trình phân tích chương trình nguồn sẽ được phân rã thành một cấu trúc phân cấp, thường là dạng cây - cây cú pháp (syntax tree) mà trong đó có mỗi nút là một toán tử và các nhánh con là các toán hạng. Ví dụ 1.1: Cây cú pháp cho câu lệnh gán position := initial + rate * 60 := position + initial * rate 60 2. Môi trường của trình biên dịch Ngoài trình biên dịch, chúng ta có thể cần dùng nhiều chương trình khác nữa để tạo ra một chương trình đích có thể thực thi được (executable). Các chương trình đó gồm: Bộ tiền xử lý, Trình dịch hợp ngữ, Bộ tải và soạn thảo liên kết. Một chương trình nguồn có thể được phân thành các module và được lưu trong các tập tin riêng rẻ. Công việc tập hợp lại các tập tin này thường được giao cho một chương trình riêng biệt gọi là bộ tiền xử lý (preprocessor). Bộ tiền xử lý có thể "bung" các ký hiệu tắt được gọi là các macro thành các câu lệnh của ngôn ngữ nguồn. Ngoài ra, chương trình đích được tạo ra bởi trình biên dịch có thể cần phải được xử lý thêm trước khi chúng có thể chạy được. Thông thường, trình biên dịch chỉ tạo ra mã lệnh hợp ngữ (assembly code) để trình dịch hợp ngữ (assembler) dịch thành dạng mã máy rồi được liên kết với một số thủ tục trong thư viện hệ thống thành các mã thực thi được trên máy. Hình sau trình bày một quá trình biên dịch điển hình : 2 Hình 1.3 - Một trình xử lý ngôn ngữ điển hình Chương trình nguồn khung Chương trình nguồn Bộ tiền xử lý Trình biên dịch Trình dịch hợp ngữ Chương trình đích hợp ngữ Mã máy khả tái định vị Trình tải / Liên kết Mã máy tuyệt đối Thư viện, Tập tin đối tượng khả tái định vị II. SỰ PHÂN TÍCH CHƯƠNG TRÌNH NGUỒN Phần này giới thiệu về các quá trình phân tích và cách dùng nó thông qua một số ngôn ngữ định dạng văn bản. 1. Phân tích từ vựng (Lexical Analysis) Trong một trình biên dịch, giai đọan phân tích từ vựng sẽ đọc chương trình nguồn từ trái sang phải (quét nguyên liệu - scanning) để tách ra thành các thẻ từ (token). Ví dụ 1.2: Quá trình phân tích từ vựng cho câu lệnh gán position := initial + rate * 60 sẽ tách thành các token như sau: 1. Danh biểu position 2. Ký hiệu phép gán := 3. Danh biểu initial 3 4. Ký hiệu phép cộng (+) 5. Danh biểu rate 6. Ký hiệu phép nhân (*) 7. Số 60 Trong quá trình phân tích từ vựng các khoảng trắng (blank) sẽ bị bỏ qua. 2. Phân tích cú pháp (Syntax Analysis) Giai đoạn phân tích cú pháp thực hiện công việc nhóm các thẻ từ của chương trình nguồn thành các ngữ đoạn văn phạm (grammatical phrase), mà sau đó sẽ được trình biên dịch tổng hợp ra thành phẩm. Thông thường, các ngữ đoạn văn phạm này được biểu diễn bằng dạng cây phân tích cú pháp (parse tree) với : - Ngôn ngữ được đặc tả bởi các luật sinh. - Phân tích cú pháp dựa vào luật sinh để xây dựng cây phân tích cú pháp. Ví dụ 1.3: Giả sử ngôn ngữ đặc tả bởi các luật sinh sau : Stmt → id := expr expr → expr + expr | expr * expr | id | number Với câu nhập: position := initial + rate * 60, cây phân tích cú pháp được xây dựng như sau : Stmt expr expr expr expr := + id id number id 60 rate initial expr position Hình 1.4 - Một cây phân tích cú pháp Cấu trúc phân cấp của một chương trình thường được diễn tả bởi quy luật đệ qui. Ví dụ 1.4: 1) Danh biểu (identifier) là một biểu thức (expr). 2) Số (number) là một biểu thức. 3) Nếu expr1 và expr2 là các biểu thức thì: expr1 + expr2 expr1 * expr2 (expr) 4 cũng là những biểu thức. Câu lệnh (statement) cũng có thể định nghĩa đệ qui : 1) Nếu id1 là một danh biểu và expr2 là một biểu thức thì id1 := expr2 là một lệnh (stmt). 2) Nếu expr1 là một biểu thức và stmt2 là một lệnh thì while (expr1) do stmt2 if (expr1) then stmt2 đều là các lệnh. Người ta dùng các qui tắc đệ qui như trên để đặc tả luật sinh (production) cho ngôn ngữ. Sự phân chia giữa quá trình phân tích từ vựng và phân tích cú pháp cũng tuỳ theo công việc thực hiện. 3. Phân tích ngữ nghĩa (Semantic Analysis) Giai đoạn phân tích ngữ nghĩa sẽ thực hiện việc kiểm tra xem chương trình nguồn có chứa lỗi về ngữ nghĩa hay không và tập hợp thông tin về kiểu cho giai đoạn sinh mã về sau. Một phần quan trọng trong giai đoạn phân tích ngữ nghĩa là kiểm tra kiểu (type checking) và ép chuyển đổi kiểu. Ví dụ 1.5: Trong biểu thức position := initial + rate * 60 Các danh biểu (tên biến) được khai báo là real, 60 là số integer vì vậy trình biên dịch đổi số nguyên 60 thành số thực 60.0 + * position initial 60 rate := thành := + * position initial inttoreal rate 60.0 Hình 1.5 - Chuyển đổi kiểu trên cây phân tích cú pháp 5 III. CÁC GIAI ÐOẠN BIÊN DỊCH Ðể dễ hình dung, một trình biên dịch được chia thành các giai đoạn, mỗi giai đoạn chuyển chương trình nguồn từ một dạng biểu diễn này sang một dạng biểu diễn khác. Một cách phân rã điển hình trình biên dịch được trình bày trong hình sau. Chương trình nguồn Phân tích từ vựng Phân tích cú pháp Phân tích ngữ nghĩa Sinh mã trung gian Tối ưu mã Sinh mã đích Chương trình đích Quản lý bảng ký hiệu Xử lý lỗi Hình 1.6 - Các giai đoạn của một trình biên dịch Việc quản lý bảng ký hiệu và xử lý lỗi được thực hiện xuyên suốt qua tất cả các giai đoạn. 1. Quản lý bảng ký hiệu Một nhiệm vụ quan trọng của trình biên dịch là ghi lại các định danh được sử dụng trong chương trình nguồn và thu thập các thông tin về các thuộc tính khác nhau của mỗi định danh. Những thuộc tính này có thể cung cấp thông tin về vị trí lưu trữ được cấp phát cho một định danh, kiểu và tầm vực của định danh, và nếu định danh là tên của một thủ tục thì thuộc tính là các thông tin về số lượng và kiểu của các đối số, phương pháp truyền đối số và kiểu trả về của thủ tục nếu có. Bảng ký hiệu (symbol table) là một cấu trúc dữ liệu mà mỗi phần tử là một mẩu tin dùng để lưu trữ một định danh, bao gồm các trường lưu giữ ký hiệu và các thuộc tính của nó. Cấu trúc này cho phép tìm kiếm, truy xuất danh biểu một cách nhanh chóng. Trong quá trình phân tích từ vựng, danh biểu được tìm thấy và nó được đưa vào bảng ký hiệu nhưng nói chung các thuộc tính của nó có thể chưa xác định được trong giai đoạn này. 6 Ví dụ 1.6: Chẳng hạn, một khai báo trong Pascal có dạng var position, initial, rate : real thì thuộc tính kiểu real chưa thể xác định khi các danh biểu được xác định và đưa vào bảng ký hiệu. Các giai đoạn sau đó như phân tích ngữ nghĩa và sinh mã trung gian mới đưa thêm các thông tin này vào và sử dụng chúng. Nói chung giai đoạn sinh mã thường đưa các thông tin chi tiết về vị trí lưu trữ dành cho định danh và sẽ sử dụng chúng khi cần thiết. Bảng ký hiệu position ... initial ... rate ... 1 2 3 4 2. Xử lý lỗi Mỗi giai đoạn có thể gặp nhiều lỗi, tuy nhiên sau khi phát hiện ra lỗi, tùy thuộc vào trình biên dịch mà có các cách xử lý lỗi khác nhau, chẳng hạn : - Dừng và thông báo lỗi khi gặp lỗi đầu tiên (Pascal). - Ghi nhận lỗi và tiếp tục quá trình dịch (C). Giai đoạn phân tích từ vựng thường gặp lỗi khi các ký tự không thể ghép thành một token. Giai đoạn phân tích cú pháp gặp lỗi khi các token không thể kết hợp với nhau theo đúng cấu trúc ngôn ngữ. Giai đoạn phân tích ngữ nghĩa báo lỗi khi các toán hạng có kiểu không đúng yêu cầu của phép toán hay các kết cấu không có nghĩa đối với thao tác thực hiện mặc dù chúng hoàn toàn đúng về mặt cú pháp. 3. Các giai đoạn phân tích Giai đoạn phân tích từ vựng: Ðọc từng ký tự gộp lại thành token, token có thể là một danh biểu, từ khóa, một ký hiệu,...Chuỗi ký tự tạo thành một token gọi là lexeme - trị từ vựng của token đó. Ví dụ 1.7: Danh biểu rate có token id, trị từ vựng là rate và danh biểu này sẽ được đưa vào bảng ký hiệu nếu nó chưa có trong đó. Giai đoạn phân tích cú pháp và phân tích ngữ nghĩa: Xây dựng cấu trúc phân cấp cho chuỗi các token, biểu diễn bởi cây cú pháp và kiểm tra ngôn ngữ theo cú pháp. Ví dụ 1.8: Cây cú pháp và cấu trúc lưu trữ cho biểu thức position := initial + rate * 60 7 Hình 1.7 - Cây cú pháp và cấu trúc lưu trữ := + * id1 id2 60 id3 := + * id 1 num 60 id 3 id 2 4. Sinh mã trung gian Sau khi phân tích ngữ nghĩa, một số trình biên dịch sẽ tạo ra một dạng biểu diễn trung gian của chương trình nguồn. Chúng ta có thể xem dạng biểu diễn này như một chương trình dành cho một máy trừu tượng. Chúng có 2 đặc tính quan trọng : dễ sinh và dễ dịch thành chương trình đích. Dạng biểu diễn trung gian có rất nhiều loại. Thông thường, người ta sử dụng dạng "mã máy 3 địa chỉ" (three-address code), tương tự như dạng hợp ngữ cho một máy mà trong đó mỗi vị trí bộ nhớ có thể đóng vai trò như một thanh ghi. Mã máy 3 địa chỉ là một dãy các lệnh liên tiếp, mỗi lệnh có thể có tối đa 3 đối số. Ví dụ 1.9: t1 := inttoreal (60) t2 := id3 * t1 t3 := id2 + t2 id1 := t3 Dạng trung gian này có một số tính chất: - Mỗi lệnh chỉ chứa nhiều nhất một toán tử. Do đó khi tạo ra lệnh này, trình biên dịch phải xác định thứ tự các phép toán, ví dụ * thực hiện trước +. - Trình biên dịch phải tạo ra một biến tạm để lưu trữ giá trị tính toán cho mỗi lệnh. - Một số lệnh có ít hơn 3 toán hạng. 5. Tối ưu mã Giai đoạn tối ưu mã cố gắng cải thiện mã trung gian để có thể có mã máy thực hiện nhanh hơn. Một số phương pháp tối ưu hóa hoàn toàn bình thường. Ví dụ 1.10: Mã trung gian nêu trên có thể tối ưu thành: t1 := id3 * 60.0 id1 := id2 + t1 Ðể tối ưu mã, ta thấy việc đổi số nguyên 60 thành số thực 60.0 có thể thực hiện một lần vào lúc biên dịch, vì vậy có thể loại bỏ phép toán inttoreal. Ngoài ra, t3 chỉ được dùng một lần để chuyển giá trị cho id1 nên có thể giảm bớt. 8 Có một khác biệt rất lớn giữa khối lượng tối ưu hoá mã được các trình biên dịch khác nhau thực hiện. Trong những trình biên dịch gọi là "trình biên dịch chuyên tối ưu", một phần thời gian đáng kể được dành cho giai đoạn này. Tuy nhiên, cũng có những phương pháp tối ưu giúp giảm đáng kể thời gian chạy của chương trình nguồn mà không làm chậm đi thời gian dịch quá nhiều. 6. Sinh mã Giai đoạn cuối cùng của biên dịch là sinh mã đích, thường là mã máy hoặc mã hợp ngữ. Các vị trí vùng nhớ được chọn lựa cho mỗi biến được chương trình sử dụng. Sau đó, các chỉ thị trung gian được dịch lần lượt thành chuỗi các chỉ thị mã máy. Vấn đề quyết định là việc gán các biến cho các thanh ghi. Ví dụ 1.11: Sử dụng các thanh ghi (chẳng hạn R1, R2) cho việc sinh mã đích như sau: MOVF id3, R2 MULF #60.0, R2 MOVF id2, R1 ADDF R2, R1 MOVF R1, id1 Toán hạng thứ nhất và thứ hai của mỗi chỉ thị tương ứng mô tả đối tượng nguồn và đích. Chữ F trong mỗi chỉ thị cho biết chỉ thị đang xử lý các số chấm động (floating_point). Dấu # để xác định số 60.0 xem như một hằng số. 7. Ví dụ Xem hình vẽ 1.8 (trang 10) mô tả các giai đoạn biên dịch cho biểu thức: position := initial + rate * 60. IV. NHÓM CÁC GIAI ÐOẠN Các giai đoạn mà chúng ta đề cập ở trên là thực hiện theo trình tự logic của một trình biên dịch. Nhưng trong thực tế, cài đặt các hoạt động của nhiều hơn một giai đoạn có thể được nhóm lại với nhau. Thông thường chúng được nhóm thành hai nhóm cơ bản, gọi là: kỳ đầu (Front end) và kỳ sau (Back end). 1. Kỳ đầu (Front End) Kỳ đầu bao gồm các giai đoạn hoặc các phần giai đoạn phụ thuộc nhiều vào ngôn ngữ nguồn và hầu như độc lập với máy đích. Thông thường, nó chứa các giai đoạn sau: Phân tích từ vựng, Phân tích cú pháp, Phân tích ngữ nghĩa và Sinh mã trung gian. Một phần của công việc tối ưu hóa mã cũng được thực hiện ở kỳ đầu. Front end cũng bao gồm cả việc xử lý lỗi xuất hiện trong từng giai đoạn. 2. Kỳ sau (Back End) Kỳ sau bao gồm một số phần nào đó của trình biên dịch phụ thuộc vào máy đích và nói chung các phần này không phụ thuộc vào ngôn ngữ nguồn mà là ngôn ngữ trung gian. Trong kỳ sau, chúng ta gặp một số vấn đề tối ưu hoá mã, phát sinh mã đích cùng với việc xử lý lỗi và các thao tác trên bảng ký hiệu. 9 position := initial + rate * 60 := + * id1 id2 inttoreal id3 60.0 := + * id1 id2 60 id3 t1 := inttoreal (60) t2:= id3 * t1 t3 := id2 + t2 id1 := t3 t1 := id3 * 60.0 id1 := id2 + t1 MOVF id3, R2 MULF #60.0, R2 MOVF id2, R1 ADDF R2, R1 MOVF R1, id1 id1 := id2 + id3 * 60 Phân tích từ vựng Phân tích cú pháp Phân tích ngữ nghĩa Sinh mã trung gian Tối ưu hóa mã Phát sinh mã đích Hình 1.8 - Minh họa các giai đoạn biên dịch một biểu thức 10 Cơ sở viễn thông Phạm Văn Tấn Trang I.1 Chương I TIN TỨC VÀ HỆ THỐNG THÔNG TIN • LỊCH SỬ PHÁT TRIỂN CÔNG NGHỆ VIỄN THÔNG ĐIỆN TỬ. • PHÂN LOẠI CÁC NGUỒN TIN TỨC VÀ CÁC HỆ THỐNG THÔNG TIN. • SÓ NG XÁC ĐỊNH VÀ SÓNG NGẪU NHIÊN. • SƠ ĐỒ KHỐI MỘT HỆ VIỄN THÔNG. • SỰ PHÂN CHIA CÁC VÙNG TẦN SỐ (FREQUENCY ALLOCATIONS). • SỰ TRUYỀN SÓNG ĐIỆN TỪ. • SỰ ĐO TIN TỨC. • CÁC HỆ THÔNG TIN LÝ TƯỞNG. • Mà HÓA (CODING). Cơ sở viễn thông Phạm Văn Tấn Trang I.2 LỊCH SỬ PHÁT TRIỂN CÔNG NGHỆ VIỄN THÔNG ĐIỆN TỬ. - Từ cuối thế kỹ 18 đầu thế kỹ 19, công nghệ phát thanh và truyền thông bằng điện đã được phát triển. - Năm 1820, George Ohm đã đưa ra công thức phương trình toán học để giải thích các tín hiệu điện chạy qua một dây dẫn rất thành công. - Năm 1830 Michall Faraday đã tìm ra định luật dẫn điện từ trường. - Có thể coi lịch sử thông tin dữ liệu được bắt đầu vào năm 1937 với sự phát minh điện tín Samuel F. B.Morse. Đó là hệ thống truyền các xung điện biểu diễn cho các dấu chấm và vạch (tương đương với các số nhị phân 1, 0) trên các đường dây đồng nhờ các máy cơ điện. Các tổ hợp khác nhau của các mã này thay cho các chữ, số, dấu,...được gọi là mã Morse. - Năm 1840, Morse đăng ký sáng kiến về điện tín ở Mỹ. - Năm 1844 đường đây điện tín đầu tiên được thiết lập giữa Baltimore và Washington DC. - Năm 1849, bản tin đầu tiên được in ra nhưng với vận tốc rất chậm nhưng đến năm 1860 vận tốc in đạt 15 bps. - Năm 1850, đại số Boole của George Boole tạo ra nền móng cho logic học và phát triển rờ le điện. Trong khoảng thời gian gian này, các đường cáp đầu tiên xuyên qua đại tây dương để lắp đặt hệ thống điện tín. - James Clerk Maxwell đã đưa ra học thuyết điện từ trường bằng các công thức toán học vào năm 1980. Căn cứ vào các học thuyết này Henrich Hertz đã truyền đi và nhận được sóng vô tuyến thành công bằng cách dùng điện trường lần đầu tiên trong lịch sử. - Tổng đài điện thoại đầu tiên được thiết lập vào năm 1876 (ngay sau khi Alexander Grâhm Bell đã phát minh ra điện thoại). Năm năm sau Bell bắt đầu dịch vụ gọi đường dài giữa New York và Chocago. Cùng khoảng thời gian đó, Guglieno Marconi của Italia đã lắp đặt một trạm phát sóng vô tuyến để phát các tín hiệu điện tín. - Năm 1900, Einstein, một nhà vật lý nổi tiếng về học thuyết tương đối đã viết rất nhiều tài liệu quan trọng về vật lý chất rắn, thống kê học, điện từ trường và cơ học lượng tử. Vào khoảng thờigian này, phòng thí nghiệm Bell của Mỹ đã phát minh và sáng chế ra ống phóng điện cực cho các kính thiên văn xoay được. Tiếp theo đó, Le De Forest trở thành nguươì khởi xướng trong lĩnh vực vi mạch điện tử thông qua phát minh của ông về một ống chân không ba cực. Lúc này, hệ thống tổng đài tương tự tự động có khả năng hoạt động không cần bảng chuyển mạch. - Năm 1910, Erwin Schrodinger đã thiết lập nền tảng cho cơ học lượng tử thông qua công bố của ông về cân bằng sóng đẻ giải thích cấu tạo nguyên tử và các đặc điểm của chúng. Vào khảng thời gian này, phát thanh công cộng được bắt dầu bằng cách phát sóng. - Năm 1920, Harold .S. Black của phòng thí nghiệm Bell đã phát minh ra một máy khuếch đại phản hồi âm bản mà ngày nay vẫn còn dùng trong lĩnh vực viễn thông và công ngệ máy điện đàm. - V.K.Zworykin (Mỹ) đã phát minh ra đèn hình cho vô tuyến truyền hình và cáp đồng trục (phương tiện truyền dẫn hiệu quả hơn các dây đồng bình thường). - Cuối những năm 1940, phòng thí nghiệm Bell đã đặt ra nền móng cho cho các chất bán dẫn có độ tích hợp cao. Howard Aiken của đại học Harward cộng tác với IBM đã thành công trong việc lắp đặt một máy điện toán đầu tiên có kích thước 50 feets và 8 feets. Và sau đó, J.Presper Ecker với Jonh Mauchly của đại chọc Pénnylvania đã phát triển máy điện toán lên một bậc gọi là máy điện toán ENIAC. Von Neuman dựa vào đây để phát triển máy điện toán có lưu giữ chương trình. - Vào những năm 1960, các loại LSI (Large Scale Interated), các máy điện toán mini, cáp quang và máy phân chia thời gian được phát triển và thương mại hoá thành công. - Vào những năm 1970, truyền hình ảnh qua vệ tinh, các hệ thống tổng đài điện tử cũng lần lượt ra đời. Cơ sở viễn thông Phạm Văn Tấn Trang I.3 Phân loẠi các nguỒn tin tỨc và các hỆ thỐng thông tin. - Một nguồn tin digital ( digital information sourse ) tạo ra 1 tập hợp hữu hạn các bản tin ( Message ) có thể. Ví dụ : Máy đánh chữ ; có một số hữu hạn các ký tự ( bản tin ) được phát ra từ nguồn này. - Một nguồn tin tức analog tạo ra các bản tin được xác định liên tục. Ví dụ một micro: Điện thế ra diễn tả tin tức về âm thanh và nó được phân bố trên một dãy liên tục nhiều trị giá. - Hệ thống thông tin digital chuyển tin tức từ một nguồn digital đến thiết bị thu ( Sink ). - Hệ thống thông tin analog chuyển tin tức từ một nguồn analog đến Sink. Nói một cách chặt chẽ, sóng digital được định nghĩa như là một hàm theo thời gian và chỉ có một tập hợp các trị giá rời rạc. Nếu dạng sóng digital là dạng sóng nhị phân, thì chỉ có hai trị giá. Dạng sóng analog là một hàm theo thời gian có khoảng các trị giá liên tục. Một hệ thống thông tin digital điện tử thường có các điện thế và dòng điện với dạng sóng digital. Tuy nhiên, nó vẫn có thể có các dạng sóng analog. Thí dụ, tin tức từ một nguồn nhị phân có thể phát đến sink bằng cách dùng một sóng sin 1000Hz để diễn tả bit 1 và một sóng sin 500Hz để diễn tả bit 0. Ở đây nguồn tin tức digital được phát đến sink bằng cách dùng các sóng analog, nhưng vẫn cứ gọi là hệ thống viễn thông digital. Xa hơn nữa, sóng analog này được gọi là tín hiệu digital vì nó mô tả 1 nguồn tin digital. Tương tự, một tín hiệu analog mô tả một nguồn tin analog . Từ quan điểm đó ta thấy một kỹ sư Viễn thông digital cần hiểu làm sao để phân tích các mạch analog cũng như các mạch digital. Viễn thông digital có những lợi điểm: - Các mạch digital tương đối rẻ có thể được dùng. - Khoảng tác động lớn hơn. ( Khoảng giữa các trị lớn nhất và nhỏ nhất ). - Dữ liệu từ tiếng nói, hình và các nguồn dữ liệu khác có thể được trộn lẫn và truyền đi trên cùng một hệ truyền digital. - Trong các hệ truyền với khoảng cách xa, nhiễu không chồng chất từ repeater đến repeater. ( Trạm phát lại ). - Sai số trong dữ liệu được phân tích thì nhỏ, dù khi có một lượng nhiễu lớn trên tín hiệu thu được. - Nhiễu có thể được sửa chữa ( corrected ) bằng cách dùng sự mã hóa. Nhưng nó cũng có những bất lợi: - Thông thường, nó cần một hệ rộng dãy tần ( Band width ) lớn hơn hệ analog. - Cần đến sự đồng bộ hóa. Với nhiều ưu điểm, các hệ digital trở nên ngày càng phổ biến. Sóng xác đỊnh và sóng ngẪu nhiên. Trong các hệ Viễn thông, ta phân các dạng sóng làm hai loại lớn: Xác định và Ngẫu nhiên. - Định nghĩa: Một dạng sóng xác định có thể được mô hình hóa như một hàm hoàn toàn riêng biệt của thời gian. Thí dụ: Nếu w(t) = A cos ( ω0t + ϕo ) Diễn tả một dạng sóng , với A, ω0 , ϕo là các hằng đã biết. Thì dạng sóng w(t) được nói là được xác định. - Định nghĩa: Một dạng sóng ngẫu nhiên không thể được chuyên biệt hóa hoàn toàn như là nột hàm theo thời gian và phải mô hình hóa 1 cách xác xuất. Các dạng sóng biểu diễn một nguồn không thể xác định được. Thí dụ, trong hệ viễn thông digital, ta có thể gửi tin tức ứng với bất kỳ một mẫu tự nào - Mỗi mẫu tự được biểu diễn bằng một dạng sóng xác định. Nhưng khi ta xét dạng sóng được phát từ nguồn ta thấy rằng đó là dạng sóng ngẫu nhiên, vì ta không biết chính xác những ký tự sẽ được phát. Cơ sở viễn thông Phạm Văn Tấn Trang I.4 Do đó, ta thực sự cần thiết kế hệ viễn thông dùng dạng sóng ngẫu nhiên và tất nhiên bất kỳ nhiễu nào được đưa vào sẽ cũng được mô tả bằng một dạng sóng ngẫu nhiên. Kỹ thuật này cần đến những khái niệm vể xác suất và thống kê. ( Sẽ làm việc phân tích và thiết kế phức tạp hơn ). Nhưnng may thay , nếu ta trình bày tín hiệu bằng dạng sóng “ tiêu biểu “ xác định, thì ta vẫn có thể được hầu hết, nhưng không tất cả các kết quả. Sơ ĐỒ KHỐI MỘT HỆ THỐNG VIỄN THÔNG. Hình 1.1 Sơ đồ khối của một hệ thống viễn thông. Chủ đích một hệ Viễn thông là truyền một tin tức từ nguồn, ký hiệu là s(t), đến Sink. Tin tức lấy ra từ Sink ký hiệu là (t); tin tức có thể là digital hay analog, tùy vào hệ được dùng. Nó có thể là tin tức về Video, audio hay vài loại khác. ~s Trong các hệ multiplex ( đa hợp ), có thể sẽ có nhiều nguồn vào và nhiều Sink. Phổ của s(t) và (t) tập trung quanh f = 0. Chúng được gọi là những tín hiệu băng gốc ( base band ). ~s Khối xử lý tín hiệu: Ở máy phát tùy điều kiện nguồn sao cho sự truyền có hiệu quả. Thí dụ: Trong 1 hệ digital, nó là một vi xử lý. Trong hệ analog, nó không gì hơn là 1 lọc hạ thông. Trong hệ lai, nó là mạch lấy mẫu tin tức vào ( analog ) và digital - hóa để có một biến điệu mã xung ( Pulse code modulation ) PCM. Tín hiệu ra của khối XLTH ở máy phát cũng là tín hiệu băng gốc vì các tần số tập trung gần f = 0. Khối sóng mang: Ở máy phát đổi tín hiệu băng gốc đã xử lý thành một băng tần để truyền đưa vào kênh truyền. Thí dụ: Nếu kênh gồm một cặp dây xoắn ( twisted - pair ) telephone, phổ của sm(t) sẽ nằm trong dãy âm tần ( audio ), từ 300 -> 3.700Hz. Nhưng nếu kênh gồm cáp quang, phổ của sm(t) sẽ là tần số ánh sáng. - Nếu kênh truyền đi những tín hiệu băng gốc, không cần dùng khối sóng mang và sm(t) có thể là tín hiệu ra của khối XLTH. - Khối sóng mang thì cần khi kênh có thể chỉ truyền các tần số thuộc 1 băng xung quanh fc , với fc >> 0. Trong trường hợp này sm(t) được gọi là tín hiệu dãy thông ( Band pass Signal ). Vì nó được thiết kế để có những tần số thuộc 1 băng quanh fc. Thí dụ, một đài phát biến điệu AM với một tần số kết hợp 850 KHz có sóng mang fc = 850 KHz. Sự áp tín hiệu băng gốc dạng sóng s(t) thành tín hiệu dãy thông sm(t) được gọi là sự biến điệu ( modulation ). ( s(t) là tín hiệu audio trong đài phát AM ). Tín hiệu dãy thông bất kỳ có dạng: sm(t0 = s (t) cos [ ωc(t) + θ(t) ] Với ωc = 2πfc, fc là tần số sóng mang. Nếu s(t) = 1 và θ(t) = 0 thì sm(t) sẽ là một tín hiệu hình sin thuần túy với f = fc và băng tần bằng 0. Cơ sở viễn thông Phạm Văn Tấn Trang I.5 Trong sự biến điệu bởi mạch sóng mang, sóng vào s(t) làm cho R (t) và/hoặc θ(t) thay đổi như là một hàm của s(t). Sự thay đổi trong R (t) và θ(t) làm cho sm(t) có một khổ băng phụ thuộc vào những tính chất của s(t0 và vào hàm áp được dùng để phát ra R (t) và θ(t). Các kênh truyền: Có thể phân chia làm 2 loại: dây mềm ( softwire ) và dây cứng (hardwire). Vài loại kênh dây mềm tiêu biểu như: Không khí, chân không và nước biển. Vài loại kênh truyền dây cứng: Cặp dây xoắn telephone, cáp đồng trục, ống dẫn sóng và cáp quang. Một cách tổng quát, kênh truyền làm giảm tín hiệu, nhiễu của kênh truyền và / hoặc nhiễu do máy thu khiến cho ~s (t) bị xấu đi so với nguồn. Nhiễu của kênh có sự gia tăng từ nguồn điện, dây cao thế, sự đánh lửa hoặc nhiễu do sự đóng ngắt của một computer. Kênh có thể chứa bộ phận khuếch đại tác động, thí dụ: Hệ thống repeater trong telephone hoặc như vệ tinh tiếp chuyển trong hệ thống viễn thông trong không gian. Dĩ nhiên, các bộ phận này cần thiết để giữ cho tín hiệu lớn hơn nhiễu. Kênh cũng có thể có nhiều đường ( multiple paths ) giữa input và output và chúng có thời gian trễ ( time delay ), tính chất giảm biên ( attenuation ) khác nhau. Những tính chất này có thể thay đổi theo thời gian. Sự thay đổi này làm thay đổi bất thường ( fading ) tín hiệu ở ngõ ra của kênh. ( Ta có thể quan sát sự fading khi nghe khi nghe 1 đài sóng ngắn ở xa ). Máy thu nhận tín hiệu ở ngỏ ra của kênh và đổi nó thành tín hiệu băng gốc. SỰ phân chia các vùng tẦN sỐ (Frequency Allocations). Trong các hệ thông tin dùng không khí làm kênh truyền, các điều kiện về giao thoa và truyền sóng thì phụ thuộc chặt chẽ vào tần số truyền. Về mặt lý thuyết, bất kỳ một kiểu biến điệu nào (Am, Fm, một băng cạnh - single sideband, phase shift keying, frequency shift keying...) đều có thể được dùng cho bất kỳ tần số truyền nào. Tuy nhiên, theo những qui ước quốc tế, kiểu biến điệu độ rộng băng, loại tin được truyền cần được xếp đặt cho từng băng tần. Bảng sau đây cho danh sách các băng tần, ký hiệu, điều kiện truyền và công dụng tiêu biểu của chúng. Băng tần Ký hiệu Đặt tính truyền Những ứng dụng tiêu biểu 3 - 30KHz VLF very low frequency Sóng đất. Suy giảm ít ngày và đêm. Nhiểu không khí cao Thông tin dưới nước 30- 300KHz LF low frequency Tương tự VLF. Ít tin cậy. Bị hấp thu vào ban ngày Hướng dẫn radio cho hải hành 300- 3000KHz MF Medium frequency Sóng đất và sóng trời ban đêm. Suy giảm ít vào ban và nhiểu vào ban ngày. Nhiểu không khí Radio hàng hải. Tần số cấp cứu phát sống Am 3 - 30MHz HF Hight frequency Sự phản xạ ở tần ion cần thay đổi theo thời gian trong ngày, theo mùa và theo tần số. Nhiểu không khí ít tại 30Mhz radio nghiệp dư. Phát thanh quốc tế. Viễn thông quân sự. Thông tin đường dài cho không hành và hải hành. Điện thoại, điện tín, fax. 30- 300MHz VHF Very high frequency Gần với LOS. Sự tán xạ gây bởi những thay đổi nhiệt độ. Nhiễu không gian. Truyền hình VHF. Radio FM stereo. Trợ giúp không hành. 0.3 - 3 GHz 1.0 - 2.0 GHz 2.0 - 4.0 GHz UHF Ultra high frequency L S Truyền LOS. Nhiễu không gian. Truyền hình VHF. Radio FM Stereo. Trợ giúp không hành. 3 - 30 GHz SHF Truyền LOS. Suy giảm do Viễn thông vệ tinh. Radar Cơ sở viễn thông Phạm Văn Tấn Trang I.6 Băng tần Ký hiệu Đặt tính truyền Những ứng dụng tiêu biểu 2 - 4.0 4.0 - 8.0 8.0 - 12.0 12.0 - 18.0 18.0 - 27.0 27.0-40.0 Supper high frequency S C X KU K Ka Oxi và hơi nước trong không khí. Sự hấp thụ do hơi nước rất cao tại 22.2 GHz microwave links. 30 - 300 GHz 26.5 - 40 33.0 - 50.0 40.0 - 75.0 75.0 - 110.0 110 - 300 EHF Extremely high frequency R Q V W Mm Tương tự trên. Hơi nước hấp thụ rất mạnh tại 183GHz. Oxy hấp thu tại 60 và 119 GHz . Radar, vệ tinh, thí nghiệm. 103 - 107 IR (Hồng ngoại ) ánh sáng khả kiến và UV ( Tử ngoại ) Truyền LOS Viễn thông quang SỰ truyỀn sóng điỆn tỪ. Các đặc tính truyền của sóng điện từ được truyền trong kênh truyền dây mềm thì phụ thuôc nhiều vào tần số. Điều này được thấy từ bảng kê ở trên. Phổ điện từ có thể được chia làm 3 băng lớn: Sóng mặt đất ( Ground ware ), sóng trời ( Sky ware ) và sóng truyền theo đường tầm mắt ( light of sight ) LOS. Sự truyền tín hiệu (signal propagation) a. Truyền sóng đất Anten phát (Transmit antenna) The Earth Anten thu (Recieve antenna) ` b. Truyền sóng trời Anten phát (Transmit antenna) Anten thu (Recieve antenna) The Earth Ion cầu Sự truyền tín hiệu (signal propagation) Cơ sở viễn thông Phạm Văn Tấn Trang I.7 Sự truyền tín hiệu (signal propagation) c. Truyền theo đường tầm mắt The Earth Anten thu (Recieve antenna) Anten phát (Transmit antenna) Hình 1.2: sự truyền sóng điện từ. 1. Tần số của sóng đất nhỏ hơn 2 MHz. Ở đây sóng điện từ có khuynh hướng truyền theo chu vi trái đất. Kiểu truyền này được dùng trong các đài AM. Ở đấy sự phủ sóng địa phương theo đường cong mặt đất và tín hiệu truyền trên đường chân trời thấy được. Câu hỏi thường được đặt ra: “ Tần số thấp nhất của sóng có thể dùng là bao nhiêu ? Câu trả lời là tần số này tùy thuộc vào chiều dài của anhten phát. Để sự bức xạ có hiệu quả, antenna cần dài hơn 1/10 bước sóng. Ví dụ: Với sóng mang fC = 10KHz, bước sóng là: λ = C fC λ = ( 3.108m/s )/104Hz = 3.104 m Như vậy, một anten dài ít nhất 3.000m để bức xạ có hiệu quả một sóng điện từ 10KHz! 2. Khoảng tần số của sóng trời là 2 đến 30 Mhz. Sự truyền của sóng này dựa vào sự phản xạ tầng ion ( ion sphere - tầng điện ly ) và mặt đất. Nhờ đó, có thể truyền một khoảng rất xa. Tầng ion có biểu đồ phân bố như sau: Hình 1.3: Biểu đồ phân bố tầng ion Sự ion hóa xãy ra do sự kích thích các phân tử khí bởi các bức xạ vũ trụ từ mặt trời. Tầng ion gồm các lớp E, F1, F2, D. Lớp D chỉ hình thành vào ban ngày và là lớp chủ yếu hấp thụ sóng trời. Lớp F là lớp chính, làm phản xạ sóng trời về trái đất. Thực tế, sự khúc xạ từng bậc qua các lớp của tầng ion khiến tầng này tác dụng như một vật phản xạ làm sóng trời bị phản xạ trở lại trái đất. Cơ sở viễn thông Phạm Văn Tấn Trang I.8 Hình 1.4: Sự phản xạ sóng trời bở tầng ion. Chỉ số khúc xạ n thay đổi theo độ cao của tầng ion, vì mật độ electron tự do thay đổi. n = 1 812− nf Trong đó: N: Mật độ electron tự do ( số e-/m3 ). f: tần số của sóng (Hz). - Dưới vùng ion hóa, n = 1 - Trong vùng ion hóa, n 0 ) Sóng bị khúc xạ theo định luật Snell: nsinϕr = sinϕi Trong đó: ϕI : Góc đến ϕr: Góc khúc xạ. a. Với những sóng có tần số f < 2MHz : 81N > f2 nên n trở nên ảo. Tầng ion sẽ làm giảm sóng đến. b. Với những sóng có tần số từ 2 - 30 MHz ( Sóng trời ), sự truyền sóng, góc phản xạ và sự hao hụt tín hiệu tại một điểm phản xạ ở tầng ion tùy thuộc vào f, vào thời gian trong ngày, theo mùa và sự tác động của vết đen mặt trời. Ban ngày, N rất lớn làm n ảo. Sóng bị hấp thu, có rất ít sóng trở lại trái đất. Ban đêm, N nhỏ nên n < 1. Khi đó, nếu sóng truyền từ trái đất lên tầng ion thì ϕr > ϕI. Sẽ xãy ra hiện tượng khúc xạ từng bậc. Do sự phản xạ nhiều lần giữa tầng ion và mặt đất, sóng trời truyền đi rất xa. Vì thế, có những sóng trời phát ra từ những đài xa bên kia trái đất vẫn có thể thu được trên băng sóng ngắn. 3. Sự truyền LOS là phương thức truyền cho các tần số trên 30 MHz. Ở đó, sóng điện từ truyền theo đường thẳng. Trong trường hợp này f2 >> 81N làm cho n ≈ 1 và như vậy có rất ít sóng bị khúc xạ bởi tầng ion. Sóng sẽ truyền ngang qua tầng này. Tính chất đó được dùng cho thông tin vệ tinh. Cách truyền LOS bất lợi cho việc truyền thông tin giữa 2 trạm mặt đất, khi mà đường đi tín hiệu phải ở trên đường chân trời. Độ cong mặt đất sẽ chặn đường truyền LOS. Cơ sở viễn thông Phạm Văn Tấn Trang I.9 Hình 1.5 Anten phát cần phải đặt trên cao, sao cho anten thu phải “ thấy “ được nó. d2 + r2 = ( r + h )2 d2 = 2rh + h2 h2 << 2 rh Như vậy: d = 2rh Bán kính trái đất là 3.960 miles. Tuy nhiên, tại những tần số LOS bán kính hiệu dụng là 4 3 3960. . Vậy khoảng cách d = 2rh miles. Trong đó h tính bằng feet. Thí dụ: Các đài truyền hình có tần số trên 30MHz trong băng VHF và UHF, vùng phủ sóng của các đài công suất lớn bị giới hạn bởi đường tầm mắt. Với một tháp anten 1000 ft → d = 44,7miles. Nếu anten thu cao 30 feet , d = 7,75 miles. Vậy với chiều cao đài phát và máy thu này, đài có vùng phủ sóng có bán kính 44,7 + 7,75 = 52,5 miles. * Với những tần số 30 - 60 MHz, tín hiệu có thể bị tán xạ bởi tầng ozon. Sự tán xạ là do sự bất thường của n ở lớp dưới của tầng này. ( ≈ 50 miles trên mặt đất ). Khiến cho thông tin có thể truyền đi xa hơn cả 1000 miles. * Tương tự sự phản xạ ở tầng tropo ( trong vòng 10 miles cao hơn mặt đất ) có thể truyền tín hiệu ( 40 MHz - 4GHz ) xa vài trăm miles. 1 miles = 1.609,31 m 1 feet = 0.3048 m sea miles = 1852 m. SỰ đo tin tỨc. Định nghĩa: Tin tức gửi từ 1 nguồn digital, khi bản tin thứ j được truyền đi là : IJ = log2 1 PJ ⎛ ⎝⎜ ⎞ ⎠⎟ bits PJ: Là xác suất của việc truyền bản tin thứ J Cơ số (base) của log xác định đơn vị được dùng để đo tin tức.Nếu log cơ số 2, thì đơn vị là bits.Với log tự nhiên đơn vị là Nats.Và với log cơ số 10 đơn vị sẽ là Hastley Bit, đơn vị đo tin có ý nghĩa khác với bit là đơn vị của dữ liệu nhị phân.Tuy nhiên người ta vẫn hay dùng ” bit ” để ký hiệu cho cả hai loại đơn vị. Công thức trên được viết lại với cơ số tự nhiên và cơ số 10: IJ = − = −1 2 1 210 10log log log logP Pj n n j Một cách tổng quát, nội dung tin tức sẽ thay đổi từ bản tin này đến bản tin khác, vì PJ sẽ không bằng nhau. Như vậy, ta cần đến một sự đo tin tức trung bình của nguồn. Cơ sở viễn thông Phạm Văn Tấn Trang I.10 Định nghĩa: Số đo tin tức trung bình (average information) của 1 nguồn là: H = P I P P bitsj j j m j jj m = = ∑ ∑= ⎛⎝⎜ ⎞ ⎠⎟1 21 1log m: Số bản tin. PJ : Xác suất của sự gởi bản tin thứ J Tin tức trung bình còn gọi là entropy. Ví dụ: Tìm information content (dung lượng tin tức ) tin tức của một bản tin gồm một word digitaldài 12digit , trong đó mỗi digit có thể lấy một trong 4 mức có thể. Xác suất của sự gởi một mức bất kỳ trong 4 mức được giả sử bằng nhau và mức của một digit không tùy thuộc vào trị giá được lấy của digit trước đó. Trong một string gồm 12 symbol (digit) mà ở đó mỗi symbol gồm một trong 4 mức đó là 4.4.....4 = 412 bits, tổ hợp (word) khác nhau. Vì mỗi mức gồm bằng nhau tất cả các word khác nhau đều bằng nhau. Vậy: PJ = 1 4 1 412 12 =⎛⎝⎜ ⎞ ⎠⎟ hoặc IJ = ( )log log2 1 2 2 1 1 4 12 4 24 ⎛ ⎝⎜ ⎞ ⎠⎟ ⎛ ⎝ ⎜⎜⎜⎜⎜ ⎞ ⎠ ⎟⎟⎟⎟⎟ = = bits Trong ví dụ trên ta thấy dung lượng tin ( information content ) trong bất kỳ một bản tin có thể nào đó đều bằng với dung tin trong bất kỳ bản tin có thể khác (24 bits). Vậy tin tức trung bình H là 24 bits. Giả sử rằng chỉ có 2 mức (nhị phân) được cho phép cho mỗi digit và rằng tất cả các wordthì gần bằng nhau Vậy tin tức sẽ là IJ = 12 bits cho word nhị phân và tin tức trung bình là H = 12bits. Ở đó tất cả word 12 bits sẽ cho 12 bits tin tức vì các word gần bằng nhau Nếu chúng không bằng nhau một vài trong các word 12 bits sẽ chứa hơn 12 bits tin tức và một vài sẽ chứa ít hơn .Và tin tức trung bình sẽ chứa ít hơn. Đinh nghĩa: Nhịp độ của nguồn (nate source) được cho bởi R = H T bits/sec H: Tin tức trung bình. T: Thời gian cần thiết để gửi một bản tin. Định nghĩa trên được áp dụng cho một nguồn digital. Các hỆ thông tin lý tưỞng. Có một số tiêu chuẩn được dùng để đánh giá tín hiệu quả của một hệ thông tin . Đó là giá thành, độ rộng kênh, công suất truyền, tỷ số s/n tại những điểm khác nhau của hệ, thời gian trể ngang qua hệ thống. Và xác suất bit error của hệ digital. Trong các hệ digital, hệ tối ưu có thể được nghĩa như là một hệ có xác suất bit error tối thiểu ở ngõ ra của hệ với sự cưỡng chế về công suất được phát và độ rộng kênh. Điều này làm nảy ra câu hỏi: liệu có thể phát minh một hệ không có bit error ở ngõ ra dù khi có nhiễu thâm nhập vào kênh ? Câu hỏi này được Claude Shannon trả lời là có thể, với vài giả thiết Shannon chứng minh rằng một dung lượng kênh C (bits/sec) sẽ được tính sao cho nếu nhịp độ tin tức R (bits/sec) nhỏ hơn C, thì xác suất của bit error tiến đến zero. Phương trình của C là: Cơ sở viễn thông Phạm Văn Tấn Trang I.11 C = B log2 1+⎡⎣⎢ ⎤ ⎦⎥ S N B: Độ rộng kênh (Hz) và S/N là tổng số công suất tín hiệu trên nhiễu tại ngõ vô của máy thu digital. - Trong các hệ analog, hệ tối ưu có chỗ định nghĩa như là một hệ có tổng số S/N lớn nhất ở ngõ ra máy thu với sự cưỡng chế về công suất được phát và độ rộng kênh. Ta có thể đặt câu hỏi: Liệu có thể thiết kế một hệ thống với tổng số S/N lớn vô hạn ở ngõ ra khi nhiễu thâm nhập vào kênh ? Câu trả lời là dĩ nhiên là không. mã hóa (CODING). Nếu dữ liệu ở ngõ ra của một hệ thông tin digital có errors, có thể giảm error bằng cách dùng một trong hai kỹ thuật : -Automatic Repeat request (ARQ). -Forward error conection (FEC). Trong một hệ ARQ, khi máy thu phân tích được error trong khối dữ liệu, nó yêu cầu khối dữ liệu phát trở lại. Trong một hệ FEC dữ liệu được phát ra cần được mã hóa sao máy thu có thể sữa sai như là các sai số đã phân tích. Biện pháp này cũng được xếp loại như sự mã hóa kênh, vì nó được dùng để sữa sai khi kênh bị nhiễu. Sự chọn lựa ARQ hay FEC tùy vào áp dụng riêng. ARQ thường được dùng trong hệ thông tin computer. FEC được dùng đễ sửa sai trễ các kênh simplex (1 way). Hệ thông tin với FEC được vẽ ở hình dưới đây. Về mặt lý thuyết dung lượng kênh của Shannon chứng tỏ rằng một trị giá vô hạn của S/N chỉ giới hạn nhịp độ truyền. Đó là xác suất của error P(E) có thể tiến đến zero khi nhịp độ tin tức nhỏ hơn dung lượng kênh. Hình 1.6 Mã hoá và xử lý Mạch sóng mang Mạch sóng mang kênh )( ~ tgm g(t) s(t) r(t) )( ~ tm Mã hoá và xử lý nhiễu Truyền Nhận Bộ thu tín hiệu số Tín hiệu số LÝ THUYẾT CƠ BẢN VỀ QUY HOẠCH TUYẾN TÍNH 5 CHƯƠNG I LÝ THUYẾT CƠ BẢN VỀ QUY HOẠCH TUYẾN TÍNH Chương này trình bày cách xây dựng mô hình quy hoạch tuyến tính của những bài toán dạng đơn giản. Đây là những kiến thức quan trọng để xây dựng mô hình cho những bài toán phức tạp hơn trong thực tế sau này. Các khái niệm về ‘’ lồi’’ đuợc trình bày để làm cơ sở cho phương pháp hình học giải quy hoạch tuyến tính. Một ví dụ mở đầu được trình bày một cách trực quan để làm rõ khái niệm về phương án tối ưu của quy hoạch tuyến tính. Nội dung chi tiết của chương bao gồm : I- GIỚI THIỆU BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 1- Bài toán vốn đầu tư 2- Bài toán lập kế hoạch sản xuất 3- Bài toán vận tải II- QUY HOẠCH TUYẾN TÍNH TỔNG QUÁT VÀ CHÍNH TẮC 1- Quy hoạch tuyến tính tổng quát 2- Quy hoạch tuyến tính dạng chính tắc 3- Phương án III- ĐẶC ĐIỂM CỦA TẬP HỢP CÁC PHƯƠNG ÁN 1- Khái niệm lồi và tính chất 2- Đặc điểm của tập các phương án 3- Phương pháp hình học IV- MỘT VÍ DỤ MỞ ĐẦU V- DẤU HIỆU TỐI ƯU 1- Ma trận cơ sở - Phương án cơ sở - Suy biến 2- Dấu hiệu tối ưu LÝ THUYẾT CƠ BẢN VỀ QUY HOẠCH TUYẾN TÍNH 6 CHƯƠNG I LÝ THUYẾT CƠ BẢN VỀ QUY HOẠCH TUYẾN TÍNH I- GIỚI THIỆU BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Có thể tạm định nghĩa quy hoạch tuyến tính là lĩnh vực toán học nghiên cứu các bài toán tối ưu mà hàm mục tiêu (vấn đề được quan tâm) và các ràng buộc (điều kiện của bài toán) đều là hàm và các phương trình hoặc bất phương trình tuyến tính. Đây chỉ là một định nghĩa mơ hồ, bài toán quy hoạch tuyến tính sẽ được xác định rõ ràng hơn thông qua các ví dụ . Các bước nghiên cứu và ứng dụng một bài toán quy hoạch tuyến tính điển hình là như sau : a- Xác định vấn đề cần giải quyết, thu thập dữ liệu. b- Lập mô hình toán học. c- Xây dựng các thuật toán để giải bài toán đã mô hình hoá bằng ngôn ngữ thuận lợi cho việc lập trình cho máy tính. d- Tính toán thử và điều chỉnh mô hình nếu cần. e- Áp dụng giải các bài toán thực tế. 1- Bài toán vốn đầu tư Người ta cần có một lượng (tối thiểu) chất dinh dưỡng i=1,2,..,m do các thức ăn j=1,2,...,n cung cấp. Giả sử : aij là số lượng chất dinh dưỡng loại i có trong 1 đơn vị thức ăn loại j (i=1,2,...,m) và (j=1,2,..., n) bi là nhu cầu tối thiểu về loại dinh dưỡng i cj là giá mua một đơn vị thức ăn loại j Vấn đề đặt ra là phải mua các loại thức ăn như thế nào để tổng chi phí bỏ ra ít nhất mà vẫn đáp ứng được yêu cầu về dinh dưỡng. Vấn đề được giải quyết theo mô hình sau đây : Gọi xj ≥ 0 (j= 1,2,...,n) là số lượng thức ăn thứ j cần mua . Tổng chi phí cho việc mua thức ăn là : LÝ THUYẾT CƠ BẢN VỀ QUY HOẠCH TUYẾN TÍNH 7 nn2211 n 1j jj xc......xcxc xcz +++== ∑ = Vì chi phí bỏ ra để mua thức ăn phải là thấp nhất nên yêu cầu cần được thỏa mãn là : nn2211 n 1j jj xc......xcxc xcz min +++== ∑ = Lượng dinh dưỡng i thu được từ thức ăn 1 là : ai1x1 (i=1→m) Lượng dinh dưỡng i thu được từ thức ăn 2 là : ai2x2 ......................................................... Lượng dinh dưỡng i thu được từ thức ăn n là : ainxn Vậy lượng dinh dưỡng thứ i thu được từ các loại thức ăn là : ai1x1+ai2x2+...+ainxn (i=1→m) Vì lượng dinh dưỡng thứ i thu được phải thỏa yêu cầu bi về dinh dưỡng loại đó nên ta có ràng buộc sau : ai1x1+ai2x2+...+ainxn ≥ bi (i=1→m) Khi đó theo yêu cầu của bài toán ta có mô hình toán sau đây : nn2211 n 1j jj xc......xcxc xcz min +++== ∑ = ⎪⎪ ⎪⎪ ⎩ ⎪⎪ ⎪⎪ ⎨ ⎧ =≥ ≥+++ ≥+++ ≥+++ n)1,2,...,(j 0x bxa...xaxa .......................................... bxa...xaxa bxa...xaxa j mnmn2m21m1 2n2n222121 1n1n212111 2- Bài toán lập kế hoạch sản xuất Từ m loại nguyên liệu hiện có người ta muốn sản xuất n loại sản phẩm Giả sử : aij là lượng nguyên liệu loại i dùng để sản xuất 1 sản phẩm loại j (i=1,2,...,m) và (j=1,2,..., n) bi là số lượng nguyên liệu loại i hiện có cj là lợi nhuận thu được từ việc bán một đơn vị sản phẩm loại j LÝ THUYẾT CƠ BẢN VỀ QUY HOẠCH TUYẾN TÍNH 8 Vấn đề đặt ra là phải sản xuất mỗi loại sản phẩm là bao nhiêu sao cho tổng lợi nhuận thu được từ việc bán các sản phẩm lớn nhất trong điều kiện nguyên liệu hiện có. Gọi xj ≥ 0 là số lượng sản phẩm thứ j sẽ sản xuất (j=1,2,...,n) Tổng lợi nhuận thu được từ việc bán các sản phẩm là : nn2211 n 1j jj xc......xcxc xcz +++== ∑ = Vì yêu cầu lợi nhuận thu được cao nhất nên ta cần có : nn2211 n 1j jj xc......xcxc xczmax +++== ∑ = Lượng nguyên liệu thứ i=1→m dùng để sản xuất sản phẩm thứ 1 là ai1x1 Lượng nguyên liệu thứ i=1→m dùng để sản xuất sản phẩm thứ 2 là ai2x2 ............................................... Lượng nguyên liệu thứ i=1→m dùng để sản xuất sản phẩm thứ n là ainxn Vậy lượng nguyên liệu thứ i dùng để sản xuất là các sản phẩm là ai1x1+ai2x2+...+ainxn Vì lượng nguyên liệu thứ i=1→m dùng để sản xuất các loại sản phẩm không thể vượt quá lượng được cung cấp là bi nên : ai1x1+ai2x2+...+ainxn ≤ bi (i=1,2,...,m) Vậy theo yêu cầu của bài toán ta có mô hình sau đây : nn2211 n 1j jj xc......xcxc xczmax +++== ∑ = ⎪⎪ ⎪⎪ ⎩ ⎪⎪ ⎪⎪ ⎨ ⎧ =≥ ≤+++ ≤+++ ≤+++ n)1,2,...,(j 0x bxa...xaxa .......................................... bxa...xaxa bxa...xaxa j mnmn22m11m 2nn2222121 1nn1212111 3- Bài toán vận tải Người ta cần vận chuyển hàng hoá từ m kho đến n cửa hàng bán lẻ. Lượng hàng hoá ở kho i là si (i=1,2,...,m) và nhu cầu hàng hoá của cửa hàng j là dj LÝ THUYẾT CƠ BẢN VỀ QUY HOẠCH TUYẾN TÍNH 9 (j=1,2,...,n). Cước vận chuyển một đơn vị hàng hoá từ kho i đến của hàng j là cij ≥ 0 đồng. Giả sử rằng tổng hàng hoá có ở các kho và tổng nhu cầu hàng hoá ở các cửa hàng là bằng nhau, tức là : ∑∑ == = n 1j j m 1i i ds Bài toán đặt ra là lập kế hoạch vận chuyển để tiền cước là nhỏ nhất, với điều kiện là mỗi cửa hàng đều nhận đủ hàng và mỗi kho đều trao hết hàng. Gọi xij ≥ 0 là lượng hàng hoá phải vận chuyển từ kho i đến cửa hàng j. Cước vận chuyển chuyển hàng hoá i đến tất cả các kho j là : ∑ = n 1j ijijxc Cước vận chuyển tất cả hàng hoá đến tất cả kho sẽ là : ∑∑ = = = m 1i n 1j ijijxcz Theo yêu cầu của bài toán ta có mô hình toán sau đây : ⎪⎩ ⎪⎨ ⎧ ==≥ == = ∑ ∑∑ = = = n)1,1,...,(j m)1,2,...,(i 0x n)1,2,...,(j dx xcz min ij m 1i jij m 1i n 1j ijij II- QUY HOẠCH TUYẾN TÍNH TỔNG QUÁT VÀ CHÍNH TẮC 1- Quy hoạch tuyến tính tổng quát Tổng quát những bài toán quy hoạch tuyến tính cụ thể trên, một bài toán quy hoạch tuyến tính là một mô hình toán tìm cực tiểu (min) hoặc cực đại (max) của hàm mục tiêu tuyến tính với các ràng buộc là bất đẳng thức và đẳng thức tuyến tính. Dạng tổng quát của một bài toán quy hoạch tuyến tính là : LÝ THUYẾT CƠ BẢN VỀ QUY HOẠCH TUYẾN TÍNH 10 ( ) ( ) ( )⎪ ⎪⎪ ⎪⎪ ⎪ ⎩ ⎪⎪ ⎪⎪ ⎪⎪ ⎨ ⎧ ⎪⎩ ⎪⎨ ⎧ ∈ ∈≤ ∈≥ ⎪⎪ ⎪⎪ ⎩ ⎪⎪ ⎪⎪ ⎨ ⎧ ∈≥ ∈≤ ∈= = ∑ ∑ ∑ ∑ = = = = 3j 2j 1j 3i n 1j jij 2i n 1j jij 1i n 1j jij n 1j jj Jj tùy ý x (III) Jj 0x Jj 0x )I(i bxa (II) )I(i bxa )I(i bxa (I) xcz maxmin/ Trong đó : • (I) Hàm mục tiêu Là một tổ hợp tuyến tính của các biến số, biểu thị một đại lượng nào đó mà ta cần phải quan tâm của bài toán. • (II) Các ràng buộc của bài toán Là các phương trình hoặc bất phương trình tuyến tính n biến số, sinh ra từ điều kiện của bài toán. • (III) Các các hạn chế về dấu của các biến số Người ta cũng thường trình bày bài toán quy hoạch tuyến tính dưới dạng ma trận như sau : [ ] ⎥⎥ ⎥⎥ ⎥⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎢⎢ ⎣ ⎡ == mnm21m 2n2221 1n1211 ij a ... a a ...................... a ... a a a ... a a aA ⎥⎥ ⎥⎥ ⎥⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎢⎢ ⎣ ⎡ = ⎥⎥ ⎥⎥ ⎥⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎢⎢ ⎣ ⎡ = ⎥⎥ ⎥⎥ ⎥⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎢⎢ ⎣ ⎡ = m 2 1 n 2 1 n 2 1 b ... b b b c ... c c c x ... x x x Gọi ai (i=1→m) là dòng thứ i của ma trận A, ta có : LÝ THUYẾT CƠ BẢN VỀ QUY HOẠCH TUYẾN TÍNH 11 ( ) ( ) ( )⎪⎪ ⎪⎪ ⎩ ⎪⎪ ⎪⎪ ⎨ ⎧ ⎪⎩ ⎪⎨ ⎧ ∈ ∈≤ ∈≥ ⎪⎩ ⎪⎨ ⎧ ∈≥ ∈≤ ∈= = 3j 2j 1j 3ii 2ii 1ii T Jj tùy ý x (III) Jj 0x Jj 0x )I(i bxa (II) )I(i bxa )I(i bxa (I) xc)x(zin/max m Người ta gọi : - A là ma trận hệ số các ràng buộc. - c là vectơ chi phí (cT là chuyển vị của c) - b là vectơ giới hạn các ràng buộc. 2- Quy hoạch tuyến tính dạng chính tắc Bài toán quy hoạch tuyến tính chính tắc là bài toán quy hoạch tuyến tính mà trong đó các ràng buộc chỉ có dấu = và các biến số đều không âm. ⎪⎪⎩ ⎪⎪⎨ ⎧ =≥ == = ∑ ∑ = = (III) n)1,2,...,(j 0x (II) )m1,2,...,(i bxa (I) xczmin/max j i n 1j jij n 1j jj ( m≤ n ) rang(A)=m ⎪⎩ ⎪⎨ ⎧ ≥ = = (III) 0x (II) bAx (I) xc)x(z min/max T Người ta có thể biến đổi bài toán quy hoạch tuyến tính dạng tổng quát thành bài toán quy hoạch tuyến tính dạng chính tắc nhờ các quy tắc sau đây : - Nếu gặp ràng buộc i có dạng ≤ thì người ta cộng thêm vào vế trái của ràng buộc một biến phụ xn+i ≥ 0 để được dấu = . LÝ THUYẾT CƠ BẢN VỀ QUY HOẠCH TUYẾN TÍNH 12 - Nếu gặp ràng buộc i có dạng ≥ thì người ta trừ vào vế trái của ràng buộc một biến phụ xn+i ≥ 0 để được dấu = . Các biến phụ chỉ là những đại lượng giúp ta biến các ràng buộc dạng bất đẳng thức thành đẳng thức, nó phải không ảnh hưởng gì đến hàm mục tiêu nên không xuất hiện trong hàm mục tiêu. - Nếu biến xj ≤ 0 thì ta đặt xj = -x’j với x’j ≥ 0 rồi thay vào bài toán. - Nếu biến xj là tuỳ ý thì ta đặt jjj xxx ′′−′= với jj x , x ′′′ đều ≥ 0 rồi thay vào bài toán. - Trong trường hợp trong số các ràng buộc có dòng mà vế phải của dòng đó là giá trị âm thì đổi dấu cả hai vế để được vế phải là một giá trị không âm. Dựa vào các phép biến đổi trên mà người ta có thể nói rằng bài toán quy hoạch tuyến tính chính tắc là bài toán quy hoạch tuyến tính mà trong đó các ràng buộc chỉ có dấu = , vế phải và các biến số đều không âm. Ví dụ : Biến đổi bài toán quy hoạch tuyến tính sau đây về dạng chính tắc : ⎪⎪ ⎪⎪ ⎪⎪ ⎩ ⎪⎪ ⎪⎪ ⎪⎪ ⎨ ⎧ ⎪⎪⎩ ⎪⎪⎨ ⎧ ≤ ≥ ⎪⎪ ⎪ ⎩ ⎪⎪ ⎪ ⎨ ⎧ =+−+ ≥++ −≥++ ≤+++− −++−= tùy ý x , x 0x 0x , x 20xx2xx 10x3xx2 1xx2x 7xx2xx2x x2xx2xx2)x(z min 32 4 51 4321 543 432 54321 54321 Bằng các thay thế : )0x,x( xxx )0x,x( xxx )0x( xx 33333 22222 444 ≥′′′′′−′= ≥′′′′′−′= ≥′′−= ta được : LÝ THUYẾT CƠ BẢN VỀ QUY HOẠCH TUYẾN TÍNH 13 0x,x, x, x, x, x, x, x, x , x 20x)xx(2)xx(x 10xx3x)xx(2 1xx)xx(2)xx( 7xxx2)xx()xx(2x x2x)xx(2)xx(x2)x(z min 4332287651 433221 85433 743322 65433221 5433221 ≥′′′′′′′ ⎪⎪⎩ ⎪⎪⎨ ⎧ =′−′′−′−′′−′+ =−+′−′′−′ −=−+′′−′+′′−′ =++′−′′−′+′′−′− −′−′′−′+′′−′−= hay : 0x,x, x, x, x, x, x, x, x, x 20x)xx(2)xx(x 10xx3x)xx(2 1xx)xx(2)xx( 7xxx2)xx()xx(2x x2x)xx(2)xx(x2)x(z min 4332287651 433221 85433 743322 65433221 5433221 ≥′′′′′′′ ⎪⎪⎩ ⎪⎪⎨ ⎧ =′−′′−′−′′−′+ =−+′−′′−′ =+−′′−′−′′−′− =++′−′′−′+′′−′− −′−′′−′+′′−′−= 3- Phương án Xét bài toán quy hoạch tuyến tính chính tắc : (P) ⎩⎨ ⎧ ≥ = = 0x bAx xc)x(z min/max T • x=[x1 x2 ... xn] T là một phương án của (P) khi và chỉ khi Ax = b. • x=[x1 x2 ... xn] T là một phương án khả thi của (P) khi và chỉ khi Ax = b và x ≥ 0 . • Một phương án tối ưu của (P) là một phương án khả thi của (P) mà giá trị của hàm mục tiêu tương ứng đạt min/max. LÝ THUYẾT CƠ BẢN VỀ QUY HOẠCH TUYẾN TÍNH 14 III- ĐẶC ĐIỂM CỦA TẬP HỢP CÁC PHƯƠNG ÁN 1- Khái niệm lồi và các tính chất a- Tổ hợp lồi - Cho m điểm xi trong không gian Rn . Điểm x được gọi là tổ hợp lồi của các điểm xi nếu : 1.... 0,....,, x...xx xx n21n21 m m 2 2 1 1 m 1i i i =α++α+α≥ααα α++α+α=α= ∑ = - Khi x là tổ hợp lồi của hai điểm x1, x2 người ta thường viết : x=λx1+(1-λ)x2 (0≤λ≤1) Nếu 0<λ<1 thì x được gọi là tổ hợp lồi thật sự. - Ðoạn thẳng Tập hợp tất cả các tổ tổ hợp lồi của 2 điểm bất kỳ A, B∈ Rn được gọi là đoạn thẳng nối A và B . Ký hiệu : δAB= {x = λA + (1-λ)B với λ∈[0,1] } Định lý Tổ hợp lồ có tính chất bắc cầu. b- Tập hợp lồi Tập con S của Rn được gọi là tập hợp lồi khi S chứa toàn bộ đoạn thẳng nối hai điểmbất kỳ của S. λx + (1-λ)y ∈ S ∀x,y∈,λ∈[0,1] Tập hợp rỗng và tập hợp chỉ có một phần tử được xem là tập hợp lồi. Định lý Giao của một số bất kỳ các tập hợp lồi là một tập hợp lồi. Định lý Nếu S là một tập hợp lồi thì S chứa mọi tổ hợp lồi của một họ điểm bất kỳ trong S. LÝ THUYẾT CƠ BẢN VỀ QUY HOẠCH TUYẾN TÍNH 15 c- Ðiểm cực biên của một tập hợp lồi Ðiểm x trong tập lồi S ⊂ Rn được gọi là điểm cực biên nếu không thể biểu diễn được x dưới dạng tổ hợp lồi thật sự của hai điểm phân biệt của S. x d- Ða diện lồi và tập lồi đa diện Đa diện lồi Tập hợp S tất cả các tổ hợp của các điểm x1, x2,....,xm cho trước được gọi là đa diện lồi sinh ra bởi các điểm đó. Đa diện lồi là một tập hợp lồi. Trong đa diện lồi người ta có thể loại bỏ dần các điểm là tổ hợp của các điểm còn lại. Khi đó người ta thu được một hệ các điểm, giả sử là y1, y2,...,yp (p≤m) . Các điểm này chính là các điểm cực biên của đa diện lồi, chúng sinh ra đa diện lồi đó. Số điểm cực biên của đa diện lồi là hữu hạn. Siêu phẳng - Nửa không gian A=[aij]m.n là ma trận cấp m.n Ai (i=1,2,...,m) là hàng thứ i của A Siêu phẳng trong Rn là tập các điểm x=[x1,x2,.....,xn]T thỏa Ai x = bi Nửa không gian trong Rn là tập các điểm x=[x1,x2,.....,xn]T thỏa Ai x ≥ bi Siêu phẳng và nửa không gian đều là các tập hợp lồi. Tập lồi đa diện Giao của một số hữu hạn các nửa không gian trong Rn được gọi là tập lồi đa diện. LÝ THUYẾT CƠ BẢN VỀ QUY HOẠCH TUYẾN TÍNH 16 ] Tập lồi đa diện là một tập hợp lồi. Nếu tập lồi đa diện không rỗng và giới nội thì đó là một đa diện lồi 2- Đặc điểm của tập hợp các phương án Ðịnh lý Tập hợp các phương án của một quy hoạch tuyến tính là một tập lồi đa diện. Nếu tập hợp lồi đa diện này không rỗng và giới nội thì đó là một đa diện lồi, số điểm cực biên của nó là hữu hạn. Ðịnh lý Tập hợp các phương án tối ưu của một quy hoạch tuyến tính là một tập lồi. Xét quy hoạch tuyến tính chính tắc ⎪⎩ ⎪⎨ ⎧ ≥ = = (III) 0x (II) bAx (I) xc)x(z min/max T Giả sử A=[aij]m.n có cấp m.n, m ≤ n, rang(A)=m . Gọi Aj (j=1,2,...,n) cột thứ j của ma trận A, quy hoạch tuyến tính chính tắc trên có thể viết : ⎩⎨ ⎧ ≥ =+++ +++= 0x bAx...AxAx xc...xcxcz(x) maxmin/ n n 2 2 1 1 nn2211 Gọi S={x=[x1,x2,...,xn]T ≥ 0 / x1A1+ x2A2+...+ xnAn=b} là tập các phương án của bài toán. [ ∈ S là một phương án khác 0. T0n02010 x,...,x,xx = Định lý Điều kiện cần và đủ để x0 là phương án cực biên ( điểm cực biên của S) là các cột Aj ứng với >0 là độc lập tuyến tính. 0jx Hệ quả Số phương án cực biên của một quy hoạch tuyến tính chính tắc là hữu hạn. Số thành phần > 0 của một phương án cực biên tối đa là bằng m. Khi số thành phần > 0 của một phương án cực biên bằng đúng m thì phương án đó được gọi là một phương án cơ sở. LÝ THUYẾT CƠ BẢN VỀ QUY HOẠCH TUYẾN TÍNH 17 Định lý Nếu tập các phương án của một quy hoạch tuyến tính chính tắc không rỗng thì quy hoạch tuyến tính đó có ít nhất một phương án cực biên. Bổ đề Nếu x là một phương án tối ưu của quy hoạch tuyến tính. x1, x2 là các phương án của quy hoạch tuyến tính. x là tổ hợp lồi thực sự của x1, x2 thì x1, x2 cũng là phương án tối ưu của quy hoạch tuyến tính. Định lý Nếu quy hoạch tuyến tính chính tắc có phương án tối ưu thì thì sẽ có ít nhất một phương án cực biên là phương án tối ưu. Ví dụ : xét quy hoạch tuyến tính chính tắc 0x,x,x 1x3x 5xx2x4 x32xz(x) max 321 21 321 21 ≥ ⎩⎨ ⎧ =+ =++ += Với hệ A1 A2 ta tính được T 1 0 10 1 3 13 x ⎥⎦ ⎤⎢⎣ ⎡ −= Với hệ A1 A3 ta tính được [ ]T2 101x = Với hệ A2 A3 ta tính được T 3 3 13 3 1 0x ⎥⎦ ⎤⎢⎣ ⎡= Vì các thành phần của phương án cực biên là > 0 nên ta chi xét x2 và x3 . Khi đó : z(x2)=2.1+3.0=2 z(x3)=2.0+3.1/3=1 Vậy [ ]T2 101x = là một phương án tối ưu. Định lý Điều kiện cần và đủ để một quy hoạch tuyến tính có phương án tối ưu là tập các phương án không rỗng và hàm mục tiêu bị chặn. LÝ THUYẾT CƠ BẢN VỀ QUY HOẠCH TUYẾN TÍNH 18 Định lý Nếu tập các phương án của một quy hoạch tuyến tính không rỗng và là một đa diện lồi thì quy hoạch tuyến tính đó sẽ có ít nhất một phương án cực biên là phương án tối ưu. 3- Phương pháp hình học Từ những kết quả trên người ta có cách giải một quy hoạch tuyến tính hai biến bằng phương pháp hình học thông qua ví dụ sau : Ví dụ : xét quy hoạch tuyến tính 0x,x 30x2x5 14x2x 4xx x2x3)x(z max 21 21 21 21 21 ≥ ⎪⎪⎩ ⎪⎪⎨ ⎧ ≤+ ≤+ −≥− += A,B,C,D,O là các điểm cực biên. Giá trị hàm mục tiêu tại đó là : x2 A B C D O x1 z(A)=3.6+2.0=18 z(B)=3.4+2.5=22 z(C)=3.2+2.6=18 z(D)=3.0+2.8=8 z(O)=3.0+2.0=0 Phương án tối ưu của bài toán đạt được tại B : x1=4 và x2=5 IV- MỘT VÍ DỤ MỞ ĐẦU Xét bài toán quy hoạch tuyến tính : LÝ THUYẾT CƠ BẢN VỀ QUY HOẠCH TUYẾN TÍNH 19 0x,x,x 8x2x4x3 11x2xx4 5xx3x2 x3x45x- z(x) min 321 321 321 321 321 ≥ ⎪⎩ ⎪⎨ ⎧ ≤++ ≤++ ≤++ −−= Đưa bài toán về dạng chính tắc bằng cách đưa vào các biến phụ w1, w2, w3 ≥ 0 ( làm cho các ràng buộc bất đẳng thức thành đẳng thức ) . Ta được : 0w,w,w,x,x,x 8wx2x4x3 11wx2xx4 5wxx3x2 x3x45x- z(x) min 321321 3321 2321 1321 321 ≥ ⎪⎩ ⎪⎨ ⎧ =+++ =+++ =+++ −−= Thực hiện việc chuyển vế ta được bài toán ban đầu như sau : 0w,w,w,x,x,x x2x4x38w x2xx411w xx3x25w x3x45x- z(x) min 321321 3213 3212 3211 321 ≥ ⎪⎩ ⎪⎨ ⎧ −−−= −−−= −−−= −−= (I) Một phương án khả thi xuất phát ( chưa là phương án tối ưu ) của bài toán là : x1 = x2 = x3 = 0 w1=5 w2=11 w3 = 8 Giá trị tương ứng của hàm mục tiêu là z(x) = 0 Người ta sẽ cải tiến phương án xuất phát này để được một phương án mới tốt hơn, nó làm cho giá trị của hàm mục tiêu giảm xuống. Người ta làm như sau : Vì hệ số của x1 trong hàm mục tiêu là âm và có giá trị tuyệt đối lớn nhất nên nếu tăng x1 từ bằng 0 lên một giá trị dương ( càng lớn càng tốt ) và đồng thời vẫn giữ x2 và x3 bằng 0 thì giá trị của hàm của hàm mục tiêu sẽ giảm xuống. Khi đó các biến ở vế trái của bài toán (I) sẽ bị thay đổi theo nhưng phải thoả ≥ 0 . Sự thay đổi của chúng không ảnh hưởng đến sự thay đổi của hàm mục tiêu. Thực hiện ý tưởng trên ta được : 0xx 0x38w 0x411w 0x25w 32 13 12 11 == ⎪⎩ ⎪⎨ ⎧ ≥−= ≥−= ≥−= LÝ THUYẾT CƠ BẢN VỀ QUY HOẠCH TUYẾN TÍNH 20 Suy ra : 2 5 x 3 8 x 4 11 x 2 5 x 1 1 1 1 ≤⇒ ⎪⎪ ⎪ ⎩ ⎪⎪ ⎪ ⎨ ⎧ ≤ ≤ ≤ (dòng 1 được chọn) Người ta chọn 2 5 x1 = nên nhận được một phương án tốt hơn được xác định như sau : 2 1 w 1w 2 5 x 0wxx 321 132 === === Giá trị tương ứng của hàm mục tiêu là 2 25 )x(z −= Bước tiếp theo là biến đổi bài toán (I) thành một bài toán tương đương bằng cách từ dòng 1 ( dòng được chọn ) tính x1 theo các biến còn lại và thế giá trị nhận được vào các dòng còn lại, ta được : 0w,w,w,x,x,x x 2 1 x 2 1 w 2 3 2 1 w x5w21w x 2 1 x 2 7 w 2 5 2 25 - z(x) min 321321 3213 212 321 ≥ ⎪⎪⎩ ⎪⎪⎨ ⎧ −++= ++= −−−= −++= 3211 x2 1x 2 3w 2 1 2 5x (II) Thực hiện tương tự như trên, người ta tăng x3 từ bằng 0 lên một giá trị dương cho phép và đồng thời vẫn giữ x2 và w1 bằng 0 thì giá trị của hàm của hàm mục tiêu sẽ giảm xuống. Khi đó các biến ở vế trái của bài toán (II) sẽ bị thay đổi theo nhưng phải thoả ≥ 0 . Ta được : 1 x 1x 5x 0x 2 1 2 1 w 01w 0x 2 1 2 5 x 3 3 3 33 2 31 ≤⇒ ⎩⎨ ⎧ ≤ ≤⇒ ⎪⎪⎩ ⎪⎪⎨ ⎧ ≥−= ≥= ≥−= ( dòng 3 được chọn ) Khi đó người ta chọn x3=1 nên thu được một phương án tốt hơn được xác định như sau : LÝ THUYẾT CƠ BẢN VỀ QUY HOẠCH TUYẾN TÍNH 21 1w 1 x2x 0wwx 231 312 === === Giá trị tương ứng của hàm mục tiêu là z(x)=-13 Bước tiếp theo là biến đổi bài toán (II) thành một bài toán tương đương bằng cách từ dòng 3 ( dòng đựợc chọn ) tính x3 theo các biến còn lại và thế giá trị nhận được vào các dòng còn lại, ta được : 0w,w,w,x,x,x x52w1w wx22w-2x wx3w-13z(x) min 321321 212 3211 321 ≥ ⎪⎩ ⎪⎨ ⎧ −++= ++= +−= +++= 3213 2wx3w1x (III) Đến đây vì không có hệ số nào của hàm mục tiêu là âm nên không thể làm giảm giá trị của hàm mục tiêu theo cách như trên nữa. Phương án thu được ở bước sau cùng chính là phương án tối ưu của bài toán. Đối với bài toán max, thay cho việc làm tăng biến có hệ số âm trong hàm mục tiêu người ta làm tăng biến có hệ số dương cho đến khi các hệ số trong hàm mục tiêu hoàn toàn âm. V- DẤU HIỆU TỐI ƯU 1- Ma trận cơ sở - Phương án cơ sở - Suy biến Xét bài toán quy hoạch tuyến tính chính tắc (P) ⎩⎨ ⎧ ≥ = = 0x bAx xc)x(z min/max T a- Ma trận cơ sở Người ta gọi cơ sở của bài toán quy hoạch tuyến tính chính tắc (P) là mọi ma trận B không suy biến (có ma trận nghịch đảo) mxm trích ra từ m cột của ma trận ràng buộc A. Các cột còn lại được gọi là ma trận ngoài cơ sở, ký hiệu là N . b- Phương án cơ sở - Phương án cơ sở khả thi B là một cơ sở của bài toán (P). Khi đó, bằng cách hoán vị các cột của A người ta có thể luôn luôn đặt A dưới dạng : LÝ THUYẾT CƠ BẢN VỀ QUY HOẠCH TUYẾN TÍNH 22 A = [ B N ] Do đó, người ta cũng phân hoạch x và c như sau : xT = [ xB xN ] cT = [ cB cN ] Một phương án x của bài toán (P) thoả : [ ] bNxBx b x x N B bAx NB N B =+⇔=⎥⎦ ⎤⎢⎣ ⎡⇔= Phương án cơ sở Người ta gọi một phương án cơ sở tương ứng với cơ sở B là một phương án đặc biệt, nhận được bằng cách cho : xN = 0 Khi đó xB được xác định một cách duy nhất bằng cách giải hệ phương trình tuyến tính bằng phương pháp Cramer : BxB = b ⇔ xB = B-1b Phương án cơ sở khả thi Một phương án cơ sở là phương án cơ sở khả thi nếu : xB = B-1b ≥ 0 Cơ sở tương ứng với một phương án khả thi được gọi là cơ sở khả thi . Ví dụ : xét bài toán quy hoạch tuyến tính dạng chính tắc : 1,2,...,6)(j 0 x 28x3xx2x 10xx4x4x3 20xx2x2 xxxxxx)x(z maxmin/ j 4321 6421 541 654321 =≥ ⎪⎪⎩ ⎪⎪⎨ ⎧ =+++ =+−+− =++ ++−+−= Ma trận ràng buộc là ⎥⎥ ⎥⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎣ ⎡ = 0 0 3 1 2 1 1 0 4- 0 4 3- 0 1 2 0 0 2 A x x x x xx 6 54321 Có thể chọn ba cột bất kỳ và kiểm chứng xem đó có thể là cơ sở không. Một cơ sở được chọn và sắp xếp lại là LÝ THUYẾT CƠ BẢN VỀ QUY HOẠCH TUYẾN TÍNH 23 ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ 2 1 3 4 3- 4- 0 2 2 x x x 214 1 0 0 0 1 0 0 0 1 x x x 365 Các cột x5 x6 x3 tạo thành một ma trận cơ sở . Các biến tương ứng được gọi là các biến (trong) cơ sở . Các cột x1 x2 x4 tạo thành một ma trận ngoài cơ sở. Các biến tương ứng được gọi là các biến ngoài cơ sở. Một phương án cơ sở khả thi của bài toán là : x1 x2 x3 x4 x5 x6 0 0 28 0 20 10 c- Suy biến Một phương án cơ sở khả thi được gọi là suy biến nếu xB = B-1b ≥ 0 có những thành phần bằng 0. Sự suy biến là một hiện tượng thường xảy ra trong một số bài toán như bài toán vận tải, dòng dữ liệu, đường đi ngắn nhất....... Đây là hiện tượng khá phức tạp (có nhiều cách giải quyết sẽ được xét sau). Vì vậy trong những phần tiếp theo ta giả sử rằng phương án cơ sở khả thi là không suy biến, tức là xB = B-1b > 0 ( dương thực sự ) . 2- Dấu hiệu tối ưu Theo trên, khi một bài toán quy hoạch tuyến tính có phương án tối ưu thì tồn tại một cơ sở khả thi (tối ưu) B* , tức là phương án cơ sở x* tương ứng với B* là phương án tối ưu. Vấn đề bây giờ là xác định một thủ tục để tìm B*. Chúng ta sẽ thấy rằng thủ tục đó được suy ra một cách trực tiếp từ việc chứng minh dấu hiệu tối ưu sau đây. Ðịnh lý 4 (dấu hiệu tối ưu) Xét bài toán quy hoạch tuyến tính chính tắc ⎩⎨ ⎧ ≥ = = 0x bAx xc)x(zmin/max T Điều kiện cần và đủ để một phương án cơ sở khả thi x có dạng : ⎥⎥⎦ ⎤ ⎢⎢⎣ ⎡ = ≥== − 0x 0bBx x N 1 B LÝ THUYẾT CƠ BẢN VỀ QUY HOẠCH TUYẾN TÍNH 24 của bài toán là phương án tối ưu là : 0 NBccc 1TB T N T N ≤−= − đối với bài toán max 0 NBccc 1TB T N T N ≥−= − đối với bài toán min Với : A = [ B | N ] cT= [ cB | cN ] Người ta thường gọi : cN là chi phí ngoài cơ sở cB là chi phí cơ sở T Nc là chi phí trượt giảm NBc 1TB − là lượng gia giảm chi phí Chứng minh (cho bài toán max) Ðiều kiện đủ Giả sử x* là một phương án cơ sở khả thi với ma trận cơ sở B và thoả 0NBcc 1TB T N ≤−= −TNc thì cần chứng minh x* là phương án tối ưu, nghĩa là chứng minh rằng với mọi phương án bất kỳ của bài toán ta luôn có : z(x) ≤ z(x*) Xét một phương án khả thi x bất kỳ , x thoả : ⎩⎨ ⎧ ≥ = 0x bAx [ ] ⎪⎪⎩ ⎪⎪⎨ ⎧ ≥≥ =⎥⎦ ⎤⎢⎣ ⎡ ⇒ 0x0x b x x NB NB N B B là ma trận cơ sở của phương án cơ sở khả thi x* B có ma trận nghịch đảo là B-1 ⇒ ⎪⎩ ⎪⎨ ⎧ ≥≥ =+ 0 x0x bNxBx NB NB ⇒ ⎪⎩ ⎪⎨ ⎧ ≥≥ ==+ 0 x0x I)B(B bBNxBBxB NB -1-1 N -1 B -1 LÝ THUYẾT CƠ BẢN VỀ QUY HOẠCH TUYẾN TÍNH 25 ⇒ ⎪⎩ ⎪⎨ ⎧ ≥≥ =+ 0 x0x .bBNxBx NB -1 N -1 B ⇒ ⎪⎩ ⎪⎨ ⎧ ≥≥ = 0 x0x NxB-bBx NB N -1-1 B Tính giá trị hàm mục tiêu đối với phương án x ta được : z(x) = cTx = [ ] NTNBTB N BT N T B xcxcx x cc +=⎥⎦ ⎤⎢⎣ ⎡ = ( ) NTNN11TB xcNxBbB c +− −− = N T NN 1T B 1T B xcNxBcbBc +− −− = (1) N 1T B T N 1T B N)xBc-(cbBc −− + Vì x* là phương án cơ sở khả thi tương ứng với ma trận cơ sở B nên ⎪⎩ ⎪⎨ ⎧ = ≥= − 0x 0bBx * N 1* B Tính giá trị hàm mục tiêu đối vơi phương án cơ bản x* ta được : z(x*) = cTx* = [ ] *NTN*BTB* N * BT N T B xcxcx x cc +=⎥⎦ ⎤⎢⎣ ⎡ = ( vì ) (2) bBcxc 1TB * B T B −= 0x*N = Từ (1) và (2) ta có : z(x) ≤ z(x*) vì 0 NBcc 1TBN ≤− − Vậy x* là phương án tối ưu. Ðiều kiện cần Giả sử là phương án tối ưu với ma trận cơ sở B, cần chứng minh rằng : ⎥⎥⎦ ⎤ ⎢⎢⎣ ⎡ = ≥== − 0x 0bBx *x * N 1* B 0 NBccc 1TB T N T N ≤−= − . ( Nc là vectơ có n-m thành phần) Ta sẽ chứng minh điều này bằng phản chứng. LÝ THUYẾT CƠ BẢN VỀ QUY HOẠCH TUYẾN TÍNH 26 Giả sử rằng tồn tại một thành phần cs của Nc mà cs > 0. Dựa vào cs người ta xây dựng một vectơ x như sau : ⎥⎦ ⎤⎢⎣ ⎡ ≥= −== − 0θIx NxBxx x sN N 1* BB Trong đó θ>0 và Is là một vectơ có (n-m) thành phần bằng 0, trừ thành phần thứ s bằng 1 . Vậy (*) ⎥⎦ ⎤⎢⎣ ⎡ −=−= ≥== −−− s 11 s 1* BB sN NBbBINBxx 0x x θIθ θI Do B-1b ≥ 0 nên người ta có thể chọn θ>0 đủ nhỏ để xB > 0 Vậy x được chọn như trên sẽ thoả : x ≥ 0 (3) Ta kiểm chứng x thỏa ràng buộc của bài toán bằng cách tính : Ax = [ ] NB N B NxBx x x NB +=⎥⎦ ⎤⎢⎣ ⎡ = ( ) ss1*B NNBxB θIθI +− − = ( ) ss11 NNBbB B θIθI +− −− = ss 11 NINBBbBB θIθ +− −− = ss NNb θIθI +− = b (4) Từ (3) và (4) cho thấy x là một phương án khả thi của bài toán Bây giờ ta chỉ ra mâu thuẩn bằng so sánh giá trị hàm mục tiêu tại x và x* . Ta có : z(x) = cTx = [ ] NTNBTB N BT N T B xcxcx x cc +=⎥⎦ ⎤⎢⎣ ⎡ = ( ) NTNN1*BTB xcNxBxc +− − = N T NN 1T B * B T B xcNxBcxc +− − = )0xc (vì xcNxBcxcxc *N T NN T NN 1T B * N T N * B T B =+−+ − = [ ] ( ) N1TBTN* N * BT N T B xNBccx x c c −−+⎥⎦ ⎤⎢⎣ ⎡ = ( ) s1TBTN*T θI NBccxc −−+ LÝ THUYẾT CƠ BẢN VỀ QUY HOẠCH TUYẾN TÍNH 27 = s T N *T θIcxc + = θIcxc sTN*T + = z(x*) + θsc > z(x*) ( vì 0c s >θ ) Vậy x* không phải là phương án tối ưu nên mâu thuẩn với giả thiết . Chú ý Qua việc chứng minh định lý dấu hiệu tối ưu ta thấy rằng từ một phương án cơ sở khả thi chưa tối ưu có thể tìm được các phương án khả thi càng lúc càng tốt hơn nhờ lặp lại nhiều lần công thức (*). Vấn đề được đặt là đại lượng θ được chọn như thế nào để nhanh chóng nhận được phương án tối ưu. Bổ đề Xét bài toán quy hoạch tuyến tính chính tắc ⎩⎨ ⎧ ≥ = = 0x bAx xc)x(zmax T với B là một cơ sở khả thi nào đó và x0 là phương án cơ sở tương ứng, tức là và ⎥⎥⎦ ⎤ ⎢⎢⎣ ⎡ = ≥== − 0x 0bBx x 0 N 10 B0 bBc)z(x 1TB 0 −= Xét NBccc 1TB T N T N −−= . Nếu tồn tại một biến ngoài cơ sở xs sao cho sc >0 với sc là thành phần thứ s của Nc thì : a- Hoặc là người ta có thể làm tăng một cách vô hạn giá trị của xs mà không đi ra khỏi tập hợp các phương án khả thi, và trong trường hợp này phương án tối ưu của bài toán không giới nội. b- Hoặc là người ta có thể xác định một cơ sở khả thi khác là có phương án cơ sở khả thi tương ứng với nó là tốt hơn , tức là : ∧ B ∧ x z(x0) < z( ) ∧ x Chứng minh Trong quá trình chứng minh định lý dấu hiệu tối ưu ta có phương án mới được xác định như sau : ⎥⎦ ⎤⎢⎣ ⎡ −=−= ≥== −−− s 11 s 1* BB sN NBbBINBxx 0x x θIθ θI LÝ THUYẾT CƠ BẢN VỀ QUY HOẠCH TUYẾN TÍNH 28 Ký hiệu : NBN 1−= sN là cột s của N bBb 1−= Như vậy ta có : ⎥⎥⎦ ⎤ ⎢⎢⎣ ⎡ θ= θ−== sN sB Ix N bx x Hai trường hợp có thể xảy ra như sau : a- Trường hợp 0Ns ≤ Trong trường hợp này xs có thể nhận một giá trị θ lớn tuỳ mà vẫn đảm bảo xB ≥ 0, nghĩa là x luôn luôn thoả ≥ 0 . Khi đó như đã biết giá trị hàm mục tiêu tương ứng là z(x) = [ ] NTNBTB N BT N T B xcxcx x c c +=⎥⎦ ⎤⎢⎣ ⎡ = ( ) sTNs11TB IθcIθNBbBc +− −− = s T Ns 1T B 1T B IθcIθNBcbBc +− −− = ( ) s1TBTN0 IθNBcc)x(z −−+ = s T N 0 Iθc)x(z + = z(x0) + θcs với θcs có thể lớn vô hạn thì giá trị của hàm mục tiêu là không giới nội. b- Trường hợp tồn tại i=1→m sao cho 0Nis > ( 0Nis > là thành phần thứ i của sN ) Trong trường hợp này giá trị của θ>0 mà xs có thể nhận không thể tăng vô hạn vì phải đảm bảo xB>0. Giá trị lớn nhất của θ mà x ∧ θ s có thể nhận được xác định như sau : m)1i( N b 0N , N b min rs r is is i →=∀ = ⎭⎬ ⎫ ⎩⎨ ⎧ >=θ∧ Phương án cơ sở khả thi mới có các thành phần như sau : ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢ ⎣ ⎡ = −== ∧∧ ∧∧ ∧ sN sB Iθx N θbx x LÝ THUYẾT CƠ BẢN VỀ QUY HOẠCH TUYẾN TÍNH 29 và giá trị hàm mục tiêu tương ứng là : )x(zcθ)x(z)x(z 0s0 >+= ∧∧ Ghi chú : Trong trường hợp bài toán không suy biến, nếu được xác định một cách duy nhất thì phương án mới có đúng m thành phần khác 0. Thật vậy : ∧ θ ∧ x - Biến xs đang bằng 0 trong phương án x0 trở thành dương thật sự vì θˆx s = - Biến xr đang dương thật sự bây giờ nhận giá trị : 0bbN N b bNθbx rrrs rs r rrsrr =−=−=−= ∧∧ Vậy phương án mới là một phương án cơ sở. Nó tương ứng với cơ sở ở được suy ra từ B bằng cách thay thế cột r bằng cột s. ∧ x ∧ B Người ta nói rằng hai cơ sở B và là kề nhau, chung tương ứng với những điểm cực biên kề nhau trong tập hợp lồi S các phương án khả thi của bài toán. ∧ B CÂU HỎI CHƯƠNG 1 1- Trình bày các bước nghiên cứu một quy hoạch tuyến tính. 2- Định nghĩa quy hoạch tuyến tính chính tắc. 3- Trình bày khái niệm về phương án của một quy hoạch tuyến tính. 4- Trình bày cơ sở lý thuyết của phương pháp hình học giải một quy hoạch tuyến tính hai biến. LÝ THUYẾT CƠ BẢN VỀ QUY HOẠCH TUYẾN TÍNH 30 BÀI TẬP CHƯƠNG 1 xuất hai loại sản phẩm : thép tấm và thép cuộn. bao nhiêu trong - Có 3 người cùng phải đi một quảng đường dài 10km mà chỉ có một chiếc xe đạp hời gian người cuối cùng đến đích là ngắn nhất. - Một nhà máy sản xuất ba loại thịt : bò, lợn và cừu với lượng sản xuất mỗi ngày là 1- Một nhà máy cán thép có thể sản Nếu chỉ sản xuất một loại sản phẩm thì nhà máy chỉ có thể sản xuất 200 tấn thép tấm hoặc 140 tấn thép cuộn trong một giờ . Lợi nhuận thu được khi bán một tấn thép tấm là 25USD, một tấn thép cuộn là 30USD. Nhà máy làm việc 40 giờ trong một tuần và thị trường tiêu thụ tối đa là 6000 tấn thép tấm và 4000 tấn thép cuộn . Vấn đề đặt ra là nhà máy cần sản xuất mỗi loại sản phẩm là một tuần để đạt lợi nhuận cao nhất. Hãy trình bày bài toán quy hoạch tuyến tính cho vấn đề trên. 2 một chổ ngồi. Tốc độ đi bộ của người thứ nhất là 4km/h, người thứ hai là 2km/h, người thứ ba là 2km/h. Tốc độ đi xe đạp của người thứ nhất là 16km/h, người thứ hai là 12km/h, người thứ ba là 12km/h. Vấn đề đặt ra là làm sao để t Hãy trình bày bài toán quy hoạch tuyến tính cho vấn đề trên. 3 480 tấn thịt bò, 400 tấn thịt lợn, 230 tấn thịt cừu. Mỗi loại đều có thể bán được ở dạng tươi hoặc nấu chín. Tổng lượng các loại thịt có thể nấu chín để bán là 420 tấn trong LÝ THUYẾT CƠ BẢN VỀ QUY HOẠCH TUYẾN TÍNH 31 Nấu chín trong giờ Nấu chín ngoài giờ giờ và 250 tấn ngoài giờ. Lợi nhuận thu được từ việc bán một tấn mỗi loại thịt được cho trong bảng sau đây : Tươi Bò 8 14 11 Lợn 4 12 7 Cừu 4 13 9 h bày bài toán quy hoạch tuyến tính để nhà máy sản xuất đạt lợi nhuận cao nhấ Một xưởng mộc làm bàn và ghế. Một công nhân làm xong một cái bàn phải mất 2 - Một nhà máy sản xuất hai kiểu mũ. Thời gian để làm ra một cái mũ kiểu thứ nhất - Trong hai tuần một con gà mái đẻ được 12 trứng hoặc ấp được 4 trứng nở ra gà - Giải những bài toán quy hoạch tuyến tính sau đây bằng phương pháp hình học : Hãy trìn t. 4- giờ, một cái ghế phải mất 30 phút. Khách hàng thường mua nhiều nhất là 4 ghế kèm theo 1 bàn do đó tỷ lệ sản xuất giữa ghế và bàn nhiều nhất là 4:1. Giá bán một cái bàn là 135USD, một cái ghế là 50USD. Hãy trình bày bài toán quy hoạch tuyến tính để xưởng mộc sản xuất đạt doanh thu cao nhất, biết rằng xưởng có 4 công nhân đều làm việc 8 giờ mỗi ngày. 5 nhiều gấp 2 lần thời gian làm ra một cái kiểu thứ hai. Nếu sản xuất toàn kiểu mũ thứ hai thì nhà máy làm được 500 cái mỗi ngày. Hàng ngày, thị trường tiêu thụ nhiều nhất là 150 cái mũ kiểu thứ nhất và 200 cái kiểu thứ hai. Tiền lãi khi bán một cái mũ kiểu thứ nhất là 8USD, một cái mũ thứ hai là 5USD. Hãy trình bày bài toán quy hoạch tuyến tính để nhà máy sản xuất đạt lợi nhuận cao nhất. 6 con. Sau 8 tuần thì bán tất cả gà con và trứng với giá 0,6USD một gà và 0,1USD một trứng. Hãy trình bày bài toán quy hoạch tuyến tính bố trí 100 gà mái đẻ trứng hoặc ấp trứng sao cho doanh thu là nhiều nhất. 7 LÝ THUYẾT CƠ BẢN VỀ QUY HOẠCH TUYẾN TÍNH 32 a)- b)- ⎪⎪ ⎪⎪ ⎩ ⎪⎪ ⎪⎪ ⎨ ⎧ ≤ ≤ ≤− ≥+ ≥+ −= 5x 5x 1xx 4x2x 3xx3 xxz max 2 1 21 21 21 21 ⎪⎪⎩ ⎪⎪⎨ ⎧ ≤ ≤+− ≤− ≤−− +−= 0x,x 1xx 4x2x 6x2x xxw min 21 21 21 21 21 c)- d)- ⎪⎩ ⎪⎨ ⎧ ≥+− ≥− += tuy ý xx 21, 2x3x2 2x2x x65xz max 21 21 21 ⎪⎪⎩ ⎪⎪⎨ ⎧ ≥ ≥− ≤+ −= 0x,x 3xx 6x2x x-2xw min 21 21 21 21 e)- f)- ⎪⎪⎩ ⎪⎪⎨ ⎧ ≥ ≥+ ≤+ += 0x,x 1x43x 2x2x x23xz max 21 21 21 21 ⎪⎪ ⎪ ⎩ ⎪⎪ ⎪ ⎨ ⎧ ≥ ≤ ≤ ≤+ −≥− −= 0x,x 6x 6x 14xx2 4xx x43xz max 21 1 2 21 21 21 g)- 0x,x 4x2x 9x4x 14x3x 24x32x 12x32x x3x4z(x) maxmin/ 21 21 21 21 21 21 21 ≥ ⎪⎪ ⎪ ⎩ ⎪⎪ ⎪ ⎨ ⎧ ≥+ ≥+ ≤− ≤+ −≥− += Cơ Sở Tự Động Học Phạm Văn Tấn Chương II Hàm Chuyển Sơ Đồ Khối Của Hệ Thống Trang II.1 Chương II: HÀM CHUYỂN VÀ SƠ ĐỒ KHỐI CỦA HỆ THỐNG • ĐẠI CƯƠNG. • ĐÁP ỨNG XUNG LỰC VÀ HÀM CHUYỂN. • SƠ ĐỒ KHỐI (BLOCK DIAGRAM). I.ĐẠI CƯƠNG Bước quan trọng thứ nhất trong việc thiết kế một hệ điều khiển là việc miêu tả toán học và mô hình hóa (modeling) cho thiết bị được kiểm soát. Một cách tổng quát, những đặc tính động của thiết bị này sẽ được xác định trước bằng một tập hợp các biến. Thí dụ, xem một động cơ điện trong hệ thống điều khiển. Ta phải xác định điện áp đặt vào, dòng điện trong cuộn dây quấn, moment được khai triển trên trục, góc dời và vận tốc của rotor, và những thông số khác nữa nếu cần thiết .Tất cả những thông số ấy được xem như các biến của hệ. Chúng liên hệ nhau thông qua những định luật vật lý được thiết lập và đưa đến các phương trình toán học dưới nhiều dạng khác nhau. Tùy bản chất của thiết bị, cũng như điều kiện hoạt động của hệ, một vài hoặc tất cả các phương trình ấy là tuyến tính hay không, thay đổi theo thời gian hay không, chúng cũng có thể là các phương trình đại số, phương trình vi phân hoặ