线性规划PPT

所有可行解的集合称为可行域。
最优解 使目标函数达到最大的可行解 称为最优解。
基本解 对于有n个变量、m个约束方程的标准 型线性规划问题，取其m个变量。若这些变量在约 束方程中的系数列向量线性无关，则它们组成一组 基变量。确定了一组基变量后，其它n-m个变量称 为非基变量。
令非基变量都为 0 ，解约束方程，可唯一得到 基变量的值，从而得到一个满足约束方程的解，称 为基本解。由此可见，一个基本解的非零分量个数 不超过m个。
量，记为xN。对线性规划（**） 取定一个基矩阵B, 令其非
基变量xN=0， 可以唯一的解出xB, xB=B-1b。 这样得到的点 x=(B-1 b,0)称为（**）的一个基本解。为了叙述方便，这里
我们将xB放在了前面， 其实它的位置可以是任意的， 这并
不影响问题的实质。显然基本解不一定是可行解，当一个 基本解同时还是可行解时（即B-1 b≥0），称之为线性规划 问题（**）的一个基本可行解，进而若B-1 b＞0，则称 x=(B-1 b,0)为（**）的一个非退化的基本可行解，并称B为 一组非退化的可行基。由于基矩阵最多只有Cnm 种不同的取 法，即使A的任意m列均线性无关，且对应的基本解均可行， (**)最多也只有C nm个不同的基本可行解。
污水的含量应不大于0.2%。而工 Min z=1000x1+800x2
厂1和工厂2处理污水的成本分别为 (2-x1)/500 ≤0.002
1000元/万m3和800元/万m3。问两 工厂各应处理多少污水才能使处理 污水的总费用最低？
[0.8(2-x1)+1.4-x2]/700 ≤0.002
x1≤2, x2≤1.4
已知生产单位产品所需的设备台时和原料A、B的消
耗量如下表。 该工厂每生产一件
ⅠⅡ
产品Ⅰ可获利2元，每生产一件产 品Ⅱ可获利3元，问应如何安排生 产计划能使该厂获利最多？
设备 1 原料 A 4 原料 B 0
2 8 台时 0 16kg 4 12kg
这个问题可以用下面的数
学模型来描述，设计划期内产 品Ⅰ、Ⅱ的产量分别为x1，x2， 可获利润用z表示，则有：
x1, x2≥0
1.1.1 问题的提出(三)
以上两例都有一些共 同的特征：
⑴用一组变量表示某个 方案，一般这些变量取
值是非负的。
⑵存在一定的约束条件， 可以用线性等式或线性
不等式来表示。
⑶都有一个要达到的目 标，可以用决策变量的
线性函数来表示。
满足以上条件的数学 模型称为线性规划模型。 线性规划模型的一般形式 如下：
基本可行解 满足非负条件的基本解称为基本 可行解。
基本可行解既是基本解、又是可行解，它对 应于线性规划问题可行域的顶点。
考察（**）， 取出A的m个线性无关的列，这些列构成A的
一个m阶非奇异子矩阵B， 称B为A的一个基矩阵。 A的其
余n-m列构成一个m× (n-m)矩阵N。称对应于B的列的变量
为基变量（共m个）， 记它们为xB。 其余变量称为非基变
线性规划
1.1 线性规划问题及其数学模型 1.1.1 问题的提出 1.1.2 图解法 1.1.3 线性规划问题的标准型
1.2 线性规划问题的求解——单纯形法 1.2.1 基本概念 1.2.2 单纯形法
1.1 线性规划问题及其数学模型
1.1.1 问题的提出（一）
例 某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，
⑶约束条件为 a11x1+a12x2++a1nxn≥b1 减去非a1负1x1变+a量12xx2n++1，+称a为1nx剩n -余xn变+1=量b1，有
⑷变量xj无约束。
令xj= xj - xj，对模型中的进行变量代换。
1.2 线性规划问题的求解——单纯形法 1.2.1 基本概念
可行解 满足约束条件（包括非负条 件）的一组变量值，称可行解。
两个定理
定理1 （基本可行解与极点的等价定理）设A为一个秩为m的 m×n矩阵(n>m),b为m维列向量，b≥0，记R为可行域。 则x为R的极点的充分必要条件为
x是
Ax b
不符合标准型的几种情况：
⑴目标函数为 min z=c1x1+c2x2++cnxn 令z=-z ,变为 max z= -c1x1- c2x2- -cnxn
⑵约束条件为 a11x1+a12x2++a1nxn≤b1 加入非a1负1x1变+a量12xx2n++1，+称a为1nx松n+弛xn+变1=量b1，有
Max Z=2x1+3x2 x1+2x2≤8 4x1 ≤16
4x2≤12 x1, x2≥0
1.1.1 问题的提出(二)
例 靠近某河流有两个化工厂，
流经第一化工厂的河流流量为每天
500万m3，两工厂之间有一条流量
为每天200万m3的支流（见图）。
第污自二水然第化从净一工工化化厂厂 。工每根1厂流天据每到排环天工放保排厂污要放2水求前污，会水1.河有42万万水20mm%中33。，每和天x2万设分m工别3厂，处1则理和有污工：水厂x21
a11x1+a12x2++a1nxn=b1
a21x1+a22x2++a2nxn=b2
(*)
am1x1+am2x2++amnxn=bm
x1, x2, , xn≥0
其中，bi≥0 (i=1,2,,m)
或者更简洁的，利用矩阵与向量记为
max z CT x
s.t. Ax b
(**)
x0
其中C和x为n维列向量，b为m维列向量， b≥0,A为m×n矩阵，m<n且rank(A)=m
s.t. x1 2 x2 8
x2
x2
4 x1 16
4 x2 12
x1, x2 0
线性规划问题 如果有最优解,则最 优解一定在可行域 的边界上取得,特别 地,一定可在可行域 的顶点上取得.
x1
x1
唯一最优解
无穷多最优解
解Байду номын сангаас界
无可行解
1.1.3 线性规划问题的标准型
线性规划问题的标准型
max z=c1x1+c2x2++cnxn
max(min)z c1x1 c2 x2 cn xn a11x1 a12 x2 a1n xn (, )b1 a21x1 a22 x2 a2n xn (, )b2 am1x1 am2 x2 amn xn (, )bm x1, x2 , xn 0
1.1.2图解法
max z 2x1 3x2