自考资讯

导航

自学考试《运筹学基础》章节习题及答案:第5章

来源 :中华考试网 2017-06-18

自学考试《运筹学基础》章节习题及答案:第5章

  第五章作业 线性规划P92

  1.线性规划的定义:线性规划是求一组变量的值,在满足一组约束条件下,求得目标函数的最优解,使决策目标达到最优。

  2.阐述线性规划的模型结构:(答案在书上68页)

  ·(1)变量是指实际系统或决策问题中有待确定的未知因素,也是指系统中的可控因素,一般来说,这些因素对系统目标的实现及各项经济指标的完成起决定作用,又称为决策变量。

  ·(2)目标函数是决策者对决策问题目标的数学描述是一个极值问题,即极大值或极小值。要依据经济规律的客观要求,并具体结合决策问题的实际情况来确定模型的目标函数。

  (3)·约束条件是指实现目标的限制因素,反映到模型中就是需要满足的基本条件即约束方程,一般是一组联立方程组或不等式方程组的数学形式。

  约束条件具有三种基本类型 :大于或等于;等于;小于或等于。

  (4)·线性规划的变量应为正值。

  线性规划明确定义:线性规划是求一组变量X1,X2,X3…的值,在满足一组约束条件下,求得目标函数的最优解(最大值或最小值)问题。

  3、解:本题是求解最大值的问题,和书上的例题5-3类似。

  首先拟定线性规划模型

  1)设定变量:

  设该电车本周生产甲车x辆,乙车y辆,丙车z辆。

  2)建立目标函数,求利润S 的最大值:

  maxS=270x+400y+450z

  3) 根据约束条件建立约束方程组:

  x+2y+3z <=100

  2x+2y+3z <=120

  4) 变量非负:

  x,y,z >=0

  建立初始单纯形表:

  1) 引入松弛变量

  x+2y+3z +k1=100

  2x+2y+3z +k2=120

  2)目标函数:maxS=270x+400y+450z+0*k1+0*k2

  3)变量非负

  4)建立初始单纯形表

  Cj 270 400 450 0 0 S

  基 x y z k1 k2

  ———————————————————————————

  0 k1 1 2 3 1 0 100

  0 k2 2 2 3 0 1 120

  ———————————————————————————

  Zj 0 0 0 0 0 0

  Cj-Zj 270 400 450 0 0 S

  分析上面的初始表,变量系数最大的是z

  k1所在行:100/3

  k2所在行:120/3=40

  所以选定 k1出基

  进行第一次迭代,得到如下单纯形表

  Cj 270 400 450 0 0 S

  基 x y z k1 k2

  ———————————————————————————

  450 z 1/3 2/3 1 1/3 0 100/3

  0 k2 1 0 0 -1 1 20

  ———————————————————————————

  Zj 150 300 450 150 0 15000

  Cj-Zj 80 100 0 -150 0 S-15000

  变量系数最大的是y,所以选择y作为基变量。

  z所在行:450/(2/3)=675

  k2所在行:20/1=20

  所以选定 k2出基

  进行第二次迭代,得到如下单纯形表

  Cj 270 400 450 0 0 S

  基 x y z k1 k2

  ———————————————————————————

  450 z 0 2/3 1 2/3 -1/3 80/3

  270 x 1 0 0 -1 1 20

  ———————————————————————————

  Zj 270 300 450 30 120 17400

  Cj-Zj 0 100 0 -30 -120 S-17400

  量系数最大的是y且是正数,所以选择y作为基变量。

  y所在行:(80/3)/(2/3)=40

  x所在行:20/0 =+∞

  +∞>40,所以z出基 (小于零的和除以0的应该不算)

  进行第三次迭代,得到如下单纯形表

  Cj 270 400 450 0 0 S

  基 x y z k1 k2

  ———————————————————————————

  400 y 0 1 3/2 3/2 -1/2 40

  270 x 1 0 0 -1 1 20

  ———————————————————————————

  Zj 270 400 600 330 70 21400

  Cj-Zj 0 0 -150 -330 -70 S-21400

  因为所有的系数都小于0,所以得到最优解。

  S=21400-150z-330k1-70k2

  当k1=k2=0时可得x=20,y=40

  所以该厂本周的产品组合应该为生产甲车20辆,乙车40辆

  4、解:MIN S=1.5X-2.5Y+18.5

  则S’=1.5X-2.5Y

  约束条件:X-Y-S1+A=1/4

  x-Y+S2=1/2

  X+Y+S3=1

  X+S4 =1

  Y+S5 =1

  标准型:MIN S’=1.5X-2.5Y+0S1+MA+0S2+0S3+0S4+0S5

  建立初始单纯行表:

  Cj 2/3 -2/5 0 M 0 0 0 0

  基 x y S1 A S2 S3 S4 S5 S

  ------------------------------------------------------------

  M A 1 -1 -1 1 0 0 0 0 1/4

  0 S2 1 -1 0 0 1 0 0 0 1/2

  0 S3 1 -1 0 0 1 1 0 0 1

  0 S4 1 0 0 0 0 0 1 0 1

  0 S5 0 1 0 0 0 0 0 1 1

  --------------------------------------------------------------

  ZJ M -M -M M 0 0 0 0 1/4M

  cj-zj 2/3-M -2/5+M M 0 0 0 0 0 s’-1/4m

  分析上面的初始表,变量系数最小的是x,所以选择x作为基变量。

  s/x 最小的是A

  所以选定 A出基

  进行第一次迭代,得到如下单纯形表:

  Cj 2/3 -2/5 0 M 0 0 0 0

  基 x y S1 A S2 S3 S4 S5 S

  ------------------------------------------------------------

  2/3 X 1 -1 -1 1 0 0 0 0 1/4

  0 S2 0 0 1 -1 1 0 0 0 1/4

  0 S3 0 2 1 -1 0 1 0 0 3/4

  0 S4 0 1 1 -1 0 0 1 0 3/4

  0 S5 0 1 0 0 0 0 0 1 1

  --------------------------------------------------------------

  ZJ 2/3 -2/3 -2/3 2/3 0 0 0 0 3/8

  cj-zj 0 -1 2/3 M-2/3 0 0 0 0 s’-3/8

  分析上面的初始表,变量系数最小的是Y,所以选择Y作为基变量。

