第1讲线性规划及单纯形法VIP免费

1第1讲线性规划及单纯形法山东轻工业学院数理学院李彬E-mail:ribbenlee@126.comtelephonenumber:13698622129.2运筹帷幄之中决胜千里之外线性规划LinearProgramming数学建模课件.3•§1线性规划问题及模型•§2图解法•§3单纯形方法•§4线性规划应用举例分析.4§1问题的提出例1.某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：问题：工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多？线性规划模型：目标函数：Maxz=50x1+100x2约束条件：s.t.x1+x2≤3002x1+x2≤400x2≤250x1,x2≥0ⅠⅡ资源限制设备11300台时原料A21400千克原料B01250千克单位产品获利50元100元.5线性规划的组成要素：目标函数MaxF或MinF约束条件s.t.(subjectto)满足于决策变量用符号来表示可控制的因素建模步骤1.理解要解决的问题，了解解题的目标和条件；2.定义决策变量（x1，x2，…，xn），每一组值表示一个方案；3.用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标；4.用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件。.6一般形式112211221122max;1,2,...,;1,...,..0;1,2,...,;1,...,nniiinniiiinnijjzcxcxcxaxaxaxbipaxaxaxbipmstxjqxjqn无限制目标函数约束条件.7可以看出，线性规划的标准形式有如下四个特点：-目标最大化；-约束为等式；-决策变量均非负；-右端项非负。.8注释njxj,...,2,1;为待定的决策变量，12(,,,)Tncccc为价值向量，njcj,...,2,1;为价值系数，12(,,...,)Tmbbbb为右端向量，矩阵为约束(系数)矩阵。mnmmnnaaaaaaaaaA212222111211.9规范形式max..0cxAxbstx.10标准形式max..0cxAxbstx.11概念可行解（或可行点）：满足所有约束条件的向量),,(21nxxxx可行集（或可行域）：所有的可行解的全体{,0}DxAxbx最优解：在可行域中目标函数值最大（或最小）的可行解，最优解的全体称为最优解集合{,OxDcxcyyD}最优值：最优解的目标函数值Oxxcv,.12模型转换令自由变量jjjxxx，其中jjxx,为非负变量求最大可以等价成求负的最小xcxcminmax目标转换变量转换.13约束转换不等式变等式不等式变不等式ininiibxaxaxa2211ininiibxaxaxa2211ininiibxaxaxa2211等式变不等式.14不等式变等式ininiibxaxaxa22110,2211iiininiisbsxaxaxa或ininiibxaxaxa22110,2211iiininiisbsxaxaxa松弛变量剩余变量.15不等式变不等式ininiibxaxaxa2211ininiibxaxaxa2211或ininiibxaxaxa2211ininiibxaxaxa2211.16例1把问题转化为标准形式121212121min2222..50zxxxxxxstxxx134134513461347max()2()22()2..()50;1,3,4,5,6,7izxxxxxxxxxxxstxxxxxi.17•对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。下面通过例2详细讲解其方法。§2图解法例2.目标函数：Maxz=50x1+100x2约束条件：s.t.x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E).18（1）画出线性规划问题的可行域，如图所示。x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400图1.19（2）目标函数z=50x1+100x2，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。得到最优解：x1=50，x2=250，最优目标值z=27500x1x2z=20000=50x1+100x2图2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE.20图解法步骤在平面上建立直角坐标系；图示约束条件；找出可行域；图示目标函数和寻找最优解。.21例3某公司由于生产需要，共需要A，B两种原料至少350吨（A，B两种材料有一定替代性），其中A...