规划建模培训2.docx

规划建模培训2.docx

《规划建模培训2.docx》由会员分享，可在线阅读，更多相关《规划建模培训2.docx（17页珍藏版）》请在冰点文库上搜索。

规划建模培训2

线性规划——整数规划

一．概念

如果一个数学规划的某些决策变量或全部决策变量要求必须取整数，则这样的问题称为整数规划问题，其模型称为整数规划模型。

如果一个整数规划的目标函数和约束都是线性的，则称此问题为整数线性规划问题，其一般形式为

二．求解举例

例1

其LINGO语句如下：

略

三．线性整数规划（IP）实例求解IP用的是分支定界法

例1某部门一周中每天需要不同数目的雇员：

周一到周四每天至少需要50人，周五至少需要80人，周六周日每天至少需要90人，现规定应聘者需连续工作5天，试确定聘用方案，即周一到周日每天聘用多少人，使在满足需要的条件下聘用总人数最少。

优化模型

X1+x4+x5+x6+x7>=50

xi都是整数

“BestIP：

94”表示当前得到的最好的整数解的目标函数值为94（人）.

“IPBound:

93.5”表示该整数规划目标值的下界为93.5（人）.

“Branches:

1”表示分支数为1（即在第1个分支中就找到了最优解）.我们前面说过，LINDO求解IP用的是分支定界法.

显然，上面第二条“整数规划目标值的下界为93.5（人）”表明至少要聘用93.5名员工，由于人数只能是整数，所以至少要聘用94（人）.而第一条说明目前得到的解就是聘用94（人），所以已经是最优的了.报告窗口中前两行告诉我们，在8次迭代后找到对应的线性规划（LP）问题的最优解，最优值等于93.3333359.LINDO求解IP用的是分支定界法，紧接着几行显示的是分支定界的信息，在第1个分支中设定X2>=4,并在该分支中找到了整数解，而且就是全局整数最优解，所以算法停止.旋转迭代（PIVOTS）共18次.后面显示的是最后的最优解X=（0，4，40，2，34，10，4）.松弛和剩余变量（SLACKORSUPLUS）仍然可以表示约束的松紧程度，但目前IP尚无相应完善的敏感性分析理论，因此REDUCEDCOST和DUALPRICES的结果在整数规划中的意义不大.

备注：

尽管LINDO对整数规划问题很有威力，但要想有效地使用，有时还是需要一定的技巧的。

这是因为，人们很容易将一个本质上很简单的问题列成一个不太好的输入模型，从而有可能导致一个冗长的分支定界计算。

遗憾的是，我们往往难以预先估计什么样的模型才能避免冗长的分支定界计算，也难以判别什么样的模型是“不太好”的输入模型。

当然这时LINDO会主动砍去一些计算过程，以缩短计算时间，而且越是高版本的LINDO软件，这种自动处理的“智能”越强.我们的建议是：

如果分支定界计算时间很长仍得不到最优解，你可以试试对输入模型进行一些等价交换：

如交换变量的次序，交换约束的顺序等。

有时也许会对减少求解的所需的时间有所帮助.

整数规划在lingo中的求解：

以例1为例，输入模型见图4-3，注意以下几点：

1）语句的顺序不重要；

2）限定变量取整数的语句“@GIN（X1）”和“@GIN（X2）”；

3）在lingo中，以“@”开头的都是函数调用，lingo中的函数一律需要以“@”开头。

如约束中@gin（x1）表示x1为整数，用@bin（x1）表示x1为0-1整数。

例2：

钢管下料问题

某钢管零售商从钢管厂进货，将钢管按照顾客要求的长度进行切割，称为下料。

假定进货时得到的原料钢管长度都是19m。

1）现有一客户需要50根长4m、20根长6m和15根长8m的钢管。

应如何下料最节省？

2）零售商如果采用的不同切割模式太多，将会导致生产过程的复杂化，从而增加生产和管理成本。

所以该零售商规定采用的不同切割模式不能超过3种。

此外。

该客户除需要1）中的3种钢管外，还要10根长5m的钢管。

应如何下料最节省？

问题分析：

对于下料问题首先要确定采用哪些切割模式。

所谓切割模式，是指按照顾客要求的长度在原料钢管上安排切割的一种组合。

例如，我们可以将19m的钢管切割成3根长4m的钢管，余料为7m；或者将长19m的钢管切割成长4m、6m和8m的钢管各1根，余料为1m。

