最优化理论与方法(线性部分)思考题与作业要求 - 用于合并

1、最优化理论与方法（线性部分）思考题1. 就你学过的运筹学问题，写出能够建立线性规划模型的问题，并举例（建立模型）。以下四种食物1、2、3、4，依次售价为50、20、30、80，而我们人体每天需摄取至少500卡路里，6盎司巧克力，10g糖以及8g脂肪，具体成分如下，饮食的营养价值食物类型卡路里巧克力（盎司）糖(盎司)脂肪（盎司）1.巧克力糖4003222.巧克力冰淇淋2002243.可口可乐1500414.蛋糕500045要求：建立一个以最小成本满足每天营养需求的线性规划模型。模型如下：minz=50x1+20x2+30x3+80x4s.t. 400x1+200x2+150x3+500x4500

2、 3x1 + 2x2 6 2x1 + 2x2 + 4x3 + 4x4 102x1 + 4x2 + 1x3 + 5x4 8 xi0(i=1，2，3，4)2. 举例（说明问题、建立模型）论述线性规划在交通、运输、物流和安全管理中的应用。答：现在物流业面临的新问题是： 认定所给问题确实是一个线性规划问题； 把它建立起线性数学模型； 并能够完成具体实务的全部工作。第一个问题实质上是具体实务究竟满足什么条件才能应用线性规划的方法。一般地说，必须有：一定要满足将目标表为最小化或最大化的要求；一定要有达到目标的不同方法，且必须要有选择的可能性；要求的目标是有限制条件的；必须将约

3、束条件用数学表示为线性等式或线性不等式，并将目标函数化为线性函数。运筹学中的指派问题、最短路问题，最小费用流问题可转化为运输问题或转运问题。设某种物品有 m 个产地 A1，A2，.，Am,各产地的产量分别是 a1，a2，am；有 n 个销地 B1，B2，.，Bn；各销地的销量分别为b1，b2，bn ，假定从 产地 Ai（i=1，2，m） 向销地 Bi（j=1，2，n） 运输单位物品的运价为Cij，若用表示从到的运输量，则在产销平衡条件下，总费用最低的数学模型为minz=i=1

4、mj=1ncijxiji=1mxij=bj，j=1，2，nj=1nxij=ai，i=1，2，mxij0以下是运输问题的数学模型，包含 m×n 个变量，(m+n)个约束方程，其系数矩阵的结构比较松散，且特殊。3. 对一个用单纯形法求解不会产生循环（且能求得最优解）的n个变量m个约束的线性规划问题，估算一下基本计算次数。答：即说明约束系数矩阵为m×n 的矩阵，且满足检验数，如有无穷多的最优解还有存在某个非基变量。其基本计算次数为：4. 简述线性规划求解算法的改进历史。答：针对一般线性规划问题的求解方法（单纯形法 改进单纯形法 对偶单纯形法），到后来特殊的线性规划问题求解算法（表

5、上作业法）5. 证明课本（清华版运筹学（第三版）2.5题。证明：下面用矩阵形式将原问题表示为：（1） max z1=CXAXbX0设其可行解为X1，其对偶问题的最优解为Y1=(y1*，ym*)。（2） max z2=CXAXb+kX0设其可行解为X2，其对偶问题的最优解为Y2。问题1的对偶问题为min =YbYACY0问题2的对偶问题为min =Y(b+k)YACY0由此可见，问题1的对偶问题的约束条件与问题2的对偶问题的约束条件相同，从而问题1的对偶问题的最优解Y1=(y1*，ym*)一定是问题2的对偶问题的可行解。而问题2的对偶问题的最优解为Y2，故Y2b+kY1b+k=Y1b+Y1k=Y

6、1b+i=1mkiyi*。因为原问题与对偶问题的最优函数值相等，故有max z2max z1+i=1mkiyi*6. 有人说：“原问题有多重解（多个最优解），对偶问题一定也有多重解”，此话是否正确？请举一算例。答：这句话是错误的。对偶问题的最优解只有在线性规划中此问题才是对的，如果是非线性规划就不对了。举例：任意一个问题有多重解非线性规划均满足。7. D-W分解算法适合那种类型的线性规划问题？请举一算例。答：D-W分解算法适合按照下列方法分解约束条件和变量：集合1中的约束条件只涉及变量集合1中的变量。集合2中的约束条件只涉及变量集合2中的变量。集合k中的约束条件只涉及变量集合k中的变量。集合k

