运筹学

——怎样把事情做到最好OPERATIONSRESEARCH运筹学(OR)绪论Operations汉语翻译工作、操作、行动、手术、运算OperationsResearch日本——运用学港台——作业研究中国大陆——运筹学OperationalResearch原来名称，意为军事行动研究定义：P1历史：P2步骤：P3~5分支：P5规划论：线性规划、非线性规划、整数规划、目标规划、动态规划图论与网络存储论排队论决策论对策论计算机仿真第一章线性规划及单纯形法线性规划研究的主要问题一类是已有一定数量的资源（人力、物质、时间等），研究如何充分合理地使用它们，才能使完成的任务量为最大。——实际上，上述两类问题是一个问题的两个不同的方面，都是求问题的最优解（max或min）。另一类是当一项任务确定以后，研究如何统筹安排，才能使完成任务所耗费的资源量为最少。第一节一般线性规划问题的数学模型一、线性规划问题的提出例1、某企业有A、B两种设备，计划期内要安排加工甲、乙两种产品，按加工要求产品在各设备上需加工台时数如下表，已知A、B设备每天的有效台时分别为10，14，已知每生产一件甲可以得利润4元，乙可得6元。问两种产品每天各生产多少，才能获得最大利润。AB甲乙2212设备产品例2、某厂生产三种药物，这些药物可以从四种不同的原料中提取。下表给出了单位原料可提取的药物量求:四种原料的使用量分别为多少?要求：生产A种药物至少160单位；B种药物恰好200单位，C种药物不超过180单位，且使原料总成本最小。解：1.设四种原料的使用量分别为：x1、x2、x3、x42.设总成本为z，则有：minz=5x1+6x2+7x3+8x43.约束条件：x1+2x2+x3+x4≥1602x1+4x3+2x4＝1603x1＋x2+x3+2x4≤180x1、x2、x3、x4≥0药物原料ABC单位成本（元／吨）甲1235乙2016丙1417丁1228它们具有以下共同点：具有这种特点的问题称为线性规划问题。2、决策变量取值都要满足一定的限制条件，这些限制条件称为约束条件，并且约束条件可以表示为决策变量的一组线性不等式或线性等式；3、每个问题都有一个要达到的目标要求，而且能够表示为决策变量的线性函数，称为目标函数。1、每个问题含有需要求解的变量，这些变量称决策变量；二、线性规划的数学模型1、线性规划的概念线性规划是在一组给定的线性约束条件下，求线性的目标函数的最大（小）值2、线性规划的数学模型一般地，线性规划问题的数学模型表示为max（或min）自由,00,,,),(),(),(..2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxatsnnxcxcxcZ2211目标函数约束条件非负约束称为决策变量),,2,1(njxj称为价值系数或目标函数系数),,2,1(njcj称为资源常数或约束右端常数),,2,1(mibi称为技术系数或约束系数),...2,1;,...,2,1(aijnjmi紧缩形式：max（或min）njjjxcZ1njxbxatsjnjijij,,2,10),(..1i=1,2,…..,m3、线性规划的标准形式为讨论方便，我们规定线性规划问题的标准形式为：①目标最大；②约束等式；③变量非负；④右端非负。nnxcxcxcZ2211max0,,,..2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxats简写为:maxZ=Σcjxjnj=1Σnj=1aijxj=bii=1,2,···,mXj0j=1,2,···,n约束方程组非负条件目标函数当目标函数为求最小值时，可通过变换将目标函数化为求最大值问题。1.minZ=Σcjxjnj=1设原问题为令Z′=-Z,则有maxZ′=Σ（-cj）Xjnj=1当约束条件为不等式时，分以下两种情况作相应的处理：2.（1）形如Σaijxjbjnj=1引进松弛变量xn+1可将不等式化为等式：Σaijxj+xn+1=bjnj=1且xn+10（2）形如Σaijxjbjnj=1引进剩余变量xn+1把不等式化为等式：Σaijxj-xn+1=bjnj=1且xn+103、若约束条件右面的某一常数项bi0则在bi相对应的约束方程两边乘上－14、若变量Xj无非负限制则引进两个非负变量Xj’、Xj’’0，令Xj＝Xj’－Xj’’5、若变量xj0，则令Xj’＝－Xj任何形式的线性规划总可以化成标准型32132minxxxZ符号不受限制321321321321,0,1382310..xxxxxxxxxxxxts54''332100)(32maxxxxxxxZ0,,,,,1)(38)(2310)(..54''3321''33215''33214''3321xxxxxxxxxxxxxxxxxxxxts三、线性规划模型建立的一般步骤1、确定决策变量2、确定目标函数3、确定约束条件四、线性规划的应用应用条件：p43例：人员安排问题医院护士24小时值班，每次值班开始时间只能为各时间段的开始时间，每次值班8小时。不同时段需要的护士人数不等（如下表）。医院至少需要多少护士才能满足要求。序号时段最少人数安排人数106—1060X1210—1470X2314—1860X3418—2250X4522—0220X5602—0630x6阅读P44：例13，例14练习：1、某工厂生产一种产品，这批产品共需要30吨铅，35吨铜和45吨铁。现有四种矿石可供选购，它们每吨含有的成分和价格如下表。现要确定每种矿石选购多少，使费用最省。矿石成分%ABCD铅铜铁2310.542314235每吨价格10153025船只种类船只数拖轮30A型驳船34B型驳船52航线号合同货运量12002400航线号船队类型编队形式货运成本（千元／队）货运量（千吨）拖轮A型驳船B型驳船1112—362521—4362023224724041—42720问：应如何编队，才能既完成合同任务，又使总货运成本为最小？2、某航运局现有船只种类、数量以及计划期内各条航线的货运量、货运成本如下表所示：minZ=x1+2x2目标函数约束条件3、将下列线性规划问题化为标准型2X1+3X2≤6X1+X2≥4X1-X2=－3X1≥0、X2无约束作业一：P491.13；1.14