用关于变量有界情形的单纯形方法解下列问题：min 一2x1＋4x2一x3＋x4 S．t． x1＋2x

正确答案：将线性规划写成下列形式： min c₁x₁+c₂x₂ s．t． A₁x₁+A₂x₂≤20 x₁∈S₁ x₂∈S₂其中c₁=(一24)c₂=(一11)A₁=(12)A₂=(41)．[*S₁是有界集设有t₁个极点x₁⁽¹⁾x₁⁽²⁾…[*．S₂是无界集设有t₂个极点有l个极方向．引入松弛变量v．主规划如下：λ_1j≥0j=12…t₁λ_2j≥0j=12…t₂μ_j≥0j=12…lv≥0．取S₁的极点．S₂的极点初始基变量取vλ₁₁λ₂₁．初始基B是三阶单位矩阵单纯形乘子(ωα₁α₂)=(000)目标值z=0初始单纯形表如下： 第1次迭代： 解下列子规划： max(ωA₁一c₁)x₁+α₁ s．t．x₁∈S₁．即 max 2x₁一4x₂ s．t． 一x₁+x₂≤3 x₁ ≤4 x₁x₂≥0．子规划的最优解最优值z₁=8即主规划中对应λ₁₂的判别数是8．λ₁₂进基主列用表格形式计算如下： 第2次迭代： 解下列子规划： max(ωA₁一c₁)x₁+α₁ s．t． x₁∈S₁．即max 2x₁—4x₂—8s．t．—x₁+x₂≤3 x₁ ≤4 x₁x₂≥0．子规划的最优解同第1次迭代最优值z₁=0．现行解下对应λ_2j的判别数均小于或等于0． 再解子规划： max (ωA₂一c₂)x₂+α₂ s．t． x₂∈S₂即 max x₃一x₄ s．t． x₃—5x₄ ≤5 一x₃+2x₄ ≤2 x₃x₄≥0．用单纯形方法解子规划可知无界．S₂的一个极方向在主规划中对应于μ₁的判别数(ωA₂一c₂)d⁽¹⁾=(1一1)=4μ₁进基主列用表格形式计算如下： 第3次迭代： 解子规则 max(ωA₁一c₁)x₁+α₁ s．t． x₁∈S₁即s．t． 一x₁+x₂≤3 x₁ ≤4 x₁x₂≥0．子规划的最优解最优值z₁=0． 再解子规划： max(ωA₂一c₂)x₂+α₂ s．t． x₂∈S₂即s．t． x₃—5x₄≤5 一x₃+2x₄≤2 x₃x₄≥0．用表格形式计算如下： 第4次迭代： 解子规划： max(ωA₁一c₁)x₁+α₁ s．t． x₁∈S₁即s．t． 一x₁+x₂≤3 x₁ ≤4 x₁x₂≥0．子规划最优解最优值z₁=0．解子规划： max(ωA₂一c₂)x₂+α₂ s．t． x₂∈S₂即s．t． x₃—5x₄≤5 一x₃+2x₄≤2x₃x₄≥0．子规划最优解最优值z₂=0．主规划对应各变量的判别数均小于或等于0因此达到最优．主规划的最优解是λ₁₂=1其余变量均为非基变量取值为0．原来问题最优解最优值f_min=一12．
将线性规划写成下列形式：minc1x1+c2x2s．t．A1x1+A2x2≤20,x1∈S1,x2∈S2,其中,c1=(一2,4),c2=(一1,1),A1=(1,2),A2=(4,1)．[*S1是有界集,设有t1个极点x1(1),x1(2),…,[*．S2是无界集,设有t2个极点,有l个极方向．引入松弛变量v．主规划如下：λ1j≥0,j=1,2,…,t1,λ2j≥0,j=1,2,…,t2,μj≥0,j=1,2,…,l,v≥0．取S1的极点．S2的极点初始基变量取v,λ11,λ21．初始基B是三阶单位矩阵,单纯形乘子(ω,α1,α2)=(0,0,0),目标值z=0,初始单纯形表如下：第1次迭代：解下列子规划：max(ωA1一c1)x1+α1s．t．x1∈S1．即max2x1一4x2s．t．一x1+x2≤3,x1≤4,x1,x2≥0．子规划的最优解最优值z1=8,即主规划中对应λ12的判别数是8．λ12进基,主列用表格形式计算如下：第2次迭代：解下列子规划：max(ωA1一c1)x1+α1s．t．x1∈S1．即max2x1—4x2—8s．t．—x1+x2≤3,x1≤4,x1,x2≥0．子规划的最优解同第1次迭代,最优值z1=0．现行解下,对应λ2j的判别数均小于或等于0．再解子规划：max(ωA2一c2)x2+α2s．t．x2∈S2,即maxx3一x4s．t．x3—5x4≤5,一x3+2x4≤2,x3,x4≥0．用单纯形方法解子规划,可知无界．S2的一个极方向在主规划中,对应于μ1的判别数(ωA2一c2)d(1)=(1,一1)=4,μ1进基,主列用表格形式计算如下：第3次迭代：解子规则max(ωA1一c1)x1+α1s．t．x1∈S1,即s．t．一x1+x2≤3,x1≤4,x1,x2≥0．子规划的最优解,最优值z1=0．再解子规划：max(ωA2一c2)x2+α2s．t．x2∈S2,即s．t．x3—5x4≤5,一x3+2x4≤2,x3,x4≥0．用表格形式计算如下：第4次迭代：解子规划：max(ωA1一c1)x1+α1s．t．x1∈S1,即s．t．一x1+x2≤3,x1≤4,x1,x2≥0．子规划最优解,最优值z1=0．解子规划：max(ωA2一c2)x2+α2s．t．x2∈S2,即s．t．x3—5x4≤5,一x3+2x4≤2,x3,x4≥0．子规划最优解,最优值z2=0．主规划对应各变量的判别数均小于或等于0,因此达到最优．主规划的最优解是λ12=1,其余变量均为非基变量,取值为0．原来问题最优解最优值fmin=一12．