線性規劃案例演示文稿目前一頁\總數一百四十五頁\編于八點線性規劃案例目前二頁\總數一百四十五頁\編于八點線性規劃線性規劃問題可行區域與基本可行解單純形算法初始可行解對偶理論靈敏度分析計算軟件案例分析目前三頁\總數一百四十五頁\編于八點線性規劃問題線性規劃實例

生產計劃問題

運輸問題線性規劃模型

一般形式

規范形式

標準形式

形式轉換

概念

目前四頁\總數一百四十五頁\編于八點某工廠用三種原料生產三種產品，已知的條件如表2.1.1所示，試制訂總利潤最大的生產計劃單位產品所需原料數量（公斤）產品Q1產品Q2產品Q3原料可用量（公斤/日）原料P12301500原料P2024800原料P33252000單位產品的利潤（千元）354生產計劃問題目前五頁\總數一百四十五頁\編于八點問題分析目前六頁\總數一百四十五頁\編于八點模型目前七頁\總數一百四十五頁\編于八點計算結果目前八頁\總數一百四十五頁\編于八點運輸問題目前九頁\總數一百四十五頁\編于八點問題分析目前十頁\總數一百四十五頁\編于八點模型目前十一頁\總數一百四十五頁\編于八點一般形式目標函數約束條件目前十二頁\總數一百四十五頁\編于八點注釋目前十三頁\總數一百四十五頁\編于八點規范形式目前十四頁\總數一百四十五頁\編于八點標準形式目前十五頁\總數一百四十五頁\編于八點概念目前十六頁\總數一百四十五頁\編于八點模型轉換約束轉換實例目標轉換變量轉換目前十七頁\總數一百四十五頁\編于八點約束轉換不等式變等式不等式變不等式等式變不等式目前十八頁\總數一百四十五頁\編于八點不等式變等式松弛變量剩余變量目前十九頁\總數一百四十五頁\編于八點不等式變不等式目前二十頁\總數一百四十五頁\編于八點

把問題轉化為標準形式目前二十一頁\總數一百四十五頁\編于八點可行區域與基本可行解

圖解法

可行域的幾何結構

基本可行解與基本定理目前二十二頁\總數一百四十五頁\編于八點圖解法目前二十三頁\總數一百四十五頁\編于八點例2.2.1解線性規劃

目前二十四頁\總數一百四十五頁\編于八點目前二十五頁\總數一百四十五頁\編于八點注釋可能出現的情況：

可行域是空集可行域無界無最優解

最優解存在且唯一，則一定在頂點上達到最優解存在且不唯一，一定存在頂點是最優解目前二十六頁\總數一百四十五頁\編于八點可行域的幾何結構基本假設凸集可行域的凸性目前二十七頁\總數一百四十五頁\編于八點基本假設目前二十八頁\總數一百四十五頁\編于八點凸集目前二十九頁\總數一百四十五頁\編于八點可行域的凸性目前三十頁\總數一百四十五頁\編于八點問題目前三十一頁\總數一百四十五頁\編于八點基本可行解與基本定理定義基本定理問題目前三十二頁\總數一百四十五頁\編于八點基本可行解定義目前三十三頁\總數一百四十五頁\編于八點目前三十四頁\總數一百四十五頁\編于八點目前三十五頁\總數一百四十五頁\編于八點基本定理目前三十六頁\總數一百四十五頁\編于八點問題目前三十七頁\總數一百四十五頁\編于八點單純形算法理論方法算法步驟單純形表算例目前三十八頁\總數一百四十五頁\編于八點理論方法★★★目前三十九頁\總數一百四十五頁\編于八點

目前四十頁\總數一百四十五頁\編于八點目前四十一頁\總數一百四十五頁\編于八點

