中国矿业大学管理运筹学教学教案第一课时线性规划地基本问题

管理运筹学中国矿业大学管理学院2006年9月O.R.

任课教师：王新宇，副教授，博士单位：管理学院－管理科学与工程系Email：wxy_cumt@163.comTel(home)理运筹学教学公用信箱

用户：orteaching@163.com密码:123456供网上答疑、资料分发收集、平时交流使用，欢迎各位同学使用，密码勿改！试题结构：选择，15分填空，10分计算题，75分课程的最终成绩：考试：70~80％平时作业和出席率20~10％实验报告10％课程要求：认真听课独立完成作业不允许无故缺席上课保持安静欢迎提问一、运筹学的起源与发展起源于二次大战的一门新兴交叉学科与作战问题相关如雷达的设置、运输船队的护航、反潜作战中深水炸弹的深度、飞行员的编组、军事物资的存储等英国称为OperationalResearch美国称为OperationsResearch战后在经济、管理和机关学校及科研单位继续研究1952年，Morse和Kimball出版《运筹学方法》1948年英国首先成立运筹学会1952年美国成立运筹学会1959年成立国际运筹学联合会(IFORS)我国于1982年加入IFORS，并于1999年8月组织了第15届大会二、运筹学的特点及研究对象运筹学的定义为决策机构对所控制的业务活动作决策时，提供以数量为基础的科学方法——Morse和Kimball运筹学是把科学方法应用在指导人员、工商企业、政府和国防等方面解决发生的各种问题，其方法是发展一个科学的系统模式，并运用这种模式预测，比较各种决策及其产生的后果，以帮助主管人员科学地决定工作方针和政策——英国运筹学会运筹学是应用分析、试验、量化的方法对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有根据的最优方案，以实现最有效的管理——中国百科全书现代运筹学涵盖了一切领域的管理与优化问题，称为ManagementScience三、运筹学的特点及研究对象运筹学的分支数学规划：线性规划、非线性规划、整数规划、动态规划、目标规划等图论与网路理论随机服务理论：排队论存储理论决策理论对策论系统仿真：随机模拟技术、系统动力学可靠性理论金融工程四、运筹学解决问题的方法步骤明确问题建立模型设计算法整理数据求解模型评价结果明确问题建立模型设计算法整理数据求解模型评价结果简化？满意？YesNoNo五、运筹学的发展趋势运筹学的危机脱离实际应用，陷入数学陷阱IT对运筹学的影响MIS,DSS,MRP-II,CIMS,ERPORDept.-->Dept.OfOR&IS运筹学与行为科学结合群决策和谈判对策理论多层规划合理性分析服务行业中的应用金融服务业信息、电信服务业医院管理四、运筹学的发展趋势软计算面向强复杂系统的计算、实时控制、知识推理智能算法：模拟退火、遗传算法、人工神经网络、戒律算法等系统仿真面向问题后勤(Logistics)全球供应链管理电子商务：集成特性随机和模糊OR问题本身的不确定性人类知识的局限性目录第一章线性规划的基本问题第二章线性规划的对偶问题与灵敏度分析第三章目标规划与整数规划第四章非线性规划第五章动态规划第六章矩阵对策第七章图与网络第八章网络计划技术(统筹法)第九章存储论第十章决策论OR第一章线性规划的基本问题(Linearprogramming)1.1线性规划问题及其数学模型1.1.1线性规划问题

(1)给定了一定数量的资源，研究如何运用这些资源使完成的任务最多。

(2)给定了一项任务，研究如何统筹安排使消耗的资源最少。LP例：生产计划问题问如何安排生产可获得最大收益？设：x1、x2分别为甲、乙两种产品的产量，Z为总利润，则

Z（X）=4x1+5x2约束条件非负约束目标函数2x1+x2

x1，x2≥0≤45≤

90≤80

x1+x2

x1+3x2

MaxLP例2：配料问题设：x1、x2分别为甲、乙两种金属的含量，Z为总成本特征：（1）存在一组决策变量(decisionvariable)

（2）存在若干约束条件(≤,=或≥)(constraints)

（3）一个目标函数“max”“min”(objectivefunction)

Z（X）=2x1+5x2约束条件

