运筹学复习资料全套

运筹学复习资料一、问答题（5选1）：1、运筹学的主要内容有哪些？运筹学为什么在美国被称为管理科学，此名称合理吗？答：运筹学是应用分析、试验、量化的方法，对经济管理系统中的人、财、物等有限资源进行统筹安排，为决策者提供有决策依据的最优方案，以实现最有效的管理。运筹学的研究内容包括规划论、图与网络分析、存贮论、排队论、对策论、决策论。规划论主要解决两大问题：如何有效利用现有的人力、物力去完成更多的任务；对于给定的任务或者目标。用最少的人力或物力如何去完成。图与网络分析主要解决生产组织、计划管理以及工程施工中的工序安排、工期控制、资源合理调配问题。决策论研究决策过程中方案的选择、度量和概率值选取问题。最终获得最优策略、最优方案。定量分析技术作为管理工具，在美国的许多企业得到广泛的应用，量化管理或者精确管理是美国企业管理的重点，运筹学在美国被称为管理科学。此名称合理。2、运筹学解决实际问题的过程可分为哪几个阶段?答：运筹学解决实际问题的过程可分为5个阶段：（1）提出并形成问题。要解问题，首先需要提出问题，明确问题的实质及关键所在，这就要求对系统进行深入的调查和分析，确定问题的界限，选准问题的目标。（2）建立模型。运筹学模型是一个能有效地达到一定目标（或多个目标）行动的系统，因此，目标一经认定，就要用数学语言描述问题，建立目标函数，分析问题所处的环境，确定约束条件，探求与问题有关的决策变量等，并选用合适的方法，建立运筹学模型。（3）分析并求解模型。根据所建模型的性质及其数学特征，选择适当的求解方法。（4）检验并评价模型。模型分析和计算得到结果以后，尚需按照它能否解决实际问题，主要考虑达成目标的情况，选择合适的标准，并通过一定的方法对模型结构和一些基本参数进行评价，以检验它们是否准确无误，否则就要考虑改换或修正模型，增减计算过程中所用到的资料或数据。（5）应用或实施模型的解。经过反复检查以后，最终应用或实施模型的解，就是供给决策者一套有科学依据的并为解决问题所需要的数据、信息或方案，以辅助决策者在处理问题时作出正确的决策和行动方案。3、试述线性规划模型建模的基本步骤及线性规划模型的构成要素的特征。答：①建模基本步骤：确定决策变量、确定目标函数、确定约束条件。②线性规划模型的构成要素及特征：决策变量，是规划问题中要确定的未知量,用来表示规划问题中用数量表示的方案\措施，可以由决策者决定和控制。目标函数，是决策变量的函数，反映决策者对于规划规划问题结果的要求。约束条件，指决策变量取值时受到的各种资源条件的限制,通常表达为含决策变量的等式或者不等式。4、试述线性规划与对偶规划之间存在的关系。答：线性规划问题具有对偶性，即任何一个求极大值的线性规划问题，都有一个求极小值的线性规划问题与之对应，反之亦然。如果把其中一个叫做原问题，则另一个就叫做它的对偶问题，并称这互相联系的两个问题为一对对偶问题。根据对偶理论，在解原问题的同时，也可以得到对偶问题的解，并且还可以提供影子价格等有价值的信息。5、什么是资源的影子价格，它同相应的市场价格之间有何区别？答：在一对对偶问题（P）和（D）中，若（P）的某个约束条件的右端常数bi增加1个单位时，所引起的目标函数最优值Z﹡的改变量yi﹡成为第i个约束条件的影子价格。如果原规划模型属于在一定资源约束条件下，按一定的生产消耗生产一组产品并寻求总体效益（如利润）目标函数最大化问题，那么其对偶模型属于对本问题中每一资源以某种方式进行估价以便得出与最优生产计划相一致的一个企业的最低总价值。该对偶模型中资源的估价表现为相应的资源的影子价格。影子价格不是市场价格，它是根据企业本身的资源情况bi、消耗系数aij和产品的利润cj计算出来的一种价格，是新增资源所创造的价值，是边际价格。不同的企业，即使是相同的资源，其影子价格也不一定相同。就是同一个企业，在不同的生产周期，资源的影子价格也不完全一样。企业决策者可以将企业资源的影子价格与市场价格相比较，买卖这种资源，使企业获利或降低成本，此时该资源的影子价格也将发生变化，直到影子价格与市场价格保持同等水平时，才处于平衡状态。影子价格是一种机会成本。二、建模题（只要求建立模型）1、资源的合理利用问题。P7一般提法：某厂计划在下一生产周期内生产B1,B2,…Bn种产品，要消耗A1,A2,…Am种资源，已知每件产品所消耗的资源数、每种资源的数量限制以及每件产品可获得的利润如表所示，问如何安排生产计划，才能充分利用现有的资源，使获得的总利润最大？设决策变量xj表示下一个周期产品Bj(j=1,2,…n)的产量，则此问题的数学模型可归结为：求xj，使得2、生产组织与计划问题。P8一般提法：某工厂用机床A1,A2,…Am加工B1,B2,…Bn种零件。在一个周期内，各机床可能工作的机时（台时），工厂必须完成各种零件的数量、各机床加工每个零件的时间（机时/个）和加工每个零件的成本（元/个）如表所示，问如何安排各机床的生产任务，才能完成加工任务，又使总成本最低？3、合理配料问题。P11一般提法：某饲养场用n种饲料B1,B2,…Bn配置成含有m种营养成分A1,A2,…Am的混合饲料，其余资料如表所示。问应如何配料，才能既满足需要，又使混合饲料的总成本最低？4、运输问题。P175设xij表示由产地Ai运往销地Bj(i=1,2,…m;j=1,2,….n)的运量，则当产销平衡时，其模型如下：当产大于销时，其模型是：当产小于销时，其模型是：5、合理下料问题。P247一般提法：设用某型号的圆钢下零件A1,A2,…,Am的毛坯。在一根圆钢上下料的方式有B1,B2,…Bn种，每种下料方式可以得到各种零件的毛坯数以及每种零件的需要量，如表所示。问怎样安排下料方式，使得即满足需要，所用的原材料又最少？设：xj

