Khóa luận tốt nghiệp Toán tin: Một số mô hình toán học trong kinh tế

Trong những năm gần đây, toán ứng dung ngdy cing dike áp dungadu ring vd hiệu quả vào các ngành kinh tế, kÿ thuật, công nehệ thông tin v3 các nejnh khoa học khác DE thấy được ý nghia cửa

BỘ GIÁO DỤC ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM TP.HỒ CHÍ MINH

Trong những năm gần đây, toán ứng dung ngdy cing dike áp dung

adu ring vd hiệu quả vào các ngành kinh tế, kÿ thuật, công nehệ thông tin

v3 các nejnh khoa học khác

DE thấy được ý nghia cửa toán học trong thựcc tiễn, sidi hạn luận van

nảy, ngưCï viết di vào tìm hi€u một eố mô hình tcán cụ thể titdd thấy dice

tầm quan trong của mn hoe.

MOL trong những ứng dung người viết trnh hảy là dite trên phucns

phdp nhân tử Lagrange dé tim cực trị của him phi tuyến Ndi dung nả v trinh

kảy thuật toda cụ thé alta trên việc ching minh déu hiệu cue trị thông qua đạo him bậc nhất, bậc hai của hàm mục tiêu Phin nảy với đế tượng hoe sinh 12 aau khi học dao him cũng có thể tiếp thu và thực hiện phép tính Negus viết trình bảy đ chương cuối lé quần {ý dt án qua việc điều phối kiếm

«(, nén dự án và một ad tính toán dita trên kết qué của xác suất LhẾng

ké nâng cac:

Như vậy, tán học gắn liền với thực tiễn, với doi edng chứ không phả;

Ig Jý Lhuyết nặng nề.

Ngdy nay việc nghién cửu về ly thuyết vả thực hành ngay cảng die

ad rộng vả phát triển nhanh Bén thân em lả mỘt sinh viên khoe toán, em rất

quan tâm đến bộ mon nảy.

Những kiến thức về ứng dung của tcán trong thực tiễn rất cẩn cho

nSưCï sido viên khi truyền đạt cho các em thấy dược aut cần thiết ca mônhoe.

luận văn nả v trừnh bay như eau:

Changk Xây dung bai todn qui hoạch vả một 86 cơ 8d toán diy fé ahing

kiến thức chuẩn bi cho ching «au

( hưcts lt Xây dựng coed vả thuật toán của phương pháp don hình

( ưng Ii Trink bảy bai toán lim cực trợ cửa him 45 bẳng phưctys pháp ahin

lif Lagrange

( ưng lV Trinh bảy mô linh quần ly dự án bing ao dé mang CPM và PERT.

Thong qué trink thực hiện luận văn nảy, em đã được Thầy Nguyễn Chi

hong tận Link hưởng dần Em xin gui đến thầy long biết ch sâu aắc.

tìm xin chân thánh cắm on Quy Thầy CÓ thuộc Khoa Toán Dac biệt

T.ÝT.ván Ung Dung đã hing din gidng day chúng em trong suốt 4 năm qua

Xin cẳm on các bạn khóa 97dlã động viên giip đỠ tôi trong quá trinh

học lap.

Do giới hạn về kiến thức vả tải liệu nên luận văn na y.khÔng tránh khỏi thiếu acl Em rất mong được Quý Thầy Có hướng dẫn, chỉ bắc đóng góp

để tiến thức dược hoén thiện hon Em xin chân Lhảnh cẳm cn.

TD HỒ Chi Minh tháng O5/2OOI

PHAM THỊ DAO

MỤC Lục

Trang

Chương I H Mot SỐ cơ sử toán Ree Re NE RR RO REE NY

A Giới thiệu bài toán dẫn đến bài toán qui hoạch - |

TA Ba li ¡II gas <- 2

lu §‹rầầ 4

Chương IT: Phương pháp đơn hình: c«esesseeeeereesesse —

Í 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 - ò:2 2-—.-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 45

ILI 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ãốố sa 58

II 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:

- 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 =(X\, X;, , Xạ) € D là 1 phương án, phương án x* mà tại đó hàmmụ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.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ị 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ũ.

2 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 4b`;| 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

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:

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.2 Đị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

Các điểm ơ; a: là các đầu mút của đoạn fa, a).

1.3 Đị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, ơ› Gm Kýhiệu | = <0 ữa, d„>

L là bao lỗi của các điểm a), G¿, Œạ

1.4 Đị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

1 5 Định nghĩa Š:

Cho A = (a, @, , @) eX=(X¿.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

GVHD: TSKH.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.6 Đị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.D 1A

Như vậy C A là tập lồi và Cy (X:, Xa Xm} =< XỊ.Xš X„>

1.7 Đị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 Ký hiệu là C, 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

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

2.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

GVHD: T'SKH.NGUYEN CHÍ LONG LUAN VAN TOT NGHIEP

Mak,,.t, 2 0 => E ktiy 6€|0/1],j= hs

Vay a tổ hợp tuyến tính lỗi của các điểm Bj), B›, By.

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

Vậy với Y € D, Xu) € D: 1 - Ages >Ö, Í<À¿¿¡ + Anes = Í

NênX = (I-2¿.)Y + Auer Xie 6D

* Chứng minh:

)X,Y eBvàZ=^X+(1 -À)Y với O0 <^À<l lúc đó Z e<X, Y>.

Do X, Y, e< X\, X:, X„> nên theo tính chất 1:

=> Z € <

X),X2, ,Xn>-Vậy B là tập lồi.

ii) Trước tiên ta chứng minh rằng nếu có | điểm trong hệ sinh của B

mà nó được viết dưới dạng tổ hợp lỗi của các điểm sinh còn lại thì ta có thể

bỏ điểm này để được hệ sinh có ít phần tử hơn.

Ta có thể giả sử phan tử sinh cuối cùng là tổ hợp lôi của các phần từ

sinh X:, Xạ, , Xea (Không mất tính tổng quát ta có thể đánh số lại).

Điều này chứng tỏ : < X\, Xa Xn > C < Xp, X¿, Xn >

Hiển nhiên ta có: < X\, X¿, „ X„¡ >C < Xi, X¿, „ Xn > (lấy Ap = 0)

Vậy B= <X), X2, ,.Xn> = <X‡,X¿ „Xa >

Ta tiếp tục làm như trên cho đến khi không còn phần tử sinh nào trong

hệ mới có thể biểu diễn bằng tổ hợp lỗi của các phẩn từ sinh còn lại thì ta

được một hệ sinh có hữu hạn phần tử B= < X;, X¿ , X, > (r << n)

-Giả sử có một cực điểm X nào đó thuộc B với X # X,, i= hr

X= EA,X, +A,X, vớiA,>0 và EA, =1

i=l

GVHD: TSKHNGUYỄNCHÍLONG - LUẬN VĂN TỐT NGHIỆP

Do tính tối giản của hệ { X;,X;, X, > nên Y #X_.

X#X nên0 <),< 1 suy ra X là tổ hợp lỗi thực sự của hai điểm khác

nhau Y và X, trong B điều này mâu thuẫn với định nghĩa cực điểm.

Vậy theo chứng minh trên số cực điểm của B là hữu han và chúng lập

thành một hệ sinh tối giản của B

B=<X¡,X: X,> các vectd X,X¿ X, độc lập tuyến tính

3.4 - D„ —X(a El) là tập lôi, với 1 là tập chỉ số bất kỳ thì tập/=(1D, cũng lôi

* Chứng minh:

Lấy X\XạeD =X.,X:eD ,,Vdưel

vơ el,DoD, lôi =lXiX:|CD,., Vơ el

X; ` X: ` ` Xm

* Chứng minh:

Lay X = (Xp Xr Xe) € Apr Arar Ay XE A, I= im

Y = (Ys, Y>, , Yn) 6 Ái Aga os An mie AVi= Lm

Với OSASI Ax.+(1-A) ys e Ai (do Aj lỗi)

AX + (1 - AVY = (AK, AX ay ÀXe) # CCL = AD yy CD = AD y‡ (Í = AD Yø)

= (AX, (1 - A) yy Axa + (1 - À)Y+, ÀX„ + (1 + Ä)Y„) 6

Ä¡x Azan Am (do Ax, + (1 - Wy, € AL)

Vậy Ai + v xÁ lỗi trong X;+ X› x x Xm.

3 Các ví dụ về tập lôi trong không gian R°:

GVHD: TSKH.NGUYEN CHÍ LONG _ LUẬN VĂN TOT NGHIỆP

Cho A (x,y) B(X¿y‡), C Ona) Tim N (x,y).

Giả sử N thuộc miễn tong của AABC

Nối CN cắt AB tại M (x,y)

x= lx' + Lyxy = 1p (Agay + Agha) + lạXy= ly + lạÀ¿X;+* lạX:

y= ly! + boyy =l(Aiyi+ Aays) + hays = ayn + lạÀ‡Y‡ + hays

bat kp =hAy k> =hAy ki els

ky + kp + ky = A) + Ap + là = (Ar tAddt là = l¡ + lạ =

2, =e k;ạx; + k3X3

y= kiy¡+ KạY¿ + k3y3

Nếu: ay = (Xy,Y4),0Œ¿; = (XQ VQ) y= (Xy.Vy),Œ = (KY)

3

= k;¡œ¡+ kpQ2 + ky, k, e [0,1], zk, = |

i*

œ là tổ hợp tuyến tinh lỗi của các a), @2 Œ

Vi du 3: Cho A; (XI,Y, A> (X2,¥2), Âm (XmsYm)

Gy =(Xi,Y)), Œ3=(X3,Y3), Om = (Am Yd A= (X,Y) € R`.

a gọi là tổ hợp tuyến tính lỗi của các vect0 Œ¡,0¿ yo dụ.

isl

| - PHAN LOẠI CÁC ĐANG TOÁN

Trên thực tế mọi bài toán đều ở dang tổng quát nên không cần kiểm

tra xem đã tổn tại ở dạng tổng quát chưa

Ma trận rang buộc A chứa một ma trận đơn vị cấp m.

4 - Biến đổi dạng của dang bài toán quy hoạch tuyến tính:

d) Nếu gap ẩn x, tùy ý về dấu ta thay x, =x," =x," , xẺ.x ">04.2- Đưa dạng chính tắc về dạng chuẩn:

a) Nếu dạng chính tắc có b, <0 ta nhân phương trình i cho -1

Ma trận ràng buộc chưa chứa ma trận đơn vị ta cộng vào mỗi phương

trình một ấn giả x„„, với hệ số bằng 1 Trong hàm mục tiêu có ẩn giả có hệ

số M(f(x) — Min), -M(f(x) => Max),ta được bài toán gọi là bài toán mở

rộng của bài toán xuất phát

b) Nếu dạng chính tắc có b, z0 (i=l,m) có sẩn một số vectơ cột đơn

vị, ta chỉ cẩn thêm ẩn giả vào những phương trình cần thiết để tạo bài toán

dạng chuẩn

* Quan hệ giữa bài toán mở rộng và bài toán xuất phát:

+ Nếu (x), X2, Xa, x„) là phương án của bài toán xuất phát (BTXP)

thì

(Xj, Xg, Xv X„„0, 0) là phương án của bài toán mở rộng (BTMR) suy ra

nếu BTMR không có phương án tối ưu thì BTXP cũng vậy

+ Nếu BTMR có phương án tối ưu mà có một ẩn giả nhận giá trị

dương thì bài toán không có phương án

BTMR Còn BTXP có phương án:

xÌ= (xg xd „Xa! ) = XÌ= ( xị , te „ X„ 0 0) là một phương án

của BTMR.

Khi đó:

f(x)= Ee, x, > Min,xeL

yell

Ta giữ nguyên rang buộc va đưa bài toán về dang Max bằng cách:

f(x)= -f(x)—> Max,xeL

Nếu hài toán trên (max)có phương án tối ưu x* thì bài toán min cũng

có phương án tối ưu là x* và Í„„ = -[„„„ Thật vậy:

F max (x)= f(x" )= ~t(x” )> >-[(x)= f(x)> fÍx" ÌwxeL

Vậy x* là phương án tối ưu của bài toán Min.

II - TÍNH CHAT CUA TẬP NGHIỆM.

1 - Định lý 1:

i) Tập các phương án cho phép của bài toán QHTT là tập lôi.

ii) Tập L có thể phân hoạch thành những lớp không giao nhau cácphương án tương đương và mỗi lớp đó là một tập lôi

i) Lấy Xị,X; eL,X = AX, +(1-A)X2 ,À e [0,1]

Theo giả thiết:

Xét một lớp tương đương L; trong phân hoạch trên và một phương án

Y eL Giả sử [(Y) =a Theo tính chất lớp tương đương ta có: ¥ X,eL.:

Í(X,)= œ => L, =(XeL: f(X) = a) =L (X: Í(X) =a} L, (X: f(X) =a) là

3 Định lý 3:

Dang tuyến tính Z của bài toán QHTT đạt giá trị nhỏ nhất (GTNN)

(dat giá trị lớn nhất (GTLN)) ở những điểm cực biên của tập lôi L cácnghiệm cho phép Nếu Z dat GTNN (GTLN) dẳng thời ở vài điểm cực biênthì nỏ cũng đạt giá trị Gy ở một điểm bất kì thuộc bao lỗi cia các điểm cực

biên ấy.

*Chứng minh:

Giả sử tập nghiệm tập cho phép của bai toán là đa diện lồi bị chan L

có một xố hữu han điểm cực biên X¡,X;,X\ X„ và có nghiệm tối ưu là Xo.

Khi đó Z(Xy) < Z(X), với mọi X e L.

e© Nếu Xo là điểm cực biên thì định lý thỏa.

© Nếu Xo không là cực biên khi đó Xo có thể biểu diễn như sau:

Reis EAixi0S, si,Ea, sit

Nếu X = $A,X,,A, e[011,ŸA, =

Có nghĩa là Z dat GTNN ở một điểm X bất kỳ là tổ hợp tuyến tínhlồi của các điểm biên

4 - Định lý 4:

Nếu véc tơ A), Az A„(m<n) trong ma trận ràng buộc độc lập tuyến

tính thì X = (xạ, X2, X2 Xm, 0 0) là điểm cực biên của tập nghiệm L.

*Chứng minh:

Giả sử X không là điểm cực biên.Ta có thể biểu diễn X như sau:

X = AX, +À¿X¿,A,A; 6(009,Ây +22 =.

Trong đó X\,X; là các điểm cực biên và:

Xy= (XI, X2iz 2Xmiy Xm+i 1 x-¬+Xai)

X;= (Xi, X2 Xin2s Xmel 2+ ¬Xa2)

AX, =b as Aix, + A2Xo) tho? Aaxml = bít)

AX, =b AiXp; + A2X22 + +ÂmXm? =b(2)

Xmị ~ Xm2 =0 Xm| = Xm2

Hay X; =X, và X =X, v X = X;(vô If) Vay X là điểm cực biên của L.

Nếu X =( X) ,x;, x„) là điểm cực biên của L thì những véc tơ trong khai triển (hệ véc tơ ràng buộc ) với các x, > 0 là độc lập tuyến tinh Vì ma

trân A có m dòng nên điểm cực biên có không quá m thành phần dương.

Giả sử k thành phần đầu trên các véc tơ X là khác không và do X là

k

điểm cực biên nên: #A.x, = A,

j=l

Giả sử {4.,/=l,k } phụ thuộc tuyến tính, khi đó tổn tại những số

œ¡, œ œ không đồng thời bằng không va:

X= (X¡- OQ) ,X;- EQ¿, Xx- 6œy,Ú, 0)

Khi đó X;, X; là dựng it kay ra Xị, X: là các điểm cực biên va

2

GVHD: TSKH.NGUYEN CHÍ LONG OR LUẬN VAN TỐT NGHIỆP

+ Nếu X°#0 thì X”= (Xịo, Xzø, Xz Oyun 0), xo > 0 Nếu X” không

là phương ấn cực biên thì A,A; A, phụ thuộc tuyến tính và

3a,.i=hr fa, #0,5A,a, =0,choơ = Min “9œ, >0

Suy ra X' ít hơn X° một thành phần dương Nếu X' chưa là phương

án cực biên ta xây đựng XỶ có ít thành phan hơn nữa.

Có hai khả năng:

e Phương án có một số thành phẩn dương và hệ véc tơ liên kết độc

lập tuyến tính

se Được véctơ 0 là phương án của bài toán.

© Cả hai trường hợp ta đều được phương án cực biên của bài toán

Nhân xét:

Từ các định lý trên ta thấy có các khả năng sau:

e Bài toán không có phương án nào (vô nghiệm).

© Bài toán có một phương án duy nhất (một nghiệm)

GVHD: TSKH.NGUYEN CHILONG

-7.Dinh lí 7:

f là hàm tuyến tính xác định trên D(D:mién ràng buộc ) Nếu xo là

phương án tối ưu,x,cD va x, =ŸXÄx, Dy! =! thì x, là các phương

Seana 7ú _ LUẬN VĂN TỐT

án tối ưu

f(xo=f(Š`Äx,)=3`2./(x,)

Do xạ là phương án tối ưu nên f(xạ)> f(x,), i=l,m (bài toán Max )

Giả sử {(xo)>f(x)), khi đó:

[x)= KLAR IE LAM ELAS) =f)

& f(xo)>f(xo)(vô lí )

Vậy f(xạ)=f(x;) hay x, là các phương án tối ưu.

Ill - PHƯƠNG PHAP DON HÌNH

Nếu bài toán QHTT có phương án tối ưu thì có ít nhất một đỉnh của

L là 1 phương án tối ưu.Vì L là một đa diện lổi hữu hạn đỉnh nên thuật

toán tìm phương án tối ưu là hữu hạn.

Xuất phát từ một phương án cực biên ta tìm cách đánh giá nó xem có

là phương án tối ưu không Nếu không thỏa ta chuyển sang một phương án

cực biên mới sao cho cải tiến giá trị hàm mục tiêu và lại đánh giá phương

án này Tiếp tục như thế cho đến khi đạt được phương án tối ưu hoặc kết

luận bài toán không có phương án tối ưu.

Ta xét bài toán QHTT:

{(x)=<¢,x>—> max (1)

Ax=b (2)

x20 (3)

Với A =(au)mạ, rankA =m

Gia sử X là một phương án cực biên nào đó ta đặt:

LUVEN CF iv SESE EAIƑ ^ cide 48929

J* = (j/x, >0}, {A ye/*} là độc lập tuyến tính nên *l < m.

1.1 - Dinh nghĩa:

i) Phương án cực biên x được gọi là không thoái hóa nếu II”! = m va

thoái hóa nến Ut < m,

ii) Bài toán QHTT được gọi là không thoái hóa nếu tất cả các

phương án cực biên là không thoái hóa.

iii) Một hệ gồm m véc tơ độc lập tuyến tính { 4,,/€./ }sao cho

J2 J* được gọi là cơ sở của phương án cực biên X và các biến

(x,,/€ Hà các biến cơ sở, các biến (x,,/€/ }: là các biến phi cơ sở.

(4,,/€.! }: các véctơ cơ sở, ( 4,,/ €/ }: các véc tơ phi cơ sở.

1.2 - Tiêu chuẩn tối uu:

Xét bài toán QHTT không thoái hoá,

Giả sử đã tìm được một phương án cực biên

X = (X¡,Xa Xm,0, 0) và cơ sở của nó {(A;,A¿, Am„} suy ra:

ExjA, =b,x, >0,j=Ï¿m (7)

yl

Với giá trị của hàm mục tiêu: EXC) =f, (8)

A, =Z, -C, = >Z„€, -C, (0)

}

1.2.1 - Dinh lý 7: (tiêu chuẩn tối wu)

Nếu x” =(x,x;, x„,0, 0) là phương án cực biên thỏa điều kiện:

Ae >0, Wk = 1,2, n thì x* là phương án tối uu.

fr, “Lex, “iC, [š»⁄4)- Ede.) =DAy, 26

` \ yt

Tức là <c,x*> >c,y>, V y eL

Vậy x* là phương án tối ưu.

Trong công thức (5) Nếu A, là véc tơ cơ sở khi đó chỉ còn Z, = 1 còn các hệ số Z¿ (k#j) đều bằng 0 Do đó A, =C, -C, = 0, Vj e J Nên trong

thực hành để kiểm tra điểu kiện tối ưu của phương án cực biên ta chỉ cần

kiểm tra A, >0, Vk £ J

1.2.2 - Định lý §:

Nếu tần tại một số k sao cho Ay < 0 thì tốn tại phương án x' tốt hơn

lương ứng với nó hàm mục tiêu tăng.

Nếu ta thay 6 trong (20) bằng Op thì thành phần thứ r của x`sẻ bằng

không tức x,-ÐgZ„= 0, Như vậy phương án mới x`với cơ sở Aj, jeJ\{r}U{k} =

J

rk

8a = min

* Trường hợp A, < 0, Z, <0, V j e J thi tất cả các thành phân x, -6Z;,

sẽ không âm, V 0 > 0 Nhưng trong trường hợp này nếu 0-> +0 thì giá trị f'= fo -OA, tiến ra vô cùng tức bài toán không có phương án tối ưu.

Dantzig đã chứng minh rằng số bước lặp sẽ giảm nếu ta thay Ay

bằng A,thỏa A,= Min ÍA, :A, <0}, khi đó:

ii) Thay biến cơ sở vào các ràng buộc Ax = b để có m phuơng trình,

m ẩn số nghiệm của hệ này(x'”,x'5;, x'») chính là phương án cực biên

ban đầu x Khi đó: fy =c,xỊ”! + cạxf” + + c„xẲ),

i) Xác định các số Zy bởi hệ phương trình:

ii) Đối với các ke] tính các đại lượng

Ay = E Z¿€, —C¿,(k # 1), còn j e J thì A,= 0.

jek

Bước 3: Kiểm tra tối ưu:

Nếu Ay >0, V ke! thi x chính là phương án cực biên tối ưu Ding

thuật toán, Trái lại chuyển sang bước 4

Bước 4: Tìm véc tơ đưa vào cơ sở Có hai khả năng xảy ra:

I.3k£J1: A,<0 và Zys 0,Vj e J thì bài toán không có phương án

tối ưu Dừng thuật toán

2 Đối với mỗi k ¢ J: Ay < 0 đều tổn tại j € J; Z„ >0

Chọn A, = Min{ Ay: A,<0] đưa véc td A, vào cơ sở.

x

Bước 5: Tim véc tơ loại khỏi cơ sở: 8, = nin 2 : Za} = = Dua

js Ts

Bước 3: Ay = -(3/2) < 0 => x° chưa là phương án tối ưu của bài toán.

Bước 4: Xét Z„ Ta có Z4 > 0,Zs4 > 0 có thể tìm phương án tốt hơn,

Chon A, đưa vào cơ sd,

Bước 5: Tìm véc tơ đưa ra khỏi cơ sở:

8, =Min|~!‡Z,, Zi, XS Z„ >0}= Mini 2222 | Min{I2,4}=4 = 22

