运筹学排班问题大作业
运筹学排班问题的建模和程序设计报告
2011级工业工程一班
杨添淇
1120110892
Yangwr2012@https://www.wendangku.net/doc/7215265513.html, 0.前言
本报告共分为五个部分：
1.排班问题的提出
2.建模的心路历程
3.新的背景与设定
4.新的建模
5.建模后的思考
其中，第二部分与第五部分最为用力，集中体现了作者想要表达的观点。其实这两部分应该写在分析报告里吧？好像搞反了…
是为序。
1.排班问题的提出
某小区组建维修保洁服务，现需要招聘维修保洁人员若干轮班工作。其中包括电工，水管工，和保洁员。工作采用计时制，每人工作满8小时后可以下班，如张三在6点上班，可在下午2点下班。根据统计，小区需求人数如下表：
时间电工水管工保洁
0点-2点 1 0 0
2点-4点0 0 0
4点-6点0 0 0
6点-8点 6 3 0
8点-10点8 6 3
10点-12点9 5 7
12点-14点 4 4 3
14点-16点8 7 5
16点-18点 4 12 10
18点-20点12 16 6
20点-22点 5 8 2
22点-24点 3 2 0
维修保洁服务的收费标准是：电工25元/小时，水工20元/小时，保洁15元/小时。试制定招聘计划和工人的排班表（即：招聘工人的数量和每个工人的上班时间）。
2.建模的心路历程
余以为，老师要我们交报告，绝不是走个形式，也不仅仅是要看我们写出的冷冰冰的代码，求解问题的能力，更是要看我们思维的走向：从哪里来，到哪里去，最终形成一条清晰的路径。确实，看这个路径的形成过程是一件非常有趣的事，记录这个过程亦然。是故，我采用了完全写实的笔法，彻头彻尾地记录下了自己的真实想法，怎么想的怎么写的，想怎么写就怎么写。所以，报告的这个部分叫做：建模的心路历程（多么温润而厚重的小标题啊）。问题的最后提到了收费问题，旋即戛然而止，留给了解题人无限的遐想空间。我想老师的本意，是好的。但读完题后，我的第一个问题便出在这最后一句上：“收费标准”中的“收费”二字作何解。
从语法角度上来讲，这是一个没有主语的动词做了“标准”二字的定语。“收费”这个动作的主语对我们求解这个问题，起着至关重要的作用。
从一个久经考场的学生的角度来看，这个收费标准应该等同于工资来看：因为工资标准在这道问题中是除了用工需求外最应该出现的已知条件，而且与聘用资费优化息息相关。
而从一个居民，一个一般人的角度来看，收费应该指的是工作的时候向住户收取的费用。其唯如此，才可以真正称得上是收费。但是转念一想，我交了一年的物业费，中间再有什么问题的话你来维修是不该收取任何费用的。这就像买了保险之后得了病，不能说自己再把医药费全扛下来，那样保险就没用了。再退一步说，就算交了物业费再找电工维修需要再交钱的话，也不应该按照时长收费——保洁倒还罢了，水管工要是为了多赚点收入一个阀门拧了一上午，那就太不美好了。
所以，我更倾向于第一种观点。毕竟我也是一个久经考场的学生。是故，以下所有建模过程都基于这个假定：即25元每小时是我们付给电工的工钱，水管工保洁工依此类推。
有人就会说了，这个收费到底是怎么回事，问老师一下不就清楚了。这就是我一直想说的另一个问题：为什么学生不愿意和老师交流。但这与建模毫无关系，所以我会在我其他的杂文里探讨这个问题，于此不做过多阐述，还是说建模的事。
排除了这个歧义项的干扰，这个问题还是有很大的解释空间的。诚然，小小的收费二字没有影响问题本身，这依然是一个开放式的问题，允许我们设定各种各样的环境，来解出各种不同的答案。
那么首先最容易想到的情况，一定是三个工种各自招人，每个时段的工作人数都必须大于等于统计需求人数，也就是什么都不加。于是不难得出数学模型如下，以电工为例：
依据表格将全天24小时划分成十二个时段，每两小时一段。设每个偶数整点时刻开始工作的人数分别为X1，X2，X3…X12，目标值F= X1+X2+X3+…+X12，求其最小值。
则有线性方程组：
F= X1+X2+X3+…+X12
X1+X10+X11+X12>1
X1+X2+X11+X12>0
X1+X2+X3+X12>0
X1+X2+X3+X4>6
.
.
.
X9+X10+X11+X12>0
这是一个典型的线性规划问题（话说这方程组好大…）。幸好现代的计算机技术可以帮助我们方便快捷地求解此类问题，不然手动求解这个方程组的情形真的是不敢想象。似乎问题到这里已经被解决的差不多了。
可是有一个严重的问题是：我根本不会用matlab……后来，在花掉了n个积攒多年的百度文库财富值之后，终于学会了matlab中基本线性规划问题的求解方法：即应用matlab中的linprog函数。
由于linprog函数只能求解约束条件为balabala小于等于某定值的方程，所以将各个约束条件进行了变形处理，最终得到以下的指令：
Matlab中的指令如下：
F=[1;1;1;1;1;1;1;1;1;1;1;1];
a=[-1 0 0 0 0 0 0 0 0 -1 -1 -1;
-1 -1 0 0 0 0 0 0 0 0 -1 -1;
-1 -1 -1 0 0 0 0 0 0 0 0 -1;
-1 -1 -1 -1 0 0 0 0 0 0 0 0;
0 -1 -1 -1 -1 0 0 0 0 0 0 0;
0 0 -1 -1 -1 -1 0 0 0 0 0 0;
0 0 0 -1 -1 -1 -1 0 0 0 0 0;
0 0 0 0 -1 -1 -1 -1 0 0 0 0;
0 0 0 0 0 -1 -1 -1 -1 0 0 0;
0 0 0 0 0 0 -1 -1 -1 -1 0 0;
0 0 0 0 0 0 0 -1 -1 -1 -1 0;
0 0 0 0 0 0 0 0 -1 -1 -1 -1];
b=[-1;0;0;-6;-8;-9;-4;-8;-4;-12;-5;-3];
vbl=[0;0;0;0;0;0;0;0;0;0;0;0];
[x,fval]=linprog(F,a,b,[],[],vbl)
运行结果如下：
Optimization terminated.
x =
0.0000
0.0000
3.4973
3.2640
1.7095
0.5292
2.9713
4.2375
1.5250
3.2662
0.0000
0.0000
fval =
21.0000
可是作为一个实际问题，尤其是这种涉及到人数的实际问题的时候，是不允许非整数解的存在的，毕竟我们不能叫半个人去工作，这样太不人道，也不好实现。况且0.6个人加上0.4个人也再不能等于一个完整的人了，这个拆分过程是不可逆的。
所以我对于机器解出的数据进行了一个最基本的整理，即四舍五入：
X= 当前工作人数所需工作人数剩余工时
0 3 1 2
0 0 0 0
3 3 0 3
3 6 6 0
2 8 8 0
1 9 9 0
3 9
4 5
4 10 8 2
2 10 4 6
3 12 12 0
0 9 5 4
0 5 3 2
fval=
21
以上解决方案满足需求条件。
水管工与保洁工运算过程类似。建模过程不再粘贴，凑字数什么的最讨厌了。
可是我们不难发现，机器明显不够智能的地方。具体体现在四点到六点上：明明没有人需要电工却叫人家大早上四点来上班，呆上两个小时再工作。如果是我的话，我一定会把老板骂个满头大包，就算你给我工钱也不能这么欺负人。
更严重的问题在于工时的浪费。为了满足十点到十二点，十八点到二十点两个略显变态的时段，造成了大量的工时浪费：工人在这两个时间段干完工作之后，剩下的时间会闲下来喝茶看报纸。这样无形中造成了人员的冗余。
浪费是可耻的。尤其是在现在这种用工荒的大环境下，对于劳动力的闲置何止是可耻，简直应该说是犯罪。而我们又不得不满足这些上帝客户们的需求。
因此，为了支持建设节约集约型社会，我们必须要改变问题的背景设定和先决条件。3.新的背景与设定
1.作为一个贪心的老板的话，我一定会考虑招聘既能当电工又能当水管工还能兼职保洁的工人。这样的话请一个人再怎么说也一定比请三个人便宜，毕竟他只吃一份盒饭，只要养活一个家庭。但是，暂且不论有没有这样一专多能的人才技工，工作时间的冲突和连续工作带来的疲劳也成了这种兼职的巨大障碍。所以，虽然很贪心，我还是放弃了这种又想马儿跑，又想马儿少吃草的天真想法。
2.如果是作为一个为了降低成本可以无所不用其极的提供服务的一方的话，首先想到的是：急什么急，有问题人手不够就让他们等一会，得了呗。
对此我实在是不敢苟同。
且不论人们对于脏乱差环境的容忍程度有多强，保洁是不是一种对于服务速度要求特高的服务项目；正常住户一般最忍不了的两件事就是停电停水或者漏电漏水（物理老师说电和水性质相似，呜呼诚不我欺）。
所以，余以为，抢险维修服务一类的工种，性质和保镖类似，失误一次就可以辞职回家了。任谁也不能容忍家里的水管如喷泉般肆虐。是故这两种问题的解决必须要及时，即不能等待。
3.排除了上面这两种可能性之后，我们似乎已经无计可施了。但是，如果把思路逆转过来的话，是不是就会好很多——我可以改变工人的工作方式，让一部分人跳着工作，以零代整，削减高峰时段的用人数避免浪费，再其他时段浪费出来的工时的填补高峰时段的空缺。这样就减少了工时的浪费。
中国的廉价劳动力们没有那么大的大爷脾气，非八小时连续不干；他们要的也不多，有的只需求温饱即可。况且题干中说的只是“工作采用计时制，每人工作满8小时后可以下班，如张三在6点上班，可在下午2点下班。”其中“可以”二字，最其妙者——又没说一定要满八小时才能下班，不满八小时按八小时计多不退少要补。
但是如果把所有工人的工作时间都拆成零零碎碎的话，似乎有点太无赖了，那就不要规划了。这像是钻了题目表述的空子。
那么我们不妨再逆转一下思路：每个工种选出一到数个队长/模范/红旗手/小标兵/灵活机动岗，多付三分之一的工钱，然后全天值班待命，哪里需要哪里搬。这就是我的第二种建模方案，它真真切切地减小了用工高峰时段的需求值。
4.新的建模
根据初步估量，暂拟订设立三个值班岗。此三人的八个小时分成四部分，分摊在几个高峰值上。将八点到十点，十点到十二点，十四点到十六点，十八点到二十点，四个时段的需求人数分别减去3，由活动岗代替。
Matlab 指令如下：
f=[1;1;1;1;1;1;1;1;1;1;1;1];
a=[-1 0 0 0 0 0 0 0 0 -1 -1 -1;
-1 -1 0 0 0 0 0 0 0 0 -1 -1;
-1 -1 -1 0 0 0 0 0 0 0 0 -1;
-1 -1 -1 -1 0 0 0 0 0 0 0 0;
0 -1 -1 -1 -1 0 0 0 0 0 0 0;
0 0 -1 -1 -1 -1 0 0 0 0 0 0;
0 0 0 -1 -1 -1 -1 0 0 0 0 0;
0 0 0 0 -1 -1 -1 -1 0 0 0 0;
0 0 0 0 0 -1 -1 -1 -1 0 0 0;
0 0 0 0 0 0 -1 -1 -1 -1 0 0;
0 0 0 0 0 0 0 -1 -1 -1 -1 0;
0 0 0 0 0 0 0 0 -1 -1 -1 -1];
b=[-1;0;0;-6;-5;-6;-4;-5;-4;-9;-5;-3];
vbl=[0;0;0;0;0;0;0;0;0;0;0;0];
[x,fval]=linprog(f,a,b,[],[],vbl)
运行结果如下：
x =
0.0000
0.0000
2.5608
3.4392
0.0000
0.0000
2.6816
2.8084
1.1153
2.3946
0.0000
0.0000
fval =
15.0000
经整理，实际人数如下：
X= 当前工作人数所需工作人数剩余工时
0 3 1 2
0 0 0 0
0 0 0 0
6 6 6 0
0+3 9 8 1
0+3 9 9 0
3 9
4 5
3+3 9 8 1
1 7 4 3
3+3 13 12 1
0 7 5 2
0 4 3 1
依然满足条件，且省下了21-15-3*4/3=2，两个人的工钱。
水管工和保洁工运算结果类似，不再粘贴，将在招聘报告中有所体现。
5.建模之后的思考
余以为，上表只是根据大量数据（或者不是足够大量的数据）得出的需求统计表，并不能说明在相应的时间就一定会出现表中所给的工作人员需求。上面这种建模，也只是我在理想的环境下做出的构想。作为运筹学作业的一部分，勉强可以——它也只能作为一个学院派的学生作业存在。而实际情况远远比这复杂得多。正如我在 3.新的背景与设定一部分中提到的第二小点中说的那样：“在这个用工荒的大环境下...”（感谢S君激活了这个思路，他提醒我从这里谈起）
是的，就算我算出了最优值，依然可能招不到人，甚至可能一个人都招不到。
由于农业的机械化，大量被闲置的劳动力从广大的农村走了出来。可是这些被锄櫌棘矜训练出的坚韧躯体并没有被赋予和身体素质相应的劳动技能。他们更多的被建筑工地或者外资血汗工厂所消化，在消耗同等体力的情况下，他们的收入是最少的。
与此同时，我国每年还有一个相当庞大的就业群体，他们的名字叫大学毕业生。这群所谓的知识分子是不屑于做这些技术工种的——如果去当电工水管工，蓝翔是比大学更好的选择。更何况，四年的大学生活，已经让他们之中很大的一部分人失去了这些真正动手操作的能力。这从这次报告便可见一斑：好多同学的matlab是经过我指点的，所以可以看到很多人的矩阵里系数都是负的，而不会想到在整个矩阵的前面加上一个负号。我是因为线性代数没学好，才这么做的，这是最笨的方法，可是他们都照着学了。我现在知道可以整个加负号，却懒得改了，所以我比他们也强不了多少。
接着说用工荒。用工荒并不是所有行业都招不到人。那些薪酬待遇最低端和最高端的行业永远都不会缺人。恰恰就是这些所谓高不成低不就的行业没有人愿意做。
为什么没人愿意做？说到底是教育问题和社会意识问题。
或许是因为我们的国家太大了，远远超过了柏拉图《理想国》中理想国家的国土和人口的上限。这直接导致了地区发展差异和城乡发展差异，而差异正是矛盾的根源所在。我朝开国数十年以来，并没有给广大的农村人民带来足够优质的教育。以至于广大的农民兄弟依然
在社会的底层挣扎（虽然说我们在封建时代有所谓“士农工商”的排序，但农民还是实质上的底层基础，默默地用劳动维系着社会机器的运转）。薄弱的劳动技能并不能支持他们享受工业革命和科技革命为他们带来的就业机遇。
而少数从农村走出来的接受了高等教育的所谓凤凰们，又和他们的同学们一道走向了另一个怪圈：大学之后找工作难。
为什么大学生不愿意做这些技术工种？因为他们接受教育的前期投入太大了，成本太高了，技术工种的收获与他们的预期落差太大，收不回成本。回想一下自己念书的过程，真的就是真金白银铺路，才走到了这一步。这就像买股票一样，从一开始就放量买进，结果股票一路下跌，却也舍不得割肉抛售。结果股价越来越低，这种情况，俗称叫套牢。早走的人认清了现实，所以在半路找了个活计，安家立业；认不清实际而又不适合高等教育的人就一路到底的读下去。我不否认有的人真的在大学里做出了推进社会发展的科研结果，但是大多数人并没有做到。结果大量金钱和青春的投入，换来的只是在象牙塔里躲上几年，不必接受社会压力的吹打；最后还放不下身段，嗟叹“时运不齐，命途多舛”，为了考公务员或者进国企搞得头尖如矛，突出了一个挤劲和钻劲。
但是为什么上大学是一件性价比如此之低的事情，却又成为了当今中国家庭教育的主流选择呢？余以为，这就是社会权力攫取途径的问题。上大学曾经是快速获得社会地位的途径，但随着高校的扩招，大学已然不是过去的大学了，但依旧为大众所迷信。
时常能想起六朝时期，对于国家公务人员的选取时采取“九品官人法”，官员队伍完全由士族大家把持，社会结构板结固化到无以复加的地步，最终导致了社会的动荡，并直接催生出了隋代的科举制度，即通过学习特定的内容参加考试，来转变自己的社会地位。
有人说，隋代的科举制度真是一个社会的大进步，敲碎了士族的垄断；但是他们没有看到的是，过去的特权阶级依然是特权阶级，参与科举的各位依然是在一群泥腿子里面摸爬滚打。所谓“学而优则仕”，实在是贻害万年。
这就是统治阶级的高明之处，通过分化被统治阶级内部，引起他们之间的竞争，从而维持一个被统治阶级的动态稳定，使他们无力动摇自己的特权。而被统治的人们从来没想过有朝一日可以不被统治，他们只是想，只要比身边的人强就可以。这让我想起了那个打劫的故事：劫匪打劫，让人们交钱。第一个人交一百，第二个人交二百，以此类推。大家纷纷排队，大家争先恐后的抢着排队，却忘了反抗。虽然有点不太恰当，但还是有点相似：念了书受了教育的就可以比别人少受点欺负，少吃点亏；却忘了为什么会被人欺负。
所以，人们形成了一种观念：种地没出息，上大学有出息；当电工没出息；上大学有出息；上蓝翔没出息，上大学有出息。没技术的干不了，有技术的为了出息不愿意干，于是，用工就荒了。
但是我们忽略了一点，本来应该是无差别的人类劳动，价值相等，为什么就在社会地位和薪资待遇上产生了差异呢？这种差异究竟是谁制定的呢？
是特权阶级？是固有观念？如果是固有观念的话，这种观念又从何而来？
杨老师您觉得呢？
运筹学试题及答案
运筹学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.要求不超过第一目标值、恰好完成第二目标值,目标函数就是
运筹学大作业
大连科技学院运筹学(Z)大作业LINGO软件在函数最大值中的运用 学院名称 专业班级 学生组号 学生姓名 指导教师 二〇一八年五月
实验LINGO软件在函数最大值中的运用 大作业目的 掌握LINGO软件求解函数最大值的基本步骤，了解LINGO软件解决函数最大值的基本原理，熟悉常用的函数最大值计算代码，理解函数最大值的迭代关系。 仪器、设备或软件 电脑，LINGO软件 大作业内容 1．LINGO软件求解函数最大值的基本原理； 2．编写并调试LINGO软件求解函数最大值的计算代码； 实施步骤 1．使用LINGO计算并求解函数最大值问题； 2．写出实验报告，并浅谈学习心得体会(选址问题的基本求解思路与方法及求解过程中出现的问题及解决方法)。 实施过程 有一艘货轮，分为前、中、后三个舱位，它们的容积与允许载重量如下表所示。现有三种商品待运，已知有关数据列于下表中。又为了航运安全，要求前、中、后舱在实际载重量上大体保持各舱最大允许载重量的比例关系。具体要求前、后舱分别与中舱之间的载重量比例偏差不超过15%，前、后舱之间不超过10%。问货轮应装载A、B、C各多少件，运费收入为最大？试建立这个问题的线性规 首先分析问题，建立数学模型： 确定决策变量 假设i=1,2,3分别代表商品A、B、C，8用j=1,2,3分别代表前、中、后舱，设决策变量x ij为装于j舱位的第i种商品的数量（件）。 确定目标函数
商品A 的件数为： 商品B 的件数为： 商品A 的件数为： 为使运费最高，目标函数为： 确定约束条件 前、中、后舱位载重限制为： 前、中、后舱位体积限制为： A 、 B 、 C 三种商品数量的限制条件： 各舱最大允许载重量的比例关系构成的约束条件： 且决策变量要求非负，即x ij ≥0,i=1,2,3；j=1,2,3。 综上所述，此问题的线性规划数学模型为： 111213x x x ++212223x x x ++313233x x x ++()()()111213212223313233 1000700600Max Z x x x x x x x x x =++++++++112131122232132333865200086530008651500 x x x x x x x x x ++≤++≤++≤112131122232132333105740001057540010571500 x x x x x x x x x ++≤++≤++≤1112132122233132336001000800 x x x x x x x x x ++≤++≤++≤1121311222321323331222321121311323338x 6x 5x 2 2(10.15)(1+0.15)38x 6x 5x 3 8x 6x 5x 11(10.15)(1+0.15)28x 6x 5x 2 8x 6x 5x 4 4(10.10)(1+0.10)38x 6x 5x 3++-≤≤++++-≤≤++++-≤≤++()()() 111213212223313233112131122232132333112131122232132333 1000700600865200086530008651500105740001057540010571500 Max Z 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 x x =++++++++++≤++≤++≤++≤++≤++≤
运筹学试题及答案汇总
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 单
运筹学试题及答案4套
《运筹学》试卷一 一、（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
运筹学第四次作业排队论问题.doc
一、汽车维修站问题 某汽车维修站只有一名修理工，一天8h 平均修理10辆汽车。已知维修时间服从负指数分布，汽车的到来服从泊松流，平均每小时有1辆汽车到达维修站。假如一位司机愿意在维修站等候，一旦汽车修复就立即开走，问司机平均需要等待多长时间。如果假设每小时有1.2辆汽车去修理，试问该维修工每天的空闲时间有多少？这对维修站里的汽车数及修理后向顾客交货时间又有怎样的影响？结合以上所求得的数据，分析汽车维修站的服务质量水平。 解：该问题是一个标准的M/M/1/2模型，即汽车司机相继到达间隔时间的分布满足负指数分布，维修工服务时间分布满足负指数分布，服务台数为c=1，系统容量限制为N=2。 (1)已知汽车的到来服从泊松流，平均到达率为=1/h λ，维修时间服从负指数分布，平均每辆汽车接受服务的时间为T=0.8h,单位时间服务车辆的数量为 1.25μ=。则根据该模型运行指标的计算公式可得出： ①系统的平均服务强度为/0.8ρλμ==； ②顾客到达后理科就能得到服务的概率，即维修站空闲，没有顾客的概率为 0+1 11N P ρ ρ -= -； ③系统的队长为1 1 (1)11N s N N L ρ ρρρ +++=---; ④系统的排队长0(1)q S L L P =--; ⑤系统的有效到达率为0(1)e P λμ=-； ⑥顾客逗留时间为0(1) s s s e L L W P λμ= = -； ⑦系统满员的概率，即顾客被拒绝的概率为1 1·1N N N P ρ ρρ +-=-； 利用LINGO 软件来求解，记有关参数1c =，系统最大容量为N=2，顾客平均到达率为1L λ==，平均每个顾客的服务时间为1 0.8T μ ==。则相应程序如 下： MODEL: sets:
运筹学试题及答案.
运筹学试题及答案 一、填空题(本大题共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．若原问题存在可行解，其对偶问题必存在可行解
运筹学大作业 哈工大
课程名称：对偶单纯形法 一、教学目标 在对偶单纯形法的学习过程中，理解和掌握对偶问题；综合运用线性规划和对偶原理知识对对偶单纯形法与单纯形法进行对比分析，了解单纯形法和对偶单纯形法的相同点和不同点，总结出各自的适用范围；掌握对偶单纯形法的求解过程；并能运用对偶单纯形法独立解决一些运筹学问题。 二、教学内容 1) 对偶单纯形法的思想来源(5min) 2) 对偶单纯形法原理(5min) 3) 总结对偶单纯形法的优点及适用情况(5min) 4) 对偶单纯形法的求解过程(10min) 5) 对偶单纯形法例题(15min) 6) 对比分析单纯形法和对偶单纯形法(10min) 三、教学进程： 1）讲述对偶单纯形法思想的来源： 1954年美国数学家C.莱姆基提出对偶单纯形法（Dual Simplex Method ）。单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解，直到检验数满足最优性条件为止。对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解。在迭代过程中始终保持基解的对偶可行性，而使不可行性逐步消失。因此在保持对偶可行性的前提下，一当基解成为可行解时，便也就是最优解。 2）讲述对偶单纯形法的原理 A.对偶问题的基本性质 依照书第58页，我们先介绍一下对偶问题的六个基本性质： 性质一：弱对偶性 性质二：最优性。如果 x j （j=1...n)原问题的可行解，y j 是其对偶问题可 行解，且有 ∑=n j j j x c 1 =∑=m i i i y b 1 ，则x j 是原问题的最优解，y j 是其对偶问题的最
优解。 性质三：无界性。如果原问题（对偶问题）具有无界解，则其对偶问题（原问题）无可行解。 性质四：强对偶性。如果原问题有最优解，则其对偶问题也一定有最优解。 性质五：互补松弛型。在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。 性质六：线性规划的原问题及其对偶问题之间存在一对互补的基解，其中原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量；这些互相对应的变量如果在一个问题的解中是基变量，则在另一问题的解中是非基变量；将这对互补的基解分别代入原问题和对偶问题的目标函数有z=w. B.对偶单纯形法（参考书p64页） 设某标准形式的线性规划问题，对偶单纯形表中必须有c j -z j ≤0（j=1...n),但b i (i=1...m)的值不一定为正，当对i=1...m ，都有b i ≥0时，表中原问题和对偶问题均为最优解，否则通过变换一个基变量，找出原问题的一个目标函数值较小的相邻的基解。 3）为什么要引入对偶单纯形法 从理论上说原始单纯形法可以解决一切线性规划问题，然而实际问题中，由于考虑问题的角度不同，变量设置的不同，便产生了原问题及其对偶问题，对偶问题是原问题从另外一个角度考虑的结果。用对偶单纯形法求解线性规划问题时，当约束条件为“≥”时，不必引入人工变量，使计算简化。 例如，有一线性规划问题： min ω =12 y 1 +16y 2 +15 y 3 约束条件 ?? ?? ???≥=≥+≥+0)3,2,1(3522 423121 i y y y y y i
最全的运筹学复习题及答案78213
最全的运筹学复习题及 答案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
运筹学大作业(线性规划问题)
运筹学 结课大作业 姓名：苏同锁 学号：1068132104 学院：数理与生物工程学院 班级：数学2010
实例：有三家物流企业将一批货物分别运送到四个城市。物流公司A，B，C所运送货物量分别为110吨、70吨、100吨四个城市I， Il，III，Ⅳ，需求量分别为60吨、70吨、50吨、70吨。物流公司A往城市I，II，III，Ⅳ每吨的运价分别为l0元、15元、20元、25元；物流公司 B到城市I，II，III，Ⅳ每吨的运价分别为2O元、10元、l5元、15元：物流公司 C 到城市I，II，III，Ⅳ每吨的运价分别为25元、30元、20元、25元。 运输费用数据表 如何确定调运方案，才能使运输总费用最小。 首先，设运输总费用为f，我们要求运输总费用最小，故目标函数为：Minf=10x11+15x12+20x13+25x14+20x21+10x22+15x23+15x24+25x31+ 30x32+20x33+25x34 其中Xij表示从物流公司i调运到城市j物资的数量，minf表示运输费用最少。 考虑约束条件如上表所述的量和销地的需求量要满足运输平衡条件，以及各变量取非负数，于是可得如下约束条件：
x11+x12+x13+x14<=110 x21+x22+x23+x24<=70 x31+x32+x33+x34<=100 x11+x21+x31>=60 x12+x22+x32>=70 x13+x23+x33>=50 x14+x24+x34>=70 Xij≥0(i=1,2,3;j=1,2,3,4) 最后，我们将目标函数和约束条件写在一起，就得到了物资调运问题的数学模型，即线性规划问题： minf=10x11+15x12+20x13+25x14+20x21+10x22+15x23+15x24+25x31+ 30x32+20x33+25x34 x11+x12+x13+x14<=110 x21+x22+x23+x24<=70 x31+x32+x33+x34<=100 x11+x21+x31>=60 x12+x22+x32>=70 x13+x23+x33>=50 x14+x24+x34>=70 Xij≥0(i=1,2,3;j=1,2,3,4)
兰州大学运筹学_运输问题课后习题题解
第七章运输问题 7.1 一个农民承包了6块耕地共300亩，准备播种小麦、玉米、水果和蔬菜四种农产品， 问如何安排种植计划，可得到最大的总收益。 解： 本问题地块总面积：42+56+44+39+60+59=300亩 计划播种总面积：6+88+96+40=300亩 因此这是一个产销平衡的运输问题。可以建立下列的运输模型： 代入产销平衡的运输模板可得如下结果：
种植计划方案 7.2 某客车制造厂根据合同要求从当年开始起连续四年年末交付40辆规格型号相同的 年度 可生产客车数量（辆） 制造成本（万元/辆） 正常上班时间 加班时间 正常上班时间 加班时间 1 20 30 50 55 2 38 24 56 61 3 15 30 60 65 4 42 23 53 58 根据该厂的情况，若制造出来的客车产品当年未能交货，每辆车每积压一年的存储和维护费用为4万元。在签订合同时，该厂已储存了20辆客车，同时又要求四年期未完成合同后还需要储存25辆车备用。问该厂如何安排每年的客车生产量，使得在满足上述各项要求的情况下，总的生产费用加储存维护费用为最少？ 解：这是一个生产储存问题，可以化为运输问题来做。根据已知条件，我们可以做以下 地块1 地块2 地块3 地块4 地块5 地块6 计划播种面积（亩） 小麦 6 39 31 76 玉米 29 59 88 水果 2 56 38 96 蔬菜 40 40 地块面积（亩） 42 56 44 39 60 59 300 300
分析，建立运输模型。 1、由于上年末库存20辆车，这些产品在这四年中只计仓储费不计生产费用，所以我们记为0年，第一行； 2、在建立的运输表中，相应单元格填入当年交付产品的所有成本（包括生产和存储成本）； 3、年份从1到4表示当年的正常生产，而1’到4’表示当年加班生产的情况； 4、由于期末（4年底）要有25辆车的库存，即4年末的需求量是40+25=65辆； 5、在表中没有具体成本的单元格中，表示没有生产也没有交货，为了保证这个真实情况的描述，在这些格中填M，使安排的生产量为0。 6、在计算成本时，当年生产当年交货不加存储成本，但对未交付的产品，第二年要付一个年的存储费4万元，依此类推。 根据上面的分析，可得运价表如下。 年度1 年度2 年度3 年度4 库存生产能力（辆） 0 4 8 12 16 20 20 1 50 54 58 6 2 66 20 1’55 59 63 67 71 30 2 56 60 64 68 38 2’61 65 69 74 24 3 60 6 4 68 15 3’65 69 74 30 4 53 57 42 4’58 62 23 合同需求量（辆）40 40 40 40 25 这是一个产大于销的运输模型，代入求解模型可得： 即：生产安排的方案：
运筹学第五版课后答案,运筹作业
47页1.1b 用图解法找不到满足所有约束条件的公共范围，所以该问题无可行解47页1.1d 无界解
1.2（b） 约束方程的系数矩阵 A= 1 2 3 4 ( ) 2 1 1 2 P1 P2 P3 P4 最优解A=(0 1/2 2 0)T和(0 0 1 1)T 49页13题 设Xij为第i月租j个月的面积 minz=2800x11+2800x21+2800x31+2800x41+4500x12+4500x22+4500x32+6000x13 +6000x23+7300x14 s.t. x11+x12+x13+x14≥15 x12+x13+x14+x21+x22+x23≥10 x13+x14+x22+x23+x31+x32≥20 x14+x23+x32+x41≥12 Xij≥0 用excel求解为：
用LINDO求解： LP OPTIMUM FOUND AT STEP 3 OBJECTIVE FUNCTION VALUE 1) 118400.0 VARIABLE VALUE REDUCED COST Z 0.000000 1.000000 X11 3.000000 0.000000
X21 0.000000 2800.000000 X31 8.000000 0.000000 X41 0.000000 1100.000000 X12 0.000000 1700.000000 X22 0.000000 1700.000000 X32 0.000000 0.000000 X13 0.000000 400.000000 X23 0.000000 1500.000000 X14 12.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 -2800.000000 3) 2.000000 0.000000 4) 0.000000 -2800.000000 5) 0.000000 -1700.000000 NO. ITERATIONS= 3 答若使所费租借费用最小，需第一个月租一个月租期300平方米，租四个月租期1200平方米，第三个月租一个月租期800平方米，
最全的运筹学复习题及答案
四、把下列线性规划问题化成标准形式： 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 —10b-1f g X32C O11／5 X l a d e01 (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
运筹学试题及答案.doc
运筹学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．要求不超过第一目标值、恰好完成第二目标值，目标函数是 A ． B ． C．
运筹学 大作业
运筹学 请在以下五组题目中任选一组作答，满分100分。 第一组： 计算题（每小题25分，共100分） 1.福安商场是个中型的百货商场，它对售货人员的需求经过统计分析如下表所示，为了保证售货人员充分休息，售货人员每周工作五天，休息两天，并要求休息的两天是连续的，问该如何安排售货人员的休息，既满足了工作需要，又使配备的售货人员的人数最少，请列出此问题的数学模型。 2.A、B两人分别有10分(1角)、5分、1分的硬币各一枚，双方都不知道的情况下各出一枚，规定和为偶数，A赢得8所出硬币，和为奇数，8赢得A所出硬币，试据此列出二人零和对策模型，并说明此游戏对双方是否公平。 3、某厂生产甲、乙两种产品，这两种产品均需在A、B、C三种不同的设备上加工，每种产品在不同设备上加工所需的工时不同，这些产品销售后所能获得利润以及这三种加工设备 问：该厂应如何组织生产，即生产多少甲、乙产品使得该厂的总利润为最大？
4、用图解法求解 max z = 6x1+4x2 s.t. 第二组： 计算题（每小题25分，共100分） 1、用图解法求解 min z =－3x1+x2 s.t. ????? ????≥≤+≥+≤≤0 8 2125234212 12121 x x x x x x x x ， 2、用单纯形法求解 max z =70x1+30x2 s.t. ?????? ?≥≤+≤+≤+072039450555409321212121x x x x x x x x ， 3、用单纯形法求解 max z =7x1+12x2 s.t. ⑵ ⑶ ⑷ ⑸、⑹ 1212212 210870x x x x x x x +≤??+≤?? ≤? ?≥?， ⑴ ⑵ ⑶ ⑷ ⑸ ⑹、⑺ ⑴
最新--运筹学期末考试试题及答案
楚大 2012---2013上学期 经济信息管理及计算机应用系 《运筹学》期末考试试题及答案 班级： 学号 一、单项选择题： 1、在下面的数学模型中，属于线性规划模型的为（ A ）。 ?????≥-≥-+=0Y ,X 1Y X 2. t .s Y X 3S min .B ?????≥≤+=0Y ,X 3XY .t .s Y X 4S max .A ?????≥≤-+=0Y ,X 2Y X .t .s Y X S max .C 22?????≥≥+=0 Y ,X 3Y X .t .s XY 2S min .D 2、线性规划问题若有最优解，则一定可以在可行域的 （ A ）上 达到。 A ．顶点 B ．内点 C ．外点 D ．几何点 3、在线性规划模型中，没有非负约束的变量称为 （ C ） A ．多余变量 B ．松弛变量 C.自由变量 D ．人工变量 4、若线性规划问题的最优解同时在可行解域的两个顶点处达到，那 么该线性规划问题最优解为（ C ）。 A.两个 B.零个 C.无穷多个 D.有限多个 5、线性规划具有唯一最优解是指（ B ） A ．最优表中存在常数项为零 B ．最优表中非基变量检验数全部非零 C ．最优表中存在非基变量的检验数为零 D ．可行解集合有界 6、设线性规划的约束条件为
?????≥=++=++0,,422341 421321x x x x x x x x 则基本可行解为（ C ）。 A ．(0, 0, 4, 3) B ． (3, 4, 0, 0) C ．(2, 0, 1, 0) D ． (3, 0, 4, 0) 7、若运输问题已求得最优解，此时所求出的检验数一定是全部 （ D ） A 、小于或等于零 B ．大于零 C ．小于零 D ．大 于或等于零 8、对于m 个发点、n 个收点的运输问题，叙述错误的是( D ) A ．该问题的系数矩阵有m ×n 列 B ．该问题的系数矩阵有m+n 行 C ．该问题的系数矩阵的秩必为m+n-1 D ．该问题的最优解 必唯一 9、关于动态规划问题的下列命题中错误的是（ A ） A 、动态规划分阶段顺序不同，则结果不同 B 、状态对决策有影响 C 、动态规划中，定义状态时应保证在各个阶段中所做决策的相对独 立性 D 、动态规划的求解过程都可以用列表形式实现 10、若P 为网络G 的一条流量增广链，则P 中所有正向弧都为G 的 （ D ）
运筹学排班问题大作业
运筹学排班问题地建模和程序设计报告 级工业工程一班 杨添淇 前言 本报告共分为五个部分： .排班问题地提出 .建模地心路历程 .新地背景与设定 .新地建模 .建模后地思考 其中，第二部分与第五部分最为用力，集中体现了作者想要表达地观点.其实这两部分应该写在分析报告里吧？好像搞反了…个人收集整理勿做商业用途 是为序. 排班问题地提出 某小区组建维修保洁服务，现需要招聘维修保洁人员若干轮班工作.其中包括电工，水管工，和保洁员.工作采用计时制，每人工作满小时后可以下班，如张三在点上班，可在下午点下班.根据统计，小区需求人数如下表：个人收集整理勿做商业用途 时间电工水管工保洁 点点 点点 点点 点点 点点 点点 点点 点点 点点 点点 点点 点点 维修保洁服务地收费标准是：电工元小时，水工元小时，保洁元小时.试制定招聘计划和工人地排班表（即：招聘工人地数量和每个工人地上班时间）.个人收集整理勿做商业用途 建模地心路历程 余以为，老师要我们交报告，绝不是走个形式，也不仅仅是要看我们写出地冷冰冰地代码，求解问题地能力，更是要看我们思维地走向：从哪里来，到哪里去，最终形成一条清晰地路径.确实，看这个路径地形成过程是一件非常有趣地事，记录这个过程亦然.是故，我采用了完全写实地笔法，彻头彻尾地记录下了自己地真实想法，怎么想地怎么写地，想怎么写就怎么写.所以，报告地这个部分叫做：建模地心路历程（多么温润而厚重地小标题啊）.个人收集整理勿做商业用途 问题地最后提到了收费问题，旋即戛然而止，留给了解题人无限地遐想空间.我想老师地本意，是好地.但读完题后，我地第一个问题便出在这最后一句上：“收费标准”中地“收费”二字作何解.个人收集整理勿做商业用途
运筹学课后习题答案
第一章 线性规划 1、 由图可得：最优解为 2、用图解法求解线性规划： Min z=2x 1+x 2 ????? ??≥≤≤≥+≤+-01058 2442 12121x x x x x x 解： 由图可得：最优解x=1.6,y=6.4
Max z=5x 1+6x 2 ? ?? ??≥≤+-≥-0 ,23222212 121x x x x x x 解： 由图可得：最优解Max z=5x 1+6x 2, Max z= +∞
Maxz = 2x 1 +x 2 ????? ? ?≥≤+≤+≤0,5242261552121211x x x x x x x 由图可得：最大值?????==+35121x x x ， 所以?????==2 3 21x x max Z = 8.
12 12125.max 2328416412 0,1,2maxZ .j Z x x x x x x x j =+?+≤? ≤?? ≤??≥=?如图所示，在（4，2）这一点达到最大值为2 6将线性规划模型化成标准形式： Min z=x 1-2x 2+3x 3 ????? ??≥≥-=++-≥+-≤++无约束 321 321321321,0,05232 7x x x x x x x x x x x x 解：令Z ’=-Z,引进松弛变量x 4≥0，引入剩余变量x 5≥0，并令x 3=x 3’-x 3’’,其中 x 3’≥0,x 3’’≥0 Max z ’=-x 1+2x 2-3x 3’+3x 3’’ ????? ? ?≥≥≥≥≥≥-=++-=--+-=+-++0 ,0,0'',0',0,05 232 '''7'''543321 3215332143321x x x x x x x x x x x x x x x x x x x
运筹学习题答案运筹学答案
《运筹学》习题答案 一、单选题 1.用动态规划求解工程线路问题时，什么样的网络问题可以转化为定步数问题求解（）B A.任意网络 B.无回路有向网络 C.混合网络 D.容量网络 2.通过什么方法或者技巧可以把工程线路问题转化为动态规划问题？（）B A.非线性问题的线性化技巧 B.静态问题的动态处理 C.引入虚拟产地或者销地 D.引入人工变量 3.静态问题的动态处理最常用的方法是？B A.非线性问题的线性化技巧 B.人为的引入时段 C.引入虚拟产地或者销地 D.网络建模 4.串联系统可靠性问题动态规划模型的特点是（）D A.状态变量的选取 B.决策变量的选取 C.有虚拟产地或者销地 D.目标函数取乘积形式 5.在网络计划技术中，进行时间与成本优化时，一般地说，随着施工周期的缩短，直接费用是( )。C A.降低的 B.不增不减的 C.增加的 D.难以估计的 6.最小枝权树算法是从已接接点出发，把( )的接点连接上C A.最远 B.较远 C.最近 D.较近 7.在箭线式网络固中，( )的说法是错误的。D A.结点不占用时间也不消耗资源 B.结点表示前接活动的完成和后续活动的开始 C.箭线代表活动 D.结点的最早出现时间和最迟出现时间是同一个时间 8.如图所示，在锅炉房与各车间之间铺设暖气管最小的管道总长度是( )。C A.1200 B.1400 C.1300 D.1700 9.在求最短路线问题中，已知起点到A，B，C三相邻结点的距离分别为15km，20km,25km，则（）。D A.最短路线—定通过A点 B.最短路线一定通过B点 C.最短路线一定通过C点 D.不能判断最短路线通过哪一点 10.在一棵树中，如果在某两点间加上条边，则图一定( )A A.存在一个圈 B.存在两个圈 C.存在三个圈 D.不含圈 11.网络图关键线路的长度( )工程完工期。C A.大于 B.小于 C.等于 D.不一定等于
运筹学习题及答案
运筹学 一、单选题 1. μ是关于可行流f的一条增广链，则在μ上有（D） A.对一切 B.对一切 C.对一切 D.对一切 2.不满足匈牙利法的条件是(D) A.问题求最小值 B.效率矩阵的元素非负 C.人数与工作数相等 D.问题求最大值 3.从甲市到乙市之间有—公路网络，为了尽快从甲市驱车赶到乙市，应借用（）C A.树的逐步生成法 B.求最小技校树法 C.求最短路线法 D.求最大流量法 4.串联系统可靠性问题动态规划模型的特点是（）D A.状态变量的选取 B.决策变量的选取 C.有虚拟产地或者销地 D.目标函数取乘积形式 5.当基变量x i的系数c i波动时，最优表中引起变化的有(B) A.最优基B B.所有非基变量的检验数 C.第i 列的系数 D.基变量X B 6.当非基变量x j的系数c j波动时，最优表中引起变化的有(C) A.单纯形乘子 B.目标值 C.非基变量的检验数 D. 常数项 7.当线性规划的可行解集合非空时一定(D) A.包含点X=(0,0,···,0) B.有界 C.无界 D.是凸集 8.对偶单纯形法的最小比值规划则是为了保证(B) A.使原问题保持可行 B.使对偶问题保持可行 C.逐步消除原问题不可行性 D.逐步消除对偶问题不可行性 9.对偶单纯形法迭代中的主元素一定是负元素（）A A.正确 B.错误 C.不一定 D.无法判断 10.对偶单纯形法求解极大化线性规划时，如果不按照最小化比值的方法选取什么变量则在下一个解中至少有一个变量为正（）B A.换出变量 B.换入变量 C.非基变量 D.基变量 11.对LP问题的标准型：max,,0 Z CX AX b X ==≥，利用单纯形表求解时，每做一次换基迭代，都能保证它相应的目标函数值Z必为（）B A.增大 B.不减少 C.减少 D.不增大 12. 单纯形法迭代中的主元素一定是正元素( ）A A.正确 B.错误 C.不一定 D.无法判断 13.单纯形法所求线性规划的最优解（）是可行域的顶点。A A.一定 B.一定不 C.不一定 D.无法判断 14.单纯形法所求线性规划的最优解（）是基本最优解。A A.一定 B.一定不 C.不一定 D.无法判断 15.动态规划最优化原理的含义是：最优策略中的任意一个K-子策略也是最优的（）A A.正确 B.错误 C.不一定 D.无法判断 16.动态规划的核心是什么原理的应用（）A A.最优化原理 B.逆向求解原理 C.最大流最小割原理 D.网络分析原理 17.动态规划求解的一般方法是什么？（）C A.图解法 B.单纯形法 C.逆序求解 D.标号法 18.工序（i,j）的最乐观时间、最可能时间、最保守时间分别是5、8和11，则工序（i,j）的期望时间是（C） A. 6 B. 7 C. 8 D. 9