Linear-Programming介紹教學(xué)課件

1LinearProgrammingNewWordsCarpenterRevenueLumberGeometricallyTableauQuadrantConvexPolygonGeorgeBernardDantzig(November8,1914–May13,2005)wasanAmericanmathematicalscientistwhomadeimportantcontributionstooperationsresearch,computerscience,economics,andstatistics.Dantzigisknownforhisdevelopmentofthesimplexalgorithm,analgorithmforsolvinglinearprogrammingproblems,andhisworkwithlinearprogramming.Instatistics,Dantzigsolvedtwoopenproblemsinstatisticaltheory,whichhehadmistakenforhomeworkafterarrivinglatetoalecture.4美國(guó)數(shù)學(xué)家，美國(guó)科學(xué)院院士。線性規(guī)劃的奠基人。1914年11月8日生于美國(guó)俄勒岡州波特蘭市。1946年在伯克利加利福尼亞大學(xué)數(shù)學(xué)系獲哲學(xué)博士學(xué)位。1947年丹齊克在總結(jié)前人工作的基礎(chǔ)上創(chuàng)立了線性規(guī)劃,并提出了解決線性規(guī)劃問(wèn)題的單純形法。1937～1939年任美國(guó)勞工統(tǒng)計(jì)局統(tǒng)計(jì)員，1941～1952年任美國(guó)空軍司令部數(shù)學(xué)顧問(wèn)、戰(zhàn)斗分析部和統(tǒng)計(jì)管理部主任。1952～1960年任美國(guó)蘭德公司數(shù)學(xué)研究員，1960～1966年任伯克利加利福尼亞大學(xué)教授和運(yùn)籌學(xué)中心主任。1966年后任斯坦福大學(xué)運(yùn)籌學(xué)和計(jì)算機(jī)科學(xué)教授。1971年當(dāng)選為美國(guó)科學(xué)院院士。1975年獲美國(guó)科學(xué)獎(jiǎng)?wù)潞椭Z伊曼理論獎(jiǎng)金。GeorgeBernardDantzig(1914～2005)

5康托羅維奇，Л.В.

蘇聯(lián)經(jīng)濟(jì)學(xué)家，蘇聯(lián)科學(xué)院院士，最優(yōu)計(jì)劃理論的創(chuàng)始人。1912年生，1930年畢業(yè)于列寧格勒大學(xué)物理數(shù)學(xué)系，1935年獲數(shù)學(xué)博士學(xué)位。1964年被選為蘇聯(lián)科學(xué)院院士。因提出資源最大限度分配理論，1975年與美籍荷蘭學(xué)者T.C.庫(kù)普曼斯一起獲得諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)金。

康托羅維奇的主要貢獻(xiàn)是把線性規(guī)劃用于經(jīng)濟(jì)管理，創(chuàng)立了最優(yōu)計(jì)劃理論。對(duì)有效利用資源和提高企業(yè)經(jīng)濟(jì)效益起了重大作用。他還提出經(jīng)濟(jì)效果的概念和衡量經(jīng)濟(jì)效果的統(tǒng)一指標(biāo)體系,作為經(jīng)濟(jì)決策的定量依據(jù),來(lái)選擇最合理的社會(huì)生產(chǎn)結(jié)構(gòu)。主要著作有《生產(chǎn)組織與計(jì)劃的數(shù)學(xué)方法》(1939)、《資源最優(yōu)利用的經(jīng)濟(jì)計(jì)算》(1959)、《最優(yōu)計(jì)劃的動(dòng)態(tài)模型》(1964)等。

6

佳林·庫(kù)普曼斯(1910年—1985年)，美國(guó)人

，1910年8月28日生于荷蘭，1940年離開荷蘭移居美國(guó)。1975年，他和康托羅維奇同時(shí)獲得諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)。線性規(guī)劃經(jīng)濟(jì)分析法的創(chuàng)立者。

