運(yùn)籌學(xué)緒論及第2章

2023/2/4廣東工業(yè)大學(xué)管理學(xué)院1管理運(yùn)籌學(xué)2023/2/4廣東工業(yè)大學(xué)管理學(xué)院2課程要求課堂紀(jì)律課前預(yù)習(xí)，課后復(fù)習(xí)。復(fù)習(xí)《線性代數(shù)》考核方式（平時(shí)成績20％，考試成績80％）遲到-5曠課-10回答問題+5請假-2不交作業(yè)-10遲交作業(yè)-52023/2/4廣東工業(yè)大學(xué)管理學(xué)院3以往成績分布學(xué)年專業(yè)學(xué)生總數(shù)不及格人數(shù)2009～2010第一學(xué)期07會(huì)計(jì)17102009～2010第二學(xué)期07財(cái)管15512010～2011第一學(xué)期08會(huì)計(jì)8512010～2011第二學(xué)期08財(cái)管14392011～2012第一學(xué)期09會(huì)計(jì)26182011～2012第二學(xué)期09財(cái)管7610財(cái)管2012～2013第一學(xué)期10會(huì)計(jì)8902014～2015第一學(xué)期13市營77？2023/2/4廣東工業(yè)大學(xué)管理學(xué)院4緒論什么是運(yùn)籌學(xué)運(yùn)籌學(xué)研究的基本特征和基本方法運(yùn)籌學(xué)的主要分支運(yùn)籌學(xué)與管理科學(xué)2023/2/4廣東工業(yè)大學(xué)管理學(xué)院5什么是運(yùn)籌學(xué)？《大英百科全書》《中國大百科全書》《辭?！贰吨袊髽I(yè)管理百科全書》英國——Operationalresearch美國——Operationsresearch2023/2/4廣東工業(yè)大學(xué)管理學(xué)院6經(jīng)濟(jì)學(xué)的基本問題：資源是有限的，而人的需求卻無窮無盡。所以經(jīng)濟(jì)學(xué)研究如何分配有限的資源去滿足無限的需求。管理學(xué)的基本問題：有限的資源分配后如何通過組織、控制和有效的利用資源，使有限的資源獲得最大的產(chǎn)出。資源投入轉(zhuǎn)換過程成果產(chǎn)出管理活動(dòng)2023/2/4廣東工業(yè)大學(xué)管理學(xué)院7運(yùn)籌學(xué)能夠?qū)?jīng)濟(jì)管理系統(tǒng)中的人力、物力、財(cái)力等資源進(jìn)行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，以實(shí)現(xiàn)最有效的管理。通常以最優(yōu)、最佳等作為決策目標(biāo)，避開最劣的方案。2023/2/4廣東工業(yè)大學(xué)管理學(xué)院8運(yùn)籌學(xué)的發(fā)展1945~1950年代創(chuàng)建時(shí)期1950年代成長時(shí)期1960年代至今普及和發(fā)展時(shí)期2023/2/4廣東工業(yè)大學(xué)管理學(xué)院9運(yùn)籌學(xué)的基本特征系統(tǒng)的整體觀念多學(xué)科的綜合應(yīng)用模型方法2023/2/4廣東工業(yè)大學(xué)管理學(xué)院10運(yùn)籌學(xué)的基本方法

——模型化的方法應(yīng)用步驟：分析與表述問題建立模型求解模型與優(yōu)化方案測試模型及對模型進(jìn)行必要的修正建立對解的有效控制方案的實(shí)施2023/2/4廣東工業(yè)大學(xué)管理學(xué)院11運(yùn)籌學(xué)的主要分支線性規(guī)劃(linearprogramming)非線性規(guī)劃(nonlinearprogramming)動(dòng)態(tài)規(guī)劃(dynamicprogramming)圖與網(wǎng)絡(luò)分析(graphtheoryandnetworkanalysis)存貯論(inventorytheory)排隊(duì)論(queuingtheory)對策論(gametheory)決策論(decisiontheory)2023/2/4廣東工業(yè)大學(xué)管理學(xué)院12運(yùn)籌學(xué)與管理科學(xué)國際上目前通行的說法：“運(yùn)籌學(xué)”與“管理科學(xué)(managementsciences)”在許多場合實(shí)際是指同一學(xué)科，不過前者強(qiáng)調(diào)方法而后者強(qiáng)調(diào)應(yīng)用。因此運(yùn)籌學(xué)是現(xiàn)代科學(xué)管理的基礎(chǔ)，從而在管理中有非常廣泛的應(yīng)用。生產(chǎn)計(jì)劃：生產(chǎn)作業(yè)的計(jì)劃、日程表的編排、合理下料、配料問題、物料管理等，追求利潤最大化和成本最小化庫存管理：多種物資庫存量的管理，庫存方式、庫存量等運(yùn)輸問題：確定最小成本的運(yùn)輸線路、物資的調(diào)撥、運(yùn)輸工具的調(diào)度以及建廠地址的選擇等人事管理：對人員的需求和使用的預(yù)測，確定人員編制、人員合理分配，建立人才評價(jià)體系等市場營銷：廣告預(yù)算、媒介選擇、定價(jià)、產(chǎn)品開發(fā)與銷售計(jì)劃制定等財(cái)務(wù)和會(huì)計(jì)：預(yù)測、貸款、成本分析、定價(jià)、證券管理、現(xiàn)金管理等***設(shè)備維修、更新，項(xiàng)目選擇、評價(jià)，工程優(yōu)化設(shè)計(jì)與管理等2023/2/4廣東工業(yè)大學(xué)管理學(xué)院14運(yùn)籌學(xué)方法使用情況(美)010203040506070統(tǒng)計(jì)計(jì)算機(jī)模擬網(wǎng)絡(luò)計(jì)劃線性規(guī)劃排隊(duì)論非線性規(guī)劃動(dòng)態(tài)規(guī)劃對策論從不使用有時(shí)使用經(jīng)常使用2023/2/4廣東工業(yè)大學(xué)管理學(xué)院15

