第5章 整数规划(2)

运筹学思考练习题答案第⼀章 L.P 及单纯形法练习题答案⼀、判断下列说法是否正确1. 线性规划模型中增加⼀个约束条件，可⾏域的范围⼀般将缩⼩，减少⼀个约束条件，可⾏域的范围⼀般将扩⼤。

(?)2. 线性规划问题的每⼀个基解对应可⾏域的⼀个顶点。

(?)3. 如线性规划问题存在某个最优解，则该最优解⼀定对应可⾏域边界上的⼀个点。

(?)4. 单纯形法计算中，如不按最⼩⽐值原则选取换出变量，则在下⼀个基可⾏解中⾄少有⼀个基变量的值为负。

(?)5. ⼀旦⼀个⼈⼯变量在迭代中变为⾮基变量后，该变量及相应列的数字可以从单纯形表中删除，⽽不影响计算结果。

(?)6. 若1X 、2X 分别是某⼀线性规划问题的最优解，则1212X X X λλ=+也是该线性规划问题的最优解，其中1λ、2λ为正的实数。

(?)7. 线性规划⽤两阶段法求解时，第⼀阶段的⽬标函数通常写为ai iMinZ x =∑(x ai 为⼈⼯变量)，但也可写为i ai iMinZ k x =∑，只要所有k i 均为⼤于零的常数。

(?)8. 对⼀个有n 个变量、m 个约束的标准型的线性规划问题，其可⾏域的顶点恰好为m n C 个。

(?)9. 线性规划问题的可⾏解如为最优解，则该可⾏解⼀定是基可⾏解。

(?)10. 若线性规划问题具有可⾏解，且其可⾏域有界，则该线性规划问题最多具有有限个数的最优解。

(?)⼆、求得L.P 问题121231425j MaxZ 2x 3x x 2x x 84x x 164x x 12x 0;j 1,2,,5=+++=??+=??+=?≥=的解如下： X ⑴=(0,3,2,16,0)T ;X ⑵=(4,3,-2,0,0)T ;X ⑶=(3.5,2,0.5,2,4)T ;X ⑷=(8,0,0,-16,12)T ; =(4.5,2,-0.5,-2,4)T ; X ⑹=(3,2,1,4,4)T ;X ⑺=(4,2,0,0,4)T 。

要求：分别指出其中的基解、可⾏解、基可⾏解、⾮基可⾏解。

1、单纯型法（第1、2章）概念和描述：线性规划问题的模型、对偶问题的模型、基变量、非基变量、解的形式（基解、基可行解、最优解、无解、无可行解）、影子价格判定：线性规划问题解的形式、单纯型表运算的规则、对偶变换的规则证明：线性规划问题的矩阵运算、对偶理论步骤：对偶单纯型法的步骤、敏感性分析的步骤计算：单纯型法、改进单纯型法、互补松弛定理的运用、对偶单纯型法、敏感性分析计算（C-r、b、A-ij、新增变量和约束）2、运输问题（第3章）概念和描述：运输问题的模型、产销不平衡问题模型描述判定：运输问题中基变量的个数、最优解判定（尤其是如何给出多个最优解）、求最小还是求最大步骤：表上作业法的步骤、最优解的步骤计算：产销不平衡问题、求最大的问题（看例3-5、09年真题）3、整数规划（第5章）概念和描述：整数规划的数学模型（相互排斥的计划、相互排斥的约束、指派问题）步骤：分枝定界法的步骤、匈牙利算法的步骤计算：分枝定界法、割平面法、指派问题不考：0-1型整数规划的全枚举法4、动态规划（第6章）计算：一维资源分配（离散、连续）、生产和存储问题（生产计划、不确定性采购）、背包问题（课本的例题有些复杂，看真题好些）、复合系统可靠度、排序（直接看例6-10）、设备更新问题。

