目标规划及单纯形法
《运筹学》课程设计
班 级 11应数1班
学 号
姓 名 薛翔文
指导老师 周永华
浙江理工大学理学院数学与应用数学专业
2013年 7 月
目标规划问题模型及单纯形算法
1、设计题目：目标规划问题模型及单纯形算法
已知三个工厂生产的产品供应四个用户需要，各工厂生产量、用户需求量及从各工厂到用户的单位产品的运输费用（详见表1）。现已有最优调配方案(详见表2)，总运费为2950元。但上述方案只考虑了运费为最少，没有考虑到很多具体的情况和条件。考虑到题目中调配方案时要考虑的方面，重新将其定位七项目标，并规定这7个目标重要性次序为：
1、第4用户为重要部门，需要量必须全部满足；
2、供应用户1的产品中，工厂3的产品不少于100单位； 3、为兼顾一般，每个用户满足率不低于80％； 4、新方案总运费不超过原方案的10％；
5、因道路限制，从工厂2到用户4的路线应尽量避免分配运输任务； 6、用户1和用户3的满足率应尽量保持平衡； 7、力求减少总运费
请给出满意的方案供决策。
用表上作业法得最优运输方案，如表2中所示,方案只考虑了运费为最少，没有考虑到很多具体情况和条件。
2、线性规划求解
对于该问题我首先采用了ligo的解题方案，当然如果问题所有的情况都可以满足，是我们最希望看到的情况，然后按照一般的线性规划问题对其进行求解。
问题分析
2.1 问题的理解与解决方向：
本题是在i个工厂的总生产量无法满足j个用户的总需求的前提条件下，关于如何分配各厂到各用户的运输任务，才能在满足各个用户最低需求的基础上实现总运费最小的问题。通过对题目约束条件的分析，运输任务分配方案的制定应该属于优化问题的范畴，再考虑到要符合实际意义的要求，我们选择通过优化知识和整数规划构建出以运费最少为目标函数的线性规划模型，以所建模型来求解总运费的最小值。但考虑到企业追求最大利润的最终目标，生产厂家势必会想尽办法满足现有最大需求，所以供不应求这一不平衡情况是不普遍的，故对题目目标加以改变建立了更加实用、更加全面的模型二。
2.2 重要条件和现实因素的理解：
1) 用户满意： 各工厂运输到某厂的产品量之和要不低于某厂的最低需求标准； 2) 新方案总运费不超过原方案的10％： 新方案的总运费超出原方案总运费的
部分不能大于原方案总运费的10%；
3) 因道路限制，从工厂2到用户4的路线应尽量避免分配运输任务： 运输任
务分配方案中最好不要有工厂2到用户4运输任务；
4) 用户1和用户3的满足率应尽量保持平衡：运输到用户1和用户3的产品总
量之比与他们的需求量之比趋近相等；
5) 单位产品：隐含分配的运输任务要符合实际条件，即运输量应为整数。 6) 对满足最大需求量的理解：因为此问题属于供需问题，所以运输到某用户的
产品量之和不能大于其需求量。
符号说明
模型的建立与求解
2.3 模型的假设和建立：
假设：
1、生产环节没有问题，能够供应足够的产品； 2、运输车辆的载重能够支持所分配的运输任务；
3、用户对产品的需求是不变的，每次运到的货物都能被全部接收；
4、除i厂到j用户的运输道路外，其它的都无限制，能够保证车辆按方案执行所分配到的运输任务；
5、运输产品量都是整数；
通过对已知数据的一般化改动（用字母代表常量），然后根据对各个数值间的相互联系的分析理解建立了一个关于三个工厂总运费最小值的线性函数模型如下：
minzc11x11c12x12c1jx1jc21x21c22x22c2jx2jci1xi1ci2xi2cijxij
xi1xi2xijsi xxxq 1j2jijj x1jx2jxijqjmj%xijo
2.4 带入已知数值求解运费最小值：
将表1中的相关的数据带入模型一得到方程如下：
minz5x112x126x137x143x215x224x236x244x315x322x333x34
关于不等式中x31>=100,是为了满足条件2，供应用户1的产品中，工厂3的产品不少于100单位；x24=0，是为了满足条件5，因道路限制，从工厂2到用户4的路线不安排分配运输任务，等式中*80%是为了满足每一个用户都可以有80%的需求量满足，此处没有考虑满足用户4的全部需求，x14+x24+x34=250，是为了满足首要要求，用户4的需求量要全部满足。
用LINGO软件求解（在LINGO中的运算过程详见附录①），并将所求得的非整解整数化，得：
x1135.0881435;x1280.0000;x1382.2811782;x1452.6309053; x2124.9120725;x220.0000;x23175.0879175;x240.0000; x31100.0000;x320.0000;x33102.6309103;x34197.3691197;
将所得整数解带入目标函数中求得：
minz3170
运输任务分配方案确定如下表：
结果分析
在求解运输任务分配方案过程中，在考虑七项目标约束条件的基础上，力求对最后的总运费进行最小值的最优化求解。运输总费用=各工厂运往用户1的费用和+各工厂运往用户2的费用和+各工厂运往用户3的费用和+各工厂运往用户4的费用和。经过计算后选择最优调配方案。然后根据从工厂到用户的单位产品的运输费用，可得出总费用=3170元。题中所给运输方案的总运费为2950，这个结果超出原方案的费用没有超过原总费用的10%，所以题中的关于新方案总运费金额的限定范围的要求也得到满足。所以，我认为所求的新方案可以认为是最优方案。
3、数学模型（采用目标规划的方法对问题进行求解）
（1）运输问题的线形规划模型为：
Min Z=5x11 +2 x12+6 x13+7 x14+3 x21+5 x22+4 x23 +6 x24+4 x31+5 x32 +2 x33 +3 x34 st x11 +x12 +x13 +x14 ≤300 x21 +x22 +x23 +x24 ≤200 x31 +x32 +x33 +x34 ≤400 x11 +x21 +x31 ≤200 x12 +x22 +x32 ≤100 x13 +x23 +x33 ≤450 x14 +x24 +x34 ≤250 则该目标规划的模型为 :
Min z= P1 (d1- + d2- )+P2 (d3- +d4- +d5- +d6- )+P3（d7+）+P4 (d8+ +d8- +d9+ +d9- ) S.t . x14 +x24 +x34+d1--d1+ =250 x31 +d2- -d2+ =100 x11 +x21 +x31 +d3- -d3+ =160 x12 +x22 +x32 +d4- -d4+ =80 x13 +x23 +x33 +d5- -d5+=360 x14 +x24 +x34 +d6- -d6+=200
5x11 +2x12 +6x13 +7x14 +3x21 +5x22 +4x23 +6x24 +4x31 +5x32 +2x33 +3x34 +d7--d7+≤
3245
x24 +d8- -d8+=0
x11 +x21 +x31 -x13 -x23 -x33 +d9- -d9+=0 c. P3级目标必须实现，方案如何？
p3级目标必须实现，将p3级约束条件改为绝对约束
5x11 +2x12 +6x13 +7x14 +3x21 +5x22 +4x23 +6x24 +4x31 +5x32 +2x33 +3x34≤3245 目标规划模型变为：
Min Z= P1 (d1- + d2- ) +P2 (d3- +d4- +d5- +d6- )+P4 (d7+ +d7- +d8+ +d8- )
st 5x11 +2x12 +6x13 +7x14 +3x21 +5x22 +4x23 +6x24 +4x31 +5x32 +2x33 +3x34≤3245 x14 +x24 +x34+(d1-)-(d1+)=250 x31+(d2-)-(d2+) =100
x11 +x21 +x31+(d3-)-(d3+)=160 x12 +x22 +x32+(d4-)-(d4+)=80 x13 +x23 +x33+(d5-)-(d5+)=360 x14 +x24 +x34+(d6-)-(d6+)=200 x24+(d7-)-(d7+)=0
9x11 +9x21 +9x31 -4x13 -4x23 -4x33+(d8-)-(d8+)=0 (1) p3目标中的10%,在10%-15%中变化,则
5x11 +2x12 +6x13 +7x14 +3x21 +5x22 +4x23 +6x24 +4x31 +5x32 +2x33 +3x34>=3245 5x11 +2x12 +6x13 +7x14 +3x21 +5x22 +4x23 +6x24 +4x31 +5x32 +2x33 +3x34
Min Z'= P1 (d1- + d2- )+P2 (d3- +d4- +d5- +d6- )+P4 (d7+ +d7- +d8+ +d8- )
st 5x11 +2x12 +6x13 +7x14 +3x21 +5x22 +4x23 +6x24 +4x31 +5x32 +2x33 +3x34>=3245 5x11 +2x12 +6x13 +7x14 +3x21 +5x22 +4x23 +6x24 +4x31 +5x32 +2x33 +3x34
x11 +x21 +x31+(d3-)-(d3+)=160 x12 +x22 +x32+(d4-)-(d4+)=80 x13 +x23 +x33+(d5-)-(d5+)=360 x14 +x24 +x34+(d6-)-(d6+)=200 x24+(d7-)-(d7+)=0
9x11 +9x21 +9x31 -4x13 -4x23 -4x33+(d8-)-(d8+)=0 (2)p3级目标放弃，减少一个约束条件 目标规划模型变为：
Min Z'= P1 (d1- + d2- )+P2 (d3- +d4- +d5- +d6- )+P4 (d7+ +d7- +d8+ +d8- ) st x14 +x24 +x34+(d1-)-(d1+)=250 x31+(d2-)-(d2+) =100
x11 +x21 +x31+(d3-)-(d3+)=160 x12 +x22 +x32+(d4-)-(d4+)=80 x13 +x23 +x33+(d5-)-(d5+)=360 x14 +x24 +x34+(d6-)-(d6+)=200 x24+(d7-)-(d7+)=0
9x11 +9x21 +9x31 -4x13 -4x23 -4x33+ (d8-)-(d8+)=0
4 ．程序
#include #include #include
float matrix[100][100],x[100]; int a[100]; int m,n,s,type;
int indexe,indexl,indexg; int i, j,in,out,temp; #define M 10000
void Input(float b[],int code[]) {
cout
cout
for(i=1;i
cout
for(j=1;j>matrix[i][j];
cout
cout
cin>>b[i]; //分别输入到b[i] 和 code[i] 中 }
cout
cin>>type;
if(type!=0&&type!=1) cout
cout
if(type==0) //如果是求极大，把它转化为极小来做，系数全部反号 for(i=1;i
matrix[n+1][i]=-matrix[n+1][i];
}
void Merge(float nget[][100],float nlet[][100],float net[][100],float b[])//合并 {
//置成我们需要的矩阵，最后一列置成0
// 1 2 1 0 0 0 // 4 0 0 1 0 0 // 0 4 0 0 1 0 //-2 -3 0 0 0 0
int i,j; for(i=1;i
for(j=m+1;j
if(nget[i][j-m-1]!=-1)matrix[i][j]=0; else matrix[i][j]=-1;
for(j=m+indexe+1;j
for(j=m+indexe+indexl+1;j
if(net[i][j-m-indexe-indexl-1]!=1)matrix[i][j]=0; else matrix[i][j]=1; }
for(i=m+1;i
for(i=m+indexe+indexl+1;i
matrix[n+1][i]=-M ; //置成M
for(i=1;i
void ProcessA()//初始a[] a[]是标记基变量，若为基变量则为0，若为非基变量则为1 { int i;
for(i=1;i
for(i=m+indexe+1;i
void InitPrint() { int i;
//printf(
void Xartificial()//消去人工变量 {
int i,j,k;
if(indexg!=0) {
for(i=m+indexe+indexl+1;i
for(j=1;j
for(k=1;k
matrix[n+1][k]=matrix[n+1][k]+matrix[j][k]*M; j=n; } } } }
void Start(float b[],int code[]) { int i;
float nget[100][100],nlet[100][100],net[100][100];
indexe=indexl=indexg=0; //indexl 表示松弛变量数量数， indexe表示减去的松弛变量数
indexg 表示人工变
for(i=1;i
{
if(code[i]==0) //如果是
{
nlet[i][indexl++]=1; //松弛变量数+1 且置成相应的标记
//Process(nlet,i,indexl-1);//传 net, 行号，indexl-1 过去
}
if(code[i]==1)
{
net[i][indexg++]=1; //人工变量数+1且置成相应的标记
//Process(net,i,indexg-1); //将刚加入的列单位化
}
if(code[i]==2)
{
net[i][indexg++]=1; //人工变量数+1 且置成相应的标记
nget[i][indexe++]=-1; //剩余变量数+1 且置成相应的标记
//Process(net,i,indexg-1);Process(nlet,i,indexe-1);
}
}
s=indexe+indexl+indexg+m; //变量总个数
Merge(nget,nlet,net,b);
ProcessA();
InitPrint();
Xartificial();
}
void Print()
{
int i,j,k,temp=1;
for(i=1;i
{
for(k=temp;k
if(a[k]==1)
{
//printf(
temp=k+1;
k=s;
}
for(j=1;j
printf(
printf(
printf(
for(j=1;j
printf(
printf(
}
void jckxj()//基础可行解
{
int i,j; //基础可行解即为 非基变量对应的x[i]=b[i], 基变量对应
的解为0
for(i=1;i
for(j=1;j
if(matrix[i][j]==1&&a[j]==1)
{
x[j]=matrix[i][s+1];
j=s;
}
for(i=1;i
if(a[i]==0)
x[i]=0;
}
void Result()
{
if(type==1)
printf(
else printf(
}
int rj()//基解矩阵
{
int i;
for(i=1;i
if(matrix[n+1][i]>0)
return 0;
return 1;
int max()//求最大的
{
int i,temp=1;
float max=matrix[n+1][1];
for(i=1;i
if(max
{
max=matrix[n+1][i];
temp=i;
}
return temp;
}
void JustArtificial()//人工变量
{
int i;
for(i=m+indexe+indexl+1;i
if(fabs(x[i])>=0.000001)
{
cout
return;
}
}
void PrintResult()
{
if(type==0)
printf(
else
printf(
}
int Check(int in)//检验
{
int i;
float maxl=-1;
for(i=1;i
if(fabs(matrix[i][in])>0 && maxl
maxl=matrix[i][s+1]/matrix[i][in];
if(maxl
return 1;
return 0;
}
int SearchOut(int *temp,int in)//出基变量
{
int i;
float min=10000;
for(i=1;i
if(fabs(matrix[i][in])>=0.000001&&(matrix[i][s+1]/matrix[i][in]>=0)
&&min>matrix[i][s+1]/matrix[i][in])
{
min=matrix[i][s+1]/matrix[i][in];
*temp=i;
}
return i;
}
void Mto(int in,int temp)
{
int i;
for(i=1;i
if(i!=in)
matrix[temp][i]=matrix[temp][i]/matrix[temp][in];
matrix[temp][in]=1;
}
void Be(int temp,int in)//初等变换
{
int i,j;
float c;
for(i=1;i
{
c=matrix[i][in]/matrix[temp][in];
if(i!=temp)
for(j=1;j
matrix[i][j]=matrix[i][j]-matrix[temp][j]*c;
}
}
void Achange(int in,int out)//出基入基转换
{
int temp=a[in];
a[in]=a[out];
a[out]=temp;
}
void Simplix()
{
while(1)
{
jckxj();
Print();
Result();
if(!rj())
in=max();
else
{
if(indexg!=0)
JustArtificial();
PrintResult();
return;
}
if(Check(in))
{
cout
return;
}
out=SearchOut(&temp,in);
Mto(in,temp);
Be(temp,in);
Achange(in,out);
}
void printB()
{
cout
cout
for(i=1;i
{
for(j=1+indexe+m;j
printf(
printf(
}
}
void rankb()
{
float b1[100][100] ,maxb,minb;
int t=1;
for (i=1;i
{
{
for (j=m+indexe+1;j
if (matrix[i][j]!=0)
b1[i][t]=-matrix[i][s+1]/matrix[i][j];
cout
t=t+1;
}
{ maxb=b1[i][1];
for (t=1;t
if ( b1[i][t]
if (maxb
maxb=b1[i][t];
}
{ minb=b1[i][1];
for (t=1;t
if ( b1[i][t]>0)
if (minb>b1[i][t])
minb=b1[i][t];
}
maxb;
minb;
cout
}
}
void rankc()
{
float c[100];
for (i=1;i
if (a[i]!=1)
c[i]=matrix[n+1][m+indexe+i];
cout
}
int main()
{
int code[100];//输入符号标记
float b[100];
Input(b,code);//初始化
Start(b,code);//标准化行
Simplix();
printB();
rankb();
rankc();
}
5、程序使用说明
输出的为取整后的数字，改程序开始界面会提示你输入相关的参数，操作简单、易懂。
6、题目运行结果及讨论分析
本体结果为 3170，与开始时得出的结果是一致的，前面已经验证过，改结果是最优的，所
以本问题的最终结果是3170，这是满足所有条件后的最小的运费。
7、主要参考资料
1. 胡觉亮 等《运筹学原理与应用》 浙江人民出版社2004年
2. 邓成梁《 运筹学的原理和方法 》 华中理工大学出版社 1997年
3. 钱颂迪 主编《 运 筹 学 》 清华大学出版社 1990年
4．汪遐昌《运筹学方法及其微机实现》 电子科技大学出版社 1996年
5．姚恩瑜 何勇 陈仕平《 数学规划与组合优化 》 浙江大学出版社 2001年