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

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

用一組未知變量表示所求的方案，這組未知變量稱為決策變量；存在一定的限制條件，且為線性表達(dá)式,稱之為約束方程；有一個(gè)目標(biāo)要求（最大化或最小化），目標(biāo)表示為未知變量的線性表達(dá)式，稱之為目標(biāo)函數(shù)；線性規(guī)劃數(shù)學(xué)模型的三要素：目標(biāo)函數(shù)MaxF或MinF約束條件s.t.(subjectto)滿足于決策變量用符號來表示可控制的因素例1

勝利家具廠生產(chǎn)桌子和椅子兩種家具。桌子售價(jià)50元/個(gè)，椅子銷售價(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í)。問該廠如何組織生產(chǎn)才能使每月的銷售收入最大？線性規(guī)劃模型

maxS=50x1+30x2s.t.4x1+3x21202x1+x250x1,x20線性規(guī)劃數(shù)學(xué)模型三要素：

決策變量、約束條件、目標(biāo)函數(shù)例2

營養(yǎng)配餐問題假定一個(gè)成年人每天需要從食物中獲得3000千卡的熱量、55克蛋白質(zhì)和800毫克的鈣。如果市場上只有四種食品可供選擇，它們每千克所含的熱量和營養(yǎng)成分和市場價(jià)格見下表。問如何選擇才能在滿足營養(yǎng)的前提下使購買食品的費(fèi)用最小？各種食物的營養(yǎng)成分表解：設(shè)x1為每天豬肉的購入量，x2為雞蛋的購入量，x3為大米的購入量，x4為白菜的購入量，則配餐問題的線性規(guī)劃模型為：

minS=14x1+6x2+3x3+2x4s.t.1000x1+800x2+900x3+200x4300050x1+60x2+20x3+10x455400x1+200x2+300x3+500x4800x1，x2，

x3，x40LP數(shù)學(xué)模型：+++=…)(2211nnxcxcxcZMinMax或≥=+++≥=+++≥=++0,,,),(),(),(..2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxats……………+……≤≤≤≥無限制二、線性規(guī)劃模型的標(biāo)準(zhǔn)化：將一般形式→標(biāo)準(zhǔn)型線性規(guī)劃的標(biāo)準(zhǔn)形式有如下四個(gè)特點(diǎn)：目標(biāo)最大化；約束為等式；決策變量均非負(fù)；右端項(xiàng)非負(fù)。

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

（1）目標(biāo)函數(shù)為最小化：令Z'=-Z，則maxZ'=-CX。（2）約束方程為不等式：不等號左端加（減）松弛變量（剩余變量）。（3）決策變量xi小于零：令xi'=-xi

，替換原變量；決策變量xi無約束：令xi=xi‘-xi’‘，替換原變量。（4）右端常數(shù)項(xiàng)小于零；兩邊同乘-1。例3

將下列問題化成標(biāo)準(zhǔn)型:MinS=-x1+2x2-3x3s.t.x1+x2+x37x1-x2+x32-3x1+x2+2x3=-5x1,x2

0,x3

無非負(fù)限制

MaxS’=x1-2x2+3x3x1+x2+x3+x4=7

x1-x2+x3–x5=2

3x1-x2-2x3=5令x3=x3’-x3’’MaxS

=x1-2x2+3x3-3x3+0·x4+0·x5s.t.x1+x2+x3-x3+x4=7x1-x2+x3-x3-x5=2

3x1-x2-2x3

+2x3

=5x1,x2,

x3，x3,x4，x50標(biāo)準(zhǔn)型為：

練習(xí)：課后習(xí)題標(biāo)準(zhǔn)型的幾種形式：（1）展開式+++=…2211nnxcxcxcMax=+++=+++=++0,,,..2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxats……………+……≥（2）緊縮形式=≥===∑==njxmibxatsxcZMaxjnjijijnjjj,2,10,2,1..11∑……（3）矩陣形式其中:),,(21ncccC…=T=),,(21nxxxX…Tmbbbb),,,(21…==mnmmnnaaaaaaaaaA…………………2122221112