Môc Lôc

Néi dung Trang

Më ®Çu 2

Ch−¬ng 1: C¸c kiÕn thøc bæ trî

1.1. Bµi to¸n quy ho¹ch tuyÕn tÝnh tæng qu¸t 5

1.2. ThuËt to¸n ®¬n h×nh gi¶i bµi to¸n quy ho¹ch tuyÕn tÝnh 7

1.3. ThuËt to¸n ®¬n h×nh ®èi ngÉu gi¶i bµi to¸n quy ho¹ch tuyÕn tÝnh chÝnh t¾c 9

Ch−¬ng 2: Bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh

2.1. Bµi to¸n tèi −u rêi r¹c 19

2.2. Mét sè thuËt to¸n gi¶i bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh 26

Ch−¬ng 3: Bµi tËp vËn dông

3.1. Bµi tËp vËn dông thuËt to¸n c¾t Gomory 50

3.2. Bµi tËp vËn dông thuËt to¸n Land - Doig 58

3.3. Bµi tËp ®−a bµi to¸n vÒ bµi to¸n c¸i tói ®Ó gi¶i 64

Tµi liÖu tham kh¶o 74

- 1 -

Lêi Nãi ®Çu

1. LÝ do chän ®Ò tµi

Tèi −u ho¸ lµ mét lÜnh vùc to¸n häc nghiªn cøu lý thuyÕt vÒ thuËt to¸n gi¶i

c¸c bµi to¸n cùc trÞ. Nã lµ mét phÇn kiÕn thøc kh«ng thÓ thiÕu ®−îc cho nh÷ng

ng−êi lµm viÖc trong c¸c lÜnh vùc øng dông cña khoa häc vµ kü thuËt. Trong lý

thuyÕt tèi −u, mét trong nh÷ng líp bµi to¸n ®Çu tiªn ®−îc nghiªn cøu trän vÑn c¶

vÒ ph−¬ng diÖn lý thuyÕt lÉn thuËt to¸n lµ bµi to¸n quy ho¹ch tuyÕn tÝnh. Ngay tõ

khi ra ®êi, quy ho¹ch tuyÕn tÝnh ®Q chiÕm mét vÞ trÝ hÕt søc quan träng; nã lµ

m«n to¸n øng dông rÊt cÇn thiÕt ®èi víi sinh viªn thuéc nhiÒu ngµnh häc kh¸c

nhau. C¸c thuËt to¸n gi¶i bµi to¸n quy ho¹ch tuyÕn tÝnh kh«ng nh÷ng gióp gi¶i

quyÕt c¸c bµi to¸n quy ho¹ch tuyÕn tÝnh tæng qu¸t cì lín mµ nã cßn lµ ®iÓm xuÊt

ph¸t quan träng trong viÖc nghiªn cøu lý thuyÕt gi¶i c¸c bµi to¸n tèi −u tæng

qu¸t.

Trong lý thuyÕt tèi −u ta gÆp mét líp bµi to¸n mµ ®èi t−îng cña nã kh«ng

thÓ chia c¾t nhá tuú ý, trong líp bµi to¸n nµy tÊt c¶ (hoÆc mét bé phËn) c¸c biÕn

chØ nhËn gi¸ trÞ nguyªn, ®ã lµ bµi to¸n quy ho¹ch nguyªn. Trong bµi to¸n quy

ho¹ch nguyªn, nÕu hµm môc tiªu vµ hÖ rµng buéc lµ c¸c hµm tuyÕn tÝnh th× ta cã

bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh. §èi víi c¸c bµi to¸n quy ho¹ch nguyªn

tuyÕn tÝnh, c¸c thuËt to¸n gi¶i bµi to¸n quy ho¹ch tuyÕn tÝnh tæng qu¸t c¬ b¶n

hÇu hÕt kh«ng thÓ sö dông ®−îc n÷a do yªu cÇu vÒ tÝnh nguyªn cña c¸c biÕn sè.

N¨m 1958 Gomory (nhµ to¸n häc ng−êi mü) ®Q c«ng bè thuËt to¸n c¾t nèi tiÕng

®Ó gi¶i bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh më ®Çu cho sù ra ®êi vµ ph¸t triÓn

cña lý thuyÕt bµi to¸n quy ho¹ch nguyªn. TiÕp ®ã, mét sè kÕt qu¶ nghiªn cøu vÒ

tËp nghiÖm vµ lêi gi¶i cho líp bµi to¸n nµy lÇn l−ît ®−îc ra ®êi. Tuy xuÊt hiÖn

sau thuËt to¸n ®¬n h×nh gi¶i bµi to¸n quy ho¹ch tuyÕn tÝnh gÇn ba thËp kû nh−ng

c¸c thuËt to¸n gi¶i bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh ®Q cã nh÷ng ®ãng gãp

kh«ng nhá cho lÜnh vùc nghiªn cøu lý thuyÕt tèi −u tæng qu¸t.

Bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh lµ phÇn kiÕn thøc kh¸ míi mÎ ®èi

víi sinh viªn s− ph¹m to¸n. Víi mong muèn khai th¸c s©u kiÕn thøc m«n quy

ho¹ch tuyÕn tÝnh nãi riªng; më réng tÇm hiÓu biÕt cña b¶n th©n vÒ tri thøc to¸n

- 2 -

nãi chung, viÖc nghiªn cøu lý thuyÕt bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh lµ hÕt

søc cÇn thiÕt.

V× nh÷ng lý do trªn chóng t«i chän "VÒ bµi to¸n quy ho¹ch nguyªn

tuyÕn tÝnh" lµm ®Ò tµi nghiªn cøu.

2. Môc ®Ých nghiªn cøu

HÖ thèng l¹i mét c¸ch chi tiÕt c¸c vÊn ®Ò lý thuyÕt vÒ bµi to¸n quy ho¹ch

nguyªn tuyÕn tÝnh; x©y dùng hÖ thèng bµi tËp vËn dông, ®Ó tõ ®ã thÊy ®−îc tÇm

quan träng vµ tÝnh thiÕt thùc cña lý thuyÕt bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh

®èi víi c¸c lÜnh vùc khoa häc kü thuËt, c¸c ho¹t ®éng thùc tiÔn cña ®êi sèng xQ

héi.

3. NhiÖm vô nghiªn cøu

• Nghiªn cøu c¸c kiÕn thøc liªn quan ®Õn bµi to¸n quy ho¹ch tuyÕn tÝnh

tæng qu¸t, mét sè thuËt to¸n gi¶i bµi to¸n quy ho¹ch tuyÕn tÝnh.

• Nghiªn cøu c¸c ph−¬ng ph¸p gi¶i bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh. • Nghiªn cøu mét sè bµi tËp vËn dông ph−¬ng ph¸p gi¶i bµi to¸n quy ho¹ch

nguyªn tuyÕn tÝnh.

4. §èi t−îng vµ ph¹m vi nghiªn cøu

§èi t−îng nghiªn cøu: Lý thuyÕt tèi −u ho¸.

Ph¹m vi nghiªn cøu: Nghiªn cøu lý thuyÕt bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh.

5. Ph−¬ng ph¸p nghiªn cøu

• Ph−¬ng ph¸p nghiªn cøu lý luËn: §äc c¸c tµi liÖu vÒ m«n quy ho¹ch tuyÕn

tÝnh, c¸c tµi liÖu liªn quan ®Õn tèi −u ho¸, c¸c kho¸ luËn tèt nghiÖp vÒ quy

ho¹ch tuyÕn tÝnh cña c¸c kho¸ tr−íc ë tr−êng §¹i häc Hïng V−¬ng.

• Ph−¬ng ph¸p lÊy ý kiÕn chuyªn gia: Tham kh¶o ý kiÕn cña gi¶ng viªn

h−íng dÉn vµ c¸c gi¶ng viªn d¹y tèi −u ho¸; quy ho¹ch tuyÕn tÝnh cña

tr−êng.

• Ph−¬ng ph¸p tæng kÕt kinh nghiÖm: Tæng kÕt kinh nghiÖm cña b¶n th©n

qua qu¸ tr×nh häc häc phÇn quy ho¹ch tuyÕn tÝnh vµ cña c¸c b¹n sinh viªn

®Q häc tèi −u hãa cña c¸c líp s− ph¹m vµ c¸c líp qu¶n trÞ kinh doanh

trong tr−êng.

- 3 -

6. ý nghÜa khoa häc vµ thùc tiÔn

S¶n phÈm khoa häc: HÖ thèng l¹i mét sè kiÕn thøc cña lý thuyÕt tèi −u tuyÕn

tÝnh, giíi thiÖu mét sè thuËt to¸n gi¶i bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh, x©y

dùng hÖ thèng bµi tËp vËn dông lý thuyÕt ®Q x©y dùng.

S¶n phÈm thùc tiÔn: Khãa luËn lµ tµi liÖu tham kh¶o cho sinh viªn to¸n, tin häc

vµ sinh viªn c¸c ngµnh kinh tÕ, qu¶n trÞ kinh doanh.

7. Bè côc kho¸ luËn

Khãa luËn gåm 74 trang, ngoµi phÇn môc lôc, më ®Çu, kÕt luËn vµ tµi liÖu

tham kh¶o néi dung chÝnh cña kho¸ luËn bao gåm 3 ch−¬ng

Ch−¬ng 1. C¸c kiÕn thøc bæ trî

1.1. Bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh tæng qu¸t

1.2. ThuËt to¸n ®¬n h×nh gi¶i bµi to¸n quy ho¹ch tuyÕn tÝnh

1.3. ThuËt to¸n ®¬n h×nh ®èi ngÉu gi¶i bµi to¸n quy ho¹ch tuyÕn tÝnh

chÝnh t¾c

Ch−¬ng 2. Bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh

2.1. Bµi to¸n tèi −u rêi r¹c

2.2. Mét sè thuËt to¸n gi¶i bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh

• ThuËt to¸n c¾t cña Gomory • Ph−¬ng ph¸p nh¸nh cËn (ThuËt to¸n Land - Doig) • Ph−¬ng ph¸p ph−¬ng tr×nh truy to¸n cña quy ho¹ch ®éng gi¶i bµi

to¸n c¸i tói

Ch−¬ng 3. Bµi tËp vËn dông

3.1. Bµi tËp vËn dông thuËt to¸n c¾t cña Gomory

3.2. Bµi tËp vËn dông thuËt to¸n Land - Doig

3.3. Bµi tËp ®−a bµi to¸n vÒ bµi to¸n c¸i tói ®Ó gi¶i

- 4 -

CH¦¥NG 1

C¸C KIÕN THøC Bæ TRî

1.1. Bµi to¸n quy ho¹ch tuyÕn tÝnh tæng qu¸t

n

=

x

,....,

j

1.1.1. Bµi to¸n quy ho¹ch tuyÕn tÝnh tæng qu¸t

x x ( , 1 2

x )n

∑ fi c x j

= 1

j

T×m vect¬ sao cho hµm f(x) = min víi c¸c ®iÒu

n

kiÖn:

(1.1)

b i , i

I 1

j

a x ij

j

= 1

n

=

£ ˛

I

(1.2)

b i , i

j

a x ij

2

j

= 1

n

˛

(1.3)

a x ij

j

b i , i

I 3

= 1

‡ ˛

j

0,

(1.4)

˛

J 1 J

,

(1.5)

2

˛

0,

j

(1.6)

J 3

  ∑     ∑    ∑   j  ‡ x  j  ˛ x R j j   £ x  j

˛

I; I3

(cid:204) (cid:204) ¨ Víi I1 (cid:204)

(cid:204) (cid:204) J1 J; J2 I; I2 J; J3 (cid:204) I; I={ 1,.., m}; I1 J; J = { 1,.., n}; J = J1 ¨ I2 ¨ I3 = I; Ii ∩ Ik =Ø; i ≠ k; i, k = 1,2,3. J2 ¨ J3, Ji ˙ Jk = Ø; I ≠ k; i,k = 1,2,3.

=

bi, cj, aij lµ c¸c h»ng sè cho tr−íc. Trong bµi to¸n trªn: • f ®−îc gäi lµ hµm môc tiªu. • Mçi hÖ thøc ë (1.1), (1.2), (1.3), (1.4), (1.5), (1.6) gäi lµ mét rµng buéc. • Mçi rµng buéc (1.1), (1.2), (1.3) gäi lµ rµng buéc c−ìng bøc (hay c¬ b¶n). • Rµng buéc (1.4), (1.5), (1.6) gäi lµ rµng buéc tù do (hay rµng buéc dÊu).

x

,....,

x x ( , 1 2

x )n

˛ + Mçi vect¬ Rn tho¶ mQn mäi rµng buéc cña bµi to¸n

gäi lµ mét ph−¬ng ¸n. TËp hîp tÊt c¶ c¸c ph−¬ng ¸n (ký hiÖu D) gäi lµ miÒn rµng

- 5 -

buéc hay miÒn chÊp nhËn ®−îc. Ph−¬ng ¸n lµm cho hµm môc tiªu ®¹t cùc tiÓu

hoÆc cùc ®¹i ®−îc gäi lµ ph−¬ng ¸n tèi −u hay mét lêi gi¶i cña bµi to¸n ®Q cho.

+ Gi¶i bµi to¸n quy ho¹ch tuyÕn tÝnh lµ t×m ph−¬ng ¸n tèi −u cña bµi to¸n

(cã thÓ lµ ph−¬ng ¸n tèi −u duy nhÊt hoÆc v« sè ph−¬ng ¸n tèi −u) hoÆc chøng tá

bµi to¸n v« nghiÖm.

1.1.2. Mét sè kÝ hiÖu quy −íc

a) NÕu A lµ ma trËn cì (m,n) th× Ai =(ai1,ai2,...,ain) lµ vect¬ dßng (ma trËn dßng) thø i (i = 1,2,...., m) cña A; Aj = (a1j, a2j,..,amj) lµ vect¬ cét (ma trËn cét) thø j (j = 1,2,...,n) cña A.

b) At lµ ma trËn chuyÓn vÞ cña A.

i,j.

,....,

x

x x ( , 1 2

x )n

c) NÕu A = (aij) vµ B = (bij) lµ hai ma trËn cïng kiÓu th× bÊt ®¼ng thøc ma trËn A ≥ B ®−îc hiÓu lµ aij ≥ bij víi " = §Æc biÖt víi vect¬ (ma trËn) j. th× x ≥ 0 ®−îc hiÓu lµ xj ≥ 0 "

d) Mçi vect¬ ®−îc xem nh− ma trËn cét trong c¸c phÐp tÝnh ma trËn ( nÕu

=

x

,....,

kh«ng nãi g× thªm hoÆc kh«ng cã quy −íc g× kh¸c).

x x ( , 1 2

x )n

n

x y j

j

e) BiÓu thøc tÝch v« h−íng cña hai vect¬ ; y = (y1, y2, ..., yn)

∑

= 1

j

n

c x j

j

®−îc viÕt: (x, y) =

∑ lµ ma trËn cÊp 1 ( ct lµ

= 1

j

g) NÕu xem c vµ x lµ hai ma trËn cét th× ctx =

ma trËn chuyÓn vÞ cña c).

Víi nh÷ng quy −íc nh− trªn bµi to¸n quy ho¹ch tuyÕn tÝnh tæng qu¸t ®−îc

=

x

,....,

viÕt gän nh− sau:

x x ( , 1 2

x )n

˛ Rn tho¶ mQn: T×m vect¬

min. f(x) = ctx fi

- 6 -

b i ,

I

1

=

‡ ˛

b i ,

I

A x i A x i

2

˛

0,

j

x

J

j

‡ ˛

, R j

x

1 J

j

2

      

˛ ˛

Trong ®ã A = (aij) lµ hai ma trËn cì (m,n).

1.1.3. D¹ng chÝnh t¾c vµ d¹ng chuÈn t¾c cña bµi to¸n quy ho¹ch tuyÕn tÝnh

D¹ng chuÈn t¾c:

f(x) = ctxfi min

‡

j J

j

Ax b   ‡ x 0, 

˛

D¹ng chÝnh t¾c:

f(x) = ctx fi min

= Ax b x 0,

j

J

j

  

‡ ˛

1.2. ThuËt to¸n ®¬n h×nh gi¶i bµi to¸n quy ho¹ch tuyÕn tÝnh

n

=

f x ( )

min

j

fi∑ c x j

= 1

j

n

=

a x ij

j

b i

∑

= 1

j

XÐt bµi to¸n quy ho¹ch tuyÕn tÝnh chÝnh t¾c (bµi to¸n I)

(I)

x

0,

= j

1,

n

j

    

‡

- 7 -

• B−íc xuÊt ph¸t: T×m mét ph−¬ng ¸n cùc biªn

=

{

}

{ = ˛ j

0x vµ c¬ së } j J A B

/

B

;j A j

J

BJ

B

˛ ˛ t−¬ng øng, trong ®ã . T×m c¸c hÖ

ija vµ c¸c −íc l−îng

j

D sè khai triÓn ( ija : hÖ sè khai triÓn vect¬ Ai qua c¸c

• B−íc 1:KiÓm tra dÊu hiÖu tèi −u:

vect¬ Aj).

0

j

D £ a) NÕu " j ˛ J th× 0x lµ ph−¬ng ¸n tèi −u. ThuËt to¸n kÕt thóc.

j

• B−íc 2: KiÓm tra dÊu hiÖu hµm môc tiªu gi¶m v« h¹n. Víi mçi j ˇ BJ mµ

D b) NÕu $ > 0 th× chuyÓn sang b−íc hai.

jA t−¬ng øng.

ija cña cét

j

D > 0 th× kiÓm c¸c hÖ sè khai triÓn

j

ija ≤ 0 "

D a) NÕu tån t¹i > 0 mµ tÊt c¶ j ˛ J th× kÕt luËn hµm môc

tiªu gi¶m v« h¹n trªn miÒn rµng buéc. Bµi to¸n kh«ng cã lêi gi¶i

h÷u h¹n. ThuËt to¸n kÕt thóc.

BJ mµ

j

ija > 0

D > 0 ®Òu tån t¹i Ýt nhÊt mét hÖ sè b) NÕu víi mçi j ˇ

1

=

th× tiÕn hµnh t×m ph−¬ng ¸n cùc biªn míi tèt h¬n víi c¬ së

J

(

J

r \ )

s

B

• B−íc 3:

¨ theo quy t¾c sau:

}

{ D > max

0,

j

J

D = s

j

B

ˇ - T×m cét xoay: T×m

sA gäi lµ cét xoay (cét ®−a vµo c¬ së ).

0 r

q

=

=

>

min

,

0

Cét

a ij

x a

rs

0 x i a ij

    

    

- T×m dßng xoay: t×m

rA gäi lµ dßng xoay.

Dßng

- 8 -

PhÇn tö n»m trªn giao cña dßng xoay vµ cét xoay cña b¶ng ®¬n h×nh ®−îc

gäi lµ phÇn tö xoay.

• B−íc 4: Thùc hiÖn phÐp biÕn ®æi ®¬n h×nh chuyÓn tõ ph−¬ng ¸n c¬ së

chÊp nhËn ®−îc x sang ph−¬ng ¸n c¬ së chÊp nhËn ®−îc x : B¶ng ®¬n h×nh

t−¬ng øng víi x (gäi t¾t lµ b¶ng míi) cã thÓ thu ®−îc tõ b¶ng ®¬n h×nh

t−¬ng øng víi x (gäi t¾t lµ b¶ng cò) theo c¸c quy t¾c biÕn ®æi sau ®©y:

rja ) b»ng c¸c phÇn

=

a) C¸c phÇn tö ë vÞ trÝ dßng xoay trong b¶ng míi (

rj

a

j

J

a ,rj a rs

˛ tö t−¬ng øng trong b¶ng cò chia cho phÇn tö xoay:

b) C¸c phÇn tö ë vÞ trÝ cét xoay trong b¶ng míi, ngo¹i trõ phÇn tö n»m

ija D ,

)j

trªn vÞ trÝ phÇn tö xoay b»ng 1, cßn tÊt c¶ lµ b»ng 0.

®−îc tÝnh tõ c) C¸c phÇn tö cÇn tÝnh cßn l¹i trong b¶ng míi (

a

rj

=

c¸c phÇn tö t−¬ng øng trong b¶ng cò theo c¸c c«ng thøc sau:

ij

a

r

)

j

J

(

j

s )

a ij

a is

i J i ( B

B

a rs

- ˛ „ ˇ „ , ,

a

s

D = D j

j

rj a

rs

D -

1.3. ThuËt to¸n ®¬n h×nh ®èi ngÉu gi¶i bµi to¸n quy ho¹ch tuyÕn tÝnh chÝnh t¾c

1.3.1. C¬ së chÊp nhËn ®−îc ®èi ngÉu

t

=

XÐt bµi to¸n quy ho¹ch tuyÕn tÝnh d¹ng chÝnh t¾c (P) vµ bµi to¸n ®èi ngÉu (Q).

( )g y

by max

f x ( )

c x=

min

=

fi fi (P) (Q)

b

£

‡

c R

A x x

0

  

=

tA y   ˛ y }

{

J

;j A j

B

˛ lµ mét hÖ gåm m vect¬ Gi¶ thiÕt r»ng rankA = m. Gi¶ sö

cét ®éc lËp tuyÕn tÝnh cña ma trËn A. Ta gäi hÖ vect¬ nµy lµ c¬ së cña ma trËn A.

- 9 -

2

n

=

{

}

N

1 A A ,

,...,

A

Ký hiÖu \ B. Ph−¬ng ¸n c¬ së (xB, xN) cña bµi to¸n (P) t−¬ng

øng víi c¬ së B thu ®−îc b»ng c¸ch gi¶i hÖ ph−¬ng tr×nh tuyÕn tÝnh xN = 0, ABxB = b.

§Þnh nghÜa : Ta gäi B lµ c¬ së chÊp nhËn ®−îc gèc nÕu ph−¬ng ¸n c¬ së

t−¬ng øng víi nã lµ ph−¬ng ¸n chÊp nhËn ®−îc cña bµi to¸n gèc, (tøc lµ nÕu

A b-=

0

x B

1 B

1

=

c=

y

(

c-

‡ ). Ta gäi ph−¬ng ¸n c¬ së ®èi ngÉu t−¬ng øng víi c¬ së B lµ vect¬ y

t A y B

B

)t A B

B

thu ®−îc b»ng c¸ch gi¶i hÖ ph−¬ng tr×nh tuyÕn tÝnh (tøc lµ )

C¬ së B ®−îc gäi lµ c¬ së chÊp nhËn ®−îc ®èi ngÉu nÕu ph−¬ng ¸n c¬ së ®èi

ngÉu øng víi nã lµ ph−¬ng ¸n chÊp nhËn ®−îc cña bµi to¸n ®èi ngÉu.

NÕu ph−¬ng ¸n c¬ së t−¬ng øng víi B lµ ph−¬ng ¸n tèi −u th× B sÏ ®−îc

gäi lµ c¬ së tèi −u.

1

=

y

(

c-

Nh− vËy nÕu B lµ c¬ së chÊp nhËn ®−îc ®èi ngÉu th× ph−¬ng ¸n c¬ së ®èi

)t A B

B

ngÉu t−¬ng øng víi nã ph¶i tho¶ mQn tÊt c¶ c¸c rµng buéc cña bµi

1

)