7馮?諾依曼（匈牙利語(yǔ)：NeumannJános；英語(yǔ)：JohnvonNeumann，1903年12月28日－1957年2月8日）是出生于匈牙利的美國(guó)籍猶太人數(shù)學(xué)家，現(xiàn)代電子計(jì)算機(jī)創(chuàng)始人之一。他在計(jì)算機(jī)科學(xué)、經(jīng)濟(jì)、物理學(xué)中的量子力學(xué)及幾乎所有數(shù)學(xué)領(lǐng)域都作過(guò)重大貢獻(xiàn)。

馮?諾伊曼從小就顯示出數(shù)學(xué)天才，關(guān)于他的童年有不少傳說(shuō)。大多數(shù)的傳說(shuō)都講到馮?諾伊曼自童年起在吸收知識(shí)和解題方面就具有驚人的速度。六歲時(shí)他能心算做八位數(shù)乘除法，八歲時(shí)掌握微積分，十二歲就讀懂領(lǐng)會(huì)了波萊爾的大作《函數(shù)論》要義。

馮?諾伊曼記憶力驚人，讀書過(guò)目成涌，自幼愛(ài)好歷史學(xué)，他的歷史知識(shí)堪稱淵博，宛如百科全書。

8

他的父親由于考慮到經(jīng)濟(jì)上原因，請(qǐng)人勸阻年方17的馮?諾依曼不要專攻數(shù)學(xué)，后來(lái)父子倆達(dá)成協(xié)議，馮?諾依曼便去攻讀化學(xué)。其后的四年間，馮?諾依曼在布達(dá)佩斯大學(xué)注冊(cè)為數(shù)學(xué)方面的學(xué)生，但并不聽課，只是每年按時(shí)參加考試。1926年他在蘇黎世的獲得化學(xué)方面的大學(xué)畢業(yè)學(xué)位，他也獲得了布達(dá)佩斯大學(xué)數(shù)學(xué)博士學(xué)位。

當(dāng)他結(jié)束學(xué)生時(shí)代的時(shí)候，他已經(jīng)漫步在數(shù)學(xué)、物理、化學(xué)三個(gè)領(lǐng)域的某些前沿。

1926年春，馮?諾依曼到哥廷根大學(xué)任希爾伯特的助手。

中學(xué)時(shí)，他的老師認(rèn)為按傳統(tǒng)的辦法教馮?諾依曼中學(xué)數(shù)學(xué)課程將是毫無(wú)意義的，他接受了大學(xué)教師的單獨(dú)的數(shù)學(xué)訓(xùn)練。1921年，已被大家當(dāng)作數(shù)學(xué)家了。他的第一篇論文是和菲克特合寫的，那時(shí)他還不到18歲。l933年擔(dān)任普林斯頓高級(jí)研究院教授，當(dāng)時(shí)高級(jí)研究院聘有六名教授，其中就包括愛(ài)因斯坦，而年僅30歲的馮?諾依曼是他們當(dāng)中最年輕的一位。

9

馮?諾伊曼是二十世紀(jì)最重要的數(shù)學(xué)家之一，在純粹數(shù)學(xué)和應(yīng)用數(shù)學(xué)方面都有杰出的貢獻(xiàn)。他研究希爾伯特空間上線性自伴算子譜理論，為量子力學(xué)打下數(shù)學(xué)基礎(chǔ)；運(yùn)用緊致群解決了希爾伯特第五問(wèn)題；他和默里創(chuàng)造了算子環(huán)理論，即現(xiàn)在所謂的馮?諾伊曼代數(shù)。1940年以后，馮?諾伊曼轉(zhuǎn)向應(yīng)用數(shù)學(xué)。在力學(xué)、經(jīng)濟(jì)學(xué)、數(shù)值分析和電子計(jì)算機(jī)方面作出了卓越貢獻(xiàn)。第二次世界大戰(zhàn)時(shí)馮?諾伊曼因戰(zhàn)事需要建立沖擊波理論和湍流理論，發(fā)展了流體力學(xué)；從1942年起，他同莫根施特恩合作，寫作《博弈論和經(jīng)濟(jì)行為》一書，使他成為數(shù)理經(jīng)濟(jì)學(xué)的奠基人之一。

