《MBA运筹学培训讲义》由会员分享，可在线阅读，更多相关《MBA运筹学培训讲义（49页珍藏版）》请在金锄头文库上搜索。
1、MBA运筹学讲义运筹学是一门应用科学，它广泛应用现代科学技术知识、用定量分析的方法，解决实际中提出的问题，为决策者选择最优决策提供定量依据。运筹学的核心思想是建立在优化的基础上。例如，在线性规划中体现为两方面：（1）对于给定的一项任务，如何统筹安排，使以最少的资源消耗去完成？（2）在给定的一定数量的资源条件下，如何合理安排，使完成的任务最多？运筹学解决问题的主要方法是用数学模型描述现实中提出的决策问题，用数学方法对模型进行求解，并对解的结果进行分析，为决策提供科学依据。随着计算机及计算技术的迅猛发展，目前对运筹学的数学模型的求解已有相应的软件。因此，在实际求解计算时常可借助于软件在计算机上进行
2、，这样可以节省大量的人力和时间。第一部分线性规划内容框架实际问题行解提出L基本概念数学模型解LPJ冋题解的概念LP问题可行解、最优基本解、基可基本最优解基本方法I孑图解法原始单纯形法法段法法段法|单纯形法一人工变量法I对偶单纯形法p对偶理论进一步讨论J敏度分析一一参数规划F经济管理领域内应用运输问题（转运问题）特殊的LP问题_整数规划多目标LP冋题*第一部分线性规划（LinearProgramming）及其应用第一章LP问题的数学模型与求解1LP问题及其数学模型（一）引例1（生产计划的问题）某工厂在计划期内要安排生产I、U的两种产品，已知生产单位产品所需的设备台时，A、B两种原材料的消耗以及每
3、件产品可获的利润如下表所示。问应如何安排计划使该工厂获利最多？In资源限量设备128（台时）原材料A4016(kg)原材料B0412(kg)单位产品利润（元）23该问题可用一句话来描述，即在有限资源的条件下，求使利润最大的生产计划方案。解：设Xi,X2分别表示在计划期内生产产品I、U的产量。由于资源的限制，所以有：机器设备的限制条件：Xi+2X28原材料A的限制条件：4xi16（称为资源约束条件）原材料B的限制条件：4x20，X20（称为变量的非负约束）显然，在满足上述约束条件下的变量取值，均能构成可行方案，且有许许多多。而工厂的目标是在不超过所有资源限量的条件下，如何确定产量X1，X2以得到
4、最大的利润，即使目标函数Z=2xi+3x2的值达到最大。综上所述，该生产计划安排问题可用以下数学模型表示：maxz=2x+3x2人2x2-8st.4Xj空164X2乞12ILx1x0引例2.（营养配餐问题）假定一个成年人每天需要从食物中获取3000卡路里热量，55克蛋白质和800毫克钙。如果市场上只有四种食品可供选择，它们每千克所含热量和营养成份以及市场价格如下表所示。问如何选择才能满足营养的前提下使购买食品的费用最小？序号食品名称热量（卡路里）蛋白质（克）钙(mg)价格（元）1猪肉100050400102鸡蛋8006020063大米9002030034白菜200105002解:设为（=1,2
5、,3,4）为第j种食品每天的购买量，则配餐问题数学模型为minz=10xi6x23x32x410000xi800X2900X3200x4-300050%+60x2+20x3+10x4兰55xt400x200x300x500x800为K0(j=1,2,3,4)（二）LP问题的模型上述两例所提出的问题，可归结为在变量满足线性约束条件下，求使线性目标函数值最大或最小的问题。它们具有共同的特征。(1) 每个问题都可用一组决策变量(X1,X2,Xn)表示某一方案，其具体的值就代表一个具体方案。通常可根据决策变量所代表的事物特点，可对变量的取值加以约束，如非负约束。(2) 存在一组线性等式或不等式的约束条
6、件。(3) 都有一个用决策变量的线性函数作为决策目标(即目标函数)：按问题的不同，要求目标函数实现最大化或最小化。满足以上三个条件的数学模型称为LP的数学模型，其一般形式为：max(或min)z=c1X1+C2X2+CnXn(1.1)S.tIduX2812X2821X2822X2I8m1X28m2X2X181nXn-，-)bi十82nXn兰(=，王)b2(1.3)(1.2)或紧缩形式nmax(或min)z八cjXjj二=,-)b(i=12,m)Xj-0(1.4)或矩阵形式max(或min)z=cx(1.5)或向量形式:AX乞(=)bX-0max或min)z=cxZPjXj兰(=,K)bj二XQ
7、(j=1,2,，n)(1.6)其中C=(C1,C2,Cn)，称为价值系数向量;an,a21,a12,a22,Qna2n称为技术系数矩阵(并称消耗系数矩阵)amn-=(P1,P2,Pn)b2b=.称资源限制向量:I-X=(X1,X2,Xn)T称为决策变量向量。(三) LP问题的标准型为了讨论LP问题解的概念和解的性质以及对LP问题解法方便，必须把LP问题的一般形式化为统一的标准型:nmaxz=cjXj;maxz=cxj1ajXj=bi（i2,m）或AX二bXj-0（j=1,2/,n）一X-maxz=cxJjXjf_Xj-0（j2,n）标准型的特点： 目标函数是最大化类型 约束条件均由等式组成 决
8、策变量均为非负 bi(i=1,2,n)1. 化一般形式为标准型 minzmax(-z)=-cx，左边“松驰变量” “岂”、左边+松驰变量; 变量Xj如一;-Xj_0变量Xj无限制一；令Xj=Xjxj bi0、等式两边同乘以(-1)o2. 模型隐含的假设 比例性假定：决策变量变化的改变量与引起目标函数的改变量成比例；决策变量变化的改变量与引起约束方程左端值的改变量成比例。此假定意味着每种经营活动对目标函数的贡献是一个常数，对资源的消耗也是一个常数。 可加性假定：每个决策变量对目标函数和约束方程的影响是独立于其它变量的。 连续性假定：决策变量应取连续值 确定性假定：所有的参数(aj,bi,Cj)均为确定，所以LP问题是确定型问题，不含随机因素。以上4个假定均由于线性函数所致。在现实生活中，完全满足这4个假定的例子并不多见，因此在使用LP时必须注意问题在什么程度上满足这些假定。若不满足的程度较大时，应考虑使用其它模型和方法。如非线性规划，整数规划或不确定型分析方法。对LP标准型，我们还假定r(A)=m0设maxZ=cxi+C2X2+CnXnXiX2XiX2
