管理運籌學(xué)第2章線性規(guī)劃課件

第2章線性規(guī)劃2/6/20231課件教學(xué)目標(biāo)與要求【教學(xué)目標(biāo)】通過對本章的學(xué)習(xí)，理解線性規(guī)劃的含義、解、可行解、可行域、基解、基可行解、最優(yōu)解的定義；掌握圖解法、單純形法（包括大M法）；會建立線性規(guī)劃數(shù)學(xué)模型；至少掌握一種軟件求解LP【知識結(jié)構(gòu)】2/6/20232課件導(dǎo)入案例——最優(yōu)生產(chǎn)計劃2/6/20233課件2.1.1線性規(guī)劃問題的提出產(chǎn)品甲產(chǎn)品乙生產(chǎn)能力設(shè)備A設(shè)備B2111108單位利潤32承導(dǎo)入案例設(shè)兩種產(chǎn)品產(chǎn)量為x1,x2,則有:總利潤表達式最大化設(shè)備A臺時占用設(shè)備B臺時占用生產(chǎn)能力,不允許超過產(chǎn)量非負決策變量

（decisionvariable）目標(biāo)函數(shù)

（objectivefunction）約束條件

（subjectto）三要素當(dāng)目標(biāo)函數(shù)與約束條件均為決策變量的線性函數(shù)，且變量取連續(xù)值時，稱為線性規(guī)劃LP；變量取整稱為整數(shù)線性規(guī)劃ILP；變量取二進制為0-1規(guī)劃BLP。2/6/20235課件2.1.2線性規(guī)劃的數(shù)學(xué)模型【例2.1】（合理配料問題）由下表建立一個LP模型求解滿足動物成長需要又使成本最低的飼料配方。飼料營養(yǎng)甲(g/kg)營養(yǎng)乙(g/kg)營養(yǎng)丙(g/kg)成本(g/kg)10.50.10.082220.060.76330.040.35541.50.150.25450.80.20.023解設(shè)xi為第i種飼料的用量，有：滿足營養(yǎng)甲需求滿足營養(yǎng)乙需求滿足營養(yǎng)丙需求變量非負限制目標(biāo)是總成本最低2/6/20236課件2.1.2線性規(guī)劃的數(shù)學(xué)模型線性規(guī)劃的一般形式：線性規(guī)劃的集合形式：線性規(guī)劃的向量形式：線性規(guī)劃的矩陣形式：2/6/20237課件2.1.3線性規(guī)劃的標(biāo)準(zhǔn)模型【例2.2】將LP模型轉(zhuǎn)化為標(biāo)準(zhǔn)式解（1）決策變量變?yōu)榉秦摚?）目標(biāo)函數(shù)最大化（3）右端項變?yōu)榉秦摚?）約束一、三添加松弛變量；約束二減剩余變量。2/6/20239課件2.2.1線性規(guī)劃幾何解的有關(guān)概念2/6/202310課件可行域2.2.2圖解法基本步驟建立直角坐標(biāo)系；圖示約束條件，確定右行域；圖示目標(biāo)函數(shù)一根基線，按目標(biāo)要求平行移動，與可行域相切，切點即為最優(yōu)解；求出切點坐標(biāo)，并代入目標(biāo)函數(shù)求得最優(yōu)值。【例2.3】用圖解法求LP最優(yōu)解ox1x22x1+x2=10x1+x2=8令3x1+2x2=121058864(2,6)z=3×2+2×6=18最優(yōu)解：x1=2,x2=6最優(yōu)值：z=182/6/202311課件2.3.1線性規(guī)劃解的有關(guān)概念及性質(zhì)承導(dǎo)入案例LP模型：ACXbCNCBXNXBNBb基基變量非基非基變量B-1b基解;若滿足XB≥0,稱基可行解.2/6/202313課件2.3.2單純形法一般而言，B為A中任一m×m階使XB非負、XN為0的可逆矩陣，由：約束條件兩端左乘B-1得基變量的非基變量表達：代入目標(biāo)函數(shù)，得：常數(shù)考察該項可見目標(biāo)函數(shù)為非基變量的線性函數(shù)。當(dāng)σN所有元素非正時，目標(biāo)函數(shù)值達到最大，得到了最優(yōu)解。因為任何一個非基變量入基后，不會使目標(biāo)函數(shù)值增大。若σN某元素（假設(shè)第k個元素）>0，則該非基變量入基，會使目標(biāo)函數(shù)值增大。σN中若有多個元素>0，選擇其中最大的（假設(shè)第k個元素）非基變量xk入基，會使目標(biāo)函數(shù)值增加的更快，于是確定xk為入基變量，σN稱為檢驗數(shù)。2/6/202314課件2.3.2單純形法由于基變量為m個，有一個入基，必然有一個出基，哪個出基呢？在確定初始基時，選擇B為單位矩陣，則下式可簡化為：即：xk入基,其余仍為0，故有當(dāng)xk的值由0增加到θ時，原來的基變量xl取值首先變成零，選擇其為出基變量。稱θ的表達式為最小比值原則。如果所有aik≤0,xk的值可以由0增加到無窮，表示可行域是不封閉的，且目標(biāo)函數(shù)值隨進基變量的增加可以無限增加，此時不存在有限最優(yōu)解。下面對以上討論進行總結(jié).2/6/202315課件2.3.2單純形法2/6/202317課件2.3.2單純形法例：承導(dǎo)入案例x1x2x3x4基cj3200bx3x40021111001108cj-zjB標(biāo)準(zhǔn)化基可行解3210/2=58/1=8[]2/6/202318課件2.3.2單純形法x1x2x3x4基cj3200bθx3x400[2]111100110858cj-zj320x1x2x3x4基cj3200bθx1x430101/2[1/2]1/2-1/20153106cj-zj1/2-3/215將入基變量替換出基變量，列出新的單純形表，并通過初等變換將新基變成單元陣：x1x2x3x4基cj3200bθx1x23210011-1-1226cj-zj-1-118最優(yōu)解最優(yōu)值2/6/202319課件2.4工人變量法【例2.4】求解LP問題標(biāo)準(zhǔn)化添加人工變量X1X2X3X4基cj320-MB-1b比值X4X3-M0[2]111011010858σj=cj-zj32*M21X1X2X3X4基cj320-MB-1b比值X1X2321001-111-126σj=cj-zj-1-118*M-1X1X2X3X4基cj320-MB-1b比值X1X330101/2[1/2]011/2-1/25358σj=cj-zj1/2-3/2*M-12/6/202321課件2.5應(yīng)用舉例2/6/202322課件案例2-1廣告媒體選擇≥2400000≥10≥2≤300000≤180000max目標(biāo)函數(shù)可達消費者人數(shù)總費用限制電視廣告費限制2/6/202323課件案例2-2公司投資計劃2/6/202325課件案例2-3自制/外購計劃設(shè)x1,x2,x3自制甲,乙,丙數(shù)量;