馮?諾伊曼對(duì)世界上第一臺(tái)電子計(jì)算機(jī)ENIAC的設(shè)計(jì)有決定性的影響，被稱為“計(jì)算機(jī)之父”。他是現(xiàn)代數(shù)值分析——計(jì)算數(shù)學(xué)的締造者之一。

10OptimizationModeling

BasicconceptsGeometricsolutions

AlgebraicsolutionsTheSimplexmethod11

BasicconceptsOptimize12OptimizeDecisionvariablesXObjectivefunctionsConstraintExample:

DeterminingaproductionscheduleAcarpentermakestablesandbookcases.Howmanyofeachtypeoffurnitureheshouldmakeeachweek---maximizeshisprofitsItcosts$5and$7toproducetablesandbookcases,respectively.Revenues:

DeterminingaproductionscheduleVariationtothepreviousscenario.UNITPROFIT$25and$30pertableandbookcase,respectively.Upto690board-feetoflumberweeklyUpto120hroflabor20board-feetoflumberand5hr---table30board-feetoflumberand4hr---bookcase

ClassificationUnconstrainedConstrainedLinearprogramNonlinearprogramDynamicprogramStochasticprogramIntegerprogram16GeometricsolutionsO51015x1x1=4x25101AB(2,5)C▽Z5x1+x2=1530x1+20x2=1605x1+2x2=5x1=0，x2=1z=3Example:Solve012341234x1x2O-1-2(1)(2)(3)ThesimplexmethodThetypicalformoflinearprogrammingTheoptimalityconditionsThesimplexmethodTheBigMmethodandtheTwo-PhaseMethodThesimplextableauinmatrixformExercises

TheStandardFormofLP1.Definition

StandardForm

----AnLPissaidtobeinstandardformifitsallconstraintareequationsandallvariablesarenonnegative

Thesimplexmethod

TheabbreviatedformThesimplexmethodLet

ThevectorformThesimplexmethodLet

ThematrixformThesimplexmethod2.HowtoConvertanLPtoStandardForm

i)IfconstraintiofanLPisa“≤”constraint,weconvertittoanequalityconstraintbyaddingaslackvariable

sitotheithconstraintandaddingthesignrestrictionsi≥0.ii)IftheithconstraintofanLPisa“≥”constraint,itcanbeconvertedtoanequalityconstraintbysubtractinganexcessvariable

eifromtheithconstraintandaddingthesignrestrictionei≥0.

iv)Iftheobjectivefunctionisaminimizationproblem,i.e.minz=CX,Let

w=-z,wesolvethenewLPproblemmaxw=-CX.iii)Ifavariablexiisunrestrictedinsign(urs),Let,whereTheSimplexAlgorithmExample1

TheSimplexAlgorithmExample2

TheSimplexAlgorithm1.BasicandnonbasicvariableThePreviewofSimplexAlgorithmAX=b---mlinearequationsinnvariables(m<n)BasicSolution---ThesolutiontoAX=bobtainedbysettingn-mvariablesequaltozeroandsolvingforthevaluesoftheremainingmvariables

Note:

Thisassumesthatsettingthen-mvariablesequaltozeroyieldsuniquevaluesfortheremainingmvariablesor,equivalently,thecolumnsfortheremainingmvariablesarelinearlyindependent.Rank(A)=m

TheSimplexAlgorithm

----Thesetofn-mvariables(thenonbasicvariables,orNBV)whicharesetequaltozerotofindabasicsolutiontoAX=bNonbasicVariable-----Thesetoftheremainingn-(n-m)=mvariables(thebasicvariables,orBV)BasicVariableExample1.Findallthebasicsolutionstothefollowingsystemoftwoequationsinthreevariables:

BVNBVBasicSolution{x1,x2}{x3}(2,1,0){x1,x3}{x2}(3,0,-1){x2,x3}{x1}(0,3,2)

TheSimplexAlgorithmBasicFeasibleSolution(orbfs)-----AbasicsolutioninwhichallvariablesarenonnegativetoAX=bExample2

FindallthebasicfeasiblesolutionstothefollowingLP:

