1. Trang Chủ
  2. Môi trường
  3. Kỹ thuật và quản lý hệ thống nguồn nước ( Đại học Quốc gia Hà Nội ) - Chương 3

Kỹ thuật và quản lý hệ thống nguồn nước ( Đại học Quốc gia Hà Nội ) - 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: n Max (hoặc Min) x 0 ? ? c j x j j ?1 (3.1.1a) Với các biểu thức... CH¦¥NG 3 Quy ho¹ch tuyÕn tÝnh vµ nh÷ng

Thể loại Tài liệu miễn phí Môi trường

Số trang 53

Ngày tạo 8/29/2018 11:44:00 PM +00:00

Loại tệp PDF

Kích thước 1.08 M

Tên tệp

Tải Kỹ thuật và quản lý hệ thống nguồn nước ( Đại học ... (.pdf)

Xem mẫu

  1. 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: n Max (hoÆc Min) x 0   c j x j (3.1.1a) j 1 Víi c¸c biÓu thøc rµng buéc: n a víi i = 1, 2, ... n (3.1.1b) x j  bi ij j 1 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 + a12x 2 + ... + a1nxn  b1 a12x2 + a22x2 + ... + a2nxn  b2 76
  2. 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 = CTx (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 77
  3. 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: 78
  4. 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. Gi¶ thiÕt vÒ tÝnh tû lÖ. Gi¶ thiÕt nµy cã nghÜa lµ sù ®ãng gãp 1. 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. Gi¶ thiÕt vÒ tÝnh céng hîp. Gi¶ thiÕt nµy cã nghÜa lµ, t¹i mét 2. cÊp ®é ho¹t ®éng cho tr­íc (x1, x 2, ... 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. Gi¶ thiÕt vÒ tÝnh kh¶ chia. C¸c ®¬n vÞ cña c¸c ho¹t ®éng cã 3. 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. Gi¶ thiÕt vÒ tÝnh tÊt ®Þnh. TÊt c¶ th«ng sè cña m« h×nh ®­îc 4. 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. 79
  5. 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µ: n Max (hoÆc Min) x0   c j x j (3.1.4a) j 1 n  ai x j  bi , víi i  1, 2,..., m (3.1.4b) j 1 x j  0. víi j  1, 2,..., n 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µ: n cjxj Max x0 = (3.1.5a) j 1 Rµng buéc bëi: 80
  6. n  aij x j  bi , i  1, 2,..., m (3.1.5b) j 1 x j  0, j  1, 2,..., n 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: 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 1. cña nã, cã nghÜa lµ: Max f(x) = Min {-f(x)} C¸c rµng buéc cã d¹ng  cã thÓ chuyÓn ®æi sang d¹ng  b»ng c¸ch 2. 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 NÕu mét biÕn quyÕt ®Þnh x kh«ng cã rµng buéc vÒ dÊu (cã thÓ 5. 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 81
  7. 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µ (x1, x 2) nãi, tÊt c¶ c¸c ®iÓm 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 82
  8. 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. 83
  9. 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, 84
  10. ®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 85
  11. 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: x0 - 5x1 + x2 + 0s1 + 0s2 + 0s3 = 0 Hµm môc tiªu: 2x1 - x2 + s1 + 0s2 + 0s3 = 10 Rµng buéc 1: 0,4x1 +0,8x2 + 0s1 + s2 + 0s3 = 4 Rµng buéc 2: -2x1 + x2 + 0s1 + 0s2 + s3 = 0 Rµng buéc 3: 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, x2 s1 10 x1    5 2 2 2 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. 0,4 (5) + 0,8 (0) + 0s1 + s2 + 0s3 = 4 Rµng buéc 2: s2 = 2 -2(5) + 0 + 0s1 + 0s2 + s3 = 0 Rµng buéc 3: 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, 0,4x1 + 0,8 (0) + 0s1 + 0 + s3 = 4 Rµng buéc 2: x1 = 10 B©y giê chóng ta ®i kiÓm tra rµng buéc 1 vµ 3 2(10) - 0 + s1 + 0s2 + 0s3 = 10 Rµng buéc 1: s1 = -10 -2(10) + 0 + 0s1 + 0s2 + s3 = 0 Rµng buéc 3: 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, -2x1 + 0s1 + 0s2 + 0 = 0 Rµng buéc 3: 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. 86
  12. KÕt qu¶ cña sù ph©n tÝch trªn cho ta thÊy gi¸ trÞ lín nhÊt cña x1 cã thÓ t¨ng ®­îc lµ x1 = 5, víi x2 = 0, s2 = 2, s3 = 10, Nh×n l¹i h×nh 3.2.2, ®iÓm nµy chÝnh lµ ®iÓm D. Gi¸ trÞ hµm môc tiªu x0 t­¬ng øng víi nghiÖm kh¶ thi t¹i ®iÓm D lµ: x0 - 5(5) + 0 + 0s1 + 0s2 + 0s3 = 0 x0 = 25 TiÕp ®Õn, x2 s1 x1  5   2 2 ®­îc thay thÕ vµo hµm môc tiªu vµ c¸c rµng buéc. x2 s1 x0  5(5   x2  0 s1  0 s2  0 s3  0  22 Hµm môc tiªu: 3 5 x0  x2  s1  0s2  0s3  25 2 2 1 1 x1  x2  s1  0 s2  0 s3  5 2 2 Rµng buéc 1: xs 0, 4(5  2  1 )  0,8 x2  0 s1  s2  0 s3  4 Rµng buéc 2: 22 0 x1  s2  0.2 s1  s2  0s3  2 x2 s1 )  x2  0 s1  0 s2  s3  0 2(5   2 2 Rµng buéc 3: 0 x1  0 x2  s1  0 s2  s3  10 B ­íc lÆp 2. B­íc lÆp thø 2 nµy b¾t ®Çu b»ng viÖc ®Þnh nghÜa xem biÕn nµo nªn ®­îc t¨ng lªn tõ gi¸ trÞ 0, Hµm môc tiªu tõ trªn cã d¹ng: 3 5 x0  x2  s1  0 s2  0 s3  25 2 2 HÖ sè ©m lín nhÊt lµ -3/2 cña x2 . Do ®ã x2 nªn t¨ng tõ 0 ®Ó lµm t¨ng gi¸ trÞ hµm môc tiªu. C©u hái tiÕp theo lµ cÇn t¨ng x2 bao nhiªu. x2 = 2 x1 -10 NÕu x1 vµ x2 >0 th× s1 =0 Rµng buéc 1: x2 NÕu x1 vµ x2 >0 th× s 2 =0 = 2 + 0,2 s1 - s 2 Rµng buéc 2: x2 =2 0 x1 + 0 x2 + 0 +0 s2 + s3 = 10, do ®ã Rµng buéc 3: s3 = 10 Thay x2 =2 tõ rµng buéc 2 vµo rµng buéc 1, x2 = 2 x1 -10, ta cã x1 =6. §èi víi hµm môc tiªu ta thay x2  2 vµo, cã: 3 5 x0  (2  0, 2 s1  s2 )  s1  0 s2  0 s3  25 2 2 3 5 x0  3  0, 3s1  s2  s1  0 s2  0 s3  25 2 2 3 x0  2, 2 s1  s2  0 s3  28 2 x0  0 x1  0 x2  2, 2 s1  1, 5s2  0 s3  25 87
  13. C¶ x1 vµ x2 cã hÖ sè 0, do vËy kh«ng thÓ thay ®æi gi¸ trÞ x1 vµ x2 thªm n÷a ®Ó t¨ng gi¸ trÞ hµm môc tiªu. 3.2.4. ThuËt to¸n c¬ b¶n ®Ó gi¶i c¸c bµi to¸n QHTT Nh­ ®­îc minh häa ë vÝ dô trªn, ba b­íc chÝnh liªn quan ®Õn gi¶i mét bµi to¸n QHTT: B­íc khëi ®éng: B¾t ®Çu víi mét nghiÖm cùc trÞ kh¶ thi 1. B­íc lÆp: DÞch chuyÓn tíi ®iÓm CTKT bªn c¹nh 2. LuËt dõng: Dïng c¸c b­íc lËp khi ®iÓm CTKT hiÖn t¹i lµ tèt h¬n 3. so víi c¸c ®iÓm bªn c¹nh nã. 3.3. Ph­¬ng ph¸p ®¬n h×nh 3.3.1. C¸c kh¸i niÖm ®¹i sè vµ thiÕt lËp c¬ b¶n Nh­ ®· ®­îc minh ho¹ tõ tr­íc, m« h×nh QHTT sö dông ph­¬ng ph¸p ®å gi¶i còng nh­ h­íng tiÕp cËn t×m kiÕm cã thÓ ®­îc thùc hiÖn dÔ dµng khi bµi to¸n chØ bao gåm hai biÕn quyÕt ®Þnh. Môc ®Ých cña vÝ dô trªn chØ lµ ®Ó minh ho¹ c¸c kh¸i niÖm h×nh häc cña ph­¬ng ph¸p ®¬n h×nh vµ thuËt to¸n c¬ b¶n cña nã. §Ó gi¶i c¸c bµi to¸n cã quy m« lín h¬n, xÐt vÒ sè l­îng c¸c biÕn quyÕt ®Þnh vµ c¸c rµng buéc, c¸c ph­¬ng ph¸p ®­îc ®Ò cËp tr­íc ®©y kh«ng thÓ ¸p dông ®­îc. H¬n n÷a, ®Ó thùc hiÖn c¸c thuËt to¸n gi¶i trªn m¸y tÝnh, c¸c vÊn ®Ò ph¶i ®­îc diÔn gi¶i ®¹i sè. 88
  14. H×nh 3.2.2 Minh häa thuËt gi¶i ®¹i sè bµi to¸n QHTT. Trong viÖc gi¶i bµi to¸n sö dông c¸c quy tr×nh ®¹i sè th× viÖc dïng c¸c ph­¬ng tr×nh nh×n chung thuËn tiÖn h¬n so víi dïng bÊt ph­¬ng tr×nh. Do ®ã, ®Ó gi¶i mét m« h×nh QHTT sö dông ph­¬ng ph¸p ®¹i sè ®¬n h×nh, ®Çu tiªn, m« h×nh ph¶i chuyÓn thµnh d¹ng chÝnh t¾c (nh­ trong vÝ dô 3.1.2). Bµi to¸n QHTT bao gåm 5 biÕn quyÕt ®Þnh (x1, x2, s1, s2, s3) vµ 3 ph­¬ng tr×nh. Trong ®¹i sè tuyÕn tÝnh, hÖ ph­¬ng tr×nh ®­îc gäi lµ bÊt ®Þnh nÕu sè Èn lín h¬n sè ph­¬ng tr×nh. §èi víi c¸c bµi to¸n cã n Èn vµ m ph­¬ng tr×nh trong ®ã n > m th× kh«ng cã lêi gi¶i duy nhÊt. BiÖn ph¸p kh¶ thi cho viÖc gi¶i hÖ bÊt ®Þnh lµ ®Æt (n-m) biÕn b»ng 0 vµ gi¶i cho m Èn cßn l¹i. C¸c nghiÖm t×m ®­îc ®­îc gäi lµ c¸c nghiÖm c¬ së. VÒ mÆt lý thuyÕt, chóng ta sÏ cã tæng sè nghiÖm lµ nCm nghiÖm c¬ së cho bµi to¸n nÕu tÊt c¶ ®Òu tån t¹i. Cho vÝ dô ta ®ang xÐt, bµi to¸n cã nhiÒu nhÊt 5C3 = 5! / (3! 2!) = 10 nghiÖm c¬ së. VÒ mÆt h×nh häc, mçi nghiÖm c¬ së diÔn t¶ giao ®iÓm cña 2 ph­¬ng tr×nh rµng buéc, mét ®iÓm cùc trÞ, bao gåm c¶ ®iÒu kiÖn d­¬ng cña x1 vµ x2. VÝ dô chØ ra trong h×nh 3.2.1 cã 6 nghiÖm c¬ së. H¬n n÷a, trong sè 6 nghiÖm c¬ së tån t¹i, chØ cã 4 ®iÓm kh¶ thi. Nh÷ng ®iÓm nµy ®­îc diÔn t¶ bëi 4 ®iÓm cùc trÞ kh¶ thi. B©y giê chóng ta cïng kiÓm tra c¸c nghiÖm c¬ së liªn quan tíi 4 ®iÓm cùc trÞ kh¶ thi nh­ trong b¶ng 3.2.1. Mçi mét ®iÓm cùc trÞ kh¶ thi cã ®óng hai biÕn (trong 5 biÕn) ®­îc ®Æt b»ng 0, Mét sè 0 kh¸c liªn quan tíi c¸c ®iÓm cùc trÞ kh¶ thi A vµ B cã ®­îc tõ rµng buéc thø 3, trong ®ã c¸c hÖ sè bªn vÕ ph¶i cña nã b»ng 0, 89
  15. Trong bµi tËp võa råi, (n-m) biÕn quyÕt ®Þnh ®Æt b»ng 0 ®­îc gäi lµ c¸c biÕn kh«ng c¬ së trong khi m biÕn quyÕt ®Þnh cßn l¹i mµ c¸c gi¸ trÞ cña chóng t×m ®­îc b»ng c¸ch gi¶i hÖ ph­¬ng tr×nh gåm m ph­¬ng tr×nh vµ m Èn, ®­îc gäi lµ c¸c biÕn c¬ së. NghiÖm cña c¸c biÕn c¬ së lµ kh«ng ©m ®­îc gäi lµ nghiÖm c¬ së kh¶ thi vµ nã x¸c ®Þnh ®iÓm cùc trÞ kh¶ thi t­¬ng øng n»m trong miÒn nghiÖm. Do vËy, trong viÖc gi¶i ®¹i sè m« h×nh QHTT, chØ cÇn ®i xem xÐt tõng nghiÖm kh¶ thi c¬ së cña m« h×nh cã d¹ng QHTT chuÈn. 3.3.2. D¹ng ®¹i sè cña ph­¬ng ph¸p ®¬n h×nh Ph­¬ng ph¸p ®¬n h×nh gi¶i mét m« h×nh QHTT b»ng c¸ch lîi dông 3 tÝnh chÊt cña ®iÓm cùc trÞ kh¶ thi ®· ®­îc th¶o luËn tr­íc ®ã. ThuËt to¸n t×m kiÕm sù tèi ­u cña mét m« h×nh QHTT lu«n tu©n theo 2 ®iÒu kiÖn c¬ b¶n: (1) §iÒu kiÖn tèi ­u vµ (2) §iÒu kiÖn kh¶ thi. §iÒu kiÖn tèi ­u ®¶m b¶o r»ng kh«ng gÆp c¸c ®iÓm suy gi¶m (®èi víi ®iÓm nghiÖm ®ang xÐt). §iÒu kiÖn kh¶ thi ®¶m b¶o r»ng, b¾t ®Çu víi mét nghiÖm kh¶ thi c¬ së, chØ cã c¸c nghiÖm kh¶ thi c¬ së ®­îc xem xÐt trong suèt qu¸ tr×nh tÝnh to¸n. B ¶ng 3.3.1 C ¸c ®iÓm cùc trÞ kh¶ thi cña bµi to¸n s¶n xuÊt vµ xö lÝ chÊt th¶i ( x1 x2 s1 s2 s3) A (0, 0, 10, 4, 0) B (2, 4, 10, 0, 0) C (6, 2, 0, 0, 10) D (5, 0, 0, 2, 10) B¶ng 3.3.2 B¶ng ®¬n h×nh cña bµi to¸n s¶n xuÊt vµ xö lÝ chÊt th¶i C ¬ së x0 x1 x2 s1 s2 s3 N ghiÖm x0 1 -5 1 0 0 0 0 s1 0 2 -1 1 0 0 10 s2 0 0,4 0,8 0 1 0 4 s3 0 -2 1 0 0 1 0 §Ó gi¶i ®¹i sè m« h×nh QHTT, d¹ng chÝnh t¾c cña m« h×nh cã thÓ ®­îc ®Æt vµo d¹ng b¶ng nh­ trong b¶ng 3.3.2, trong ®ã hµm môc tiªu ®­îc diÔn t¶ nh­ sau: 90
  16. x0 - 5x1 + x2 - 0s1 - 0 s2 -0s3 = 0 B©y giê bµi to¸n QHTT cã thÓ ®­îc gi¶i theo 3 b­íc cña thuËt gi¶i ®· ®­îc tr×nh bÇy trong Môc 3.2.4. B­íc khëi ®éng- ph­¬ng ph¸p ®¬n h×nh b¾t ®Çu tõ mét nghiÖm kh¶ thi c¬ së bÊt kú. C¸c biÕn ¶o cho ta mét nghiÖm xuÊt ph¸t kh¶ thi bëi v× tõ b¶ng 3.3.2 ta thÊy (a) c¸c hÖ sè rµng buéc cña chóng t¹o nªn mét ma trËn ®¬n vÞ; vµ (b) toµn bé c¸c hÖ sè vÕ ph¶i ®Òu kh«ng ©m (tÝnh chÊt cña d¹ng chÝnh t¾c). B­íc lÆp- b­íc nµy liªn quan ®Õn hai quy tr×nh tÝnh to¸n dùa trªn ®iÒu kiÖn tèi ­u vµ ®iÒu kiÖn kh¶ thi. Quy tr×nh thø nhÊt x¸c ®Þnh ra mét biÕn kh¶ thi c¬ së míi lµm cho gi¸ trÞ hµm môc tiªu ®­îc c¶i thiÖn. Ph­¬ng ph¸p ®¬n h×nh thùc hiÖn ®iÒu nµy b»ng c¸ch lùa chän mét trong sè c¸c biÕn kh«ng c¬ së hiÖn thêi ®Ó t¨ng lªn trªn gi¸ trÞ 0, biÕt tr­íc r»ng hÖ sè cña nã trong hµm môc tiªu cã kh¶ n¨ng c¶i thiÖn gi¸ trÞ hiÖn thêi cña x0, Do mét ®iÓm cùc trÞ kh¶ thi trong m« h×nh QHTT ph¶i cã (n-m) c¸c biÕn kh«ng c¬ së b»ng 0, mét biÕn c¬ së hiÖn thêi ph¶i ®­îc biÕn ®æi thµnh kh«ng c¬ së, biÕt tr­íc nghiÖm lµ kh¶ thi. BiÕn kh«ng c¬ së hiÖn thêi bÞ biÕn ®æi thµnh c¬ së ®­îc gäi lµ biÕn vµo trong khi biÕn c¬ së hiÖn thêi bÞ biÕn ®æi thµnh kh«ng c¬ së ®­îc gäi lµ biÕn ra. §èi víi mét bµi to¸n tèi ®a ho¸, biÕn vµo ®­îc lùa chän dùa trªn ®iÒu kiÖn tèi ­u, v× biÕn kh«ng c¬ së cã hÖ sè ©m lín nhÊt trong ph­¬ng tr×nh x0 ë b¶ng ®¬n h×nh. §iÒu nµy lµ t­¬ng ®­¬ng víi viÖc lùa chän mét biÕn víi hÖ sè d­¬ng lín nhÊt trong hµm môc tiªu gèc bëi v× ®é lín cña hÖ sè hµm môc tiªu diÔn t¶ tèc ®é thay ®æi cña hµm môc tiªu do thay ®æi mét ®¬n vÞ gi¸ trÞ cña biÕn quyÕt ®Þnh. HÖ sè cã gi¸ trÞ ©m lín nhÊt ®­îc chän bëi v× nã cã tiÒm n¨ng lín nhÊt trong viÖc c¶i thiÖn gi¸ trÞ hµm môc tiªu. MÆt kh¸c, viÖc lùa chän biÕn vµo cho bµi to¸n cùc tiÓu ho¸ tu©n theo quy luËt ng­îc l¹i. §ã lµ, lùa chän biÕn kh«ng c¬ së víi hÖ sè d­¬ng lín nhÊt trong hµng cña hµm môc tiªu trong b¶ng ®¬n h×nh nh­ lµ biÕn vµo. Khi mµ biÕn vµo ®· ®­îc x¸c ®Þnh, mét trong sè c¸c biÕn c¬ së hiÖn thêi ph¶i ®­îc chän ®Ó trë thµnh biÕn kh«ng c¬ së. Sù lùa chän biÕn ®i ra ®­îc thùc hiÖn b»ng ®iÒu kiÖn kh¶ thi ®Ó ch¾c ch¾n r»ng chØ cã c¸c nghiÖm kh¶ thi ®­îc liÖt kÔ xem xÐt trong suèt c¸c b­íc lÆp. BiÕn ra ®­îc lùa chän sö dông tiªu chuÈn sau: bi víi mäi aik >0 i  aik víi aik lµ c¸c hÖ sè cña c¸c rµng buéc liªn quan ®Õn c¸c biÕn vµo xk BiÕn c¬ së hiÖn thêi n»m trong hµng hµng cã θ = min (i) ®­îc lùa chän nh­ lµ biÕn ra. VÝ dô 3.3.1. Dùa trªn b¶ng 3.3.1. lùa chän biÕn vµo, biÕn ra cho b­íc lÆp ®Çu tiªn. 91
  17. Lêi gi¶i. Xem xÐt b¶ng ®¬n h×nh 3.3.2, biÕn quyÕt ®Þnh x1 cã thÓ ®­îc lùa chän nh­ lµ biÕn vµo. H­íng liªn quan tíi biÕn vµo chØ ra h­íng mµ theo ®ã nghiÖm tèt h¬n cã thÓ t×m ®­îc. Xem h×nh 3.2.1, nã diÔn t¶ sù di chuyÓn tõ nghiÖm kh¶ thi c¬ së hiÖn thêi t¹i ®iÓm A däc theo chiÒu d­¬ng cña trôc x1. Di chuyÓn däc theo chiÒu d­¬ng cña trôc x1, cã thÓ t×m thÊy hai ®iÓm cùc trÞ D (5,0) vµ E (10,0). Thùc tÕ, 5 vµ 10 lµ giao ®iÓm cña hai ph­¬ng tr×nh rµng buéc thø nhÊt vµ thø hai víi trôc x1 d­¬ng. h×nh 3.2.1. còng chØ ra r»ng ®iÓm E(10,0) lµ kh«ng kh¶ thi cho bµi to¸n. Do vËy, tõ ®iÒu nµy thÊy r»ng di chuyÓn däc theo chiÒu d­¬ng cña trôc x1 tõ ®iÓm A chØ cã thÓ tíi ®iÓm D mµ kh«ng ph¸ ho¹i c¸c ®iÒu kiÖn kh¶ thi. C¸c giao ®iÓm cña c¸c ph­¬ng tr×nh rµng buéc víi trôc chØ ra h­íng t×m kiÕm cã thÓ thu ®­îc tõ b¶ng ®¬n h×nh b»ng c¸ch tÝnh tû sè cña c¸c phÇn tö trong cét nghiÖm víi c¸c phÇn tö rµng buéc n»m trong cét t­¬ng øng víi biÕn vµo. Xem xÐt vÝ dô ®­îc minh häa trong b¶ng 3.3.2, hai cét ®­îc sö dông ®Ó tÝnh to¸n giao ®iÓm ®­îc chØ ra bªn d­íi trong b¶ng 3.3.3 vµ theo: b1 10 1   5 a11 2 b2 4 2    10 a21 0, 4 Tû sè nhá nhÊt lµ  = min (1, 2) = min (5,10) = 5 Chó ý r»ng tû sè cho rµng buéc cuèi cïng kh«ng ®­îc x¸c ®Þnh bëi v× hÖ sè -2 cña cét x1 chØ ra h­íng t×m kiÕm theo chiÒu ©m trªn trôc x1, nã kh«ng kh¶ thi bëi v× c¸c biÕn quyÕt ®Þnh yªu cÇu kh«ng ©m. So s¸nh c¸c gi¸ trÞ cña c¸c giao ®iÓm d­¬ng, biÕn c¬ së cã liªn quan tíi gi¸ trÞ giao ®iÓm nhá nhÊt, ®ã lµ min(5,10) =5, lµ s1. s1 nµy sÏ ®­îc chän nh­ lµ biÕn ra vµ trë thµnh biÕn kh«ng c¬ së ®Ó cho ®iÒu kiÖn kh¶ thi ®­îc tháa m·n. Cho môc ®Ých th¶o luËn, nÕu s2 ®­îc chän lµ biÕn ra, sù quyÕt ®Þnh sÏ dÉn chóng ta ®Õn ®iÓm E n»m bªn ngoµi miÒn nghiÖm vµ nghiÖm trë nªn kh«ng kh¶ thi. Khi mµ biÕn vµo ®· ®­îc lùa chän dùa trªn ®iÒu kiÖn tèi ­u vµ biÕn ra ®­îc lùa chän theo ®iÒu kiÖn kh¶ thi, tr¹ng th¸i cña c¸c biÕn trong danh s¸ch biÕn c¬ së B¶ng 3.3.3 TÝnh to¸n gi¸ trÞ cña  cho b­íc lÆp 1 TT c¸c rµng buéc x1 N ghiÖm  1 2 10 5 2 0,4 4 10 3 -2 0 - vµ kh«ng c¬ së ph¶i ®­îc cËp nhÊt. Sö dông danh s¸ch c¸c biÕn míi, c¸c tÝnh to¸n ®­a ra mét b¶ng ®¬n h×nh míi. Trong tÝnh to¸n, chØ ra trong b¶ng 3.3.2, nªn chó ý r»ng c¸c phÇn tö trong mçi cét d­íi tõng biÕn c¬ së hiÖn thêi cã gi¸ trÞ b»ng 1 t¹i c¸c ®iÓm giao cña hµng chøa biÕn ra vµ toµn bé c¸c phÇn tö kh¸c ®Òu b»ng 0, C¸c biÕn ®æi ®¹i sè sau ®©y ®­îc thùc hiÖn ®Ó tháa m·n yªu cÇu nµy. C¸c gi¸ trÞ cña c¸c phÇn tö trong b¶ng ®¬n h×nh liªn quan tíi c¸c biÕn c¬ së vµ kh«ng c¬ së míi cã thÓ ®­îc tÝnh to¸n theo c¸c biÕn ®æi hµng (hay ph­¬ng ph¸p gi¶i triÖt tiªu Gauss-Jordan). Hµng rµng buéc cã liªn quan tíi biÕn ra ®­îc gäi lµ ph­¬ng tr×nh chÝnh vµ lµm c¬ së cho biÕn ®æi hµng nµy. C¸c phÇn tö n»m t¹i ®iÓm giao gi÷a cét ®i vµo vµ hµng chÝnh ®­îc gäi lµ phÇn tö chÝnh. Ph­¬ng tr×nh chÝnh vµ phÇn tö chÝnh ®ãng vai trß trung t©m trong tÝnh to¸n. Trong biÕn ®æi hµng, môc tiªu lµ biÕn ®æi b¶ng sang d¹ng 92
  18. cã c¸c phÇn tö chÝnh b»ng mét vµ c¸c phÇn tö kh¸c b»ng kh«ng t¹i bÊt kú ®©u trong cét liªn quan tíi biÕn c¬ së míi. VÝ dô 3.3.2. Xem b¶ng 3.3.2. thùc hiÖn phÐp biÕn ®æi chÝnh ®Ó cËp nhËt b¶ng ®¬n h×nh sau khi x1 vµ s1 ®­îc lùa chän t­¬ng øng lµ biÕn vµo vµ biÕn ra. Lêi gi¶i. BiÕt r»ng x1 lµ biÕn vµo vµ s1 lµ biÕn ra, phÇn tö chÝnh trong b¶ng 3.3.4 lµ 2, nã ®­îc khoanh trßn. Hµng t­¬ng øng víi ®iÓm chÝnh nµy lµ hµng chÝnh. BiÕn ®æi chÝnh b»ng ph­¬ng ph¸p triÖt tiªu Gauss-Jordan, xem b¶ng 3.3.4, bao gåm 2 b­íc sau: Chia toµn bé c¸c phÇn tö trong ph­¬ng tr×nh chÝnh liªn quan tíi s2 bëi gi¸ trÞ cña phÇn tö chÝnh. ¸p dông c¸c phÐp nh©n thÝch hîp vµo hµng chÝnh võa ®­îc söa ®æi ë b­íc (1) vµ c¸c hµng kh¸c trong b¶ng nµy (xem b¶ng 3.3.4) sao cho toµn bé c¸c phÇn tö kh¸c víi phÇn tö chÝnh trong cét ®i vµo cã gi¸ trÞ b»ng kh«ng. B¶ng ®¬n h×nh míi thu ®­îc sau c¸c biÕn ®æi trªn thÓ hiÖn trong B¶ng 3.3.5 trong ®ã danh s¸ch thµnh viªn ®­îc cËp nhËt, s1 ®­îc thay thÕ bëi x1. C¸c gi¸ trÞ trong cét nghiÖm liªn quan tíi ba rµng buéc lµ c¸c gi¸ trÞ t­¬ng øng víi c¸c biÕn ëc b¶n hiÖn thêi. Gi¸ trÞ trong cét nghiÖm ë hµng x0 lµ gi¸ trÞ cña hµm môc tiªu t¹i ®iÓm nghiÖm hiÖn thêi. Víi b¶ng ®¬n h×nh hiÖn thêi, nghiÖm míi lµ x1 = 5 vµ x2 = 0 (do tr¹ng th¸i kh«ng c¬ së cña nã) víi gi¸ gÞ hµm môc tiªu t­¬ng øng x0 = 25. C¸c gi¸ trÞ cña c¸c biÕn ¶o lµ kh«ng quan träng trong hoµn c¶nh hiÖn thêi v× chóng kh«ng cã ¶nh h­ëng tíi gi¸ trÞ cña hµm môc tiªu. B ¶ng 3.3.4 Minh ho¹ c¸c biÕn ®æi hµng x0 x1 x2 s1 s2 s3 NghiÖm BiÕn ®æi hµng 1 -5 1 0 0 0 0 (+)(x)(5) (÷)(2) 0 2 -1 1 0 0 10 0 0,4 0,8 0 1 0 4 ( +)(x)(-.4) 0 -2 1 0 0 1 0 (+)(x)(2) B¶ng 3.3.5 KÕt qu¶ cña b­íc lÆp 1 C¬ së x0 x1 X2 s1 s2 s3 NghiÖm x0 1 0 -1,5 2,5 0 0 25 s1 0 1 -0,5 0,5 0 0 5 s2 0 0 1 -0,2 1 0 2 s3 0 0 0 1 0 1 10 Trong tÝnh to¸n thùc tÕ, kh«ng cÇn tÝnh to¸n c¸c phÇn tö trong cét ch­a c¸c biÕn c¬ së. Thùc ra kh«ng ph¶i tÊt c¶ c¸c phÇn tö trong b¶ng cÇn tÝnh to¸n ë mçi b­íc lÆp. BiÕn ®èi hµng ®­îc m« t¶ ë phÇn trªn cã thÓ ®­îc söa ®æi lµm t¨ng tÝnh mÒm dÎo ®Ó cã thÓ tÝnh to¸n c¸c gi¸ trÞ cña bÊt kú phÇn tö nµo trong b¶ng. Gi¶ thiÕt r»ng trong bÊt kú vßng lÆp nµo cña ph­¬ng ph¸p ®¬n h×nh, phÇn tö aij ë hµng i cét j lµ phÇn tö chÝnh. Gi¸ trÞ cña ph©n tö t¹i giao cña hµng k cét l, akl, cã thÓ ®­îc t×nh to¸n theo: A’ kl = (akl . aij - akj . ail)/ aij (3.3.1) trong ®ã a ’ kl lµ gi¸ trÞ míi thay thª gi¸ trÞ cò akl trong b¶ng ®¬n h×nh tr­íc. Th«ng t×n cÇn ®­îc sö dông trong ph­¬ng tr×nh (3.3.1) ®­îc thÓ hiÖn trªn h×nh 3.3.1. 93
  19. Khi mét b¶ng ®¬n h×nh míi ®­îc t¹o ra, cÇn ph¶i xem xÐt xem nghiÖm tèi ­u ®· cã thÓ t×m ®­îc ch­a. §iÒu nµy ®­îc thùc hiÖn b»ng c¸ch kiÓm tra c¸c gi¸ trÞ cña c¸c biÕn kh«ng c¬ së hiÖn thêi trong hµng cña hµm môc tiªu trong b¶ng ®¬n h×nh. Sö dông lËp luËn gièng nh­ ®· sö dông ë b­íc lÆp thø nhÊt, chóng ra xem xem cã c¸c biÕn kh«ng c¬ së cßn l¹i nµo cã tiÒm n¨ng lµm t¨ng thªm gi¸ trÞ hiÖn thêi cña x0, §èi víi c¸c bµi to¸n tèi ®a ho¸, bÊt kú mét biÕn kh«ng c¬ së nµo liªn quan ®Õn mét hÖ sè ©m trong hµng x0 cña b¶ng ®¬n h×nh ®Òu cã thÓ lµ øng cö cho biÕn vµo trong vßng lÆp tiÕp sau. NÕu tr­êng hîp nµy x¶y ra, b¶ng ®¬n h×nh hiÖn thêi ®­îc tèi ­u ho¸ l¹i sö dông mét quy tr×nh gièng nh­ ®­îc m« t¶ ë trªn. NÕu tÊt c¶ c¸c hÖ sè môc tiªu ë hµng x0 cña b¶ng ®¬n h×nh lµ kh«ng ©m, nghiÖm tèi ­u ®· ®¹t ®­îc bëi v× kh«ng cßn biÕn nµo cã tiÒm n¨ng lµm t¨ng thªm gi¸ trÞ cña x0, Xem xÐt b¶ng ®¬n h×nh hiÖn thêi ta thÊy r»ng hÖ sè môc tiªu liªn quan tíi x2 (mét biÕn kh«ng cë së) trong hµng x0 lµ -1,5. §iÒu nµy chØ ra r»ng nÕu t¨ng gi¸ trÞ cña x2 tõ møc kh«ng cã thÓ tiÕp tôc lµm t¨ng gi¸ trÞ hiÖn thêi cña x0 = 25. Do ®ã x2 ®­îc lùa chän lµm biÕn vµo. §Ó lùa chän biÕn ra, c¸c tû sè gi÷a c¸c nghiÖm cña c¸c biÕn c¬ së hiÖn thêi (x1, s2, s3) víi c¸c thµnh phÇn trong b¶ng ë c¸c cét ®i vµo ®­îc tÝnh to¸n. BiÕn c¬ së hiÖn thêi liªn quan tíi tû sè d­¬ng nhá nhÊt ®­îc lùa chän lµm biÕn ra. Cã nghÜa lµ, biÕn min(-,2/1,10/0) = c¬ së hiÖn thêi, t­¬ng øng víi min(-,2,∞ ) = 2 lµ biÕn ra trong vßng lÆp thø hai cña ph­¬ng ph¸p ®¬n h×nh. Hµng chÝnh lµ hµng s2 vµ phÇn tö chÝnh lµ 1. Sau c¸c biÕn ®æi hµng, b¶ng ®¬n h×nh míi ®­îc cËp nhËt trªn b¶ng 3.3.6. §iÓm cùc trÞ kh¶ thi liªn quan tíi b¶ng nµy lµ (x1, x2) = (6, 2) vµ gi¸ trÞ cña hµm môc tiªu t­¬ng øng, x0, lµ 28, vµ lín h¬n gi¸ trÞ tr­íc ®ã b»ng 25. Xem xÐt c¸c hÖ sè môc tiªu ë hµng x0 cña b¶ng ta thÊy tÊt c¶ c¸c hÖ sè lµ kh«ng ©m. §èi víi bµi to¸n cùc ®¹i ho¸, lµ tr­êng hîp bµi to¸n s¶n xuÊt vµ xö lÝ chÊt th¶i, nã chØ ra r»ng kh«ng cã c¸c biÕn kh«ng c¬ së (s1, s2) nµo tån t¹i cã tiÒm n¨ng lµm t¨ng tiÕp gi¸ trÞ cña hµm môc tiªu. 94
  20. H×nh 3.3.1 C¸c biÕn ®æi hµng c¸c phÇn tö. Víi ®iÒu nµy chóng ra cã thÓ kÕt luËn r»ng nghiÖm hiÖn thêi (x*1, x*2) = (6, 2), lµ nghiÖm tèi ­u vµ l·i thùc tèi ®a cã thÓ thu ®­îc cho ng­êi s¶n xuÊt x*0 = 28 ngh×n ®« la. 3.3.3. Tãm t¾t ph­¬ng ph¸p ®¬n h×nh Tõ c¸c m« t¶ cña thuËt to¸n ®¬n h×nh ®Ó gi¶i c¸c bµi toµn QHTT, quy tr×nh gi¶i tu©n theo hai ®iÒu kiÖn c¬ b¶n, ®ã lµ, ®iÒu kiÖn tèi ­u vµ ®iÒu kiÖn kh¶ thi. Cô thÓ h¬n cho c¸c biÕn ®æi ®¹i sè, hai ®iÒu kiÖn nµy cã thÓ ®­îc m« t¶ b»ng ng«n tõ nh­ sau. B¶ng 3.3.6 KÕt qu¶ cña b­íc lÆp 2 C¬ së x0 x1 x2 s1 s2 s3 N ghiÖm x0 1 0 0 2,2 1,5 0 28 s1 0 1 0 0,4 0,5 0 6 s2 0 0 1 -0,2 1 0 2 s3 0 0 0 1 0 1 10 95
nguon tai.lieu . vn
Toán học Môi trường Vật lý Sinh học Địa Lý Hoá học Nông - Lâm - Ngư Cơ khí - Chế tạo máy Tiếng Anh phổ thông Khoa học ứng dụng Nông - Lâm Kiến thức tổng hợp Giáo dục học Xã hội học