工程数学复习题

1工程数学复习题一、写出下面问题的数学模型规划，不需求解（1）设要从甲地调出物资2000吨，从乙地调出物资1100吨，分别供给A地1700吨、B地1100吨、C地200吨、D地100吨。已知每吨运费如表1所示，运费与运量成正比，建立运费最省的供给方案。ABCD甲2125715乙51513715解：设甲、乙运往A、B、C、D的物资量分别为x11,x12,x13,x14,x21,x22,x23,x24吨，则由题意，我们需要去求21x11+25x12+7x13+15x14+51x21+51x22+37x23+15x24的最小值。显然x11,x12,x13,x14,x21,x22,x23,x24不能任意取值，我们还有“甲地调出物资2000吨”、“供给A地1700吨”等条件限制。总结需求及条件限制，得到下面的完整数学模型：111213142122232411121314212223241121122213231424min212571551513715..2000,1100,1700,1100,200,100,0,1,2,1,2,3,4ijfxxxxxxxxstxxxxxxxxxxxxxxxxxij（2）某工厂用3种原料P1，P2，P3生产3种产品Q1，Q2，Q3。已知的条件如下表所示，制定出总利润最大的生产计划。Q1Q2Q3原料可用量（kg/日）P12301500P2024800P33252000单位产品利润(千元)354解：设三种产品的生产量分别为x1,x2,x3时可以得到最大利润3x1+5x2+4x3，则由题意，我们可以得销地运费产地销地单位产品所需原料kg原料2到完整的模型为1231223123max354..231500,24800,3252000,0,1,2,3jzxxxstxxxxxxxxj（3）给出货郎游问题、背包问题的线性规划模型。货朗问题从v0出发，恰好经过v1，v2，…，vn各一次回到v0，从vi到vj路程为dij，（dii＝M充分大），怎么走最近？,000mins.t.=1,0,,=1,0,,1,101,,0,,1,,nijijijnijinijjijijijizdxxjnxinuunxnijnxorijnuin为实数，背包问题n个物品，体积分别为v1，v2，…，vn，价值分别为p1，p2，…，pn，一个容积为V的包，取哪些物品放入包内，使包内物品总价值最高。=1=1max=s.t.=0,1niiiniiiizpxvxVx二、用图解法解线性规划121212min5..284zxxstxxxx3三、论述用单纯形方法解LP问题的基本思想、步骤，并证明主要结论。答：（1）单纯形法解LP问题的基本思想是：先找一个基本可行解，然后判断它是否为最优解，如不是，就找一个更好的基本可行解，再进行判断，如此迭代进行，直到找到最优解或者判断该问题无界。（2）基本步骤：Step1转换一般的LP模型为标准型。Step2找一个初始可行基。Step3计算单纯形表中的各矩阵。Step4构造单纯形表。Step5判断最优解，是，则结束。否则，转入下一步。Step6换基迭代，返回Step5。（3）证明主要结论：定理若0，则x是最优解。证110,0,0,TTTTBBxxzcBbxcBb。定理若的第k个分量0k，且10kkABA，则该LP问题无界。这里Ak表示矩阵A的第k列。证1111111(+)0TTTTBBTTBTTTkBkTBkTBzcBbxcBbxcBbBAcBbecBbcBb（＋）0k四、用最优化思想求解下面的非线性规划问题222123123123max4212..329,,0Fxxxstxxxxxxx1+2x2=8x1-x2=4x1-5x2=0(4,0)(0,-4)x1x2(0,4)(8,0)4解：21()49zfz，故2222222202222202222022(2)()max{4}97164max{}999784max{()}97949xyxyxyyxfyxxyxyxyyy33332332309223309233092309(9)max{212(9)}4max{212(9)}922max{81236}92218max{()}911174xxxxfxfxxxxxx五、用动态规划思想，设计填表法，求解下面的划分问题：在集合A＝｛a1，a2，…，an｝上定义正整数函数s，令()aABsa，问是否存在AA，使得()2aABsa。解：{1,2,5,4,6,3,3}24t(3,5)=Tt(3,9)=Ft(2,4)=Ft(7,12)=T?Ft(n,B/2)令t(i,j)表示前i个元素中是否可以取出一部分元素其和为j，即，t(i,j)=T表示前i个元素中可以取出一部分元素其和为j，t(i,j)=F表示前i个元素中不可能取出一部分元素其和为j，则划分问题就是计算t(n,B/2)的值。012j…B/21TTF2TT?TTiTt(i,j)nT？？5012341,2TFTFF2,3TFTTF3,1TTTTT4,2TT,1,0,1,()(,),1,(1,),1,(1,()),iiTijTijsatijTitijTTitijsaTFothers六、证明：从n个元素中取出奇数个元素和取出偶数个元素取法数相同。证明：设C(n,k)为从n个元素中取出k个的方法数。那么取奇数个元素的方法数就为：S1=C(n,1)+C(n,3)+...+C(n,m),m是不超过n的最大奇数取偶数个元素的方法数为：S2=C(n,0)+C(n,2)+...+C(n,p），p是不超过n的最大偶数根据二项式公式：0=[1+(-1)]^2=C(n,0)-C(n,1)+C(n,2)+...+(-1)^nC(n,n)=S2-S1从而S2=S1七、字典序法生成排列时，135798642是第几个排列，下一个排列是谁？字典序法123456789,123456798123456879123456897…,98765432134968752122634321a1右面比a1小的多少个349687521349786521349712568算法：对P1P2P3…Pn，从右向左找最长降序子列Pi+1…Pn，记下Pi，找比Pi大的最右边一位Pk，交换Pi和Pk，将Pk右侧子列倒排。P1P2P3…PnP1P2P3…Pi-1PiPi+1…PnP1P2P3…Pi-1PiPi+1…Pk-1PkPk+1…PnP1P2P3…Pi-1PkPi+1…Pk-1PiPk+1…PnP1P2P3…Pi-1PkPn…Pk+1PiPk-1…Pi+1八、给出错排及错排问题的定义，并用两种不同方法求解错排问题。错排问题就是n个元素依次给以标号1，2，…，n，n个元素的全排列中，求每个元素都不在自己原来位置上的排列的个数。方法一：n各有序的元素应有n！种不同的排列。如若一个排列式的所有的元素都不在原来的位置上，则6称这个排列为错排。任给一个n，求出1,2,……,n的错排个数Dn共有多少个。递归关系式为：D(n)=(n-1)(D(n-1)+D(n-2))D(1)=0,D(2)=1可以得到:错排公式为f(n)=n![1-1/1!+1/2!-1/3!+……+(-1)^n*1/n!]其中,n!=1*2*3*.....*n,特别地,有0!=0,1!=1.解释：n个不同元素的一个错排可由下述两个步骤完成：第一步，“错排”1号元素（将1号元素排在第2至第n个位置之一），有n-1种方法。第二步，“错排”其余n-1个元素，按如下顺序进行。视第一步的结果，若1号元素落在第k个位置，第二步就先把k号元素“错排”好，k号元素的不同排法将导致两类不同的情况发生：1、k号元素排在第1个位置，留下的n-2个元素在与它们的编号集相等的位置集上“错排”，有f(n-2)种方法；2、k号元素不排第1个位置，这时可将第1个位置“看成”第k个位置，于是形成（包括k号元素在内的）n-1个元素的“错排”，有f(n-1)种方法。据加法原理，完成第二步共有f(n-2)+f(n-1)种方法。根据乘法原理，n个不同元素的错排种数f(n)=(n-1)[f(n-2)+f(n-1)](n2)。方法二：n个人每个人都不站在原来的位置的方法数有:f(n)=n!(1/2!-1/3!+1/4!+..+(-1)^n/n!)此公式的推导过程要用到筛法公式,而且推导过程很复杂,除了竞赛高考肯定不会出现,对于n不大于4时可采用枚举法.一般只需记住n不大于5的情况即可f(2)=1,f(3)=2,f(4)=9,f(5)=44此外还有一个简单的公式f(n)={n!/e},{x}表示最接近x的整数,e为自然底数,其值为2.7182818.........,一般取2.72即可九、证明6个人中或者存在3个人相互认识，或者存在3个人相互不认识。证明：任取一人A，将其认识的人放入集合F，将其不认识的人放入集合S。由鸽巢原理，F、S中有一个集合不少于3人。若F中至少有三个人，任取三人设为BCD，若BCD相互不认识，则得证，若BCD不是相互不认识，则其中至少有两人相互认识，不妨设BC相互认识，则ABC三人相互认识，得证；若中S中至少有三人，……。AAAAAAABAACAADAASF