【正文】 ? ?m a x 0j j k? ? ??? m in 0iliki k l kbbaaa???? ? ?????167。 在 δj＞ 0 （ j=m+1， m+2， … ， n）中，若有某個(gè) δk對(duì)應(yīng)的 xk的系數(shù)列向量Pk≤0，則此線性規(guī)劃問(wèn)題存在無(wú)界解，停止計(jì)算，否則轉(zhuǎn)入 4。 1 對(duì)線性規(guī)劃的回顧 單純形法 j? ?例：線性規(guī)劃問(wèn)題數(shù)學(xué)模型的某種標(biāo)準(zhǔn)形式 1 1 2 2 1 11 1 , 1 1 1 , 2 2 1 12 2 , 1 1 2 , 2 2 2 2, 1 1 , 2 212m a x, , 0m m m m n nm m m m n nm m m m n nm m m m m m m m n n mnz c x c x c x c x c xx a x a x a x bx a x a x a x bx a x a x a x bx x x??? ? ? ?? ? ? ?? ? ? ?? ? ? ? ? ? ?? ? ? ???? ? ? ?????? ? ? ??? ??167。 1 對(duì)線性規(guī)劃的回顧 三、單純形法的解題步驟 找出 初始可行基 ，確定初始基可行解，建立初始單純形表。 二、單純形法的含義 單純形法是一種迭代算法，首先找到一個(gè)初始基可行解，然后判斷它是否為最優(yōu)解，如果是就停止迭代，否則，按照一定的法則，再找到一個(gè)更好且與當(dāng)前基可行解相鄰的基可行解，再進(jìn)行判斷，直到找不到更好的基可行解或判斷問(wèn)題無(wú)解為止。 單純形法 一、單純形法的解題思路 從某一基可行解開(kāi)始，轉(zhuǎn)化到另一個(gè) 相鄰 的基可行解，并且使相應(yīng)的目標(biāo)函數(shù)值有改進(jìn)。 —— 若線性規(guī)劃在兩個(gè)頂點(diǎn)以上達(dá)到最優(yōu) ,則一定有無(wú)窮多個(gè)最優(yōu)解。 1 對(duì)線性規(guī)劃的回顧 —— 若線性規(guī)劃有最優(yōu)解，則一定在凸集的某個(gè)（些）頂點(diǎn)上 達(dá)到最優(yōu)，即此時(shí)一定存在某個(gè)頂點(diǎn)是最優(yōu)解。 定理 2 X是線性規(guī)劃可行域 R 頂點(diǎn)的充要條件是 X是 線性規(guī)劃的基本可行解。 —— 線性規(guī)劃問(wèn)題的可行域是一個(gè)凸集。 線性規(guī)劃問(wèn)題解的概念 線性規(guī)劃解的性質(zhì) 定理 1 線性規(guī)劃的可行域 R 是一個(gè)凸集，且有有限個(gè)頂點(diǎn)。 為什么？ 167。 1 對(duì)線性規(guī)劃的回顧 線性規(guī)劃問(wèn)題解的概念 6 問(wèn)題：最優(yōu)解與基可行解？ 最優(yōu)解不一定是 基可行解 ， 基可行解 也不一定是最優(yōu)解。 基可行解一定是基解，但基解不一定是基可行解。 基解不一定是可行解，可行解也不一定是基解。 1 對(duì)線性規(guī)劃的回顧 線性規(guī)劃問(wèn)題解的概念 ? 可行解 ： 滿足函數(shù)約束條件和非負(fù)約束條件的解 ? 最優(yōu)解 ： 使目標(biāo)函數(shù)達(dá)到最大值的可行解 ? 基 ： 設(shè) A是約束方程組的 m n階系數(shù)矩陣， B是矩陣 A中 m m階 非奇異子矩陣 ，稱 B是線性規(guī)劃問(wèn)題的一個(gè)基 ? 基向量 ： 基 B中每一個(gè)列向量 Pj ? 非基向量 ： A中其余列向量 Pj（不在 B中） ? 基變量 ： 與基向量 Pj對(duì)應(yīng)的決策變量 xj ? 非基變量 ： 與非基向量對(duì)應(yīng)的決策變量 ? 基解 ? 基可行解 ： 滿足非負(fù)約束條件的基解 ? 可行基 ： 對(duì)應(yīng)于基可行解的基 167。 1 對(duì)線性規(guī)劃的回顧 11m a x120 1 2njjjnij j ijjz c xa x b i mx j n????????? ????? ， ， ， ， ， ， ，下述 5種情況如何 化為標(biāo)準(zhǔn)型？ 1. 約束條件為不等式 3. xj為自由變量 4. 資源系數(shù) bi 0 5. m≥n 167。這樣的問(wèn)題稱為 線性規(guī)劃 。 1 對(duì)線性規(guī)劃的回顧 線性規(guī)劃定義 ：求 一組變量 x x … 、 xn的 值 ，使之滿足關(guān)于這組變量的若干個(gè) 線性 等式或不等式的 約束條件 ，而且使這組變量的一個(gè) 線性 函數(shù)取到 極大值 (或極小值 )。 4 內(nèi)點(diǎn)算法簡(jiǎn)介 167。 2 線性規(guī)劃在工商管理中的應(yīng)用 167。第二章 線性規(guī)劃 Linear Programming 167。 1 對(duì)線性規(guī)劃的回顧 167。 3 線性規(guī)劃問(wèn)題的計(jì)算機(jī)求解 167。 5 案例分析 167。這些變量稱為決策變量 ，所要優(yōu)化的函數(shù)稱為 目標(biāo)函數(shù) ，決策變量是取實(shí)數(shù)值的 連續(xù)變量 。 線性規(guī)劃模型的結(jié)構(gòu) ?目標(biāo)函數(shù) ： max， min max z(min f)=∑ cjxj ?約束條件 ： ≥,=,≤ ∑aijxj ≤(=, ≥) bi (i=1,2, …m) ?變量符號(hào) ： ≥0,unr,≤0 xj ≥0 (j=1,2, …n) 線性規(guī)劃 數(shù)學(xué)模型 的標(biāo)準(zhǔn)形式（標(biāo)準(zhǔn)型） ? 目標(biāo)函數(shù)求最大值 ? 函數(shù)約束條件全為等式 ? 決策變量全為非負(fù) ? 函數(shù)約束條件右端項(xiàng)全為非負(fù) 167。 1 對(duì)線性規(guī)劃的回顧 非標(biāo)準(zhǔn)形式化為標(biāo)準(zhǔn)形式總結(jié) 線性規(guī)劃模型 化為標(biāo)準(zhǔn)形式 變量 Xj≥0 不變 Xj≤0 令 Xj * = Xj ,則 Xj * ≥0 Xj無(wú)約束 令 Xj * Xj *’ = Xj ,則 Xj *, Xj *’ ≥0 約束條件 右端項(xiàng) bi≥0 不變 bi0 約束式兩端同乘以” 1” 形式 ai1x1+…+a inxn =bi 不變 ai1x1+…+a inxn ≤bi ai1x1+…+ ainxn+xsi =bi ai1x1+…+a inxn ≥ bi ai1x1+…+a inxnxri =bi 目標(biāo)函數(shù) max z= c1x1+…+c nxn 不變 min z= c1x1+…+c nxn 令 z*= z, 化為求 max z*= c1x1… xn 167。 1 對(duì)線性規(guī)劃的回顧 1 可行解與最優(yōu)解 ： 最優(yōu)解一定是可行解，但可行解不一定是最優(yōu)解。 2 可行解與基解： 3 可行解與基可行解 ： 基可行解一定是可行解，但可行解不一定是基可能解。 4 基本解與基可行解 ： 非可行解 可行解 基可行解 基本解 167。 5 最優(yōu)解與基本解 ： 最優(yōu)解不一定是基解，基解也不一定是最優(yōu)解。 1 對(duì)線性規(guī)劃的回顧 非可行解 可行解 基可行解 基本解 考慮無(wú)窮多最優(yōu)解的情況 。 定理 3 若線性規(guī)劃有最優(yōu)解，則必存在一個(gè)基可行解是最優(yōu)解。 —— 線性規(guī)劃的每一個(gè)基可行解對(duì)應(yīng)可行域的一個(gè)頂點(diǎn) (基可行解與可行域頂點(diǎn)一一對(duì)應(yīng) )。 167。 定理 4 若線性規(guī)劃在可行域的兩個(gè)頂點(diǎn)上達(dá)到最優(yōu)，則在兩個(gè)頂點(diǎn)的連線上也達(dá)到最優(yōu)。 —— 最優(yōu)解不一定是基可行解，基可行解也不一定是最優(yōu)解。即從可行域的一個(gè)頂點(diǎn)沿約束邊界轉(zhuǎn)換到可行域的另一個(gè)相鄰的且使目標(biāo)函數(shù)值有改進(jìn)的頂點(diǎn)，直到目標(biāo)函數(shù)值到達(dá)最優(yōu)時(shí)的頂點(diǎn)為止 。 167。 c1 … cm cm+1 … cB xB b x1 … xm xm+1 … xn c1 x1 b1 1 … 0 a1,m+1 … a1,n c2 x2 b2 0 … 0 a2,m+1 … a2,n … … … … … … … … … cm xm bm 0 … 1 am,m+1 … am,n 0 … 0 … jc ?1 , 11mm i i mic c a???? ?,1mn i i nic c a?? ?167。 1 對(duì)線性規(guī)劃的回顧 單純形法 (單純形法的解題 步驟 ) 檢驗(yàn)各非基變量 xj（ j=m+1， m+2， … ， n）的檢驗(yàn)數(shù) δj，若 δj≤0，則已得最優(yōu)解，停止計(jì)算，否則轉(zhuǎn)入 3。 根據(jù) ，確