c

0

tA y

c£

t t A A ( B

c B

- - £ to¸n ®èi ngÉu hay (1.7)

DÔ thÊy nÕu B lµ c¬ së chÊp nhËn ®−îc gèc, th× ®iÒu kiÖn (1.7) chÝnh lµ

tiªu chuÈn tèi −u. Nh− vËy, c¬ së B sÏ lµ tèi −u nÕu nh− nã võa lµ chÊp nhËn

®−îc gèc võa lµ chÊp nhËn ®−îc ®èi ngÉu.

NhËn xÐt

• ThuËt to¸n ®¬n h×nh gèc lµ b¾t ®Çu tõ mét c¬ së chÊp nhËn ®−îc gèc, sau

mét sè h÷u h¹n lÇn chuyÓn c¬ së sÏ ®i ®Õn c¬ së tèi −u.

• ThuËt to¸n ®¬n h×nh ®èi ngÉu l¹i b¾t ®Çu tõ mét c¬ së chÊp nhËn ®èi ngÉu

nh−ng ch−a ph¶i chÊp nhËn ®−îc gèc, ta tiÕn hµnh dÞch chuyÓn sang c¸c

c¬ së chÊp nhËn ®−îc ®èi ngÉu míi cho ®Õn khi gÆp ®−îc c¬ së tèi −u th×

dõng l¹i.

1.3.2. ThuËt to¸n ®¬n h×nh ®èi ngÉu khi ®· biÕt c¬ së chÊp nhËn ®−îc ®èi ngÉu

- 10 -

XÐt bµi to¸n quy ho¹ch tuyÕn tÝnh d¹ng chÝnh t¾c.

=

b

f(x) = ctxfi min

A x x

0

  

‡

Gi¶ sö B lµ c¬ së chÊp nhËn ®−îc ®èi ngÉu. Kh«ng gi¶m tæng qu¸t ta coi B

= (A1,A2,....,Am).

Ta lËp b¶ng ®¬n h×nh øng víi c¬ së B cña bµi to¸n gèc.

Gi¶ ...... ..... C¬ cj c¬ së c1 cn cj

ph−¬ng ¸n së ...... ..... A1 An Aj

1 ja

1b

A1 c1

2b

2 ja

A2 c2

..... ..... ..... ......

mb

mja

Am cm

j

D D

1

=

=

b b b ( , 1 2

,...,

b )'m

B b-

B¶ng 1

j

Trong ®ã:

j

=

=

=

2

j

mj

A

(

a a 1 , j

,....,

a

)

1 B A j

,

1,

n

-

1

j

=

j

1,

n

c

D = j

c B A B

j

- - ;

Cét gi¶ ph−¬ng ¸n cã thÓ chøa c¸c thµnh phÇn ©m v× B ch−a ch¾c ®Q lµ

mét c¬ së chÊp nhËn ®−îc gèc.

- 11 -

0

j

n= 1,

j

D £ Do B lµ mét c¬ së chÊp nhËn ®−îc ®èi ngÉu nªn "

C¸c b−íc cña thñ tôc ®¬n h×nh ®èi ngÉu.

i

m= 1,

B−íc 1: KiÓm tra tiªu chuÈn tèi −u. C¬ së ®ang xÐt sÏ lµ tèi −u nÕu mäi

ib ,

thµnh phÇn cña cét gi¶ ph−¬ng ¸n ®Òu kh«ng ©m v× khi ®ã c¬ së ®ang

i

m= 1,

xÐt sÏ chÊp nhËn ®−îc gèc vµ v× thÕ nã lµ tèi −u.

ib ‡

0

" • NÕu th× gi¶ ph−¬ng ¸n (xB, xN) lµ mét ph−¬ng ¸n tèi −u.

i

m= 1,

i

m= 1,

ThuËt to¸n kÕt thóc.

ib < 0 th× ta t×m rb = min{ ib ,

• NÕu $ i, mµ }.

NÕu cã nhiÒu chØ sè cïng ®¹t cùc tiÓu th× chän r lµ mét chØ sè tuú ý trong sè ®ã.

m= 1,

i

B−íc 2: KiÓm tra ®iÒu kiÖn ®Ó tËp ph−¬ng ¸n cña bµi to¸n lµ kh«ng rçng: nÕu cã

ib < 0 th× trªn dßng i ph¶i tån t¹i Ýt nhÊt mét phÇn tö

ija < . 0

n= 1,

j

mµ

ib < 0 (i = 1,2,...,m) mµ

ija ‡

• NÕu cã dßng øng víi 0 " . Khi ®ã

bµi to¸n gèc (P) kh«ng cã ph−¬ng ¸n.

n

=

=

,

i (

1,

m )

a x i j

j

b i

ThËt vËy. Gi¶ sö (P) cã ph−¬ng ¸n, tøc lµ $ x ˛ Rn tho¶ mQn Ax = b, x‡ 0

∑

j

= 1

n= 1,

j

ija ‡

hay (*)

0 ( (*) kh«ng thÓ x¶y ra v× 0, xj ‡ ) cßn bi < 0. VËy bµi to¸n (P)

kh«ng cã ph−¬ng ¸n.

ib < 0 ®Òu tån t¹i Ýt nhÊt mét phÇn tö

ija £

0

• NÕu trªn mçi dßng øng víi

. Khi ®ã ta tiÕn hµnh mét b−íc lÆp ®¬n h×nh ®èi ngÉu ®Ó

chuyÓn sang mét c¬ së chÊp nhËn ®−îc ®èi ngÉu míi. Gi¶ sö ®Q chän

dßng xoay r. Ta t×m cét ®−a vµo c¬ së thay cho cét Ar. Cét ®−a vµo

thay cho Ar ph¶i ®¶m b¶o sao cho c¬ së míi vÉn lµ c¬ së chÊp nhËn

- 12 -

®−îc ®èi ngÉu. Gi¶ sö cét As ®−îc ®−a vµo thay cho cét Ar, khi ®ã

rj

phÇn tö trôc ars vµ sau khi thùc hiÖn tÝnh to¸n ®æi c¬ së th× c¸c phÇn tö

)

j

s

rs

a a

D - D ë dßng −íc l−îng øng víi c¬ së míi sÏ lµ (

Do ®ã muèn c¬ së míi vÉn lµ chÊp nhËn ®−îc ®èi ngÉu ta ph¶i chän chØ sè

j

s

=

<

rj

min

;

a

0

D

rs

rj

a

D  a 

  

s øng víi . Cét As gäi lµ cét xoay.

Sau khi ®Q x¸c ®Þnh ®−îc dßng xoay, cét xoay ta tiÕn hµnh c¸c tÝnh to¸n

trong phÐp biÕn ®æi ®¬n h×nh gièng nh− ®Q lµm trong bµi to¸n gèc.

1.3.3. ThuËt to¸n ®¬n h×nh ®èi ngÉu khi ch−a biÕt c¬ së xuÊt ph¸t chÊp

nhËn ®−îc ®èi ngÉu

XÐt bµi to¸n quy ho¹ch tuyÕn tÝnh d¹ng chÝnh t¾c sau:

=

A x

b

f(x) = ctx fi min

x

0

  

‡

Gi¶ sö c¬ së chÊp nhËn ®−îc ®èi ngÉu lµ ch−a biÕt. Tuy vËy ta cã thÓ t×m

®−îc c¬ së B cña ma trËn A. Kh«ng gi¶m tæng qu¸t ta coi r»ng B = {A1, A2,...,

Am}. Gi¶ sö c¬ së B kh«ng ph¶i lµ c¬ së chÊp nhËn ®−îc ®èi ngÉu (cã thÓ nã

còng kh«ng chÊp nhËn ®−îc gèc).

§−a thªm vµo mét biÕn gi¶ x0 ‡ 0 víi hÖ sè hµm môc tiªu c0 = 0, vµ thªm

vµo hÖ rµng buéc cña bµi to¸n xuÊt ph¸t mét rµng buéc gi¶ sau:

x0 + xm +1 + ...........+ xn = M

trong ®ã (xm+1,......, xn) lµ vect¬ c¸c biÕn phi c¬ së, cßn M lµ mét sè d−¬ng lín h¬n bÊt kú mét sè cô thÓ nµo cÇn so s¸nh víi nã. Bµi to¸n thu ®−îc ta sÏ gäi lµ

- 13 -

0

=

⌢ )m A

,....,

,

bµi to¸n më réng. §èi víi bµi to¸n më réng ta cã mét c¬ së cña nã lµ ⌢ ⌢ ⌢ 1 B A A (

⌢ Ta x©y dùng b¶ng ®¬n h×nh t−¬ng øng víi c¬ së B

cña bµi to¸n më réng.

Ph−¬ng ¸n ....... ....... c0 c1 cn cj

⌢ 1A

⌢ 0A

⌢ jA

⌢ mA

cj c¬ së C¬ ⌢ së B ....... ....... M

⌢ 0A

1 1 0 1 c0

⌢ 1A

1b

1ja

1na

0 c1

..... ..... ..... ..... ..... ......

mb

⌢ mA

mja

mna

0 cm

1

n

j

0

D D D D ......

⌢ b M+

Chó ý r»ng, khi tÝnh gi¸ trÞ c¸c thµnh phÇn cña cét ph−¬ng ¸n ta viÕt nã

⌢ d−íi d¹ng i b

i

. Khi ®ã trong b¶ng ®¬n h×nh cét ph−¬ng ¸n ®−îc t¸ch ra lµm

⌢ hai cét, mét cét ghi hÖ sè ib

⌢ cña M, cßn cét kia ghi hÖ sè tù do ib

.

n= 1,

j

⌢ }. Do B

s

D > 0. Thùc hiÖn mét phÐp biÕn ®æi ®¬n h×nh víi phÇn

D D Gi¶ sö ; kh«ng ph¶i lµ c¬ së chÊp nhËn ®−îc = max { j

s

®èi ngÉu cña bµi to¸n nªn

tö xoay a0s (nghÜa lµ ®−a biÕn xs vµo c¬ së cßn ®−a x0 ra khái c¬ së) ta sÏ ®i ®Õn

j

n= 1,

j

D b¶ng ®¬n h×nh míi mµ trong ®ã tÊt c¶ c¸c phÇn tö cña dßng −íc l−îng ;

®Òu lµ kh«ng d−¬ng tøc lµ thu ®−îc b¶ng ®¬n h×nh ®èi ngÉu víi c¬ së chÊp nhËn

®−îc ®èi ngÉu nªn ta cã thÓ tiÕn hµnh thñ tôc ®¬n h×nh ®èi ngÉu víi c¬ së chÊp

nhËn ®−îc ®èi ngÉu ®Ó gi¶i bµi to¸n më réng.

ThuËt to¸n ®¬n h×nh ®èi ngÉu gi¶i bµi to¸n më réng sÏ kÕt thóc ë mét

trong c¸c tr−êng hîp sau.

- 14 -

1) Bµi to¸n më réng kh«ng cã ph−¬ng ¸n. Khi ®ã bµi to¸n xuÊt ph¸t còng

kh«ng cã ph−¬ng ¸n. ThËt vËy, nÕu bµi to¸n xuÊt ph¸t cã ph−¬ng ¸n chÊp

=

x

(

x x , 0 1

,....,

x

)n

nhËn ®−îc x = (x1, x2,...., xn) th× râ rµng x = (x0, x1,...., xn) víi x0 = M - xm+1 -..........- xn còng lµ mét ph−¬ng ¸n cña bµi to¸n më réng.

2) Bµi to¸n më réng cã ph−¬ng ¸n tèi −u vµ x0 lµ biÕn c¬

x 1( ,....,

x lµ ph−¬ng ¸n tèi −u cña bµi to¸n ban ®Çu. )n

së. Trong tr−êng hîp nµy hµm môc tiªu cña bµi to¸n kh«ng phô thuéc vµo

=

1

x

(

x x , 0

,....,

x

)n

M, do ®ã

3) Bµi to¸n më réng cã ph−¬ng ¸n tèi −u vµ x0 kh«ng lµ

biÕn c¬ së. Trong tr−êng hîp nµy c¸c biÕn c¬ së sÏ phô thuéc vµo M. Cã

hai kh¶ n¨ng x¶y ra

• NÕu gi¸ trÞ hµm môc tiªu cña bµi to¸n më réng phô thuéc vµo M th×

khi M fi ¥ gi¸ trÞ hµm môc tiªu sÏ dÇn ®Õn ¥ .Trong tr−êng hîp

nµy bµi to¸n xuÊt ph¸t cã ph−¬ng ¸n chÊp nhËn ®−îc nh−ng hµm

môc tiªu kh«ng bÞ chÆn d−íi nªn bµi to¸n kh«ng cã lêi gi¶i.

• NÕu gi¸ trÞ hµm môc tiªu cña bµi to¸n më réng kh«ng phô thuéc

vµo M th× bµi to¸n xuÊt ph¸t cã ph−¬ng ¸n tèi −u vµ cã thÓ chÊp

nhËn ®−îc nã b»ng c¸ch bá 0x vµ gi¶m dÇn gi¸ trÞ M cho ®Õn khi cã

2x ,....,

nx trë thµnh 0.

mét trong c¸c 1x ,

1.3.4. ¸p dông thuËt to¸n ®¬n h×nh ®èi ngÉu ®Ó gi¶i bµi to¸n quy ho¹ch

tuyÕn tÝnh víi sè rµng buéc t¨ng dÇn

XÐt bµi to¸n quy ho¹ch tuyÕn tÝnh (I):

Gi¶ sö ta ®Q gi¶i bµi to¸n (I) b»ng thuËt to¸n ®¬n h×nh vµ thu ®−îc ph−¬ng

=

{ 2 B A A

1 ,

} ,..., m A

¸n tèi −u c¬ së *x víi c¬ së tèi −u B. Kh«ng gi¶m tæng qu¸t ta cã thÓ coi r»ng

. Ta cã b¶ng ®¬n h×nh tèi −u lµ b¶ng 1 phÇn 1.3.2.

- 15 -

n

B©y giê bæ sung vµo hÖ rµng buéc cña bµi to¸n mét ph−¬ng tr×nh:

x

(1.8)

j

b + 1 m

£

∑ a + m j 1,

= 1

j

NÕu *x tho¶ mQn rµng buéc ( 1.8) th× nã vÉn lµ ph−¬ng ¸n tèi −u cña bµi

*x kh«ng tho¶ mQn rµng buéc bæ sung,

to¸n cã rµng buéc bæ sung nµy. Gi¶ sö

n

*

>

a

tøc lµ:

m

1,

j

b m

+ 1

∑

j

x+

= 1

j

*x vµ c¬ së tèi −u B ®Ó

(1.9)

VÊn ®Ò ®Æt ra: LiÖu ta cã thÓ sö dông ph−¬ng ¸n tèi −u

gi¶i bµi to¸n víi rµng buéc bæ sung hay kh«ng?

1nx + ‡

§−a thªm vµo biÕn phô 0 chuyÓn rµng buéc (1.8) vÒ d¹ng ®¼ng

n

+

=

a

x

+

thøc ta thu ®−îc:

m

1,

j

j

x n

+ 1

b m

+ 1

∑

= 1

j

(1.10)

XÐt bµi to¸n (I) víi rµng buéc bæ sung (1.10) mµ ta sÏ gäi lµ bµi to¸n bæ

n

=

+

sung.

f x ( )

0

min

c x j

j

x + 1 n

∑

= 1

j

n

=

=

1,

m

a x ij

j

b i ; i

∑

= 1

j

n

+

=

a

x

x

+

+

+

m

1,

j

j

1

n

b m

1

∑

= 1

j

fi

0;

1,

1

x

= j

+ n

j

        

‡

- 16 -

2

m

n

1

=

⌢ B

⌢ ⌢ 1 A A ,

(

,...,

⌢ ⌢ A A + ,

)

§èi víi bµi to¸n bæ sung c¬ së cña nã lµ . B¶ng

®¬n h×nh t−¬ng øng víi c¬ së nµy cã thÓ thu ®−îc tõ b¶ng ®¬n h×nh tèi −u cña bµi

to¸n ban ®Çu vµ cã d¹ng sau.

..... ... cj c¬ së Ph−¬ng c1 c2 cn cj

⌢ nA

⌢ jA

⌢ 2A

⌢ 1A

¸n C¬ së ⌢ B ..... .... cn+1 1nA +⌢

1b

1 ja

0 c1

⌢ 1A ⌢ 2A

2b

2 ja

0 c2

.... 0 .... .... .....

mb

mja

0 cm

⌢ mA 1nA +⌢

1mb +

j

a + 1,m

1 cn+1

j

j

1

2

n

D D D D D 0 .... ....

m

=

Trong ®ã:

a + 1, m j

1,

;

a + 1, m j

= + a j m n ij

-

∑ a + 1, m i

= 1

i

=

m

+ = 1, j

a

0;

j

1,

m

m

=

m

+ 1

b

b m

+ 1

a + 1, m i

b i

- ∑

= 1

i

Do (1.9) nªn b¶ng ®¬n h×nh thu ®−îc kh«ng ph¶i lµ chÊp nhËn ®−îc gèc.

ThÕ nh−ng râ rµng nã lµ chÊp nhËn ®−îc ®èi ngÉu. V× vËy ta cã thÓ ¸p dông thuËt

to¸n ®¬n h×nh ®èi ngÉu tõ b¶ng nµy ®Ó gi¶i bµi to¸n bæ sung. Kü thuËt võa m« t¶

ë trªn ®−îc gäi lµ " kÜ thuËt t¸i tèi −u ho¸".

- 17 -

KÕt luËn ch−¬ng 1

Ch−¬ng 1 ®Q tr×nh bµy mét sè vÊn ®Ò c¬ së cña lý thuyÕt tèi −u: bµi to¸n

quy ho¹ch tuyÕn tÝnh tæng qu¸t, thuËt to¸n ®¬n h×nh gèc gi¶i bµi to¸n quy ho¹ch

tuyÕn tÝnh, thuËt to¸n ®¬n h×nh ®èi ngÉu gi¶i bµi to¸n quy ho¹ch tuyÕn tÝnh. §©y

lµ c¸c néi dung c¬ b¶n lµm c¬ së ®Ó tiÕn hµnh nghiªn cøu c¸c thuËt to¸n gi¶i bµi

to¸n quy ho¹ch nguyªn tuyÕn tÝnh ë ch−¬ng 2.

- 18 -

Ch−¬ng 2

bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh

2.1. Bµi to¸n tèi −u rêi r¹c

2.1.1. X©y dùng m« h×nh tèi −u rêi r¹c

Tr−íc tiªn chóng ta bµn vÒ nh÷ng nguyªn nh©n dÉn ®Õn tÝnh rêi r¹c cña

biÕn sè trong viÖc x©y dùng m« h×nh tèi −u ho¸ cho c¸c bµi to¸n thùc tÕ.

Mét trong nh÷ng nguyªn nh©n ®Çu tiªn dÉn ®Õn tÝnh rêi r¹c cña biÕn sè lµ

tÝnh kh«ng chia c¾t ®−îc cña ®èi t−îng nghiªn cøu. Ngoµi ra, trong nhiÒu bµi

to¸n thùc tÕ chÝnh do cÊu tróc tæ hîp ban ®Çu cña bµi to¸n mµ c¸c biÕn sè chØ cã

thÓ nhËn c¸c gi¸ trÞ rêi r¹c. Cuèi cïng, tÝnh rêi r¹c cña c¸c biÕn sè cã thÓ xuÊt

hiÖn tõ tÝnh kh«ng liªn tôc, ®a cùc trÞ cña hµm môc tiªu cña bµi to¸n. Ta sÏ minh

ho¹ cho c¸c vÊn ®Ò võa bµn tíi ë c¸c vÝ dô sau nµy.

M« h×nh bµi to¸n tèi −u rêi r¹c tæng qu¸t

Bµi to¸n tèi −u rêi r¹c tæng qu¸t cã thÓ ph¸t biÓu nh− sau:

,....,

) min(

max )

f x x ( , 1 2

x n

n

=

fi , (2.1)

x

,....,

)

D

˛ (cid:204)

R

x x ( , 1 2

x n

=

x

,....,

x x ( , 1 2

x )n

Trong ®ã D lµ tËp c¸c vect¬ mµ mét sè (hoÆc tÊt c¶) c¸c

thµnh phÇn cña nã chØ nhËn gi¸ trÞ rêi r¹c.

Th«ng th−êng tËp D ®−îc x¸c ®Þnh bëi mét hÖ thèng c¸c ph−¬ng tr×nh vµ

=

= ( ) 0,

i

1, 2,....,

,

bÊt ph−¬ng tr×nh víi ®iÒu kiÖn bæ sung vÒ tÝnh nguyªn cña c¸c biÕn sè sau ®©y:

ig x

m 1

(2.2)

0,

1,.....,

m

ig x ( )

+ = i m 1

£ (2.3)

- 19 -

=

j

1,2,...,

jx - nguyªn,

n 1

(2.4)

n< ta

Khi ®ã bµi to¸n (2.1) - (2.4) ®−îc gäi lµ bµi to¸n quy ho¹ch nguyªn.

n= ta cã bµi to¸n quy ho¹ch nguyªn hoµn toµn, cßn nÕu 1n

NÕu 1n

cã bµi to¸n quy ho¹ch nguyªn bé phËn.

Mét tr−êng hîp riªng quan träng cña bµi to¸n quy ho¹ch nguyªn lµ bµi

( )

f x vµ ( )

ig x (i = 1,2,...,m) lµ tuyÕn tÝnh.

to¸n quy ho¹ch nguyªn tuyÕn tÝnh thu ®−îc tõ bµi to¸n tæng qu¸t khi c¸c hµm

2.1.2. Mét sè t×nh huèng th−êng gÆp khi x©y dùng c¸c m« h×nh thùc tÕ cña

tèi −u rêi r¹c

2.1.2.1. Bµi to¸n ®iÒu kiÖn kh«ng chia c¾t ®−îc

Trong viÖc m« h×nh ho¸ nhiÒu vÊn ®Ò øng dông, tõ ý nghÜa thùc tÕ c¸c

biÕn sè ph¶i nhËn gi¸ trÞ nguyªn. Ch¼ng h¹n, xÐt bµi to¸n lËp kÕ 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. §Ó s¶n xuÊt c¸c lo¹i s¶n phÈm nµy cÇn sö dông m lo¹i

=

=

1,

m j ;

n 1, )

