下载文档原格式
研究生入学考试辅导《运筹学讲义》1.线线规划与单纯形法●线性规划问题和数学模型；●线性规划图解法●线性规划解的概念和单纯形法●单纯形法的一些具体问题2.对偶理论与灵敏度分析●线性规划问题的对偶及其变换；●线性规划的对偶定理；●对偶单纯形法；●线性规划的灵敏度分析写出规划模型和标准化问题；指出解的类型；和对偶问题结合的题目；求解的问题；1.某饲料厂用原料A、B、C加工成三种不同牌号的饲料甲、乙、丙。
已知各种牌号饲料中A、B、C含量，原料成本，各种原料的每月限制用量，三种牌号的饲料的单位加工费及售价如【表1-1】所示。
表1-1问该厂每月应生产这三种牌号饲料各多少千克，使该厂获利最大？试建立这个问题的的线性规划的数学模型。
2.有如下线性规划问题，令X6,X7分别为约束条件（1）和（2）的松弛变量，指出下表各组解的类型（可行解、非可行解、基础可行解、基础非可行解）,,,,7204234360 22 264242x ax5432154315 432154321≥≤++ +≤+++ +++++xxxxxx xx xxxxx xxxxxxfM）＝（3.设某投资者有30000元可供为期四年的投资。
现有下列五项投资机会可供选择：A:在四年内，投资者可在每年年初投资，每年每元投资可获得0.2元，每年获利后可将本利重新投资；B：在四年内，投资者应在第一年年初或第三年年初投资，每年每元获利0.5元，两年后获利。
然后再将本利投资；C：在四年内，投资者应在第一年年初投资，三年后每元获利0.8元。
获利后可将本利重新投资，这项投资最多不超过20000元；D：在四年内，投资者应在第二年投资，两年后获利每元投资可获利0.6元，获利后可将本利和投资，这项投资最多不超过20000元；E：在四年内，投资者应在第一年投资，四年后获利每元1.7元，最大投资不超过20000元；求：四年后，投资获利最大？不求解。
4.某公司计划在三年的计划期内，有四个项目可以投资：项目一从第一年到第三年年初都可以投资，年末可收回本利120%，每年又可以重新将所获本利纳入投资计划；项目二需要在第一年初投资，经过两年可收回本利150%，又可以重新将所获本利纳入投资计划，但用于该项目的最大投资额不得超过20万元；项目三需要在第二年年初投资，经过两年可收回本利160%，但用于该项目的最大投资额不得超过15万元；项目四需要在第三年年初投资，年末可收回本利140%，但用于该项目的最大投资额不得超过10万元。
《运筹学》复习资料整理总结1. 建立线性规划模型的步骤。
确定决策变量 确定目标函数 确定约束条件方程2. 线性规划问题的特征。
都有一个追求的目标，这个目标可表示为一组变量的线性函数，按照问题的不同，追求的目标可以为最大，也可以为最小。
问题中有若干个约束条件，用来表示问题中的限制或要求，这些约束条件可以用线性等式或线性不等式表示。
问题中用一组决策变量来表示一种方案。
3. 线性规划问题标准型的特征。
4. 化标准型的方法。
123123123123min z 2+223-8340,0,x x x x x x x x x x x x =+-+=⎧⎪-+-≤⎨⎪≤≥⎩为自由变量123123123123min z 2+223-634,0,x x x x x x x x x x x x =+-+=⎧⎪-+-≥⎨⎪≥⎩为自由变量5. 基本解：令其余的变量取值为0，则得到Ax=b 的一个解y,称此解为线性规划问题的基本解。
6. 基本可行解：若基本解y 满足y ≥0,则称这个解为基本可行解。
7. 可行解：满足约束条件的解x=（x1、x2、……xn ）T 称为线性规划问题的可行解。
8. 最优解：函数达到最优的可行解叫做最优解。
9.图解法适合于变量个数为2个的线性规划问题。
10.单纯形法解线性规划问题如何确定初始基本可行解。
（1）约束条件为≤，先加入松弛变量x1、x2……xm后变为等式，取松弛变量为基本变量（2）约束条件为=，先加入人工变量xm+1、xm+2……xm+n，人工变量价值系数为m（3）约束条件为≥，先加入多于变量xn+1、xn+2……xm+n后变为等式，在添加人工变量xn+m+111.单纯形法最优解的检验准则。
（1）若基本可行解x’对应的典式的目标函数中非基变量的系数全部满足cN-cBB-1Pj≤0,则基本可行解x’为原问题的最优解。
（2）若基本可行解x’对应的典式的目标函数中所有非基变量的系数满足cN-cBB-1Pj≤0,且有一非基变量的系数满足Ck-Zk=0,则原问题有无穷多组最优解12.对目标函数为极小（min）型的线性规划问题，用单纯形法解的三种处理方法。
《管理运筹学》1、运筹学的工作步骤(1)提出和形成问题．(2)建立模型．(3)求解．(4)解的检验．(5)解的控制．(6)解的实施.2、运筹学模型三种基本形式：(1)形象模型(2)模拟模型(3)符号或数学模型构模的五种方法和思路： (1)直接分析法 (如线性规划)(2)类比法（手机的普及与电视机的普及）(3)数据分析法（如汽车销售量预测模型）(4)试验分析法（销售量与价格之间的关系模型）(5)想定(构想)法（销售与心理）3、如何将线性规划问题的一般形式化为标准形式：1.如果问题是求目标函数的最小值，求min f＝∑Cjxj则可先将目标函数乘（-1），化为求极大值问题，即求 max Z=－f=－∑Cjxj2.如果有某个bk≤0，则可将该等式两边均乘以(－1)，使右端常数项bk=－bk≥03.如果第k个约束条件是∑akjxj≤bk,引入松弛变量sk≥0 , 将它写成∑akjxj+sk＝bk如果第l个约束条件是∑aljxj≥bl则引入剩余变量(也可称为松弛变量)sl≥0，将它写成∑aljxj—sl=bl 且使松弛变量和剩余变量在目标函数中的系数为零。
4.如果对某个变量xj没有非负限制(这种变量称为自由变量或无约束变量)，则引进两个非负变量xj′，xj″，令xj＝xj′－xj″代人目标函数和约束条件中，可将它化为对全部变量都有非负限制的问题。
4、①目标函数为变量的线性函数，约束条件也为变量的线性等式或不等式的模型称之为线性规划。
②如果目标函数是变量的非线性函数，或约束条件中含有变量非线性的等式或不等式的数学模型则称之为非线性规划。
③满足所有约束条件的解称为该线性规划的可行解。
④把使得目标函数值最大(即利润最大)的可行解称为该线性规划的最优解,此目标函数值称为最优目标函数值，简称最优值5、图解法的启示1．最优解：如果某一个线性规划问题有最优解，则一定有一个可行域的顶点对应一个最优解。
（一般为封闭可行域凸集）2．无穷多个最优解：若将上例中的目标函数变为求maxZ=50x1+50x2则代表目标函数的直线平移到最优位置后将和直线x1+x2=300重合。
运筹学复习一、 填空题1、线性规划中，满足非负条件的基本解称为基本可行解，对应的基称为可行基线.2、性规划的目标函数的系数是其对偶问题的右端常数；而若线性规划为最大化问题，则3、对偶问题为最小化问题。
4、在运输问题模型中，1m n +-个变量构成基变量的充要条件是不含闭回路。
5、动态规划方法的步骤可以总结为：逆序求解最优目标函数，顺序求__最优策略、最优路线和最优目标函数值。
6、工程路线问题也称为最短路问题，根据问题的不同分为定步数问题和不定步数问题；7、对不定步数问题，用迭代法求解，有函数迭代法和策略迭代法两种方法。
8、在图论方法中，通常用点表示人们研究的对象，用边表示对象之间的某种联系。
9、一个无圈且连通的图称为树。
10、图解法提供了求解只含有两个决策变量的线性规划问题的方法．11、图解法求解生产成本最小线性规划问题时，等成本线越往左下角移动，成本越低．12、如果线性规划问题有有限最优解，则该最优解一定在可行域的边界上上达到。
13、线性规划中，任何基对应的决策变量称为基变量．14、原问题与对偶问题是相互对应的． 线性规划中，对偶问题的对偶问题是原问题．15、在线性规划问题中，若某种资源的影子价格为10，则适当增加该资源量，企业的收益将_会 (“会”或“不会”)提高．16、表上作业法实质上就是求解运输问题的单纯形法．17、产销平衡运输问题的基变量共有m+n-1个．18、动态规划不仅可以用来解决和时间有关的多阶段决策问题，也可以处理与时间无关的多阶段决策问题．19、构成动态规划模型，需要进行以下几方面的工作：正确选择阶段（k ）变量，正确选择状态（Sk ）变量，正确选择_ 决策（UK ）变量，列出状态转移方程, 列出_阶段指标函数_，建立函数基本方程．20、动态规划方法可以用来解决和某些与时间有关的问题，但也可以用来解决和某些与时间无关的问题.在图论方法中，图是指由点与边和点与弧组成的示意图．21、网络最短路径是指从网络起点至终点的一条权之和最小的路线．简述单纯形法的计算步骤：第一步：找出初始可行解，建立初始单纯形表。
第一章绪论一运筹学的发展历史1学科起源：二战期间英美等国军事部门集中多学科人员，研究提高武器系统效能，如反空袭雷达控制系统，使雷达和高炮相配合。
诺将物理学家布莱克特（Blackett）领导研究小组“Operational Research”，多学科构成（布莱克特马戏团）。
战争结束后专家转移到企业和院校——学科形成。
2我国古代的运筹思想：齐王赛马——齐王“上中下”，田忌“下上中”丁渭修皇宫——北宋真宗宰相丁渭（澶chan州之盟的主和派），主持皇宫失火后的修复。
宫前大街取土、引汴河运料、完工后回填废土。
3我国近代以来：50年代开始钱学森、许志国等引进运筹学理论，华罗庚教授回国后从事优选法和统筹法研究推广（烧茶壶的故事）4翻译：来自汉高祖“夫运筹帷幄之中,决胜千里之外,吾不如子房;填国家,抚百姓,给饷馈,不绝粮道,吾不如萧何;连百万之众,战必胜,攻必取,吾不如韩信。
”台湾地区直译为“运作研究”。
二运筹学的特点运筹学存在多种定义，如“依照给定目标和条件，从众多方案中选择最优方案的最优化技术”，学科特点：最优化、定量化1 多种专家的协作2 科学的方法：从实际情况出发，通过假设的模型打到一个符合实际的结论3 目的在于解决实际问题。
4 需要系统的信息资料5 需要建立模型——运筹学的核心问题就是通过合适的模型分析系统的未来情况6 对于复杂问题，需要计算机三运筹学的模型运筹学的主要特点是通过模型来描述和分析所认定范围内的系统状态。
分析过程包括：1 系统分析和问题描述。
认定问题的实质——社会经济问题复杂性、不可重复性，不同于具有可控性的物理模型（提高企业效益：开发市场？增加设备？加强研发？）。
明确系统的主要目标（利润最大化、市场占有率最大化、销售收入最大化？GDP增长、可持续协调增长？）、找出系统主要变量和参数、变化范围、相互关系及其对目标的影响。
分析问题的可行性：技术可行性—有无现成的运筹学方法？经济可行性—研究的成本和预期的效果，考虑运筹决策的时间和代价，要对研究问题的深度和广度作出一定限制操作可行性—研究人员的配备2 建立数学模型——要尽可能简单；要能完整的描述所研究的系统。
运筹学讲义《管理运筹学》1、运筹学的工作步骤(1)提出和形成问题．(2)建立模型．(3)求解．(4)解的检验．(5)解的控制．(6)解的实施.2、运筹学模型三种基本形式：(1)形象模型(2)模拟模型(3)符号或数学模型构模的五种方法和思路： (1)直接分析法 (如线性规划)(2)类比法（手机的普及与电视机的普及）(3)数据分析法（如汽车销售量预测模型）(4)试验分析法（销售量与价格之间的关系模型）(5)想定(构想)法（销售与心理）3、如何将线性规划问题的一般形式化为标准形式：1.如果问题是求目标函数的最小值，求min f＝∑Cjxj则可先将目标函数乘（-1），化为求极大值问题，即求 max Z=－f=－∑Cjxj2.如果有某个bk≤0，则可将该等式两边均乘以(－1)，使右端常数项bk=－bk≥03.如果第k个约束条件是∑akjxj≤bk,引入松弛变量sk≥0 , 将它写成∑akjxj+sk＝bk如果第l个约束条件是∑aljxj≥bl则引入剩余变量(也可称为松弛变量)sl≥0，将它写成∑aljxj—sl=bl 且使松弛变量和剩余变量在目标函数中的系数为零。
4.如果对某个变量xj没有非负限制(这种变量称为自由变量或无约束变量)，则引进两个非负变量xj′，xj″，令xj＝xj′－xj″代人目标函数和约束条件中，可将它化为对全部变量都有非负限制的问题。
4、①目标函数为变量的线性函数，约束条件也为变量的线性等式或不等式的模型称之为线性规划。
②如果目标函数是变量的非线性函数，或约束条件中含有变量非线性的等式或不等式的数学模型则称之为非线性规划。
③满足所有约束条件的解称为该线性规划的可行解。
④把使得目标函数值最大(即利润最大)的可行解称为该线性规划的最优解,此目标函数值称为最优目标函数值，简称最优值5、图解法的启示1．最优解：如果某一个线性规划问题有最优解，则一定有一个可行域的顶点对应一个最优解。
（一般为封闭可行域凸集）2．无穷多个最优解：若将上例中的目标函数变为求maxZ=50x1+50x2则代表目标函数的直线平移到最优位置后将和直线x1+x2=300重合。
运筹学课程讲义第一部分 线性规划 第一章 线性规划的基本性质 1.1 线性规划的数学模型一、 线性规划问题的特点胜利家具厂生产桌子和椅子两种家具。
桌子售价50元/个，椅子售价30元/个。
生产桌子和椅子需木工和油漆工两种工种。
生产一个桌子需要木工4小时，油漆工2小时。
生产一个椅子需要木工3小时，油漆工1小时。
该厂每月可用木工工时为120小时，油漆工工时为50小时。
问该厂如何组织生产才能使每月的销售收入最大？213050m ax x x z +=⎪⎩⎪⎨⎧≥≤+≤+0,50212034212121x x x x x x 例：某工厂生产某一种型号的机床。
每台机床上需要 2.9m 、2.1m 、1.5m 的轴，分别为1根、2根和1根。
这些轴需用同一种圆钢制作，圆钢的长度为74m 。
如果要生产100台机床，问应如何安排下料，才能用料最省？二、 数学模型的标准型 1. 繁写形式 2. 缩写形式 3. 向量形式 4. 矩阵形式三、 任一模型如何化为标准型？1. 若原模型要求目标函数实现最大化，如何将其化为最小化问题？2. 若原模型中约束条件为不等式，如何化为等式？3. 若原模型中变量x k 是自由变量，如何化为非负变量？4. 若原模型中变量x j 有上下界，如何化为非负变量？⎪⎪⎩⎪⎪⎨⎧≥≤-=--≤+--≥-+----=无约束321321321321321,0,052010651535765max x x x x x x x x x x x x x x x z 令'''3'3''3'331'1,0,,,Z Z x x x x x x x =-≥-=-=⎪⎪⎩⎪⎪⎨⎧≥-=+-++=+-+-=+-+-+--+-++-=0,,,,,,,5201010651533507765min 7654''3'32'17''3'32'15''3'32'164''3'32'1765''3'32'1'x x x x x x x x x x x x x x x x x x x x x x x x Mx Mx x x x x x z 1. 2图解法该法简单直观，平面作图适于求解二维问题。
第二讲 运输问题11111,2,, ..1,2,, 0mnij iji j nij i j m ij j i ij MinZ w x x a i m s tx b j n x =====⎧==⎪⎪⎪⎨==⎪⎪≥⎪⎩∑∑∑∑产地约束销量约束定理1 运输问题的数学模型必有最优解。
运输问题基变量的个数为m +n －1 。
对于运输问题的基可行解，m ×n 个变量中至多只能有m +n －1个变量取正值，而其他的变量为零 一、基本概念1）数字格 2）空格 3）闭回路结论1： 运输问题的一个可行解是基可行解的充要条件是： 1）数字格的个数为m+n-1个2） m+n-1个数字格不构成闭回路（从数字格出发） 结论2： 对每一个空格处，有且仅有一条闭回路。
例：判断下表给出的调运方案能否作为表上作业法求解时的初始解二、表上作业法（1）初始方案的确定：最小元素法；伏格尔法 （2）最优性检验：闭回路法；位势法 （3）闭回路内改进方案 (1.1)最小元素法(就近供应)就进供应，即从单位运价表中最小的运价开始确定供销关系，然后次小，一直到求出初始基可行解为止。
销地7410206563b j5810947a i 1391123A 3A 2A 1B 4B 3B 2B 1产地(1.2)伏格尔法销地7410206563b j5810947a i 1391123A 3A 2A 1B 4B 3B 2B 1产地(2.1)闭回路法计算检验数∑∑-=σ偶奇ij ij ijc c注：1)数字格检验数均为0 2)空格检验数销地7410206563b j5810947a i 1391123A 3A 2A 1B 4B 3B 2B 1产地③④①⑥③③(2.2)位势法求检验数j i cv u =+对数字格而言计算）行势、列势的定义与注：:13）行势、列势可不唯一，但检验数是一致的。
σ),()2=σ+-=ij j i ij ij v u c 数字格检验数的计算：空格销地7410206563b j5810947a i 1391123A 3A 2A 1B 4B 3B 2B 1产地③④①⑥③③（3）闭回路内改进方案销地741058101391123A 3A 2A 1B 4B 3B 2B 1产地③④①⑥③③121-11012（06年，第三题，20分）下表是一运输问题的表格，其中右上角数字是单位运价，方框内是运量。
