下载文档原格式
◼1.5 求解线性规划问题的单纯形法➢LP问题的几何意义➢单纯形法的经济解释➢单纯形法的计算步骤❖基本概念为凸集。
则称若设K K XXK XK X),10( )1( ,,)2()1()2()1(≤≤∈−+∈∈ααα 1、凸集：在某个点集K 中任给出两点，若连接这两点的线段上的一切点也在此点集中。
即2、顶点：不能用不同的两点的线性组合表示的点。
➢LP 问题的几何意义❖基本定理➢LP问题的可行域是凸集。
➢可行解X=(x,x2,…,x m,0,…,0)T是基本可行解的充要条件是X1的非零分量所对应的系数列向量是线性无关的➢基本可行解对应可行域的顶点➢有可行解必有基本可行解，即凸集非空、有顶点➢最优解一定在可行域的顶点上得到（必定在基本可行解中）例设有一家具厂用木材和钢材生产A,B,C 三种家具，生产一件家具所需的材料、每件家具可获得的利润以及每月可供的木材和钢材数量如下表，问此家具厂应如何安排各种家具的生产量才能使企业获得最大的利润？产品木材钢材单位产品获利（元）A B C3 21 14 4415材料可供量8000 3000解：设A,B,C 三件家具的产量(件数)分别为x 1,x 2,x 3，有：⎪⎩⎪⎨⎧=≥≤++≤++++=3,2,1,0300042800043..54321321321j x x x x x x x t s x x x MaxZ j➢单纯形法的经济解释模型的标准型为：⎪⎩⎪⎨⎧=≥=+++=+++⋅+⋅+++=5,4,3,2,1,0300042800043..00545321432154321j x x x x x x x x x t s x x x x x MaxZ j系数矩阵和基：⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡=10011041201413B A 取则：x 4, x 5为初始基变量; x 1, x 2x 3为非基变量，变换标准型的约束条件：⎩⎨⎧−−−=−−−=32153214423000438000x x x x x x x x 代入目标函数：Z = 0 + 4x 1+ x 2+ 5x 3令非基变量等于0，基变量x 4=8000, x 5=3000)3000,8000,0,0,0()0(==Z XT初始基本可行解经济解释观察目标函数：321540x x x Z +++=选x 3入基，x 1, x 2仍为非基变量且为0，代入上方程组：75043000,48000min 04300004800033534=⎭⎬⎫⎩⎨⎧=⎩⎨⎧≥−=≥−=x x x x x 则：则：基变量为x 4, x 3;非基变量为x 1, x 2x 5，变换标准型的约束条件：⎪⎩⎪⎨⎧−−−=+−=⇒⎩⎨⎧−−−=−−=+521351452132143414121430005000230004380004x x x x xx x x x x x x x x x 代入目标函数：Z = 3750 + 1.5x 1－0.25x 2－1.25x 5 令非基变量等于0，基变量x 3=750,x 4=50003750)0,5000,750,0,0()1(==Z XT基本可行解当x 3=750时，x 5=0即为非基变量，x 4=5000观察目标函数：5214541233750x x x Z −−+=选x 1入基，x 2, x 5仍为非基变量，且为0，代入上方程组：{}15002*750,5000min 0217500500011314==⎪⎩⎪⎨⎧≥−=≥−=x x x x x 则：则：基变量为x 1, x 4; 非基变量为x 2, x 3x 5，变换标准型的约束条件：⎪⎪⎩⎪⎪⎨⎧−−−=+++=⇒⎩⎨⎧−−−=−−=+5321532453213241212211500232213500430002480003xx x x x x x x x x x x x x x x 代入目标函数：Z = 6000 －x 2－3x 3－2x 5 令非基变量等于0，基变量x 1=1500, x 4=35006000)0,3500,0,0,1500()2(==Z XT最优解当x 1=1500时，x 3=0即为非基变量，x 4=3500将问题化标准型，求出初始基本可行解，建立初始单纯形表是否最优？是否无解？最优解YNY无解N确定换入变量、换出变量，迭代，得到一个新的基本可行解➢单纯形法的计算步骤例线性规划问题的标准型：⎪⎩⎪⎨⎧=≥=+++=+++⋅+⋅+++=5,4,3,2,1,0300042800043..00545321432154321j x x x x x x x x x t s x x x x x MaxZ j初始单纯形表：∑='=mi iji j a c Z 1c j → 41 5 0 0 C ’ B X B b x 1 x2 x3 x4 x5 0 0X 4 X 5 8000 30003 2 1 14 4 1 0 0 1 Z j C j – Z j0 40 10 50 00 0初始解为X=(0,0,0,8000,3000)Z=0检验数表达式推导：∑∑∑∑∑∑∑∑∑∑+=+====+=+=+==+=−+='−+'=+−'=+'=−=nm j jj jnm j jm i ij i j mi i imi nm j jjnm j j iji inm j j jmi i i nm j jiji i x z cZ x a c c b cx cx ab cx cx c Z m i x ab x 10111111111)()()(),,2,1(＝代入目标函数式： ➢判别式：MaxZ: c j –z j ≤ 0 (对于所有的非基变量）问题达到最优；换入变量的确定：{}入基K K K j j x Z c Z c Max ⇒−=>−0换出变量的确定：出基L LKLik ik i x a b a a b Min ⇒=⎭⎬⎫⎩⎨⎧>=0,θ系数矩阵的变换：按照增广矩阵的变换规则，将基变量的系数矩阵转化为单位矩阵，非基矩阵和资源向量作相应的变化。
运筹学单纯形法各个步骤详解1. 引言大家好，今天咱们来聊聊一个听起来有点高深莫测，但其实特别有意思的东西——运筹学的单纯形法。
别看它名字复杂，其实它就是解决线性规划问题的绝招，像一把钥匙，打开了优化的宝藏。
想象一下，如果你有一大堆资源，要把它们分配到不同的地方，听起来就像玩拼图一样。
好了，废话不多说，咱们直接进入正题！2. 单纯形法的基本概念2.1 线性规划的起源首先，线性规划是啥？简单来说，它就是在一系列限制条件下，想要最大化或最小化某个目标函数。
这听起来像是在做一场抉择，你得在各种选择中找到最优解。
有点像在超市里，看到一堆零食，犹豫不决，最后只能选那包最爱吃的，既美味又划算。
2.2 单纯形法的基本思路而单纯形法就是解决这个问题的武器。
它的核心思想很简单，跟追求完美一样，咱们要一步步地朝着最优解迈进。
想象你在爬山，每一步都在找那个最容易走的路，直到你站在山顶，俯瞰整个美景，啊，真是太棒了！3. 单纯形法的步骤3.1 初始化那么，怎么开始呢？首先，咱们得把问题转化为标准形式。
这就像把一个繁杂的图案简化成几何图形，让它看起来更清晰。
要把不等式转换为等式，添加松弛变量，这样就可以把问题整理得干干净净。
3.2 构建初始单纯形表接下来，咱们构建初始单纯形表。
这个表就像一本菜单，上面列出了所有可能的选择和它们的成本。
每个变量都有自己的“价格”，而咱们的目标就是尽量少花钱，最大化收益。
想想你逛街时，总是想着要花最少的钱买到最好的东西，嘿，这就是单纯形法的精神！3.3 寻找基变量和入基变量然后，咱们得找出“基变量”和“入基变量”。
基变量就像在舞台上表演的演员，而入基变量就是准备加入的“新人”。
在这个过程中，咱们得判断哪个新人能让整个表演更精彩。
如果找对了，舞台瞬间就能变得熠熠生辉，若是找错了，哎呀，那可就尴尬了。
3.4 更新单纯形表一旦找到了合适的入基变量，咱们就得更新单纯形表。
这一步就像在调味，添加新的元素，让整体味道更加丰富。
单纯形法求解线性规划的步骤
1>初始化
将给定的线性规划问题化成标准形式,并建立一个初始表格,它最右边的单元格都是非负的(否则无解),接下来的m列组成一个m*m的单元矩阵(目标行的单元格则不必满足这一条件),这m列确定了初始的基本可行解的基本变量,而表格中行用基本变量来表示
2>最优化测试
如果目标行的所有单元格都是非负的(除了最右列中代表目标函数值的那个单元格),就可以停止了,该表格代表了一个最优解,它的基本变量的值在最右列中,而剩下的非基本变量都为0
3>确定输入变量
从目标行的前n个单元格中选择一个负的单元格(选择绝对值最大的那个)该单元格所在的列确定的输入变量及主元列
4>确定分离变量
对于主元列的每个正单元格,求出θ比率(如果主元格的单元格为负或为0,说明该问题是无解的,算法终止),找出θ比率最小的列,改行确定了分离变量和主元行
5>建立下一张表格
将主元行的所有单元格除以主元得到新的主元行,包括主元行在内的每一行,要减去改行主元列单元格和新主元行的成绩(除主元行为1外,这一步将主元列的所有单元格变成0).把主元列的变量名进行代换,得到新的单纯形表,返回第一步
为求简单
在本程序中,需要自己建立标准矩阵(比如加入松弛变量等工作需要用户自己完成),程序的输入有两种方式:
1:指定行和列,由用户自行输入每一个元素SimpleMatrix(introw=0,int col=0);
2:直接在主程序中初始化一个二维数组,然后利用构造函数SimpleMatrix(introw,int col,double **M) 来初始化和处理(本程序所用的实例用的是这种方法)
程序中主要的函数以及说明
~SimpleMatrix();
销毁动态分配的数组.用于很难预先估计矩阵的行和列,所以在程序中才了动态的内存分配.需要重载析构函数
bool Is_objectLine_All_Positive();其中row2为主元所在的行,col为主元所在的列,row1为要处理的行
void PrintAnswer();数不合法"<<endl;
}
SimpleMatrix::SimpleMatrix(int row,int col)
{
init(row,col);
for(int i=0;i<rowLen;i++)
cout<<"请输入矩阵中第"<<i+1<<"行的系数"<<endl; for(int j=0;j<colLen;j++)
cin>>data[i][j];
}
？
}
SimpleMatrix::SimpleMatrix(int row,int col,double **M) {
rowLen=row;
colLen=col;
init(row,col);
for (int i=0;i<row;i++)
for(int j=0;j<col;j++)
{
data[i][j]=*((double*)M+col*i+j); ;
}
}
SimpleMatrix::~SimpleMatrix()
{
if(colLen*rowLen != 0 )
{
for(int i=rowLen-1;i>=0;i--)
{
if (data[i]!=NULL)
delete[] data[i];
}
if (data!=NULL)
delete[] data;
}？
}
bool SimpleMatrix::Is_objectLine_All_Positive()
{
for(int i=0;i<colLen-1;i++)
if(data[rowLen-1][i]<0)
return false;
return true;
}
bool SimpleMatrix::Is_MainCol_All_Negative(int col) {
for(int i=0;i<rowLen;i++)
if(data[i][col]>0)
return false;
return true;
}
bool SimpleMatrix::Is_column_all_Positive(int col)
{
for(int i=0;i<rowLen-1;i++)
{
return false;
}
return true;
}
int SimpleMatrix::InColumn()
{
int count=0;
for(int i=0;i<colLen-1;i++)
{
int temp=GetItem(rowLen-1,i);
if(temp>=0)
{
count++;
}
else
break;
}
double maxItem=fabs(GetItem(rowLen-1,count));
int index_col;
for(i=0;i<colLen-1;i++)
{
double temp=GetItem(rowLen-1,i);
if(temp<0)
{
if(maxItem<=fabs(temp))
{
maxItem=fabs(temp);
index_col=i;
}
}
}
return index_col;
}
int SimpleMatrix::DepartRow(int col)
{
int index_row;
int count=0;
for(int i=0;i<rowLen;i++)
{
if(data[i][col]<0)
count++;
else
break;
}
double minItem=data[count][colLen-1]/data[count][col]; index_row=count;
double temp;
for(i=0;i<rowLen-1;i++)
temp=data[i][col];
if(temp>0)
{
temp=data[i][colLen-1]/temp;
if(temp<minItem)
{
minItem=temp;
index_row=i;
}
}
}
return index_row;
}
void SimpleMatrix::MainItem_To_1(int row,int col)
{
double temp=GetItem(row,col);
pp
#include <iostream>
#include ""
using namespace std;
int main()
{
double M[4][7]={{5,3,1,1,0,0,9},{-5,6,15,0,1,0,15},{2,-1,1,0,0,-1,5},{-10,-15,-12,0,0,0,}}; SimpleMatrix Matrix(4,7,(double **)M);
if(5))//判断是否存在最优解
{
bool p=();//判断主元列是否全部为正,确定是否已经取得最优解
while(!p)
{
int col=();//确定主元所在的行
if(col))//确定线性规划的解是否为无解的
{
cout<<"线性规划问题是无界的,没有最优解"<<endl;
exit(EXIT_FAILURE);
}
else
{
int mainRow=(col);//确定主元所在的行
(mainRow,col);//将主元所在的行做变换,使主元变成1
int i=0;
while(i<())
{
if(i!=mainRow)
{
(i,mainRow,col);//处理矩阵中其他的行,使主元列的元素为0
i++;
}
else
i++;
}
}
}
for(int i=0;i<();i++)//输出变换以后的矩阵,判断是否正确处理{
for (int j=0;j<();j++)
{
cout<<(i,j)<<" ";
}
cout<<endl;
}
p=();
}
();
}
else
cout<<"线性规划无解"<<endl;
return0;
}。
