线性规划

第一部分 线性规划

线性规划中研究的问题要求目标与约束条件函数均是线性的，而目标函数只能是一个．在经济管理与工程技术的问题中，大量的问题是线性的，有的可以转化为线性的，从而使线性规划有着极大的应用价值．线性规划已经成为现代化管理的一种重要手段．

第一节 线性规划问题的模型与基本理论

一、引例

案例1.1 火电厂动力配煤问题［1］

大型火力发电厂大部分使用煤粉锅炉, 而锅炉技术特性是根据给定燃煤质量设计的, 只有在燃煤质量符合锅炉设计要求时, 锅炉才能保持最佳运行状态。

动力配煤是根据工业锅炉对煤质的特定要求, 由几种不同性质, 不同种类的煤按一定比例掺配加工而成的燃料。通过配煤使燃料的主要技术指标适应炉型要求, 保证工业锅炉出力稳定,热效率高。对火力发电厂而言, 发电煤耗是最主要的成本指标, 所以合理的配煤方案不仅能提高发电厂的生产能力和发电效率, 而且还能够降低发电成本。

某火力发电厂, 日用燃煤量为1 万t , 该厂煤粉锅炉的燃料煤的质量要求见表1－1。该厂可选1、2、3、4 号矿井的煤炭产品进行动力配煤作为煤粉锅炉的燃料, 各矿煤炭产品的产量、煤质及购价(包括运费) 见表1－2。求发电用煤成本最低的配煤方案。

表1－1 某火电厂用煤质量要求

粒度/ mm 灰分Ad / % 硫分St ,d / % 挥发分Vdaf/ % 发热量Qnet ,ar/ kJ ·kg - 1 水分Mt/ % 灰熔点ST/ ℃

小于 小于 小于 大于 大于 小于 大于

13 24 1 27 17325.4 6 1350

表1－2 某火电厂可选购煤炭产品的质量指标和购价表

指标 单位 1号矿井 2号矿井 3号矿井 4号矿井

粒度 mm 13 13 13 13

灰分Ad % 23 22 25 23

硫分St ,d % 0.7 0.9 1 1.4

水分Mt % 5 7 5 7

挥发分Vdaf % 26.04 30.2 25 35

发热量Qnet ,ar /kJkg 16730 18815 16625 17022

灰熔点ST 0C 1360 1400 1355 1390

产量 t /d 9000 7000 4000 2000

购价 元/t 75.5 80 65 71

解：对于该火力发电厂的配煤问题，设(1,2,3,4)ixi是使用i号矿井煤的使用比 例，为满足燃料煤的质量要求，必须满足如下条件：

灰分要求： 12342322252324xxxx

硫分要求： 12340.70.91.41xxxx

挥发分要求：123426.0430.2253527xxxx

发热量要求：12341673018815166251702217325.4xxxx

水分要求： 123457576xxxx

灰熔点要求：123413601400135513901350xxxx

由于各号矿井的生产能力有一定限制，因此还必须满足：

1号矿井的生产能力限制 : 9000100001x

2号矿井的生产能力限制 : 7000100002x

3号矿井的生产能力限制 ：4000100003x

4号矿井的生产能力限制 : 2000100004x

自然限制条件：

12341xxxx

0,(1,2,3,4)ixi

发电用煤的单位成本为

75.5806571zxxxx

综上分析，该火力发电厂的配煤问题的数学模型为

12341234123412341234123412341min75.580657123222523240.70.91.4126.0430.22535271673018815166251702217325.45757613601400135513901350..10009000zxxxxxxxxxxxxxxxxxxxxxxxxxxxxstx234123410007000100040001000200010,(1,2,3,4)ixxxxxxxxi 案例1.2 投资计划问题

