Bài toán qui hoạch tuyến tính đa mục tiêu trong không gian giá trị

Môc lôc

Më ®Çu

Ch¬ng I. Mét sè kh¸i niÖm c¬ b¶n vÒ gi¶i tÝch låi vµ bµi to¸n qui ho¹ch tuyÕn

tÝnh.

1.1 Mét sè kh¸i niÖm c¬ b¶n…………………..…………………...................7

1.1.1 TËp afine…………….……………..……………….…....................7

1.1.2 TËp låi…………………………..…………………….….................8

1.1.3 TËp låi ®a diÖn………………………..…………………...............10

1.1.4 §iÓm trong vµ ®iÓm trong t¬ng t¬ng ®èi……………..................13

1.1.5 Hµm låi………………………………………………....................15

1.1.6 TÝnh chÊt cùc trÞ………………………………………...................15

1.2 Ph¬ng ph¸p ®¬n h×nh gi¶i bµi to¸n qui ho¹ch tuyÕn tÝnh…....................16

1.2.1 M« h×nh to¸n häc……………………………………….................16

1.2.2 M« t¶ h×nh häc cña ph¬ng ph¸p ®¬n h×nh……………..................18

1.2.3 NghiÖm c¬ së vµ ph¬ng ¸n cùc biªn..............................................18

1.2.4 ThuËt to¸n ®¬n h×nh…………………………………….................19

1.2.5 C«ng thøc ®æi c¬ së vµ b¶ng ®¬n h×nh……………….....................26

1.2.6 VÊn ®Ò c¬ së cùc biªn vµ c¬ së xuÊt ph¸t………...…….................28

1.2.7 §èi ngÉu cña qui ho¹ch tuyÕn tÝnh..................................................29

1.3 KÕt luËn ...................................................................................................33

Ch¬ng II. Bµi to¸n qui ho¹ch tuyÕn tÝnh ®a môc tiªu.

2.1 ThÕ nµo lµ bµi to¸n tèi u ®a môc tiªu………………………..................34

2.2 M« h×nh to¸n häc vµ cÊu tróc tËp nghiÖm…………………….................39

2.2.1 Kh«ng gian víi thø tù tõng phÇn………………………...................40

1

2.2.2 NghiÖm h÷u hiÖu, nghiÖm h÷u hiÖu yÕu……………..….................41

2.3 Lý do gi¶i bµi to¸n qui ho¹ch tuyÕn tÝnh ®a môc tiªu trong kh«ng gian gi¸

trÞ .........................................................................................................................42

2.4 KÕt luËn.....................................................................................................43

Ch¬ng III. Bµi to¸n qui ho¹ch tuyÕn tÝnh ®a môc tiªu trong kh«ng gian gi¸ trÞ.

3.1 T¬ng ®¬ng h÷u hiÖu………………………………………...................45

3.2 C¬ së lý thuyÕt...........................................................................................47

3.2.1 Ph¬ng ph¸p xÊp xØ ngoµi…………………………….....................48

3.2.2 Bµi to¸n t×m ®Ønh cña tËp låi ®a diÖn………………….....................51

3.2.3 Ph¬ng ph¸p ph©n ho¹ch ®a diÖn thµnh c¸c ®¬n h×nh…..................60

3.3 ThuËt to¸n xÊp xØ ngoµi…………………………………….....................72

3.4 KÕt luËn ....................................................................................................75

KÕt luËn chung……………………………………………………................76

Phô lôc………………………………………………………………...............77

Tµi liÖu trÝch dÉn...……………………………………………..................109

2

Më ®Çu

Trong nh÷ng n¨m gÇn ®©y, c¸c ph¬ng ph¸p tèi u ho¸ ngµy cµng ®îc ¸p dông

s©u réng vµ hiÖu qu¶ vµo c¸c nghµnh kinh tÕ, kü thuËt, c«ng nghÖ th«ng tin vµ c¸c

nghµnh khoa häc kh¸c. C¸c ph¬ng ph¸p tèi u lµ c«ng cô ®¾c lùc gióp ngêi lµm

quyÕt ®Þnh cã nh÷ng gi¶i ph¸p tèt nhÊt vÒ ®Þnh lîng vµ ®Þnh tÝnh.

Mét trong nh÷ng líp bµi to¸n tèi u ®Çu tiªn ®îc ngiªn cøu trän vÑn c¶ vÒ lý

thuyÕt lÉn thuËt to¸n lµ bµi to¸n qui ho¹ch tuyÕn tÝnh (QHTT). Qui ho¹ch tuyÕn

