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

5康托羅維奇，Л.В.

蘇聯經濟學家，蘇聯科學院院士，最優計劃理論的創始人。1912年生，1930年畢業于列寧格勒大學物理數學系，1935年獲數學博士學位。1964年被選為蘇聯科學院院士。因提出資源最大限度分配理論，1975年與美籍荷蘭學者T.C.庫普曼斯一起獲得諾貝爾經濟學獎金。

康托羅維奇的主要貢獻是把線性規劃用于經濟管理，創立了最優計劃理論。對有效利用資源和提高企業經濟效益起了重大作用。他還提出經濟效果的概念和衡量經濟效果的統一指標體系,作為經濟決策的定量依據,來選擇最合理的社會生產結構。主要著作有《生產組織與計劃的數學方法》(1939)、《資源最優利用的經濟計算》(1959)、《最優計劃的動態模型》(1964)等。

6

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

，1910年8月28日生于荷蘭，1940年離開荷蘭移居美國。1975年，他和康托羅維奇同時獲得諾貝爾經濟學獎。線性規劃經濟分析法的創立者。

7馮?諾依曼（匈牙利語：NeumannJános；英語：JohnvonNeumann，1903年12月28日－1957年2月8日）是出生于匈牙利的美國籍猶太人數學家，現代電子計算機創始人之一。他在計算機科學、經濟、物理學中的量子力學及幾乎所有數學領域都作過重大貢獻。

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

馮?諾伊曼記憶力驚人，讀書過目成涌，自幼愛好歷史學，他的歷史知識堪稱淵博，宛如百科全書。

8

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

當他結束學生時代的時候，他已經漫步在數學、物理、化學三個領域的某些前沿。

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

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

9

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

馮?諾伊曼對世界上第一臺電子計算機ENIAC的設計有決定性的影響，被稱為“計算機之父”。他是現代數值分析——計算數學的締造者之一。

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問題及其數學模型例1

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

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

線性規劃的最優解若存在，必能在可行域的在極點獲得若在兩個極點同時獲得，則有無窮多最優解凸集不是凸集極點三、線性規劃應用舉例

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

例1（下料問題）某工廠要做100套鋼架，每套用長為2.9m,2.1m,1.5m的圓鋼各一根。已知原料每根長7.4m，問：應如何下料，可使所用原料最省？方案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設x1,x2,x3,x4,x5,x6,x7,x8分別為上述8種方案下料的原材料根數，建立如下的LP模型：最優解為：

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Ⅷ一、線性規劃的標準型MaxZ=c1x1+c2x2+…+cnxn

a11x1+a12x2+…+a1nxn

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

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

為價格系數X=(x1,x2,…,xn)T

為決策向量

A=(aij)m×n

為技術系數

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

為資源系數1)Min型目標函數加負號

因為，求一個函數的極小點，等價于求該函數的負函數的極大點。注意：Min型化為Max型求解后，最優解不變，但最優值差負號。

2、非標準型標準型2）約束條件例如：9x1+4x2≤3609x1+4x2+x3=360松弛變量

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

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

≤0，則當前解為最優；否則，至少有σk

>0，轉3。3.換基迭代（基變換）（1）進基：取對應的Pk進基。（2）出基：取對應的Pl進基。得新基，轉2。注：出基變量的選取為了保證新的基可行。σ的計算:XBCBB-1bx1x2x3x4x5θσ四、單純形法的實現——單純形表例：煤電油例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.化為標準型x3x4x5000360200300943451010001000112000單純形表:7σθx5x4x3x2x1B-1bCBXB四、單純形法的實現——單純形表例：煤電油例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.化為標準型x3x4x5000360200300943451010001000112000單純形表:790θ的計算:4030σθx5x4x3x2x1B-1bCBXB四、單純形法的實現——單純形表例：煤電油例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.化為標準型x3x4x5000360200300943451010001000112000單純形表:7904030[]樞紐元素σθx5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000單純形表:7904030[]x3x4x20012300.31000.1σ以10為主元進行初等行變換502.5001-0.52407.8010-0.43.4000-1.2即:σθx5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000單純形表:7904030[]x3x4x20012300.31000.1σ以10為主元進行初等行變換502.5001-0.52407.8010-0.43.4000-1.2即:30.820100σθx5x4x3x2x1B-1bCBXBx3x4x5000360200300943451010001000112000單純形表:7904030[]x3x4x20012300.31000.1σ以10為主元進行初等行變換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[]以為主元進行初等行變換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.化為標準型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問題:MaxZ=CXAX=bX≥0s.t.設問題：，A中不含I(Ⅰ)增加人工變量X人=（xn+1，……，xn+m）T，X人在目標函數中的系數為-M（M為充分大正數）。于是原問題化為：2方法:MaxZ=CX-MX人AX+IX人=bX,X人≥0s.t.(Ⅱ)單純形法求解(Ⅱ),若最優基變量中不含X人，則所得解的前n個分量即為X*否則，(Ⅰ)無解。3結論:例：用單純形法求解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六、單純形法總結1、Min型單純形表與Max型的區別僅在于：令σk=min{σj≤0}的xk進基，當σ≥0時最優。2、解的幾種情況及其在單純形表上的體現（討論Max型）唯一最優解σj≤0,非基σ<0多重最優解σj≤0有非基σk=0無界解有σk>0但B-1Pk≤0無可行解用大M法求解，最優基中含有X人退化解最優解中某基變量為0ThesimplexalgorithmConverttheLPtostandardformRewritetheLPasitscanonicalform.Determinewhetherthecurrentbasicfeasiblesolutionisoptimalbyoptimalityconditions,ifso,stop,otherwiseturntothenextstep.Choosetheenteringandleavingvariableandperformthepivotingoperationtotransfertoanothersimplextable