0050算法笔记线性规划单纯形算法未完全实现Word文件下载.docx
《0050算法笔记线性规划单纯形算法未完全实现Word文件下载.docx》由会员分享，可在线阅读，更多相关《0050算法笔记线性规划单纯形算法未完全实现Word文件下载.docx（23页珍藏版）》请在冰点文库上搜索。
如果入基变量所在的列与基本变量所在行交叉处的表元素为负数，那么该元素将不受任何限制，相应的基本变量只会越变越大。
如果入基变量所在列的所有元素都是负值，则目标函数无界，已经得到了问题的无界解。
如果选出的列中有一个或多个元素为正数，要弄清是哪个数限制了入基变量值的增加。
受限的增加量可以用入基变量所在列的元素（称为主元素）来除主元素所在行的“常数列”（最左边的列）中元素而得到。
所得到数值越小说明受到限制越多。
应该选取受到限制最多的基本变量作为离基变量，才能保证将入基变量与离基变量互调位置后，仍满足约束条件。
上例中，惟一的一个值为正的z行元素是3，它所在列中有2个正元素，即4和3。
min{12/4,10/3}=4，应该选取x4为离基变量；
入基变量x3取值为3。
单纯形算法的第3步：
转轴变换。
转轴变换的目的是将入基变量与离基变量互调位置。
给入基变量一个增值，使之成为基本变量；
修改离基变量，让入基变量所在列中，离基变量所在行的元素值减为零，而使之成为非基本变量。
解离基变量所相应的方程，将入基变量x3用离基变量x4表示为
再将其代入其他基本变量和所在的行中消去x3，
代入目标函数得到
形成新单纯形表
单纯形算法的第4步：
转回并重复第1步，进一步改进目标函数值。
不断重复上述过程，直到z行的所有非基本变量系数都变成负值为止。
这表明目标函数不可能再增加了。
在上面的单纯形表中，惟一的值为正的z行元素是非基本变量x2相应的列，其值为1/2。
因此，选取非基本变量x2作为入基变量。
它所在列中有惟一的正元素5/2，即基本变量x1相应行的元素。
因此，选取x1为离基变量。
再经步骤3的转轴变换得到新单纯形表。
新单纯形表z行的所有非基本变量系数都变成负值，求解过程结束。
整个问题的解可以从最后一张单纯形表的常数列中读出。
目标函数的最大值为11；
最优解为：
x*=（0,4,5,0,0,11）。
单纯形算法计算步骤如下：
步骤1：
选入基变量。
如果所有cj0，则当前基本可行解为最优解，计算结束。
否则取ce>
0相应的非基本变量xe为入基变量。
步骤2：
选离基变量。
对于步骤1选出的入基变量xe，如果所有aie0，则最优解无界，计算结束。
否则计算
选取基本变量xk为离基变量。
新的基本变量下标集为
新的非基本变量下标集为
步骤3：
作转轴变换。
新单纯形表中各元素变换如下。
步骤4：
转步骤1。
4、将一般问题转化为约束标准型
有几种巧妙的办法可以将一般的线性规划问题转换为约束标准型线性规划问题。
首先，需要把或形式的不等式约束转换为等式约束。
具体做法是，引入松弛变量，利用松弛变量的非负性，将不等式转化为等式。
松驰变量记为yi，共有m1+m3个。
在求解过程中，应当将松弛变量与原来变量同样对待。
求解结束后，抛弃松弛变量。
注意松弛变量前的符号由相应的原不等式的方向所确定。
为了进一步构造标准型约束，还需要引入m个人工变量，记为zi。
至此，原问题已经变换为等价的约束标准型线性规划问题。
对极小化线性规划问题，只要将目标函数乘以-1即可化为等价的极大化线性规划问题。
5、一般线性规划问题的2阶段单纯形算法
引入人工变量后的线性规划问题与原问题并不等价，除非所有zi都是0。
为了解决这个问题，在求解时必须分2个阶段进行。
第一阶段用一个辅助目标函数
替代原来的目标函数。
这个线性规划问题称为原线性规划问题所相应的辅助线性规划问题。
对辅助线性规划问题用单纯形算法求解。
如果原线性规划问题有可行解，则辅助线性规划问题就有最优解，且其最优值为0，即所有zi都为0。
在辅助线性规划问题最后的单纯形表中，所有zi均为非基本变量。
划掉所有zi相应的列，剩下的就是只含xi和yi的约束标准型线性规划问题了。
单纯形算法第一阶段的任务就是构造一个初始基本可行解。
单纯形算法第二阶段的目标是求解由第一阶段导出的问题。
此时要用原来的目标函数进行求解。
如果在辅助线性规划问题最后的单纯形表中，zi不全为0，则原线性规划问题没有可行解，从而原线性规划问题无解。
6、一般线性规划问题的2阶段单纯形算法
用单纯形算法解一般的线性规划问题时，可能会遇到退化的情形，即在迭代计算的某一步中，常数列中的某个元素的值变成0，使得相应的基本变量取值为0。
如果选取退化的基本变量为离基变量，则作转轴变换前后的目标函数值不变。
在这种情况下，算法不能保证目标函数值严格递增，因此，可能出现无限循环。
考察下面的由Beale在1955年提出的退化问题的例子。
按照2阶段单纯形算法求解该问题将出现无限循环。
Bland提出避免循环的一个简单易行的方法。
Bland提出在单纯形算法迭代中，按照下面的2个简单规则就可以避免循环。
规则1：
设
，取xe为入基变量。
规则2：
设
取xk为离基变量。
算法leave（col）已经按照规则2选取离基变量。
选取入基变量的算法enter（objrow）中只要加一个break语句即可。
7、算法描述和实现
1.//线性规划
单纯性算法
2.#include
"
3.#include
<
cmath>
4.#include
iostream>
5.#include<
fstream>
6.using
namespace
std;
7.
8.class
LinearProgram
9.{
10.
public:
11.
LinearProgram（char
*
filename）;
12.
~LinearProgram（）;
13.
void
solve（）;
14.
private:
15.
int
enter（int
objrow）;
16.
leave（int
col）;
17.
simplex（int
18.
phase1（）;
19.
phase2（）;
20.
compute（）;
21.
swapbasic（int
row,int
22.
pivot（int
23.
stats（）;
//这个方法是干什么的
24.
setbasic（int
basicp）;
25.
output（）;
26.
m,
//约束总数
27.
n，
//变量数
28.
m1,
//不等式约束数<
=
29.
m2,
//等式约束
30.
m3,
//不等式约束数>
31.
n1,n2,
//n1
n
+
m3,n2
n1
m1
32.
error,
//记录错误类型
33.
*basic,
//基本变量下标
34.
*nonbasic;
//非基本变量下标
35.
double
**a,minmax;
36.};
37.
38.//从标准输入文件中读入数据，构造初始单纯形表
39.LinearProgram:
:
*filename）
40.{
41.
ifstream
inFile;
42.
i,j;
43.
value;
44.
cout<
按照下列格式输入数据：
endl;
45.
1:
+1（max）或-1（min）;
m;
n"
46.
2:
m1;
m2;
m3"
47.
约束系数和右端项"
48.
目标函数系数"
49.
error
0;
50.
51.
（filename）;
52.
inFile>
>
minmax;
53.
54.
n;
55.
56.
//输入各类约束数
57.
58.
59.
m3;
60.
61.
if（m!
=m1+m2+m3）
62.
{
63.
1;
64.
}
65.
66.
67.
n2
68.
Make2DArray（a,m+2,n1+1）;
//构造二维数组
69.
basic
new
int[m+2];
70.
nonbasic
int[n1+1];
71.
72.
//初始化基本变量和非基本变量
73.
for（int
i=0;
i<
=m+1;
i++）
74.
75.
j=0;
j<
=n1;
j++）
76.
77.
a[i][j]
78.
79.
80.
81.
82.
83.
nonbasic[j]
j;
84.
85.
86.
//引入松弛变量和人工变量
87.
i=1,j=n1+1;
=m;
i++,j++）
88.
89.
basic[i]
90.
91.
i=m-m3+1,j=n+1;
92.
93.
;
94.
a[m+1][j]
95.
96.
97.
//输入约束系数和右端项
98.
i=1;
99.
100.
j=1;
=n;
101.
102.
103.
104.
105.
106.
if（value<
0）
107.
108.
109.
110.
a[i][0]
111.
112.
113.
//输入目标函数系数
114.
115.
116.
117.
a[0][j]
value
118.
119.
120.
//引入人工变量，构造第1阶段的辅助目标函数
121.
122.
123.
i=m1+1,value=;
124.
125.
+=
a[i][j];
126.
127.
128.
129.
（）;
130.}
131.
132.//根据目标函数系数所在的行objrow，执行约束标准型线性规划问题的单纯形算法
133.int
LinearProgram:
objrow）
134.{
135.
row
）
136.
137.
col
enter（objrow）;
138.
if（col>
139.
140.
leave（col）;
141.
142.
else
143.
144.
return
145.
146.
if（row>
147.
148.
pivot（row,col）;
149.
150.
151.
152.
2;
153.
154.
155.}
156.
157.//根据目标函数系数所在行objrow，选取入基变量
158.int
159.{
160.
temp
DBL_EPSILON;
//什么含义
161.
j=1,col=0;
n1;
162.
163.
if（nonbasic[j]<
=n2
&
a[objrow][j]>
temp）
164.
165.
166.
a[objrow][j];
167.
break;
//Bland避免循环法则
168.
169.
170.
col;
171.}
172.
173.//根据入基变量所在列col,选取离基变量
174.int
col）
175.{
176.
DBL_MAX;
//怎么定义的值为多少
177.
i=1,row=0;
178.
179.
val
a[i][col];
180.
if（value>
DBL_EPSLION）
181.
182.
a[i][0]/val;
183.
if（val<
184.
185.
i;
186.
val;
187.
188.
189.
190.
row;
191.}
192.
193.//以入基变量所在列col和离基变量所在行row交叉处元素a[row][col]为轴心，做转轴变换
194.void
195.{
196.
197.
198.
if（j!
=col）
199.
200.
a[row][j]
a[row][j]/a[row][col];
201.
202.
203.
a[row][col]
a[row][col];
204.
m+1;
205.
206.
if（i!
=row）
207.
208.
209.
210.
211.
212.
-
a[i][col]*a[row][j];
213.
if（fabs（a[i][j]<
214.
升级会员 