模型决策法简介(ppt 35页).ppt

第六章模型决策方法、线性规划等时序和路径规划分配问题最短路径问题最大流问题、模型决策方法、优化模型max(min)目标函数s.t .约束、线性规划模型的建立、示例1两个产品的生产。生产单位产品所需的设备台和a、b这两种原材料的消耗、资源限制和市场价格如下表所示： 资源限制设备11300大原材料a 21400kg公斤原材料b 01250kg公斤市场价格50100问题：如何安排生产计划，使工厂利润最大化？计划和决策，分析：(1) x1设置-生产产品数量；X2-生产产品数量。(2)目标函数：MAX50 x1 100 x2(3)约束：subject to(s . t .)3360 x1x 23002 x2400 X2250 x1，X2.cnxns.t.a11x 1.a1 nxn；(，=) B1 a21 x 1.a2 nxn；(，=) B2.am1x1.amn xn；(，=) bmx ij 0i=1，n，j=1，m，计划和决策，线性编程应用领域：板，导线问题成分问题投资问题生产计划问题，劳动力配置问题；运输问题，电子商务流通问题；企业决策问题企业或商业竞争应对问题等。计划和决策，以及典型的线性编程建模过程步骤1。理解和分析实际问题、资源情况、解决问题的目标；Step2。决定变量(x1，xn)决定-解决问题的具体解决方案(量化方案)；步骤3 .目的函数和约束条件的确定；步骤4 .线性规划软件解决方案的应用；Step5。检查得到的解决方案是否妥当：如果可能，就开始具体实施；否则，请转至Step1或Step2并修改模型。计划和决策，案例2:(生产计划问题)公司面临外协加工或自身生产问题。这家公司生产三种产品，这三种产品都要经过铸造、加工、组装。甲和乙两种产品的铸造可以外协加工，也可以自行生产。但是c产品的铸造只有自行生产才能保证质量。有关资料，请参阅下表：计划和决定、工作时间和费用a&b c总工作时间(小时)510078000各机器加工工作时间(小时)64812000各组装工作时间(小时)3221000各生产铸件的费用(元)354各委外铸件的费用(元)、计划和决策，分析：集Xi-公司加工a、b、c三个产品数量，i=1，2，3。X4，X5-委外加工后，公司加工与组装的a，b产品数量：目标函数：每个产品利润为：每个x1的产品利润333623-(3 2 3)=15元每个x2的产品利润：118-(5 1 2)=10元每个x3的产品利润333616-(4 3 2)=7元每个x4的产品利润333623-(5 2 3)120003 x12x 3 x42x 5；10000xi 0i=1，5，规划和决策，图形化：Step1。确定可执行域D=x|x满足上述约束下面的图2-1: step 2。检查线50 x1 100 x2=0下面的图2-2-1:Step2 3。向上移动直线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、计划和加工每个部件的平均每周需求、当前库存水平和批所需的时间如下表所示：如何排列每个零件的生产顺序？零件ABCDEF的平均需求1043333473目前存货数量72214892823处理时间2.01.01.5，（.)，计时计划问题，（.)，计时计划问题，计时计划问题，(3)到期日最新政策，(3)到期日最新政策，(3)计时计划问题，“最短处理时间优先”如果操作尚未延迟，则这是最佳解决方案。否则，请继续执行步骤2。步骤2:在调度的计时中查找一个延迟的作业。查找处理时间最长的作业，包括在步骤3:2中找到的作业本身。步骤4:从时间安排中提取此作业并更新其时间。如果还有延迟的任务，请转到步骤2，否则转到步骤5。将步骤5:4中提取的任务放在计时的末尾。范例3:继承上述范例中的8个工作，以解决工作延迟项目数最小的计时。为此，请使用上述步骤5。任务ABCDEFGH处理时间2584723到期时计时计划问题、步骤1:按到期时间对任务进行排序。任务GBCAEFDH到期时间27813142036启动处理时间027171231262331处理时间2524783完成处理时间27710121623134延迟任务* * *步骤2:在上述计时中延迟1的任务为c。步骤3:到c为止，处理时间最长的作业(包括c)为b，处理时间为5。计时计划问题；步骤4:提取作业b并更新相关时间。任务GCAEFDH过期时间283142036开始处理时间025711826处理时间2324783处理时间2571182629步骤5:现在，由于任务没有延迟，因此将任务b添加到计时的末尾。任务GCAEFDHB到期时间2831420367启动处理时间02571182629处理时间23247835完成处理时间25718262934当前只有一个任务延迟平均等待时间为98/8=12.25，平均延迟时间为27/8=3.375天。计时计划问题、(5)Johnsonsrule(约翰逊原则)步骤1:列出每台机器的操作和处理时间。步骤2:查找每个系统上处理时间最短的下一个任务。第三步：如果这是在机器1上，请尽量把这项工作放在前面；如果这在机器2上，请尽量把这件事放在后面。重复此操作时，总是从计时的两端向内进行，新分配的任务更接近计时的中间。步骤4:不再思考此任务，返回到步骤2。如果再也找不到这样的任务，这是最佳解决方案。实例4:有7个任务按顺序处理机器1和机器2。在每台机器上，每项作业所需的处理时间如下：定时间才能最大限度地提高机器利用率。任务ABCDEFG机器12584129机器214730566，时序计划问题，时序计划问题，调度问题，总成本最小化为目标，如何在每个系统上部署操作员。原则：每个操作员只能指定一个任务，每个任务只能由一个人完成。Cij I操作员完成第j个任务的成本xijmin cijxij xij=1 xij=1xi j=0，1i=1，n，j=1，m，=1(调度操作员I完成任务j)=0(不调度操作员I完成任务j)，j，I，最短路径问题G(V，E)是连接的图表，边缘(vi，vj)，v2216 v47 V6，46，v21128 V7，18