【正文】 …… … … am1x1 + am2x2 + … amnxn = bm xk 無非負(fù)要求 ， xj ≤0 ， 其余的變量大于等于零 。 （ 2）線性規(guī)劃問題的共同特征 綜合上述這三點(diǎn) ， 這類問題都可以用如下數(shù)學(xué)語言來描述 。 線性規(guī)劃問題都有一個目標(biāo)要求，并且這個目標(biāo)可以表示為一組未知數(shù)的線性函數(shù)，稱之為目標(biāo)函數(shù)，按研究問題的實(shí)際情況目標(biāo)函數(shù)可以是求最小值也可以是求最大值。 2）約束條件 。通常要求這些未知數(shù)取值是非負(fù)。 建立數(shù)學(xué)模型 ： 設(shè) I 產(chǎn)品生產(chǎn) x1 公斤 ， II 產(chǎn)品生產(chǎn) x2 公斤 MAX 總利潤 Z ＝ 7 x1 + 12 x2 目標(biāo)是 9 x1 + 4 x2 ≤ 360 4 x1 + 5 x2 ≤ 200 3 x1 + 10 x2 ≤ 300 x1， x2， ， x3 ≥ 0 建立數(shù)學(xué)模型： 設(shè) I 產(chǎn)品生產(chǎn) x1 公斤 ， II 產(chǎn)品生產(chǎn) x2 公斤 MAX 總利潤 Z ＝ 7 x1 + 12 x2 目標(biāo)是 9 x1 + 4 x2 ≤ 360 4 x1 + 5 x2 ≤ 200 3 x1 + 10 x2 ≤ 300 x1， x2， ， x3 ≥ 0 以上問題屬于線性規(guī)劃問題 ， 這類問題從數(shù)學(xué)上講所具有的共同特征是： 1）決策變量 。 問如何安排生產(chǎn) ， 以使總利潤達(dá)到最大化 。 二是對這個線性規(guī)劃進(jìn)行求解 。 線性規(guī)劃 整數(shù)規(guī)劃 動態(tài)規(guī)劃 零一規(guī)劃 非線性規(guī)劃 目標(biāo)規(guī)劃 2 理論分支 理論分支 康脫絡(luò)維奇 ——論文 “生產(chǎn)組織與計劃中的數(shù)學(xué)方法” ， 1939年。 第三章 規(guī)劃論 其中，線性規(guī)劃是形成最早也是最成熟的一個分支。 在生產(chǎn)生活以及軍事領(lǐng)域經(jīng)常會遇到資源分配問題，不同的分配方案產(chǎn)生的效益是不一樣的，所以，為了追求最佳效益，必須在不同的分配方案中選擇最佳的資源分配方案。規(guī)劃論就是研究針對不同需求對有限資源進(jìn)行分配的一個運(yùn)籌學(xué)分支。到目前為止，它的應(yīng)用也最廣泛，是數(shù)學(xué)規(guī)劃及運(yùn)籌學(xué)其他分支的基礎(chǔ)。 1947年，丹捷格提出了 單純形法 第一節(jié) 線性規(guī)劃 對于一個實(shí)際問題 ， 如果采用線性規(guī)劃去求解 ， 應(yīng)做兩方面的工作 ， 一是把求解問題抽象成能用線性規(guī)劃來解的數(shù)學(xué)模型 ， 這就是數(shù)學(xué)建模。 即 數(shù)學(xué)建模 求 解 1 線性規(guī)劃方法解決問題的過程 （ 1） 引例 某軍工廠準(zhǔn)備用三種原料來制造兩種產(chǎn)品 ， 有關(guān)數(shù)據(jù)如下表所示 。 單位產(chǎn)品 產(chǎn)品 消耗量 原料 （ 公斤 ） I II 原料總量 A 9 4 360 B ４ ５ 200 C 3 10 300 單位產(chǎn)品利潤（元） 7 12 2 線性規(guī)劃問題的數(shù)學(xué)模型 確定目標(biāo)：求出生產(chǎn)兩種產(chǎn)品的數(shù)量各為公斤 ， 以使總利潤達(dá)到最大 。 每一個問題都用一組未知數(shù)（ ……x n） 表示某一方案，這組未知數(shù)的一組定值代表一個具體的規(guī)劃方案。以后我們稱這組未知數(shù)為決策變量。 3）目標(biāo)函數(shù) 。我們總是希望收益、效益、效率等指標(biāo)達(dá)到最大化，而對于成本、費(fèi)用 、支出等指標(biāo)則希望達(dá)到最小化。 目標(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ī)劃問題的標(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 用求和符號表示標(biāo)準(zhǔn)形式 ， 則標(biāo)準(zhǔn)形式可簡寫為： 3 線性規(guī)劃問題的標(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)形式可簡寫為 令 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ī)劃問題的標(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)形式可簡寫為 maxZ=CX ??????mnmmnnaaaaaaaaa????212222111211??????Ａ＝ ?????????????nbbbB?21C=(c1， c2 ， … ， c )； ?????????xxxX?21AX=B X≥0 3 線性規(guī)劃問題的標(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 )； 價值向量 約束條件系數(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)準(zhǔn)形化為標(biāo)準(zhǔn)形式 非標(biāo)準(zhǔn)形式 min Z =