显然，可行的切割模式是很多的。

其次，应当明确哪些切割模式是合理的。

合理的切割模式通常还假设余料不应大于或等于客户需要钢管的最小尺寸。

例如，可以将长19m的钢管切割成3根4m的钢管是可行的，但余料为7m，可进一步将7m的余料切割成4m钢管（余料为3m），或者将7m的余料切割成6m钢管（余料为1m）。

经过简单的计算可知，问题1）的合理切割模式一共有7种，如表1所示：

于是问题转化为在满足客户需要的条件下，按照哪几种合理的模式，每种模式切割多少根原料钢管最为节省。

而所谓节省，可以有两种标准，一是切割后剩余的总余料量最小，二是切割原料钢管的总根数最少。

下面将对这两个目标分别讨论。

问题1）用xi表示按照表1第i种模式（i=1,2,…,7）切割的原料钢管的根数，若以切割后剩余的总余料量最小为目标，则按照表1最后一列可得

minZ1=3x1+x2+3x3+3x4+x5+x6+3x7

若以切割原料钢管的总根数最少为目标，则有

表1钢管下料问题1）的合理切割模式

模式

4m钢管根数

6m钢管根数

8m钢管根数

余料/m

1

4

0

0

3

2

3

1

0

1

3

2

0

1

3

4

1

2

0

3

5

1

1

1

1

6

0

3

0

1

7

0

0

2

2

MinZ2=x1+x2+x3+x4+x5+x6+x7

约束条件为客户的需求，按照表1应有

4x1+3x2+2x3+x4+x5≥50

x2+2x4+x5+3x6≥20

x3+x5+2x7≥15

最后，切割的原料钢管的根数xi显然应当是非负整数（用Z表示整数集合，Z+表示非负整数集合）：

xi∈Z+，i=1,2,…,7

于是，问题1）归结为在约束条件下，使目标达到最小。

显然这是线性整数规划模型。

钢管下料问题1）的求解

以切割后剩余的总余料量最小为目标，建立LINGO模型：

min=3*x1+x2+3*x3+3*x4+x5+x6+3*x7;

4*x1+3*x2+2*x3+x4+x5>=50;

x2+2*x4+x5+3*x6>=20;

x3+x5+2*x7>=15;

@gin（x1）;

@gin（x2）;

@gin（x3）;

求解可以得到最优解如下：

OBJECTIVEFUNCTIONVALUE

1）27.00000

VARIABLEVALUEREDUCEDCOST

X10.0000003.000000

X212.0000001.000000

X30.0000003.000000

X40.0000003.000000

X515.0000001.000000

X60.0000001.000000

X70.0000003.000000

即按照模式2切割12根原料钢管，按照模式5切割15根原料钢管，共27根，总余料量27m。

显然，在总余料量最小的目标下，最优解将是使用余料尽可能小的切割模式（模式2和模式5的余料为1m），这会导致切割原料钢管的总根数较多。

以切割原料钢管的总根数最少为目标，建立LINGO模型：

min=x1+x2+x3+x4+x5+x6+x7;

4*x1+3*x2+2*x3+x4+x5>=50;

x2+2*x4+x5+3*x6>=20;

x3+x5+2*x7>=15;

@gin（x1）;

@gin（x2）;

@gin（x3）;

@gin（x4）;

@gin（x5）;

@gin（x6）;

@gin（x7）;

求解可以得到最优解如下：

OBJECTIVEFUNCTIONVALUE

1）25.00000

VARIABLEVALUEREDUCEDCOST

X10.0000001.000000

X215.0000001.000000

X30.0000001.000000

X40.0000001.000000

X55.0000001.000000

X60.0000001.000000

X75.0000001.000000

即按照模式2切割15根原料钢管，按照模式5切割5根原料钢管，按照模式7切割5根原料钢管，共25根，总余料量35m。

与上面得到的结果相比，总余料量增加了8m，但是所用的原料钢管的总根数减少了2根，在余料没有什么用途的情况下，通常选择总根数最少为目标。

问题2）如果按照问题1）的办法处理，首先要通过枚举法确定哪些切割模式是合理的，并从中选出不超过3种模式。

而由于需求的钢管规格增加到4种，所以枚举法的工作量较大。

下面介绍一种带有普遍性的方法，可以同时确定切割模式和切割数量。

