(3.1.1)--线性规划图解法（NO3）.pdf
运运 筹筹 学学 第三讲第三讲 线性规划的图解法线性规划的图解法 2 一、线性规划问题的图解法一、线性规划问题的图解法 1 1、线性规划的可行域、线性规划的可行域 可行域：可行域：满足所有约束条件的解的集合，满足所有约束条件的解的集合，即所有约束条件共同围城的区域。即所有约束条件共同围城的区域。maxZ=3x1+5 x2 2 x1 16 2x2 10 3x1+4 x2 32 x1 0,x2 0 S.t.2x1=16 2x2=10 3x1+4 x2=32 x1 x2 4 8 10 3 5 9 0 A B C D 3 2x1=16 2x2=10 x1 x2 4 8 10 3 5 8 3x1+4 x2=32 0 A B C D 2 2、线性规划的最优解、线性规划的最优解 目标函数目标函数 Z=3x1+5 x2 代表以代表以 Z 为参数的一族平行线。为参数的一族平行线。Z=30 Z=37 Z=15 一、线性规划问题的图解法一、线性规划问题的图解法 maxZ=3x1+5 x2 2 x1 16 2x2 10 3x1+4 x2 32 x1 0,x2 0 S.t.最优解为最优解为C点点 最优解为最优解为x1=4,x2=5 最优值最优值Maxz=37 3 3、LPLP问题图解法的步骤：问题图解法的步骤：（1）画出直角坐标系；（2）依次做每条约束直线，标出可行域的方向，并找出它们共同的可行域；（3）任取一目标函数值作一条目标函数线（称等值线）,根据目标函数（最大或最小）类型，平移该直线即将离开可行域处，则与目标函数线接触的最终点即表示最优解。例：例：用图解法求解如下线性规划问题 12121212max432324.3226,0Zstxxxxxxx x2x1+3x2=24 3x1+2x2=26 Q2(6,4)Q1(26/3,0)Q3(0,8)A(12,0)B(0,13)最优解为x1=6,x2=4 最优值为maxz=36 一、线性规划问题的图解法一、线性规划问题的图解法 5 4 4、线性规划解的特性、线性规划解的特性 a b c d 由线性不等式组成的可行域是凸多边形由线性不等式组成的可行域是凸多边形(凸多边形是凸集凸多边形是凸集)凸集定义：集合内部任意两点连线上的点都属于这个集合凸集定义：集合内部任意两点连线上的点都属于这个集合 可行域有有限个顶点。可行域有有限个顶点。目标函数最优值一定在可行域的边界达到，而不可能在目标函数最优值一定在可行域的边界达到，而不可能在其区域的内部。其区域的内部。一、线性规划问题的图解法一、线性规划问题的图解法 6 5 5、线性规划解的可能性、线性规划解的可能性 （1）唯一最优解：只有一个最优点）唯一最优解：只有一个最优点（2）多重最优解：无穷多个最优解）多重最优解：无穷多个最优解 当市场价格下降到当市场价格下降到7474元，其数学模型变为元，其数学模型变为 12121212max34216210s.t.3432,0Zxxxxxxx x2x1=16 2x2=10 3x1+4 x2=32 x1 x2 4 8 10 2 5 8 0 A B C D Z=24 Z=32 Z=12 一、线性规划问题的图解法一、线性规划问题的图解法 7 3、无界解：可行域无界，目标值无限增大、无界解：可行域无界，目标值无限增大 (缺乏必要约束缺乏必要约束)12112max35216s.t.,0Zxxxx x一、线性规划问题的图解法一、线性规划问题的图解法 8 4、没有可行解：线性规划问题的可行域是空集、没有可行解：线性规划问题的可行域是空集 (约束条件相互矛盾约束条件相互矛盾)12121212max355s.t.3424,0Zxxxxxxx xx1x2O2 4 6 8 2 4 6 8目标冲突目标冲突 利害冲突利害冲突 目标强冲突目标强冲突 利害弱冲突利害弱冲突 一、线性规划问题的图解法一、线性规划问题的图解法 9（一）线性规划的标准型式（一）线性规划的标准型式 二、线性规划问题的标准型二、线性规划问题的标准型 1 1、标准型表达方式、标准型表达方式 (1)(1)代数式代数式 11max s.t.0 njjjnijjijjZc xa xbx(2)(2)向量式向量式 1maxs.t.0njjjjZxxCXpb(3)(3)矩阵式矩阵式 max0Z CXAX=bXA：技术系数矩阵，简称系数矩阵；：技术系数矩阵，简称系数矩阵；b：可用的资源量，称资源向量；：可用的资源量，称资源向量；C：决策变量对目标的贡献，称价值向量；：决策变量对目标的贡献，称价值向量；X：决策向量。：决策向量。10 一、线性规划的标准型一、线性规划的标准型 2 2、标准型转换方法、标准型转换方法 (1)如果极小化原问题如果极小化原问题minZ=CX，则令，则令 Z=-Z，转为求，转为求 maxZ=-CX (2)若某个若某个bi0，则以，则以1乘该约束两端，使之满足非负性的要求。乘该约束两端，使之满足非负性的要求。(3)对于对于型约束，则在左端加上一个非负松弛变量，使其为等式。型约束，则在左端加上一个非负松弛变量，使其为等式。(4)对于对于型约束，则在左端减去一个非负剩余变量，使其为等式。型约束，则在左端减去一个非负剩余变量，使其为等式。(5)若某决策变量若某决策变量xk无非负约束，令无非负约束，令xk=xk-xk，(xk0,xk 0)。1234512312412512345max3500020160210.3432,0Zxxxxxxxxxxxstxxxx x x x x二、线性规划问题的标准型二、线性规划问题的标准型 12121212max35216210s.t.3432,0Zxxxxxxx x例例1：将下述LP问题化为标准型 minZ=-x1+2x2-3x3 x1+2x2+3x37 s.t.-x1+x2-x3-2 -3x1+x2+2x3=5 x1,x30,x2无约束 1223max2()31223412235.12231223452()37()23()25,0Zstxxxxxxxxxxxxxxxxxxx xxx x x 解：首先设 222xxx 并引入松驰变量 54,xx例例2 将下列线性规划问题标准化。123123123123123max2320212.442,0,26zxxxxxxxxxstxxxx xx332xx 326x解：解：首先考察变量，令首先考察变量，令，则，则 转化为转化为 33024xx123123412361237351234567max22322210.44104,0zxxxxxxxxxxxstxxxxxxx xx xxxx 由此得到标准型：由此得到标准型：13 三、线性规划问题解的概念三、线性规划问题解的概念 基矩阵：基矩阵：一个非奇异的子矩阵（线性无关）。一个非奇异的子矩阵（线性无关）。矩阵矩阵A中任意中任意m列的线性无关子矩阵列的线性无关子矩阵B，称为一个基。，称为一个基。组成基组成基B的列为基向量，用的列为基向量，用Pj表示表示(j=1,2,n)。基变量：基变量：与基向量与基向量Pj 相对应的相对应的m个变量个变量xj称为基变量称为基变量 其余的其余的n-m个变量为非基变量个变量为非基变量 1 1、线性规划解之关系、线性规划解之关系 基解：基解：令所有非基变量等于零，得出基变量的唯一解令所有非基变量等于零，得出基变量的唯一解 。100010001Bx3 x4 x5 基变量是基变量是x3,x4,x5 非基变量是非基变量是x1,x2 令非基变量令非基变量x1=x2=0，得到一个基解，得到一个基解 x3=16，x4=10，x5=32 1234512312412512345max3500020160210.3432,0Zxxxxxxxxxxxstxxxx x x x x1234512312412512345max3500020160210.3432,0Zxxxxxxxxxxxstxxxx x x x x例：求出下列线性规划问题的基解例：求出下列线性规划问题的基解 基变量 非基变量 基解X=(x1,x2,x3,x4,x5)是否可行/最优 x3,x4,x5 x1,x2(0,0,16,10,32)可行基解 x3,x2,x5 x1,x4(0,5,16,0,12)可行基解 x3,x2,x1 x4,x5(4,5,8,0,0)最优基解 x3,x2,x4 x1,x5(0,8,16,-6,0)不可行基解 x1,x2,x5 x4,x3(8,5,0,0,-12)不可行基解 x1,x4,x2 x3,x5(8,2,0,6,0)可行基解 x1,x4,x5 x2,x3(8,0,0,10,8)可行基解 2x1=16 2x2=10 x1 x2 4 8 10 3 5 8 3x1+4 x2=32 0 A B C D 15 1 1、线性规划解之关系、线性规划解之关系 可行解可行解：满足约束条件满足约束条件AX=b,X0AX=b,X0的解。的解。可行基可行基：可行解对应的基矩阵。可行解对应的基矩阵。基可行解基可行解：满足非负性约束的基解称为基可行解。满足非负性约束的基解称为基可行解。最优解：最优解：使目标函数最优的可行解，称为最优解使目标函数最优的可行解，称为最优解。最优基：最优基：最优解对应的基矩阵，称为最优基。最优解对应的基矩阵，称为最优基。非 可 行 解 可 行 解 基 解 基 可 行 解 三、线性规划问题的解概念三、线性规划问题的解概念 1234512312412512345max3500020160210.3432,0Zxxxxxxxxxxxstxxxx x x x x16 2 2、线性规划基本原理、线性规划基本原理 定理定理1.1.若线性规划问题存在可行域，则其可行域一定是凸集。若线性规划问题存在可行域，则其可行域一定是凸集。定理定理2.2.线性规划问题的基可行解对应可行域的顶点。线性规划问题的基可行解对应可行域的顶点。定理定理3.3.若可行域有界，线性规划的目标函数一定可以在可行域若可行域有界，线性规划的目标函数一定可以在可行域的顶点上达到最优。的顶点上达到最优。定理定理4.4.线性规划如果有可行解，则一定有基可行解；如果有最线性规划如果有可行解，则一定有基可行解；如果有最优解，则一定有基可行解是最优解。优解，则一定有基可行解是最优解。三、线性规划问题的解概念三、线性规划问题的解概念 2x1=16 2x2=10 x1 x2 4 8 10 3 5 8 3x1+4 x2=32 0 A B C D 敬请指教！谢谢！