tÝnh ngay tõ khi ra ®êi (vµo cuèi n¨m 30 cña thÕ kû XX) ®· chiÕm vÞ trÝ quan träng

trong tèi u ho¸. M« h×nh tuyÕn tÝnh lµ m« h×nh rÊt phæ biÕn trong thùc tÕ v× sù phô

phuéc tuyÕn tÝnh lµ sù phô thuéc ®¬n gi¶n vµ dÔ hiÓu nhÊt. H¬n n÷a, vÒ mÆt lý

thuyÕt chóng ta biÕt r»ng cã thÓ xÊp xØ víi ®é chÝnh x¸c cao c¸c bµi to¸n phi tuyÕn

bëi d·y c¸c bµi to¸n qui ho¹ch tuyÕn tÝnh. Nãi c¸ch kh¸c, c¸c thuËt to¸n gi¶i

QHTT lµ c«ng cô quan träng trong viÖc nghiªn cøu gi¶i c¸c bµi to¸n phøc t¹p h¬n.

ThuËt to¸n ®¬n h×nh do Dantzig ®Ò xuÊt tõ 1947, ®Õn nay vÉn lµ mét ph¬ng ph¸p ®-

îc sö dông réng r·i. MÆc dï vÒ lý thuyÕt ®©y lµ ph¬ng ph¸p cã ®é phøc t¹p mò.

Sau líp bµi to¸n qui ho¹ch tuyÕn tÝnh, nhiÒu híng nghiªn cøu kh¸c nhau xuÊt hiÖn

nh qui ho¹ch låi, qui ho¹ch toµn côc vµ lý thuyÕt ®iÒu khiÓn tèi u.

Bµi to¸n qui ho¹ch ®a môc tiªu còng míi ®îc ph¸t triÓn vµ trë thµnh mét

chuyªn ngµnh to¸n häc tõ nh÷ng n¨m 1950. Gi¶i ®¸p nh÷ng c©u hái ®Æt ra mµ qui

ho¹ch tuyÕn tÝnh kh«ng gi¶i ®îc, ch¼ng h¹n nh trong mét c«ng ty ngoµi viÖc n©ng

cao chÊt lîng s¶n phÈm th× c«ng ty còng chó träng tíi ®a d¹ng ho¸ s¶n phÈm, giµ

thµnh rÎ, doanh thu lín,…Kh¸ch hµng khi chän mua hµng th× muèn hµng rÎ, võa cã

3

chÊt lîng cao, võa cã h×nh thøc ®Ñp. Tãm l¹i, môc ®Ých cña bµi to¸n qui ho¹ch

tuyÕn tÝnh ®a môc tiªu lµ tèi u ®ång thêi nhiÒu hµm môc tiªu ®éc lËp víi nhau trªn

mét miÒn chÊp nhËn ®îc. Do kh«ng gian gi¸ trÞ cña líp bµi to¸n nµy kh«ng ®îc s¾p

thø tù toµn phÇn, nªn kh¸i niÖm nghiÖm th«ng thêng kh«ng cßn thÝch hîp. Trong

qui ho¹ch ®a môc tiªu, cïng víi kh¸i niÖm thø tù tõng phÇn, ta sÏ sö dông kh¸i

niÖm nghiÖm h÷u hiÖu.

Mét ph¬ng ¸n chÊp nhËn ®îc ®îc gäi lµ nghiÖm h÷u hiÖu nÕu kh«ng tån t¹i

mét ph¬ng ¸n chÊp nhËn ®îc kh¸c tèt h¬n nã, Ýt nhÊt lµ theo mét môc tiªu, cßn c¸c

môc tiªu kh¸c kh«ng tåi h¬n.

§Çu thÕ kû XX, Pareto ®· sö dông kh¸i niÖm nµy khi «ng nghiªn cøu phóc

lîi vµ thu nhËp cña d©n chóng. ¤ng ®· lËp luËn nh sau: "NÕu thu nhËp cña mét

nhãm d©n c t¨ng lªn, nhng thu nhËp cña mét nhãm kh¸c gi¶m xuèng th× khi ®ã

kh«ng thÓ so s¸nh "phóc lîi" cña toµn x· héi. §ã lµ trêng hîp kh«ng so s¸nh ®îc.

Nhng cã thÓ thÊy r»ng, phóc lîi x· héi sÏ t¨ng lªn nÕu thu nhËp cña Ýt nhÊt mét

nhãm ngêi nµo ®ã lín lªn, cßn thu nhËp cña nh÷ng nhãm kh¸c kh«ng thÊp xuèng".

