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

Chapter1線性規(guī)劃與單純形法LinearProgrammingandSimplexAlgorithm運(yùn)籌學(xué)OperationsResearch1.線性規(guī)劃問(wèn)題及其數(shù)學(xué)模型2.線性規(guī)劃問(wèn)題的幾何意義3.單純形法4.單純形法的計(jì)算步驟5.單純形法的進(jìn)一步討論6.應(yīng)用舉例

線性規(guī)劃是運(yùn)籌學(xué)的一個(gè)重要分支。自1947年丹捷格〔〕提出了線性規(guī)劃問(wèn)題求解的方法——單純形法之后，線性規(guī)劃在理論上趨向成熟，在實(shí)用中日益廣泛與深入。特別是在計(jì)算機(jī)能處理成千上萬(wàn)個(gè)約束條件和決策變量的線性規(guī)劃問(wèn)題之后，線性規(guī)劃的適用領(lǐng)域更為廣泛。從解決技術(shù)問(wèn)題的最優(yōu)化設(shè)計(jì)到工業(yè)、農(nóng)業(yè)、商業(yè)、交通運(yùn)輸業(yè)、軍事、經(jīng)濟(jì)方案和管理決策等領(lǐng)域都可以發(fā)揮作用。引言線性規(guī)劃研究的問(wèn)題：如何合理地利用有限的人力、物力、財(cái)力等資源，以便得到最好的經(jīng)濟(jì)效果。1.1問(wèn)題的提出1.1問(wèn)題的提出例1某工廠在方案期內(nèi)要安排生產(chǎn)I、II兩種產(chǎn)品，生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種原材料的損耗，如表1.1所示。III設(shè)備原材料A原材料B1402048臺(tái)時(shí)16kg12kg表1-1該工廠每生產(chǎn)一件產(chǎn)品Ⅰ可獲利2元，每生產(chǎn)一件產(chǎn)品Ⅱ可獲利3元，問(wèn)應(yīng)如何安排方案使該工廠獲利最多？用數(shù)學(xué)關(guān)系式描述這個(gè)問(wèn)題1.1問(wèn)題的提出1.1問(wèn)題的提出得到本問(wèn)題的數(shù)學(xué)模型為:這就是一個(gè)最簡(jiǎn)單的線性規(guī)劃模型。

例2

靠近某河流有兩個(gè)化工廠(見(jiàn)圖1-1)，流經(jīng)第一化工廠的河流流量為每天500萬(wàn)立方米，在兩個(gè)工廠之間有一條流量為每天200萬(wàn)立方米的支流。

化工廠1每天排放含有某種有害物質(zhì)的工業(yè)污水2萬(wàn)立方米，化工廠2每天排放的工業(yè)污水為1.4萬(wàn)立方米。從化工廠1排出的污水流到化工廠2前，有20%可自然凈化。根據(jù)環(huán)保要求，河流中工業(yè)污水的含量應(yīng)不大于0.2%。因此兩個(gè)工廠都需處理一局部工業(yè)污水。化工廠1處理污水的本錢是1000元/萬(wàn)立方米,化工廠2處理污水的本錢是800元/萬(wàn)立方米。問(wèn):在滿足環(huán)保要求的條件下，每廠各應(yīng)處理多少工業(yè)污水，使兩個(gè)工廠處理工業(yè)污水的總費(fèi)用最小。1.1問(wèn)題的提出設(shè)第一化工廠每天處理工業(yè)污水x1萬(wàn)立方米，第二化工廠每天處理工污水x2萬(wàn)立方米。從第一化工廠到第二化工廠之間，河流中工業(yè)污水含量不大于0.2%，由此可得近似關(guān)系式流經(jīng)第二化工廠后，河流中的工業(yè)污水含量仍要不大于0.2%，這時(shí)有近似關(guān)系式1.1問(wèn)題的提出建模型之前的分析和計(jì)算1.1問(wèn)題的提出得到本問(wèn)題的數(shù)學(xué)模型為：1.1問(wèn)題的提出上述兩個(gè)問(wèn)題具有的共同特征：每一個(gè)線性規(guī)劃問(wèn)題都用一組決策變量(x1,x2,…,xn)表示某一方案，這組決策變量的值代表一個(gè)具體方案。一般這些變量的取值是非負(fù)且連續(xù)的；都有關(guān)于各種資源和資源使用情況的技術(shù)數(shù)據(jù)，創(chuàng)造新價(jià)值的數(shù)據(jù)；存在可以量化的約束條件，這些約束條件可以用一組線性等式或線性不等式來(lái)表示;都有一個(gè)到達(dá)某一目標(biāo)的要求，可用決策變量的線性函數(shù)(稱為目標(biāo)函數(shù))來(lái)表示。按問(wèn)題的要求不同，要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化或最小化。線性規(guī)劃模型的一般形式1.1問(wèn)題的提出決策變量及各類系數(shù)之間的對(duì)應(yīng)關(guān)系1.1問(wèn)題的提出1.2圖解法例1是一個(gè)二維線性規(guī)劃問(wèn)題，因而可用作圖法直觀地進(jìn)行求解。1.2圖解法目標(biāo)值在〔4，2〕點(diǎn)，到達(dá)最大值141.2圖解法〔1〕無(wú)窮多最優(yōu)解(多重最優(yōu)解)，見(jiàn)圖1-4。〔2〕無(wú)界解，見(jiàn)圖1-5-1?！?〕無(wú)可行解，見(jiàn)圖1-5-2。通過(guò)圖解法，可觀察到線性規(guī)劃的解可能出現(xiàn)的幾種情況：1.2圖解法目標(biāo)函數(shù)maxz=2x1+4x2

圖1-4無(wú)窮多最優(yōu)解〔多重最優(yōu)解〕1.2圖解法圖1-5-1無(wú)界解1.2圖解法當(dāng)存在相互矛盾的約束條件時(shí)，線性規(guī)劃問(wèn)題的可行域?yàn)榭占＠?，如果在?的數(shù)學(xué)模型中增加一個(gè)約束條件:那么該問(wèn)題的可行域即為空集，即無(wú)可行解.無(wú)可行解的情形1.2圖解法增加的約束條件圖1-5-2不存在可行域1.2圖解法——在邊界，而且是在某個(gè)頂點(diǎn)上獲得思考：1〕線性規(guī)劃的可行域是一個(gè)什么形狀？2〕最優(yōu)解在什么位置獲得？——多邊形，而且是“凸”的多邊形結(jié)論：1.2圖解法問(wèn)題：性質(zhì)2有何重要意義？1.3線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式

