运筹学线性规划问题与图解法.pptx

运筹学运筹学（OR:operational research(英英)operations research(美美)）主讲：卢安文2 线性规划（LP:Linear Programming）问题与图解法 2.1 问题的提出v生产计划问题v某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表产品A产品B资源限量劳动力设 备原材料9434510360200300利润元/kg70120问题：如何安排生产计划，使得获利最多？v步骤：1、确定决策变量：设生产A产品x1kg,B产品x2kg2、确定目标函数：maxZ=70X1+120X23、确定约束条件：人力约束 9X1+4X2360 设备约束 4X1+5X2 200 原材料约束3X1+10X2 300 非负性约束X10 X20v配料问题:每单位原料i含vitamin如下：原料原料 A B 每单位成本每单位成本 1 4 1 0 2 2 6 1 2 5 3 1 7 1 6 4 2 5 3 8 每单位添每单位添 加剂中维生加剂中维生 12 14 8 素最低含量素最低含量求：最低成本的原料混合方案求：最低成本的原料混合方案解：设每单位添加剂中原料解：设每单位添加剂中原料i的用量为的用量为xi(i=1,2,3,4)minZ=2x1+5x2+6x3+8x4 4x1+6x2+x3+2x4 12 x1+x2+7x3+5x4 14 2x2+x3+3x4 8 xi 0(i=1,4)线性规划问题的基本特征线性规划问题的基本特征v决策变量：向量决策变量：向量(x1 xn)T 代表一个具体的代表一个具体的方案，一般有方案，一般有xi非负非负v约束条件：线性等式或不等式约束条件：线性等式或不等式v目标函数：目标函数：Z=(x1 xn)线性式，求线性式，求Z极大极大（Max）或极小）或极小(Min)线性规划问题的一般形式线性规划问题的一般形式Max(min)Z=C1X1+C2X2+CnXna11X1+a12X2+a1nXn (=,(=,)b)b1 1a21X1+a22X2+a2nXn (=,(=,)b)b2 2 am1X1+am2X2+amnXn (=,(=,)b)bm mXj j 0(0(j=1,n)简写式向量式v其中：C=(c1,c2,cn)价值向量vX=(x1,x2,xn)T决策向量vPj=(a1j.a2j,amj)T系数向量vB=(b1,b2,bn)T 资源向量矩阵式其中系数矩阵2.2线性规划问题的线性规划问题的图解法图解法v1图解法用于求解两个决策变量的线性规划问图解法用于求解两个决策变量的线性规划问题，图解法简单直观，有助于了解线性规划题，图解法简单直观，有助于了解线性规划问题求解的基本原理。问题求解的基本原理。v如：如：maxZ=70X1+120X2 人力约束 9X1+4X2360 设备约束 4X1+5X2 200 原材料约束3X1+10X2 300 非负性约束X10 X20 .90 80 60 40 20 0 20 40 60 80 100 x1 x29x1+4x2 3604x1+5x2 200 3x1+10 x2 300ABCDEFGHIZ=70 x1+120 x2v图中阴影部分为可行域（满足约束条件的点的集可行域（满足约束条件的点的集合）合）v可行解：满足约束条件的解可行解：满足约束条件的解v可行域是可行解的集合可行域是可行解的集合v当等值线Z=70 x1+120 x2 v平行移动到 H点时Z取得最大值 v此时，x1=20,x2=24vZ=70*20+120*24 v设备和原材料恰好使用完，而人力节余84个单位v即：设备约束和原材料约束条件取等号，而人力约束条件仍然取不等号 2线性规划问题的解线性规划问题的解v可行解：满足约束条件的解可行解：满足约束条件的解X=(x1,x2,xn)Fv可行域可行域:可行解的集合可行解的集合(线性规划问题的线性规划问题的可行域可行域一般为凸集一般为凸集)v最优解：使目标函数达到最优的可行解最优解：使目标函数达到最优的可行解v若若线性规划问题有唯一线性规划问题有唯一最优解，则最优解一最优解，则最优解一定在可行域的顶点处取得定在可行域的顶点处取得v线性规划问题可能存在无穷多个线性规划问题可能存在无穷多个最优解（最优解（若若线性规划问题有两个线性规划问题有两个最优解，则一定有最优解，则一定有无穷多个无穷多个最优解最优解）v线性规划问题可能存在无界线性规划问题可能存在无界解（解（即无最优解）即无最优解）v线性规划问题可能存在无可行线性规划问题可能存在无可行解（解（此时无最优解，此时无最优解，可行域为空集可行域为空集）3 线性规划问题的标准型线性规划问题的标准型v目标函数极大化（或极小化）v约束条件为等式，且右端常数全为非负v决策变量非负化标准型maxZ=70X1+120X2 maxZ=70X1+120X2+0S1+0s2+0s3 9X1+4X2360 9X1+4X2+S1 =360 4X1+5X2 200 4X1+5X2 +s2 =200 3X1+10X2 300 3X1+10X2 +s3=300 X10 X20 Xj0 j=1,2 其中S1，s2，s3 0为松弛变量化标准型minZ=x1+2x2-3x3 maxZ=x12x2+3(x3x”3)x1+x2+x3 9 x1+x2+x3 x”3+s1=9-x1-2x2+x3 2 x12x2+x3 x”3 s2=2 3x1+x2-3x3=5 3x1+x23(x3 x”3)=5 x1 0 x2 0 x3无约束 x1 0 x2 0 x3 0 x”3 0 s10 s2 0 其中s1 为松弛变量，s2为剩余变量 x3x3x”3+0s1+0s2线性规划的标准型线性规划的标准型 v下列情况具体处理v若要求目标函数求最大化v若约束方程为不等式：非负松弛变量，非负剩余变量v若变量不是非负：非正，自由变量，v右边为非正v任何形式的线性规划模型都可以化为标准型。