第六章模型决策法(3).ppt

第六章模型决策法,线性规划等时序与路径规划分派问题最短路问题最大流问题,模型决策法,优化模型max(min)目标函数s.t.约束条件,线性规划模型的建立,实例1两种产品的生产。已知生产单位产品所需的设备台时及A、B两种原材料的消耗，资源限制及市场价格如下表：资源限制设备11300台时原材料A21400千克原材料B01250千克市场价格50100问题：如何安排生产，才能使工厂获利最多？,规划与决策,分析：（1）设x1生产产品的数量；x2生产产品的数量。（2）目标函数：MAX50 x1+100 x2（3）约束条件：subjectto(s.t.):x1+x23002x1+x2400 x2250 x1,x20,规划与决策,线性规划模型：max50 x1+100 x2s.t.x1+x23002x1+x2400 x2250 x1,x20,规划与决策,线性规划模型的一般形式maxc1x1+c2x2+cnxns.t.a11x1+a1nxn(,=)b1a21x1+a2nxn(,=)b2am1x1+amnxn(,=)bmxij0i=1,n,j=1,m,规划与决策,线性规划应用领域：合理利用板、线材问题；配料问题；投资问题；生产计划问题、劳动力安排问题；运输问题、电子商务配送问题；企业决策问题；企业或商业竞争对策问题等。,规划与决策,一般线性规划建模过程Step1.理解及分析实际问题，资源状况，解决问题实现的目标；Step2.确定决策变量（x1,，xn）解决问题的具体方案（量化方案）；Step3.确定目标函数及约束条件；Step4.应用线性规划软件求解；Step5.检验所求得的解决方案是否可行：如可行，则开始具体实施；否则，转Step1或Step2修改模型。,规划与决策,案例2：（生产计划问题）某公司面临一个外协加工还是自行生产问题。该公司生产甲、乙、丙三种产品，这三种产品都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸造可以外协加工，亦可以自行生产。但丙产品的铸造必须自行生产才能保证质量。有关数据见下表：,规划与决策,工时与成本甲乙丙总工时每件铸造工时（小时）51078000每件机加工工时（小时）64812000每件装配工时（小时）32210000自产铸件每件成本（元）354外协铸件每件成本（元）56-机加工每件成本（元）213装配每件成本（元）322每件产品售价（元）231816问题：如何安排生产计划，使公司获利最大？,规划与决策,分析：设xi公司加工甲、乙、丙三种产品数量，i=1,2,3。x4、x5由外协铸造后再由本公司机加工和装配的甲、乙两种产品数量；目标函数：每件产品利润分别是：每件x1产品利润:23-（3+2+3）=15元每件x2产品利润:18-（5+1+2）=10元每件x3产品利润:16-（4+3+2）=7元每件x4产品利润:23-（5+2+3）=13元每件x5产品利润:18-（6+1+2）=9元目标函数为：max15x1+10 x2+7x3+13x4+9x5,规划与决策,约束条件：5x1+10 x2+7x380006x1+4x2+8x3+6x4+4x5120003x1+2x2+2x3+3x4+2x510000 xi0i=1,5,规划与决策,图解法:Step1.确定可行域D=x|x满足上述约束条件如下图2-1：Step2.确定直线50 x1+100 x2=0如下图2-2：Step3.向上移动直线50 x1+100 x2=0如图2-2，z=50 x1+100 x2的值不断地增加，达到B点时，达到最大；Step4.最优解为B=(50,250),z最大=27500。,规划与决策,0100200300,300,200,100,D,图2-1,规划与决策,0100200300,300,200,100,D,B(50,250),Z=50 x1+100 x2,图2-2,时序与路径规划,讨论各种时序规划问题介绍时序规划原则分派问题运输问题网络的最短路径网络的最大流,时序规划问题,A,B,E,F,D,C,机器,机器,D,E,F,C,A,B,等待处理的一批工作,按最优次序排队,一台机器工作的时序规划,时序规划问题,原则：(1)最紧迫的优先实例1：6种部件作为一批等待一台机器加工。每一部件的平均周需求量、当前的存货水平以及加工一批所需时间如下表，你将如何安排各种部件的生产次序？部件ABCDEF平均需求量104263473当前存货量722148922823加工时间2.01.50.50.51.01.5,时序规划问题,时序规划问题,时序规划问题,以“加工时间最短者优先”为原则,时序规划问题,以“加工时间最短者优先”为原则,时序规划问题,(3)到期日最近者原则,时序规划问题,(3)到期日最近者原则,时序规划问题,(4)延误的工作项目最少第1步：运用先到期者优先的原则排出工作的初始次序。如果已经没有工作被延误，这便是最优解，否则，则进行第2步。第2步：在安排的时序中找到1项延误的工作。第3步：找出第2步所找工作之前（包括这一工作本身）加工时间最长的工作。第4步：将这一工作从时序安排中抽出来，并更新相应的时间。如果仍然有被延误的工作，再转向第2步，否则转向第5步。第5步：将第4步抽出的工作放到时序的末尾。实例3：沿用上述实例的8项工作，求解工作延误项数最少的时序。为此我们采用上述五个步骤。工作ABCDEFGH加工时间25384723到期时间1378301420236,时序规划问题,第1步：将工作按到期时间排序。工作GBCAEFDH到期时间2781314203036开始加工时间0271012162331加工时间25324783完成加工时间27101216233134延误工作*第2步：在上述时序中，第1项被延误的工作是C。第3步：到C之前，包括C在内，加工时间最长的工作是B，加工时间为5。,时序规划问题,第4步：抽出工作B，更新相关的时间：工作GCAEFDH到期时间281314203036开始加工时间0257111826加工时间2324783完成加工时间25711182629第5步：现在已经没有工作被延误了，所以我们将工作B加到时序的最后。工作GCAEFDHB到期时间2813142030367开始加工时间025711182629加工时间23247835完成加工时间2571118262934现在只有一项工作被延误，平均排队时间为98/8=12.25，平均延误时间为27/8=3.375天。,时序规划问题,(5)Johnsonsrule(约翰逊原则)步骤1：列出各项工作及它们在每台机器上的加工时间。步骤2：找出下一个在各台机器上加工时间最短的工作。步骤3：如果这是在机器1上，尽量将这一工作安排在前面；如果这是在机器2上，尽量将这一工作安排在后面。在重复做这些的时候，总是从时序的两端向内进行，新安排的工作离时序的中间更近。步骤4：不必再考虑这一工作，回到步骤2。如果再找不到这样的任务，这就是最优解。实例4：有7项工作要顺序经过机器1和机器2加工。每项工作在每台机器上所需的加工时间如下，如何安排时序才能使机器利用率最高。工作ABCDEFG机器1251084129机器2147310566,时序规划问题,时序规划问题,分派问题,如何以总成本最低为目标将操作员分派到各台机器上。原则：每个操作员只能分派给一项任务，每项任务只能由一人完成。Cij第i个操作员完成第j项任务的成本XijminCijXijXij=1Xij=1Xij=0,1i=1,n,j=1,m,=1(分派操作员i完成任务j)=0(不分派操作员i完成任务j),j,i,最短路问题,最短路问题G(V,E)为连通图，边（vi,vj)的权为lij，求一条道路，使它从vs到vt的总权最少？方法：1动态规划法2Dijkstra算法引例：某一配送中心要给一个快餐店送快餐原料，应按什么路线送货才能使送货时间最短？,V216v47v6,46,V11228v7,185,V36v5,（配送中心）,（快餐店）,最大流问题,最