,.
No.1 线性规划
1、某织带厂生产A、B两种纱线和C、D两种纱带，纱带由专门纱线加工而成。这四种产品的产值、成本、加工工时等资料列表如下： 产品 项目 单位产值 (元) 单位成本 (元) 单位纺纱用时 (h) 单位织带用时 (h) 168 42 3 0 140 28 2 0 1050 350 10 2 406 140 4 0.5 A B C D 工厂有供纺纱的总工时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? x1? x2? x3??5???6x1?7x2?9x3?16 s.t. ?|19x1?7x2?5x3|?13???x1,x2?0, x3?不限解：将约束条件中的第一行的右端项变为正值，
并添加松弛变量x4，在第二行添加人工变量
x5，将第三行约束的绝对值号打开，变为两
个不等式，分别添加松弛变量x6, x7，并令
，则有
max[?f(x)]= {?2 x1 ?3 x2 ?5()+0 x4 ?M x5+0 x6 +0 x7}
,.
?? x3???x4?5 ?x1 ?x2 ?x3???6x?7x?9x??9x?? ?x?16 12335????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??x?6x?3x?125 ?123s.t. ???2x1?x2?0.5x3?420?x1,x2,x3?0, ?解：在约束行1,2,3分别添加x4, x5, x6松弛变量，有初始基础可行解和单纯形法迭代步骤如下： Cj ? b 610 125 420 2 5 3 0 0 0 CB 0 0 0 OBJ= XB x4 x5 x6 0 x1 3 ?1 ?2 0 2 2 x2 2 (6) 1 0 5 5 x3 ?1 3 1/2 0 3 3 x4 1 0 0 0 0 0 x5 0 1 0 0 0 0 x6 0 0 1 0 0 0 bi/aij* 610/2 125/6* 420/1 zj ? cj - zj Cj ? b CB 0 5 0 XB x4 x2 x6 x1 x2 0 1 0 5 0 5 x3 ?2 1/2 0 5/2 1/2 3 x4 1 0 0 0 0 0 x5 ?1/3 1/6 ?1/6 5/6 ?5/6 0 x6 0 0 1 0 0 0 bi/aij* 170.5 － － 1705/3 (10/3) 125/6 ?1/6 2395/6 ?11/6 OBJ= 625/6 zj ? cj - zj Cj ? b 341/2 197/4 2847/4 ?5/6 17/6 2 CB 2 5 0 XB x1 x5 x6 x1 1 0 0 2 0 x2 0 1 0 5 0 x3 x4 x5 x6 0 0 1 0 0 bi/aij* － 125.125 － ?3/5 3/10 ?1/10 (2/5) 1/20 3/20 ?11/111/20 ?7/20 0 4/5 17/20 11/20 11/5 0 ?11/20 OBJ= 2349/4 zj ? cj - zj ,. Cj ? b 1955/8 985/8 13555/16 2 5 3 0 0 0 CB 2 3 0 XB x1 x3 x6 x1 1 0 0 2 0 x2 3/2 5/2 11/4 21/2 ?11/2 x3 0 1 0 3 0 x4 3/8 1/8 x5 1/8 3/8 x6 0 0 1 0 0 bi/aij* 11/16 1/16 9/8 11/8 OBJ= 6865/8 zj ? cj - zj ?9/8 ?11/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?0?12第一阶段单纯形表
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?1234560 0 0 0 ?1 ?1
Cj ? b 80 75 CB ?1 ?1 XB x5 x6 x1 1 (3) ?4 4 0 x2 2 1 ?3 3 0 x3 ?1 0 1 ?1 0 x4 0 ?1 1 ?1 0 x5 1 0 ?1 0 ?1 x6 0 1 ?1 0 ?1 bi/aij* 80 75/3* OBJ= ?155 zj ? cj - zj Cj ? b 55 25 CB ?1 0 OBJ= XB x5 x1 ?55 x1 0 1 0 0 0 x2 (5/3) 1/3 ?5/3 5/3 0 x3 ?1 0 1 ?1 0 x4 1/3 ?1/3 ?1/3 1/3 0 x5 1 0 ?1 0 ?1 x6 bi/aij* * ?1/3 55?3/51/3 1/3 ?4/3 ?1 25?3 zj ? cj - zj Cj ? b 33 14 CB 0 0 OBJ= 第二阶段 XB x2 x1 0 x1 0 1 0 0 ?4 x2 1 0 0 0 ?6 x3 ?3/5 1/5 0 0 0 x4 1/5 0 0 0 x5 x6 bi/aij* 3/5 ?1/5 0 ?1 0 ?1 ?2/5 ?1/5 2/5 zj ? cj - zj Cj ? b 33 14 CB ?6 ?4 XB x2 x1 x1 0 1 ?4 0 x2 1 0 ?6 0 x3 ?3/5 1/5 14/5 x4 1/5 ?2/5 2/5 bi/aij* OBJ= ?254 zj ? cj - zj ?14/5 ?2/5
运筹学课后习题集规范标准答案林齐宁版本北邮出版社