表示用Bj(j=1.2…n)种方式下料的圆钢根数，则这一问题的数学模型为：求xj，使得：6、0-1整数规划问题。P267例1一般模型nmaxZ=∑cixi；i=1n∑aijxj≤bi（i=1，2，…，m）；j=1s.t.xj=0,1（j=1，2，…，n）。7、目标规划P228例2课件：例三一般形式课本例二：已知一个生产计划的线性规划模型为：其中目标函数为总利润，x1,x2为产品A、B产量。现有下列目标：1、要求总利润必须超过2500元；2、考虑产品受市场影响，为避免积压，A、B的生产量不超过60件和100件；3、由于甲资源供应比较紧张，不要超过现有量140。试建立目标规划模型，并用图解法求解。解：以产品A、B的单件利润比2.5：1为权系数，模型如下：三、计算题：1、单纯形法。P51例1。例1：将线性规划问题化为典式,并列初始单纯形表解：先引入松驰变量x1、x2、x3，将问题化为典式取初始可行基

此时问题已是关于基的典式，故可直接作初始单纯形表，由表Ⅰ可知，初始基可行解（0，0，170，100，150），初始目标函数值再进行第二步迭代，由表Ⅱ可知，新的基可行解（0，30，110,10,0），相应的目标函数再进行第三步迭代，由表Ⅲ可知，检验数已全部非正，于是判定已求得最优解（50/7，200/7，540/7，0,,0），相应的目标函数最优值序号1018000Ⅰ000170100150521002301015001Z01018000Ⅱ0018110103023/5010-2/57/5001-3/51/51001/5Z-54032/5000-18/5Ⅲ01018540/750/7200/7001-23/711/71005/7-3/7010-1/72/7Z-4100/7000-32/7-6/72、某厂准备生产A、B、C三种产品，它们都要消耗劳动力和原材料，已知有关数据如下表：ABC资源限制劳动力63545原材料34530单件利润（元）415(1)

试建立线性规划模型，求使该厂获利最大的生产计划。(2)

