运筹学复习题型(推荐).doc

一、将线性规划化为标准型和写出相应的对偶规划;
二、用图解法求解具有两个决策变量的线性规划问题;
三、用单纯形方法及人工变量法求解线性规划问题;
四、灵敏度分析;
五、整数规划与分枝定界法,0-1规划与隐枚举法,指派问题
六、求解产销平衡的运输问题和产销不平衡的运输问题;
七、动态规划与求解。
例题选讲
例:某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品,这些产品分别需要在A、B、C、D四种不同的设备上加工。按工艺规定:产品Ⅰ和Ⅱ在个设备上所需要的加工时数于下表中。已知各设备在计划期内的有效台时数分别是12、8、16和12。该工厂每生产一件产品Ⅰ可得利润2圆,每生产一件产品Ⅱ可得利润3圆,问:应如何安排生产,可获得最大利润。
设备
产品
A
B
C
D
Ⅰ
2
1
4
2
Ⅱ
3
2
1
4
解设生产产品Ⅰ和Ⅱ分别为和件,则由条件可得关系


⑴标准型的概念:
①目标函数为极大化;
②资源常数;
③约束条件关系为等式;
④决策变量。
例: 将下面的线性规划化为标准型


无非负限制
解


二、图解法
例用图解法求解线性规划问题
极大化


解:最优解
三、单纯形方法
对于具有两个以上决策变量的线性规划问题,我们采用单纯形方法进行求解。具体过程是:
⑴建立单纯形表,在单纯形表中,务必使基变量的价值系数为零,则检验数行是价值系数行的相反数;
⑵若检验数则当前解为最优解(当前解是基变量取相应的资源常数,非基变量取为零);若存在检验数,则要进行相应的换基,即:迭代;
⑶①进基:进基变量
:
②出基:出基变量为第行所对应的基变量,由下面的关系确定
③以主元进行迭代,目标:主元化为1,该列的其余元化为零。
⑷再一次判定当前解是否为最优解。
例用单纯形法求解线性规划
极大化


解引入松弛变量,得到原规划的标准型
极大化


单纯形表为

所以,最优解为最优解值为21.
人工变量法
对于约束条件中没有阶单位阵的线性规划,通过引入适当的人工变量,再加以求解。
1. ***
在***中,引入的人工变量的价值系数为,而相应的约束条件系数向量为单位向量。

例用人工变量法求解线性规划。

.
符号不限。
例求解规划



建立对偶规划的要点
⑴原规划是极大化,则对偶规划是极小化;
⑵原规划的价值系数是对偶规划中的资源常数;
⑶原规划与对偶规划的约束条件系数矩阵为矩阵的转置关系;
⑷原规划中的第个决策变量无非负限制,则对偶规划中的第个约束条件为等式;
⑸原规划中的第个决策变量非正,则对偶规划中的第个约束条件取反向不等式;
例求下面问题的对偶规划
极大化

无非负限制。
解极小化


对偶单纯形法
基本要求:检验数;资源常数存在负值。
解法:
列出对偶单纯形表;
将基变量在目标函数中系数化为零,检验数为新目标函数中系数的相反数;
判断,若,则当前解为最优解;
若中存在负项,则进行迭代,确定出基和进基变量;
出基:记为第r行对应的变量;
进基:,为进基变量;
以为主元进行迭代。目标:将主元化为1,该列的其余元化为0。
灵敏度分析
灵敏度分析的任务:确定各个变量使得最优解保持不变的变化范围;以及在最优解改变的时候求出相应的最优解。
⑴非基变量的价值系数的变化范围,使最优解保持不变。
⑵基变量的价值系数的变化范围,使最优解保持不变。
:
若最优解改变,则对两种情况有
⑶资源常数变化范围使最优基不变:
:
⑷非基变量的系数向量的增量的变化范围使最优解不变:
⑸增加新的决策变量使最优解保持不变:
例:设线性规划


求:;
,使最优解不变; 取,求最优解;
,使最优基不变, 取求最优解;
;
解
即,原问题的最优解为
,故当时,即时, 最优解不变;
为基变量,由公式,当最优解不变, 即
时,最优解不变.
现对最优解改变,此时原最优表为
即相应的最优解为


最优基不变.
当最优解改变,此时
此时最优表为
即最优解为

故最优解改变.
相应的最优表为
例用分枝定界法求解整数规划
用隐枚举法求解0-1规划