数据、模型与决策课程解题思路

数据、模型与决策课程解题思路一、不确定性决策收益矩阵的格式 ——横表头为市场情况，列表头为方案；乐观准则 ——最大最大：按行找出各方案中最大收益，选择最大收益最大的方案；悲观准则 ——最大最小：按行找出各方案中最小收益，选择最小收益最大的方案；等可能准则 ——最大平均：按行计算出各方案的平均收益，选择平均收益最大的方案；后悔值准则 ——最小最大后悔：按列找出各种市场情况下最大收益值，用最大收益值减去本列的各个收益得其后悔值，按行找出各方案的最大后悔值，选择后悔值最小的方案；乐观系数准则 ——最大加权平均：按行找出各方案中最大和最小收益值，以“乐观系数”和“1－乐观系数”为权计算最大和最小收益值的加权平均值，选择加权平均值最大的方案。以课堂作业1举例如下：市场需求量乐观准则悲观准则等可能准则乐观系数准则大中小失败最大最大最大最小最大平均最大加权平均扩建502510-1550-1517.530.5新建7030-10-4070-4012.537外包3015-5-1030-107.518市场需求量后悔值准则大中小失败后悔值最小最大扩建502510-152050520新建7030-10-4000203030外包3015-5-10401515040二、规划模型的标准化解题思路：标准形式的约束条件有三个要件，一是常数项非负；二是只能有等式；三是定义域非负。根据上述要件，分四步操作：A、判断常数项是否非负，如有负值则两边同乘（-1），并相应改变不等号方向；B、判断是否有不等式，如有则设松弛或剩余变量xi≥0，大于号减、小于号加xi变等式；C、判断各变量的定义域是否非负，如为负值，则设xj=（-xi）≥0，代入模型；如为-∞≤xk≤∞，则设xk=（xm－xn），xm、xn≥0，代入模型；D、整理变量下标后，得到标准形式。三、线性规划模型的解法及敏感性分析A、图解步骤如下：1、以x1为横轴、x2为纵轴建立直角坐标系，标出各约束条件和目标函数的直线；2、在第一象限找出可行域；3、目测目标函数平移后最可能与可行域的哪个顶点相切，则该点为最优解点；4、解方程得到该点坐标，即得最优解，代入目标函数得最优值。5、小技巧：(1)作图时，对约束条件，可分别令x1和x2为零，得到其与纵轴和横轴的交点，连接即可；对目标函数，令x1为一特殊值，得出x2，再与原点相连，可得函数直线，再沿横轴平移到合适位置即；(2)各条直线斜率绝对值越大的，越接近垂直于x1轴；(3)确定可行域时，要考虑坐标轴和原点；(4)目测判断最优点不易时，可将相邻数点的坐标解出代入目标函数进行比较。B、松弛变量和剩余变量1、约束条件为“≤”的存在松弛变量，为“≥”的存在剩余变量；2、将最优解代入各约束条件即得各自的松弛或剩余变量；3、构成最优解的约束条件的松弛或剩余变量为零。C、对偶价格1、不构成最优解的约束条件的对偶价格为零；2、构成最优解的约束条件存在对偶价格，求解时令其中一个约束条件的常数项增加1，另一个约束条件不变，重新解出交点坐标，代回目标函数计算目标值，再与原最优值相差即得；3、对偶价格的讨论均在各约束条件常数项的上、下限范围内进行，超范围时对偶价格可能发生变化；4、已知对偶价格和最优值求常数项变化时，目标函数求Max时，增加目标值的，常数项同向变化，即增大；求Min时，增加目标值的，常数项反向变化，即减少；反之亦然。D、目标函数系数上、下限1、目标函数系数的变化，在图解时可视为目标函数直线斜率的变动，即该直线以最优解点为支点旋转；其取值范围为最优解不变的范围，即不突破构成最优解的两条直线斜率kmin和kmax的范围。2、求解时，将目标函数变换为x2=(-c1/c2)*x1的形式，通过kmin≤(-c1/c2)≤kmax，分别代入c1或c2，可得c2或c1的上、下限。E、约束条件常数项的上、下限1、约束条件常数项的变化，在图解时可视为约束条件直线在纵轴上截距的变动，即该直线沿横轴平移，不会与另两条约束条件直线交点相交的范围，也就是不会改变可行域的结构、不会减少可行域边数（坐标轴不算）的范围；其取值范围为对偶价格不变的范围，但有可能会改变最优解和最优值。2、求解时，找到该约束条件相邻的两个可行域的顶点坐标(xa,xb)，根据x2-xb=k*(x1-xa)点斜式方程，分别求出约束条件平移至该两个顶点的在横轴上的截距、即变化后的常数项上、下限。 F、百分之一百法则1、增加率和减少率之和不超过100%；2、增加（减少）率＝增加（减少）值/允许增加（减少）值；增减值以当前值为基数计算，允许增减值以当前值为基数、各值取值范围的上、下限计算；3、多个目标函数系数变动时，其意义为最优解不变；多个约束条件常数项变动时，其意义为对偶价格不变；不适用目标函数系数和约束条件常数项同时变动的情况，也不适用于相关系数和常数项同步增减（即有增无减、或在减无增）的情况。G、相差值1、最优解中为零的变量，其系数变化到不为零时的差值；2、最优解中不为零的变量，其相差值必为零；3、目标函数求Max时，其相差值为其上限值减去当前值，且该系数无下限；目标函数求Min时，其相差值为其下限值减去当前值，且该系数无上限；四、线性规划模型的建立A、问题的实质——在某些资源限制下，求利润最大或成本最小。这些资源限制包括资金、物料、工时的最高或最低要求等，关键是找到合适的变量，将目标和限制联系起来。B、人力资源问题——按循环周期计算当天（单位时间）内上班或休息的人数并与限制条件相比较xi为每天（单位时间）上班或休息的人数；Min配备的总人数、上班或休息的人员（成本最低）S.T.满足每天（单位时间）上班或休息人数的限制xi≥0C、生产计划问题——按不同生产车间或工序生产产品的件数及其所需的物料、设备或工时与限制相比较xi为每个车间或工序生产产品的件数；Max利润或Min成本S.T.1、满足物料、设备或工时的限制2、各工序生产的产品数量应相等xi≥0D、套裁下料问题——列出一根整料所有可行的裁料方案，不同裁料方案运用的次数及其所得不同规格工件的总数与总需求量相比较xi为每种裁料方案的运用次数，最终整料的使用量为xi之和；Min裁料方案运用次数之和；S.T.各种裁料方案裁得的不同规格的工件必须不少于其总需求量；xi≥0E、配料问题——每种产品中各原料的比例应满足要求，且各原料的总使用量不得超过限制xi为每种产品中各原料的使用量；Max利润或Min成本；S.T.1、每种产品中各原料的比例；2、各原料的使用量少于限制量；xi≥0F、连续投资问题——根据项目回收期不同列出各年各种方案可能的投资表，总收益为各项目最后一期投资的和，各期的投资应等于期初资金（也就是上一期投资的收入）xi为每项目在各年的投资额；Max总收益或Min总风险；S.T.1、各期的投资等于期初资金（也就是上一期投资的收入）；2、满足各期投资限制xi≥0五、运输模型A、产销表的基本形式销地产地销地1销地2销地……产量产地1产地2产地……销量总产量总销量B、基本运输问题的线性规划求解令各产地运往各销地的货物量为xi，则：Min运费（xi乘以运价）S.T.每个产地的产量等于运往各销地的货物量每个销地的销量等于运往该地的货物量xi≥0C、产销不平衡问题——转化为产销平衡问题产大于销时，增加虚拟销地，即增加一列，该列的运费为“0”，销量为差额；销大于产时，增加虚拟产地，即增加一行，该行的运费为“0”，产量为差额；D、有条件的产销不平衡问题——转化为产销平衡问题当销大于产，且部分销地的产销量可在一定范围内变化时：1、将该销地的销售拆分为两地，即一列变两列，其中一列的销量为该销地的基数，另一列的销量为其可变数，各产地至该两个销地的运费不变；2、增加虚拟产地，即增加一行，该行中到基数销地的运费为M（意为足够大），到可变数销地的运费为“0”，该行的产量为产销的差额；3、当存在销量不限的销地时，各真实产地到该销地的运费为M，虚拟产地到该销地的运费为“0”，虚拟产地的产量为各销地可变数之和。E、生产存储问题——将各期视为产销地，各期的生产量和交货量分别视为产量和销费，各期生产的产品其生产成本与至交货期的存储成本之和视为运费，其中按时间顺序不存在交货的运费为M，转化运输问题。销地产地第一季度第二季度第三季度第四季度生产量（产量）第一季度生产成本1生产成本1+存储成本生产成本1+存储成本×2生产成本1+存储成本×3第二季度M生产成本2生产成本2+存储成本生产成本2+存储成本×2第三季度MM…………第四季度MMM……交付量（销量）总产量总销量F、转运问题——将中转站既视为销地、也视为产地，转化为运输问题运输模型表中产地由原产地加中转地构成，销地为最终销地加中转地构成，直接相连的路线运费按各地间运费填列，不直接相连的路线运费为M（意为足够大），本地到本地的运费为“0”。六、整数规划模型整数规划——可行解为非负整数的集合，可行域表现为某一区域内的可行点A、图解法1、按常规方法标出该模型的可行域，并在可行域中标出横、纵坐标为整数的可行点；2、标出目标函数直线，按求Max或Min分别从可行域的右边或左边沿x1轴平移，最先接触的可行点即为最优解，代入目标函数得最优值；3、标定可行点时应充分注意坐标轴上的整数点（包括原点）和约束函数直线上的整数点；B、0－1规划问题1、0或1为某一现象的状态，0表示非、即不发生、不指派、不分配、不选用等，1则相反；2、通过设定0－1变量与某一现象的后果相乘，表示该现象发生或不发生带来的后果，同时，0－1变量的和可以限制某类现象共同发生或不发生的次数；3、投资场所选择问题令各投资场所被选择的情况xi(i＝1,2…n)为0－1变量，0表示不被选择，1表示被选择，则：Max利润或Min成本（xi乘以各投资场所的利润或成本）S.T.必须选择或可以同时选择的投资场的xi值之和与限制相比较xi为0－1变量3、固定成本问题令各产品的产量xi(i＝1,2…m)为非负整数变量，生产该产品所需投入固定资产发生状态xm+j(j＝1,2…n)为0－1变量，0表示某产品不被选择，1表示被选择，则：Max利润（各产品的营业利润之和减去为生产其所投入的固定资产之和）S.T.(1)生产产品所需的物料、设备和工时与限制条件相比较(2)xi≤Mxm+j（M为足够大的数，应远大于该组产品可能的最大产量，此约束条件是为排除不投入生产某产品所需的固定资产、但却有xi存在的情况——当xm+j为零时，此时xi必为零；当xm+j为1时，此时xi可为实际值且不受M的限制）xi(i＝1,2…m)为非负整数变量，xm+j(j＝1,2…n)为0－1变量4、指派问题令指派某人从事某项工作的状态xi(i＝1,2…n)为0－1变量，0表示不指派某人从事某项工作，1表示指派，则：Min成本、费用或工时（某人从事某项工作的成本、费用或工时乘以xi后之和）S.T.(1)各人被指派从事某项工作的状态之和为1(2)各项工作有人被指派的状态之和也为1xi(i＝1,2…n)为0－1变量指派问题可用运输模型解决，其基本形式为：工作人员工作1工作2工作…被指派人员数量人员11人员21人员…1工作量111总人量总工作量运输模型中有关产销不平衡的处理也可用于指派问题。5、分布系统设计问题该问题涉及不同生产地到销售地的运费和不同生产地的建设费用（固定成本）。令各生产地的产量xi（i=1,2,…m）为非负整数，选择某一生产地的可能xm+j（j=1,2…n）为0－1变量，0表示不选择、1表示选择，则：Min成本（成本为各生产地产量xi乘以成本与各生产地建设费用乘以xm+j之和）S.T.(1)各生产地销往各销售地的销量与产量限制相比较（其中已建成生产地的限制条件直接用当前产量，待建生产地的限制条件用预计产量乘xm+j）(2)各销售地中各生产地的产量与销量限制相比较xi（i=1,2,…m）为非负整数，xm+j（j=1,2…n）为0－1变量分布系统设计问题可用运输模型解决。6、投资问题与线性规划中连续投资问题相类似，只是各期的投资量存在限制、投资与否也不确定。因此，用０－１变量表示投资的可能性，根据项目回收期不同列出各年各种方案可能的投资表，其中总收益为各项目最后一期投资的和，各期的投资应等于期初资金（也就是上一期投资的收入）。目标为求总收益最大，约束条件包括各期的投资应等于期初资金（也就是上一期投资的收入），以及各期投资的限制。七、目标规划模型目标规划问题——指不能同时满足所有约束条件的情况下，求最大限度满足各级目标的最优解A、目标规划问题不存在满足所有约束条件的解——在图形上表现为至少有一个限制条件的可行区域与其它不相交、不存在满足所有约束条件的共同可行域；B、目标规划问题存在分级目标，即优先保证目标实现的等级，优先满足等级高的目标——在图形上表现为从第一级目标的可行域中找满足第二级目标偏差值最小的点、即到第二级限制条件直线距离最短的点；并依此类推；C、目标规划问题引入了偏差变量di+、di-，分别表示超过或少于约束条件常数项的值——在图形上表现为约束条件直线（k<0）上di+＝0、di-＝0（无偏差），右上方区域为为di+≥0、di-＝0（超过常数项），左下方区域为di+＝0、di-≥0（少于常数项）；D、列出分级目标规划模型的步骤：（1）选定各目标的优先等级，按优先次序排列各约束条件——必须予以满足的条件为绝对约束，其等级最高，有一定浮动空间的条件为条件约束，分优先等级；（2）条件约束为“≤”的，求mindi+（方向相后、表示超出的最少），条件约束为“≥”的，求mindi-（同样方向相后、表示低于的最少）（3）在条件约束中参考引入松弛、剩余变量化标准规划模型的做法，在式子左边加上“-di++di-”，将不等号转换为等号，此时不用考虑正负符号，直接加上即可；（4）第一级目标规划模型为：Mind1+/d1-+d2+/d2-+…（不一定唯一，多个照排）S.T.绝对约束第一级条件约束（不一定唯一，多个照排）xi,di≥0第二级及以下各级目标规划模型为：Mind3+/d3-+d4+/d4-+…（不一定唯一，多个照排）S.T.绝对约束第一级条件约束（不一定唯一，多个照排）第二级条件约束（不一定唯一，多个照排）第…级条件约束（不一定唯一，多个照排）增加上一级条件约束的计算结果增加上…级条件约束的计算结果xi,di≥0E、列出总目标规划模型minz=P1（d1+/d1-+d2+/d2-+…）+P2（d3+/d3-+d4+/d4-+…）+…（P1、P2代表优先等级，同一优先级目标列在一起，具体是di+或di-根据约束条件确定）S.T.绝对约束第一级条件约束第二级条件约束第…级条件约束xi,di≥0F、总目标规划模型与分级目标模型之间的相互转换——参考两类模型的做法即可。G、加权目标规划——当目标存在权重时，在目标函数的di+或di-上直接加上权重即可，约束条件不变。H、目标规划模型的图解——找两条约束条件直线划定的可行域中距离最短的点1、建立坐标系，做出各约束条件的可行域，并将绝对约束视为第零级约束，首先予以保证；2、两级约束条件的最优解——如两条直线相交，则可同时满足，最优解为交点；如不相交，则本级约束条件可行域中距下一级约束条件直线距离最近的点为最优解；3、找到最优解后，代入目标函数，即得最优值，再分别计算各约束条件距要求的差值；4、一般情况下，图解法不便于解超过两级的目标规划。八、网络最优化模型网络最优化问题——选择最优路线A、有方向的问题——有明确的起点和终点，求从起点到终点费用最省、流量最大的问题，包括最短路问题、最小费用问题、最大流问题、最小费用最大流问题1、狭克斯屈拉法解最短路问题——从起点开始，依次计算路程中各节点之前的费用和步数，最终计算出到终点所有可能路径所需的费用和步数，选择费用最低的路径；2、搬箱子理念——设想运送一个箱子从起点到终点，除起点和终点外，无论路径中哪一个中间节点，只有一个箱子进、一个箱子出，各节点进出平衡，而起点只有一个箱子出，终点只有一个箱子进；——通过某节点的流入量和流出量相等，保证了路径内各节点流量平衡、前后衔接，也建立了线性规划模型的约束条件；——实际使用时，起点各条路径的流出量合计为1，终点各条路径的流入量合计为1，中间节点各流入路径合计量减去流出路径合计量为零；3、线性规划模型的建立令各条路径的选择可能性为xi（最短路问题），或流量为xi（费用和流量问题）Min路程/成本（各路径距离或成本乘以xi）或max流量（起点各路径流出量之和）S.T.起点：流出量之和（最大流量问题不计算此点）中间点：1、各点流入量减流出量为零2、各路径流量限制终点：流入量之和（最大流量问题不计算此点）xi≥