TheSimplexAlgorithmSolution:NBVBVBasicSolutionBasicFeasibleSolution{x1,x2}{x3,x4,x5}(0,0,100,80,40)Yes{x1,x3}{x2,x4,x5}(0,100,0,-20,40)No{x1,x4}{x2,x3,x5}(0,80,20,0,40)Yes{x1,x5}{x2

x3,x4}Nosolution-

{x2,x3}{x1,x4,x5}(50,0,0,30,-10)No{x2,x4}{x1,x3,x5}(80,0,-60,0,-40)No{x2,x5}{x2,x3,x4}(40,0,20,40,0)Yes{x3,x4}{x1,x2,x5}(20,60,0,0,20)Yes{x3,x5}{x1,x2,x4}(40,20,0,20,0)Yes{x4,x5}{x1,x2,x3}(40,40,-20,0,0)NoTheSimplexAlgorithmTherelationshipbetweenLP’ssolutions

TheSimplexAlgorithmFeasibleSolutionBFSBSInfeasibleSolution2.SomeBasicTheories

ConvexSet-----AsubsetSofRnsatisfyingthatifforanytwopointsxandyofSthelinesegmentjoiningxandygivenbyz=tx+(1-t)y,for0≤t≤1alsobelongstoSNote:

Inotherwords,asetofpointsSisaconvexsetifthelinesegmentjoininganypairofpointsinSiswhollycontainedinS.

TheSimplexAlgorithmExtremePoint----ApointzofaconvexsetSsuchthatifzisexpressedasaconvexcombinationoftwopointsxandyofS,i.e.,ifz=tx+(1-t)y,forsome0<t<1,thenx=y.Note:

Inotherwords,foranyconvexsetS,apointPinSisanextremepointifeachlinesegmentthatliescompletelyinSandcontainsthepointP,wherePisanendpointofthelinesegment.

AEBCDA

BCTheSimplexAlgorithmTheorem1.

Thefeasibleregionforanylinearprogrammingproblemisaconvexset.Theorem2.ForanLP,thereisauniqueextremepointoftheLP’sfeasibleregioncorrespondingtoeachbfs.Also,thereisatleastonebfscorrespondingtoeachextremepointofthefeasibleregion.

Theorem3.IfanLPhasanoptimalsolution,theremustbeanextremepointofthefeasibleregionthatisoptimal.

TheSimplexAlgorithm一、LP問(wèn)題及其數(shù)學(xué)模型例1

某工廠可生產(chǎn)甲、乙兩種產(chǎn)品，需消耗煤、電、油三種資源，有關(guān)單耗數(shù)據(jù)如表，試擬定使總收入最大的生產(chǎn)計(jì)劃。127單價(jià)300103油20054電36049煤資源限制乙甲產(chǎn)品資源甲乙資源限制煤94360電45200油310300單價(jià)712產(chǎn)品資源線性規(guī)劃模型三要素：（1）決策變量設(shè)甲產(chǎn)品生產(chǎn)x1，乙產(chǎn)品生產(chǎn)x2（2）目標(biāo)函數(shù)

MaxZ=7x1+12x2（3）約束條件9x1+4x2≤3604x1+5x2≤2003x1+10x2≤300x1,x2≥0s.t.返回SubjectTo，意為“使其滿足”2.LP解的幾種情況（1）唯一解（2）多重最優(yōu)解（3）無(wú)可行解注：出現(xiàn)（3）、（4）情況時(shí)，建模有問(wèn)題（4）無(wú)有限最優(yōu)解圖解法的結(jié)論：線性規(guī)劃的可行域是凸集

線性規(guī)劃的最優(yōu)解若存在，必能在可行域的在極點(diǎn)獲得若在兩個(gè)極點(diǎn)同時(shí)獲得，則有無(wú)窮多最優(yōu)解凸集不是凸集極點(diǎn)三、線性規(guī)劃應(yīng)用舉例

例1（下料問(wèn)題）某工廠要做100套鋼架，每套用長(zhǎng)為2.9m,2.1m,1.5m的圓鋼各一根。已知原料每根長(zhǎng)7.4m，問(wèn)：應(yīng)如何下料，可使所用原料最??？

