熊伟编《运筹学》Ch1 线性规划.ppt

练习:饼干生产问题 设X1表示I型饼干日产量，X2表示II型饼干日产量（单位为吨），z表示I型和II型饼干所创造的日总利润 练习：运输问题 设Xij表示从仓库Ai调到商场Bj的调拨数，（i=1,2;j=1,2,3）以 台为单位，则有以下LP模型： max z=5x1+4x2 s.t. 3x1+ 5x2≤15 2x1+ x2≤5 2x1+ 2x2≤11 x1 ≥0, x2≥0 非标准型LP模型转化为标准型LP模型 一、目标函数是极小化的转化 例： 四、决策变量有上下界的转换 线性规划的可行域是凸集 线性规划的最优解在极点上 进基变量、离基变量、基变换 练习题2 设X1表示I型饼干日产量，X2表示II型饼干日产量（单位为吨），z表示I型和II型饼干所创造的日总利润 转化为标准模型 引入松弛变量s1 , s2 , s3 ≥ 0 将主元素a22化为1 两阶段单纯形法与大M单纯形法的目的类似，将人工变量从基变量中换出，以求出原问题的初始基本可行解。将问题分成两个阶段求解，第一阶段的目标函数是 约束条件是加入人工变量后的约束方程，当第一阶段的最优解中没有人工变量作基变量时，得到原线性规划的一个基本可行解，第二阶段就以此为基础对原目标函数求最优解。当第一阶段的最优解w≠0时，说明还有不为零的人工变量是基变量，则原问题无可行解。 1.5 单纯形法 Simplex Method 2. 两阶段单纯形法 【例1.22】用两阶段单纯形法求解例19的线性规划。 【解】标准型为 在第一、三约束方程中加入人工变量x6、x7后，第一阶段问题为 用单纯形法求解，得到第一阶段问题的计算表如下： 1.5 单纯形法 Simplex Method Cj 0 0 0 0 0 1 1 b CB XB x1 x2 x3 x4 x5 x6 x7 1 0 1 x6 x5 x7 －4 1 2 3 －1 －2 1 2 [1] －1 0 0 0 1 0 1 0 0 0 0 1 4 10 1→ λj 2 －1 －2↑ 1 0 0 0 ? 1 0 0 x6 x5 x3 －6 －3 2 [5] 3 －2 0 0 1 －1 0 0 0 1 0 1 0 0 ? 3→ 8 1 λj 6 －5↑ 0 1 0 0 ? ? 0 0 0 x2 x5 x3 －6/5 3/5 －2/5 1 0 0 0 0 1 －1/5 3/5 －2/5 0 1 0 ? ? 3/5 31/5 11/5 λj 0 0 0 0 0 ? ? ? 1.5 单纯形法 Simplex Method 最优解为 最优值w=0。第一阶段最后一张最优表说明找到了原问题的一组基可行解，将它作为初始基可行解，求原问题的最优解，即第二阶段问题为 1.5 单纯形法 Simplex Method Cj 3 2 －1 0 0 b CB XB x1 x2 x3 x4 x5 2 0 －1 x2 x5 x3 －6/5 [3/5] －2/5 1 0 0 0 0 1 －1/5 3/5 －2/5 0 1 0 3/5 31/5 → 11/5 λj 5 ↑ 0 0 0 0 ? 2 3 －1 x2 x1 x3 0 1 0 1 0 0 0 0 1 1 1 0 2 5/3 2/3 13 31/3 19/3 λj 0 0 0 －5 －25/3 ? 用单纯形法计算得到下表 最优解X＝（31/3，13，19/3，0，0)T；最优值Z＝152/3 1.5 单纯形法 Simplex Method 【例1.23】用两阶段法求解例1.21的线性规划。 【解】例1.21的第一阶段问题为 用单纯形法计算如下表： 1.5 单纯形法 Simplex Method Cj 0 0 0 0 1 b CB XB x1 x2 x3 x4 x5 0 1 x3 x5 [3] 1 1 －2 1 0 0 －1 0 1 6→ 4 λj ? －1↑ 2 0 1 0 ? 0 1 x1 x5 1 0 1/3 －7/3 1/3 －1/3 0 －1 0 1 2 2 λj ? 0 7/3 1/3 1 0 ? λj≥0,得到第一阶段的最优解X=(2,0,0,0,2)T