【正文】 , 解得 即加電Ⅱ的利潤的變化范圍應(yīng)滿足 3．4．2分析的變化右端項(xiàng)的變化在實(shí)際問題中反映為可用資源數(shù)量的變化。表10基0600 4/5162101/50123011/500001/1003/2即美佳公司隨加電Ⅰ，Ⅱ的利潤變化應(yīng)調(diào)整為生產(chǎn)Ⅰ2件，Ⅱ3件。 解 （1）將家電Ⅰ，Ⅱ的利潤變化直接反映到最終單純形表（表4）中得表9。表8原問題對偶問題結(jié)論或繼續(xù)計(jì)算的步驟可行解可行解問題的最優(yōu)解或最優(yōu)基不變可行解非可行解用單純形法繼續(xù)迭代求最優(yōu)解 非可行解可行解用對偶單純形法繼續(xù)迭代求最優(yōu)解 非可行解非可行解引進(jìn)人工變量，編制新的單純形表重新計(jì)算3．4靈敏度分析的主要內(nèi)容3．4．1分析的變化,只可能出現(xiàn)如表8中的前兩種情況.下面舉例說明。② 盡量減少附加的計(jì)算工作量。第三章線性規(guī)劃中靈敏度分析3．1含義和研究對象3．1．1什么是靈敏度分析？是指研究線性規(guī)劃模型的某些參數(shù)（）或限制量（，約束條件）的變化對最優(yōu)解的影響及其程度的分析過程〈也稱為優(yōu)化后分析〉。因?yàn)檫@種情況，若把表中第行的約束方程列出有 （13）因，又，故不可能存在的解。因?yàn)橛蓪ε紗栴}的基本性質(zhì)知，當(dāng)對偶問題有可行解時，原問題可能有可行解，也可能無可行解。對新的基再檢查是否所有。（b）對，因，故有。設(shè)下一個表中的檢驗(yàn)數(shù)為，由式 （12）分兩種情況說明滿足（11）式來選取主元素時，式（12）中（對）。2）確定換入基的變量①為了使下一個表中第行基變量為正值，因而只有對應(yīng)的非基變量才可以考慮作為換入基的變量。否則，通過變換一個基變量，找出原問題的一個目標(biāo)函數(shù)值較小的相鄰基本解。 表7基100010001000 表7中必須有，的值不要求為正。對偶單純形法的基本思路：先找出一個對偶問題的可行基，并保持對偶問題為可行解條件下，如不存在，通過變換到一個相鄰的目標(biāo)函數(shù)值較小的基本解(因?qū)ε紗栴}是求目標(biāo)函數(shù)極小化)，并循環(huán)進(jìn)行，一直到原問題也為可行解(即)，這時對偶問題與原問題均為可行解。反之，如果存在一個對偶問題的可行基，即對，有或，這時只要有，即原問題的解也為可行解，即兩者均為最優(yōu)解。若是，又基變量中無非零人工變量，即找到了問題最優(yōu)解；若為否，再找出相鄰的目標(biāo)函數(shù)值更大的基可行解，并繼續(xù)判別，只要最優(yōu)解存在，就一直循環(huán)進(jìn)行到找出最優(yōu)解為止。將互補(bǔ)松弛性質(zhì)應(yīng)用于其對偶問題時可以這樣敘述：如果有，則；如果有, 則。在線性規(guī)劃問題的最優(yōu)解中，如果對應(yīng)某一約束條件的對偶變量值為非零，則該約束條件取嚴(yán)格等式；反之如果約束條件取嚴(yán)格不等式，則其對應(yīng)的對偶變量一定為零。若原問題及其對偶問題均具有可行解，則兩者均具有最優(yōu)解，且它們最優(yōu)解的目標(biāo)函數(shù)值相等。如果是原問題的可行解, 是其對偶問題的可行解，且有 則是原問題的最優(yōu)解，是對偶問題的最優(yōu)解。 ③若原問題有可行解而其對偶問題無可行解，則原問題目標(biāo)函數(shù)值無界；反之對偶問題有可行解而其原問題無可行解，則對偶問題的目標(biāo)函數(shù)值無界。如果是原問題的可行解，是其對偶問題的可行解，則恒有 由弱對偶性，可得出以下推論： ①原問題任一可行解的目標(biāo)函數(shù)值是其對偶問題目標(biāo)函數(shù)值的下界；反之對偶問題任一可行解的目標(biāo)函數(shù)值是其原問題目標(biāo)函數(shù)值的上界。將這個解代入對偶問題的目標(biāo)函數(shù)值 有 （9）由（9）式看出，當(dāng)原問題為最優(yōu)解時，這時對偶問題為可行解，且兩者具有相同的目標(biāo)函數(shù)值。 表6項(xiàng)目基變量非基變量10從表5和表6看出，當(dāng)?shù)蠡兞繛闀r，其在初始單純形表中的系數(shù)矩陣為，則有：1）對應(yīng)初始單純形表中的單位矩陣，迭代后的單純形表中為； 2）初始單純形表中基變量,，迭代后的表中；3）初始單純形表中約束系數(shù)矩陣為[，]＝[，]，迭代后的表中約束系數(shù)矩陣為[，]＝[，]＝[，]。又因單純形法的迭代是對約束增廣矩陣進(jìn)行的行的初等變換，對應(yīng)的系數(shù)矩陣在新表中應(yīng)為。將在初始單純形表中單獨(dú)列出，而中去掉后的若干列后剩下的列組成矩陣，這樣(1)的初始單純形表可列成如表5的形式。單純形法計(jì)算時，總選取為初始基，對應(yīng)基變量為。用替換基變量，得到一個新的基，按上述單純形法計(jì)算步驟第三步，可以找到新的基可行解，并列出新的單純形表，記作表3如下：表321000基015051002412/601/60010[4/6]01/6101/301/30由于上表中還存在大于零的檢驗(yàn)數(shù)，故重復(fù)上述步驟得下表，記作表4：表421000基015/20015/415/227/21001/41/213/20101/43/20001/41/2上表中所有，且基變量中不含人工變量，故表中的基可行解為最優(yōu)解，代入目標(biāo)函數(shù)得。因，故確定為換入變量。例3：用單純形法求解線性規(guī)劃問題 解 先將上述問題化成標(biāo)準(zhǔn)形式有 其約束條件系數(shù)矩陣的增廣矩陣為 是單位矩陣，構(gòu)成一個基，對應(yīng)變量是基變量。根據(jù)的原則，確定為換入變量，計(jì)算（），按規(guī)則，確定為換出變量。 若已獲得最優(yōu)解（或確定無最優(yōu)解），則停止；否則進(jìn)行下一步。2．2．3．2單純形法迭代步驟1）求出初始可行解，列出初始單純形表。 ②若存在某個非基變量的檢驗(yàn)數(shù)大于零，而該非基變量對應(yīng)的系數(shù)均非正，則該線性規(guī)劃問題具有無界解（無最優(yōu)解）。2）最優(yōu)性檢驗(yàn)與解的判別（目標(biāo)函數(shù)極大型） ①當(dāng)所有變量對應(yīng)的檢驗(yàn)數(shù)均非正時，現(xiàn)有的基可行解即為最優(yōu)解。2．2．3單純形法2．2．3．1單純形法迭代原理1）確定初始基可行解 ①當(dāng)線性規(guī)劃問題的所有約束條件均為≤號是，松弛變量對應(yīng)的系數(shù)矩陣即為單位矩陣，以松弛變量為基變量可確定基可行解。基向量：B中一列（共m個）→基變量非基向量：B外（A中）一列（共n－m個）→非基變量可行解：滿足①、②的解最優(yōu)解：滿足③的可行解基本解：令所有非基變量=0，求出的滿足①的解基本可行解：滿足②的基本解最優(yōu)基本可行解：滿足③的基本可行解基本解退化的基本解：有基變量=0的基本解退化的基本可行解退化的最優(yōu)化基本可行解2．2．2線性規(guī)劃的圖解法l 適于求解二維問題l 不必化為標(biāo)準(zhǔn)型2．2．1．1圖解法步驟例2： 1）由全部約束條件作圖求出可行域2）作出一條目標(biāo)函數(shù)的等值線3）平移目標(biāo)函數(shù)等值線，作圖得最優(yōu)點(diǎn)，再算出最優(yōu)值 圖1最優(yōu)點(diǎn)Q： ；最優(yōu)值Z： .2．2．1．2從圖解法看線性規(guī)劃問題解的幾種情況1）有唯一最優(yōu)解（一般情況）2）有無窮多組最優(yōu)解（平行；最優(yōu)值相同）對例2，修改為：3） 無可行解（可行域空集）對例2，增加一個約束條件：4） 無有限最優(yōu)解（無界域；取決于求還是？）對例2，去掉第一個約束條件l 線性規(guī)劃的可行域?yàn)橥辜?，特殊情況下為無界域（有有限個頂點(diǎn)）或空集。基：已知A是約束條件的mn系數(shù)矩陣，其秩為m。類似可定久矩陣A的行秩。秩：設(shè)A是mn矩陣。2．2線性規(guī)劃模型的求解2．2．1線性規(guī)劃問題的基與解 ① ② ③線性無關(guān)：對于n維空間的一組向量，若數(shù)域F中有一組不全為0的數(shù)（），使 成立，則稱這組向量在F上線性相關(guān)。如果變量代表某產(chǎn)品當(dāng)年計(jì)劃數(shù)與上一年計(jì)劃數(shù)之差，顯然的以值可能是正也可能是負(fù)，這時可令，其中，將其代入線性規(guī)劃模型即可。松弛變量或剩余變量在實(shí)際問題中分別表示未被充分利用的資源和超出的資源數(shù)，均未轉(zhuǎn)化為價(jià)值和利潤，所以引進(jìn)模型后它們在目標(biāo)函數(shù)中的系數(shù)均為零。當(dāng)約束條件為“≥”時，如有，可令，得。3）約束條件為不等式。對不符合標(biāo)準(zhǔn)形式的線笥規(guī)劃問題，可分別通過下列方法化為標(biāo)準(zhǔn)形式。又