运筹学 第五章 整数规划

1、第1、5章整数编程、第2、整数编程是需要变量整数值的数学编程的一种，可分为线性和非线性(本章介绍了线性)。根据变量的值特性，可以分为仅整数配置、混合整数配置、0-1整数配置等。3，整数规划是数学规划中较弱的分支，目前只能解中等大小的线性整数规划问题，而非线性整数规划问题还没有好的方法。例如：登山队员正在准备登山，他需要携带的物品包括食物、氧气、冰湖、绳子、帐篷、相机和通信设备，每件物品的重要性系数和重量如下。假设登山队员能携带的最大重量是25公斤。问：如何装备设备？5，6，解法：诗=1表示登山队员没有随身物品I，诗=0表示登山队员没有随身物品I，问题是0-1组态： max z=20 x115

2、x2 18x 314 x4 x54x 6 10x 7s . t . 5 x15 2x 3 6x 4 12x 7只有一个限制，即最多只能装载b公斤的物品，每个物品只能全部携带，因此旅行者决定了每个物品有用程度的“价值”，如果总共有n个物品，那么它的价值就是cj。问题是：携带的物品总重量不超过b公斤，携带什么物品能最大化总价值吗？8，解决方法：如果xj=1表示不携带随身物品j，xj=0表示不携带随身物品j，则问题显示为0-1计划： max z=cjxj s.t. axj b XJ=0或1，9。将货物运输到货箱中时，问：a，a，b，a，b，a，b，a，b，b，y，b，b，z为了最大化总利润，要装多少

3、箱？10，图形方式：x1 *=4 x2 *=1 zi *=90，max z=20 x110 x25 x14x 2 242 x12 5x 13 x1，x20 x1，x2整数，11，对于max问题，请参见zI* zl* min问题的zI* zl*，12，数学模型整数编程(IP)的通用数学模型： max z=cjxj s.t. aijxj bi (I=1，2，m)，14，示例：以下两个约束相互矛盾：f(x)-5 0 (1) f(x) 0 (2)足以表示-f(x) 5 M(1-y) (3) f(x) My (4) MY=0时(2)(4)没有差异，(3)表达式显然成立。上述方法可以处理绝对值形式的约束f

4、(x) a (a0)。f(x) a (5) f(x) -a (6)是矛盾的约束。f(x)-5 0(1)-f(x)5m(1-y)(3)f(x)0(2)f(x)My(4)，f(x) a (5) f(x) -a (6)，17，例如，两个约束2x1x28x1x22只能存在一个，并使用变量0-1表示此要求。解决方案：如果引入0-1变量y和足够大的正M，则18，8-2x1-3x2 M(1-y) x1 x2-2 My时y=0，x1 x2 2成立，2x1 3x2 8-M自然成立，不必要。Y=1，2x1 3x2 8已设定，x1 x2 2 M自然成立，因此是多馀的。，2x1 3x2 8 x1 x2 2，19，选择

