单纯形法求解线性规划的步骤.pdf

单纯形法求解线性规划的步骤

1初始化

将给定的线性规划问题化成标准形式,并建立一个初始表格,它最右边的单元格都是非负的(否则无解),接下来的m列

组成一个m*m的单元矩阵(目标行的单元格则不必满足这一条件),这m列确定了初始的基本可行解的基本变量,而表

格中行用基本变量来表示

2最优化测试

如果目标行的所有单元格都是非负的(除了最右列中代表目标函数值的那个单元格),就可以停止了,该表格代表了一

个最优解,它的基本变量的值在最右列中,而剩下的非基本变量都为0

3确定输入变量

从目标行的前n个单元格中选择一个负的单元格(选择绝对值最大的那个)该单元格所在的列确定的输入变量及主元

列

4确定分离变量

对于主元列的每个正单元格,求出θ比率(如果主元格的单元格为负或为0,说明该问题是无解的,算法终止),找出θ比

率最小的列,改行确定了分离变量和主元行

5建立下一张表格

将主元行的所有单元格除以主元得到新的主元行,包括主元行在内的每一行,要减去改行主元列单元格和新主元行的

成绩(除主元行为1外,这一步将主元列的所有单元格变成0).把主元列的变量名进行代换,得到新的单纯形表,返回第

一步

为求简单

在本程序中,需要自己建立标准矩阵(比如加入松弛变量等工作需要用户自己完成),程序的输入有两种方式:

1:指定行和列,由用户自行输入每一个元素SimpleMatrix(introw=0,intcol=0);

2:直接在主程序中初始化一个二维数组,然后利用构造函数SimpleMatrix(introw,intcol,double**M)来初始化和处

理(本程序所用的实例用的是这种方法)

程序中主要的函数以及说明

~SimpleMatrix();

销毁动态分配的数组.用于很难预先估计矩阵的行和列,所以在程序中才了动态的内存分配.需要重载析构函数

boolIs_objectLine_All_Positive();其中row2为主元所在的行,col为主元所在的列,row1为要处理的行

voidPrintAnswer();数不数不合合法法

}

SimpleMatrix::SimpleMatrix(introw,intcol)

{

init(row,col);

for(inti=0;irowLen;i++)

{

returnfalse;

}

returntrue;

}

intSimpleMatrix::InColumn()

{

intcount=0;

for(inti=0;icolLen-1;i++)

{

inttemp=GetItem(rowLen-1,i);

if(temp=0)

{

count++;

}

else

break;

}

doublemaxItem=fabs(GetItem(rowLen-1,count));

intindex_col;

for(i=0;icolLen-1;i++)

{

doubletemp=GetItem(rowLen-1,i);

if(temp0)

{

if(maxItem=fabs(temp))

{

maxItem=fabs(temp);

index_col=i;

}

}

}

returnindex_col;

}

intSimpleMatrix::DepartRow(intcol)

{

intindex_row;

intcount=0;

for(inti=0;irowLen;i++)

{

if(data[i][col]0)

count++;

else

break;

}

doubleminItem=data[count][colLen-1]/data[count][col];

index_row=count;

doubletemp;

for(i=0;irowLen-1;i++)

{

temp=data[i][col];

if(temp0)

{

temp=data[i][colLen-1]/temp;

if(tempminItem)

{

minItem=temp;

index_row=i;

}