第1章 線性規(guī)劃模型與標(biāo)準(zhǔn)化課件

第一章、線性規(guī)劃及單純形法

線性規(guī)劃（LinearProgramming，LP）是運(yùn)籌學(xué)的一個(gè)重要分支。第1章線性規(guī)劃模型與標(biāo)準(zhǔn)化一、問(wèn)題提出什么是線性規(guī)劃模型？線性規(guī)劃模型的特點(diǎn)是什么？如何建立線性規(guī)劃模型？標(biāo)準(zhǔn)化的提出及實(shí)現(xiàn)第1章線性規(guī)劃模型與標(biāo)準(zhǔn)化定義：對(duì)于求取一組變量xj(j=1,2,......,n)，使之既滿(mǎn)足線性約束條件，又使具有線性表達(dá)式的目標(biāo)函數(shù)取得極大值或極小值的一類(lèi)最優(yōu)化問(wèn)題稱(chēng)為線性規(guī)劃問(wèn)題，簡(jiǎn)稱(chēng)線性規(guī)劃（LP）。第1章線性規(guī)劃模型與標(biāo)準(zhǔn)化線性規(guī)劃模型的特點(diǎn)：

用一組未知變量表示所求的方案，這組未知變量稱(chēng)為決策變量；存在一定的限制條件，且為線性表達(dá)式；有一個(gè)目標(biāo)要求（最大化，當(dāng)然也可以是最小化），目標(biāo)表示為未知變量的線性表達(dá)式，稱(chēng)之為目標(biāo)函數(shù)；對(duì)決策變量有非負(fù)要求。第1章線性規(guī)劃模型與標(biāo)準(zhǔn)化線性規(guī)劃數(shù)學(xué)模型的三要素：目標(biāo)函數(shù)MaxF或MinF約束條件s.t.(subjectto)滿(mǎn)足于決策變量用符號(hào)來(lái)表示可控制的因素第1章線性規(guī)劃模型與標(biāo)準(zhǔn)化例1勝利家具廠生產(chǎn)桌子和椅子兩種家具。桌子售價(jià)50元/個(gè)，椅子銷(xiāo)售價(jià)格30元/個(gè)，生產(chǎn)桌子和椅子要求需要木工和油漆工兩種工種。生產(chǎn)一個(gè)桌子需要木工4小時(shí)，油漆工2小時(shí)。生產(chǎn)一個(gè)椅子需要木工3小時(shí)，油漆工1小時(shí)。該廠每個(gè)月可用木工工時(shí)為120小時(shí)，油漆工工時(shí)為50小時(shí)。問(wèn)該廠如何組織生產(chǎn)才能使每月的銷(xiāo)售收入最大？第1章線性規(guī)劃模型與標(biāo)準(zhǔn)化線性規(guī)劃模型

maxS=50x1+30x2s.t.4x1+3x2

1202x1+x2

50x1,x2

0線性規(guī)劃數(shù)學(xué)模型三要素：

決策變量、約束條件、目標(biāo)函數(shù)第1章線性規(guī)劃模型與標(biāo)準(zhǔn)化例2營(yíng)養(yǎng)配餐問(wèn)題假定一個(gè)成年人每天需要從食物中獲得3000千卡的熱量、55克蛋白質(zhì)和800毫克的鈣。如果市場(chǎng)上只有四種食品可供選擇，它們每千克所含的熱量和營(yíng)養(yǎng)成分和市場(chǎng)價(jià)格見(jiàn)下表。問(wèn)如何選擇才能在滿(mǎn)足營(yíng)養(yǎng)的前提下使購(gòu)買(mǎi)食品的費(fèi)用最小？第1章線性規(guī)劃模型與標(biāo)準(zhǔn)化各種食物的營(yíng)養(yǎng)成分表第1章線性規(guī)劃模型與標(biāo)準(zhǔn)化解：設(shè)x1為每天豬肉的購(gòu)入量，x2為雞蛋的購(gòu)入量，x3為大米的購(gòu)入量，x4為白菜的購(gòu)入量，則配餐問(wèn)題的線性規(guī)劃模型為：