目前四十二頁\總數一百四十五頁\編于八點算法步驟目前四十三頁\總數一百四十五頁\編于八點單純形表目前四十四頁\總數一百四十五頁\編于八點目前四十五頁\總數一百四十五頁\編于八點目前四十六頁\總數一百四十五頁\編于八點目前四十七頁\總數一百四十五頁\編于八點算例目前四十八頁\總數一百四十五頁\編于八點初始單純形表目前四十九頁\總數一百四十五頁\編于八點迭代1目前五十頁\總數一百四十五頁\編于八點迭代2目前五十一頁\總數一百四十五頁\編于八點目前五十二頁\總數一百四十五頁\編于八點初始解兩階段法大M法說明目前五十三頁\總數一百四十五頁\編于八點兩階段法基本思想

第一階段：通過求解輔助問題的最優基可行解得到原問題的初始基可行解。

第二階段：求原問題的最優解算例目前五十四頁\總數一百四十五頁\編于八點輔助問題目前五十五頁\總數一百四十五頁\編于八點原輔助題問與題的關系目前五十六頁\總數一百四十五頁\編于八點求輔助問題的三種情況目前五十七頁\總數一百四十五頁\編于八點算例目前五十八頁\總數一百四十五頁\編于八點第1階段目前五十九頁\總數一百四十五頁\編于八點第1階段目前六十頁\總數一百四十五頁\編于八點第1階段目前六十一頁\總數一百四十五頁\編于八點第1階段目前六十二頁\總數一百四十五頁\編于八點第1階段目前六十三頁\總數一百四十五頁\編于八點第2階段目前六十四頁\總數一百四十五頁\編于八點大M法目前六十五頁\總數一百四十五頁\編于八點說明目前六十六頁\總數一百四十五頁\編于八點對偶理論對偶規劃對偶理論對偶單純形算法目前六十七頁\總數一百四十五頁\編于八點對偶規劃標準形式線性規劃的對偶規劃規范形式線性規劃的對偶規劃一般形式線性規劃的對偶規劃實例目前六十八頁\總數一百四十五頁\編于八點標準形式的對偶規劃目前六十九頁\總數一百四十五頁\編于八點目前七十頁\總數一百四十五頁\編于八點規范形式的對偶規劃目前七十一頁\總數一百四十五頁\編于八點一般形式的對偶規劃目前七十二頁\總數一百四十五頁\編于八點實例目前七十三頁\總數一百四十五頁\編于八點對偶理論﹡﹡﹡目前七十四頁\總數一百四十五頁\編于八點目前七十五頁\總數一百四十五頁\編于八點目前七十六頁\總數一百四十五頁\編于八點目前七十七頁\總數一百四十五頁\編于八點對偶單純形算法基本思想算法過程算例目前七十八頁\總數一百四十五頁\編于八點基本思想目前七十九頁\總數一百四十五頁\編于八點單純形算法目前八十頁\總數一百四十五頁\編于八點對偶單純形目前八十一頁\總數一百四十五頁\編于八點正則解正則解對偶可行解目前八十二頁\總數一百四十五頁\編于八點正則解的單純性表目前八十三頁\總數一百四十五頁\編于八點規劃無可行解保持正則性目前八十四頁\總數一百四十五頁\編于八點入基變量目前八十五頁\總數一百四十五頁\編于八點目前八十六頁\總數一百四十五頁\編于八點否算法過程初始正則解檢查可行是則停止得最優解選出基變量檢查是否無可行解是則停止否無最優解選入基變量計算典式檢驗數目前八十七頁\總數一百四十五頁\編于八點算例目前八十八頁\總數一百四十五頁\編于八點迭代目前八十九頁\總數一百四十五頁\編于八點迭代目前九十頁\總數一百四十五頁\編于八點迭代目前九十一頁\總數一百四十五頁\編于八點目前九十二頁\總數一百四十五頁\編于八點目前九十三頁\總數一百四十五頁\編于八點靈敏度分析概況改變價值向量改變右端向量目前九十四頁\總數一百四十五頁\編于八點概況信息的不確定性

信息的變化：

價值向量—市場變化