運(yùn)籌學(xué)方法在中國使用情況(隨機(jī)抽樣)0102030405060708090統(tǒng)計(jì)計(jì)算機(jī)模擬網(wǎng)絡(luò)計(jì)劃線性規(guī)劃排隊(duì)論非線性規(guī)劃動(dòng)態(tài)規(guī)劃對策論從不使用有時(shí)使用經(jīng)常使用2023/2/4廣東工業(yè)大學(xué)管理學(xué)院16運(yùn)籌學(xué)在國內(nèi)或國外的推廣應(yīng)用前景是非常廣闊的。工商企業(yè)對運(yùn)籌學(xué)應(yīng)用的需求是很大的。在工商企業(yè)推廣運(yùn)籌學(xué)方面有大量的工作要做。2023/2/4廣東工業(yè)大學(xué)管理學(xué)院17由國際運(yùn)籌與管理科學(xué)協(xié)會(huì)（INFORMS）和它的管理科學(xué)實(shí)踐學(xué)會(huì)（CollegeforthePracticeoftheManagementSciences）主持評獎(jiǎng)的負(fù)有盛名的弗蘭茨·厄德曼（FranyEdlman）獎(jiǎng)，就是為獎(jiǎng)勵(lì)優(yōu)秀的運(yùn)籌學(xué)在管理中的應(yīng)用的成就設(shè)立的，該獎(jiǎng)每年舉行一次，在對大量富有競爭力的入圍者進(jìn)行艱苦的評審后，一般有六位優(yōu)勝者獲獎(jiǎng)。組織應(yīng)用Interface期刊號

每年效益（美元）聯(lián)合航空滿足乘客需求前提下,以最低成本進(jìn)行訂票及安排機(jī)場工作班次1-2/1986600萬Citgo石油優(yōu)化煉油程序及產(chǎn)品供應(yīng)、配送及營銷1-2/19877000萬荷馬特發(fā)展優(yōu)化商業(yè)區(qū)和辦公樓銷售程序1-2/19874000萬AT&T優(yōu)化商業(yè)用戶的電話銷售中心選址1-2/19904.06億標(biāo)準(zhǔn)品牌控制成品庫存（制定最優(yōu)再訂購點(diǎn)和訂購量，確保安全庫存）12/1981380萬施樂通過戰(zhàn)略調(diào)整，縮短維修機(jī)器的反應(yīng)時(shí)間和改進(jìn)維修人員的生產(chǎn)率11/1975第二部分生產(chǎn)率提高50%寶潔重新設(shè)計(jì)北美生產(chǎn)和分銷系統(tǒng)以降低成本并加快了市場進(jìn)入速度1-2/19972億法國國家鐵路制定最優(yōu)鐵路時(shí)刻表并調(diào)整鐵路日運(yùn)營量1-2/19981500萬Delta航空進(jìn)行上千個(gè)國內(nèi)航線的飛機(jī)優(yōu)化配置來最大化利潤1-2/19941億IBM重組全球供應(yīng)鏈，保持最小庫存的同時(shí)滿足客戶需求1-2/2000第一年7.5億Merit青銅制品公司安裝統(tǒng)計(jì)銷售預(yù)測和成品庫存管理系統(tǒng)，改進(jìn)客戶服務(wù)1-2/1993更優(yōu)的服務(wù)2023/2/4廣東工業(yè)大學(xué)管理學(xué)院19第二章線性規(guī)劃及單純形法2023/2/4廣東工業(yè)大學(xué)管理學(xué)院20學(xué)習(xí)內(nèi)容線性規(guī)劃問題及其數(shù)學(xué)模型圖解法單純形法原理單純形法計(jì)算步驟單純形法的進(jìn)一步討論應(yīng)用舉例2023/2/4廣東工業(yè)大學(xué)管理學(xué)院21第一節(jié)線性規(guī)劃及其數(shù)學(xué)模型問題的提出線性規(guī)劃的數(shù)學(xué)模型線性規(guī)劃的標(biāo)準(zhǔn)形式例1