同问题1）一样，只使用合理的切割模式，其余料不应大于3m（因为客户需要的钢管最小尺寸为4m，而本题中参数都是整数）。

由于不同切割模式不能超过3种，可以用用xi表示按照第i种模式（i=1,2,3）切割的原料钢管的根数。

又设使用第i种切割模式下每根原料钢管生产长4m、5m、6m和8m的钢管数量分别为r1i，r2i，r3i，r4i。

仅以使用的原料总根数最少为目标，即

minx1+x2+x3

满足客户需求的约束条件为

r11x1+r12x2+r13x3≥50

r21x1+r22x2+r23x3≥10

r31x1+r32x2+r33x3≥20

r41x1+r42x2+r43x3≥15

每一种切割模式必须可行、合理，所以每根原料钢管的成品量不能超过19m，也不能少于16m（余料不能大于3m），于是

16≤4r11+5r21+6r31+8r41≤19

16≤4r12+5r22+6r32+8r42≤19

16≤4r13+5r23+6r33+8r43≤19

最后，加上非负整数约束：

xi，rji∈Z+，i=1,2,3,j=1,2,3,4

于是，问题2）归结为在在约束条件下，求xi和r1i，r2i，r3i，r4i（i=1,2,3）使目标达到最小。

当然，这是一个整数非线性规划模型。

钢管下料问题2）模型的进一步优化：

非线性整数规划模型虽然用LINGO软件可以直接求解，但为了减少运行时间，可以增加一些显然的约束条件，从而缩小可行解的搜索范围。

例如，由于3种切割模式的排列顺序是无关要紧的，所以不妨增加以下约束：

x1≥x2≥x3

又如，注意到所需原料钢管的总根数有明显的上界和下界。

首先，原料钢管的根数不可能少于

（根）。

其次，考虑一种非常特殊的生产计划：

第一种切割模式下只生产4m钢管，一根原料钢管切割成4根4m钢管，为满足50根4m钢管的需求，需要13根原料钢管；第二种切割模式下只生产5m，6m钢管，一根原料钢管切割成1根5m钢管和2根6m钢管，为满足10根5m和20根6m钢管的需求，需要10根原料钢管；第三种切割模式下只生产8m钢管，一根原料钢管切割成2根8m钢管，为满足15根8m钢管的需求，需要8根原料钢管。

于是满足要求的这种生产计划共需要13+10+8=31根原料钢管，这就得到了最优解的一个上界，所以可增加以下约束：

26≤x1+x2+x3≤31

LINGO模型为：

min=x1+x2+x3;

r11*x1+r12*x2+r13*x3>=50;

r21*x1+r22*x2+r23*x3>=10;

r31*x1+r32*x2+r33*x3>=20;

r41*x1+r42*x2+r43*x3>=15;

4*r11+5*r21+6*r31+8*r41<=19;

4*r12+5*r22+6*r32+8*r42<=19;

4*r13+5*r23+6*r33+8*r43<=19;

4*r11+5*r21+6*r31+8*r41>=16;

4*r12+5*r22+6*r32+8*r42>=16;

4*r13+5*r23+6*r33+8*r43>=16;

x1+x2+x3>=26;

x1+x2+x3<=31;

x1>=x2;

x2>=x3;

@gin（x1）;@gin（x2）;@gin（x3）;

@gin（r11）;@gin（r12）;@gin（r13）;

@gin（r21）;@gin（r22）;@gin（r23）;

@gin（r31）;@gin（r32）;@gin（r33）;

@gin（r41）;@gin（r42）;@gin（r43）;

得到输出如下：

Localoptimalsolutionfoundatiteration:

12211

Objectivevalue:

28.00000

VariableValueReducedCost

X110.000000.000000

X210.000002.000000

X38.0000001.000000

r113.0000000.000000

r122.0000000.000000

r130.0000000.000000

r210.0000000.000000

r221.0000000.000000

r230.0000000.000000

r311.0000000.000000

r321.0000000.000000

r330.0000000.000000

r410.0000000.000000

r420.0000000.000000

r432.0000000.000000

即按照模式1，2，3分别切割10根，10根，8根原料钢管，使用原料钢管总根数为28根。

第一种切割模式下一根原料钢管切割成3根4m钢管和1根6m钢管；第二种切割模式下一根原料钢管切割成2根4m钢管，1根5m钢管和1根6m钢管；第三种切割模式下一根原料钢管切割成2根8m钢管。

