運籌學(xué)單純形計算

第1頁，共41頁，2022年，5月20日，10點20分，星期六1、初始單純形表第2頁，共41頁，2022年，5月20日，10點20分，星期六2、換基操作第3頁，共41頁，2022年，5月20日，10點20分，星期六例1用單純形法解LP第4頁，共41頁，2022年，5月20日，10點20分，星期六單純形表迭代進2出5進1出3第5頁，共41頁，2022年，5月20日，10點20分，星期六第6頁，共41頁，2022年，5月20日，10點20分，星期六線性規(guī)劃及單純型法

單純形法進一步討論

第五節(jié)第7頁，共41頁，2022年，5月20日，10點20分，星期六1、人工變量法（大M法）第8頁，共41頁，2022年，5月20日，10點20分，星期六例1用大M法求解LP問題引入松弛變量和剩余變量第9頁，共41頁，2022年，5月20日，10點20分，星期六例1用大M法求解LP問題再引入“人工變量”，構(gòu)造初始表：人工變量第10頁，共41頁，2022年，5月20日，10點20分，星期六用單純形表迭代第11頁，共41頁，2022年，5月20日，10點20分，星期六用單純形表迭代第12頁，共41頁，2022年，5月20日，10點20分，星期六求輔助問題的三種情況第13頁，共41頁，2022年，5月20日，10點20分，星期六2、兩階段法基本思想

第一階段求解目標函數(shù)只有人工變量的輔助問題得到原問題的初始基可行解。

第二階段利用初始基可行解求原問題的最優(yōu)解第14頁，共41頁，2022年，5月20日，10點20分，星期六第15頁，共41頁，2022年，5月20日，10點20分，星期六原輔助題問與題的關(guān)系第16頁，共41頁，2022年，5月20日，10點20分，星期六例2用兩階段法求解LP問題引入松弛變量和剩余變量，化為等約束第17頁，共41頁，2022年，5月20日，10點20分，星期六例2用兩階段法求解LP問題引入“人工變量”，第一階段：第一階段第18頁，共41頁，2022年，5月20日，10點20分，星期六第一階段計算第19頁，共41頁，2022年，5月20日，10點20分，星期六第一階段計算第20頁，共41頁，2022年，5月20日，10點20分，星期六第二階段計算第21頁，共41頁，2022年，5月20日，10點20分，星期六3、關(guān)于解的判別第22頁，共41頁，2022年，5月20日，10點20分，星期六3、關(guān)于解的判別第23頁，共41頁，2022年，5月20日，10點20分，星期六步驟框圖初始表計算非基變的量檢驗數(shù)無可行解無窮多最優(yōu)解*基中有人工變量非基變量檢驗數(shù)=0用初等變換換基操作唯一最優(yōu)解無界解第24頁，共41頁，2022年，5月20日，10點20分，星期六例3解的判別第25頁，共41頁，2022年，5月20日，10點20分，星期六例3解的判別有無界解第26頁，共41頁，2022年，5月20日，10點20分，星期六解的判別無可行解第27頁，共41頁，2022年，5月20日，10點20分，星期六4、向量矩陣描述第28頁，共41頁，2022年，5月20日，10點20分，星期六單純形表中的矩陣向量形式第29頁，共41頁，2022年，5月20日，10點20分，星期六5、單純形法小結(jié)第30頁，共41頁，2022年，5月20日，10點20分，星期六5、單純形法小結(jié)第31頁，共41頁，2022年，5月20日，10點20分，星期六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第32頁，共41頁，2022年，5月20日，10點20分，星期六注意：目標函數(shù)中加等號變量與系數(shù)之間用“*”Model:-end可省略第33頁，共41頁，2022年，5月20日，10點20分，星期六LinGo模式Model:

Sets:Endsets

Data:Enddata

調(diào)用函數(shù)與計算end!定義集合！定義數(shù)據(jù)第34頁，共41頁，2022年，5月20日，10點20分，星期六集合部分model:！開始sets:！定義集合ve/1..3/:c,x;co/1..3/:b;ma(co,ve):a;endsets！注：集表達式：名稱/成員/：屬性名稱（初始集）：屬性第35頁，共41頁，2022年，5月20日，10點20分，星期六定義數(shù)據(jù)data:！定義數(shù)據(jù)c=354;ba=230024325;Enddata！注：數(shù)據(jù)的大小與集合定義中一致，分量中間用空格或逗號分開，數(shù)據(jù)結(jié)束后用分號；第36頁，共41頁，2022年，5月20日，10點20分，星期六調(diào)用函數(shù)max=@sum(ve(j):c(j)*x(j));@for(co(i):@sum(ve(j):a(i,j)*x(j))<=b(i));主要函數(shù)：@for(set(set_index_list)|condition:expression)@sum(set(set_index_list)|condition:expression)@min(max)(set(set_index_list)|condition:expression)第37頁，共41頁，2022年，5月20日，10點20分，星期六結(jié)果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第38頁，共41頁，2022年，5月20日，10點20分，星期六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第39頁，共41頁，2022年，5月20日，10點20分，星期六RowSlackorSurplusDualPrice12675.000