nguyªn liÖu. BiÕt

ija ( i

- chi phÝ nguyªn liÖu lo¹i i ®Ó s¶n xuÊt ra mét s¶n

m= 1,

)

phÈm lo¹i j

ib ( i

n= 1,

j

- dù tr÷ nguyªn liÖu lo¹i i cña nhµ m¸y ;

jc (

) - tiÒn lQi tõ viÖc b¸n mét s¶n phÈm lo¹i j ;

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 hay

nan hoa xe ®¹p) th× 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

vµ gi¸ trÞ mét s¶n phÈm lµ cao (vÝ dô cç m¸y kÐo), th× tÝnh nguyªn cña biÕn sè

- 20 -

kh«ng thÓ bá qua. Ta thu ®−îc m« h×nh to¸n häc cña bµi to¸n lµ bµi to¸n quy

n

max

j

fi∑ c x j

= 1

j

n

ho¹ch nguyªn tuyÕn tÝnh sau:

1,

m

a x ij

j

= b i , i

∑

= 1

j

0

j

n= 1,

£

jx ‡

jx - nguyªn,

,

2.1.2.2. Bµi to¸n víi ®iÒu kiÖn logic

XÐt ®iÒu kiÖn logic d−íi d¹ng † hoÆc lµ - hoÆc lµ† . Nh÷ng ®iÒu kiÖn nh−

vËy th−êng gÆp khi chóng ta ph¶i lùa chän c¸c ph−¬ng ¸n s¶n xuÊt, x©y dùng. VÝ

dô, khi ph¶i quyÕt ®Þnh ¸p dông c¸c ph−¬ng thøc s¶n xuÊt míi vµo s¶n xuÊt

chóng ta th−êng gÆp t×nh huèng sau: hoÆc lµ kh«ng s¶n xuÊt s¶n phÈm j ( jx = 0)

jd

hoÆc lµ nÕu chÊp nhËn s¶n xuÊt nã th× ph¶i s¶n xuÊt víi sè l−îng kh«ng Ýt h¬n

jd lµ sè l−îng s¶n phÈm lo¹i j tèi thiÓu cÇn s¶n xuÊt ®Ó bï l¹i ®−îc nh÷ng chi

d‡

x

(

jx = 0, hoÆc lµ

j

j

phÝ cÇn bá ra khi ®−a ph−¬ng thøc s¶n xuÊt s¶n phÈm míi nµy vµo ho¹t ®éng ). † . Gi¶ sö biÕt Tøc lµ chóng ta gÆp ph¶i ®iÒu kiÖn † hoÆc lµ

jp cña biÕn

jx trong bµi to¸n ®ang xÐt. Khi ®ã ®−a vµo biÕn logic

neu chap nhan san xuat san pham j

y

j

0,

neu nguoc lai

 1, =  

cËn trªn

Ta cã thÓ ®−a rµng buéc l«gic nãi trªn vÒ hÖ rµng buéc t−¬ng ®−¬ng sau:

}0,1 {

x

0

x

0

jy ˛

j

p y j

j

j

d y j

j

- £ - ‡ , ,

2.1.2.3. Bµi to¸n víi biÕn sè rêi r¹c

Trong thùc tÕ cã tr−êng hîp biÕn sè chØ nhËn mét sè gi¸ trÞ nhÊt ®Þnh:

- 21 -

{

}

,....,

= x Q j j

q q 2, 1 j

j

q mj

˛

jx lµ quy m« c«ng suÊt cña nhµ m¸y ®iÖn cÇn x©y dùng ë ®Þa

VÝ dô nÕu

jQ lµ tËp c¸c quy m« c«ng suÊt tiªu chuÈn.

®iÓm j , th×

m

x

j

= ∑ q t ij ij

= 1

i

m

1

ij

=∑ t

= 1

i

rµng buéc nãi trªn lµ t−¬ng ®−¬ng víi hÖ B»ng c¸ch ®−a vµo c¸c biÕn phô ijt

}0,1 , { = i

1,

m

ijt

˛

PhÐp biÕn ®æi võa tr×nh bµy cã thÓ sö dông ®Ó ®−a ®iÒu kiÖn

x

d

jx - nguyªn

j

j

m

i

x

t

j

ij

£ £ , 0

= ∑ 2

=

0

i

m

1

ij

=∑ t

i

= 1

vÒ biÕn logic:

}0,1 , { = i

0,

m

ijt

=

m

˛

2

 log j d 

trong ®ã lµ sè thùc th× kÝ hiÖu [a ] ®Ó chØ sè nguyªn lín nhÊt

  (nÕu a mµ ta sÏ gäi lµ phÇn nguyªn cña a ), tøc lµ mäi bµi to¸n quy

kh«ng v−ît qu¸ a

ho¹ch nguyªn ®Òu cã thÓ ®−a vÒ bµi to¸n víi biÕn logic.

f x cã d¹ng ( )

2.1.2.4. Bµi to¸n víi chi phÝ cè ®Þnh

Trong nhiÒu bµi to¸n thùc tÕ hµm môc tiªu

- 22 -

n

f x (

)

f

(

x

)

j

j

= ∑

=

1

j

+

>

0

c x x , j j

j

)

f x ( j j

=

0

x j

d =  j 0, 

n= 1,

j

trong ®ã

jd > 0,

jd th−êng ®−îc hiÓu lµ chi phÝ cè ®Þnh cÇn thiÕt ®Ó ®−a

víi . C¸c sè

ph−¬ng thøc s¶n xuÊt j vµo ho¹t ®éng, nã kh«ng phô thuéc vµo c−êng ®é sö

dông ph−¬ng thøc nµy ( jx ).

jp lµ cËn trªn cña biÕn

jx trong bµi to¸n tèi −u ho¸

{min

f x

( ) :

x D˛ }

Gi¶ sö biÕt

,

n

+

khi ®ã bµi to¸n ®Æt ra cã thÓ dÉn vÒ bµi to¸n t−¬ng ®−¬ng sau

min

c x j

j

d t j

j

∑

=

1

j

fi ,

x D x

,

}0,1 , {

n= 1,

j

j

p t j

j

jt ˛

˛ £ , .

2.1.3. Mét sè m« h×nh phæ biÕn cña tèi −u rêi r¹c

Trong phÇn nµy ta tr×nh bµy mét sè m« h×nh ®Q ®ãng vai trß quan träng

trong viÖc ph¸t triÓn lÝ thuyÕt tèi −u rêi r¹c ®ång thêi còng lµ nh÷ng m« h×nh cã

nhiÒu øng dông réng rQi trong thùc tÕ cña tèi −u rêi r¹c.

2.1.3.1. Bµi to¸n c¸i tói

Mét nhµ th¸m hiÓm cÇn ®em theo mét c¸i tói cã träng l−îng kh«ng qu¸ b. Cã

ja vµ gi¸ trÞ sö

n= 1,

j

n lo¹i ®å vËt cã thÓ ®em theo. §å vËt thø j cã träng l−îng lµ

jc (

dông lµ ). Hái r»ng nhµ th¸m hiÓm cÇn ®em theo c¸c lo¹i ®å vËt nµo vµ

víi sè l−îng lµ bao nhiªu ®Ó cho tæng gi¸ trÞ sö dông cña c¸c ®å ®em theo lµ lín

nhÊt?

- 23 -

=

j

(

j

n ),1

jx lµ sè l−îng ®å vËt lo¹i

Gäi mµ nhµ th¸m hiÓm sÏ ®em theo. Khi

n

®ã, m« h×nh to¸n häc cña bµi to¸n cã d¹ng sau:

max

c x j

j

∑

= 1

j

n

fi

b

a x j

j

∑

= 1

j

£

0;

x

= , nguyen j

1,

n .

x

j

j

        

‡ -

T . XuÊt

2.1.3.2. Bµi to¸n ng−êi du lÞch

T T 1,

,...., n

Mét ng−êi du lÞch muèn ®i tham quan n +1 thµnh phè 0

ph¸t tõ 0T ng−êi du lÞch muèn ®i qua tÊt c¶ c¸c thµnh phè cßn l¹i, mçi thµnh phè

ijc lµ chi phÝ ®i tõ thµnh

n= 0,

i

j

n= 0,

®óng mét lÇn, råi quay trë l¹i thµnh phè xuÊt ph¸t. BiÕt

jT (

, ) hQy t×m hµnh tr×nh víi tæng chi phÝ lµ phè iT ®Õn thµnh phè

nhá nhÊt.

Ta cã thÓ thiÕt lËp t−¬ng øng 1-1 gi÷a hµnh tr×nh

....

T 0

T i 1

T i

2

T in

T 0

p =

,...,

fi fi fi fi fi

i ( , 1

i 2

i )n

+

+

+ + ...

0

víi mét ho¸n vÞ cña n sè tù nhiªn 1,2,..,n. §Æt

c f p = 1 ( ) 0 i

c i i 1 2

c i n

i 1 n

c i n

p =

,...,

-

i ( , 1

i 2

i )n

vµ kÝ hiÖu P P P P lµ tËp tÊt c¶ c¸c ho¸n vÞ cña n sè tù nhiªn 1,2,...,n.

Khi ®ã bµi to¸n ng−êi du lÞch cã thÓ ph¸t biÓu d−íi d¹ng bµi to¸n tèi −u

rêi r¹c sau

f p (

)

fi min,

PPPP p ˛

,....,

A lµ mét hä c¸c tËp con cña tËp m phÇn tö X. Hái

A A , 1 2

n

2.1.3.3. Bµi to¸n ph©n ho¹ch } Gi¶ sö FFFF = {

r»ng cã thÓ t×m ®−îc F(cid:204) FFFF sao cho

X

F˛

j

A i

,

= ∪

A i

= ˘ A˙ j

A A ,i

j

A F i

„ , i , , ˛

- 24 -

=

X

{ 1, 2,...,

} m

A

a= (

(tøc lµ c¸c tËp trong F t¹o thµnh mét ph©n ho¹ch cña tËp X). Kh«ng gi¶m tæng

)ij

. §−a vµo ma trËn liªn thuéc , víi c¸c qu¸t ta coi r»ng

phÇn tö ®−îc x¸c ®Þnh nh− sau

khi i

A

j

a

ij

˛

0,

khi i

A

j

 1, =  

=

=

c

A=

i

1,

m j ,

1,

n

ˇ

jA . §−a vµo biÕn sè

j

j

. KÝ hiÖu = sè phÇn tö cña tËp

neu A

F

x

j

0,

j neu nguoc lai

 1, =  

n= 1,

j

˛

n

. Khi ®ã bµi to¸n ph©n ho¹ch cã thÓ dÉn vÒ bµi to¸n tèi −u rêi r¹c sau

max,

c x j

j

∑

= 1

j

n

=

=

1,

i

1,

m

a x ij

j

∑

j

= 1

fi

}0,1 , { = j

1,

n

jx

˛ .

Râ rµng nÕu gi¸ trÞ tèi −u cña bµi to¸n võa viÕt b»ng m th× ta cã tr¶ lêi

kh¼ng ®Þnh cho bµi to¸n ph©n ho¹ch, ng−îc l¹i bµi to¸n ph©n ho¹ch kh«ng cã lêi

gi¶i.

Mét tr−êng hîp riªng cña bµi to¸n tèi −u rêi r¹c lµ bµi to¸n quy ho¹ch

nguyªn tuyÕn tÝnh khi ta ®−a thªm vµo bµi to¸n quy ho¹ch tuyÕn tÝnh tæng qu¸t

n

=

®iÒu kiÖn c¸c biÕn sè lµ nguyªn. D¹ng tæng qu¸t cña bµi to¸n.

x

,...,

f x =

x x ( , 1 2

x )n

c x j

j

∑

=

1

j

fi sao cho hµm ( ) min víi hÖ ®iÒu T×m vect¬

kiÖn

- 25 -

n

I

a x ij

j

b i , i

1

∑

= 1

j

n

£ ˛

I

a x ij

j

b i , i

2

∑

= 1

j

n

=

‡ ˛

I

3

a x ij

j

b i , i

∑

=

i

j

        

˛

0

j

n= 1,

jx

‡ , nguyªn,

, I, I2 (cid:204) I, I3 (cid:204) I; I = {1,2,..., m}; I1 ¨ I2 ¨ I3 = I; Ii ˙ I k = ˘

1,3.

Víi I1 (cid:204) i k = , aij , cj, bi lµ c¸c h»ng sè cho tr−íc.

ë ch−¬ng 2 chóng ta sÏ tr×nh bµy nh÷ng c¬ së lý thuyÕt vµ c¸c thuËt to¸n

gi¶i bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh.

2.2. Mét sè thuËt to¸n gi¶i bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh

2.2.1. ThuËt to¸n c¾t Gomory

T− t−ëng cña thuËt to¸n :

n

XÐt bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh d¹ng chÝnh t¾c (bµi to¸n II)

min

c x j

j

∑

= 1

j

n

=

=

1,

m

(2.6)

a x ij

j

b i , i

j

= 1

fi (2.5) f(x) =

0,

1,

(2.7)

x

= j

n

=

j

1,

n

 ∑    

‡

j jx - nguyªn ,

(2.8)

n

Khi bá ®i ®iÒu kiÖn (2.8) ta ®−îc bµi to¸n (III):

min

c x j

j

∑

= 1

j

n

=

=

1,

m

a x ij

j

b i , i

= 1

j

fi f(x) =

x

0,

= j

j

 ∑    

=

‡

1, n }0

{ = xD

:

Ax

xb ,

‡ miÒn chÊp nhËn ®−îc cña bµi to¸n (III). KÝ hiÖu:

- 26 -

kx .

Gi¶ sö ë b−íc k ta thu ®−îc ph−¬ng ¸n tèi −u

kx - nguyªn th×

kx lµ ph−¬ng ¸n tèi −u cña bµi to¸n (II). ThuËt to¸n

NÕu

kÕt thóc.

Ng−îc l¹i, x©y dùng rµng buéc tuyÕn tÝnh Lk(x) = 〈 pk, x〉 - dk ≤ 0 (2.9) vµ bæ sung vµo hÖ rµng buéc x¸c ®Þnh Dk (HÖ rµng buéc ë cña bµi to¸n ë b−íc k) ta thu ®−îc :

D

D

:

}0

=+

k

1

k

{ ( ) xLx k

£ ˙ , chuyÓn sang b−íc k+1.

Rµng buéc tuyÕn tÝnh (2.9) cÇn ph¶i ®−îc x©y dùng sao cho tho¶ mQn hai

tÝnh chÊt c¬ b¶n sau:

• Mäi ph−¬ng ¸n chÊp nhËn ®−îc cña bµi to¸n (II) ®Òu ph¶i tho¶ mQn nã

(tøc lµ nã kh«ng c¾t bá bÊt cø ph−¬ng ¸n chÊp nhËn ®−îc nµo cña bµi

) 0>k

to¸n xuÊt ph¸t II).

kx cña bµi to¸n

( k xL

• , nghÜa lµ nã ph¶i c¾t bá ph−¬ng ¸n tèi −u

quy ho¹ch tuyÕn tÝnh cña b−íc tr−íc khái miÒn rµng buéc cña bµi to¸n

quy ho¹ch tuyÕn tÝnh ë b−íc sau.

Rµng buéc (2.9) tho¶ mQn hai tÝnh chÊt võa nªu sÏ ®−îc gäi lµ mét l¸t c¾t

hîp c¸ch. Sau mçi b−íc, nÕu ch−a gÆp ph−¬ng ¸n tèi −u cña bµi to¸n (II) th× ta

l¹i bæ sung mét l¸t c¾t hîp c¸ch vµo hÖ rµng buéc cña bµi to¸n (III) ®Ó khoanh

vïng tËp ph−¬ng ¸n tèi −u cña bµi to¸n (III) vµ t×m ph−¬ng ¸n cña bµi to¸n (II).

X©y dùng l¸t c¾t cña bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh.

Gi¶ sö ta ®Q gi¶i bµi to¸n quy ho¹ch tuyÕn tÝnh (III) chóng ta thu ®−îc

jA

(

j

n= 1, )

ph−¬ng ¸n c¬ së tèi −u *x vµ c¬ së t−¬ng øng víi nã lµ B. Kh«ng gi¶m tæng qu¸t

ta coi r»ng B = (A1, A2,..., Am); trong ®ã lµ cét thø j cña ma trËn A.

Sö dông biÓu diÔn biÕn c¬ së qua biÕn phi c¬ së ta cã:

1

1

x

BbB

Nx

B

N

- - - (2.10)

1

=

=

=

=

=

)

(

)

= (

2

b

b b , 1

b ,..., m

B b-

1 B A

a i : ij

1,

m j ,

1,

n

- ®−a vµo c¸c kÝ hiÖu: ,

Ta viÕt l¹i (2.10) d−íi d¹ng to¹ ®é:

- 27 -

n

)

i m= 1,

= + x b i i

x j

( -∑ a ij

= + 1 j m

, (2.11)

b i

,0 = i

,1

m

rb lµ kh«ng nguyªn

‡ .Gi¶ sö

)mr £

=