非负约束目标函数

x2

x1，x2≥0≤0.06=1≥

0.92

x1

x1+x2

MinLP其中：（2）和（3）中各决策变量之间的关系均为线性关系。1.1.2线性规划数学模型的一般形式

Max(Min)Z（X）=c1x1+c2x2+…+cnxn

a11x1+a12x2+…+a1n

xn

≤(=,≥)b1a21x1+a22x2+…+a2n

xn

≤(=,≥)b2…………..am1x1+am2x2+…+amn

xn

≤(=,≥)bm

x1，x2，…，xn≥0

LP

Max(Min)Z（X）=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1n

xn

≤(=,≥)b1a21x1+a22x2+…+a2n

xn

≤(=,≥)b2…………..am1x1+am2x2+…+amn

xn

≤(=,≥)bm

x1，x2，…，xn≥0

1.1.3线性规划数学模型的标准型

MaxZ（X）=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1n

xn=b1a21x1+a22x2+…+a2n

xn=b2……………..am1x1+am2x2+…+amn

xn=bm

x1，x2，…，xn≥0LP1.1.3线性规划数学模型的标准型

MaxZ（X）=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1n

xn=b1a21x1+a22x2+…+a2n

xn=b2……………..am1x1+am2x2+…+amn

xn=bm

x1，x2，…，xn≥0标准型特征（1）决策变量均为非负变量（2）所有约束条件都是“=”型（3）目标函数为“Max”型（4）常数项bi(i=1,2,…,n)≥0标准型形式缩写（1）一般形式（2）向量形式（3）矩阵形式LP（1）一般形式MaxZ（X）=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1n

xn=b1a21x1+a22x2+…+a2n

xn=b2……………..am1x1+am2x2+…+amn

xn=bm

x1，x2，…，xn≥0Σa1jxj=b1

Σa2jxj=b2

Σamjxj=bm

nΣaijxj=bij=1xj≥0(i=1,2,…,m)

nMax(Z)=Σcjxjj=1(j=1,2,…,n)St:LPMaxZ（X）=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1n

xn=b1a21x1+a22x2+…+a2n

xn=b2……………..am1x1+am2x2+…+amn

xn=bm

x1，x2，…，xn≥0a11a21…am1a12a22…am2a1na2n…amnx1+x2+xn

=b1b2…bm…+（2）向量形式

MaxZ(X)=CX

nΣpjxj=bj=1xj≥0(j=1,2,…,n)LPa1ja2j…amj=pj令（3）矩阵形式

MaxZ（X）=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1n

xn=b1a21x1+a22x2+…+a2n

xn=b2……………..am1x1+am2x2+…+amn

xn=bm

x1，x2，…，xn≥0Max(Z)=CXAX=b

a11a12…a1n

a21a22…a2n

……………am1am2…amnx1x2…xnb1b2

…bm=X≥0

LP线性规划数学模型的一般形式线性规划数学模型的标准型（1）一般形式

nΣaijxj=bij=1xj≥0(i=1,2,…,m)

nMax(Z)=Σcjxjj=1(j=1,2,…,n)St:（2）向量形式

MaxZ(X)=CX

nΣpjxj=bj=1xj≥0(j=1,2,…,n)Max(Z)=CXAX=bX≥0

（3）矩阵形式St:St:LP1.1.4线性规划的标准化问题目标函数为“Min”型

MinZ=CXΣaijxj

≤bi这时xn+i称为松弛变量Σaijxj

+xn+i

=biΣaijxj

≥bi这时xn+i称为剩余变量也可统称为松弛变量Σaijxj

-xn+i=bi决策变量xi无非负约束(1)(2)令：Z/=-Z1.1.4.2约束条件为“≤”则：Max(-Z)=-CX或“≥”型令：xi

=xi/

-xi//（其中xi/

、xi//≥0

）代入原问题LP例：将下列线性规划模型化成标准型

MinZ（X）=3x1-x2+3x3

x1+x2+x3≤6x1+x2-x3≥2-3x1+2x2+x3=5x1，x2≥0

其标准型如下：

Max[-Z（X）]=-3x1+x2-3x3/+3x3//x1+x2+x3/

-x3//+x4x1+x2-x3/

