运筹学-4整数规划.pptVIP

张红历;;本章内容;;一、整数规划的数学模型的一般形式;纯整数规划：所有决策变量要求取非负整数〔这时引进的松弛变量和剩余变量可以不要求取整数〕。;二、整数规划的例子;例2某效劳部门各时段〔每2h为一时段〕需要的效劳员人数见下表。按规定，效劳员连续工作8h为一班。现要求安排效劳员的工作时间，使效劳部门效劳员总数最少。;;;4;三、整数规划解特点;;最优解不一定在顶点上到达

最优解不一定是放松问题最优解的邻近整数解

整数可行解远多于顶点，枚举法不可取;整数规划=相关的线性规划+整数约束

整数规划是约束得更紧的问题,它的可行域是其相关线性规划问题可行域的一个子集；

整数解的数目远少于线性规划的解，只要可行域有界，整数解的数目有限；

整数规划的求解难度远大于线性规划。;例：设整数规划问题如下;用图解法求出最优解

x1＝3/2,x2=10/3

且有Z=29/6;因此，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法。

其中〔2，2〕〔3，1〕点为最大值，Z=4。;求解整数规划方法;;;有“三栖学者”美称的理查德·卡普(RichardManningKarp)获得1985年度的图灵奖是众望所归的。

卡普之所以被称为“三栖学者”是因为他知识渊博，贯穿多个学科专业，因而同时被加州大学伯克利分校的电气工程和计算机系、数学系以及工业工程和运筹学系三个系聘为教授。

卡普之所以被授予图灵奖，也是因为他在算法的设计与分析、计算复杂性理论、随机化算法等诸多方面作出了创造性奉献。;1、根本思想

分枝定界法是一个用途十分广泛的算法，运用这种算法的技巧性很强，不同类型的问题解法也各不相同。

分支定界法的根本思想是对有约束条件的最优化问题的所有可行解〔数目有限〕空间进行有哪些信誉好的足球投注网站。该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集〔称为分支〕，并为每个子集内的解的值计算一个下界或上界〔称为定界〕。在每次分支后，对但凡界限超出可行解值那些子集不再做进一步分支。这样，解的许多子集〔即有哪些信誉好的足球投注网站树上的许多结点〕就可以不予考虑了，从而缩小了搜???范围。这一过程一直进行到找出可行解为止，该可行解的值不大于任何子集的界限。因此这种算法一般可以求得最优解。

将问题分枝为子问题并对这些子问题定界的步骤称为分枝定界法。;;检查所有分支的解及目标函数值，假设某分支的解是整数并且目标函数值大于〔max)其他分支的目标函数值，那么将其他减去不再计算；假设还存在非整数解并且目标函数值大于〔max)整数解的目标值，需要继续分支，再检查，直到得到最优解。;;二、具体解题步骤;;3.定界〔修改上下界〕;4.比较与剪支;补充例子：用分枝定界法求解整数规划问题〔用图解法计算〕;用图解法求〔LP〕的最优解，如下图。;有下式：;;参加条件：x2≤3,x2≥4有下式：;;在〔LP3〕的根底上继续分枝。参加如下条件形成下式：;x1;至此，原问题〔IP〕的最优解为：

x1=2，

x2=3,

Z*=Z(5)

＝－17

以上的求解过程可以用一个树形图表示如右：;例〔p132)用分枝定界法求解整数规划问题;LP1

x1=1,x2=7/3

Z(1)＝10/3;分枝定界法计算过程总结：;用分枝定界法

求解下题;8.33;;;;尽管LP1的解中x1不为整数，但Z5Z因此LP5的最优解就是原整数规划的最优解。;从分支定界法的原理和步骤可知，它也适用于求解混合整数规划问题。;;0－1整数规划是一种特殊形式的整数规划，这时的决策变量xi只取两个值0或1。;;;;1;0-1规划的实例－例1;解：解题时先引入0－1变量Xi(i=1,2,…,7)

令

;该公司只有600万资金可用于投资，由于技术上的

原因，投资受到以下约束：

1、在工程1、2和3中必须有一项被选中

2、工程3和4只能选中一项且必须选中一项；

3、工程5被选中的前提是工程1被选中;

如何在满足上述条件下选择一个最好的投资

方案，使投资收益最大？;投资工程模型：;试引入0－1变量将以下各题分别表达为一般线性约束条件

〔1〕x1+x2≤6或4x1+6x2≥10或2x1+4x2≤20

〔2〕假设x1≤5，那么x2≥0，否那么x2≤8

〔3〕x2取值0，1，3，5，7;;例5.