Advances in Applied Mathematics 应用数学进展, 2016, 5(1), 45-50
Published Online February 2016 in Hans. https://www.doczj.com/doc/b83267036.html,/journal/aam
https://www.doczj.com/doc/b83267036.html,/10.12677/aam.2016.51007
On the Assigning Problem in
Operation Research
Tianxiao Zhao1, Fugang Chao2, Han Ren2,3
1Department of Mathematical Science, Tsinghua University, Beijing
2Department of Mathematics, East China Normal University, Shanghai
3Shanghai Key Laboratory of Pure Mathematics and Mathematical Practice, Shanghai
Received: Jan. 29th, 2016; accepted: Feb. 21st, 2016; published: Feb. 24th, 2016
Copyright ? 2016 by authors and Hans Publishers Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY).
https://www.doczj.com/doc/b83267036.html,/licenses/by/4.0/
Abstract
In this paper, we characterize the assigning problem and present an algorithm to compute the op-timal solutions efficiently. In our everyday life, such problems are always needed to use assigning methods to give a good solution. Since they are 0-1 problem, we may find relative optimal solu-tions.
Keywords
Operation Research, Assigning Problem, Simplicial Algorithm
运筹学中的指派问题
赵天骁1，晁福刚2，任韩2,3
1清华大学数学科学系，北京
2华东师范大学数学系，上海
3上海市核心数学与实践重点实验室，上海
收稿日期：2016年1月29日；录用日期：2016年2月21日；发布日期：2016年2月24日
赵天骁 等
摘 要
详细给出指派问题的定性刻化，同时提供一个可行算法，有效计算指派问题的最优解。在日常生活中会遇到类似的问题，需要用指派问题进行解决，使得完成任务的总效率最高，就需要用指派问题进行解决。由于是0-1问题，所以总能求的相对最优解。
关键词
运筹学，指派问题，单纯形算法
1. 背景与数学模型
在日常生活中常遇到这样的问题：某单位需要完成项任务，恰好有个人可以承担这些任务。由于每个人专长不同，各人完成任务的效率也不相同。于是产生了这样一个问题：指派哪个人去完成哪些任务，使得完成项任务的总效率最高？这类问题称为指派问题(Assigning problem)。指派问题在博弈论与经济行为[1]、和生态经济学[2]等学科都有广泛的应用，文中未加说明的符号和术语参见文献[3]。
如果用ij C 表示i 个人完成第j 项工作的效率，,1,2,,i j n = ，而变量
1,,
0,,ij i j x i j =
指派第人去完成第项任务不指派第人去完成第项任务 则相应的极小化数学模型为
min ij ij i
j
Z c x =∑∑, (1)
1,1,2,,,ij i
x j n ==∑
(2) 1,1,2,,,ij j
x i n =
=∑ (3)
{}0,1,1ij x i j n ∈≤≤≤ (4)
由上所述，指派问题有以下几个特点：
1) 指派问题是一个平衡的0-1运输规划问题。这可以由(2)~(4)看出。
从上讲，可以用表上作业法或单纯形法救解。但，当阶为较大时这些方法过于繁琐。可以利用其自身特点建立更为简单有效的方法。
2) 代数性质。不难由(2)~(4)看出，每一次指派对应于一个n 阶排列。如果将(x ij )视为一个n × n 指派方阵，则(2)，(3)表明：每次指派对应于n 个位于不同行不同列上1的定位。故，所有可能方法数为n ！。由此可见，指派问题一定有最优解。但是，用穷法来决定最优解其工作量是巨大的。这可以由Stirling 公式
12!~n n n n ??
看出。
3) 最优指派的不变性。
指派问题的最优解有这样的一个重要特性：如果从系数矩阵(C ij )的一行(列)各个元素中分别减去一个
赵天骁 等
常数c (通常是该行或列的最小元素)，得到一个新的矩阵(b ij )。那么以(b ij )为系数矩阵求得的最优指派和原系数矩阵的最优指派相同。
值得注意的是，对于这个性质进行证明对于理解它是必要的。现在提供一个简短的证明如下： 设原问题的最优指派为
()()(){}
1122,,,n n A x x x σσσ= ，
其中，
()1i i x σ=， 0,1,ij ij x A C i j n ??=≤≤，
且()()()12n σσσ 是1到n 的一个排列。易见，相应的最优值为
()()()01122min n n Z c c c Z σσσ=+++=
不妨设()ij B b =是将()ij C C =的第一行各元素减去c 后得到的新矩阵。则B 所对应指派问题在A 上的值为。
()()()
()()
()()112211220,
B n n n n Z b b b c c c c Z c σσσσσσ=+++?+++=? = 所以，
0min B Z Z c ≤?。
另一方面，设B 在某指派()()(){}
1122,,,r r nr n x x x 上达到最小，即有
()()()()()
()()
()()()()
1122112201122min min B r r nr n r r nr n c r r nr n Z z b b b c c c c c c c c Z c Z c ==+++?++++++?≥?=
? ==。
故，
min min min c B c Z c Z Z c ?≤≤?
从而()
ij B b =在指派()()(){}
1122,,,n n x x x σσσ 上的值0Z c ?最小。 关于此性质有以下几点应说明如下：
1) ()ij B b =与()
ij C C =的最优指派相同是指它们的最优解集合完全一样，但它们的目标函数的量优值不一定相同。除非B = C 。
2) 这个性质提供了这样一种途径：在保留最优指派集合不变前提下，通过相应的行列变换，将原系数矩阵化为一个含有充分多0元素的矩阵，其指派问题最优解易于决定。
2. 指派的决定
指派的决定十分重要。如果当前矩阵中独立0元素(位于不同行列不同列的0元素)个数为阶数n 时，指派问题已经解决；当独立0元素个数小于n 时，由Konig 定理可知，必须将这个系数矩阵进一步化简，以便有更多的独立0元素出现。因此每次指派都起着承前启后的作用。
指派的决定包含两个阶段：首先进行试指派，然后根据性质3和匈牙利方法进行调节。其算法如下： Step 1. 利用性质3将原矩阵各行(列)减去响应行(列)的最小元素，直到新系数矩阵每行每列均有0出现。
赵天骁 等
Step 2. (救极大独立0元素集合。如果阶数较小，可以用直观法得到。否则，按以下步骤进行) 从0元素最少的行(列)开始，比较这一行各0元素所在列中0元素数目。选择0元素最少的那一列所对应0元素为一个独立0元素，然后划去同行同列其它0元素，直到所有0元素都被化去或被选定为0元素。如果独立0元素数目等于阶数n ，则最优指派已求出；否则执行下一步。
Step 3. (求最大独立0元素集合)
求出一对非独立0元素01和02，它们之间有一条交错链(独立0元素和非独立0元素交替出现)相连，而且这条交错链不可扩张成更长的交错链，则将链上的非独立0元素与链外独立0元素合并成一个更大的独立0元素集合。重复这一过程直到这样的可扩交错链不存在。(此时的独立0元素集合具有最多元)。
Step 4. 用匈牙利方法求得若干条直线覆盖所有0元素(直线数目 = 前一步求出极大独立0元素数目)。 Step 5. (寻求新的0元素)
在没有被直线覆盖的元素中求最小元素，然后在所有未被直线覆盖的行中各元素减去这个最小元素，同时在被竖直的直线覆盖各元素中加上这个最小元素(以保留相应列中独立0元素不变)。转Step 2。
关于这个算法有以下几点须说明如下： 1) 适用于极大独立0元素集合。
Step2求出的独立0元素集合不一定是最大的，但一定是极大的。(清华版《运筹学》[4]第132页亦未提供最大性的证明)。此处Step 3将其调节为最大的独立0元素集合。其理论基础是图论中匹配的交错路理论[1]。这因为匈牙利方法求出的覆盖0元素的直线数恰好求出等于当前的最大独立0元素数目。这一点可以由操作过程得出。
2) Step2可以简化。只用求用一个极大0元素集合替代，虽然Step2提供的方法过于繁琐。 3) 用Step4得出的新矩阵中0元素数目不一定比原来的矩阵的少(并非如清华版《运筹学》第131~132页强调的那样“0元素严格增加”)。
因为虽然在未被直线覆盖的元素中减去最小元素可增加其中的0元素，但在相应的竖直直线覆盖的元素中加上这个最小元保留却可能减少更多的0元素。但是，有一个重要的信息却保留下来了，即：新矩阵有一个极大独立0元素集合包含了当前直线所覆盖的极大独立0元素集合。表明新矩阵中极大独立0元素数不小于原矩阵的当前极大独立–元数目。这一点可以由下例中看出，在这里新矩阵是由原矩阵经过上述运算得到的。
020
3030010572980406365?
? ?
? 22032300837011
8040414
3?
? ? ?
左边矩阵含有11个0元而右边的含有10个0元，但是前者中独立0元素却在后者中保留下来。这里，·表示独立0元素。
4) 匈牙利方法求出竖直直线数目一定少于未被直线覆盖的元素形成矩阵的行数。这一点可由求直线的过程看出。
5) 总效率严格递减。
由性质(3)可以知道，原矩阵的行上减去的元素总和大于列上减去元素的总和，意即：新矩阵效率总和严格小于原矩阵效率总和。正是由于这个性质使得该算法执行至多α次后停止。这里，α是初始系数矩阵的总效率。
赵天骁 等
6) 本算法适用于最大化的指派问题。只要注意到此算法仅利用了效率系数均非负或均非正这个特性。将目标函数反号，同时所有效率系数反号，然后执行该算法求最小指派既可。
3. 应用
例1 求以下所示效率矩阵的指派问题的最小解。
779798966671712149151466104107109
解：第1行到第5行的最小元素分别为7，6，7，6，4。按照Step 1，各行分别减去各自的最小元素后得到一个各行各列均含0元素的矩阵
00202230000105729800406365
执行Step 2和Step 3选定一组最大的独立0元素(用实心的黑色圆·表示)，有
020
2230010572980406365?
? ?
?
因为：独立0元素数目 = 4 (<5)，必须执行Step 4以求4条直线覆盖所有0元素。这4条直线分别位于第1，2，4行和第1列，而未被覆盖的元素位于第3和第5行。其中最小元素是2。执行Step5后得到矩阵
2
202430083501180404143?
? ?
?
可以看出，执行Step 5后并未增加0元素。返回Step2求得一组最大独立0元素集合中实习黑圆所示)：
220243008350118040414
3? ? ? ?
赵天骁 等
其中独立0元素个数5 = 阶数。最优指派已经决定，既：
1224354351min 7696432Z c c c c c =++++=++++=
例2 计算以下赋权完全二部图的最小完美匹配。其中边(X i , Y j )权为矩阵中(i , j )处的值(如以下右边两个图所示)。
解：经过Step 2和Step 3选定独立0元素如中间上图所示，而下图对应于相应的匹配。经过Step 4和Step5求得新矩阵(所含0元素并未增加)，重新返回Step 2和Step 3选定最大独立0元素集合如右边上图所示，下边对应于相应的完美匹配。
6
1385
273
0763524
132
1111140032057
2525
0303
10??
??
?
?
?
?
?
其最小匹配值为
132431418ωωωω+++=
(注：利用该算法亦能计算赋权完全二部图上的最大匹配)。
基金项目
本文得到国家自然科学基金(数学基地科研训练及能力提高)项目资助和上海市科学技术委员会的资助，资助课题编号为13dz2260400。
参考文献 (References)
[1] Athanasiou, E. (2013) A Solomonic Solution to the Problem of Assigning a Private Indivisible Good. Games and
Economic Behavior , 82, 369-387. https://www.doczj.com/doc/b83267036.html,/10.1016/j.geb.2013.07.007 [2] Bastianoni, S., Pulselli, F.M. and Tiezzi, E. (2004) The Problem of Assigning Responsibility for Greenhouse Gas
Emissions. Ecological Economics , 49, 253-257. https://www.doczj.com/doc/b83267036.html,/10.1016/j.ecolecon.2004.01.018 [3] 田丰, 马仲蕃. 图与网络流理论[M]. 北京: 科学出版社, 1987. [4] 钱颂迪. 运筹学[M]. 北京: 清华大学出版社, 1997.
运筹学A卷) 一、单项选择题(从下列各题四个备选答案中选出一个正确答案,答案选错或未选者,该题不得分。每小题1分,共10分) 1.线性规划具有唯一最优解就是指 A.最优表中存在常数项为零 B.最优表中非基变量检验数全部非零 C.最优表中存在非基变量的检验数为零 D.可行解集合有界 2.设线性规划的约束条件为 则基本可行解为 A.(0, 0, 4, 3) B.(3, 4, 0, 0) C.(2, 0, 1, 0) D.(3, 0, 4, 0) 3.则 A.无可行解 B.有唯一最优解medn C.有多重最优解 D.有无界解 4.互为对偶的两个线性规划, 对任意可行解X 与Y,存在关系 A.Z > W B.Z = W C.Z≥W D.Z≤W 5.有6 个产地4个销地的平衡运输问题模型具有特征 A.有10个变量24个约束
B.有24个变量10个约束 C.有24个变量9个约束 D.有9个基变量10个非基变量 6、下例错误的说法就是 A.标准型的目标函数就是求最大值 B.标准型的目标函数就是求最小值 C.标准型的常数项非正 D.标准型的变量一定要非负 7、m+n－1个变量构成一组基变量的充要条件就是 A.m+n－1个变量恰好构成一个闭回路 B.m+n－1个变量不包含任何闭回路 C.m+n－1个变量中部分变量构成一个闭回路 D.m+n－1个变量对应的系数列向量线性相关 8.互为对偶的两个线性规划问题的解存在关系 A.原问题无可行解,对偶问题也无可行解 B.对偶问题有可行解,原问题可能无可行解 C.若最优解存在,则最优解相同 D.一个问题无可行解,则另一个问题具有无界解 9、有m个产地n个销地的平衡运输问题模型具有特征 A.有mn个变量m+n个约束…m+n-1个基变量 B.有m+n个变量mn个约束 C.有mn个变量m+n－1约束 D.有m+n－1个基变量,mn－m－n－1个非基变量 10.要求不超过第一目标值、恰好完成第二目标值,目标函数就是
3）若问题中 x2 列的系数变为（3，2）T，问最优解是否有变化； 4）c2 由 1 变为 2，是否影响最优解，如有影响，将新的解求出。 Cj CB 0 0 Cj-Zj 0 4 Cj-Zj 3 4 Cj-Zj 最优解为 X1=1/3,X3=7/5,Z=33/5 2对偶问题为Minw=9y1+8y2 6y1+3y2≥3 3y1+4y2≥1 5y1+5y2≥4 y1,y2≥0 对偶问题最优解为 y1=1/5,y2=3/5 3 若问题中 x2 列的系数变为（3，2）T 则P2’=(1/3,1/5σ2=-4/5＜0 所以对最优解没有影响 4）c2 由 1 变为2 σ2=-1＜0 所以对最优解没有影响 7. 求如图所示的网络的最大流和最小截集(割集，每弧旁的数字是（cij , fij ）。（10 分） V1 (9,5 (4,4 V3 (6,3 T 3 XB X4 X5 b 9 8 X1 6 3 3 X4 X3 1 8/5 3 3/5 3/5 X1 X3 1/3 7/5 1 0 0 1 X2 3 4 1 -1 4/5 -11/5 -1/3 1 - 2 4 X 3 5 5 4 0 1 0 0 1 0 0 X4 1 0 0 1 0 0 1/3 -1/ 5 -1/5 0 X5 0 1 0 -1 1/5 -4/5 -1/3 2/5 -3/5 VS (3,1 (3,0 (4,1 Vt (5,3 V2 解： (5,4 (7,5 V4 V1 (9,7 (4,4 V3 (6,4 (3,2 Vs (5,4 (4,0 Vt (7,7 6/9 V2 最大流＝11 (5,5 V4 8. 某厂Ⅰ、Ⅱ、Ⅲ三种产品分别经过 A、B、C 三种设备加工。已知生产单位各种产品所需的设备台时，设备的现有加工能力及每件产品的预期利润见表：ⅠⅡⅢ设备能力(台.h A 1 1 1 100 B 10 4 5 600 C 2 2 6 300 单
《运筹学》试卷一 一、（15分）用图解法求解下列线性规划问题 二、（20分）下表为某求极大值线性规划问题的初始单纯形表及迭代后的表，、 为松弛变量，试求表中到的值及各变量下标到的值。 -13 1 1 6 1 1-200 2-1 1 1/2 1/2 1 4 07 三、（15分）用图解法求解矩阵对策， 其中 四、（20分） （1）某项工程由8个工序组成，各工序之间的关系为 工序a b c d e f g h 紧前工序——a a b,c b,c,d b,c,d e 试画出该工程的网络图。 （2）试计算下面工程网络图中各事项发生的最早、最迟时间及关键
线路（箭线下的数字是完成该工序的所需时间，单位：天） 五、（15分）已知线性规划问题 其对偶问题最优解为，试根据对偶理论求原问题的最优解。 六、（15分）用动态规划法求解下面问题：
七、（30分）已知线性规划问题 用单纯形法求得最优单纯形表如下，试分析在下列各种条件单独变化的情况下，最优解将如何变化。 2 -1 1 0 0 2 3 1 1 3 1 1 1 1 1 6 10 0 -3 -1 -2 0 （1）目标函数变为； （2）约束条件右端项由变为； （3）增加一个新的约束： 八、（20分）某地区有A、B、C三个化肥厂向甲、乙、丙、丁四个销地供应同一种化肥，已知产地产量、销地需求量和各产地运往不同销地单位运价如下表，试用最小元素法确定初始调运方案，并调整求最优运输方案 销地 产地 甲乙丙丁产量 A41241116 B2103910
C8511622需求量814121448 《运筹学》试卷二 一、（20分）已知线性规划问题： （a）写出其对偶问题； （b）用图解法求对偶问题的解； （c）利用（b）的结果及对偶性质求原问题的解。 二、（20分）已知运输表如下： 销地 产地B1B2B3B4供应量 50 A 1 3 2 7 6 A 2 60 7 5 2 3 25 A 3 2 5 4 5 需求量60 40 20 15 （1）用最小元素法确定初始调运方案； （2）确定最优运输方案及最低运费。 三、（35分）设线性规划问题 maxZ=2x1+x2+5x3+6x4
运筹学实践报告指派问题
第一部分问题背景 泰泽公司（Tazer）是一家制药公司。它进入医药市场已经有12年的历史了，并且推出了6种新药。这6种新药中5种是市场上已经存在药物的同类产品，所以销售的情况并不是很乐观。然而，主治高血压的第6种药物却获得了巨大的成功。由于泰泽公司拥有生产治疗高血压药物的专利权，所以公司并没有遇到什么竞争对手。仅仅从第6种药物中所获得的利润就可以使泰泽公司正常运营下去。 在过去的12年中，泰泽公司不断地进行适量的研究和发展工作，但是却并没有发现有哪一种药物能够获得像高血压药物一样的成功。一个原因是公司没有大量投资进行创新研究开发的动力。公司依赖高血压药物，觉得没有必要花费大量的资源寻找新药物的突破。 但是现在泰泽公司不得不面对竞争的压力了。高血压药物的专利保护期还有5年1。泰泽公司知道只要专利期限一到，大量药品制造公司就会像秃鹰一样涌进市场。历史数据表明普通药物会降低品牌药物75%的销售量。 今年泰泽公司投入大量的资金进行研究和开发工作以求能够取得突破，给公司带来像高血压药物一样的巨大成功。泰泽公司相信如果现在就开始进行大量的研究和开发工作，在高血压药物专利到期之后能够发明一种成功药物的概率是很高的。作为泰泽公司研究和开发的负责人，你将负责选择项目并为每一个项目指派项目负责人。在研究了市场的需要，分析了当前药物的不足并且拜会了大量在有良好前景的医药领域进行研究的科学家之后，你决定你的部门进行五个项目，如下所示： Up项目：开发一种更加有效的抗忧郁剂，这种新药并不会带来使用者情绪的急剧变化。 Stable项目：开发一种治疗躁狂抑郁病的新药。 Choice项目：为女性开发一种副作用更小的节育方法。 Hope项目：开发一种预防HIV的疫苗。 Release项目：开发一种更有效的降压药。 对于这5个项目之中的任何一个来说，由于在进行研究之前你并不知道使用的配方以及哪种配方是有效的，所以你只能明确研究所要解决的疾病。 你还有5位资深的科学家来领导进行这5个项目。有一点你十分清楚，那就是科学家都是一些喜怒无常的人，而且他们只有在受到项目所带来的挑战和激励的时候才会努力工作。为了保证这些科学家都能够到他们感兴趣的项目中去，你为这个项目建立了一个投标系统。这5位科学家每个人都有1000点的投标点。 1一般来说，专利权保护发明的期限为17年。在1995年，GATT立法拓展专利权的保护期限到20年。在本案例之中，泰泽公司的高血压药物的注册时间是在1995年之前，所以专利权只能够保护这种药物17年。
运筹学试题及答案 一、填空题(本大题共8小题，每空2分，共20分) 1．线性规划问题中，如果在约束条件中出现等式约束，我们通常用增加__人工变量_的方法来产生初始可行基。2．线性规划模型有三种参数，其名称分别为价值系数、_技术系数 __和__限定系数_。 3．原问题的第1个约束方程是“=”型，则对偶问题相应的变量是__无非负约束(或无约束、或自由)_变量。 4．求最小生成树问题，常用的方法有：避圈法和 _破圈法__。 5．排队模型M／M／2中的M，M，2分别表示到达时间为__负指数_分布，服务时间服从负指数分布和服务台数为2。 6．如果有两个以上的决策自然条件，但决策人无法估计各自然状态出现的概率，那么这种决策类型称为__不确定__型决策。 7．在风险型决策问题中，我们一般采用__效用曲线_来反映每个人对待风险的态度。 8．目标规划总是追求目标函数的_ 最小 __值，且目标函数中没有线性规划中的价值系数，而是在各偏差变量前加上级别不同的__ 优先因子(或权重)__。 二、单项选择题(本大题共l0小题，每小题3分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。多选无分。 9．使用人工变量法求解极大化线性规划问题时，当所有的检验数在基变量中仍含有非零的人工变量，表明该线性规划问题【 D 】 A．有唯一的最优解 B．有无穷多最优解 C．为无界解 D．无可行解 10．对偶单纯形法解最大化线性规划问题时，每次迭代要求单纯形表中【 D 】 A．b列元素不小于零 B．检验数都大于零 C．检验数都不小于零 D．检验数都不大于零 11．已知某个含10个结点的树图，其中9个结点的次为1，1，3，1，1，1，3，1，3，则另一个结点的次为【 A 】A．3 B．2 C．1 D．以上三种情况均有可能 12．如果要使目标规划实际实现值不超过目标值。则相应的偏离变量应满足【 B 】 13．在运输方案中出现退化现象，是指数字格的数目【 C 】 A．等于 m+n B．等于m+n-1 C．小于m+n-1 D．大于m+n-1 16．关于线性规划的原问题和对偶问题，下列说法正确的是【 B 】 A．若原问题为无界解，则对偶问题也为无界解 B．若原问题无可行解，其对偶问题具有无界解或无可行解 c．若原问题存在可行解，其对偶问题必存在可行解
浅谈运筹学中的运输问题 摘 要：运筹学自二战以来开始打来那个应用在除战争以外的许多领域，尤其在企业管理中表现的尤为突出。运筹学的思想贯穿了企业管理的始终，在企业战略管理、生产计划、市场营销、运输问题、库存管理、人事管理、财务会计等各个方面都具有重要的作用，对企业管理的发展产生重要影响。这里我们主要对运输问题几种方法做一个简单的介绍。 关键词：最下元素法；沃格尔法（V ogel ） 首先我们先来介绍运输问题的数学模型：设有m 个产地（记作A 1，A 2，A 3,…,Am ），生产某种物资，其产量分别为a 1,a 2，…，am ；有n 个销地（记作B 1，B 2，…，Bn ），其需要量分别为b 1,b 2，…，bn ；且产销平衡，即 。从第i 个产地到j 个销地的单位运价为cij ，在满足各地需要的前提下，求总运输费用最小的调运方案。 设xij (i =1,2,…，m ；j =1,2,…,n )为第i 个产地到第j 个销地的运量，则数学模型为： n j m i x n j b x m i a x ij j m i ij n j i ij ,,1;,,1, 0,,1,,11 1 ==≥====∑∑== ∑∑ ===n j ij ij m i x c z 1 1 min （！）最小元素法：最小元素法的思想是就近优先运送，即最小运价Cij 对应的变量xij 优先赋值 {} j i ij b a x ,min = 然后再在剩下的运价中取最小运价对应的变量赋值并满足约束，依次下去，直到最后一个初始基可行解。 下面举一个例子：求表3－7给出的运输问题的初始基本可行解。
解： 在x 12、x 22、x 33、x 34中任选一个变量作为基变量，例如选x 12 初始基本可行解可用下列矩阵表示 ??????????634610 表3－8中，标有符号 的变量恰好是3+4－1=6个且不包含闭回路， {} 323123141312,,,,,x x x x x x 是一组基变量，其余标有符号×的变量是非基变量， （2）运费差额法（V ogel ）:最小元素法只考虑了局部运输费用最小，对整个产销系统的总运输费用来说可能离最优值较远。有时为了节省某一处的运费，而在其它处可能运费很大。运费差额法对最小元素法进行了改进，考虑到产地到销地的最小运价和次小运价之间的差额，如果差额很大，就选最小运价先调运，否则会增加总运费。例如下面两种运输方案， 20101258515 10??????=?C 2010125815510? ?????=?C 15 15 15 15 前一种按最小元素法求得，总运费是Z 1=10×8+5×2+15×1=105，后一种方案考虑到C 11与C 21之间的差额是8－2=6，如果不先调运x 21，到后来就有可能x 11≠0，这样会使总运费增加较大，从而先调运x 21，再是x 22，其次是x 12这时总运费Z 2=10×5+15×2+5×1=85 运筹学 课 程 设 计 报 告 专业： 班级： 学号： ： 2012年6月20日 目录 一、题目。 二、算法思想。 三、算法步骤。 四、算法源程序。 五、算例和结果。 六、结论与总结。 一、题目：匈牙利法求解指派问题。 二、算法思想。 匈牙利解法的指派问题最优解的以下性质： 设指派问题的系数矩阵为C=()c ij n n?，若将C的一行（或列）各元素分别减去一个常数k（如该行或列的最小元素），则得到一个新的矩阵C’=()'c ij n n?。那么，以C’位系数矩阵的指派问题和以C位系数矩阵的原指派问题有相同最优解。 由于系数矩阵的这种变化不影响约束方程组，只是使目标函数值减少了常 数k，所以，最优解并不改变。必须指出，虽然不比要求指派问题系数矩阵中无 负元素，但在匈牙利法求解指派问题时，为了从以变换后的系数矩阵中判别能否 得到最优指派方案，要求此时的系数矩阵中无负元素。因为只有这样，才能从总 费用为零这一特征判定此时的指派方案为最优指派方案。 三、算法步骤。 （1）变换系数矩阵，使各行和各列皆出现零元素。 各行及各列分别减去本行及本列最小元素，这样可保证每行及每列中都有 零元素，同时，也避免了出现负元素。 （2）做能覆盖所有零元素的最少数目的直线集合。 因此，若直线数等于n，则以可得出最优解。否则，转第（3）步。 对于系数矩阵非负的指派问题来说，总费用为零的指派方案一定是最优指派方案。在第（1）步的基础上，若能找到n个不同行、不同列的零元素，则对应的指派方案总费用为零，从而是最优的。当同一行（或列）上有几个零元素时，如选择其一，则其与的零元素就不能再被选择，从而成为多余的。因此，重要的是零元素能恰当地分布在不同行和不同列上，而并在与它们的多少。但第（1）步并不能保证这一要求。若覆盖所有零元素的最少数目的直线集合中的直线数目是n，则表明能做到这一点。 此时，可以从零元素的最少的行或列开始圈“0”，每圈一个“0”，同时把位于同行合同列的其他零元素划去（标记为），如此逐步进行，最终可得n个位于不同行、不同列的零元素，他们就对应了最优解；若覆盖所有零元素的最少数目的直线集合中的元素个数少于n，则表明无法实现这一点。需要对零元素的分布做适当调整，这就是第（3）步。 （3）变换系数矩阵，是未被直线覆盖的元素中出现零元素。回到第（2）步。 在未被直线覆盖的元素中总有一个最小元素。对未被直线覆盖的元素所在的行（或列）中各元素都减去这一最小元素，这样，在未被直线覆盖的元素中势必会出现零元素，但同时却又是以被直线覆盖的元素中出现负元素。为了消除负元素，只要对它们所在的列（或行）中个元素都加上这一最小元素（可以看作减去这一最小元素的相反数）即可。 四、算法源程序。 最全的运筹学复习题及 答案78213 四、把下列线性规划问题化成标准形式： 2、minZ=2x1-x2+2x3 五、按各题要求。建立线性规划数学模型 1、某工厂生产A、B、C三种产品，每种产品的原材料消耗量、机械台时消耗量以及这些资源的限量，单位产品的利润如下表所示： 根据客户订货，三种产品的最低月需要量分别为200，250和100件，最大月销售量分别为250，280和120件。月销售分别为250 ，280和120件。问如何安排生产计划，使总利润最大。 2、某建筑工地有一批长度为10米的相同型号的钢筋，今要截成长度为3米的钢筋 90根，长度为4米的 钢筋60根，问怎样下料，才能使所使用的原材料最省? 1．某运输公司在春运期间需要24小时昼夜加班工作，需要的人员数量如下表所示：起运时间服务员数 2—6 6—10 10一14 14—18 18—22 22—2 4 8 10 7 12 4 每个工作人员连续工作八小时，且在时段开始时上班，问如何安排，使得既满足以上要求，又使上班人数最少? 五、分别用图解法和单纯形法求解下列线性规划问题．并对照指出单纯形迭代的每一步相 当于图解法可行域中的哪一个顶点。 六、用单纯形法求解下列线性规划问题： 七、用大M法求解下列线性规划问题。并指出问题的解属于哪一类。 八、下表为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为maxZ=5x1+3x2，约束形式为“≤”，X3，X4为松驰变量．表中解代入目标函数后得Z=10 X l X2X3X4 —10 b -1 f g X3 2 C O 1 1／5 X l a d e 0 1 (1)求表中a～g的值 (2)表中给出的解是否为最优解? （1）a=2 b=0 c=0 d=1 e=4/5 f=0 g=－5 （2）表中给出的解为最优解 第四章线性规划的对偶理论 五、写出下列线性规划问题的对偶问题 1．minZ=2x1+2x2+4x3 P66： 8.某部门有3个生产同类产品的工厂（产地），生产的产品由4个销售点出售，各工厂A 1， A 2，A 3的生产量、各销售点B 1，B 2，B 3，B 4的销售量（假定单位为t ）以及各工厂到销售点的单位运价（元/t ）示于下表中，问如何调运才能使总运费最小？ 表 解：一、该运输问题的数学模型为： 可以证明：约束矩阵的秩为r (A) = 6. 从而基变量的个数为 6. 34 33323124232221 3141 141312116115893102114124min x x x x x x x x x x x x x c z i j ij ij +++++++++++== ∑∑ ==??? ??????????==≥=++=++=++=++=+++=+++=+++4,3,2,1;3,2,1,0141214822 1016342414332313322212312111343332312423222114131211j i x x x x x x x x x x x x x x x x x x x x x x x x x ij 111213142122232431323334x x x x x x x x x x x x 712111111111111111111111111??? ? ? ? ? ? ? ? ? ??? 二、给出运输问题的初始可行解（初始调运方案） 1. 最小元素法 思想：优先满足运价（或运距）最小的供销业务。 其余（非基）变量全等于零。此解满足所有约束条件，且基变量（非零变量）的个数为6（等于m+n-1=3+4-1=6). 总运费为（目标函数值） ,1013=x ,821=x ,223=x ,1432=x ,834=x ,614=x ∑∑===314 1 i j ij ij x c Z 运筹学作业 -----关于指派问题的求解算法设计 学院:计算机科学与技术学院 班级:信息与计算科学1202班 学号:1208060220 姓名:韩雪平 2014、7、3 1.问题描述与数学模型: 在现实生活中,有各种各样的指派问题。例如,有若干项工作(或者任务,事情)需要分配给若干人(或者部门,设备等)来完成;有若干项合同需要选择若干个投标者来承包;有若干条交通线(如航空线,航海线,公路线等)需要配置若干交通运输工具(如飞机,船只,汽车等)来运营;有若干班级需要安排在不同的教师里上课;等等/诸如此类问题,它们的基本要求就是来满足特定的指派要求时,使指派方案的总体效果最佳。由于指派总就是多样性的,有必要定义指派的特定问题的标准形式。 指派问题的标准形式(以人与事为例):设有n个人与n件事,已知第i个人做第j件事的费用为cij(i,j=1,2,、、、、n),求人与事之间一一对应的指派方案,使完成的这n件事的总费用最少。 一般称矩阵 c11 c12 c13 c14 (1) c21 c22 c23 c24 (2) c31 c32 c33 c34 (3) C= 、、、、、 、、、、、 、、、、、 cn1 cn2 cn3 cn4……cn5 为指派问题的系数矩阵。在实际问题中,根据cij的具体意义,矩阵C可以有不同的名称,如费用矩阵,成本矩阵,时间矩阵等。系数矩阵C中,第i行各元素表示第i人做各事的费用,第j列各元素表示第j件事由各个人做的费用。 为建立标准的指派问题的数学模型,引入n^2个0-1变量 1 当指派第i人去做第i件事时 Xij=｛ (i,j=1,2,3……,n) 0 当不指派第i人去做第j件事时 然后对矩阵进行化解,当然作为可行解,矩阵中每一列都有且只有一个1,每行有且仅有一个1,以满足约束条件 第七章运输问题 7.1 一个农民承包了6块耕地共300亩，准备播种小麦、玉米、水果和蔬菜四种农产品， 问如何安排种植计划，可得到最大的总收益。 解： 这是一个产销平衡的运输问题。可以建立下列的运输模型： 代入产销平衡的运输模板可得如下结果： 得种植计划方案如下表： 7.2 某客车制造厂根据合同要求从当年开始起连续四年年末交付40辆规格型号相同的大型客车。该厂在这四年内生产大型客车的能力及每辆客车的成本情况如下表： 根据该厂的情况，若制造出来的客车产品当年未能交货，每辆车每积压一年的存储和维 护费用为4万元。在签订合同时，该厂已储存了20辆客车，同时又要求四年期未完成合同后还需要储存25辆车备用。问该厂如何安排每年的客车生产量，使得在满足上述各项要求的情况下，总的生产费用加储存维护费用为最少？ 解：得运价表（产大于销的运输模型）如下： 第一季度正常上班生产20台，加班27台，拿出正常生产18台和加班2台，加上年前储存的20台，满足本季度的40台； 第二季度正常生产38台，不安排加班。加上第一季度储存的2台，满足本季度的40台； 第三季度正常生产15台，不安排加班。加上第一季度储存的25台，满足本季度的40台； 第四季度正常生产42台。加班生产23台。拿出正常生产的17台的加班生产的23台满足本季度的40台。剩余25台以后务用。 7.3 某企业生产有甲、乙、丙、丁四个分厂生产同一种产品，这四个分厂的产量分别为：200吨、300吨、400吨和100吨，这些产品供应给A、B、C、D、E、F六个地区，六个地区的需求量分别为：200吨、150吨、350吨、100吨、120吨、120吨。由于工艺、技术的差别，各分厂运往各销售地区的单位运价（万元/吨）、各厂单位产品成本（万元/吨）和各销地的销售价格（万元/吨）如下表： Advances in Applied Mathematics 应用数学进展, 2016, 5(1), 45-50 Published Online February 2016 in Hans. https://www.doczj.com/doc/b83267036.html,/journal/aam https://www.doczj.com/doc/b83267036.html,/10.12677/aam.2016.51007 On the Assigning Problem in Operation Research Tianxiao Zhao1, Fugang Chao2, Han Ren2,3 1Department of Mathematical Science, Tsinghua University, Beijing 2Department of Mathematics, East China Normal University, Shanghai 3Shanghai Key Laboratory of Pure Mathematics and Mathematical Practice, Shanghai Received: Jan. 29th, 2016; accepted: Feb. 21st, 2016; published: Feb. 24th, 2016 Copyright ? 2016 by authors and Hans Publishers Inc. This work is licensed under the Creative Commons Attribution International License (CC BY). https://www.doczj.com/doc/b83267036.html,/licenses/by/4.0/ Abstract In this paper, we characterize the assigning problem and present an algorithm to compute the op-timal solutions efficiently. In our everyday life, such problems are always needed to use assigning methods to give a good solution. Since they are 0-1 problem, we may find relative optimal solu-tions. Keywords Operation Research, Assigning Problem, Simplicial Algorithm 运筹学中的指派问题 赵天骁1，晁福刚2，任韩2,3 1清华大学数学科学系，北京 2华东师范大学数学系，上海 3上海市核心数学与实践重点实验室，上海 收稿日期：2016年1月29日；录用日期：2016年2月21日；发布日期：2016年2月24日 第七章运输问题 一个农民承包了6块耕地共300亩，准备播种小麦、玉米、水果和蔬菜四种农产品， 问如何安排种植计划，可得到最大的总收益。 解： 这是一个产销平衡的运输问题。可以建立下列的运输模型： 代入产销平衡的运输模板可得如下结果： 得种植计划方案如下表： 某客车制造厂根据合同要求从当年开始起连续四年年末交付40辆规格型号相同的大型客车。该厂在这四年内生产大型客车的能力及每辆客车的成本情况如下表： 根据该厂的情况，若制造出来的客车产品当年未能交货，每辆车每积压一年的存储和维 护费用为4万元。在签订合同时，该厂已储存了20辆客车，同时又要求四年期未完成合同后还需要储存25辆车备用。问该厂如何安排每年的客车生产量，使得在满足上述各项要求的情况下，总的生产费用加储存维护费用为最少？ 解：得运价表（产大于销的运输模型）如下： 第一季度正常上班生产20台，加班27台，拿出正常生产18台和加班2台，加上年前储存的20台，满足本季度的40台； 第二季度正常生产38台，不安排加班。加上第一季度储存的2台，满足本季度的40台； 第三季度正常生产15台，不安排加班。加上第一季度储存的25台，满足本季度的40台； 第四季度正常生产42台。加班生产23台。拿出正常生产的17台的加班生产的23台满足本季度的40台。剩余25台以后务用。 某企业生产有甲、乙、丙、丁四个分厂生产同一种产品，这四个分厂的产量分别为：200吨、300吨、400吨和100吨，这些产品供应给A、B、C、D、E、F六个地区，六个地区的需求量分别为：200吨、150吨、350吨、100吨、120吨、120吨。由于工艺、技术的差别，各分厂运往各销售地区的单位运价（万元/吨）、各厂单位产品成本（万元/吨）和各销地的销售价格（万元/吨）如下表： 第三章运输问题 一、学习目的与要求 1、掌握表上作业法及其在产销平衡运输问题求解中的应用 2、掌握产销不平衡运输问题求解方法 二、课时 6学时 第一节 运输问题及其数学模型 一、运输问题的数学模型 单一品种运输问题的典型情况：设某种物品有m 个产地A 1,A 2,…,A m ，各产地的产量分别是a 1,a 2,…,a m ；有N 个销地B 1,B 2,…,B n ，各销地地销量分别为b 1,b 2,…,b n 。假定从产地A i (i =1,2, …,m )向销地B j (j =1,2,…,n )运输单位物品的运价是c ij ，问怎样调运这些物品才能使总运费最小？ 表中x ij i j ij i j 如果运输问题的总产量等于其总销量，即有 ∑∑===n j j m i i b a 1 1 则称该运输问题为产销平衡运输问题；反之，称为产销不平衡运输问题。 产销平衡运输问题的数学模型如下： ???? ? ????≥=====∑∑∑∑===+=0,...,2,1,...,2,1..min 1 111 1 ij m i j ij n j i ij m i n j ij ij x n j b x m i a x t s x c z 这就是运输问题的数学模型，它包含m ×n 个变量，(n 十m)个约束方程．其系数矩阵的结构比较松散，且特殊。 二、运输问题数学模型的特点 1、运输问题有有限最优解，即必有最优基本可行解 2、运输问题约束条件的系数矩阵A 的秩为 (m+n-1) 该系数矩陈中对应于变量x ij 的系数向量p ij ，其分量中除第i 个和第m 十j 个为1以外，其余的都为零．即 A ij ＝(0…1…1…0)’=e i +e m+j 对产销平衡的运输问题具有以下特点： (1)约束条件系数矩阵的元素等于0或1 (2)约束条件系数矩阵的每一列有两个非零元素，对应于每一个变量在前m 个约束方程中出现一次，在后n 个约束方程中也出现一次。 此外，对于产销平衡问题，还有以下特点 (3)所有结构约束条件都是等式约束 (4)各产地产量之和等于各销地销量之和 运筹学在运输问题中的应用 关键字：运筹学运输 引言：运输是土木工程中经常遇到的问题，在工程造价中占较大的比例。如何使运输费用达到最小化，这就需要在施工前优化施工组织设计，将运筹学、网络技术等理论的设计方法应用到施工中，使得成本费用最经济。下面我们借鉴运筹学中的理论来解决运输问题。 一、运输路线最短问题。 根据运筹学中最短路径算法，寻找最短路线，就是从最后一段开始，用由后向前逐步递推的方法求卅各点到终点的最短路线，最终求得南起点到终点的最短路线。 某工程需要从点Sl运送500吨的建筑材料一个工地S1O。 首先．将图l的路线问题看成四个阶段的问题．南S1到S2，S3，S4为第一阶段；南S2，S3，S4到S5，S6，S7为第二阶段；南S5，S6，S7到S8。S9为第i阶段；南S8，S9到SIO为第四阶段。下面引进几个符号： D(Sk,Sm)为Sk到Sm的距离，f(Sk)Sk到终点的最短距离。 (1)在第四阶段。 目前状态可以是S8或S9，可选择的下一状态是S1O，所以有 (2)在第i阶段。 目前状态可以是S5或S6或S7，可以选择的下一状态为S8或S9．所以有 (3)在第二阶段。 目前状态可以是S2或S3或S4，可以选择的下一状态为S5或S6或S7，所以有 (4)在第一阶段。 目前状态只有S1，可以选择的下一状态为S2或S3或S4．所以有 通过最短路径算法计算。可知从Sl(出发点)到S1O(终点)的最短运输路程为1080千米(权数路径距离)，所走的最优路线采用“顺序追踪法”来确定，最优运输路径：S1一S3一S6—S8—S10。 二、自卸车排队问题 在工程中经常遇到材料的运输和施工之间的关系，例如铺路的碎石、沥青的运输和路面的铺设之间的关系。如果运输工作进行得太快，而施工进程跟不上，就会有太多的原料来不及施工，导致运输设备和人员的闲置。相反，如果运输进度赶不上施工，就会出现施工设备和人员的闲置。 下面以高速公路高速公路沥青路面机械化施工系统为例子进行说明。高速公路沥青路面机械化施工系统，是指以沥青混合料拌和站、自卸汽车、沥青混凝土摊铺机、初压压路机、复压压路机、终压压路机等6种主体机械组成的沥青路面铺筑机群施工系统。沥青混凝土混合料作为纽带，将这6种机械共同联系在一起。准确、协调地工作，形成在“拌和一运料一摊铺一初压一复压一终压”过程中机械间的“相互影响、相互联系、相互制约”规律，即沥青路面施工系统机群工作规律。” 要研究沥青路面施工系统机群工作规律，首先应研究、分析机群施工系统的概率规律性及机械排队数量的目的，为研究拌和站、自卸汽车、摊铺机、初压压路机、复压压路机、终压压路机的运行工作情况作准备，为该系统资源优化配置(即机械的性能与数量优化组合)提供理论依据。其中重点是研究机械排队队长分布和机械排队数量。 1、系统流程分析 系统理想的工作情况是：当沥青混合料拌和站刚拌合好l车料时，就有l辆汽车到达拌和站处并装料；当摊铺机需要进料时，就有1辆汽车到达摊铺机处并立即卸料；沥青混凝土经摊铺机摊铺后，压路机立即分别予以压实。 拌和子系统是指由拌和站与运料汽车形成的系统。汽车总数是有限的。如只有M辆汽车，每辆汽车来到系统中接受服务后仍回到原来的总体，还会再来。由于拌和站的空间比较大，运输汽车是有限的，不会出现有运输车不能进入的情况，所以问题可以归结为单服务台等待制模型M/M/1/∞。这类问题的主要特征是系统空问是无限的，允许永远排队。 设：M为运料汽车总数量；L为平均队长；λn为拌和站处汽车平均到达率；μn为拌和站服务率，即单位时间内装车数量；W为平均逗留时间；Wq为平均等待时间。则系统状态流图见图1。 《数值分析》课程设计非线性方程求根公式的集成与菜单调用 院（系）名称信息工程学院 专业班级12普本信计 学号1201110054 学生姓名孟浩 指导教师孔繁民 2015年6月16日 课程设计任务书 2014—2015学年第二学期 专业班级：12 普本信计学号：1201110054 姓名：孟浩 课程设计名称：运筹学 设计题目：运筹学模型在运输问题中的应用 完成期限：自2015年 5 月24 日至2015 年05 月30 日共 1 周一、设计目的 运筹帷幄之中，决胜千里之外。运筹学是多种学科的综合性学科，是最早形成的一门软科学。他把科学的方法、技术和工具应用到包括一个系统管理在内的各种问题上，以便为那些掌握系统的人们提供最佳的解决问题的办法。他用科学的方法研究与某一系统的最优管理有关问题。因此运筹学是一门有重要应用价值的学科，特别在现代科学管理中是处处离不开运筹学。为了更好的理解运筹学，我们运用运筹学知识建立数学模型来解决运输问题中的应用的问题。 二、设计要求 1、运用LINGO等工具。 2、运筹学模型在运输问题中的应用。 3、按照格式要求写出3000字文档。 三、参考文献 [1]谢金星薛毅，优化建模与LINDO/LINGO软件[M]，北京：清华大学出版社. [2]吴祈宗，运筹学[M] ，北京：机械工业出版社. [3]朱德通，最优化模型与实验/应用数学系列丛书[M] ，上海：同济大学出版社 [4]谷歌地图 https://www.doczj.com/doc/b83267036.html,/maps?q=%E4%BB%CB%AE+%BB%AF%B7%CA&ie=gbk. 工作任务与工作量要求：查阅文献资料不少于3篇，课程设计报告1篇不少于3000字 指导教师（签字）：教研室主任（签字）： 批准日期：年月日运筹学指派问题的匈牙利法实验报告
最全的运筹学复习题及答案78213
运筹学(胡运权版)第三章运输问题课后习题答案
运筹学指派问题
第七章 运筹学 运输问题案例
运筹学中的指派问题
运筹学 运输问题案例
运筹学课件第三章运输问题
运筹学在运输问题中的应用
运筹学模型在运输问题中的应用
相关主题
文本预览