+x3//-x5-3x1+2x2+x3/

-x3//

=5x1，x2,x3/

,

x3//

,

x4,

x5≥0=6=2+0x4+0x5LP1.2线性规划的解标准型

MaxZ（X）=c1x1+c2x2+…+cnxn

(1-1)a11x1+a12x2+…+a1n

xn=b1a21x1+a22x2+…+a2n

xn=b2……………..am1x1+am2x2+…+amn

xn=bm

(1-2)x1，x2，…，xn≥0(1-3)

线性规划的可行解(Feasiblesolotion)

满足约束条件(1-2)，(1-3)的解

X=（x1，x2，…，xn）称为线性规划问题的可行解。线性规划的最优解(Optimalsolution)

满足约束条件(1-1)的可行解

X*=（x1*，x2*，…，xn*）称为线性规划问题的最优解。LP线性规划的基若A为线性方程组（1-2）的mn阶系数矩阵，其秩为m，则A中任意m个线性无关的列向量构成的mm阶子矩阵,称为该线性规划的一个基，记为B。显然基矩阵的行列式不等于零。例：232003110233=（P1，P2，P3，P4）x1,x2,x3,x4A=320311233=（P2，P3，P4）

x2,x3,x4若：B=为基向量为基变量LP(1)基向量：组成基矩阵的m个列向量称为基向量。(2)非基向量：其余的n-m个列向量称为非基向量。(3)基变量：与基向量相对应的m个变量称为基变量。(4)非基变量：其余的n-m个变量称为非基变量。线性规划的基本解a11x1+…+a1mxm+a1m+1xm+1+…+a1n

xn=b1a21x1+…+a2mxm+a2m+1xm+1+…+a2n

xn=b2……………am1x1+…+ammxm+amm+1xm+1+…+amn

xn=bm

LPa11x1+…+a1mxm=b1a21x1+…+a2mxm=b2………..

am1x1+…+ammxm=bm

若：x1，x2，…，xm为基变量；令n-m个非基变量xm+1=xm+2=…=xn=0再由方程组:解出基变量x*1，x*2，…，x*m的值,则解向量:

X*=(x*1，x*2，…，x*m,0,…,0)称之为对应一个基的基本解。a11x1+…+a1mxm+a1m+1xm+1+…+a1n

xn=b1a21x1+…+a2mxm+a2m+1xm+1+…+a2n

xn=b2……………am1x1+…+ammxm+amm+1xm+1+…+amn

xn=bm

a12x2+…+a1mxm+a1m+1xm+1=b1a22x2+…+a2mxm+a1m+1xm+1=b2………………..

am2x2+…+ammxm

+a1m+1xm+1=bm

若：x2，…，xm

，xm+1为基变量；令n-m个非基变量x1=xm+2=…=xn=0由方程组:解出基变量x*2，…，x*m，x*m+1的值,则解向量:

X*=(0，x*2，…，x*m,x*m+10,…,0)称之为对应一个基的基本解。LP根据基本解的定义不难得出以下结论：

线性规划的基本解不是唯一的，它与线性规划的基一一对应，个数不超过Cnm。LP线性规划的基本可行解满足非负条件（1-3）的基本解称为基本可行解；对应于基本可行解的基称为可行基。图示：可行解基本可行解基本解方程组的解LP1．2．2线性规划的图解法1．2．2．1一般情形例1:MaxZ（X）=4x1+5x2x1+x2

≤452x1+x2

≤80x1+3x2

≤90x1，x2≥0ADOCBX2X1多边形OABCD为线性规划的可性域，目标函数在C(45/2,45/2)达到最大x1=45/2x2=45/2,Z=405/2454580403090目标:x2=-4/5x1+1/5Z(等值线)Z=0LPADOCBX2X1LPCOADBX2X1LP1．2．2．2特殊情形(1)多重最优解例2MaxZ（X）=4x1+4x2x1+x2

≤452x1+x2

≤80x1+3x2

