運籌學(xué)課件線性規(guī)劃

第2章線性規(guī)劃遼寧工業(yè)大學(xué)韓宇鑫

管理運籌學(xué)課件16一月2023【教學(xué)目標(biāo)】理解線性規(guī)劃基本概念：解、可行解、可行域、基解、基可行解、最優(yōu)解掌握圖解法、單純形法（包括大M法）；會建立線性規(guī)劃數(shù)學(xué)模型；了解一種軟件求解LP【知識結(jié)構(gòu)】管理運籌學(xué)課件16一月2023導(dǎo)入案例——最優(yōu)生產(chǎn)計劃管理運籌學(xué)課件16一月2023本章主要內(nèi)容2.1線性規(guī)劃問題與模型2.1.1線性規(guī)劃問題的提出2.1.2線性規(guī)劃的數(shù)學(xué)模型2.1.3線性規(guī)劃標(biāo)準(zhǔn)模型2.2圖解法2.2.1線性規(guī)劃幾何解的有關(guān)概念2.2.2圖解法基本步驟2.2.3線性規(guī)劃幾何解的討論2.3單純形法2.3.1線性規(guī)劃解的有關(guān)概念及性質(zhì)2.3.2單純形法2.4人工變量法2.5線性規(guī)劃應(yīng)用舉例案例2-1媒體選擇問題案例2-2投資計劃問題案例2-3自制/外購決策問題案例2-4合理下料問題本章小結(jié)管理運籌學(xué)課件16一月20232.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)量非負(fù)決策變量

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

（objectivefunction）約束條件

（subjectto）三要素當(dāng)目標(biāo)函數(shù)與約束條件均為決策變量的線性函數(shù)，且變量取連續(xù)值時，稱為線性規(guī)劃LP；變量取整稱為整數(shù)線性規(guī)劃ILP；變量取二進(jìn)制為0-1規(guī)劃BLP。管理運籌學(xué)課件16一月20232.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)丙需求變量非負(fù)限制目標(biāo)是總成本最低管理運籌學(xué)課件16一月20232.1.2線性規(guī)劃的數(shù)學(xué)模型線性規(guī)劃的一般形式：線性規(guī)劃的集合形式：線性規(guī)劃的向量形式：線性規(guī)劃的矩陣形式：管理運籌學(xué)課件16一月20232.1.3線性規(guī)劃的標(biāo)準(zhǔn)模型標(biāo)準(zhǔn)形式:

目標(biāo)函數(shù)最大化、約束條件為等式、決策變量均非負(fù)、右端項非負(fù).非標(biāo)準(zhǔn)形式進(jìn)行如下轉(zhuǎn)化:1.目標(biāo)函數(shù)最小2.不是等式約束管理運籌學(xué)課件16一月20232.1.3線性規(guī)劃的標(biāo)準(zhǔn)模型【例2.2】將LP模型轉(zhuǎn)化為標(biāo)準(zhǔn)式解（1）決策變量變?yōu)榉秦?fù)（2）目標(biāo)函數(shù)最大化（3）右端項變?yōu)榉秦?fù)（4）約束一、三添加松弛變量；約束二減剩余變量。管理運籌學(xué)課件16一月20232.2.1線性規(guī)劃幾何解的有關(guān)概念存在唯一最優(yōu)解的線性規(guī)劃問題可行域2.2.2圖解法基本步驟建立直角坐標(biāo)系；圖示約束條件，確定右行域；圖示目標(biāo)函數(shù)一根基線，按目標(biāo)要求平行移動，與可行域相切，切點即為最優(yōu)解；求出切點坐標(biāo)，并代入目標(biāo)函數(shù)求得最優(yōu)值?！纠?.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=18例

用圖解法求解

max

z=x1+x2

s.t.

x1+2x2

4

x1-2x2

5

x1,x2

014235123x1

x2x1+2x2

4x1-2x2

5

無可行解的線性規(guī)劃問題例用圖解法求解：

max

z=2x1+x2

s.t. x1+x2

2

x1-2x2

0

x1

,

x2

014235123x1

x2x1+x2

2z=2x1+x2x1-2x2

0無界的線性規(guī)劃問題例

用圖解法求解：

max

z=40x1+30x2

s.t.

4x1+3x2

120

2x1+x2

50x10，x20x2

x1

4050302x1+x2

5020101020304x1+3x2

120z=40x1+30x2

存在無窮多最優(yōu)解管理運籌學(xué)課件16一月20232.2.3線性規(guī)劃幾何解的討論線性規(guī)劃幾何解存在四種情況：唯一最優(yōu)解、無窮多最優(yōu)解、無界解、無可行解。

可行域為封閉有界區(qū)域時，可能存在唯一最優(yōu)解，無窮多最優(yōu)解兩種情況；

可行域為非封閉無界區(qū)域時，可能存在唯一最優(yōu)解，無窮多最優(yōu)解，無界解三種情況；

