[工学]运筹学整数规划

整数线性规划

篮球队选队员问题

篮球队要选择5名队员上场组成出场阵容参加比赛。8名篮球队员的身高及擅长位置如下表：

队员 1 2 3 4 5 6 7 8

身高 1.92 1.90 1.88 1.86 1.85 1.83 1.80

1.78

擅长位置 中锋 中锋 前锋 前锋 前锋 后卫 后卫 后卫

要求出场阵容满足以下条件：

(1) 只能有一个中锋上场；

(2) 至少有一名后卫；

(3) 若1号和4号都上场,则6号不出场；

(4) 2号和8号至少保留一个不出场。

提问：应当选择哪5位上场，才能使出场的五名队员平均身高最高？

分析与求解：

0-1整数规划问题

设0-1变量xi

xi = 第 名队员未选上 第 名队员被选上

设第i名队员的身高为ai（i=1,2……,8），则目标函数为：

建立模型的限制条件为：

使用MATLAB的intlinprog函数求解0-1规划问题，代码如下：

f=[-0.384 -0.380 -0.376 -0.372 -0.370 -0.366 -0.360

-0.356 ];

A=[1 1 0 0 0 0 0 0

0 1 0 0 0 0 0 1

1 0 0 1 0 1 0 0

0 0 0 0 0 -1 -1 -1];

b=[1;1;2;-1]

aeq=ones(1,8)

beq=5

intcon=8

lb = zeros(8,1);

ub = ones(8,1);

x=intlinprog(f,intcon,A,b,aeq,beq,lb,ub)

求解结果：

LP: Optimal objective value is -1.864000.

x =

0

1

1

1

案例. 石华建设监理公司监理工程师配置问题

1问题重述

石华建设监理公司 ( 国家甲级 ) 侧重于国家大中型项目的监理，仅在河北省石家庄市就曾同时监理七项工程，总投资均在 5 000 万元以上．由于工程开工的时间不同，各工程工期之间相互搭接，具有较长的连续性， 1998 年监理的工程量与 1999 年监理的工程量大致相同．每项工程安排多少监理工程师进驻工地，一般是根据工程的投资、建筑规模、使用功能、施工的形象进度、施工阶段来决定的．监理工程师的配置数量随之变化．由于监理工程师从事的专业不同，他们每人承担的工作量也是不等的．有的专业一个工地就需要三人以上，而有的专业一人则可以兼管三个以上的工地．因为从事监理业的专业多达几十个，仅以高层民用建筑为例就涉及到建筑学专业、工民建 ( 结构 ) 专业、给水排水专业、采暖通风专业、强电专业、弱电专业、自动控制专业、技术经济专业、总图专业、合同和信息管理专业等，这就需要我们合理配置这些人力资源．为了方便计算，我们把所涉及的专业技术人员按总平均人数来计算，工程的施工形象进度按标准施工期和高峰施工期来划分．通常标准施工期需求的人数较容易确定．但高峰施工期就比较难确定了，原因有两点： (1) 高峰施工期各工地不是同时来到，是可以事先预测的，在同一个城市里相距不远的工地，就存在着各工地的监理工程师如何交错使用的运筹问题． (2) 各工地总监在高峰施工期到来的时候要向公司要人，如果每个工地都按高峰施工期配置监理工程师的数量，将造成极大的人力资源浪费，这一点应该说主要是人为因素所造成的．因此，为了达到高峰施工期监理工程师配置数量最优，人员合理地交错使用，扼制人为因素，根据历年来的经验对高峰施工期的监理工程师数量在合理交错发挥作用的前提下限定了范围．另经统计测算得知，全年平均标准施工期占 7 个月，人均年成本 4 万元；高峰施工期占 5 个月，人均年成本 7 万元．标准施工期所需监理工程师如下表所示．

实验报告

课程名称：___ 运筹学 ____ 项目名称：整数规划问题_

姓名：__专业：、 班级：1班 学号： 同组成员：_ __

一、

实验准备1：

实验知识点：

在前面我们所研究的线性规划问题中，一般问题的最优解都是非整数解，即

为分数和小数。但是对于实际中的具体问题的解常常要求必须取整数，即称为