1.3線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式用向量形式表示的標(biāo)準(zhǔn)形式線性規(guī)劃1.3線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式

用矩陣形式表示的標(biāo)準(zhǔn)形式線性規(guī)劃1.3線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式

這時(shí)只需將目標(biāo)函數(shù)最小化變換為求目標(biāo)函數(shù)最大化，。（1）若要求目標(biāo)函數(shù)實(shí)現(xiàn)極小化，即必須注意，盡管以上兩個(gè)問(wèn)題的最優(yōu)解相同，但它們最優(yōu)解的目標(biāo)函數(shù)值卻相差一個(gè)符號(hào)。于是得到即令如何將一般線性規(guī)劃轉(zhuǎn)化為標(biāo)準(zhǔn)形式的線性規(guī)劃1.3線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式

引進(jìn)一個(gè)松弛變量，把原不等式約束用兩個(gè)約束來(lái)等價(jià)地替換設(shè)約束條件為〔2〕約束方程為不等式有兩種情況：一種是約束方程為“≤〞不等式，那么可在“≤〞不等式的左端參加非負(fù)松弛變量，把原“≤〞不等式變?yōu)榈仁健?.3線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式

另一種是約束方程為“≥〞不等式，那么可在“≥〞不等式的左端減去一個(gè)非負(fù)剩余變量〔也可稱松弛變量〕，把原“≥〞不等式變?yōu)榈仁健ＲM(jìn)一個(gè)剩余變量，把原不等式約束用兩個(gè)約束來(lái)等價(jià)地替換設(shè)約束條件為1.3線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式

〔4〕在標(biāo)準(zhǔn)形式中，要求約束條件的右端項(xiàng)bi>0，否那么等式兩端乘以-1。下面舉例說(shuō)明。可以令，其中。即用兩個(gè)非負(fù)變量之差來(lái)表示一個(gè)無(wú)符號(hào)限制的變量，當(dāng)然的符號(hào)取決于和的相對(duì)大小。（3）若存在取值無(wú)約束的變量1.3線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式

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

例3將例1的數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式的線性規(guī)劃。例1的數(shù)學(xué)模型在參加了松馳變量后變?yōu)槔?將下述線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形式線性規(guī)劃(1)用x4?x5替換x3，其中x4，x5≥0；(2)在第一個(gè)約束不等式左端參加松弛變量x6；(3)在第二個(gè)約束不等式左端減去剩余變量x7；(4)令z′=?z，將求minz改為求maxz′即可得到該問(wèn)題的標(biāo)準(zhǔn)型。1.3線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式

例4例4的標(biāo)準(zhǔn)型1.3線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式

1.4線性規(guī)劃問(wèn)題解的概念可行解滿足約束條件（1-5）、（1-6）式的解稱為線性規(guī)劃問(wèn)題的可行解，其中使目標(biāo)函數(shù)達(dá)到最大值的可行解稱為最優(yōu)解?？紤]LP的標(biāo)準(zhǔn)型稱為基向量，與基向量相對(duì)應(yīng)的變量稱為基變量，否則稱為非基變量。設(shè)A是約束方程組的維系數(shù)矩陣，其秩為m。B是A中m階非奇異子矩陣(|B|≠0)，那么稱B是線性規(guī)劃問(wèn)題的一個(gè)基，這就是說(shuō)，矩陣B是由A中m個(gè)線性無(wú)關(guān)的列向量組成。為不失一般性,可設(shè)B是A中的前m列，即2基1.4線性規(guī)劃問(wèn)題解的概念注：〔1〕對(duì)應(yīng)于給定的基B，基解是唯一的。〔2〕基解中非基變量取零值，非零分量的數(shù)目不超過(guò)m。〔3〕基解一定滿足等式約束，但不一定滿足非負(fù)約束。稱為對(duì)應(yīng)于基B的基解。令所有非基變量，得到因B可逆，該方程有唯一解。把約束方程〔1-5〕式寫成1.4線性規(guī)劃問(wèn)題解的概念例在下述線性規(guī)劃問(wèn)題中列出全部的基并確定相應(yīng)的基解。解：將該線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形：只要從A的列向量中找出3個(gè)線性無(wú)關(guān)的列向量就組成該線性規(guī)劃問(wèn)題的一個(gè)基。1.4線性規(guī)劃問(wèn)題解的概念取A的第一、二、三列組成子矩陣易見(jiàn)，故B1是該線性規(guī)劃問(wèn)題的一個(gè)基。令非基變量，則約束方程變?yōu)榛兞繛椋腔兞?。令非基變量為零，求解線性方程組，就可找出全部基解。解得這里X〔1〕不滿足非負(fù)約束，故不是可行解。1.4線性規(guī)劃問(wèn)題解的概念取A的第一、四、五列得到基，相應(yīng)地基解取A的第一、三、五列得到基，相應(yīng)地基解類似地取A的第一、二、四列得到基，相應(yīng)地基解取A的第一、二、五列得到基，相應(yīng)地基解1.4線性規(guī)劃問(wèn)題解的概念對(duì)于A的第一、三、四列組成的矩陣易見(jiàn)，故不能作成一組基。取A的第二、三、四列得到基相應(yīng)地基解取A的第二、四、五列得到基相應(yīng)地基解取A的第三、四、五列得到基，相應(yīng)地基解同理，也不能作成一組基。1.4線性規(guī)劃問(wèn)題解的概念〔1〕基解的數(shù)目最多是個(gè)?！?〕基解中非零分量的個(gè)數(shù)小于m個(gè)時(shí)，該基解是退化解。3基可行解滿足非負(fù)約束條件的基解稱為基可行解。以下討論時(shí)，假設(shè)不出現(xiàn)退化的情況，即基解中非零分量恰為m個(gè)。說(shuō)明：4可行基對(duì)應(yīng)于基可行解的基稱為可行基。1.4線性規(guī)劃問(wèn)題解的概念幾何上，圖中A、B、C、D、E、F、G、H對(duì)應(yīng)X〔i〕〔i=1，2，…,8〕1.4線性規(guī)劃問(wèn)題解的概念4x1=16x1x2x1+2x2=84x2=12HEGBADFC直觀上，可行解即可行域中的點(diǎn)，基解是約束直線的交點(diǎn)，基可行解即可行域的頂點(diǎn)。它們之間的關(guān)系可以用圖1-6表示?；夥强尚薪饪尚薪饣尚薪鈭D1-61.4線性規(guī)劃問(wèn)題解的概念第2節(jié)線性規(guī)劃問(wèn)題的幾何意義

