【正文】 ：線性等式或不等式 ? 目標(biāo)函數(shù)： Z=?(x1 … xn) 線性式，求 Z極大或極小 關(guān)于線性的界定 ?如果規(guī)劃問題的數(shù)學(xué)模型中，決策變量的取值可以是連續(xù)的，目標(biāo)函數(shù)是決策變量的線性函數(shù)，約束條件是含決策變量的線性等式或不等式，則該類規(guī)劃問題的數(shù)學(xué)模型稱為線性規(guī)劃的數(shù)學(xué)模型。 ?二是可疊加性，如生產(chǎn)多種產(chǎn)品時對某項資源的消耗量應(yīng)等于各產(chǎn)品對該項資源的消耗量的和。問運輸（存儲）方案？ 設(shè) xij為 i 倉庫運到 j工廠的原棉數(shù)量 (i ＝ 1， 2， 3， j ＝ 1，2， 3) minZ= 2x11 + x12+3x13+2x21 +2x22 +4x23 +3x31 +4x32 +2x33 x11 +x12+x13 ? 50 x21+x22+x23 ? 30 x31+x32+x33 ? 10 x11 +x21+x31 = 40 x12 +x22+x32 = 15 x13 +x23+x33 = 35 xij ? 0 練習(xí) 2 、連續(xù)投資 10萬元 A：從第 1年到第 4年每年初投資，次年末回收本利 B： 第 3年初投資，到第 5年末回收 ，最大投資 4萬元 C： 第 2年初投資，到第 5年末回收 ，最大投資 3萬元 D： 每年初投資，每年末回收 。 k =A,B,C,D )第 i年初投 k項目的資金數(shù) MaxZ= + x2C++ x1A+x1D=10 x2A+x2C+x2D= x1D x2C? 3 x3A +x3B+x3D = x1A+ x2D x3B ? 4 x4A +x4D = x2A+ x3D x5D = x3A+ x4D xik ? 0 應(yīng) 用 ? 市場營銷 (廣告預(yù)算和媒介選擇，競爭性定價，新產(chǎn)品開發(fā)，制定銷售計劃 ) ? 生產(chǎn)計劃制定 (合理下料，配料，“生產(chǎn)計劃、庫存、勞力綜合” ) ? 庫存管理 (合理物資庫存量，停車場大小，設(shè)備容量 ) ? 運輸問題 ? 財政、會計 (預(yù)算，貸款，成本分析，投資，證券管理 ) ? 人事 (人員分配，人才評價，工資和獎金的確定 ) ? 設(shè)備管理 (維修計劃，設(shè)備更新 ) ? 城市管理 (供水，污水管理，服務(wù)系統(tǒng)設(shè)計、運用 ) 線性規(guī)劃的適用情況 ?要解決的問題的目標(biāo)可以用數(shù)值指標(biāo)反映 ?對于要實現(xiàn)的目標(biāo)有多種方案可選擇 ?有影響決策的若干約束條件 3．線性規(guī)劃標(biāo)準(zhǔn)形式 線性規(guī)劃模型的結(jié)構(gòu) 目標(biāo)函數(shù) ： max， min 約束條件： ≥,=,≤ 變量符號：： ≥0, ≤0 線性規(guī)劃的標(biāo)準(zhǔn)形式 目標(biāo)函數(shù)： max 約束條件 ： = 變量符號 ： ≥0 線性規(guī)劃標(biāo)準(zhǔn)型的幾種表示法 (一 )、一般型 a11X1+ a12X2+…+ a 1nXn =b1 a21X1+ a22X2+…+ a 2nXn =b2 … … … … am1X1+ am2X2+…+ a mnXn =bm Xj ?0(j=1,2,…,n ) MaxZ=C1X1+ C2X2+…+C nXn 其中 bi ?0 (i=1,2,…,m ) (二 )、矩陣型 maxZ=CX AX=b X ?0 b?0 P1 P2 ……… Pn a11 a12 ……… a 1n 其中 A= a21 a22 ……… a2n ………………… am1 am2 ………a mn X1 X= X2 Xn … b1 b= b2 bm … C=(C1 C2 …C n ) (三 )、向量型 X1 AX=(P1 P2 …P n ) X2 = b Xn … CXZ ?m a x?????????01XbxpnjjjP1 X1+ P2 X2 + … +P n Xn=b (四 )、化標(biāo)準(zhǔn)型 (1)、約束條件 (2)、變量 (3)、目標(biāo)函數(shù) (4)、右端常數(shù) (1)、約束條件 X3為松弛變量 X4為剩余變量 松弛變量或剩余變量在實際問題中分別表示未被充分利用的資源和超出的資源數(shù)，均未轉(zhuǎn)化為價值和利潤，所以引進模型后它們在目標(biāo)函數(shù)中的系數(shù)均為零。X3 +0X5 x1 + 2x2 ? 30 3x1 + 2x2 ? 60 2x2 ? 24 x1， x2 ? 0 例： max Z= 40x1 +50x2 松弛變量 例： 4x1 + 6x2 + x3+2x4 ?12 x1 + x2 +7x3+5x4 ?14 2x2 + x3+3x4 ? 8 xi ? 0 (i =1,…, 4) 4X1+6X2+ X3 +2X4 X5 =12 X1+ X2+7X3+5X4 X6 =14 2X2+ X3+3X4 X7=8 X1 , …, X7 ?0 剩余變量 (2)、變量 3 X139。 X1 4X2 ? 14 X139。 X1 X取值無約束的情況。 令 X= X39。 +X2 ? 11 X139。 , X2 ?0 X兩邊有約束的情況。 = X1 +6 0 ? X139。m a x令 Z39。 例：將 min Z = X1+2X2 3X3 X1+X2 +X3? 7 X1 X2 +X3 ?2 X1， X2?0， X3無限制 化為標(biāo)準(zhǔn)型 解： ① 令 X3 =X4 X5 ② 加松弛變量 X6 ③ 加剩余變量 X7 ④ 令 Z39。= X1 2X2 +3X4 3X5 X1 +X2 +X4 X5 +X6=7 X1 X2 +X4 X5 X7 =2 X1 , X2 , X4 , … , X7 ?0 min Z = X1+2X2 3X3 X1+X2 +X3? 7 X1 X2 +X3 ?2 X1， X2?0， X3無限制 練 習(xí) 作業(yè) 課本 P44 1． 2 4．線性規(guī)劃的圖解法 AX=b (1) X ? 0 (2) maxZ=CX (3) 定義 1： 滿足約束 (1)、 (2)的 X=(X1 … Xn)T稱為 LP問題的可行解，全部可行解的集合稱為可行域。 圖解法的步驟： 在平面上建立直角坐標(biāo)系 圖示約束條件，找出可行域 圖示目標(biāo)函數(shù)和尋找最優(yōu)解 例 maxZ=40X1+ 50X2 X1+2X2 ? 30 3X1+2X2 ? 60 2X2 ? 24 X1 , X2 ?0 解： (1)、確定可行域 X1 ?0 X1 =0 (縱 ) X2 ?0 X2=0 (橫 ) X1+2X2 ? 30 X1+2X2 =30 (0,15) (30,0) X2 0 10 20 30 D A B C 3X1+2X2 =60 (0,30) (20,0) 2X2 =24 20 30 10 X1 X1+2X2 ? 30 3X1+2X2 ? 60 2X2 ? 24 X1 , X2 ?0 (2)、求最優(yōu)解 解： X* = (15,) Zmax =975 Z=40X1+50X2 0=40X1+50X2 (0,0)， (10,8) X2 0 10 20 30 20 30 10 X1 D A B C C點： X1+2X2 =30 3X1+2X2 =60 Z= 40 X1 + 80X2 =0 X1 + 2X2 =30 D A B C X2 0 X1 最優(yōu)解： BC線段 B點 C點 X(1)=(6,12) X(2)=(15,) X=? X(1)+(1?) X(2) (0? ? ? 1) 求解 例 maxZ=40X1+ 80X2 X1+2X2 ? 30 3X1+2X2 ? 60 2X2 ? 24 X1 , X2 ?0 X1 =6? + (1 ? ) X1 =159? X2 =+? (0? ? ? 1) X= = ? +(1? ) maxZ=1200 X1 6 15 X2 12 無界解 無有限最優(yōu)解 例 maxZ=2X1+ 4X2 2X1+X2 ?8 2X1+X2 ? 2 X1 , X2 ?0 Z=0 2X1+ X2=8 2X1+ X2=2 8 2 4 6 X2 4 0 X1 例 maxZ=3X1+2X2 X1 X2 ?1 X1 , X2 ?0 無解 無可行解 1 X1 1 X2 0 總 結(jié) 唯一解 無窮多解 無有限最優(yōu)解 無可行解 有解 無解 當(dāng)目標(biāo)函數(shù)的直線族與某約束條件平行，且該問題有解時。 有解但可行域可伸展到無窮時 由圖解法得到的啟示 (1)、線性規(guī)劃問題的解的情況有四種：唯一最優(yōu)解；無窮多最優(yōu)解；無界解；無可行解。 (2)、若線性規(guī)劃可行域存在，則可行域是一個凸集。 練 習(xí) 課本 P35 1． 1 作業(yè)： 5．線性規(guī)劃基本概念 maxZ=CX AX =b X?0 Am n 滿秩 X = (x1… x n)T 一、線性規(guī)劃問題的解的概念 先復(fù)習(xí)線性規(guī)劃標(biāo)準(zhǔn)型的一般型、向量型和矩陣型 補充：秩的概念 矩陣的行向量組的秩 ， 也就是行向量組中最大線性無關(guān)組所含向量的個數(shù) ，稱為矩陣的行秩；矩陣的列向量組的秩 ， 也就是列向量組中最大線性無關(guān)組所含向量的個數(shù) ， 稱為矩陣的列秩 ， 可以證明：矩陣的行秩等于矩陣的列秩 。 由此及行列式的性質(zhì)可得到結(jié)論： 1. R(A)=0?A=0； 2. 對于 Am*n， 有 0=R(A)=min(m,n)； 3. 若 R(A)=r， 則 A中至少有一個子式 Dr(A)0， 而所有的 Dr+1(A)=0. 設(shè) A是 n階矩陣 ， 若秩 (A)=n， 則稱 A為 滿秩矩陣 ， 或 非奇異的 ， 或 非退化的 。 因此僅當(dāng)矩陣是方陣時 ， 滿秩陣才是可逆陣 。 B中的每一個列向量 Pj稱為基向量，與基向量對應(yīng)的變量稱為基變量，其他變量稱為非基變量。全部可行解的集合稱為可行域。 定義 4： 基本解 —— 對應(yīng)于基 B， X= 為 AX=b的一個解 ，則 X為線性規(guī)劃問題的基本解，也稱基解 。 B1 b 0 ※ 基本解中最多有 m個非零分量。 n! m!(nm)! 定義 6： 可行基 —— 對應(yīng)于基可行解的基稱為可行基。 定義 1： 凸集 ——如果集合 D中任意兩個點， 其連線上的所有點也都是集 合 D中的點，則稱 D為凸集。1 , 181。k 滿足