线性规划与对偶理论.ppt

第二部分线性规划主要内容：第一节（LP）模型的建立及标准形式模型的四个要点：规划论模型包含的三个方面：规划论模型的数学表示：规划论中不同规划的主要区别： ——函数线性与非线性的区别：函数不是线性的规划问题解：二、（LP）模型的种类例3(运输最优调配问题)建模：MinZ=1.5x11+2.0x12+0.3x13+3.0x14
……
1.2x31+0.2x32+2.0x33+2.5x34s.t三、（LP）模型的标准形式模型的矩阵表示:模型的简化表示:四、模型的标准化2、不等式约束的改写：3、决策变量非正的改写：标准化的例：目标：余料总长→最少s.t例最优解二、图解法举例如何使用图解法？s.tX1X1X1X1三、图解法的启示第三节单纯型算法一、基解与基可行解如果A中存在一个“m阶”的方阵B，则AX=b可表示为：BXB+NXN=b（P1P2······Pn）利用图解法中的例，了解基解在几何中的对应关系X1结论：最优解各解之间的关系：三、寻找最优解算法的思路例：2x1＋2x2＋x3＝12
x1＋2x2＋x4＝8
4x1＋x5＝18
4x2＋x6＝12
xi≥0i=1,2,3,4,5,6首先要找到一个(随便哪个) (初始的)基可行解：x3＝12－(2x1＋2x2)
x4＝8－(x1＋2x2)
x5＝18－(4x1)
x6＝12－( 4x2)目标值Z(0)=2x1+3x2=0x3＝12－(2x1＋2x2)
x4＝8－(x1＋2x2)
x5＝18－(4x1)
x6＝12－( 4x2)1/2x3＝6－(x1＋x2)
1/2x4＝4－(1/2x1＋x2)
x5＝18－(4x1)
1/4x6＝3－( x2)求出新的基可行解：
令非基变量x1=0，x6=0
可得基变量x3=6，x4=2，x5=18，x2=3寻找下一个基可行解(使x1进基)：消去其他方程的x1：x1＝2－(x4－1/2x6)寻找下一个基可行解(使x6进基)：2x1＋2x3＝8－(-2x4)x6＝4－(2x3－4x4)即最优解为:X*=X(3)=(4,2,0,0,2,4)T
最优值为:Z*=Z(3)=14上述消去法求解的启示：四、单纯形法（Dantzig1946）单纯形算法的计算步骤：c1x1+···+cmxm+cm+1xm+1+···+cnxn=Z-0
首先，列出单纯形的准备表：单纯形法计算步骤：第二步：(最优判断)第三步：(无解判断)第四步：(进基列确定)第五步：(选主元)第六步：(换基运算)例：利用单纯形法求解下列LP问题准备表检查检验数rj，进基列的确定，判断表2x1x2x3x4x5
-z-2-10001
x411/20011/2
x21-1100-2
x331/20101/2判断表3x1x2x3x4x5
-z-4-200-20
x5210021
x2511040
x32001-10第四节（LP）的对偶理论一、两个例子问题1建模(LP)：问题2建模(DP)：(LP)问题1(LP)模型结果：例2、（生产计划问题）问题1建模(LP)：问题2建模(DP)：MaxZ=20x1+30x2例题的启示：二、对偶规划的定义MinZ=c1x1+c2x2+······+cnxn由(LP)写出(DP)的要点例：MinZ=20x1-30uMinZ=20x1-30uMaxg=-18y1+10y2-10y3+16y4MinZ=20x1+30x2三、对偶理论的两个重要结论四、对偶最优解的经济学解释——影子价格2、影子价格的含义：影子价格的含义（续1）影子价格的含义（续2）第五节（LP）的灵敏度分析灵敏度分析的主要内容：例1：矿山生产计划优化P92最优解：资源的影子价格：例2：昆钢产品结构优化（一）目标函数（二）决策变量分别表示由本系统外(但在本公司内)的连铸普碳坯，连铸低合金坯，炼钢厂扁锭，普通无缝管坯和一般锅炉管坯。
综上可知：
决策变量共71个，外生变量5个。/（三）约束条件2．物流约束3．工时约束：（共5个）4．能源约束：（共2个）5．工艺结构约束：（共3个）6．指令性计划要求约束：（共12个）附：使用1987年数据得出目标函数如下：对此模型的评论：例3：借贷资金分配问题——柔性OR模型分析：求解途径：行为模型的建立：分别就各因素配额ejS作再分配，即：
确定加权系数aij，使得：Step4.导出行为的模型：三个支持算法：(见教材P153~154)获得满意解的“人－机”对话过程： 或使用[算法2]修改e，计算后进行Step6。
Step5.直接修改A，并转回Step2，
或使用[算法3]修改aj，计算后进行Step7。
Step6.评判新的e，
若恰当，则返回Step2；
若否，则返回Step4。
Step7.评判aj，
若恰当，则返回Step2；
若否，则返回Step5。评注：