在本章第一节和第二节的例题中研究的对象都是连续可分的,即决策变量是连续的,建立的模型是线性规划.然而,实际生活中还会遇到不同的情况,如下述所示.
一、汽车厂生产计划
一汽车厂生产小、中、大三种类型的汽车,已知各类型每辆车对钢材、劳动时间的需求、利润以及每月工厂钢材、劳动时间的现有量(见表5.3.1).试制订月生产计划,以使工厂的利润最大.
进一步讨论:由于各种条件限制,如果生产某一类型汽车,则至少要生产80辆,那么最优的生产计划应做何改变?
表5.3.1 汽车厂的生产数据
【模型建立与求解】
设每月生产小、中、大型汽车的数量分别为x1,x2,x3,工厂的月利润为z,在题目所给参数均不随生产数量变化的假设下,立即可得线性规划模型:
其中N为非负整数集(自然数集).这样的数学规划称为整数规划(Integer Programming,简记为IP).IP可以用LINGO直接求解,输入文件:
注:最后一行中的“@gin”是将变量限定为整数的函数.求解得到输出(只列出需要的结果):
IP的最优解x1=64,x2=168,x3=0,最优值z=632,即问题要求的月生产计划为生产小型车64辆、中型车168辆,不生产大型车.
讨论:对于问题中提出的“如果生产某一类型汽车,则至少要生产80辆”的限制,上面得到的IP的最优解不满足这个条件.这种类型的要求是实际生产中经常提出的.下面以本问题为例说明解决这类要求的办法.
对于原LP模型(5.3.1)~(5.3.4),需增加约束
下面是求解模型(5.3.1)~(5.3.5)的三种方法:
解法1 分解为多个LP子模型.
(5.3.5)式可分解为八种情况:
这里可以应用剪枝法,(8)显然不可能是问题的解.可以检查,(3)和(7)不满足约束条件(5.3.2),也不可能是问题的解.对其他五个LP子模型逐一求解,比较目标函数值,可知最优解在(5)情形得到:x1=80,x2=150,x3=0,最优值z=610.
注:可以不检查是否满足约束条件,解所有LP子模型,结果同上.
解法2 引入0-1变量
设y1只取0,1两个值,则“x1=0或≥80”等价于:
其中M为相当大的正数,本例可取1000(x1不可能超过1000).类似地有:
于是(5.3.1)~(5.3.4),(1′)~(3′)构成一个特殊的整数规划模型(既有一般整数变量,又有0-1变量),用LINGO直接求解时,输入的最后要加上0-1变量的限定语句:
@bin(y1);@bin(y2);@bin(y3);求解可得到与第一种方法同样的结果.
解法3 化为非线性规划.
条件(5.3.4),(5.3.5)可表示为:
式子左端是决策变量的非线性函数,(5.3.1)~(5.3.3),(1″)~(3″)构成非线性规划(Non-Linear Programming,简记作NP).该模型可如下输入LINGO:
求解可得到与第二种方法同样的结果.
评注:像汽车这样的对象自然是整数变量,应该建立整数规划模型,但是求整数规划比线性规划要难得多(即使使用数学软件),所以当整数变量取值很大时,常作为连续变量用线性规划处理.
一般来说,非线性规划的求解比线性规划困难得多,特别是问题规模较大或者要求得到全局最优解时更是如此.为了考虑(5.3.5)式这样的条件,通常是引入0-1变量,而一般尽量不用非线性规划.
二、原油采购与加工
某公司用两种原油(A和B)混合加工成两种汽油(甲和乙).甲、乙两种汽油含原油A的最低比例分别为50%和60%,售价分别为4800元/t和5600元/t.该公司现有原油A和B的库存量分别为500 t和1000 t,还可以从市场上买到不超过1500 t的原油A.原油A的市场价为:购买量不超过500 t时的单价为10000元/t;购买量超过500 t但不超过1000 t时,超过500t的部分8000元/t;购买量超过1000t时,超过1000t的部分6000元/t.该公司应如何安排原油的采购和加工[7]?
【问题分析】
安排原油采购、加工的目标只能是利润最大,题目中给出的是两种汽油的售价和原油A的采购价,利润为销售汽油的收入与购买原油A的支出之差.这里的难点在于原油A的采购价与购买量的关系比较复杂,是分段函数关系,能否及如何用线性规划、整数规划模型加以处理是关键所在.
【模型建立】
设原油A的购买量为x,根据题目所给数据,采购的支出c(x)可表为如下的分段线性函数(以下价格以千元/t为单位):
设原油A用于生产甲、乙两种汽油的数量分别为x11和x12,原油B用于生产甲、乙两种汽油的数量分别为x21和x22,则总的收入为4.8(x11+x21)+5.6(x12+x22).于是本例的目标函数——利润为
约束条件包括加工两种汽油用的原油A、原油B库存量的限制,和原油A购买量的限制,以及两种汽油含原油A的比例限制,分别表示为:(www.xing528.com)
由于(5.3.6)式中的c(x)不是线性函数,(5.3.6)~(5.3.13)给出的是一个非线性规划,而且,对于这样用分段函数定义的c(x),一般的非线性规划软件也难以输入和求解,那么能不能想办法将该模型化简,从而用现成的软件求解呢?
【模型求解】
下面介绍三种解法.
解法1 一个自然的想法是将原油A的采购量x分解为三个量,即用x1,x2,x3分别表示以价格10千元/t、8千元/t、6千元/t采购的原油A的数量,总支出为c(x)=10x1+8x2+6x3,且
这时目标函数(5.3.7)变为线性函数:
应该注意到,只有当以10千元/t的价格购买x1=500t时,才能以8千元/t的价格购买x2(x2>0),这个条件可以表示为
同理,只有当以8千元/t的价格购买x2=500t时,才能以6千元/t的价格购买x3(x3>0),于是
此外,x1,x2,x3的取值范围是
由于有非线性约束(5.3.16)和(5.3.17),(5.3.8)~(5.3.18)构成非线性规划模型.将该模型输入LINGO软件如下:
注:因为(5.3.14)式和(5.3.18)式保证了(5.3.10)式,所以上面输入中不需要(5.3.10)式.将文件存储并命名后,选择菜单“LINGO|Solve”,运行该程序得到:
最优解是用库存的500 t原油A、500 t原油B生产1000 t汽油甲,不购买新的原油A,利润为4800000元.
但是LINGO得到的结果只是一个局部最优解(local optimal solution),还能得到更好的解吗?除线性规划外,LINGO在缺省设置下一般只给出局部最优解,但可以通过修改LINGO选项要求计算全局最优解.具体做法是:选择“LINGO|Options”菜单,在弹出的选项卡中选择“General Solver”,然后找到选项“Use Global Solver”将其选中,并应用或保存设置.重新运行“LINGO|Solve”,可得到如下输出:
全局最优解是购买1000 t原油A,与库存的500 t原油A和1000 t原油B一起,共生产2500 t汽油乙,利润为5000000元,高于局部最优解对应的利润.
解法2 引入0-1变量将(5.3.16)和(5.3.17)转化为线性约束.
令y1=1,y2=1,y3=1,分别表示以10千元/t、8千元/t、6千元/t的价格采购原油A,则约束(5.3.16)和(5.3.17)可以替换为:
(5.3.8)~(5.3.15),(5.3.18)~(5.3.22)构成整数(线性)规划模型,将它输入LINGO软件如下:
运行该程序得到的最优解与第一种解法得到的结果(全局最优解)相同.
解法3 直接处理分段线性函数c(x).(5.3.6)式表示的c(x)如图5.3.1所示.
图5.3.1 分段线性函数c(x)图形
记x轴上的分点为b1=0,b2=500,b3=1000,b4=1500.当x在第一个小区间[b1,b2]时,记
x=z1b1+z2b2,z1+z2=1,z1,z2≥0,
因为c(x)在[b1,b2]是线性的,所以c(x)=z1c(b1)+z2c(b2).同样,当x在第二个小区间[b2,b3]时,
x=z2b2+z3b3,z2+z3=1,z2,z3≥0,c(x)=z2c(b2)+z3c(b3).
当x在第三个小区间[b3,b4]时,
x=z3b3+z4b4,z3+z4=1,z3,z4≥0,c(x)=z3c(b3)+z4c(b4).
为了表示x在哪个小区间,引入0-1变量yk(k=1,2,3),当x在第k个小区间时,yk=1,否则,yk=0.这样,z1,z2,z3,z4,y1,y2,y3应满足:
此时x和c(x)可以统一地表示为
(5.3.7)~(5.3.13),(5.3.23)~(5.3.27)也构成一个整数规划模型,将它输入LINGO软件求解,得到的结果与第二种解法相同.
评注:这个问题的关键是处理分段线性函数,我们推荐化为整数规划模型的第二、第三种解法,第三种解法更具一般性,其做法如下:
设一个n段线性函数f(x)的分点为b1≤…≤bn≤bn+1,引入zk,将x和f(x)表示为:
zk和0-1变量yk满足:
免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。