Do B lµ c¬ së tèi −u nªn ( £1

=

rj

rj

a

a

,

= + j m n

1,

r

r

f

b

rjf

0

 

 

b 

  ,

- - §Æt: .

rb kh«ng nguyªn nªn 0 < f0 < 1. Tõ (2.11) víi i = r ta cã.

n

n

=

+

+

Do

r

ij

x

b

f

(

+ )

x

f

(

x

)

r

0

j

rj

j

∑

 

 

∑   a 

= + 1 j m

= + 1 j m

- - ( 2.12)

n

n

Tõ ®ã suy ra:

r

ij

f

f

(

b

a

(

x

)

0

rj

= - + ) x j

x r

j

∑

∑

+  

 

 

 

= + 1 j m

= + 1 j m

- - - - (2.13)

VÕ ph¶i cña (2.13) sÏ lµ nguyªn nÕu nh− x lµ ph−¬ng ¸n chÊp nhËn ®−îc

n

cña bµi to¸n (II), do ®ã vÕ tr¸i cña (2.13) còng ph¶i lµ mét sè nguyªn tøc lµ:

(

)

x

f 0

rj

j

-∑ f

= + 1 j m

=

- - - nguyªn. (2.14)

rj

rj

a

n= 1,

j

rjf

jx ‡

a 

  ‡

n

- MÆt kh¸c do 0 vµ 0 ; nªn

f

(

x

)

0

rj

j

-∑ f

= + 1 j m

n

- - ‡ - 0f

f

(

x

)

0

rj

j

0f < 1 nªn

0f > -1 (2.15)

-∑ f

= + j m 1

- - ‡ - Mµ do 0 <

n

(

)

-=

Tõ (2.14) - (2.15) ta suy ra

( ) xL

f

f

x

0

rj

j

0 (2.16)

∑

+= 1 mj

‡ - -

*

=

2

m

b b ( , 1

,...,

b

, 0,...., 0)

x

Nh− vËy mäi ph−¬ng ¸n chÊp nhËn ®−îc cña bµi to¸n (II) ®Òu tho¶ mQn

râ rµng (2.16) cßn ph−¬ng ¸n tèi −u cña bµi to¸n (III)

lµ kh«ng tho¶ mQn (2.16). VËy (2.16) lµ mét l¸t c¾t.

- 28 -

§Ó gi¶i bµi to¸n (III) víi rµng buéc bæ sung (2.16) (gäi lµ bµi to¸n më

réng) ta cã thÓ ¸p dông thuËt to¸n t¸i tèi −u ho¸. §Ó lµm viÖc ®ã ta thªm vµo biÕn

1nx + ‡

n

n

phô 0 chuyÓn ( 2.16) vÒ d¹ng ®¼ng thøc.

(

x

)

f

(

x

)

f

rj

j

0

rj

j

0

1nx + = 0 hay

1nx + =

-∑ f

-∑ f

= + j m 1

= + j m 1

- - - - -

1+nx

lµ biÕn c¬ së. Ta tiÕp tôc gi¶i bµi to¸n (II) víi c¬ së ®−îc bæ Coi biÕn

1+nx

sung thªm biÕn .

VÝ dô: XÐt bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh

f x = ( )

+ 3x 1

x 2

+

=

+

5

2

x 5 =

- fi min.

3

3

2

x 3

=

+

-

10

5

x 2 + x 2 x

4

x 4

x 1 x 1 x 1

-

x

2 = j

0;

1,5

j

      

j =

1, 5

‡

jx - nguyªn,

j =

1,5

.

jx - nguyªn

Gi¶i bµi to¸n trªn bá qua ®iÒu kiÖn theo ph−¬ng ph¸p ®¸nh thuÕ.

=

+

5

2

fM(x,u) = -3x1 + x2 + M u6 +

3

2

3

+

-

5

4

u

10

x 1 x 1 x 1

x 2 + x 2 x 2

x 5 = x 3 + x 4

= 6

    

0

j =

1, 5

-

jx ‡

u ‡

0

6

,

C¬ së Ph−¬ng ¸n -3 1 0 0 0 M

cj c¬ së B A1 A2 A3 A5 A6 (x,u) A4

0 A5 2 5 1 0 0 1 0

0 A3 3 -2 1 0 0 0 [3]

A6 M 10 4 0 -1 0 1 5

3 -1 0 0 0 0

5 4 0 -1 0 0

- 29 -

0 0 A5 3 0 7/3 -2/3 0 1

1 -3 A1 1 0 -2/3 1/3 0 0

0 M A6 5 1 -5/3 -1 0 [22/3]

0 0 -1 0 0 1

0 0 22/3 -5/3 -1 0

0 31/22 -3/22 0 0 A5 1 [7/22]

1 16/11 2/11 0 -3 A1 0 -1/11

0 15/22 -5/22 1 1 0 -3/22 A2

0 -17/22 27/121 0 0

0 0 A4 31/7 1 -3/7 22/7 0

1 -3 13/7 0 1/7 2/7 0 A1

0 1 9/7 0 -2/7 3/7 1 A2

1

b =

0 0 -5/7 -3/7 0

13 7

Trong ph−¬ng ¸n tèi −u c¸c biÕn c¬ së ®Òu kh«ng nguyªn. Ta chän

=

kh«ng nguyªn x©y dùng l¸t c¾t theo (2.16)

f

0

13 7

13 - = 1 7

6 7

13   7 

 =  

-

=

L x ( )

(

)

(

) 0

x 3

x 5

6 1 7 7

2 7

- - - - - ‡

6x ‡

§−a vµo biÕn 0 ta chuyÓn rµng buéc vÒ d¹ng ®¼ng thøc:

=

(

)

(

)

x 6

x 3

x 5

2 7

6 7

1 7

- - - - - . ViÕt rµng buéc nµy vµo cuèi b¶ng sau:

C¬ së Ph−¬ng -3 1 0 0 0 0

¸n cj c¬ së A1 A2 A3 A4 A5 A6

31/7 0 A4 0 0 -3/7 1 22/7 0

13/7 -3 A1 1 0 1/7 0 2/7 0

9/7 1 A2 0 1 -2/7 0 3/7 0

-6/7 0 A6 0 0 -1/7 0 1 [-2/7]

0 0 -5/7 0 -3/7 0

- 30 -

0 11 1 0 A4 -5 0 0 [-2]

0 1 0 -3 A1 1 1 0 0

0 3/2 0 1 A2 0 0 1 -1/2

0 A5 3 0 0 0 1/2 1 -7/2

0 0 0 -1/2 0 -3/2

5/2 0 0 -1/2 1 0 -11/2 0 A3

1 1 0 0 0 0 1 -3 A1

5/4 0 1 -1/4 0 0 -5/4 1 A2

0 A5 7/4 0 0 1/4 0 1 -3/4

5

0 0 -1/4 0 0 -17/4

ib kh«ng nguyªn i = 2,3,5. Ta chän

b = ®Ó lËp l¸t c¾t thø 2.

7 4

Do

X©y dùng l¸t c¾t theo (2.16) ta thu ®−îc:

(

) {(

) 0

x 4

x 6

3 1 4 4

3 ) 4

3 4

-   

 }(  

- - - - - - - ‡ L(x) =

=

L x ( )

(

)

(

) 0

x 4

x 6

1 4

- - - - - ‡

3 1 4 4 7x ‡

§−a vµo biÕn 0 chuyÓn rµng buéc trªn vÒ d¹ng ®¼ng thøc ta thu ®−îc:

=

(

)

(

)

x 4

x 6

x 7

1 4

3 1 4 4

- - - - - . ViÕt rµng buéc vµo cuèi b¶ng sau.

C¬ 1 0 0 0 0 0 Ph−¬ng -3

së B ¸n cj c¬ së A1 A2 A3 A4 A5 A6 A7

5/2 A3 0 0 0 1 -1/2 0 -11/2 0

1 A1 -3 1 0 0 0 0 1 0

5/4 A2 1 0 1 0 -1/4 0 -5/4 0

7/4 A5 0 0 0 0 1/4 1 -3/4 0

-3/4 A7 0 0 0 0 0 -1/4 1 [-1/4]

0 0 0 -1/4 0 -17/4 0

- 31 -

-2 -5 0 0 1 0 0 4 A3 0

0 1 0 0 0 0 1 1 A1 -3

-1 -1/4 0 0 0 1 0 2 A2 1

1 -1 1 0 0 0 0 1 0 A5

A4 0 3 0 0 0 1 0 1 -4

0 0 0 0 0 -13/4 -1

Tõ b¶ng ®¬n h×nh cña bµi to¸n më réng, ta gi¶i b»ng thuËt to¸n ®¬n h×nh

*x = (1,2,4,3,1),

*( f x = -1. )

®èi ngÉu vµ thu ®−îc ph−¬ng ¸n tèi −u:

2.2.2. Ph−¬ng ph¸p nh¸nh cËn (ThuËt to¸n Land - Doig) gi¶i bµi to¸n quy

ho¹ch nguyªn tuyÕn tÝnh

{

2.2.2.1. S¬ ®å tæng qu¸t

min

XÐt bµi to¸n tèi −u rêi r¹c tæng qu¸t } f x x D˛ ( ) : (2.17)

trong ®ã D lµ tËp h÷u h¹n phÇn tö.

Do D lµ tËp h÷u h¹n nªn bµi to¸n ®Æt ra lu«n cã ph−¬ng ¸n tèi −u mµ ta sÏ

)Ag (

kÝ hiÖu lµ *x .

g

XÐt hµm sè x¸c ®Þnh trªn 2 \D ˘ :

: 2 \D

ℝ

˘ fi

tho¶ mQn hai ®iÒu kiÖn:

{

g ) (

i

A

) min

f x

( ) :

} x A

g‡

£ ˛ ;

g ) (

ii

)

(

)

D

A 1

A 2

A 1

A 2

)Ag (

(cid:204) (cid:204) , nÕu (2.18)

)Ag (

§Þnh nghÜa. Gi¸ trÞ trªn tËp A D(cid:204) ®−îc gäi lµ cËn d−íi cña tËp A.

{

min

} f x x A˛ ( ):

)Ag (

ViÖc lùa chän phô thuéc vµo tõng bµi to¸n cô thÓ. Th«ng th−êng ta chän

sao cho viÖc tÝnh nã dÔ dµng h¬n gi¶i bµi to¸n vµ sao cho

nã cµng gÇn víi gi¸ trÞ tèi −u cña bµi to¸n nµy. RÊt tiÕc lµ trong phÇn lín c¸c

,....,

tr−êng hîp hai yªu cÇu nµy lµ ®èi lËp nhau.

(1) (1) D D , 1 2

(1) D : n 1

Gi¶ sö ta cã mét ph©n ho¹ch tËp D thµnh c¸c tËp con

- 32 -

n 1

= ˘

D

D

,

∩

(1) i

= ∪

D

D

l

(1 ) k

(1 ) l

i

= 1

g

„ (2.19) , k

=

{ g

}

min

(

) :1

(

)

) min

*( f x

f x

( ) :

} x D

(1) D i

= i n 1

(1) D i 0

*

‡ £ £ ˛ Tõ (2.18) ta cã { (2.20)

f x ( )

f x (

)

x bÊt k× so víi ph−¬ng ¸n tèi −u *x theo c«ng thøc sau:

1

*

g

e

- Tõ ®ã cã thÓ ®¸nh gi¸ ®é lÖch gi÷a ph−¬ng ¸n chÊp nhËn ®−îc

f x ( )

(

D

x ( )

f x ( )

f x (

)

= (1) ) i 0

e

1( )x

£ - - (2.21)

e ®èi víi bµi to¸n cô thÓ,

0

NÕu n»m trong kho¶ng chÝnh x¸c ®Þnh tr−íc

1

e

e£

( )x

tøc lµ nÕu

0

(2.22)

e

th× x cã thÓ coi lµ lêi gi¶i gÇn ®óng.

f x ( )

* f x (

)

- £ §Þnh nghÜa. Ph−¬ng ¸n chÊp nhËn ®−îc x D˛ tho¶ mQn

®−îc gäi lµ ph−¬ng ¸n e - tèi −u cña bµi to¸n.

(1)

sao cho

f x ( )

)i

0

Cßn nÕu ta t×m ®−îc x D˛ Dg= ( (2.23)

f x ( )

* f x (

)

(1)

£ th× tõ (2.21) suy ra tøc lµ x lµ ph−¬ng ¸n tèi −u.

iD lµ cã triÓn väng chøa ph−¬ng ¸n tèi −u

0

(1)

Trªn quan ®iÓm nay ta thÊy tËp

i

iD ,

i 0

„ h¬n c¸c tËp cña ph©n ho¹ch (2.19). NÕu nh− chóng ta kh«ng cã thªm

g

=

th«ng tin nµo kh¸c vÒ ph−¬ng ¸n tèi −u cña bµi to¸n (2.17) th× ®iÒu kiÖn

{ g

}

(

) min

(

) :1

i

(1) D i

n 1

(1) D i 0

,....,

£ £ (2.24)

D cña ph©n

(1) D D , 1

(1) 2

(1) n 1

(1)

sÏ ®−îc nhËn lµm quy t¾c chän trong sè c¸c tËp

iD ®Ó ®iÓm diÖn tr−íc.

0

(1)

ho¹ch (2.19) tËp

iD ra thµnh c¸c tËp con:

0

)

l i ( 0

Gi¶ sö b©y giê ta l¹i cã thªm ph©n ho¹ch tËp

D˙

l

(2) D i

= ∪

(2) D k

= ˘ (2) l

(1) D i 0

= 1

i

„ , , k .

Khi ®ã c¸c tËp hîp

- 33 -

,...,

,

,...,

,

,....,

D

(1) D 1

(2) D 1

)

(1) D i 1 0

(1) D + i 1 0

(1) D n 1

(2) l i ( 0

-

n

2

D

D

sÏ t¹o thµnh mét ph©n ho¹ch míi cña tËp D, mµ sau khi ®æi kÝ hiÖu ta cã:

( 2 ) i

= ∪

=

1

i

(2)

(2.25)

iD cã cËn

0

§èi víi ph©n ho¹ch míi nµy theo tiªu chuÈn (2.24) ta l¹i t×m ra tËp

( 2 )

d−íi nhá nhÊt. NÕu tiªu chuÈn (2.22) hay (2.23) ch−a ®−îc tho¶ mQn th× ta l¹i

iD . Tãm l¹i ta cã l−îc ®å sau:

0

tiÕp tôc qu¸ tr×nh víi tËp

(0)

S¬ ®å thuËt to¸n nh¸nh cËn.

D= ,

n = . Chän 1

e lµ ®é chÝnh x¸c cña lêi gi¶i

1D

0

0

B−íc chuÈn bÞ. §Æt

cÇn t×m.

B−íc k = 0, 1,....

kn

D

= ∪ k ( ) D i

= 1

i

g

=

Gi¶ sö ë ®Çu b−íc lÆp nµy ta ®Q cã ph©n ho¹ch

{ g

}

(

) min

(

) :1

k ( ) D i

i n k

k ( ) D i 0

£ £ T×m

k

e

=

g

NÕu t×m ®−îc x D˛ tho¶ mQn

x ( )

f x ( )

(

e )

0

k ( ) D i 0

- £

e - tèi −u, thuËt to¸n kÕt thóc.

0

( )k

Th× x lµ ph−¬ng ¸n

iD ta thu ®−îc ph©n ho¹ch cña tËp D

0

Ng−îc l¹i tiÕn hµnh ph©n ho¹ch tËp

1k + .

+

k

)

1)

k

cho b−íc

{

}

{

}

min

:1

i

min

:1

i

( D i

n k

( D i

n k

+ 1

£ £ ‡ £ £ Do D lµ tËp h÷u h¹n vµ

Nªn víi k ®ñ lín ta sÏ thu ®−îc ph©n ho¹ch tËp D thµnh c¸c tËp con chØ gåm

( )k

mét phÇn tö. Tõ ®ã suy ra tÝnh h÷u h¹n cña s¬ ®å võa tr×nh bµy.

iD rÊt cã thÓ chóng sÏ t×m ®−îc c¸c

0

Chó ý: Trong qu¸ tr×nh ph©n ho¹ch tËp

ph−¬ng ¸n chÊp nhËn ®−îc cña bµi to¸n. KÝ hiÖu x lµ ph−¬ng ¸n chÊp nhËn ®−îc

t×m ®−îc. Ta sÏ gäi x lµ lêi gi¶i tèt nhÊt hiÖn cã hay gäi v¾n t¾t lµ kØ lôc, cßn gi¸

- 34 -

=

f

f x ( )

(

)k

trÞ sÏ gäi lµ gi¸ trÞ kØ lôc. Gi¶ sö ë b−íc k ta ®Q cã kØ lôc x, khi ®ã ta cã

iD cã gi¸ trÞ cËn d−íi lµ lín h¬n

thÓ lo¹i khái qu¸ tr×nh ®iÓm diÖn tÊt c¶ c¸c tËp

hoÆc b»ng gi¸ trÞ kØ lôc.

Khi ¸p dông s¬ ®å võa tr×nh bµy ®èi víi mét bµi to¸n tèi −u rêi r¹c cô thÓ ta

( )k

cÇn ph¶i x©y dùng ®−îc hai thñ tôc chÝnh sau:

iD ra thµnh c¸c tËp con (cßn gäi lµ thñ tôc

0

• Thñ tôc ph©n ho¹ch tËp

)Ag (

ph©n nh¸nh);

. • Thñ tôc tÝnh cËn d−íi

2.2.2.2. Mét ¸p dông cña l−îc ®å nh¸nh cËn vµo viÖc gi¶i bµi to¸n quy ho¹ch

nguyªn tuyÕn tÝnh lµ thuËt to¸n Land - Doig. S¬ ®å cña thuËt to¸n

n

=

=

Gi¶ sö ta cÇn gi¶i bµi to¸n QHTT nguyªn (P):

( ) f x

t c x

min

c x j

j

∑

= 1

j

n

=

fi

,1

m

,1=

n

j

xa ij

j

, ib i

0jx ‡

∑

= 1

j

£ D ={ ; , nguyªn, }

)¢ P lµ bµi to¸n:

n

=

)

( f x

min

j

fi∑ c x j

= 1

j

n

=

Ta kÝ hiÖu (

,1

m

0

j

,1=

n

xa ij

j

, ib i

jx

∑

=

1

j

)¢ P cã hai kh¶ n¨ng:

f=D

£ ‡ D¢ ={ ; , }

B−íc chuÈn bÞ: Gi¶i bµi to¸n ( f=¢D NÕu th× . Bµi to¸n kh«ng cã ph−¬ng ¸n.

0x th×:

NÕu t×m ®−îc ph−¬ng ¸n tèi −u

0x lµ nguyªn th×

0x còng lµ ph−¬ng ¸n tèi −u cña (P).

• NÕu

0x kh«ng nguyªn th× ®Æt:

• NÕu

0x ; ta chia D thµnh hai

m(D) = [ min f(x)] = [f (x0)] (sè nguyªn nhá nhÊt kh«ng bÐ h¬n f(x0))

rx lµ thµnh phÇn kh«ng nguyªn nµo ®ã cña

Gi¶ sö 0

tËp b»ng c¸ch ®−a vµo c¸c rµng buéc lo¹i trõ nhau nh− sau:

- 35 -

=

:

x D x r

1 D 1

}  

0 x  r

=

˛ £

{ {

:

} 1

1 D 2

x D x r

+ 0 x  r

 

f=

˛ ‡

D

= DD

1 1 D

1 2

1 1 D

1 2

1

˙ ¨ Khi ®ã: vµ .

)P lµ bµi to¸n: 1(

n

=

KÝ hiÖu

( ) xF

t xc

min,

xc j

j

1 Dx 1

= ∑

j

= 1

1

)P lµ bµi to¸n: 2(

n

=

˛ fi

( ) xF

t xc

min,

Dx

xc j

j

1 2

= ∑

= 1

j

˛ fi

(

), (

)

P lµ c¸c bµi to¸n QHTT nguyªn. Gi¶i c¸c bµi to¸n(

1 P 1

1 2

)1 1P

)1 2P

1

jx nguyªn, §Ó

)P vµ ( 1(

)1 2P bá ®i ®iÒu kiÖn

¢ ¢ vµ ( , ®ã

ta cã thÓ gÆp ph¶i c¸c t×nh huèng sau ®©y: t×m

1

1

= ˘

)

{ } 1, 2

i

,

iD khái qu¸ tr×nh tiÕp theo v×

iD

f=1

¢ ˛ th× lo¹i lµ c¸c bµi to¸n QHTT t−¬ng øng víi ( )1 ( )1 1Dm 2Dm vµ 1. Ph¸t hiÖn (

iD

.

ix nguyªn, khi ®ã

ix còng lµ ph−¬ng ¸n tèi

)i

)1

2. T×m ®−îc ph−¬ng ¸n tèi −u

iP

−u cña bµi to¸n( . Ta tÝnh (

f x , gäi ®ã lµ mét kû lôc vµ lo¹i nã khái )1 2P

1P vµ ( )1

qu¸ tr×nh tiÕp theo. NÕu t×m ®−îc kû lôc cña c¶ hai bµi to¸n (

th× chØ viÖc so s¸nh chóng ®Ó t×m ra ph−¬ng ¸n tèi −u.

=

f x (

)i

ix kh«ng nguyªn )i f x ).

( )1 im D

 

 (sè nguyªn nhá nhÊt kh«ng bÐ h¬n ( 

th× cËn d−íi 3. T×m ®−îc ph−¬ng ¸n tèi −u

Qu¸ tr×nh cø thÕ tiÕp tôc.

B−íc k: Gi¶ sö b−íc (k - 1) ta ®Q t×m ®−îc mét ph©n ho¹ch cña D gåm k tËp:

- 36 -

1

1

1-k

1

-kD ,

3

kD vµ ®Q gi¶i c¸c bµi to¸n QHTT (bá ®i ®iÒu kiÖn x

1

2

)'1

)'1

kP -

kP -

-kD ,..., -kD , nguyªn) t−¬ng øng lµ: (

2

1

)'1k kP -

1-k

- 1k

) +¥=

, ( ,..., ( vµ thu ®−îc kÕt qu¶ lµ:

jD lµ rçng, j = {1,2,...,k}; ta coi

( jDm

1. Ph¸t hiÖn mét sè tËp .

1-k

2. T×m ®−îc mét sè kû lôc (ph−¬ng ¸n tèi −u nguyªn).

jD cßn l¹i.

*

1

3. T×m ®−îc cËn d−íi cña c¸c tËp

,

x D -

k s

˛ ThuËt to¸n ë b−íc k thùc hiÖn nh− sau: )* ( f x T×m kû lôc nhá nhÊt, gi¶ sö ®ã lµ:

( )* f x . NÕu

Lo¹i bá tÊt c¶ c¸c tËp rçng vµ c¸c tËp cã cËn d−íi lín h¬n

( )* f x th×

*x lµ ph−¬ng ¸n tèi −u cña

kh«ng cßn tËp nµo cã cËn d−íi nhá h¬n

)*

bµi to¸n (P). ThuËt to¸n kÕt thóc.

( f x th× ta ph©n nh¸nh t¹i ®Ønh

NÕu cã nh÷ng tËp cã cËn d−íi nhá h¬n

nµo cã cËn d−íi nhá nhÊt.

V× b¶n sè cña D lµ h÷u h¹n nªn thuËt to¸n kÕt thóc sau mét sè h÷u h¹n b−íc.

VÝ dô: Gi¶i bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh (P) sau ®©y b»ng thuËt to¸n

min.

4

1

2

x

2

- £ -

4

11

2

x

Land - Doig: f(x) = -x1 - x2 fi + x 1 + £

2 1 / 2

x 1 x 1

    - 

0

£ -

x x ‡ 2,

, nguyªn. 1

)¢ P bá ®i ®iÒu kiÖn nguyªn cña c¸c biÕn sè

B−íc chuÈn bÞ. Gi¶i bµi to¸n (

0

=

=

=

ta ®−îc ph−¬ng ¸n tèi −u:

[

]

m D (

f x ) min ( )

f x (

)

4

3 5 2 2

-  

 = -  

=

=

1

- x0 = (3/2, 5/2). .

0x kh«ng nguyªn vµ cã:

0 x 1

0 x 1

 

 

3 = ⇒ 2

3      2

B−íc 1. V× . Ta chia D

thµnh 2 tËp:

- 37 -

=

{

/

} 1

1 D 1

x D x 1

=

˛ £

{

} 2

1 D 2

x D x 1/

˛ ‡

)1 1P

1

=

¢ ta ®−îc ph−¬ng ¸n tèi −u: Gi¶i bµi to¸n (

1,

1 x

)1

f x (

)

1

2

( m D 1

 

 

 =  

 = -  

3  = -  2 

- vµ t×m ®−îc .

3 2 Gi¶i bµi to¸n (

   )1 2P

1

=

¢ ta ®−îc ph−¬ng ¸n tèi −u:

)

1 f x (

)

2

3

x =

(2,

)

1 m D ( 2

  

  

3 2

 = -  

3  = -  2 

1

)

m D< (

)

- vµ t×m ®−îc

1 m D ( 2

1 1

2D

1

1 2

x = kh«ng nguyªn nªn ta ph©n ho¹ch tËp

Do . Nªn ta ph©n nh¸nh t¹i

2D thµnh 2 tËp:

3 2

B−íc 2. Do

/

2 D 1

1 x D x 2 2

£

{ = ˛ { = ˛

} 1 } 2

/

2 D 2

1 x D x 2 2

2

‡

)P ¢ ta thu ®−îc ph−¬ng ¸n tèi −u: 1(

2

=

[

)

] )

3

x =

(

,1)

Gi¶i bµi to¸n

2 m D ( 1

f x ( 2

9 4

 = -  

9  - = - 1  4 

2

2

2

)m D = +¥

vµ t×m ®−îc .

)D = ˘ 2(

2(

)P ¢ ta thÊy 2(

2

2

<

)

)

Gi¶i bµi to¸n vµ

m D ( 1

1 m D ( 1

1D .

2

Do nªn ta ph©n nh¸nh t¹i

x = kh«ng nguyªn nªn ta ph©n ho¹ch tËp

1D thµnh hai tËp:

2 1

2

=

B−íc 3 :Do

;

3 D 1

2

3

=

˛ £

9 4 { x D x 1 1 {

;

} 2 } 3

x D x 1 1

D 2

˛ ‡

(

3 )P 1

3

3

=

[ = -

)

f x (

)

] - = - 2 1

3

x =

( 2 ,1)

¢ Gi¶i bµi to¸n ta thu ®−îc ph−¬ng ¸n tèi −u:

3 m D ( 1

 

 

3

3

m D = ˘

(

)

vµ t×m ®−îc .

2

)P ¢ ta thÊy 2(

. Gi¶i bµi to¸n

- 38 -

3

3

3

=

= -

(

)

)

x =

) 2,1

( f x

3

( 3 m D 1

1D ta ghi ®−îc kû lôc:

T¹i . tho¶ mQn ®iÒu

=

= -

(

)

) 2,1 ;

* x

( * f x

3

kiÖn nguyªn nªn nã lµ ph−¬ng ¸n tèi −u cña bµi to¸n ®Q cho, thuËt to¸n kÕt thóc.

.

2.2.3. Bµi to¸n c¸i tói vµ ph−¬ng ph¸p ph−¬ng tr×nh truy to¸n cña quy

ho¹ch ®éng gi¶i bµi to¸n c¸i tói

Bµi to¸n c¸i tói lµ bµi to¸n t×m cùc ®¹i (cùc tiÓu) cña hµm môc tiªu tuyÕn tÝnh

trong sè nguyªn kh«ng ©m víi mét rµng buéc tuyÕn tÝnh d¹ng ®¼ng thøc hoÆc

bÊt ®¼ng thøc. Néi dung thùc tÕ cña bµi to¸n ®−îc m« t¶ nh− sau:

2.2.3.1.Néi dung thùc tÕ cña bµi to¸n c¸i tói

Mét nhµ th¸m hiÓm cÇn ®em theo mét c¸i tói cã träng l−îng kh«ng qu¸ b. Cã

n= 1,

j

n lo¹i ®å vËt cã thÓ ®em theo. §å vËt thø j cã träng l−îng lµ aj vµ gi¸ trÞ sö dông

). Hái r»ng nhµ th¸m hiÓm cÇn ®em theo c¸c lo¹i ®å vËt nµo vµ víi lµ cj (

sè l−îng lµ bao nhiªu ®Ó cho tæng gi¸ trÞ sö dông cña c¸c ®å ®em theo lµ lín

nhÊt.

=

j

(

j

n ),1

M« h×nh to¸n häc cña bµi to¸n.

jx lµ sè l−îng ®å vËt lo¹i

Gäi mµ nhµ th¸m hiÓm sÏ ®em theo. Khi

n

®ã, m« h×nh to¸n häc cña bµi to¸n cã d¹ng sau:

max

c x j

j

∑

= 1

j

n

fi

b

a x j

j

∑

= 1

j

£

x

0;

x

= , nguyen j

1,

n .

j

j

        

‡ -

Bµi to¸n c¸i tói cßn ®−îc ph¸t biÓu tõ mét t×nh huèng thùc tÕ kh¸c nh− sau

Mét nhµ th¸m hiÓm s−u tÇm ®−îc n mÉu quÆng tõ mét vïng xa x«i vµ ph¶i

®em theo chóng vÒ nhµ. MÉu quÆng thø i cã träng l−îng lµ ai vµ gi¸ trÞ lµ ci. Hái nhµ th¸m hiÓm ph¶i ®em vÒ nh÷ng mÉu quÆng nµo ®Ó cã tæng gi¸ trÞ cña chóng

lµ lín nhÊt, biÕt r»ng nhµ th¸m hiÓm ®ã cã mang theo mét c¸i tói vµ anh ta chØ

mang ®−îc träng l−îng kh«ng qu¸ b.

- 39 -

Bµi to¸n c¸i tói ®ãng vai trß hÕt søc quan träng trong lý thuyÕt tèi −u bëi

v×: thø nhÊt, mäi bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh víi biÕn sè giíi néi ®Òu

cã thÓ ®−a vÒ bµi to¸n c¸i tói; thø hai, ®Ó gi¶i bµi to¸n c¸i tói cã thÓ sö dông

nh÷ng thuËt to¸n t−¬ng ®èi h÷u hiÖu.

2.2.3.2. §−a bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh vÒ bµi to¸n c¸i tói . C¸c

t y+

0

ph−¬ng ph¸p hîp nhÊt ho¸

t y th× mäi nghiÖm nguyªn cña ph−¬ng tr×nh 1 1

2

2

= -

§Þnh lý 1: NÕu nh− t1, t2 lµ hai sè nguyªn nguyªn tè cïng nhau (t1, t2) = 1 = (2.26) ®Òu cã thÓ biÓu

y 1

= qt y , 2 2

qt 1

, trong ®ã q lµ mét sè nguyªn tuú ý. diÔn d−íi d¹ng

Chøng minh: Gi¶ sö y1, y2 lµ nghiÖm nguyªn cña ph−¬ng tr×nh (2.26).

2

=

y

y

1

2

1y

˛ Z (t1, t2) = 1. Nªn y2 ph¶i chia hÕt t1 tøc lµ

t t 1

- Khi ®ã mµ

y2 = qt trong ®ã q ˛ Z .Tõ (1.1) suy ra y1 = - qt2.

§Þnh lý 2: NÕu nh− t1, t2 lµ hai sè nguyªn d−¬ng tho¶ mQn:

n= 1,

j

1) (t1, t2) = 1. 2) t2 kh«ng chia hÕt b1, t1 kh«ng chia hÕt b2. 3) t1 > b2 – amin; t2 > b1 – amin.

} trong ®ã amin = min{ ai j; aij > 0; i = 1,2;

n

=

a x 1 j

j

b 1

j

= 1

(2.27)

n

=

b 2

a x 2 j

j

= 1

j

 ∑     ∑ 

=

=

i

1,

m j ,

1,

n

Khi ®ã tËp c¸c nghiÖm nguyªn kh«ng ©m cña hÖ

) trong ®ã aij ‡ 0, bi > 0 lµ c¸c sè nguyªn (

n

+

=

+

)