=> Dua A; ra khỏi cơ sở Cơ sở mới Jˆ={ A,A,,A,}

Lân lặp 2: Chọn x° = (x;,X2,0,x4,0)

Bước 3: Đưa số liệu lên bang đơn hình:

a

ee a ees ES ee eee ee ee

Bước 4: Tính các Ay, Ay = EZyC,,.keJ,cdn A; =0,j€1.

jel

Bước 5: Kiểm tra tối ưu:

+ Ak>0,Vke! thì x” là phương án tối ưu Ta dừng lại.

+ 3k£l:Ak<0 và 2 <0,VjeJ thì bài toán không có phương án

tối ưu Dừng.

A =Min{A, :A, <0} 6, = Min ik > | = Sẽ

jk "

Đưa A, vào cơ sở, A,ra khỏi cơ sở,

Bước 6: Thực hiện phép xoay với các phần tử trục là Z„ như sau:

+ Chia đòng chính (r) cho Z„ (được số 1 ở vị trí trục).

+ Lấy mỗi dòng chính trừ đi tích của các dòng chính (sau khi chia

cho Z„) Nhân phần tử xoay (được số 0 ở vị trí còn lại của cột xoay) Lúc

này A, là véc tơ đơn vị cơ sở.

Dựa trên công thức:

Ta được bảng mới với phương án mới x'.Trở lại bước 4.

Ví du 2: Với ví dụ trên sau khi sau khi tính x° = (6,3,6,0,0) và các Z„

,k =4,5 phần tử trục n= Zu == (vì ở bing 1 còn 3A, =-> <0)

Thực hiện xoay với Z4; = ; được số liệu bảng thứ hai Ta tiếp tục

tính A, và thấy A; > 0, Vj Dùng thuật toán và được phương án x’ = (4,5,0)

và fsx = 33.