例1（下料問(wèn)題）某工廠要做100套鋼架，每套用長(zhǎng)為2.9m,2.1m,1.5m的圓鋼各一根。已知原料每根長(zhǎng)7.4m，問(wèn)：應(yīng)如何下料，可使所用原料最省？方案2.92.11.5余料7.4m2.9m2.1m1.5m2010.1Ⅰ1200.3Ⅱ1110.9Ⅲ1030Ⅳ0301.1Ⅴ0220.2Ⅵ0130.8Ⅶ0041.4Ⅷ5010302x1+x2+x3+x4=1002x2+x3+3x5+2x6+x7=100x1+x3+3x4+2x6+3x7+4x8=100x1,x2,x3,x4,x5,x6,x7,x8≥0設(shè)x1,x2,x3,x4,x5,x6,x7,x8分別為上述8種方案下料的原材料根數(shù)，建立如下的LP模型：最優(yōu)解為：

x1=10,x2=50,x3=0,x4=30,x5=0,x6=0,x7=0,x8=0minZ=x1+x2+x3+x4+x5+x6+x7+x8s.t.余料1.52.12.9方案2010.1Ⅰ1200.3Ⅱ1110.9Ⅲ1030Ⅳ0301.1Ⅴ0220.2Ⅵ0130.8Ⅶ0041.4Ⅷ一、線性規(guī)劃的標(biāo)準(zhǔn)型MaxZ=c1x1+c2x2+…+cnxn

a11x1+a12x2+…+a1nxn

=b1…………am1x1+am2x2+…+amnxn

=bmx1，x2，…，xn≥0s.t.1、標(biāo)準(zhǔn)形式MaxZ=CXAX=bX≥0s.t.注：標(biāo)準(zhǔn)型中要求bi≥0§2單純形法矩陣表示其中：C=(c1,c2,…,cn)

為價(jià)格系數(shù)X=(x1,x2,…,xn)T

為決策向量

A=(aij)m×n

為技術(shù)系數(shù)

b=(b1,b2,…,bm)T

為資源系數(shù)1)Min型目標(biāo)函數(shù)加負(fù)號(hào)

因?yàn)?，求一個(gè)函數(shù)的極小點(diǎn)，等價(jià)于求該函數(shù)的負(fù)函數(shù)的極大點(diǎn)。注意：Min型化為Max型求解后，最優(yōu)解不變，但最優(yōu)值差負(fù)號(hào)。

2、非標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型2）約束條件例如：9x1+4x2≤3609x1+4x2+x3=360松弛變量

“≤”型約束，加松弛變量；

“≥”型約束，減松弛變量；2、非標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型3）自由變量xk進(jìn)行變量替換：例、將如下問(wèn)題化為標(biāo)準(zhǔn)型第二個(gè)約束減松弛變量解：令、第一個(gè)約束加松弛變量、、標(biāo)準(zhǔn)型例、研究約束集合基本解的個(gè)數(shù)≤令x2=x3=0，得基本解X1=(1/2,0,0)T,對(duì)應(yīng)于A點(diǎn)；1/211/3ABCx2x3x1令x1=x3=0，得基本解X2=(0,1,0)T,對(duì)應(yīng)于B點(diǎn)；令x1=x2=0，得基本解X3=(0,0,1/3)T,對(duì)應(yīng)于C點(diǎn)；基可行解例、研究約束集合基本解的個(gè)數(shù)≤令x1=0，得基本解X1=(0,3,2,-1)T；令x2=0，得基本解X2=(3,0,1,-8)T;令x3=0，得基本解X3=(2,1,0,5)T,對(duì)應(yīng)于F點(diǎn)；畫出可行域12341234ABCDEF0x1x2標(biāo)準(zhǔn)化令x4=0，得基本解X4=(1/3,8/3,5/3,0)T,對(duì)應(yīng)于D點(diǎn)；三、單純形法的基本方法基本方法：確定初始基可行解檢驗(yàn)是否最優(yōu)？轉(zhuǎn)到另一更好的基可行解停YN方法前提：模型化為標(biāo)準(zhǔn)型1.初始可行基B0的確定若A中含有I：B0=I若A中不含I：人工變量法2.最優(yōu)性檢驗(yàn)矩陣分塊把目標(biāo)函數(shù)用非基變量表示：∴檢驗(yàn)數(shù)向量，記為σ。當(dāng)σ≤0時(shí)，當(dāng)前解為最優(yōu)解。方法：（1）計(jì)算每個(gè)xj的檢驗(yàn)數(shù)（2）若所有σj