x

j

j

j

t a ( 1 1

t a 2 2

t b 1 1

t b 2 2

lµ trïng víi tËp nghiÖm nguyªn kh«ng ©m cña ph−¬ng tr×nh:

∑

j

= 1

(2.28).

Chøng minh:

Chøng minh (2.27) ⇒⇒⇒⇒ (2.28).

- 40 -

*

=

(

,....,

* * x x , 1 2

x )n

Gi¶ sö * x lµ nghiÖm nguyªn kh«ng ©m cña hÖ (2.27)

n

=

* j

a x j 1

b 1

∑

j

= 1

n

=

* j

a x j 2

b 2

∑

j

= 1

     

Khi ®ã ta cã:

n

=

* j

t a x j 1 1

t b 1 1

∑

= 1

j

n

=

j

* j

t a x 2 2

t b 2 2

∑

=

j

     

n

n

+

=

* t a x 1 1 j j

* t a x 2 2 j j

+ t b t b 1 1 2 2

Do t1, t2 lµ hai sè nguyªn d−¬ng tho¶ mQn ®iÒu kiÖn 1), 2), 3), ta cã

∑

∑

=

j

= 1

j

n

+

=

j

* t a x ) 2 2 j j

+ t b t b 1 1 2 2

Céng hai vÕ cña hÖ trªn ⇒

∑ ( t a 1 1

= 1

j

⇒

*

*

*

=

x

(

,

,....,

Chøng minh (2.28) ⇒⇒⇒⇒ (2.27)

* x 1

x 2

x )n

n

=

i =

1,2

Gi¶ sö lµ nghiÖm nguyªn kh«ng ©m cña (2.28).

,y y lµ c¸c sè nguyªn.VËy *

* y i

* j

b i

* ,y y lµ 1 2

* 1

* 2

-∑ a x ij

= 1

j

+

=

t y

0

§Æt ; . Khi ®ã

1

t y 2

2

= -

y

t q=

. nghiÖm nguyªn cña ph−¬ng tr×nh 1

* y 1

t q 2

* 2

1

Tõ ®iÒu kiÖn 1) vµ ®Þnh lý 1 ta cã ; ; q – nguyªn. Ta chøng

*

minh q = 0.

1y

n

• ThËt vËy gi¶ sö q > 0 th× q ‡ 1 (do q nguyªn) ⇒ - t2 ‡ -t2q =

* y i

a x 1 j

* j

= - ∑ b 1

j

= 1

n

*

*

y i

a x 1 j

j

- (2.29) Hay t2 ≤

= ∑

= 1

j

n

*

Tõ ®iÒu kiÖn 2) ta cã 0 „ b1 – t2q = b1 +

a

a x 1 j

j

min

∑

= 1

j

‡ (2.30) MÆt „ * 0jx ‡ , * jx - nguyªn cho nªn

- 41 -

n

*

t

a

2

b 1

a x 1 j

j

b 1

min

∑

=

1

j

*

£ - £ - Tõ (2.29) vµ (2.30) suy ra (tr¸i víi gi¶ thiÕt 3).

2y dÉn ®Õn t1 ≤ b2 – amin (tr¸i víi gi¶

• T−¬ng tù víi q < 0 th× t1 ≤ - qt1 = -

n

*

*

=

thiÕt 3).

a x 1 j

* j

b i

1y = 0,

2y = 0 hay

∑

= 1

j

VËy q = 0 ⇒ , i = 1,2.

*x lµ nghiÖm cña (2.27).

n

b i

i

m= 1,

Tøc lµ

=∑ * a x ij j

= 1

j

m= 1,

i

HÖ qu¶: §èi víi hÖ ; (2.31)

), lu«n t×m ®−îc c¸c trong ®ã aij lµ c¸c sè nguyªn kh«ng ©m, bi > 0 (

n

m

m

=

)

x

t a i

ij

j

i

∑ ∑ (

∑ t b i

=

=

=

1

j

1

i

1

i

sè nguyªn t1, t2,...., tm sao cho tËp nghiÖm nguyªn kh«ng ©m cña hÖ (2.31) lµ trïng víi tËp c¸c nghiÖm nguyªn kh«ng ©m cña ph−¬ng tr×nh

+

VÝ dô: §−a vÒ mét ph−¬ng tr×nh t−¬ng ®−¬ng víi hÖ sau ®©y:

2

x

3

x

1 0

2

1 +

£

x

11

4 +

£

3

2 x

x 1 x

3

13

£

1 ,

x

2 0,

nguyen

x 1

2

      

‡

H−íng dÉn:

4x ,

3x ,

5x biÕn ®æi c¸c bÊt ph−¬ng tr×nh vÒ ph−¬ng tr×nh

§−a vµo c¸c biÕn phô

+

=

2

x

2

x 3 +

10 =

x

x 4 +

11 =

2 x

x

3

13

2

5

+ 3 x  1  + x 4  1  + x 3  1

j =

1,5

ta thu ®−îc hÖ sau:

jx ‡

jx - nguyªn,

0 ,

Hîp nhÊt ho¸ hai ph−¬ng tr×nh ®Çu cña hÖ trªn:

T×m hai sè (t1, t2) = 1, t1 kh«ng chia hÕt 11, t2 kh«ng chia hÕt 12. t1> 11- 1= 10, t2 > 10- 1 = 9.

- 42 -

VËy t1 = 12, t2 = 11. Khi ®ã ta thu ®−îc ph−¬ng tr×nh;

47x1 + 68x2 + 12x3 + 11x4 = 241. Hîp nhÊt ho¸ ph−¬ng tr×nh thu ®−îc víi ph−¬ng tr×nh thø ba cña hÖ ban ®Çu :

t×m ®−îc t3 = 15, t4 = 242 thu ®−îc ph−¬ng tr×nh sau: 1431x1 + 1746x2 + 180x3 + 165x4 242x5 = 6761. §iÓm h¹n chÕ cña ®Þnh lý 2 ®ßi hái kh«ng ©m ®èi víi tÊt c¶ c¸c hÖ sè. §Þnh

lý d−íi ®©y kh¾c phôc nh−îc ®iÓm ®ã nh−ng l¹i ®ßi hái c¸c biÕn sè ph¶i giíi

néi.

n

=

=

1,2

a x ij

j

b i , i

= 1

j

(2.32)

=

§Þnh lý 3: XÐt hÖ ph−¬ng tr×nh:

,

,

1,

x

d x nguyen j

n

j

j

j

 ∑    £ 0 

=

=

,

1, 2,

j

1,

n

£ -

a b d i , , ij i

j

trong ®ã ( ) lµ c¸c sè nguyªn. Khi ®ã nÕu t1, t2 lµ c¸c sè

nguyªn d−¬ng, nguyªn tè cïng nhau tho¶ mQn c¸c ®iÒu kiÖn :

S.

S. 1. (t2, -t1) ˇ 2. (-t2, t1) ˇ

y i

+ y i

iy - nguyªn, i = 1,2}

- £ £ , trong ®ã S = {(y1,y2);

=

=

y i {

0,

= j

- - -

} = , n i

1,

1,2

y i

a d ij

j

b J , i i

< j a : ij

∑

j J i

+

=

+ =

- ˛

{

0,

= j

} = n i ,

1,

1,2

y i

a d ij

j

b J , i

i

> j a : ij

∑

+

j J

i

- ˛

n

+

=

+

(

)

x

th× tËp c¸c lêi gi¶i cña (2.32) sÏ trïng víi tËp c¸c lêi gi¶i cña hÖ

t a 1 1

j

t a 2 2

j

j

t b 1 1

t b 2 2

∑

= 1

j

(2.33)

n= 1,

j

x

d

j

jx - nguyªn,

j

£ £ 0 , .

Chøng minh.

Tr−íc hÕt ta nhËn thÊy r»ng nÕu (2.32) cã nghiÖm th× ta ph¶i cã

- 43 -

n

+

=

0

a d ij

j

b i

a x ij

j

b i

b i

a x ij

j

b i

y i

∑

∑

∑

+

+

- = ‡ ∑ a x ij j = 1

j

j J

j J

j J

i

i

i

- ‡ - ‡ - - ˛ ˛ ˛

= ,

i

1, 2

a d ij

- = b j i

y i

∑

j J

i

- ‡ - ˛

y

0

i

+ y i

*

=

* x

(

,

,....,

- £ £ (2.34) VËy ®iÒu kiÖn cÇn ®Ó cho hÖ (2.32) cã nghiÖm lµ:

* x 1

* x 2

x )n

Gi¶ sö lµ nghiÖm cña (2.32) khi ®ã *x lµ nghiÖm cña (2.33)

*

=

* x

(

,....,

• Chøng minh (2.33) ⇒⇒⇒⇒ (2.32)

* * x x , 1 2

x )n

n

=

Gi¶ sö lµ nghiÖm nguyªn kh«ng ©m cña (2.33).

1, 2

* y i

* a x ij j

= b i ; i

∑

= 1

j

*

*

- §Æt

* ,y 1

y lµ c¸c sè nguyªn. VËy 2

* ,y 1

y lµ nghiÖm nguyªn cña ph−¬ng 2

= -

+

=

t q=

t y

0

Khi ®ã

* y 2

1

* y 1

t q 2

1

t y 2

2

n

*

*

=

.Tõ ®Þnh lý 1 ta cã ; ; q – nguyªn vµ do tr×nh 1

1,2

a d ij

j

a x ij

j

b i

a x ij

j

b i , i

∑

∑

∑

+

= 1

j

j J

j J

i

i

*

*

£ - £ - - ˛ ˛

(

)

S˛

y

i =

1, 2

* * y y , 1 2

j

b i

a d ij

j

-∑ a x ij

∑

+

j J

j J

i

i

(

)

S˛

£ £ Hay , . Nªn ta chøng minh q = 0 - ˛ ˛

* * y y , 1 2

• ThËt vËy nÕu q > 0 th× tõ (-qt2, qt1) =

+

ta suy ra

qt

t

0

y 1

2

2

y 1

- £ - £ - £ £

y

0

y

2

t 1

qt 1

+ 2

- £ £ £ £

S (tr¸i víi ®iÒu kiÖn 2) Tøc lµ (-t2, t1) ˛

(

= )

(

,

)

S

• T−¬ng tù nÕu q < 0 th× tõ

qt qt , 2 1

* y 1

* y 2

- ˛ ta suy ra

*

*

S (tr¸i víi ®iÒu kiÖn 1). (t2, - t1)˛

*x lµ nghiÖm cña hÖ (2.32).

1y

2y

VËy q = 0 ⇒ = 0, = 0. Tøc

Chó ý: §iÒu kiÖn cña ®Þnh lý 3 sÏ ®−îc tho¶ mQn nÕu ta chän t1, t2 lµ hai sè nguyªn d−¬ng, nguyªn tè cïng nhau tho¶ mQn mét trong sè c¸c ®iÒu

+ +

kiÖn sau:

y

1,

t

1

•

t 1

2

2

+ + y 1

‡ ‡

- 44 -

(

=

+

xay

k

F k

1

k

k

} )

{ max xc k Xx k

k

[

] }

X

{ ,..,1,0=

ay

- - ˛

+Z lµ tËp c¸c sè nguyªn kh«ng ©m.

k

k

Trong ®ã, kÝ hiÖu cßn

=

y

0,

b

NÕu ®Æt:

= 0 ( ) 0, F y

(2.36)

(

} )

=

+

th× ta sÏ cã c«ng thøc truy to¸n sau ®©y:

=

=

xay

k

1,

n y ,

0,

b

( ) yF k

{ xc k

k

F k

1

k

k

max Xx k

k

- - , (2.37) ˛

n

=

b

a x j

j

∑

= 1

j

,

,

§èi víi bµi to¸n c¸i tói rµng buéc ®¼ng thøc

a c b lµ nguyªn d−¬ng, hÖ thøc (2.37) vÉn ®óng nÕu ta thay ®æi

j

j

trong ®ã

= -

®iÒu kiÖn ®Çu (2.36) bëi ®iÒu kiÖn sau

= (0) 0,

,

y

0

F 0

F y ( ) 0

¥ „ (2.38)

+

Chóng ta cã thÓ dÉn ra nh÷ng hÖ thøc truy to¸n kh¸c ®Ó tÝnh Fk(y). HÖ thøc Dantzig.

y c ( ),

} ) ;

a

a

k

1

F y ( k

k

k

( ) F y k

y <

;

{ max F k ( ) y

y

a

- ‡ -

F k

k

1

 =  

-

Víi ®iÒu kiÖn ®Çu (2.36) hoÆc (2.38)

§Ó gi¶i bµi to¸n c¸i tói b»ng c¸ch dïng hÖ thøc Dantzig nãi trªn ta cÇn

*

*

=

x

(

,...,

)

tÝnh Fk(y) víi " k, y, sau ®ã xÐt c¸ch thu ®−îc Fn(b). §Ó t×m c¸c gi¸ trÞ cña c¸c

jx trong ph−¬ng ¸n tèi −u

j

* * x x , 1 2

* x n

thµnh phÇn . Ta xÐt qu¸ tr×nh nµy

=

=

k

0 ,

n y ,

0 ,

b

)

nh− sau:

. LËp b¶ng 1: Víi c¸c gi¸ trÞ Fk(y) (

=

0 ,

k h i F y

(

)

0

j

(

y

)

1

LËp b¶ng 2: Víi c¸c gi¸ trÞ jk(y) ®−îc x¸c ®Þnh nh− sau:

1,

k h i F y

)

0

1 (

1

=  

=

y ( ),

y ( )

„

1

j y ( ) k

- -

j k k

khi F k 1 y ( )

khi F k

1

F y ( ) k F y ( ) k

 =  

„ -

- 45 -

*

jx trong ph−¬ng

B¶ng 2 sÏ cho phÐp x¸c ®Þnh c¸c gi¸ trÞ cña c¸c biÕn sè

< £

¸n tèi −u. Gi¸ trÞ jn(b) b»ng chØ sè lín nhÊt cña biÕn sè d−¬ng trong ph−¬ng ¸n tèi −u. V× vËy ®Æt:

0,

:

j

n

x

j

j =

j

( ) j b n ( ) j b n

 =  1, 

d

"

d =

x

x=

(

= )

(

b

)

+ . ( ) 1

j b a n

nj

j b ( ) n

j b n

j b ( ) n

- X¸c ®Þnh . NÕu th×

0,

:

(

j

j b a n

j b ( ) n

< < ) ( ) j b n

x

j

j =

" -

(

)

j

j b a n

( ) j b n

- Ng−îc l¹i, ®Æt =  1; 

TiÕp tôc thñ tôc trªn cho ®Õn khi gÆp jn(0).

+

+

VÝ dô: Gi¶i bµi to¸n c¸i tói sau:

F x ( )

= + x 1

x 3 2

x 5 3

x max 9 4

+

+

+

+

=

2

4

7

10

x 1

x 3 2

x 3

x 4

x 5

0

j =

1,5

fi

jx ‡

jx - nguyªn,

= -

, .

,

y

0

= ,

F y 0( )

F 0(0) 0

¥ „ Ta cã:

=

=

y

0 :

= (0) 1

0

F 1

0      2

=

+

= -

Khi k = 1 ta cã:

y

1:

= (1) 1

(1)

F 1

F 0

1      2

=

+

2:

= (2) 1

= (0) 1

y

F 1

F 0

2      2

=

+

= -

¥

y

3:

= (3) 1

(1)

F 1

F 0

3      2

=

+

y

4:

= (4) 1

= (0) 2

F 1

F 0

4      2

=

+

= -

¥

5:

= (5) 1

(1)

y

F 1

F 0

5      2

¥

- 46 -

=

+

y

6 :

= (6) 1

= (0) 3

F 1

F 0

6      2

=

+

= -

y

7 :

= (7) 1

(1)

F 1

F 0

7      2

=

+

=

y

8 :

= (8) 1

(0)

4

F 1

F 0

8      2

=

+

= -

¥

y

9 :

= (9) 1

(1)

F 1

F 0

9      2

=

=

+

y

10 :

(10) 1

= (0) 5

F 1

F 0

10 2

  

  

¥

+

=

=

0 :

(0)

{ 3.0

y

= 0

F 1

F 2

+

= -

=

=

Khi k = 2 ta cã:

} (0) } (1)

1:

(1)

max

y

F 1

F 2

+

=

=

} (2)

max { 3.0 { 3.0

2 :

(2)

y

= 1

F 1

F 2

=

=

+

+

=

¥

{

max

3 :

(3)

y

(3);3.1

max

3

F 2

F 1

F 1

+

=

=

+

=

¥ =

- ¥

} = ;3 }

max { 3.0 { 3.0

4 :

(4)

y

(4);3.1

} (0) } (1)

max

2

F 2

F 1

F 1

+

=

=

+

=

-

{ 2, {

max

5 :

(5)

y

(5);3.1

} (2)

max

4

F 2

F 1

F 1

+

=

=

+

+

=

- ¥

max

6 :

(6)

y

(6);3.1

(3);3.2

} = ,6

6

F 2

F 1

F 1

F 1

+

=

=

+

+

=

- ¥ { 3,

max {

}

max { 3.0 { 3.0 { 3.0

7 :

(7)

y

(7);3.1

(4);3.2

max

¥ = ,5,

5

F 2

F 1

F 1

F 1

+

=

=

+

+

=

- ¥ -

max

8 :

(8)

y

(8);3.1

(5);3.2

} = ,4 } (0) } (1) } (2)

max

{ 4,

} = ,7

F 2

F 1

F 1

F 1

+

=

=

+

+

+

=

- ¥

y

9 :

(9)

(9);3.1

,6,

max =

=

F 1 +

F (6);3.2 1 +

F (3);3.3 1 +

- ¥ - ¥

9 }