美佳公司計(jì)劃制造I、II兩種家電產(chǎn)品，已知各制造1件分別占用的設(shè)備A、B的臺(tái)時(shí)、調(diào)試時(shí)間、調(diào)試工序及每天可用于這兩種家電的能力、各售出1件的獲利情況如下表所示。III每天可用能力設(shè)備A（h）設(shè)備B（h）調(diào)試工序（h）06152115245利潤（元）21問該公司應(yīng)每天制造兩種家電各多少件，使獲取的利潤最大?例2捷運(yùn)公司租借倉庫的問題月份1234所需倉庫面積(100m2)15102012合同租借期限1個(gè)月2個(gè)月3個(gè)月4個(gè)月合同期內(nèi)的租費(fèi)(元/100m2)2800450060007300試確定該公司簽訂租賃合同的最佳方案，使所付租借費(fèi)用最小?例1、例2的共同點(diǎn)

在現(xiàn)有各項(xiàng)資源條件的限制或約束下，如何確定方案，使預(yù)期目標(biāo)達(dá)到最優(yōu)。例1的資源限制：設(shè)備A、B與調(diào)試工序每天可用時(shí)數(shù)。目標(biāo)：總利潤最大例2的資源約束：租期內(nèi)每月所需的倉庫面積數(shù)。目標(biāo)：總租金最小2023/2/4廣東工業(yè)大學(xué)管理學(xué)院25155x2A約束：設(shè)備例1的數(shù)學(xué)模型2023/2/4廣東工業(yè)大學(xué)管理學(xué)院262023/2/4廣東工業(yè)大學(xué)管理學(xué)院27例2的數(shù)學(xué)模型2023/2/4廣東工業(yè)大學(xué)管理學(xué)院28模型的特征模型的三個(gè)要素（1）決策變量（2）目標(biāo)函數(shù)（3）約束條件線性規(guī)劃模型的特征（1）目標(biāo)函數(shù)是決策變量的線性函數(shù)（2）約束條件是含決策變量的線性等式或不等式2023/2/4廣東工業(yè)大學(xué)管理學(xué)院29線性規(guī)劃模型的一般形式2023/2/4廣東工業(yè)大學(xué)管理學(xué)院30線性規(guī)劃模型的一般形式（續(xù)1）決策變量：價(jià)值系數(shù)：資源常數(shù)：技術(shù)（工藝）系數(shù)：2023/2/4廣東工業(yè)大學(xué)管理學(xué)院31線性規(guī)劃模型的一般形式（續(xù)2）利用和號∑簡化模型的表示2023/2/4廣東工業(yè)大學(xué)管理學(xué)院32線性規(guī)劃模型的一般形式（續(xù)3）向量形式式中2023/2/4廣東工業(yè)大學(xué)管理學(xué)院33線性規(guī)劃模型的一般形式（續(xù)4）其中矩陣形式2023/2/4廣東工業(yè)大學(xué)管理學(xué)院34線性規(guī)劃模型的一般形式（續(xù)5）注：決策變量通常是非負(fù)的，但從數(shù)學(xué)意義上決策變量可以取非正的值，或取任何實(shí)數(shù)。2023/2/4廣東工業(yè)大學(xué)管理學(xué)院35線性規(guī)劃問題的標(biāo)準(zhǔn)形式2023/2/4廣東工業(yè)大學(xué)管理學(xué)院36標(biāo)準(zhǔn)形式的特征目標(biāo)函數(shù)為求最大值約束條件均為等式資源常數(shù)非負(fù)決策變量只能取非負(fù)值不具備上述所有特征的線性規(guī)劃問題稱為非標(biāo)準(zhǔn)形式的線性規(guī)劃問題2023/2/4廣東工業(yè)大學(xué)管理學(xué)院37化線性規(guī)劃問題為標(biāo)準(zhǔn)形式的方法（1）目標(biāo)函數(shù)為求最小值的，即將目標(biāo)函數(shù)用其相反數(shù)代替，得到新的目標(biāo)函數(shù)，即令則求原目標(biāo)函數(shù)的最小值問題等價(jià)于求新目標(biāo)函數(shù)的最大值問題2023/2/4廣東工業(yè)大學(xué)管理學(xué)院38化線性規(guī)劃問題為標(biāo)準(zhǔn)形式的方法（續(xù)1）（2）右端常數(shù)小于零，即將該約束條件兩端同乘（－1）（3）約束條件為不等式“”型，左端加上一個(gè)非負(fù)的松弛變量“”型，左端減去一個(gè)非負(fù)的剩余變量松弛變量和剩余變量在目標(biāo)函數(shù)中的系數(shù)為零2023/2/4廣東工業(yè)大學(xué)管理學(xué)院39（4）取值無約束的變量。用兩個(gè)非負(fù)變量的差表示該變量。（5）取非正值的變量。用其相反數(shù)代替該變量化線性規(guī)劃問題為標(biāo)準(zhǔn)形式的方法（續(xù)2）2023/2/4廣東工業(yè)大學(xué)管理學(xué)院40線性規(guī)劃問題要處理的內(nèi)容x1,x3右端常數(shù)不等式不等式最小化目標(biāo)處理后2023/2/4廣東工業(yè)大學(xué)管理學(xué)院41練習(xí)P432.2

