模型的結(jié)構(gòu)及建模步驟及標(biāo)準(zhǔn)型

1、2020/7/11,第一章 線性規(guī)劃模型和單純形法1.1線性規(guī)劃模型的結(jié)構(gòu)及建模步驟,主講：鄭來(lái)運(yùn) 機(jī)械工程學(xué)院,2020/7/11,光華食品廠主要生產(chǎn)蔥油餅干（型）和蘇打餅干（型）。根據(jù)銷售部門提供的信息可知，目前這兩種餅干在市場(chǎng)上都很暢銷，該廠能生產(chǎn)多少，市場(chǎng)就能賣出多少。但從生產(chǎn)部門得知，有三種關(guān)鍵設(shè)備即攪拌機(jī)、成型機(jī)、烘箱的生產(chǎn)能力，限制了該廠的餅干生產(chǎn)。 該公司每天生產(chǎn)這兩種餅干的量應(yīng)為多少，可使其利潤(rùn)最大？,2020/7/11,2020/7/11,光華食品廠主要生產(chǎn)蔥油餅干（型）和蘇打餅干（型），銷售利潤(rùn)分別為500元/噸和400元/噸。根據(jù)銷售部門提供的信息可知，目前這兩種餅干在

2、市場(chǎng)上都很暢銷，該廠能生產(chǎn)多少，市場(chǎng)就能賣出多少。但從生產(chǎn)部門得知，有三種關(guān)鍵設(shè)備即攪拌機(jī)、成型機(jī)、烘箱的生產(chǎn)能力，限制了該廠的餅干生產(chǎn)。該公司每天生產(chǎn)這兩種餅干的量應(yīng)為多少，可使其利潤(rùn)最大？其具體數(shù)據(jù)如表所示：,例1 資源利用問(wèn)題,2020/7/11,例1 資源利用問(wèn)題,即：生產(chǎn) 蔥油餅干(型) 1噸 蘇打餅干(型) 3噸 企業(yè)利潤(rùn)：1700元,2020/7/11,本節(jié)重點(diǎn)和難點(diǎn)及教學(xué)目標(biāo),重點(diǎn)與難點(diǎn)：如何建立線性規(guī)劃問(wèn)題的數(shù)學(xué)模型？(建模條件、步驟及相應(yīng)的技巧) 教學(xué)目標(biāo)：掌握建模的步驟和方法，能根據(jù)實(shí)際背景抽象和建立適當(dāng)?shù)木€性規(guī)劃模型。,Linear Programming proble

3、m and its Models,2020/7/11,例1 資源利用問(wèn)題,光華食品廠主要生產(chǎn)蔥油餅干（型）和蘇打餅干（型），銷售利潤(rùn)分別為500元/噸和400元/噸。根據(jù)銷售部門提供的信息可知，目前這兩種餅干在市場(chǎng)上都很暢銷，該廠能生產(chǎn)多少，市場(chǎng)就能賣出多少。但從生產(chǎn)部門得知，有三種關(guān)鍵設(shè)備即攪拌機(jī)、成型機(jī)、烘箱的生產(chǎn)能力，限制了該廠的餅干生產(chǎn)。該公司每天生產(chǎn)這兩種餅干的量應(yīng)為多少，可使其利潤(rùn)最大？其具體數(shù)據(jù)如表所示：,2020/7/11,設(shè)：,Step1 -確定決策變量,未知量，可由決策者決定和控制,x1為餅干I的生產(chǎn)數(shù)量 x2為餅干II的生產(chǎn)數(shù)量,Step.1,2020/7/11,問(wèn)題目標(biāo)

4、： 光華食品廠每天生產(chǎn)這兩種餅干的量應(yīng)為多少，可使其利潤(rùn)最大？,目標(biāo)函數(shù)：max Z=5x14x2,Step2 -定義目標(biāo)函數(shù),Step.2,2020/7/11,2020/7/11,光華食品廠主要生產(chǎn)蔥油餅干（型）和蘇打餅干（型）。根據(jù)銷售部門提供的信息可知，目前這兩種餅干在市場(chǎng)上都很暢銷，該廠能生產(chǎn)多少，市場(chǎng)就能賣出多少。但從生產(chǎn)部門得知，有三種關(guān)鍵設(shè)備即攪拌機(jī)、成型機(jī)、烘箱的生產(chǎn)能力，限制了該廠的餅干生產(chǎn)。該公司每天生產(chǎn)這兩種餅干的量應(yīng)為多少，可使其利潤(rùn)最大。其具體數(shù)據(jù)如表所示：,設(shè)備，現(xiàn)有工時(shí)受限制,如何利用現(xiàn)有資源才最好？,辨認(rèn)哪些是決策的關(guān)鍵影響因素？在選取這些關(guān)鍵因素時(shí)存在哪些資源

