运筹学--第2节(线性规划-标准型).ppt

第一章 线性规划及单纯形法 * 第一章 线性规划及单纯形法 * 第一章 线性规划及单纯形法 * 第一章 线性规划及单纯形法 * 第一章 线性规划及单纯形法 * 第一章 线性规划及单纯形法 * 第一章 线性规划及单纯形法 * 第一章 线性规划及单纯形法 * 第一章 线性规划及单纯形法 * 第一章 线性规划及单纯形法 * 第一章 线性规划及单纯形法 * 第一章 线性规划及单纯形法 * 第一章 线性规划及单纯形法 * 第一章 线性规划及单纯形法 * 第一章 线性规划及单纯形法 * 第一章 线性规划及单纯形法 * 第一章 线性规划及单纯形法 * 第一章 线性规划及单纯形法 * 第一章 线性规划及单纯形法 * 第一章 线性规划及单纯形法 * 第一章 线性规划及单纯形法 * 第一章 线性规划及单纯形法 * （2）约束条件 x3为松弛变量 x4为剩余变量 松弛变量或剩余变量在实际问题中分别表示未被充分利用的资源和超出的资源数，均未转化为价值和利润，所以引进模型后它们在目标函数中的系数均为零。 当约束条件为“≤”时， 当约束条件为“≥”时， x1 +2x2 +x3 =30 3x1 +2x2 +x4 =60 2x2 +x5 =24 x1 , …, x5 ?0 转化为：maxZ=40x1+ 50x2+0·x3 +0·x4+0·x5 x1 + 2x2 ? 30 3x1 + 2x2 ? 60 2x2 ? 24 x1，x2 ? 0 例：max Z= 40x1 +50x2 松弛变量 例: 4x1 + 6x2 + x3+2x4 ?12 x1 + x2 +7x3+5x4 ?14 2x2 + x3+3x4 ? 8 xi ? 0 (i =1,…,4) 4x1+6x2+x3 +2x4 - x5 =12 x1+ x2+7x3+5x4 - x6 =14 2x2+ x3+3x4 - x7 =8 x1 , …, x7 ?0 剩余变量 （3）右端常数 右端项b＜0时，只需将等式或不等式两端同乘(－1)，则等式右端项必大于零。 （4）变量 3 x1 -3 x1 +2x2 ? 8 x1 - x1 – 4x2 ? 14 x1 , x1 ,x2 ?0 a、x ? 0的情况， 3x1+2x2 ? 8 x1 –4x2? 14 x2?0 令x1= x1- x1 b、x取值无约束的情况。 令x ＝-x。 令x= x-x x1 +x2 ? 11 x1? 16 x1 , x2 ?0 c、x两边有约束的情况。 x1+x2 ? 5 -6 ? x1 ? 10 x2?0 -6+6 ? x1+6 ? 10+6 令x1 = x1 +6 0 ? x1? 16 x1 +x2+ x3 = 11 x1 +x4 = 16 x1 , x2 , x3 , x4 ,,?0 将 min Z = -x1+2x2 –3x3 x1+x2 +x3? 7 x1 -x2 +x3 ?2 x1，x2?0，x3无限制 化为标准型 例： 解：① 令x3 =x4 - x5 ② 加松弛变量x6 ③加剩余变量x7 ④ 令Z= -Z maxZ= x1 –2x2 +3x4 –3x5 x1 +x2 +x4 -x5 +x6 =7 x1 -x2 +x4 -x5 -x7 =2 x1 , x2 , x4 , … , x7 ?0 min Z = -x1+2x2 –3x3 x1+x2 +x3? 7 x1 -x2 +x3 ?2 x1，x2?0，x3无限制 练 习 补充作业、运输问题 从仓库到工厂运送单位原材料的成本，工厂对原材料的需求量，仓库目前库存分别如表所示，求成本最低的运输方案。 工厂 仓库