単純アルゴリズムで線形計画を解く
32614 ワード
「アルゴリズム導論」第七部分第29章は線形計画の単純性アルゴリズムについての解説があります.
ここにmingxinglai同志の学習ブログを添付します.コードにはバグがあり、正確に最適解を解除できませんでした.リンク:http://blog.csdn.net/lalor/article/details/7314134
また、線形計画の解決については、MATLABやLINGO、LINGOの方が専門的で、多パラメータにも適しています.
cygwinでコンパイルすることができます.g++を使う必要があります.そうでなければcan't find streamもgcc-lstdc++.中国語の文字セットを使わないとcygwinによく表示されません.他の集積開発環境でコンパイルして実行したほうがいいです.
原文のリンク:http://read.pudn.com/downloads107/sourcecode/windows/system/439107/%E5%8D%95%E7%BA%AF%E6%80%A7%E7%AE%97%E6%B3%95.cpp__.http
ここにmingxinglai同志の学習ブログを添付します.コードにはバグがあり、正確に最適解を解除できませんでした.リンク:http://blog.csdn.net/lalor/article/details/7314134
また、線形計画の解決については、MATLABやLINGO、LINGOの方が専門的で、多パラメータにも適しています.
cygwinでコンパイルすることができます.g++を使う必要があります.そうでなければcan't find streamもgcc-lstdc++.中国語の文字セットを使わないとcygwinによく表示されません.他の集積開発環境でコンパイルして実行したほうがいいです.
原文のリンク:http://read.pudn.com/downloads107/sourcecode/windows/system/439107/%E5%8D%95%E7%BA%AF%E6%80%A7%E7%AE%97%E6%B3%95.cpp__.http
1 // Visual C++
2 #include<iostream>
3 #include<cmath>
4 using namespace std;
5 #define M 10000
6 //
7 float kernel[11][31];//
8 int m=0,n=0,t=0;//m:
9 //n:
10 //t: ：－1 ，1
11 //
12 void input()
13 {
14 //
15 cout<<"－－－－－－－－－－ －－－－－－－－－－－"<<endl;
16 cout<<" ："<<endl<<endl;
17 cout<<" m: "<<" m= ";
18 cin>>m;
19 cout<<endl<<" n:"<<" n= ";
20 cin>>n;
21 int i,j;
22 //
23 for (i=0;i<=n+1;i++)
24 for (j=0;j<=m+n+n;j++)
25 kernel [i][j]=0;
26 //
27 cout<<endl<<" （1 <=,-1 >=）:"<<endl<<endl<<" ";
28 for (i=1;i<=m;i++)
29 cout<<" x"<<i;
30 cout<<" "<<" "<<endl;
31 for (i=1;i<=n;i++)
32 {
33 cout<<" "<<i<<" ";
34 for (j=1;j<=m+2;j++)
35 cin>>kernel [i][j];
36 }
37
38 for (i=1;i<=n;i++)
39 {
40 kernel [i][0]=kernel [i][m+2];
41 kernel [i][m+2]=0;
42 }
43 //
44 cout<<endl<<endl<<" （ :1； :-1）:"<<endl<<endl<<" ";
45 for(i=1;i<=m;i++)
46 cout<<"x"<<i<<" ";
47 cout<<" "<<endl<<" ";
48 cout<<" : ";
49 for (i=1;i<=m;i++)
50 cin>>kernel [0][i];
51 cin>>t;
52 //
53 if(t==-1)
54 for(i=1;i<=m;i++)
55 kernel [0][i]=(-1)*kernel [0][i];
56 for(i=1;i<=n;i++)
57 {
58 kernel [i][m+i]=kernel [i][m+1];
59 if(i!=1)
60 kernel [i][m+1]=0;
61 }
62 }
63
64 //
65 void comput()
66 {
67 int i,j,flag,temp1,temp2,h,k=0,temp3[10];
68 float a,b[11],temp,temp4[11],temp5[11],f=0,aa,d,c;
69 //
70 for(i=1;i<=n;i++)
71 temp3[i]=0;
72 for(i=0;i<11;i++)
73 { temp4[i]=0;
74 temp5[i]=0;
75 }
76 for(i=1;i<=n;i++)
77 {
78 if(kernel [i][m+i]==-1)
79 {
80 kernel [i][m+n+i]=1;
81 kernel [0][m+n+i]=M;
82 temp3[i]=m+n+i;
83 }
84 else
85 temp3[i]=m+i;
86 }
87 for(i=1;i<=n;i++)
88 temp4[i]=kernel [0][temp3[i]];
89
90 //
91 do{
92 for(i=1;i<=m+n+n;i++)
93 {
94 a=0;
95 for(j=1;j<=n;j++)
96 a+=kernel [j][i]*temp4[j];
97 kernel [n+1][i]=kernel [0][i]-a;
98 }
99 for(i=1;i<=m+n+n;i++)
100 {
101 if(kernel [n+1][i]>=0) flag=1;
102 else
103 {
104 flag=-1;
105 break;
106 }
107 }
108 if(flag==1)
109 { for(i=1;i<=n;i++)
110 {
111 if(temp3[i]<=m+n) temp1=1;
112 else
113 {
114 temp1=-1;
115 break;
116 }
117 }
118 //
119 cout<<endl<<endl;
120 cout<<"－－－－－－－－－－ －－－－－－－－－－－"<<endl<<endl;
121 if(temp1==1)
122 {
123 cout<<" !"<<endl<<endl<<" ："<<endl<<endl<<" ";
124 for(i=1;i<=n;i++)
125 temp5[temp3[i]]=kernel [i][0];
126 for(i=1;i<=m;i++)
127 f+=t*kernel [0][i]*temp5[i];
128
129 for(i=1;i<=m;i++)
130 {
131 cout<<"x"<<i<<" = "<<temp5[i];
132 if(i!=m)
133 cout<<"， ";
134 }
135 cout<<" ;"<<endl<<endl<<" f= "<<f<<endl<<endl;
136 return ;
137 }
138 else
139 {
140 cout<<" "<<endl<<endl;
141 return ;
142 }
143 }
144 if(flag==-1)
145 {
146 temp=100000;
147 for(i=1;i<=m+n+n;i++)
148 if(kernel [n+1][i]<temp)
149 {
150 temp=kernel [n+1][i];
151 h=i;
152 }
153
154 for(i=1;i<=n;i++)
155 {
156 if(kernel [i][h]<=0) temp2=1;
157 else {
158 temp2=-1;
159 break;
160 }
161 }
162 }
163 if(temp2==1)
164 {
165 cout<<" ";
166 return ;
167 }
168 if(temp2==-1)
169 {
170 c=100000;
171 for(i=1;i<=n;i++)
172 {
173 if(kernel [i][h]!=0) b[i]=kernel [i][0]/kernel [i][h];
174 if(kernel [i][h]==0) b[i]=100000;
175 if(b[i]<0) b[i]=100000;
176 if(b[i]<c)
177 {
178 c=b[i];
179 k=i;
180 }
181 }
182 temp3[k]=h;
183 temp4[k]=kernel [0][h];
184 d=kernel [k][h];
185 for(i=0;i<=m+n+n;i++)
186 kernel [k][i]=kernel [k][i]/d;
187 for(i=1;i<=n;i++)
188 { if(i==k)
189 continue;
190 aa=kernel [i][h];
191 for(j=0;j<=m+n+n;j++)
192 kernel [i][j]=kernel [i][j]-aa*kernel [k][j];
193 }
194 }
195
196 }
197 while(1);
198 return ;
199 }
200
201 //
202 int main()
203 { cout<<"------------------- ----------------------"<<endl<<endl;
204 input();
205 comput();
206 return 1;
207 }