≤0，則當(dāng)前解為最優(yōu)；否則，至少有σk

>0，轉(zhuǎn)3。3.換基迭代（基變換）（1）進(jìn)基：取對(duì)應(yīng)的Pk進(jìn)基。（2）出基：取對(duì)應(yīng)的Pl進(jìn)基。得新基，轉(zhuǎn)2。注：出基變量的選取為了保證新的基可行。σ的計(jì)算:XBCBB-1bx1x2x3x4x5θσ四、單純形法的實(shí)現(xiàn)——單純形表例：煤電油例MaxZ=7x1+12x29x1+4x2≤3604x1+5x2≤2003x1+10x2≤300x1,x2≥0s.t.MaxZ=7x1+12x29x1+4x2+x3=3604x1+5x2+x4=2003x1+10x2+x5=300x1,…,x5≥0s.t.化為標(biāo)準(zhǔn)型x3x4x5000360200300943451010001000112000單純形表:7σθx5x4x3x2x1B-1bCBXB四、單純形法的實(shí)現(xiàn)——單純形表例：煤電油例MaxZ=7x1+12x29x1+4x2≤3604x1+5x2≤2003x1+10x2≤300x1,x2≥0s.t.MaxZ=7x1+12x29x1+4x2+x3=3604x1+5x2+x4=2003x1+10x2+x5=300x1,…,x5≥0s.t.化為標(biāo)準(zhǔn)型x3x4x5000360200300943451010001000112000單純形表:790θ的計(jì)算:4030σθx5x4x3x2x1B-1bCBXB四、單純形法的實(shí)現(xiàn)——單純形表例：煤電油例MaxZ=7x1+12x29x1+4x2≤3604x1+5x2≤2003x1+10x2≤300x1,x2≥0s.t.MaxZ=7x1+12x29x1+4x2+x3=3604x1+5x2+x4=2003x1+10x2+x5=300x1,…,x5≥0s.t.化為標(biāo)準(zhǔn)型x3x4x5000360200300943451010001000112000單純形表:7904030[]樞紐元素σθx5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000單純形表:7904030[]x3x4x20012300.31000.1σ以10為主元進(jìn)行初等行變換502.5001-0.52407.8010-0.43.4000-1.2即:σθx5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000單純形表:7904030[]x3x4x20012300.31000.1σ以10為主元進(jìn)行初等行變換502.5001-0.52407.8010-0.43.4000-1.2即:30.820100σθx5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000單純形表:7904030[]x3x4x20012300.31000.1σ以10為主元進(jìn)行初等行變換502.5001-0.52407.8010-0.43.4000-1.230.820100[]x3x1x2071224010-0.120.16σ201000.4-0.284001-3.121.16000-1.36-0.52σσθx5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000單純形表:7904030[]x3x4x20012300.31000.1502.5001-0.52407.8010-0.43.4000-1.230.820100[]以為主元進(jìn)行初等行變換2.5x3x1x2071224010-0.120.16σ201000.4-0.284001-3.121.16000-1.36-0.52σσθx5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000單純形表:7904030[]x3x4x20012300.31000.1502.5001-0.52407.8010-0.43.4000-1.230.820100[]∴X*=(20,24,84,0,0)TZ*=428例：用單純形法求解MinS=-x1+2x2x1-x2≥

-2x1+2x2≤6x1,x2≥0s.t.化為標(biāo)準(zhǔn)型MaxS′=x1-2x2-x1+x2+x3=

2x1+2x2+x4=

