規(guī)劃數(shù)學(xué)大作業(yè)

PAGE規(guī)劃數(shù)學(xué)大作業(yè)學(xué)院：控制與計(jì)算機(jī)工程學(xué)號：1122227184姓名：賀煥PAGE1目錄1問題背景描述 12問題建模 23計(jì)算機(jī)求解 34結(jié)果分析 45附錄 6PAGE11問題背景描述從1947年丹捷格（G.B.Dantzig）提出單純形求解方法以來，線性規(guī)劃作為運(yùn)籌學(xué)的一個重要分支，無論是在理論方面還是在算法方面都日益趨向成熟和完善，并在實(shí)踐中取得了良好的應(yīng)用效果；尤其是隨著計(jì)算機(jī)處理能力的不斷提高，使其得以更廣泛的應(yīng)用。規(guī)劃問題往往與資源的有限性密切相關(guān)，處理的是有限資源條件下的成本最小或利潤最大等問題。在生產(chǎn)管理和經(jīng)營活動中經(jīng)常提出一類問題，即如何合理地利用有限的人力、物力、財(cái)力等資源，以便得到最好的經(jīng)濟(jì)效果。以下對一個生產(chǎn)管理問題進(jìn)行分析和研究。某工廠在某一計(jì)劃期內(nèi)準(zhǔn)備生產(chǎn)甲、乙、丙三種產(chǎn)品，生產(chǎn)需要消耗A、B、C三種資源，已知各種產(chǎn)品中A、B、C的含量，原料成本，各種原料的每月限制用量，三種產(chǎn)品的單位加工費(fèi)及售價如下表1所示。表1原料甲乙丙原料成本（元/千克）每月限制用量（千克）A60%15%25%2.002000B20%25%25%1.502500C20%60%50%1.001200加工費(fèi)（元/千克）0.500.400.30售價3.402.852.25每月應(yīng)生產(chǎn)這三種產(chǎn)品各多少千克，才能使該廠獲利最大呢？對于此問題可以考慮建立線性規(guī)劃的數(shù)學(xué)模型進(jìn)行求解，針對此問題建立數(shù)學(xué)模型。

2問題建模針對上面提出的問題，用以下的數(shù)學(xué)模型來描述，設(shè)x1、x2、x3分別表示每月應(yīng)生產(chǎn)甲、乙、丙這三種產(chǎn)品的千克數(shù)。因?yàn)樵螦、B、C的限量，可以得到以下不等式：該廠的目標(biāo)是在不超過所有資源限量的條件下，如何確定產(chǎn)量x1、x2、x3以得到最大的利潤。若用z表示利潤，這時綜合上述，該計(jì)劃問題可用數(shù)學(xué)模型表示為：目標(biāo)函數(shù)：滿足約束條件：

3計(jì)算機(jī)求解單純形法求解線性規(guī)劃的思路：一般線性規(guī)劃問題具有線性方程組的變量數(shù)大于方程個數(shù)，這時有不定的解。但可以從線性方程組中找出一個個的單純形，每一個單純形可以求得一組解，然后再判斷該解使目標(biāo)函數(shù)值是增大還是變小，決定下一步選擇的單純形。這就是迭代，直到目標(biāo)函數(shù)實(shí)現(xiàn)最大值或最小值為止。這樣問題就得到了最優(yōu)解。對于上面建立的數(shù)學(xué)模型考慮用單純形法進(jìn)行求解。引入松弛變量x4、x5、x6。將目標(biāo)函數(shù)整理得：約束條件變?yōu)椋河缮鲜鰯?shù)據(jù)即可構(gòu)造初始單純形表，如表2所示。表2cj1.21.1750.575000CBXBbx1x2x3x4x5x60x420000.600.150.251000x525000.200.250.250100x612000.200.600.50001使用計(jì)算機(jī)求解得到最優(yōu)解為：X*=(3090.91,969.697,0,0,1639.39,0)T目標(biāo)函數(shù)值為：z*=4848.48

