单纯形讲稿.ppt

第一章　线性规划与单纯形法;本章学习目的和要求;主要研究目的;第一节　线性规划的基本概念;　　　产品 单位消耗 原料;解：设P、Q的产量分别为x1，x2，则问题的模型为;【例1-2】 某公司打算利用甲、乙、丙3种原料配置一种新型保健饮料，已知每千克原料中两种主要保健成分A，B的含量及原料单价如表1-2所示。;　　解：设每千克饮料中原料甲，乙，丙的投入量分为x1，x2，x3千克，则问题的模型为：;　【例1-3】 A1，A2是两个粮库，每月分别可调出粮食30吨与40吨，三个粮店B1，B2，B3每月的需求量分别为20吨，25吨与18吨。粮库与粮店之间每吨粮食的运费如下表1-3所示（单位：元/吨）。;解：设从粮库Ai到粮店Bj的调运量为xij，i=1，2，j=1，2，3，则问题的模型为：;　　上述三个问题属于同一类型的决策优化问题，它们具有下列共同特点： （1）每个行动方案可用一组变量（x1，…，xn）的值表示，这些变量一般取非负值； （2）变量的变化要受某些限制，这些限制条件用一些线性等式或不等式表示； （3）有一个需要优化的目标，它也是变量的线性函数。 　　　具备以上三个特点的数学模型称为线性规划（Linear Programming，简记为LP）。 ;实际问题中线性的含义;　　线性规划的一般形式为：;　　采用求和符号Σ，线性规划的一般形式可以简写为：;用向量形式可表示为：;二、图解法 ;【例1-4】 求下列问题的最优解。;（1）确定问题的可行域R。;（2）分析目标函数Z的等值线平行移动与Z值的关系，确定最优解的位置。;（3）计算最优解。;线性规划问题求解的几种可能结局：;3.无界解;4.无解或无可行解;图解法得到的启示;第二节 线性规划的标准形式和解的性质 ;线性规划标准形式的特点： 1. 约束条件全部是等式 2. 目标函数限定求最大值 ;变换一般LP为标准形式的方法： （1）如果原问题目标函数求极小值： ;例：把LP问题 ;解;例、将下列线性规划模型化为标准型; 化为标准形式;线性规划可行解得概念;单位矩阵的介绍;　　设系数矩阵A的秩是m，即A的m个行向量是线 性无关的。若B是A的m阶子阵，称B为问题的 一个基。设B=（　　，　，…，　），称对应的 变量　，　，…，　 为基变量，其它的变量称为 非基变量。令非基变量等于0，从方程组可以唯一 解出基变量的值，从而得到方程组的一个解，称 为基本解；如果它的各个分量非负，即它同时又 是可行解，则称之为基可行解，对应的基称为可行基。 　　可行解是约束方程组的解并且满足非负条件； 基本解是约束方程组具有特定性质的解，它至多有m 个非0分量，但未必满足非负性。基可行解同时具有 两者的性质。 ;【例】;第三节 单纯形法 （重点）;【例】 ;　　从目标函数z=2x1+5x2来看，如果x1或x2成为基变量（简称入基），变成正值，则z值将会上升。由于x2系数更大，引入x2更有利于z的上升，故首先选择x2入基，x1仍然保持是非基变量。此时约束方程组实际成为： ;　　把约束方程组（1）转化为对新基变量x2,x3,x4的解出形式： ;由（2）第三式得到x2=3－ x5，代入z的表达式，得到 ?　z=2x1+5x2=2x1+5（3－　x5）=2x1－　x5+15 　　x1的系数为正，故引入x1，x5保持为0 由　　　　　　　　　　知x1≤min｛2/1，14/5，—｝=2 　　　取x1=2，则x3=0，x3退出基。然后把方程组（2）变换为对x1，x2，x4的解出形式： ;由（3）的第一式得到x1=2－x3+ x5代入（2）中。 ?z=2（2－x3+　x5）－　x5+15=－2x3－　x5+19 　　此式表明z≤19，而当X=X3时，z=19，因此X3是问题最优解，z的最优值是19万元。 　 总结： 　　　单纯形法是一种迭代算法，每步迭代包括下列环节： 　　　首先判定当前基可行解是否最优，若是，则结束；否则，先确定换入变量，再确定换出变量，最后把方程组转化为对新基变量的解出形式，得到新的基可行解。 ;二、 单纯形法要点和单纯形表 ;　　　假定所有b1，…bm≥0。显然问题有基可行解X1=(b1,b2,…,bm,0,…,0)T，相应目标函数值　　　　　　。 　　　　　　　　　　　i=（1，2，…，m） ;基变量的检验数永远为0。 非基变量xj的检验数σj是引入xj一个单位时目标函数z的改变量，只有σj0时，方值得让xj入基。 ;2.单纯形表 ;总结;(1)基变量的检验数永远为0。 (2)非基变量xj的检验数σj是引入xj一个单位时目标函数z的改变量，只有σj0时，方值得让xj入基。 (3)每个变量xj（包括基变量在内）的检验数σj，等于cj减去基变量价值系数行矩阵元素与表中xj的系数列