2.1根本概念設(shè)K是n維歐氏空間的一個(gè)點(diǎn)集，若任意兩點(diǎn)的連線上的所有點(diǎn)；則稱K為凸集。注：（1）就是以X（1）、X（2）為端點(diǎn)的線段方程，當(dāng)時(shí)，；當(dāng)時(shí)，（2）直觀上，凸集沒(méi)有凹入部分，其內(nèi)部沒(méi)有空洞。1凸集試判斷以下圖形是否凸集：2.1根本概念設(shè)K是凸集，，若X不能用K中兩個(gè)不同的點(diǎn)的凸組合表示為則稱X是K的一個(gè)頂點(diǎn)或極點(diǎn)。設(shè)

是n維歐氏空間En中的k個(gè)點(diǎn)。若存在且使則稱X為的凸組合。2凸組合3頂點(diǎn)注：X是凸集K的頂點(diǎn)即X不可能是K中某一線段的內(nèi)點(diǎn)，而只能是K中某一線段的端點(diǎn)。2.2幾個(gè)定理定理1若線性規(guī)劃問(wèn)題存在可行域，則其可行域是凸集。設(shè)，則有

令X為X1，X2連線上的任意一點(diǎn)，即把它代入約束條件，得到顯然。由此可見(jiàn)，X是凸集。證明：只要證明D中任意兩點(diǎn)連線上的點(diǎn)必然在D內(nèi)即可。引理1線性規(guī)劃問(wèn)題的可行解為基可行解的充要條件是X的正分量所對(duì)應(yīng)的系數(shù)列向量是線性獨(dú)立的。證明：不失一般性，假設(shè)可行解X的前k個(gè)分量為正，即。（1）必要性由基可行解的定義可知。（2）充分性若向量線性獨(dú)立，則必有；當(dāng)時(shí)，它們恰好構(gòu)成一個(gè)基，從而為相應(yīng)的基可行解。當(dāng)k<m時(shí)，則一定可以從其余的列向量中取出m-k個(gè)與構(gòu)成最大的線性獨(dú)立向量組，其對(duì)應(yīng)的解恰為X，根據(jù)定義它是基可行解。2.2幾個(gè)定理2.2幾個(gè)定理證明：不失一般性，假設(shè)可行解X的前m個(gè)分量為正，即故(1)若X不是基可行解，則它一定不是可行域的頂點(diǎn)。根據(jù)引理1，若X不是基可行解，則其正分量所對(duì)應(yīng)的系數(shù)列向量線性相關(guān)，即存在一組不全為零的數(shù)使得定理2線性規(guī)劃問(wèn)題的基可行解X對(duì)應(yīng)于可行域D的頂點(diǎn)。2.2幾個(gè)定理用一個(gè)的數(shù)乘（1-9）式再分別和（1-8）式相加和相減，這樣得到現(xiàn)取由X（1）、X（2）可以得到

即X是X（1）、X（2）連線的中點(diǎn)。另一方面，當(dāng)充分小時(shí)，可保證。即X（1）、X（2）是可行解。這證明了X不是可行域D的頂點(diǎn)。2.2幾個(gè)定理（2）若X不是可行域D的頂點(diǎn)，則它一定不是基可行解。因?yàn)閄不是可行域D的頂點(diǎn)，故在可行域D中可找到不同的點(diǎn)使當(dāng)j>m時(shí)，有，由于X（1）、X（2）是可行域的兩點(diǎn)，應(yīng)滿足和將兩式相減，即得因，所以上式系數(shù)不全為零，故向量組線性相關(guān)，即X不是基可行解。2.2幾個(gè)定理例5設(shè)X是三角形中任意一點(diǎn)，X〔1〕，X〔2〕和X〔3〕是三角形的三個(gè)頂點(diǎn)，試用三個(gè)頂點(diǎn)的坐標(biāo)表示X〔見(jiàn)以下圖〕。引理2若K是有界凸集，則任何一點(diǎn)可表示為K的頂點(diǎn)的凸組合。圖1-82.2幾個(gè)定理解：任選一頂點(diǎn)X（2），做一條連線XX(2)；并延長(zhǎng)交于X(1)、X（3）連線上一點(diǎn)X′。因X′是X(1)、X（3）連線上一點(diǎn)，故可用X(1)、X（3）的線性組合表示為又因X是X′與X（2）連線上的一個(gè)點(diǎn)，故將X′的表達(dá)式代入上式得到令即可。2.2幾個(gè)定理定理3假設(shè)可行域有界，線性規(guī)劃問(wèn)題的目標(biāo)函數(shù)一定可以在其可行域的頂點(diǎn)上到達(dá)最優(yōu)。證明：設(shè)是可行域的頂點(diǎn)，若X(0)不是頂點(diǎn)，且目標(biāo)函數(shù)在X(0)處達(dá)到最優(yōu)。因X(0)不是頂點(diǎn)，所以它可以用D的頂點(diǎn)線性表示為