Ta nhËn thÊy r»ng, theo quan ®iÓm cña to¸n häc, kh¸i niÖm nghiÖm h÷u hiÖu mµ

chóng ta dïng trong qui ho¹ch ®a môc tiªu phï hîp víi luËn ®Ò Pareto.

Khi p ( p ≥ 2) hµm môc tiªu ®Òu lµ hµm tuyÕn tÝnh vµ miÒn rµng buéc lµ tËp

låi ®a diÖn kh¸c rçng trong n

R , ta nhËn ®îc bµi to¸n qui ho¹ch tuyÕn tÝnh ®a môc

tiªu. Cho tíi nay, cã rÊt nhiÒu thuËt to¸n ®a ra ®Ó x¸c ®Þnh mét phÇn hoÆc toµn bé

tËp nghiÖm h÷u hiÖu cña bµi to¸n, ch¼ng h¹n: ph¬ng ph¸p v« híng ho¸, ph¬ng

ph¸p tham sè, ph¬ng ph¸p ®¬n h×nh ®a môc tiªu vµ c¸c d¹ng c¶i biªn, ph¬ng ph¸p

nãn ph¸p tuyÕn...(xem [6, 7, 8-9, 12, 17, 19, 21-22, vµ 24-25]).

4

Tuy nhiªn, khèi lîng tÝnh to¸n cña c¸c thuËt to¸n nµy t¨ng nhanh khi kÝch

thíc cña bµi to¸n qui ho¹ch tuyÕn tÝnh ®a môc tiªu (tøc sè rµng buéc cña miÒn

chÊp nhËn, sè chiÒu cña kh«ng gian quyÕt ®Þnh vµ sè hµm môc tiªu) t¨ng.

Trong nh÷ng n¨m gÇn ®©y nhiÒu nhµ to¸n häc ®· chuyÓn sang nghiªn cøu

gi¶i quyÕt bµi to¸n qui ho¹ch tuyÕn tÝnh ®a môc tiªu trong kh«ng gian gi¸ trÞ.

Trong b¸o c¸o nµy, em sÏ tr×nh bµy thuËt to¸n xÊp xØ ngoµi gi¶i bµi to¸n qui ho¹ch

tuyÕn tÝnh ®a môc tiªu trong kh«ng gian gi¸ trÞ cña H.P. Benson, ®ã lµ néi dung bµi

b¸o: "Hybrid Approach for Solving Multipe-Objective Linear Programs in

Outcome Space". Jota: Vol. 98, NO. 1, July, 1998.

Trong b¸o c¸o nµy ngoµi phÇn môc lôc, më ®Çu, phô lôc vµ tµi liÖu trÝch dÉn

cßn cã 3 ch¬ng:

Ch¬ng I: Mét sè kh¸i niÖm c¬ b¶n vÒ gi¶i tÝch låi vµ bµi to¸n qui ho¹ch

tuyÕn tÝnh.

Ch¬ng II: Bµi to¸n qui ho¹ch tuyÕn tÝnh ®a môc tiªu.

Ch¬ng III: Bµi to¸n qui ho¹ch tuyÕn tÝnh ®a môc tiªu trong kh«ng gian gi¸

trÞ.

Néi dung c¸c ch¬ng nh sau:

Ch¬ng I: Giíi thiÖu mét sè kiÕn thøc c¬ b¶n vÒ gi¶i tÝch låi ®Ó ¸p dông cho

c¸c phÇn sau, vµ ph¬ng ph¸p ®¬n h×nh dïng ®Ó gi¶i bµi to¸n qui ho¹ch tuyÕn tÝnh.

Ch¬ng II: Giíi thiÖu tæng qu¸t vÒ bµi to¸n qui ho¹ch ®a môc tiªu: m« h×nh

to¸n häc, kh¸i niÖm nghiÖm h÷u hiÖu vµ h÷u hiÖu yÕu, lý do gi¶i bµi to¸n qui

ho¹ch tuyÕn tÝnh ®a môc tiªu trong kh«ng gian gi¸ trÞ.

Ch¬ng III: Giíi thiÖu thuËt to¸n xÊp xØ ngoµi gi¶i bµi to¸n qui ho¹ch tuyÕn

tÝnh ®a môc tiªu trong kh«ng gian gi¸ trÞ.

5

6

Ch¬ng I

Mét sè kh¸i niÖm c¬ b¶n vÒ gi¶i tÝch låi vµ

bµi to¸n qui ho¹ch tuyÕn tÝnh.

Bµi to¸n qui ho¹ch tuyÕn tÝnh cã vai trß trî gióp quan träng trong c¸c bíc

