A动画 管理系统工程教学课件第六章：线性规划

基变量的检验数： CB- CB B-1B = 0
C - CB B-1A =（0， CN - CB B-1N ）
定理：若检验数全小于等于零，且某一个非基变量 的检验数为0，则线性规划问题有无穷多最优解。 （无穷多最优解情况）
xmk , mk 0. 证明：某个非基变量 xm k 换入基变量中，得到基可行解 X
•从可行域中某个基可行解（一个顶点） 开始（称为初始基可行解）。
线性规划（2）-单纯形方法
单纯形方法基本思路：
•从可行域中某个基可行解（一个顶点） 开始（称为初始基可行解）。 •如可能，从可行域中求出具有更优目标 函数值的另一个基可行解（另一个顶点）， 以改进初始解。
线性规划（2）-单纯形方法
单纯形方法基本思路：
Z= 9＋2 x1 -（3/4）x5 令新的非基变量（ x1，x5 ）=（0，0）T 得到新的基可行解： x(2)=(0,3,2, 16 , 0) T S2= 9 经济含义：生产乙产品3个，获得利润9 百元。
其中（1）—1/2（3）
这个方案比前方案好，但是否是最优？
这个方案比前方案好，但是否是最优？ 分析： Z= 9＋2 x1 -（3/4）x5 非基变量x1系数仍为正数，确定x1为换 入变量。在保证正消去系统的情况下， 确定x3为换出变量。得到新的消去系统：
•从可行域中某个基可行解（一个顶点） 开始（称为初始基可行解）。 •如可能，从可行域中求出具有更优目标 函数值的另一个基可行解（另一个顶点）， 以改进初始解。
•继续寻找更优的基可行解，进一步改进 目标函数值。当某一个基可行解不能再改 善时，该解就是最优解。
第三节
线性规划-单纯形方法
单纯形方法基本思路：
增加单位产品乙（x2）比甲对目标函数 的贡献大（检验数最大），把非基变量 x2换成基变量，称x2为换入基变量，而 把基变量x5换成非基变量，称x5为换出 基变量。 （在选择出基变量时，一定保证消去系 统为正消去系统）（最小比值原则）

约束条件为：
8 25 x1 8 15 x2 1800 8 25 x 1800 1 8 15 x2 1800 x1 0, x2 0
6
线性规划模型：
min z 40 x1 36 x2
5 x1 3 x2 45 x 9 1 s.t. x2 15 x1 0, x2 0
2
两个引例 问题一 ： 任务分配问题：某车间有甲、乙两台机床，可用
于加工三种工件.假定这两台车床的可用台时数分别为800和 900，三种工件的数量分别为400、600和500，且已知用二种 不同车床加工单位数量不同工件所需的台时数和加工费用如 下表.问怎样分配车床的加工任务，才能既满足加工工件的要 求，又使加工费用最低？
注：lingo的灵敏度分析需要激活（系统默认是不激活的）为了激活灵敏性分析， 运行LINGO|Options…，选择General Solver Tab， 在Dual Computations列表 框中，选择Prices and Ranges选项。 确认并运行LINGO|Ranges或快捷键 ctrl+R.
在LINGO模型 min 13* x1 9* x 2 10* x3 11* x 4 12* x5 8* x6; 窗口输入： x1 x 4 400;
x 2 x5 600; x3 x6 500; 0.4* x1 1.1* x 2 x3 800; 0.5* x 4 1.2* x5 1.3* x6 900;
Cost
X1 X2 X3 X4 X5 X6 Row Price
影子价格
Slack or Surplus
1 2 3 4 5 6
13800.00 0.000000 0.000000 0.000000 140.0000 50.00000

④根据 max（σj>0）=σk 确定xk为换入变量；根据θ 规则 θ＝min{b'i/a'ik｜1≤i≤m, a'ik>0}＝b'l/a'lk 确定相应的换出变量，并得到中心元素a'lk。转⑤。
⑤以a‘lk为枢轴元素进行转轴运算，得到新的单纯形 表。转②.
用单纯行法求解线性规划问题后，应回答下面几 个问题：
x1, x2, , xn≥0
其中，bi≥0 (i=1,2,,m)
不符合标准型的几个方面：
⑴目令标z=函-z数,变为为minmza=xcz1x=1+-cc12xx12-+c2x2+-cnxn-cnxn ⑵约束条件为 a11x1+a12x2++a1nxn≤b1
加入非a1负1x1变+a量12xx2n++1，+称a为1nx松n+弛xn+变1=量b1，有 ⑶约束条件为 a11x1+a12x2++a1nxn≥b1
am1x1 am2 x2 amnxn (, )bm x1, x2 , xn 0
1.1 线性规划问题及其数学模型
1.1.2 图解法
max z 2x1 3x2 x2
x2
x1 2 x2 8
4 x1 16
4 x2 12
x1 , x2 0
x1
x1
唯一最优解
无穷多最优解
线性规划问题
如果有最优解,则最
Min z=1000x1+800x2
(2-x1)/500 ≤0.002 [0.8(2-x1)+1.4-x2]/700
≤0.002
工厂各应处理多少污水才能使处理 x1≤2, x2≤1.4

第3页
生产计划问题
某工厂用三种原料生产三种产品，已知的条件如表 2.1.1所示，试制订总利润最大的生产计划
单位产品所需原 产品 料数量（公斤） Q1
产品 Q2
产品 原料可用量 Q3 （公斤/日）
原料P1
2
3
0 1500
原料P2
0
2
4
800
原料P3
3 2 5 2000
单位产品的利润 3
5
4
（千元）
第4页
剩余变量
第18页
不等式变不等式
a i1 x 1 a i 2 x 2 a in x n b i
a i1 x 1 a i 2 x 2 a in x n b i
或
a i1 x 1 a i 2 x 2 a in x n b i
a i1 x 1 a i 2 x 2 a in x n b i
最 优 解 （ 1， 4）
2x1 x2 2 x1 2x2 2
x1 x2 5
第24页
注释
可能出现的情况：
可行域是空集 可行域无界无最优解 最优解存在且唯一，则一定在顶点上达到 最优解存在且不唯一，一定存在顶点是最优解
第25页
可行域的几何结构
基本假设 凸集 可行域的凸性
第26页
中运 筹 帷 幄 之
运筹学课件
线性规划
Linear Programming
外决 胜 千 里 之
第1页
线性规划
线性规划问题 可行区域与基本可行解 单纯形算法 初始可行解 对偶理论 灵敏度分析 计算软件 案例分析
第2页
线性规划问题
线性规划实例
生产计划问题 运输问题
线性规划模型
一般形式 规范形式 标准形式 形式转换 概念