Chương IT: Phương pháp đơn hình:. Phần loại các ame O68 co neẴcnenecoocan=eeoerieee 16 DAs TTR ch LẬP tGMNI Hi tccccc20/2466666G10000060001000666062yuce 19 II. Phương pháp Goin Mình .-c- 2-2 25 Chương III : Qui hoạch phi tuyến. s5 s<<<5s5552sssesssssessssassae 42 I, Một số định nghĩa và tính chất.«-ccc co ccsreoreeecree 42 II.
Cực đại, cực tiểu và điểm yên ngựa của hàm 2 biến. Cực trị có ràng buộc và phương pháp phân tử Lagrange. 51 Chương IV : Mô hình quản lý dự án. oer daccosatiossesessepias a Bek OC, | | go eree=eanãốố.
Mô hình dự án bằng sơ đỗ mạng. 555cc 59 A - GIỚI THIEU BÀI TOÁN QUI HOẠCH 1 - Bài toán dẫn đến bài toán qui hoạch: Bài toán: Một xí nghiệp dùng m loại nguyên liệu để sản xuất n loại sản phẩm khác nhau. Gọi b, (i= I,m) là lượng nguyên liệu loại i mà nhà máy dự trữ. x, (i= Ln) là lượng sản phẩm i mà xí nghiệp sản xuất với c, là tiền lãi mỗi đơn vị sản phẩm ¡.
a, (i= Lm, (= In) là lượng nguyên liệu ¡ dùng để sản xuất một đơn vị sản phẩm j. Hãy xác định lượng các sản phẩm x, cần sản xuất sao cho tiền lãi của xí nghiệp là cao nhất: f(x) = Fc,x, —> Max tel Với Ÿ ayx, <b, (i= 1m) ysl x20 (j=ln) 2 - Dang tổng quát: 2.1 - nghĩa Định 1; - Bài toán trên là các bài toán qui hoạch tuyến tinh (ham f(x) va các rang buộc là tuyến tính). - Hàm f(x) và ràng buộc thỏa diéu kiện nào đấy gọi là bài toán qui hoạch GVHD: TSKH.NGUYEN CHÍ LONG ` gh LUAN VAN TỐT NGHIỆP (=) — Với gi(x) < b.(i=lm),x eXcCR' (2) [ (x) gọi là hàm mục tiêu, g, (x) gọi là các hàm rang huộc. D =|[xeX#g(x) < (2) =b,i= Im } gọi là mién chấp nhận được hay miễn rang buộc., Xạ) € D là 1 phương án, phương án x* mà tại đó hàm mục tiêu đạt cực đại (hay cực tiểu) gọi là phương ấn tối ưu, f (x*): giá trị tối ưu.2 - Định nghĩa 2: Bài toán qui hoạch gọi là: i) Qui hoạch tuyến tính (QHTT) nếu hàm mục tiêu f(x) và tất cả các hàm ràng buộc là tuyến tính.
Tập D là đa diện lồi. ii) Qui hoạch phi tuyến nếu hàm mục tiêu f(x) hoặc ft nhất một trong các hàm rằng buộc là phi tuyến hoặc cả 2 là phi tuyến. iii) Qui hoạch lôi nếu bài toán tìm cực tiểu hàm lỗi trên tập D lỗi, * Nhân xéU, Để giải bài toán qui hoạch, thường là tìm giá trị của f (x) trên tất cả các phương án rồi so sánh chúng để tìm phương án tối ưu. Tuy nhiên, tập D có quá nhiều phan tử nên cách làm trên không khả thi, vì vậy đối tượng của môn qui hoạch là nghiên cứu từng thành phần của bài toán để đưa về những bài toán hoặc lớp bài toán giải được.
B - MỘT SỐ CƠ SỞ TOÁN I- PHÉP KHỬ GAUSS - JORDAN Xét hệ phương trình: a,x, +q;x, * +a, haa b, A,X, +AyX, + +4,X, = b, Bị lá Ayr = My b, a>) 432 « Ay (B\A)=|: bạ Ami 3m2 -‹+ Ime 1, Nếu nhân một số phương trình nào đó của hệ với một số khác 0 ta được hệ mới tương đương với hệ cũ. Nếu nhân một phương trình nào đó của hệ với một số tùy ý rồi công kết quả với phương trình khác ta được hệ mới tương đương với hệ da cho. Mọi hệ phương trình được xác định bởi ma trận mở rong nén mọi phép biến đổi thực chất là biến đổi ma tran md rộng, 2 phép biến đổi trên cho ma trận mở rộng là phép khử Gauss- Jordan. Ta quan tâm đến phẩn tử a, # 0 gọi là phần tử trục xoay.Hang r là hàng chủ yếu, cột s gọi là cột chủ yếu.Ta biến đổi ma trận mở rộng có dạng trên về dạng: bi} ai air 2 4 b`;| a's) ax 2 am (B'\ A) = b,|an a’ .E â”m b m| A4Ìm( A°m‡ Ô a’ Bằng các bước sau: cộng vào hàng i cũ của (B\A) (i=l,m ir) - Như vậy sau khi biến đổi cột chủ yếu thành vectơ đơn vị thứ r.
Ẩn x, còn lại duy nhất ở hàng r với hệ số bằng 1. 2 Ví dụ: B\A= l3 5 3 3-1I 42 8 1 2 Chọn phần tử trục a„ = ay = 2 Ta thực hiện phép khử như sau:. Hàng 2: chia cho ax = 2 ta được: 10 2 l 4 1⁄2. Hàng |}: lấy -a;;= -3 nhân hàng 2 rồi cộng vào hàng I: 5 3 3-1 I ~30 -6 -3 -12 -3/2 -25-3 0 -l3 -1/2 .Hàng 3: lấy -ay) =] nhân hàng 2 rồi cộng vào hang 3: 2 I -l -1 J 102 1 4 1⁄2 I2 3 0 3 3/2 25-3) 0 -13 -1/2 Khi đó: (B\1A)=| 10 2| 1 4 1⁄2 12 310 3 3/2 II - TẬP LOI 1 - Các định nghĩa và định lý: 1.
Định nghĩa 1: Cho các điểm (vectd) a ,œa,. œ„ của R", một tổ hợp lỗi của các điểm (vectơ) là một điểm (vectd) a € R" có dạng: GVHD: TSKH.NGUYEN CHÍ LONG v LUẬN VĂN TỐT NGHIỆP 1. Định nghĩa 2: Cho tập L c R" gọi là tập lỗi nếu mỗi cap điểm a, a» € L kéo theo mọi tổ hợp lỗi œ = kị a; + kz a2 (ky k2 © [0,1], kị + kạ = 1) cũng thuộc L. a: là các đầu mút của đoạn fa, a).
Định nghĩa 3 : Nếu ơ;, Ot). d„ là m điểm đã cho của R" thì tập tất cả các tổ hợp lỗi của các điểm này gọi là đa diện lỗi sinh bởi các ơi, ơ›. d„> L là bao lỗi của các điểm a), G¿,. Định nghĩa 4 : Cho Le R", điểm œ e L gọi là điểm cực biên của L nếu œ không thể biểu diễn dưới dạng tổ hợp lồi thực sự của 2 điểm khác nhau thuộc L.
Định nghĩa Š: Cho A = (a, @,.X: , X)eXvàœecR Ta ký hiệu<A,X>= $a, x, e Siêu phẳng H trong tập X là tập hợp các điểm X e X nghiệm đúng phương trình < A,X >=a H =(XeEX:<A,X>=a} Một siêu phẳng H chia X làm 2 nửa không gian đóng ký hiệu: H, = [XeX/<A X>>ơ} H = (XeX/<A .X><ơ] Một khúc lỗi trong X là giao của hữu hạn nửa không gian đóng trong X.Mội khúc lỗi giới nội gọi là đa diện lôi. Vídu: XétX=RÌ A(2,\1)€ R a= H = {x € R°/ 2x; + x2 = l] : siêu phẳng chính là đường thẳng 2x; +X2 = 1 trong hé trục xoy. H, = {xe R?/2x¡ + 2x221} là nửa mặt phẳng không chứa gốc 0.NGUYEN CHI LONG LUẬN VAN TỐT NGHIỆP Các khái niệm khúc lồi, đa diện lồi cho ta khái niệm hình hoc của tập các phương án của bài toán qui hoạch, 1. Định nghĩa 6 : Cho A c X.
Phần giao của tất cả các tập lỗi trong X chứa A được gọi là bao lỗi của A ký hiệu là C„A Che fe D lỗi cX.A là tập lồi và Cy (X:, Xa. Định nghĩa 7: Cho A c X phần giao của tất cả các tập lỗi đóng ong X chứa A được gọi là bao lỗi đóng của tập A. Như vậy CạA là tập Idi đóng nhỏ nhất chứa A. * ` i) D c X, D lồi thì Dm intD (phần trong) cũng lỗi và bao đóng D lồi.
+ D lỗi: Lấy X;, X: € D, cần chứng minh X = AX; + (1 -À)X;eD (OSAS 1) X¡eD =>3 lân cận U¿ của X¡: Uy CD => 2 U) + (1 - À) X; là 1 lân cận của X và kU) +(1 -A)XzcCD=>X e D. Vậy D lỗi, + D Wi: Lấy X;,X2 e D cẩn chứng minh X = À X, + (1-4) X2€D (OSA SI) Giả sử U là | lân cận của O thì: (X; *+U)¬Dz$ (X,€ D) (X2+U)AD#6 (X2€ D) => 3X, € (X,+U)¬D,¡=l2. Dat X' =A X, +(1-A)X, GVHD: TSKH.NGUYỄN CHÍ LONG LUẬN VĂN TỐT NGHIỆP => ÀX,+(l-À)X;eD=>XeD Thì X' =À(X,+U)+(lI -À)(X:+U) =X+U => (X+U)nDz 6 =>XeE D. ii) Cạ D = CạD * CoD là tập lỗi chứa D nên CạD là tập lổi đóng chứa D => CạD 2€, D (*)(C¿ D là tập lỗi đóng nhỏ nhất chứa D) Cạ D > CoD (vì CoD là giao của tất cả các tấp lồi không cần đóng chứa D).
=> om D> C,D (F?) Từ (*), (#*) suyra C,D = CạD 1. Dinh nghia 8: Tap K c X, K được gọi là nón, có đỉnh Onếu VX eK, VA>Othi A X € K. K là nón có đỉnh là x, nếu K - x, là nón có đỉnh là O. Cho K là nón có đỉnh O thì K được gọi là nón lồi nếu K là lồi tức V X, YeK,V)À,B>0:ÀX+BYe K.
Vị dụ: Trong R" Tập Ky ={(ŒX.Xa) © R” với X, 20 (i= In) Là các nón lôi có đỉnh O. Định nghiã 9: Phần giao của tất cả các nón lỗi (có đỉnh là O) chứa tap A và điểm O được gọi là nón lỗi sinh bởi tập A ký hiệu Ky, 1,10. Định lý 1; (Carathedory) GVHD: 1SKH.NGUYỄN CHÍ LONG LUẬN VĂN TỐT NGHIỆP ————--—————————————————ễễễ———_—_-__SỏSSSS. * Chứng minh: Xét B=(1JxA =({(1.X,)eB Và ¡25⁄9 - 2:0 (1,X) SAL (UX) HAL, Xa) te.
ta IXY _ lường: +.1 - Nếu œ € R là tổ hợp lôi của các điểm a, Gy., Oy € R và va, ( = bm) lai tà tổ hợp tôi của các điểm , Bs. By ER thì ứ cũng là 10 hyp lôi của các điểm By, Bu. B, « là tổ hợp lỗi của các a, i= Im nên «M3 m as k,a,.k,e 10,1] ' l Le a, là tổ hợp lồi của các B¿ J = ls ` ` a = tu B,. š tụ =1,4,€ [0,1] j* p= m ` ` m a = Lk, z t„B, = £(2 k, 1) B, tel jel geloaed DU) t m = = (k, tổ; =I + Lk, 1,3 )B; Feet Lk, 4B, 1 * Suy ra œ là tổ hợp tuyến tính của các j,, j= hs m m m ` tì b5 k, tụy + Pkt), Hot TK ok Ch = ok, =I 1 tel ——=———— ca SVTH: PHAM THỊ ĐÀO 8 GVHD: T'SKH.NG CHÍ UYLON EN G LUAN VAN TOT NGHIEP Mak,,.t, 2 0 => E kt iy 6€|0/1],j= hs Vay a tổ hợp tuyến tính lỗi của các điểm Bj), B›,.
2- DcX thì D là tập lôi nếu và chỉ nếu mọi tổ hợp lỗi X của các điểm X, c D cũng thuộc D. * Chứng minh: "=>” Với n= 2, X\, X: 6D, A), Ap 20, Ay +À‡ = 1, Theo định nghĩa tập lỗi thì X = A,X, + AyX> e D. Vậy kết luận đúng với n = 2. Giả sử kết luận đúng với n < k ta cần chứng minh kết luận đúng với n=k +1, Nghĩa là: WX.
Xe, Xe, ED và VA,>0(1= Lk +1) kel Với EA, = 1th) X A,X + Aa Xo. +eXs + Anes Xu¿e D. t=ÍỊ Ta giả sử Aus < 1 (vì nếu Ay) =Í => Ap = Ap =. Suy ra X = Auer X¡‹.