运筹学是一门应用科学，它广泛应用现代科学技术知识、用定量分析的方法，解决实际中提出的问题，为决策者选择最优决策提供定量依据。运筹学的核心思想是建立在优化的基础上。
例如，**性规划中体现为两方面：
（1）对于给定的一项任务，如何统筹安排，使以最少的资源消耗去完成？
（2）在给定的一定数量的资源条件下，如何合理安排，使完成的任务最多？
运筹学解决问题的主要方法是用数学模型描述现实中提出的决策问题，用数学方法对模型进行求解，并对解的结果进行分析，为决策提供科学依据。
随着计算机及计算技术的迅猛发展，目前对运筹学的数学模型的求解已有相应的软件。因此，在实际求解计算时常可借助于软件在计算机上进行，这样可以节省大量的人力和时间。
第一部分线性规划内容框架。
lp问题。基本概念数学模型可行解、最优解。
实际问题lp问题解的概念基本解、基可行解。
提出基本最优解。
基本方法。**法。
原始单纯形法。
单纯形法大m法。
人工变量法。
对偶单纯形法两阶段法。
对偶理论。进一步讨论。
灵敏度分析──参数规划*
在经济管理领域内应用。
运输问题**运问题）
特殊的lp问题整数规划。
多目标lp问题*
第一部分线性规划（linear programming）及其应用。
第一章 lp问题的数学模型与求解。
§1 lp问题及其数学模型。
（一）引例1（生产计划的问题）
某工厂在计划期内要安排生产ⅰ、ⅱ的两种产品，已知生产单位产品所需的设备台时，a、b两种原材料的消耗以及每件产品可获的利润如下表所示。问应如何安排计划使该工厂获利最多？
该问题可用一句话来描述，即在有限资源的条件下，求使利润最大的生产计划方案。
解：设x1,x2分别表示在计划期内生产产品ⅰ、ⅱ的产量。由于资源的限制，所以有：
机器设备的限制条件：x1+2x2≤8
原材料a的限制条件： 4x1≤16 （称为资源约束条件）
原材料b的限制条件： 4x2≤12
同时，产品ⅰ、ⅱ的产量不能是负数，所以有。
x1≥0，x2≥0称为变量的非负约束）
显然，在满足上述约束条件下的变量取值，均能构成可行方案，且有许许多多。而工厂的目标是在不超过所有资源限量的条件下，如何确定产量x1，x2以得到最大的利润，即使目标函数。
z=2x1+3x2的值达到最大。
综上所述，该生产计划安排问题可用以下数学模型表示：
maxz=2x1+3x2
引例2. （营养配餐问题）
假定一个成年人每天需要从食物中获取3000卡路里热量，55克蛋白质和800毫克钙。如果市场上只有四种食品可供选择，它们每千克所含热量和营养成份以及市场**如下表所示。问如何选择才能满足营养的前提下使购买食品的费用最小？
解：设xj(j=1,2,3,4)为第j种食品每天的购买量，则配餐问题数学模型为。
minz=10x16x23x32x4
（二）lp问题的模型。
上述两例所提出的问题，可归结为在变量满足线性约束条件下，求使线性目标函数值最大或最小的问题。它们具有共同的特征。
1）每个问题都可用一组决策变量(x1,x2,…xn)表示某一方案，其具体的值就代表一个具体方案。通常可根据决策变量所代表的事物特点，可对变量的取值加以约束，如非负约束。
2）存在一组线性等式或不等式的约束条件。
3）都有一个用决策变量的线性函数作为决策目标（即目标函数），按问题的不同，要求目标函数实现最大化或最小化。
满足以上三个条件的数学模型称为lp的数学模型，其一般形式为：
max(或min)z=c1x1+c2x2+…+cnxn1.1)
或紧缩形式。
max(或min)z=
或矩阵形式。
max(或min)z=cx
或向量形式：
max(或min)z=cx
其中c=(c1,c2,…,cn)，称为价值系数向量；
称为技术系数矩阵（并称消耗系数矩阵）
=(p1,p2,…,pn)
称资源限制向量。
x=(x1,x2,…,xn)t称为决策变量向量。
三）lp问题的标准型。
1.为了讨论lp问题解的概念和解的性质以及对lp问题解法方便，必须把lp问题的一般形式化为统一的标准型：
maxz或。
maxz=cx
或。标准型的特点：
目标函数是最大化类型。
约束条件均由等式组成。
决策变量均为非负。
bi(i=1,2,…,n)
2.化一般形式为标准型。
minzmax(-z)=-cx
“”左边+松驰变量；“”左边－“松驰变量”
变量xj0-xj0变量xj无限制令xj=xj－xj
bi<0等式两边同乘以(-1)。
3.模型隐含的假设。
比例性假定：决策变量变化的改变量与引起目标函数的改变量成比例；决策变量变化的改变量与引起约束方程左端值的改变量成比例。此假定意味着每种经营活动对目标函数的贡献是一个常数，对资源的消耗也是一个常数。
可加性假定：每个决策变量对目标函数和约束方程的影响是独立于其它变量的。
连续性假定：决策变量应取连续值。
确定性假定：所有的参数(aij,bi,cj)均为确定，所以lp问题是确定型问题，不含随机因素。
以上4个假定均由于线性函数所致。在现实生活中，完全满足这4个假定的例子并不多见，因此在使用lp时必须注意问题在什么程度上满足这些假定。若不满足的程度较大时，应考虑使用其它模型和方法。
如非线性规划，整数规划或不确定型分析方法。
对lp标准型，我们还假定r(a)=m（四）lp问题的解的概念。
设lp问题。
maxz1.7)
1.从代数的角度看：
可行解和最优解满足约束条件(1.8)和(1.9)的解x=(x1,x2,…,xn)t称为可行解。
所有可行解构成可行解集，即可行域。而使目标函数达到最大值的可行解称为最优解，对应的目标函数值称为最优值。
求解lp问题就是求其最优解和最优值，但从代数的角度去求是困难的。
2.从lp角度看：
基：设a为mxn矩阵，r(a)=m，b是a中的mxm阶非奇异子矩阵（即|b|0），则称b是lp问题的一个基。
若b是lp问题的一个基，则b由m个线性独立的列向量组成，即b=(pr1,pr2,…,prm)，其中prj=(a1rj,a2rj,…,amrj)t，(j=1,2,…,m)称为基向理。与其向量prj相对应的变量xrj称为基变量，其它变量称为非基变量。显然，对应于每个基总有m个基变量，n－m个非基变量。
基本解与基可行解设b是lp问题的一个基，令其n－m个非基变量均为零，所得方程的解称为该lp问题的一个基本解。显然，基b与基本解是一一对应的，基本解的个数≤cmn。在基本解中，称满足非负条件的基本解为基可行解，对应的基称为可行基。
退化解如果基解中非零分量的个数小于m，则称此基本解为退化的，否则是非退化的。
最优基如果对应于基b的基可行解是lp问题的最优解，则称b为lp问题的最优基，相应的解又称基本最优解。
问题解之间的关系如图所示。
五）两个变量lp问题的**法。
问题解的几何表示。以引例为例说明。
maxz=2x1+3x2
按以下顺序进行：
解：（1）画出直角坐标系；
（2）依次做每条约束线，标出可行域的方向，并找出它们共同的。
可行域；（3）任取一目标函数值作一条目标函数线（称等值线），根据目标函数（最大或最小）类型，平移该直线即将离开可行域上，则与目标函数线接触的最终点即表示最优解。
图1其中，将目标函数z=2x1+3x2改写为，因此，它可以表示为：以z为参数，以为斜率的一族平行线。位于同一条直线上的点具有相同的值。
解的几种情况：
1）此例有唯一解q2，即x1=4,x2=2,z=14
（2）有无穷多最优解（多重解），若将目标函数改为z=2x1+4x2则线段q2，q3上的点均为最优解。
（3）无界解。
求max无界。
但求min有唯一解。
（4）无可行解。
可行域与最优解间的关系：
可行域最优解。
空集无最优解（无可行解）
有界集唯一最优解。
多重解。无界集无有限最优解（无界解）
结论：（1）lp问题的可行域是凸集（凸多边形，凸多面体，…）
2）lp问题最优解若存在，则必可在可行域的顶点上得到；
3）lp问题的可行域的顶点个数是有限的；
4）若lp问题有两个最优解，则其连线上的点都是最优解。因此，求解lp问题可转化为如何在可行域的顶点上求出使目标函数值达到最优的点的问题。
2.基可行解的几何意义。
对例1 lp问题标准化为maxz=2x1+3x2
可求得所有的基本解：
x(1)=(0,0,8,16,12)t(0点),x(2)=(4,0,4,0,12)t(q1点)
x(3)=(4,2,0,0,4)t(q2点),x(4)=(2,3,0,8,0)t(q3点)
x(5)=(0,3,2,16,0)t(q4点),x(6)=(4,3,-2,0,0)t(c点)
x(7)=(8,0,0,-16,12)t(a点),x(8)=(0,4,0,16,-4)t(b点)
但a、b、c三点是非可行域上的点，即非可行解。因此，x(1)，x(2)，x(3)，x(4)，x(5)才是基可行解，它们与可行域的顶点相对应。于是还有。
结论：（5）对于标准型的lp问题，x是基可行解的充要条件是x为可行域的顶点。
（6）lp问题可行域顶点的个数=基可行解的个数≤基的个数≤cmn
3.**法只适用于两个变量（最多含三个变量）的lp问题。
4.求解lp问题方法的思考：
完全枚举法，对m、n较大时，cmn是一个很大的数，几乎不可能；
管理运筹学作业答案 韩大卫 MBA
第1章线性规划基本性质。p47 1 1 2 解 设每天从煤矿运往城市的煤为吨，该问题的lp模型为 p48 1 2 2 解 则该lp问题无可行解。p48 1 2 3 韩大卫 第1章线性规划基本性质管理运筹学作业答案 韩大卫 mba运筹学作业答案 1 第1章线性规划基本性质p47 1 1 2 解 设每天...
运筹学试卷 物流运筹学
2012 2013学年第一学期。运筹学 试卷。试卷 自拟送卷人 唐文广打印 校对 唐文广。一 6分 已知线性规划模型。写出该问题的对偶问题。二 15分 用单纯形法求解下面线性规划问题 作1张表即可 三 10分 求解下面标准指派问题，其中效率矩阵为。四 15分 某项工程由a b i j k等11项工序...
运筹学试题与案例集 运筹学
20xx年运筹学试题与案例集 天津。全国运筹学精品课程建设与题库案例交流研讨会运筹学试题与案例集 内部交流资料 中国运筹学会教育普及工作委员会 天津运筹学会 天津工业大学 20xx年5月 全国运筹学精品课程建设与题库案例交流研讨会 2010.05 目录 第一部分运筹学试题4 试题 1 北京工商大学4...