5、和環(huán)境的限制？,2020/7/11,攪拌機(jī)的工時(shí)限制： 3x1 + 4x215,成型機(jī)的工時(shí)限制： 2x1 +x25,烘箱的工時(shí)限制： 2x1 +2x211,非負(fù)約束：產(chǎn)量非負(fù) x1 0, x2 0,Step3 -表示約束條件,Step.3,2020/7/11,(1)決策變量：x1為餅干I的生產(chǎn)數(shù)量，x2為餅干II的生產(chǎn)數(shù)量。 (2)目標(biāo)函數(shù)：目標(biāo)是企業(yè)利潤(rùn)最大化 max Z= 5x1 +4x2 (3)約束條件：生產(chǎn)受設(shè)備能力制約，能力需求不能突破有效供給量。 攪拌機(jī)的工時(shí)限制的約束條件表達(dá)為 3x1+ 4x2 15 同理，成型機(jī)的工時(shí)限制約束條件表達(dá)為 2x1+ x2 5 烘箱的工時(shí)限制，其

6、約束條件為 2x1+ 2x2 11 非負(fù)約束：產(chǎn)品的產(chǎn)量為非負(fù) x1 0， x2 0,LP模型：,例1中建模的過(guò)程(小結(jié)),2020/7/11,解：用變量x1和x2分別表示光華食品廠生產(chǎn)餅干I和餅干II的數(shù)量。 目標(biāo)函數(shù) 約束條件,用數(shù)學(xué)語(yǔ)言完整描述,2020/7/11,決策變量 問(wèn)題中要確定的未知量，表明規(guī)劃中的用數(shù)量表示的方案、措施，可由決策者決定和控制。 一般取值要求非負(fù) 目標(biāo)函數(shù) 目標(biāo)函數(shù)是決策變量的線性函數(shù) 有的目標(biāo)要實(shí)現(xiàn)極大，有的則要求極小 約束條件 指決策變量取值時(shí)受到的各種資源條件的限制通常把各種限制條件表達(dá)為一組等式或不等式稱約束條件 約束條件是決策變量的線性函數(shù),線性規(guī)劃模

7、型的三要素,總結(jié),當(dāng)數(shù)學(xué)模型的目標(biāo)函數(shù)為線性函數(shù)，約束條件為線性等式或不等式時(shí)稱此數(shù)學(xué)模型為線性規(guī)劃模型。,2020/7/11,線性規(guī)劃問(wèn)題(Linear Programming problem),研究?jī)?nèi)容：在一定的人力、財(cái)力、資源條件下，如何合理安排使用，使得效益最高；某項(xiàng)任務(wù)確定后，如何安排人、財(cái)、物，使之最省。 線性規(guī)劃問(wèn)題的共同點(diǎn)：要求達(dá)到某些數(shù)量上的最大化或最小化；在一定的約束條件下追求其目標(biāo)最優(yōu)。,2020/7/11,確定約束條件 由決策變量所受的限制條件確定決策變量所要滿足的約束條件。,線性規(guī)劃問(wèn)題建模步驟,總結(jié),確定決策變量 根據(jù)影響所要達(dá)到目的的因素找到?jīng)Q策變量；,寫(xiě)出目標(biāo)函

8、數(shù) 由決策變量和所在達(dá)到目的之間的函數(shù)關(guān)系確定目標(biāo)函數(shù)；,2020/7/11,運(yùn)籌學(xué)的工作步驟,2020/7/11,例：用濃度45%和92%的硫酸配置100噸濃度80%的硫酸。,決策變量：取45%和92%的硫酸分別為 x1 和 x2 噸 約束條件：,求解二元一次方程組得解,非負(fù)約束： x1 0， x2 0,線性規(guī)劃建模課堂練習(xí)-產(chǎn)品配比問(wèn)題,2020/7/11,若有5種不同濃度的硫酸可選(30%,45%,73%,85%,92%)會(huì)如何呢？,取這5種硫酸分別為 x1、x2、x3、x4、x5 ，有,若5種硫酸價(jià)格分別為400, 700, 1400, 1900, 2500元/t， 如何使費(fèi)用最?。?

9、線性規(guī)劃建模課堂練習(xí)-產(chǎn)品配比問(wèn)題,2020/7/11,線性規(guī)劃模型舉例2,運(yùn)輸問(wèn)題：見(jiàn)課本第七頁(yè),2020/7/11,建立數(shù)學(xué)模型,目標(biāo)函數(shù),2020/7/11,線性規(guī)劃模型- 運(yùn)輸問(wèn)題,2020/7/11,分析,運(yùn)輸問(wèn)題模型,2020/7/11,建立數(shù)學(xué)模型,運(yùn)輸問(wèn)題模型,2020/7/11,設(shè)：產(chǎn)品甲生產(chǎn)x1，產(chǎn)品乙生產(chǎn)x2,目標(biāo)：Max z=70 x1+65x2,約束條件：,設(shè)備A生產(chǎn)能力限制：7x1+3x2210,設(shè)備B生產(chǎn)能力限制：4x1+5x2200,設(shè)備C生產(chǎn)能力限制：2x1+4x2180,產(chǎn)量非負(fù)限制： x1，x20,決策變量,決策變量,目標(biāo)函數(shù),約束條件,三要素： 1.決策

