运筹学复习题

线性规划的可行域是什么形状多边形，而且是“凸”形的多边形。最优解在什么位置获得在边界，而且是在某个顶点获得。凸集中的“极点”，又称顶点或角点。2）线性规划的最优解（若存在的话）必能在可行域的顶点获得。1、线性规划问题的标准型式标准型式特点MAX型、等式约束、非负约束线性规划问题的一般型式如何转化为标准型式引入符号和变量（1）目标函数MIN型MAX型，引入负号（2）约束条件不等式，引入松弛变量或剩余变量X3称为松弛变量。问其实际意义是什么（3）对于取值无约束的变量XK（4）对于右端项BI0的情况等式两端同时乘以1即可。（5）对于XI0的情况令XX即可。基本可行解基可行解非负的基本解。写出下面LP的对偶模型。对偶模型为三、对偶问题的经济解释1、对偶最优解的经济解释资源的影子价格（SHADOWPRICE）对偶约束的经济解释产品的机会成本（OPPORTUNITYCOST）对偶松弛变量的经济解释产品的差额成本（DIFFERENTIALCOST）在利润最大化的生产计划中（1）影子价格大于0的资源没有剩余；（2）有剩余的资源影子价格等于0；（3）安排生产的产品机会成本等于利润；（4）机会成本大于利润的产品不安排生产。最优解不一定在顶点上达到最优解不一定是松弛问题最优解的邻近整数解整数可行解远多于顶点，枚举法不可取松弛问题不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。分枝界定解法纯整数规划、混合整数规划分支定界法就是将B的可行域分成子区域（称为分支方法）的方法，通过减小最优值的上界和增大最优值的下界最终得到最优值。适合于用动态规划方法求解的只是一类特殊的多阶段决策问题，即具有“无后效性”的多阶段决策过程。指系统从某个阶段往后的发展，仅由本阶段所处的状态及其往后的决策所决定，与系统的历史无关。图由点和边组成，记为GV，E，其中VV1，V2，VN为结点的集合，EE1，E2，EM为边的集合。点表示研究对象边表示研究对象之间的特定关系图的每条边都有一个表示一定实际含义的权数，称为赋权图，记为DV，A，C。双代号网络图计算工期TC等于以网络计划的终点节点为箭头节点的各个工作最早完成时间的最大值。最早完成时间等于最早开始时间加上其持续时间EFIJESIJDIJ最早开始时间等于各紧前工作最早完成时间的最大值ESIJMAXEFHIMAXESHIDHI最迟开始时间等于最迟完成时间减去其持续时间LSIJLFIJDIJ最迟完成时间等于各紧后工作最迟开始时间的最小值LFIJMINLSJKMINLFJKDJK总时差等于其最迟开始时间减去最早开始时间，或等于最迟完成时间减去最早完成时间TFIJLSIJESIJ自由时差当工作IJ有紧后工作JK时，其自由时差应为FFIJESJKEFIJ后一项的ES前一项的EF关键路线自始至终全部由关键工作组成的线路，或线路上总的工作持续时间最长的线路为关键线路。例1（M/M/1/无穷/无穷/FCFS）表示到达间隔为负指数分布，服务时间也为负指数分布，1个服务台，系统容量无限，顾客源无限，先到先服务。例2（M/M/C/N/无穷/LCFS）表示到达间隔为负指数分布，服务时间也为负指数分布，C个服