北京交通大学经济管理学院81.3.3初始基可行解的确定School of Ecorsics and ManagomentBoijing Jiaotong Universityu 问题1：找初始顶点？--观察或人造u问题2：判断最优？u问题3：转换到另一顶点？u找初始顶点分三种情况来进行：n从P(j=1,2,L,n)中一般能直接观察到a cjxj(1-20)max Z =:j-1存在初始可行基nelOua Px,=b(1-21)uB=(P,P,,P)=/=U018x, 3 0 j=1,2,L ,n由此得到初始基可行解北京交通大学1
§1.3.3初始基可行解的确定 u 问题1：找初始顶点？ -观察或人造 u 问题2：判断最优？ u 问题3：转换到另一顶点？ u找初始顶点分三种情况来进行：
北京交通大学经济管理学院可得初始基可行解Schooland ManagomentofEBoijing Jiaotong UniversityX(0) =(b,b2,L ,bm,0,L ,0)"mZ。=cb +czb, +L +cmbm=a c,bi-1max Z=2x, +3x,=8Xi+2x2+X3B(0)=(P3 , P4, Ps)iii=164x+X4X(0)=(0, 0, 8, 16, 12)7s.t.i4x2+xs=12iiiZo= 0K30北京交通大学
可得初始基可行解 X (0) =(0, 0, 8, 16, 12)T Z0 = 0 B (0) =( P3 , P4 , P5 )
北京交通大学练习：确定此问题的初始基可行解经济管理学院School of Econnics and ManagomentBojingJiaotong UniversitymaxZ=3x, - x, - xs3xi+x4 - 2x, =12i- x, =1X2s.t.i=12x+XiilXx30北京交通大学
练习：确定此问题的初始基可行解
北京交通大学经济管理学院81.3.2 初始基可行解的确定School of EonenndannagemenBoijing Jiaotong University对所有约束条件是”形式的不等式，在每个约束条件的左端2一个松弛变量 重新对x,及a,(i=1,2,L,m;j=1,2,L ,n)进行编号,得ix+a,m+1m +L +a,x, =b:i+a2,m+1Xm1 +L +a2nx, =b,iX1-231LL1:iiXm+amm+/m+ +L +ammX,= b.转化为第一种情况得到初始基可行解X=(b,b,L ,b.,0L ,O)北京交通大学
§1.3.2 初始基可行解的确定
北京交通大学经济管理学院81.3.2初始基可行解的确定School of EoicsandManagomentBoijing Jiaotong University对所有约束条件是°3"”）形式的不等式及等式约束情况(3)若不存在单位矩阵时采用人造基方法对等式约束加上一个非负的人工变量变为等式约束对不等式约束减去一个非负的剩余变量再加上一个非负的人工变量详细情况第五节讨论北京交通大学
§1.3.2 初始基可行解的确定