资源描述：
《线性规划及单纯形法(I)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第一章 线性规划及其单纯形法第一章线性规划及单纯形法第一节线性规划问题及数学模型LinearProgramming,LP1939年苏康托洛维奇和1941年美Hichook在生产组织管理和制定交通运输方案方面研究和应用线性规划，求解方法——解乘数法1947年G.B.Dantzig单纯形法1979年苏哈奇安多项式算法（椭球算法）1984年Karmarkar算法多项式时间算法每次迭代不是从一个顶点出发求改进的顶点，而是使迭代点保持在某个单纯形的内部，因此是一种内点算法。2LP是数学规划的一个重要分支，数学规划着重解决资源的优化配置，一般可以表达成以下两个问题中的一个：（1）当资源给定时，要
2、求完成的任务最多；（2）当任务给定时，要求为完成任务所消耗的资源最少。若上述问题的目标﹑约束都能表达成变量的线性关系，则这类优化问题称LP问题。LP是一种解决在线性约束条件下追求最大或最小的线性目标函数的方法。3一、实例例1生产计划问题(书P8，典型示例)Step1:明确问题，设定决策变量设I、II两种产品的产量分别为x1,x2。Step2:确定约束条件32利润12公斤40原料B16公斤04原料A8台时21设备资源限量III产品4说明：OBJ表示Objective;s.t.表示SubjecttoStep3:给出目标函数Step4:整理数学模型5例2污水处理问题(书P9)设x1﹑x2为
3、工厂1﹑2的日污水处理量。建立该问题的数学模型为：500万m3200万m31.4万m3，800元/万m3o工厂22万m3，1000元/万m3o工厂16二、总结目标函数用决策变量的线性函数来表示。按问题的不同，要求目标函数实现最大化和最小化。线性规划问题（LP问题）的共同特征：每一个问题变量都用一组决策变量（x1,x2,…,xn）表示某一方案，这组决策变量的值代表一个具体方案，这些变量是非负的且在某范围内连续取值。存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。7三、线性规划问题的一般形式8四、两变量线性规划问题的图解法1.线性不等式的几何意义—半平面作出LP问题
4、的可行域作出目标函数的等值线移动等值线到可行域边界得到最优点2.图解法步骤例1（典型示例）：94x1=164x2=12x1+2x2=8x1x2Q6(0,4)Q7(8,0)Q4(0,3)O(0,0)Q2(4,2)Z=2x1+3x2做目标函数2x1+3x2的等值线，与阴影部分的边界相交于Q(4,2)点，表明最优生产计划为：生产I产品4件，生产II产品2件。Q1(4,0)Q3(2,3)Q5(4,3)图解法意义不大，但可直观揭示有关概念。103.LP解的类型有4类：（1）唯一最优解如例1的Q2点。（2）无穷多最优解（多重解）（3）无界解（4）无可行解1104812x1963①③②可行域Z=3
5、64,6此线段上的点均为最优点x2当例1的目标函数变为maxZ=2x1+4x2多重解示例8,312x2可行域不闭合②Z增大方向①x1无界解示例13产生原因：缺少约束条件注意：可行域不闭合不一定就会出现无界解，这要看目标函数的性质。若目标函数是min，则有最优解。无论有无最优解，一定有可行解。14无可行解示例①③④无公共区域(可行域)产生原因：有相互矛盾的约束条件。②x2x1154.图解法的作用LP问题有可行解有最优解唯一解无穷多解无最优解（可行域为无界）无可行解（无解）（1）规律：揭示了线性规划问题有关规律和结论。（2）结论：若LP问题有最优解，则要么最优解唯一（对应其中一个顶点），
6、要么有无穷多最优解（对应其中两个顶点连线上的所有点）。16五、线性规划问题的标准型1.标准型的构成要素（1）目标函数：max（2）约束条件：等式（3）变量约束：非负xj³0（4）资源限量：非负bi³0172.标准型的表示方法（1）解析式18简写的解析式19亦可写成：其中：（2）矩阵式20X—决策变量列向量。b—约束条件右端常数（资源）列向量。C—目标函数价值系数行向量。Am´n—约束条件左端系数矩阵。21（3）向量和矩阵符号式223.非标准型的标准化（1）最小转换成最大y1=f(x)y2=-f(x)xyx*y1*y2*23（2）不等式约束条件转换成等式约束条件（3）变量约束转换24（
7、4）把bi<0转换成bi>025例1可化为26例2化标准型2728六、标准型LP问题的解1.基本概念29303132334x1=164x2=12x1+2x2=8x1x2Q6(0,4)Q7(8,0)Q4(0,3)O(0,0)Q2(4,2)Q1(4,0)Q3(2,3)Q5(4,3)Q7基解x2，x3x5=12x4=－16x1=8Q6基解x1，x3x5=－4x4=16x2=4Q5基解x4，x5x3=－2x2=3x1=4Q4基可行解x1，x5x4=16x3=2x2
