第一章、線性規劃及單純形法線性規劃（LinearProgramming，LP）是運籌學的一個重要分支。一、問題提出什么是線性規劃模型？線性規劃模型的特點是什么？如何建立線性規劃模型？標準化的提出及實現定義：對于求取一組變量xj(j=1,2,......,n)，使之既滿足線性約束條件，又使具有線性表達式的目標函數取得極大值或極小值的一類最優化問題稱為線性規劃問題，簡稱線性規劃（LP）。線性規劃數學模型的三要素：目標函數MaxF或MinF約束條件s.t.(subjectto)滿足于決策變量用符號來表示可控制的因素例1勝利家具廠生產桌子和椅子兩種家具。桌子售價50元/個，椅子銷售價格30元/個，生產桌子和椅子要求需要木工和油漆工兩種工種。生產一個桌子需要木工4小時，油漆工2小時。生產一個椅子需要木工3小時，油漆工1小時。該廠每個月可用木工工時為120小時，油漆工工時為50小時。問該廠如何組織生產才能使每月的銷售收入最大？線性規劃模型maxS=50x1+30x2s.t.4x1+3x21202x1+x250x1,x20線性規劃數學模型三要素：

決策變量、約束條件、目標函數例2營養配餐問題假定一個成年人每天需要從食物中獲得3000千卡的熱量、55克蛋白質和800毫克的鈣。如果市場上只有四種食品可供選擇，它們每千克所含的熱量和營養成分和市場價格見下表。問如何選擇才能在滿足營養的前提下使購買食品的費用最小？解：設x1為每天豬肉的購入量，x2為雞蛋的購入量，x3為大米的購入量，x4為白菜的購入量，則配餐問題的線性規劃模型為：

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

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

（1）目標函數為最小化：令Z'=-Z，則maxZ'=-CX。（2）約束方程為不等式：不等號左端加（減）松弛變量（剩余變量）。（3）決策變量xi小于零：令xi'=-xi，替換原變量；決策變量xi無約束：令xi=xi‘-xi’‘，替換原變量。（4）右端常數項小于零；兩邊同乘-1。例3將下列問題化成標準型:MinS=-x1+2x2-3x3s.t.x1+x2+x37x1-x2+x32-3x1+x2+2x3=-5x1,x20,x3無非負限制MaxS’=x1-2x2+3x3x1+x2+x3+x4=7x1-x2+x3–x5=23x1-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=23x1-x2-2x3+2x3=5x1,x2,

x3，x3,x4，x50標準型為：

練習：課后習題（2）緊縮形式=≥===∑==njxmibxatsxcZMaxjnjijijnjjj,2,10,2,1..11∑……（3）矩陣形式其中:),,(21ncccC…=T=),,(21nxxxX…Tmbbbb),,,(21…==