max { 3.0 { 3.0 { max 3.0

(10)

10 :

(10);3.1

(7);3.2

(4);3.3

{ 5,

} ,9 ¥ = ,8,

8

7 { max

F 1

F 1

F 1

} = max F (0) 1 } = + F (1) 1

F 2 F y 2 Khi k = 3 ta cã:

=

=

+

0 :

(0)

{ 5.0

y

= 0

F 3

F 2

=

=

+

= -

- ¥ -

1:

(1)

max

y

} (0) } (1)

F 3

F 2

=

=

+

max { 5.0 { 5.0

2 :

(2)

y

= 1

F 3

F 2

=

=

+

max

3 :

(3)

y

} (2) } (3)

= 3

F 3

F 2

=

=

+

+

=

max { 5.0 { 5.0

4 :

(4)

y

(4);5.1

{ } 2,5

F 3

F 2

F 2

=

=

+

+

=

¥ =

¥

max {

= 5 }

max { 5.0

max

5 :

(5)

y

(5);5.1

} (0) } (1)

max

4,

4

F 3

F 2

F 2

-

- 47 -

+

=

+

=

=

6 :

(6)

max

(6);5.1

max

y

= 6

F 3

F 2

F 2

=

+

+

=

=

7 :

(7)

{ 5.0 { 5.0

} (2) } (3)

max

(7);5.1

y

= 8

F 3

F 2

F 2

=

+

+

+

=

=

=

8 :

(8)

max

(8);5.1

(4);5.2

10

{ } 7,7,10

y

F 3

F 2

F 2

F 2

=

+

+

+

¥ =

=

=

}

9 :

(9)

max

(9);5.1

(5);5.2

{ } 6;6 { } 5,8 } (0) } (1)

y

F 3

F 2

F 2

F 2

=

+

+

+

=

=

=

max { 5.0 { 5.0 { 5.0

max

10 :

(10)

(10);5.1

(6);5.2

max { 9 9,9, { } 8,11,11

max } (2)

max

11

y

F 3

F 2

F 2

F 2

-

=

+

=

y

0 :

(0)

{ 9.0

= 0

F 3

F 4

=

+

= -

=

Khi k = 4 ta cã:

y

} (0) } (1)

1:

(1)

max

F 3

F 4

=

+

=

y

max { 9.0 { 9.0

2 :

(2)

= 1

F 3

F 4

=

+

=

y

} (2) } (3)

max

3 :

(3)

F 3

F 4

=

+

=

y

max { 9.0 { 9.0

4 :

(4)

= 5

F 3

F 4

=

+

=

y

= 3 } (4) } (5)

max

5 :

(5)

= 4

F 3

F 4

=

+

=

y

} (6)

max

6 :

(6)

= 6

F 3

F 4

=

+

=

+

=

y

max { 9.0 { 9.0 { 9.0

7 :

(7)

(7);9.1

{ } 8,9

F 4

F 3

F 3

=

+

=

+

=

¥ =

¥

= 9 }

y

max

8 :

(8)

(8);9.1

} (0) } (1)

max

10

F 4

F 3

F 3

=

+

=

+

=

=

y

max

9 :

(9)

(9);9.1

} (2)

F 4

F 3

F 3

=

=

+

+

=

=

y

