1、线性规划的可行域是什么形状？ 多边形，而且是“凸”形的多边形。 最优解在什么位置获得？ 在边界，而且是在某个顶点获得。 凸集中的“极点”，又称顶点或角点。 2）线性规划的最优解（若存在的话）必能在可行域的顶点获得。 1、线性规划问题的标准型式 标准型式特点： max 型、等式约束、非负约束 线性规划问题的一般型式如何转化为标准型式？ 引入符号和变量 （ 1）目标函数： min 型 - max 型，引入负号 （ 2）约束条件：不等式，引入松弛变量或剩余变量 x3 称 为松弛变量。问：其实际意义是什么？ （ 3）对于取值无约束的变量 Xk ： （ 4）对于右端项 bi 0 的情况： 等式两端同时乘
2、以 1 即可。 （ 5）对于 xi 0 的情况： 令 x= x 即可。 基本可行解 (基可行解 )：非负的基本解。 写出下面 LP 的对偶模型。 对偶模型为： 三、对偶问题的经济解释 1、对偶 最优解 的经济解释 资源的影子价格（ Shadow Price） 对偶 约束 的经济解释 产品的机会成本（ Opportunity Cost） 对偶 松弛变量 的经济解释 产品的差额成本（ Differential Cost） 在利润最大化的生产计划中： （ 1）影子价格大于 0 的资源没有剩余； （ 2）有剩余的资源影子价格等于 0； （ 3）安排生产的产品机会成本等于利润； （ 4）机会成本大于利润
3、的产品不安排生产。 最优解不一定在顶点上达到 最优解不一定是松弛问题最优解的邻近整数解 整数可行解远多于顶点，枚举法不可取 松弛问题 ：不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为 该整数规划问题的松弛问题。 分枝界定解法：纯整数规划、混合整数规划 分支定界法 就是将 B的可行域分成子区域（称为分支方法）的方法，通过减小最优值的上界和增大最优值的下界最终得到最优值。 适合于用动态规划方法求解 的只是一类特殊的多阶段决策问题，即具有“ 无后效性 ”的多阶段决策过程。指系统从某个阶段往后的发展，仅由本阶段所处的状态及其往后的决策所决定，与系统的历史无关。 图 由 点 和 边 组成，
4、记为 G=(V， E)，其中： V=v1， v2， vn 为结点的集合， E=e1， e2， em 为边的集合。 点 表示研 究对象 边 表示研究对象之间的特定关系 图的每条边都有一个表示一定实际含义的权数，称为 赋权图 ，记为 D=(V， A， C)。 双代号网络图 ： 计算工期 (TC):等于以网络计划的终点节点为箭头节点的各个工作最早完成时间的最大值。 最早完成时间等于最早开始时间加上其持续时间： EFi-j= ESi-j+Di-j 最早开始时间 等于各紧前工作最早完成时间的最大值： ESi-j = max EFh-i=max ESh-i+Dh-i 最迟开始时间等于最迟完成时间减去其持续时间： LSi-j= LFi-j Di-j 最迟完成时间等于各紧后工作最迟开始时间的 最小值 ： LFi-j = min LSj-k=min LFj-k Dj-k 总时差等于其最 迟 开始时间减去最 早 开始时间，或等于最 迟 完成时间减去最 早 完成时间： TFi-j= LSi-j ESi-j 自由时差 : 当工作 i-j有紧后工作 j-k 时，其自由时差应为： FFi-j= ESj-k EFi-j (后一项的 ES-前一项的 EF)
