资源描述：
《最优化理论和方法(线性部分)思考题和作业要求答案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、最优化理论与方法（线性部分）思考题1.就你学过的运筹学问题，写出能够建立线性规划模型的问题，并举例（建立模型）。工厂生产利润最大化问题2.举例（说明问题、建立模型）论述线性规划在交通、运输、物流和安全管理中的应用。3.对一个用单纯形法求解不会产生循环（且能求得最优解）的n个变量m个约束的线性规划问题，估算一下基本计算次数。4.简述线性规划求解算法的改进历史。5•证明课本（清华版运筹学（笫三版））2.5题。6.有人说：“原问题有多重解（多个最优解），对偶问题一定也有多重解”，此话是否止确？请举一算例。7.D・W分解算法适合哪种
2、类型的线性规划问题？请举一算例。8.何谓“原始-对偶”单纯形法？请举一算例。9.何谓有界变量的线性规划问题？如何求解？请举一算例。10•何谓线性规划的逆问题，分别对“最优解的逆线性规划问题”和“对目标函数值的线性规划逆最优值问题”举出算例。11•对同一优化问题，是否存在决策变量一样但所建模型不一样的情况？请举例；是否存在目标函数中没有决策变量的最优化问题？12•简述建立线性多目标规划的过程，自选一个实际问题，建立模型并用图解法和单纯形法求解。要求每个人所举例题都不一样，否则视为抄袭!最优化理论与方法（线性部分）思考题1.解：
3、以工厂生产利润最大化问题：某工厂生产I、II两种产品，己知有关数据见下表。试求获利最大的生产方案。III资源量原料（kg）2111设备（hr）1210利润（元/件）810设衍、尢2分别代表I、II两种产品生产量，其线性规划模型表述为:maxz=8兀1+10%2{2%1+兀2S11%!+2无2<10xlfx2>02.解：以管理（指派）问题：有一份中文说明书，需翻译为日、英、德、法四种文字，分别记作A、B、C、D、现有甲乙丙丁四人，他们将中文说明书翻译成不同语种的说明书所需要的时间如下表所示。问应指派何人去完成何种工作，使所需总
4、时间最少？ABCD甲215134乙1041415丙9141613J*78119=i.j=表示指派第i人去完成j项任务的时间,引入切,其取值只能使0和1。并另切取1时表示指派第i个人去完成第j项工作；取0时表示不指派第i个人去完成第j项工作。当问题要求极小化时的数学模型是:minz二nn=工》JXij[=17=1Yj=iXij=1,i=l,2,...,n器i切=1,j=1,2,...,n切=0或1i.j=1.对一个用单纯形法求解不会产生循环(且能求得最优解)的n个变量m个约束的线性规划问题，估算一下基本计算次数。考虑最一般的情
5、况。(1)确定换出变量：n1=m(2)基变换：n2=3■(n+m+1)(3)检验数计算：n3=n•(m+m—1+1)=2mn所以，基本计算次数N=K•(2mn+3n+4m+3),式中，K为迭代次数。2.简述线性规划求解算法的改进历史。线性规划是运筹学的一个重要分支。法国数学家J.-B.-J.傅里叶和C.瓦莱一普森分别于1832和1911年独立地提出线性规划的想法，但未引起注意。1939年苏联数学家几B.康托罗维奇在《生产组织与计划中的数学方法》一书中提岀线性规划问题，也未引起重视。1947年美国数学家G.B.Dantzing
6、提出求解线性规划的单纯形法，为这门学科奠定了基础。1947年美国数学家J.von诺伊曼提出对偶理论，开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力。50年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法。例如，1954年C.莱姆基提出对偶单纯形法，1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题，1956年A.塔克提出互补松弛定理，1960年G.B•丹齐克和P.沃尔夫提出分解算法等。1979年苏联数学家L.G.Khachian提出解线性规划问题的椭球算法，并证明它是多项式时间算
7、法。1984年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划问题的新的多项式时间算法。用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50o现已形成线性规划多项式算法理论。1.证明课本（清华版运筹学（第三版））2.5题。证明：原问题用矩阵描述写为：①maxZr—CXst[AX^blX>0其中b=（bltb2，…,bny设其可行解为X1，其对偶问题的最优解为（珀，…,几）.maxZ2=CX(AX0设其可行解为X2,其对偶问题的最优解为W问题②的对偶问题为:mina)=Y(b+k)
8、(YA>Cty>o其中比=（心,他,・・・,褊）丁•・・丫2为最优解・•・丫2少+k）sY13+fc）・・・X2为②的可行解，・・・化
