运筹学线性规划问题与图解法.doc

《运筹学线性规划问题与图解法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运筹学线性规划问题与图解法线性规划图解法§2.1 图解法 图解法不是解线性规划的主要方法只是用于说明线性规划解的性质和特点。只能解两个变量问题。（用图解法求解线性规划不需要化成标准型）图解法的步骤：1、约束区域的确定2、目标函数等值线3、平移目标函数等值线求最优值线性规划解的几种可能情况1、唯一最优解2、无穷多最优解3、无可行解4、无有限最优解无界解有唯一解例1：maxz2x13x2x2s.t.x12x2≤84x1≤16x1x2≥0可行域画图步骤：1、约束区域的确定目标函数2、目标函数等值线42等值线3、平移目标函数等值线求最优值z14x1有无穷多解例2maxz2x14x2x2s.t.

2、x12x2≤8x12x284x2≤123x1≤12x1x2≥04x212Q1线段Q1Q2上的任意点都是最优解Q23x112x1x2无可行解例3：maxz3x12x22x1x22s.t3x14x212xx012约束条件围不成区域x1又称矛盾方程无有限最优解无界解x2例4：maxz4x13x2-3x12x2≤6s.t.-x13x2≥18x1x2≥0-3x12x26x1线性规划的几何特性： 线性规划问题若有最优解一定在其可行域的顶点达到；唯一最优解必在一个顶点达到或无穷多最优解至少在两个顶点达到；无解可行域为空集或目标函数无有限极值。图解法得出线性规划问题解的几种情况解的几种情况约束条件图形

3、特点方程特点唯一解一般围成有限区域最优值只在一个顶点达到无穷多解在围成的区域边界上至少目标和某一约束有两个顶点处达到最优值方程成比例无可行解无围不成区域有矛盾方程解无界解无解围成无界区域且无有限缺少一必要条件最优值的方程复习线性代数内容:列向量xx1，x2，…，xm）T为m维列向量。xRm线性相关一组向量v1…vn如果有一组不全为零的系数α1…αn使得:α1v1…αnvn0则称v1…vn是线性相关的.线性无关一组向量v1…vn如果对于任何数α1…αn若要满足:α1v1…αnvn0则必有系数α1…αn0全为零则称v1…vn线性无关线性独立.矩阵A的秩设A为一个m×n阶矩阵m0的数乘（2）

4、式在分别与（1）相加和相减，这样得到x1-μα1P1x2-μα2P2…xm-μαmPmbx1μα1P1x2μα2P2…xmμαmPmb令X1x1-μα1x2-μα2…xm-μαm0…0X2x1μα1x2μα2…xmμαm0…0当μ充分小时可保证xi±μαi≥0i12…m即X1X2是可行解。11由X1X2可以得到X2X12X2即X是X1X2连线的中心。所以X不是可行域D的顶点.必要性（基可行解顶点，用反证法）：X不是可行域的顶点故可在可行域内找到两个不同的点x1x2，使得Xx11-x20