《运筹学》总复习。
第1章线性规划及其对偶问题。
基本概念。
基本要素：决策变量、目标函数、约束条件。
线性规划定义：决策变量为可控的连续变量，目标函数和约束条件为决策变量的线性函数。
标准形式：目标函数取“max”、约束条件取“=”约束右端项非负、决策变量非负。
解的概念：凡满足约束条件的决策变量的取值称为线性规划的可行解，所有可行解的集合称为线性规划的可行域，使目标函数达到最优值的可行解称为线性规划的最优解。
数学建模与求解。
建模步骤：科学选择决策变量、找出所有约束条件、明确目标要求、非负变量的选择。
单纯形法与对偶单纯形法：
两阶段法：第一阶段：添加人工变量，构造人工变量之和为最小的目标函数辅助线性规划，由松驰变量和人工变量构成初始单纯形表，进行迭代。
在最终单纯形表中如果存在人工变量，由无可行解，否则转第二阶段。
第二阶段：在第一阶段求解的最终单纯形表中去掉人工变量，目标系数恢复为标准模型的目标系数，按单纯形法继续迭代。
练习题：1.某厂利用原料a、b生产甲、乙、丙3种产品，已知生产单位产品所需原料数、单件利润及有关数据如表所示，试建立该问题线性规划模型，并用单纯形法求解。
2.某旅馆在不同时段所需服务员数如表所示：
每班服务员从开始上班到下班连续工作8小时，为满足每班所需要的最少服务员数，这个旅馆至少需要多少服务员？（列出该问题线性规划模型，不求解）
3.用两阶段法求解线性规划问题：
4.用对偶单纯形法求解线性规划问题：
第2章整数规划与分配问题。
0-1变量的用法及建模。
理解0-1变量的9种用途，其中(1)(2)(4)(8)重点掌握。
1）多个取1：
2）n中取k：
n中至少取k，改为。
n中最多取k，改为。
3）变量取离散数值：
4）选甲必须选乙，选乙不一定选甲：或1
5）两个约束条件只需满足一个：
或。式中：m为任意大正数。
6）n个约束条件中满足k个：
7）若，则；否则，
或 8）选了甲或乙，丙就不能入选，选了丙，甲、乙都不能入选。
9）对可表述为：
匈牙利法。
步骤：1.从每行中减去最小数。
2.再从每列中减去最小数。
1)先看行，从第一行开始，如该行只有一个0,给该0打δ,划去该为所在列，如有两个以上0或无0,转下一行，到最后一行；
2)再看列，如该列只有一个0,给该0打δ,划去该0所在行，如无0或两个以上0,转下一列；
3)重复(1)(2),可能出现三种结局：
a.有m个打δ的0,令对应δ号的xij=1,即为最优。
b.存在0的闭回路。
对闭回路上的0按顺时针编号，任取单号或双号打δ,分别对打δ的0都划去所在行(或都划去所在列)返回3(1)
c.打δ的0的数4.从未被划去的数字中找出最小数字k,对未被划去的行分别减k;对被划去的列加k,回到3
练习题：1．某公司有5000万元可用于投资，有6个投资方案，其投资额、安排员工数和年利润额如表所示：
要求：1）投资额不超过5000万元；
2）至少安排150人员就业；
3）年利润额尽可能地多。
试建立该问题0-1规划数学模型（不求解）
2.某校排球队准备从以下8名预备队员中选拔4名正式队员，并使平均身高尽可能高。这8名预备队员情况如下表所示。
要求：1）8名预备队员选4名；
2）最多补充1名主攻；
3）最多补充1名副攻；
4）至少补充1名二传；
5）至少补充1名接应；
6）a和e只能入选1名；
7）无论b或d入选，a都不能入选。
建立数学模型，不求解）
3.某企业接受订货，产品需求量为6000公斤，可由3种设备进行生产，其成本与产量如下：
企业如何组织生产才能使总成本最小？试列出该问题的整数规划数学模型（不求解）。
4.试利用0-1变量对下列各题分别表示成一般线性约束条件。
1）x1+x2≤2或2x1+3x2≥8
2）变量x3只能取
3）若x2≤4，则x5≥0，否则x5≤3
4）以下四个约束条件中至少满足两个：
5.用匈牙利法求解分配问题：
第3章运输问题。
数学模型。
1.产销平衡运输问题数学模型。
2.产销不平衡的运输问题转化为产销平衡的运输问题。
产》销：添加一个假想销地，使其销量=∑产量-∑销量。
产《销：添加一个假想产地，使其产量=∑销量-∑产量。
3.会将一般的非地理问题转化为运输问题数学模型。
表上作业法。
1）用最小元素法给出初始方案。
2）用位势法求检验数。
3）用闭回路法进行方案调整。
重复（2）（3）步，直到得最优解。
练习题：1.某建筑公司6个工地（a、b、c、d、e、f）的物资需要运输，各工地起点、终点及所需车次如表（a）所示，相关工地间路程如表（b）所示。
ab）试求最优调运方案（列出产销平衡表，并用表上作业法求解）。
第4章目标规划。
基本概念。
偏差变量：用以表示实际值与超出或未达到目标值的差距的变量称为偏差变量；
正偏差变量：超出目标的差距称为正偏差变量；
负偏差变量：未达到目标值的差距称为负偏差变量；
优先级：对两个不同目标，如果其重要程度相差悬殊，为达到一个目标甚至可以牺牲另一目标，可将它们划分属不同优先级。优先级是一个定性概念，规定：pk>>pk+1
权系数：在同一优先级内，根据重要程度不同，用权系数确定其优先顺序。权系数是一个具体的数字。
数学建模。
建模步骤：1）确定优先因子。
2）列出目标要求（不等式）
3）约束转换（加减负正偏差变量变为等式）
4）由目标要求确定目标值偏差（允许超过目标：负偏差最小；允许不完成：正偏差最小；要求准确完成：正、负偏差之和最小）
5）将目标值偏差组合起来，加上系统约束和目标约束及变量非负约束构成目标规划数学模型。
练习题：1．某广播电台每天开播12小时，其中广告节目用以赢利，每分钟可收入500元，新闻节目每分钟需支出50元，而**节目每分钟支出20元，依据规定：正常情况下广告节目不超过广播时间的15%，每小时至少安排5分钟的新闻节目，试问该电台每天应如何安排广播节目？
其优先级如下：p1——满足规定要求，p2——每天的纯收入达到1千元并力争超过。试建立此问题的目标规划模型（不求解）。
2．某公司计划生产甲、乙两种产品，它们分别要经过设备a和设备b两道工序的加工，其所需工时定额如下表：
系统约束：两种设备已满负荷，不能加班。
目标要求：p1：盈利达到150元，并尽可能地超过；
p2：两种产品的产量之和尽可能超过10千克；
p3：产品乙不少于6千克。
试建立此问题的数学模型（不求解）
第6章图与网络模型。
基本概念。
图：点和连线的集合。
不带箭头的连线称为边(edge).带箭头的连线称为弧(arc).
无向图：连线不带箭头的图，用为：g=
式中：v=，e= 表示。（如图a）.
有向图：连线带箭头的图，用d=表示，（如图b）
边相邻：两条边有公共的端点。
点相邻：两点有公共的关联边。
环：两端点相重的边。
多重边：两条以上边所连的端点相重。
简单图：无环、无多重边的图。
次(度) ：某一点具有的关联边的数目。
孤立点：次为“0”的点，悬挂点：次为“1”的点。
悬挂边：与悬挂点相连的边。
奇点：次为奇数的点。
偶点：次为偶数的点；
链：点、边的交错序列。
圈(或称路) ：封闭的链。
连通图：任两点至少存在一条链。
基础图：有向图去掉箭头就变成了无向图，此无向图称为该有向图的基础图。
树：一个无圈的连通图称为树。
基本方法。
最小支撑树的避圈法与破圈法。
最短路的dijkstra标号算法。
最大流的ford-fulkerson标号算法。
中国邮路问题：
结论1:若无奇点，则邮递员可以走遍所有街道，做到每条街道只走一次而不重复。
结论2:1)有奇点的连线的边最多重复一次；
2)在该网络图的每个回路上，有重复的边的长度不超过回路总长的一半。
练习题。1.用避圈法或破圈法求下图所示最小支撑树。
2.用dijkstra标号算法求上图所示从v1到v8的最短路。
3.如图，圆圈代表网络节点，节点间的连线表示它们间有网线相连，连线上的数表示该网线传送10兆字节的信息所用时间(单位：秒)。
现需从点s向点t传送10兆字节的信息，问至少需多少时间？
4.用ford-fulkerson标号算法求上图所示从s到t的网络最大流。
第8章对策论。
对策模型三要素。
局中人、策略集、赢得矩阵。
二人零和对策的条件：
1）有两个局中人；
2）每个局中人的策略都是有限的；
3）每一策略组合下，各局中人赢得之和始终为零。
对策模型的假设前提：
1）对策双方的行为是理智的；
2）局中人选取策略的目标是收益最大或损失最小；
3）局中人同时选取各自的行动策略，且不知道对方选取哪一个策略；
4）对策中的有关规定和要求，局中人是知道的。
矩阵对策最优纯策略。
求法：超优原则化简，最大最小原则。
最优混合策略。
求法：线性规划法。
练习题。1．求赢得矩阵a的最优纯策略。
运筹学总复习
0 绪论。1 什么是运筹学？2 运筹学起源？3 运筹学的分支？1 线性规划。1 什么是线性规划？2 线性规划数学模型三要素 矩阵形式？3 法的步骤 说明线性规划问题什么特点？4 线性规划解的四种形式？5 线性规划问题化标准形式 标准形式的特点 min型目标函数化为max形式。6 基本解 基本可行解。...
运筹学总复习
基本要求。一 将线性规划化为标准型和写出相应的对偶规划 二 用 法求解具有两个决策变量的线性规划问题 三 用单纯形方法及人工变量法求解线性规划问题 四 灵敏度分析 五 整数规划与分枝定界法，0 1规划与隐枚举法，指派问题。六 求解产销平衡的运输问题和产销不平衡的运输问题 七 动态规划与求解 八 带 ...
运筹学总复习
一 判断题。线性规划问题目标函数可以同时在两个顶点上达到最优解。二 选择题。存贮策略达到最优时，达到了什么目标 b a.平均订购费用最低b.平均的运营费用最低 c.订货周期最短d.订货量最小。三 填空题。如下图所示的网络图，弧上数为 为了使为可行流，则 2 1 3 3 找一条增广链 s 2 1 4 ...