复习课运筹学课件

复习课

运筹学绍兴文理学院工学院计算机系2005.12.模型、概念图解法标准化单纯形法对偶理论线性规划问题第五章线性规划的图解法

maxz=x1+3x2 约束条件：

x1+

x2≤6 -x1+2x2≤8 x1≥0,x2≥0可行域目标函数等值线最优解(4/3,14/3)64-860x1x2约束条件(s.t.)线性规划问题⑴2.5x1+1.5x2≤904x1+5x2≤2003x1+10x2≤300x1≥0,x2≥0目标函数maxz=7x1+12x2若干个决策变量x1,x2;2.约束条件(≤或≥或＝);3.符号约束(非负或非正或自由);4.目标函数(max或min)。图解法线性规划问题⑵x1+x2≤6x1－x2≤4x1+3x2≥62x1+x2≥4x1≥0,x2≥0s.t.Minz=3x1+2x2约束条件2x1+9x2≤182x1+4x2≤103x1+2x2≤12

x1≥0,x2≥0线性规划问题⑵目标函数maxf=3x1+4x2线性规划问题⑵2x1+9x2=18最优解(3.5,0.75)目标函数f=3x1+4x2=13.53x1+2x2=122x1+4x2=10可行解区域约束条件x1+2x2≤84x1≤164x2≤12

x1≥0,x2≥0线性规划问题⑶目标函数Maxf=2x1+3x2线性规划的标准化用单纯形法求解线性规划要先标准化：目标函数求极大；全部是等式约束；所有决策变量全有非负约束。MinzMax-z不等式约束通过添加松弛变量(≤)或剩余变量(≥)化为等式约束。处理非正和自由的变量LP问题的单纯形法用单纯形法求解下列线性规划求最大；全是≤的不等式；常数项b≥0;全有非负约束。这类最适用：

单纯形法LP问题的单纯形法标准化；列初始单纯形表；迭代。引入松弛变量x3,成x1+2x2+x3=2引入松弛变量x4,成2x1+x2+x4=2极小化极大。两个松弛变量LP问题的单纯形法初始单纯形表基变量是哪两个？x3x4230000CB=?LP问题的单纯形法初始单纯形表头两行?Zj=?末行？2300121022101200LP问题的单纯形法单纯形表最优?谁进基?比值?谁出基？12LP问题的单纯形法迭代X2进基，x3出基，红格要变成几?LP问题的单纯形法第一次迭代是最优解?谁进基?谁出基?LP问题的单纯形法第二次迭代是最优解?最优解是?max?LP问题的单纯形法标准化；列初始单纯形表；迭代。引入松弛变量x4,成x1+x4=2引入松弛变量x5,成x1+x2+2x3+x5=4三个松弛变量引入松弛变量x6,成3x2+4x3+x6=6LP问题的单纯形法初始单纯形表基变量是哪三个？x４x51200x640000CB=?1

00

1

00

21

12

0

10

40

34

0

01

60

00

0

0001

24

0

00线性规划例1.一目标函数是MaxZ的LP问题，用单纯形法解的过程中，得到如下数据有缺的单纯形表。其中u为常数，求表中(*处)所有缺失的数。分析CB列中可确定哪几个？06000Zj行中可确定哪几个？60000000Z1=？σj行中可确定哪几个？C1-σ1=666u35-6u-31150a12=?右下角=?基变量列中可确定哪几个？续u=?时已得到唯一最优解。u>5/6u=0时有最优解吗?无有界最优解.u=0.5时有唯一最优解吗?迭代一次得最优解.对偶线性规划LP问题对偶规划的提出求LP问题的对偶规划LP问题对偶单纯形法例(对偶理论):原问题几个变量？这是要求X1,

X2使销售收入最____的LP问题LP的对偶理论设X1,

X2为产品1,产品2的产量大约束条件有几个？

等式还是不等式约束？Minf=y1y2

y3

y4

其对偶有几个变量？约束条件有几个？求极大？极小？42极小12+16+12y1y2y3y4y1y2y3y4y1y2y3y42++4+02+2+0+423≥≥≥0，，，+8Minz=2x1+x2-x3x1+x2-x3=

1x1-x2+x3

2x2+x3

3x10,x20,x3自由例1、写出下面问题的对偶规划Maxw=

y1y2y3

+2+3y1y2y3

y1y2y3

y1y2y3

y1y2y3

++0－+－++２１-１≤≥＝自由,≥0,≤0对一般的LP问题中：

