Tài liệu Bài toán quy hoạch đa mục tiêu

0 Trêng ®¹i häc Vinh Khoa To¸n Bµi to¸n quy ho¹ch ®a môc tiªu Kho¸ luËn tèt nghiÖp ®¹i häc Ngµnh cö nh©n s ph¹m to¸n Gi¸o viªn híng dÉn: PGS.TS. TrÇn Xu©n Sinh Ngêi thùc hiÖn: Lª ThÞ Th¬ng Sinh viªn líp 43A2 - Khoa To¸n Vinh - 2006 Lêi nãi ®Çu Trong hÇu hÕt c¸c bµi to¸n tèi u, chóng ta thêng míi ®Ò cËp ®Õn mét môc tiªu duy nhÊt, môc tiªu nµy ®îc biÓu thÞ bëi mét hµm cÇn lµm cùc ®¹i hay cùc tiÓu. Chóng ta ®· biÕt c¸ch gi¶i bµi to¸n quy ho¹ch tuyÕn tÝnh mét môc tiªu. Cßn ®èi víi nh÷ng bµi to¸n quy ho¹ch nhiÒu môc tiªu th× sao, liÖu cã ®îc gi¶i quyÕt t¬ng tù hay kh«ng? Bµi to¸n quy ho¹ch ®a môc tiªu tuyÕn tÝnh ®· vµ ®ang ®îc nhiÒu ngêi quan t©m vµ gi¶i quyÕt bëi tÝnh phøc t¹p vµ nh÷ng øng dông quan träng cña nã trong thùc tiÔn kinh tÕ – kü thuËt. VÊn ®Ò ë ®©y kh«ng ph¶i lµ t×m mét ph¬ng ¸n ®Ó ®¹t ®îc mét môc tiªu nµo ®ã mµ c«ng viÖc cÇn lµm lµ t×m mét ph¬ng ¸n lµm tèi u ®ång thêi nhiÒu hµm môc tiªu. Tuy nhiªn, c¸c hµm môc tiªu ®ã thêng xung ®ét 1 nhau, do ®ã viÖc t×m mét ph¬ng ¸n nh vËy lµ rÊt khã. Ch¼ng h¹n nh trong thùc tÕ c¸c nhµ s¶n xuÊt kinh doanh ph¶i cã ph¬ng ¸n s¶n xuÊt nh thÕ nµo ®Ó ngoµi nh÷ng môc tiªu nh gi¶m chi phÝ, h¹ gi¸ thµnh s¶n phÈm ngêi ta cßn quan t©m ®Õn viÖc duy tr× lîi nhuËn, æn ®Þnh lao ®éng. §Ó ®¹t ®îc ®ång thêi c¸c môc tiªu nh vËy qu¶ thùc lµ kh«ng dÔ. ChÝnh v× c¸i khã cña vÊn ®Ò nµy ®· khiÕn chóng t«i cã sù tß mß muèn quan t©m vµ ®i s©u vµo t×m hiÓu. Do ®ã chóng t«i ®· chän ®Ò tµi “Bµi to¸n quy ho¹ch ®a môc tiªu”. Trong ph¹m vi cña kho¸ luËn tèt nghiÖp, chóng t«i chØ míi d¸m nªu môc ®Ých cña ®Ò tµi ®a ra bµi to¸n quy ho¹ch ®a môc tiªu vµ mét sè híng tiÕp cËn bµi to¸n. Tõ ®ã ®a ra mét sè thuËt to¸n ®Ó gi¶i bµi to¸n. Kho¸ luËn ®îc chia thµnh 2 ch¬ng Ch¬ng 1: Tr×nh bµy bµi to¸n quy ho¹ch ®a môc tiªu tuyÕn tÝnh, c¸c híng tiÕp cËn bµi to¸n vµ nªu mét sè tÝnh chÊt quan träng cña bµi to¸n. Môc ®Ých cña ch¬ng 1 lµ cho ngêi ®äc mét c¸i nh×n tæng qu¸t vÒ bµi to¸n ®a môc tiªu. Ch¬ng 2: §a ra c¸c bíc gi¶i quyÕt bµi to¸n. PhÇn ®Çu tr×nh bµy mét sè ph¬ng ph¸p gi¶i bµi to¸n kÕt hîp víi së thÝch cña ngêi nhËn lêi gi¶i. PhÇn sau tr×nh bµy thuËt to¸n tèi u Pareto ®Ó gi¶i quyÕt bµi to¸n. Kho¸ luËn ®îc thùc hiÖn vµ hoµn thµnh t¹i trêng §¹i häc Vinh víi sù gióp ®ì, híng dÉn tËn t×nh chu ®¸o cña thÇy gi¸o PGS.TS. TrÇn Xu©n Sinh vµ nh÷ng thÇy c« gi¸o thuéc tæ §iÒu khiÓn khoa To¸n. T¸c gi¶ xin bµy tá lßng biÕt ¬n ch©n thµnh ®Õn thÇy híng dÉn vµ c¸c thÇy c« gi¸o trong khoa To¸n ®· t¹o ®iÒu kiÖn gióp ®ì trong qu¸ tr×nh häc tËp vµ hoµn thµnh kho¸ luËn nµy. Do thêi gian vµ kh¶ n¨ng cã h¹n cña t¸c gi¶, kho¸ luËn kh«ng thÓ tr¸nh khái nh÷ng thiÕu sãt, rÊt mong ®îc sù gãp ý cña ngêi ®äc. Vinh, 4/2006 T¸c gi¶ 2 Ch¬ng 1 quy ho¹ch §a môc tiªu 1.1. Bµi to¸n Trong nhiÒu øng dông thuéc c¸c ngµnh kinh tÕ - kü thuËt, ®iÒu khiÓn c¸c ho¹t ®éng s¶n xuÊt, thùc tÕ thêng g¾n liÒn víi viÖc thiÕt kÕ vµ lËp kÕ ho¹ch theo nhiÒu môc tiªu tèi u. Chóng ta còng thêng gÆp nh÷ng bµi to¸n liªn quan ®Õn viÖc ph©n tÝch, lùa chän quyÕt ®Þnh híng vµo nhiÒu môc tiªu kh¸c nhau. Ch¼ng h¹n trong mét ®¬n vÞ s¶n xuÊt kinh doanh, chóng ta nªn lùa chän quyÕt ®Þnh nµo sao cho ®¹t ®îc c¸c môc tiªu nh: nhanh, nhiÒu, tèt, rÎ, v.v.. Tuy nhiªn, c¸c môc tiªu nµy thêng xung ®ét víi nhau, v× thÕ, khã cã gi¶i ph¸p ®¹t tèi u ®ång thêi tÊt c¶ c¸c môc tiªu nµy. Trong nh÷ng t×nh huèng nh vËy, ta cÇn cã c¸ch ®Æt bµi to¸n vµ c¸ch xö lý thÝch hîp. Quy hoach ®a môc tiªu sÏ cung cÊp thªm c«ng cô ®Ó gi¶i quyÕt vÊn ®Ò nµy. Bµi to¸n quy ho¹ch ®a môc tiªu (Multiple objective programming problem MOP): max (min)f(X) : X  D  Rn, (1.1) trong ®ã f(X) = (f1(X),..., fk(X)) gäi lµ vect¬ môc tiªu (k  2), f1, f2,..., fk lµ c¸c hµm môc tiªu. D  , ®îc gäi lµ tËp ph¬ng ¸n. X  D gäi lµ ph¬ng ¸n. (Chó ý: §Ó tiÖn lîi, tõ ®©y ta ký hiÖu tËp ph¬ng ¸n lµ D). Mét ph¬ng ¸n X lµm cùc ®¹i (hay cùc tiÓu) ®ång thêi c¸c hµm môc tiªu ®îc gäi lµ ph¬ng ¸n tèi u (hoÆc lµ nghiÖm) cña bµi to¸n. Trong gi¸o tr×nh nµy, chóng ta xÐt bµi to¸n quy ho¹ch ®a môc tiªu tuyÕn tÝnh (Multiple objective linear programming problem - MOLP), tøc lµ f(X) hµm tuyÕn tÝnh vµ tËp D   ®a diÖn tåi. Ta h·y nªu mét vÝ dô cô thÓ. 1.2. VÝ dô 3 Mét nhµ m¸y dù kiÕn s¶n xuÊt 3 lo¹i s¶n phÈm míi A, B, C (cïng mét lo¹i vËt liÖu). Chi phÝ vÒ vËt liÖu, c«ng vµ lîi nhuËn thu ®îc cho ë b¶ng 1.1. BiÕt nhµ m¸y chØ dïng ®îc vµo phÇn s¶n xuÊt nµy lµ 165 kg vËt liÖu vµ 130 ngµy c«ng. LËp m« h×nh bµi to¸n thÓ hiÖn kÕ ho¹ch s¶n xuÊt sao cho tæng sè tiÒn l·i vµ tæng sè s¶n phÈm lín nhÊt. B¶ng 1.1 S¶n phÈm A B C VËt liÖu (kg) 20 30 15 C«ng (ngµy) 7 6 3 Lîi nhuËn (triÖu ®ång) 50 35 20 LËp bµi to¸n: Gäi x1, x2, x3 lÇn lît lµ sè s¶n phÈm A, B, C. Khi ®ã, c¸c ®iÒu kiÖn h¹n chÕ vÒ vËt liÖu vµ lao ®éng lµ:      20x1 + 30x2 + 15x3  165 7x1 + 6x2 + 3x3  130 x1, x2, x3  0. TiÒn l·i thu ®îc vµ tæng sè c¸c s¶n phÈm A, B, C lÇn lît ®îc biÓu diÔn lµ: f1(X) = 50x1 + 35x2 + 20x3 f2(X) = x1 + x2 + x3. CÇn t×m X = (x1, x2, x3) tháa m·n c¸c ®iÒu kiÖn trªn sao cho sè tiÒn l·i vµ tæng sè s¶n phÈm lµ lín nhÊt. Ta cã m« h×nh to¸n häc max f(X) = (f1(X), f2(X)) : X  D, trong ®ã D ®îc x¸c ®Þnh bëi      20x1 + 30x2 + 15x3  165 7x1 + 6x2 + 3x3  130 xi  0, i = 1, 2, 3. Ta ®· biÕt c¸ch gi¶i bµi to¸n quy ho¹ch 1 môc tiªu, ®Ó gi¶i quyÕt bµi to¸n quy hoach ®a môc tiªu, ta cã nhiÒu híng tiÕp cËn kh¸c nhau. Sau ®©y lµ mét sè híng tiÕp cËn gi¶i bµi to¸n quy ho¹ch ®a môc tiªu. 1.3. C¸c híng tiÕp cËn gi¶i bµi to¸n quy ho¹ch ®a môc tiªu 1.3.1. C¸ch tiÕp cËn theo môc tiªu Néi dung cña c¸ch tiÕp cËn nµy lµ: - Quy ®Þnh cho mçi môc tiªu mét møc b»ng sè x¸c ®Þnh. - X¸c ®Þnh c¸c hÖ sè ph¹t do vi ph¹m møc quy ®Þnh trªn. - T×m ph¬ng ¸n ®¹t cùc tiÓu tæng ®é lÖch cña c¸c gi¸ trÞ môc tiªu so víi møc ®· quy ®Þnh cho tõng môc tiªu, tæng ®îc tÝnh víi träng sè lµ c¸c hÖ sè ph¹t ®· x¸c ®Þnh. Cã 3 d¹ng møc môc tiªu: 4 - CËn díi (møc mét phÝa): quy ®Þnh giíi h¹n díi cho c¸c gi¸ trÞ môc tiªu cÇn ®¹t ®îc. - Møc 2 phÝa: quy ®Þnh gi¸ trÞ mµ môc tiªu cÇn ®¹t ®îc (kh«ng h¬n, kh«ng kÐm). - CËn trªn (møc mét phÝa): quy ®Þnh giíi h¹n trªn mµ gi¸ trÞ môc tiªu kh«ng ®îc vît qu¸. Theo c¸ch tiÕp cËn nµy, c¸c bµi to¸n nhiÒu môc tiªu nµy ®îc chia ra 2 lo¹i bµi to¸n: quy häach nhiÒu môc tiªu kh«ng u tiªn vµ quy ho¹ch nhiÒu môc tiªu cã u tiªn. Sau ®©y, ta sÏ xÐt riªng tõng lo¹i bµi to¸n. a) Quy ho¹ch nhiÒu môc tiªu kh«ng u tiªn Trong bµi to¸n nµy, c¸c môc tiªu ®a ra ®Òu cã tÇm quan träng nh nhau, kh«ng ph©n biÖt c¸i nµo h¬n c¸i nµo, ®Ó gi¶i bµi to¸n nµy ta sö dông c¸c biÕn phô ®Ó ®a bµi to¸n nhiÒu môc tiªu vÒ bµi to¸n quy ho¹ch tuyÕn tÝnh ®· biÕt c¸ch gi¶i. §Ó cho dÔ hiÓu ta xÐt vÝ dô cô thÓ sau: VÝ dô: Mét xÝ nghiÖp dù kiÕn ®a vµo s¶n xuÊt 3 lo¹i s¶n phÈm míi (kÝ hiÖu lµ A, B, C) ®Ó thay thÕ cho c¸c mÉu s¶n phÈm cò s¾p ngõng s¶n xuÊt. Chñ xÝ nghiÖp muèn c©n nh¾c tíi 3 môc tiªu chÝnh: lîi nhuËn, lao ®éng vµ vèn ®Çu t. Cô thÓ lµ: 1) CÇn ®¹t lîi nhuËn tèi thiÓu lµ 125 triÖu ®ång tõ c¸c s¶n phÈm míi. 2) Cè g¾ng duy tr× ®éi ngò lao ®éng hiÖn cã ë møc 4000 ngêi. 3) Gi÷ møc ®Çu t kh«ng vît qu¸ 55 triÖu ®ång. Chñ xÝ nghiÖp thÊy r»ng kh«ng cã kh¶ n¨ng ®¹t ®ång thêi c¶ 3 môc tiªu nµy. V× thÕ sau khi bµn b¹c, «ng quyÕt ®Þnh ®a ra c¸c hÖ sè ph¹t nh sau: 5 trªn 1 triÖu ®ång lîi nhuËn ®¹t thÊp h¬n møc quy ®Þnh; 2 trªn 100 lao ®éng sö dông thªm; 4 trªn 100 lao ®éng d«i d vµ 3 trªn 1 triÖu ®ång vèn ®Çu t t¨ng thªm. Gi¶ sö r»ng 3 møc lîi nhuËn, sè lao ®éng vµ vèn ®Çu t tû lÖ thuËn víi møc s¶n xuÊt s¶n phÈm. C¸c sè liÖu ®Þnh møc ®îc cho ë b¶ng 1.2, cïng víi c¸c møc môc tiªu vµ c¸c hÖ sè ph¹t. B¶ng 1.2 S¶n phÈm HÖ sè Môc tiªu Møc môc tiªu A B C ph¹t Lîi nhuËn 12 9 15 5  125 (triÖu ®ång) Lao ®éng 5 3 4 = 40 ( 100 lao ®éng 2(+), 4(-) Vèn ®Çu t 5 7 8 3  55 (triÖu ®ång) Trong bµi to¸n nµy cã ®ñ 3 d¹ng møc môc tiªu: cËn díi (lîi nhuËn), møc 2 phÝa (lao ®éng) vµ cËn trªn (vèn ®Çu t). Gäi x1, x2, x3 lÇn lît lµ sè s¶n phÈm A, B, C. C¸c môc tiªu lîi nhuËn, lao ®éng vµ vèn ®Çu t lÇn lît ®îc diÔn ®¹t: 12x1 + 9x2 + 15x3  125 5x1 + 3x2 + 4x3 = 40 5x1 + 3x2 + 4x3  55. KÝ hiÖu Z lµ lîng ph¹t do vi ph¹m c¸c môc tiªu trªn víi hÖ sè ph¹t ®· cho th× c¸c môc tiªu tæng thÓ lµ t×m x1, x2, x3 sao cho lµm c¸c cùc tiÓu lîng ph¹t nµy. 5 §Ó diÔn ®¹t chÝnh x¸c h¬n, ta thªm vµo c¸c biÕn sè phô y1, y2, y3. y1 = 12x1 + 9x2 + 15x3 – 125 y2 = 5x1 + 3x2 + 4x3 - 40 y3 = 5x1 + 3x2 + 4x3 – 55. Do mçi yj cã thÓ nhËn gi¸ trÞ d¬ng hay ©m nªn ta thay thÕ c¸c biÕn nµy bëi yj = yj+ - yj-, víi yj+, yj-  0; j = 1, 2, 3. Môc tiªu ®· nªu vÒ mÆt to¸n häc cã thÓ diÕn ®¹t Z = 5y1- + 2y2+ + 4y2- + 3y3+  min víi c¸c ®iÒu kiÖn:        12x1 + 9x2 + 15x3 - (y1+ - y1- ) = 125 5x1 + 3x2 + 4x3 - (y2+ - y2- ) = 40 5x1 + 7x2 + 8x3 - (y3+ - y3- ) = 55 xj  0, yk+  0, yk-  0, víi j = 1, 2, 3; k = 1, 2, 3. §©y chÝnh lµ m« h×nh bµi to¸n quy ho¹ch tuyÕn tÝnh mét môc tiªu. Dïng ph¬ng ph¸p ®¬n h×nh gi¶i bµi to¸n trªn, ta nhËn ®îc ph¬ng ¸n tèi u nh sau: 25 5 , x2 = 0, x3 = 3 3 25 y1+ = 0, y1- = 0, y2+ = , y2- = 0, y3+ = 0, y3- = 0. 3 25 Nh vËy, y1 = 0, y2 = , y3 = 0, nghÜa lµ môc tiªu thø nhÊt vµ thø 3 ®îc tháa 3 x1 = m·n, cßn môc tiªu vÒ lao ®éng kh«ng tháa m·n, vît møc quy ®Þnh lµ 25 (tøc 3 833 ngêi). Lîng ph¹t do vi ph¹m môc tiªu vÒ lao ®éng lµ Z = 16. b) Quy ho¹ch nhiÒu môc tiªu cã u tiªn Trong bµi to¸n nµy c¸c môc tiªu ®îc ph©n cÊp theo c¸c møc u tiªn kh¸c nhau, môc tiªu cã møc u tiªn cao h¬n sÏ ®îc chó ý h¬n. V× thÕ, sù tËp trung tríc hÕt vµo viÖc ®¹t ®îc c¸c môc tiªu nµy ®Õn møc tèi ®a cã thÓ, sau ®ã råi xÐt ®Õn c¸c môc tiªu tiÕp theo. Khi xÐt c¸c môc tiªu cïng cÊp u tiªn, c¸ch lµm gièng nh phÇn trªn. Cã 2 ph¬ng ph¸p chÝnh ®Ó xö lý c¸c bµi to¸n quy ho¹ch nhiÒu môc tiªu cã u tiªn: - Ph¬ng ph¸p tuÇn tù - Ph¬ng ph¸p trùc tiÕp. Ta sÏ xÐt 2 ph¬ng ph¸p nµy th«ng qua vÝ dô cô thÓ sau: VÝ dô: Kh«ng hµi lßng víi dù ¸n t¨ng lùc lîng lao ®éng cña xÝ nghiÖp trªn 20% (833/4000) nh ®· thÊy ë vÝ dô tríc, chñ xÝ nghiÖp quyÕt ®Þnh xem xÐt l¹i c¸ch ®Æt bµi to¸n nh ®· nªu tãm t¾t ë b¶ng tríc. ViÖc t¨ng sè lao ®éng sÏ g©y cho xÝ nghiÖp nhiÒu khã kh¨n, V× thÕ, môc tiªu hµng ®Çu lµ tr¸nh t¨ng lao ®éng, h¬n 6 n÷a, chñ xÝ nghiÖp còng biÕt r»ng t¨ng møc ®Çu t cho s¶n xuÊt s¶n phÈm míi vît qu¸ 55 triÖu ®ång còng lµ vÊn ®Ò nan gi¶i nªn tr¸nh ®Çu t qu¸ møc nµy còng lµ môc tiªu hµng ®Çu cÇn ®îc tÝnh ®Õn. Tõ ®ã, chñ xÝ nghiÖp quyÕt ®Þnh 2 môc tiªu trªn cã møc u tiªn sè 1, cßn 2 môc tiªu cßn l¹i cã møc u tiªn 2. C¸c hÖ sè ph¹t ®îc cho ë b¶ng 1.3, trong ®ã M biÓu thÞ sè d¬ng kh¸ lín (lín h¬n bÊt cø sè nµo cÇn so s¸nh víi nã). B¶ng 1.3 S¶n phÈm HÖ sè Môc tiªu Møc môc tiªu A B C ph¹t  40 (100 lao ®éng) 5 3 4 2M Møc 1 5 7 8 3M  55 (triÖu ®ång) 12 9 15  125 (triÖu ®ång) 5 Møc 2 5 3 4 4  40 (100 lao ®éng) * Ph¬ng ph¸p tuÇn tù Theo ph¬ng ph¸p nµy, gi¶i bµi to¸n quy ho¹ch ®a môc tiªu th«ng qua viÖc gi¶i mét d·y c¸c bµi to¸n quy ho¹ch tuyÕn tÝnh. Tæng qu¸t nh sau: - Giai ®o¹n ®Çu ta chØ dùa vµo m« h×nh quy hoach tuyÕn tÝnh c¸c môc tiªu cã møc u tiªn 1 vµ ¸p dông ph¬ng ph¸p ®¬n h×nh ®Ó gi¶i nh m« h×nh ®· lµm tríc ®©y. NÕu ph¬ng ¸n tèi u lµ duy nhÊt th× dõng l¹i mµ kh«ng cÇn xÐt c¸c môc tiªu cßn l¹i. NÕu cã nhiÒu ph¬ng ¸n tèi u víi cïng gi¸ trÞ tèi u f*, chuyÓn sang giai ®o¹n 2 vµ ®a vµo m« h×nh môc tiªu cã møc u tiªn 2. - Giai ®o¹n 2: + NÕu f* = 0 th× mäi biÕn phô biÓu thÞ ®é lÖch gi÷a gi¸ trÞ cña c¸c môc tiªu cã møc u tiªn 1 vµ møc môc tiªu cña chóng ph¶i b»ng 0, lóc ®ã mäi biÕn phô cã thÓ lo¹i bá khái m« h×nh ë giai ®o¹n 2. + NÕu f* > 0 th× chØ thªm vµo m« h×nh ®· thiÕt lËp ë giai ®o¹n 1 nh÷ng môc tiªu cã møc u tiªn 2, sau ®ã cÇn thªm vµo rµng buéc ph¶n ¸nh gi¸ trÞ môc tiªu cña giai ®o¹n 1 b»ng f*. Sau khi gi¶i theo thuËt to¸n ®¬n h×nh, nÕu thÊy cã nhiÒu lêi gi¶i th× tiÕp tôc lÆp l¹i qu¸ tr×nh trªn choc¸c môc tiªu cã møc u tiªn thÊp h¬n. VÝ dô: XÐt vÝ dô víi sè liÖu cho ë b¶ng 1.3. ë giai ®o¹n 1 chØ cã 2 môc tiªu cã møc u tiªn 1 ®îc ®a vµo m« h×nh quy ho¹ch tuyÕn tÝnh, V× thÕ, ta cã thÓ bá nh©n tö M ë c¸c hÖ sè ph¹t. Gäi x1, x2, x3 lÇn lît lµ sè s¶n phÈm A, B, C. T¬ng tù nh bµi to¸n nhiÒu môc tiªu kh«ng u tiªn, bµi to¸n quy ho¹ch tuyÕn tÝnh t¬ng øng cã d¹ng f = 2y2+ + 3y3+  min víi ®iÒu kiÖn 5x1 + 3x2 + 4x3 - (y2+ - y2- ) = 40 5x1 + 7x2 + 8x3 - (y3+ - y3- ) = 55 7      xj  0, yk+  0, yk-  0, j = 1, 2, 3; k = 2, 3. (§Ó dÔ so s¸nh víi m« h×nh mµ c¶ 4 môc tiªu cã cïng møc u tiªn nh nhau chØ sè díi cña c¸c biÕn phô ®îc gi÷ nguyªn nh cò). Dïng ph¬ng ph¸p ®¬n h×nh gi¶i ra ta ®îc lêi gi¶i cña bµi to¸n nµy cã y2+ = y3+ = 0, víi f* = 0, lóc nµy c¸c biÕn phô y2+, y3+ lo¹i bá khái m« h×nh. M« h×nh bµi to¸n quy ho¹ch tuyÕn tÝnh ë giai ®o¹n 2 lµ f = 5y2- + 4y3-  min víi c¸c ®iÒu kiÖn:        12x1 + 9x2 + 15x3 - y1+ + y1= 125 5x1 + 3x2 + 4x3 - y2 = 40 5x1 + 3x2 + 4x3 - y3 = 55 xj  0, yk+  0, yk-  0, j = 1, 2, 3; k = 1, 2, 3. Dïng ph¬ng ph¸p ®¬n h×nh gi¶i bµi to¸n nµy ta nhËn ®îc nghiÖm duy nhÊt lµ x1 = 5; x2 = 0; x3 = 3,75 y1+ = 0; y1- = 8,75; y2- = 0; y3- = 0 víi f* = 43,75 Do lêi gi¶i lµ duy nhÊt nªn qu¸ tr×nh gi¶i kÕt thóc, ph¬ng ¸n tèi u cña bµi to¸n lµ Xt. = (x1, x2, x3 ) = (5; 0; 3,75). Nh vËy, ë møc u tiªn 1: c¶ 2 môc tiªu ®Òu tháa m·n, cßn ë møc u tiªn 2 th× chØ cã môc tiªu vÒ lao ®éng ®îc tháa m·n, cßn môc tiªu vÒ lîi nhuËn gÇn ®¹t ®îc (thiÕu 8,75 triÖu ®ång). * Ph¬ng ph¸p trùc tiÕp Theo ph¬ng ph¸p nµy c¸c môc tiªu ®îc ®a cïng mét lóc vµo m« h×nh nhng víi c¸c hÖ sè ph¹t ®îc nh©n víi c¸c nh©n tö kh¸c nhau, møc u tiªn cµng cao th× nh©n tö M cµng lín. Nh vËy, ph¬ng ph¸p nµy kh¸c víi ph¬ng ph¸p tuÇn tù lµ nã ®i t×m lêi gi¶i cña bµi to¸n nhiÒu môc tiªu b»ng c¸ch chØ gi¶i mét m« h×nh quy ho¹ch tuyÕn tÝnh. VÝ dô: §Ó dÔ h×nh dung ta xÐt tiÕp vÝ dô víi sè liÖu cho ë b¶ng 1.3. Tõ b¶ng ®ã cho thÊy: - C¸c môc tiªu trong mçi møc u tiªn ®îc g¾n víi c¸c hÖ sè ph¹t kh¸c nhau. - C¸c hÖ sè ph¹t (2 vµ 3) cña c¸c môc tiªu cã møc u tiªn 1 ®îc nh©n víi hÖ sè M kh¸ lín. Víi c¸c hÖ sè ph¹t nµy vµ t¬ng tù c¸ch lËp bµi to¸n nh trªn, ta ®i ®Õn m« h×nh quy hoach tuyÕn tÝnh duy nhÊt Z = 5y2- + 2My2+ + 4y2- + 3My3+  min víi ®iÒu kiÖn 12x1 + 9x2 + 15x3 - (y1+ - y1-) = 125 8        5x1 + 3x2 + 4x3 5x1 + 7x2 + 8x3 - (y2+ - y2-) = 40 - (y - y ) = 55 + 3 3 xj  0, yk+  0, yk-  0, j = 1, 2, 3; k = 1, 2, 3. Vµ ta còng thu ®îc kÕt qu¶ nh trªn. Trªn ®©y lµ vÝ dô chØ cã 2 møc u tiªn. NÕu gÆp bµi to¸n cã nhiÒu h¬n 2 møc u tiªn th× c¸c møc u tiªn ®îc g¾n víi c¸c nh©n tö M1, M2, ..., Mp-1, Mp = 1, trong ®ã M1 lµ sè rÊt lín so víi M2, ..., Mp – 1 lµ sè rÊt lín so víi Mp. Tãm l¹i, quy ho¹ch ®a môc tiªu tuyÕn tÝnh vµ c¸c ph¬ng ph¸p gi¶i ®· tr×nh bµy ë trªn cho mét c¸ch xö lý cã hiÖu qu¶ c¸c bµi to¸n ®Ò cËp ®Õn nhiÒu môc tiªu cïng mét lóc. Kü thuËt c¬ b¶n ë ®©y lµ dïng c¸c biÕn sè phô cho phÐp ta chuyÓn bµi to¸n nhiÒu môc tiªu vÒ mét hay nhiÒu bµi to¸n quy ho¹ch tuyÕn tÝnh. 1.3.2. C¸ch tiÕp cËn tèi u Pareto Néi dung cña c¸ch tiÕp cËn nµy lµ t×m mét gi¶i ph¸p ®¹t ®îc sù tháa hiÖp tèt nhÊt gi÷a nhiÒu môc tiªu kh¸c nhau hoÆc ®a ra tËp c¸c gi¶i ph¸p nh thÕ ®Ó ngêi cã tr¸ch nhiÖm ra quyÕt ®Þnh tham kh¶o, lùa chän. ViÖc t×m ra c¸c gi¶i ph¸p nµy ®ßi hái ph¶i cã c¸ch ®Æt vÊn ®Ò vµ c¸ch tÝnh to¸n míi. Trong môc nµy, ta sÏ nªu c¸ch m« t¶ theo tham sè cho bµi to¸n ®a môc tiªu tuyÕn tÝnh. XÐt bµi to¸n quy ho¹ch ®a môc tiªu (MOLP) ®îc viÕt l¹i díi d¹ng ma trËn Vmax CX : AX = B, X  0, (1.2) víi C lµ ma trËn pn cã hµng thø k lµ vect¬ Ck  Rn, k = 1, p (p  2). MiÒn rµng buéc D = X  Rn ; AX = B, X  0. Hµm fk(X) = Ck, X , k = 1, p x¸c ®Þnh mét môc tiªu tuyÕn tÝnh cÇn ®¹t tèi u. B©y giê ta sÏ lµm râ kh¸i niÖm tèi u ®a môc tiªu trong bµi to¸n (MOLP). XÐt vÝ dô sau: VÝ dô: Gi¶ sö mét xëng méc dù kiÕn s¶n xuÊt 2 lo¹i s¶n phÈm: bµn, ghÕ tõ nguån v¸n gç gô xÎ vµ lao ®éng hiÖn cã. Chi phÝ vÒ gç, c«ng, tiÒn l·i ®îc cho ë B¶ng 1.4. B¶ng 1.4 S¶n phÈm Gç (dm3) C«ng (ngµy) TiÒn l·i (1000 ®) Bµn 40 5 60 GhÕ 10 3 25 Lîng gç dïng ®Ó s¶n xuÊt lµ 780dm 3 vµ 150 ngµy c«ng. VËy nªn s¶n xuÊt bao nhiªu s¶n phÈm mçi lo¹i ®Ó cã l·i lín nhÊt? LËp m« h×nh bµi to¸n. Gäi x1, x2 lÇn lît lµ sè bµn vµ sè ghÕ cÇn s¶n xuÊt. Ta cÇn t×m nh÷ng sè x1, x2 tháa m·n 9      40x1 + 10x2  780 5x1 + 3x2  150 x1, x2 nguyªn, kh«ng ©m, vµ lµm cho tiÒn l·i f1(X) = C1, X = 60x1 + 25x2 lµ lín nhÊt. §©y lµ bµi to¸n quy ho¹ch tuyÕn tÝnh mét môc tiªu, dïng ®å thÞ ta cã ®îc lêi gi¶i lµ x1 = 12, x2 = 30 vµ tiÒn l·i lín nhÊt lµ f1 = 1.470.000®. NÕu b©y giê chñ xëng l¹i muèn t×m ph¬ng ¸n s¶n xuÊt sao cho tæng sè s¶n phÈm lµ lín nhÊt tøc lµ f2(X) = C2, X = x1 + x2 ®¹t cùc ®¹i th× cÇn s¶n xuÊt bao nhiªu s¶n phÈm mçi lo¹i Gi¶i bµi to¸n quy ho¹ch tuyÕn tÝnh f2(X) = C2, X  max   víi ®iÒu kiÖn    40x1 + 10x2  780 5x1 + 3x2  150 x1, x2  0, x1, x2 nguyªn. B¼ng ph¬ng ph¸p ®å thÞ ta ®îc kÕt qu¶ lóc nµy lµ x1 = 0, x2 = 50. Nh vËy s¶n xuÊt 50 ghÕ vµ kh«ng s¶n xuÊt bµn lóc ®ã tæng s¶n phÈm lín nhÊt vµ s¶n xuÊt ®îc lµ f2 = 50. ë trªn ta ®i xÐt riªng rÏ tõng môc tiªu, b©y giê nÕu ta ®i t×m mét ph¬ng ¸n X = (x1, x2) sao cho tháa m·n ®ång thêi c¶ 2 hµm môc tiªu (cïng lµm cùc ®¹i 2 hµm môc tiªu) th× dÉn ®Õn bµi to¸n tèi u ®a môc tiªu sau CX =  60x1  25x2     x1  x2  Bµi to¸n tèi u ®a môc tiªu lµ max CX víi ®iÒu kiÖn      40x1 + 10x2  780 5x1 + 3x2  150 x1  0; x2  0. Lóc ®ã c¸c ph¬ng ¸n X1 = (12, 30) vµ X2 = (0, 50) sÏ t¬ng øng víi 10 CX1 = 1470    42  vµ CX2 = 1250    50  Nh vËy, ta nhËn thÊy r»ng 2 ph¬ng ¸n nµy xung ®ét víi nhau: X1 cã gi¸ trÞ môc tiªu thø nhÊt cao h¬n nhng gi¸ trÞ môc tiªu thø hai l¹i nhá h¬n, cßn X2 th× ngîc l¹i; gi¸ trÞ môc tiªu thø nhÊt thÊp h¬n cßn gi¸ trÞ môc tiªu thø hai l¹i cao h¬n. V× vËy, ta kh«ng thÓ chän ®îc ph¬ng ¸n mµ gi¸ trÞ cña c¶ hai môc tiªu ®Òu vît tréi so víi ph¬ng ¸n kia. Còng vËy nÕu chän bÊt kú mét ph¬ng ¸n nµo kh¸c dï lµ cùc biªn hay kh«ng còng sÏ dÉn ®Õn lµm gi¶m gi¸ trÞ cña f1 hoÆc f2 hoÆc c¶ 2. Nh vËy, bµi to¸n tèi u ®ång thêi 2 môc tiªu nµy lµ cha thùc hiÖn ®îc. Do ®ã, ®Ó gi¶i quyÕt vÊn ®Ò tèi u ®a môc tiªu ta cÇn x¸c ®Þnh l¹i kh¸i niÖm tèi u. Ta sÏ ®a ra ®Þnh nghÜa t¬ng tù nh kh¸i niÖm trong kinh tÕ vÒ ®iÓm h÷u hiÖu hay ®iÓm tèi u Pareto. §èi víi bµi to¸n tèi u (1.2) ta ®Þnh nghÜa lêi gi¶i (hay ®iÓm) h÷u hiÖu nh sau: §Þnh nghÜa. §iÓm X0  D ®îc gäi lµ ®iÓm tèi u Pareto hay ®iÓm h÷u hiÖu cña bµi to¸n tèi u ®a môc tiªu (1.2) nÕu kh«ng tån t¹i X  D sao cho CX  CX0 vµ CX  CX0, nghÜa lµ CkX  CkX0, víi mäi k = 1, 2, ..., p vµ CkX > CkX0 víi Ýt nhÊt mét k nµo ®ã thuéc 1, 2, ..., p. C¸ch ph¸t biÓu t¬ng ®¬ng cña ®Þnh nghÜa trªn lµ: §iÓm X0  D ®îc gäi lµ ®iÓm tèi u Pareto hay ®iÓm h÷u hiÖu cña bµi to¸n tèi u ®a môc tiªu (1.2) nÕu cã tån t¹i X  D sao cho CX  CX0 th× CX = CX0. Khi ®ang ë mét ®iÓm h÷u hiÖu nÕu chuyÓn sang mét ®iÓm h÷u hiÖu kh¸c th× sÏ lµm gi¶m gi¸ trÞ cña Ýt nhÊt mét môc tiªu nµo ®ã. Theo ®Þnh nghÜa nµy th× c¸c lêi gi¶i cña bµi to¸n s¶n xuÊt bµn ghÕ ë trªn (12, 30) vµ (0, 50) ®Òu lµ nh÷ng ®iÓm h÷u hiÖu. Th«ng thêng trong c¸c bµi to¸n tèi u ®a môc tiªu th× c¸c môc tiªu thêng xung ®ét nhau, do ®ã, ta cÇn lµm c©n ®èi c¸c môc tiªu. Mét trong nh÷ng biÖn ph¸p ®Ó ®¹t ®îc sù c©n ®èi gi÷a c¸c môc tiªu lµ g¸n cho mçi môc tiªu mét trong sè d¬ng, biÓu thÞ møc ®é quan träng cña môc tiªu ®ã vµ xÐt hµm môc tiªu chung b»ng tæng cã träng sè cña c¸c hµm môc tiªu ®· cho. Do c¸c träng sè thêng kh«ng chÝnh x¸c vµ cha ®îc x¸c ®Þnh nªn vÊn ®Ò ®¸ng quan t©m lµ t×m tÊt c¶ c¸c lêi gi¶i cña bµi to¸n trªn ®èi víi mäi gi¸ trÞ d¬ng cña tham sè vµ liªn hÖ c¸c lêi gi¶i t×m ®îc víi kh¸i niÖm ®iÓm h÷u hiÖu. Nh vËy, ta ®i ®Õn bµi to¸n quy ho¹ch tuyÕn tÝnh tham sè, nhiÒu môc tiªu sau: 11 p max , CX =   k Ck, X: AX = B, X  0, k 1 (1.3) p víi  = (1, 2,..., p)  Rp vµ  > 0,   k = 1 (kh«ng mÊt tÝnh tæng qu¸t ta gi¶ sö k 1 nh vËy). Khi ®ã viÖc t×m c¸c ®iÓm h÷u hiÖu cña bµi to¸n tèi u ®a môc tiªu (1.2) quy vÒ t×m c¸c ph¬ng ¸n cña bµi to¸n (1.3). §Þnh lý. Ph¬ng ¸n X0 cña bµi to¸n (1.2) lµ ®iÓm tèi u Pareto khi vµ chØ khi t×m ®îc vect¬ träng sè   Rp,  > 0, sao cho X0 lµ ph¬ng ¸n tèi u cña bµi to¸n (1.3). Chøng minh. §iÒu kiÖn ®ñ: Cho X0  D, tøc lµ X0  Rn vµ tháa m·n A X0 = B, X0  0 Gi¶ sö t×m ®îc vect¬   Rp víi k > 0, k = 1, p sao cho X0 ®¹t cùc ®¹i cña , CX  trªn D. NÕu X0 kh«ng ph¶i lµ ®iÓm h÷u hiÖu cña bµi to¸n (1.2) lóc ®ã tån t¹i X  D sao cho CX  CX0 vµ Ck, X > Ck, X0 víi Ýt nhÊt mét k nµo ®ã thuéc 1, ..., p. Tõ ®ã suy ra , CX > , CX0, ®iÒu nµy m©u thuÉn víi X0 lµ ph¬ng ¸n tèi u cña bµi to¸n (1.3). VËy X0 lµ ®iÓm tèi u Pareto cña bµi to¸n (1.2). §iÒu kiÖn cÇn: Gi¶ sö X0  D lµ ®iÓm tèi u Pareto cña bµi to¸n (1.2). Khi ®ã tËp låi ®a diÖn M0 = Y  Rp, Y = CX - CX0, X  D kh«ng chøa vect¬ Y > 0. Do ®ã nãn låi ®a diÖn M = TY: Y  M0, T  0 còng kh«ng chøa vect¬ TY nµo nh thÕ. V× vËy nÕu N lµ ®a diÖn x¸c ®Þnh bëi N = Z  Rp: zi = 1, zi  0, i th× M  N = . Do M, N lµ c¸c tËp låi ®ãng, mÆt kh¸c N giíi néi nªn N lµ tËp compact nªn theo ®Þnh lý t¸ch trong gi¶i tÝch låi th× tån t¹i vect¬   Rp,   0 sao cho , Y < , Z, Y  M, Z  N. Cho Y = 0 vµ Z = ei = (0, ..., 0, 1, 0, ..., 0)  Rp ta ®îc (sè 1 vÞ trÝ thø i) , 0 < , ei, tøc lµ 0 < i , i = 1, ..., p. Tõ ®ã suy ra  = (1, ..., p) > 0 lµ t×m ®îc. (*) 12 BËy giê ta cÇn chøng minh X0 lµ ph¬ng ¸n tèi u cña bµi to¸n (1.3) hay X0 ®¹t cùc ®¹i cña , CX trªn D. ThËt vËy, nÕu ngîc l¹i th× tån t¹i X  D sao cho , CX > , CX0 hay lµ , CX - CX0 > 0. Khi ®ã vect¬ TY = T(CX - CX0)  M, T  0 vµ , TY  + khi T  +. §iÒu nµy tr¸i víi (*). Do ®ã X0 lµ ph¬ng ¸n tèi u cña bµi to¸n (1.3). Qua ®Þnh lý nµy ta thÊy r»ng tËp tÊt c¶ c¸c ®iÓm h÷u hiÖu cña bµi to¸n tèi u ®a môc tiªu (1.2) trïng víi tËp c¸c ph¬ng ¸n tèi u cña bµi to¸n (1.3). Gi¶i bµi to¸n (1.3) ta t×m ®îc tËp c¸c ®iÓm h÷u hiÖu cña bµi to¸n (1.2). MÆt kh¸c lêi gi¶i cña bµi to¸n ®a môc tiªu chØ cã thÓ chän trong tËp c¸c ®iÓm h÷u hiÖu. VËy vÊn ®Ò lµ ph¶i chän trong tËp c¸c ®iÓm h÷u hiÖu c¸c ®iÓm tèi u theo mét sè tiªu chuÈn phô nµo ®ã. Cã nhiÒu thuËt to¸n kh¸c nhau ®Ó t×m tÊt c¶ hay mét phÇn cã chän läc c¸c ®iÓm h÷u hiÖu cña bµi to¸n (1.2) vµ (1.3). ë ch¬ng sau chóng ta sÏ tr×nh bµy mét sè thuËt to¸n ®Ó gi¶i quyÕt vÊn ®Ò nµy. 1.3.3. Gép c¸c môc tiªu Gi¶ sö cã k hµm môc tiªu fi : D  R, i = 1, ..., k. Cã nhiÒu c¸ch gép môc tiªu, ch¼ng h¹n: C¸ch 1: X©y dùng mét hµm U(f(X)) = U(f1(X), f2(X), ..., fk(X)). Tõ ®ã gi¶i bµi to¸n max(min)U(f(X)). VÊn ®Ò lµ chän hµm U nh thÕ nµo. Th«ng thêng ®èi víi bµi to¸n quy ho¹ch víi rµng buéc tuyÕn tÝnh D = X  Rn, AX = B, X  0 ta cã thÓ chän hµm U nh sau k U(X) =  c f (X), i i i 1 trong ®ã ci, (ci > 0), i = 1, ..., k, lµ c¸c träng sè g¸n cho môc tiªu thø i. Lóc ®ã bµi to¸n nhiÒu môc tiªu ®îc chuyÓn vÒ bµi to¸n mét môc tiªu duy nhÊt U(X)  max(min)    AX = B, X  0 C¸ch 2: §èi víi mçi hµm môc tiªu fi chän mét trÞ “chuÈn” gi¸ trÞ fi(X) cña mét ph¬ng ¸n X kh¸ tèt theo môc tiªu thø i vµ ®Æt yi = max0, fi(X) - fi  (møc ®é vît kÕ ho¹ch) zi = max0, f i - fi(X) (møc ®é hôt kÕ ho¹ch) Hµm U ®îc x¸c ®Þnh U(Y, Z) = TY + TZ, víi ,  lµ vect¬ k träng sè vµ Y = (y1, ..., yk), Z = (z1, ..., zk). fi (ch¼ng h¹n 13 Khi ®ã bµi to¸n nhiÒu môc tiªu ®Çu cã thÓ thay b»ng bµi to¸n mét môc tiªu duy nhÊt sau U(Y, Z)  max(min) AX = B   víi ®iÒu kiÖn    f(X) - Y + Z =  ( chän tríc) X, Y, Z  0. 1.3.4. Dïng nh÷ng ®Þnh møc kiÓm tra Gi¶ sö mçi môc tiªu fi cã mét ®Þnh møc thay k môc tiªu ®· chän b»ng môc tiªu F(X) = 1mink i nµo ®ã (i = 1, ..., k). Khi ®ã ta fi fi ( X ) fi §Ó gi¶i bµi to¸n víi hµm môc tiªu nµy ta lÊy biÕn míi lµ V = 1mink i fi ( X ) fi vµ gi¶i bµi to¸n quy ho¹ch maxV fi(X)  AX = B X0   víi ®iÒu kiÖn    fi (i = 1, ..., k) Nh vËy viÖc gi¶i bµi to¸n nhiÒu môc tiªu ®îc chuyÓn vÒ gi¶i bµi to¸n mét môc tiªu trªn. 1.3.5. §a mét mªtric vµo kh«ng gian c¸c hµm môc tiªu Tríc tiªn ta gi¶i c¸c bµi to¸n mét môc tiªu thø i (i = 1, ..., k) maxfi(X) X  D  Rn Gi¶ sö Xi ®¹t cùc ®¹i cña c¸c fi(X), khi ®ã ®Æt fi = fi(Xi), i = 1, ..., k th× ®iÓm fi = (f1, ..., fk)  Rk ®îc gäi lµ tèi u lý tëng (hay “cùc ®¹i tuyÖt ®èi”). Th«ng thêng th× c¸c ®iÓm Xi lµ ph©n biÖt vµ f lµ lý tëng kh«ng ®¹t tíi ®îc tõ mét X nµo chÊp nhËn ®îc. Do ®ã ta ®i t×m ®iÓm gÇn lý tëng nhÊt nh sau Ta x¸c ®Þnh trong kh«ng gian c¸c hµm môc tiªu mét “kho¶ng c¸ch” tõ ®iÓm f(X) tíi ®iÓm cùc ®¹i tuyÖt ®èi f b»ng c¸ch LÊy mét ma trËn P = (pij) ®èi xøng cÊp kk, x¸c ®Þnh d¬ng §Æt h=  f i, j i   ( X )  f i  pij f j ( X )  f j  14 h gäi lµ kho¶ng c¸ch tõ f(X) ®Õn f. Trêng hîp riªng khi P lµ ma trËn ®ång nhÊt th× h = k ( f i 1 i ( X )  fi ) 2 còng chÝnh lµ kho¶ng c¸ch th«ng thêng gi÷a 2 ®iÓm trong kh«ng gian Rk. Bµi to¸n nhiÒu môc tiªu ban ®Çu chuyÓn vÒ bµi to¸n quy ho¹ch th«ng thêng víi hµm môc tiªu h(X). min h(X) XD Trªn ®©y lµ mét sè c¸ch tiÕp cËn ®Ó gi¶i bµi to¸n quy ho¹ch ®a môc tiªu. 1.4. Mét sè tÝnh chÊt cña bµi to¸n quy ho¹ch ®a môc tiªu tuyÕn tÝnh 1.4.1. Bµi to¸n quy ho¹ch ®a môc tiªu tuyÕn tÝnh Chóng ta nh¾c l¹i bµi to¸n tèi u ®a môc tiªu tuyÕn tÝnh (1.2): Cho p lµ mét sè nguyªn (p  2), Ci = (ci1, ci2, ..., cin)  Rn, i = 1, ..., p. C lµ ma trËn cÊp p  n cã c¸c hµng lµ c¸c vect¬ Ci, i = 1, ..., p. B = (bi) lµ ma trËn cÊp m  1. A = (Aj) = (aij) lµ ma trËn cÊp m  n. X = (xj) lµ ma trËn cÊp n 1. D = X  Rn: AX = B, X  0 lµ miÒn rµng buéc cña bµi to¸n. Bµi to¸n tèi u ®a môc tiªu tuyÕn tÝnh (MOLP) ®îc x¸c ®Þnh bëi VmaxCX : AX = B, X  0 (1.2) 1.4.2. TÝnh chÊt 1.4.2.1. §Þnh lý. Gi¶ sö Ck, X lµ mét trong c¸c môc tiªu cña bµi to¸n (1.2). XÐt bµi to¸n quy ho¹ch maxCk, X : AX = B, X  0 (*). * lµ ph¬ng ¸n tèi u duy nhÊt cña bµi to¸n (*) trªn th× X* lµ mét ®iÓm NÕu X h÷u hiÖu cña bµi to¸n (1.2). Chøng minh. Do X* lµ ph¬ng ¸n tèi u duy nhÊt cña bµi to¸n (*), nÕu víi mét ph¬ng ¸n X  D mµ X  X* th× ta lu«n cã Ck, X* > Ck, X. Do ®ã kh«ng tån t¹i X  D sao cho CX  CX* vµ CX  CX*. Tõ ®ã suy ra X* lµ ®iÓm h÷u hiÖu cña bµi to¸n (1.2). 1.4.2.2. NÕu bµi to¸n tèi u ®a môc tiªu tuyÕn tÝnh (1.2) cã ®iÓm h÷u hiÖu th× nã cã Ýt nhÊt mét ®Ønh (ph¬ng ¸n cùc biªn) cña D lµ ®iÓm h÷u hiÖu. 1.4.2.3. NÕu 2 ®iÓm h÷u hiÖu X 1, X 2 cña bµi to¸n (1.2) lµ 2 ®Ønh kÒ nhau th× tÊt c¶ c¸c ®iÓm thuéc c¹nh [X 1, X 2] ®Òu lµ nh÷ng ®iÓm h÷u hiÖu cña bµi to¸n (1.2). Chøng minh. Gi¶ sö X  [X1, X 2]. 15 Khi ®ã tån t¹i   [0, 1] sao cho X = X1 + (1 - )X2. CÇn chøng minh X lµ ®iÓm h÷u hiÖu. Ngîc l¹i, gi¶ sö X kh«ng ph¶i lµ ®iÓm h÷u hiÖu cña bµi to¸n (1.2), khi ®ã tån t¹i X’  D sao cho CX’  CX vµ CX’  CX. Ta cã CX = CX1 + (1- )X2 nªn CX’  CX1 + (1 -)CX2. MÆt kh¸c, do X 1, X 2 lµ c¸c ®iÓm h÷u hiÖu nªn CX1 > CX’, CX’ > CX2. Suy ra CX’ > CX’ + (1 - )CX’ = CX’. V« lý. VËy X lµ ®iÓm h÷u hiÖu cña bµi to¸n (1.2). B©y giê ta xÐt bµi to¸n quy ho¹ch tuyÕn tÝnh    víi ®iÒu kiÖn     y0 = y1 + y2 + ... + yp  max CX – Y = CX0 (1.5) AX = B (1.6) X0 (1.7) (1.4) Y = (y1, ..., yp)  0. (1.8) Ký hiÖu D’ lµ tËp ph¬ng ¸n cña bµi to¸n ®a cho. 1.4.2.4. §Þnh lý. Tõ bµi to¸n (1.4)-(1.8), ta cã a) X0 lµ ®iÓm h÷u hiÖu cña bµi to¸n (1.2) khi vµ chØ khi maxy0 = 0. b) NÕu (X1, Y1) lµ ph¬ng ¸n tèi u víi gi¸ trÞ maxy0 > 0 th× X1 lµ ®iÓm h÷u hiÖu cña bµi to¸n (1.2). c) NÕu hµm môc tiªu y0 kh«ng bÞ chÆn trªn trong miÒn rµng buéc D’ th× bµi to¸n (1.2) kh«ng cã ®iÓm h÷u hiÖu. Chøng minh. a) Theo ®Þnh nghÜa X0 lµ ®iÓm h÷u hiÖu cña bµi to¸n (1.2), tøc lµ khi vµ chØ khi kh«ng tån t¹i X  X  D sao cho CX  CX0 vµ CX  CX0, tøc lµ kh«ng tån t¹i Y  0 vµ Y  0, Y  D’, ®iÒu ®ã cã nghÜa lµ khi vµ chØ khi maxy0 = 0. b) NÕu (X1, Y1) lµ ph¬ng ¸n tèi u cña bµi to¸n quy ho¹ch tuyÕn tÝnh vµ gi¸ trÞ maxy0 > 0. Ta chøng minh X1 lµ ®iÓm h÷u hiÖu cña bµi to¸n (1.2). Gi¶ sö X1 kh«ng ph¶i lµ ®iÓm h÷u hiÖu cña bµi to¸n (1.2). Khi ®ã tån t¹i X2  D sao cho CX2  CX1 vµ CX2  CX1. §Æt Y2 = CX2 – CX0 ta cã Y2 = CX2 – CX0  Y1 = CX1 – CX0, hay Y2  Y1 vµ Y2  Y1. §iÒu nµy m©u thuÉn víi Y1 lµ ph¬ng ¸n tèi u cña bµi to¸n quy ho¹ch tuyÕn tÝnh trªn. Do ®ã X1 lµ ®iÓm h÷u hiÖu cña bµi to¸n tèi u ®a môc tiªu (2.1). c) Ký hiÖu D0 = X  D : CX  CX0Do hµm môc tiªu kh«ng bÞ chÆn trªn trong miÒn D’ nªn tån t¹i d·y Xt  D0 sao cho p  k 1 C k , X t  + (khi t   (1.9) 16 NÕu D cã ®iÓm h÷u hiÖu, ch¼ng h¹n lµ X , th× kh«ng tån t¹i X  D tháa m·n p CX  C X , CX  C X , nghÜa lµ  Ck , X ®¹t cùc ®¹i trªn D. k 1 Nãi riªng trªn D0  D th× ®iÒu nµy tr¸i víi (1.9) V× vËy D kh«ng thÓ cã ®iÓm h÷u hiÖu. Ký hiÖu DE lµ tËp hîp c¸c ®iÓm h÷u hiÖu cña bµi to¸n (MOLP). T tëng chÝnh cña ph¬ng ph¸p tèi u Pareto lµ tõ ®a môc tiªu, lÊy riªng mét môc tiªu nµo ®ã, ký hiÖu lµ Ci, X, xÐt bµi to¸n quy ho¹ch (P) max Ci, X : X  DE. Ngêi ta [4] ®· chøng minh ®îc ®Þnh lý quan trong sau ®©y: 1.4.2.5. §Þnh lý. Bµi to¸n (P) cã ph¬ng ¸n tèi u lµ mét ®Ønh (ph¬ng ¸n cùc biªn) cña D. C¸c ®Þnh lý trªn ®· tr¶ lêi cho c©u hái khi nµo th× mét ®iÓm X0 D lµ mét ®iÓm h÷u hiÖu, c¸ch t×m mét ®iÓm h÷u hiÖu vµ chØ râ bµi to¸n khi nµo th× kh«ng cã ®iÓm h÷u hiÖu. Nh vËy th× víi bµi to¸n ®a môc tiªu tuyÕn tÝnh (MOLP), viÖc t×m c¸c ®iÓm h÷u hiÖu qui vÒ viÖc kh¶o s¸t c¸c bµi to¸n quy ho¹ch tuyÕn tÝnh. C¸c kÕt qu¶ nµy sÏ ®îc sö dông trong môc 2.2, ch¬ng 2. Ch¬ng 2 thuËt to¸n gi¶i quy ho¹ch ®a môc tiªu tuyÕn tÝnh Bµi to¸n ®a môc tiªu ®· vµ ®ang ®îc nhiÒu ngêi quan t©m gi¶i quyÕt vµ ®· cã nhiÒu ph¬ng ph¸p gi¶i. Tuy nhiªn, mçi ph¬ng ph¸p ®Òu cã nh÷ng u khuyÕt ®iÓm cña nã. Nhng tËp trung l¹i ta thÊy bµi to¸n ®a môc tiªu thêng qua 2 bíc sau: Bíc 1: T×m tÊt c¶ c¸c ph¬ng ¸n tèi u pareto Xk. Ta nhËn thÊy r»ng nghiÖm tèi u cña bµi to¸n lµ nghiÖm tèi u pareto. Song ®iÒu ngîc l¹i cha ch¾c ®· ®óng, chuyÓn sang bíc 2. Bíc 2: Xö lý thu gän tËp tèi u pareto ®Ó thu ®îc nghiÖm tèi u. Thùc tÕ cã rÊt nhiÒu ph¬ng ph¸p vµ c¸ch gi¶i quyÕt kh¸c nhau. C¸c ph¬ng ph¸p nµy cã thÓ gi¶i bµi to¸n quy ho¹ch ®a môc tiªu tuÇn tù qua 2 bíc chñ yÕu hoÆc dïng ®Ó xö lý tËp ph¬ng ¸n tèi u pareto. Còng cã nh÷ng ph¬ng ph¸p gi¶i hÇu nh gép c¶ 2 bíc l¹i, ch¼ng h¹n nh ph¬ng ph¸p gi¶i dùa vµo lý thuyÕt ®å thÞ. Trong ch¬ng nµy chóng ta sÏ ®a ra mét sè ph¬ng ph¸p ®Ó gi¶i quyÕt bµi to¸n ®a môc tiªu. ë phÇn ®Çu ta sÏ nªu tæng quan c¸c ph¬ng ph¸p kh¸c nhau ®Ó gi¶i bµi to¸n ®a môc tiªu. PhÇn tiÕp theo sÏ tr×nh bµy ph¬ng ph¸p tèi u pareto ®Ó gi¶i quyÕt bµi to¸n ®a môc tiªu. 2.1. Tæng quan c¸c ph¬ng ph¸p gi¶i bµi to¸n ®a môc tiªu Nh¾c l¹i m« h×nh cña bµi to¸n ®a môc tiªu (1.1): 17 max (min) f(X) X  D  Rn f(X) = (f1(X), ..., fk(X)  Rk, k  2. D lµ tËp ph¬ng ¸n cña bµi to¸n, fi(X) lµ c¸c hµm môc tiªu. ë ®©y ta sÏ ®i gi¶i quyÕt bµi to¸n quy ho¹ch ®a môc tiªu kÕt hîp víi së thÝch cña ngêi nhËn lêi gi¶i (NNLG). Tøc lµ bµi to¸n mµ khi xö lý tËp ph¬ng ¸n pareto, vai trß cña NNLG t¸c ®éng ®¸ng kÓ trong qu¸ tr×nh gi¶i. NNLG dêng nh ngô ý r»ng trong tËp ph¬ng ¸n ®ã, c¸c ph¬ng ¸n cã quan hÖ tréi h¬n () vµ kh«ng ph©n biÖt (∽) ®îc h×nh thµnh tõ viÖc so s¸nh “lîi Ých” cña c¸c ph¬ng ¸n. Gi¶i bµi to¸n nh vËy gäi lµ bµi to¸n quy ho¹ch ®a môc tiªu (QH§MT) kÕt hîp së thÝch NNLG. Ta hiÓu “lîi Ých” ë ®©y lµ mét hµm u : f(D)  R vµ u ®îc gi¶ thiÕt tháa m·n mét sè ®iÒu kiÖn nµo ®ã kh¸i qu¸t tõ bµi to¸n thùc tÕ vµ hiÖn tîng thùc tiÔn. Tuy nhiªn, ë ®©y ta hiÓu ®¬n thuÇn u chØ lµ mét ¸nh x¹ do së thÝch cña NNLG. Hµm u cã thÓ cho díi d¹ng têng minh hoÆc lµ d¹ng Èn (tøc lµ hiÓu r»ng c¸c ph¬ng ¸n cã thÓ so s¸nh ®îc víi nhau theo mét nghÜa “h¬n” “kÐm” “kh«ng ph©n biÖt” nµo ®ã). Bµi to¸n quy ho¹ch ®a môc tiªu kÕt hîp víi lîi Ých cña NNLG trong trêng hîp hµm u têng minh cã thÓ viÕt max u(f(X)) : X  D (víi bµi to¸n min th× chØ cÇn ®æi dÊu hµm u vµ chuyÓn vÒ max). Sau ®©y ta ®i vµo cô thÓ tõng ph¬ng ph¸p 2.1.1. Ph¬ng ph¸p nhîng bé dÇn Ph¬ng ph¸p nµy dÉn ®Õn t×m mét lêi gi¶i tháa hiÖp tèt nhÊt tøc lµ t×m nghiÖm X* mµ theo ý thÝch cña NNLG th× mäi X  D, X*  X hoÆc X* ∽ X ThuËt to¸n gi¶i Bíc 0: Gi¶i k bµi to¸n mét môc tiªu riªng rÏ max (fi(X)) : X  D, i = 1, ..., k. LËp b¶ng thëng ph¹t (b¶ng 2.1), trong ®ã Xi lµ ph¬ng ¸n tèi u, fi0, i = 1, 2, ..., k lµ gi¸ trÞ tèi u. B¶ng 2.1 Hµm môc tiªu ... f1 f2 fk Ph¬ng ¸n ... X1 f10 f2(X1) fk(X1) 0 ... X2 f2 fk(X2) ... ... ... ... ... Xk f k0 Bíc 1. C¨n cø vµo b¶ng thëng ph¹t vµ f10, NNLG b¾t f1 ph¶i nhîng bé mét lîng f1 vµ gi¶i bµi to¸n maxf2(X) 18 víi ®iÒu kiÖn    XD f1(X)  f10 - f1 Gi¶ sö f2* lµ gi¸ trÞ tèi u cña bµi to¸n, chuyÓn sang bíc 2. Bíc 2. NNLG c¨n cø vµo f20 vµ f2* b¾t f2 nhîng bé mét lîng f2 vµ gi¶i bµi to¸n maxf3(X)   víi ®iÒu kiÖn    XD f1(X)  f10 - f1 f2(X)  f2* - f2 Gi¶ sö f3* lµ gi¸ trÞ tèi u cña bµi to¸n, chuyÓn sang bíc tiÕp theo. .......... Bíc k. C¨n cø vµo fk0 vµ fk*, NNLG b¾t fk nhîng bé mét lîng fk vµ gi¶i bµi to¸n víi ®iÒu kiÖn XD          f1(X)  f10 - f1 f2(X)  f2* - f2 ... fk(X)  fk* - fk Ph¬ng ¸n tèi u cña bµi to¸n cuèi cïng lÊy lµm ph¬ng ¸n tèi u cho bµi to¸n xuÊt ph¸t ban ®Çu. 2.1.2. Ph¬ng ph¸p t×m nghiÖm cã kho¶ng c¸ch ng¾n nhÊt ®Õn nghiÖm lý tëng Theo ph¬ng ph¸p nµy, hµm lîi Ých u tû lÖ víi kho¶ng c¸ch tõ ph¬ng ¸n X  D ®Õn nghiÖm lý tëng. Ta gäi X1 gÇn nghiÖm lý tëng h¬n X2 nÕu ph¬ng ¸n X1  X2. Tríc tiªn ta ®Þnh nghÜa thÕ nµo lµ nghiÖm lý tëng vµ kho¶ng c¸ch ®îc x¸c ®Þnh nh thÕ nµo. 2.1.2.1. §Þnh nghÜa. Gi¶ sö X1, X2  Rn. Kho¶ng c¸ch gi÷a 2 ®iÓm X1, X2 lµ mét sè d x¸c ®Þnh bëi n 1 2  d =  xi  xi   i 1  víi X1 = (x11, x21, ..., xn1); X2 = (x12, x22, ..., xn2)  Rn;  lµ tham sè,   1. Tõ ®Þnh nghÜa ta thÊy d  d  d1, trong ®ã d = max xi1 – xi2. i 19 Cho bµi to¸n quy ho¹ch ®a môc tiªu maxf(X) X  D, X* ®îc gäi lµ nghiÖm lý tëng cña bµi to¸n nµy nÕu X* lµ mét nghiÖm (nãi chung kh«ng nhÊt thiÕt lµ ph¬ng ¸n chÊp nhËn ®îc) mµ t¹i ®ã gi¸ trÞ cña mçi hµm môc tiªu riªng rÏ ®Òu ®¹t cùc ®¹i. Gi¶ sö fi* lµ c¸c gi¸ trÞ tèi u cña tõng môc tiªu riªng rÏ: fi* = maxfi(X) víi X  D. Khi ®ã gi¸ trÞ cña hµm môc tiªu f t¹i X* lµ (f1*, ..., fk*) vµ kho¶ng c¸ch tõ mét ph¬ng ¸n X ®Õn nghiÖm lý tëng x¸c ®Þnh bëi k  d =  f i ( X )  f i  i 1   .  2.1.2.2. Bµi to¸n cùc tiÓu kho¶ng c¸ch ®Õn nghiÖm lý tëng Bµi to¸n k min   f i ( X )  f i   i 1     (2.1) X  D. (2.2) ë ®©y vÊn ®Ò x¸c ®Þnh  nãi chung phô thuéc vµo c¸c bµi to¸n cô thÓ vµ c¸c kÕt qu¶ vÒ mÆt lý thuyÕt ®Ó t×m ra mét thuËt to¸n gi¶i bµi to¸n quy ho¹ch (2.1) (2.2). XÐt 2 trêng hîp ®Æc biÖt: (+) Trêng hîp  = 1. Lóc ®ã gi¶i bµi to¸n k min d 1 = min   f i ( X )  f i   ,   X D XD  i 1  (2.3) t¬ng ®¬ng víi lêi gi¶i bµi to¸n k  X D max i 1 fi ( X ) . (2.4) Lóc nµy k X X  1 2 k  f (X ) >  f (X ). i i 1 i 1 2 i 1 (+) Trêng hîp  = . Bµi to¸n min d = min max fi* – fi (X), X D X D 1 i  k (2.4) cßn cã thÓ viÕt díi d¹ng min W (2.5)