第一章线性规划与单纯形法
一、本章考情分析：常考题型：选择填空判断计算 分值：必考知识点，30分以上,非常重要！
二、本章基本内容：１）掌握线性规划的数学模型的标准型； ２）掌握线性规划的图解法及几何意义； ３）了解单纯形法原理； ４）熟练掌握单纯形法的求解步骤；
５）能运用大Ｍ法与两阶段法求解线性规划问题； ６）熟练掌握线性规划几种解的性质及判定定理．
三、本章重难点：
重点：１）单纯形法求解线性规划问题； ２）解的性质； ３）线性规划问题建模．
难点：１）单纯形法原理的理解； ２）线性规划问题建模．
四、本章要点精讲：·要点 １ 化标准型 ·要点 ２ 图解法 ·要点 ３ 单纯形法的原理 ·要点 ４ 单纯形法的计算步骤 ·要点 ５ 单纯形法的进一步讨论
1）要点 １ 化标准型
线性规划的数学模型：Z=CX （C：价值系数） Ax=b （a：工艺或技术系数 b：资源限制）
复习思路提示：化标准型按“目标函数—资源限量—约束条件—决策变量”的顺序进行。
2）要点 ２ 图解法
线性规划解的情况有：唯一最优解、无穷多最优解、无界解、无可行解；
3）要点 ３ 单纯形法原理
解的概念与关系:基：设A是约束方程组的m*n阶系数矩阵（设n>m），其秩为m，B是A中的一个m*m阶的满秩子矩阵（B≠0的非奇异子矩阵），称 B是线性规划问题的一个基．设除基变量以外的变量称为非基变量。 基解：在约束方程组中，令所有的非基变量=0，可以求出唯一解X。 基可行解：变量非负约束条件的基解． 可行基：基可行解的基．
几个定理：１线性规划问题的可行解为基可行解的充要条件是 Ｘ的正分量所对应的系数列向量是线性独立的． ２线性规划问题的基可行解 Ｘ对应线性规划问题可行域（凸集）的顶点． ３若线性规划问题有最优解，一定存在一个基可行解是最优解．
最优解唯一时，最优解也是基最优解；当最优解不唯一时，最优解不一定是基最优解．
案例. 石华建设监理公司监理工程师配置问题
1问题重述
石华建设监理公司 ( 国家甲级 ) 侧重于国家大中型项目的监理，仅在河北省石家庄市就曾同时监理七项工程，总投资均在 5 000 万元以上．由于工程开工的时间不同，各工程工期之间相互搭接，具有较长的连续性， 1998 年监理的工程量与 1999 年监理的工程量大致相同．每项工程安排多少监理工程师进驻工地，一般是根据工程的投资、建筑规模、使用功能、施工的形象进度、施工阶段来决定的．监理工程师的配置数量随之变化．由于监理工程师从事的专业不同，他们每人承担的工作量也是不等的．有的专业一个工地就需要三人以上，而有的专业一人则可以兼管三个以上的工地．因为从事监理业的专业多达几十个，仅以高层民用建筑为例就涉及到建筑学专业、工民建 ( 结构 ) 专业、给水排水专业、采暖通风专业、强电专业、弱电专业、自动控制专业、技术经济专业、总图专业、合同和信息管理专业等，这就需要我们合理配置这些人力资源．为了方便计算，我们把所涉及的专业技术人员按总平均人数来计算，工程的施工形象进度按标准施工期和高峰施工期来划分．通常标准施工期需求的人数较容易确定．但高峰施工期就比较难确定了，原因有两点： (1) 高峰施工期各工地不是同时来到，是可以事先预测的，在同一个城市里相距不远的工地，就存在着各工地的监理工程师如何交错使用的运筹问题． (2) 各工地总监在高峰施工期到来的时候要向公司要人，如果每个工地都按高峰施工期配置监理工程师的数量，将造成极大的人力资源浪费，这一点应该说主要是人为因素所造成的．因此，为了达到高峰施工期监理工程师配置数量最优，人员合理地交错使用，扼制人为因素，根据历年来的经验对高峰施工期的监理工程师数量在合理交错发挥作用的前提下限定了范围．另经统计测算得知，全年平均标准施工期占 7 个月，人均年成本 4 万元；高峰施工期占 5 个月，人均年成本 7 万元．标准施工期所需监理工程师如下表所示．
1. 简答题
（1） 运筹学的工作步骤
提出和形成问题：即要弄清问题的目标，可能的约束，问题的可控变量以及相关的参数，搜集相关资料；
建立模型：即把问题中可控变量，参数，目标与约束之间的关系用模型表示出来；
求解：用各种手段将模型求解，解可以是最优解，次优解，满意解。复杂模型的求解需用计算机，解得精度要求可有决策者提出；
解的检验：首先检查求解步骤和程序有无错误，然后检查解是否反映现实问题；
解的控制：通过控制解的变化过程决定对解是否做一定的改变；
解的实施：是指将解用到实际中必须考虑的实际问题，如向实际部门讲清解的用法，在实施中可能产生的问题和修改。
（2） 退化产生原因及解决办法
单纯形法计算中用θ规则确定换出变量时，有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，这就出现退化解。
勃兰特规则：
1.选取cj-zj＞0中下标最小的非基变量xk为换入变量，即k=min(j｜cj-zj＞0)
2. 当按θ规则计算存在两个和两个以上最小比值时，选取下标最小的基变量为换出变量。
（3）对偶问题的经济解释
• 这说明yi是右端项bi每增加一个单位对目标函数Z的贡献。
• 对偶变量 yi在经济上表示原问题第i种资源的边际价值。
• 对偶变量的值 yi*所表示的第i种资源的边际价值，称为影子价值。 njmiiijjybxcZ11iiybZ若原问题的价值系数Cj表示单位产值，则yi 称为影子价格；
若原问题的价值系数Cj表示单位利润，则yi 称为影子利润。
影子价格不是资源的实际价格，而是资源配置结构的反映，是在其它数据相对稳定的条件下某种资源增加一个单位导致的目标函数值的增量变化。
（4）分枝定界法步骤
a) 先求出整数规划相应的LP(即不考虑整数限制)的最优解，
b) 若求得的最优解符合整数要求，则是原IP的最优解；
c) 若不满足整数条件，则任选一个不满足整数条件的变量来构造新的约束，在原可行域中剔除部分非整数解。
第一章
线性规划及单纯形法
2本章主要内容
线性规划概述绪论
一般线性规划问题的数学模型
线性规划问题的图解法
线性规划的基本定理
单纯形法
用计算机软件求解线性规划问题
线性规划的应用举例
3【开篇案例】
某旅行社为了迎接旅
游黄金周的到来，对一日
游导游人员的需求经过统
计分析如表所示。为了保
证导游充分休息，导游每
周工作5天，休息两天，
并要求休息的两天是连续
的。问应该如何安排导游
人员的作息，既满足工作
需要，又使配备的导游人
数最少？一、人力资源分配的问题线性规划
时间所需导游人数
星期日40
星期一34
星期二32
星期三35
星期四28
星期五46
星期六42
4【开篇案例】
明兴公司生产甲、乙、丙三种产品，都需要经过铸造、机加工
和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自
行生产，但产品丙必须本厂铸造才能保证质量。数据如右表。问：
公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、
乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？二、生产计划的问题
甲乙丙资源限制
铸造工时(小时/件)51078000
机加工工时(小时/件)64812000
装配工时(小时/件)32210000
自产铸件成本(元/件)354
外协铸件成本(元/件)56--
机加工成本(元/件)213
装配成本(元/件)322
产品售价(元/件)231816线性规划
5【开篇案例】
某工厂要用三种原料1、2、3混合调配出三种不同规格
的产品甲、乙、丙，数据如右表。问：该厂应如何安排生产，
使利润收入为最大？三、配料问题产品名称规格要求单价（元/kg）
甲原材料1不少于50%，原材料2不超过25%50
乙原材料1不少于25%，原材料2不超过50%35
丙不限25
原材料名称每天最多供应量单价（元/kg）
110065
210025
36035线性规划
6【开篇案例】
某部门现有资金200万元，今后五年内考虑给以下的项目投资。
已知：项目A：从第一年到第五年每年年初都可投资，当年末能收回
