2016最优化理论与方法(线性部分)思考题

最优化理论与方法（线性部分）思考题1就你学过的运筹学问题，写出能够建立线性规划模型的问题，并举例（建立模型）。以下四种食物1、2、3、4，依次售价为50、20、30、80，而我们人体每天需摄取至少500卡路里，6盎司巧克力，10G糖以及8G脂肪，具体成分如下，饮食的营养价值食物类型卡路里巧克力（盎司）糖盎司脂肪（盎司）1巧克力糖4003222巧克力冰淇淋2002243可口可乐1500414蛋糕500045要求建立一个以最小成本满足每天营养需求的线性规划模型。模型如下MIN501202303804ST400120021503500450031226212243441021421354801，2，3，42举例（说明问题、建立模型）论述线性规划在交通、运输、物流和安全管理中的应用。答现在物流业面临的新问题是认定所给问题确实是一个线性规划问题；把它建立起线性数学模型；并能够完成具体实务的全部工作。第一个问题实质上是具体实务究竟满足什么条件才能应用线性规划的方法。一般地说，必须有一定要满足将目标表为最小化或最大化的要求；一定要有达到目标的不同方法，且必须要有选择的可能性；要求的目标是有限制条件的；必须将约束条件用数学表示为线性等式或线性不等式，并将目标函数化为线性函数。运筹学中的指派问题、最短路问题，最小费用流问题可转化为运输问题或转运问题。设某种物品有M个产地,各产地的产量分别是1，2，；有N个销地；各销地的销量分别为1，2，1，2，假定从产地（I1，2，M）向销地1，2，（J1，2，N）运输单位物品的运价为，若用表示从到的运输量，则在产销平衡条件下，总费用最低的数学模型为MIN111，1，2，1，1，2，0以下是运输问题的数学模型，包含个变量，MN个约束方程，其系数矩阵的结构比较松散，且特殊。3对一个用单纯形法求解不会产生循环（且能求得最优解）的N个变量M个约束的线性规划问题，估算一下基本计算次数。答即说明约束系数矩阵为MN的矩阵，且满足检验数，0J如有无穷多的最优解还有存在某个非基变量。其基本计算MK次数为4简述线性规划求解算法的改进历史。答针对一般线性规划问题的求解方法（单纯形法改进单纯形法对偶单纯形法），到后来特殊的线性规划问题求解算法（表上作业法）5证明课本（清华版运筹学（第三版）25题。证明下面用矩阵形式将原问题表示为（1）MAX10设其可行解为，其对偶问题的最优解为。111，（2）MAX20设其可行解为，其对偶问题的最优解为。22问题1的对偶问题为MIN0问题2的对偶问题为MIN0由此可见，问题1的对偶问题的约束条件与问题2的对偶问题的约束条件相同，从而问题1的对偶问题的最优解一11，定是问题2的对偶问题的可行解。而问题2的对偶问题的最优解为，故2。因为原问题与211111对偶问题的最优函数值相等，故有MAX2MAX116有人说“原问题有多重解（多个最优解），对偶问题一定也有多重解”，此话是否正确请举一算例。答这句话是错误的。对偶问题的最优解只有在线性规划中此问题才是对的，如果是非线性规划就不对了。举例任意一个问题有多重解非线性规划均满足。7DW分解算法适合那种类型的线性规划问题请举一算例。答DW分解算法适合按照下列方法分解约束条件和变量集合1中的约束条件只涉及变量集合1中的变量。集合2中的约束条件只涉及变量集合2中的变量。集合K中的约束条件只涉及变量集合K中的变量。集合K1中的约束条件可以涉及任何变量。集合K1中的约束条件称为中心约束条件。适合按照以上方式分解的LP。算例一家公司在两家工厂生产两种钢材。工厂1每天可以使用12吨煤，工厂2每天可以使用15吨煤；煤不能在两工厂之间运输，工厂1每天可以使用10小时的鼓风炉时间，工厂2每天可以使用4小时的鼓风炉时间，铁矿位于两家工厂之间，每天提供80吨铁，钢材1每吨售价170美元，钢材2每吨售价160美元。所有钢材都送给一个客户；从工厂1运一吨钢材需要80美元，工厂2运一吨钢材需要100美元。假设运输成本是唯一的可变成本，表述并求解一个使该公司利润（收入运输成本）最大的LP。公司的资源要求产品需要的铁（T）需要的煤T需要鼓风炉时间H工厂1钢材1832工厂1钢材2611工厂2钢材1731工厂2钢材2521工厂1每天生产的钢材1的吨数1工厂1每天生产的钢材2的吨数2工厂2每天生产的钢材1的吨数3工厂2每天生产的钢材2的吨数4LP123412341234MAX9087061586780,ZXXSTXXX变量集合11和2工厂1的变量变量集合23和4工厂2的变量约束条件集合1（1）和（2）工厂1的约束条件约束条件集合2（3）和（4）工厂2的约束条件约束条件集合3（5）工厂1的约束条件8何谓“原始对偶”单纯形法请举一算例。答应用对偶原理求解原始线性规划的一种方法在原始问题单纯形表格上进行对偶处理。线性规划问题123123MIN5354,0WYYST添加松弛变量以后的标准型，再将标准型中灯饰两边乘以1，则以上问题转化为54123312,MIN350YSTY然而在有些问题中，我们很容易找到初始基本解，因此使用对偶单纯形法求解线性规划问题是有一定条件的，其条件是1单纯形表的B列中至少有一个负数2单纯形表中的基本解都满足最优性检验对偶单纯形法与原始单纯形法相比有两个显著的优点1初始解可以是不可行解，当检验数都非正时，即可进行基的变换，这时不需要引入人工变量，因此简化了计算9何谓有界变量的线性规划问题如何求解请举一算例。答实际运用中的线性规划问题,其决策变量具有上下界限的限制。至于其求解算法，以先转化为标准形式的线性规划问题,然后按照单纯形方法进行求解，或者是有界变量单纯形法。以下是一具体算例（基线算法）列出母表X1X2X3X4X5RHS21000V111101012312342512345MAX10800,VXSTXX212018取初始基本可行解（0，0，1，11，6），初始解X1和X2中都取其对应下界,我们可将X1和X2作为下非基变量，可将X3作为进基，得BL表，X1X2X3X4X5RHS23100V1V21401010VV106700182VV4LL其解为1，2，选取2为旋转主元得到新的BL表X1X2X3X4X5RHS1321200V22V10052121010V2V18023018VV14LU其对应不等式组的解为2,10，此表已为最优表，最优值MAXZ10，计算得最优解为4，0，2，4，4。10何谓线性规划的逆问题，分别对“最优解的逆线性规划问题”和“对目标函数值的线性规划逆最优值问题”举出算例。答给定线性规划问题一个可行但非最优的解,要求在某种模0X的意义下,尽可能少的调整价值向量,使其成为新问题的最优解。最优解的逆线性优化问题算例对目标函数值的线性规划逆最优值问题算例11对同一优化问题，是否存在决策变量一样但所建模型不一样的情况请举例；是否存在目标函数中没有决策变量的最优化问题答同一优化问题存在决策变量一样但是所建模型不一样的。处理实际问题时，一般没有一个唯一正确的模型，而是有多种不同的方案。建模是一个演进过程，从一个初始模型往往需要不断的完善渐渐演化成一个完整的数学模型。举例针对港口岸桥调度问题，最终的目标函数，我们可以要求总成本最小，亦可要求所有岸桥总行走里程最短。最终建立的模型不一样。决策变量是建立最优化问题模型三要素之一，故不存在目标函数中没有决策变量的最优化问题。12简述建立线性多目标规划的过程，自选一个实际问题，建立模型并用图解法和单纯形法求解。答主要研究多余一个目标函数的在给定区域上的最优化。即先确定此规划的决策变量，还要引进正、负偏差，以及完善D约束条件（绝对约束和目标约束），确定优化因子（优先等级）与权系数，确定目标规划的目标函数，完成最终的线性多目标规划。一个生产问题，有关数据如下表，要求第二种原料用完。问应如何安排生产可使总利润最大，产量之和最小。原料甲乙总量A4480B4248C106单位利润8010