运筹学复习笔记

几种产品,利润最大的线性规划数学模型

解题方法

  1. 设第一样有x1x_1,第二样有x2...x_2...
  2. 确定目标函数maxz=c1x1+c2x2+...+cnxnmax z= c_1x_1 + c_2x_2 + ... + c_nx_nminz=c1x1+c2x2+...+cnxnmin z= c_1x_1 + c_2x_2 + ... + c_nx_n
  3. 列个 s.t.{s.t.\lbrace 把各个约束条件列上去
  4. {\lbrace 最后写上 {\lbrace内各未知条件的取值范围

例题

某厂生产A、B、C三种产品,都需要用到煤、金属材料、电力资
源。各产品的单位产品利润、资源消耗以及现有生产资源如下:
image.png
问如何制定生产计划可使该厂利润最大,请建立线性规划数学模型。

解题步骤

  1. 设A产品的产量是x1x_1吨,设B产品的产量是x2x_2吨,设C产品的产量是x3x_3吨。\Rightarrow 煤共用了6x1+8x2+7x36x_1+8x_2+7x_3,金属共用了80x1+50x2+60x380x_1+50x_2+60x_3,电共用了50x1+10x2+30x350x_1+10x_2+30x_3,共赚了利润8x1+5x2+7x38x_1+5x_2+7x_3
  2. maxz=8x1+5x2+7x3maxz = 8x_1+5x_2+7x_3
  3. s.t.{6x1+8x2+7x354080x1+50x2+60x3400050x1+10x2+30x32000x1,x2,x30s.t.\begin{cases} 6x_1+8x_2+7x_3\leq540 \\ 80x_1+50x_2+60x_3 \leq 4000 \\ 50x_1+10x_2+30x_3 \leq 2000 \\ x_1,x_2,x_3 \geq 0 \end{cases}

化标准型

标准型目标:

  1. 目标函数为max的形式
  2. 多变量的式子都是等式
  3. 右侧的数字都是0\geq0
  4. 式子中的变量都是0\geq0

解题方法

  1. minα=amin \alpha=a变成maxβ=amax\beta=-a
  2. 将大括号中多变量的式子都变成等式(给不等式加上或减去某个0\geq0xnx_n,就能变成等式)
  3. 使所有式子最右边的数都0\geq0
  4. 将大括号中单变量的式子都变成啥0\geq0的形式,若某变量xm0x_m\leq0,则设置一个0\geq0的新变量xmx_m^\prime,使xm=xmx_m^\prime=-x_m,这样可以将xm0x_m\leq0变成xm0x_m^\prime\geq0
  5. 若某变量xpx_p没提到\是自由变量\是无约束变量,这说明xpx_p可正可负可为0,则两个0\geq0的新变量xpx_p^\primexpx_p^{\prime\prime}使xpxp=xpx_p^\prime - x_p^{\prime\prime}=x_p(因为两个0\geq0的数相减,结果就是可正可负可为0)
  6. 把大括号里所以单变量的式子,写到最下面一行。

例题

minz=3x1x2+2x3minz=3x_1-x_2+2x_3
s.t.{2x1+x24x31x1+2x2+2x32x1+x2=2x2,x30s.t.\begin{cases} 2x_1+x_2-4x_3\leq 1 \\ x_1+2x_2+2x_3 \geq 2 \\ x_1+x_2 = -2 \\ x_2 \geq , x_3 \leq 0 \end{cases}

解题步骤

  1. maxβ=3x1+x22x3max\beta = -3x_1+x_2-2x_3
  2. s.t.{2x1+x24x3+x4=1   x40x1+2x2+2x3x5=2   x50x1+x2=2x2,x30s.t.\begin{cases} 2x_1+x_2-4x_3 + x_4 = 1 ~~~ x_4\geq0 \\ x_1+2x_2+2x_3 -x_5 = 2 ~~~ x_5\geq0 \\ x_1+x_2 = -2 \\ x_2 \geq , x_3 \leq 0 \end{cases}
  3. s.t.{2x1+x24x3+x4=1   x40x1+2x2+2x3x5=2   x50x1x2=2x2,x30s.t.\begin{cases} 2x_1+x_2-4x_3 + x_4 = 1 ~~~ x_4\geq0 \\ x_1+2x_2+2x_3 -x_5 = 2 ~~~ x_5\geq0 \\ -x_1-x_2 = 2 \\ x_2 \geq , x_3 \leq 0 \end{cases}
  4. s.t.{2x1+x2+4x3+x4=1   x40x1+2x22x3x5=2   x50x1x2=2x2,x30s.t.\begin{cases} 2x_1+x_2+4x_3^\prime + x_4 = 1 ~~~ x_4\geq0 \\ x_1+2x_2-2x_3^\prime -x_5 = 2 ~~~ x_5\geq0 \\ -x_1-x_2 = 2 \\ x_2 \geq , x_3^\prime \geq 0 \end{cases}
  5. s.t.{2x12x1+x2+4x3+x4=1   x40x1x1+2x22x3x5=2   x50x1x1x2=2x10,x10,x2,x30s.t.\begin{cases} 2x_1^\prime- 2x_1^{\prime\prime} +x_2+4x_3^\prime + x_4 = 1 ~~~ x_4\geq0 \\ x_1^\prime- x_1^{\prime\prime}+2x_2-2x_3^\prime -x_5 = 2 ~~~ x_5\geq0 \\ x_1^{\prime\prime}- x_1^\prime-x_2 = 2 \\ x_1^\prime \geq0, x_1^{\prime\prime}\geq0 , x_2 \geq , x_3^\prime \geq 0 \end{cases}
  6. s.t.{2x12x1+x2+4x3+x4=1x1x1+2x22x3x5=2x1x1x2=2x10,x10,x2,x30,x40,x50s.t.\begin{cases} 2x_1^\prime- 2x_1^{\prime\prime} +x_2+4x_3^\prime + x_4 = 1 \\ x_1^\prime- x_1^{\prime\prime}+2x_2-2x_3^\prime -x_5 = 2 \\ x_1^{\prime\prime}- x_1^\prime-x_2 = 2 \\ x_1^\prime \geq0, x_1^{\prime\prime}\geq0 , x_2 \geq , x_3^\prime \geq 0 ,x_4\geq0 ,x_5\geq0\end{cases}

图解法

解题方法

  1. 画出x1Ox2x_1Ox_2坐标系,在坐标系中画出满足“{\begin{cases}\end{cases}”的区域MM
    a.把“{\begin{cases}\end{cases}”内每个不等式都尽量变成x2x_2如何的式子
    b.讲不等式中的\geq,\leq变成==,得到几条直线并将这些直线画到x1Ox2x_1Ox_2坐标系中。
    c.若原不等式是{x2?,   画出直线上面的区域x2?,   画出直线下面的区域\begin{cases} x_2\geq?, ~~~ \text{画出直线上面的区域} \\ x_2\leq?, ~~~ \text{画出直线下面的区域} \end{cases}
    若原不等式是{x1?,   画出直线右面的区域x1?,   画出直线左面的区域\begin{cases} x_1\geq?, ~~~ \text{画出直线右面的区域} \\ x_1\leq?, ~~~ \text{画出直线左面的区域} \end{cases}
    d.各区域重合部分为MM
    {区域M不存在,   则直接写答案,无解若区域M存在,   则继续步骤2\begin{cases} \text{区域M不存在}, ~~~ \text{则直接写答案,无解} \\ \text{若区域M存在}, ~~~ \text{则继续步骤2} \end{cases}

  2. 令目标函数左边等于0,得到直线LL,做出平行于直线LL,并且与MM相切的两条线,找出切点坐标,将坐标代入目标函数,求出值。

  3. 若要求maxmax,则得到最大值的切点为最优解;
    若要求minmin,则得到最肖值的切点为最优解;

注:若最优解是无数个点,则答:有无穷多解
若最优解在无穷远处,则答:解为无界解


运筹学复习笔记
https://www.zhaojun.inkhttps://www.zhaojun.ink/archives/36
作者
卑微幻想家
发布于
2021-03-16
许可协议