10、變量 2.目標(biāo)函數(shù) 3.約束條件,例3 生產(chǎn)計(jì)劃,2020/7/11,線性規(guī)劃模型的一般形式,一般地，假設(shè)線性規(guī)劃數(shù)學(xué)模型中，有m 個(gè)約束，有n個(gè)決策變量xj, j=1,2,n，目標(biāo)函數(shù)的變量系數(shù)用cj表示, cj稱為價(jià)值系數(shù)。約束條件的變量系數(shù)用aij表示，aij稱為工藝系數(shù)。約束條件右端的常數(shù)用bi (i=1,2,m)表示，bi稱為資源限量。則線性規(guī)劃數(shù)學(xué)模型的一般表達(dá)式可寫(xiě)成,2020/7/11,線性規(guī)劃模型的一般形式(注釋),2020/7/11,緊縮形式,線性規(guī)劃模型的一般形式,在實(shí)際中一般xj0,但有時(shí)xj0或xj無(wú)符號(hào)限制。,2020/7/11,其中 :,線性規(guī)劃問(wèn)題的一般形式,矩

11、陣形式,2020/7/11,例4 生產(chǎn)計(jì)劃問(wèn)題2,2020/7/11,max Z= 40 x1 +50 x2,解:設(shè)產(chǎn)品A, B產(chǎn)量分別為變量x1 ， x2,建立模型,2020/7/11,1、定義？ 所謂線性規(guī)劃就是求一個(gè)線性函數(shù)在一組線性約束條件下極值的問(wèn)題。,2、構(gòu)成？ 線性規(guī)劃的數(shù)學(xué)模型由決策變量 （Decision variables）、目標(biāo)函數(shù)（Objective function）及約束條件（Constraints）構(gòu)成。稱為三個(gè)要素。,3、特征？ （1）一組決策變量；（2）一個(gè)線性目標(biāo)函數(shù)；（3）一組線性約束條件,小結(jié),2020/7/11,線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式,在用單純法求解線

12、性規(guī)劃問(wèn)題時(shí)，為了討論問(wèn)題方便，需將線性規(guī)劃模型化為統(tǒng)一的標(biāo)準(zhǔn)形式。,線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型為: 1.目標(biāo)函數(shù)求最小值（或求最大值） 2約束條件都為等式方程 3變量xj非負(fù) 4常數(shù)bi非負(fù),注：本教材默認(rèn)目標(biāo)函數(shù)是 min,2020/7/11,線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式,標(biāo)準(zhǔn)形式為:,目標(biāo)函數(shù)最小 約束條件等式 右端常數(shù)非負(fù) 決策變量非負(fù),2020/7/11,簡(jiǎn)寫(xiě)為,2020/7/11,用向量表示,2020/7/11,用矩陣表示,C價(jià)值向量 b資源向量 X決策變量向量,2020/7/11,.目標(biāo)函數(shù)的轉(zhuǎn)換,如果是求極大值，則可將目標(biāo)函數(shù)乘以（-1）可化為求極小值問(wèn)題。,非標(biāo)準(zhǔn)形式轉(zhuǎn)化為標(biāo)準(zhǔn)形式的方法

13、,令Z = -Z,2020/7/11,非標(biāo)準(zhǔn)形式轉(zhuǎn)化為標(biāo)準(zhǔn)形式的方法,x3為松弛變量,x4為剩余變量,松弛變量或剩余變量在實(shí)際問(wèn)題中分別表示未被充分利用的資源和超出的資源數(shù)，均未轉(zhuǎn)化為價(jià)值和利潤(rùn)，所以引進(jìn)模型后它們?cè)谀繕?biāo)函數(shù)中的系數(shù)均為零。,當(dāng)約束條件為“”時(shí)，,當(dāng)約束條件為“”時(shí)，,約束條件,2020/7/11,轉(zhuǎn)化為：minZ=-40 x1-50 x2+0 x3 +0 x4+0 x5,例1：max Z= 40 x1 +50 x2,注：松弛變量在目標(biāo)函數(shù)中的系數(shù)均為零。,非標(biāo)準(zhǔn)形式轉(zhuǎn)化為標(biāo)準(zhǔn)形式的方法,2020/7/11,例2:,非標(biāo)準(zhǔn)形式轉(zhuǎn)化為標(biāo)準(zhǔn)形式的方法,2020/7/11,右端項(xiàng)b0時(shí)，只需將等式或不等式兩端同乘(1)，則等式右端項(xiàng)必大于零。,非標(biāo)準(zhǔn)形式轉(zhuǎn)化為標(biāo)準(zhǔn)形式的方法,右端項(xiàng),2020/7/11,非標(biāo)準(zhǔn)形式轉(zhuǎn)化為標(biāo)準(zhǔn)形式的方法,（1）、x 0的情況,令x1= x1- x1 ,（2）、x取值無(wú)約束的情況,令x -x,令x= x-x,變量,2020/7/11,將 max Z = -x1+2x2 3x3,化為標(biāo)準(zhǔn)型,例,例3,2020/7/11,解： 令x3 =x4 - x5, 加松弛變量x6,加剩余