运筹学作业标准答案 (教师用)
·No.1 线性规划
1
1、某织带厂生产A、B两种纱线和C、D两种纱带，纱带由专门纱线加工而成。这四种产品的产值、成本、加工工时等资料列表如下： 产品 项目 单位产值 (元) 单位成本 (元) 单位纺纱用时 (h) 单位织带用时 (h) A 168 42 3 0 B 140 28 2 0 C 1050 350 10 2 D 406 140 4 0.5 工厂有供纺纱的总工时7200h，织带的总工时1200h。 (1) 列出线性规划模型，以便确定产品的数量使总利润最大；
(2) 如果组织这次生产具有一次性的投入20万元，模型有什么变化？对模型
的解是否有影响？
解：(1)设A的产量为x1，B的产量为x2，C的产量为x3，D的产量为x4，则
有线性规划模型如下：
max f(x)=(168?42)x1 +(140?28)x2 +(1050?350)x3 +(406?140)x4
=126 x1 +112 x2 +700 x3 +266 x4
?3x1?2x2?10x3?4x4?7200?s.t. ? 2x3?0.5x4?1200
?xi?0, i?1,2,3,4?(2)如果组织这次生产有一次性的投入20万元，由于与产品的生产量无关，
故上述模型只需要在目标函数中减去一个常数20万，因此可知对模型的解没有影响。 2、将下列线性规划化为极大化的标准形式
minf(x)?2x1?3x2?5x3解：将约束条件中的第一行的右端项变为正值，并添加松弛变量x4，在第二行添加人工变量x5，? x1? x2? x3??5???6x1?7x2?9x3?16 将第三行约束的绝对值号打开，变为两个不等式，s.t. ?|19x1?7x2?5x3|?13分别添加松弛变量x6, x7，并令x?xx????，则?333??x1,x2?0, x3?不限有
max[?f(x)]= {?2 x1 ?3 x2 ?5(x3??x3??)+0 x4 ?M x5+0 x6 +0 x7}
?? x3???x4?5 ?x1 ?x2 ?x3????9x3?? ?x5?16 ?6x1?7x2?9x3????5x3?? ?x6?13 s.t. ? 19x1?7x2?5x3??19x?7x?5x??5x?? ?x?1312337??,x3??,x4,x5,x6,x7?0?x1,x2,x3?运筹学作业标准答案 (教师用)
3、用单纯形法解下面的线性规划
maxf(x)?2x1?5x2?3x3?3x1?2x2?x3?610???x1?6x2?3x3?125 s.t. ???2x1?x2?0.5x3?420?x1,x2,x3?0, ?2
解：在约束行1,2,3分别添加x4, x5, x6松弛变量，有初始基础可行解和单纯形法迭代步骤如下： CB XB 0 x4 0 x5 0 x6 OBJ= 0 CB XB 0 x4 5 x2 0 x6 OBJ= 625/6 2 x1 3 ?1 ?2 0 2 2 Cj ? b x1 1705/3 (10/3) 125/6 ?1/6 2395/6 ?11/6 zj ? ?5/6 cj - zj 17/6 Cj ? b 610 125 420 zj ? cj - zj 2 x1 1 0 0 2 0 5 x2 2 (6) 1 0 5 5 x2 0 1 0 5 0 5 x2 0 1 0 5 0 3 x3 ?1 3 1/2 0 3 3 x3 ?2 1/2 0 5/2 1/2 3 x3 ?3/5 (2/5) ?11/10 4/5 11/5 0 x4 1 0 0 0 0 0 x4 1 0 0 0 0 0 x4 3/10 1/20 11/20 17/20 0 0 x5 0 1 0 0 0 0 x5 ?1/3 1/6 ?1/6 5/6 ?5/6 0 x5 ?1/10 3/20 ?7/20 11/20 ?11/20 0 x5 1/8 3/8 1/16 11/8 ?11/8 0 x6 0 0 1 0 0 0 x6 0 0 1 0 0 0 x6 0 0 1 0 0 bi/aij* 610/2 125/6* 420/1 bi/aij* 170.5 － － bi/aij* － 125.125 － Cj ? CB XB b 2 x1 341/2 5 x5 197/4 0 x6 2847/4 OBJ= 2349/4 zj ? cj - zj 2 5 3 0 0 Cj ? CB XB b x1 x2 x3 x4 x6 bi/aij* 2 x1 1955/8 1 3/2 0 3/8 0 3 x3 985/8 0 5/2 1 1/8 0 0 x6 13555/16 0 11/4 0 11/16 1 OBJ= 6865/8 zj ? 2 21/2 3 9/8 0 cj - zj 0 0 0 ?11/2 ?9/8 答：最优解为x1 =244.375, x2 =0, x3 =123.125, 剩余变量x6 =847.1875；最优解
的目标函数值为858.125。
运筹学作业标准答案 (教师用)
No.2 两阶段法和大M法 1、用两阶段法解下面问题：
minf(x)?4x1?6x2?x1?2x2?80?s.t. ?3x1?x2?75?x,x?012?3
解：将原问题变为第一阶段的标准型
maxf(x)?0?x1?0?x2?x5?x6?x1?2x2?x3?x5?80?s.t. ?3x1?x2?x4?x6?75?x,x,x,x,x,x?0?123456
第一阶段单纯形表 CB ?1 ?1 OBJ= CB ?1 0 OBJ= CB 0 0 OBJ= 第二阶段 CB ?6 ?4 OBJ= XB x2 x1 ?254 Cj ? b 33 14 zj ? cj - zj ?4 x1 0 1 ?4 0 ?6 x2 1 0 ?6 0 0 0 x3 x4 1/5 ?3/5 1/5 ?2/5 14/5 2/5 ?14/5 ?2/5 bi/aij* XB x5 x6 ?155 XB x5 x1 ?55 XB x2 x1 0 Cj ? b 80 75 zj ? cj - zj Cj ? b 55 25 zj ? cj - zj Cj ? b 33 14 zj ? cj - zj 0 x1 1 (3) ?4 4 0 x1 0 1 0 0 0 x1 0 1 0 0 0 x2 2 1 ?3 3 0 x2 (5/3) 1/3 ?5/3 5/3 0 x2 1 0 0 0 0 x3 ?1 0 1 ?1 0 x3 ?1 0 1 ?1 0 x3 ?3/5 1/5 0 0 0 x4 0 ?1 1 ?1 0 x4 1/3 ?1/3 ?1/3 1/3 0 x4 1/5 ?2/5 0 0 ?1 x5 1 0 ?1 0 ?1 x5 1 0 ?1 0 ?1 x5 3/5 ?1/5 0 ?1 ?1 x6 0 1 ?1 0 ?1 x6 ?1/3 1/3 1/3 ?4/3 bi/aij* 80 75/3* bi/aij* 55?3/5* 25?3 ?1 x6 bi/aij* ?1/5 2/5 0 ?1 答：最优解为x1 =14，x2 =33，目标函数值为254。
运筹学作业标准答案 (教师用)
2、用大M法解下面问题，并讨论问题的解
maxf(x)?10x1?15x2?12x3?5x1?3x2?x3?9???5x1?6x2?15x3?15s.t. ?2x1?x2?x3?5??x1,x2,x3?0, ?4
解：第1、2行约束条件添加x4, x5松弛变量，第3行添加x6剩余变量和x7人工变量，有如下初始单纯形表和迭代步骤： CB 0 0 ?M OBJ= XB x4 x5 x7 ?5M Cj ? b 9 15 5 zj ? cj - zj 10 x1 (5) ?5 2 ?2M 10+2M 15 x2 3 6 1 ?M 15+M 12 x3 1 15 1 ?M 12+M 0 x4 1 0 0 0 0 0 x5 0 1 0 0 0 0 x6 0 0 ?1 M ?M ?M x7 0 0 1 ?M 0 CB 10 0 ?M XB x1 x5 x7 Cj ? b 9/5 24 7/5 zj ? cj - zj 10 x1 1 0 0 10 0 15 x2 3/5 9 ?1/5 6+M/5 9?M/5 12 x3 1/5 (16) 3/5 2?3M/5 0 x4 1/5 1 ?2/5 2+2M/5 0 x5 0 1 0 0 0 0 x6 0 0 ?1 M ?M ?M x7 0 0 1 ?M 0 OBJ= 18?7M/5 10+3M/5 ?2?2M/5 CB 10 12 ?M OBJ= XB x1 x3 x7 33?M/2 Cj ? b 3/2 3/2 1/2 zj ? cj - zj 10 x1 1 0 0 10 0 15 x2 39/80 9/16 ?43/80 93/8+ 43M/80 27/8 ?43M/80 12 x3 0 1 0 12 0 0 x4 3/10 1/20 11/20 21/8+ 7M/16 ?21/8 ?7M/16 0 x5 ?1/10 3/20 ?7/20 5/8+ 3M/80 ?5/8 ?3M/80 0 x6 0 0 ?1 M ?M ?M x7 0 0 1 ?M 0 答：最后单纯形表中检验数都小于等于0，已满足最优解判定条件，但人工变量x7仍未迭代出去，可知原问题无可行解(无解)。
运筹学作业标准答案 (教师用)
No.3 线性规划的对偶问题
1、写出下列线性规划问题的对偶问题：
maxf(x)?2x1?3x2?5x35
解：对偶问题为
ming(y)?5y1?4y2?6y3y1?2y2 ?2??y1 ?y3?3? ?s.t.??y1?y2?y3??5?y1? y3?0???y1?0,y2?0,y3?不限(1)
? x1?x2?x3?x4?5? 2x1 ?x3 ?4?s.t. ?? x2?x3?x4?6?x1?0,x2,x3?0, x4?不限?
?x1?6 ?x??2 ?1?x2?14 ?x2?4 ??x3??8? x3??12???x1?不限,x2?0,x3?0minf(x)?4x1?3x2?8x3 (2)
??2?x1?6?s.t. ?4?x2?14??12?x??83?
解：原问题的约束条件可改写为右式
maxg(y)?6y1?2y2?14y3?4y4?8y5?12y6? y1?y2 ?4 ? y3 ?y4 ??3?s.t. ? y5?y6?8???y1,y3,y5?0, y2,y4,y6?0令改写后约束条件每行对应的对偶变量为y1,...,y6，则有对偶规划如下：