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

最优化理论与方法（线性部分）思考题 就你学过的运筹学问题，写出能够建立线性规划模型的问题，并举例（建立模型）。 以下四种食物1、2、3、4，依次售价为50、20、30、80，而我们人体每天需摄取至少500卡路里，6盎司巧克力，10g糖以及8g脂肪，具体成分如下， 饮食的营养价值 食物类型 卡路里 巧克力（盎司） 糖(盎司) 脂肪（盎司） 1.巧克力糖 400 3 2 2 2.巧克力冰淇淋 200 2 2 4 3.可口可乐 150 0 4 1 4.蛋糕 500 0 4 5 要求：建立一个以最小成本满足每天营养需求的线性规划模型。 模型如下： s.t. 举例（说明问题、建立模型）论述线性规划在交通、运输、物流和安全管理中的应用。 答：现在物流业面临的新问题是：?认定所给问题确实是一个线性规划问题；?把它建立起线性数学模型；?并能够完成具体实务的全部工作。第一个问题实质上是具体实务究竟满足什么条件才能应用线性规划的方法。一般地说，必须有：①一定要满足将目标表为最小化或最大化的要求；②一定要有达到目标的不同方法，且必须要有选择的可能性；③要求的目标是有限制条件的；④必须将约束条件用数学表示为线性等式或线性不等式，并将目标函数化为线性函数。运筹学中的指派问题、最短路问题，最小费用流问题可转化为运输问题或转运问题。 设某种物品有?m?个产地 ,各产地的产量分别是?；有?n?个销地?；各销地的销量分别为?，假定从?产地?（i=1，2，?，m）?向销地?（j=1，2，?，n）?运输单位物品的运价为，若用表示从到的运输量，则在产销平衡条件下，总费用最低的数学模型为 以下是运输问题的数学模型，包含 个变量，(m+n)个约束方程，其系数矩阵的结构比较松散，且特殊。 对一个用单纯形法求解不会产生循环（且能求得最优解）的n个变量m个约束的线性规划问题，估算一下基本计算次数。 答：即说明约束系数矩阵为m×n 的矩阵，且满足检验数，如有无穷多的最优解还有存在某个非基变量。其基本计算次数为： 简述线性规划求解算法的改进历史。 答：针对一般线性规划问题的求解方法（单纯形法 → 改进单纯形法 → 对偶单纯形法），到后来特殊的线性规划问题求解算法（表上作业法） 证明课本（清华版运筹学（第三版））2.5题。 证明：下面用矩阵形式将原问题表示为： max 设其可行解为，其对偶问题的最优解为。 （2） max 设其可行解为，其对偶问题的最优解为。 问题1的对偶问题为 min 问题2的对偶问题为 min 由此可见，问题1的对偶问题的约束条件与问题2的对偶问题的约束条件相同，从而问题1的对偶问题的最优解一定是问题2的对偶问题的可行解。 而问题2的对偶问题的最优解为，故。因为原问题与对偶问题的最优函数值相等，故有 有人说：“原问题有多重解（多个最优解），对偶问题一定也有多重解”，此话是否正确？请举一算例。 答：这句话是错误的。对偶问题的最优解只有在线性规划中问题才是对的，如果是非线性规划就不了… 集合k中的约束条件只涉及变量集合k中的变量。 集合k+1中的约束条件可以涉及任何变量。集合k+1中的约束条件称为中心约束条件。适合按照以上方式分解的LP。 算例： 一家公司在两家工厂生产两种钢材。工厂1每天可以使用12吨煤，工厂2每天可以使用15吨煤；煤不能在两工厂之间运输，工厂1每天可以使用10小时的鼓风炉时间，工厂2每天可以使用4小时的鼓风炉时间，铁矿位于两家工厂之间，每天提供80吨铁，钢材1每吨售价170美元，钢材2每吨售价160美元。所有钢材都送给一个客户；从工厂1运一吨钢材需要80美元，工厂2运一吨钢材需要100美元。假设运输成本是唯一的可变成本，表述并求解一个使该公司利润（收入—运输成本）最大的LP。 公司的资源要求 产品 需要的铁（t） 需要的煤(t) 需要鼓风炉时间(h) 工厂1钢材1 8 3 2 工厂1钢材2 6 1 1 工厂2钢材1 7 3 1 工厂2钢材2 5 2 1 =工厂1每天生产的钢材1的吨数 =工厂1每天生产的钢材2的吨数 =工厂2每天生产的钢材1的吨数 =工厂2每天生产的钢材2的吨数 LP: 何谓“原始-对偶”单纯形法？请举一算例。 答：应用对偶原理求解原始线性规划的一种方法——在原始问题单纯形表格上进行对偶处理。 线性规划问题： 添加松弛变量以后的标准型，再将标准型中灯饰两边乘以-1，则以上问题转化为： 然而在有些问题中，我们很容易找到初始基本解，因此使用对偶单纯形法求解线性规划问题是有一定条件的，其条件是：?(1)?单纯形表的b列中至少有一个负数.?(2)?单纯形表中的基本解都满足最优性检验.? 对偶单纯形法与原始单纯形法相比有两个显著的优