Quy hoạch tuyến tính và những ứng dụng trong hệ thống nguồn nước

76 CH¦¥NG 3 Quy ho¹ch tuyÕn tÝnh vµ nh÷ng øng dông trong hÖ thèng nguån n­íc 3.1. Quy ho¹ch tuyÕn tÝnh M« h×nh quy ho¹ch tuyÕn tÝnh (QHTT) ®· vµ ®ang ®­îc ¸p dông réng r·i trong c¸c bµi to¸n ph©n bæ tèi ­u tµi nguyªn. Nh­ tªn cña nã gîi ý, m« h×nh QHTT cã hai tÝnh chÊt c¬ b¶n lµ c¶ hµm môc tiªu vµ c¸c rµng buéc lµ c¸c hµm tuyÕn tÝnh cña c¸c biÕn quyÕt ®Þnh. D¹ng tæng qu¸t cña mét m« h×nh QHTT cã d¹ng: Max (hoÆc Min) j n j j xcx    1 0 (3.1.1a) Víi c¸c biÓu thøc rµng buéc: ij n 1j ij bxa   víi i = 1, 2, ... n (3.1.1b) xj  0, víi j = 1, 2, ... n (3.1.1c) Trong ®ã, cj lµ hÖ sè cña hµm môc tiªu, aij lµ hÖ sè c«ng nghÖ vµ bi lµ hÖ sè vÕ ph¶i cña ph­¬ng tr×nh rµng buéc (Right Hand Side - RHS) ë d¹ng ®¹i sè, m« h×nh QHTT nµy cã thÓ khai triÓn nh­ sau: Max (hoÆc Min) x0 = c1x1 + c2x2 + ... + cnxn (3.1.2a) Víi c¸c rµng buéc: a11x1 + a12x2 + ... + a1nxn  b1 a12x2 + a22x2 + ... + a2nxn  b2 77 M M M M M (3.1.2b) am1x1 + am2x2 + ...+ amnxn  bm x1  0; x2  0, ...xn  0 ë d¹ng ma trËn, m« h×nh QHTT cã thÓ viÕt chÝnh x¸c lµ: Max (hoÆc Min) x0 = C Tx (3.1.3a) Víi rµng buéc Ax  b (3.1.3b) x  0 (3.1.3c) Víi C lµ vÐc t¬ cét (n x 1) cña c¸c hÖ sè hµm môc tiªu, x lµ vec t¬ cét (n x 1) cña c¸c biÕn quyÕt ®Þnh, A lµ ma trËn (m x n) cña c¸c hÖ sè c«ng nghÖ, b lµ vÐc t¬ cét (m x 1) c¸c hÖ sè c¸c vÕ bªn ph¶i hµm rµng buéc. ChØ sè trªn T ký hiÖu chuyÓn vÞ cña ma trËn hay vect¬. C¸c s¸ch hay cã liªn quan ®Õn QHTT bao gåm Gass (1985), Taha (1987), Vinston (1987) vµ Hillien vµ Lieberman (1990). VÝ dô 3.1.1. XÐt mét hÖ thèng bao gåm mét nhµ m¸y s¶n xuÊt vµ mét nhµ m¸y xö lÝ chÊt th¶i (Fiering vµ c¸c céng sù, 1971). Nhµ m¸y s¶n xuÊt t¹o ra c¸c thµnh phÈm víi gi¸ b¸n ra cho mçi thµnh phÈm lµ 10 ngh×n ®« la. Tuy nhiªn, gi¸ s¶n xuÊt cho mçi thµnh phÇn lµ 3 ngh×n ®« la. Trong qu¸ tr×nh s¶n xuÊt hai ®¬n vÞ chÊt th¶i ®­îc t¹o ra tõ mçi thµnh phÈm. Ngoµi viÖc quyÕt ®Þnh sè l­îng c¸c thµnh phÈm nªn s¶n xuÊt, ng­êi qu¶n lý nhµ m¸y còng cÇn quyÕt ®Þnh l­îng chÊt th¶i ®­îc th¶i ra kh«ng qua xö lÝ ®Ó lµm sao lîi nhuËn thùc (net-benefit) cña nhµ m¸y lµ tèi ®a mµ yªu cÇu vÒ chÊt l­îng n­íc cña s«ng kh«ng bÞ v­ît qu¸ møc cho phÐp. C«ng suÊt tèi ®a cña nhµ m¸y xö lÝ chÊt th¶i lµ 10 ®¬n vÞ chÊt th¶i víi hiÖu suÊt sö lý lµ 80%, vµ gi¸ thµnh cho mçi ®¬n vÞ chÊt th¶i lµ 0,6 ngh×n ®« la. §ång thêi nhµ m¸y còng ph¶i tr¶ thuÕ ¶nh h­ëng cho l­îng chÊt th¶i th¶i ra s«ng (2 ngh×n ®« la cho mçi mét ®¬n vÞ chÊt th¶i ra). §¬n vÞ qu¶n lý kiÓm so¸t « nhiÔm n­íc ®­a ra tiªu chuÈn tèi ®a lµ 4 ®¬n vÞ chÊt th¶i cña mçi nhµ m¸y th¶i ra. H·y thiÕt lËp m« h×nh QHTT cho bµi to¸n nµy. Lêi gi¶i. B­íc ®Çu tiªn cña viÖc x©y dùng m« h×nh lµ x¸c ®Þnh c¸c thµnh phÇn hÖ thèng vµ c¸c mèi quan hÖ t­¬ng t¸c cña chóng. Trong vÝ dô nµy, c¸c thµnh phÇn cña hÖ thèng lµ: nhµ m¸y s¶n xuÊt, nhµ m¸y xö lÝ chÊt th¶i, vµ con s«ng nhËn l­îng chÊt th¶i. Tõ ®Þnh nghÜa cña bµi to¸n, ta thÊy cã 2 biÕn quyÕt ®Þnh lµ: (1) sè l­îng c¸c ®¬n vÞ thµnh phÈm nªn s¶n xuÊt, x1, vµ (2) l­îng chÊt th¶i ®æ trùc tiÕp vµo s«ng kh«ng qua xö lÝ, x2. Tõ sù m« t¶ mèi quan hÖ qua l¹i gi÷a thµnh phÈm, l­îng chÊt th¶i ®­îc t¹o ra, hiÖu suÊt nhµ m¸y xö lÝ, mét s¬ ®å minh häa hÖ thèng nghiªn cøu cã thÓ ®­îc thiÕt lËp vµ thÓ hiÖn trªn h×nh 3.1.1. L­îng chÊt th¶i ë mçi nh¸nh cã thÓ ®­îc x¸c ®Þnh b»ng nguyªn lý c©n b»ng khèi l­îng. VÊn ®Ò cèt lâi cÇn lµm tr­íc khi x©y dùng m« h×nh lµ x¸c ®Þnh môc tiªu vµ c¸c rµng buéc cña bµi to¸n. Trong vÝ dô nµy, môc tiªu cña bµi to¸n tèi ®a lîi nhuËn thùc. C¸c rµng buéc g©y ra bëi c¸c h¹n chÕ vÒ c«ng suÊt nhµ m¸y xö lÝ chÊt th¶i vµ l­îng chÊt th¶i cho phÐp ®æ vµo s«ng ®­îc quy ®Þnh víi c¸c nhµ kiÓm so¸t « nhiÔm n­íc. Khi ®· x¸c ®Þnh ®­îc môc tiªu vµ c¸c rµng buéc cña bµi to¸n, b­íc x©y dùng m« h×nh tiÕp theo vÒ c¬ së liªn quan ®Õn viÖc chuyÓn hãa c¸c m« t¶ c¸c môc tiªu vµ rµng buéc b»ng ng«n ng÷ sang sù diÔn t¶ b»ng to¸n häc th«ng qua c¸c biÕn quyÕt ®Þnh vµ c¸c th«ng sè. L·i thùc cña nhµ m¸y s¶n xuÊt ®­îc x¸c ®Þnh dùa trªn 4 yÕu tè: (a) sè l­îng b¸n ra c¸c thµnh phÈm (tÝnh b»ng ngh×n ®« la) gi¸ thµnh s¶n xuÊt cña c¸c thµnh phÈm (tÝnh b»ng ngh×n ®« la), 3x1; (c) chi phÝ cho viÖc xö lÝ chÊt th¶i (ngh×n ®« la) t¹o ra tõ qu¸ tr×nh s¶n xuÊt, 0,6(2x1-x2) vµ (d) thuÕ ¶nh h­ëng (ngh×n ®« la) ®¸nh vµo l­îng chÊt th¶i kh«ng qua xö lÝ, 2{x2+0,2(2x1-x2)}. Lîi nhuËn thùc cña nhµ m¸y b»ng tæng l­îng tiÒn thu ®­îc trõ ®i tæng c¸c chi phÝ. Hµm môc tiªu cña bµi to¸n lµ tèi ®a hãa 78 lîi nhuËn thùc (l·i rßng), vµ b»ng: 10x1-{3x1+0,6(2x1-x2)+2x2+0,2(2x1-x2)}. Hµm môc tiªu cã thÓ diÔn gi¶i lµ: Max x0 = 5x1-x2 Theo h×nh. 3.1.1, rµng buéc do h¹n chÕ vÒ c«ng suÊt cña nhµ m¸y xö lÝ n­íc th¶i cã thÓ diÔn t¶ b»ng c«ng thøc to¸n häc lµ: 2x1 - x2  10 H×nh 3.1.1 S¬ ®å m« t¶ hÖ thèng s¶n xuÊt xö lÝ chÊt th¶i. Rµng buéc nµy cho thÊy l­îng chÊt th¶i ®­îc xö lÝ, 2x1 - x2, kh«ng thÓ v­ît qu¸ c«ng suÊt cña nhµ m¸y, b»ng 10 ®¬n vÞ chÊt th¶i. T­¬ng tù, rµng buéc liªn quan ®Õn tæng l­îng chÊt th¶i cã thÓ ®æ vµo s«ng ®­îc diÔn gi¶i lµ: x2 + 0,2(2x1 - x2 )  4 ë ®ã, vÕ tr¸i (LHS) cña ®iÒu kiÖn rµng buéc nµy lµ tæng l­îng chÊt th¶i ®æ vµo s«ng (xem h×nh 3.1.1) vµ vÕ ph¶i (RHS) cña nã lµ tæng l­îng ®¬n vÞ chÊt th¶i cho phÐp ®æ ra s«ng quy ®Þnh bëi c¬ quan kiÓm so¸t « nhiÔm n­íc. Ngoµi hai rµng buéc dÔ nhËn thÊy ë ®©y, tån t¹i mét rµng buéc kh¸ nhá ®Ó nhËn biÕn ®­îc, vµ cÇn ®­îc ®­a vµo trong m« h×nh. Mét rµng buéc cÇn thiÕt ®Ó ch¾c ch¾n r»ng mét khèi l­îng n­íc ®­îc xö lÝ lµ d­¬ng. Nãi mét c¸ch kh¸c, m« h×nh nªn bao gåm mét rµng buéc lµm cho l­îng chÊt th¶i qua xö lÝ nµy kh«ng ©m, (2x1 - 2). Nã cã thÓ ®­îc diÔn gi¶i b»ng c«ng thøc to¸n häc nh­ sau: 2x1 -x2  0 Cuèi cïng, hai biÕn quyÕt ®Þnh kh«ng thÓ ©m, xÐt vÒ ý nghÜa vËt lý. Do ®ã, rµng buéc kh«ng ©m cña hai biÕn quyÕt ®inh, x1  0 vµ x2  0, ph¶i ®­îc ®­a vµo h­íng rµng buéc. Phiªn b¶n cuèi cïng cña m« h×nh quy ho¹ch tuyÕn tÝnh ®­îc viÕt d­íi d¹ng to¸n häc, sau mét vµi biÕn ®æi, cã thÓ tãm t¾t l¹i thµnh: 79 Max x0 = 5x1 - x2 Víi c¸c rµng buéc: 2x1 - x2  10 4x1 + 0,8 x2  4 2x1 - x2  0 x1  0 vµ x2  0 Xem xÐt kü viÖc thiÕt lËp m« h×nh tèi ­u hãa nµy, ng­êi ta cã thÓ nhËn thÊy r»ng m« h×nh nµy lµ mét m« h×nh quy ho¹ch tuyÕn tÝnh, Linear Programming - LP. Tuy nhiªn, nÕu nãi mét c¸ch chÆt chÏ, m« h×nh trªn cã thÓ kh«ng ®­îc c«ng nhËn lµ m« h×nh QHTT nÕu c¸c biÕn quyÕt ®Þnh, ®Æc biÖt lµ biÕn x1, chØ cã thÓ mang gi¸ trÞ nguyªn. NÕu x¶y ra tr­êng hîp nµy, m« h×nh lµ m« h×nh quy ho¹ch hçn hîp vµ yªu cÇu mét thuËt gi¶i ®Æc biÖt ®Ó gi¶i nã. Thùc tÕ lµ cã mét sè c¸c gi¶ thiÕt cÇn ®­îc ®­a vµo trong viÖc thiÕt lËp m« h×nh QHTT. C¸c gi¶ thiÕt nµy ®­îc m« t¶ mét c¸ch chi tiÕt ë c¸c môc tiÕp theo. 3.1.1. C¸c gi¶ thiÕt cña c¸c m« h×nh quy ho¹ch tuyÕn tÝnh Cã bèn gi¶ thiÕt Èn c¬ b¶n ®­îc ®­a vµo m« h×nh QHTT. 1. Gi¶ thiÕt vÒ tÝnh tû lÖ. Gi¶ thiÕt nµy cã nghÜa lµ sù ®ãng gãp cña biÕn quyÕt ®Þnh thø j vµo gi¸ trÞ hiÖu qu¶, cjxj, vµ viÖc nã sö dông c¸c tµi nguyªn kh¸c nhau, aijxj, tû lÖ trùc tiÕp víi gi¸ trÞ cña biÕn quyÕt ®Þnh t­¬ng øng. 2. Gi¶ thiÕt vÒ tÝnh céng hîp. Gi¶ thiÕt nµy cã nghÜa lµ, t¹i mét cÊp ®é ho¹t ®éng cho tr­íc (x1, x2, ... xn), tæng l­îng sö dông c¸c tµi nguyªn vµ sù ®ãng gãp vµo gi¸ trÞ hiÖu qu¶ tæng hîp b»ng tæng c¸c gi¸ trÞ t­¬ng øng ®­îc t¹o ra bëi c¸c ho¹t ®éng tiÕn hµnh riªng biÖt. 3. Gi¶ thiÕt vÒ tÝnh kh¶ chia. C¸c ®¬n vÞ cña c¸c ho¹t ®éng cã thÓ ®­îc chia ra lµm nhiÒu cÊp ®é ph©n chia, do ®ã gi¸ trÞ kh«ng nguyªn cña c¸c biÕn quyÕt ®Þnh lµ chÊp nhËn ®­îc. 4. Gi¶ thiÕt vÒ tÝnh tÊt ®Þnh. TÊt c¶ th«ng sè cña m« h×nh ®­îc gi¶ thiÕt lµ kh«ng ®æi vµ kh«ng cã tÝnh bÊt ®Þnh. ¶nh h­ëng cña tÝnh bÊt ®Þnh cña c¸c th«ng sè tíi kÕt qu¶ cã thÓ ®­îc ®iÒu tra b»ng viÖc tiÕn hµnh ph©n tÝch ®é nhËy. 3.1.2. C¸c d¹ng cña bµi to¸n QHTT Do c¸c m« h×nh QHTT cã thÓ ®­îc thÓ hiÖn d­íi nhiÒu d¹ng kh¸c nhau (tèi ®a hãa, cùc tiÓu hãa, , , ), viÖc cÇn thiÕt lµ ph¶i thay ®æi c¸c d¹ng nµy cho phï hîp víi mét quy tr×nh gi¶i cô thÓ. VÒ c¬ b¶n cã 2 d¹ng m« t¶ m« h×nh QHTT ®­îc sö dông: d¹ng chÝnh t¾c vµ d¹ng chuÈn. 80 D¹ng chÝnh t¾c ®­îc sö dông cho viÖc gi¶i c¸c m« h×nh QHTT theo ph­¬ng ph¸p ®¹i sè. C¸c ®Æc ®iÓm c¬ b¶n cña nã cã liªn quan ®Õn: (1) tÊt c¶ c¸c rµng buéc viÕt d­íi d¹ng ph­¬ng tr×nh ngo¹i trõ rµng buéc kh«ng ©m cña c¸c biÕn quyÕt ®Þnh. C¸c ®iÒu kiÖn nµy vÉn tån t¹i ë d¹ng bÊt ph­¬ng tr×nh; (2) TÊt c¶ c¸c hÖ sè vÕ ph¶i cña c¸c ph­¬ng tr×nh rµng buéc lµ kh«ng ©m, nghÜa lµ bi  0; (3) tÊt c¶ c¸c biÕn quyÕt ®Þnh lµ kh«ng ©m; vµ (4) Hµm môc tiªu cã thÓ lµ cùc ®¹i hãa hay cùc tiÓu hãa. Mét m« h×nh QHTT cã d¹ng chÝnh t¾c ®­îc thÓ hiÖn lµ: Max (hoÆc Min) 0 1 n j j j x c x   (3.1.4a) 1 , 1, 2,..., 0. 1,2,..., n i j i j j a x b i m x j n       víi víi (3.1.4b) VÝ dô 3.1.2. BiÕn ®æi m« h×nh QHTT cña vÝ dô ®­îc nªu ë môc tr­íc vÒ s¶n xuÊt, xö lÝ n­íc th¶i sang d¹ng chÝnh t¾c. Lêi gi¶i. V× hµm môc tiªu cã d¹ng chÝnh t¾c cã thÓ lµ cùc ®¹i hãa hay cùc tiÓu hãa nªn kh«ng cÇn thiÕt ph¶i biÕn ®æi hµm môc tiªu nµy. Tuy nhiªn, d¹ng chÝnh t¾c cña m« h×nh QHTT ®ßi hái tÊt c¶ c¸ rµng buéc ph¶i ë d¹ng ph­¬ng tr×nh. §iÒu nµy kh«ng tháa m·n víi c¶ 3 rµng buéc cña m« h×nh ta ®ang xÐt. Do vËy c¸ch biÕn ®æi lµ ®iÒu kiÖn cÇn thiÕt. Chó ý r»ng v× rµng buéc ®Çu tiªn cã d¹ng , mét biÕn ¶o (slack variables) kh«ng ©m s1 cã thÓ ®­îc céng vµo vÕ tr¸i cña rµng buéc, trë thµnh: 2x1 - x2 + s1 = 10 T­¬ng tù, rµng buéc bÊt ph­¬ng tr×nh thø hai cã thÓ biÕn ®æi vÒ d¹ng: 0,4x1 + 0,8x2 + s2 = 4 Trong ®ã s1 lµ biÕn ¶o kh«ng ©m ë rµng buéc thø hai. §èi víi rµng buéc thø 3, v× nã cã d¹ng , mét biÕn ¶o kh«ng ©m cã thÓ ®­îc trõ ë vÕ tr¸i, vµ ta cã kÕt qu¶: 2x1 - x2 - s3 = 0 C¸c biÕn quyÕt ®Þnh nguyªn thñy vµ ba biÕn ¶o cña s1, s2, s3 ®Òu kh«ng ©m, vµ do ®ã ®iÒu kiÖn thø 3 cña d¹ng chÝnh t¾c ®­îc tháa m·n. Thªm vµo ®ã, c¶ hÖ sè cña vÕ ph¶i cña c¸c rµng buéc còng lµ kh«ng ©m. Cuèi cïng ta cã d¹ng chÝnh t¾c cña m« h×nh QHTT cho vÝ dô s¶n xuÊt, xö lÝ chÊt th¶i nh­ sau: Max x0 = 5x1 - x2 + 0s1 + 0s2 + 0s3 Víi rµng buéc: 2x1 - x2 + s1 = 10 0,4 x1 + 0,8x2 + s2 = 4 2x1 - x2 - x3 = 0 TÊt c¶ x vµ s lµ kh«ng ©m. D¹ng chuÈn, mÆt kh¸c, rÊt cã Ých trong viÖc thÓ hiÖn lý thuyÕt ®èi ngÉu (duality theory) cña m« h×nh QHTT. Nã së h÷u ba ®Æc tÝnh sau trong viÖc thiÕt lËp m« h×nh: (1) tÊt c¶ c¸c biÕn quyÕt ®Þnh lµ kh«ng ©m; (2) tÊt c¶ c¸c rµng buéc cã d¹ng ; vµ (3) hµm môc tiªu cã d¹ng tèi ®a hãa. Mét m« h×nh QHTT cã d¹ng chuÈn lµ: Max x0 = 1 n j j j c x   (3.1.5a) Rµng buéc bëi: 81 1 , 1,2,..., 0, 1,2,..., n ij j i j j a x b i m x j n       (3.1.5b) CÇn chó ý r»ng c¸c hÖ sè ë vÕ ph¶i cña rµng buéc cã thÓ mang gi¸ trÞ ©m. VÝ dô 3.1.3. ChuyÓn ®æi m« h×nh QHTT gèc cho vÝ dô s¶n xuÊt, xö lÝ n­íc th¶i sang d¹ng chuÈn. Lêi gi¶i: V× hµm môc tiªu nguyªn b¶n ®· cã d¹ng tèi ®a hãa nh­ yªu cÇu nªn kh«ng cÇn cã sù biÕn ®æi thªm ®èi víi nã. §èi víi c¸c rµng buéc, hai rµng buéc ban ®Çu cã d¹ng  nªn tháa m·n yªu cÇu cña d¹ng chuÈn. Tuy nhiªn, rµng buéc thø 3 cã d¹ng , ®Ó chuyÓn nã sang d¹ng  ta nh©n c¶ hai vÕ rµng buéc nµy víi -1 vµ cã kÕt qu¶ nh­ sau: -2x1 + x2  0 Yªu cÇu kh«ng ©m cña c¸c biÕn quyÕt ®Þnh cïng ®­îc tháa m·n. Cuèi cïng chóng ta cã m« h×nh QHTT d­íi d¹ng chuÈn sau: Max (x0) = 5x1 - x2 Rµng buéc bëi: 2x1 - x2  10 0,4x1 + 0,8x2  4 -2x1 + x2 0 x1  0 vµ x2  0 Th«ng th­êng, m« h×nh QHTT sau khi ®­îc x©y dùng th­êng kh«ng tháa m·n c¸c ®Æc tÝnh cña d¹ng chÝnh t¾c còng nh­ d¹ng chuÈn. C¸c biÕn ®æi c¬ së sau ®©y gióp c¸c b¹n cã thÓ chuyÓn ®æi mét m« h×nh QHTT sang bÊt kú d¹ng nµo: 1. Tèi ®a hãa mét hµm f(x) th× t­¬ng øng víi tèi thiÓu hãa gi¸ trÞ ©m cña nã, cã nghÜa lµ: Max f(x) = Min {-f(x)} 2. C¸c rµng buéc cã d¹ng  cã thÓ chuyÓn ®æi sang d¹ng  b»ng c¸ch nh©n hai vÕ cña bÊt ph­¬ng tr×nh víi -1 3. Mét ph­¬ng tr×nh cã thÓ ®­îc thay thÕ b»ng hai bÊt ph­¬ng tr×nh tr¸i dÊu nhau. VÝ dô, ph­¬ng tr×nh g(x) = b cã thÓ ®­îc thay thÕ b»ng g(x)  b vµ g(x)  b. 4. Mét bÊt ph­¬ng tr×nh cã dÊu gi¸ trÞ tuyÖt ®èi cã thÓ thay thÕ b»ng hai bÊt ph­¬ng tr×nh kh«ng cã dÊu gi¸ trÞ tuyÖt ®èi. VÝ dô, ( )g x b kh«ng thÓ thay thÕ b»ng g(x) b vµ g(x)  -b 5. NÕu mét biÕn quyÕt ®Þnh x kh«ng cã rµng buéc vÒ dÊu (cã thÓ d­¬ng, b»ng kh«ng, hoÆc ©m), nã cã thÓ thay b»ng hai biÕn quyÕt ®Þnh kh«ng ©m; x = x+ - x-, víi x+  0 vµ x-  0, 6. §Ó biÕn ®æi mét bÊt ph­¬ng tr×nh sang ph­¬ng tr×nh, mét biÕn kh«ng ©m cã thÓ ®­îc céng vµo hoÆc trõ ®i. 3.2. C¸c thuËt gi¶i cho quy ho¹ch tuyÕn tÝnh 82 3.2.1. Ph­¬ng ph¸p ®å gi¶i Mét c¸ch ®¬n gi¶n ®Ó gi¶i bµi to¸n QHTT lµ sö dông ph­¬ng ph¸p ®å gi¶i (h×nh häc). Tuy nhiªn, ph­¬ng ph¸p nµy chØ ¸p dông ®­îc cho c¸c bµi to¸n QHTT cã nhiÒu nhÊt lµ hai biÕn quyÕt ®Þnh (kh«ng kÓ c¸c biÕn ¶o). §Ó ®Æt c¬ së cho viÖc diÔn gi¶i h×nh häc cho thuËt gi¶i ®¹i sè ®­îc m« t¶ sau nµy, ph­¬ng ph¸p ®å gi¶i sÏ ®­îc sö dông ®Ó gi¶i bµi to¸n s¶n xuÊt, xö lÝ chÊt th¶i ë vÝ dô sau ®©y. VÝ dô 3.2.1. Gi¶i bµi to¸n s¶n xuÊt – xö lÝ chÊt th¶i ®Ó t×m sè l­îng ®¬n vÞ thµnh phÈm tèi ­u cÇn s¶n xuÊt x1 vµ lù¬ng chÊt th¶i ®­îc s¶n sinh vµ ®æ trùc tiÕp vµo s«ng kh«ng qua xö lÝ x2 ®Ó l·i thùc cña nhµ s¶n xuÊt lµ lín nhÊt. Lêi gi¶i. XÐt m« h×nh QHTT x©y dùng cho bµi to¸n ë vÝ dù 3.1.1, nã liªn quan ®Õn hai biÕn quyÕt ®Þnh vµ ba rµng buéc (ngo¹i trõ c¸c yªu cÇu kh«ng ©m cña c¸c biÕn quyÕt ®Þnh). MiÒn nghiÖm (feasible space) ®­îc x¸c ®Þnh bëi tÊt c¶ c¸c rµng buéc cña m« h×nh, bao gåm c¶ rµng buéc kh«ng ©m cña c¸c biÕn quyÕt ®Þnh. Do hai biÕn quyÕt ®Þnh kh«ng thÓ ©m, miÒn nghiÖm ph¶i n»m trong gãc phÇn t­ thø nhÊt (§«ng B¾c). MiÒn nghiÖm (vïng g¹ch chÐo) cho bµi to¸n vÝ dô nµy ®­îc thÓ hiÖn trªn h×nh 3.2.1. Mçi ®­êng liÒn nÐt trªn h×nh 3.2.1 ®­îc x¸c ®Þnh tõ mçi rµng buéc t­¬ng øng ë ph­¬ng tr×nh, vµ hai trôc thÓ hiÖn hai ®iÒu kiÖn kh«ng ©m cña hai biÕn quyÕt ®Þnh x1 vµ x2. Mòi tªn trªn mçi ®­êng chØ ra nöa mÆt ph¼ng mµ trªn ®ã tÊt c¶ c¸c ®iÓm tháa m·n rµng buéc nµy. MiÒn nghiÖm do ®ã lµ miÒn giao cña tÊt c¶ c¸c nöa mÆt ph¼ng kh¶ thi vµ tÊt c¶ c¸c ®iÓm trªn miÒn nghiÖm tháa m·n ®ång thêi tÊt c¶ c¸c rµng buéc. Mçi ®iÓm thuéc miÒn nµy lµ mét nghiÖm kh¶ thi cho m« h×nh tèi ­u. Do gi¸ trÞ cña lîi nhuËn thùc tèi ®a lµ ch­a biÕt, mét qu¸ tr×nh thö sai cÇn ®­îc tiÕn hµnh. §Çu tiªn, ta vÏ mét ®­êng th¼ng x0 = 0 ®Ó cho hµm môc tiªu t­¬ng øng ®i qua gèc täa ®é. VÒ mÆt to¸n häc mµ nãi, tÊt c¶ c¸c ®iÓm (x1, x2) n»m trªn ®­êng 5x1 - x2 = 0 sÏ cho gi¸ trÞ tæng lîi nhuËn thËt b»ng 0, TÊt nhiªn, ta chØ quan t©m ®Õn nh÷ng ®iÓm n»m trªn vïng kÎ chÐo thÓ hiÖn miÒn nghiÖm. §Ó biÕt ®­îc tæng lîi nhuËn thùc cã thÓ ®­îc c¶i thiÖn hay kh«ng, ®­êng th¼ng hµm môc tiªu cã thÓ ®­îc dÞch chuyÓn tiÕn hoÆc lïi song song víi ®­êng cò ®Ó xem gi¸ trÞ hµm môc tiªu biÕn ®æi ra sao. §­êng th¼ng thÓ hiÖn hµm môc tiªu ®­îc dÞch chuyÓn sang tr¸i vµ c¸c gi¸ trÞ x1, x2 chän bÊt kú trªn ®­êng nµy ®­îc dïng ®Ó tÝnh to¸n gi¸ trÞ hµm môc tiªu. Ta cã thÓ thÊy r»ng gi¸ trÞ x0 t­¬ng øng víi bÊt cø ®­êng th¼ng nµo dÞch chuyÓn sang tr¸i ®­êng 5x1 - x2 =0 vµ song song víi nã ®Òu cã gi¸ trÞ ©m. Khi cµng dÞch chuyÓn ®­êng nµy sang tr¸i, gi¸ trÞ x0 cµng trë nªn ©m nhiÒu h¬n. §iÒu nµy chØ ra r»ng sù t×m kiÕm nghiÖm ®­îc tiÕn hµnh sai h­íng v× bµi to¸n ®Æt ra lµ lo¹i tèi ®a hãa; gi¸ trÞ x0 cµng lín cµng tèt. Nh­ vËy, h­íng t×m kiÕm nªn ®­îc thay ®æi b»ng c¸ch chuyÓn dÞch ®­êng th¼ng hµm môc tiªu vÒ bªn ph¶i cña ®­êng 5x1 - x2 =0, Ngay lËp tøc, gi¸ trÞ cña lîi nhuËn thùc chuyÓn sang d­¬ng vµ t¨ng liªn tôc khi ®­êng nµy ®­îc chuyÓn xa vÒ phÝa ph¶i. Tuy nhiªn, ®­êng nµy kh«ng thÓ dÞch chuyÓn sang ph¶i mét c¸ch v« h¹n kÓ c¶ khi nã liªn tôc lµm t¨ng lîi nhuËn thùc. Nh­ cã thÓ nhËn thÊy, sau khi v­ît qua ®iÓm C, ®­êng th¼ng hµm môc tiªu kh«ng chøa mét nghiÖm kh¶ thi nµo. Trong vÝ dô nµy, cã thÓ kÕt luËn r»ng, cÆp x1, x2 t¹i ®iÓm C, (6,2), lµ nghiÖm tèi ­u cña bµi to¸n. Lîi nhuËn thùc cã thÓ ®¹t ®­îc cña nhµ xuÊt lµ 5 (6) - 1 (2) = 28 ngh×n ®« la Ph­¬ng ph¸p ®å gi¶i chØ ¸p dông ®­îc cho nh÷ng bµi to¸n cã chøa hai biÕn quyÕt ®Þnh. §èi víi c¸c bµi to¸n cã nhiÒu h¬n hai biÕn quyÕt ®Þnh, h×nh d¹ng cña c¸c hµm môc tiªu vµ c¸c ph­¬ng tr×nh rµng buéc cã d¹ng c¸c mÆt ®a diÖn låi trong kh«ng gian n-chiÒu. 3.2.2. C¸c ®iÓm cùc trÞ (®iÓm gãc) kh¶ thi Trong vÝ dô minh häa võa råi, nghiÖm tèi ­u cña bµi to¸n QHTT t×m ®­îc khi sö dông ph­¬ng ph¸p ®å n»m t¹i mét ®iÓm gãc cña miÒn nghiÖm (gäi lµ ®iÓm kh¶ thi cùc trÞ). CÇn nhÊn m¹nh r»ng, kh«ng cã g× lµ ®Æc biÖt 83 vµ trïng hîp vÒ vÝ dô nµy vµ dÉn ®Õn mét kÕt qu¶ nh­ vËy. Thùc tÕ, ®èi víi tÊt c¶ c¸c bµi to¸n QHTT nghiÖm tèi ­u lu«n r¬i vµo biªn cña miÒn nghiÖm. C¸c ®iÓm cùc trÞ kh¶ thi trong mét bµi to¸n QHTT cã ba tÝnh chÊt quan träng. ý nghÜa cña nã ®èi víi kü thuËt gi¶i ®¹i sè sÏ ®­îc m« t¶ ë phÇn sau. Nh÷ng tÝnh chÊt sau ®©y ®­îc ®­a ra kh«ng kÌm víi chøng minh to¸n häc. Nh÷ng chøng minh nµy cã thÓ t×m thÊy ë c¸c s¸ch QHTT hay s¸ch quy ho¹ch to¸n (Dantzig, 1963, Bradley, Hax vµ Magrati, 1977; vµ Taha, 1987). TÝnh chÊt 1a: NÕu m« h×nh QHTT chØ cã duy nhÊt mét nghiÖm tèi ­u, nghiÖm nµy ph¶i n»m t¹i mét ®iÓm cùc trÞ kh¶ thi. TÝnh chÊt 1b. NÕu bµi to¸n cã nhiÒu nghiÖm tèi ­u, Ýt nhÊt hai trong sè c¸c nghiÖm tèi ­u n»m t¹i hai ®iÓm cùc trÞ kh¶ thi c¹nh nhau. Nh­ ®· ®­îc minh ho¹ trong h­íng tiÕp cËn ®å gi¶i, mçi bµi to¸n chØ cã mét nghiÖm tèi ­u duy nhÊt, chóng ta lu«n cã thÓ n©ng lªn hay h¹ xuèng ®­êng hµm môc tiªu (hay mÆt ®a diÖn) cho ®Õn khi nã tiÕp xóc víi ®iÓm ®ã, ®iÓm tèi ­u, t¹i mét gãc cña miÒn nghiÖm. Cã thÓ t­ëng t­îng ra r»ng c¸c nghiÖm tèi ­u ®a nghiÖm x¶y ra khi ®­êng th¼ng hµm môc tiªu (hay mÆt ®a diÖn) song song víi mét trong sè c¸c biªn cña miÒn nghiÖm. §èi víi bµi to¸n hai chiÒu, nÕu ®a nghiÖm x¶y ra, hai ®iÓm cùc trÞ kh¶ thi tèi ­u n»m c¹nh nhau. §èi víi c¸c bµi to¸n nhiÒu chiÒu h¬n, cã nhiÒu h¬n hai ®iÓm cùc trÞ kh¶ thi tèi ­u n»m c¹nh nhau. ý nghÜa cña tÝnh chÊt nµy lµ, trong khi ®i t×m nghiÖm tèi ­u cho mét bµi to¸n QHTT, sù chó ý cã thÓ tËp trung vµo c¸c ®iÓm cùc trÞ kh¶ thi, chø kh«ng ph¶i lµ vïng bªn trong cña miÒn nghiÖm. 84 H×nh 3.2 Mét miÒn nghiÖm cña vÝ dô s¶n xuÊt – xö lÝ n­íc th¶i. TÝnh chÊt 2: ChØ cã mét sè h÷u h¹n c¸c ®iÓm kh¶ thi cùc trÞ. XÐt mét m« h×nh QHTT cã d¹ng chÝnh t¾c víi m ph­¬ng tr×nh vµ n biÕn quyÕt ®Þnh ch­a biÕt (n>m). §èi víi hÖ c¸c ph­¬ng tr×nh trªn, sè c¸c nghiÖm cã thÓ lµ nCm = n!(n-m)! vµ lµ h÷u h¹n. Tuy nhiªn, sè nghiÖm nµy cung cÊp giíi h¹n trªn cña sè c¸c ®iÓm kh¶ thi cùc trÞ bëi v× rÊt nhiÒu trong sè c¸c nghiÖm nµy lµ kh«ng kh¶ thi hay kh«ng tån t¹i. TÝnh chÊt nµy cã thÓ gîi ý r»ng nghiÖm tèi ­u cã thÓ thu ®­îc b»ng c¸ch liÖt kª vµ xem xÐt tÊt c¶ c¸c ®iÓm cùc trÞ kh¶ thi. Tuy nhiªn, ®iÒu nµy th­êng lµ kh«ng kh¶ thi v× sè c¸c ®iÓm kh¶ thi cã thÓ rÊt lín ®Ó cã thÓ liÖt kª vµ xem xÐt mét c¸ch hiÖu qu¶. H¬n thÕ n÷a, nghiÖm tèi ­u kh«ng thÓ x¸c ®Þnh ®­îc tr­íc khi tÊt c¶ c¸c ®iÓm cùc trÞ kh¶ thi ®­îc liÖt kª vµ xem xÐt. TÝnh chÊt 3: NÕu mét ®iÓm cùc trÞ kh¶ thi tèt h¬n (®¸nh gi¸ víi x0) tÊt c¶ c¸c ®iÓm kh¶ thi bªn c¹nh nã th× nã còng tèt h¬n tÊt c¶ c¸c ®iÓm cùc trÞ kh¶ thi cßn l¹i (cã nghÜa lµ nã lµ mét ®iÓm tèi ­u toµn côc.) Tõ tÝnh chÊt nµy ta kh«ng ph¶i ®i liÖt kª vµ xem xÐt tÊt c¶ c¸c ®iÓm cùc trÞ kh¶ thi ®Ó t×m ®­îc nghiÖm tèi ­u cña bµi to¸n. Thay vµo ®ã, vÞ trÝ cña mét ®iÓm cùc trÞ kh¶ thi ®ang xem xÐt cã thÓ ®­îc kh¼ng ®Þnh ®¬n gi¶n b»ng viÖc so s¸nh nã víi c¸c ®iÓm c¹nh nã. NÕu tÝnh chÊt 3 ®­îc tháa m·n, 85 ®iÓm cùc trÞ kh¶ thi mµ ta ®ang xÐt lµ nghiÖm tèi ­u toµn côc cña bµi to¸n QHTT. Nªn nhÊn m¹nh r»ng yªu cÇu c¬ b¶n cho tÝnh chÊt nµy tån t¹i lµ miÒn nghiÖm lµ låi. NÕu kh«ng, nghiÖm tèi ­u thu ®­îc sÏ kh«ng ®­îc ®¶m b¶o lµ nghiÖm tèi ­u toµn côc mµ chØ lµ nghiÖm tèi ­u côc bé. HiÖn t­îng nµy ®Æc biÖt th­êng xuyªn x¶y ra trong c¸c bµi to¸n quy hoach phi tuyÕt tÝnh. May m¾n lµ miÒn nghiÖm cña c¸c bµi to¸n QHTT hÇu nh­ lµ lu«n lu«n låi. 3.2.3. ThuËt gi¶i cho c¸c bµi to¸n quy ho¹ch tuyÕn tÝnh ë môc nµy ba tÝnh chÊt quan träng cña ®iÓm cùc trÞ kh¶ thi th¶o luËn tr­íc ®©y sÏ ®­îc øng dông vµo mét bµi to¸n QHTT vµ mét thuËt gi¶i sÏ ®­îc thiÕt kÕ ®Ó gi¶i bµi to¸n QHTT nµy. Chóng ta quay l¹i bµi to¸n s¶n xuÊt, xö lÝ chÊt th¶i tr­íc ®©y. Nh­ ®­îc m« t¶ ë h×nh 3.2.1, m« h×nh QHTT cã bèn ®iÓm cùc trÞ kh¶ thi. §Çu tiªn, ta ph¶i x¸c ®Þnh ®iÓm xuÊt ph¸t cho viÖc t×m kiÕm nghiÖm tèi ­u. HiÓn nhiªn lµ nÕu ®iÓm xuÊt ph¸t gÇn víi ®iÓm tèi ­u, ta cã thÓ hy väng viÖc t×m kiÕm nghiÖm sÏ nhanh h¬n. Tuy nhiªn, nh×n chung lµ rÊt khã cã thÓ x¸c ®Þnh ngay tõ ®Çu mét ®iÓm xuÊt ph¸t tèt, ®Æc biÖt lµ cho c¸c bµi to¸n nhiÒu chiÒu. Do vËy, sÏ lµ hîp lý nÕu b¾t ®Çu viÖc t×m kiÕm tõ ®iÓm ë gèc täa ®é (x1, x2) = (0,0) v× ®iÓm gèc lµ mét ®iÓm cùc trÞ kh¶ thi, chó ý r»ng trong c«ng viÖc t×m kiÕm nghiÖm tèi ­u, lu«n cÇn thiÕt b¾t ®Çu víi mét nghiÖm kh¶ thi. Khi ®· x¸c ®Þnh ®­îc ®iÓm xuÊt ph¸t cùc trÞ kh¶ thi, gi¸ trÞ cña hµm môc tiªu t­¬ng øng x0 sÏ ®­îc tÝnh ®Ó lµm c¬ së cho c¸c b­íc so s¸nh tiÕp theo. Trong tr­êng hîp nµy, t¹i ®iÓm (0,0), gi¸ trÞ x0 t­¬ng øng b»ng 0, B­íc tiÕp theo lµ t×m mét nghiÖm tèt h¬n b»ng c¸ch so s¸nh c¸c gi¸ trÞ cña c¸c hµm môc tiªu t¹i c¸c ®iÓm cùc trÞ kh¶ thi bªn c¹nh. Hai ®iÓm cùc trÞ kh¶ thi bªn c¹nh ®iÓm (0, 6) lµ B (2, 4) vµ D (5, 0) víi c¸c gi¸ trÞ t­¬ng øng cña hµm môc tiªu lÇn l­ît lµ 6 vµ 25. KÕt qu¶ nµy chØ ra r»ng sù dÞch chuyÓn tõ ®iÓm A ®Õn D ®¹t ®­îc sù c¶i thiÖt tèt h¬n so víi tõ A ®Õn B. Do vËy, ®iÓm D trë thµnh ®iÓm cùc trÞ kh¶ thi c¬ së. T¹i ®iÓm D, qu¸ tr×nh so s¸nh ®­îc lËp l¹i b»ng c¸ch x¸c ®Þnh c¸c ®iÓm cùc trÞ kh¶ thi n»m bªn c¹nh ®iÓm D. Trong tr­êng hîp nµy, hai ®iÓm A vµ C lµ hai ®iÓm tiÕp gi¸p. Tuy nhiªn tõ so s¸nh tr­íc ®©y, gi¸ trÞ hµm môc tiªu t¹i A kh«ng tèt h¬n gi¸ trÞ t¹i ®iÓm hiÖn t¹i D. Do vËy ®iÓm C lµ ®iÓm cùc trÞ kh¶ thi cÇn ®­îc so s¸nh víi ®iÓm D. T¹i ®iÓm C (6, 2) gi¸ trÞ x0 b»ng 5(6) - 1(2)=28. Do gi¸ trÞ nµy lín h¬n 25 t¹i ®iÓm D, ®iÓm cùc trÞ kh¶ thi c¬ së ®­îc thay b»ng ®iÓm C. T¹i ®iÓm cùc trÞ kh¶ thi c¬ së C, kh«ng cßn ®iÓm cùc trÞ kh¶ thi tiÕp gi¸p nµo ®Ó so s¸nh (®iÓm B ®· ®­îc so s¸nh vµ lo¹i bá bëi ®iÓm D trong b­íc tr­íc ®©y). Gi¸ trÞ cña x0 t¹i ®iÓm C lµ tèt h¬n so víi tÊt c¶ c¸c ®iÓm CTKT bªn c¹nh (®iÓm B vµ D). Tõ tÝnh chÊt thø ba cña c¸c ®iÓm CTKT th¶o luËn tr­íc ®©y, ta cã thÓ kÕt luËn r»ng nghiÖm 86 tèi ­u cña vÝ dô s¶n xuÊt, xö lÝ chÊt th¶i lµ s¶n xuÊt 6 ®¬n vÞ thµnh phÈm vµ ®æ tr­îc tiÕp hai ®¬n vÞ chÊt th¶i ra s«ng mµ kh«ng qua xö lÝ. §iÒu ®ã còng cã nghÜa lµ cã 2(6) - 2=10 ®¬n vÞ chÊt th¶i ®i qua nhµ m¸y xö lÝ. Gi¸ trÞ l·i rßng t­¬ng øng lµ 28 ngh×n ®« la. C¸c b­íc ®­îc m« t¶ trªn ®©y (sö dông 3 tÝnh chÊt cña c¸c ®iÓm CTKT ®Ó gi¶i mét m« h×nh QHTT) h×nh thµnh kh¸i niÖm vÒ mét thuËt gi¶ næi tiÕng ®­îc gäi lµ Ph­¬ng ph¸p ®¬n h×nh (Simplex method). Ph­¬ng ph¸p nµy lµ mét quy tr×nh tæng qu¸t ®Ó gi¶i c¸c bµi to¸n QHTT. Nã lµ mét ph­¬ng ph¸p rÊt hiÖu qu¶ ®· ®­îc ¸p dông ®Ó gi¶i c¸c bµi to¸n lín h¬n liªn quan ®Õn hµng tr¨m c¸c biÕn quyÕt ®Þnh vµ rµng buéc trªn m¸y tÝnh ®iÖn tö. C¸c ch­¬ng tr×nh m¸y tÝnh dùa trªn ph­¬ng ph¸p ®¬n h×nh cã mÆt réng r·i ®Ó sö dông. VÝ dô 3.2.2. Gi¶i b»ng ph­¬ng ph¸p ®¹i sè bµi to¸n s¶n xuÊt, xö lÝ chÊt th¶i cña vÝ dô 3.2.1. Lêi gi¶i. Hµm môc tiªu vµ c¸c rµng buéc cã thÓ ®­îc viÕt nh­ sau: Hµm môc tiªu: x0 - 5x1 + x2 + 0s1 + 0s2 + 0s3 = 0 Rµng buéc 1: 2x1 - x2 + s1 + 0s2 + 0s3 = 10 Rµng buéc 2: 0,4x1 +0,8x2 + 0s1 + s2 + 0s3 = 4 Rµng buéc 3: -2x1 + x2 + 0s1 + 0s2 + s3 = 0 B­íc ®Çu tiªn b¾t ®Çu víi ®iÓm CTKT (x1= 0 vµ x2 = 0) B­íc lÆp 1 B­íc lÆp b¾t ®Çu b»ng viÖc lùa chän hoÆc biÕn x1 hoÆc biÕn x2 nªn t¨ng gi¸ tõ gi¸ trÞ 0, Do x1 cã hÖ sè ©m lín nhÊt (-5) nªn nã sÏ cã t¸c ®éng lín nhÊt cho viÖc lµm t¨ng hµm môc tiªu. QuyÕt ®Þnh tiÕp theo lµ cÇn t¨ng x1 lªn bao nhiªu. CÇn nhí r»ng c¸c biÕn ¶o kh«ng bao giê cã gi¸ trÞ ©m. §Çu tiªn kiÓm tra rµng buéc 1 b»ng c¸ch t×m gi¸ trÞ x1 víi s1 = 0 vµ x2 = 0, 2 1 1 10 5 2 2 2 x s x     Sau ®ã thay x1 = 5 vµo c¸c rµng buéc cßn l¹i vµ t×m gi ¸trÞ c¸c biÕn ¶o. Rµng buéc 2: 0,4 (5) + 0,8 (0) + 0s1 + s2 + 0s3 = 4 s2 = 2 Rµng buéc 3: -2(5) + 0 + 0s1 + 0s2 + s3 = 0 s3 = 10 V× c¸c biÕn ¶o vÉn gi÷ gi¸ trÞ d­¬ng víi x1 = 5. Ta xÐt rµng buéc 2 vµ t×m gi¸ trÞ cña x1 víi x2 = 0 vµ s2 = 0, Rµng buéc 2: 0,4x1 + 0,8 (0) + 0s1 + 0 + s3 = 4 x1 = 10 B©y giê chóng ta ®i kiÓm tra rµng buéc 1 vµ 3 Rµng buéc 1: 2(10) - 0 + s1 + 0s2 + 0s3 = 10 s1 = -10 Rµng buéc 3: -2(10) + 0 + 0s1 + 0s2 + s3 = 0 s3 = 20 §èi víi rµng buéc 1, x1 = 10 lµ qu¸ lín v× biÕn ¶o s1 mang gi¸ trÞ ©m (s1 = -10). TiÕp theo, xÐt rµng buéc 2 vµ t×m gi¸ trÞ x1 víi x2 = 0 vµ s3 = 0, Rµng buéc 3: -2x1 + 0s1 + 0s2 + 0 = 0 x1 = 0 §iÒu nµy nãi lªn r»ng nã kh«ng di chuyÓn khái vÞ trÝ xuÊt ph¸t. 87 KÕt qu¶ cña sù ph©n t