【正文】 的 1～ 4月份的 4個月內(nèi)租用倉庫堆放物資 。 倉庫租借費用隨合同期而定 ， 期限越長 ， 折扣越大 ，具體數(shù)字如表 12所示 。 因此 ，該廠可根據(jù)需要 ， 在任何一個月初辦理租借合同 。 運籌學(xué)教程 2022/2/14 8 假設(shè)用 xij表示捷運公司第 i（ i＝ 1， 2， … ， 4） 個月月初簽訂租借期為 j（ j＝ 1， 2， … ， 4） 個月的倉庫面積數(shù) (單位為 100m2） 。求： 5年末總資本最大運籌學(xué)教程 2022/2/14 9 組成線性規(guī)劃模型的三個要素 max Z＝ 2x1＋ x2 5x2≤15 6x1＋ 2x2≤24 x1＋ x2≤5 x1， x2≥0 目標(biāo)函數(shù) ： 約束條件 （ 1）變量（決策變量） : 它是規(guī)劃中要確定的未知量 ，是用數(shù)量方式來表示的方案或措施 ， 可由決策者決定和控制 。 （ 3）約束條件： 指決策變量取值時受到的各種資源條件的限制 ， 通常用等式或不等式來表達 。 由于目標(biāo)函數(shù)是決策變量的線性函數(shù) ， 約束條件是含決策變量的線性等式或不等式 ，所以此類模型稱為線性規(guī)劃的數(shù)學(xué)模型 。 二是 可迭加性 。 運籌學(xué)教程 2022/2/14 10 模型中， cj稱為價值系數(shù)。 aij稱為技術(shù)系數(shù)或工藝系數(shù)。 則線性規(guī)劃模型的一般形式為： max(或 min)z＝ c1x1+c2x2+… +xn a11x1+a12x2+… +a1nxn≤（ 或＝ ， ≥） b1 a21x1+a22x2+… +a2nxn≤（ 或＝ ， ≥） b2 ………………………………………… am1x1+am2x2+… +amnxn≤（ 或＝ ， ≥） bm x1,x2,… ,xn≥0 ?????=?=?=?=??==),2,1(0),2,1(),(m in )m a x (11njxmibxaxczjinjjijnjjj??或或簡寫為： ???????=?=?=0),(m in )m a x (1jnjjjxbxPCXz或或向量形式： ?????=?=0(m in )m a x (XbAXCXz），或或矩陣形式： ),( 21 ncccC ?=????????????=mjjjjaaaP?21??????????=mbbbb?21??????????=mnmmnnaaaaaaaaaA??????212222111211運籌學(xué)教程 2022/2/14 11 三、線性規(guī)劃問題的標(biāo)準(zhǔn)形式 若得出的線性規(guī)劃模型不是標(biāo)準(zhǔn)形式 ， 應(yīng)通過下列方法將其化為標(biāo)準(zhǔn)形式： ， 即 ?????=?===??==),2,1(0),2,1(m a x11njxmibxaxczjinjjijnjjj??本教材規(guī)定，線性規(guī)劃模型的標(biāo)準(zhǔn)形式為： 其特點是： (1)目標(biāo)函數(shù)求極大； (2)約束條件取等式； (3)變量非負(fù)； (4)約束條件右邊常數(shù)為正值 。 當(dāng)約束條件為 “ ≤” 時 ， 在約束符號的左邊加上一個松弛變量 ， 將 “ ≤” 變?yōu)?“ ＝ ” ； 如 6x1+2x2≤24,化為標(biāo)準(zhǔn)形式為 6x1+2x2＋ x3＝ 24， x3≥0。 。 x ≤ 0的情況 ， 令 xˊ＝－ x， 顯然 xˊ≥0。 運籌學(xué)教程 2022/2/14 13 例 3 將下述線性規(guī)劃模型化為標(biāo)準(zhǔn)形式 min z＝ x1+2x2+3x3 － 2x1+x2+x3≤9 － 3x1+x2+2x3≥4 4x1－ 2x2－ 3x3＝－ 6 x1≤0， x2≥0， x3取值無約束 （ 左邊減去 x8） （ 令 z1＝－ z） （ 左邊加上 x7） （ 兩邊同時乘以 － 1） 解： 令 x4＝－ x1， x3＝ x5－ x6代入上式，其中 x4， x5， x6≥0 min z＝－ x4+2x2+3（ x5－ x6) 2x4+x2+(x5－ x6)≤9 3x4+x2+2(x5－ x6)≥4 － 4x4－ 2x2－ 3(x5－ x6)＝－ 6 x2,x4,x5,x6≥0 max z1 ＝－ 2x2＋ x4－ 3x5＋ 3x6 x2 +2x4+ x5－ x6＋ x7＝ 9 x2+ 3x4+2x5－ 2x6－ x8＝ 4 2x2＋ 4x4＋ 3x5－ 3x6＝ 6 x2,x4,x5,x6,x7,x8≥0 該線性規(guī)劃問題的標(biāo)準(zhǔn)形式為 運籌學(xué)教程 2022/2/14 14 0123450 1 2 3 4167。 圖解法的目的：一是判別線性規(guī)劃問題的求解結(jié)局；二是在存在最優(yōu)解的條件下 ， 把問題的最優(yōu)解求出來 。 例： max z＝ 2x1＋ x2 5x2≤15 6x1＋ 2x2≤24 x1＋ x2≤5 x1， x2≥0 Q1 Q3 Q2 Q4 O x1 x2 5x2＝ 15 6x1＋ 2x2＝ 24 x1＋ x2＝ 5 z＝ 2 z＝ (， ) 6x1＋ 2x2＝ 24 x1＋ x2＝ 5 聯(lián)立 單純形法 返回第一章目錄 運籌學(xué)教程 2022/2/14 15 二、線性規(guī)劃問題求解的幾種可能結(jié)局 上例用圖解法解得線性規(guī)劃問題的最優(yōu)解為 x1＝ ， x2＝， 與最優(yōu)解相應(yīng)的目標(biāo)函數(shù)值 z＝ 。 除此之外 ， 線性規(guī)劃問題的求解還有以下幾種情況： 。 ， 或無可行解 。 遺漏必要的約束條件 約束條件之間存在矛盾 運籌學(xué)教程 2022/2/14 16 三、由圖解法得到的起示 ， 解的情況有： 有唯一最優(yōu)解；無窮多最優(yōu)解；最優(yōu)解無界 （ 無界解 ） ；無可行解 。 ， 則最優(yōu)解或最優(yōu)解之一 （ 如果有無窮多解的話 ） 一定是可行域的某個頂點 。 比較周圍相鄰頂點的目標(biāo)函數(shù)值是否比這個值大 ， 如果不是 ， 則該頂點就是最優(yōu)解點或最優(yōu)解的點之一 ， 否則轉(zhuǎn)到比這個點的目標(biāo)函數(shù)值更大的另一頂點 ， 重復(fù)上述過程 ， 直到找出使目標(biāo)函數(shù)值達到最大的頂點為止 。 13 單純形法原理 可行解：滿足 （ 2） 、 （ 3）式的解稱為可行解 。 最優(yōu)解 ： 使目標(biāo)函數(shù) （ 1）達到最大值的可行解稱為最優(yōu)解 。 ??????????=mnmmnnaaaaaaaaaA???????21222211211 ),(21212222111211mmmmmmmPPPaaaaaaaaaB ????????=????????????=系數(shù)矩陣 基 ： 圖解法 返回第一章目錄 運籌學(xué)教程 2022/2/14 18 一、線性規(guī)劃問題的解的概念 基 B中的每一個列向量 Pj(j=1， 2， … ， m） 稱為 基向量 ， 與基向量 Pj對應(yīng)的變量 xj稱為 基變量 ； 除基變量以外的變量稱為 非基變量 。 加上非基變量取 0的值 ， 得 X＝ （ x1,x2,… ， xm,0,… ,0） T。 運籌學(xué)教程 2022/2/14 19 基可行解 ：滿足非負(fù)約束的解稱為基可行解 。 例： 找出下述線性規(guī)劃問題的全部基解 ， 指出其中的基可行解 ， 并確定最優(yōu)解 。 打√者為基可行解 。 若對于 C中任意兩點 X1， X2滿足 αX1 + (1 α )X2∈C (0 ＜ α ＜ 1) 則稱 C為凸集 。 即 ： X＝ α X1 + (1 α )X2∈C (0 ＜ α ＜ 1) 稱 C為凸集 。 二、凸集和頂點 凸集 凸集 凸集 凸集 凸集 凸集 運籌學(xué)教程 2022/2/14 21 不是凸集 不是凸集 不是凸集 不是凸集 二、凸集和頂點 頂點 設(shè) K為凸集 ， X∈C ， 若 X不能用 C中不同的兩點 X1，X2的線性組合表示為 X＝ α X1+(1α )X2 ∈C (0 ＜ α ＜ 1) 則稱 X為 C的一個頂點 （ 或極點 ） 。 運籌學(xué)教程 2022/2/14 22 三、 線性規(guī)劃的基本定理 定理 1：若線性規(guī)劃問題存在可行解 ， 則問題的可行域是凸集 。 定理 2：線性規(guī)劃的基本可行解對應(yīng)于其可行域的頂點 。 單純形法迭代原理 運籌學(xué)教程 2022/2/14 23 定理 1：若線性規(guī)劃問題存在可行解 ， 則問題的可行域是凸集 。 設(shè) X1=(x11,x12,… ， x1n)T, X2=(x21,x22,… ， x2n)T為 C內(nèi)任意兩點 ，即 X1∈C ， X2∈C ， 將 X1 ， X2代入約束條件 ， 有 ∑ Pjx1j＝ b j=1 n ∑ Pjx2j＝ b j=1 n ； （ 19） X1， X2連線上任意一點可表示為： X＝ aX1＋ （ 1－ a） X2 （ 0a1) (110) 將 （ 19） 代入 （ 110） 得： bbbbxPxPxPxxPxPnjnjnjjjjjjjnjnjjjjjj=??=??=??=? ? ?? ?= = == =aaaaaa1 1 12211 121 ])1([所以 X1∈C ， X2∈C 。 運籌學(xué)教程 2022/2/14 24 引理 線性規(guī)劃的可行解 X =(x1,x2,…, xn)為基可行解的充要條件是 X 的正分量所對應(yīng)的系數(shù)列向量線性獨立。 由基可行解的定義得證 。 若向量 P1,P2,… ,Pk線性獨立 ， 則必有 k≤m時；當(dāng) k= m時 ， 它們恰好構(gòu)成一個基 ， 從而X=(x1,x2, … ,xm,0,… ,0)T為相應(yīng)的基可行解 。 返回 運籌學(xué)教程 2022/2/14 25 定理 2： 線性規(guī)劃的基本可行解對應(yīng)于其可行域的頂點 。 用反證法證明： X不是可行域的頂點 ?X不是基可行解 。 假設(shè) X的前 m個分量為正 ， 有 )(1bxPnjjj =?=運籌學(xué)教程 2022/2/14 26 由引理知 P1,P2,… ,Pm線性相關(guān) ， 即存在一 組不全為零的數(shù) δ i(i=1,2,… ， m),使得 d1P1+d2P2+… +dmPm= 0 () 將 （ ） 乘以一個不全為零的數(shù) μ得 md1P1+md2P2+…+ mdmPm= 0 () ()+()得： (x1＋ md1)P1+(x2＋ md2)P2+…+(x m＋ mdm)Pm=b ()()得： (x1－ md1)P1+(x2－ md2)P2+…+(x m－ mdm)Pm=b 令 X(1)=[(x1＋ md1),(x2＋ md2), … ,(xm＋ mdm),0, … ,0] X(2)=[(x1－ md1),(x2－ md2), … ,(xm－ mdm),0, … ,0] 又 m可以這樣來選擇 ， 使得對所有 i=1,2, … ,m有 xi177。 引理 運籌學(xué)教程 2022/2/14 27 （ 2） X不是可行域的頂點 ?X不是基本可行解。 (0a1。 運籌學(xué)教程 2022/2/14 28 是目標(biāo)函數(shù)的最大值。 證：設(shè) X(0)=(x10,x20,… ,xn0)是線性規(guī)劃的一個最優(yōu)解 ， 若 X(0)不是基可行解 ， 由定理 2知 X(0)不是頂點 ， 一定能在可行域內(nèi)找到通過 X(0)的直線上的另外兩個點 （ X(0)+md)≥0和 （ X(0)－ md） ?0。 C(X(0)－ md)＝ CX(0)－ Cmd 因 CX(0)為目標(biāo)函數(shù)的最大值 ， 故有 CX(0) ≥ CX(0)＋ Cmd ； CX(0) ≥ C