管理运筹学讲义整数规划

整数线性规划

篮球队选队员问题

篮球队要选择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 页 共 29 页 《运筹学》复习参考资料

资料加工、整理人——杨峰（函授总站高级讲师）

要求掌握的各部分知识点

第一部分 线性规划问题的求解（相当于教材的第一章）

——重要算法：单纯形迭代、大M法单纯形迭代、表上作业法、匈牙利法

第二部分 动态规划问题的求解（相当于教材的第三章）

——重要算法：图上标号法

第三部分 网络分析问题的求解（相当于教材的第四章）

——重要算法：破圈法、TP标号法、寻求网络最大流的标号法

第四部分 存储论简介（相当于教材的第七章）

※杨老师关于学习方法的提示：《运筹学》属于应用数学的范畴，本门课程在管理类本科生层次开设时，又称“管理运筹学”，是现代数学理论和计算机技术应用于管理科学的新兴学科。非应用数学系（专业）学生学习本门课程之前务必先具备“高数Ⅱ”（线性代数、概率论与数理统计）的知识基础。学员同志们通过学习，必须领会数学建模的思想、系统工程的思想。

非全日制学生学习时，只要求知道若干典型数学模型及其算法的操作，即只须明白“怎样做”，而不必去过问“为什么”要这样做。 第 2 页 共 29 页 第一部分 线性规划问题的求解

一、两个变量的线性规划问题的图解法：

㈠概念准备：定义：满足所有约束条件的解为可行解；可行解的全体称为可行（解）域。

定义：达到目标的可行解为最优解。

㈡图解法：

图解法采用直角坐标求解：x1——横轴；x2——竖轴。1、将约束条件（取等号）用直线绘出；

2、确定可行解域；

3、绘出目标函数的图形（等值线），确定它向最优解的移动方向；

注：求极大值沿价值系数向量的正向移动；求极小值沿价值系数向量的反向移动。

4、确定最优解及目标函数值。

㈢参考例题：（只要求下面这些有唯一最优解的类型）

例1：某厂生产甲、乙两种产品，这两种产品均需在A、B、C三种不同的设备上加工，每种产品在不同设备上加工所需的工时不同，这些产品销售后所能获得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示：

实验报告

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

姓名：__专业：、 班级：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. 决策变量

决策变量是问题中需要优化的变量，其取值决定了问题的解。在整数规划中，决策变量通常表示为整数。

2. 目标函数

目标函数是整数规划问题中需要最小化或最大化的目标。它可以是线性函数或非线性函数，但在整数规划中，通常只考虑线性目标函数。

3. 约束条件 约束条件是问题的限制条件，限制了决策变量的取值范围。在整数规划中，约束条件可以是线性等式或线性不等式。

三、整数规划的解决算法

解决整数规划问题的常见算法包括割平面法、分支定界法和动态规划法等。这些算法通过不断对问题进行优化，逐步逼近最优解。

1. 割平面法

割平面法是一种通过添加额外的约束条件来逼近最优解的方法。它首先求解一个松弛问题，然后根据松弛问题的解加入新的约束条件，直到找到最优解。

2. 分支定界法

分支定界法是一种将整数规划问题划分为多个子问题，并对每个子问题进行求解的方法。它通过不断分支和剪枝来找到最优解。

3. 动态规划法

动态规划法是一种通过将问题分解为多个子问题，并通过求解子问题的最优解来求解原始问题的方法。它采用自底向上的求解方式，将所有可能的决策情况进行组合，得到最优解。

四、整数规划在实际问题中的应用

整数规划在实际问题中有着广泛的应用。以下是一个应用整数规划解决的实际问题示例： 某公司生产两种产品A和B，每天的生产时间为8小时。产品A每单位利润为100元，产品B每单位利润为150元。同时，每天产品A和产品B的生产时间不能超过4小时。现在需要确定每天生产的产品数量，以使得总利润最大化。