設(shè)X(m)是所有頂點(diǎn)中目標(biāo)函數(shù)值最大的，則X(m)一定也是最優(yōu)解。事實(shí)上，有故，X(m)也是最優(yōu)解。2.2幾個(gè)定理定理2刻劃了可行域的頂點(diǎn)與基可行解的對(duì)應(yīng)關(guān)系，頂點(diǎn)是基可行解，反之，根本可行解一定是頂點(diǎn)，但它們并非一一對(duì)應(yīng)，有可能兩個(gè)或幾個(gè)基可行解對(duì)應(yīng)于同一頂點(diǎn)〔退化基可行解時(shí)〕。定理3描述了最優(yōu)解在域中的位置，假設(shè)最優(yōu)解唯一，那么最優(yōu)解只能在某一頂點(diǎn)上到達(dá)，假設(shè)具有多重最優(yōu)解，那么最優(yōu)解是某些頂點(diǎn)的凸組合，從而最優(yōu)解是可行域的頂點(diǎn)或界點(diǎn)，不可能是可行域的內(nèi)點(diǎn)。假設(shè)線性規(guī)劃的可行解集非空且有界，那么一定有最優(yōu)解；假設(shè)可行解集無(wú)界，那么線性規(guī)劃可能有最優(yōu)解，也可能沒(méi)有最優(yōu)解。丹捷格教授在一次演說(shuō)中，形象而風(fēng)趣地說(shuō)明了單純形解法的奇效：設(shè)給70個(gè)人分配70項(xiàng)任務(wù)，每人一項(xiàng)。如果每人完成各項(xiàng)任務(wù)所需要付出的代價(jià)（時(shí)間、工資）都知道，要尋求代價(jià)最小的方案。所有的可行方案共有70！種。70！比還要大。如果用窮舉法，逐個(gè)來(lái)比較的話，即使用個(gè)地球或個(gè)太陽(yáng)的容量來(lái)裝計(jì)算機(jī)，這些計(jì)算機(jī)從150億年前開(kāi)始，全部投入計(jì)算，大約要算到太陽(yáng)熄滅才有答案。而用單純形法軟件，幾秒鐘就可以給出答案。單純形法是求解線性規(guī)劃的主要算法，1947年由美國(guó)斯坦福大學(xué)教授丹捷格〔G.B.Dantzig〕提出。第3節(jié)單純形法第3節(jié)單純形法單純形法(SimplexAlgorithm)先求出一個(gè)初始基可行解并判斷它是否最優(yōu)，假設(shè)不是最優(yōu)，再換一個(gè)基可行解并判斷，直到得出最優(yōu)解或無(wú)最優(yōu)解。它是一種逐步逼近最優(yōu)解的迭代方法。oABCDEz=omaxz優(yōu)跨越式尋找最優(yōu)解3.1舉例例6試以例1來(lái)討論如何用單純形法求解。解：本例的標(biāo)準(zhǔn)型為：約束條件(1-12)式的系數(shù)矩陣為可看到x3,x4,x5的系數(shù)構(gòu)成的列向量3.1舉例P3

,P4,P5是線性獨(dú)立的，這些向量構(gòu)成一個(gè)基B。對(duì)應(yīng)于B的變量x3,x4,x5為基變量.從(1-12)式中可以得到〔1-13〕3.1舉例將(1-13)式代入目標(biāo)函數(shù)(1-11)：得到當(dāng)令非基變量x1=x2=0，便得到z=0。這時(shí)得到一個(gè)基可行解X(0)

X(0)=(0,0,8,16,12)T

本基可行解的經(jīng)濟(jì)含義是：工廠沒(méi)有安排生產(chǎn)產(chǎn)品Ⅰ、Ⅱ，資源都沒(méi)有被利用，所以工廠的利潤(rùn)為z=0。3.1舉例從分析目標(biāo)函數(shù)的表達(dá)式(1-14)可以看到：

非基變量x1,x2(即沒(méi)有安排生產(chǎn)產(chǎn)品Ⅰ，Ⅱ)的系數(shù)都是正數(shù)，因此將非基變量變換為基變量，目標(biāo)函數(shù)的值就可能增大。從經(jīng)濟(jì)意義上講，安排生產(chǎn)產(chǎn)品Ⅰ或Ⅱ，就可以使工廠的利潤(rùn)指標(biāo)增加。所以只要在目標(biāo)函數(shù)(1-14)的表達(dá)式中還存在有正系數(shù)的非基變量，這表示目標(biāo)函數(shù)值還有增加的可能，就需要將非基變量與基變量進(jìn)行對(duì)換。3.1舉例一般選擇正系數(shù)最大的那個(gè)非基變量x2為換入變量，將它換到基變量中，同時(shí)還要確定基變量中哪一個(gè)換出來(lái)成為非基變量。分析(1-13)式，當(dāng)將x2定為換入變量后，必須從x3,x4,x5中確定一個(gè)換出變量，并保證其余的變量仍然非負(fù)，即x3,x4,x5≥0。3.1舉例當(dāng)x1=0時(shí)，由(1-13)式得到從(1-15)式可看出，只有選擇

x2=min(8/2,-,12/4)=3時(shí)，才能使(1-15)式成立。因當(dāng)x2=3時(shí)，基變量x5=0，這就決定用x2去替換x5。以上數(shù)學(xué)描述說(shuō)明，每生產(chǎn)一件產(chǎn)品Ⅱ，需要用掉各種資源數(shù)為(2，0，4)。由這些資源中的薄弱環(huán)節(jié)，就確定了產(chǎn)品Ⅱ的產(chǎn)量。這里就是由原材料B的數(shù)量確定了產(chǎn)品Ⅱ的產(chǎn)量

x2=12/4=3件。3.1舉例為了求得以x3,x4,x2為基變量的一個(gè)基可行解和進(jìn)一步分析問(wèn)題，需將(1-13)中x2的位置與x5的位置對(duì)換，得到3.1舉例將(1-16)式中x2的系數(shù)列向量變換為單位列向量。其運(yùn)算步驟是：③′=③/4；①′=①－2×③′;②′=②,并將結(jié)果仍按原順序排列有：高斯消去法3.1舉例3.1舉例再將(1-17)式代入目標(biāo)函數(shù)(1-11)式得到令非基變量x1=x5=0，得到目標(biāo)值z(mì)=9和另一基可行解X(1)=(0,3,2,16,0)T從目標(biāo)函數(shù)的表達(dá)式(1-18)可看到，非基變量x1的系數(shù)是正的，說(shuō)明目標(biāo)函數(shù)值還可以增大，即X(1)還不是最優(yōu)解。確定x1進(jìn)基，此時(shí)非基變量x5=0。3.1舉例當(dāng)x1=2時(shí)，基變量x3=0，確定x3退基。新的基變量x1,x4,x2，非基變量x3,x5，對(duì)（1-17）式作初等變換得由和x3，x4，x2非負(fù)可知，x1至多增加2個(gè)單位。3.1舉例令非基變量x3=x5=0，得到新的基可行解X(2)=(2,3,0,8,0)T把目標(biāo)函數(shù)用非基變量x3，x5表示確定x5進(jìn)基，x3=0。由及x1，x4，x2非負(fù)，知x5至多增加4個(gè)單位，此時(shí)x4=0。x4退基，新的基變量x1，x5，x2。3.1舉例約束對(duì)應(yīng)的增廣矩陣將基變量前的系數(shù)矩陣(P1,P5,P2)經(jīng)初等行變換化為單位陣，只需將化為單位向量。為了求出新的基可行解，也可考慮對(duì)約束對(duì)應(yīng)的增廣矩陣作初等行變換。從上面的增廣陣可以看到基可行解X(3)=(4,2,0,0,4)T，目標(biāo)函數(shù)用非基變量表示得到