6x1,…,x4≥0s.t.XBCBB-1bx1x2x3x4θx302-1110不考慮x406[1]2016σ1-200x3080311x1161201σ0-40-1∴X*=(6,0,8,0)TZ*=-6例：用單純形法求解MaxZ=5x1+3x2+2x3+4x45x1+x2+x3+8x4=102x1+4x2+3x3+2x4=10x1,x2,x3,x4≥0s.t.MaxZ=5x1+3x2+2x3+4x45x1+x2+x3+8x4=102x1+4x2+3x3+2x4=10x1,…,x6≥0s.t.+x5

+x6-Mx5-Mx6？五、人工變量法（大M法）1問(wèn)題:MaxZ=CXAX=bX≥0s.t.設(shè)問(wèn)題：，A中不含I(Ⅰ)增加人工變量X人=（xn+1，……，xn+m）T，X人在目標(biāo)函數(shù)中的系數(shù)為-M（M為充分大正數(shù)）。于是原問(wèn)題化為：2方法:MaxZ=CX-MX人AX+IX人=bX,X人≥0s.t.(Ⅱ)單純形法求解(Ⅱ),若最優(yōu)基變量中不含X人，則所得解的前n個(gè)分量即為X*否則，(Ⅰ)無(wú)解。3結(jié)論:例：用單純形法求解MaxZ=5x1+3x2+2x3+4x45x1+x2+x3+8x4=102x1+4x2+3x3+2x4=10x1,x2,x3,x4≥0s.t.解：增加人工變量x5、x6，則模型化為：MaxZ=5x1+3x2+2x3+4x4-Mx5-Mx65x1+x2+x3+8x4+x5=102x1+4x2+3x3+2x4+x6=10x1,…,x6≥0s.t.MaxZ=5x1+3x2+2x3+4x4-Mx5-Mx65x1+x2+x3+8x4+x5=102x1+4x2+3x3+2x4+x6=10x1,…,x6≥0s.t.XBCBB-1bx1x2x3x4x5x6θ511810243201σx5x6-M-M10105+7M3+5M2+4M4+10M005/4501x5σ123420[8]115θx6x4x3x2x1B-1bCBXBx5x6-M-M10105+7M3+5M2+4M4+10M005/45σx4x64-M5/45/81/81/81015/23/415/411/4015/2+3/4M005/2+15/4M3/2+11/4M10201x5σ123420[8]115θx6x4x3x2x1B-1bCBXBx5x6-M-M10105+7M3+5M2+4M4+10M005/45σx4x64-M5/45/81/81/81015/23/4[15/4]11/4015/2+3/4M005/2+15/4M3/2+11/4M102σx4x24313/501/30121/5111/150200-1/35/31001x5σ123420[8]115θx6x4x3x2x1B-1bCBXBx5x6-M-M10105+7M3+5M2+4M4+10M005/45σx4x64-M5/45/81/81/81015/23/4[15/4]11/4015/2+3/4M005/2+15/4M3/2+11/4M102σx4x2431[3/5]01/30121/5111/150200-1/35/310σx1x2535/3101/185/35/30113/18-1/30-10/30-4/9∴X*=(5/3,5/3,0,0)T,Z*=40/3六、單純形法總結(jié)1、Min型單純形表與Max型的區(qū)別僅在于：令σk=min{σj≤0}的xk進(jìn)基，當(dāng)σ≥0時(shí)最優(yōu)。2、解的幾種情況及其在單純形表上的體現(xiàn)（討論Max型）唯一最優(yōu)解σj≤0,非基σ<0多重最優(yōu)解σj≤0有非基σk=0無(wú)界解有σk>0但B-1Pk≤0無(wú)可行解用大M法求解，最優(yōu)基中含有X人退化解最優(yōu)解中某基變量為0ThesimplexalgorithmConverttheLPtostandardformRewritetheLPasitscanonicalform.Determinewhetherthecurrentbasicfeasiblesolutionisoptimalbyoptimalityconditions,ifso,stop,otherwiseturntothenextstep.Choosetheenteringandleavingvariableandperformthepivotingoperationtotransfertoanothersimplextable