可行域為空集時，沒有可行解，原問題沒有最優(yōu)解。若線性規(guī)劃存在最優(yōu)解，則最優(yōu)解或最優(yōu)解之一肯定能夠在可行域（凸集）的某個極點找到（所謂凸集是指集合中任何兩點的連線上的點仍在集合中）。管理運籌學(xué)課件16一月20232.3.1線性規(guī)劃解的有關(guān)概念及性質(zhì)承導(dǎo)入案例LP模型：ACXbCNCBXNXBNBb基基變量非基非基變量B-1b基解;若滿足XB≥0,稱基可行解.管理運籌學(xué)課件16一月20232.3.2單純形法一般而言，B為A中任一m×m階使XB非負(fù)、XN為0的可逆矩陣，由：約束條件兩端左乘B-1得基變量的非基變量表達(dá)：代入目標(biāo)函數(shù)，得：常數(shù)考察該項可見目標(biāo)函數(shù)為非基變量的線性函數(shù)。當(dāng)σN所有元素非正時，目標(biāo)函數(shù)值達(dá)到最大，得到了最優(yōu)解。因為任何一個非基變量入基后，不會使目標(biāo)函數(shù)值增大。若σN某元素（假設(shè)第k個元素）>0，則該非基變量入基，會使目標(biāo)函數(shù)值增大。σN中若有多個元素>0，選擇其中最大的（假設(shè)第k個元素）非基變量xk入基，會使目標(biāo)函數(shù)值增加的更快，于是確定xk為入基變量，σN稱為檢驗數(shù)。管理運籌學(xué)課件16一月20232.3.2單純形法由于基變量為m個，有一個入基，必然有一個出基，哪個出基呢？在確定初始基時，選擇B為單位矩陣，則下式可簡化為：即：xk入基,其余仍為0，故有當(dāng)xk的值由0增加到θ時，原來的基變量xl取值首先變成零，選擇其為出基變量。稱θ的表達(dá)式為最小比值原則。如果所有aik≤0,xk的值可以由0增加到無窮，表示可行域是不封閉的，且目標(biāo)函數(shù)值隨進(jìn)基變量的增加可以無限增加，此時不存在有限最優(yōu)解。下面對以上討論進(jìn)行總結(jié).管理運籌學(xué)課件16一月20232.3.2單純形法單純形法解題步驟:使LP模型右端項非負(fù)、約束符取“=”、目標(biāo)函數(shù)max（即標(biāo)準(zhǔn)化），并設(shè)法在約束系數(shù)中構(gòu)造一個單位矩陣,令其為初始基,該基必為可行基，右端項即為基可行解。求檢驗數(shù).若所有檢驗數(shù)均不大于0，找到最優(yōu)解，計算結(jié)束；若存在大于0的檢驗數(shù)，找出最大者σk

，對應(yīng)的變量xk為入基變量。若alk均不大于0，則解無界，計算結(jié)束，否則找出最小比值：

對應(yīng)的變量xl為出基變量。用入基變量替換出基變量，并通過行初等變換將基變成單位矩陣，右端項即為基可行解，轉(zhuǎn)第2步。管理運籌學(xué)課件16一月20232.3.2單純形法管理運籌學(xué)課件16一月20232.3.2單純形表例：承導(dǎo)入案例x1x2x3x4基cj3200bx3x40021111001108cj-zjB標(biāo)準(zhǔn)化基可行解3210/2=58/1=8[]管理運籌學(xué)課件16一月20232.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)值管理運籌學(xué)課件16一月20232.4工人變量法用單純形法求解LP要求能找出一個單位陣作為初始基。因此，當(dāng)約束符均為“≤”時，把松弛變量作為初始基變量，則可直接列出單純形表；若存在約束符為“≥”或“=”，則不一定能找出一個單位陣，這種情況通常要添加人工變量（artificialvariable），將所有松弛變量和人工變量作為初始基變量，則可列出單純形表。但原本約束已經(jīng)取“=”，因此，必須使人工變量為0才是可行解。故在迭代過程中如果最終單純形表中含有人工變量，則該LP無可行解。采取的辦法是設(shè)目標(biāo)函數(shù)中人工變量的系數(shù)為“-M”（M為任意大的有界正數(shù)），如果最終單純形表中含有人工變量，則目標(biāo)函數(shù)不會實現(xiàn)最大化。這種通過添加人工變量來找初始基的方法稱為人工變量法。求解具有人工變量的LP，通常用“兩階段法”或“大M法”來解決。下面通過例2.3為例，說明“大M法”的應(yīng)用。管理運籌學(xué)課件16一月20232.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-1管理運籌學(xué)課件16一月20232.5應(yīng)用舉例管理運籌學(xué)課件16一月2023案例2-1廣告媒體選擇≥2400000≥10≥2≤300000≤180000max目標(biāo)函數(shù)可達(dá)消費者人數(shù)總費用限制電視廣告費限制管理運籌學(xué)課件16一月2023案例2-2公司投資計劃A、B、C、D四個產(chǎn)品項目投資6000萬元。產(chǎn)品項目A:1~5年每年年初投資，當(dāng)年年末收回本利110%。產(chǎn)品項目B：1~4年每年年初投資，次年年末收回本利125%。產(chǎn)品項目C：第3年年初投資，第5年年末收回本利140%。產(chǎn)品項目D：第2年年初進(jìn)行，第5年年末收回本利155%。每年投資額限制：項目B900萬元，項目C2400萬元，項目D3000萬元。在滿足各個投資項目的限制條件下，使企業(yè)在五年內(nèi)獲得最大的收益。管理運籌學(xué)課件16一月2023案例2-2公司投資計劃管理運籌學(xué)課件16一月2023案例2-3自制/外購計劃設(shè)x1,x2,x3自制甲,乙,丙數(shù)量;x4,x5外購甲,乙數(shù)量單位利潤：自制甲：23-(3+2+3)=15自制乙：18-(5+1+2)=10自制丙：16-(4+3+2)=7外購甲：23-(5+2+3)=13