單純形法解線性規(guī)劃問題

單純形法解線性計(jì)劃問題金融83周慧媛0812178摘要:線性計(jì)劃是運(yùn)籌學(xué)中研究較早、發(fā)展較快、應(yīng)用廣泛、方法較成熟一個(gè)關(guān)鍵分支,它是輔助大家進(jìn)行科學(xué)管理一個(gè)數(shù)學(xué)方法.研究線性約束條件下線性目標(biāo)函數(shù)極值問題數(shù)學(xué)理論和方法,英文縮寫LP。自1946年G.B.Dantizig提出單純形法以來,它一直是求解線性計(jì)劃問題最有效數(shù)學(xué)方法之一。單純形法理論依據(jù)是:線性計(jì)劃問題可行域是n維向量空間Rn中多面凸集,其最優(yōu)值假如存在必在該凸集某頂點(diǎn)處達(dá)成。頂點(diǎn)所對(duì)應(yīng)可行解稱為基礎(chǔ)可行解。經(jīng)過引入一般單純形法,依次迭代并判定,逐步迫近,最終得到最優(yōu)解。關(guān)鍵字:線性計(jì)劃,單純形法,最優(yōu)值,最優(yōu)解單純形法基礎(chǔ)思想任何一個(gè)單純形法迭代算法必需處理三個(gè)問題:1.從哪一個(gè)頂點(diǎn)開始？2.用一條什么樣有效路徑進(jìn)行出一個(gè)頂點(diǎn)向另一個(gè)很好頂點(diǎn)移動(dòng)？3.何時(shí)停止該過程？單純形法即從一個(gè)粗解開始,成功改善現(xiàn)有解,直到所要求目標(biāo)滿足為止。對(duì)于一個(gè)迭代算法,要求一個(gè)停止計(jì)劃,以檢驗(yàn)是否達(dá)成目標(biāo)。單純形法計(jì)算方法:1.找出一個(gè)初始可行基B12.求出對(duì)應(yīng)典式及檢驗(yàn)數(shù)向量&3.求&k=max{&j/j=1,2,3….n}4.若&k<=0,停止。伴隨經(jīng)濟(jì)全球化不停深化,企業(yè)面臨愈加猛烈市場競爭。企業(yè)須不停提升管理水平,增強(qiáng)其贏利能力,在生產(chǎn)、銷售、新產(chǎn)品研發(fā)等一系列過程中只有自己優(yōu)勢,提升企業(yè)效率,降低成本,形成企業(yè)關(guān)鍵競爭力。過去很多企業(yè)在生產(chǎn)、運(yùn)輸、市場營銷等方面沒有利用線性計(jì)劃進(jìn)行合理配置,從而增加了企業(yè)生產(chǎn),使企業(yè)利潤不能達(dá)成最大化。在競爭日益猛烈今天,假如還根據(jù)過去方法,是難以生存,所以就有必需利用線性計(jì)劃知識(shí)對(duì)戰(zhàn)略計(jì)劃、生產(chǎn)、銷售各個(gè)步驟進(jìn)行優(yōu)化從而降低生產(chǎn)成本,提升企業(yè)效率。在各類經(jīng)濟(jì)活動(dòng)中,常常碰到這么問題:在生產(chǎn)條件不變情況下,怎樣經(jīng)過統(tǒng)籌安排,改善生產(chǎn)組織或計(jì)劃,合理安排人力、物力資源,組織生產(chǎn)過程,使總經(jīng)濟(jì)效益最好。這么問題常常能夠化成所謂“線性計(jì)劃”（LinearProgramming,簡記為LP）問題,在利用單純形法去處理。二、單純形法在企業(yè)中應(yīng)用案例分析:某工廠生產(chǎn)甲、乙、丙三種產(chǎn)品,多種產(chǎn)品每件所需原料A分別為2、4、2kg;每件所需原料B分別為4、6、5kg;消耗工時(shí)為6、3、8小時(shí);各產(chǎn)品利潤分別為每件160、180、120元。每七天企業(yè)可用于這些產(chǎn)品工時(shí)為900小時(shí),可提供原料A、B分別為480kg和800kg。以總利潤最大為目標(biāo)考慮各產(chǎn)品生產(chǎn)計(jì)劃。經(jīng)過計(jì)算,得到下列最優(yōu)單純形表:160180120000c(B)X(B)RHSx1x2x3x4x5x6180x250***01/4-1/6160x1125***0-1/81/40x430***1-3/41/6-z-29000***0-25-10請解答下列問題:（1）寫出此問題線性計(jì)劃模型及其最優(yōu)解、最優(yōu)基和最優(yōu)基逆;（2）把最優(yōu)單純形表中“*”格中數(shù)字補(bǔ)充完整;（3）若產(chǎn)品乙利潤從180變?yōu)?50而其她參數(shù)均不變時(shí),問題最優(yōu)解和最優(yōu)值是什么？解:設(shè)每七天分別生產(chǎn)甲、乙、丙三種產(chǎn)品x1,x2,x3件,z表示一周企業(yè)總利潤此問題線性計(jì)劃模型為:Maxz=160x1+180x2+120x32x1+4x2+2x3<=4804x1+6x2+5x3<=8006x1+3x2+8x3<=900x1、x2、x3>=0此問題最優(yōu)解為x1=125,x2=50,x3=0,最大利潤為29000最優(yōu)基為B=421最優(yōu)基逆B=01/4-1/6

6400-1/81/4360 1-3/41/6(2)用B-1左乘約束條件系數(shù)矩陣各列向量得最優(yōu)表x1,x2,x3對(duì)應(yīng)列向量,并計(jì)算出待定檢驗(yàn)數(shù)。160180120000c(B)X(B)RHSx1x2x3x4x5x6180x25001-1/1201/4-1/6160x11251011/80-1/81/40x43000-5/121-3/41/6-z-2900000-850-25-10（3）當(dāng)產(chǎn)品乙利潤從180變?yōu)?50而其它參數(shù)均不變時(shí),原最優(yōu)表變?yōu)?160250120000c(B)X(B)RHSx1x2x3x4x5x6250x25001-1/1201/4-1/6160x11251011/80-1/81/40x43000-5/121-3/41/6-z-2900000-475/60-25-10最優(yōu)解改變,接續(xù)迭代得:160250120000c(B)X(B)RHSx1x2x3x4x5x6250x28001-1/21-0.50160x180102-1.5100x418000-5/26-4.51-z-3280000-75-10-350最優(yōu)解為x1=80,x2=80,x3=0,最大利潤為32800三、單純形法利用到企業(yè)中作用和意義把單純形法知識(shí)利用到企業(yè)中去,能夠使企業(yè)適應(yīng)市場猛烈競爭,立刻、正確、科學(xué)制訂生產(chǎn)計(jì)劃、投資計(jì)劃、對(duì)資源進(jìn)行合理配置。過去企業(yè)在制訂計(jì)劃,調(diào)整分配方面很困難,既要考慮生產(chǎn)成本,又要考慮贏利水平,人工測算需要很長時(shí)間,不易做到機(jī)動(dòng)靈活,利用線性計(jì)劃并配累計(jì)