CHƯƠNG I: MOT SO KIÊN THỨC CHUAN BỊ 1. Bài toán quy hoạch tuyến tính (QHTT): 1. Giới thiệu: Bai toán QHTT dang tông quát: (mm) x) => min(max) Ax>h Bai toán QHTT dạng chính tắc: Íc,x) > min (7TT,)4 Ax=b x20 Bai toán QHTT dang chuẩn tắc: (c. x) > min (TT,)4 Ax>b x20 trong ca 3 bài toản trên: Ae M_(R),beER" ceR" xe R” 2.
Điều kiện dé bài toán QHTT có phương án tối ưu: Xét bải toán QHTT dạng chuân tắc: Ƒ{z)= Íc. Định lý 1: Nếu M #@ và Mbj chặn thì (77) có phương án tối ưu. Định lý 2: Giả sử M +Ø. Khi 46 (T7) có phương 4n tối ưu khi và chỉ khi hàm mục tiêu ƒ bị chặn dudi trong M.
Giải bài toán quy hoạch tuyến tính: 1. Thuật toán đơn hình gốc: - Xét bai toán bài toán QHTT dang chính tắc: (c.x)— min (TTHAx=h xa0 thỏa các điều kiện sau: (¡) men (/) rankA =m (iii) Tên tại ma trận B được lập thành từ các cột củaA sao cho: » B là ma trận vuông cấp m, khá nghịch. - Đề giái (77) ta dùng thuật toan don hình góc sau: 6 Bước &=U: © Tim ma trận vuông B=[A" A*. A] cấp m khả nghịch thỏa x, = B'b20 {A® là cột thứ / cua ma trận A} e Tính BA.
® Lập bang đơn hình ứng với ma trận Ø như sau: CTpa |ES =a - | | fs | 1 J, 6y A, =2 -e€,„j=l,n - Kiểm tra điều kiện tối ưu: * Néu A, <S0./= I,n thi phương an x" có: (x) bel ;, |Oje) là phương án tối ưu của (77). Thuật toán kết thúc. Osy, San “Nếu tồn tại j, thỏa {A >0 u, S0, =l,m thi ta kết luận (77) không cỏ phương an tôi ưu. Thuật toán két thúc.
10 Nếu ngược lại thi: Xác định j, thỏa A, =max{A | ¿ tia 2kin| sh s30) " tale ` trong đó các dữ kiện trong bảng đơn hình trên được xác định thông qua bảng don hình ở bước k —! như sau: = A Với j =Ï„m thi A, =A,--“—* My cà, khi i= i, u + Với i=i,m thì x, =(x,)=} `” i #i, kh i kh i =i i, Với ¡ =1,m, j =l.n thi u, =4 *” i #i, kh i e Kiểm tra điều kiện tôi ưu như ở bước 0. Thuật toán đơn hình đối ngẫu: Xét bai toán quy hoạch tuyến tính dạng chính tắc: (c.x) > min (TT)4 Ax=b x20 trong đó rankA =m 2.1 Cơ sở ứng với ma trận: Định nghĩa: Ta gọi một cơ sở ứng với ma trận 4 là một bộ gom m vectơ cột của A độc lập tuyến tinh Ø = | 4°.1 Cơ sử chấp nhận được đối ngẫu: Xét bai toản đối ngẫu cua (77): mtr b, A4 véc Định nghĩa 1: Ta gọi phương án cơ sở đôi ngẫu tương ứng với cơ sở 8= 4*,4”,.4'^} là vecto y thu được bảng cách giải hệ phương trình B’y=c,, trong đó Cy =(c,,¢, — ). Định nghĩa 2: Cơ sở 8 được gọi là cơ sở chấp nhận được đối ngẫu nếu phương án cơ sở đối ngẫu tương ứng với nó là phương án chấp nhận được của bài toán đối ngẫu (77). Nhận xét: Nếu B là cơ sở chấp nhận được đối ngẫu thì y=(B")'c, thỏa 4” y<e hay: A’ ((a")'c,)se ©((#)*«} (#'} se’ c©cj(B'4l<e” (*) Ta nhận thấy (*) chính là tiêu chuẩn tối ưu trong thuật toán đơn hình gốc.2 Thuật toán đơn hình doi ngẫu khí biết cơ sở chấp nhận được đối ngẫu: > Bước 1: - Gia sư ta tìm được cơ sở chấp nhận được đối ngẫu 8= |A".A“}\ tức tìm được ma trận B lập từ các cột của ma trận A sao cho c” —c; (BA) >0).
- Lập bảng đơn hình chấp nhận được đối ngẫu ứng với cơ sở B như bảng đơn hình của thuật toán đơn hình góc. trong đó: x, =B8'b =ưn: es h DỆ =(B A), 41 =l.J = ln ant > Bước 2: - Nếu x, >0 thi phương án x’ có J „ I là phương án tối wu của (77). Thuật toán kết thúc. l<,;<m - Nếu tồn tại í thỏa {(x,) <0 thi ta kết luận (77) không có phương án u20 Jj= Ln chấp nhận được.
Thuật toán kết thúc. Ngược lại, thì: + Xác định i, thỏa (x,), = min{(x,), :£ =1,mÌ và j, thỏa cà =min| sn, <i. A A Mian My, + Thực hiện phép biến đổi đơn hình với phan tử xoay w,„ rồi quay lại bước 2 3. Kỹ thuật tái tối ưu hóa: + Van đề đặt ra: Cho bài toán quy hoạch tuyến tỉnh: 13 dex, => min yet (77) ¥a,x, =b ,i=l.m ov x,20j=hn Gia sử giải (77) bằng thuật toán đơn hình gốc hoặc thuật toán don hình đối ngẫu ta thu được phương án tối ưu x` với cơ sở tôi ưu 8.
Xét bài toán (Ø) là bai toán (77) có bổ sung thêm rang buộc Š`a,.: CLee | dex, => min pm x 3, $4.4 x,>0,/ =l,n Ta nhận thấy, nêu x” thỏa rang buộc thứ (m+1) thì x" là phương án tối ưu của (@). Vấn đề đặt ra: Nếu x’ không thỏa ràng buộc thứ (m+1) thì có thể tận dụng những thông tin đã có (phương án ti ưu x” và cơ sở tối ưu B) để giải bài toán có bổ sung ràng buộc (@) hay không? + Giải quyết vấn đề: Không mắt tính tong quát giả sử giải (77) ta thu được phương án tối ưu x` và cơ sở tương ứng 8= {4',4',., 4”} và bảng đơn hình ứng với z' là: L$ | |5 | = | Thuật toán kết thúc Bài toán (77) được viết lại như sau: 14 Khi đó thêm biến phụ x,,, >0 vào bai toán (Q) ta được bài toán sau: a b3 3 => min mm x, + ` ux, =(xX;), vi =lm DI 3a./=ln+l Với i=i,m ta nhân dòng thứ ¿ với (-a,,,,) rồi cộng vào dong thứ (œ + 1) thì (Q) có dạng sau: LẠ 3›c,x, > min yl x + b3) u,x, =(x,), ,Í=lm (Q)) š(s. Sti (xạ), il tl x,20,/=lLn+l Khi đó để giải (Ø} ta xuất phát từ bảng đơn hình chap nhận được đối ngẫu sau: [TTT- T7 TT rà LBs Lowes] Bs | as | | | b.,(x„) <0 Huy 2 0,4=1,m,u, ehuel =| - i Reconi Uneasy =F 44. j=l được lây từ bảng đơn hình gốc ứng với phương án tôi ưu xˆ.
Áp dụng thuật toán đơn hình đổi ngẫu bắt đầu từ bảng này dé giải bài toán có bố sung ràng buộc.) là phương án chấp nhận được của (Q) thì (x,.x,) là phương án chap nhận được của (Q). - Nếu (Q) không có phương án chấp nhận được thi (Q) cũng không có phương án chap nhận được.„„} là phương án tối ưu của (Q) thì (x;. x;) là phương án tôi ưu của (Ø). - Nếu (Q) không có phương án tối ưu thì (Q) cũng không có phương án tối ưu 4.
Dùng kết quả của bài toán QHTT dang chính tắc để kết luận cho kết quả của bài toán QHTT dạng chuẩn tắc: Các thuật toán trên chỉ áp dụng cho bài toán QHTT dạng chính tắc. Tuy nhiên, đôi khi bai toán đặt ra ở dạng không phải chính tắc, dạng chuẩn tắc chẳng han, vậy làm thé nào để giải những bai toán ở dạng không phải chính tắc? Sau đây là cách kết luận nghiệm cho bai toán QHTT dang chuẩn tắc thông qua kết quả của bài toán QHTT đạng chính tắc tương ứng: Xét bài toán QHTT dạng chuẩn tắc: + dex, > min J! (T7) Say, >h,ui=l.m mt x,20,/=l,n 16 Thêm biến phụ x, 20.1 = Lm ta được bai toán QHTT dang chỉnh tắc: a 3”c,x, > min (r! (77 ) S a u , c t a = h. i = l m x, 20 jelaem Giải (Tr) roi dựa vao kết quả thu được kết luận cho (TT): - Nếu (x,.) là phương án chấp nhận được của (77) thì (x,.x„) là phương án chấp nhận được của (77). - Nêu (77) không cỏ phương an chấp nhận được thì (77)ciing không có phương án chấp nhận được.x„„„} là phương án tối ưu của (7T} thì (x,,x,,.x,) là phương án tối ưu của (77).
- Nếu (77) không có phương án tối ưu thi (77)cũng không có phương án tối ưu. 17 CHƯƠNG II: GIẢI BÀI TOÁN QHTT NGUYEN A. Giới thiệu bài toán: ¬ ; ; Trong việc mô hình hoa nhiều van de img dụng, từ ý nghĩa thực tế các biến số phải nhận giá trị nguyên. Ching hạn, xét bài toán lập ke hoạch sản xuất với sản phẩm cuối cùng là không chia cắt được.
Một nhà máy có khá năng sản xuất n loại sản phẩm. Dé san xuất các loại sản phẩm nay can sử dụng m loại nguyên liệu. Biết: a, là chi phí nguyên liệu loại / để sản xuất ra một sản phẩm loại j 6 là dự trữ nguyên liệu loại¿ của nhà máy e, là tiền lãi từ việc bán một sản phẩm loại / trong đó ¡ =I. Nếu như sản phẩm được sản xuất với số lượng lớn (ví dụ như bi xe đạp) thi việc bỏ qua tính nguyên của biển số không dẫn đến những sai lệch đáng kế.
Thể nhưng nếu sản phẩm được sản xuất với số lượng không lớn va giá trị của một sản phẩm là cao (ví dụ như cổ máy kéo), thì tính nguyên của biển số là không thé bo qua. , Ta có mô hình toán học của bài toán trên là bài toán quy hoạch tuyên tính sau: , do, ~» max Say, Sb, ,ui=l.m ee mm Dat: x=(X;3g. đụ al? %ại a on iy b=(b,„b,.b„ ta có thé viết lại bài toán trên đưới dạng ma trận: (c,x) — max (P)4 Ax<b x>0.xeZ' Bai toán (P) được gọi là bài toán QHTT nguyên tông quát. Để giải những bài toán dang này, trong lịch sử toán học ứng dụng đã tìm ra một số phương pháp giải hữu hiệu, như Thuật toán cat Gomory, Thuật toán nhánh cận,.
Sau đây ta sẽ xét cụ thể cách giải bài toán này. Giải bài toán QHTT nguyên: ; Bài toán: Hay giải bài toán quy hoạch tuyển tinh nguyên: JS (x) =(c,x) > min (f.)\Ax=b x2a0xeZ' trong đỏ Ae A„. Y tưởng cơ bản giải bài toán QHTT nguyên: Dé giải bai toán QHTT nguyên (Ø ) ta giải bai toán QHTT tương ứng: /(xÌ =(e. Ta sẽ kết luận nghiệm cua ( /„) thông qua kết quả của (P,).
Cơ sở lý luận cơ bản: Cho bài toán quy hoạch tuyến tính nguyên: ƒ{(z) = (c,x) > min (f,)4Ax=b trong đó Ae M„. Gọi (7) là bai toán quy hoạch tuyến tinh tương ứng: #(x)= Íc, x)—» min (24Ax=» x20 trong đó Ae M. Mệnh đề 1: Nếu bài toán (72) không có phương án chấp nhận được thi bài toán (A) cũng không có phương án chấp nhận được. Chứng minh: Gọi D.D lần lượt là tập các phương án chap nhận được của (f,).(F,] Vi D=@ nên D=@ (døDc DỊ.
Vậy mệnh đẻ đã được chứng minh. Mệnh đề 2: Nếu bài toán (A) không cỏ phương án tối ưu thi bai toán (#„) cũng không có phương an tôi ưu. Chứng minh: Gọi D.