單純形法大法兩階段法

單純形法大法兩階段法第1頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月目錄單純形算法計(jì)算步驟初始可行基的確定大M法兩階段法4231第2頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月線性規(guī)劃的單純形算法計(jì)算流程初始基本可行解是否最優(yōu)解或無(wú)限最優(yōu)解?結(jié)束沿邊界找新的基本可行解NY第3頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月線性規(guī)劃解的概念第4頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月1.初始基本可行解的確定線性規(guī)劃標(biāo)準(zhǔn)型：minZ=CXAX=bX≥0從系數(shù)矩陣A中找到一個(gè)可行基B，不妨設(shè)B由A的前m列組成，即B=(P1,P2,……Pm)。進(jìn)行等價(jià)變換－－約束方程兩端分別左乘B－1.

第5頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月2.最優(yōu)性檢驗(yàn)第6頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月3.基變換取某一非基變量xk→換入基（即讓xk>0，其余非基變量仍為0），同時(shí)再?gòu)幕兞恐袚Q出一個(gè)變量xBr→作為非基變量。如何求換入變量xk和換出變量xBr？第7頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月3.基變換從目標(biāo)函數(shù)看xk越小越好，但從可行性看xk又不能任意小。若aik≤0,i=1,…，m,xk可任意取值，此時(shí)問(wèn)題是無(wú)界的；若aik>0,為保證可行性，即xBi=bi-aikxk≥0，應(yīng)取重復(fù)上述過(guò)程，直至所有的σj均≥0，得到最優(yōu)解。

注意：xBr=0第8頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月總結(jié)計(jì)算步驟：給定初始基步1.令xN=0,，xB=B-1b=b，z0=cBxB；步2.檢驗(yàn)數(shù)σj=cj-cBB-1Pj，σj≥0，停止，得最優(yōu)解，否則取σk＝min{σj}，轉(zhuǎn)步3；步3.解ak=B-1Pk，若ak≤0，停止,不存在有限最優(yōu)解.否則轉(zhuǎn)步4.計(jì)算xk進(jìn)基，xBr離基，用Pk替代PBr得新的可行基B步5.以ark為主元素進(jìn)行迭代.轉(zhuǎn)步2新可行解：x=(xB1,…xBr-1,0,xBr+1,…,xBm,0,…，0,xk,0,…，0)第9頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月單純形法流程圖初始可行基開(kāi)始以ark為主元素進(jìn)行迭代得到最優(yōu)解得到最優(yōu)解YYNN所有σj≥0？所有ark≤0?計(jì)算σk＝min{σj|σj<0}第10頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月單純形法例題例3.2求解線性規(guī)劃問(wèn)題將線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形式作初始單純形表，按單純形法計(jì)算步驟進(jìn)行迭代，結(jié)果如下：CBXBb－2－3000x1x2x3x4x50x381210040x41640010－0x5120[4]00130－2－3000第11頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月單純形法例題0x32[1]010－1/220x416400104－3x2301001/4－9－20003/4－2x121010－1/2－0x4800－41[2]4－3x2301001/412130020－1/4－2x141001/400x５400－21/21－3x22011/2－1/8014003/21/80表最后一行的檢驗(yàn)數(shù)均為正，這表示目標(biāo)函數(shù)值已不可能再減小，于是得到最優(yōu)解，目標(biāo)函數(shù)值

．第12頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月初始可行基的確定若系數(shù)矩陣A中含有一個(gè)子矩陣是單位矩陣Im,則取Im為初始可行基。對(duì)于約束條件是“≤”形式的不等式，引入松弛變量將其轉(zhuǎn)換為標(biāo)準(zhǔn)型，再將系數(shù)矩陣中松弛變量對(duì)應(yīng)的單位矩陣取為初始可行基。對(duì)于約束條件是“≥”形式的不等式及等式約束情況，若不存在單位矩陣時(shí)，可采用人工變量，即對(duì)不等式約束就減去一個(gè)非負(fù)的剩余變量后，再加入一個(gè)非負(fù)的人工變量；對(duì)等式約束再加入一個(gè)非負(fù)的人工變量，總可得到一個(gè)單位矩陣作為初始可行基。第13頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月大M法和兩階段法如果線性規(guī)劃模型中約束條件系數(shù)矩陣中不存在單位向量組，解題時(shí)應(yīng)先加入人工變量，人工地構(gòu)成一個(gè)單位向量組。人工變量只起過(guò)渡作用，不應(yīng)影響決策變量的取值。兩種方法可控制人工變量取值使用，盡快地把人工變量減小到零。大M法兩階段法第14頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月大M法

