运筹学线性规划图解法

j 1
证明：线性规划 max z =CX s.t. AX=b X≥0 设x(1)≠x(2)为D内任取两点，则Ax(1)=b,Ax(2)=b,x(1) ≥ 0, x(2) ≥ 0,令x为线段x(1) ,x(2)上任一点,既有 x=μ x(1)+(1-μ )x(2) (0≤μ ≤1) 则 Ax=A[μ x(1) + (1-μ ) x(2)] (0≤μ ≤1) =μ Ax(1)+Ax(2)-μ Ax(2) =μ b+b–μ b=b 又因为 x(1) ≥ 0, x(2) ≥ 0, 0≤μ ≤1 所以 x ≥ 0 即 x∈D 证毕
§2.2 线性规划问题解的概念
设线性规划的标准形式： max z=Σ cjxj (1) s.t.Σ aijxj=bi i=1,2,…,m (2) xj≥0 j=1,2,…,n (3) 可行域：由约束条件(2)、(3)所围成的区域； 可行解：满足(2)、(3)条件的解X=(x1，x2，…，xn)T为可行解； 基：设A是约束条件方程组的m×n维系数矩阵,其秩为m，B是A中 m×m阶非奇异子矩阵，则称B为线性规划问题的一个基。 设
B=
a11 a21 … am1
a12 … a1m a22 … a2m … … am2 …amm
=(p1,p2, …,pm)
基向量、非基向量、基变量、非基变量： 称pj(j=1,2,…,m）为基向量，其余称为非基向量；与基 向量pj(j=1,2,…,m）对应的xj称为基变量，其全体写成 XB=（x1，x2，…，xm）T；否则称为非基变量，其全体经 常写成XN。 基解：对给定基B,设XB是对应于这个基的基变量 XB=(x1，x2，…，xm)T； 令非基变量xm+1=xm+2=…=xn=0， 由（2）式得出的解X=（x1，x2，…，xm，0，…，0）T 称为基解。 基可行解：所有决策变量满足非负条件(xj ≥0)的基解, 称作基可行解。 可行基：基可行解所对应的基底称为可行基。
•x1
• x1
• x2 • x2
凸集性质:
凸组合：设x(1),x(2),…,x(k)是n维空间中的k个点,若存在 μ 1,μ 2,…,μ k (0≤μ i≤1 i=1,2,…k 且Σ μ i=1)使 x=μ 1x(1)+μ 2x(2)+…+μ kx(k)成立,则称 x为 x(1),x(2),…,x(k) 的凸组合。 特别，平面上的两点x(1),x(2),连线上任一点x的坐标为 x=α x(1)+(1-α )x(2) 0≤α ≤1. 顶点：设K为凸集,x∈K并且x不能用K内不同的两点x(1),x(2) (x≠x(1),x≠x(2))的凸组合表示,则称x为顶点. 定理1: 线性规划问题若存在可行域,则其必是凸集，亦即 n D={X∣AX=b}={X∣ Pj x j b , xj≥0 }是凸集。
图解法得出线性规划问题解的几种情况
解的几种情况约束条件图形特点 唯一解 一般围成有限区域,最优值 只在一个顶点达到 无穷多解 在围成的区域边界上,至少 有两个顶点处达到最优值 无可行解 ( 无 围不成区域 解) 无界解(无解) 围成无界区域 , 且无有限 最优值 方程特点
目标和某一约束 方程成比例 有矛盾方程
缺少一必要条件 的方程
复习线性代数内容:
列向量 x=(x1，x2，…，xm）T为m维列向量。xRm 线性相关 一组向量v1,…,vn,如果有一组不全为零的系数 α 1, …,α n,使得: α 1 v1+…+α nvn=0 则称v1,…,vn 是线性相关的. 线性无关 一组向量v1,…,vn,如果对于任何数α 1,…,α n, 若要满足: α 1 v1+…+α nvn=0 ,则必有系数 α 1=…=α n=0,(全为零)则称v1,…,vn线性无关(线 性独立). 矩阵A的秩 设A为一个m×n阶矩阵(m<n)若矩阵中最大线性 无关列向量个数为k,则称矩阵A的秩数为k,记 为秩(A)=k.
引理1.线性规划问题的可行解X为基本可行解的充分 必要条件是X的正分量所对应的系数列向量是线性独立的. 证明: 必要性：已知 X 为线性规划的基本可行解，要证 X 的 正分量所对应的系数列向量线性独立。 因为X为基本解，由定义，其非零分量所对应的系数 列向量线性独立；又因为X还是可行解，从而其非零分量 全为正。
•无有限最优解(无界解) 例4：
x2
max z=4x1+3x2
s.t. -3x1+2x2≤6 -x1+3x2≥18 x1, x2 ≥ 0
-3x1+2x2=6
线性规划的几何特性： 线性规划问题若有最优解,一定在其可行域的顶点达到；
唯一最优解必在一个顶点达到 或无穷多最优解至少在两
个顶点达到；
无解(可行域为空集或目标函数无有限极值)。
解的关系：
可行解 基可 行解
基解
非可 行解
注： 基解的数目最多为Cnm个。基可行解的数目一般小于 基解的数目; 基解中非零分量的个数小于m个时，基解称为退化解。 以后在不声明的情况下，均假设不出现退化情况。
§2.3 线性规划问题的几何意义
凸集 : （直观）图形中连接任意两点的直线全部都在图 形区域内,称此图形是凸的.严格数学定义: 设Ω 为一n维 欧 氏 空 间 的 点 集 , 若 任 意 两 点 x1,x2∈Ω , 有 x=λ x1+(1λ )x2∈Ω ，其中λ ∈[0，1]，则称Ω 为凸集。
x2 x1+2x2=8
4x2=12
线段Q1Q2上的任意点都是最优解
Q1
Q2 x1
3x1=12Biblioteka x2•无可行解 例3：
max z 3x1 2 x2 2 x1 x2 2 s.t 3x1 4 x2 12 x , x 0 1 2
约束条件围不成区域 (又称矛盾方程)
x1
•有唯一解 例1： max z=2x1+ 3x2 s.t. x1+2x2≤8 4x1≤16 x1,x2≥0 画图步骤： 1、约束区域的确定 2、目标函数等值线 3、平移目标函数等值线求最优值 x2
可行域
(4,2) z=14
目标函数 等值线
x1
•有无穷多解
例2 max z =2x1+4x2 s.t. x1+2x2≤8 4x2 ≤ 12 3x1 ≤12 x1, x2 ≥0