高项运筹学
基本介�
运�学是一���的学科,博大精深。在信息系��目管理�考�中通常
会考察3分左右,且�算量很大,但是只要把一些常�的思想、常�的解�方
法掌握了,再把�年的真�搞清楚,基本就OK了。
知�点分布
�划�:�性�划、非�性�划、整数�划、目��划
��与网�
存��
排��
决策�
常��型和解�思路
�性�划
�性�划主要用于解决生活、生�中的�源利用、人力�配、
生�安排等��,它是一个重要的数学模型。��的�性�划指的是
目�函数含两个自�量的�性�划,其最�解可以用数形�合方法求
出。用数学�言来�,就是在一��束条件下�找目�函数的极��
�。
常��型和解�思路
�策�(博弈)
按决策者的主��度不同分�5中准�:悲�主�、��主�、折中主�、等
可能性和后悔�准�五�。
��主�准�:也称�最大最大准�(MAXMAX准�),其决策的原�是
“大中取大”;
悲�主�准�:也称�最大最小准�(MAXMIN准�),其决策的的原�
是“小中取大;
折中主�准�,也称�赫�威斯准�,折中决策方法的特点是事物既不��
冒�,也不悲�保守,而是折中平衡一下;
等可能准�,也称�拉普拉斯准�;
后悔�准�,即�憾�也称���奇准�、最小机会�失准�。在制定决策
后,如果不符合理想情况,必然有后悔的感�。
常��型和解�思路
随机决策��
是指决策者所面�的各�自然状�是随机出�的一�决策��。随机决策必
�条件:
1、存在着决策者希望达到的明确目�
2、存在着不以决策者的主�意志��移的两�以上的自然状�
3、存在着两个以上的可供��的行�方案
4、不同行�方案在不同自然状�下的益��可以�算出来。
随机决策��可以�一�分���型和非确定型决策��。在��型中,�
然未来自然状�的�生是随机的,但��状��生的概率是已知或可以�先估�的。
在非确定型中,不�未来自然状�的�生�随机的,而且各�自然状��生的概率
也是未知和无法�先估�的。
常��型和解�思路
���量分析的工作程序
���量分析是用��推�方法����量之�的�系做出数
�估�的一�数量分析方法。它首先把��理�表示�可�量的数学
模型即���量模型,然后用��推�方法加工���料,使�个数
学模型数�化。
常��型和解�思路
状��移矩�
状��移矩�是俄国数学家��科夫提出的,他在20世�初�
�,一个系�的某些因素在�移中,第n次�果只受第n-1的�果影
响,即只与当前所�状�有�,而与�去状�无�。在��科夫分析
中,引入状��移�个概念。
所�状�是指客�事物可能出�或存在的状�;状��移是指客
�事物由一�状��移到另一�状�的概率。
常��型和解�思路
�合分析
�合分析是一�用来研究消�者�于�品或服�偏好的技�。
通���技�,我�可以�取有�新�品的各�相�属性在消�者的
��行�中所起到的影响程度,及在各�属性中各�可替�因素的具
体效用函数,从而帮助客�从多�可��的�品性能中做出准确判断。
常��型和解�思路
最小生成�
最小生成�:�于�通的���(�通�)G,其生成�也是
��的。生成�T各�的���和称���的�。�里:TE表示T的
�集,w(u,v)表示�(u、v)的�。�最小的生成��G的最
小生成�。最小生成�可���MST。
常��型和解�思路
决策表(期望��价�)
决策表又称判断表,是一�呈表格状的�形工具,适用于描述
�理判断条件�多,各条件又相互�合、有多�决策方案的情况。精
确而�接描述��的方式,将多个条件与�些条件�足后要�行�作
相��。
常��型和解�思路
决策�
�个决策或事件(即自然状�)都可能引出两个或多个��,
�致不同的�果,把折中决策分支画成�形很像一棵�的枝干,故称
决策�。一般都是自上而下的来生成的。其算法是一�逼近离散函数
�的方法。
常��型和解�思路
��
��(Graph Theory)是数学的一个分支。它以��研究
�象。��中的�是由若干�定的点及�接两点的�所构成的�形,
���形通常用来描述某些事物之�的某�特定�系,用点代表事物,
用�接两点的�表示相�两个事物�具有���系。
�年��解析
�年��解析
所�决策,是指�确定未来某个行�的目�,根据自己的��,在占
有一定信息的基�上,借助于科学的方法和工具,�需要决定的��的各
个因素�行分析、�算和�价,并从两个以上的可行方案中,��一个最
�方案的分析判断�程。
根据决策�局的多少,可以将决策分�确定型决策(�个方案只有一
个�局)和不确定型决策(�个方案有多个�局)。本��属于不确定型
决策��。决策准�包括��准�、悲�准�、后悔�准�等。其中,
Maxmin悲�准�(最大最小准�)是指�于任何行�方案,都��将是
最坏的状��生,即收益�最小的状��生。然后,比�各行�方案�施
后的�果,取具有最大收益�的行�作�最�行�的决策原�。
�年��解析
�年��解析
从�点1到�点6可以同�沿多条路径运�,�的最大流量��是各条路径上最大流
量之和。�条路径上的最大流量由其各段流量的最小�决定。按照��,�次�尽量先找
出具有最大流量的路径,理�上可以�明,�然�找各�路径的�法可以不同,运�方案
也可以有很多�,但�的最大流量�是唯一确定的。
比�直�的解�方法是,�找出一条路径算出流量后,�路径上各段�路上的流量
�扣除已�算�的流量,形成剩余流量。剩余流量�0的�路�将其�除。
�算方法如下:
路径1356的最大流量�10,将13之�的路径断�
路径1256的剩余最大流量�6,将12之�的路径断�
路径146的剩余最大流量�5,将46之�的路径断�
路径14256的剩余最大流量�1,将25之�的路径断�
路径14356的剩余最大流量�1,将43之�的路径断�。至此不存在 从1到6的运
�路径。故而其最大流量是所有可能运�路径上的最大流量之和,即�:
10+6+5+1+1=23
�年��解析
�年��解析
�了�短�工�,�适当安排加工各零件的�序,以�短其�床最后的加工��,
并�短�床最先的加工��。因此�采取如下原�来安排各零件的加工�序:在�定的工
�表中找出最小�,如果它是�床��,��零件�最后加工;如果它是�床��,��
零件�最先加工,除去�零件后,再按此原����行安装。
在表中,最小工��2小�,�是零件C所用的�床加工��,因此零件C��放在
最后加工;除去零件C后,工�表中最小工��4小�,�是零件B所需的�床加工��,
因此零件B�最先加工。再除去B之后,工�表中最小���5小�,是零件D所需的�
床加工��。因此零件D�安排在零件A之后�行加工。此�所得的最�加工方案是:按
B、A、D、C的�序来加工。需要4+8+6+6=24小�。
�年��解析
将部分公路改造成高速公路,使各个城市之�均可通�高速公路通达,至少要
改造��()公里的公路,���公里数最少的改造方案共有()个。
A、1000 B、1300 C、1600 D、2000
A、1 B、2 C、3 D、4
�年��解析
从�目来看,本�要求得到�的最小支撑�(即�取部分�,使其保持�通,又使其��度最
小)
1)任取一点,例如A,将其�入已完成部分,点A与其他各点中的最小距离�AE=200,从
而将AE及点E�入已完成部分。
2)点A、E与其他各点之�的最短距离是AB=AF=300,从而可以将�AB与点B(或�
AF与点F)�入已完成部分。
3)点A、B、E与点C、D、F两个集合之�的最短距离�AF=BF,从而将�AF(或BF)
与点F�入到已完成部分。
4)点A、B、E、F与点C、D两个集合之�的最短距离�FD=200,从而将�FD与点D
�入到已完成部分。
5)点A、B、E、F、D与点C两个集合之�的最短距离�CD=300,从而将点C与�CD
�入已完成部分。
6)所有6个点都已接通,其��AB、AE、AF、FD、CD,��度�
300+200+300+200+300=1300
其中CD在最短��度方案中不可少,而AB、BF、AF中可以任�2条。因此,�共有3个
最短��度的方案。
�年��解析
�年��解析
将6��程作�6个�点画出,然后在两个�程�点之�画��表示它�不可以在同
一天安排考�,那�,�个博士的各��修�之�都�画出��,如�所示,例如,B1
博士�修了A、B、D3��程,�ABD之�都�有��,表示�3��中的任何两�都
不能安排在同一天考�。
从�中可以看出,能�安排在同一天考�的�程有AE、BC、DE、DF。所以AE
排在第一天,BC排在第二天,DF排在第三天。
排除法:
直接�各个��答案�行�探,排除不合理的,确�合理的安排
��答案A不合理,BD排在同一天,B1等考�一天考两�
��答案B不合理,AC排在同一天,B2等考生一天考两�
��答案C不合理,AF排在同一天,B3等考生一天考两�
所以只能�D
�年��解析
A、甲采取高价策略,乙采取低价策略
B、甲采取高价策略,乙采取高价策略
C、甲采取低价策略,乙采取低价策略
D、甲采取高价策略,乙采取高价策略
�年��解析
�是一个�短的博弈��,站在A网站的立�上看,假�B网站采用
高价策略,那�自己采用高价策略得1000万元,采用低价策略得1500万
元,如果B网站采用低价策略,那�自己采用高价策略得200万元,采用
低价策略得700万元,�然也��采用低价策略。
同理,站在B网站的立�上看,也是��,不管A网站采用什�价格
策略,自己都�采用低价策略�好。因此,�个博弈的�果一定是两个网
站都采用低价策略,各得到700万元的利�。
�年��解析
某公司准�将新招聘的4名�售�分配到下属3个�售点甲、乙和丙。各�售点增加若干名�
售�后可增加的月�售�如下表所示:
增加�售�(千元)
根据此表,只要人�分配适当,公司�月最多可以增加�售�()千元
A、43 B、47 C、48 D、49
增加�售�
(千元)
增1人 增2人 增3人 增4人
甲 12 22 30 38
乙 11 20 24 30
丙 13 25 30 36
�年��解析
由于各个点增加同�的人数后增加的�售�不尽相同,且要求使公司�月所增加的�售�最大,
因此分配���先考�增加�售�多的�售点。
方案1:4人集中在一个点。�将4个人分派到�售点甲,公司�月所增加的�售��38千元。
方案2:三个人分配到同一个点,另一个人分配到另一点。即第二列和第四列数据的排列�合。
其中,当3个人分配到甲,另一人分配到丙�,公司�月所增加的�售�最高:43千元
方案3: 两个人分配到一个�售店,另两个人分配到另一个�售点。此�考�第3列数据的排
列�合,共有3�,其中当甲、乙两个�售点各分配2人�,增加的�售�最高:47千元
方案4:2人分配到同一个�售点,其他两个�售点各分配1人,此�所需考�的是第2列、第
3列数据的排列�合。共有3�方案,其中2人分配到丙,甲、乙各分配一人�,�售�增加最多:
48千元。
答案:C
�年��解析
制造某��品需要4道工序,�道工序可�用多�方法。下�列出了指����品各道工序可�用的不同
方法:从�点1�始,����4条�段(表示4道工序所�用的方法),�成一条�路,直到�点12�束。�
条�段上��的数字表示利用相�方法�件�品可�得的利�(元)。企��了�取最大利�,需要找出从�
点1到�点12的一条�路,使其��的各道工序的利�之和达到最大。利用运�方法�算后可知,指��件�
品可以�得最大利�是()元。
A、28 B、31 C、33 D、34
�年��解析
解析:
从��上看,本�就是求�点1到�点12的最�路径,其算法�似于求最短路径的方法,采
用倒推��方法�行推算的解���如下:
1)先找出离�点只有一�的�点9、10、11,分���其到达�点的路径与�度。
2)再找出前往�点9、10、11只有一�的�点5、6、7、8,�其中�个�点,找出其到
�点的最�路径,分�将其路径与�度��出来。得到5-9-12(15),6-11-12(13),7-
11-12(16),8-9-12(19)
3)再找前往�点5、6、7、8只有一�的�点2、3、4,�其中�个�点,找出其到�点的
最�路径。�些�点到�点的最�路径及�度�如下:2、8、9、12(26),3-8-9-12(29),
4-8-9-12(23)
4)最后,找出�点1通��点2、3、4到�点的路径中的最�路径,并��出来,即1-3-8-
9-12(33)
�年��解析
某工程包括A、B、C、D、E、F、G、H八个作�,各个作�的�前作�、所需��和所需
人数如下表所示(假��个人均能承担各个作�):
�工程的工期��()周,按此工期,整个工程至少需要()人
A、8 B、9 C、10 D、11
A、8 B、9 C、10 D、11
作� A B C D E F G H
�前作� - - A B C C D,E G
所需��(周)2 1 1 1 2 1 2 1
所需人数 8 4 5 4 4 3 7 8
�年��解析
某IT企��划�一批新招聘的技�人��行�前脱�培�,培�内容包括�程和��两个�
�,�个��要求在基�知�、�用技�和����三个方面都得到提高。根据培�大�,�周的
�程培�可以同��得基�知�3学分、�用技�7学分以及����10学分;�周的��培�可
以同��得基�知�5学分、�用技�2学分以及����7学分。企�要求�次�前培�至少能完
成基�知�70学分,�用技�86学分,����185学分。以上�明如下表所示:
那���的�前培�至少需要()周��才能�足企�的要求。
A、15 B、18 C、20 D、23
�程(学分/周) ��(学分/周) 学分最低要求
基�知� 3 5 70
�用技� 7 2 86
���� 10 7 185
�年��解析
从��的角度出�,可采用��法快速做�,假���的�前培��
15周,且全部安排�程培�,�基�知��分�3*15=45<70分,�用
技��分�7*15=105分>86分,�����分�10*15=150分
<185分,因此假�不能�足�体要求。
同理,假����前培��18周,�����分�10*18=180分
<185分,因此假�不能�足��要求。
若��的�前培��20周,�程培�和��培�分�安排15周、5周,
�基�知��分�70分,�用技��分�115分,�����分�185分。
能��足要求。
答案:C
�年��解析
�重量限24吨的某架�运�机�行将一批金属原料运往某地的任�。待运�的各箱原料的重
量、运�利�如下表所示。
��化安排,��机本次运�可以�得最大利��()千元
A、11 B、10 C、9 D、8
箱号 1 2 3 4 5 6
重量(吨) 8 13 6 9 5 7
利�(千元)3 5 2 4 2 3
�年��解析
解析:
将表中重量最少的4个数据相加,即5+6+7+8=26吨>24吨,因此
�架�机不能同�运�表中任何4箱的物品。按利�从高到低同�运�表中
任何3箱物品�行�排。当同�运�箱号�1、4、6的物品�,�重量�
好�24吨,此�利��3+4+3=10(千元)
�年��解析
某工厂生�甲、乙两��品,生�1公斤甲�品需要煤9公斤、�4度、
油3公斤,生�1公斤乙�品需要煤4公斤、�5度、油10公斤。�工厂�
有煤360公斤、�200度、油300公斤。已知甲�品�千克利��7千元,
乙�品�公斤利��万元,�了�取最大利���生�甲�品()公
斤,乙�品()公斤。
A、20 B、21 C、22 D、23
A、22 B、23 C、24 D、25
�年��解析
依�意, X1�甲�品生�量, X2�乙�品生�量, Z�可�取的最大利�,�反映了�生
��划��的�行�划数学模型表示如下:
目�函数:
�束条件:
�年��解析
某厂需要��生���生�某��品,可以����四�生�能力不同的��,市���
�品的需求状况有三�(需求量�大、需求量中等、需求量�小)。厂方估�四���在各�
需求状况下的收益如下表。根据收益期望�最大的原�,����() 。
A、��1 B、��2 C、��3 D、��4
�� 一 二 三 四
需求量�大概率� 50 30 25 10
需求量中等概率� 20 25 30 10
需求量�小概率� -20 -10 -5 10
�年��解析
�于����,其收益期望�:
����1的收益期望��17
����2的收益期望��16
����3的收益期望��18
����4的收益期望��10
所以,��C
�年��解析
某公司新建一座200平米的厂房,�准�部署生�某�品的��。�
公司�空�生���品的甲、乙、丙、丁四�型号的��各3台,��型号
���天的生�能力由下表�出。在厂房大小限定的情况下,�厂房�天
最多能生���品()个。
A、520 B、540 C、524 D、530
甲 乙 丙 丁
占地面�(平米) 40 20 10 5
�天生�能力(个)100 60 20 8
�年��解析
�是一个整数背包��。其中一�解法是�婪法,按���位面�的生�能力从高
到低排序,一次�取����,直到把厂房面�用完。根据表中的数据,将甲、乙、丙、
丁4�型号的��“�天生�能力”除以各自的“占地面�”,可得��型号的���平方米
�天的生�能力。�算�果分��个、个、个和个。因此在相同面�的情
况下,�按乙、甲、丙、丁的�序����。
依�意,生���品的甲、乙、丙、丁4中型号的��各3台。在厂房大小限定的情
况下,若要使�厂房�天的生�能力最大,�需要��3台乙型号��、3台甲型号��、
两台丙型号��。�8台��的�占地面��20*3+40*3+10*2=200平方米,�厂房
�天最多能生�指定�品的个数�520个。
�年��解析
在�件���目中,��路径是�目事件网�中(),�成��路径的活�称���活�。下�中
��路径��()个���位。
A、最�的回路 B、最短的回路
C、源点和�点�的最�路径 D、源点和�点件的最短路径
A、14 B、18 C、23 D、25
�年��解析
某工厂生�两��品S和K,受到原材料供�的��加工工�的限制。�件�品的利�、原材
料消耗及加工工�如下表。��得最大利�,S�生�()件
A、7 B、8 C、9 D、10
�品 S K �源限制
原材料消耗(公斤/件) 10 20 120
��工�(小�/件) 8 8 80
利�(元/件) 12 16
�年��解析
� x,y 分�表示在�划期内�品S 、 K的�量x>=0,y>= 0 。依�意,列出以下列方程
式及相�的求解�程。
当 x=8、y=2 �,将�得最大利�128元
�年��解析
公司��一套信息管理�件,其中一个核心模�的性能�整个系�的市��售前景影响极大,
�模�可以采用S公司自己研�、采�代�和有条件��三�方式��。S公司的可能利�(�位:
万元)收入如下表。
按��,此�管理�件�售50万套,20万套,5万套和�售不出的概率分��15%,25%,
40%和20%,�S公司���()方案。
A、自己研� B、采�代� C、有条件�� D、条件不足无法��
�售50万套 �售20万套 �售5万套 �不出去
自己研� 450000 200000 -50000 -150000
采�代� 65000 65000 65000 65000
有条件�� 250000 400000 0 0
�年��解析
分��算采用三�方式�的��期望��67500万元、65000万元和62500万元,故而�
�A、自己研�。
�年��解析
某公司打算��一�商品,�价�450元/件,售价500元/件。若��商品一周内售不完,�
�件�失50元。假定根据以往���料估�,�周最多�售4件,并且�周需求量分��0、1、2、
3和4件的��概率如下表所示:
�公司�周��()件可使利�最高
需求量(件) 0 1 2 3 4
��概率 0
�年��解析
本�主要考�运�学中的��性决策方法。
1)根据已知条件,可�算出不同��量及�量下可能�得的收益�果:
第一行,��量如果是1件,�售一件只能�得50元;如果市�上可以�售2件,但是由于��量只有1
件,因此收益仍然是50元
第二行,如果��2件,但是只能�售一件,�得50元,同�因�有一件没有�出去�失50元,两者相
抵,�收益�50-50.如果可以�售两件,可以�得收益100元
依次�推可以得到其他收益�
2)不同��量及�量下可能�得收益�果填好以后,根据决策��算公式,得到��量�1�的期望收
益:50*+50*+50*+50*=50。同理得到��量�2、3、4�的期望�。
3)决策��:��3件可�得最高收益110元。
1 2 3 4 期望收益�
1 50 50 50 50 50
2 0 100 100 100 90
3 -50 50 150 150 110
4 -100 0 200 200 100
�年��解析
某�目有Ⅰ、Ⅱ、Ⅲ、Ⅳ四�不同任�,恰有甲、乙、丙、丁四个人去完成各�不同的任�。
由于任�性�及�人的技�水平不同,他�完成各�任�所需��也不同,具体如下表所示
�目要求�个人只能完成一�任�,�了使�目花�的���最短,��指派丁完成()任�。
A、Ⅰ B、Ⅱ C、Ⅲ D、Ⅳ
�年��解析
此��运�学中�准的指派��,以人�指派�例,大都�足以下三个前提假�:人数等于任�数;
�个人必�且只需完成一�任�;��任�必�且只需一人去完成。
本�的效率矩��
本�求最小�,下面用匈牙利解法求解。
1)行��,找出�一行(�一列)的最小�,然后��一行(�一列都减去�个数。
�年��解析
2)�指派,找独立的零元素。独立零元素个数� ,矩��数� ,当 �,��得解。
最�解�:
最短���:4+4+9+11=28
�指派丁完成任�Ⅲ。C是正确答案
�年��解析
某�目各期的�金流量如下表所示:
���率�10%,��目的�����()
A、140 B、70 C、34 D、6
期数 0 1 2
��金流量 -630 330 440
�年��解析
根据���公式可知:
目前�目的���=-630+330/(1+10%)+440/(1+10%)2=-630+300+364=34
�年��解析
某企�需要采用甲、乙、丙三�原材料生�Ⅰ、Ⅱ两��品。生�两��品所需原材料数量、
�位�品可�得理人以及企�西安有原材料数如表所示:�公司可以�得的最大利�是()万元。
取得最大利��,原材料()尚有剩余。
A、21 B、34 C、39 D、48
A、甲 B、乙 C、丙 D、乙和丙
�品(吨) �有原材料
(吨)Ⅰ Ⅱ
所需�源 甲 1 1 4
乙 4 3 12
丙 1 3 6
�位利�(万元 吨) 9 12
�年��解析
�生�的�品Ⅰ�x吨,�品Ⅱ�y吨,1x+1y≤4,4x+3y≤12,1x+3y≤6解上述方程可知,
x=2,y=4/3。因此,最大利�是:9*2+12*4/3=34。原料“甲”�剩余:。
B、A
�年��解析
决策�分析法通常用决策��表�行分析,根据下表的决策�分析法�算,�中机会�点的�
期收益EMV分�是$90和$( )。
�年��解析
两家工厂A1和A2向三个零售店B1、B2和B3供�某�商品。A1和A2可供�的
商品件数是200和300,而B1、B2和B3的需求量是100件、200件和50件。各工厂
和零售店之�可以�行�运。如果运�的�位成本如下所示(例如:表中第4列第3行的
数字“5”表示将一件商品从A2运到B1的成本)。
在最�的�运安排中,�足各零售商品需求的运��成本是()
A、1750 B、1550 C、1350 D、850
A1 A2 B1 B2 B3
A1 0 6 7 8 9
A2 6 0 5 4 3
B1 7 2 0 5 1
B2 1 5 1 0 4
B3 8 9 7 6 0
�年��解析
1:分�求出A1 �点 和 A2�点通往 B1 B2 B3 的最短路径
2:判断最�方案
首先A2运往B3最�,首先��足B3,A2运往B3 50件(完全�足);A2剩余250件
� 其次A2运往B2 200件(完全�足);A2剩余50件
再次A2运往B1 50件(A2全部消耗);B1仍需50件
� 最后A1运往B1 50件(完全�足);A1剩余150件
3、50*3+200*4+50*5+50*7=150+800+250+350=1550
� 因此�B
�年��解析
某大型布��目由甲、乙两个子�目�成。甲�目�地准�需3天,乙�目�地准�需2天;
甲�目施工需5天,乙�目施工需4天。两个�目�地准�都需要一台�用��。在只有一台可用的
�用��的情况下,此大型�目至少需要()天才能完成。
A、6B、8C、9D、10
�年��解析
此�是�源平衡的��,��是9天,甲先干3天�目准�工作,乙先不干,甲干了3天的�
目准�工作后做施工5天,同�乙�始干�目准�工作2天,干完后接着干�目施工6天,其中5天
和甲一�,所以����3+2+4=9天。
�年��解析
五�任�需要分配到四�不同型号的机器上来�行。四�型号的机器分�有25、30、20和
30台。五�任�的工作量分�是20、20、30、10和25,不能把第四�机器分配到第四�任�
上。 ��任�当中的�个工作量在�行�需占用任意型号的1台机器。各�机器分配到各�任��
所�生的�位成本如下表所示:
任�分配的最�分配方案中,�成本是()
A、500 B、605 C、560 D、520
一 二 三 四 五
一 10 2 3 15 9
二 5 10 15 2 4
三 15 5 14 7 15
四 20 15 13 …… 8
�年��解析
解�思路:
1、 首先�制 ��数量/工作量表格
2、 然后找到成本差最大的任�,将��全部投入,如有剩余再�入其他低成本任�中。以此�推。
3、 根据上�成本�示,任�三成本差异最大,因此将��一投入任�三,而任�三剩余5个�位,
�找成本低的任����四。
4、 再次�找差异最大是任�四,所以任�四由��二完成,而��二剩余20个�元,
5、 再看任�二,由于��一已投入任�三,因此需要有��三来完成,没有剩余。
6、 在看任�一、四,正好可以由��二与��四来完成。
7、 用��数*�位成本的�和即�答案
8、 20*5+20*5+25*3+5*13+10*2+25*8=560
� 因此�C
�年��解析
假��台机床只能完成一道工序,�有四道工序需要分配到四台机床上,分配成本(以元�)如下
所表示,由于工�要求,工序一不能分配到机床丙上,工序三又不能分配到机床丁上。成本最低的
分配方案中,其成本是()
A、12 B、13 C、14 D、15
机床
工序
甲 乙 丙 丁
一 5 5 - 2
二 7 4 2 3
三 9 3 5 -
四 7 2 6 7
�年��解析
用迪杰斯特拉算法:
1:可确定二只能丙做(将丙所在行列 划掉)
2:三只能乙做(将丙所在行列 划掉)
3:由于:甲做一、丁做四 的成本 要大于 甲做四、丁做一 的成本。因此:确定甲做四、丁做一。
4:甲四、乙三、丙二、丁一 。即:7+3+2+2=14
因此�C
谢 谢!