minz=-3X1+X2+X3x1

-

2x2+x3

≤

11-4x1+x2

+2x3

≥

3-2x1+x3=1x1，x2，x3

≥0

minz=-3X1+X2+X3+0x4

+0x5

–Mx6

–Mx7

x1-2x2+x3+

x4

=11

-4x1+x2+2x3-x5

+x6

=3

-2x1+x3+x7

=1

x1，x2，x3，

x4

，

x5，x6，x7

≥0大M單純形法要求將目標(biāo)函數(shù)中的人工變量被指定一個(gè)很大的目標(biāo)函數(shù)系數(shù)（人工變量與松弛剩余變量不同之處）。第15頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月兩階段法

minz=-3X1+X2+X3x1

-

2x2+x3

≤

11-4x1+x2

+2x3

≥

3-2x1+x3=1x1，x2，x3

≥0

minz=x6

+x7

x1-2x2+x3+x4=11-4x1+x2+2x3-x5+x6

=3

-2x1+x3+x7

=1

x1，x2，x3，x4，x5，x6，x7

≥0第一階段，構(gòu)筑一個(gè)只包括人工變量的目標(biāo)函數(shù),在原約束條件下求解，如果計(jì)算結(jié)果是人工變量均為0，則繼續(xù)求解；進(jìn)入第二階段，如果人工變量不為0，說(shuō)明原問(wèn)題無(wú)解。目的是為原問(wèn)題求初始基可行解。第二階段，在此基可行解基礎(chǔ)上對(duì)原目標(biāo)函數(shù)進(jìn)行優(yōu)化。第16頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月習(xí)題三2.(1)用單純形法求解線性規(guī)劃問(wèn)題：

將線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形式

作初始單純形表，按單純形法計(jì)算步驟進(jìn)行迭代，結(jié)果如下：第17頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月習(xí)題三作初始單純形表，按單純形法計(jì)算步驟進(jìn)行迭代，結(jié)果如下：此時(shí)，σ均為正，目標(biāo)函數(shù)已不能再減小，于是得到最優(yōu)解為：x*=(1,1.5,0,0)T目標(biāo)函數(shù)值為：f(x*)=17.5第18頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月習(xí)題三3.(1)分別用單純形法中的大M法和兩階段法求解下列線性規(guī)劃問(wèn)題：

解：大M法：把原問(wèn)題化為標(biāo)準(zhǔn)形式，并加入人工變量如下：

第19頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月習(xí)題三

因?yàn)镸是一個(gè)很大的正數(shù)，此時(shí)σj均為正,所以，得到最優(yōu)解：x*=(0,0,1,1,)T，最優(yōu)值為f(x*)=?3第20頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月習(xí)題三解：兩階段法：首先，構(gòu)造一個(gè)僅含人工變量的新的線性規(guī)劃如下：按單純形法迭代如下：第21頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月習(xí)題三最優(yōu)解為：x*=(0,0,1,1,0,0)T，最優(yōu)值：g(x)=0因人工變量x5=x6=0，則原問(wèn)題的基可行解為:x=(0,0,1,1,)T,進(jìn)入第二階段計(jì)算如下表所示：由上表可知，檢驗(yàn)數(shù)均大于等于0，所以得到最優(yōu)解：x*=(0,0,1,1,)T最優(yōu)值為f(x*)=?3。

第22頁(yè)，課件共24頁(yè)，創(chuàng)作于2023年2月linprog函數(shù)求解線性規(guī)劃問(wèn)題其中，f,x,b,beq,lb,ub為向量,A,Aeq為矩陣。x=linprog(f,A,b)功能：求解最小化問(wèn)題minf*x條件A*x≤b。x=linprog(f,A,b,Aeq,beq)功能：求解最小化問(wèn)題minf*x條件A*x≤bAeq*x=beq，如果沒(méi)有不等式就設(shè)置A=[]和b=[]；沒(méi)有等式就設(shè)置Aeq=[],beq=[]x=linprog(f,A,b,Aeq,beq,lb,ub)功能：求解最小化問(wèn)題minf*x條件A*x≤bAeq*x=beqlb≤x≤ub，決策變量有上下限時(shí)，如果沒(méi)有不等式就設(shè)置A=[]和b=[]；沒(méi)有等式