运筹规划(二)-线性规划

如果一个优化模型的决策变量是连续,具有单一线性目标函数,而且所有约束都是关于决策变量的线性等式或是不等式,那么该优化模型称为线性规划。

资源分配模型

资源分配问题是一类简单、应用广泛的线性规划。其核心是在资源有限的情况下,如何将资源分配给彼此竞争的需求,从而实现资源的优化配置。这些资源可以是所有的有限资源。

时间分配问题

本学期,小明选修了运筹学、工程经济学、统计学和材料学4门功课。他一共有30个小时的复习时间来为考试做准备;他希望能够对有限的时间进行合理分配。他最喜欢的是运筹学,所以他在运筹学投入的时间不会低于其他课程。他认为每门功课复习操作10个小时用处不大。根据以往的经验,他在运筹上每投入1h能够提升2%的成绩,在工程经济学上每投入1h能够提升3%的成绩,在统计学上每投入1h能提高1%的成绩,在材料学上每投入1h呢个个提高5%的成绩,那么如何来构建小明的时间投入呢?

hjh_{j} :在第j门功课上投入的小时数

时间分配模型如下:

总成绩回报

max 2h1+3h2+h3+5h4s.t. h1+h2+h3+h4=30h1>hjhj<10hj<0max\ 2h_{1}+3h_{2}+h_{3}+5h_{4} \\ s.t.\ h_{1}+h_{2}+h_{3}+h_{4}=30 \\ h_{1}>h_{j} \\ h_{j} < 10 \\ h_{j} <0

以上这个例子就是典型的资源分配问题。

混料模型

资源分配模型是将各资源分配给不同的需求,混料模型是把零散的资源整合起来,简而言之就是混料模型需要决策是各种成分的组成以最好的满足产出的需求,现实生活中会有很对的混料模型的例子,包括化学配料、营养组合等。

瑞典钢材生产

钢铁行业的生产是通过高温熔化废料以生成新型的合金产品,这是一个典型的混料问题。
每次融入进料时都面临一个优化问题,为了生产出满足各种化学成分要求的合金产品,金属废料往往要加入一定的存添加剂。最大程度的利用金属废料是至关重要的,因为添加剂昂贵。
我们虚拟的瑞典铁厂计划生产1000千克的熔炉进料,所有的刚才主要的原料是铁。如表列举了4种废料的含量比、可用数量以及单位成本。表中也列出了3种可用的高成本纯添加剂以及各种元素的含量范围。比如要1000千克的钢材产成品中,碳含量应该是0.65%到0.75%之间。

碳(%) 镍(%) 铬(%) 钼(%) 可用量 成本
废料1 0.8 18 12 - 75 16
废料2 0.7 3.2 1.1 0.1 250 10
废料3 0.85 - - - 无限制 8
废料4 0.4 - - - 无限制 9
- 100 - - 无限制 48
- - 100 100 无限制 60
- - - - 无限制 53
成品中最低占比 0.65 3.0 1.0 1.1 - -
成品中最高占比 0.75 3.5 1.2 1.3 - -

原理1.1,混料模型中,决策变量可以设定为混合物中包含各种原料的数量。
上面的例子中一共有7个决策变量。
如上问题建模如下