≤90x1，x2≥0DCBAX2X1OR等直线与线段CB平形，线段CB上的任意点均可使目标函数取得相同的最大值，则该规划有多重最优解LP(2)无最优解例3MaxZ（X）=5x1+4x2-4x1+3x2≤3-2x1+4x2≤8x1，x2≥001B可行域无界AX1②①（6/5，13/5）2X2注意；可行域无界，并不意味着目标函数值无界。如果目标函数为:MinZ（X）=5x1+4x2LP01B可行域无界AX1②①（6/5，13/5）2X2LP01B可行域无界AX1②①（6/5，13/5）2X2唯一最优解无界可行域无穷多最优解无最优解LP(3)无可行解7例4

MaxZ（X）=x1+2x2

x1+x2≤510x1+7x2≥70x1，x2≥0无可行域（解）X10X25510有界可行域无界可行域无可行域唯一最优解无穷多最优解无最优解无可行解LP有界可行域无界可行域无可行域唯一最优解无穷多最优解无最优解无可行解LP1．2．3线性规划解的基本性质

(1)满足线性规划约束条件的可行解集（可行域）构成一个凸多边形。(2)凸多边形的顶点（极点）与基本可行解一一对应（即一个基本可行解对应一个顶点）。(3)线性规划问题若有最优解，则最优解一定在凸多边形的某个顶点上取得。由（2）和（3）可得如下结论：线性规划问题若有最优解，则最优解一定是某个基本可行解。LPADOCBX2X1

MaxZ（X）=4x1+5x2+0x3+0x4+0x5x1+x2+x3=452x1+x2+x4=80x1+3x2+x5=90x1，x2，x3，x4，x5≥0

x2=0x1=0x3=0x4=0x5=0LP107*60*60*24*365=31536*1010<1015确定初始基本可行解X(k)k=0

检验X(k)是否最优转换到另一个基本可行解X(k+1)

并使Z(X(k+1))>Z(X(k))NY停1．3单纯形法1．3．1单纯形法的基本思路LP例1MaxZ（X）=4x1+5x2x1+x2≤452x1+x2≤80x1+3x2≤90x1，x2≥0将上式化为标准形式

MaxZ（X）=4x1+5x2+0x3+0x4+0x5x1+x2+x3=452x1+x2+x4=80x1+3x2+x5=90x1，x2，x3，x4，x5≥0

(1)确定初始的基本可行解

X（0）=（0，0，45，80，90）Tx3为第1种资源的剩余量x4为第2种资源的剩余量x5为第3种资源的剩余量LP(2)检验将X（0）代入目标函数，即

MaxZ（X（0））=4x1+5x2+0x3+0x4+0x5=0

由于非基变量x1、x2的系数都>0,所以X（0）不是最优解。(3)基变换确定进基变量:x2的系数>x1的系数,∴x2进基变量确定退出变量：分析：

x1+x2+x3=452x1+x2+x4=80x1+3x2+x5=90x1，x2，x3，x4，x5≥0

LP

x1+x2+x3=452x1+x2+x4=80x1+3x2+x5=90x1，x2，x3，x4，x5≥0

注意x1仍然为0如果：x3=0x2=45/1

X（1）=（0，45，0，35，-45）

x4=0x2=80/1

X（1）=（0，80，-35，0，-150）

x5=0x2=90/3

X（1）=（0，30，15，50，0）分析：LP

x1+x2+x3=452x1+x2+x4=80x1+3x2+x5=90

x2=θ=min{45/1,80/1,90/3}=30

当x2由0变到30时，x5首先变为0，故x5为退出基变量。变换方程，求新的基本可行解

X（1）=（0，30，15，50，0）T（4）返回（2）检验

Z（X（1））=4x1+5(30-1/3x1-1/3x5)=150+7/3x1-5/3x5

因7/3>0，故X（1）仍不满足最优性条件，继续进行转换（5）返回（3）基变换确定进基变量为x1

确定退出变量2/3x1+x3-1/3x5=155/3x1+x4-1/3x5=501/3x1+x2+1/3x5=30x1=θ=min{45/2,30,90}=45/2当x1由0变到45/2时，x3首先变为0，故x3为退出基变量。LP2/3x1+x3-1/3x5=155/3x1+x4-1/3x5=501/3x1+x2+1/3x5=30x1+3/2x3-1/2x5=45/2-5/2x3+x4+1/2x5=25/2

