下载文档原格式
运筹学知识点：绪论1.运筹学的起源2.运筹学的特点第一章线性规划及单纯形法1.规划问题指生产和经营管理中如何合理安排，使人力、物力等各种资源得到充分利用，获得最大效益。
2.规划问题解决两类问题：一是给定一定数量的人力、物力等资源，研究如何充分利用，以发挥其最大效果；二是已给定计划任务，研究如何统筹安排，用最少的人力和物力去完成。
3.规划问题的数学模型包含三个组成要素：决策变量、目标函数（单一）、约束条件（多个）。
线性规划问题的数学模型要求：决策变量为可控的连续变量，目标函数和约束条件都是线性的。
4.线性规划问题的标准形式：目标函数为极大、约束条件为等式、决策变量为非负、变量为非负5.划标准型时添加的松驰变量、剩余变量和人工变量6.理解可行解、最优解、基、基解、基可行解等概念，且掌握各类解间的关系7.用图解法理解线性规划问题的四种解的情况：无穷多最优解、无界解、无可行解、唯一最优解8.用图解法只有解决两个变量的决策问题9.线性规划问题存在可行解，则可行域是凸集。
10.线性规划问题的基可行解对应线性规划问题可行域的顶点。
11.线性规划问题的解进行最优性检验：当所有的检验数小于等于零时为最优解；尤其当检验数小于零时（即不等于零）有唯一最优解；当某个非基变量检验数为时，有无穷多最优解；当存在某个检验数大于零且对应的系数又小于等于零时，有无界解。
12.单纯形法的计算过程，可能出计算题13.入单纯形表前首先要化成标准形式。
14.确定换出变量时根据θ值最小原则，且要求公式中对应的系数大于零。
15.当线性规划中约束条件为等式或大于等于时，划为标准型后，系数矩阵中又不包含单位矩阵时，需要添加人工变量构造一个单位矩阵作为基。
16.人工变量的系数为足够大的一个负值，用—M代表17.一般线性规划问题的数学建模题（生产计划问题、人才资源分配问题、混合配料问题等）第二章对偶问题1.原问题和对偶问题数学模型的对应关系，可能出填空题和数学模型题2.每一个线性规划必然有与之相伴而生的对偶问题3.对偶问题的性质：弱对偶性、无界性、强对偶性、最优性、互补松弛性，其中互补松弛性可能出计算题4.原问题与其对偶问题之间存在一对互补的基解，其中原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题变量5.影子价格的定义，用互补松驰性理解影子价格的含义6.影子价格与企业的生产任务、产品结构、技术状况等相关，与市场需求无关7.理解影子价格是机会成本第三章运输问题1.运输问题的数学模型，出建模题2.掌握三个数字：m+n、m*n、m+n-13.解的退化及处理4.运输规划问题本质仍然是线性规划，系数矩阵的特殊性，利用表上作业法求解，核心依然是单纯形法5.表上作业法的计算过程，可能出大题6.什么是基格和空格及含义以及检验数的经济意义7.初始方案的方法，计算检验数的方法，调整方案的方法8.检验数的含义及检验规划与一般线性规划问题的差别9.产销不平衡问题的处理，包括产大于销和销大于产，假想地的单位运价设为零第四章整数规划1.整数规划的分类：纯整数、混合整数、0-1整数2.指派问题的数学模型，可能出建模题3.匈牙利法的计算过程4.解矩阵的特点：n个解1位于不同行不同列上5.分枝定界法分枝和定界的依据以及如何分枝和如何定界6.整数规划问题的求解方法及适用条件7.整数规划问题与其松弛问题解的关系第五章目标规划1.线性规划的局限：严格约束、单目标、约束同等重要2.目标规划问题的数学模型，可能会出建模题，强调目标函数由偏差变量、优先因素和权系数构成3.偏差变量的含义及特点，成对出现，非负且至少有一个为零4.目标约束是等式，等式左边添加一对偏差变量相减5.目标规划问题求解的单纯形表计算停止的规划：要么所有行的检验数均为非负，要么前i行检验数为非负，第i+1行存在负的检验数，但在负检验数上面存在正检验数6.目标规划的达成函数中的偏差变量的选择第六章图论与网络优化1.图论中的图研究对象间的关系，只关心图中有多少个点及点间有线相连2.树的定义及性质3.最小树的求解方法：避圈法和破圈法4.狄克斯屈拉算法的特点：不仅求出从始点到终点的最短路，还求出从始点其他任何各点的最短路5.有向图（点弧）非对称关系和无向图（点边）对称关系的应用6.可行流的定义：两大类的三个条件7.增广链的定义及特点8.最大流最小割定理9.用ford-fulkerson算法求网络中的最大流的计算过程10.算法的核心和实质是判断是否存在增广链，，即网络达到最大流的条件是网络中不存在增广链第七章网络计划技术1.关键路线的定点：持续时间最长、节点时差为零、不止一条2.工作持续时间的确定方法及使用条件3.节点最早时间、节点最迟时间的理解4.工作时间参数着重理解总时差和自由时差，即总时差是若干项工作共同拥有的机动时间，自由时差是某项工作单独拥有的机动时间5.绘制网络技术图的规则第八章动态规划1.动态规划是研究多阶段决策问题的理论和方法2.状态必须具备无后效性，及无后效性的定义3.动态规划和顺序解法和逆序解法的路径及应用条件。
运筹学习题精选第一章线性规划及单纯形法选择1．在线性规划模型中，没有非负约束的变量称为……………………………………………………( C )A．多余变量 B．松弛变量 C．自由变量 D．人工变量2．约束条件为0AX的线性规划问题的可行解集b,≥=X 是………………………………………( B )A．补集 B．凸集 C．交集 D．凹集3．线性规划问题若有最优解，则一定可以在可行域的（ C）上达到。
A．内点 B．外点 C．顶点 D．几何点4．线性规划标准型中bi（i=1，2，……m）必须是…………………………………………………( B)A．正数 B．非负数 C．无约束 D．非零的5．线性规划问题的基本可行解X对应于可行域D 的………………………………………………( D)A．外点 B．所有点 C．内点 D．极点6．基本可行解中的非零变量的个数小于约束条件数时，该问题可求得……………………………( B ) A．基本解 B．退化解 C．多重解 D．无解7．满足线性规划问题全部约束条件的解称为…………………………………………………( C )A．最优解 B．基本解 C．可行解 D．多重解8．线性规划一般模型中，自由变量可以用两个非负变量的（B ）代换。
A．和 B．差 C．积 D．商9．当满足最优检验，且检验数为零的变量的个数大于基变量的个数时，可求得………………………( A )A ．多重解B ．无解C ．正则解D ．退化解 10．若线性规划问题有最优解，则必定存在一个( D )是最优解。
A ．无穷多解 B. 基解 C. 可行解 D. 基可行解 填空计算 1． 某厂生产甲、乙、丙三种产品，已知有关数据如下表所示,求使该厂获利最大的生产计划。
2． 目标函数为max Z =28x4+x5+2x6，约束形式为“≤”，且x1，x2，x3为松弛变量，表中的解代入目标函数中得Z=14，求出a~g 的值，并判断是否→j c 0 0 0 28 1 2B C 基 b 1x 2x 3x 4x5x 6x 2 6x A 3 0 -14/3 0 1 1 0 2x 5 6 D 2 0 5/2 0 28 4x 0 0 E F 1 0 0 j j z c - B C 0 0 -1 G3． 某工厂生产A 、B 两种产品，已知生产A 每公斤要用煤6吨、电4度、劳动力3个；生产B 每公斤要用煤4吨、电5度、劳动力10个。
第8章动态规划8.1 在设备负荷分配问题中，n =10，a =0.7，b =0.85，g =15，h =10，期初有设备1000台。
试利用公式(8.7)确定10期的设备最优负荷方案。
【解】由公式10()n t n tii i i g h a a g b a ---==-≤≤-∑∑得(g -h )/g (b -a )＝0.2222，a 0＋a 1＋a 2＝1+0.7＋0.49＝2.19＜2.222＜a 0+a 1＋a 2＋a 3＝2.533，n －t －1＝2，t =7，则1~6年低负荷运行，7~10年为高负荷运行。
各年年初投入设备数如下表。
年份1 2 3 4 5 6 7 8 9 10 设备台数 1000 850 723 614 522 444 377 264 184.8 129 8.2如图8－4，求A 到F 的最短路线及最短距离。
【解】A 到F 的最短距离为13；最短路线 A→ B2→ C3 → D2 → E2 → F 及A→C2 → D2 → E2 → F8.3求解下列非线性规划(1) 123123max 0,1,2,3j Z x x x x x x C x j =++=⎧⎪⎨≥=⎪⎩ (2) 22123123123min ,,0Z x x x x x x Cx x x =++++=⎧⎨≥⎩（3）2123123123max 2310,,0Z x x x x x x x x x =++++=⎧⎨≥⎩(4)123123max 42100,1,2,3j Z x x x x x x x j =++=⎧⎪⎨≥=⎪⎩ (5) 123123max 24100,1,2,3j Z x x x x x x x j =++≤⎧⎪⎨≥=⎪⎩（6）221123123123max 228,,0Z x x x x x x x x x x =+++++=⎧⎨≥⎩【解】（1）设s 3=x 3 , s 3+x 2=s 2，s 2+x 1=s 1=C则有 x 3= s 3 ，0≤x 2≤s 2，0≤x 1≤s 1=C 用逆推法，从后向前依次有k ＝3，333333()max()x s f s x s ===及最优解 x 3*=s 3k ＝2，22222222233222222000()max [()max [()]max (,)x s x s x s f s x f x x s x h s x ≤≤≤≤≤≤==-=由222222120,2h s x x s x ∂=-=∂则＝22222<0,h x ∂∂＝－故2212x s =为极大值点。
所以22222222111()244f s s s s =-=及最优解x 2*=s 2k =1时，1111112111221*********()max[()]max ()max (,)4x s x s x s f s x f s x s x h s x ≤≤≤≤≤≤==-=，由221111111(43)04h s s x x x ∂=-+=∂，得*1113x s =故23111111111()()12327f s s s s s =-= 已知知x 1 + x 2+ x 3 = C ，因而按计算的顺序推算，可得各阶段的最优决策和最优解如下*113x C =，311()27f C c =由s 2=s 1－x 1*=2C/3，*222211,()39x C f s C ==由s 3=s 2－x 2*=C/3，*33311,()33x C f s C ==最优解为：31111(,,);33327T X C C C z C ==【解】（2）设s 3=x 3 , s 3+x 2=s 2，s 2+x 1=s 1=C则有x 3= s 3 ，0≤x 2≤s 2，0≤x 1≤s 1=C 用逆推法，从后向前依次有k ＝3，2333333()min()x s f s x s ===及最优解 x 3*=s 3k ＝2，22222222223322222202200()min [()min [()]min (,)x s x s x s f s x f x x s x h s x ≤≤≤≤≤≤=+=+-=由2222221420,2h s x x s x ∂=-=∂则＝2222x h ∂∂=4>0,故x 2=221s 为极小值点。
因而有2*2222211(),22f s s x s ==k ＝1时，1111211111111001()min [()min (,)2x s x s f s x s x h s x ≤≤≤≤=+-=由111110h s x x ∂=-+=∂知*1111111,()2x s f s s =-=-得到最优解1(1,1/2,1/2);2T X C z C =-=-【解】(3) 设s 3=x 3 , s 3+x 2=s 2，s 2+x 1=s 1=10 则有 x 3= s 3 ，0≤x 2≤s 2，0≤x 1≤s 1=10 用逆推法，从后向前依次有k ＝3时，3323333()max()x s f s x s ===及最优解 x 3=s 3k ＝2时，222222222222200()max [3()]max (,)x s x s f s x s x h s x ≤≤≤≤=+-=222222332202h s x x s x ∂=-+==-+∂时 而222222320,2h x s x ∂=>=-+∂故不是一个极大值点。
讨论端点：当x 2=0时2222()f s s ＝, x 2= s 2时222()3f s s =如果s 2>3时, 2222()f s s =k ＝1时，111121111111100()max[2()]max (,)x s x s f s x s x h s x ≤≤≤≤=+-=11111122201h s x x s x ∂=-+==-+∂时 21122120,1h x s x ∂=>=-+∂故不是一个极大值点 同理有, x 1=0, f 1（s 1）= s 12= 100，x 1= s 1, f 1（s 1）= 2s 1= 20 (舍去) 得到最优解(0,0,10);100X z ==【解】(4)设s 3=x 3 ,2s 3+4x 2=s 2，s 2+x 1=s 1=10 则有x 3= s 3 ，0≤x 2≤s 2/4，0≤x 1≤s 1=10 用逆推法，从后向前依次有 k ＝1，333333()max()x s f s x s ===及最优解x 3*=s 3k ＝2，22222222222204041()max [(2)max (,)2x s x s f s x s x h s x ≤≤≤≤=-=由22x h ∂∂=21s 2-4x 2=0,则 x 2=81s 2222240h x ∂=-<∂,故2218x s =为极大值点。
则2222()32s f s =及最优解x 2*=s 2/8k ＝1，1111211111111001()max[()]max (,)32x s x s f s x s x h s x ≤≤≤≤=-= 22*1111111111(43)0,323h s s x x x s x ∂=-+==∂，故31111()216f s s = 得到最优解(10/3,5/6,5/3);125/27T X z ==【解】(5)按问题中变量的个数分为三个阶段s 1，s 2，s 3 ，且s 3≤10，x 1，x 2，x 3为各阶段的决策变量，各阶段指标函数相乘。
设s 1=2x 1 , s 1+4x 2=s 2，s 2+x 3=s 3≤10，则有x 1= s 1/2，0≤x 2≤s 2/4，0≤x 3≤s 3=10 用顺推法，从前向后依次有 k ＝1，111111/2()max ()2x s s f s x ===及最优化解x 1*=s 1/2 k ＝2，2222222222220/40/41()max [(4)max (,)2x s x s f s x s x h s x ≤≤≤≤=-=由22221402h s x x ∂=-=∂,则*2218x s = 222240h x ∂=-<∂,故2218x s =为极大值点。
则32221()32f s s = k ＝3，3333233333333001()max [()]max (,)32x s x s f s x s x h s x ≤≤≤≤=-= 由22*3333333311(43)0,323h s s x x x s x ∂=-+==∂ 故33331()216f s s =，由于s 3≤10，则s 3=10时取最大值，x 3＝10/3，s 2=s 3－x 3＝20/3，x 2＝5/6，s 1=s 2－4x 2＝10/3，x 1＝5/3得到最优解(5/3,5/6,10/3);125/27T X z ==【解】（6）设s 1=x 1, s 1+x 2=s 2，s 2+x 3=s 3=8k ＝1，1122111111()max(2)2x s f s x x s s ==+=+及最优化解x 1*=s 1k ＝2，222222222222222200()max [2()2()]max (,)x s x s f s x s x s x h s x ≤≤≤≤=+-+-=2222622,h x s x ∂=--∂222260h x ∂=>∂ x 2*=0时，f 2（s 2）=s 22+2s 2, x 2*= s 2时，f 2（s 2）=2s 22 故2222222()max{2,2}f s s s s =+ k ＝3，①当x 2*=0时，23333333333033033()max [()2()]max (,)x s x s f s x s x s x h s x ≤≤≤≤=+-+-= 同样得x 3*=0时，f 3（s 3）=s 32+2s 3x 3*=s 3时，f 3（s 3）=s 3 所以， f 3（s 3）= s 32+2s 3=80②当x 2*= s 2时，f 3（s 3）=330max s x ≤≤[x 3+2（s 3-x 3）2]同样得x 3*=0时，f 3（s 3）=2s 32 =128 x 3*=s 3时，f 3（s 3）=s 3 =8 所以， f 3（s 3）= 2s 32=128 最优解为(0,8,0);128X z ==8.4用动态规划求解下列线性规划问题。
12121212max 242624,0Z x x x x x x x x =++≤⎧⎪≤⎪⎨≤⎪⎪≥⎩【解】设s 2=x 2 ,s 2+2x 1=s 1≤6则有 0≤x 2=s 2≤4，0≤x 1≤s 1/2 用逆推法，从后向前依次有 222()4f s s =及最优解x 2*=s 2111111122110/20/2()max [2()]max [46]x s x s f s x f s s x ≤≤≤≤=+=-由 s 2=s 1－2x 1≤4， s 1≤6，取s 1＝6，111110/2()max [246]x s f s x ≤≤=-又1≤x 1≤2，取x 1＝1，11()18f s =最优解(1,4);18T X z ==8.5 10吨集装箱最多只能装9吨，现有3种货物供装载，每种货物的单位重量及相应单位价值如表8.24所示。