以上问题都要清楚各自的模型描述、状态和决策变量取值描述、状态转移方程和指标函数形式不考：二维资源分配、货郎担问题5、图论（第7章）概念和描述：连通图、割集、最短路等问题的模型描述、可行流、最大流、饱和弧、非饱和弧、增广链、最小费用增广链证明：定理7.8步骤：Dijkstra算法的步骤、Floyd算法的的步骤、最长路算法的递推关系、寻找增广联的调整步骤、最小费用最大流问题的转换步骤计算：最短路（Dijkstra、Floyd）、最长路、最大流、最小费用最大流不考:寻找最小支撑树算法、图的矩阵表示、最短路另外两个算法、中国邮路问题6、排队论（第9章）判定：问题所属的排队类型、little公式的适用对象证明：用生灭过程的状态转移方程推导MM1、MM1N、MMC、MMCN的排队参数（MM1的证明考过，其他的最好也好，实在不行就把公式记下来背吧）计算：MM1、MM1N、MMC、MMCN、MD1、ME1、MM1中的最优服务率、MMC中最优服务台数不考：MM1N及顾客数为有限中的最优服务率、顾客源有限的排队系统其他不用看的章节：第4线性规划应用举例、第8章络计划（不考大题）、第10章存贮论课后习题不用全做，调自己认为经典的做做，在用胡的习题集对答案就可以了。

Slack or Surplus 100.0000 -4.000000 -5.000000
20
0-1型整数规划
0-1型整数规划是整数规划中的特殊情形，它 的变量xj仅取值0或1。这时xj称为0-1变量，或 称二进制变量。 xj仅取值0或1这个条件可由下 0 述约束条件： ≤ x j ≤ 1 整数 所代替，是和一般整数规划的约束条件形式一 致的。
23
例4 指派问题
指派问题的标准形式（以人和事为例）是： 有 n 个人和 n 件事，已知第 i 人做第 j 事的 费用为 Cij（i，j = 1，2，…，n），要求确定 人和事之间的一一对应的指派方案，使完成这 件事的总费用最少。
24
指派问题的标准形式及其数学模型
xij = 1 当指派第 i 人完成第 j 项任务 0 当不指派第 i 人完成第 j 项任务
27
非线性规划
形如：
max f ( x) ⎧ hi ( x) = 0, i = 1, L , m s.t. ⎨ g j ( x) ≥ 0, j = 1, L , l ⎩
称为非线性规划。
28
例一
某公司经营两种物品，第一种物品每吨售价30 元，第二种物品每吨售价450元，售出每吨第 一种物品时所需的营业时间平均是0.5小时， 第二种物品的时间是（2+0.25x2）小时，其中 x2是第二种物品售出的数量。已知该公司在这 段时间内的总营业时间为800小时，试决定使 其营业额最大的营业计划。
31
Local optimal solution found at iteration: 101 Objective value: 49815.00 Variable X1 X2 Row 1 2 Value 1495.500 11.00000 Slack or Surplus 49815.00 0.000000 Reduced Cost 0.000000 0.5508468E-08 Dual Price 1.000000 60.00000

1 xj 0 对项目j投资 对项目j不投资 （j 1， ，n） 2，
则问题可表示为：
max z c j x j
j 1 n
n a j x j B j 1 x1 x2 0 s.t. x3 x4 1 x x x 2 7 5 6 x j 0或1 j 1,2, , n 【例5-3】工厂A1和A2生产某种物资，由于该种物资供不应 求，故需要再建一家工厂，相应的建厂方案有A3和A4两个。这 种物资的需求地有B1、B2、B3、B4四个。各工厂年生产能力、各 地年需求量、各厂至各需求地的单位物资运费cij(j=1,2,3,4) 见表5-2。
三、割平面法的算法步骤
步骤1：将约束条件系数及右端项化为整数，用单纯形法求 解整数规划问题(ILP)的松弛问题(LP)。设得到最优基B，相应 的基最优解为X*。 步骤2：判别X*的所有分量是否全为整数？如是，则X*即为 (ILP)的最优解，算法终止；若否，则取X*中分数最大的分 量 x * ，引入割平面(5.7)。
表5-2
Ai cij A1 A2 Bj B1 2 8 B2 9 3 B3 3 5 B4 4 7 生产能力 (千吨/年) 400 600
A3
A4 需求量(千吨/年)
7
4 350
6
5 400
1
2 30025 150200200工厂A3或A4开工后，每年的生产费用估计分别为1200万元或 1500万元。现要决定应该建设工厂A3还是A4，才能使今后每年 的总费用(即全部物资运费和新工厂生产费用之和)最少。
一般来说，整数线性规划可分为以下几种类型：
1. 纯整数线性规划(Pure Integer Linear Programming)： 指全部决策变量都必须取整数值的整数线性规划，也称为全整 数规划。 2. 混合整数线性规划(Mixed Integer Linear Programming)：指决策变量中一部分必须取整数值，而另一部 分可以不取整数值的整数线性规划。 3. 0-1整数线性规划(Zero-one Integer Linear Programming)：指决策变量只能取0或1两个值的整数线性规划。