《运筹学总复习》由会员分享，可在线阅读，更多相关《运筹学总复习（11页珍藏版）》请在金锄头文库上搜索。
1、运筹学总复习第 1章 线性规划及其对偶问题 基本概念基本要素：决策变量、目标函数、约束条件 线性规划定义：决策变量为可控的连续变量，目标函数和约束条件为决策变量的线性函数 标准形式：目标函数取“max”、约束条件取“=”、约束右端项非负、决策变量非负 解的概念：凡满足约束条件的决策变量的取值称为线性规划的可行解,所有可行解的集合称 为线性规划的可行域,使目标函数达到最优值的可行解称为线性规划的最优解。 数学建模与求解 建模步骤：科学选择决策变量、找出所有约束条件、明确目标要求、非负变量的选择 单纯形法与对偶单纯形法：单纯形法对偶单纯形法两阶段法：第一阶段：添加人工变量，构造人工变量之和为最小的
2、目标函数辅助线性规划，由松驰 变量和人工变量构成初始单纯形表，进行迭代。在最终单纯形表中如果存在人工变量， 由无可行解，否则转第二阶段。第二阶段：在第一阶段求解的最终单纯形表中去掉人工变量，目标系数恢复为标准模型 的目标系数，按单纯形法继续迭代。 练习题：1. 某厂利用原料A、B生产甲、乙、丙3种产品，已知生产单位产品所需原料数、单件 利润及有关数据如表所示，试建立该问题线性规划模型，并用单纯形法求解。甲乙丙原料拥有量A63545B34530单件利润4152. 某旅馆在不同时段所需服务员数如表所示： 每班服务员从开始上班到下班连续工作8 小时，为满足每班所需要的最少服务员数，这个旅 馆至少需要
3、多少服务员？（列出该问题线性规划模型，不求解）时间段最少服务员数106:0010:0020210:0014:0030314:0018:0025418:0022:0030522:0002:0010602:0006:00103. 用两阶段法求解线性规划问题：min w = x + 2 x + 3x123x + 2 x + 3x = 15123s.t 0134. 用对偶单纯形法求解线性规划问题：min w = 5 x + 2 x + 4 x1233x + x + 2x 4123s.t 6 x + 3 x + 5 x 12123x 013第 2章 整数规划与分配问题0-1 变量的用法及建模理解 0-1
4、 变量的9 种用途，其中(1)(2)(4)(8)重点掌握(1)多个取 1： x = 1，x = 0,或 1.jjj=1(2) n 中取 k： 另 x 二 k, x 二 0,或 1.jjj=1n中至少取k,改为 x k, x = 0,或1.jjj=1n中最多取k,改为 x k, x = 0,或1.jj3)变量取离散数值：x =迟 c yi iVi =1迟 y = 1, y = 0或1iii=1选甲必须选乙，选乙不一定选甲：兀甲 兀乙，x甲,兀乙=0或15）两个约束条件只需满足一个：3 x + 2 x 2 - (1- y) M或 V 1 2一 3x + 2x 10 + yM, y = 0或112式
5、中： M 为任意大正数6） n 个约束条件中满足 k 个迟 a x b + y M (i = 1,2,ij j i iV j =1另 y = n - k y = 0或1iii=1, n)若x 2 0 ；否则x 24,x5 3” x 0 - y MV 51x 4 - y M22x 0 - yM 4 - (1 - y)My=V.x5 3 + (1 - y) M8）选了甲或乙,丙就不能入选,选了丙,甲、乙都不能入选x + x 1甲 丙Vx + x 1乙 丙、可表述为： f (x) = yk + cxV y Mxx Myx ,x , x =0或1 甲乙丙0,当 x = 0对 f(x)= k + cx,
6、 当x0匈牙利法步骤：1. 从每行中减去最小数2. 再从每列中减去最小数3.（1）先看行，从第一行开始，如该行只有一个0,给该0打A,划去该为所在列,如有两个以上0或 无 0,转下一行,到最后一行;（2）再看列，如该列只有一个0,给该0打A ,划去该0所在行，如无0或两个以上0,转下一列；（3）重复（1）（2）,可能出现三种结局:a. 有m个打A的0,令对应A号的xij=1，即为最优.b. 存在0的闭回路.对闭回路上的0按顺时针编号，任取单号或双号打A,分别对打A的0都划去所在行（或都划去 所在列）返回 3（1）C.打A的0的数 万案投资额（万元）可安排员工数（人）年利润额（万元）120005
7、01502200060200335001001504100020100540001002006150050100要求：（1 ）投资额不超过 5000 万元； （2）至少安排150人员就业； （3）年利润额尽可能地多。试建立该问题 0-1 规划数学模型（不求解）2. 某校排球队准备从以下8名预备队员中选拔4名正式队员，并使平均身高尽可能高。这8 名预备队员情况如下表所示。预备队员号码身高（厘米）位置A1197主攻B2194主攻C3189副攻D4196副攻E5188二传F6180二传G7183接应H8185接应要求：（1）8名预备队员选4名2）最多补充1 名主攻；3）最多补充1 名副攻；4）至少补
8、充1 名二传；5）至少补充1 名接应；6）A 和 E 只能入选 1 名；（7）无论B或D入选，A都不能入选。建立数学模型，不求解）3.某企业接受订货，产品需求量为6000 公斤，可由3 种设备进行生产，其成本与产量如下：设备设备调整费（元）生产成本（元/公斤）生产能力（公斤）A200063000B250054000C300045000企业如何组织生产才能使总成本最小？试列出该问题的整数规划数学模型（不求解）。4.试利用 0-1变量对下列各题分别表示成一般线性约束条件。(1) X+x2W2 或 2X+3x228（2）变量x3只能取0、5、9、12（3）若 x2W4,则 x50,否则 x5W3（
9、4）以下四个约束条件中至少满足两个x + x 21 2X 1 1x 3125. 用匈牙利法求解分配问题：85907390 -8969_828778916658C =（2）C =83827988783886908085_97461)第 3 章 运输问题数学模型1. 产销平衡运输问题数学模型minz= em en c xij iji=1 j =1De厶x = aij is.t 0ij迟x = bijji=12. 产销不平衡的运输问题转化为产销平衡的运输问题 产销：添加一个假想销地，使其销量=工产量-工销量 产Pk+1权系数：在同一优先级内，根据重要程度不同，用权系数确定其优先顺序。权系数是一个具
10、体的数字。 数学建模 建模步骤：（1）确定优先因子（2）列出目标要求（不等式）（3）约束转换（加减负正偏差变量变为等式）（4）由目标要求确定目标值偏差（允许超过目标：负偏差最小；允许不完成：正偏差最小 要求准确完成：正、负偏差之和最小）（5）将目标值偏差组合起来，加上系统约束和目标约束及变量非负约束构成目标规划数学 模型 练习题：1某广播电台每天开播12 小时，其中广告节目用以赢利，每分钟可收入500 元，新闻节目 每分钟需支出50元，而音乐节目每分钟支出20 元，依据规定：正常情况下广告节目不超过 广播时间的 15%，每小时至少安排 5 分钟的新闻节目，试问该电台每天应如何安排广播节 目？其
11、优先级如下：P1满足规定要求，P2每天的纯收入达到1千元并力争超过。 试建立此问题的目标规划模型（不求解）。2.某公司计划生产甲、乙两种产品，它们分别要经过设备A和设备B两道工序的加工，其 所需工时定额如下表：、产品工序甲（小时/千克）乙（小时/千克）有效工时（小时）设备A5380设备B2772单位盈利100元/千克120元/千克系统约束：两种设备已满负荷，不能加班。目标要求：P1：盈利达到150元，并尽可能地超过；P2：两种产品的产量之和尽可能超过10千克;P3：产品乙不少于6千克。试建立此问题的数学模型（不求解）第 6章 图与网络模型 基本概念图：点和连线的集合.不带箭头的连线称为边（edge）.带箭头的连线称为弧（Arc）. 无向图：连线不带箭头的图，用为:G=V,E式中：V=V