7、+1中的约束条件可以涉及任何变量。集合k+1中的约束条件称为中心约束条件。适合按照以上方式分解的LP。算例：一家公司在两家工厂生产两种钢材。工厂1每天可以使用12吨煤，工厂2每天可以使用15吨煤；煤不能在两工厂之间运输，工厂1每天可以使用10小时的鼓风炉时间，工厂2每天可以使用4小时的鼓风炉时间，铁矿位于两家工厂之间，每天提供80吨铁，钢材1每吨售价170美元，钢材2每吨售价160美元。所有钢材都送给一个客户；从工厂1运一吨钢材需要80美元，工厂2运一吨钢材需要100美元。假设运输成本是唯一的可变成本，表述并求解一个使该公司利润（收入运输成本）最大的LP。公司的资源要求产品需要的铁（t）需要的

8、煤(t)需要鼓风炉时间(h)工厂1钢材1832工厂1钢材2611工厂2钢材1731工厂2钢材2521x1=工厂1每天生产的钢材1的吨数x2=工厂1每天生产的钢材2的吨数x3=工厂2每天生产的钢材1的吨数x4=工厂2每天生产的钢材2的吨数LP:变量集合1：x1和 x2工厂1 的变量变量集合2：x3和 x4工厂2 的变量约束条件集合1：1和（2）工厂1 的约束条件约束条件集合2：3和（4）工厂2 的约束条件约束条件集合3：（5）工厂1 的约束条件8. 何谓“原始-对偶”单纯形法？请举一算例。答：应用对偶原理求解原始线性规划的一种方法在原始问题单纯形表格上进行对偶处理。线性规划问题：添加松弛变量以后

9、的标准型，再将标准型中灯饰两边乘以-1，则以上问题转化为：然而在有些问题中，我们很容易找到初始基本解，因此使用对偶单纯形法求解线性规划问题是有一定条件的，其条件是： (1) 单纯形表的b列中至少有一个负数. (2) 单纯形表中的基本解都满足最优性检验. 对偶单纯形法与原始单纯形法相比有两个显著的优点： (1) 初始解可以是不可行解，当检验数都非正时，即可进行基的变换，这时不需要引入人工变量，因此简化了计算. 9. 何谓有界变量的线性规划问题？如何求解？请举一算例。答：实际运用中的线性规划问题,其决策变量具有上下界限

10、的限制。至于其求解算法，以先 转化为标准形式的线性规划问题,然后按照单纯形方法进行求解，或者是有界变量单纯形法。以下是一具体算例（基线算法）：列出母表：X1X2X3X4X5RHS2-1000v11110102-1-2018取初始基本可行解（0，0，-1，11，6），初始解x1和x2中都取其对应下界,我们可将x1和x2作为下非基变量，可将x3作为进基，得BL表，X1X2X3X4X5RHS 2-3100v-1v2-1401010-vv106-70018+2vv-4ll其解为-1，2，选取2为旋转主元得到新的BL表：X1X2X3X4X5RHS 1-321200v22v10052121010-v2v1

11、802-3018-vv14lu其对应不等式组的解为2,10，此表已为最优表，最优值max z=10，计算得最优解为4，0，2，4，4。10. 何谓线性规划的逆问题，分别对“最优解的逆线性规划问题”和“对目标函数值的线性规划逆最优值问题”举出算例。答：给定线性规划问题一个可行但非最优的解,要求在某种模的意义下,尽可能少的调整价值向量,使其成为新问题的最优解。最优解的逆线性优化问题算例：对目标函数值的线性规划逆最优值问题算例：11. 对同一优化问题，是否存在决策变量一样但所建模型不一样的情况？请举例；是否存在目标函数中没有决策变量的最优化问题？答：同一优化问题存在决策变量一样但是所建模型不一样的。

12、处理实际问题时，一般没有一个唯一正确的模型，而是有多种不同的方案。建模是一个演进过程，从一个初始模型往往需要不断的完善渐渐演化成一个完整的数学模型。举例：针对港口岸桥调度问题，最终的目标函数，我们可以要求总成本最小，亦可要求所有岸桥总行走里程最短。最终建立的模型不一样。决策变量是建立最优化问题模型三要素之一，故不存在目标函数中没有决策变量的最优化问题。12. 简述建立线性多目标规划的过程，自选一个实际问题，建立模型并用图解法和单纯形法求解。答：主要研究多余一个目标函数的在给定区域上的最优化。即先确定此规划的决策变量，还要引进正、负偏差，以及完善约束条件（绝对约束和目标约束），确定优化因子（优先等级）与权系数，确定目标规划的目标函数，完成最终的线性多目标规划。一个生产问题