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

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

勝利家具廠生產(chǎn)桌子和椅子兩種家具。桌子售價50元/個，椅子銷售價格30元/個，生產(chǎn)桌子和椅子要求需要木工和油漆工兩種工種。生產(chǎn)一個桌子需要木工4小時，油漆工2小時。生產(chǎn)一個椅子需要木工3小時，油漆工1小時。該廠每個月可用木工工時為120小時，油漆工工時為50小時。問該廠如何組織生產(chǎn)才能使每月的銷售收入最大？線性規(guī)劃模型

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

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

營養(yǎng)配餐問題假定一個成年人每天需要從食物中獲得3000千卡的熱量、55克蛋白質(zhì)和800毫克的鈣。如果市場上只有四種食品可供選擇，它們每千克所含的熱量和營養(yǎng)成分和市場價格見下表。問如何選擇才能在滿足營養(yǎng)的前提下使購買食品的費用最??？各種食物的營養(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ù)學模型：+++=…)(2211nnxcxcxcZMinMax或≥=+++≥=+++≥=++0,,,),(),(),(..2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxats……………+……≤≤≤≥無限制二、線性規(guī)劃模型的標準化：將一般形式→標準型線性規(guī)劃的標準形式有如下四個特點：目標最大化；約束為等式；決策變量均非負；右端項非負。

問題：如何將一般形式的線性規(guī)劃模型化為標準型，使其滿足以下四個特點？目標最大化；約束為等式；決策變量均非負；右端項非負。

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

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

將下列問題化成標準型:MinS=-x1+2x2-3x3s.t.x1+x2+x37x1-x2+x32-3x1+x2+2x3=-5x1,x2

0,x3

無非負限制

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標準型為：

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