gi¶i bµi to¸n qui ho¹ch tuyÕn tÝnh ®a môc tiªu. Trong ch¬ng nµy, tríc hÕt em xin

nh¾c l¹i mét sè kh¸i niÖm c¬ b¶n sÏ cÇn dïng ®Õn trong c¸c phÇn sau. PhÇn tiÕp

cña ch¬ng dµnh ®Ó tr×nh bµy ph¬ng ph¸p ®¬n h×nh gi¶i bµi to¸n qui ho¹ch tuyÕn

tÝnh.

1.1. Mét sè kh¸i niÖm c¬ b¶n

1.1.1-TËp affine

* §êng th¼ng ®i qua 2 ®iÓm n

a,b∈R lµ tËp hîp tÊt c¶ c¸c ®iÓm x trong R

n

cã d¹ng

x = λa + (1 − λ)b, víi mäi λ ∈ R .

* Mét tËp M chøa ®êng th¼ng ®i qua 2 ®iÓm bÊt k× cña nã th× ®îc gäi lµ tËp

affine.

* §o¹n th¼ng ®i qua 2 ®iÓm n

a,b∈R kÝ hiÖu lµ [a,b], lµ tËp

{ x R : x a (1 )b, 0 1}

n ∈ = λ + − λ ≤ λ ≤ .

* ChiÒu cña tËp M trïng víi chiÒu cña kh«ng gian con song song L víi nã.

n

L = M + a víi a∈ R

* Cho mét tËp C bÊt k×, tËp affine nhá nhÊt chøa C ®îc gäi lµ bao affine cña

C, kÝ hiÖu aff C.

7

* Siªu ph¼ng lµ tËp cã d¹ng H { x R : a,x ,a R \ { 0} , R}

n n

= ∈ = α ∈ α ∈ .

Ngîc l¹i, tËp bÊt k× cã d¹ng trªn lµ mét siªu ph¼ng.

VÝ dô 1.1.1

Trong kh«ng gian 2- chiÒu: siªu ph¼ng lµ mét ®êng th¼ng, trong kh«ng gian

3- chiÒu: siªu ph¼ng lµ mét mÆt ph¼ng.

* TËp hîp tÊt c¶ c¸c ®iÓm x (x , x ,..., x ) = 1 2 n

n ∈ R tho¶ m·n bÊt ph¬ng tr×nh

tuyÕn tÝnh: a,x , a R \ { 0} , R

n ≤ α ∈ α ∈ ®îc gäi lµ nöa kh«ng gian ®ãng.

* Nöa kh«ng gian ®îc cho bëi: a,x , a R \ { 0} , R

n < α ∈ α ∈ ®îc gäi lµ nöa kh«ng gian

më.

1.1.2- TËp låi

* Mét tËp A trong kh«ng gian R

n

®îc gäi lµ tËp låi nÕu ∀a,b∈A, ∀λ∈[0,1]

th×

x = λa + (1 − λ)b ∈ A.

Nãi c¸ch kh¸c, nÕu A lµ tËp låi th× nã chøa ®o¹n th¼ng nèi hai ®iÓm bÊt k× cña nã.

* NÕu n

x ∈R , x=∑=

n

i 1

i

i λ x , 0 λi ≥ , ∑=

=

n

i 1

λ i 1 th× x ®îc gäi lµ tæ hîp låi cña

1 2 n n

x , x ,..., x ∈R .

8

MÖnh ®Ò 1.1.1. TËp n A ⊂ R lµ låi khi vµ chØ khi nã chøa tÊt c¶ c¸c tæ hîp låi

cña c¸c phÇn tö thuéc A.

* TËp M⊂R

n

®îc gäi lµ mét nãn víi ®Ønh a nÕu: ∀x ∈M,∀λ ≥ 0 th×

x =a + λ(x − a) ∈ M .

§Þnh lý 1.1.1 TËp låi lµ ®ãng víi phÐp giao, phÐp céng, phÐp nh©n víi mét sè

vµ phÐp lÊy tæ hîp tuyÕn tÝnh. NÕu A vµ B lµ 2 tËp låi trong Rn

th× c¸c tËp sau

còng lµ låi:

(i) A ∩ B := { x : x ∈ A, x ∈ B}

(ii) λA + βB := { x = λa + βb : a ∈ A,b ∈ B,λ,β ∈ R} .

DÔ thÊy, giao cña mét hä bÊt kú c¸c tËp låi còng lµ tËp låi.

Giao cña tÊt c¶ c¸c tËp låi chøa tËp n