max { 9.0 { 9.0 { 9.0

max

10 :

(10)

(10);9.1

max { 10, { } 10 9,10 { } 11,12

max

max } (3)

12

F 4

F 3

F 3

-

F y ,y <1 0 5 ( )

=

=

=

(10)

(10);

(8);

(7);

(6);

(5);

(4);

(3);

(2);

(1);

(0)

{ max F 4

F 5

F 4

F 4

F 4

F 4

F 4

F 4

F 4

F 4

F 4

F 4

y =

Khi k = 5 ta xÐt ngay y = 10 v× kh«ng cÇn tÝnh c¸c gi¸ trÞ trung gian

10: { 12,10,10,9,6,4,5,3,1,

max

(9); } = ,0

12

- ¥

T×m ph−¬ng ¸n tèi −u:

x = vµ 0

5

víi

= F 5(10) 12 = F 4(10) 12

= víi

x = vµ 4 1 x = vµ 0

F 3(3) 3

3

= víi

F 2(3) 3

= 4(10) 12 F = F 3(3) 3 = 2(3) 3 F = F 1(0) 0

x = vµ 2 1 x = 0

F 1(0) 0

= víi 1

víi

- 48 -

*

x =

(0,1,0,1,0)

F x = *(

) 12

VËy ph−¬ng ¸n tèi −u: , .

KÕt luËn ch−¬ng 2:

Mét trong nh÷ng thµnh tùu næi bËt cña lý thuyÕt tèi −u tæng qu¸t vµo

nh÷ng n¨m 70 cña thËp kû 20 lµ viÖc x©y dùng lý thuyÕt gi¶i líp bµi to¸n quy

ho¹ch nguyªn tuyÕn tÝnh. C¸c nhµ khoa häc ®i tiªn phong trong lÜnh vùc nµy lµ

Gomory, Land, Doig....

C¸c vÊn ®Ò lý thuyÕt ®−îc tr×nh bµy ë ch−¬ng 2 lµ thµnh tùu míi nhÊt, cËp

nhËt nhÊt cña lý thuyÕt tèi −u tuyÕn tÝnh nãi riªng; lý thuyÕt quy ho¹ch nguyªn

tuyÕn tÝnh nãi chung. Trong qu¸ tr×nh tr×nh bµy c¸c kÕt qu¶ nghiªn cøu chóng t«i

®Q cè g¾ng ®¶m b¶o tÝnh chi tiÕt, tÝnh cô thÓ cña c¸c ®Þnh lý c¸c thuËt to¸n mµ

c¸c tµi liÖu tham kh¶o chØ tr×nh bµy kh¸t qu¸t, v¾n t¾t nh»m gióp ng−êi ®äc hiÓu

mét c¸ch ®Çy ®ñ vµ s©u s¾c nhÊt c¸c vÊn ®Ò khi ®äc tµi liÖu

- 49 -

Ch−¬ng 3

Bµi tËp vËn dông

3.1. Bµi tËp vËn dông thuËt to¸n c¾t Gomory

Bµi tËp 1: Gi¶i bµi to¸n sau

Mét nhµ m¸y s¶n xuÊt xe m¸y cÇn s¶n xuÊt hai dßng xe Hon §a vµ

Yamaha. BiÕt nguyªn liÖu nhµ m¸y sö dông ®Ó s¶n xuÊt hai dßng xe trªn lµ

kh«ng qu¸ 38 ®¬n vÞ nguyªn liÖu lo¹i 1 vµ kh«ng qu¸ 7 ®¬n vÞ nguyªn liÖu lo¹i

2. §Ó s¶n xuÊt mét chiÕc xe dßng Hon §a cÇn tèn 2 ®¬n vÞ nguyªn liÖu lo¹i 1; 1

®¬n vÞ nguyªn liÖu lo¹i 2 vµ tiÒn lQi thu ®−îc khi b¸n mét chiÕc xe dßng Hon §a

lµ 1 ®¬n vÞ tiÒn, ®Ó s¶n xuÊt mét chiÕc xe m¸y dßng Yamaha cÇn tèn 11 ®¬n vÞ

nguyªn liÖu lo¹i 1; 1 ®¬n vÞ nguyªn liÖu lo¹i 2 vµ tiÒn lQi thu ®−îc khi b¸n mét

chiÕc xe dßng Yamaha lµ 2 ®¬n vÞ tiÒn. HQy gióp nhµ m¸y lùa chän s¶n xuÊt

dßng xe m¸y nµo; víi sè l−îng lµ bao nhiªu ®Ó thu ®−îc lîi nhô©n cao nhÊt.

Lêi gi¶i

M« h×nh to¸n häc cña bµi to¸n nh− sau

f x ( )

max

= + x 1

x 2 2

fi

38

£

x 11 2 7

x 2

+ 2 x  1  + x  1

£

0jx ‡

jx - nguyªn, j =1,2

,

jx - nguyªn.

§−a bµi to¸n vÒ d¹ng chÝnh t¾c vµ gi¶i bµi to¸n bá qua ®iÒu kiÖn

= - ( ) f x

2

x 1

x 2

x 11 2

7

x 2

+ = x 38 3 + = x 4

+ 2 x  1  + x  1

- - fi min

0,

= j

1,4

jx

‡

Ta cã b¶ng ®¬n h×nh d−íi ®©y:

- 50 -

jc c¬

C¬ së Ph. ¸n

-1 A1 -2 A2 0 A3 0 A4

së 0 38 2 1 0 [11]

A3 A4 0 7 1 0 1 1

j

D 1 2 0 0

-2 38/11 2/11 1 1/11 0

A2 A4 0 39/11 0 -1/11 1 [9/11]

j

D 7/11 0 -2/11 0

-2 8/3 0 1 1/9 -2/9

A2 A1 -1 13/3 1 0 -1/9 11/9

j

D 0 0 -1/9 -7/9

Trong ph−¬ng ¸n tèi −u c¸c biÕn c¬ së ®Òu kh«ng nguyªn. Chän biÕn c¬ së

= -

) 0

L x ( )

)

(

(

x 4

x 3

2 9

2 9

1 9

2 3

  

  

2x vµ x©y dùng ®−îc l¸t c¾t (theo c«ng thøc (2.16)):  -  

  

- - - - - - ‡

(

)

(

) 0

( )L x =

x 3

x 4

2 3

1 9

7 9

x ‡

0

- - - - - ‡

5

= -

§−a vµo biÕn vµ chuyÓn rµng buéc vÒ ®¼ng thøc

(

)

(

)

x 3

x 4

x 5

2 1 3 9

7 9

- - - - . ViÕt rµng buéc nµy vµo cuèi b¶ng sau.

jc c¬

C¬ së Ph. ¸n -1 -2 0 0 0

A1 A2 A3 A4 A5

A2 së -2 8/3 0 1 1/9 -2/9 0

A1 -1 13/3 1 0 -1/9 11/9 0

A5 0 -2/3 0 0 -7/9 1 [-1/9]

j

D 0 0 -1/9 -7/9 0

A2 -2 2 0 1 0 1 1

A1 -1 5 1 0 0 2 -1

A3 0 6 0 0 1 7 -9

j

D 0 0 0 -4 -1

- 51 -

VËy nhµ m¸y nªn s¶n xuÊt 5 chiÕc xe dßng Hon §a, 2 chiÕc xe dßng

Yamaha th× tiÔn lQi thu ®−îc lµ lín nhÊt ( lµ 9 ®¬n vÞ tiÒn).

f x ( )

= + x 1

x max 2 2

+

fi Bµi tËp 2:

4

x

5

x

2 2

1

2

+

£

x

3

x

3 3

2

£

x

1

1 + x 1

£

x

2 = j

0,

1, 2

j

  9   -   

jx ,

jx - nguyªn, j = 1,2.

‡

Lêi gi¶i

jx -

§−a bµi to¸n vÒ d¹ng chÝnh t¾c vµ gi¶i bµi to¸n bá qua ®iÒu kiÖn

nguyªn ta cã b¶ng ®¬n h×nh tèi −u sau:

jc

C¬ së Ph. ¸n -1 -2 0 0 0

A1 A2 A3 A4 A5

c. s -1 A1 17/9 1 0 1/9 0 -5/9

A4 0 22/3 0 0 -4/3 1 11/3

-2 A2 26/9 0 1 1/9 0 4/9

j

D 0 0 -1/3 0 -1/3

=

=

>

=

2

4

b 1

b

b

Trong ph−¬ng ¸n tèi −u c¸c biÕn c¬ së ®Òu kh«ng nguyªn. Chän biÕn c¬

8     9  

1     3  

së 1x x©y dùng l¸t c¾t v×

=

L x ( )

(

)

(

) 0

x 3

x 5

8 9

1 9

4 9

- - - - - ‡

6x ‡

§−a vµo biÕn 0 vµ chuyÓn rµng buéc vÒ d¹ng ®¼ng thøc:

(

)

(

)

x 6

x 3

x 5

8 9

1 9

4 9

- = - - - - . ViÕt rµng buéc nµy vµo cuèi cña b¶ng sau.

C¬ së Ph−¬ng -2 0 0 0 0 -1

cj c¬ së A2 A3 A4 A5 A6 ¸n A1

- 52 -

A1 -1 17/9 1 0 1/9 0 -5/9 0

A4 0 22/3 0 0 -4/3 1 11/3 0

A2 -2 26/9 0 1 1/9 0 4/9 0

A6 0 -8/9 0 0 -1/9 0 1 [-4/9]

j

D 0 0 -1/3 0 -1/3 0

-5/4 0 0 1/4 0 1 3 A1 -1

33/4 0 1 -9/4 0 0 0 A4 0

1 0 0 0 1 0 2 A2 -2

-9/4 1 0 1/4 0 0 2 A5 0

j

x =

(3,2)

D 0 0 -1/4 0 0 -3/4

f x = *( ) 7

= -

Ph−¬ng ¸n tèi −u * ,

f x ( )

2

6

4

min

+ x 1

+ x 2

x 3

+ 2 x 4

x 3 5

+

+

=

52

2 +

4 +

=

x 3 x

6

x 1 x 4 2

+

x 2 x 2 3 =

3

4 36

x 2

x 5

    

0

j =

1,5

- fi Bµi tËp 3:

jx ‡

, nguyªn,

j =

1,5

Lêi gi¶i

jx - nguyªn,

Gi¶i bµi to¸n quy ho¹ch tuyÕn tÝnh bá qua ®iÒu kiÖn ta

thu ®−îc b¶ng ®¬n h×nh tèi −u sau:

2 -6 -4 2 -3 C¬ së cj c¬ së Ph. ¸n

A1 A2 A3 A4 A5

A1 2 52 1 2 0 0 [4]

A4 2 60 0 4 1 0 2

A5 -3 36 0 3 0 1 0

j

D 0 9 16 0 0

A3 -4 13 1/4 1/2 1 0 0

2 34 -1/2 0 1 0 A4 [3]

A5 -3 36 0 0 0 1 3

j

D -4 1 0 0 0

- 53 -

A3 -4 22/3 1/3 0 1 -1/6 0

A2 -6 34/3 -1/6 1 0 1/3 0

A5 -3 2 1/2 0 0 -1 1

j

D -23/6 0 0 -1/3 0

Trong ph−¬ng ¸n tèi −u c¸c biÕn c¬ së ®Òu kh«ng nguyªn. Chän biÕn c¬

2x vµ x©y dùng l¸t c¾t theo (2.16)

së

=

L x ( )

(

)

(

) 0

x 1

x 4

1 5 3 6

1 3

- - - - - ‡

6x ‡

§−a vµo biÕn 0 vµ chuyÓn rµng buéc vÒ d¹ng ®¼ng thøc:

=

(

)

(

x

)

x

x 1

4

6

1 3

5 6

1 3

- - - - - . ViÕt rµng buéc nµy vµo cuèi b¶ng sau.

jc c¬

C¬ së Ph. ¸n -6 -4 2 2 -3 0

A2 A3 A1 A4 A5 A6

22/3 1/3 0 -1/6 0 0 1 A3 së - 4

34/3 -1/6 1 1/3 0 0 0 A2 - 6

2 1/2 0 -1 1 0 0 - 3 A5

-1/3 5/6 0 [-1/3] 0 1 0 A6 0

j

D -23/6 0 -1/3 0 0 0

15/2 -1/12 0 0 0 - 1/2 1 A3 - 4

11 2/3 1 0 0 1 0 A2 - 6

3 -2 0 0 1 -3 0 A5 - 3

1 -5/2 0 1 0 - 3 0 2 A4

j

3

b =

D - 8/3 0 0 0 - 1 0

3x ®Ó x©y

15 2

Trong ph−¬ng ¸n tèi −u kh«ng nguyªn, chän biÕn c¬ së

dùng l¸t c¾t.

=

L x ( )

(

)

(

) 0

x 1

x 6

1 11 12 2

1 2

x ‡

0

- - - - - ‡

7

vµ chuyÓn rµng buéc vÒ d¹ng ®¼ng thøc: §−a vµo biÕn

- 54 -

=

)

(

)

(

x 1

x 6

x 7

1 11 12 2

1 2

- - - - - . ViÕt rµng buéc nµy vµo cuèi b¶ng sau.

jc c¬

Ph. ¸n 2 -6 - 4 2 -3 C¬ 0 0

A1 A2 A3 A4 A5 së A6 A7

0 - 1/2 0 0 1 0 -1/12 15/2 A3 së - 4

0 1 0 0 0 1 2/3 11 A2 - 6

0 -3 1 0 0 0 -2 3 A5 - 3

0 - 3 0 1 0 0 -5/2 1 A4 2

A7 0 -1/2 -11/12 0 0 0 1 0 [- 1/2]

j

D 0 - 8/3 0 0 - 1 0 0

A3 - 4 8 5/6 0 1 0 0 0 1

A2 - 6 10 -7/6 1 0 0 0 0 2

A5 - 3 6 7/2 0 0 0 1 0 -6

A4 2 4 3 0 0 1 0 0 -6

A6 0 1 11/6 0 0 0 0 1 -2

j

*

f x = - *( )

102

x =

(0,10,8,4,6)

D 0 -5/6 0 0 0 -10 0

+

+

Ph−¬ng ¸n tèi −u , .

= ( ) 10

f x

14

min

x 1

x 2

x 21 3

+

+

fi Bµi tËp 4

2

2

x

14

x 1

7 +

+

‡

2 x

9

11

12

x 3 x 3

+

2 +

‡

x

9

6

3

10

x 1 x 1

2

x 3

  8   

0

j =

1,3

jx ‡

jx - nguyªn,

‡

Lêi gi¶i

+

+

§−a bµi to¸n vÒ d¹ng chÝnh t¾c, ta cã:

= ( ) 10

f x

14

min

x 1

x 2

x 21 3

+

+

fi

2

14

+

7 +

-

9

12

x 3 x 3

+

x 2 x 11 2 +

-

6

10

x 1 x 1 x 1

x 2

3 x 3

= x 4 = x 5 = x 6

2   8   9 

-

- 55 -

j =

1, 6

0

jx ‡

jx - nguyªn,

,

jx nguyªn ta cã b¶ng ®¬n

Gi¶i bµi to¸n trªn víi ®iÒu kiÖn bá ®i ®iÒu kiÖn

h×nh tèi −u sau ®©y:

C¬ Ph−¬ng 10 14 21 0 0 0

së cj c.s ¸n A1 A2 A3 A4 A5 A6

28/57 12/19 0 1/19 -7/57 A1 10 1 0

26/3 -5 0 -1 -2/3 A5 0 0 1

2/19 1 2/57 21 0 0 A3 106/57 -3/19

j

,

˛j

}3,5,1 {

D 0 0 0 -104/19 -53/19 -28/57

x j

Trong ph−¬ng ¸n tèi −u c¸c biÕn ®Òu kh«ng nguyªn. Chän

5x vµ x©y dùng ®−îc l¸t c¾t:

= -

biÕn c¬ së

( ) L x

(

) 0

x 6

2 1 3 3

0

‡x

- - ‡

7

= -

§−a vµo biÕn vµ chuyÓn rµng buéc trªn vÒ d¹ng ®¼ng thøc ta thu

(

)

x 7

x 6

2 1 3 3

- - ®−îc: .

ViÕt rµng buéc nµy vµo dßng cuèi cïng cña b¶ng sau ta thu ®−îc b¶ng míi:

jc

C¬ Ph.

0 A4 10 A1 14 A2 21 A3 0 A5 0 A6 0 A7 së ¸n c.s

A1 10 28/57 1/19 1 12/19 0 0 0 -7/57

A5 0 26/3 -1 0 -5 0 1 0 -2/3

A3 21 106/57 -3/19 0 2/19 1 0 0 2/57

0 0 0 1 A7 0 -2/3 0 0 [-1/3]

j

D 0 0 0 0 -28/57 -104/19 -53/19

- 56 -

x =

, 0,

, 0,10, 2)

Gi¶i bµi to¸n b»ng thuËt to¸n ®¬n h×nh ®èi ngÉu. Ph−¬ng ¸n t×m ®−îc

14 ( 19

102 57

ch−a nguyªn. Chän biÕn c¬ së 1x ®Ó x©y dùng l¸t c¾t, ®−a

8x , c¸c tÝnh to¸n ®−îc thÓ hiÖn trong b¶ng sau:

vµo biÕn

Ph. 10 C¬ 14 21 0 0 0 0 0

¸n A1 së cj c.s A2 A3 A4 A5 A6 A7 A8

14/19 1 A1 10 12/19 0 1/19 0 0 -7/19 0

10 0 0 -5 0 -1 1 0 - 2 0 A5

2/19 1 -3/19 2/19 0 21 102/57 0 A3 0 0

0 A6 0 2 0 0 0 0 0 - 3 0

A8 0 - 14/19 0 -12/19 0 -1 /19 0 1 [-12/19] 1

j

D 0 -104/19 0 -53/19 0 0 -28/ 19 0

x =

(

, 0,

, 0,

)

Gi¶i bµi to¸n b»ng thuËt to¸n ®¬n h×nh ®èi ngÉu. Ph−¬ng ¸n t×m ®−îc

5 3

37 11 7 , , 2 6 3

7 6

ch−a nguyªn. Chän biÕn c¬ së 3x ®Ó x©y dùng l¸t c¾t, ®−a

9x , c¸c tÝnh to¸n ®−îc thÓ hiÖn trong b¶ng:

vµo biÕn

Ph. 10 14 21 0 0 0 0 0 C¬ 0

A1 A2 A3 A5 A6 A7 A8 A9 së cj c.s A4 ¸n

A1 1/12 7/6 1 0 1 0 0 0 - 7/12 0 10 A5 - 5/6 37/3 -3 0 0 1 0 0 -19/6 0 0 A3 - 1/6 5/3 0 1 0 0 0 0 1/6 0 21

A6 0 1/4 11/2 3 0 0 0 1 0 -19/4 0

A7 0 1/12 7/6 1 0 0 0 0 1 - 19/12 0

A9 0 [-5/6] - 2/3 0 0 0 0 0 0 - 1/6 1

j

D 0 - 4 0 - 46/57 0 0 0 - 7/3 0

x

, 0,

,13,

Gi¶i bµi to¸n b»ng thuËt to¸n ®¬n h×nh ®èi ngÉu. Ph−¬ng ¸n t×m ®−îc

3x ®Ó x©y dùng l¸t c¾t,

11 10

9 4 , 5 5

53 11 , 10 10

 =  

  

ch−a nguyªn. Chän biÕn c¬ së

10x

, c¸c tÝnh to¸n ®−îc thÓ hiÖn trong b¶ng: ®−a vµo biÕn

- 57 -

C¬ Ph. 10 14 21 0 0 0 0 0 0 0

së cj c.s ¸n A1 A2 A3 A4 A5 A6 A7 A8 A9 A10

1 0 0 0 1/10 0 A1 10 11/10 1 0 0 - 3/5

0 0 1 0 -1 0 0 13 -3 0 0 - 3 A5

-1/5 0 9/5 0 0 0 1/5 A3 21 0 1 0 0

A6 0 53/10 0 3 0 0 0 1 0 - 24/5 3 /10 0

A7 0 11/10 0 1 0 1 0 0 1 - 8/5 1 /10 0

A4 0 4/5 0 0 0 0 0 0 0 1/5 - 6/5 0

A10 0 - 4/5 0 0 0 0 0 0 0 - 1/5 1 [-4/5]

j

D 0 0 - 4 0 0 0 0 0 - 9/5 - 16/5

A1 10 1 1 1 0 0 0 0 0 - 5/8 0 1/8

A5 0 14 0 -3 0 0 1 0 0 - 11/4 0 - 5/4

A3 21 2 0 0 1 0 0 0 0 1/4 0 - 1/4

A6 0 5 0 3 0 0 0 1 0 - 39/8 0 3/8

A7 0 1 0 1 0 1 0 0 1 13/8 0 1/8

A4 0 2 0 0 0 0 0 0 0 1/2 0 - 3/2

A9 0 1 0 0 0 0 0 0 0 1/4 1 - 5/4

j

*

x =

( ) 1,0,2,2,14,5

f x = *( )

52

D - 4 0 0 0 0 0 -1 0 0 - 4

Ph−¬ng ¸n tèi −u ,

3.2. Bµi tËp vËn dông thuËt to¸n Land - Doig

Gi¶i c¸c bµi to¸n quy ho¹ch nguyªn sau b»ng ph−¬ng ph¸p nh¸nh vµ cËn cña

= -

)

( f x

min

Land-Doig

+ fi x x 3 1 2

Bµi tËp 5:

3

2

x

3

2

+

- £

5

4

10

x

2

+

‡

2

5

x

x 1 x 1 x 1

2

    

£

- 58 -

0

jx - nguyªn,

jx ‡

,

Lêi gi¶i

)P ¢ bá qua ®iÒu kiÖn

jx - nguyªn ta thu

B−íc chuÈn bÞ: Gi¶i bµi to¸n (

0

®−îc ph−¬ng ¸n tèi −u:

m D ( )

3

5

x =

(

)

13 9 , 7 7

 = -  

13 9  = - +  7 7 

x =

· , .

0x kh«ng nguyªn vµ cã:

0 1

13 7

=

1

B−íc 1: V× kh«ng nguyªn ⇒

0 x 1

 

 = 

13 7

  

  

=

. Ta chia tËp D thµnh hai tËp :

{

/

} 1

1 D 1

x D x 1

˛ £

{ = ˛

} 2

1 D 2

x D x 1/

‡

1

x =

(1,

)

)1 1P

5 4

=

)

)

1

1 f x (

1 m D ( 1

 

 

5 4

 = - + 3  

 = -  

1

) +¥=1

f=1

¢ Gi¶i bµi to¸n ( ta ®−îc ph−¬ng ¸n tèi −u: vµ t×m ®−îc

2D

( 2Dm

)P ¢ thÊy 2(

1

1D thµnh 2 tËp:

=

Gi¶i bµi to¸n nªn .

/

2 D 1

1

=

˛ £

=

D

/

} 1 }2

1

x

2 2

1 1

2

2

 

 = 

5 4

  

  

2

2

2

‡ ˛ B−íc 2: Ta ph©n nh¸nh { 1 x D x 1 2 { xDx V×

)m D =+¥ 1(

1D = ˘

)P ¢ thÊy 1(

2

2

x =

(1,2)

Gi¶i bµi to¸n nªn

)P ¢ ta ®−îc ph−¬ng ¸n tèi −u 2(

2

2

=-

f x= (

)

)

1 . S¬ ®å ph©n nh¸nh ®Õn b−íc nµy nh− sau:

m D 2(

Gi¶i bµi to¸n vµ t×m ®−îc kû lôc

- 59 -

1

D m= -5

1D

1

2D

2

¥+

m= -1 m =+¥

1D

2

2D

2

2

= -

)

m D= (

)

1

m = m = -1

1 m D ( 1

2

2D ta

2

2

2

=

= -

)

f x (

)

1

x =

(1, 2)

. T¹i Ta thÊy cËn d−íi nhá nhÊt cña c¸c ®Ønh treo lµ:

m D ( 2

ghi ®−îc kû lôc . tho¶ mQn ®iÒu kiÖn nguyªn nªn

=

= -

)

* x

( ) 1, 2 ;

( * f x

1

nã lµ ph−¬ng ¸n tèi −u cña bµi to¸n ®Q cho, thuËt to¸n kÕt thóc

=-

.

( ) f x

x x 1

2 min

+

- fi Bµi tËp 6

11

x

38

2

x 1 +

£

2 7

x

£

2 5

x

5

x 1 x 4 1

2

    

- £

Lêi gi¶i

)P

¢ bá ®i ®iÒu kiÖn nguyªn cña c¸c biÕn sè B−íc chuÈn bÞ. Gi¶i bµi to¸n (

=

ta ®− îc ph−¬ng ¸n tèi −u:

) ( m D

0 f x (

)

7

0x

,

 

 

40 9

23 9

 = -  

40 23  = -  9 9 

  

=  

]

=

4

0 x 1

- ;

0x kh«ng nguyªn vµ cã:

40 9

40 9

[ =⇒= 0 x  1 

  

B−íc 1. V× .Ta chia

=

D thµnh 2 tËp:

/

1 D 1

=

£ ˛

D

/

}4 }5

1 2

{ xDx 1 { xDx 1

‡ ˛

)1 1P

¢ ta ®−îc ph−¬ng ¸n tèi −u: Gi¶i bµi to¸n (

- 60 -

=

,4

1x

1 f x (

)

6

)1 vµ t×m ®−îc ( m D 1

 

 

30 11

74 11

  

 = -  

 = -  

.

) +¥=1

f=1

=   Gi¶i bµi to¸n(

2D

( 2Dm

)1 2P

1

¢ thÊy nªn

=

B−íc 2. Ta ph©n nh¸nh

D

{ x

D

x

/

2 1

1 1

2

2

=

1D thµnh 2 tËp: }2 ]

£ ˛

=

{

} 3

/

2

D 2

1 x D x 1 2

1 2

30 11

=  

  

˛ ‡ v× [ x

)2 1P

2

=

2,

2x

)2

f x (

)

5

¢ Gi¶i bµi to¸n( ta ®−îc ph−¬ng ¸n tèi −u:

( m D 1

 

 

15 4

23 4

 = -  

 = -  

=  

  

vµ t×m ®−îc .

)2 2P

2

2

=

x

3,

)

f x (

)

5

¢ ta ®−îc ph−¬ng ¸n tèi −u: Gi¶i bµi to¸n (

  

  

11 2

=  

 = -  

 = -  

) =2

. vµ t×m ®−îc ( 2 m D 2

5   2  )2 ( 1Dm

( 2Dm

2

V× nªn ta ph©n nh¸nh t¹i ®©u còng ®−îc.

1D thµnh hai tËp:

=

B−íc 3: Chia

/

3 D 1

=

£ ˛

]

=

D

/

}3 }4 v× [ x

3

3 2

{ 2 xDx 1 1 { 2 xDx 1 2

2 1

15 4

= 

 

‡ ˛

)3 1P

3

=

= -

)

)

3 =x

)2,3 (

( f x

5

¢ ta ®−îc ph−¬ng ¸n tèi −u: Gi¶i bµi to¸n (

( 3 m D 1

vµ t×m ®−îc kû lôc: .

) +¥=3

f=3

( 2Dm

3

3

= -

=

= -

2D )

¢ Gi¶i bµi to¸n ( nªn .

5

)

)

( f x

5

)3 2P ( 3 m D 1

2 2

1D ta ghi ®−îc kû lôc:

( 3 m D 1

ta thÊy ( ) m D= . T¹i .

3 =x

f x =- *( )

5

x =

(3,2)

Ta thÊy )2,3 ( tho¶ mQn ®iÒu kiÖn nguyªn nªn nã lµ ph−¬ng ¸n tèi −u cña bµi to¸n

®Q cho, thuËt to¸n kÕt thóc * ,

( ) f x

max

= - x 1

+ x 3 2

x 3 3

fi Bµi tËp 7

- 61 -

+

2

x

x

4

- £

4

3

2 x

3 2

- £

2 x 2

x

3

x 1 x 1 + x 3 1

+ 2

3

   - 

£

x

0,

x

j =

1,3

j

j

‡ - nguyªn,

Lêi gi¶i

)P

¢ B−íc chuÈn bÞ: Gi¶i bµi to¸n ( bá ®i ®iÒu kiÖn nguyªn cña c¸c biÕn sè

0

0

=

=

m D (

)

f x (

)

+ · 3

14

x =

(

,0,

)

ta ®− îc ph−¬ng ¸n tèi −u:

 

 

1 2

9 2

1 2

9 2

  

 =  

=

4

,

0x kh«ng nguyªn vµ cã:

0 3

0 x 3

 

 = 

9 x = ⇒ 2

9      2

B−íc 1. V× . Ta chia D

thµnh hai tËp:

{ = ˛

/

} 4

1 D 1

x D x 3

=

£

{

/

} 5

1 D 2

x D x 3

˛ ‡

1

x =

)1 1P

1 ( ,0,4) 2

1

=

+ ·

=

)

f x (

)

3 4

12

¢ Gi¶i bµi to¸n ( ta ®−îc ph−¬ng ¸n tèi −u: vµ t×m ®−îc

1 m D ( 1

 

 

1 2

 =  

1

.

(2,2,5)

x =

   )1 2P

=

=

)

1 f x (

)

11

¢ Gi¶i bµi to¸n ( ta ®−îc ph−¬ng ¸n tèi −u vµ t×m ®−îc

1 m D ( 2

  

  

1

(

)

)

(

.

m D = 11 <

m D =12 nªn ta ph©n nh¸nh t¹i

1 1

1 2

1D .

1

Ta thÊy

1D thµnh hai tËp:

=

B−íc 2: Chia tËp

=

{

/

} 0

0

2 D 1

1 x D x 1 1

1 1

1 x 1

 

 = 

1 x = ⇒ 2

1      2

=

˛ £ ; V×

{

/

} 1

2 D 2

1 x D x 1 1

˛ ‡ ;

2

m D = +¥ )

(

1D = ˘

2 1

)2 1P

2

2

x =

(1,

, 4)

m D =

) 11

(

¢ Gi¶i bµi to¸n ( thÊy nªn .

2 2

)P ¢ ta ®−îc ph−¬ng ¸n tèi −u 2(

2 3

vµ t×m ®−îc Gi¶i bµi to¸n

- 62 -

1

1

x =

(2,2,5)

(

m D =

) 11

(

m D = )

2 2

1 2

2D cã

1

=

=

)

1 f x (

11

Ta thÊy mµ t¹i tho¶ mQn ®iÒu kiªn

1 m D 2(

2D ta ghi ®−îc kû lôc

  

 )  

1

x =

(2,2,5)

nguyªn cña bµi to¸n ®Q cho. VËy t¹i vµ

*

*

=

lµ ph−¬ng ¸n tèi −u cña bµi to¸n ®Q cho, thuËt to¸n kÕt thóc

x

(2, 2,5),

f x (

= ) 11

.

f x ( )

2

max

= + x 1

x 2

+

fi Bµi tËp 8

4

5

x

22

x 1

2

+

£

x

11

£

2 x

1

x 1 + x 1

2

  3  - 

0

j =

1, 2

£

jx ‡

jx - nguyªn,

,

Lêi gi¶i

)P

¢ B−íc chuÈn bÞ: Gi¶i bµi to¸n ( bá ®i ®iÒu kiÖn nguyªn cña c¸c biÕn sè

ta cã b¶ng ®¬n h×nh tèi −u sau:

jc

C¬ Ph−¬ng - 1 -2 0 0 0

së ¸n A1 A2 A3 A4 A5 c.s

-1 A1 17/9 1 0 1/9 0 - 5/9

0 A4 22/3 0 0 - 4/3 1 11/3

-2 A2 26/9 0 1 1/9 0 4/9

j

0

0

=

D 0 0 - 1/3 0 - 1/3

x =

(

)

m D (

)

f x (

)

2

7

 

 

17 26 , 9 9

17 9

26 = - 9

 = -  

  

=

1

- · Ph−¬ng ¸n tèi −u: .

0x kh«ng nguyªn vµ cã

0 x 1

 

 = 

17 9

  

  

B−íc 1. V× .Ta chia D thµnh hai tËp:

} 1

{ = ˛ D x D x 1/

1 1

=

£

{

D

/

} 2

1 2

x D x 1

˛ ‡

)1 1P

=

=

)

1 f x (

)

5

x =

(1,2)

¢ Gi¶i bµi to¸n ( ta ®−îc ph−¬ng ¸n tèi −u:

1 m D 1(

 

 

vµ t×m ®−îc . 1

- 63 -

1

)P ¢ ta ®−îc ph−¬ng ¸n tèi −u: 2(

1

=

)

7

2 ( f x

x =

(2,

)

1 ( m D 2

Gi¶i bµi to¸n

 

 ) 

14 5

14 5

 = + · 2 2  

 =  

1

)

= > 7

vµ t×m ®−îc .

= nªn ta ph©n nh¸nh t¹i ) 5

1 m D ( 2

1 m D ( 1

2D .

1

V×

1 x D x 2/ 2

2 D 1

£

2D thµnh hai tËp: } 2 } 3

2 2

1 2

2

‡ B−íc 2: Ta ph©n nh¸nh { = ˛ { = ˛ D x D x 2/

)P ¢ ta ®−îc ph−¬ng ¸n tèi −u: 1(

2

2

2

=

=

)

f x (

)

7

x =

(3,2)

Gi¶i bµi to¸n

m D 1(

 

 

2

2

m D = +¥ )

(

vµ t×m ®−îc .

2D = ˘

2 2

)P ¢ ta thÊy 2(

2

= >

) 7

= .VËy t¹i ) 5

vµ . Gi¶i bµi to¸n

2 m D ( 2

1 m D ( 1

2D ta ghi ®−îc kû lôc

2

7

(

x =

(3, 2)

m D = vµ )

§Õn b−íc nµy ta thÊy

2 2

x =

(3,2)

tho¶ mQn ®iÒu kiÖn nguyªn nªn nã lµ ph−¬ng ¸n tèi −u

f x = . *( ) 7

cña bµi to¸n ®Q cho, thuËt to¸n kÕt thóc * ,

3.3. Bµi tËp ®−a bµi to¸n vÒ bµi to¸n c¸i tói ®Ó gi¶i

Bµi tËp 9: Gi¶i bµi to¸n sau

Mét nhµ m¸y s¶n xuÊt vËt liÖu x©y dùng cÇn s¶n xuÊt 4 lo¹i vËt liÖu x©y

dùng. BiÕt nguyªn liÖu nhµ m¸y sö dông cÇn ®Ó s¶n xuÊt 4 lo¹i nguyªn liÖu trªn

lµ kh«ng qu¸ 20 tÊn. Nguyªn liÖu nhµ m¸y sö dông ®Ó s¶n xuÊt mét vËt liÖu x©y

dùng lo¹i 1 lµ 6 tÊn vµ lîi nhuËn mµ nhµ m¸y thu ®−îc tõ mét vËt liÖu lo¹i 1 lµ 2

®¬n vÞ tiÒn, nguyªn liÖu nhµ m¸y sö dông ®Ó s¶n xuÊt mét vËt liÖu x©y dùng lo¹i

2 lµ 3 tÊn vµ lîi nhuËn nhµ m¸y thu ®−îc tõ mét vËt liÖu lo¹i 2 lµ 7 ®¬n vÞ tiÒn,

nguyªn liÖu nhµ m¸y sö dông ®Ó s¶n xuÊt mét vËt liÖu lo¹i 3 lµ 2 tÊn vµ lîi nhuËn

nhµ m¸y thu ®−îc tõ mét vËt liÖu lo¹i 3 lµ 3 ®¬n vÞ tiÒn, nguyªn liÖu nhµ m¸y sö

dông ®Ó s¶n xuÊt mét vËt liÖu x©y dông lo¹i 4 lµ 1 tÊn vµ lîi nhuËn thu ®−îc tõ

mét vËt liÖu lo¹i 4 lµ 1 ®¬n vÞ tiÒn. HQy gióp nhµ m¸y lùa chän s¶n xuÊt lo¹i vËt

liÖu nµo vµ víi sè l−îng lµ bao nhiªu ®Ó nhµ m¸y thu ®−îc lîi nhuËn lín nhÊt.

Lêi gi¶i

M« h×nh to¸n häc cña bµi to¸n trªn nh− sau:

- 64 -

+

+

+

F x

= ( ) 2

7

max

x 1

x 2

x 3 3

x 4

+

+

+

fi

6

3

2

20

x 1

x 2

x 3

x 4

0

j =

1, 4

£

jx - nguyªn,

jx ‡

,

VËn dông ph−¬ng ph¸p gi¶i bµi to¸n c¸i tói ®Ó gi¶i bµi to¸n trªn.

=

y

:0

( ) 0 = 0

F 1

=

=

=

y

:1

( ) 1

0.2

0

F 1

1 6

= 2 

 

=

=

=

:2

( ) 2

0.2

0

y

F 1

2 6

 

= 2 

=

=

=

y

:3

( ) 3

0.2

0

F 1

3 6

= 2 

 

=

=

=

y

:4

( ) 4

0..2

0

F 1

4 6

= 2 

 

=

=

=

y

:5

( ) 5

0.2

0

F 1

5 6

= 2  

  

=

=

y

:6

( ) 6

= 21.2

F 1

6 6

= 2  

  

=

=

y

:7

( ) 7

= 21.2

F 1

7 6

= 2  

  

=

=

y

:8

( ) 8

= 21.2

F 1

8 6

= 2 

 

=

=

y

:9

( ) 9

= 21.2

F 1

9 6

= 2  

  

=

)

=

y

:10

( 10

= 21.2

F 1

10 = 2  6 

  

=

=

=

y

:11

( ) 11

1.2

2

F 1

11 6

= 2  

  

=

)

=

=

y

:12

( 12

2.2

4

F 1

12 6

= 2 

 

Khi k = 1 ta cã:

- 65 -

=

=

=

:13

( ) 13

2.2

4

y

F 1

  

13 = 2  6 

)

=

=

=

:14

( 14

2.2

4

y

F 1

14 6

 

= 2 

=

)

=

=

y

:15

( 15

2.2

4

F 1

15 6

= 2 

 

=

)

=

=

y

:16

( 16

2.2

4

F 1

16 6

= 2 

 

)

=

=

=

:17

( 17

2.2

4

y

F 1

 

17 = 2  6

=

)

=

=

y

:18

( 18

3.2

6

F 1

18 6

= 2  

  

=

)

=

=

y

:19

( 19

3.2

6

F 1

19 6

= 2 

 

=

)

=

=

y

:20

( 20

3.2

6

F 1

20 6

= 2  

  

=

y

:0

=

+

y

:1

F 1

F 2

+

=

=

y

:2

F 2

+

=

=

} 0 = } 0 = +

y

:3

F 1

F 1

F 2

+ + +

= = =

+

} =

:4 :5 :6

y y y

( ) 0

F 1

=

+

} =

( ) 2.7;4

( ) 1

F 1

F 1

y

+

=

+

+

} =

y

( ) 2.7;5

( ) 2

F 1

F 1

