线æ§è§åé®é¢çæ°å¦æ¨¡åçä¸è¬å½¢å¼ããï¼1ï¼ååºçº¦ææ¡ä»¶åç®æ å½æ°
ããï¼2ï¼ç»åºçº¦ææ¡ä»¶æ表示çå¯è¡å
ããï¼3ï¼å¨å¯è¡åå
æ±ç®æ å½æ°çæä¼è§£ [ç¼è¾æ¬æ®µ]线æ§è§åçåå±ããæ³å½æ°å¦å®¶ J.- B.- J.å
éå¶å C.ç¦è±ï¼æ®æ£®åå«äº1832å1911å¹´ç¬ç«å°æåºçº¿æ§è§åçæ³æ³ï¼ä½æªå¼èµ·æ³¨æã
ãã1939å¹´èèæ°å¦å®¶Ð.Ð.康æç½ç»´å¥å¨ãç产ç»ç»ä¸è®¡åä¸çæ°å¦æ¹æ³ãä¸ä¹¦ä¸æåºçº¿æ§è§åé®é¢ï¼ä¹æªå¼èµ·éè§ã
ãã1947å¹´ç¾å½æ°å¦å®¶G.B.丹é½å
æåºçº¿æ§è§åçä¸è¬æ°å¦æ¨¡ååæ±è§£çº¿æ§è§åé®é¢çéç¨æ¹æ³ââå纯形æ³ï¼ä¸ºè¿é¨å¦ç§å¥ å®äºåºç¡ã
ãã1947å¹´ç¾å½æ°å¦å®¶J.von诺ä¼æ¼æåºå¯¹å¶ç论,å¼åäºçº¿æ§è§åç许å¤æ°çç 究é¢åï¼æ©å¤§äºå®çåºç¨èå´å解é¢è½åã
ãã1951å¹´ç¾å½ç»æµå¦å®¶T.C.åºæ®æ¼æ¯æ线æ§è§ååºç¨å°ç»æµé¢åï¼ä¸ºæ¤ä¸åº·æç½ç»´å¥ä¸èµ·è·1975年诺è´å°ç»æµå¦å¥ã
ãã50年代å对线æ§è§åè¿è¡å¤§éçç论ç 究ï¼å¹¶æ¶ç°åºä¸å¤§æ¹æ°çç®æ³ãä¾å¦ï¼1954å¹´C.è±å§åºæåºå¯¹å¶å纯形æ³ï¼1954å¹´S.å æ¯åT.è¨è¿ªç人解å³äºçº¿æ§è§åççµæ度åæååæ°è§åé®é¢ï¼1956å¹´A.å¡å
æåºäºè¡¥æ¾å¼å®çï¼1960å¹´G.B.丹é½å
åP.æ²å°å¤«æåºå解ç®æ³çã
ãã线æ§è§åçç 究ææè¿ç´æ¥æ¨å¨äºå
¶ä»æ°å¦è§åé®é¢å
æ¬æ´æ°è§åãéæºè§ååé线æ§è§åçç®æ³ç 究ãç±äºæ°åçµå计ç®æºçåå±ï¼åºç°äºè®¸å¤çº¿æ§è§å软件ï¼å¦MPSXï¼OPHEIEï¼UMPIREçï¼å¯ä»¥å¾æ¹ä¾¿å°æ±è§£å å个åéç线æ§è§åé®é¢ã
ãã1979å¹´èèæ°å¦å®¶L. G. Khachianæåºè§£çº¿æ§è§åé®é¢çæ¤çç®æ³ï¼å¹¶è¯æå®æ¯å¤é¡¹å¼æ¶é´ç®æ³ã
ãã1984å¹´ç¾å½è´å°çµè¯å®éªå®¤çå°åº¦æ°å¦å®¶N.å¡é©¬å¡æåºè§£çº¿æ§è§åé®é¢çæ°çå¤é¡¹å¼æ¶é´ç®æ³ãç¨è¿ç§æ¹æ³æ±è§£çº¿æ§è§åé®é¢å¨åé个æ°ä¸º5000æ¶åªè¦å纯形æ³æç¨æ¶é´ç1/50ãç°å·²å½¢æ线æ§è§åå¤é¡¹å¼ç®æ³ç论ã50年代å线æ§è§åçåºç¨èå´ä¸ææ©å¤§ã 建ç«çº¿æ§è§å模åçæ¹æ³ [ç¼è¾æ¬æ®µ]线æ§è§åç模å建ç«ããä»å®é
é®é¢ä¸å»ºç«æ°å¦æ¨¡åä¸è¬æ以ä¸ä¸ä¸ªæ¥éª¤ï¼
ãã1.æ ¹æ®å½±åæè¦è¾¾å°ç®ççå ç´ æ¾å°å³çåéï¼
ãã2.ç±å³çåéåæå¨è¾¾å°ç®çä¹é´çå½æ°å
³ç³»ç¡®å®ç®æ å½æ°ï¼
ãã3.ç±å³çåéæåçéå¶æ¡ä»¶ç¡®å®å³çåéæè¦æ»¡è¶³ç约ææ¡ä»¶ã
ããæ建ç«çæ°å¦æ¨¡åå
·æ以ä¸ç¹ç¹ï¼
ãã1ãæ¯ä¸ªæ¨¡åé½æè¥å¹²ä¸ªå³çåéï¼x1,x2,x3â¦â¦ï¼xnï¼ï¼å
¶ä¸n为å³çåé个æ°ãå³çåéçä¸ç»å¼è¡¨ç¤ºä¸ç§æ¹æ¡ï¼åæ¶å³çåéä¸è¬å¼éè´çã
ãã2ãç®æ å½æ°æ¯å³çåéç线æ§å½æ°ï¼æ ¹æ®å
·ä½é®é¢å¯ä»¥æ¯æ大åï¼maxï¼ææå°åï¼minï¼ï¼äºè
ç»ç§°ä¸ºæä¼åï¼optï¼ã
ãã3ã约ææ¡ä»¶ä¹æ¯å³çåéç线æ§å½æ°ã
ããå½æ们å¾å°çæ°å¦æ¨¡åçç®æ å½æ°ä¸ºçº¿æ§å½æ°ï¼çº¦ææ¡ä»¶ä¸ºçº¿æ§çå¼æä¸çå¼æ¶ç§°æ¤æ°å¦æ¨¡å为线æ§è§å模åã
ããä¾ï¼
ããç产å®æ模åï¼æå·¥åè¦å®æç产â
ãâ
¡ä¸¤ç§äº§åï¼å·²ç¥ç产åä½äº§åæéç设å¤å°æ¶åAãB两ç§åææçæ¶èï¼å¦è¡¨æ示ï¼è¡¨ä¸å³è¾¹ä¸åæ¯æ¯æ¥è®¾å¤è½åååææä¾åºçééï¼è¯¥å·¥åç产ä¸åä½äº§åâ
å¯è·å©2å
ï¼ç产ä¸åä½äº§åâ
¡å¯è·å©3å
ï¼é®åºå¦ä½å®æç产ï¼ä½¿å
¶è·å¾æå¤ï¼
ãã解ï¼
ãã1ãç¡®å®å³çåéï¼è®¾x1ãx2为产åâ
ãâ
¡çç产æ°éï¼
ãã2ãæç¡®ç®æ å½æ°ï¼è·å©æ大ï¼å³æ±2x1+3x2æ大å¼ï¼
ãã3ãæ满足ç约ææ¡ä»¶ï¼
ãã设å¤éå¶ï¼x1+2x2â¤8
ããåææAéå¶ï¼4x1â¤16
ããåææBéå¶ï¼4x2â¤12
ããåºæ¬è¦æ±ï¼x1,x2â¥0
ããç¨max代æ¿æ大å¼ï¼s.t.ï¼subject to çç®åï¼ä»£æ¿çº¦ææ¡ä»¶ï¼å该模åå¯è®°ä¸ºï¼
ããmax z=2x1+3x2
ããs.t. x1+2x2â¤8
ãã4x1â¤16
ãã4x2â¤12
ããx1,x2â¥0 [ç¼è¾æ¬æ®µ]线æ§è§åç解æ³ããæ±è§£çº¿æ§è§åé®é¢çåºæ¬æ¹æ³æ¯å纯形æ³ï¼ç°å¨å·²æå纯形æ³çæ å软件ï¼å¯å¨çµå计ç®æºä¸æ±è§£çº¦ææ¡ä»¶åå³çåéæ°è¾¾ 10000个以ä¸ç线æ§è§åé®é¢ã为äºæé«è§£é¢é度ï¼åææ¹è¿å纯形æ³ã对å¶å纯形æ³ãåå§å¯¹å¶æ¹æ³ãå解ç®æ³ååç§å¤é¡¹å¼æ¶é´ç®æ³ã对äºåªæ两个åéçç®åç线æ§è§åé®é¢ï¼ä¹å¯éç¨å¾è§£æ³æ±è§£ãè¿ç§æ¹æ³ä»
éç¨äºåªæ两个åéç线æ§è§åé®é¢ãå®çç¹ç¹æ¯ç´è§èæäºç解ï¼ä½å®ç¨ä»·å¼ä¸å¤§ãéè¿å¾è§£æ³æ±è§£å¯ä»¥ç解线æ§è§åçä¸äºåºæ¬æ¦å¿µã
ãã对äºä¸è¬çº¿æ§è§åé®é¢ï¼
ããMin z=CX
ããS.T.
ããAX =b
ããX>=0
ããå
¶ä¸A为ä¸ä¸ªm*nç©éµã
ããè¥Aè¡æ»¡ç§©
ããåå¯ä»¥æ¾å°åºç©éµBï¼å¹¶å¯»æ¾åå§åºè§£ã
ããç¨N表示对åºäºBçéåºç©éµãåè§åé®é¢1å¯å为ï¼
ããè§åé®é¢2ï¼
ããMin z=CB XB+CNXN
ããS.T.
ããB XB+N XN = b (1)
ããXB >= 0, XN >= 0 (2)
ãã(1)两边åä¹äºB-1ï¼å¾
ããXB + B-1 N XN = B-1 b
ããåæ¶ï¼ç±ä¸å¼å¾XB = B-1 b - B-1 N XNï¼ä¹ä»£å
¥ç®æ å½æ°ï¼é®é¢å¯ä»¥ç»§ç»å为ï¼
ããè§åé®é¢3ï¼
ããMin z=CB B-1 b + ( CN - CB B-1 N ) XN
ããS.T.
ããXB+B-1N XN = B-1 b (1)
ããXB >= 0, XN >= 0 (2)
ãã令N:=B-1Nï¼b:= B-1 bï¼Î¶= CB B-1bï¼Ï= CN - CB B-1 Nï¼åä¸è¿°é®é¢å为è§åé®é¢å½¢å¼4ï¼
ããMin z= ζ + Ï XN
ããS.T.
ããXB+ N XN = b (1)
ããXB >= 0, XN >= 0 (2)
ããå¨ä¸è¿°åæ¢ä¸ï¼è¥è½æ¾å°è§åé®é¢å½¢å¼4ï¼ä½¿å¾b>=0ï¼ç§°è¯¥å½¢å¼ä¸ºåå§åºè§£å½¢å¼ã
ããä¸è¿°çåæ¢ç¸å½äºå¯¹æ´ä¸ªæ©å±ç©éµï¼å
å«CåAï¼ ä¹ä»¥å¢å¹¿ç©éµ ãæ以éå¨éæ©Bï¼ä»èæ¾åºå¯¹åºçCBã
ããè¥åå¨åå§åºè§£
ããè¥Ï>= 0
ããåz >=ζãåæ¶ï¼ä»¤XN = 0ï¼XB = bï¼è¿æ¯ä¸ä¸ªå¯è¡è§£ï¼ä¸æ¤æ¶z=ζï¼å³è¾¾å°æä¼å¼ãæ以ï¼æ¤æ¶å¯ä»¥å¾å°æä¼è§£ã
ããè¥Ï >= 0ä¸æç«
ããå¯ä»¥éç¨å纯形表åæ¢ã
ããÏä¸åå¨åé<0ãè¿äºè´åé对åºçå³çåéç¼å·ä¸ï¼æå°ç为jãNä¸ä¸j对åºçååé为Pjã
ããè¥Pj <=0ä¸æç«
ããåPjè³å°åå¨ä¸ä¸ªåéaiï¼j为æ£ãå¨è§åé®é¢4ç约ææ¡ä»¶ï¼1ï¼ç两边ä¹ä»¥ç©éµTã
ããT=
ããååæ¢åï¼å³çåéxjæ为åºåéï¼æ¿æ¢æåæ¥çé£ä¸ªåºåéã为使å¾T b >= 0ï¼ä¸T Pj=eiï¼å
¶ä¸ï¼ei表示第i个åä½åéï¼ï¼éè¦ï¼
ããl aiï¼j>0ã
ããl βq+βi*(-aq,j/ai,j)>=0ï¼å
¶ä¸q!=iãå³Î²q>=βi/ ai,j * aq,jã
ããn è¥aq,j<=0ï¼ä¸å¼ä¸å®æç«ã
ããn è¥aq,j>0ï¼åéè¦Î²q / aq,j >=βi/ ai,jãå æ¤ï¼è¦éæ©i使å¾Î²i/ ai,jæå°ã
ããå¦æè¿ç§æ¹æ³ç¡®å®äºå¤ä¸ªä¸æ ï¼éæ©ä¸æ æå°çä¸ä¸ªã
ãã转æ¢åå¾å°è§åé®é¢4çå½¢å¼ï¼ç»§ç»å¯¹Ïè¿è¡å¤æãç±äºåºè§£æ¯æé个ï¼å æ¤ï¼ä¸å®å¯ä»¥å¨æéæ¥è·³åºè¯¥å¾ªç¯ã
ããè¥å¯¹äºæ¯ä¸ä¸ªiï¼ai,j<=0
ããæä¼å¼æ çã
ããè¥ä¸è½å¯»æ¾å°åå§åºè§£
ããæ 解ã
ããè¥Aä¸æ¯è¡æ»¡ç§©
ããåç®ç´å°Aè¡æ»¡ç§©ï¼è½¬å°è¥Aè¡æ»¡ç§©ã [ç¼è¾æ¬æ®µ]线æ§è§åçåºç¨ããå¨ä¼ä¸çå项管çæ´»å¨ä¸,ä¾å¦è®¡åãç产ãè¿è¾ãææ¯çé®é¢,线æ§è§åæ¯æä»åç§éå¶æ¡ä»¶çç»åä¸,éæ©åºæ为åçç计ç®æ¹æ³,建ç«çº¿æ§è§å模åä»èæ±å¾æä½³ç»æ.
温馨提示:答案为网友推荐,仅供参考