右端向量—資源變化系數矩陣—技術進步

認知的誤差分析方法

靜態分析-比較靜態分析-動態分析目前九十五頁\總數一百四十五頁\編于八點改變價值向量

一般改變情況

改變非基變量的價值向量

改變基變量的價值向量

算例目前九十六頁\總數一百四十五頁\編于八點一般改變目前九十七頁\總數一百四十五頁\編于八點非基變量目前九十八頁\總數一百四十五頁\編于八點基變量目前九十九頁\總數一百四十五頁\編于八點算例目前一百頁\總數一百四十五頁\編于八點目前一百零一頁\總數一百四十五頁\編于八點改變右端向量基本思想算例目前一百零二頁\總數一百四十五頁\編于八點

基本思想目前一百零三頁\總數一百四十五頁\編于八點目前一百零四頁\總數一百四十五頁\編于八點算例目前一百零五頁\總數一百四十五頁\編于八點目前一百零六頁\總數一百四十五頁\編于八點計算軟件LinDoLinGoMatlab目前一百零七頁\總數一百四十五頁\編于八點LinDo輸入模型求解點擊求解按鈕即可結果目前一百零八頁\總數一百四十五頁\編于八點輸入模型!注釋內容，可用中文!目標函數：最大-max,最小-min,大小寫不分

max3x1+5x2+4x3!約束，以subjectto開始

subjectto2x1+3x2<=15002x2+4x3<=8003x1+2x2+5x3<=2000end目前一百零九頁\總數一百四十五頁\編于八點注意事項變量以字母開頭，下標寫在后面，系數與邊量之間加空格不等號為:<=(<),>=(>),=,<=與<等同變量非負約束可省略結束時以end標示目前一百一十頁\總數一百四十五頁\編于八點結果

LPOPTIMUMFOUNDATSTEP3OBJECTIVEFUNCTIONVALUE1)2675.000

VARIABLEVALUEREDUCEDCOSTX1375.0000000.000000X2250.0000000.000000X375.0000000.000000

ROWSLACKORSURPLUSDUALPRICES2)0.0000001.0500003)0.0000000.6250004)0.0000000.300000目前一百一十一頁\總數一百四十五頁\編于八點LinGo輸入模型

LinDo模式

LinGo模式求解點擊求解按鈕即可結果目前一百一十二頁\總數一百四十五頁\編于八點LinDo輸入模式model:MAX=3*x1+5*x2+4*x3;2*x1+3*x2<=1500;2*x2+4*x3<=800;3*x1+2*x2+5*x3<=2000;end目前一百一十三頁\總數一百四十五頁\編于八點注意與LinDo的區別目標函數中加等號變量與系數之間用“*”Model:-end可省略目前一百一十四頁\總數一百四十五頁\編于八點LinGo模式Model:

Sets:Endsets

Data:Enddata

