运筹学,单纯形法求解。maxz 2x1+x2+x3 st

2021-01-15 07:29:39 字数 4195 阅读 5776

1楼:郭敦顒

郭敦顒回答:

maxz=2x1+x2+x3

st:4x1+2x2+2x3≥4 (1)2x1+4x2≤20 (2)

4x1+8x2+2x3≤1 (3)

(3)-(2)得2x3≤-39,

x3≤-19.5

4x1+2x2+2x3=4,4x1+8x2+2x3=1时,6x2=-3,x2=-0.5代入(2)得,2x1≤18,x1≤9将x1=9,x2=-0.5,x3=-19.

5代入目标值得,maxz=2x1+ x2+ x3=18-0.5-19.5=-2,maxz=-2。

用单纯形法求解线性规划问题 maxz=2x1-x2+x3,

2楼:立港娜娜

偶形式: 2y1-y2-y3=-2 3y1-2y2-3y3=-4 求 max -24y1+10y2+15y3 优解 y1=0,y2=2,y3=0 优值20设原始问题min则其偶问题 max。

原问题引入人工变量x4,剩余变量x5,人工变量x6 。

maxz=2x1+3x2-5x3 -mx4-mx6、x1+x2+x3+x4=7,2x1-5x2+x3-x5+x6=10,x1,x2,x3,x4,x5,x6≥0用人工变量法求解。

1、线性规划简介:

线性规划步骤:

(1)列出约束条件及目标函数。

(2)画出约束条件所表示的可行域。

(3)在可行域内求目标函数的最优解及最优值。

2、标准型:

描述线性规划问题的常用和最直观形式是标准型。标准型包括以下三个部分:

一个需要极大化的线性函数:

以下形式的问题约束:

和非负变量:

其他类型的问题,例如极小化问题,不同形式的约束问题,和有负变量的问题,都可以改写成其等价问题的标准型。

3、模型建立、

从实际问题中建立数学模型一般有以下三个步骤;

1、根据影响所要达到目的的因素找到决策变量。

2、由决策变量和所在达到目的之间的函数关系确定目标函数。

线性规划难题解法:

3、由决策变量所受的限制条件确定决策变量所要满足的约束条件。

所建立的数学模型具有以下特点:

1、每个模型都有若干个决策变量(x1,x2,x3……,xn),其中n为决策变量个数。决策变量的一组值表示一种方案,同时决策变量一般是非负的。

2、目标函数是决策变量的线性函数,根据具体问题可以是最大化(max)或最小化(min),二者统称为最优化(opt)。

3、约束条件也是决策变量的线性函数。

当我们得到的数学模型的目标函数为线性函数,约束条件为线性等式或不等式时称此数学模型为线性规划模型。

4、解法:

求解线性规划问题的基本方法是单纯形法,已有单纯形法的标准软件,可在电子计算机上求解约束条件和决策变量数达 10000个以上的线性规划问题。

为了提高解题速度,又有改进单纯形法、对偶单纯形法、原始对偶方法、分解算法和各种多项式时间算法。对于只有两个变量的简单的线性规划问题,也可采用**法求解。

这种方法仅适用于只有两个变量的线性规划问题。它的特点是直观而易于理解,但实用价值不大。通过**法求解可以理解线性规划的一些基本概念。

**法解线性规划问题:

对于一般线性规划问题:min z=cx、s.t、ax =b、x>=0其中a为一个m*n矩阵。

若a行满秩、则可以找到基矩阵b,并寻找初始基解。用n表示对应于b的非基矩阵。则规划问题1可化为:

规划问题2:

min z=cb xb+**xn。

线性规划法解题

s.t.b xb+n xn = b (1)、xb >= 0, xn >= 0 (2)(1)两边同乘于b-1,得xb + b-1 n xn = b-1 b。

同时,由上式得xb = b-1 b - b-1 n xn,也代入目标函数,问题可以继续化为:

规划问题3:

min z=cb b-1 b + ( ** - cb b-1 n ) xn、xb+b-1n xn = b-1 b (1)、xb >= 0, xn >= 0 (2)。

令n:=b-1n,b:= b-1 b,ζ= cb b-1b,σ= ** - cb b-1 n,则上述问题化为规划问题形式4:

min z= ζ + σ xn、xb+ n xn = b (1)、xb >= 0, xn >= 0 (2)。

