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ước3.1. Quy hoạch tuyến tínhMô 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:nMax (hoặc Min) x 0 ? ? c j x jj ?1(3.1.1a)Với các biểu thức...
Nội dung trích xuất từ tài liệu:
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 CH¦¥NG 3 Quy ho¹ch tuyÕn tÝnh vµ nh÷ng øng dông trong hÖ thèng nguån níc3.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éngr·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 1Ví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 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 (nx 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ªnT ký hiÖu chuyÓn vÞ cña ma trËn hay vect¬. C¸c s¸ch hay cã liªn quan ®ÕnQHTT 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 ...