Bài giảng quy hoạch tuyến tính - Chương 1: Bài toán quy hoạch tuyến tính - ĐH Kinh tế Kỹ Thuật Công Nghệ

Mọi bài toán quy hoạch tuyến tính đều có thể quy về bài toán dạng quy tắc tương đương theo nghĩa trị tối ưu của hàm mục tiêu trong hai bài toán là trùng nhau và từ phương án tối ưu của bài toán này mà suy ra phương án tối ưu của bài toán kia ..
Nội dung trích xuất từ tài liệu:
Bài giảng quy hoạch tuyến tính - Chương 1: Bài toán quy hoạch tuyến tính - ĐH Kinh tế Kỹ Thuật Công NghệTrường Đại học kinh tế kỹ thuật công nghiệp Bộ môn khoa học cơ bản BÀI GIẢNG QUY HOẠCH TUYẾN TÍNHChương 1: Bài toán quy hoạch tuyến tínhTRƯỜNG ĐẠI HỌC KINH 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 tuyến tính tổng quát1.2. Bài toán dạng chính tắc1.3. Bài toán dạng chuẩn1.4. Các tính chất chung1.5. Phương pháp đơn hình1.6. Phương pháp đơn hình đối ngẫu1.1. Bài toán quy hoạch tuyến tính tổng quát 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 mục tiêu Mỗi phương trình hoặc bất phương trình trong hệ điều kiện gọi là một ràng buộc. ■ Một số khái niệm : Phương án: Vectơ x = (x1, x2,..., xn) thoả mãn mọi điều Phkiện ràng buộc của bài toán gọi là một phương án. n ∑a x = b i thì ràng buộc i gọi là “chặt” đối với -Nếu ij j j=1phương án x, hoặc phương án x thoả mãn chặt ràng buộc i. n -Nếu ∑ a ij x j > ( 1.2. Bài toán dạng chính 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 tuyến tính đều có thể quy về bàitoán dạng chính tắc tương đương theo nghĩa trị tối ưu củahàm mục tiêu trong hai bài toán là trùng nhau và từ phươngán tối ưu của bài toán này suy ra phương án tối ưu của bàitoán kia ●Cách đưa bài toán về dạng chính tắc -Nếu xj ≤ 0 thì đổi biến xj’= −xj ≥ 0. n ∑a x ≤ bi -Nếu một nràng buộc có dạng thì có thể ij jthay bằng ∑ j=1 a ij x j + x = b i với x ip ≥ 0 và hệ số của p i j=1 px x ip i n ∑ ọi Các biến a ij x jg≥ iblà biến phụ. trong f(x) bằng 0. n j=1 ∑ -Nếu mộa ij x j − x = có dạng x ip ≥ 0 p bi buiộc t ràng thì thay j=1bằng , -Nếu xj không có ràng buộc dấu thì đặt xj = xj’− xj’’,Ví dụ: Đưa bài toán sau về dạng chính 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 biến phụ sẽ được đánh số tiếp là x5, x6.Đặt x3’= – x3 ≥ 0, x4 = x4’ – x4’’, x4’, x4’’ ≥ 0.Ta được bài toán chính tắc tương đương 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. Bài toán 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 mm +1 x m +1 + a mm + 2 x m + 2 + ...... + a mn x n = b m m x j ≥ 0 (j = 1, n ) Trong đó: b i ≥ 0, (i = 1, m) Bài toán dạng chuẩn là bài toán dạng chính tắc có vếphải không âm và mỗi phương trình đều có một biến sốvới hệ số bằng 1 đồng thời không có trong các phươngtrình khác (gọi là biến cô lập với hệ số bằng 1). Từ hệ phương trình ràng buộc của bài toán dễ dàng suyra một phương án đầu tiên: x0 = (b1, b2, …,bm, 0, 0,…, 0),với cơ sở là {A1, A2,…Am} = E, đó là phương án cực biên. 1.4. Các tính chất chung1. Tính chất 1: Sự tồn tại phương án cực biên: Nếu bài toán có phương án và hạng của ma trận hệ ràng buộc bằng n thì bài toán có phương án cực biên. Hạng của ma trận hệ ràng buộc của bài toán dạn ...