所有非基變量的系數(shù)都是負(fù)數(shù)，所以目標(biāo)函數(shù)達(dá)到最大，X(3)是最優(yōu)解。即當(dāng)產(chǎn)品Ⅰ生產(chǎn)4件，產(chǎn)品Ⅱ生產(chǎn)2件時(shí)，工廠可以得到最大利潤(rùn)。新的增廣陣3.1舉例小結(jié)與圖解法比較：?jiǎn)渭冃畏◤某跏蓟尚薪釾〔0〕開(kāi)始迭代，依次得到X〔1〕，X〔2〕，X〔3〕。這相當(dāng)于圖中的目標(biāo)函數(shù)平移時(shí)，從O點(diǎn)開(kāi)始，首先碰到Q4，然后碰到Q3，最后達(dá)到Q2。x1x2Q2(4,2)Q3(2,3)O(0,0)Q4(0,3)X(0)=(0,0,8,16,12)TX(1)=(0,3,2,16,0)TX(2)=(2,3,0,8,0)TX(3)=(4,2,0,0,4)T3.2初始基可行解確實(shí)定由于基可行解是由一個(gè)可行基決定的。因此，確定一個(gè)初始基可行解X〔0〕相當(dāng)于確定一個(gè)初始可行基B0。方法：假設(shè)A中含I，那么B0=I；假設(shè)A中不含I，那么可用人工變量法構(gòu)造一個(gè)I.問(wèn)題：假設(shè)B0=I，那么X〔0〕=？3.3最優(yōu)性檢驗(yàn)與解的判別設(shè)是LP的一個(gè)基，為相應(yīng)的基可行解。將約束寫成非基變量表示基變量的形式，不妨設(shè)思路：對(duì)一個(gè)給定的基可行解，把目標(biāo)函數(shù)用非基變量表示，非基變量前的系數(shù)稱為檢驗(yàn)數(shù)。當(dāng)所有非基變量的檢驗(yàn)數(shù)均小于等于零時(shí)，當(dāng)前解即最優(yōu)解。3.3最優(yōu)性檢驗(yàn)與解的判別將（1-24）式代入目標(biāo)函數(shù)令則3.3最優(yōu)性檢驗(yàn)與解的判別1最優(yōu)解的判別定理若所有非基變量的檢驗(yàn)數(shù)，，則X（0）是最優(yōu)解。2無(wú)窮多最優(yōu)解判別定理若所有非基變量的檢驗(yàn)數(shù)，，又存在某個(gè)非基變量的檢驗(yàn)數(shù)，則線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解。證將非基變量xm+k換入基變量中得到新的基可行解X〔1〕。X〔1〕也是最優(yōu)解。從而X〔0〕，X〔1〕連線上的所有點(diǎn)都是最優(yōu)解。3.3最優(yōu)性檢驗(yàn)與解的判別3無(wú)界解判別定理若，并且，，那么該線性規(guī)劃問(wèn)題具有無(wú)界解。證明思路：由及xm+k每增加一個(gè)單位,目標(biāo)函數(shù)值增加選擇xm+k進(jìn)基，因，所以對(duì)任意的，

都是可行解。令，則。其它情形以上討論都是針對(duì)標(biāo)準(zhǔn)型的，即求目標(biāo)函數(shù)極大化時(shí)的情況。當(dāng)要求目標(biāo)函數(shù)極小化時(shí)，一種情況是將其化為標(biāo)準(zhǔn)型。如果不化為標(biāo)準(zhǔn)型，只需在上述1，2點(diǎn)中把σj≤0改為σj≥0，第3點(diǎn)中將σm+k＞0改寫為σm+k＜0即可。3.3最優(yōu)性檢驗(yàn)與解的判別假設(shè)初始基可行解X(0)不是最優(yōu)解及不能判別無(wú)界時(shí)，需要找一個(gè)新的基可行解。具體做法是從原可行基中換一個(gè)列向量(當(dāng)然要保證線性獨(dú)立)，得到一個(gè)新的可行基，稱為基變換。為了換基，先要確定換入變量，再確定換出變量，讓它們相應(yīng)的系數(shù)列向量進(jìn)行對(duì)換，就得到一個(gè)新的基可行解。3.4基變換3.4基變換為了使目標(biāo)函數(shù)增加得快，從直觀上一般選σj>0中的最大者，即對(duì)應(yīng)的將xk進(jìn)基。也可任選或按最小號(hào)碼選。由可知，若存在σj>0，xj增加則目標(biāo)函數(shù)還可能增大，這時(shí)要將某個(gè)檢驗(yàn)數(shù)大于零的非基變量換到基變量中去，即令該變量的取值大于零。1換入變量確實(shí)定不妨設(shè)xk進(jìn)基，則其余的非基變量仍然為零。由對(duì)，當(dāng)xk取值超過(guò)時(shí),將破壞xi的非負(fù)性,故在新的基可行解中xk的值不超過(guò)3.4基變換2換出變量確實(shí)定3.4基變換另一方面，xk取值越大，目標(biāo)函數(shù)的增加量就越多。故取。這時(shí)原基變量，將從基變量中換出。處在變量轉(zhuǎn)換的交叉點(diǎn)上，稱之為主元，它所在的列稱為主元列，它所在的行稱為主元行。新的可行解問(wèn)題：X〔1〕是不是基可行解？判別方法：由引理1，只需要考慮X〔1〕中的正分量所對(duì)應(yīng)的系數(shù)列向量是否線性無(wú)關(guān)。3.4基變換X（1）中正分量所對(duì)應(yīng)的系數(shù)列向量設(shè)注意到將Pk的表達(dá)式代入（*）得到

因線性無(wú)關(guān)，故，