s/x 最小的是S3(在这注意了S/Y Y必须是大于0的数,因此1/4*(—1)=-/4就不算,还有除以0的也不算。因此应该是S3出基)

  所以选定 S3出基

  进行第二次迭代,得到如下单纯形表:

  Cj 2/3 -2/5 0 M 0 0 0 0

  基 x y S1 A S2 S3 S4 S5 S

  ------------------------------------------------------------

  2/3 X 1 0 -1/2 1/2 0 1/2 0 0 5/8

  0 S2 0 0 1 -1 1 0 0 0 1/4

  -2/5 Y 0 1 1/2 -1/2 0 1/2 0 0 3/8

  0 S4 0 0 1/2 -1/2 0 -1/2 1 0 3/8

  0 S5 0 0 -1/2 1/2 0 -1/2 0 1 5/8

  --------------------------------------------------------------

  ZJ 2/3 -2/5 -2 2 0 -1/2 0 0 0

  cj-zj 0 0 2 M-2 0 1/2 0 0 s’

  此时S’=2S1+(M-2)A+1/2S3

  上式中X,Y,S1,A,S2,S3,S4,S5的数值均为正数。这就表明若我们给S1,A,S3以任何正数,都将使目标函数增大,因而只有当S1,A,S3 全为0时,才能求得目标函数的最小值。

  即:S’=0

  则最优解S=S’+18.5=18.5

  此时 X=0.625

  Y=0.375

分享到

您可能感兴趣的文章