x2-1/2x3+1/2x5=45/2求新的基本可行解当x1由0变到45/2时，x3首先变为0，故x3为退出基变量。LP求新的基本可行解x1+3/2x3-1/2x5=45/2-5/2x3+x4+1/2x5=25/2x2-1/2x3+1/2x5=45/2

X（2）=（45/245/2025/20）T

返回（2）继续检验

Z（X（2））=4(45/2-3/2x3+1/2x5)+5(45/2+1/2x3-1/2x5)=405/2-7/2x3-1/2x5

所有非基变量的检验数均≤0，问题已获得最优解。

X*=X（2）=（45/245/2025/20）TZ（X*）=405/2LP第一步：寻找初始基本可行解第三步：换基迭代（2）确定出基变量：（2）确定出基变量：三、换基迭代在第4个方程五、循环迭代：单纯形原理的矩阵描述设标准的线性规划问题为

min z= CTX s.t. AX=b X0矩阵A可以分块记为A=[B，N]

相应地，向量X和C可以记为

AX=b可以写成

BXB+NXN=b即

XB=B-1b-B-1NXN

对于一个确定的基B，目标函数z可以写成目标函数z用非基变量表出的形式单纯形表的结构

左端同乘B-111100x1x2x3x4x54

50

0

0

21010130014

50

0

0

45

80

90x3x4x50

0

045/180/190/3[]CBxBcjb

MaxZ（X）=4x1+5x2+0x3+0x4+0x5x1+x2+x3=452x1+x2+x4=80x1+3x2+x5=90x1，x2，x3，x4，x5≥0

1．3．2单纯形表仍以例1为例LP2/3010-1/330x3x4x20

0