這表明，從而線性無(wú)關(guān)。即X（1）是基可行解。3.5迭代〔旋轉(zhuǎn)運(yùn)算〕不妨假定xk進(jìn)基，xl退基。xk,xl的系數(shù)列向量分別為：原基可行解對(duì)應(yīng)的增廣矩陣：x1

…xl…xmxm+1

…xk…xnb為了求出新的基可行解，需要把當(dāng)前基變量的系數(shù)矩陣經(jīng)初等行變換化為單位陣，即把Pk化為單位向量。作以下變換：(1)第l行除以主元alk;(2)第i（i≠l）行的元素減去主元行的倍。3.5迭代〔旋轉(zhuǎn)運(yùn)算〕原基可行解對(duì)應(yīng)的增廣矩陣：x1

…xl…xmxm+1

…xk…xnb3.5迭代〔旋轉(zhuǎn)運(yùn)算〕經(jīng)過(guò)初等變換后的增廣矩陣：x1

…xl…xmxm+1

…xk…xnb從而得到新的基可行解3.5迭代〔旋轉(zhuǎn)運(yùn)算〕以為基變量，可得基可行解。用x2替換x5，將的系數(shù)矩陣變換為單位陣，經(jīng)變換為：例7試用上述方法計(jì)算例6的兩個(gè)基變換。解：將例6的約束方程組的系數(shù)矩陣寫成增廣矩陣新的基可行解：第4節(jié)單純形法的計(jì)算步驟單純形法的表格形式是把用單純形法求基可行解、檢驗(yàn)其最優(yōu)性、迭代等步驟都用表格的方式給出，其表格的形式很像增廣矩陣，而計(jì)算方法較多使用矩陣的初等行變換。將約束與目標(biāo)組成n+1個(gè)變量，m+1個(gè)方程的方程組。為了便于迭代運(yùn)算，可將上述方程組寫成增廣矩陣形式：第4節(jié)單純形法的計(jì)算步驟4.1單純形表假設(shè)將z看作不參與基變換的基變量，它與x1,x2,…,xm的系數(shù)構(gòu)成一個(gè)基，這時(shí)可采用行初等變換將c1,c2,…,cm變換為零，使其對(duì)應(yīng)的系數(shù)矩陣為單位矩陣。得到4.1單純形表cj→c1…cmcm+1…cnθiCBXBbx1…xmxm+1…xn

c1c2…cmx1x2…xmb1b2…bm1…0a1,m+1…a1n0…0a2,m+1…a2n………………0…1am,m+1…amnθ1θ2…θm

σj0…0σm+1

…σn根據(jù)上述增廣矩陣設(shè)計(jì)計(jì)算表，見(jiàn)表1-2.4.1單純形表表1-2稱為初始單純形表，每迭代一步構(gòu)造一個(gè)新單純形表。表1-2的說(shuō)明XB列中填入基變量，這里是x1，x2,…，xm；CB列中填入基變量的價(jià)值系數(shù)，這里是c1,c2,…,cm；它們是與基變量相對(duì)應(yīng)的；b列中填入約束方程組右端的常數(shù)；cj行中填入變量的價(jià)值系數(shù)c1,c2,…,cn；θi列的數(shù)字是在確定換入變量后，按θ規(guī)則計(jì)算后填入；最后一行稱為檢驗(yàn)數(shù)行，對(duì)應(yīng)各非基變量xj的檢驗(yàn)數(shù)是4.2計(jì)算步驟(1)找出初始可行基，確定初始基可行解，建立初始單純形表。(2)檢驗(yàn)各非基變量xj的檢驗(yàn)數(shù)，假設(shè)所有σj≤0，j=m+1,…,n,那么已得到最優(yōu)解，停止計(jì)算。否那么轉(zhuǎn)入下一步。(3)在σj>0，j=m+1,…,n中，假設(shè)有某個(gè)σk對(duì)應(yīng)xk的系數(shù)列向量Pk≤0，那么最優(yōu)解無(wú)界，停止計(jì)算。否那么，轉(zhuǎn)入下一步。(4)根據(jù)max{σj>0}=σk，確定xk為換入變量，按θ規(guī)那么計(jì)算θ=min{bi/aik|aik>0}=bl/alk可確定xl為換出變量，轉(zhuǎn)入下一步。4.2計(jì)算步驟現(xiàn)用例1的標(biāo)準(zhǔn)型來(lái)說(shuō)明上述計(jì)算步驟。(5)以alk

為主元素進(jìn)行迭代，把xk所對(duì)應(yīng)的列向量Pk變?yōu)閱挝幌蛄?。將XB列中的xl換為xk，得到新的單純形表。重復(fù)（2）～（5）,直到終止。4.2計(jì)算步驟例1的標(biāo)準(zhǔn)型：(1)取松弛變量x3,x4,x5為基變量，它對(duì)應(yīng)的單位矩陣為基。這就得到初始基可行解X(0)=(0,0,8,16,12)T。將有關(guān)數(shù)字填入表中，得到初始單純形表，見(jiàn)表1-3。表中左上角的cj是表示目標(biāo)函數(shù)中各變量的價(jià)值系數(shù)。在CB列填入初始基變量的價(jià)值系數(shù)，它們都為零。cj→23000θCBXBbx1x2x3x4x50x38121008/2=40x41640010-0x5120[4]00112/4=3cj-zj

23000表1-3計(jì)算非基變量的檢驗(yàn)數(shù)各非基變量的檢驗(yàn)數(shù)為σ1=c1?z1=2?(0×1+0×4+0×0)=2σ2=c2?z2=3?(0×2+0×0+0×4)=34.2計(jì)算步驟4.2計(jì)算步驟它所在行對(duì)應(yīng)的x5為換出變量，x2所在列和x5所在行的交叉處[4]稱為主元素或樞元素(pivotelement)。(2)因檢驗(yàn)數(shù)都大于零，且P1，P2有正分量存在，轉(zhuǎn)入下一步；(3)max(σ1,σ2)=max(2,3)=3，對(duì)應(yīng)的變量x2為換入變量，計(jì)算θ(4)以[4]為主元素進(jìn)行旋轉(zhuǎn)運(yùn)算或迭代運(yùn)算，即初等行變換，使P2變換為(0,0,1)T,在XB列中將x2替換x5,于是得到新表1-4。換人變量換出變量主元素cj→23000θCBXBbx1x2x3x4x50x32[1]010-1/220x4164001043x2301001/4-