5、多个约束之一。例如，如果模型引入以下n个约束中的一个约束有效，则fi(x) 0 i=1，2， n. n 0-1变量yi，i=1，2，n，以上约束为fi(x)m(1-y1 y2 yn=要使k约束条件有效，请确保fi(x) M(1-yi)，y1 y2 yn=k约束条件仅有效到最大k:要使最小k个约束条件有效，请执行以下操作：fi (x) m (1-yi)，y1 y2 ynk，y1 ynk否则，如果第一个约束不成立，则第二个约束也可能不成立。可以说明如下：如果22，f (x)0为真，则g (x) 0必须成立。如果F (x)0不为真，则对g (x)没有限制。引入0-1变量：如果f (x) -M(1-y

6、) (*) g (x) My，23，f (x)0为真，则y不能为1。否则，与(*)相矛盾。因此，设置y=0，g (x) 0。如果F (x) 0(即f (x)0不为真)，则y的值不再重要。y始终取值(*)，因此y的值不受(*)控制，因此g (x)的值不受限制。f (x) -M(1-y) (*) g (x) My，24，解决方案概述开始接触整数规划问题时，通常有两个初始想法：由于可执行程序的数量有限，所以在彻底比较后总是能找到最佳方案。例如，背包问题充其量有2n种方法，但实际上是不可能的。假设计算机每秒可以比较1000000种方式，比较260种方式大约需要360世纪。25，忽略变量的整数要求，求解

7、线性规划问题，然后用四舍五入法得到整数解。只有在变量的值很大的情况下，此方法才能成功，特别是在0-1配置中，如果变量值很大，此方法就不能成功。26，例如，存在以下问题：max z=3x 113 x2s . t . 2x 19x 22 40 11 x1-8x 282 x1、x20和整数值，27，o 1 2 3 4 5 6 8 9 10，5 4 3 1，x1，x2，I、max z=3x 113 x2s . t . 2x 1 9x 22 40 11 x1-8x 282 x1、x20和整数值，28，o 1 2 3 4 5 6 8 9 10，5 4 3 1、e、f、g、h、I、j、29、o 1 2 3

8、4 5 6 8 9 10、5 4 3 2 1、x1、x2、I (2、4)、b P4，P3，P5，30，x12，x23，x17，x24，X2 3， 解决当前整数计划问题的两种基本方法在上文中进行了说明。32，5.1季度和边界方法原始问题的缓解问题：放弃特定约束(如整数要求)后出现的问题(p)称为(IP)的缓解问题。最常见的缓解问题是放弃变量的整数要求后(p)是线性规划问题。33，消除整数约束，通过单纯形方法，34，分支和边界方法步骤通常解决相应的松弛问题，可能会出现以下几种情况：如果最佳解决方案的每个组件都恰好是整数，那么该解决方案就是原始整数编程的最佳解决方案，计算结束。，35，分支和边界方法

9、步骤通常会发生以下几种情况以解决相应的缓解问题：如果最佳解决方案的每个组件都恰好是整数，那么该解决方案就是原始整数编程的最佳解决方案，计算结束。如果没有缓和问题的可行解决方案，就没有原始整数编程问题的可行解决方案，计算结束。36，松弛问题的最优解，但如果每个分量都不是整数，那么这个解不是原始整数编程的最优解，继续下一步。37，平滑问题的最优解，但如果每个分量都不是整数，则该解不是原始整数编程的最优解，继续下一步。必须选择不符合整数条件的基本变量之一，以满足分叉的XL XL或XL XL 1之一，并将这两个约束条件添加到原始问题中，以形成两个互不兼容的子问题(二分法)。38，边框：使用满足整数条件

10、的每个分支的最佳目标函数值作为上限(下限)边界，确定是保留分支还是修剪分支。39，边框：使用满足整数条件的每个分支的最佳目标函数值作为上限(下限)边界，确定是保留分支还是修剪分支。修剪：将那些子问题的最佳值与边界值进行比较，将优或不优的分支全部剪掉，直到各分支明确表明为止。40，例如，使用分支定界法解决：max Z=4x 1 3x 2s . t . 3x 14x 2 12 4x 1 2x 12 9x 1，x20整数使用单纯形方法解决相应缓解问题的最佳解决方案(6/5，21/10)Z=111，41，0 1 2 4，4 3 2 1，x1，x2，分支：x1 1，x12，P1，p2，(6/5，21/10)， 0 1 2 3 4，4 3 2 1、x1、x2、和(P1) x1 1 (1，9/4)季度：(P3) x22 (P4) x23，P1，p2 3) z=9，47，x12，x22，X11，x23，p 13360(1，9/4) z=10 (3/4) ，49，0 1 2 3 4 6，8 7 6 5 4 3 2 1，x1，x2，p，50，0 1 2 3 6，8 7 6 5 4 3 2 1，x1，x2，p，53，0 1 2 3 4 6，8 7 6 4 3 1，x1，x2，p，对(P1) x1 3选择x2进行分支。(P3)