minS=14x1+6x2+3x3+2x4s.t.1000x1+800x2+900x3+200x4

300050x1+60x2+20x3+10x4

55400x1+200x2+300x3+500x4

800x1，x2，

x3，x4

0第1章線性規(guī)劃模型與標(biāo)準(zhǔn)化LP數(shù)學(xué)模型：+++=…)(2211nnxcxcxcZMinMax或≥=

+++≥=

+++≥=

++0,,,),(),(),(..2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxats……………+……≤≤≤≥第1章線性規(guī)劃模型與標(biāo)準(zhǔn)化二、線性規(guī)劃模型的標(biāo)準(zhǔn)化：將一般形式→標(biāo)準(zhǔn)型第1章線性規(guī)劃模型與標(biāo)準(zhǔn)化線性規(guī)劃的標(biāo)準(zhǔn)形式有如下四個(gè)特點(diǎn)：目標(biāo)最大化；約束為等式；決策變量均非負(fù)；右端項(xiàng)非負(fù)。

第1章線性規(guī)劃模型與標(biāo)準(zhǔn)化問(wèn)題：如何將一般形式的線性規(guī)劃模型化為標(biāo)準(zhǔn)型，使其滿(mǎn)足以下四個(gè)特點(diǎn)？目標(biāo)最大化；約束為等式；決策變量均非負(fù)；右端項(xiàng)非負(fù)。

第1章線性規(guī)劃模型與標(biāo)準(zhǔn)化（1）目標(biāo)函數(shù)為最小化：令Z'=-Z，則maxZ'=-CX。（2）約束方程為不等式：不等號(hào)左端加（減）松弛變量（剩余變量）。（3）決策變量xi小于零：令xi'=-xi

，替換原變量；決策變量xi無(wú)約束：令xi=xi‘-xi’‘，替換原變量。（4）右端常數(shù)項(xiàng)小于零；兩邊同乘-1。第1章線性規(guī)劃模型與標(biāo)準(zhǔn)化例3將下列問(wèn)題化成標(biāo)準(zhǔn)型:MinS=-x1+2x2-3x3s.t.x1+x2+x3

7x1-x2+x3

2-3x1+x2+2x3=-5x1,x2

0,x3無(wú)非負(fù)限制MaxS’=x1-2x2+3x3x1+x2+x3+x4=7x1-x2+x3–x5=23x1-x2-2x3=5令x3=x3’-x3’’第1章線性規(guī)劃模型與標(biāo)準(zhǔn)化MaxS

=x1-2x2+3x3

-3x3

+0·x4+0·x5s.t.x1+x2+x3

-x3

+x4=7x1-x2+x3

-x3

-x5=23x1-x2-2x3

+2x3

=5x1,x2,

x3

，x3

,x4，x5

0標(biāo)準(zhǔn)型為：

第1章線性規(guī)劃模型與標(biāo)準(zhǔn)化練習(xí)：課后習(xí)題第1章線性規(guī)劃模型與標(biāo)準(zhǔn)化標(biāo)準(zhǔn)型的幾種形式：（1）展開(kāi)式+++=…2211nnxcxcxcMax=

+++=

+++=

++0,,,..2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxats……………+……≥第1章線性規(guī)劃模型與標(biāo)準(zhǔn)化（2）緊縮形式=≥==

=∑==njxmibxatsxcZMaxjnjijijnjjj,2,10,2,1..11∑……第1章線性規(guī)劃模型與標(biāo)準(zhǔn)化（3）矩陣形式其中:),,(21ncccC…=T=),,(21nxxxX…Tmbbbb),,,(21…==mnmmnnaaaaaaaaaA…………………212222111211第1章線性規(guī)劃模型與標(biāo)準(zhǔn)化（4）向量—矩陣形式：其中：njaaaP