线性规划建模及单纯形法
思考题
主要概念及内容：
线性规划模型结构（决策变量，约束不等式、等式，目标函数）；线性规划标准形式；可行解、可行集（可行域、约束集），最优解；基、基变量、非基变量、基向量、非基向量；基本解、基本可行解、可行基、最优基。 复习思考题：
1、线性规划问题的一般形式有何特征？
2、建立一个实际问题的数学模型一般要几步？
3、两个变量的线性规划问题的图解法的一般步骤是什么？
4、求解线性规划问题时可能出现几种结果，哪种结果反映建模时有错误？
5、什么是线性规划的标准型，如何把一个非标准形式的线性规划问题转化成标准形式。 6、试述线性规划问题的可行解、基本解、基本可行解、最优解、最优基本解的概念及它们之间的相互关系。
7、试述单纯形法的计算步骤，如何在单纯形表上判别问题具有唯一最优解、有无穷多个最优解、无界解或无可行解。
8、在什么样的情况下采用人工变量法，人工变量法包括哪两种解法？
9、大M 法中，M 的作用是什么？对最小化问题，在目标函数中人工变量的系数取什么？最大化问题呢？
10、什么是单纯形法的两阶段法？两阶段法的第一段是为了解决什么问题？在怎样的情况下，继续第二阶段？ 作业习题
1、将下列线性规划问题化为标准型
maxz?3x1?5x2?4x3?2x4minf?3x1?x2?4x3?2x4?2x1?6x2?x3?3x4?18?2x1?3x2?x3?2x4??51?（1）??x1?3x2?2x3?2x4?13 （2）?3x1?2x2?2x3?x4??7
???x?4x?3x?5x?9234?1?2x1?4x2?3x3?2x4?15???x1,x2,x4?0?x1,x2?0,x4?02、（1）求出下列不等式组所定义的多面体的所有基本解和基本可行解（极点）：
?2x1?3x2?3x3?6???2x1?3x2?4x3?12 ?x,x,x?0?123（2）对下述线性规划问题找出所有基本解,指出哪些是基本可行解,并确定最优解.
maxz?3x1?x2?2x3?12x1?3x2?6x3?3x4?9?8x?x?4x?2x?10 ?1235??3x1?x6?0?xj?0(j1,??,6)?3、用图解法求解下列线性规划问题
maxz?x1?2x2?2x1?x2?6?4x1?7x2?56（1）? （2） 3x?2x?12?1?23x?5x?15??12x?3?1?x,x?0?12?x,x?0?12
4、在以下问题中，列出所有的基，指出其中的可行基，基础可行解以及最优解。 maxz?x1?2x2?x3minz??x1?3x2?x1?x2?2x3?6??x1?4x2?x3?4?x,x,x?0?123
5、用单纯形法求解以下线性规划问题
maxz?3x1?2x2maxz?x2?2x3?x1?3x2?4x3?12?2x1?3x2?3（1）? （2）?
2x?x?12?x?x?5?2?132?x,x,x?0?x,x?0?123?126、用大M法及两阶段法求解以下线性规划问题
maxz?x1?3x2?4x3minf?x1?3x2?x3?3x1?2x2?13?x1?x2?x3?3（1）? （2）? ?x2?3x3?17??x1?2x2?2??2x?x?x?133?12??x1?5x2?x3?4???x1,x2,x3?0?x1,x2,x3?07、某工厂生产过程中需要长度为 3.1 米、2.5 米和 1.7 米的同种棒料毛坯分别为 200 根、100 根和 300 根。现有的原料为 9 米长棒材，问如何下料可使废料最少？
8、有1，2，3，4四种零件均可在设备A或设备B上加工，已知在这两种设备上分别加工一个零件的费用如下表所示。又知设备A或B只要有零件加工均需要设备的启动费用，分别为100元和150元。现要求加工1，2，3，4零件各三件。问应如何安排使总的费用最小。试建立线性规划模型。
9、某造船厂根据合同从当年起连续三年末各提供四条规格相同的大型客货轮。已知该厂这三年内生产大型客货轮的能力及每艘客货轮成本如下表所示：
已知加班生产时,每艘客货轮成本比较正常时高出60万元；又知造出来的客货轮若当年不交货,每艘每年积压一年造成损失为30万元。在签定合同时，该厂已积压了两艘未交货的客货轮，而该厂希望在第三年未完成合同还能储存一艘备用。问该厂如何安排每年
客货轮的生产量，在满足上述各项要求的情况下总的生产费用最少？试建立线性规划模型，不求解。
线性规划问题的对偶及灵敏度分析
思考题
主要概念及内容：
对偶问题，对称形式、非对称形式；对偶定理；对偶单纯形法；灵敏度分析。 复习思考题：
1、对偶问题和它的经济意义是什么？
2、简述对偶单纯形法的计算步骤。它与单纯形法的异同之处是什么？ 3、什么是资源的影子价格？它和相应的市场价格之间有什么区别？
4、如何根据原问题和对偶问题之间的对应关系，找出两个问题变量之间、解及检验数之间的关系？
5、利用对偶单纯形法计算时，如何判断原问题有最优解或无可行解？
6、在线性规划的最优单纯形表中，松弛变量（或剩余变量） ，其经济意义是什么？ 7、在线性规划的最优单纯形表中，松弛变量 的检验数 ，其经济意义是什么？
8、关于价值系数和资源常量 单个变化对线性规划问题的最优方案及有关因素将会产生什么影响？有多少种不同情况？如何去处理？ 9、线性规划问题增加一个变量，对它原问题的最优方案及有关因素将会产生什么影响？如何去处理？ 10、线性规划问题增加一个约束，对它原问题的最优方案及有关因素将会产生什么影响？如何去处理？ 作业习题
1、写出下列问题的对偶规划
2、试用对偶理论讨论下列原问题与它们的对偶问题是否有最优解
3、考虑如下线性规划
（1）写出对偶规划。
（2）用单纯形法解对偶规划，并在最优表中给出原规划的最优解。 （3）说明这样做比直接求解原规划的好处。
4、用对偶单纯形方法，求解下面问题
minf?5x1?2x2?4x3?3x1?x2?2x3?4（1）??6x1?3x2?5x3?10?x,x,x?0?1235、考虑下面线性规划
maxz?2x1?3x2?2x1?2x2?x3?12?x?2x?x?8124? ?4x?x?16?15?4x?x?126?2??x1,x2,x3,x4,x5,x6?0maxz??x1?2x2?3x3?2x1?x2?x3?4 （2）??x1?x2?2x3?8??x2?x3?2??x1,x2,x3?0
其最优单纯形表为： 基变量 x1 x2 x3 x4 x5 x6 x3 0 4 4 2 -14 x1 x6 x2 0 0 1 -1 -1/4 0 1 0 0 0 1/4 0 0 0 0 -2 1/2 1 0 0 0 -3/2 -1/8 0 0 0 0 -3/2 -1/8 0 ?j
试分析如下问题
（1）分别对cj 进行灵敏度分析。 （2）对bi 进行灵敏度分析。 （3）当cj=时，求新最优解。 （4）当bi= 时，求新最优解。
（5）增加一个约束 ，问对最优解有何影响？ （6）确定保持当前最优解不变的P1的范围。
6、已知某工厂计划生产A1 、A2 、A3三种产品，各产品需要在甲、乙、丙设备上加工。有关数据如下
试问：
（1）如何充分发挥设备能力，使工厂获利最大；
（2）若为了增加产量，可借用别的工厂的设备甲，每月可借用60台时，租金1.8万元，问是否合算？
（3）若另有两种新产品A4、A5 ，其中每件A4 需用设备甲12台时、乙5台时、丙10台时，每件获利2.1千元；每件A5需用设备甲4台时、乙4台时、丙12台时，每件获利1.87千元。如 甲、乙 、丙 设备台时不增加，分别回答这两种新产品投产是否合算？ （4）增加设备乙的台时是否可使企业总利润进一步增加？ 7、已知某求极大化线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形表如下表所示，求表中各括弧内未知数的值。 Cj 3 2 2 0 0 0 b x1 x2 x3 x4 x5 x6 XB CB x4 x5 x6 1 1 1 1 0 0 (B) (A) 1 2 0 1 0 15 2 (C) 1 0 0 1 20 3 2 2 0 0 0 ?j ? x4 x1 ? ? x2 ?j 0 0 (D) (L) -1/4 -1/4 5/4 1 0 (E) 0 3/4 (I)0 25/4 0 1 (F) 0 (H) 1/2 5/2 0 (K) (G) 0 -5/4 (J)
运筹学作业习题