4結(jié)果分析根據(jù)以上的計(jì)算結(jié)果可以知道，每月生產(chǎn)甲產(chǎn)品3090.91千克，乙產(chǎn)品969.697千克，不生產(chǎn)丙產(chǎn)品，可使該廠獲利最大，達(dá)到4848.48元。討論線性規(guī)劃問題時，假定aij、bi、cj都是常數(shù)。但實(shí)際上這些系數(shù)往往是估計(jì)值和預(yù)測值。如市場條件一變，cj值就會變化；aij往往是因工藝條件的改變而改變；bi是根據(jù)資源投入后的經(jīng)濟(jì)效果決定的一種決策選擇。以下將針對上述模型中的cj、bi的變化進(jìn)行討論。當(dāng)cj是非基變量xj的系數(shù)時，若滿足，則原最優(yōu)解仍然為最優(yōu)解，否則需重新計(jì)算。假設(shè)丙產(chǎn)品開始暢銷，其售價由原來的2.25元/千克上漲至3元/千克。那么重新計(jì)算的結(jié)果為：每月生產(chǎn)甲產(chǎn)品2800千克，丙產(chǎn)品1280千克，不生產(chǎn)乙產(chǎn)品，可使該廠獲利最大，達(dá)到5056元。若售價由原來的2.25元/千克上漲至2.75元/千克。重新計(jì)算的結(jié)果仍然為原最優(yōu)解。由以上分析中的公式可知丙產(chǎn)品售價小于2.837879元/千克時，原最優(yōu)解不變。以上兩組數(shù)據(jù)驗(yàn)證了這一靈敏度分析。當(dāng)cj是基變量xj的系數(shù)時，若滿足，j=1，2，…，n，則原最優(yōu)解仍然為最優(yōu)解，否則需重新計(jì)算。假設(shè)甲產(chǎn)品開始暢銷，其售價由原來的3.40元/千克上漲至6元/千克。那么重新計(jì)算的結(jié)果仍然為原最優(yōu)解。若甲產(chǎn)品開始滯銷，其售價由原來的3.40元/千克下調(diào)至2.5元/千克。那么重新計(jì)算的結(jié)果為：每月生產(chǎn)乙產(chǎn)品2000千克，不生產(chǎn)甲產(chǎn)品和丙產(chǎn)品，可使該廠獲利最大，達(dá)到2350元。由以上分析中的公式，j=1，2，…，n，可知甲產(chǎn)品的售價介于2.59和6.9元/千克之間時最優(yōu)解不變。以上兩組數(shù)據(jù)驗(yàn)證了這一靈敏度分析。當(dāng)br發(fā)生變化時，若滿足，則原最優(yōu)基不變，但最優(yōu)解的值發(fā)生了變化，所以為新的最優(yōu)解。假設(shè)工廠新增了原料B，每月的限制用量上調(diào)至3000千克，那么重新計(jì)算的結(jié)果為：每月生產(chǎn)甲產(chǎn)品3090.91千克，生產(chǎn)乙產(chǎn)品969.697千克，不生產(chǎn)丙產(chǎn)品，可使該廠獲利最大，達(dá)到4848.48元。若工廠減少了原料B，每月的限制用量下調(diào)至500千克，那么重新計(jì)算的結(jié)果為：每月生產(chǎn)甲產(chǎn)品2500千克，不生產(chǎn)乙產(chǎn)品和丙產(chǎn)品，可以使該廠獲利最大，達(dá)到3000元。由以上分析中的公式，可知當(dāng)原料B的限制用量大于530.303千克時，可以使得原最優(yōu)基不變，但最優(yōu)解的值會發(fā)生變化。以上兩組數(shù)據(jù)驗(yàn)證了這一靈敏度分析。

