||
例子是引用:http://dec3.jlu.edu.cn/webcourse/t000048/yun/ch1_05.htm
第一阶段,求初始基可行解:在约束中添加人工变量,使约束矩阵出现单位子矩阵,然后以这些人工变量之和的相反数W求最大为目标函数,进行求解。若第一阶段最优解对应的最优值等于零,则所有人工变量一定都取零值,说明原问题存在基可行解,可以进行第二阶段计算,否则原问题无可行解,应停止计算。
x_4,x_5为松弛变量;x_6,x_7为人工变量。第一阶段,存在最优解是人工变量解为0,原问题才有最优解。
c | 0 | 0 | 0 | 0 | 0 | -1 | -1 | ||
c_B | x_B | B^(-1)b | x_1 | ||||||
x_4 | A | ||||||||
x_6 | |||||||||
x_7 | |||||||||
检验量 [c_B,C_N] - c_B*B^(-1)(B,N) 显然基变量的检验量均为0 |
对于目标函数是极大的,如何填单纯形表:
(1)选择检验量大于0的作为入基,为了避免循环问题,每次选择符合条件的角标最小的非基变量。
(3)在选择好入基以后,对[B^(-1)b,A]做初等行变换,使基变量对应单位阵。
(4)当所有检验量都是小于等于0时,得到最优解。
注:单纯形的过程对应于在凸多面体上一个顶点到另一个顶点的移动过程。
第二阶段,求原问题的最优解:将第一阶段计算得到的最终表,除去人工变量,恢复原来的目标函数,并以第一阶段的最优解为初始基可行解,重新计算检验数,然后用单纯形法继续求解。
对于上面的例子,单纯形的过程如下:
同理:
对于目标函数是极小的,如何填单纯形表:
(1)选择检验量小于0的作为入基,为了避免循环问题,每次选择符合条件的角标最小的非基变量。
(3)在选择好入基以后,对[B^(-1)b,A]做初等行变换,使基变量对应单位阵。
(4)当所有检验量都是大于等于0时,得到最优解。
若变量为自有变量(可取正、负或零,符号无限制),则引入两个非负变量表示。
可参考这一博客:http://www.cnblogs.com/oucsheep/p/3420092.html
glpsol -m glpk_c.input -o glpk_c.sol(自己命名的一个输出文件名)
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-7-17 23:20
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社