原材料增加1个单位,能够使最优目标函数值增加或减少多少?解：（1）设决策变量分别表示A、B、C三种产品的产量，则此问题的数学模型为:引入松驰变量将问题化为标准型选初始可行基。令非基变量得初始基可行解。列单纯形表序号C41500CBXBbx1x2x3x4x5Ⅰ00x4x5453063510345*00Z04

1

500Ⅱ05x4x31563*-101-13/54/5101/5Z-301-300-1Ⅲ45x1x3531-1/301/3-1/3011-1/52/5Z-350-8/30-1/3-2/3由上表知，最优解为X*=（5，0，3，0，0）T，目标函数最优值Z*=35。即最优生产计划为：A产品生产5单位，C产品生产3单位，B产品生产0单位。（2）写出此问题线性规划的对偶规划，由上表可知对偶规划的最优解为Y*=（1/3，2/3）。根据对偶理论，对偶规划的最优解就是原规划中变量的影子价格，劳动力和原材料的影子价格分别为1/3，2/3。因此，原材料增加1个单位，按最优生产计划安排生产可以多获利2/3个单位。3、某公司在计划期内要安排生产A、B两种产品（假设市场销路很好）。生产单位产品的利润以及所需的劳动力、设备台时以及原材料的消耗资料由下表给出。产品A产品B资源限制劳动力设备原材料9434510360（工时）200（台时）300（千克）单位产品利润70120⑴

试求使该公司获利最大的生产方案。⑵

设备增加1台时，能够使最优目标函数增加或减少多少？解：⑴设A、B两种产品的产量分别是X1、X2，此生产问题的线性规划模型是：用单纯形法求解，首先引入松驰变量x3、x4、x5，将线性规划化成标准型，取松驰变量x3、x4、x5为基变量，求得初始基可行解X=（0，0，360，200，300）。列出单纯形表，根据规则在表中求解。序号C70120000CBXBbX1X2X3X4X5Ⅰ000X3X4X53602003009410045010310001Z070120000Ⅱ00120X3X4X224050307.8010-0.42.5011-0.50.31000.1Z-360034000-12Ⅲ070120X3X1X284202400

-2.12

-3.121.1610

0.4

0.4-0.201-0.12