5附錄計(jì)算機(jī)求解使用的語言是C++，實(shí)現(xiàn)代碼如下所示：#include<iostream>usingnamespacestd;intmain(intargc,_TCHAR*argv[]){ intM,N,XB[100],human[100],num,i,j,k,l; floatA[100][100],a[100][100],b[100],th[100],C[100],cj_zj[100],CB[100]; //獲取初始數(shù)據(jù) cout<<"構(gòu)建初始單純形表。"<<endl <<"輸入決策變量的個數(shù)N="; cin>>N; cout<<"輸入價值向量C："; for(i=0;i<N;i++) { cin>>C[i]; } cout<<"輸入約束方程組中方程的個數(shù)M="; cin>>M; cout<<"輸入約束方程組的增廣矩陣："<<endl; for(i=0;i<M;i++) { for(intj=0;j<N;j++) { cin>>A[i][j]; } cin>>b[i]; } cout<<"輸入初始的CB："; for(i=0;i<M;i++) { cin>>CB[i]; } cout<<"輸入初始的XB："; for(i=0;i<M;i++) { cin>>XB[i]; XB[i]--; } cout<<"輸入人工變量的個數(shù)："; cin>>num; if(num>0) { cout<<"輸入人工變量："<<endl; for(i=0;i<num;i++) { cin>>human[i]; human[i]--; } }loop: //計(jì)算cj-zj cout<<"cj-zj為："<<endl; for(j=0;j<N;j++) { boolflag=false; for(i=0;i<M;i++) { if(j==XB[i]) { flag=true; break; } } if(flag) { cj_zj[j]=0; cout<<cj_zj[j]<<""; continue; } floatsum=0; for(i=0;i<M;i++) { sum+=CB[i]*A[i][j]; } cj_zj[j]=C[j]-sum; cout<<cj_zj[j]<<""; } cout<<endl<<endl; //判斷是否所有cj-zj<=0 for(j=0;j<N;j++) { if(cj_zj[j]>0) { break; } } if(j<N) { for(i=0;i<M;i++) { if(A[i][j]>0) { break; } } if(i<M) { //確定換入變量 floatmaxj=0; k=0; for(j=0;j<N;j++) { if(cj_zj[j]>maxj) { k=j; maxj=cj_zj[j]; } } cout<<"換入變量為："<<k+1<<endl<<endl; //求旋轉(zhuǎn)變量 cout<<"旋轉(zhuǎn)變量為："; for(i=0;i<M;i++) { if(A[i][k]>0) { th[i]=b[i]/A[i][k]; } else { th[i]=-1; } cout<<th[i]<<""; } cout<<endl<<endl; //確定換出變量 floatminj=1000000; for(i=0;i<M;i++) { if(th[i]<0) { continue; } if(th[i]<minj) { minj=th[i]; /*l=XB[i];*/ l=i; } } cout<<"換出變量為："<<XB[l]+1<<endl<<endl; //迭代運(yùn)算 XB[l]=k; CB[l]=C[k]; floatbb[100]; for(i=0;i<M;i++) { for(j=0;j<N;j++) { a[i][j]=A[i][j]; } bb[i]=b[i]; } b[l]=bb[l]/a[l][k]; for(j=0;j<N;j++) { A[l][j]=a[l][j]/a[l][k]; } for(i=0;i<M;i++) { if(i==l) { continue; } for(j=0;j<N;j++) { A[i][j]=a[i][j]-A[l][j]*a[i][k]; } b[i]=bb[i]-b[l]*a[i][k]; } cout<<"增廣矩陣為："<<endl; for(i=0;i<M;i++) { for(j=0;j<N;j++) { cout<<A[i][j]<<""; } cout<<b[i]<<endl; } cout<<endl; gotoloop; } else { cout<<"此問題無界！"<<endl; return0; } } else { for(i=0;i<M;i++) { for(j=0;j<num;j++) { if(XB[i]==human[j]&&CB[i]!=0) { cout<<"此問題無可行解！"<<endl; return0; } } } for(i=0;i<N;i++) { for(j=0;j<M;j++) { if(i==XB[j]) { break; } } if(j<M) { continue; } else { if(cj_zj[i]==0) { cout<<"此問題有無窮多最優(yōu)解！"<<endl; return0; } } } cout<<"此問題有唯一解！"<<endl; cout<<"最優(yōu)解為："<<endl; floatX[100]; for(