原问题第k个约束为等式或≥，对偶问题第k个变量是自由或非正变量。原问题第k个变量是自由或非正变量，则对偶问题第k个约束为等式或≤约束。对偶问题

原问题对偶问题目标函数类型MaxMin目标函数与右边目标函数系数右边常数项常数项的对应关系右边常数项目标函数系数变量数与约束数变量数n约束数n的对应关系约束数m变量数m原问题变量类型与 变量≥

0 ≥约束对偶问题约束类型变量≤

0≤约束的对应关系自由变量＝约束原问题约束类型与约束≥

变量≤

0对偶问题变量类型约束≤

变量≥

0的对应关系约束＝自由变量对偶关系对应表原线性规划Minz=4X1+2X2-3X3-X1+2X2

62X1+3X3

9X1+5X2-2X3=

4X2,X30Maxf-y1+2y2+y3对偶规划例2、写出下面问题的对偶规划=6y1+9y2+4y32y1+5y33y2-2y3y10

,y3自由y20,4

2-3=

Minz=3X1+2X2+X3+4X42X1+4X2+5X3+X403X1-X2+7X3-2X425X1+2X2+X3+6X410X1,X2,X3,

X40例3、用对偶单纯形法解规划问题运输问题运输问题模型；表上作业法:求初始基可行解、判优、迭代。*用Excel解运输问题。运输问题产地数m=2,销地数n=3,产销平衡，决策变量个数m*n,等式约束数m+n，不等式约束数0,目标函数是总运价,要求最小。表上作业法运输问题的表上作业法：平衡产销；找出初始基可行解(西北角法、最小元素法、Vogel法)；基可行解是否最优的判别(闭回路法、位势法*)；非最优的基可行解的改进(闭回路调整法).

平衡产销运输问题中产销不平衡时：产>销：增加一个假想的仓库，运费为0，当新销地。产<销：增加一个假想的产地，运费为0。总可以调整为产销平衡。

找出初始基可行解运输问题的独立的等式约束数=系数矩阵的秩=基变量个数=m+n-1，非基变量个数=m*n-m-n+1。找出初始基可行解(m+n-1格)：西北角法；最小元素法;伏格尔(Vogel)法*等.

西北角法最后得的初始基可行解。34422223366找初始基可行解的西北角法尽量用下标小的（左上角——西北角优先安排）：x11=min(s1,d1)=d1=3,划去第一列（B1已满足）,s1←s1-x11；x12=min(s1-x11,d2)=4,划去第一行（A1已满足）；……划去m+n-1行(列)大功告成。最小元素法最后得的初始基可行解(不同于西北角法)。31144363333找初始基可行解的最小元素法尽量先用运价小的（就近优先安排，可能“因小失大”）：c21=min(cij)=1,x21=min(s2,d1)=3划去第一列（B1已满足）s2←s2-x21；c23=min,x23=min(s2-x21,d3)=1划去第二行（A2已满足）d3←d3-x23；……划去m+n-1行(列)大功告成。是基可行解？不是！！！从闭回路看。？？4+5-1=8。？？？？？基可行解是否最优的判别基可行解是否最优的判别(闭回路法、位势法*)；闭回路法求检验数,因为非最优的基可行解改进时用闭回路调整,所以优先介绍“闭回路法”位势法求检验数*.

闭回路法对每个非基变量(如x11)求它的闭回路;121求它的检验数：3-1+2-3=1>0。检验数无负是最优解，否则可调整。314633-11012闭回路法调优非基变量如x24检验数负,不是最优解;利用它的闭回路调整:min(1,3)=1;调整:奇加偶减，新方案再检验……。314633121-110121052位势法判优新方案再检验,逐个非基变量求检验数太繁，可用位势法求检验数；检验数全部非负,找到最优解(不唯一)。3132560310-23-590221912运输问题例2.求下列运输问题的解。检查产销是否平衡？产销平衡？20最小元素法用最小元素法求下列运输问题的初始基可行解。用位势法检查此解是否最优？30550350110333位势法检验求出位势检查此解是否最优？求检验数此解优否1否！闭回路？如何调？迭代、检验用闭回路调整,调整量？Min{1,3}=1621求位势！0141001求检验数！361115有负的吗？最优？是！总运费？39！一个求最大的LP问题的单纯形表如下：课堂练习一.求其中空缺的数(*)分别是什么？求出此LP问题的解。x50040133/40014010000