CH5-1LP_r 线性规划.ppt

1、1、Chapter 5线性规划、2，5.1线性规划简介、运筹学中应用最广泛的方法之一运筹学、网络计划、整数计划、目标计划和多用途计划都是解决基于线性规划的稀疏资源优化分配的有效方法，从而将成本降至最低1947 DANTZIG职员轮换培训任务分配“单纯形” 1960年“最佳资源利用的经济计算”康托洛维奇和库弗曼斯60-70年代电脑50约束100变量30000约束30000变量，长期历史，4，理论成熟，冯诺依曼和市场营销(广告)牙齿更有名的劳动综合)库存管理(合理的物资库存、停车场大小、设备容量)运输问题财政、会计(预算、贷款、成本分析、投资、证券管理)人事(人员分配、人才评价、工资和奖金决定)

2、在一定程度的人力、财力、资源条件下，如何合理安排利用，确定效益最高的某些任务后，如何最珍惜人、财政、东西，7、A、B后备资源煤1 2 30劳动日3 2 60仓库0 2 24利润40 50，、 原料长度7.4米1.5米，示例合理下料问题，3个茄子示例，12，解决方案：第I种方案哈哈的原料设置为Xi根，minZ=0.1x2 0.2x3 0.3x4 0.8x5，13 Minz=2x11x12 3x13 2x2，追求：5年末总资本最大值，16，分析，17，Xik(I=1，2，5；K=A，B，C，D)第I年的k项目投资资金数，maxz=1.15 x4a 1.40 x2c 1.25 x3b 1.11 x5

3、d，18，5.2线性规划格式，常规，19，标准格式，备注Min z=您可以添加“”的约束条件：线性规划问题标准化方法，21，如max Z=-x1 2x2 3x3，转换为标准型，22，解决方法：x3=x4-X5，变量X6，变量x7相减，Z P1 x1 p2 x2 pn x2 5.3线性规划问题解答的概念假设在标准形式中，等式约束没有不必要的方程(即A的排序为M)牙齿，并且可执行的域D=x|Ax=b，x0=牙齿线性规划问题是不可能的。d称为d的其中一个x的可行解决方案。如果d有x*，cTx* cTx，xD，则x*是最佳解决方案。最佳解，26，基本向量和基本向量，设定P1，p2，pm牙齿A的M个线性

4、无关栏向量，矩阵B=(p1，P2，PM)称为问题(LP)的基础。其中，每一列称为基础向量。bxb nxn=bb XB=B- nxn XB=B- 1b- B- 1n xn，显然，x的格式类似于x=(x1，xm，0，0)T，x1，默认B=(P3 P4 P5)=I可逆N=(P1 P2)，29，确定默认变量是否为x1，x3，x4的默认解，并确定是否为可行解。X=(1，0，3/2，3/2)如果T是，30，(1)有可能的解，线性规划(LP)有可能的解，则必须有基本的可行解。证明x=，p1，p2，pk线性相关，即都具有非零牙齿的数字a1，a2，ak，a1p1 a2p2 akpk=0，LP问题与多个茄子解的关

5、系，31，x (1)=X选择相应的E以获得新的可执行解决方案，因为XJ eaj，xj-eaj(j=1，k)中至少有一个等于0，其他值大于0。问题被证明。否则，重复上述过程，直到与正分量相对应的热向量线性无关为止。32，(2)证明有最优解，是：牙齿最优解。如果X不是默认的可执行解，则两个新的可执行解： x ea，x-ea，相应的目标CTx-ecTa cTx。因此，cTa=0。因此，e 0牙齿足够的时间，x ea、x-ea也是可行的最佳解决方案。根据(1)的证明，可以获得最佳默认可行解决方案。以线性规划(LP)表示，N=50 m n=50 m=20 C5020=4.701013，100000/秒1

6、.309104小时545天，分析，(1)(2)结论，如果仅找到所有基本可行解决方案，则为相应的基本，34，x，y，5.4 LP理论基础，可在标准格式中运行的域D=x|Ax=b，x0通过从凸集，Proof，D中选择x，y，0 1来验证x (1- )y边界如果为I 0，则x(0)可以表示为顶点的凸面组合。因此，CTX(0)=CT(1x(1)2x(2)kx(k)=1 CTX(1)2 CTX，36，扩展结论，如果从线性规划可牙齿域中的多个顶点达到最佳，则因此，CTX=CT (1x (1) 2x (2) MX (m)，=1 CTX (1) 2 CTX (2) mctx (m)，=1z * 2z，(必须从

7、哪个顶点到达)，解决线性规划问题的另一个直接想法：逐个比较凸集顶点。=z*，37，定理线性规划问题的基本可行解与可行域的顶点相对应。其标准为B=(p1 p2pm)，您可以从Ax=b中获得BxB=b。也就是说，如果x1p1 x2p2 xmpm=b，x可以表示为可执行域中两个不同点的凸组合(例如x=u (1-) v)，则u，v表示u=(u1，U2，um)不需要将x=(x1，x2，xm，xn)T设置为顶点，而是Ax=b，x0，只需要描述正分量对应的系数向量线性无关。也就是说，p1，pk线性相关，即y1，yk都不是0牙齿，因此需要输入y1p1 ykpk=0，Y=(Y1，YK，0，0) T。40，注：牙

8、齿性质与前面的性质相结合，可以看出，如果线性规划问题有最优解，就一定能在可行域的顶点实现。测试这些顶点以比较最佳解决方案工作量过大。幸运的是，可实现域中的顶点对应于基本的可实现解决方案。这样我们就可以从基础可行解的角度考虑，以获得最佳解。在数值计算中，即首先基本可行的解决方案是最佳解决方案(判断！)，否则，其他基本可执行解决方案(转换！)，达到目标函数最小的最佳解决方案，41，5.5单纯形法，1947年G.B.Dantzig提出，在当前远视算法人民的基础上进行了许多其他形式的改进，形成了很多变种。简便性、电脑可实施性和完整的理论支持，现在成为了以线性规划为中心的内容。利用基本思想、基本可行解和极点的对应关系，首先求出基本解，然后用一定的策略求出另一基本可行解，降低目标函数值。徐璐其他基本可能解决方案的数量有限(可能字段中的顶点数量有限)，因此在特定条件下，始终可以重复为函数最佳解决方案。42，算法解决的问题，(1)如何获得LP的初始基本可执行解决方案。(2)将基本可行解决方案判断为最佳解决方案的方法。，(3)如何从一个基本可执行解决方案中降低目标函数值，然后重复到默认可执行解决方案，43，5.5.1最优化测试，常见线性规划问题设置格式：min z=c1x1c 2 x2 cnxn s . t . a11x 12 x2 a1 nxn=b1a 21 x1a 22 x2 a2