大虎说事

王大虎:例6 (套裁下料问题)

王大虎

某工厂要做100套钢架,每套钢架需要长度分别为2.9m,2.1m和1.5m的圆钢各一根.已知原料每根长7.4m;问应如何下料,可使所用原料最省?

解 最简单的做法是:在每根原料上截取2.9m、2.1m和1.5m的圆钢各一根组成一套钢架,每根原材料剩余料头0.9m.如此做100套钢架,需要原材料100根,X生90m的料头——这当然是一个不小的浪费.为了找到一个省料的套裁方案,必须先设计出较好的几个下料方案.所谓较好,即首先要求每个方案下料后的料头较短;其次要求这些方案的总体能裁下所有规格的圆钢,并且不同方案有着不同的各种所需圆钢的比例.这样的套裁才能满足对各种不同规格圆钢的需要并达到省料的目的.为此我们设计出5种下料方案以供套裁用,如表1-6.

表1-6

 

为了用最少的原材料得到100套钢架,需要混合使用表1-6中的几种下料方案,设按照方案Ⅰ,Ⅱ,Ⅲ,Ⅳ,Ⅴ下料的原材料根数分别为x1,x2,x3,x4,x5,则可列出下面的数学模型

minz=x1+x2+x3+x4+x5

 

王大虎

例7 (运输模型)某公司从两个产地A1,A2将物品运往三个销地B1,B2,B3,各产地的产量、各销地的销量以及各产地运往销地的每件物品的运费如表1-7.

表1-7

 

应如何调运,能够使总运费最小?

解 由于A1,A2两个产地的总产量为200+300=500(件);B1,B2,B3三个销地的总销量为150+150+200=500(件),总产量等于总销量,这是一个产销平衡的运输问题.把A1,A2的产量全部分配给B1,B2,B3,正好满足这三个销地的需要.

设xij表示从产地Ai调运到Bj的运输量(i=1,2;j=1,2,3),例如,x12表示从A1调运到B2的物品数量.现将安排的运输量列入表1-8.

表1-8

 

从表1-8可写出此问题的数学模型.

满足产地产量的约束条件为

x11+x12+x13=200,

x21+x22+x23=300

满足销地销量的约束条件为

x11+x21=150

x12+x22=150

x13+x23=200,

王大虎

要使运输费最小,即

minf=6×11+4×12+6×13+6×21+5×22+5×23,

所以此运输问题的线性规划模型是

minf=6×11+4×12+6×13+6×21+5×22+5×23

 

例8 (指派问题)某商业公司计划开办五家新商店B1,B2,B3,B4,B5.为了尽早建成营业,商业公司通知了五个建筑公司A1,A2,A3,A4,A5,以便让每家新商店由一个建筑公司来承建.建筑公司Ai对新商店Bj建造费用的投标为cij,数据见表1-9.商业公司应对五家建筑公司怎样分配建造任务,才能使总建造费用最少?试建立此问题的数学模型.

表1-9

 

解 这是一个标准的任务指派问题,引入0—1变量

 

则此问题的数学模型为

minz=4×11+8×12+…+10×54+6×55

 

2.线性规划问题的数学模型

通过上述内容可以看出,线性规划模型的三个要素缺一不可.决策变量,目标函数,约束条件一起构成了完整的线性规划模型.我们总结如下:

线性规划问题的数学模型的一般形式

求一组变量xj(j=1,2,…,n)的值,使其满足

 

并使目标函数的值最大或者最小.

下面给出三个实例线性规划问题的一般模型.

例9 (生产计划问题)设用A1,A2,…,Am种原料,可以生产B1,B2,…,Bn种产品.现有原料数、每单位产品所需原料数,及每单位产品可得利润数如表1-10.

表1-10

王大虎
王大虎

王大虎

问如何组织生产计划才能使得利润最大?

解 设xj为生产产品Bj(j=1,2,…,n)的计划数.这一个问题的数学模型为

求一组变量xj(j=1,2,…,n)的值,使它满足

 

并且使目标函数的值最大.

例10 (套裁下料问题)设用某原材料(条材或板材)下零件A1,A2,…,Am的毛坯.根据过去经验在一件原材料有B1,B2,…,Bn种不同的下料方式,每种下料方式可得毛坯个数及每种零件需要量如表1-11.问如何安排下料方式,使得既能满足需要,用的原材料又最少.

表1-11

 

解 设用Bj种方式下料的原材料数为xj,则这一问题的数学模型为

求一组变量xj(j=1,2,…,n)的值,使它满足

 

并且使目标函数的值最小(使用原材料数最少).

例11 (指派问题)拟分配n人去干n项工作,每人干且仅干一项工作,若分配第i人去干第j项工作,需花费cij单位时间,问应如何分配工作才能使工人花费的总时间最少?

容易看出,要给出一个指派问题的实例,只需给出矩阵C=(cij),C被称为指派问题的系数矩阵.

引入变量xij,若分配i干j工作,则取xij=1,否则取xij=0.上述指派问题的数学模型为

 

值得注意的是,线性规划问题所隐含的假定:

比例性假定:决策变量变化引起的目标函数改变量和决策变量改变量成比例.同样,每个决策变量的变化引起约束方程左端值的改变量和该变量的改变量成比例.

可加性假定:每个决策变量对目标函数和约束方程的影响是独立于其他变量的,目标函数值是每个决策变量对目标函数贡献的总和.

连续性假定:线性规划问题中的决策变量应能够连续取值.

王大虎

确定性假定:线性规划问题中的所有参数都是确定的参数.线性规划问题不包含随机因素.

【练习1】

根据以下实际问题建立线性规划模型

1.某厂计划生产Ⅰ,Ⅱ两种产品,已知生产单位重量的产品所需的设备为A及B、C两种原料,生产设备和原料消耗表如表1-12

表1-12

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注