【正文】 相對應(yīng)。解的幾種情況：（1）此例有唯一解Q2，即x1=4,x2=2,z=14 （2）有無窮多最優(yōu)解（多重解），若將目標函數(shù)改為z=2x1+4x2則線段Q2，Q3上的點均為最優(yōu)解。 W基本解可行解 基可行解（五）兩個變量LP問題的圖解法 。顯然，基B與基本解是一一對應(yīng)的，基本解的個數(shù)≤Cmn。若B是LP問題的一個基，則B由m個線性獨立的列向量組成，即B=(Pr1,Pr2,…,Prm)，其中Prj=(a1rj,a2rj,…,amrj)T，(j=1,2,…,m)稱為基向理。而使目標函數(shù)達到最大值的可行解稱為最優(yōu)解，對應(yīng)的目標函數(shù)值稱為最優(yōu)值。如非線性規(guī)劃，整數(shù)規(guī)劃或不確定型分析方法。④確定性假定：所有的參數(shù)(aij,bi,cj)均為確定，所以LP問題是確定型問題，不含隨機因素。①比例性假定：決策變量變化的改變量與引起目標函數(shù)的改變量成比例；決策變量變化的改變量與引起約束方程左端值的改變量成比例。令xj=xj162。左邊－“松馳變量”③變量xj163。max(z)=cx②“163。（2）存在一組線性等式或不等式的約束條件。問如何選擇才能滿足營養(yǎng)的前提下使購買食品的費用最?。啃蛱柺称访Q熱量(卡路里)蛋白質(zhì)(克)鈣(mg)價格(元)1豬肉100050400102雞蛋8006020063大米9002030034白菜200105002解:設(shè)xj(j=1,2,3,4)為第j種食品每天的購買量，則配餐問題數(shù)學(xué)模型為minz=10x16x23x32x4 （二）LP問題的模型上述兩例所提出的問題，可歸結(jié)為在變量滿足線性約束條件下，求使線性目標函數(shù)值最大或最小的問題。由于資源的限制，所以有：機器設(shè)備的限制條件：x1+2x2≤8原材料A的限制條件： 4x1≤16 （稱為資源約束條件）原材料B的限制條件： 4x2≤12同時，產(chǎn)品Ⅰ、Ⅱ的產(chǎn)量不能是負數(shù)，所以有x1≥0，x2≥0 （稱為變量的非負約束）顯然，在滿足上述約束條件下的變量取值，均能構(gòu)成可行方案，且有許許多多。第一部分 線性規(guī)劃內(nèi)容框架LP問題基本概念 數(shù)學(xué)模型 可行解、最優(yōu)解實際問題 LP問題 解的概念 基本解、基可行解提 出 基本最優(yōu)解 基本方法 圖解法 原始單純形法 單純形法 大M法 人工變量法 對偶單純形法 兩階段法 對偶理論 進一步討論 靈敏度分析──參數(shù)規(guī)劃* 在經(jīng)濟管理領(lǐng)域內(nèi)應(yīng)用 運輸問題（轉(zhuǎn)運問題） 特殊的LP問題 整數(shù)規(guī)劃 多目標LP問題*第一部分 線性規(guī)劃（Linear Programming）及其應(yīng)用第一章 LP問題的數(shù)學(xué)模型與求解 167。運籌學(xué)的核心思想是建立在優(yōu)化的基礎(chǔ)上。 例如，在線性規(guī)劃中體現(xiàn)為兩方面： （1）對于給定的一項任務(wù)，如何統(tǒng)籌安排，使以最少的資源消耗去完成？ （2）在給定的一定數(shù)量的資源條件下，如何合理安排，使完成的任務(wù)最多？ 運籌學(xué)解決問題的主要方法是用數(shù)學(xué)模型描述現(xiàn)實中提出的決策問題，用數(shù)學(xué)方法對模型進行求解，并對解的結(jié)果進行分析，為決策提供科學(xué)依據(jù)。1 LP問題及其數(shù)學(xué)模型 （一）引例1（生產(chǎn)計劃的問題） 某工廠在計劃期內(nèi)要安排生產(chǎn)Ⅰ、Ⅱ的兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時，A、B兩種原材料的消耗以及每件產(chǎn)品可獲的利潤如下表所示。而工廠的目標是在不超過所有資源限量的條件下，如何確定產(chǎn)量x1，x2以得到最大的利潤，即使目標函數(shù)Z=2x1+3x2 的值達到最大。它們具有共同的特征。（3）都有一個用決策變量的線性函數(shù)作為決策目標（即目標函數(shù)），按問題的不同，要求目標函數(shù)實現(xiàn)最大化或最小化?！?74。0174。－xj178。此假定意味著每種經(jīng)營活動對目標函數(shù)的貢獻是一個常數(shù)，對資源的消耗也是一個常數(shù)。以上4個假定均由于線性函數(shù)所致。對LP標準型，我們還假定r(A)=mn。求解LP問題就是求其最優(yōu)解和最優(yōu)值，但從代數(shù)的角度去求是困難的。與其向量Prj相對應(yīng)的變量xrj稱為基變量，其它變量稱為非基變量。在基本解中，稱滿足非負條件的基本解為基可行解，對應(yīng)的基稱為可行基。以引例為例說明①②③④maxz=2x1+3x2按以下順序進行：解：（1）畫出直角坐標系； （2）依次做每條約束線，標出可行域的方向，并找出它們共同的 可行域；AQ1Q2x2③② （3）任取一目標函數(shù)值作一條目標函數(shù)線（稱等值線），根據(jù)目標函數(shù)（最大或最?。╊愋停揭圃撝本€即將離開可行域上，則與目標函數(shù)線接觸的最終點即表示最優(yōu)解。 （3）無界解x20x1求max無界但求min有唯一解 （4）無可行解x2x10可行域與最優(yōu)解間的關(guān)系： 可行域 最優(yōu)解 空 集 無最優(yōu)解（無可行解） 有界集 唯一最優(yōu)解 多重解 無界集 無有限最優(yōu)解（無界解）結(jié)論：（1）LP問題的可行域是凸集（凸多邊形，凸多面體，…）； （2）LP問題最優(yōu)解若存在，則必可在可行域的頂點上得到； （3）LP問題的可行域的頂點個數(shù)是有限的； （4）若LP問題有兩個最優(yōu)解，則其連線上的點都是最優(yōu)解。于是還有結(jié)論：（5）對于標準型的LP問題，X是基可行解的充要條件是X為可行域的頂點。2 單純形法與計算機求解 ：求出一個初始基可行解 y停判別此基可行解是否最 優(yōu) 解 N求出使目標函數(shù)值得到改善的基可行解 （表格形式） （1）建立初始單純形表，假定B=I，b≥0 設(shè)maxZ=c1x1+c2x2+…+xn將目標函數(shù)改寫為：Z+c1x1+c2x2+…+xn=0把上述方程組和目標函數(shù)方程構(gòu)成n+1個變量，m+1個方程的方程組，并寫成增廣矩陣的形式：Z x1 x2 … xm xm+1 … xn 0 1 0 … 0 1m+1 … 1n 10 0 1 … 0 2m+1 … 2n 20 0 0 … 1 mm+1 … mn m1 c1 c2 … cm cm+1 … 0以非基變量表示基變量形式代入Z中的基變量,有 令 于是因此，上述的增廣矩陣就可寫成：Z x1 x2 … xm xm+1 … xn 0 1 0 … 0 1m+1 … 1n 10 0 1 … 0 2m+1 … 2n 20 0 0 … 1 mm+1 … mn m1 0 0 … 0 …－ 再令則上述增廣矩陣可寫成下面表格形式：即初始單純形表T（B）CjC1……Cmcm+1……qiCBxBx1……xmxm+1……xnC1x111……0a1m+1……a1nC2x220……0a2m+1……a2n：：：： ：：………：Cmxmm0……1amm+1……amnZZ00……0sm+1……sn172。 （3）更好表現(xiàn)一般規(guī)律的在矩陣形式的單純形表中設(shè)MaxX=CX MaxZ=CX+0XL 其標準型為 將系數(shù)矩陣(A,I)分劃為(B,N,I)，其中B為可行基，對應(yīng)于基變量向量XB,N對應(yīng)于XN，I對應(yīng)于XL,(XN,XL)為非基變量向量。CBCNCLXBXNXLXB1B1NB1ZCBB1b0CBB1N－CNCBB1例如將例1 化成標準型后如下表T（B）：Cj23000qiCBXBx1x2x3x4x50x38121000x416400100x51204001Z023000172。 在T(B)中，若有σk0 (1163。否則轉(zhuǎn)入（3） （3）換基迭代（基變換） 1176。換基迭代的關(guān)鍵在于將換入變量對應(yīng)的列向量用初等行變換方法變換成單位列向量。所謂人工變量法是在原問題不含有初始可行基B=I的情況下，人為的對約束條件增加虛擬的非負變量（即人工變量），構(gòu)造出含有B=I的另一個LP問題后求解。在最終表中若不能全部被換出，則說明原問題無可行解。注意到：①分別在約束條件增加人工變量x5,x6是為了構(gòu)成“人工基” ②對于Min的目標函數(shù)采用(+M)，而對于Max的目標函數(shù)則采用(M)作為人工變量的系數(shù),是強加于人工變量的一種懲罰,其目的是為了強制人工變量由變量轉(zhuǎn)為非基變量，使之恢復(fù)原