【正文】 aaa???????212222111211B= a11x1 + a12x2 + … a1nxn = b1 a21x1 + a22x2 + … a2nxn = b2 …… am1x1 + am2x2 + … amnxn = bm =（ P1， P2， …… ， PM） 非基變量 —— 其余變量稱為 （ 對(duì)應(yīng)于Ｂ ） 的 非基變量 。 圖解法解題的基本步驟 確定可行域 確定目標(biāo)函數(shù)移動(dòng)的方向 確定最優(yōu)解 用圖解法求解如下線性規(guī)劃問(wèn)題 min Z = 2x1 + 2x2 x1 x2 ≥ 1 x1 + 2x2 ≤ 0 x1 ， x2 ≥ 0 練習(xí) 1 用圖解法求解如下線性規(guī)劃問(wèn)題 min Z = 2x1 + 2x2 x1 + x2 ≥1 x1 + x2 ≤2 x1， x2 ≥0 練習(xí) 2 5 有關(guān)線性規(guī)劃問(wèn)題解的概念 可行域 ——所有可行解所構(gòu)成的集合就是可行域 對(duì)于圖解法，可行域就是由約束條件圍成的一個(gè)凸多邊形，我們?nèi)绻?R表示可行域，則 R={x/Ax=b,x≥0} 可行解 ——同樣 ， 在可行域上的點(diǎn)都滿足約束條件所以 ， 我們稱這些點(diǎn)為可行解 。 求解線性規(guī)劃問(wèn)題 maxZ＝ 2x1+5x2 x1≤4 x2≤3 x1+2x2≤ 8 x1≥0,x2≥0 例題 把 x1， x2 看作上平面上點(diǎn)的坐標(biāo) ， 在第一象限內(nèi)用圖形將此規(guī)劃問(wèn)題的約束條件和目標(biāo)函數(shù)都反映出來(lái)就是 約束條件圍成了一個(gè)區(qū)域 ， 這個(gè)凸多邊形oabcd內(nèi)的任一點(diǎn)的坐標(biāo)都滿足約束條件 。 如： x1 + x2 + x3 ≥ 60 （ 2） 將非標(biāo)準(zhǔn)形化為標(biāo)準(zhǔn)形式 非標(biāo)準(zhǔn)形式是 max ( min ) Z = c1x1 + c2x2 + … + xn a11x1 + a12x2 + … a1nxn = b1 a21x1 + a22x2 + … a2nxn = b2 … …… …… …… ………… …… … … am1x1 + am2x2 + … amnxn = bm xk 無(wú)非負(fù)要求 ， xj ≤0 ， 其余的變量大于等于零 。 線性規(guī)劃問(wèn)題都有一個(gè)目標(biāo)要求，并且這個(gè)目標(biāo)可以表示為一組未知數(shù)的線性函數(shù)，稱之為目標(biāo)函數(shù)，按研究問(wèn)題的實(shí)際情況目標(biāo)函數(shù)可以是求最小值也可以是求最大值。通常要求這些未知數(shù)取值是非負(fù)。 問(wèn)如何安排生產(chǎn) ， 以使總利潤(rùn)達(dá)到最大化 。 線性規(guī)劃 整數(shù)規(guī)劃 動(dòng)態(tài)規(guī)劃 零一規(guī)劃 非線性規(guī)劃 目標(biāo)規(guī)劃 2 理論分支 理論分支 康脫絡(luò)維奇 ——論文 “生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法” ， 1939年。 在生產(chǎn)生活以及軍事領(lǐng)域經(jīng)常會(huì)遇到資源分配問(wèn)題，不同的分配方案產(chǎn)生的效益是不一樣的，所以，為了追求最佳效益，必須在不同的分配方案中選擇最佳的資源分配方案。到目前為止，它的應(yīng)用也最廣泛，是數(shù)學(xué)規(guī)劃及運(yùn)籌學(xué)其他分支的基礎(chǔ)。 即 數(shù)學(xué)建模 求 解 1 線性規(guī)劃方法解決問(wèn)題的過(guò)程 （ 1） 引例 某軍工廠準(zhǔn)備用三種原料來(lái)制造兩種產(chǎn)品 ， 有關(guān)數(shù)據(jù)如下表所示 。 每一個(gè)問(wèn)題都用一組未知數(shù)（ ……x n） 表示某一方案，這組未知數(shù)的一組定值代表一個(gè)具體的規(guī)劃方案。 3）目標(biāo)函數(shù) 。 目標(biāo)函數(shù)： max ( min ) Z = c1x1 + c2x2 + … + xn a11x1 + a12x2 + … a1nxn ≥（ = ， ≤） b1 a21x1 + a22x2 + … a2nxn ≥（ = ， ≤） b2 …… am1x1 + am2x2 + … amnxn ≥（ = ， ≤） bm x1， x2， … xn ≥ 0 3 線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式 （ 1） 線性規(guī)劃的標(biāo)準(zhǔn)形式是： 目標(biāo)函數(shù)： max Z = c1x1 + c2x2 + … + xn a11x1 + a12x2 + … a1nxn = b1 a21x1 + a22x2 + … a2nxn = b2 …… am1x1 + am2x2 + … amnxn = bm x1， x2， … xn ≥ 0 線性規(guī)劃的標(biāo)準(zhǔn)形式是： max Z = c1 x1 + c2 x2 + … + xn a11 x1 + a12 x2 + … a1n xn = b1 a21 x1 + a22 x2 + … a2n xn = b2 …… am1 x1 + am2 x2 + … amn xn = bm x1， x2， … xn ≥ 0 max Z = ??njjjxc1 iji jij bxa ??, ??????????minj??11ijijij bxa ??,x j ≥0 用求和符號(hào)表示標(biāo)準(zhǔn)形式 ， 則標(biāo)準(zhǔn)形式可簡(jiǎn)寫為： 3 線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式 線性規(guī)劃的標(biāo)準(zhǔn)形式是： max Z = c1x1 + c2x2 + … + xn a11x1 + a12x2 + … a1nxn = b1 a21x1 + a22x2 + … a2nxn = b2 …… am1x1 + am2x2 + … amnxn = bm x1， x2， … xn ≥ 0 用矩陣表示標(biāo)準(zhǔn)形式 ， 則標(biāo)準(zhǔn)形式可簡(jiǎn)寫為 令 C表示由目標(biāo)函數(shù)的系數(shù)構(gòu)成的矩陣，即 用 A表示由約束條件的系數(shù)構(gòu)成的矩陣， 即 ??????mnmmnnaaaaaaaaa????212222111211??????Ａ＝ 令 X 表示由決策變量構(gòu)成的矩陣 ， 即 ?????????????nxxxX?21B表示約束條件向量，即 ???????????bbbB?21C=(c1， c2 ， … ， c )； 3 線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式 線性規(guī)劃的標(biāo)準(zhǔn)形式是： max Z = c1x1 + c2x2 + … + xn a11x1 + a12x2 + … a1nxn = b1 a21x1 + a22x2 + … a2nxn = b2 …… am1x1 + am2x2 + … amnxn = bm x1， x2， … xn ≥ 0 用矩陣表示標(biāo)準(zhǔn)形式 ， 則標(biāo)準(zhǔn)形式可簡(jiǎn)寫為 maxZ=CX ??????mnmmnnaaaaaaaaa????212222111211??????Ａ＝ ?????????????nbbbB?21C=(c1， c2 ， … ， c )； ?????????xxxX?21AX=B X≥0 3 線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式 線性規(guī)劃的標(biāo)準(zhǔn)形式是： max Z = c1x1 + c2x2 + … + xn a11x1 + a12x2 + … a1nxn = b1 a21x1 + a22x2 + … a2nxn = b2 …… am1x1 + am2x2 + … amnxn = bm x1， x2， … xn ≥ 0 幾點(diǎn)稱謂 ??????mnmmnnaaaaaaaaa????212222111211??????Ａ＝ ?????????????nxxxX?21決策向量 ?????????????nbbbB?21約束方程組的限定向量 C=(c1， c2 ， … ， c )； 價(jià)值向量 約束條件系數(shù)矩陣 （ 2） 將非標(biāo)準(zhǔn)形化為標(biāo)準(zhǔn)形式 非標(biāo)準(zhǔn)形式是 max ( min ) Z = c1x1 + c2x2 + … + xn a11x1 + a12x2 + … a1nxn ≥（ = ， ≤） b1 a21x1 + a22x2 + … a2nxn ≥（ = ， ≤） b2 …… am1x1 + am2x2 + … amnxn ≥（ = ， ≤） bm x1， x2， … xn ≥ 0 標(biāo)準(zhǔn)形式是 ： max Z = c1x1 + c2x2 + … + xn a11x1 + a12x2 + … a1nxn = b1 a21x1 + a22x2 + … a2nxn = b2 …… am1x1 + am2x2 + … amnxn = bm x1， x2， … xn ≥ 0 （ 2） 將非標(biāo)