医疗行业模型决策法分析

第六章模型决议法线性规划等时序与路径规划分配问题最短路问题最大流问题医疗行业模型决策法分析第1页模型决议法优化模型max(min)目标函数s.t.约束条件医疗行业模型决策法分析第2页线性规划模型建立实例1两种产品生产。已知生产单位产品所需设备台时及A、B两种原材料消耗，资源限制及市场价格以下表： Ⅰ Ⅱ 资源限制 设备 1 1 300台时 原材料A 2 1 400千克 原材料B 0 1 250千克 市场价格 50 100 问题：怎样安排生产，才能使工厂赢利最多？医疗行业模型决策法分析第3页规划与决议分析：（1）设x1—生产产品Ⅰ数量；

x2—生产产品Ⅱ数量。（2）目标函数：MAX50x1+100x2（3）约束条件：subjectto(s.t.):

x1+x2≤3002x1+x2≤400x2≤250x1,x2≥0医疗行业模型决策法分析第4页规划与决议线性规划模型：

max50x1+100x2

s.t.x1+x2≤3002x1+x2≤400x2≤250x1,x2≥0医疗行业模型决策法分析第5页规划与决议线性规划模型普通形式

maxc1x1+c2x2+…+cnxn

s.t.a11x1+…+a1nxn≤(≥,=)b1a21x1+…+a2nxn≤(≥,=)b2

…am1x1+…+amnxn≤(≥,=)bm

xij≥0i=1,…,n,j=1,…,m医疗行业模型决策法分析第6页规划与决议线性规划应用领域：合理利用板、线材问题；配料问题；投资问题；生产计划问题、劳动力安排问题；运输问题、电子商务配送问题；企业决议问题；企业或商业竞争对策问题等。医疗行业模型决策法分析第7页规划与决议一般线性规划建模过程Step1.了解及分析实际问题，资源情况，处理问题实现目标；Step2.确定决议变量（x1,…，xn）—处理问题详细方案（量化方案）；Step3.确定目标函数及约束条件；Step4.应用线性规划软件求解；Step5.检验所求得处理方案是否可行：如可行，则开始详细实施；不然，转Step1或Step2修改模型。医疗行业模型决策法分析第8页规划与决议案例2：（生产计划问题）某企业面临一个外协加工还是自行生产问题。该企业生产甲、乙、丙三种产品，这三种产品都需要经过铸造、机加工和装配三个车间。甲、乙两种产品铸造能够外协加工，亦能够自行生产。但丙产品铸造必须自行生产才能确保质量。相关数据见下表：医疗行业模型决策法分析第9页规划与决议工时与成本 甲 乙 丙 总工时 每件铸造工时（小时） 5 10 7 8000 每件机加工工时（小时） 6 4 8 1 每件装配工时（小时） 3 2 2 10000 自产铸件每件成本（元） 3 5 4 外协铸件每件成本（元） 5 6 - 机加工每件成本（元） 2 1 3 装配每件成本（元） 3 2 2 每件产品售价（元） 23 18 16 问题：怎样安排生产计划，使企业赢利最大？医疗行业模型决策法分析第10页规划与决议分析：设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+10x2+7x3+13x4+9x5医疗行业模型决策法分析第11页规划与决议约束条件：5x1+10x2+7x3

≤80006x1+4x2+8x3+6x4+4x5

≤13x1+2x2+2x3+3x4+2x5

≤10000xi

≥0i=1,…,5医疗行业模型决策法分析第12页规划与决议图解法:Step1.确定可行域D={x|x满足上述约束条件}以下列图2-1：Step2.确定直线50x1+100x2=0以下列图2-2：Step3.向上移动直线50x1+100x2=0如图2-2，z=50x1+100x2值不停地增加，到达B点时，到达最大；Step4.最优解为B=(50,250),z最大=27500。医疗行业模型决策法分析第13页规划与决议

0100200300300200100D图2-1医疗行业模型决策法分析第14页规划与决议

0100200300300200100DB(50,250)Z=50x1+100x2图2-2医疗行业模型决策法分析第15页时序与路径规划讨论各种时序规划问题介绍时序规划标准分配问题运输问题网络最短路径网络最大流医疗行业模型决策法分析第16页时序规划问题