45/230905/3001-1/31/31001/37/3000-5/355015][11100x1x2x3x4x54

50

0

0

21010130014

50

0

0

45

80

90x3x4x50

0

045/180/190/3[]CBxBcjb1233/1/2/3/3=1/31/=3/1+-2/=3/2+-103/20-1/2x1x4x24

0

00-5/211/201-1/201/200-7/20-1/2525/245/21/1//=3/245/22/3010-1/3x1x2x3x4x54

50

0

0

5/3001-1/31/31001/315

50

30x3x4x20

0

5CBxBcjb7/3000-5/345/230903/1/2/[]2//1//3//=2/+-5/32//1//=3/+-1/33//1//≤0=cj-CBPj103/20-1/2x1x4x24

0

00-5/211/201-1/201/200-7/20-1/2525/245/245/22//1//3//≤0=cj-CBPj所有的检验数均已小于或等于零，问题已获得最优解

X*=（45/2，45/2，0，25/2，0）TZ=405/2

求解方法—单纯形方法maxz=50x1+40x2

s.t.

3x1+5x2≤150

x2≤20

8x1+5x2≤300

x1,x2≥0标准化maxz=50x1+40x2

s.t.

3x1+5x2＋x3

=150(1)

x2

+x4

=20(2)

8x1+5x2

+x5=300(3)

x1,x2,x3,x4,x5≥0

单纯形表（初始）

B1=(P3,P4,P5)=I当前基本可行解：(0,0,150,20,300),Z=0当前基本可行解：(75/2,0,75/2,20,0),Z=1875B2=(P3,P4,P1)=当前基本可行解：(30,12,0,8,0),Z=1980达到最优解B3=(P2,P4,P1)=转换关系思考：对于特殊的线性规划问题，如有多重最优解，及无最优解时，如何从单纯形表中获得有关信息？例2MaxZ（X）=4x1+4x2+0x3+0x4+0x5x1+x2+x3=452x1+x2+x4=80x1+3x2+x5=90x1，x2，x3，x4，x5≥0单纯形表：LP11100x1x2x3x4x54

40

0

0

21010130014

40

0

0

45

80

90x3x4x50

0

045/180/290CBxBcjb[]=cj-CBPj多重解01/21-1/2050x3x1x50

4

10802011/201/2005/20-1/21020-200405][11100x1x2x3x4x54

40

0

0

21010130014

40

0

0

45

80

90x3x4x50

0

045/180/290[]CBxBcjb=cj-CBPj012-1025x2x1x54

4

3525/210-11000-52100-40003510][=cj-CBPj01/21-1/2050x3x1x50

4

10802011/201/2005/20-1/21020-200405][=cj-CBPj所有的检验数均小于或等于零，最优解：

X1*=（35，10，0，0，25）T非基变量x4的检验数为0，表明该规划有无限多最优解,继续迭代求出另一个最优(基本可行)解。≤0ADOCBX2X1

MaxZ（X）=4x1+5x2+0x3+0x4+0x5x1+x2+x3=452x1+x2+x4=80x1+3x2+x5=90x1，x2，x3，x4，x5≥0

x2=0x1=0x3=0x4=0x5=0LP012-1025x2x1x54

4

3525/210-11000-52100-40003510][=cj-CBPj’≤001-1/201/2x2x1x44

4

103/20-1/200-5/211/200-400045/2=cj-CBPj≤045/225/2X2*=（45/2，45/2，0，25/2，0）T

X*=aX1*+(1-a)X2*

（0<=a<=1）

Z(X*)=180本题说明：1、最优解不唯一，但最优值唯一3、在实际应用中，有多种方案可供选择例3MaxZ（X）=5x1+4x2+0x3+0x4-4x1+3x2+x3=3-2x1+4x2+x4=8x1,…,x4≥0无最优解[]LP令：x1=M>0(任意大)，x2=0,x3=3+4M,x4=8+2MZ=５Ｍ，可以任意大！！！[][]LP即使继续迭代计算此问题无最优解。[]LP例3MaxZ（X）=5x1+4x2-4x1+3x2≤3-2x1+4x2≤8x1，x2≥001B可行域无界AX1②①（6/5，13/5）2X2LP3、将约束方程化为每个方程只含一个基变量目标函数表示成非基变量的函数

单纯形法步骤：1、化标准型

2、选定一个可行基，并得一基本可行解X？5、判断X是否为最优解：若目标函数行中所有检验数λi≤0,

则X为最优解。若存在某个λ

j>0,且所有的aij<0，则不存在有界最优解。否则转下一步4、做单纯形表6、换基迭代（1）入基变量：设λ

k=max{λ

i|λ

i>0},取xk为入基变量（2）出基变量：

7、对单纯形表做初等行变换：把基变量对应的列化为单位向量，目标函数的基变量系数化为零，得一新的基本可行解X。转第4步例题：人员安排问题医院护士24小时值班，每次值班8小时。不同时段需要的护士人数不等。据统计：

序号时段最少人数安排人数106—1060X1210—1470X2314—1860X3418—2250X4522—0220X5602—0630x6建模:目标函数：minZ=x1+x2+x3+x4+x5+x6约束条件：x1+x2

≥70x2+x3≥60x3+x4≥50x4+x5≥20x5+x6≥30

x6+x1≥60非负性约束：xj

≥0,j=1,2,…6ＬＩＮＤＯ中一般整型变量的命令是:ＧＩＮ变量名或GIN变量的总数（适用于全部是整型变量）０－１变量的命令是：INTEGER变量名或INTEGER变量的总数（适用于全部是整型变量）1.4人工变量法人为地构造一个单位矩阵来充当初始可行基，再通过单纯形迭代将它们逐个地从基变量中替换出来。若经过基的变换，基变量中不再含有非零的人工变量，这表示原问题有解。若在最终表中当所有Cj-zj≤0，而在其中还有某个非零人工变量，这表示无可行解。大M法两阶段法例：MinZ（X）=-3x1+x2+x3x1-2x2+x3≤11-4x1+x2+2x3≥3-2x1+x3=1x1，x2，x3≥0

Max[-Z（X）]=3x1-x2-x3x1-2x2+x3+x4=11-4x1+x2+2x3-x5=3-2x1+x3=1x1，x2，x3，x4，x5≥0其标准型：（以下称为模型1，用M1表示）M1+0x4+0x5LP1．4确定初始基本可行解的两种方法1．4．1大M法

Max[-Z（X）]=3x1-x2-x3+0x4+0x5x1-2x2+x3+x4=11-4x1+x2+2x3-x5=3-2x1+x3=1x1，x2，x3，x4，x5≥0M1构造新问题M2

Max[-Z（X）]=3x1-x2-x3+0x4+0x5x1-2x2+x3+x4=11-4x1+x2+2x3-x5=3-2x1+x3=1x1，x2，x3，x4，x5，≥0原理核心：打破原来的约束，再设法恢复。+x7+x6M2-Mx6

-Mx7，x7x6LP基本思想:假定人工变量在基变量中的价值系数为一个绝对值很大的-M(M>>0,对于极小化问题用+M),这样只要基变量中还存在人工变量,目标函数就不可能实现极值.x1x2x3x4x5x6x711

31x4x6x70

-M

-M11/13/2[]CBxBcjb3-1-100-M-M1

-21

1

0

00-4

12

0

-1

10-2

01

0

0

013-6M

-1+M-1+3M

0

-M

001单纯形表:LP

Max[-Z（X）]=3x1-x2-x3+0x4+0x5-Mx6-Mx7x1-2x2+x3+x4=11-4x1+x2+2x3-x5+x6=3-2x1+x3+x7=1x1，x2，x3，x4，x5，x6，x7≥0x1x2x3x4x5x6x711

31x4x6x70

-M

-M11/13/2[]CBxBcjb3-1-111-M-M1

-21

1

0

00-4

12

0

-1

10-2

01

0

0

013-6M

-1+M-1+3M

0

-M

0011x4x6x30

-M

-1[]3

-20

1

0

0-10

10

0

-1

1-2-2

01

0

0

011M-10

0

-M

01-3M11101x4x6x30

-M

-1[]3

-20

1

0

0-10

10

0

-1

1-2-2

01

0

0

011M-10

0

-M

01-3M11109x1x2x33

-1

-11

0

0

1/3

-2/3

2/3-5/30

10

0

-1

1-20

01

2/3

-4/3

4/3-7/3000

-1/3

-1/3

141x2x4x30

-13

00

1

-2

2-50

10

0

-1

1-2-2

01

0

0

01

10

0

0

-1

1-M-M-1-112[]1例4

MaxZ（X）=x1+2x2x1+x2≤510x1+7x2≥70x1，x2≥0[]所有的检验数都小于或等于零，但人工变量x5仍未从基变量中退出，这表明原问题无可行解。≤0

MaxZ（X）=x1+2x2x1+x2+x3=510x1+7x2-x4=70x1，…，x4≥0+x5-Mx5，x5再例：（LP）Maxz=5x1

+2x2

+3x3

-x4

s.t.x1+

2x2+

3x3=152x1

+x2

+5x3=20

x1

+2x2

+4x3

+x4

=26

x1

,x2

,x3

,x4

≥0Maxz=5x1+2x2+3x3-x4-Mx5-Mx6

s.t.x1+2x2+3x3+x5

=152x1+x2+5x3+x6=20

x1+2x2+4x3+x4

=26

x1,x2,x3,x4,x5,x6

≥0大M法问题(LP-M）大M法

（LP-M）得到最优解：(25/3，10/3，0，11)T

最优目标值：112/31．4．2两阶段法例：Max[-Z（X）]=-3x1+x2+x3+0x4+0x5x1-2x2+x3+x4=11-4x1+x2+2x3-x5=3-2x1+x3=1x1，x2，x3，x4，x5≥0第一阶段：据给定的问题构造其辅助问题，为原问题求初始基本可行解.辅助问题:

x1-2x2+x3+x4=11-4x1+x2+2x3-x5=3-2x1+x3=1x1，...，x5≥0+x6+x7x6+x7，x6，x7MinW(X)=LP

x1-2x2+x3+x4=11-4x1+x2+2x3-x5=3-2x1+x3=1x1，...，x5≥0+x6+x7x6+x7，x6，x7MinW(X)=LP辅助问题最优解X=(0,1,1,12,0,0,0)[][]≤0LP第二阶段：将第一阶段求出的最优解，作为第二阶段的初始基本可行解，然后在原问题的目标函数下进行优化，以决定原问题的最优解。

X*=(4,1,9,0,0);Z(X*)=-2≤0[]Maxz=5x1+2x2+3x3-x4-Mx5-Mx6

s.t.x1+2x2+3x3+x5

=152x1+x2+5x3+x6=20

x1+2x2+4x3+x4

=26

x1,x2,x3,x4,x5,x6

≥0两阶段法第一阶段问题（LP-1）

Maxz=-x5

-x6s.t.x1+2x2

+3x3

+x5

=152x1

+x2

+5x3

+x6=20

x1

+2x2+4x3

+x4

=26x1,x2,x3,x4,x5,x6

≥0两阶段法：第一阶段(LP-1）

得到原问题的基本可行解:(0，15/7，25/7，52/7)T第二阶段把基本可行解填入表中

得到原问题的最优解:(25/3，10/3，0，11)T最优目标值：112/3两阶段法计算步骤小结

是否否

是唯一最优解LP问题引人松弛变量`人工变量,列出单纯形表非基变量检验数j≤0对任一j>0有aij≤0令k=max{j}Xk为入基变量对所有aik≥0计算min(θi)

=min(bi/aik)=θ

lXl为出基变量换基迭代1.Xk替代Xl2.对主元行3.对主元列4.对其它行列变换无最优解无可行解基变量含有非零人工变量非基变量检验数为零多重最优解打印结果结束是是注意：单纯形法中1、每一步运算只能用矩阵初等行变换；2、表中第3列(b列)的数总应保持非负（≥0）；3、当所有检验数均非正（≤0）时，得到最优单纯形表。若直接对目标求最h，要求所有检验数均非负；4、当最优单纯形表存在非基变量对应的检验数为零时，可能存在无穷多解；单纯形法注意事项5、关于退化和循环。如果在一个基本可行解的基变量中至少有一个分量xBi=0(i=1,2,…,m)，则称此基本可行解是退化的基本可行解。一般情况下，退化的基本可行解（极点）是由若干个不同的基本可行解（极点）在特殊情况下合并成一个基本可行解（极点）而形成的。退化的结构对单纯形迭代会造成不利的影响。

可能出现以下情况：①进行进基、出基变换后，虽然改变了基，但没有改变基本可行解（极点），目标函数当然也不会改进。进行若干次基变换后，才脱离退化基本可行解（极点），进入其他基本可行解（极点）。这种情况会增加迭代次数，使单纯形法收敛的速度减慢。②在特殊情况下，退化会出现基的循环，一旦出现这样的情况，单纯形迭代将永远停留在同一极点上，因而无法求得最优解。

在单纯形法求解线性规划问题时，一旦出现这种因退化而导致的基的循环，单纯形法就无法求得最优解，这是一般单纯形法的一个缺陷。但是实际上，尽管退化的结构是经常遇到的，而循环现象在实际问题中出现得较少。尽管如此，人们还是对如何防止出现循环作了大量研究。1952年Charnes提出了“摄动法”，1954年Dantzig，Orden和Wolfe又提出了“字典序法”，这些方法都比较复杂，同时也降低了迭代的速度。1976年，Bland提出了一个避免循环的新方法，其原则十分简单。仅在选择进基变量和出基变量时作了以下规定：①在选择进基变量时，在所有j

>0的非基变量中选取下标最小的进基；②当有多个变量同时可作为出基变量时，选择下标最小的那个变量出基。这样就可以避免出现循环,当然，这样可能使收敛速度降低。合理利用线材问题：如何下料使用材最少。配料问题：在原料供应量的限制下如何获取最大利润。投资问题：从投资项目中选取方案，使投资回报最大。线性规划应用建模一、线性规划---产品生产计划：合理利用人力、物力、财力等，使获利最大。劳动力安排：用最少的劳动力来满足工作的需要。运输问题：如何制定调运方案，使总运费最小。数学规划的建模有许多共同点，要遵循下列原则：

(1)容易理解。建立的模型不但要求建模者理解，还应当让有关人员理解。这样便于考察实际问题与模型的关系，使得到的结论能够更好地应用于解决实际问题。

(2)容易查找模型中的错误。这个原则的目的显然与(1)相关。常出现的错误有：书写错误和公式错误。

(3)容易求解。对线性规划来说，容易求解问题主要是控制问题的规模，包括决策变量的个数和约束条件的个数。这条原则的实现往往会与(1)发生矛盾，在实现时需要对两条