管理运筹学

赵鹏举中原工学院管理运筹学数学的魅力与实质数学的本质是处理抽象对象，是比语言更精炼、更严谨的符号系统。是人类理性的集中体现。数学的方法是建立一个牢不可破的公理体系，并以演绎推理的方法去构建和扩展整个学科体系。数学分支数学分支数学分支应用演绎方法公理体系数学大厦数学的魅力与实质数学方法在自然科学体系中无处不在，并取得了光辉的成就。19世纪以后，数学被广泛深入地应用于社会科学领域。经济学、管理学领域的许多大师具有高超的数学技能。数学的魅力与实质本门课程不仅要学习一门课程，一套方法，更重要的是要学会理性分析问题的方法。培养逻辑思维能力和抽象思维能力。数学在发展的过程中遇到过许多问题，而且也并非确切无疑，大家要敢于质疑，敢于提问题。数学的魅力与实质一个例子：S=1-1+1-1+1…请问S等于多少？数学的魅力与实质至少有三种解法：1、S=（1-1）+（1-1）+（1-1）…2、S=1+（-1+1）+（-1+1）…3、1-S=1-(1-1+1-1…)=1-1+1-1+1-1…=S得到2S=1，从而S=1/2。数学的魅力与实质事实上，这是一个争论未定的题目，反映了人类对自然认识的不足。无穷的概念存在许多不足之处，而且并非绝对精确。不同的学派对无穷有着不同的认识。考核方法平时成绩占20%，每位同学的初始成绩都是60分（按100分为满分计算）。每次作业交上加1分，不交不加不减，拷贝别人作业一次扣2分。上课主动回答问题每次加2分。提出有价值问题或发现老师错误每次加5分。运筹学的体系和发展历史定义运筹学是一门应用于管理有组织系统的科学它为掌管这类系统的人提供决策目标和数量分析的工具运筹学应用分析、实验、量化的方法，对经济管理系统中人、财、物等有限资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理正式起源与二次世界大战，被称为Operationsresearch,日本人翻译为运做学，台湾人翻译为作业研究运筹学的体系和发展历史田忌赛马萌芽在20世纪初，Lanchester战斗方程。丹麦工程师爱尔朗研究电话通讯系统时提出了一些排队论的公式。30年代，数学家列温逊运用运筹思想分析商业广告、顾客心理。运筹学的体系和发展历史二次世界大战中，英美科学家研究如何有效运用雷达，研究船队遇到袭击如何减少损失，以及如何使用深水炸弹等紧迫问题。应用：德国潜艇被摧毁数增加到400%，船只中弹数由47%减少到29%。结果：打赢了空战和海战，保证了二次世界大战的最终胜利。运筹学在现实生活中的例子企业安排生产计划库存管理公交系统优化食堂窗口设置电脑游戏，帝国时代、魔兽争霸等。运筹学的学科体系规划论：包括线性规划、非线性规划、整数规划等。1947年，Danzig提出单纯形法，随后规划方法得到了广泛的应用。图论与网络分析：图是研究离散事物之间关系的一种分析模型。例：有甲、乙、丙、丁、戊、己6名同学参加ABCDEF六个项目的比赛，下表是各运动员报名参赛的项目，问6个项目顺序如何安排，作到每名运动员不连续参加两项比赛。运筹学的学科体系ABCDEF甲**乙***丙**丁**戊**己**运筹学的学科体系排队论：研究公共服务系统的运行与优化的数学理论方法。决策论：研究不确定情况以及风险情况下的决策。存储论：研究企业的库存计划，进货周期等。博弈论：研究竞争环境下决策者行为的数学方法。运筹学的工作步骤提出和形成问题：弄清问题的目标，可能的约束，问题的可控变量，相关参数等。建立模型：把问题中的可控变量、参数、目标、约束之间的关系用一定的模型表示出来。求解：用计算或实验方法求出问题的解。解的检验：检查求解过程，检查解能否反映现实问题。解的实施：将解运用到实际问题中。第一章线性规划本章内容线性规划模型线性规划问题的图解法单纯形法非标准形线性规划的解法线性规划模型规划问题：就是否合理利用有限资源的问题。线性规划：线性的规划问题。两个意思：1、目标函数是线性的2、约束条件是线性的线性规划模型生产决策问题某汽车工厂生产大轿车和载重汽车两种型号的汽车,已知每辆汽车所用的钢材都是2吨/辆，该工厂每年供应的钢材为1600吨；工厂的生产能力是每2.5小时可生产一辆载重汽车，每5小时可生产一辆大轿车，工厂全年的有效工时为2500小时；已知供应给该厂大轿车用的座椅每年可装配400辆。据市场调查，出售一辆大轿车可获利4000元，出售一辆载重汽车可获利3000元。如何安排生产才能使工厂获利最大？线性规划模型建模型如下：设大轿车数量为x1,载重汽车数量为x2。0,40025005.25160022..34max211212121xxxxxxxtsxxzs.t.是subjectto的简写，表示受限制于。线性规划模型某工厂在计划期间内生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如下表所示：ⅠⅡ设备11300台时原料A21400Kg原料B01250Kg已知Ⅰ、Ⅱ两种产品每单位分别可以获利50元、100元，问工厂应该如何安排生产才能使工厂获利最多。线性规划模型设置变量：生产Ⅰ产品x1个，Ⅱ产品x2个目标函数是利润最大化：资源是有限的，第一个限制是设备台时的限制：2110050maxxxz30021xx线性规划模型第二个限制是原材料A的限制：第三个限制是原材料B的限制：显然，产量不可能为负数：400221xx2502x0,21xx线性规划模型建模型如下：设生产Ⅰ产品x1件,Ⅱ产品x2件。)2(0,2504002300..)1(10050max212212121xxxxxxxtsxxz线性规划模型（1），（2）分别被称为目标函数和约束条件。目标函数中变量的系数被称为价值系数，约束条件不等号右端称为资源向量或限定系数，约束条件左端变量的系数被称为技术系数。目标函数和约束条件都是一次幂函数，或称线性函数，因此这类规划问题被称为线性规划问题。线性规划模型例3：生产卷烟的主要原材料包括烟叶和烟梗。国家规定每千克焦油含量不超过15mg，烟气烟碱含量不超过1.4mg，现在知道每千克烟叶含焦油12mg，烟气烟碱1.5mg，烟梗含焦油18mg，烟气烟碱0.3mg，烟叶每千克50元，烟梗每千克20元，问如何搭配使生产成本最小。线性规划模型设每千克卷烟用烟叶x1千克，烟梗x2千克，模型如下：)2(0,14.13.05.1151812..2050min2121212121xxxxxxxxtsxxf这是目标函数一个求最小化的问题。线性规划的标准形为求解方便，一般线性规划都可以转化成如下标准形式：),,2,1(0..max221122222121112121112211njxbxaxaxabxaxaxabxaxaxatsxcxcxczjmnmnmmnnnnnn要求)...2,1(0mibi线性规划的标准形目标函数为求最小化时，等式两端同乘以-1，变为求最大化。约束条件为=时，加一个松弛变量，约束条件为=时，减一个剩余变量。资源变量为负数时，等式两端同乘以-1。变量为=0时，令变量无约束时，令0,''jjjxxx0,;''''''jjjjjxxxxx线性规划的图解法以例1为例：0,40025005.25160022..34max211212121xxxxxxxtsxxz线性规划的图解法2134xxx2800400400800x116002221xx25005.2521xx4001x2134xx2134xx线性规划的图解法从图中可以得到：x1=200,x2=600,z=2600最优解为：生产200辆大轿车，生产600辆载重汽车，可获利润2600千元。钢材和工时全部用完，座椅剩余200套。几个概念凸集：设k是n维欧氏空间中的一个点集，在集合中任意取两点x1,x2∈k。如果这两点连线上的一切点都落在k中，则称k为凸集。角顶：设k为凸集，x∈k，如果不能用不同的两点x1,x2∈k线性表出x，则称x为k的一个角顶。角顶可行解和角顶不可行解：既是角顶解又是可行解的解称为角顶可行解，是角顶解而不是可行解的解称为角顶不可行解。图解法的几点启示线性规划的可行域必定为凸集或无界区域。线性规划的最优解必定在顶点取得。如果有多个最优解，那么至少有两个相邻的角顶可行解是最优解。角顶可行解的数目是有限的。如果一个角顶可行解的目标函数值比相邻的所有角顶解好，它就是最优解。解决线性规划问题的思路基本思路是在满足约束条件的前提下，从一个初始顶点开始，不断寻找改进目标函数的顶点，直到无法改进为止。步骤1：从一个角顶可行解出发，判断相邻的角顶可行解是否比目前的点更好。如果相邻的角顶可行解都劣与这个顶点，则说明这个点已经是最优解，算法结束。步骤2：如果相邻的角顶可行解更好，就向这个点移动。重复步骤1。线性规划问题解的基本概念可行解：满足约束条件解称为可行解，对应图解法的阴影部分。基：约束条件中任意一个m阶非奇异子矩阵确定一个线性规划问题的基。对应图解法中的顶点。基可行解：既是可行解又是基解称为基可行解。最优解：满足目标函数和约束条件的解称为最优解。单纯形法求解单纯形法的步骤单纯形表法单纯形表法中的一些特殊情况求解单纯形法的步骤步骤1：将模型转化为标准形。步骤2：找到一个初始可行基，列出初始单纯形表。步骤3：判断初始可行基是否最优。如果是最优解则结束，否则转步骤4。步骤4：如果不是最优，则通过一定的规则将一个变量换出，另一个变量换入，构成一个新的基解。转步骤3。求解单纯形法的步骤x2800400400800x116002221xx25005.2521xx4001x2134xx2134xx求解单纯形法的步骤图形解法只能解决2维的线性规划问题（仅有两个变量）。对超过3维的情况，既无法在平面上画出图形，也无法进行直观的想象。根据图形解法的启示，提出单纯形法解决线性规划问题的基本思路。单纯形表法以例一为例：0,40025005.25160022..34max211212121xxxxxxxtsxxz单纯形表法步骤1：首先转化为标准形式：添加松弛变量。0,,,,40025005.25160022..34max543215142132121xxxxxxxxxxxxxtsxxz单纯形表法步骤2：找到一个初始可行基。即寻找一个m阶的非奇异子矩阵。从标准形的线性规划问题中可以看出，x3,x4,x5构成了一个3阶的单位矩阵，把这三个变量作为初始可行基。列出初始单纯形表。单纯形表法列出初始单纯形表：x1x2x3x4x5xCj000543xxx40025001600zjzj-cj430002210052.501010001bθ单纯形表法步骤3：确定换入换出变量。方法：先确定换入变量，计算检验数zj-cj，计算方法：，cj为对应xj的系数。以最负的检验数对应的系数列作为主列元素。随后确定换出变量，计算检验数θ，计算方法：，选择θ值最小的行对应的主列元素作为换出变量。miijijacz1)0(ikikiiaab单纯形表法确定换入换出变量：x1x2x3x4x5xCj000543xxx40025001600zj-4-3000zj-cj00000430002210052.5010[1]0001bθ0400500800单纯形表法步骤4：以主元素为中心，进行迭代运算。x1x2x3x4x5xCj400143xxx400500800zj0-3004zj-cj40004430000210-202.501-510001bθ1600