學(xué)號尾數(shù)為奇數(shù)的同學(xué)做（1）學(xué)號尾數(shù)為偶數(shù)的同學(xué)做（2）2023/2/4廣東工業(yè)大學(xué)管理學(xué)院42第二節(jié)圖解法有關(guān)概念滿足所有約束條件的一組決策變量x1,x2,…,xn稱為LP問題的可行解所有可行解的集合稱為可行域使得目標(biāo)函數(shù)值達(dá)到最優(yōu)的可行解稱為LP問題的最優(yōu)解求解LP問題就是求出其最優(yōu)解2023/2/4廣東工業(yè)大學(xué)管理學(xué)院43

圖解法及其目的圖解法即通過平面作圖的方法求解線性規(guī)劃，適用于只含兩個(gè)決策變量的簡單LP問題。圖解法的目的有二：一是利用它來判別LP問題求解的可能結(jié)局。二是在LP問題最優(yōu)解存在時(shí)，求出最優(yōu)解。采用圖解法時(shí)通常無須將LP問題化為標(biāo)準(zhǔn)形式2023/2/4廣東工業(yè)大學(xué)管理學(xué)院44圖解法步驟：在平面上建立直角坐標(biāo)系圖示約束條件，找出可行域圖示目標(biāo)函數(shù)尋找最優(yōu)解2023/2/4廣東工業(yè)大學(xué)管理學(xué)院45例1Maxz=2x1+x2s.t.5x2≤156x1+2x2

≤24

x1+x2≤5x1,x2≥0x2=33x1+x2=12x1+x2=5最優(yōu)解可行域x1x22023/2/4廣東工業(yè)大學(xué)管理學(xué)院46線性規(guī)劃問題幾種可能的解有唯一的最優(yōu)解有無窮多個(gè)最優(yōu)解無界解無解（無可行解）2023/2/4廣東工業(yè)大學(xué)管理學(xué)院47由圖解法得到的啟示LP問題的解存在4種可能的情況若LP問題的可行域非空，則必為凸集若LP問題的最優(yōu)解存在，則最優(yōu)解或最優(yōu)解之一是可行域的頂點(diǎn)LP問題的求解思路先找出可行域的任一頂點(diǎn)，計(jì)算該頂點(diǎn)處的目標(biāo)函數(shù)值；比較周圍相鄰頂點(diǎn)的目標(biāo)函數(shù)值是否比這個(gè)值大，如果為否，則該頂點(diǎn)為最優(yōu)解（或最優(yōu)解之一）對應(yīng)的點(diǎn)，否則轉(zhuǎn)到比這個(gè)點(diǎn)目標(biāo)函數(shù)值更大的頂點(diǎn)，重復(fù)上述過程，直到找出目標(biāo)函數(shù)值最大的頂點(diǎn)為止。2023/2/4廣東工業(yè)大學(xué)管理學(xué)院48練習(xí)P432.12023/2/4廣東工業(yè)大學(xué)管理學(xué)院49第三節(jié)單純形法原理線性規(guī)劃解的基本概念考慮標(biāo)準(zhǔn)形式的線性規(guī)劃問題可行解——滿足所有約束條件的解X=(x1,x2,…,xn)T,稱為LP問題的可行解。所有可行解的集合稱為可行域。最優(yōu)解——使得目標(biāo)函數(shù)達(dá)到最大值的可行解稱為最優(yōu)解。LP問題的可行域是一個(gè)凸集。凸集及其頂點(diǎn)凸集——如果一個(gè)非空集合中任意兩點(diǎn)的連線段上所有點(diǎn)仍屬于該集合，則稱該集合為凸集。凸集的頂點(diǎn)——若凸集中的一個(gè)點(diǎn)不是任何另外兩點(diǎn)連線段上的點(diǎn)，則稱該點(diǎn)為這個(gè)凸集的頂點(diǎn)。凸集不是凸集頂點(diǎn)基——設(shè)A為約束方程組的m╳n階系數(shù)矩陣（通常總假定n>m，且A的秩=m），若B是A的一個(gè)m╳m階的滿秩子矩陣，則稱B是LP問題的一個(gè)基。若B是LP問題的一個(gè)基，則它的每一個(gè)列向量稱為基向量，與基向量對應(yīng)的變量稱為基變量LP問題的基本概念（續(xù)1）LP問題的基本概念（續(xù)2）基解在約束方程組 中令所有的非基變量xm+1=xm+2=…=xn=0,則由于剩下的變量（基變量）構(gòu)成的方程組的系數(shù)行列式|B|≠0，因此約束方程組此時(shí)有唯一的解XB=（x1,x2,…,xm,0,…,0)T這個(gè)解稱為LP問題的（對應(yīng)基B的）基解。很明顯，對應(yīng)著不同的基，LP問題有不同的基解。因此LP問題的基解不是唯一的，但總數(shù)不超過 。此外基解不一定是可行解。LP問題的基本概念（續(xù)3）基可行解——滿足非負(fù)約束條件的基解稱為

