第一章 線性規(guī)劃與單純形法

-(1.13)非基變量的檢驗(yàn)數(shù)用分別為基變量檢驗(yàn)數(shù)都為0，得初始單純形表如表1.8所示。表1.82-11-2112020101-11011002-2303001370008表1.8所對(duì)應(yīng)的基本可行解為，因?yàn)?，所以不是最?yōu)解，仍需求新的基本可行解，根據(jù)Bland法則選取為入基變量，，由Bland法則取定為出基變量，換基迭代得表1.9。表1.9所對(duì)應(yīng)的基本可行解為，因?yàn)樗袡z驗(yàn)數(shù)非正，所以為最優(yōu)解。最優(yōu)目標(biāo)函數(shù)值。

表1.92-11-21100-210-321011002-200-301-30-700-6例1.10中換基迭代中采用了Bland法則來避免循環(huán)現(xiàn)象的出現(xiàn)。其實(shí)到目前為止在實(shí)際問題的線性規(guī)劃模型中還未曾出現(xiàn)過循環(huán)現(xiàn)象。因此在退化現(xiàn)象出現(xiàn)時(shí)，實(shí)際上可以隨意決定哪一個(gè)變量作為出基變量，不必考慮理論上有可能出現(xiàn)循環(huán)的后果。例1.11求解下列線性規(guī)劃問題：解：化為標(biāo)準(zhǔn)型后用單純形法計(jì)算，得初始單純形表如表1.10所示。表1.102400004-1210001012010021-100124000表1.10中，，，選定為入基變量，由法則，，選定為出基變量，為主元素。換基迭代得表1.11。表1.112400042-1/211/2000620-110041/201/20140-20047/2011/41/402310-1/21/2005/2003/4-1/41000-20經(jīng)過兩次初等變換迭代得基本可行解，所有檢驗(yàn)數(shù)都小于等于0，故為最優(yōu)解。最優(yōu)目標(biāo)函數(shù)值。其中非基變量的檢驗(yàn)數(shù)，若增加，目標(biāo)函數(shù)值不變，即當(dāng)進(jìn)基時(shí)目標(biāo)函數(shù)值仍為最優(yōu)值20。以為入基變量，繼續(xù)迭代，如表1.12所示，得到另一個(gè)基本可行解仍為最優(yōu)解，目標(biāo)函數(shù)值。是線性規(guī)劃問題的兩個(gè)最優(yōu)基本可行解，它們連線上的所有點(diǎn)（凸組合）都是問題的最優(yōu)解，從而原問題有無窮多最優(yōu)解。表1.122400048/30101/3-1/3214/31001/32/3010/3001-1/34/3000-20定理1.5無窮多最優(yōu)解判定定理當(dāng)所有的檢驗(yàn)數(shù)全部小于等于零時(shí),若有某個(gè)非基變量的檢驗(yàn)數(shù)也是零,則該線性規(guī)劃有無窮多最優(yōu)解。例1.12求解下列線性規(guī)劃問題：解：化為標(biāo)準(zhǔn)型后用單純形法計(jì)算，如表1.13所示表1.13-2300024-210042-301-2300，為入基變量，但，沒有符合條件的最小比值，說明當(dāng)非基變量保持為0時(shí)，只要就能保證非負(fù)，即可以無限增大，此時(shí)目標(biāo)函數(shù)值也無限增大且滿足約束條件，從而問題具有無界解。用圖解法也可看出問題有無界解，定理1.6無界解判定定理在單純形表中，若某個(gè)檢驗(yàn)數(shù)且在中的系數(shù)均為負(fù)，則線性規(guī)劃問題具有無界解。3．大法前面討論的線性規(guī)劃問題，其標(biāo)準(zhǔn)型中系數(shù)矩陣中都有單位子陣，作為初始基，很容易就可以得到初始基本可行解。但在實(shí)際問題中，有些規(guī)劃問題的標(biāo)準(zhǔn)型中不含單位子陣，此時(shí)需要在約束方程中添加虛擬變量，構(gòu)造單位子陣作為初始基。這種人為添加的變量稱為人工變量。在一個(gè)線性規(guī)劃問題中添加人工變量，要求不改變?cè)瓎栴}，這就要求人工變量的取值對(duì)目標(biāo)函數(shù)值不影響，為此在極大化目標(biāo)函數(shù)中使人工變量的系數(shù)為“”（為足夠大的正數(shù)），這樣目標(biāo)函數(shù)要實(shí)現(xiàn)極大化，必需把人工變量從基變量中換出。否則目標(biāo)函數(shù)不可能實(shí)現(xiàn)最大化。我們將這種方法稱為大法。例1.13求解下列線性規(guī)劃問題：解：在問題中，添加松弛變量，人工變量，得到在用單純形表求解的過程中，只需將看成一個(gè)足夠大的正數(shù)，其它都和前面的方法一樣。表1.143-1-100-M-M0111-211000-M3-4120-110-M1-2010001-6M+3M-13M-10-M000103-20100-1-M10100-11-2-11-20100011M-100-M01-3M0123001-22-5-110100-11-2-11-20100011000-11-M-1-M341001/3-2/32/3-5/3-110100-11-2-190012/3-4/34/3-7/3000-1/3-1/31/3-M2/3-M得到最優(yōu)解最優(yōu)目標(biāo)函數(shù)值。說明：終止表可能出現(xiàn)下面三種情況：eq\o\ac(○,1)基變量中無人工變量；eq\o\ac(○,2)基變量中含有人工變量但取值為0；eq\o\ac(○,3)基變量中含有人工變量且取值非0。在前兩種情況下，原問題有最優(yōu)解，但在第三種情況下中，最優(yōu)解含有不為0的人工變量，則原問題無可行解。第六節(jié)用WinQSB解線性規(guī)劃問題QSB是QuantitativeSystemsforBusiness的縮寫，WinQSB是QSB在Windows操作系統(tǒng)下運(yùn)行的版本。WinQSB是一種教學(xué)軟件，里面有大量的運(yùn)籌學(xué)模型，對(duì)于非大型的問題一般都能計(jì)算，較小的問題還能演示中間的計(jì)算過程，特別適合多媒體課堂教學(xué)。該軟件可應(yīng)用于求解運(yùn)籌學(xué)中的各種問題。本節(jié)主要介紹運(yùn)用WinQSB求解線性規(guī)劃問題。安裝WinQSB軟件后，在系統(tǒng)程序中自動(dòng)生成WinQSB應(yīng)用子程序，用戶可以根據(jù)不同的問題選擇相應(yīng)的子程序進(jìn)行求解。求解線性規(guī)劃問題采用子程序“LinearandIntegerProgramming”。下面結(jié)合例題介紹WinQSB求解線性規(guī)劃問題的操作步驟及應(yīng)用。例1.14用WinQSB求解下列線性規(guī)劃問題解：WinQSB軟件求解的線性規(guī)劃問題不必化為標(biāo)準(zhǔn)型，不等式約束可以在輸入數(shù)據(jù)時(shí)直接輸入，對(duì)于單個(gè)決策變量的約束，例如非負(fù)約束或無約束等，可以直接通過修改系統(tǒng)變量類型即可。第1步：?jiǎn)?dòng)子程序“LinearandIntegerProgramming”。點(diǎn)擊開始程序WinQSBLinearandIntegerProgramming，如圖1.8所示。圖1.8第2步：建立新問題。選擇FileNewProgram”，出現(xiàn)圖1.9所示的問題選項(xiàng)輸入界面。圖1.9問題題頭（ProblemTitle）：沒有可不輸入；決策變量數(shù)（NumberofVariables）：本例中有兩個(gè)決策變量，填入2；約束條件數(shù)（NumberofConstraints）：本例中不計(jì)非負(fù)約束共有3個(gè)約束條件，填入3；目標(biāo)函數(shù)準(zhǔn)則（ObjectiveCriterion）：本例目標(biāo)函數(shù)選最小化（Minimization）；數(shù)據(jù)輸入格式（DataEntryFormat）：一般選擇矩陣式電子表格式（SpreadsheetMatrixForm），另一個(gè)選項(xiàng)為自由格式輸入標(biāo)準(zhǔn)模式（NormalModelForm）；變量類型（DefaultVariableType）：一共有以下四個(gè)選項(xiàng)非負(fù)連續(xù)變量選擇第1個(gè)單選按鈕（Nonnegativecontinuous）；非負(fù)整型變量選擇第2個(gè)單選按鈕（Nonnegativeinteger）；二進(jìn)制變量選擇第3個(gè)按鈕（Binary[0,1]）；自由變量選擇第4個(gè)按鈕（Unsigned/unrestricted）。本例中選非負(fù)連續(xù)變量。第3步：輸入數(shù)據(jù)。單擊“OK”，生成表格并輸入數(shù)據(jù)如表1.15：表1.15系統(tǒng)默認(rèn)變量名為，約束條件名為。在表中第1行輸入價(jià)值系數(shù)；第2-4行列對(duì)應(yīng)輸入約束方程系數(shù)，“Direction”列輸入約束符，“R.H.S”列輸入右端項(xiàng)；第5行輸入變量下限，第6行輸入變量上限，由于之前選擇變量類型為非負(fù)連續(xù)變量，因此默認(rèn)變量下限為0，變量上限為Ｍ，這里Ｍ表示正無窮大；第7行為變量類型，可以通過雙擊修改。第4步：求解點(diǎn)擊“SolveandAnalyze”菜單，下拉菜單中有三個(gè)選項(xiàng)：求解但不顯示迭代過程“SolvetheProblem”、求解并顯示迭代過程“SolveandDisplaySteps”及圖解法“GraphicMethod”顯示單純形法迭代步驟，選擇“SimplexIteration”直到最終單純形表。若選擇“SolvetheProblem”，生成如下運(yùn)行結(jié)果：表1.16決策變量（DecisionVariable）：x1、x2最優(yōu)解（SolutionValue）：x1=60,x2=30；價(jià)值系數(shù)（UnitCostorProfitc(j)）：c1=4000,c2=3000；最優(yōu)函數(shù)值（Totalcontribution）：x1貢獻(xiàn)240000、x2貢獻(xiàn)90000,共計(jì)330000；檢驗(yàn)數(shù)（ReducedCost）：0，0。即當(dāng)變量增加一個(gè)單位時(shí)，目標(biāo)函數(shù)值的改變量。價(jià)值系數(shù)的允許最小值（AllowableMin.c[j]）和允許最大值（AllowableMax.c[j]）：價(jià)值系數(shù)在此范圍變動(dòng)時(shí)時(shí)，最優(yōu)解不變。約束條件（Constraint）：C1、C2、C3左端取值（LeftHandSide）：12000、30000、15000右端取值（RightHandSide）：12000、20000、15000松馳變量或剩余變量的取值（SlackorSurplus）：該值等于約束左端與約束右端之差。為0表示資源已達(dá)到限制值，大于0表示未達(dá)到限制值。影子價(jià)格（ShadowPrice）：6.6667、0、16.6667，即為對(duì)偶問題的最優(yōu)解。約束右端的允許最小值（AllowableMin.RHS）和允許最大值（AllowableMax.RHS）：表示約束右端在此范圍變化時(shí)最優(yōu)解不變。第5步：結(jié)果顯示及分析。點(diǎn)擊菜單欄result，存在最優(yōu)解決時(shí)，下拉菜單有（1）-（9）9個(gè)選項(xiàng)，無最優(yōu)解時(shí)有（10）和（11）兩個(gè)選項(xiàng)只顯示最優(yōu)解（SolutionSummary）約束條件結(jié)果（ConstraintSummary），比較約束條件兩端的值對(duì)價(jià)值系數(shù)進(jìn)行靈敏度分析（SensitivityAnalysisofOBJ）對(duì)約束條件右端常數(shù)項(xiàng)進(jìn)行靈敏度分析（SensitivityAnalysisofRHS）詳細(xì)結(jié)果報(bào)告（CombinedReport）參數(shù)分析（PerformParametricAnalysis）最終單純形表（FinalSimplexTableau）另一個(gè)基本最優(yōu)解（ObtainAlternateOptimal），存在無窮多最優(yōu)解時(shí)，系統(tǒng)給出另一個(gè)基本最優(yōu)解。顯示運(yùn)行時(shí)間以及迭代次數(shù)（ShowRunTimeandIteration）不可行性分析（InfeasibilityAnalysis）無界性分析（UnboundednessAnalysis）表1.17中列出了WinQSB中常用術(shù)語。表1.17常用術(shù)語含義Alternativesolutionexists存在替代解，有多重解Basicandnonbasicvariable基變量和非基變量Basis基Basisstatus基變量狀態(tài)，提示是否為基變量Branch-and-boundmethod分支定界法Cj-Zj檢驗(yàn)數(shù)Combinedreport組合報(bào)告Constraintsummary約束條件摘要Constraint約束條件Constraintdirection約束方向Constraintstatus約束狀態(tài)Decisionvariable決策變量Dualproblem對(duì)偶問題Enteringvariable入基（進(jìn)基）變量Feasiblearea可行域Feasiblesolution可行解Infeasible不可行Infeasibilityanalysis不可行性分析Leavingvariable出基變量Left-handside左端Lowerorupperbound下界或上界MinimumandmaximumallowableCj最優(yōu)解不變時(shí)，價(jià)值系數(shù)允許變化范圍MinimumandmaximumallowableRHS最優(yōu)基不變時(shí)，資源限量允許變化范圍Objectivefunction目標(biāo)函數(shù)Optimalsolution最優(yōu)解Parametricanalysis參數(shù)分析Rangeandslopeofparametricanalysis參數(shù)分析的區(qū)間和斜率Reducedcost約簡(jiǎn)成本（價(jià)值），檢驗(yàn)數(shù)，即當(dāng)非基變量增加一個(gè)單位是目標(biāo)函數(shù)的改變量Rangeoffeasibility可行區(qū)間Rangeofoptimality最優(yōu)區(qū)間Relaxedproblem松弛問題Relaxedoptimum松弛最優(yōu)Right-handside右端常數(shù)SensitivityanalysisofOBJcoefficients目標(biāo)函數(shù)系數(shù)的靈敏度分析SensitivityanalysisofRight-handside右端常數(shù)的靈敏度分析Shadowprice影子價(jià)格Simplexmethod單純形法Slack,surplusorartificialvariable松弛變量、剩余變量或人工變量Solutionsummary最優(yōu)解摘要Subtract(Add)morethanthisfromA(i,j)減少（增加）約束系數(shù)，調(diào)整工藝系數(shù)Totalcontribution總體貢獻(xiàn)，目標(biāo)函數(shù)cjxj的值Unboundedsolution無界解Unbounded無界

