整数型规划及应用

2012——2013学年第 一 学期

合肥学院数理系

实验报告

课程名称： 运 筹 学

实验项目： 应用LINDO软件求解整数规划

实验类别：综合性□ 设计性 □√ 验证性□

专业班级： 10级数学与应用数学（1）班

姓 名： 汪 勤 学 号： 1007021004

实验地点： 35-612

实验时间： 2012-11-29

指导教师： 管梅老师 成 绩：

1

一.实验目的

1、熟悉LINDO软件的求解整数规划功能。

2、学习应用LINGO软件求解整数规划问题。

3、熟练掌握LINGO软件的操作。

二.实验内容

1、某班有男同学30人,女同学20人,星期天准备去植树。根据经验,一天中,男同学平均每人挖坑20个,或栽树30棵,或给25棵树浇水,女同学平均每人挖坑10个,或栽树20棵,或给15棵树浇水。问应怎样安排,才能使植树(包括挖坑、栽树、浇水)最多。建立该问题的数学模型，并求其解。

2、求解线性规划：121212212max2251228..010,zxxxxxxstxxx为整数

3、在高校篮球联赛中,我校男子篮球队要从８名队员中选择平均身高最高的出场阵容,队员的号码、身高及擅长的位置如下表：

队员 身高（m） 位置

1 1.92 中锋

2 1.90 中锋

3 1.88 前锋

4 1.86 前锋

5 1.85 前锋

6 1.83 后卫

7 1.80 后卫

8 1.78 后卫

同时，要求出场阵容满足以下条件： 2 ⑴ 中锋最多只能上场一个。

混合整数规划及其应用

混合整数规划（Mixed Integer Programming，MIP）是运筹学中一个重要的分支，它可以用于解决包括生产计划、物流运输、资源调度等实际问题。本文将探讨混合整数规划的基本概念、典型模型以及应用范例。

一、基本概念

1.定义

混合整数规划是指在线性规划基础上加入了整数变量的限制条件，有时还将变量限制为 0/1 取值，即 0 表示不选取某个变量，1 表示选取某个变量。

2.数学模型

混合整数规划的一般数学模型如下：

$max\ Z=c^{T}x+d^{T}y$

$s.t.$

$A x+B y \leq b$

$x\in R^{n}, y \in Z^{m}$

其中，$x$ 是连续变量向量，$y$ 是整数变量向量，目标函数

$Z$ 为一线性函数，$A$, $B$ 为系数矩阵，$b$ 为约束条件的取值。本模型中整数变量 $y$ 的限制条件可以是 $y \in\{0,1\}^{m}$ 也可以是 $y

\in Z^{m}(m>0)$。 3.求解方法

求解混合整数规划可以采用分枝界限法、Gomory 切割法、随机搜索等方法。其中，分枝界限法是运筹学中最基本的解法，其最优性原理为“不断将问题分解成子问题，逐步地去掉某些变量，直到问题变为纯整数规划问题为止，然后通过确定某些变量取值来求解”。随机搜索法则是通过不断随机生成可行解并比较其目标值的大小进行求解。

二、典型模型

1.背包问题

背包问题中，有 $n$ 种不同体积和不同价值的物品，需要将它们装入一个容量为 $V$ 的背包。每种物品只有选择或不选择两种情况。设

$w_{i}$ 为第 $i$ 种物品的价值，$v_{i}$ 为第 $i$ 种物品的体积，则该问题的混合整数规划模型为：

$max\ \sum_{i=1}^{n} w_{i} x_{i}$

$s.t.$

$\sum_{i=1}^{n} v_{i} x_{i} \leq V$

1

甲乙公司不合作即竞争下所争取到的不同名专业推广者所建立的不同动态规划模

型的组合方案如下：其中X 为可能竞争到的专业推广者人数，即动态规划模型中第一天的 2 专业推广者推

广能力的份数，Y 为第二天需要的专业推广者推广能力的份数，即第三天安排从事推广

工作的专业推广者的人数；Z 为第三天需要的专业推广者推广能力的份数，即第三天安排从事推广工作的专业推广者的人数；a 为x 名专业推广者累计从事培训工作出来的兼职推广者的批数（每批20 人），其中，有多种组合方案；甲公司雇佣这些兼职推广者均工作一天，从事推广工作，第二天辞退a −b批兼职推广员，其余的b批继续从事推广工作一天后辞退，即兼职宣传员总共最多雇佣2 天；cost 为花费的成本，即资金的使用数量；F 为不同方案下所达到的总推广效益。上表可以提供给甲公司做决策依据，根据效益的大小甲公司可以决策的目标方向顺序是从①--⑧，即不合作的情况下甲公司可以尽量争取到9 人，如若不行，考虑争取4 人。§5.4 0—1型整数规划模型

1、 0—1型整数规划模型概述

整数规划指的是决策变量为非负整数值的一类线性规划，在实际问题的应用中，整数规划模型对应着大量的生产计划或活动安排等决策问题，整数规划的解法主要有分枝定界解法及割平面解法（这里不作介绍，感兴趣的读者可参考相关书籍）。在整数规划问题中，0—1型整数规划则是其中较为特殊的一类情况，它要求决策变量的取值仅为0或1，在实际问题的讨论中，0—1型整数规划模型也对应着大量的最优决策的活动与安排讨论，我们将列举一些模型范例，以说明这个事实。

0—1型整数规划的的数学模型为：

目标函数 nnxcxcxczMinMax2211)(

约束条件为：

1 | 0 ) ,() ,() ,(22112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxa, , ,21

应用混合整数线性规划

混合整数线性规划（MILP）是数学规划中的一种重要类型，它在实际应用中具有广泛的应用价值。MILP可以被描述为一种在优化的同时满足线性和离散限制的问题。其中，线性部分通常是指一个线性目标函数和一组线性约束条件，而离散部分通常是指一个或多个变量必须是整数。

MILP的应用场景涵盖了许多领域，如物流、供应链、生产调度、航空航天、电力系统等。在这些领域中，MILP都能够提供有效的决策支持。比如，在供应链中，MILP可以帮助企业优化物流运输路线、合理安排存储和配送等流程。在生产调度中，MILP可以帮助企业优化生产线的排程，提升生产效率和资源利用率。在航空航天领域，MILP可以帮助航空公司优化飞行计划、航班调度和飞机维护等决策。在电力系统中，MILP可以帮助电力公司优化电力调度、电网规划和电力市场设计等问题。

在MILP问题的求解中，现有的算法主要包括分支定界法、割平面法、内点法等。其中，分支定界法是一种被广泛应用的算法，它将问题分解为一系列子问题，并逐步缩小搜索空间，最终找到全局最优解。割平面法则是一种通过添加额外的约束条件来削弱问题可行域的算法。内点法则是一种通过寻找问题的最优解点的算法，它能够有效地处理大规模的MILP问题。此外，近年来出现的许多启发式算法，如遗传算法、蚁群算法、模拟退火算法等也被用于MILP问题求解。

无论采用何种算法，应用MILP问题求解时需要考虑如下几点：

首先，需要确保模型的准确性与完整性。一个好的模型应该能够准确地反映现实问题，并包含所有重要的因素和约束条件。

其次，需要选择适合问题特点的求解算法。在实际运用中，不同的问题具有不同的特点，有些问题规模非常大，需要使用分布式计算等技术才能求解。因此，需要根据具体问题的特点选择适合的求解算法，并进行参数调整和优化。

最后，需要关注求解结果的有效性与可行性。有时候，求解结果可能不是最优解，但在现实中却是可行的。因此，在应用MILP求解时需要进行适当的检验和验证，确保结果的有效性和可行性。