基可行解?？尚谢獙?yīng)著基可行解的基稱為可行基很明顯LP問題的基可行解是有限的。并且每一個(gè)基可行解對應(yīng)著可行域的一個(gè)頂點(diǎn)。2023/2/4廣東工業(yè)大學(xué)管理學(xué)院54練習(xí)P432.32023/2/4廣東工業(yè)大學(xué)管理學(xué)院55幾個(gè)基本定理定理1：若LP問題存在可行解，則問題的可行域?yàn)橥辜ɡ?：LP問題的基可行解對應(yīng)著LP問題可行域的頂點(diǎn)定理3：若LP問題有最優(yōu)解，一定存在一個(gè)基可行解是最優(yōu)解2023/2/4廣東工業(yè)大學(xué)管理學(xué)院56單純形法迭代原理單純形法迭代步驟找出一個(gè)基可行解是否為最優(yōu)解停止轉(zhuǎn)換到相鄰的基可行解，并使目標(biāo)函數(shù)增大開始YN2023/2/4廣東工業(yè)大學(xué)管理學(xué)院571.確定初始基可行解基可行解求基解求解線性方程組找基B或基變量2023/2/4廣東工業(yè)大學(xué)管理學(xué)院58初始基可行解通常都是從一種特殊的基可行解出發(fā)求解LP問題，這一特殊的基可行解稱為初始基可行解。初始基可行解對應(yīng)的基，也稱初始可行基，它具有特定的形式，它是單位矩陣或者由單位矩陣經(jīng)過變換列以后得到的矩陣。相應(yīng)的基變量稱為初始基變量，它是一組變量，具有特點(diǎn)：共有m個(gè)變量，恰好每個(gè)約束方程包含一個(gè)變量，且該變量的系數(shù)為1。2023/2/4廣東工業(yè)大學(xué)管理學(xué)院59已知初始基變量，求初始基可行解以例1為例說明求法。添加松弛變量后可標(biāo)準(zhǔn)化為其中x3,x4,x5為初始基變量，初始基可行解為2023/2/4廣東工業(yè)大學(xué)管理學(xué)院602.判別最優(yōu)性不難發(fā)現(xiàn)這時(shí)每個(gè)初始基變量取的值恰好就是包含這個(gè)變量的約束方程的右端常數(shù)值，非基變量取的值為零。將這個(gè)解代入到目標(biāo)函數(shù)，就可得到這個(gè)解對應(yīng)的目標(biāo)函數(shù)值。2023/2/4廣東工業(yè)大學(xué)管理學(xué)院61目標(biāo)函數(shù)目前的值為零，很明顯如果能使的變量x1或x2取正值的話，目標(biāo)函數(shù)的值還可以增加。所以目標(biāo)函數(shù)還未達(dá)到其最大值。一般地，若目標(biāo)函數(shù)已經(jīng)表示成了非基變量的函數(shù)，且其中非基變量的系數(shù)中還有正數(shù)，則目標(biāo)函數(shù)還可能增大。這時(shí)目標(biāo)函數(shù)中各變量的系數(shù)稱為檢驗(yàn)數(shù)。這時(shí)目標(biāo)函數(shù)的表達(dá)式為2023/2/4廣東工業(yè)大學(xué)管理學(xué)院623.旋轉(zhuǎn)若基可行解不是最優(yōu)解，則需要轉(zhuǎn)到一個(gè)相鄰的基可行解，并使得目標(biāo)函數(shù)值增加。所謂相鄰的基可行解是指兩個(gè)基可行解只有一個(gè)基變量不同而其它的基變量都相同。要從一個(gè)基可行解轉(zhuǎn)到與它相鄰的基可行解，意味著需要將一個(gè)非基變量變成基變量，而且將一個(gè)原來的基變量變?yōu)榉腔兞?，前者稱為換入變量，后者稱為換出變量。2023/2/4廣東工業(yè)大學(xué)管理學(xué)院63確定換入變量目的：新的基變量換入后，會(huì)使目標(biāo)函數(shù)值增大（通常還希望增加的越大越好）因此選擇在目標(biāo)函數(shù)中系數(shù)為正值的非基變量作為換入變量，通常取在目標(biāo)函數(shù)中最大的正系數(shù)對應(yīng)的非基變量為換入變量，即取最大的正檢驗(yàn)數(shù)對應(yīng)的非基變量為換入變量。換入變量為x1對例1，這時(shí)目標(biāo)函數(shù)為2023/2/4廣東工業(yè)大學(xué)管理學(xué)院64確定換出變量由于基變量只有m個(gè)，因此將一個(gè)非基變量變?yōu)榛兞亢?，必須將一個(gè)原來的基變量變?yōu)榉腔兞浚@個(gè)變量稱為換出變量。換出變量與換入變量是密切相關(guān)的。設(shè)xk是換入變量。若xk>0，則第i個(gè)約束條件可以寫成并且由于其余的非基變量保持零值，因此2023/2/4廣東工業(yè)大學(xué)管理學(xué)院65由此可見為保證xi≥0，就必須從而對所有的i，若aik>0，則若確定xk為換入變量，則可估計(jì)xk的取值，使得：其余的決策變量都取非負(fù)值；并且目標(biāo)函數(shù)得到盡可能的增加。對前者，只須對所有的i成立，即為了使目標(biāo)函數(shù)盡可能增加，顯然應(yīng)該有設(shè)i=l(1ln)時(shí)，上式右端達(dá)到最小值。由于因此xl=0。這意味著xl可以是非基變量。因此取xl為換出變量。也就是取使得成立的l對應(yīng)的基變量xl為換出變量。對例1由于已經(jīng)確定了x1是換入變量。而因此x4是換出變量24/65/1確定換出變量等價(jià)于確定了一組新的基變量，為了方便地求出相應(yīng)的基解，接下來將進(jìn)行如下的運(yùn)算：將這組新的基變量的系數(shù)矩陣化為單位矩陣（或單位矩陣交換列后得到的矩陣），這等價(jià)于使得這組基變量中每個(gè)變量只出現(xiàn)在一個(gè)方程中并且在該方程中的系數(shù)為1，這稱為旋轉(zhuǎn)運(yùn)算。旋轉(zhuǎn)運(yùn)算可以利用對約束方程組進(jìn)行加減消元法完成。2023/2/4廣東工業(yè)大學(xué)管理學(xué)院69對例1的約束方程組第2式6第3式–第2式2023/2/4廣東工業(yè)大學(xué)管理學(xué)院70由此可以立即得到新的基解為很明顯，它是基可行解。為了判斷這一新的基可行解是否為最優(yōu)解，需要將原目標(biāo)函數(shù)改寫為新的非基變量的函數(shù)。原目標(biāo)函數(shù)為由代入目標(biāo)函數(shù)，得即其中系數(shù)1/3，-1/3分別是非基變量x2，x4的檢驗(yàn)數(shù)。因此對應(yīng)于這一新的基可行解，目標(biāo)函數(shù)值為z=8。問題是這一目標(biāo)函數(shù)值是否為最優(yōu)的目標(biāo)函數(shù)值。由于x2的系數(shù)（檢驗(yàn)數(shù)）為1/3，是正數(shù)，因此如果能使x2取正數(shù)，則目標(biāo)函數(shù)還能增加。因此該基可行解仍不是最優(yōu)解。一般地，對一個(gè)基可行解而言，若非基變量的檢驗(yàn)數(shù)中存在正數(shù)，則該解不是最優(yōu)解；否則它一定是最優(yōu)解。2023/2/4廣東工業(yè)大學(xué)管理學(xué)院72單純形法求解過程小結(jié)（1）求出初始基可行解（2）通過非基變量在目標(biāo)函數(shù)中的系數(shù)（檢驗(yàn)數(shù)）是否都小于或等于零，判別該基可行解是否為最優(yōu)解。若是，結(jié)束運(yùn)算；否則進(jìn)行下一步。（3）確定換入變量。取最大的正檢驗(yàn)數(shù)對應(yīng)的非基變量為換入變量。2023/2/4廣東工業(yè)大學(xué)管理學(xué)院73單純形法求解過程小結(jié)（續(xù)）（4）確定換出變量。用換入變量在各方程中的正的系數(shù)去除該方程的右端常數(shù)，在除得的商中取最小者，該最小商所在方程中的基變量就是換出變量。由此得到一組新的基變量。（5）旋轉(zhuǎn)運(yùn)算。將新的基變量在約束方程中的系數(shù)矩陣化為單位矩陣（或單位矩陣交換列后的矩陣）?；氐降冢?）步。2023/2/4廣東工業(yè)大學(xué)管理學(xué)院74單純形表的方法單純形法的所有運(yùn)算實(shí)際上都可歸結(jié)為對LP模型的目標(biāo)函數(shù)系數(shù)以及約束方程組的系數(shù)（矩陣）的運(yùn)算。為了簡化運(yùn)算過程，并使運(yùn)算過程程序化。人們構(gòu)造了單純形表來進(jìn)行運(yùn)算。0611000100011524552121x3x4x5x1x2x3x4x5bXb00021000Cb初始單純形表例1中的模型化為標(biāo)準(zhǔn)形式后為σj21000CbXbbx1x2x3x4x5000x3x4x515245051006201011001σj21000基變量目標(biāo)函數(shù)系數(shù)右端常數(shù)基變量在目標(biāo)函數(shù)中的系數(shù)約束方程組系數(shù)矩陣檢驗(yàn)數(shù)基可行解：目標(biāo)函數(shù)值為：z=0這個(gè)基可行解不是最優(yōu)解21000CbXbbx1x2x3x4x5000x3x4x515245051006201011001σj21000換入變量24/65/1換出變量主元21000CbXbbx1x2x3x4x5020x3x1x515410510011/301/6002/30-1/61σj01/30-1/3021000CbXbbx1x2x3x4x5020x3x1x515410510011/301/6002/30-1/6101/30-1/30基可行解為：目標(biāo)函數(shù)值為：z=815/54/(1/3)1/(2/3)21000CbXbbx1x2x3x4x5021x3x1x215/27/23/20015/4-15/21001/4-1/2010-1/43/2000-1/4-1/221000CbXbbx1x2x3x4x5021x3x1x215/27/23/20015/4-15/21001/4-1/2010-1/43/2000-1/4-1/2最優(yōu)解為：最優(yōu)目標(biāo)函數(shù)值為：z=8.5因此對例1中的問題，最優(yōu)的生產(chǎn)計(jì)劃安排是每天生產(chǎn)甲家電3.5件，乙家電1.5件，每天可以得到的最大利潤為8.5元。（按此計(jì)劃安排生產(chǎn)，每天設(shè)備A可富余7.5臺(tái)時(shí)）21000CbXbbx1x2x3x4x5000x3x4x51524505100620101100124/65/1σj21000021x3x1x215/27/23/20015/415/21001/4-1/2010-1/43/28?000-1/4-1/2020x3x1x515410510011/301/6002/30-1/6115/54/(1/3)1/(2/3)σj01/30-1/30初始單純形表最終單純形表單純形表合并的表示2023/2/4廣東工業(yè)大學(xué)管理學(xué)院81無窮多個(gè)最優(yōu)解檢驗(yàn)數(shù)的實(shí)際意義：檢驗(yàn)數(shù)是非基變量每增加一個(gè)單位，目標(biāo)函數(shù)的增加值。因此如果在最終單純形表中，當(dāng)所有的檢驗(yàn)數(shù)都小于或等于零，并且存在非基變量的檢驗(yàn)數(shù)等于零的情況時(shí)，LP問題存在無窮多個(gè)最優(yōu)解。實(shí)際上，此時(shí)可選擇檢驗(yàn)數(shù)為零的非基變量為換入變量，迭代到一個(gè)新的基可行解，它的目標(biāo)函數(shù)值等于最優(yōu)解的目標(biāo)函數(shù)值，從而也是最優(yōu)解。因此有無窮多個(gè)最優(yōu)解。2023/2/4廣東工業(yè)大學(xué)管理學(xué)院82無界解若換入變量（或正檢驗(yàn)數(shù)）所在列的所有系數(shù)都小于或等于零，則LP問題為無界解。例如，如果單純形表為21000CbXbbx1x2x3x4x5000x3x4x51524505100-62010-11001σj21000實(shí)際上換入變量為x1，相應(yīng)的約束方程組為由于x2仍是非基變量，因此由此可見，不管x1取什么樣的正數(shù)，x3、x4、x5都保持非負(fù)，這意味著x1的取值沒有任何限制，從而目標(biāo)函數(shù)值可以無限增加。2023/2/4廣東工業(yè)大學(xué)管理學(xué)院84最小化的線性規(guī)劃問題在標(biāo)準(zhǔn)形式的LP模型中，關(guān)于目標(biāo)函數(shù)的要求可以降低，即不必要求目標(biāo)函數(shù)是求最大值，而可以是求最小值。對最小化的LP問題，單純形法求解過程有兩處值得注意的修改。1.最優(yōu)解的判別：當(dāng)所有檢驗(yàn)數(shù)大于或等于0時(shí)，單純形表給出的解是最優(yōu)解2.換入變量的確定：最小的負(fù)檢驗(yàn)數(shù)對應(yīng)的變量為換入變量2023/2/4廣東工業(yè)大學(xué)管理學(xué)院85例求解如下的最小化LP問題2023/2/4廣東工業(yè)大學(xué)管理學(xué)院87單純形法的進(jìn)一步討論如果約束方程不存在前面所述的初始基變量，處理的方式是通過添加人工變量來得到所需要的初始基變量。添加人工變量的方法是，先化約束條件為標(biāo)準(zhǔn)形式。然后在不含初始基變量的方程的左邊人為地加上一個(gè)非負(fù)變量（人工變量），作為該方程的初始基變量，不同的方程添加的人工變量也不同。2023/2/4廣東工業(yè)大學(xué)管理學(xué)院88人工變量的處理人工變量是由于應(yīng)用單純形法求解的需要人為添加的變量，因此在最終單純形表的基變量中不應(yīng)包含人工變量。因此人工變量應(yīng)該逐個(gè)從基變量中換出來。為了使人工變量能從基變量中逐個(gè)換出，可采用如下兩種方法：大M法和兩階段法。大M法這種方法是（對最大化的LP問題）通過將人工變量在目標(biāo)函數(shù)中的系數(shù)取成絕對值充分大的負(fù)數(shù)，因而迫使其盡快從基變量中換出。這樣的負(fù)數(shù)通常寫成“-M”。具體的做法是對最大化的LP問題，人工變量在目標(biāo)函數(shù)中的系數(shù)取為“-M”對最小化的LP問題，人工變量在目標(biāo)函數(shù)中的系數(shù)取為“M”然后再用單純形法求解。若最優(yōu)解的基變量中仍含有人工變量，則LP問題為無可行解。給定LP問題化成標(biāo)準(zhǔn)形式后為不存在前面那種初始基變量，因此要添加人工變量添加人工變量，并用大M法處理人工變量，模型變?yōu)槿缓笥脝渭冃畏ㄇ蠼庠搯栴}-30100-M-MCbXbbx1x2x3x4x5x6x70-M-Mx4x6x74191111000-21-10-1100310001σj-2M-34M10-M0000-Mx4x2x731630211-10-21-10-11060403-31σj6M-304M+103M-4M0-30100-M-MCbXbbx1x2x3x4x5x6x700-3x4x2x10310001-1/2-1/2-1/2011/30001/3102/301/21/21/6σj00303/2-M-3/2-M+1/2001x4x2x305/23/20001-1/2-1/2-1/2-1/2100-1/41/41/43/20103/4-3/41/4σj-9/2000-3/4-M+3/4-M-1/4最優(yōu)解為最優(yōu)目標(biāo)函數(shù)值為2023/2/4廣東工業(yè)大學(xué)管理學(xué)院94兩階段法兩階段法：添加了人工變量后，分兩個(gè)階段來求解LP問題。第一階段：求解輔助的LP問題。輔助的LP問題構(gòu)造如下：約束條件就是原來的（添加了人工變量后）條件，目標(biāo)函數(shù)是所有人工變量之和，對這樣的目標(biāo)函數(shù)求最小值。若第一階段的目標(biāo)函數(shù)的最優(yōu)值不等于零，則原LP問題無可行解，否則進(jìn)入第二階段。第二階段：將第一階段的最終單純形表中的人工變量去掉，并將目標(biāo)函數(shù)系數(shù)換成原LP問題的目標(biāo)函數(shù)系數(shù)，然后以這樣得到的單純形表為初始單純形表，用單純形法求解原LP問題。2023/2/4廣東工業(yè)大學(xué)管理學(xué)院96首先寫出輔助的LP問題現(xiàn)在用單純形法求解該輔助LP問題，注意它為最小化問題。既可直接求解，也可轉(zhuǎn)化為最大化問題求解。0000011CbXbbx1x2x3x4