运筹学-1复习.doc

MATLAB 基础及在运筹学中的应用 1 第1 章线性规划当数学规划问题的目标函数( 对要达到的目标的数学描述) 和约束条件( 资源的限制等) 中出现的所有函数都是线性函数的时候称为线性规划。 一般线性规划问题的数学模型线性规划问题的一般形式为: Max Zcxcxcx nn???? 1122?( 或求最小)st axaxaxbbb axaxaxbbb axaxaxbbb xxx nnnnmm mn nmmm n.. ,),),),,, ( ( ( 1111221111 2112222222 112212000 ????????????????????????????????或或或向量形式引进向量??? 21?c ,?? Tmbbb? 21?b ,?? Tnxxx? 21?x ,?? Tnjjjjaaa? 21?P 线性规划问题可以改写为向量形式 cx????? nnxcxcxcZ Max ? 2211??? n1j..bxP jjts (或bb??, )0?x 向量- 矩阵形式再引进矩阵????????????? mn mm n naaa aaa aaaA??????? 21 222 21 112 11 线性规划问题可以表示为向量- 矩阵形式: cx?Z Max ?x (或bb??, )0?x MATLAB 基础及在运筹学中的应用 2 应用单纯形法的标准形式:nnxcxcxcZ Max ????? 2211st axaxaxbaxaxaxbaxaxaxbxxx nnnnmm mn nmn..,,, 11112211 21122222 112212000 ??????????????????????????在标准形式中约束条件都是等式。向量- 矩阵形式的标准形式是: cx?Z Max ?x0?x 3. 非标准线性规划问题的标准化(1 )如果某个约束为: axaxaxb kk knnk1122?????可以在不等式的左边增加一个变量 x nk??0 ,则约束可改写为: axaxaxxb kk knnnkk 1122???????(2 )如果某个约束为: axaxaxb hhhnnh 1122?????在不等式的左边减去一个变量 x nh??0 ,则约束可改写为: axaxaxxb hhhnnnhh 1122???????这里引进的变量 knx ?和hnx ?称为松弛变量。(3 )如果问题是求最小值,则引进???ZZ ,化为求最大问题。(4 )如果对某变量 x j 没有非负约束,则引进两个非负变量??x j0 ,???x j0 ,令 xxx jjj?????代入约束条件中。 4. 线性规划问题的解 MATLAB 基础及在运筹学中的应用 3 可行解: 线性规划的满足所有约束条件的解称为可行解, 全部可行解的集合称为可行域。最优解: 使得目标函数达到最大的可行解称为最优解。 线性规划问题的图解法图解法是一种简单直观的解线性规划问题的方法。它适用于含有两个变量的模型。虽然实际的线性规划问题很少只有两个变量的情况,但它有助于理解线性规划问题的解的基本性质,这种解法的思想有助于学****其它解法。因此,学好图解法是学****线性规划的基础。下面以例 1-1 中的生产计划问题为例介绍图解法。【例 1-4 】用图解法解例 1-1 中的生产计划问题: 2132 max xxz??????????????????0, 12 4 16 4 82 12 22.. 21 2 1 21 21xx x x xx xxts 图解法的步骤: 第一步: 确定可行域,即确定满足所有约束条件的点的图形范围。为此需分析约束条件的几何意义。将),( 21xx 看做 21,xx 平面上的点, 那么变量的非负约束 0, 21?xx , 表示第一象限的所有点。下面分析约束条件 12 22 21??xx ,直线 12 22 21??xx 将21,xx 平面分为两个部分直线下面的点 12 22 21??xx ,直线上面的点 12 22 21??xx ,因此约束条件 12 22 21??xx ,0, 21?xx 表示图 1-2 中阴影三角形中的所有点。以此类推, 4 项约束可以与 1x 轴, 2x 轴构成 4 个这样的三角形, 它们在 21,xx 平面上的交集称为可行解区域, 简称可行域。由图 1-3 的阴影部分给出。 MATLAB 基础及在运筹学中的应用 4 图 1-2 例 1-1 的可行域 0 1 2 3 4 5 6 7 8 -2 -1 0 1 2 3 4 5 6 x 1 x 2 2x 1+ 2x 2= 12 4x 2= 12 4x 1= 16 x 1+ 2x 2= 8 图 1-3 例 1-1 的可行解 MATLAB 基础及在运筹学中的