min 16x1+10x2+8x3+9x4+48x5+60x6+53x7s.t. x1+x2+x3+x4+x5+x6+x7=10000.0080x1+0.007x2+0.0085x3+0.004x4>0.006510000.0080x1+0.007x2+0.0085x3+0.004x4<0.007510000.18x1+0.32x2+x5>0.0310000.18x1+0.32x2+x5<0.03510000.12x1+0.011x2+x5>0.0110000.12x1+0.011x2+x5<0.01210000.001x2+x7>0.01110000.001x2+x7<0.0131000x1<75x2<250min\ 16x_{1}+10x_{2}+8x_{3}+9x_{4}+48x_{5}+60x_{6}+53x_{7} \\ s.t.\ x_{1}+x_{2}+x_{3}+x_{4}+x_{5}+x_{6}+x_{7}=1000 \\ 0.0080x_{1}+0.007x_{2}+0.0085x_{3}+0.004x_{4}>0.0065*1000 \\ 0.0080x_{1}+0.007x_{2}+0.0085x_{3}+0.004x_{4}<0.0075*1000 \\ 0.18x_{1}+0.32x_{2}+x_{5}>0.03*1000 \\ 0.18x_{1}+0.32x_{2}+x_{5}<0.035*1000 \\ 0.12x_{1}+0.011x_{2}+x_{5}>0.01*1000 \\ 0.12x_{1}+0.011x_{2}+x_{5}<0.012*1000 \\ 0.001x_{2}+x_{7}>0.011*1000 \\ 0.001x_{2}+x_{7}<0.013*1000 \\ x_{1}<75 \\ x_{2} < 250

比例约束

上述问题中,碳含量下限约束可以表达为

0.0080x1+0.007x2+0.0085x3+0.004x4>0.0065j=17xj0.0080x_{1}+0.007x_{2}+0.0085x_{3}+0.004x_{4}>0.0065 *\sum_{j=1}^{7}x_{j}

也可以表达为

0.0080x1+0.007x2+0.0085x3+0.004x4j=17xj>0.0065\frac{0.0080x_{1}+0.007x_{2}+0.0085x_{3}+0.004x_{4}}{\sum_{j=1}^{7}x_{j}}>0.0065

第二种表达式不是线性的,然而,如果在不等式两边同时乘以分母(永远是非负的),就可以得到一个方向保持不变的线性不等式约束啦。

比率约束在混料模型中十分常见,比如原料3和原料4的比率不能超过2:3,其相应的约束条件就是表示为

x3x4<23\frac{x_{3}}{x_{4}}<\frac{2}{3}

因为分布大于0,同时乘以一个x4就能得到一个线性的不等式。
但是需要注意的是,并不是所有的比率约束都能转化成线性不等式。

x3x1x2<23\frac{x_{3}}{x_{1}-x_{2}}<\frac{2}{3}

虽然所有变量都是非负的,但是分布的正负不能判断,如果没有其他额外的信息,我们无法转为线性约束。

运营规划模型

另一种经典的线性规划模型是用于规划运营决策问题。从公益组织政府部分到制造型企业和分销企业等形形色色的组织中,规划者必须制定做什么,什么时候做,在哪里做等方面的决策,我们把这类问题称为运营规划模型

一家橙汁公司以每吨1500美元价格销售给零售商,销量可以达到15000吨。橙汁的生产可以通过橙汁榨汁,也可以通过浓缩的橙汁勾兑(1600美元/吨)得到。橙子的市场供应量为10000吨,1吨橙子能够榨汁0.2吨。浓缩的橙汁的供给足够大,每吨浓缩橙汁可以勾兑2吨橙汁。请指定一个线性规划模型帮助公司指定运营规划,以最大的公司的净利润最大。

x1x_{1}:用于榨汁的橙汁吨数。
x2x_{2}:用于勾兑的浓缩橙汁吨数。
x1x_{1}:销售的橙汁的吨数。

max 200x11600x2+1500x3s.t. x1<10000x3<150000.2x1+2x2=x3x1,x2,x3>0max\ -200x_{1} - 1600x_{2}+1500x_{3} s.t.\ x_{1}<10000 \\ x_{3}<15000 \\ 0.2x_{1}+2x_{2}=x_{3} \\ x_{1},x_{2},x_{3} >0

上述的线性规划中,目标函数是最大的销售收益和采购成本之间的差值。第1个约束是可以用于榨汁的橙子的数量限制,第2个是限制销售量最多15000吨,第3个是约束是产品销售中的平衡约束。
所谓平衡约束是构建决策变量之间的关系表达式。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×