Khi k = 2 ta cã: ( ) 0 = 0 F 2 ( ) ( ) { = 1 1 0.7max ( ) ( ) { 2 F 2 0.7max 1 ( ) } 7 ( ) ( ) { = 3 0 1.7;3 0.7max ( ) } 7 ( ) ( ) { = + = F 4 F 1 F 1.7;4 0.7max 2 1 1 ( ) } 7 ( ) ( ) { = + = F 5 2 F 1.7;5 F 0.7max 2 1 1 ( ) { ( ) ( ) = + 6 F 0.7max 1.7;6 F 2.7;3 F 2 1 1 { } 14 + + + = 14;07;2 0max 0 ( ) ( ) { = + + 1.7;7 F 0.7max F 7 :7 2 1 } { = + + + = 14 max 0 2;7 0;14 0 ( ) { ( ) = 0.7max :8 F 1.7;8 F 8 2 1 } { + = + + = 14 max 0 2;7 0;14 0

- 66 -

=

+

+

+

+

} =

:9

( ) 3.7;3

( ) 0

F 1

F 1

= {

( ) 1.7;9 +

+

y

=

=

+

+

+

+

)

y

10:

( ) { F 0.7max 9 F 2 1 = + 14;07;20max 21;0 ( ( ) 10 ;7.1 10 max{7.0

( ) F 2.7;6 1 } 21 + = 0 ( ) 7 ;7.2

( ) 4 ;7.3

( ) 1 }

=

F 2

F 1

F 1

F 1

F 1

=

+

+

+

+

=

+

=

+

)

+ = + max{0 2;7 2;14 0;21 0} 21 ( ) ( ) 8 ;7.2 11 ;7.1

( 11 max{7.0

y

11:

( ) 5 ;7.3

( ) 2 }

=

F 1

F 1

F 2

F 1

F 1

+

=

+ =

+

=

+

+

=

+

+

)

+ max{0 2;7 2;14 0;21 0} 21 ( ) + 12 ;7.1

( 12 max{7.0

( ) 9 ;7.2

y

12:

( ) 6 ;7.3

( ) 3 ;7.4

( ) 0 }

F 1

F 1

F 2

F 1

F 1

F 1

=

+ =

+

+

+

=

=

+

+

+

+

+

)

+ max{0 2;7 2;14 0;21 0;28 0} 28 ( ) ( ) 7 ;7.3 13 ;7.1

( 13 max{7.0

( ) 10 ;7.2

13:

y

( ) 4 ;7.4

( ) 1 }

F 2

F 1

F 1

F 1

F 1

F 1

=

+

+

+

=

=

+

+

+

+

+

)

+ = + max{0 2;7 2;14 2;21 0;28 0} 28 ( ) 11 ;7.2

( 14 max{7.0

( ) 14 ;7.1

14:

y

( ) 8 ;7.3

( ) 5 ;7.4

( ) 2 }

F 2

F 1

F 1

F 1

F 1

F 1

+

+

+

+ max{0 4;7 2;14 2;21 0;28 0} 28

= )

+

+

+

+

+

=

=

( ) 4.7;6

( ) ;3

y

F 1

F 1

0.7max{ +

:15 +

+

+

35;0 +

F 1 + +

( ) 4.7;7

( ) ;4

5.7 = y

F 1

F 1

F 1

F 1 +

0.7max{ +

F 1 :16 +

=

+ +

35;0 +

+

5.7 = y

F 1

+

F 1 :17 +

( ) F 3.7;9 1 + = }0 35 ( ) 3.7;10 = }0 35 ( ) 3.7;11 + +

+

4.7 = y

F 1

) ( 1.7;18 +

+

+

+

( ) ;7

5.7 = y

F 1

=

+

35 ( ) F ;6 1 = 42 + F 1 = 42

+

F 1 :19 + 5.7 = y

+ ) +

21;4 ) ( 2.7;17 + +

F 1 :20 +

+ = ( ) ( ) 2.7;12 1.7;15 F 1 + + + 14;47;40max{ 28;2 21;2 ( ( ) ) ) = + F 1.7;16 2.7;13 1 + + + 14;47;40max{ 28;2 21;2 ( ( ) ) ) + F 0.7max{ 1.7;17 2.7;14 1 ( ) = + + 14;47;40max{ F }2 1 ) ( + F 0.7max{ 2.7;15 1 ( ) + = + 14;47;60max{ }0 21;4 F 1 ) ( ) ( ) = F 0.7max{ 1.7;19 2.7;16 1 ( ) + + + 14;47;60max{ F }1 1 ( ) = + F F 0.7max{ 1.7;20 1 1 ( ) ( ) + = 6.7;5 }2

F 1 + 21;2 28;2 ) ( + F 3.7;12 1 + + 28;2 35;2 ( ) + F 3.7;13 1 + 28;2 35;2 ) ( + F 3.7;14 1 + + 14;47;60max{

( ) F ;8 1 + = }0 35;0 ( ) + F 4.7;9 1 + + 42;0 }0 ) ( + F 4.7;10 1 + + 42;0 }0 ) ( + F ;11 1 + 28;2

21;4

;2

F 1

( F 15 2 ( ) = }0 ( F 16 2 ( ) = }1 ( F 17 2 ( ) + 5.7;5 F 1 ) ( = F 18 :18 2 ( ) + 6.7;3 ( F 19 2 ( ) 6.7;4 ( F 20 2 ( ) 5.7;8 +

=

4.7 +

F 1 42;0

}0

35

F 1 42

=

y

:0

F 3

=

=

+

:1

y

F 3

F 2

=

=

+

+

:2

y

{ 0.3max { 0.3max

} 0 ( ) = 1 ( ) 1.3;2

( ) 0

} 3 =

F 3

F 2

F 2

Khi k = 3 ta cã: ( ) 0 = 0 ( ) 1 ( ) 2

- 67 -

=

+

=

=

+

+

y

:3

( ) 1.3;3

}1 ( )

} 7 =

=

+

+

+

+

{

( ) 3 F 3 ( ) 4 max 3.0

F 2 ( ) + 4 ;3.1

F 2 ( ) 2 ;3.2

4y = :

} + = 7 max 0 7;3 0;6 0

F 3

F 2

F 2

F 2

=

+

+

+

+

+

{

{ 0.3max { {

( ) 5 max 3.0

{ + 03;70max } ( ) 0 } ( ) 1

( ) 5 ;3.1

( ) 3 ;3.2

5y = :

=

} + = 10 max 0 7;3 7;6 0

F 3

F 2

F 2

F 2

=

+

+

+

+

( ) 6 max{3.0

( ) 6 ;3.1

( ) 4 ;3.2

( ) 2 ;3.3

( ) 0 }

6y = :

F 3

F 2

F 2

F 2

F 2

+

+

+

=

+ = max{0 14;3 7;6 0;9 0} 14

=

+

+

+

+

( ) 7 max{3.0

( ) 7 ;3.1

( ) 5 ;3.2

( ) 1 }

=

y = : 7

F 3

F 2

F 2

F 2

F 2

+

+

=

+

+

+

+

+

+ = + = max{0 14;3 7;6 7;9 0} 14 ( ) 6 ;3.2

( ) 8 max{3.0

( ) 8 ;3.1

( ) 4 ;3.3

( ) 2 ;3.4

( ) 2 }

y = : 8

( ) 3 ;3.3

F 2

F 2

F 3

F 2

F 2

F 2

=

=

+

+

+

+

+

+ + + + + =

( ) 9 max{3.0

( ) 7 ;3.2

( ) 5 ;3.3

( ) 3 ;3.4

( ) 1 }

y = : 9

F 2

F 2

F 2

F 3

F 2

F 2

= max{0 14;3 14;6 7;9 0;12 0} 17 ( ) 9 ;3.1 =

+

=

=

+

+

+

+

( ) 4.3;4

( ) ;2

y

0.3max{

( ) 1.3;10

F 2

F 2

+

:10 +

F 2 +

+

( ) F 2.3;8 2 + +

( ) 3.3;6 + =

5.3

0max{

3;21

21

F 2 15;0

9;14

F 2

=

=

+

+

+

+

+

y

0.3max{

6;14 ( ) 1.3;11

( ) 4.3;5

( ) ;3

F 2

F 2

:11 +

+

F 2 +

+

0max{ =

+

5.3 = y

6;21 ) ( 1.3;12 +

12;7 ( ) F 2.3;9 2 + + 12;7 ) ( 2.3;10 +

F 2 15;7 + F 2 +

}0 ( ) 3.3;7 + = }0 ( ) 3.3;8 +

( ) 4.3;6 +

+

( ) ;4 =

5.3

0.3max{ ( ) + = }0

3;28

9;14

24 + F 2 15;7

18;0

F 2 }0

28

F 2

F 2

=

=

+

+

+

+

+

y

( ) F 10 3 ( ) = }0 ( ) F 11 3 ( ) = }1 F 2 ( ) F 12 :12 3 ( ) + 6.3;2 ( ) 13 max{3.0

13:

3;21 + F 2 0max{ ( ) 13 ;3.1

9;14 + F 2 + 6;21 ( ) 11 ;3.2

12;14 ( ) 9 ;3.3

( ) 7 ;3.4

( ) 5

F 3

F 2

F 2

F 2

F 2

F 2

+

+

+

+

+

+

+

+

{

3.5

(1)}

+ + + + + = = max{0 21;3 14;6 7;9 7;12 0} 21

F 2

F 2

=

=

+

+

+

+

+

y

:14 +

} + = max 0 28;3 21;6 21;9 14;12 7;15 7;18 0 28 ( ( ) ) 2.3;12 4.3;8 + +

( ) 3.3;10 +

( ) ;6 +

0.3max{ ( ) + 7.3;2

( ) 1.3;14 ( ) = }0

F 2 + 12;14

F 2 0max{

F 2 + 6;28

3;28

9;21

F 2 15;14

;7

F 2

F 2 + F 2

5.3 + =

+

+

+

+

+

31 ) =

18 y

F 2

F 2

+

F 2 +

( ) 13 ;3.2 +

( ) 9 ;3.4 +

( ) F 7 ; 2 +

F 2 +

+

( ) 3 ;3.7

( ) ( ) 11 ;3.3 15 ;3.1 ( ) + = 1 } max{0 35;3 28;6 21;9 21;12 14;15 7;

F 2

F 2

(3);3.6 ( ) F 14 3 ( ) F 6.3;4 2 = }21;0 ( 15: F 15 max{3.0 3 ( ) + 5 ;3.6 =

3.5 +

F 2 18 7;21} 35

=

- 68 -

+

+

+

+

+

+

=

=

y

( ) ;6

( ) 2.3;14 +

+

( ) 3.3;12 +

+

:16 +

0.3max{ ( ) 8.3;2

( ) 1.3;16 ( ) = }0

F 2 0max{

3;35

F 2 6;28

9;28

( ) F 4.3;10 2 + + 12;21

( ) F 5.3;8 2 + 15;14

+ 18;14

F 2 ;7

F 2 + F 2

F 2

F 2 35 =

+

+

+

+

+

( ) ;9

+

) ( 3.3;13 + +

) ( 4.3;11 +

+

+

) ( 2.3;15 ( ) = }1

) ( 1.3;17 ( ) 8.3;3

F 2 0max{

0.3max{ ( ) + 7.3;5

3;35

9;28

F 2 6;35

F 2 12;21

;21

F 2 F 2

+

+

+

+

5.3 + 15 = y

F 2

+

+

( ) 4.3;12 + +

( ) ;10 +

( ) 3.3;14 ( ) = }0

F 2 0max{

3;42

F 2 6;35

;28

F 2

( ) 2.3;16 ( ) 9.3;2 =

5.3 + =

24;7 +

42 +

+

+

9 y

F 2

+

( ) ;11 +

F 2 F 2 + }27;0 ( ) 2.3;17 ( ) + 9.3;3

( ) 3.3;15 ( ) = }1

( ) F 4.3;13 2 + + 0max{

3;42

F 2 6;35

;35

5.3 + =

+

+

9 y

+

+

+

( ) ;12 +

F 2 0max{

;42

( ) F 16 3 ( ) 7.3;4 6.3 =+ + }0 24;021 ) ( = y F :17 17 3 ( ) + 6.3;7 F 2 + 21;7 18;14 ( ) = F :18 18 3 ( ) + 6.3;8 F 2 + 12;28 15;21 ( ) = F :19 19 3 ( ) + F 6.3;9 2 + 12;28 15;21 ( ) = F :20 20 3 ( ) + 6.3;10 + +

5.3 +

( ) 3.3;16 ( ) F 10.3;2 2 + +

=

F 2 6;42

F 2 + F F 2 2 + =+ 24;7 }0 38 ( ) + F 0.3max{ 1.3;18 2 ( ) ( ) + + F 7.3;6 8.3;4 F 2 2 + + + 21;14 18;14 ( ) + F 1.3;19 0.3max{ F 2 2 ( ) ( ) + + 8.3;5 F 7.3;7 F F 2 2 2 + + + =+ 21;14 27;7 24;7 }0 42 ( ( ) ) + + + F F F 1.3;20 2.3;18 2 2 2 ( ) ( ) + F F 8.3;6 9.3;4 2 2 + + + 21;14

F 2 12;28

24;14

15;28

18;21

27;7

( ) F 4.3;14 2 ( ) = F }0 2 + 30;0

}0

45

F 2 + 18;21 0.3max{ ( ) + 7.3;8 + 3 9;35 Khi k = 4 t−¬ng tù ta cã:

=

=

=

=

y

1 1 :

F

(1 1 )

2 4

y

0 :

F

( 0 )

0

4

4

=

=

=

=

y

F

1 :

( 0 )

1

y

1 2 :

F

(1 2 )

2 8

4

=

=

=

=

y

4 F

2 :

( 2 )

3

4

y

1 3 :

F

(1 3 )

2 9

4

=

=

y

F

3 :

( 3 )

7

=

=

4

(1 4 )

3 1

1 4 :

y

F

4

=

=

y

F

4 :

( 4 )

8

=

=

4

(1 5 )

3 5

1 5 :

y

F

4

=

=

y

F

5 :

( 5 )

1 0

4

=

=

(1 6 )

3 6

1 6 :

y

F

4

=

=

y

F

6 :

( 6 )

1 4

4

=

=

(1 7 )

3 8

1 7 :

y

F

4

=

=

y

F

7 :

( 7 )

1 5

4

=

=

(1 8 )

4 2

1 8 :

y

F

4

=

=

y

F

8 :

( 8 )

1 7

4

=

=

(1 9 )

4 3

1 9 :

y

F

4

=

=

y

F

9 :

( 9 )

=

=

2 0 :

( 2 0 )

4 5

y

F

4

=

2 1 =

y

4 F

1 0 :

(1 0 )

2 2

4

=⇒=

45

x

;0

F 4

4

=⇒=

45

x

;1

F 3

3

F 2

)

=⇒=

( 20 ( 18

42

x

;6

) ( = 20 45 F 3 ) 42 ( = 18 ( ) 0 = 0

F 2

2

F 1

Ta thÊy: ( ) 20 )

- 69 -

=⇒=

( ) 0

0

0

F 1

x 1

*

*

=

)

=

x

( ) ;0,1,6,0

( xF

45

Ph−¬ng ¸n tèi −u: .

+

+

Bµi tËp 10: Gi¶i bµi to¸n c¸i tói sau.

F x

7

5

max

= ( ) 11 x 1

x 2

x 3

+

+

fi

6

4

3

20

x 1

x 2

x 3

j =

1,3

£

jx - nguyªn,

0jx ‡

,

Lêi gi¶i

Gi¶i bµi to¸n c¸i tói trªn b»ng c¸ch dïng hÖ thøc Dantzig:

F y 0 ( )

1( )F y

j y 1( )

F y 2 ( )

j y 2 ( )

F y 3( )

j y 3 ( )

y

0 0 0 0 0 0 0 0

1 0 0 0 0 0 0 0

2 0 0 0 0 0 0 0

3 0 0 0 0 0 5 3

4 0 0 7 0 2 7 2

5 0 0 7 0 2 7 2

6 0 11 11 1 1 11 1

7 0 11 11 1 1 12 3

8 0 11 14 1 2 14 2

9 0 11 14 1 2 16 3

10 0 11 18 1 2 18 2

11 0 11 18 1 2 19 3

12 0 22 22 1 1 22 1

13 0 22 22 1 1 23 3

14 0 22 25 1 2 25 2

15 0 22 25 1 2 27 3

- 70 -

16 0 22 1 29 2 29 2

17 0 22 1 29 2 30 3

18 0 33 1 33 1 33 1

19 0 33 1 33 1 34 3

20 0 33 1 36 1 36 2

= F 3(20) 36

*

j

= ⇒

x = . 1

* 2

x = , 3 0

Ta thu ®−îc gi¸ trÞ tèi −u .

*

=

T×m ph−¬ng ¸n tèi −u cña bµi to¸n: 3(20) 2

(20

= )

= (20 4)

(16) 2

x = + = 2 1 1 2

j TiÕp tôc: 3

a 2

j 3

j 3

*

- = (16 4)

(12) 1

= ⇒

x = 1 1

j 3

j 3

- - ⇒

(12

- = (12 6)

= (6) 1

x = + = . 1 1 1 2

j 3

= a ) 1

j 3

j 3

- ⇒ *

(6

- = (6 6)

= (0) 0

j 3

= a ) 1

j 3

j 3

*

F x = *(

) 36

- .

x =

(2, 2, 0)

Ph−¬ng ¸n tèi −u: ,

+

5

max

+

2

13

x 2 x 2

+ fi x 3 + £ x 3

8 x  1  3 x  1

0

j =

1, 3

Bµi tËp 11: Gi¶i bµi to¸n c¸i tói sau:

jx ‡

, nguyªn,

Lêi gi¶i

Ta gi¶i bµi to¸n trªn theo hÖ thøc Dantzig:

y

0 F0(y) 0 F1(y) 0 j1(y) 0 F2(y) 0 j2(y) 0 F3(y) 0 j3(y) 0

1 0 0 0 0 0 1 3

2 0 0 0 5 2 5 2

3 0 8 1 8 1 8 1

4 0 8 1 10 2 10 2

5 0 8 1 13 2 13 2

6 0 16 1 16 1 16 1

- 71 -

7 0 16 1 18 2 18 2

8 0 16 1 21 2 21 2

9 0 24 1 24 1 24 1

10 0 24 1 26 2 26 2

11 0 24 1 29 2 29 2

12 0 32 1 32 1 32 1

13 0 32 1 34 2 34 2

*

*

= . 0

x 2

x= 31,

Ta thu ®−îc gi¸ trÞ tèi −u cña bµi to¸n lµ F3(13) = 34.

T×m ph−¬ng ¸n tèi −u cña bµi to¸n j3(13) = 2 ⇒

TiÕp tôc do

(13

- = (13 2)

= fi (11) 2

1 1 2

j 3

= a ) 2

j 3

j 3

= + = * x 2

=

-

(11

= )

a

= (11 2)

= fi (9) 1

1.

j 3

2

j 3

j 3

* x 1

- -

(9

- = (9 3)

= fi (6) 1

1 1 2

j 3

= a ) 1

j 3

= + = * x 1

j 3

- .

j=

2 1 3.

(6

(6 3)

= 3(3) 1

j 3

j 3

fi = + = * x 1

- -

(3

- = (3 3)

(0)

j 3

= a ) 1 = a ) 1

j 3

j 3

*

x =

(3, 2,0)

- chÊm døt.

VËy ph−¬ng ¸n tèi −u cña bµi to¸n lµ .

KÕt luËn ch−¬ng 3:

Ch−¬ng 3 ®Q tr×nh bµy c¸c bµi tËp vËn dông lý thuyÕt quy ho¹ch nguyªn

tuyÕn tÝnh tæng qu¸t; c¸c thuËt to¸n gi¶i bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh:

thuËt to¸n c¾t cña Gomory, thuËt to¸n Land – Doig, ®−a bµi to¸n quy ho¹ch

nguyªn vÒ bµi to¸n c¸i tói ®Ó gi¶i b»ng ph−¬ng ph¸p truy to¸n cña quy ho¹ch

®éng gi¶i bµi to¸n c¸i tói. KÕt qu¶ tr×nh bµy ë ch−¬ng 3 cho thÊy tÇm quan träng

, tÝnh thiÕt thùc cña lý thuyÕt bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh ®èi víi c¸c

lÜnh vùc khoa häc kü thuËt, c¸c ho¹t ®éng thùc tiÔn cña ®êi sèng xQ héi.

- 72 -

KÕt luËn

Theo h−íng ®i s©u nghiªn cøu bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh kho¸

luËn ®Q thu ®−îc nh÷ng kÕt qu¶ chÝnh sau:

• HÖ thèng ho¸ c¸c kiÕn thøc liªn quan ®Õn bµi to¸n quy ho¹ch tuyÕn tÝnh

tæng qu¸t, mét sè thuËt to¸n gi¶i bµi to¸n quy ho¹ch tuyÕn tÝnh

• Tr×nh bµy tæng qu¸t lý thuyÕt x©y dùng c¸c thuËt to¸n gi¶i c¸c bµi to¸n

quy ho¹ch nguyªn tuyÕn tÝnh: thuËt to¸n c¾t Gomory, thuËt to¸n Land –

Doig, ph−¬ng ph¸p truy to¸n cña quy ho¹ch ®éng gi¶i bµi to¸n c¸i tói.

• X©y dùng hÖ thèng c¸c bµi tËp vËn dông c¸c thuËt to¸n trªn ®Ó gi¶i.

Kho¸ luËn cã thÓ ph¸t triÓn theo c¸c h−íng sau

• X©y dùng c¸c biÖn ph¸p chèng xoay vßng trong gi¶i bµi to¸n quy ho¹ch

nguyªn (theo thuËt to¸n c¾t Gomory)

• Nghiªn cøu, vËn dông lý thuyÕt gi¶i bµi to¸n quy ho¹ch nguyªn tuyÕn tÝnh

cho bµi to¸n quy ho¹ch nguyªn tæng qu¸t

C¨n cø vµo môc tiªu, néi dung nghiªn cøu ®Q ®Ò ra trong ®Ò c−¬ng nghiªn cøu vµ

sö dông hîp lý c¸c ph−¬ng ph¸p nghiªn cøu, t«i ®Q tiÕn hµnh nghiªn cøu ®óng

h−íng vµ hoµn thµnh kho¸ luËn. MÆc dï b¶n th©n t«i ®Q rÊt cè g¾ng, song do

®iÒu kiÖn vÒ thêi gian, tr×nh ®é chuyªn m«n cã h¹n nªn kho¸ luËn kh«ng tr¸nh

khái nh÷ng thiÕu sãt, t«i rÊt mong nhËn ®−îc sù chØ b¶o tËn t×nh cña c¸c thÇy

gi¸o, c« gi¸o vµ sù gãp ý cña c¸c b¹n sinh viªn ®Ó kho¸ luËn ®−îc hoµn chØnh

h¬n.

- 73 -

Tµi liÖu tham kh¶o

1. TrÇn §×nh ¸nh - Bµi tËp quy ho¹ch tuyÕn tÝnh.

2. PhÝ M¹nh Ban - Quy ho¹ch tuyÕn tÝnh cao ®¼ng s− ph¹m - NXB §HSP

2004.

3. PhÝ M¹nh Ban - Bµi tËp quy ho¹ch tuyÕn tÝnh - NXB §HSP 2004.

4. NguyÔn §øc NghÜa - Tèi −u ho¸ quy ho¹ch tuyÕn tÝnh vµ rêi r¹c - NXBGD

1996.

5. Bïi Minh TrÝ - Tèi −u hãa - NXB khoa häc kü thuËt - 2006.

6. Bïi Minh TrÝ - Bµi tËp tèi −u ho¸ - NXB Khoa häc vµ kü thuËt - 2006.

7. Bïi ThÕ T©m - NguyÔn Vò TiÕn. C¸c thuËt to¸n tèi −u ho¸ (Quy ho¹ch

tuyÕn tÝnh). NXB Giao th«ng vËn t¶i Hµ Néi 2000.

8. NguyÔn §Þch. Lý thuyÕt tèi −u ho¸ (tµi liÖu dïng cho sinh viªn ®¹i häc

më Hµ Néi, 2004.)

9. NguyÔn Ngäc Th¾ng – NguyÔn §×nh Ho¸. Quy ho¹ch tuyÕn tÝnh. NXB

§¹i häc quèc gia Hµ Néi 2004.

10. §Æng V¨n Uyªn. Quy ho¹ch tuyÕn tÝnh. S¸ch §¹i häc S− ph¹m – NXBGD

1998.

- 74 -

- 75 -