cj-zj2000-3/44.2計(jì)算步驟表1-4(5)檢查表1-4的所有cj?zj,這時(shí)有c1?z1=2；說(shuō)明x1應(yīng)為換入變量。重復(fù)(2)～(4)的計(jì)算步驟，得表1-5。換人變量換出變量因?yàn)檫€存在檢驗(yàn)數(shù)>0，繼續(xù)進(jìn)行迭代。cj→23000CBXBbx1x2x3x4x5θ2x121010-1/2-0x4800-41[2]43x2301001/412cj-zj

00-201/4主元素4.2計(jì)算步驟表1-5

(6)表1-6最后一行的所有檢驗(yàn)數(shù)都已為負(fù)或零.這表示目標(biāo)函數(shù)值已不可能再增大，于是得到最優(yōu)解.cj→23000θCBXBbx1x2x3X4x52x141011/400x5400-21/213x22011/2-1/80cj-zj00-3/2-1/804.2計(jì)算步驟表1-6X*=X(3)=(4,2,0,0,4)T

目標(biāo)函數(shù)的最大值z(mì)*=14設(shè)線性規(guī)劃問(wèn)題的約束條件.其中沒(méi)有可作為初始基的單位矩陣，則分別給每個(gè)約束方程加入人工變量xn+1,…,xn+m，得到第5節(jié)單純形法的進(jìn)一步討論第5節(jié)單純形法的進(jìn)一步討論以xn+1,…,xn+m為基變量，便可得到一個(gè)m×m單位矩陣。令非基變x1,…,xn為零，便可得到一初始基可行解X(0)=(0,0,…,0,b1,b2,…,bm)T注：人工變量與松弛變量和剩余變量不同。松弛變量、剩余變量可以取零值，也可以取正值，而人工變量只能取零值。一旦人工變量取正值，那么有人工變量的約束方程和原始的約束方程就不等價(jià)了，這樣所求得的解就不是原線性規(guī)劃的解。第5節(jié)單純形法的進(jìn)一步討論這就要求經(jīng)過(guò)基變換將人工變量從基變量中逐個(gè)替換出來(lái)?；兞恐胁辉俸蟹橇愕娜斯ぷ兞浚@表示原問(wèn)題有解。假設(shè)在最終表中當(dāng)所有cj?zj≤0，而在其中還有某個(gè)非零人工變量，這表示原問(wèn)題無(wú)可行解。如何求解含有人工變量的線性規(guī)劃問(wèn)題?第5節(jié)單純形法的進(jìn)一步討論5.1人工變量法1大M法思路：為了要求人工變量為零，規(guī)定人工變量在目標(biāo)函數(shù)中的系數(shù)為－M.這樣只要人工變量不等于零，目標(biāo)函數(shù)就不可能實(shí)現(xiàn)極大化。為了使目標(biāo)函數(shù)實(shí)現(xiàn)極大就必須把人工變量從基變量中換出。如果直到最后人工變量仍不能從基變量中換出，也就是說(shuō)人工變量仍不為零，那么該線性規(guī)劃問(wèn)題無(wú)可行解。5.1人工變量法例8用大M法求解線性規(guī)劃問(wèn)題解在上述問(wèn)題的約束條件中參加松弛變量x4，剩余變量x5，人工變量x6，x7，得到cj→-31100MMθiCBXBbx1x2x3x4x5x6x70MMx4x6x711311-4-2-21012[1]1000-10010001113/21cj-zj-3+6M1-M1-3M0M005.1人工變量法因本例的目標(biāo)是要求min，所以用所有cj?zj≥0來(lái)判別目標(biāo)函數(shù)是否實(shí)現(xiàn)了最小化。用單純形法進(jìn)行計(jì)算時(shí)，見(jiàn)表1-6。5.1人工變量法cj→-31100MMθiCBXBbx1x2x3x4x5x6x70M1x4x6x3101130-2-2[1]00011000-10010-1-211

cj-zj-11-M00M03M-1011x4x2x31211[3]0-2010001100-2-10210-5-214cj-zj-10001M-1M+1-311x1x2x34191000100011/302/3-2/3-1-4/32/314/3-5/3-2-7/3cj-zj0001/31/3M-1/3M-2/35.1人工變量法兩階段法兩階段法是處理人工變量的另一種方法，這種方法是將參加人工變量后的線性規(guī)劃分兩階段求解。第一階段：不考慮原問(wèn)題是否存在基可行解；給原線性規(guī)劃問(wèn)題參加人工變量，并構(gòu)造僅含人工變量的目標(biāo)函數(shù)和要求實(shí)現(xiàn)最小化。如5.1人工變量法5.1人工變量法然后用單純形法求解上述模型，若，這說(shuō)明原問(wèn)題存在基可行解，可以進(jìn)行第二階段計(jì)算。否則原問(wèn)題無(wú)可行解，應(yīng)停止計(jì)算。第二階段：將第一階段計(jì)算得到的最終表，除去人工變量。將目標(biāo)函數(shù)行的系數(shù)，換成原問(wèn)題的目標(biāo)函數(shù)系數(shù)，作為第二階段計(jì)算的初始表。注：第一階段構(gòu)造的線性規(guī)劃問(wèn)題約束條件與原線性規(guī)劃一樣，而目標(biāo)函數(shù)是求人工變量之和的最小值。如果此值為零，即說(shuō)明存在一個(gè)可行解，使得所有的人工變量都為零。如果此值不為零，那么不存在使所有人工變量都為零的可行解，原問(wèn)題無(wú)可行解。5.1人工變量法5.1人工變量法例9

試用兩階段法求解如下線性規(guī)劃問(wèn)題：解:先在上述線性規(guī)劃問(wèn)題的約束方程中參加人工變量，給出第一階段的數(shù)學(xué)模型為：5.1人工變量法5.1人工變量法第一階段用單純形法求解，見(jiàn)表1-7。求得的結(jié)果是，最優(yōu)解是x1=0,x2=1,x3=1,x4=12,x5=x6=x7=0因?yàn)槿斯ぷ兞縳6=x7=0，所以(0，1，1，12，0)T是原線性規(guī)劃問(wèn)題的基可行解。于是可以進(jìn)行第二階段運(yùn)算。將第一階段的最終表中的人工變量取消填入原問(wèn)題的目標(biāo)函數(shù)系數(shù)，進(jìn)行第二階段計(jì)算，見(jiàn)表1-8。cj→0000011θiCBXBbx1x2x3x4x5x6x7011x4x6x711311-4-2-21012[1]1000-10010001113/21cj-zj6-1-30100010x4x6x3101130-2-2[1]00011000-10010-1-21-1-cj-zj0-100103000x4x2x3121130-2010001100-2-10210-5-21cj-zj00000115.1人工變量法表1-8Cj-31100θi