在上述变换中,若能找到规划问题形式4,使得b>=0,称该形式为初始基解形式。

上述的变换相当于对整个扩展矩阵(包含c及a) 乘以增广矩阵。所以重在选择b,从而找出对应的cb。

若存在初始基解:若σ>= 0

则z >=ζ。同时,令xn = 0,xb = b,这是一个可行解,且此时z=ζ,即达到最优值。所以,此时可以得到最优解。

若不成立:

可以采用单纯形表变换。

σ中存在分量<0。这些负分量对应的决策变量编号中,最小的为j。n中与j对应的列向量为pj。

若pj <=0不成立。

则pj至少存在一个分量ai,j为正。在规划问题4的约束条件:

(1)的两边乘以矩阵t。

则变换后,决策变量xj成为基变量,替换掉原来的那个基变量。为使得t b >= 0,且t pj=ei(其中,ei表示第i个单位向量),需要:

l ai,j>0。

l βq+βi*(-aq,j/ai,j)>=0,其中q!=i。即βq>=βi/ ai,j * aq,j。

n 若aq,j<=0,上式一定成立。

n 若aq,j>0,则需要βq / aq,j >=βi/ ai,j。因此,要选择i使得βi/ ai,j最小。

如果这种方法确定了多个下标,选择下标最小的一个。

转换后得到规划问题4的形式,继续对σ进行判断。由于基解是有限个,因此,一定可以在有限步跳出该循环。

若对于每一个i,ai,j<=0最优值无解。

若不能寻找到初始基解无解。

若a不是行满秩化简直到a行满秩,转到若a行满秩。

怎么用两阶段法求解maxz= 2x1-x2+2x3 s.t.{x1+x2+x3>=6 -2x1+x3>=2 2x2-x3>=0 x1,x2,x3>=0}

3楼:少见多怪

(1)先将目标函数和约束条件化为标准型: max z=6x1-3x2+3x3+0x4+0x5+0x6 s.t.

3x1+x2+x3+x4=60 2x1-2x2+4x3+x5=20 3x1+3x2-3x3+x6=60 x1,x2,x3,x4,x5,x6>=0 首先将x1作为入基变量,x5作为出基变量求的目标函数为60 x1 x2 x3 x4 x5 x6 解 r 0 -。

单纯形法 max z=12x1+8x2+5x3 约束: 3x1+2x2+x3<=20 x1+x2+x3<=11 12x1+4x2+x3<=48 那些x后数字是下标

4楼:匿名用户

^解:a=矩阵[1,3,12 ;1,2,4;1,1,1]b=(12,8,5)

x=(x1,x2,x3)

ax=b

x=a^(-1)*b

(a,e)转换:

a^(-1)=0.4000 -1.8000 2.

4000-0.6000 2.2000 -1.

60000.2000 -0.4000 0.

2000x=2.4000

2.4000

0.2000

a1=x1+x2+x3

a2=3x1+2x2+x3

a3=12x1+4x2+x3

z=2.4*a1+2.4*a2+0.2*a3=<2.4*11+2.4*20+0.2*48=84

max z=84

分别用单纯形法中的的大m法和两阶段法求解下述线性规划问题,并指出属拿一类解 min z=2x1+3x2+x3满足约束 10

5楼:芩

大m法:先化成标准形

max z'=-2x1-3x2-x3+0x4+0x5-mx6-mx7s.t. x1+4x2+2x3-x4+x6=43x1+2x2-x5+x7=6

x1 x2 x3 x4 x5 x6 x7≥0最优解 x=(4/5,9/5,0,0,0,0)z最优值 min z=7

非基变量x3的检验数等于0,所以有无穷多最优解两阶段法:第一阶段最优解x=(4/5,9/5,0,0,0,0)是基本可行解 min z=0

第二阶段最优解 x=(4/5,9/5,0,0,0,0) min z=7

非基变量x3的检验数为0,所以有无穷多最优解

用单纯形法求解线性规划问题maxZ 2x1-x2+x3

1楼 立港娜娜 偶形式 2y1 y2 y3 2 3y1 2y2 3y3 4 求 max 24y1 10y2 15y3 优解 y1 0 y2 2 y3 0 优值20设原始问题min则其偶问题 max。 原问题引入人工变量x4,剩余变量x5,人工变量x6 。 maxz 2x1 3x2 5x3 mx4 m...