Bài giảng quy hoạch tuyến tính

      109

Mọi việc quy hoạch tuyến tính đều có thể quy về vấn đề dạng quy tắc tương đương theo nghĩa trị tối ưu của hàm kim chỉ nam trong hai câu hỏi là trùng nhau và từ phương án tối ưu của việc này nhưng suy ra phương án về tối ưu của vấn đề kia ..


Bạn đang xem: Bài giảng quy hoạch tuyến tính

*

Xem thêm: Tranh Thêu Chữ Thập Hoa Mẫu Đơn 9 Bông, Tranh Đính Đá Hoa Mẫu Đơn

Nội dung Text: bài giảng quy hoạch tuyến đường tính - Chương 1: việc quy hoạch tuyến đường tính - ĐH kinh tế tài chính Kỹ Thuật Công Nghệ
Trường Đại học tài chính kỹ thuật công nghiệp bộ môn công nghệ cơ phiên bản BÀI GIẢNG QUY HOẠCH TUYẾN TÍNHChương 1: việc quy hoạch con đường tínhTRƯỜNG ĐẠI HỌC ghê TẾ KỸ THUẬT CÔNG NGHIỆP BỘ MÔN KHOA HỌC CƠ BẢN BÀI GIẢNGQUY HOẠCH TUYẾN TÍNHChương I: BÀI TOÁN QUY HOẠCH TUYẾNTÍNHChương II: BÀI TOÁN VẬN TẢIChương III: MÔ HÌNH SƠ ĐỒ MẠNG LƯỚICHƯƠNG I: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH1.1. Bài toán quy hoạch con đường tính tổng quát1.2. Việc dạng chủ yếu tắc1.3. Việc dạng chuẩn1.4. Các tính chất chung1.5. Cách thức đơn hình1.6. Phương thức đơn hình đối ngẫu1.1. Câu hỏi quy hoạch con đường tính tổng thể n f ( x ) = ∑ c j x j → min (max) j=1 n ∑ a ij x j = b i ( i ∈ I1 )  j=1 n  a x ≥ ( ≤) b ( i ∈ I ) ∑ ij j i 2  j=1 Hàm f(x) gọi là hàm phương châm Mỗi phương trình hoặc bất phương trình vào hệ điều kiện gọi là một trong những ràng buộc. ■ một vài khái niệm : Phương án: Vectơ x = (x1, x2,..., xn) thoả mãn gần như điều Phkiện ràng buộc của vấn đề gọi là 1 trong những phương án. N ∑a x = b i thì ràng buộc i gọi là “chặt” so với -Nếu ij j j=1phương án x, hoặc giải pháp x nhất trí chặt ràng buộc i. N -Nếu ∑ a ij x j > ( 1.2. Bài toán dạng bao gồm tắc: n f ( x ) = ∑ c j x j → min (max) j=1 n ∑ a ij x j = b i (i = 1, m)  j=1  x ≥ 0 (j = 1, n ) j  Mọi bài toán quy hoạch con đường tính đều rất có thể quy về bàitoán dạng thiết yếu tắc tương tự theo nghĩa trị về tối ưu củahàm mục tiêu trong hai việc là trùng nhau và từ phươngán buổi tối ưu của câu hỏi này suy ra phương án tối ưu của bàitoán cơ ●Cách đưa câu hỏi về dạng thiết yếu tắc -Nếu xj ≤ 0 thì đổi trở thành xj’= −xj ≥ 0. N ∑a x ≤ bi -Nếu một nràng buộc gồm dạng thì có thể ij jthay bằng ∑ j=1 a ij x j + x = b i cùng với x ip ≥ 0 và thông số của p i j=1 px x ip i n ∑ ọi những biến a ij x jg≥ iblà trở thành phụ. Vào f(x) bởi 0. N j=1 ∑ -Nếu mộa ij x j − x = tất cả dạng x ip ≥ 0 p. Bi buiộc t ràng thì cố gắng j=1bằng , -Nếu xj không có ràng buộc vết thì để xj = xj’− xj’’,Ví dụ: Đưa việc sau về dạng chủ yếu tắc:f(x) = –2x1 + x2 + 3x3 + 5x4 ⇒ min x1 – 3x2 + 5x3 – x4 ≤ 16   2x1 – x2 – 2x3 + 2x4 ≥ – 4    4x1 + 3x2 + x3 + x4 = 9   x1, x2 ≥ 0, x3 ≤ 0  Các trở nên phụ sẽ tiến hành đánh số tiếp là x5, x6.Đặt x3’= – x3 ≥ 0, x4 = x4’ – x4’’, x4’, x4’’ ≥ 0.Ta được việc chính tắc tương tự sau:f(x) = –2x1 + x2 – 3x3’ + 5x4’ – 5x4’’ ⇒ min x – 3x2 – 5x3’ – x4’ + x4’’ + x5 = 16 12x – x2 + 2x3’ + 2x4’ – 2x4’’ – x6 = –414x + 3x2 – x3’ + x4’ – x4’’ =91 x1, x2 , x3’, x4’, x4’’, x5, x6 ≥01.3. Câu hỏi dạng chuẩn nf ( x ) = ∑ c j x j → min (max) j=1x1 + a 1m +1x m +1 + a 1m + 2 x m + 2 + ...... + a 1n x n = b1x 2 + a 2m +1x m +1 + a 2m + 2 x m + 2 + ...... + a 2n x n = b 2......................................................................x + a milimet +1 x m +1 + a milimet + 2 x m + 2 + ...... + a mn x n = b m m x j ≥ 0 (j = 1, n ) trong đó: b i ≥ 0, (i = 1, m) vấn đề dạng chuẩn là việc dạng thiết yếu tắc có vếphải ko âm cùng mỗi phương trình đều sở hữu một biến chuyển sốvới thông số bằng 1 đồng thời không tồn tại trong những phươngtrình không giống (gọi là phát triển thành cô lập với thông số bằng 1). Từ hệ phương trình buộc ràng của bài xích toán dễ dàng suyra một phương án đầu tiên: x0 = (b1, b2, …,bm, 0, 0,…, 0),với đại lý là A1, A2,…Am = E, kia là cách thực hiện cực biên. 1.4. Các tính chất chung1. đặc thù 1: Sự tồn tại phương án cực biên: Nếu câu hỏi có phương pháp và hạng của ma trận hệ ràng buộc bằng n thì việc có phương án cực biên. Hạng của ma trận hệ buộc ràng của vấn đề dạng chủ yếu tắc luôn luôn bằng n cần nếu bài toán chính tắc có phương án thì phải có phương án cực biên. 2. đặc điểm 2: Sự mãi mãi phương án tối ưu: Nếu vấn đề có phương pháp và trị số hàm mục tiêu bị ngăn trên tập cách thực hiện thì câu hỏi có phương án về tối ưu. 3. đặc thù 3: Tính hữu hạn của số phương pháp cực biên: Số phương án cực biên của mọi bài toán quy hoạch1.5. Phương thức đơn hình 1. Nội dung của phương pháp: khởi nguồn từ một phương án cực biên đầu tiên, tìm cáchđánh giá phương án cực biên ấy, nếu nó vẫn chưa tối ưu thìtìm cách chuyển quý phái một phương pháp cực biên bắt đầu tốthơn, quy trình được tái diễn vì số phương pháp cực biên làhữu hạn buộc phải sau một trong những hữu hạn cách hoặc đã kết luậnbài toán không giải được vày hàm mục tiêu không xẩy ra chặnhoặc sẽ tìm được phương án tối ưu. Cách thức này chỉ vận dụng được cho những bài xích toáncó phương án cực biên, mặc dù mọi việc QHTTTđều rất có thể đưa về vấn đề dạng chính tắc, với khi nó đang cóphương án thì sẽ có phương án rất biên. Cho nên vì thế không có tác dụng mất tính chất tổng quát lác từ phía trên ta sẽchỉ xét bài toán dạng bao gồm tắc. 2. Các đại lý của phương án cực biên: Định nghĩa: Một hệ vectơ Aj tự do tuyến tính baohàm hệ thống các vectơ tương xứng với các thành phầndương của giải pháp cực biên x gọi là cơ sở của phươngán rất biên ấy ký hiệu: J, trong đó: J = j, Aj phía trong cơ sở. Một cách thực hiện cực biên ko suy biến gồm đúng m thànhphần dương, có một cơ sở duy nhất, đó chính là các vectơtương ứng với các thành phần dương, còn giải pháp cựcbiên suy biến thì có không ít cơ sở không giống nhau, phần tầm thường củachúng là những vectơ tương xứng với các thành phần dương.3. Thuật toán của phương thức đơn hình trả sử vẫn biết giải pháp cực biên x0, cơ sở J0. Lập bảng 1-1 hình tương ứng:Hệ Cơ Phươn c1 c2 … cr … centimet cm+1 … ông chồng … cs … cnsố sở gán: xJ x x … x … x x … x … x … x 1 2 r m m+1 k s ncJ Jc1 x1 x10 1 0 … 0 …0 x1,m+1… x1k … x1s… x1nc2 x2 x20 0 1 … 0 …0 x2,m+1… x2k … x2s … x2n… … … …………………………………………….cr xr xr0 0 0 … 1 … 0 xr,m+1… xrk … xrs … xrn …………………………………………………….… … … 0 0…0…1 xm,m+1…xmk …xms ... Xmncm xm xm0 f(x) f(x0) 0 0…0…0 ∆m+1 … ∆k … ∆s … ∆nBước 1: Kiểm tra tín hiệu tối ưu: ∑c xTính những ước lượng ∆k theo công thức: Δ = − chồng k j jk j∈J -Nếu ∆k ≤ 0, (∀k ∉ J0) thì x0 là phương án buổi tối ưu. -Nếu ∆k > 0 thì x0 chưa phải là phương án buổi tối ưu,chuyển sang bước 2.Bước 2: bình chọn tính không giải được của bài bác toán: -Nếu mãi sau một ∆k > 0 mà xjk ≤ 0 (∀j ∈ J0) thì bài toán không có phương án tối ưu. -Nếu với từng ∆k > 0 đều sở hữu ít tuyệt nhất một xjk > 0 thì đưa sang bước 3.Bước 3: chọn vectơ đưa vào cơ sở và khẳng định vectơloại ngoài cơ sở: -Giả sử max ∆ k = ∆ s , vectơ As được chuyển vào cơ sở, ∆ k >0 x0 j tính θ 0 = min x js j∈J 0 , x js > 0 x0 ( r ∈ J 0 , x rs > 0) -Giả sử θ 0 = r x rs Vectơ Ar bị loại khỏi cơ sở bộ phận xrs gọi là thành phần xoay của phép biến đổi đổi. Lập bảng 1-1 hình mới, vậy xs vào địa điểm xr, cùng cs vào địa chỉ cr. đưa sang cách 4.tổng quát lác cho tổng thể bảng (bao gồm cả hàng mong lượng∆ k). -Để tính sản phẩm vectơ gửi vào (xs) trong bảng new talấy hàng vectơ một số loại ra (xr) vào bảng cũ chia cho chỗ tửxoay. -Để tính sản phẩm xj trong bảng mới, ta đem hàng xj trongbảng cũ trừ đi sản phẩm xs vừa mới tính được sau khi nhân nóvới xjs. Hiệu quả của quá trình chuyển đổi sẽ mang đến ta bảng solo hìnhứng với phương án cực biên mới x1, xuất sắc hơn x0. Đối cùng với x1 trở lại bước 1 và quá trình lặp lại saumột số hữu hạn cách sẽ kiếm được phương án rất biên tốiưu hoặc kết luận bài toán ko giải được vày hàm mục tiêukhông bị chặn.Ví dụ 1: Giải việc sau bằng phương pháp đơn hình: f(x) = 2x1 + 3x2 – x3 – 1/2x4 ⇒ min x – x2 + x3 + 1/2x4 = 18 1  x2 – 4x3 + 8x4 ≤ 8    –2x2 + 2x3 – 3x4 ≤ 20   xj ≥ 0 (j =1…4)  