CBXBbx1x2x3x4x5011x4x2x31211[3]0-2010001100-2-104--cj-zj-10001-311x1x2x34191000100011/302/3-2/3-1-4/3-cj-zj0001/31/35.2退化在單純形法計(jì)算中用θ規(guī)那么確定換出變量時(shí)，有時(shí)存在兩個(gè)以上相同的最小比值，這樣在下一次迭代中就有一個(gè)或幾個(gè)基變量等于零，這就出現(xiàn)了退化解。這時(shí)換出變量xl=0，迭代后目標(biāo)函數(shù)值不變。這時(shí)不同基表示為同一頂點(diǎn)。有人構(gòu)造了一個(gè)特例，當(dāng)出現(xiàn)退化時(shí)，進(jìn)行屢次迭代，而基從B1,B2，…又返回到B1，即出現(xiàn)計(jì)算過(guò)程的循環(huán)，便永遠(yuǎn)達(dá)不到最優(yōu)解。5.2退化盡管實(shí)際計(jì)算過(guò)程中循環(huán)現(xiàn)象極少出現(xiàn)，但還是有可能發(fā)生的。如何解決這問(wèn)題?先后有人提出了“攝動(dòng)法〞，“字典序法〞。1974年Bland提出一種防止循環(huán)的Bland規(guī)那么：(1)選取cj?zj＞0中下標(biāo)最小的非基變量xk為換入變量，即k=min(j｜c(diǎn)j?zj＞0)(2)當(dāng)按θ規(guī)那么計(jì)算存在兩個(gè)和兩個(gè)以上最小比值時(shí)，選取下標(biāo)最小的基變量為換出變量。5.2退化第6節(jié)應(yīng)用舉例一般講，一個(gè)經(jīng)濟(jì)、管理問(wèn)題凡滿足以下條件時(shí)，才能建立線性規(guī)劃的模型。〔1〕要求解問(wèn)題的目標(biāo)函數(shù)能用數(shù)值指標(biāo)來(lái)反映，且為線性函數(shù)；〔2〕存在著多種方案，及有關(guān)數(shù)據(jù)；〔3〕要求到達(dá)的目標(biāo)是在一定約束條件下實(shí)現(xiàn)的，這些約束條件可用線性等式或不等式來(lái)描述。例10合理利用線材問(wèn)題?，F(xiàn)要做100套鋼架，每套用長(zhǎng)2.9m，2.1m和1.5m的原鋼各一根。原料長(zhǎng)7.4m,問(wèn)應(yīng)如何下料，使用的原材料最省。第6節(jié)應(yīng)用舉例第6節(jié)應(yīng)用舉例解最簡(jiǎn)單的做法，在每根原材料上截取2.9m,2.1m和1.5m的原鋼各一根組成一套，每根原材料剩下料頭0.9m。為了做100套鋼架，需用原材料100根，有90m料頭。假設(shè)改用套裁，這可以節(jié)約原材料。下面有幾種套裁方案，都可以采用。 下料根數(shù)長(zhǎng)度(m)方案ⅠⅡⅢⅣⅤ2.92.51.510321221213合計(jì)料頭7.407.30.17.20.27.10.36.60.8第6節(jié)應(yīng)用舉例第6節(jié)應(yīng)用舉例為了得到100套鋼架，需要混合使用各種下料方案。設(shè)x1，x2，x3，x4，x5分別為上面5種方案下料的原材料根數(shù)?？闪谐鲆韵聰?shù)學(xué)模型：minz=0x1+0.1x2+0.2x3+0.3x4+0.8x5

s.t.x1+2x2+x4≥1002x3+2x4+x5≥1003x1+x2+2x3+3x5≥100

x1，x2，x3，x4，x5≥0解：如以AC表示產(chǎn)品A中C的成分，AP表示產(chǎn)品A中P的成分，依次類推。某工廠要用三種原材料C、P、H混合調(diào)配出三種不同規(guī)格的產(chǎn)品A、B、D。產(chǎn)品的規(guī)格要求，產(chǎn)品單價(jià)，每天供給的原料數(shù)量及原料單價(jià)，分別見(jiàn)表1-13和表1-14。問(wèn)該廠如何安排生產(chǎn)，使利潤(rùn)收入最大？產(chǎn)品名稱規(guī)格要求單價(jià)（元/kg）A原材料C不少于50%原材料P不超過(guò)25%50B原材料C不少于25%原材料P不超過(guò)50%35D不限25表1-13例11配料問(wèn)題根據(jù)表1-13有：這里AC+AP+AH=A；BC+BP+BH=B(1-40)將(1-40)逐個(gè)代入(1-39)并整理得到例11配料問(wèn)題表1-14說(shuō)明這些原材料供給數(shù)量的限額。參加到產(chǎn)品A、B、D的原材料C總量每天不超過(guò)100kg，P的總量不超過(guò)100kg，H總量不超過(guò)60kg。表1-14原材料名稱每天最多供應(yīng)量（kg）單價(jià)(元/kg)C10065P10025H6035例11配料問(wèn)題由此得約束條件AC+BC+DC≤100AP+BP+DP≤100AH+BH+DH≤60在約束條件中共有9個(gè)變量，為計(jì)算和表達(dá)方便，分別用x1,…,x9表示。令x1=Ac,x2=Ap,x3=AH,x4=BC,x5=BP,x6=BH,x7=DC,x8=DP,x9=DH.例11配料問(wèn)題約束條件可表示為：例11配料問(wèn)題目標(biāo)函數(shù)目的是使利潤(rùn)最大，即產(chǎn)品價(jià)格減去原材料的價(jià)格為最大。產(chǎn)品價(jià)格為：50(x1+x2+x3)——產(chǎn)品A35(x4+x5+x6)——產(chǎn)品B25(x7+x8+x9)——