調用函數與計算end!定義集合！定義數據目前一百一十五頁\總數一百四十五頁\編于八點集合部分model:！開始sets:！定義集合ve/1..3/:c,x;co/1..3/:b;ma(co,ve):a;endsets！注：集表達式：名稱/成員/：屬性名稱（初始集）：屬性目前一百一十六頁\總數一百四十五頁\編于八點定義數據data:！定義數據c=354;ba=230024325;Enddata！注：數據的大小與集合定義中一致，分量中間用空格或逗號分開，數據結束后用分號；目前一百一十七頁\總數一百四十五頁\編于八點調用函數max=@sum(ve(j):c(j)*x(j));@for(co(i):@sum(ve(j):a(i,j)*x(j))<=b(i));主要函數：@for(set(set_index_list)|condition:expression)@sum(set(set_index_list)|condition:expression)@min(max)(set(set_index_list)|condition:expression)目前一百一十八頁\總數一百四十五頁\編于八點結果Globaloptimalsolutionfoundatiteration:3Objectivevalue:2675.000VariableValueReducedCostC(1)3.0000000.000000C(2)5.0000000.000000C(3)4.0000000.000000X(1)375.00000.000000X(2)250.00000.000000X(3)75.000000.000000目前一百一十九頁\總數一百四十五頁\編于八點B(1)1500.0000.000000B(2)800.00000.000000B(3)2000.0000.000000A(1,1)2.0000000.000000A(1,2)3.0000000.000000A(1,3)0.0000000.000000A(2,1)0.0000000.000000A(2,2)2.0000000.000000A(2,3)4.0000000.000000A(3,1)3.0000000.000000A(3,2)2.0000000.000000A(3,3)5.0000000.000000目前一百二十頁\總數一百四十五頁\編于八點RowSlackorSurplusDualPrice12675.0001.00000020.0000001.05000030.0000000.625000040.0000000.3000000目前一百二十一頁\總數一百四十五頁\編于八點Scilab函數命令1：[x,lagr,f]=linpro(p,C,b[,x0])命令2：[x,lagr,f]=linpro(p,C,b,ci,cs[,x0])命令3：[x,lagr,f]=linpro(p,C,b,ci,cs,me[,x0])命令4：[x,lagr,f]=linpro(p,C,b,ci,cs,me,x0[,imp])命令5：[x1,crit]=karmarkar(a,b,c,x0)注意事項目前一百二十二頁\總數一百四十五頁\編于八點命令1問題形式

minp'*xs.t.C*x<=b[x,lagr,f]=linpro(p,C,b[,x0]）目前一百二十三頁\總數一百四十五頁\編于八點命令2[x,lagr,f]=linpro(p,C,b,ci,cs[,x0])問題形式minp'*xs.t.C*x<=bci<=x<=cs目前一百二十四頁\總數一百四十五頁\編于八點命令3[x,lagr,f]=linpro(p,C,b,ci,cs,me[,x0])問題minp'*xs.t.C(j,:)x=b(j),j=1,...,meC(j,:)x<=b(j),j=me+1,...,me+mdci<=x<=cs目前一百二十五頁\總數一百四十五頁\編于八點命令4

[x,lagr,f]=linpro(p,C,b,ci,cs,me,x0[,imp])

問題形式

minp'*xs.t.C(j,:)x=b(j),j=1,...,meC(j,:)x<=b(j),j=me+1,...,me+mdci<=x<=cs指定初始可行解x0目前一百二十六頁\總數一百四十五頁\編于八點命令5[x1,crit]=karmarkar(a,b,c,x0)問題形式minc'*xs.t.a*x=bx>=0目前一百二十七頁\總數一百四十五頁\編于八點注意事項命令2和3中x0可省略，但命令4和5中不可省略向量都是列向量，參數的順序不可換命令3中等式約束必須在前面目前一百二十八頁\總數一百四十五頁\編于八點人力資源分配問題某個中型百貨商場對售貨人員（周工資200元）的需求經統計如下表為了保證銷售人員充分休息，銷售人員每周工作5天，休息2天。問應如何安排銷售人員的工作時間，使得所配售貨人員的總費用最小？星期一二三四五六七人數12151214161819目前一百二十九頁\總數一百四十五頁\編于八點模型假設每天工作8小時，不考慮夜班的情況；每個人的休息時間為連續的兩天時間；每天安排的人員數不得低于需求量，但可以超過需求量目前一百三十頁\總數一百四十五頁\編于八點問題分析因素：不可變因素：需求量、休息時間、單位費用；可變因素：安排的人數、每人工作的時間、總費用；方案：確定每天工作的人數，由于連續休息2天，當確定每個人開始休息的時間就等于知道工作的時間，因而確定每天開始休息的人數就知道每天開始工作的人數，從而求出每天工作的人數。變量：每天開始休息的人數約束條件：1.每人休息時間2天，自然滿足。2.每天工作人數不低于需求量，第i天工作的人數就是從第i-2天往前數5天內開始工作的人數，所以有約束：

目前一百三十一頁