运筹学线性整数规划http://see,xidian.edu.cn
运筹学 线性整数规划
线性整数规则(LinearIntegerprogramming)基本概念定义1：在LP中当要求决策变量（部分或全部）取整数值时，此类LP称为线性整数规划（LIP）或整数线性规划(ILP)。对于一个LP，若要求全体决策变量均为整数，则该LP称为纯（Pure）整数线性规划否则称为混合（mixed）整数线性规划；又若决策变量只能取0与1时，则该LP称为0一1规划。max z=Cxmax z-CxLP: s.tAx-bLIP: s.t Ax-bx≥0x>0，x各分量部分或全体取整数
线性整数规则 (Linear Integer programming) ⚫ 基本概念 ◆ 定义1：在LP中当要求决策变量（部分或全部）取 整数值时，此类LP称为线性整数规划（LIP）或整 数线性规划(ILP)。对于一个LP，若要求全体决策变 量均为整数，则该LP称为纯（Pure）整数线性规划； 否则称为混合（mixed）整数线性规划；又若决策变 量只能取0与1时，则该LP称为0—1规划。 max z=Cx max z=Cx LP: s.t Ax=b LIP: s.t Ax=b x≥0 x≥0 ,x各分量部分或全体取整数
决策变量（部分或全体）取整数的原因：这些决策变量可以是购买的设备数，工作的工人数，设备的工厂数，购买的股票数（1手，2手LIP研究概况LIP要比LP问题的求解复杂得多，目前尚未找到一个较好的统一的求解方法目前研究较多的有穷举法（太繁杂）>取整法（误差不好估计）>LIP（分支定界法，割平面法等）（动态规划法，图论法等）>NLIP
决策变量（部分或全体）取整数的原因： 这些决策变量可以是购买的设备数，工 作的工人数，设备的工厂数，购买的股 票数（1手，2手.） ⚫ LIP研究概况 LIP要比LP问题的求解复杂得多，目前 尚未找到一个较好的统一的求解方法， 目前研究较多的有 ➢ 穷举法（太繁杂） ➢ 取整法（误差不好估计） ➢ LIP（分支定界法，割平面法等） ➢ NLIP（动态规划法，图论法等）
穷举法思想：设x=(X1,X2...Xn)T，首先将每个xj的整数上界找出来，使0≤x≤i=l~n，然后在可行域D中将满足上述条件的整数点全部找出来，共有為（，+1)。最后逐个验证其是否为基本可行点(Ax<b，x>O)，并对这些基本可行解x通过目标函数值的比较来求最优解例1：0≤x1≤3，0≤x2≤4，故共有(3+1)(4+1)=20个整数点（又称格子点），其中只有13个基本可行点，通过下表1比较目标函数值可知可取为最优解，，但穷举法z(x）=14作量太x=(2,2)，大，以n=4，0≤xj≤24为例，共有254=个格子点验证是否为基本可行解，并比较目标值
⚫ 穷举法思想：设x=(x1 ,x2 ,.xn ) T，首先将每个xj 的整数上界 找出来，使0≤xj≤ ，j=1~n，然后 在可行域D中将满足上述条件的整数点全部找出 来，共有 个。最后逐个验证其是否为 基本可行点(Ax≤b，x≥0)，并对这些基本可行解 通过目标函数值的比较来求最优解 。 ⚫ 例1： 0≤x1≤3， 0≤x2≤4，故共有(3+1)(4+1)=20 个整数点（又称格子点），其中只有13个基本 可行点，通过下表1比较目标函数值可知可取 为最优解， ，但穷举法枚举的工作量太 大，以n=4， 0≤xj≤ 24 为例，共有254=个格子 点验证是否为基本可行解，并比较目标值。 j l ( 1) 1 + = j n j l x ~ (2,2) ~ x = ) 14 ~ z(x =
例1: max z=4xj+3x24xj+5x2≤20s.t2Xj+X2 ≤6X1,X2≥0Xi,X2为整数A(5/3,8/3)4x,+5x2=22x,+x2=6
⚫ 例1：max z=4x1+3x2 s.t 4x1+5x2≤20 2x1+x2 ≤6 x1 ,x2≥0 x1 ,x2为整数 2x1+x2=6 4x1+5x2=2 A(5/3,8/3)