通达公司是某电力公司下属的三产公司。该公司在今后三年内有四种投资机会：第1种是3年内每年年初投资，年底可获利润15％，并可将本金收回；第2种是在第一年的年初投资，第二年年底可获利润40％，并将本金收回，考虑到可能存在的风险，该项投资不得超过200万元；第3种是在第二年的年初投资，第三年年底收回本金，并获利润50％，考虑到可能存在的风险，该项投资不得超过150万元：第4种是在第三年的年初投资，于该年年底收回本金，且获利润40％，考虑到可能存在的风险，该项投资不得超过100万元。现在该公司准备拿出300万元资金，问如何制定投资计划．使到第三年年末本利和最大。

解：设置变量如下表，

投资机会1 投资机会2 投资机会3 投资机会4

第一年

1x 4x

第二年

2x

5x

第三年

3x

6x

下面通过讨论逐年的资金使用情况来分析约束条件和目标函数：

第一年年初，可供使用资金为300万元，有两种投资机会，投资额分别是1x，4x，因此

14=300xx

另外，第2种投资不得超过200万元，故有4200x。

第二年年初，可供使用资金为11.15x万元，有两种投资机会，投资额分别是2x，5x，因此

251=1.15xxx

另外，第3种投资不得超过150万元，故有5150x。

第三年年初，可供使用资金为241.151.4xx万元，有两种投资机会，投资额分别是3x，6x，因此

3624=1.151.4xxxx

另外，第4种投资不得超过100万元，故有6100x。

第三年年年末资金的本利和为3561.151.51.4xxx。

综合上述分析，将各条件中含变量的项移到方程左边，并注意到个项目的投资额不能是负数，可得投资计划问题的数学模型为

356141252436456123456max1.151.51.4=3001.15=01.151.4=0..200150100,,,,,0zxxxxxxxxxxxxstxxxxxxxxx

二、线性规划模型

一般线性规划问题的建模过程：

1．理解要解决的问题，要搞清在什么条件下，要追求什么目标。

2．定义决策变量，每一个问题都用一组决策变量12(,,,)Tnxxx来表示某一方案；这组决策变量的值就代表一个具体方案，一般这些变量取值是非负的。

3．用一组决策变量的线性等式或不等式来表示在解决问题过程中所必须遵循的约束条件。

4．用决策变量的线性函数形式写出所要追求的目标，称之为目标函数，按实际问题的不同，要求目标函数实现最大化或最小化。

线性规划一般模型：

1122min(max)nnzcxcxcx

1111221121122222112212(,)(,)...........................................(,),,,nnnnmmmnnmnaxaxaxbaxaxaxbstaxaxaxbxxx取值符号限制。

标准型：

1122maxnnzcxcxcx （1－1）

1111221121122222112212...........................................0),,,0nnnnimmmnnmnaxaxaxbaxaxaxbstbaxaxaxbxxx（ （1－2）

标准化步骤：

1）目标函数的标准化。minsCx，令s= -z，得：maxzCx，

2）决策变量的标准化。

'''''='''00,0kkkkkxxkkxxxkkkxxxxx无约束

3）约束常数的标准化。如果有某约束常数为负数，可在等式（或不等式）两边同时乘以-1，把约束常数变为正数。

约束不等式的标准化当约束条件为"≤"形式的不等式，可在不等式左边加上一个非负的新变量，也就是松弛变量，把不等号变为等号；当约束条件为"≥"形式的不等式，可在不等式左边减去一个非负的剩余变量（也可称松弛变量），把不等号变为等号。

例1－1。把下面线性规划模型化为标准型：

12max510zxx

12121212350240..2250,xxxxstxxxx无约束

解:令234xxx,引入松弛变量567,,xxx,上述线性规划模型可化为如下标准型:

max z=5x1+10x3-10x4

1345134613473350240..22250,1,3,4,5,6,7jxxxxxxxxstxxxxxj

例1－2 把下面线性规划模型化为标准型：

1234123412341234213min23523402430.4327501010,0sxxxxxxxxxxxxstxxxxxxx

解：设2244''''''24,,xxxxxxzs，

标准型为

12234412234451223446122344227228122344max2()35()()23()+402()4()+3043()27()50.()10()10,,,,,zxxxxxxxxxxxxxxxxxxxxxxxxxxstxxxxxxxxxxxxx5678,0xxx，，