1
第八章最优化问题
最优化分支：线性规划，整数规划，几何规划，非线性规划，动 态规划。又称规划论。
应用最优化方法解决问题时一般有以下几个特点 ：
1. 实用性强
2. 采用定量分析的科学手段
3•计算量大，必须借助于计算机
4.理论涉及面广
应用领域：工业，农业，交通运输，能源开发，经济计划，企业 管理，军事作战……。
§ 8.1最优化问题实例
最优化问题：追求最优目标的数学问题。
经典最优化理论：
(1)无约束极值问题：opt f(Xi,X2, ,Xn)
(min f(Xi,X2, ,Xn)或 max f(Xi,x2^ ,Xn)) 其中，f(Xi,X2/ ,Xn)是定义在n维空间上的可微函数。
解法(求极值点)：求驻点，即满足
fxi (Xi， ,Xn) = 0
fx2 (Xi, ,Xn) = 0
并验证这些驻点是否极值点 2
(2)约束极值问题：Opt f(Xi,X2, ,Xn)
s.t. hj(Xi,X2, ,Xn) = 0, j = 1,2, ,1(1 n)
解法：采用Lagrange乘子法，即将问题转化为求 Lagrange函数
l
,l) = f(X1,X2, ,Xn)、
j=1
的无约束极值问题
近代最优化理论的实例：
例1 （生产计划问题）设某工厂有3种资源B1，B2，Bs，数量各
为bi, b2, bs,要生产10种产品Ai，…，Aio。每生产一个单位的
Aj需要消耗Bi的量为aj，根据合同规定，产品Aj的量不少于q，再 设Aj的单价为q。问如何安排生产计划，才能既完成合同，又使总 收入最多？（线性规划问题）
数学模型：设Aj的计划产量为Xj , z为总收入
10
目标函数：maxz-y CjXj jm
1o
lz am 玄 bj =1,2,3
约束条件：'冃
.X^ dj, j = 1,2，…,10
线性规划问题通常采用单纯形法来求解。
例2 （工厂设址问题）要在m个不同地点计划修建 m个规模不完 全相同的工厂，他们的生产能力分别是 6,a2…，am （为简便起见， 假设生产同一种产品），第i个工厂的建设费用fj =1,2，…，m。又 有n个零售商店销售这种产品，对这种产品的需求量分别为L(XI,X2, X； ‘1, 3
整数规划知识点总结
一、整数规划基本概念
整数规划是指决策变量的取值受到整数限制的线性规划问题。数学形式可以表示为：
\[\min c^Tx\]
\[ s.t. Ax \leq b\]
\[x\geq0 \]
\[x_i \in \{0, 1, 2, ...\}\]
其中，c为目标函数系数，x是决策变量，A是约束系数矩阵，b是约束条件的右端向量，决策变量x是整数。当所有的决策变量都是整数时，称为纯粹整数规划（Pure Integer
Programming）。当部分决策变量为整数，部分为连续变量时，称为混合整数规划（Mixed Integer Programming, MIP）。
二、整数规划解法
整数规划问题的求解可以采用分支定界法、割平面法、隐枚举法等不同方法。下面将对常用的整数规划解法进行简要介绍。
1.分支定界法
分支定界法是一种求整数规划解的有效方法，它通过对决策变量进行分支，将整数规划问题不断分解为子问题，然后采用线性规划方法求解子问题。具体步骤如下：
1）求解线性规划松弛问题，得到一个整数解。
2）若解为整数，则成为可行解，否则确定需要分支的决策变量，分为两个子问题。
3）对子问题继续重复上述过程，直到无法再分或求解出整数解为止。
2.割平面法
割平面法是在分支定界法的基础上进行改进，它在每一次迭代求解线性规划松弛问题后，引入一些额外的不等式（割平面）来改进松弛问题的界。这些割平面是通过分析整数规划问题的特性产生的，可以有效提高整数规划问题求解的效率。
3.隐枚举法
隐枚举法是一种通过隐藏对决策变量的枚举，将整数规划问题转化为线性规划问题进行求解的方法。该方法可以高效地求解整数规划问题，是一种常用的整数规划求解算法。
以上是整数规划常用的三种求解方法，通过不同的算法可以解决不同种类的整数规划问题。 三、整数规划应用领域
整数规划在实际决策问题中有着广泛的应用，如生产计划、运输调度、项目投资、资源配置等诸多领域。下面将对整数规划在不同应用领域的具体案例进行介绍。
整数规划求解方法
整数规划是一种优化问题，其中决策变量被限制为整数。求解整数规划问题的方法有以下几种：
1. 枚举法：对整数规划的决策变量进行枚举计算，找到满足约束条件的整数解并计算目标函数的值。虽然这种方法可以保证找到最优解，但是在决策变量较多时计算复杂度非常高。
2. 列生成法/分支定界法：将整数规划转化为线性规划问题，然后利用线性规划求解方法求解。通过不断添加新的决策变量，同时利用剪枝技术来减少搜索空间，从而求得整数规划的最优解。
3. 隐枚举法：通过将整数规划问题转化为混合整数规划问题，然后利用线性松弛来求解。通过求解线性松弛问题的松弛变量，来判断是否满足整数约束条件，进而判断是否需要继续搜索。
4. 启发式方法/元启发式方法：基于某种特定的启发规则进行搜索，通过局部搜索和全局搜索相结合的方式来求解整数规划问题。常见的启发式算法有遗传算法、粒子群算法等。
5. 对偶法/割平面法：通过对目标函数和约束条件进行线性组合，构建一个对偶问题，并求解对偶问题来间接求得原问题的最优解。
需要根据具体的整数规划问题来选择合适的求解方法。有些方法适用于特定类型的整数规划问题，所以需要根据问题特点来选择合适的方法。同时，对于大规模的整数规划问题，可能需要结合多种方法进行求解。
116 第8章 整数规划
§8.1 整数规划问题特征及其求解方法简介
现实生活中，根据实际问题所建立的数学模型有一种很重要的情形：目标函数和约束函数是线性函数，还要求决策变量取整数值.这类问题称为线性整数规划，简称为整数规划(IP)．
要求所有变量取整数值，称为纯整数规划；
要求部分变量取整数值，称为混合整数规划；
要求变量只取0或1，则称为0-1 规划.
某些约束函数或目标函数为非线性，称为非线性（纯/混合）整数规划.
典型的整数规划问题：
运作问题（Operational problems）: 货物的分配，生产调度、机器排序等；
计划问题（Planning problems）: 资金预算、设施选址、证券组合分析等；
设计问题（Design problems）: 通信和交通网络设计，超大规模集成电路设计、自动化生产线设计等.
共同特点：研究如何对稀有资源进行有效的管理和使用，使其发挥尽可能大的效益.
整数规划在美国军事空运指挥中的运用实例：
背景：美国防部的空运由军事空运指挥中心（MAC）负责，总部设在圣路易斯附近的斯科特空军基地. MAC每年有5,000个飞行员,驾驶1,700架飞机在24个国家的850个基地飞行约700,000小时.
要求在特定的某一天，MAC能派遣1,700个架次，执行9次救援任务，转移5,000名乘客和1,000吨货物以及用医用飞机转移200名伤员.
MAC的总指挥（四星上将）有一个由23人组成的智囊团，为MAC派遣飞行队的相关决策出谋划策.智囊团广泛运用线性整数规划对规模大而复杂的问题求得有效的解.
（1）优化货物空运计划
MAC利用C-5，C-141和C-130飞机的35％的飞行时间，按普通的货运计划在全球范围内飞行.但要被运输的货物总量超出了MAC飞行队的运载能力，因此，大量的货物运载能力必须从商业空运购买.
智囊团面临的问题：设计一个称为空中货运计划的网状系统，使得购买运载能力的支出最小.
