第一章线性规划 线性规划模型model 线性规划的图解法与灵敏度分析 线性规划的基本概念 LP的基本定理 单纯形法 simplexmethod单纯形法的进一步讨论小结 引例标准型---------化标准型线性规划的标准形式目标函数:max约束条件 :=变量符号 :≥0极小换极大,目标函数乘负1等式右端righthandside负变正,同乘负1不等式约束变等式,减剩余(sur plus)变量,加松弛(slack)变量无约束变量变两个有约束变量相减对于负变量,求取相反数变 量化标准型线性规划的图解法thegraphicalsolutionmax z=x1+3x2 s.t. x1+x 2≤6 -x1+2x2≤8 x1≥0,x2≥0x1+x2=6-x1+2x2=8求解方程组得:x2 =14/3,x1=4/3为最优解目标函数值为z=x1+3x2=46/3解的几种情况:唯一解无穷多解 (多重解)无有限最优解(无界解)无可行解灵敏度分析(SensitivityAnalysis)灵敏度分析 是要在求得最优解以后,解决以下几方面的问题:线性规划问题中的各系数在什么范围内变化,不会影响已获得的最优基;如果系数的变化 超过以上范围,如何在原来最优解的基础上求得新的最优解;当线性规划问题增加一个新的变量或新的约束,如何在原来最优解的基础上获得新的 最优解。即分析价值系数Cj的变化分析bj的变化分析技术系数aij的变化 增加变量x增加约束条件灵敏度分析的图解法max z=x1+3x2 s.t. x1+x 2≤6 -x1+2x2≤8 x1≥0,x2≥0-1≤-c1/c2≤1/2,即-1/2≤c1/c2≤ 1时最优解不变当c2=3不变,那么-3/2≤c1≤3时最优解不变。当c1=1不变,那么-1/2≤1/c2 ≤1时即c2≤-2或1≤c2最优解不变。其他情况:资源变多,可行域变大。可行解变化。如图。作业1:(混合配 料问题)绿色饲料公司生产雏鸡、蛋鸡、肉鸡三种饲料。这三种饲料是由A、B、C三种原料混合而成。产品的规格要求、产品单价、日销售量、 原料单价见下表:作业2:P351.4(2)分别用图解法和单纯形法求解下述线性规划问题,并对照指出对应图解法中可 行域的哪一个顶点。max z=2x1+x2 s.t. 3x1+5x2≤15 6x1+2x2≤24 x1≥0, x2≥0AB备用资源 人1230 财3260物 0224利润4050例 生产计划问题A,B各生产多少,可获最大利润?x1+2x2?30 3x1+2x2?602x2?24 x1,x2?0maxZ=40x1+50x2解:设产品A,B产量分别为变量x1, x2决策变量约束条件目标函数例求:最低成本的添加剂的原料混合方案维生素原料123 4每单位添加剂中维生素最低含量A4612 12B117514 C02138原料单位成本2 568解:设每单位添加剂中原料i的用量为xi(i=1,2,3,4)mi nZ=2x1+5x2+6x3+8x44x1+6x2+x3+2x4?12x1 +x2+7x3+5x4?142x2+x3+3x4?8x i?0(i=1,…,4)决策变量约束条件目标函数一般式Max(min)Z=C1X1+C2X2+…+CnXn a11X1+a12X2+…+a1nXn?(=,?)b1a21X1+a22X2+…+a2nXn?(=,?)b2 ………am1X1+am2X2+…+amnXn?(=,?)bmXj?0(j=1,…,n)线性 规划模型矩阵形式线性规划模型的结构目标objective函数:max(imize),min约束条件constraints :≥,=,≤变量(variable)符号::≥0,≤0线性规划的标准形式standardform目标函数:max 约束条件 :=变量符号 :≥0SubjecttoNonnegativeconstraintsfunctionalco nstraints例可行域、可行解目标函数等值线最优解64-860x1x2可行域目标函数等值线最优解64-860x1x2maxz=x1+2x2受资金和生产能力的限制,每天只能生产30吨,问如何安排生产计划才能获利最大?试建立模型。 |
|