整数解。为了求整数解，我们设想把所求的非整数解采用“舍入取整”的方法处理，似乎是成了整数解，但事实上这样得到的结果未必是可行的。因为取整后就

不一定是原问题的可行解了，或者虽然是可行解，但也不一定是最优解。因此，

对于要求最优解整数解的问题，需要寻求直接的求解方法，这就是整数规划问题。

如果一个数学规划的某些决策变量或全部决策变量要求必须取整数，则这样的问题称为整数规划问题，相应的模型称为整数规划模型，在整数规划中，如果所有的决策变量都为非负整数，则称之为纯整数规划问题；否则称之为混合整数规划问题。如果整数规划的目标函数和约束都是线性的，则称此问题为整数线性规划问题。

实验环境：LINGO软件

二、 实验过程记录2：

1 注：1、实验准备部分包括实验环境准备和实验所需知识点准备。

2、若是单人单组实验，同组成员填无。 例4.5设某部队为了完成某项特殊任务，需要昼夜24小时不间断值班，但每天不同时段所需要的人数不同，具体情况如表4-4所示。假设值班人员分别在各时间段开时上班，并连续工作8h。现在的问题是该部队要完成这项任务至少需要配备多少名班人员？

解：

根据题意，假设用ix（i=1,2,3,4,5,6）分别表示第i个班次开始上班的人数，

每个人都要连续值班8h，于是根据问题的要求可归结为如下的整数规划模型：

目标函数：iixz61min

约束条件：）且为整数（6...1,0x30>=x6+x520>=x5+x450>=x4+x360>=x3+x270>=x2+x160>=x6+x1ii

浙江科技学院考试试卷

第 1 页 共 6 页 2004-2005学年第一学期考试试卷 A 卷

命题：

一、解线性规划（30分）

某厂利用两种设备A，B生产三种产品甲、乙、丙，其中生产一个甲需设备A 8 h，设备B 1h，生产一个乙需设备A 4 h，设备B 3h，生产一个丙需设备A 7 h，设备B 3h，甲乙设备可利用工时分别为600h，400h。生产一个甲可获利润20，一个乙可获利润12，一个丙可获利润10。问该工厂应如何安排生产，使总利润最大？

1〉用线性规划求最优解

2〉如果生产一个甲的利润由20变为15，问最优解是否发生改变，如果改变求新解

3〉问如果A的工时从600下降到540，最优解是否发生改变，如果改变求新解

4〉假设企业考虑将一种新产品投入生产，这种新产品每件分别需A，B两种设备10h，2.5h，可获利润为28，问这种新产品是否应该投产？

5〉假设由于用电紧张，现在规定用电只能控制在1200kw，而生产甲、乙、丙三种产品每件需耗电量分别为20kw、10kw，19kw，试问原问题最优解是否发生变化？

二、某公司从三个产地A1，A2，A3将物品运往四个销售地B1，B2，B3，B4，各产地的产量、各销售地的销量和各产地运往各销售地每件物品的运费如表，问如何调运，使总运费最小（20分）

浙江科技学院考试试卷

第 2 页 共 6 页

三、解0-1型整数规划（15分）

MinZ=4X1+3 X2+2X3

2X1-5 X2+3X3≤4

4X1+ X2+3 X3≥3

X2+X3≥1

X1， X2， X3=0或1

四、给出线性规划问题（15分）

MaxZ=X1+2X2+ X3

X1+ X2-X3≤2

X1- X2+X3=1

2X1+ X2+X3≥2

X1≥0， X2≤0， X3无约束

1〉写出对偶问题

2〉利用对偶问题性质证明原问题目标函数值Z≤1

五、建模（20分）

1、某工厂有100台机器，拟分四个周期使用，在每一周期有两种生产任务，据经验，把机器X1台投入第一种生产任务，则在一个生产周期中将有1/3X1台机器作废，余下的机器全部投入第二种生产任务，则有1/10机器作废。如果干第一种生产任务每台机器可收益10，干第二种生产任务每台机器可受益7。问怎样分配机器，使总收益最大？（只需建模，写出阶段、状态变量含义、决策变量含义、状态转移方程、指标函数、最优函数）