-0.120.16Z-4280000-13.6-5.2由于最终表中所有的检验数都已经成为负数或者零,于是得到最优解:目标函数最优值（2）写出此问题的线性规划的对偶规划，求出对偶规划的最优解，根据对偶理论，对偶规划的最优解就是原规划中变量的影子价格，劳动工时、设备台时和原材料的影子价格分别为0，13.6，5.2。因此，设备每增加1台时，按最优计划安排生产可以多获利13.6元。4、对偶问题。作业P136（9）（10）（11）（9）已知线性规划问题.①写出其对偶问题；②已知原问题的最优解为3，2，0，试根据互补松弛定理，直接求出对偶问题的最优解；（3）如果上述规划中的第一个约束为资源约束，写出这种资源的影子价格。解：①原问题的对偶问题为②由于＞0，＞0，由互补松驰定理得其对应的对偶问题的约束条件为0，即所以对偶问题的最优解为③，第一种资源的影子价格为4（10）已知线性规划问题其对偶问题的最优解为，试根据对偶理论求出原问题的最优解。解：此LP问题的对偶问题为将代入对偶问题的约束条件（1）（2）为严格不等式，由互补松驰定理推知，。又因。故原问题的两个约束条件应取等式，有解得，故原问题的最优解为（0，0，4，4），目标函数最优值为（11）已知线性规划问题①写出其对偶问题；②已知原问题的最优解为1，1，2，0试根据对偶理论，直接求出对偶问题的最优解。解：①对偶规划为②将X*=（1，1，2，0）T代入原方程的约束条件则最后一个约束为松约束，所以又由于，，，由互补松驰定理知，其对偶问题的约束方程必为等式，即所以有即对偶问题的最优解为（2，2，1，0）5、运输问题。P177例1。作业P213。2（1）⑴P177例1。⑵作业P213。2（1）已知运输问题的产销平衡表与单位运价表如表所示，试用表上作业法分别求最优解（表中M代表充分大的正数）。销地产地B1B2B3B4产量A137645A224322A343853销量3322解：单位运价销地B1B2B3B4产量产地A1①◎②②5，4，2，03764A2②×××2，02432A3×③××3，04385销量3，1，03，02，02，0（x22,x12,x11,x21）为一个闭回路，σ22=（4+3）-（7+2）=-2＜0（x23,x13,x11,x21）为一个闭回路，σ23=（3+3）-（6+2）=-2＜0（x24,x14,x11,x21）为一个闭回路，σ24=（2+3）-（4+2）=-1＜0（x31,x11,x12,x32）为一个闭回路，σ31=（4+7）-（3+3）=5＞0（x33,x13,x12,x32）为一个闭回路，σ33=（8+7）-（6+3）=7＞0（x34,x14,x12,x32）为一个闭回路，σ34=（5+7）-（4+3）=5＞0单位运价销地B1B2B3B4产量产地A1③◎◎②53764A2◎×②×22432A3×③××34385销量3322X11*=3,X12*=0,X13*=0,X14*=2,X21*=0,X23*=2,X32*=3,其余Xij*=0，目标函数的最优值为Z*=3×3+0×7+0×6+2×4+0×2+2×3+3×3=32.6、用匈牙利法求解分配问题。P285、7（1）（2）（1）已知效益矩阵为79101213121617（cij）=1516141511121516解：791012－702350234（cij）=13121617－121045104415161415－141201120011121516－1101450144－1◎234√◎1231◎442◎0042◎Ø3〈422◎ØØ1442√Ø033√◎134√01012◎44√202222◎Ø3〈44400ØØ33√0011√√Ø1◎12◎2244Ø◎◎Ø11此时，独立零元素的个数m＝4。于是已求得最优解X13=X22*=X34*=X41*=1，其余Xij*=0。目标函数最优值Z﹡＝10×1+12×1+15×1+11×1＝48(2)已知效益矩阵为38210387297（cij）=64275842359106910解：382103－2160810407087297－26507553064（cij）=64275－2420533004284235－262013500029106910－63403422023－1－2－1－1◎4Ø7Ø0427053◎64√310423◎Ø42302425ØØ◎25020222Ø23√00001√Ø427◎31◎423◎2425Ø2◎2◎ØØØ1此时，独立零元素的个数m＝5。于是已求得最优解X15*=X23*=X32*=X44*=X51*=1，其余Xij*=0。目标函数最优值Z﹡＝3×1+2×1+4×1+3×1+9×1＝217、最短路径问题。解：整个计算过程分三个阶段，从最后一个阶段开始，第一阶段（C

→D）：

C

有三条路线到终点Df1

(C1

)=1；

f1(C2

)=3；

f1

(C3

)=4第二阶段（B

→C）：

B

到C

有六条路线。d(

B1,C1

)+

f1

(C1

)3+14f2

(

B1

)=mind(

B1,C2

)+

f1

(C2

)=min3+3=min6=4d(

B1,C3

)+

f1

(C3

)1+45最短路线为B1→C1

→D路长4d(

B2,C1

)+

f1

(C1

)2+13f2

(

B2

)=mind(

B2,C2

)+

f1

(C2

)=min3+3=min6=3d(

B2,C3

)+

f1

(C3

)1+45最短路线为B2→C1

→D路长3第三阶段（

A

→

B

）：

A

到B

有二条路线。d(A,

B1

)＋

f2

(

B1

)2+4f3

(A)=min=min=min｛6,7｝=6d(A,

B2

)＋

f2

(

B2

)4+3所以：最短路线为A→B1→C1

→D。路长6解：整个计算过程分四个阶段，从最后一个阶段开始，第一阶段（D

→E）：

D

有两条路线到终点E。显然有

f1

(D1

)=5；

f1(D2

)=2第二阶段（C

→D）：

C

到D有三条路线。d(

C1,D1

)+

f1

(D1

)3+58f2

(

C1

)=mind(

C1,D2

)+

f1

(D2

)=min9+2=min11=8d(