例3、飞行计划问题

这个问题是以第二次世界大战中的一个实际问题为背景，经过简化而提出来的。

在甲、乙双方的一场战争中，一部分甲方部队被乙方部队包围长达4个月。

由于乙方封锁了所有水陆交通通道，被包围的甲方部队只能依靠空中交通维持供给。

运送4个月的供给分别需要2，3，3，4次飞行，每次飞行编队由50架飞机组成（每架飞机需要3名飞行员），可以运送10万t物质。

每架飞机每个月只能飞行一次，每名飞行员每个月也只能飞行一次。

在执行完运输任务后的返回途中有20%的飞机会被乙方部队击落，相应的飞行员也因此牺牲或失踪。

在第1个月开始时，甲方拥有110架飞机和330名熟练的飞行员。

在每个月开始时，甲方可以招聘新飞行员和购买新飞机。

新飞机必须经过一个月的检查后才可以投入使用，新飞行员必须在熟练飞行员的指导下经过一个月的训练才能投入飞行。

每名熟练飞行员可以作为教练每个月指导20名飞行员（包括他自己在内）进行训练。

每名飞行员在完成一个月的飞行任务后，必须有一个月的带薪假期，假期结束后才能再投入飞行。

已知各项费用（单位略去）如下表所示，请为甲方安排一个飞行计划。

第1个月

第2个月

第3个月

第4个月

新飞机价格

200．0

195．0

190．0

185．0

闲置的熟练飞行员报酬

7．0

6．9

6．8

6．7

教练和新飞行员报酬（包括培训费用）

10．0

9．9

9．8

9．7

执行飞行任务的熟练飞行员报酬

9．0

8．9

9．8

9．7

休假期间的熟练飞行员报酬

5．0

4．9

4．8

4．7

飞行计划的原始数据

如果每名熟练飞行员可以作为教练每个月指导不超过20名飞行员（包括他自己在内）进行训练，模型和结果有那些改变？

习题4-2

1.用机床A1、A2、A3加工零件B1和B2,零件数相等。

日产量（个/日）如下表，如何生产使总产量最多？

max=x11+x12+x21+x22+x31+x32;

x11<=30;x12<=20;x21<=15;x22<=40;x31<=18;x32<=50;

x11+x21+x31=x12+x22+x32;

@gin（x11）;@gin（x12）;@gin（x21）;@gin（x22）;@gin（x31）;@gin（x32）;Globaloptimalsolutionfound.

Objectivevalue:

126.0000

Extendedsolversteps:

0

Totalsolveriterations:

0

VariableValueReducedCost

X1130.00000-1.000000

X1220.00000-1.000000

X2115.00000-1.000000

X220.000000-1.000000

X3118.00000-1.000000

X3243.00000-1.000000

RowSlackorSurplusDualPrice

1126.00001.000000

20.0000000.000000

30.0000000.000000

40.0000000.000000

540.000000.000000

60.0000000.000000

77.0000000.000000

80.0000000.000000

2.一家24小时自助餐厅在24小时内需要的服务员人数如下表：

起止时间

2-6

6-10

10-14

14-18

18-22

22-2

最少人数

4

8

10

7

12

4

每个服务员每天连续工作8小时。

问：

（1）该餐厅最少需要招聘几个服务员？

（2）劳动法规定，每个工作人员每星期至少休息1天。

加上此限制，最少应该招聘几个服务员？

3.某军用与民用计算机硬件制造商目前正在生产民用器件E-1200、E-1500，每个纯利分别为$50、$40。

加工时间与日加工能力如下表：

车间

E-1200

E-1500

车间能力（每天小时数）

1

2

0

300

2

0

3

540

3

2

2

440

4

1．2

1．5

300

假设所有产品都能卖掉，制定最佳生产方案；

假设E-1200的纯利减少$10，制定最佳生产方案；

假设此公司获准生产军用产品Z-1800，其在四个车间的加工时间分别为0.1小时、3.6小时、2.2小时、1.2小时，每个纯利为$55，民用产品的纯利同

（1），制定最佳生产方案。

4.（总运力问题）某卡车公司拨款800万元用于购买新的运输工具，有3种运输工具可供选择：

A的载重量10吨，平均时速45千米，价格26万元；

B的载重量20吨，平均时速40千米，价格36万元；

C的载重量18吨，平均时速40千米，价格42万元。

