1、目目录录 考点一 线性规划与单纯形法. 1 考点二 对偶理论与灵敏度分析.3 考点三 运输问题.7 考点四 线性目标规划.9 考点五 整数线性规划. 10 考点六 图与网络分析. 12 考点七 排队论.13 考点八 存储论.18 考点九 决策论.22 1 考点一线性规划与单纯形法 一、线性规划数学建模 1. 普通的含有两三个决策变量的生产问题,需要用单纯形法进行求解; 2. 较为复杂的建模问题,通常不需要求解。 二、单纯形法求解 1. 普通的单纯形法求解:只需引入松弛变量,便能够直接找到单位矩阵; 2. 人工变量法:化成标准型后,不是规范型(没有单位矩阵),因此需加入人工变 量,用大 M 法或
2、者两阶段法进行求解; 3. 对偶单纯形法:存在单位矩阵、检验数全部都小于等于零、b 存在负值,满足以 上三个条件,才可用对偶单纯形法进行求解。 三、最优性判别 1. 最优解判别规则:若 0 12 .0 .0 T m Xb bb ( ) ( , , , ,)为对应于基B的一个基可 行解,对于一切1,.,jmn,有检验数0 j ,则 0 X( )为最优解。 唯一最优解判别规则: 若 0 12 .0 .0 T m Xb bb ( ) ( , , , ,)为对应于基B的一个基可行 解,对于一切1,.,jmn,有检验数0 j ,则 0 X( )为唯一最优解。 无穷多最优解判别规则:若 0 12 .0 .
3、 0 T m Xbbb ( ) (, ,,)为对应于基 B的一个基 可行解,对于一切1,.,jmn,有检验数0 j ,且存在某个非基变量对应的检 验数0 m k ,则该线性规划问题有无穷多个最优解。 2. 无界解判别规则: 若 0 12 ,00, T m Xb bb, , ,对应于基 B 的一个基可行解, 存 在 某 个 非 基 变 量 对 应 的 检 验 数0 m k , 并 且 对 应 的 变 量 系 数 012. m i m k ai , (, , ),则称该线性规划问题有无界解(或无最优解)。 3. 无可行解判别规则:用单纯形法求解线性规划问题时,在添加人工变量后,才可 能出现无可行解
4、。因为人工变量是后加入到原约束条件中的虚拟变量,要求经过基的变 换将他们从基变量中逐个替换出来。基变量中不再含有非零的人工变量,这表示原问题 2 有解。若在最终表中当所有 0 jj cz ,而基变量中还有某个非零人工变量,这表示原 问题无可行解。 3 考点二对偶理论与灵敏度分析 一、写对偶问题 (1)口诀:大化小,约束反;小化大,变量反 (2)原问题与对偶问题对应关系: 原问题(或对偶问题)对偶问题(或原问题) 目标函数 max z目标函数 min w 约束条件:m 个 第i个约束条件类型为“” 第i个约束条件类型为“” 第i个约束条件类型为“=” 变量数:m 个 第i个变量“” 第i个变量“
5、” 第i个变量是自由变量 变量数:n 个 第j个变量“” 第j个变量“” 第j个变量是自由变量 约束条件:n 个 第j个约束条件类型为“” 第j个约束条件类型为“” 第j个约束条件类型为“=” 目标函数系数 约束条件右端项 约束条件右端项 目标函数系数 二、互补松弛定理 (1)若原问题有最优解,那么对偶问题也有最优解,且目标函数值相同,即 maxminzw。 (2)若 ,XY分别是原问题和对偶问题的可行解,那么 0 S YX和0 S Y X 的充要 条件是 ,XY为最优解,其中 SS X Y,为对应线性规划问题的松弛变量构成的向量。互补 松弛性定理的另外一种表达方式:线性规划取最优解时,若对应
6、的某一约束条件的对偶 变量0,该约束严格取=;若约束条件取严格不等式,其对应的对偶变量一定=0。 三、影子价格 (1)对偶变量 i y就是第i种资源的影子价格 4 (2)影子价格是一种机会成本 影子价格是在资源最优利用条件下对单位资源的估价,这种估价不是资源实际的市 场价格。因此,从另一个角度说,它是一种机会成本。 若第i种资源的单位市场价格为 i m,则有当 * ii ym时,企业愿意购进这种资源,单 位纯利为 * ii ym,则有利可图;如果 * ii ym,则企业有偿转让这种资源,可获单位纯 利 * ii my,否则,企业无利可图,甚至亏损。 (3)影子价格在资源利用中的应用 根据对偶理
7、论的互补松弛性定理: 00 SS YXY X, 表明生产过程中如果某种资源 i b未得到充分利用时,该种资源的影子价格为 0;若 当资源资源的影子价格不为 0 时,表明该种资源在生产中已耗费完。 (4)影子价格对单纯形表计算的解释 单纯形表中的检验数 1 1 m jjBjjiji i CC B PCa y 其中 j C表示第j种产品的价格; 1 m iji i a y 表示生产该种产品所消耗的各项资源的影 子价格的总和,即产品的隐含成本。 当产值大于隐含成本时,即0 j ,表明生产该项产品有利,可在计划中安排;否 则0 j ,用这些资源生产别的产品更有利,不在生产中安排该产品。 四、对偶单纯形
8、法 (1)对偶单纯形法使用条件:存在单位矩阵、检验数全部都小于等于零、b 存在负 值; (2)对偶问题最优解:松弛变量检验数相反数,即影子价格; (3) 对偶单纯形法与普通单纯形法的换基顺序不一样, 普通单纯形法是先确定进基 变量后确定出基变量,对偶单纯形法先确定出基变量后确定进基变量; (4) 用对偶单纯形法求解线性规划是一种求解方法, 而不是去求对偶问题的最优解; (5)普通单纯形法的最小比值是|0 i ik ik b mina a 其目的是保证下一个原问题的 5 基本解可行,对偶单纯形法的最小比值是|0 j ik ij mina a ,其目的是保证下一个对 偶问题的基本解可行。 五、灵敏
9、度分析 (1)目标函数系数 j c的灵敏度分析 基底变量 r c发生改变,会影响所有非基变量检验数 max /|0min /|0 jrjrjrjrjrj jj a aca a 非基变量 j c发生改变,只会影响自己的检验数 (2)右端常数项 b 的灵敏度分析 b 的变化是初表发生改变,不会影响检验数,只会影响 b 这一列 1 B bb m ax/|0m in/|0 iirirriirir baabbaa (3)约束系数 ij a 灵敏度分析 N变化分析 当N变为N时,它不会使右边常数(解值)变化,而只会引起检验数变化,其变 化后的检验数为 1 NB CC B N 。 若非基变量 j p变为 j
10、 p,则该列的检验数变为 1 c jjBj C B p 。 只要0 j ,则最优基不变;若0 j ,则可用单纯形法继续计算。 B变化分析 a. 1 0Bb 且 1 0 NB CC B N ,则此基B为最优基, 1 B XB b 为最优解。 b. 1 0Bb 而 1 NB CC B N 中存在正数, 则此基B不是最优基, 1 B XB b 只是可 行解,用单纯形法继续计算。 c. 1 0 NB CC B N 而 1 B b 中存在负数,则 1 B XB b 只是基解,这时可用对偶单 纯形法继续计算。 d. 若 1 NB CC B N 中存在正数, 而 1 B b 中存在负数, 此时该基解既不是基
11、可行解, 也不是正则解(即对偶问题的基可行解),故需引入人工变量,用人工变量法运算或者 6 从头开始算起。 (4)增加新变量或者新约束的灵敏度分析 7 考点三运输问题 一、运输问题建模 (1)产销平衡:假设 m 个产地 n 个销地,约束条件的个数为:m+n;变量的个数 为:mn;基变量的个数为 m+n-1;决策变量为 ij x。 (2)产销不平衡:产大于销或销大于产,增加虚拟的销地或产地,运价为 0。 1 1 1 1 1,2,., . . 1,2,., 0 1,2,.,;1,2,. min , n iji j m ijj i mn ijij ij ij xaim stxbjn xim jn z
12、c x 二、建立运价平衡表 先建立产销平衡表,再建立运价平衡表。注意:产量或者销量不固定时,要按照最 大的产量或者销量考虑,并且需要拆分。 三、运输问题求解 表上作业法是一种求解运输问题的特殊方法,其实质是单纯形法。 步骤描述方法 第一步求初始基可行解(初始调运方案) 最小元素法、 元素差额法、 第二步 求检验数并判断是否得到最优解当非基变量的 检验数 ij 全都非负时得到最优解, 若存在检验 数0 ij ,说明还没有达到最优,转第三步。 闭回路法和位 势法 8 第三步 调整运量,即换基,选一个变量出基,对原运 量进行调整得到新的基可行解,转入第二步 闭回路法 9 考点四线性目标规划 一、目标
13、规划建模 11 1 1 1,2,., , 1,2,.,. . 0 1 min z ,2,., ,0 1,2,., LK n kjjkkk j n ijji j j llkk k lkk k k l c xddgkk a x Pd bimst xjn ddk d k 二、图解法 对只具有两个决策变量的目标规划的数学模型,可以用图解法来分析求解。先在平面 直角坐标系的第一象限内,做各约束条件。绝对约束条件的作图与线性规划相同。做目标 约束时,先令0 ii dd ,做相应的直线,然后在这直线旁标 ii dd ,。 三、单纯形法 (1)建立初始单纯形表,在表中将检验数行按优先因子个数分别列成K行,置
14、1k ,即对应优先因子行中的第 1 行开始计数。 (2)检查该行中是否存在负数,且对应的前1k 行的系数是零。若有负数取其中 最小者对应的变量为换入变量,转(3)。若无负数,则转(5)。 (3)按最小比值规则确定换出变量,当存在两个和两个以上相同的最小比值时,选 取具有较高优先级别的变量为换出变量。 (4)按单纯形法进行基变换运算,建立新的计算表,返回(2)。 (5)当kK时,计算结束。表中的解即为满意解。否则置1kk ,返回到(2) 。 10 考点五整数线性规划 一、0-1 建模:决策变量只能取值 0 或 1 的整数线性规划 (1)选址问题(2)约束条件互斥 二、分支定界法 (1)求整数规划
15、的松弛问题最优解 若松弛问题的最优解满足整数要求,得到整数规划的最优解,否则转下一步; (2)分支与定界 任意选一个非整数解的变量 i x,在松弛问题中加上约束: ii xx和 1 ii xx其中, 表示取整。 组成两个新的松弛问题,称为分枝。新的松弛问题具有特征:当原问题是求最大值 时,目标值是分枝问题的上界;当原问题是求最小值时,目标值是分枝问题的下界。 三、割平面法 首先不考虑变量 i x是整数这一条件,仍然先解其相应的线性规划问题,若得到非整 数的最优解,则增加能割去非整数解的线性约束条件(用几何术语,成为割平面),使 得由原可行域中切割掉一部分,切割掉的部分只包含非整数解,即没有切掉
16、任何整数可 行解。 四、匈牙利法 (1)变换指派问题的系数矩阵() ij C为() ij b,使在() ij b的各行各列中都出现 0 元素,即从() ij C的每行元素都减去该行的最小元素;再从所得新系数矩阵的每列元素 中减去该列的最小元素。 (2)进行试指派,以寻求最优解。 在() ij b中找尽可能多的独立 0 元素,若能找出 n 个独立 0 元素,就以这 n 个独立 0 元素对应解矩阵() ij x中的元素为 1,其余为 0,这就得到最优解。找独立 0 元素,常用 的步骤为如下。 从只有一个 0 元素的行开始,给该行中的 0 元素加圈,记作。然后划去所在列 11 的其它 0 元素,记作
17、;这表示该列所代表的任务已指派完,不必再考虑别人了。依次 进行到最后一行。 从只有一个 0 元素的列开始(画的不计在内),给该列中的 0 元素加圈,记作; 然后划去所在行的 0 元素,记作,表示此人已有任务,不再为其指派其他任务了。 依次进行到最后一列。 若元素的数目 m 等于矩阵的阶数 n(即:mn),那么这指派问题的最优解已得 到。若 mn,则转入下一步。 (3)用最少的直线通过所有 0 元素。其方法: 对没有的行打“”; 对已打“”的行中所有含元素的列打“”; 再对打有“”的列中含元素的行打“”; 重复、直到得不出新的打号的行、列为止; 对没有打号的行画横线,有打号的列画纵线,这就得到覆
18、盖所有 0 元素的最少 直线数 l。 注:l 应等于 m,若不相等,说明试指派过程有误,回到第(2)步,另行试指派; 若 lmn,表示还不能确定最优指派方案,须再变换当前的系数矩阵,以找到 n 个独立 的 0 元素,为此转第(4)步。 (4)变换矩阵() ij b以增加 0 元素 在没有被直线通过的所有元素中找出最小值,没有被直线通过的所有元素减去这个 最小元素;直线交点处的元素加上这个最小值。新系数矩阵的最优解和原问题仍相同。 转回第(2)步。 12 考点六图与网络分析 一、最小支撑树(铺水泥路、架电话线) (1)避圈法(2)破圈法 二、最短路 (1) Dijkstra 算法 使用条件:权重
19、大于等于零,有向图、无向图均可使用,任意点到起点的最短路; (2)Bellman 算法 使用条件:可以算负权重,只能计算有向图,任意点到起点的最短路; (3)Floyd 算法 使用条件:正负权重都可以,有向图、无向图均可使用,任意两点的最短路; 三、最大流 (1)可行流f 是最大流,当且仅当不存在关于f 的增广链; (2)最大流量最小截量定理:任一个网络D中,从 s v到 t v的最大流的流量等于分 离 s v, t v的最小截集的容量。 (3)标号法:标号过程,调整过程 13 考点七排队论 一、单服务台负指数排队系统 1. 标准的 M/M/1 模型(M/M/1/) 0 , 1 =1 11 n
20、 n P Pn (1) s L ;(2) q L ;(3) 1 s W ;(4) q W (1) ss LW;(2) qq LW ;(3) 1 sq WW ;(4) sq LL 2. 系统的容量有限制的情形(M/M/1/N/) (1) 0 1 1 1 1 1, 1 1 N n n N P nN P (2) 1 1 0 0 1 11 1 1 1 1/ N s N qs s s qs N LP L W P WW L L (3) 0 1=- eN P(1 P) (4) 01 2 1 1 1: s N PPP N L N 3. 顾客源为有限的情形(M/M/1/m) 14 (1) 0 0 0 1 ! !
21、 ! 1 ! i m i n n P m mi m PPnm mn (2) 0 0 0 00 0 1 1 1 1 11 1 1 s qs s s q qs LmP P LLPm Lm W PP L WW P 在机器故障问题中 s L是平均故障台数,而 0 1 s mLP 表示正常运转的平均 台数。 (3) es mL 二、多服务台负指数排队系统 1. 标准的 M/M/c模型,即(M/M/c/) (1) c (2) 1 1 0 0 0 0 111 ! 1 1 ! 1 ! kc c k n n n n c kc Pnc n P Pnc c c P 15 (3) 02 1 ! 1 sq c qn n
22、 c LL c Lnc PP c (4) q s sq L L WW , 2. 系统的容量有限制,即(M/M/c/N/) (1) 1 0 0 0 0 !1 0 ! ! kcN cc k n c n cc P kc cn Pncc n P c PcnN c (2) 0 2 11 ! 1 1 /1 1 c N cN c q sqN qqN sq Pc LNc c LLcP WLP WW (3) 1 0 0 0 1 1 0 1 0 ! 0 ! 1 0,0, ! 1 ! k c k n n qqs n c c n sncn cn n c P k c PPnc n LWW c c n LnPc c n
23、Nc P 3. 有限顾客源,即(M/M/c/m) 16 (1) m c (2) 1 0 01 111 ! kk ccm nk c cc P mkmkmcmkm (3) 0 0 ! 0 ! ! ! 1 ! ! n n n n c m Pnc mn n P m Pcnm mn c c (4) / / e sqqs ssees qqe LLLmL WLmL WL 三、一般服务时间模型 1. M/G/1 模型 22 2 1 s Var T L ,其中 E T 2. 定长服务时间 M/D/1 模型 2 2 1 s L 3./1 k ME模型 (1) 22 2 11 11 T ii E TVar T kk
24、 EVar T k 17 (2) 22 2 2 2 1 1 2 121 1 21 s qs q s sq k k L k k LL k L L WW , 18 考点八存储论 一、确定性存储 1. 不允许缺货,备货时间很短 333 00001013 110 221 2 2 CC RC tQRtCC RtCC R C RCt 2. 不允许缺货,生产需要一定时间 /TRt P 33 00 11 22 . . C PC RP tQE OQ C R PRCPR 03 0130 1 2 min2 PRRtC R C tC tC C RT PPC P PR 3 33 000 111 222 C R PRC
25、RPC R SQRTR CPRC P PRC P 19 3. 允许缺货,备货时间很短 312 23312 000 1211212 123 000 12 31 00 212 222 2 min, 2 CCCC C RRCCC tSQ C RCC CCCC C C C R C t sCt S CC RC C QS CCC 4. 允许缺货,生产需要一定时间 20 331212 000 1212 32 003 112 13 01 122 2 0213 12 22 2 2 min,2 CC RCCCCPP tQR t C RCPRCCPR C RCPR SR tt CCCP C C RPR BR t C
26、CCP CPR C t tC C R CCP 最大存储量 最大缺货量 5. 价格有折扣的存储问题 (1)对 CQ (不考虑定义域)求得极值点为 0 Q (2)若 01 QQ,计算: 03 011 0 1 2 QC CQCK RQ 31 112 1 1 2 CQ CQCK RQ 32 213 2 1 2 CQ CQCK RQ 由 012 min,CQCQCQ 得到单位货物最小费用的订购批量 * Q。例如 0121 min,CQCQCQCQ ,则取 * 1 QQ (3)若 102 QQQ,计算 02 CQCQ 、。 由 02 min,CQCQ 决定 * Q (4)若 20 QQ,则取 * 0 QQ
27、。 21 二、随机性存储 1. 需求是随即离散的 报童问题:报童每日售报数量是一个随机变量。报童每售出一份报纸赚k元。如报 纸未能售出,每份赔h元。每日售出报纸份数r的概率 P r根据以往的经验是已知的, 问报童每日最好准备多少份报纸? 报童应准备的报纸最佳数量Q应按下列不等式确定: 1 00 QQ rr k P rP r kh 2. (s,S)策略 1 2 12 ii r Sr S CK P rNP r CC 得出满足不等式的 i S,即令 i SS,本阶段订货量为QSI 12 312 r sr s r Sr S KsC sr P rCrs P r CKSC Sr P rCrS P r 22 考点九 决策论 一、不确定型决策 (1)悲观主义决策准则(maxmin) (2)乐观主义决策准则(maxmax) (3)等可能性准则 (4)最小机会损失准则 (5)折中主义准则 二、风险决策 (1)最大期望收益决策准则 (2)最小机会损失决策准则 (3)全情报价值 (4)贝叶斯公式的应用