S ⊂ R ®îc gäi lµ bao låi cña tËp S vµ kÝ

hiÖu lµ convS. Râ rµng, convS lµ tËp låi nhá nhÊt chøa S.

VÝ dô 1.1.2 Cho c¸c tËp A, B, C nh H×nh 1.

H×nh 1.

Theo ®Þnh nghÜa X = conv{ A ∪ B} , Y = convC.

§Þnh lý 1.1.2

9

Bao låi cña tËp n

S ⊂ R chøa tÊt c¶ c¸c tæ hîp låi cña c¸c phÇn tö cña nã.

1.1.3- TËp låi ®a diÖn

* TËp låi ®a diÖn lµ giao cña mét sè h÷u h¹n c¸c nöa kh«ng gian ®ãng. Nãi

c¸ch kh¸c, tËp låi ®a diÖn lµ tËp nghiÖm cña mét hÖ bÊt ®¼ng thøc tuyÕn tÝnh cã

d¹ng

a , x bi

,i 1,2,...,m

i

≥ = ,

trong ®ã

a R ,

i n ∈ bi ∈R .

* Mét tËp låi ®a diÖn lµ bao låi cña mét sè h÷u h¹n ®iÓm vµ mét sè h÷u h¹n

®o¹n th¼ng.

* Mét tËp låi ®a diÖn bÞ chÆn thêng ®îc gäi lµ ®a diÖn låi.

* Mét ®a diÖn låi lµ giao cña mét sè h÷u h¹n ®iÓm.

Cho tËp låi ®a diÖn M, tËp con F ⊂ M ®îc gäi lµ diÖn nÕu:

x ∈ F, a,b∈ M,0 < λ < 1, x = λa + (1 − λ)b∈ F ⇒ a,b∈ F.

Nãi c¸ch kh¸c, F lµ mét diÖn cña M nÕu F chøa mét ®iÓm trong (hoÆc ®iÓm trong

t¬ng ®èi) cña mét ®o¹n th¼ng nµo ®ã cña M th× F chøa trän c¶ ®o¹n th¼ng ®ã. Mét

diÖn cã thø nguyªn lµ 0 ®îc gäi lµ mét ®Ønh hay ®iÓm cùc biªn, c¹nh lµ diÖn cã thø

nguyªn b»ng 1.

* Cho C lµ mét tËp låi ®a diÖn, mét ®iÓm x0 ∈C®îc gäi lµ ®iÓm cùc biªn

(hay ®Ønh) nÕu nã kh«ng chøa bÊt kú mét ®o¹n th¼ng nµo cña C nhËn x 0 lµm ®iÓm

trong cña ®o¹n th¼ng ®ã, tøc lµ kh«ng tån t¹i 2 ®iÓm ph©n biÖt a,b∈C sao cho

10

x a (1 )b 0 1 0 = λ + − λ víi < λ < .

Víi tËp låi ®a diÖn, mét ®Ønh cña diÖn còng chÝnh lµ ®Ønh cña tËp ®ã.

* Mét tËp h÷u h¹n n +1 ®iÓm 0 1 n n

u ,u ,...,u ∈R ®îc gäi lµ ®éc lËp affine khi

vµ chØ khi

1 0 2 0 n 0

u − u ,u − u ,...,u − u

lµ ®éc lËp tuyÕn tÝnh.

* NÕu n+1 ®iÓm 0 1 n n

u ,u ,...,u ∈R lµ ®éc lËp affine th× bao låi cña nã ®îc gäi

lµ mét n-®¬n h×nh víi c¸c ®Ønh 0 1 n

u ,u ,...,u .

VÝ dô 1.1.3

Trong mÆt ph¼ng 2

R ®¬n h×nh lµ mét tam gi¸c, H×nh 2a.

Trong kh«ng gian 3

R ®¬n h×nh lµ mét tø diÖn, H×nh 2b.

a) b)

H×nh 2.

* ¶nh cña tËp låi: Cho n

S ⊂ R vµ ¸nh x¹ p

f : S → R . Khi ®ã nÕu S lµ tËp låi vµ

f lµ ¸nh x¹ tuyÕn tÝnh th× ¶nh f(S) cña S qua ¸nh x¹ f còng lµ tËp låi. Nh¾c l¹i r»ng,

ma trËn C cÊp (m × p) chÝnh lµ ¸nh x¹ tuyÕn tÝnh tõ n p

R → R .

XÐt ¸nh x¹ tuyÕn tÝnh n p C: R → R , ta cã ®Þnh lý sau

11