运筹学复习课1.ppt

运筹学复习课一

;第一章线性规划和单纯形法;一、线性规划的三个要素;例1资源利用问题;是问题中要确定的未知量，说明规划中的用数量表示的方案、措施，可由决策者决定和控制。;第2步--定义目标函数;第3步--表示约束条件;解：用变量x1和x2分别表示光华食品厂生产饼干I和饼干II的数量，z为利润。

目标函数

限制条件

;二、线性规划问题的标准形式;⑴.目标函数的转换;非标准形式转化为标准形式的方法;x1+2x2+x3=30

3x1+2x2+x4=60

2x2+x5=24

x1,…,x5?0;例2:;;3x1+2x2?8

x1–4x2?14

X1无符号限制，x2?0;例4：课本〔13页〕例1.1-5、课本〔74页〕5;线性规划问题的图解法;

可行解：凡满足全部约束条件的决策变量的取值称为线性规划的可行解。

可行域：全部可行解所组成的集合称为线性规划的可行域。

最优解：使目标函数到达最优值的可行解称为线性规划的最优解

最优值：在最大化问题中是指Z的最大值，在最小化问题中是指Z的最小值。

一个LP问题假设存在最优解，那么称它有解；否那么称之为无解。;1、判别线性规划问题的求解结局；

2、是在存在最优解的条件下，找出问题的最优解。;例1、maxZ=40x1+50x2;(1)、建立坐标系;(3)、求最优解;线性规划问题的图解法;2.1线性规划问题的图解法;2.1线性规划问题的图解法;线性规划解的情况;唯一解

无穷多解

无有限最优解

无可行解;唯一解

无穷多解

无有限最优解

无可行解;*;*;对集合E中任意两个点其连线上的所有点都是集合E中的点，那么E为凸集。

;设线性规划的标准型

minZ=CX〔1.1〕

AX=b〔1.2〕

X≥0〔1.3〕

式中A是m×n矩阵，m≤n并且r〔A〕=m;【例1】线性规划;B

基;根本解：对某一确定的基B，令非基变量等于零，利用AX=b解出基变量，两者搭配构成基Ｂ的根本解。;根本可行解(basisfeasiblesolution)假设根本解满足非负条件那么称为是根本可行解〔也称???可行解〕。;单纯形法的计算步骤;单纯形法的步骤;迭代：(接上一页〕

(步骤3):通过初等行变换〔一行乘以或者除以一个非零常数；一行加上或者减去另一行的倍数〕，按照高斯消去法，在当前表的下方建立新的单纯形表，在新的表中，基仍为单位阵。然后返回最优性检验步骤。

需要做的特定的初等变换运算如下：

1、出基行除以主元，把主元位置上的元素化为1

2、把入基列上主元以外的数全部化为0

对入基列中有负系数的其他行〔包括0行〕，把该负系数的绝对值和变化后的出基行的乘积加到该行去。

3、对每出基列中拥有正系数的其他行〔包括0行〕减去该系数和变化后的出基行的乘积;关于单纯形法的补充说明1;关于单纯形法的补充说明2;单纯形表例题;第一章复习结束;第二章对偶理论与灵敏度分析;知识要点;原始问题

maxz=CX

s.t. AX≤b

X≥0;原问题与对偶问题之间的关系;2x1+2x2?12

x1+2x2?8

4x1?16

4x2?12

x1x2?0;〔2〕怎样写出非对称形式的对偶问题？

?把一个等式约束写成两个不等式约束，再根据对称形式的对偶关系定义写出；;写出下面问题的对偶规划;对偶问题;对偶关系对应表;minW=7y1+9y2;非对称形式对偶问题例题;课本例题P83例2.1-1;课本例题P83例2.1-1;课本例题P83例2.1-1;非对称形式对偶问题练习:

;对偶问题为;无界性：假设原问题可行，但其目标函数值无界，那么对偶问题无可行解。;例1：;【例2】证明以下线性规划无最优解：;;定理2.5强对偶定理;定理2.7互补松弛性定理;用互补松弛定理计算对偶问题的最优解;已知原问