ABEFDC机器机器DEFCAB等候处理一批工作按最优次序排队一台机器工作时序规划医疗行业模型决策法分析第17页时序规划问题标准：(1)最紧迫优先实例1：6种部件作为一批等候一台机器加工。每一部件平均周需求量、当前存货水平以及加工一批所需时间以下表，你将怎样安排各种部件生产次序？部件ABCDEF平均需求量104263473当前存货量722148922823加工时间2.01.50.50.51.01.5医疗行业模型决策法分析第18页时序规划问题

医疗行业模型决策法分析第19页时序规划问题

医疗行业模型决策法分析第20页时序规划问题

以“加工时间最短者优先”为标准医疗行业模型决策法分析第21页时序规划问题

以“加工时间最短者优先”为标准医疗行业模型决策法分析第22页时序规划问题(3)到期日最近者标准医疗行业模型决策法分析第23页时序规划问题(3)到期日最近者标准医疗行业模型决策法分析第24页时序规划问题(4)延误工作项目最少第1步：利用先到期者优先标准排出工作初始次序。假如已经没有工作被延误，这便是最优解，不然，则进行第2步。第2步：在安排时序中找到1项延误工作。第3步：找出第2步所找工作之前（包含这一工作本身）加工时间最长工作。第4步：将这一工作从时序安排中抽出来，并更新对应时间。假如依然有被延误工作，再转向第2步，不然转向第5步。第5步：将第4步抽出工作放到时序末尾。实例3：沿用上述实例8项工作，求解工作延误项数最少时序。为此我们采取上述五个步骤。工作ABCDEFGH加工时间25384723到期时间1378301420236医疗行业模型决策法分析第25页时序规划问题第1步：将工作按到期时间排序。工作GBCAEFDH到期时间2781314203036开始加工时间0271012162331加工时间25324783完成加工时间27101216233134延误工作****第2步：在上述时序中，第1项被延误工作是C。第3步：到C之前，包含C在内，加工时间最长工作是B，加工时间为5。医疗行业模型决策法分析第26页时序规划问题第4步：抽出工作B，更新相关时间：工作GCAEFDH到期时间281314203036开始加工时间0257111826加工时间2324783完成加工时间25711182629第5步：现在已经没有工作被延误了，所以我们将工作B加到时序最终。工作GCAEFDHB到期时间2813142030367开始加工时间025711182629加工时间23247835完成加工时间2571118262934现在只有一项工作被延误，平均排队时间为98/8=12.25，平均延误时间为27/8=3.375天。医疗行业模型决策法分析第27页时序规划问题(5)Johnson’srule(约翰逊标准)步骤1：列出各项工作及它们在每台机器上加工时间。步骤2：找出下一个在各台机器上加工时间最短工作。步骤3：假如这是在机器1上，尽可能将这一工作安排在前面；假如这是在机器2上，尽可能将这一工作安排在后面。在重复做这些时候，总是从时序两端向内进行，新安排工作离时序中间更近。步骤4：无须再考虑这一工作，回到步骤2。假如再找不到这么任务，这就是最优解。

实例4：有7项工作要次序经过机器1和机器2加工。每项工作在每台机器上所需加工时间以下，怎样安排时序才能使机器利用率最高。工作ABCDEFG机器1251084129机器2147310566医疗行业模型决策法分析第28页时序规划问题

医疗行业模型决策法分析第29页时序规划问题

医疗行业模型决策法分析第30页分配问题怎样以总成本最低为目标将操作员分配到各台机器上。标准：每个操作员只能分配给一项任务，每项任务只能由一人完成。Cij

第i个操作员完成第j项任务成本Xij

minΣΣCijXijΣXij=1ΣXij=1Xij=0,1i=1,…,n,j=1,…,m=1(分配操作员i完成任务j)=0(不分配操作员i完成任务j)ji医疗行业模型决策法分析第31页最短路问题最短路问题G(V,E)为连通图，边（vi,vj)权为lij，求一条道路，使它从vs到vt总权最少？方法：1动态规划法2Dijkstra算法引例：某一配送中心要给一个快餐店送快餐原料，应按什么路线送货才能使送货时间最短？医疗行业模型决策法分析第32页V216v47v64