習(xí)題一A1.1對(duì)于下面每一個(gè)約束，畫出一個(gè)單獨(dú)的圖形表示出滿足這些約束的非負(fù)解。（a）（b）（c）（d）畫出滿足上面所有約束以及非負(fù)約束的可行域。1.2考慮目標(biāo)函數(shù)（a）分別畫出表示和相應(yīng)的目標(biāo)函數(shù)等值線。（b）寫出上面三條等值線的斜截式方程，比較它們的斜率以及在軸上的截距。1.3用圖解法求解下列線性規(guī)劃問題，并指出問題是具有唯一最優(yōu)解、無窮多最優(yōu)解、無界解還是無可行解。（a）（b）（c）1.4工廠利用原材料Q、R、S每月生產(chǎn)A、B兩種產(chǎn)品，每噸產(chǎn)品的原材料消耗量、每月可用原材料量及單件產(chǎn)品利潤(rùn)如表1.18所示。表1.18原材料每噸產(chǎn)品所需原材料可用原材料量產(chǎn)品A產(chǎn)品BQ212R122S334單件產(chǎn)品利潤(rùn)32（a）建立這個(gè)問題的線性規(guī)劃模型，使每月利潤(rùn)最大。(b)用圖解法求解該模型。1.5將下列線性規(guī)劃問題化為標(biāo)準(zhǔn)形式。（a）（b）（c）1.6設(shè)線性規(guī)劃取基，分別指出和所對(duì)應(yīng)的基變量和非基變量，求出基本解，并說明是不是可行解。1.7分別用圖解法和單純形法求解下面的線性規(guī)劃問題，指出單純形法迭代的每一步對(duì)應(yīng)于圖形上的哪一個(gè)極點(diǎn)。1.8用單純形法求下列線性規(guī)劃。（a）（b）（c）（d）1.9用大法求解下列線性規(guī)劃問題。（a）（b）1.10已知線性規(guī)劃的最優(yōu)單純形表如表1.19所示，求原問題中的參數(shù)以及最優(yōu)基B。表1.1