其中，C是B的变种，新设了一个卧铺，所以载重降低了、价格上升了。

A需要1名司机，如果每天三班工作，每天可运行18小时.当地法律规定B和C均需要两名司机，如果三班工作，B每天可运行18小时，C可运行21小时.该公司目前每天有150名司机可用，短期内无法招募到其他训练有素的司机。

当地工会禁止司机每天工作超过一个班次。

此外，受维修保障能力的限制，公司最多能拥有30辆运输工具。

请你建立数学模型，确定A、B、C的数量使得公司的总运力最大。

5.（机票的销售策略）在四个城市A、B、C、H之间，有唯一一家航空公司提供三个航班，这三个航班的“出发地—目的地”分别为AH、HB、HC，可搭载旅客的最大数量分别为120人、100人、110人，机票的价格分头等舱和经济舱两类。

经过市场调查，公司销售部得到了每天旅客的相关信息，见下表。

该公司应该在每条航线上分别分配多少张头等舱和经济舱的机票？

出发地—目的地

头等舱需求/人

头等舱价格/人

经济舱需求/人

经济舱价格/人

AH

33

190

56

90

AB（经H转机）

24

244

43

193

AC（经H转机）

12

261

67

199

HB

44

140

69

80

HC

16

186

17

103

1、一汽车厂生产小.中.大三种类型的汽车，已知各类型每辆车对钢材.劳动时间的需求，利润以及每月工厂钢材.劳动时间的现有量如表2-3所示。

由于各种条件限制，如果生产某一类型汽车，则至少要生产80辆，试制定月生产计划，使工厂的利润最大。

5．两个汽车公司春运期间为三条线路增派汽车，甲公司可提供12辆，乙公司可提供20辆；A线路需9辆，B线路需15辆，C线路需8辆。

已知甲公司运营A、B、C三线的距离依次为10公里、5公里、6公里；乙公司运营A、B、C三线的距离依次为4公里、8公里、15公里。

若每辆每公里的运营费为常数a元，则甲公司供应给A、B、C三线各多少辆，使总运营费用最省？

6．某机车厂在A、B两处分厂分别有库存机车16台、12台，现要运往甲、乙两地，其中甲地15台，乙地13台。

已知从A地运一台机车到甲地的运费为5000元，到乙地的运费为4000元；从B地运一台机车到甲地的运费为3000元，到乙地的运费为6000元。

问应设计怎样的调运方案，才能使这些机车的总运费最省？

此时总运费是多少？

7．A市、B市和C市分别有某种机器10台、10台和8台。

现在决定把这些机器支援给D市18台、E市10台。

已知从A市调运一台机器到D市、E市的运费分别为200元和800元；从B市调运一台机器到D市、E市的运费分别为300元和700元；从C市调运一台机器到D市、E市的运费分别为400元和500元。

⑴设从A市、B市各调x台机器到D市,当28台机器全部调运完毕后,求总运费W（元）关于x（台）的函数式,并求W的最小值和最大值；

⑵设从A市调x台到D市，B市调y台到D市，当28台机器全部调运完毕后，用x、y表示总运费W（元），并求W的最小值和最大值。

8．某运输公司有7辆载重量为6吨的A型卡车与4辆载重量为10吨的B型卡车，有9名驾驶员，在建筑某段高速公路中，此公司承包了每天至少搬运360吨沥青的任务，已知每辆卡车每天往返的次数为A型车8次，B型车6次，每辆卡车每天往返的成本费为A型车160元，B型车252元，每天派出A型车与B型车各多少辆，公司所花的成本费最低？

最低成本费是多少？

9.某厂生产甲、乙、丙三种产品，都分别经A、B两道工序。

设A工序可以分别在A1或A2上完成，B工序可以分别在B1、B2、B3上完成。

已知甲产品可在A、B任一设备上加工；乙产品可在任一A设备上加工，但完成B工序时，只能在B1上加工；丙产品只能在A2和B2上加工。

具体工序时间及其他数据如表所示，问如何安排生产计划，使得该厂获利最大。

设备

甲产品

乙产品

丙产品

设备有效台时

设备加工费（元/h）

A1

5

10

6000

0.05

A2

7

9

12

10000

0.03

B1

6

8

4000

0.06

B2

4

11

7000

0.11

B3

7

4000

0.05

原料费（元/件）

0.25

0.35

0.50

售价

（元/件）

1.25

2.00

2.80