线性规划中部分决策变量为0

线性规划模型是运筹学的重要分支，是20世纪三四十年代初兴起的一门学科.1947年美国数学家G.B.Dantzig及其同事提出的求解线性规划的单纯形法及其有关理论具有划时代的意义.他们的工作为线性规划这一学科的建立奠定了理论基础.随着1979年苏联数学家哈奇扬的椭球算法和1984年美籍印度数学家H.Karmarkar算法的相继问世，线性规划的理论更加完备、成熟，实用领域更加宽广.线性规划研究的实际问题多种多样，如生产计划问题、物资运输问题、合理下料问题、库存问题、劳动力问题、最优设计问题等，这些问题虽然出自不同的行业，有着不同的实际背景，但都是属于如何计划、安排、调度的问题，即如何物尽其用、人尽其才的问题.此外，线性规划的求解方法还在非线性规划的求解中得到应用或作为某种算法的子问题.

就模型而言，线性规划模型类似于高等数学中的条件极值问题，只是其目标函数和约束条件都限定为线性函数.线性规划模型的求解方法目前仍以单纯形法为主.

许多实际优化问题的数学模型往往都是一个线性规划问题（特别是在生产计划这样的经济管理领域）.这不是偶然的，我们来分析一下线性规划具有哪些特征，或者说实际问题具有什么性质，其模型就是一个线性规划问题.

比例性：每个决策变量对目标函数的“贡献”与该决策变量的取值成正比；每个决策变量对每个约束条件右端项的“贡献”与该决策变量的取值成正比.

可加性：各个决策变量对目标函数的“贡献”与其他决策的取值无关；各个决策变量对每个约束条件右端项的“贡献”与其他决策变量的取值无关.

连续性：每个决策变量的取值是连续的.

比例性和可加性保证了目标函数和约束条件对于决策变量的线性性，连续性则允许得到决策变量的实数最优解.

人们处理的最优化问题，小至简单思索的某个决策，大至构成一个大型的科学计算问题，都具有三个基本要素，即变量、目标和约束条件.线性规划也不例外，其模型的建立离不开三个要素.建立线性规划模型的关键是明确问题的决策变量、目标函数和约束条件.

决策变量：是决策者可以控制的因素，例如根据不同的实际问题，决策变量可以选为产品的产量、物资的运量及工作的天数等.

目标函数：是以函数形式来表示的决策者追求的目标.例如目标可以是利润最大或成本最小等.对于线性规划，目标函数要求是线性的.

约束条件：是决策变量需要满足的限定条件.对于线性规划，约束条件是一组线性等式或不等式.

例5-1　机床加工问题

某机床厂生产甲、乙两种机床，每台销售后的利润分别为4000元与3000元.生产甲机床需用A、B机器加工，加工时间分别为每台2 h和1 h；生产乙机床需用A、B、C三种机器加工，加工时间为每台各1 h.若每天可用于加工的机器时数分别为A机器10 h、B机器8 h和C机器7 h，问该厂每天应生产甲、乙机床各几台，才能使总利润最大？

【解题思路】

这个优化问题的目标是使每天的获利最大，要做的决策是生产计划，即每天生产甲机床多少台、乙机床多少台，决策受到设备加工能力的限制.按照题目所给，将决策变量、目标函数和约束条件用数学符号及式子表示出来，就可以得到下面的数学模型.

设为使总利润最大，生产x₁台甲机床、x₂台乙机床，此时获利为z元.故z=4000x₁+3000x₂.生产x₁台甲机床，x₂台乙机床，需要A机器工作（2x₁+x₂）h，需要B机器工作（x₁+x₂）h，需要C机器工作x₂ h.每天可用于加工的机器时数分别为A机器10 h、B机器8 h和C机器7 h，即：2x₁+x₂≤10，x₁+x₂≤8，x₂≤7；x₁，x₂均不能为负值，即x₁≥0，x₂≥0.当需要进行决策的时期非常长时，每天生产的甲、乙两种机床数量可以视为连续实数，这样也就满足线性规划的三种条件.

最后有如下数学模型：

在建立线性规划数学模型之后需要解决的问题就是如何将模型求解出来.解决线性规划的单纯形法理论已经相当成熟，可以通过该方法求解.但是，当决策变量很多的情况下，人工使用单纯形法已经不是一种聪明的选择.竞赛的时间是非常宝贵的，因此可以通过数学软件进行求解.Matlab也可以求解线性规划问题，但是Lindo软件表现得更为专业，而且Lindo的使用很简练、很容易让人掌握.Lindo语法与Lingo语法非常接近，因此学好Lindo对Lingo的学习也是很有帮助的.接下来通过实例让大家了解Lindo的语法操作.

Lindo线性规划源程序如下所示：

max 4000x1+3000x2

s.t. 2x1+x2＜=10 x1+x2＜=8 x2＜=7 x1＞=0 x2＞=0

其中第一行为目标函数，首先用max或者min声明求解的目标函数最大化或者最小化，然后键入目标函数.可见在Lindo的语法操作中没有乘号，也不允许出现乘号，末尾结束不出现分号.第二行以s.t.（subject to）开始键入约束条件，不同约束条件之间需要空格或者换行.

按住Ctrl＋S运行，得到运行结果如下：LP OPTIMUM FOUND AT STEP　　　0

OBJECTIVE FUNCTION VALUE

1）　　　26000.00

VARIABLE　　　　VALUE　　　　　REDUCED COST

　　X1　　　　2.000000　　　　　0.000000

　　X2　　　　6.000000　　　　　0.000000

ROW　　SLACK OR SURPLUS　　　DUAL PRICES

2）　　　　0.000000　　　　　1000.000000

3）　　　　0.000000　　　　　2000.000000

4）　　　　1.000000　　　　　　0.000000

5）　　　　2.000000　　　　　　0.000000

6）　　　　6.000000　　　　　　0.000000

NO.ITERATIONS=　　　　0

RANGES IN WHICH THE BASIS IS UNCHANGED：

OBJ COEFFICIENT RANGES

VARIABLE　　CURRENT　　　　ALLOWABLE　　　　ALLOWABLE

COEF　　　　　INCREASE　　　　DECREASE

　　X1　　4000.000000　　　2000.000000　　　1000.000000

　　X2　　3000.000000　　　1000.000000　　　1000.000000

RIGHTHAND SIDE RANGES

ROW　　CURRENT　　　　ALLOWABLE　　　ALLOWABLE

RHS　　　　　INCREASE　　　　DECREASE

2　　　10.000000　　　　6.000000　　　　1.000000

3　　　8.000000　　　　0.500000　　　　3.000000

4　　　7.000000　　　　INFINITY　　　　1.000000

5　　　0.000000　　　　2.000000　　　　INFINITY

6　　　0.000000　　　　6.000000　　　　INFINITY

在上述运行结果中，除了可以得到该问题的最优决策变量值和最优目标函数值以外，还有许多对结果分析有用的信息.结果的第一部分显示：单纯形法通过0次迭代可以得到最优目标函数值26000.即最优决策下可获利26000元.结果的第二部分显示决策变量：x₁＝2，x₂＝6.此时才能得到目标函数的最优值，而后面显示了约束的性质.

4个约束条件的右端不妨看做4种“资源”.输出中“SLACK OR SURPLUS”给出这4种资源在最优解下是否有剩余，其中机器C尚余1 h的加工能力，机器A和机器B的加工能力已经没有剩余.一般称“资源”剩余为零的约束为紧约束（有效约束）.

成为紧约束的“资源”一旦增加，“效益”必然跟着增长.输出中“DUAL PRICES”给出这几种资源在最优解下“资源”增长1个单位时“效益”的增量：当机器A的加工能力增加1个单位（1 h）时利润增长1000元，机器B的加工能力增加1个单位（1 h）时利润增长2000元，而增加非紧约束（机器C的能力）显然不会使利润增长.这里，“效益”的增量可以看做“资源”的潜在价值，经济学上称为影子价格，即机器A 加工1 h的影子价格为1000元，机器B加工1 h的影子价格为2000元，机器C的影子价格为零.各位可以用直接求解的办法验证上面的结论，即将输入文件中机器A的加工时间约束右端的10改为11，看看得到的最优值（利润）是否恰好增长1000元.

在使用Lindo求解线性规划的过程中，当点击运行时，会弹出一对话框，询问是否做灵敏度分析.这也是Lindo求解的一个优势，其支持对于问题的灵敏度分析.

目标函数的系数发生变化时（假定约束条件不变），最优解和最优值会改变吗？输出中“CORRENT COEF”的“ALLOWABLE INCREASE”和“ALLOWABLE DECREASE”给出了最优决策变量值不变条件下目标函数系数允许改变的范围：x₁的系数为（4000-1000，4000+2000），即（3000，6000）；x₂的系数为（3000-1000，3000+1000），即（2000，4000）.即当市场价格发生变动时，如x₁的单价在（3000，6000）之间变动，决策变量不变可以取得最优决策变量值，但是此时的最优目标函数值将会发生变化.需要注意的是：x₁系数的允许范围需要x₂系数不变，反之亦然.

对“资源”的影子价格作进一步的分析.影子价格的作用是有限制的.输出中“CURRENT RHS”的“ALLOWABLE INCREASE”和“ALLOWABLE DECREASE”给出了影子价格有意义条件下约束右端的有限制范围：机器A的工作时间最多增加6 h，机器B的工作时间最多增加0.5 h.

例5-2　利润优化问题

某工厂在计划期内要安排生产甲、乙两种产品，已知生产单位产品所需的设备台数及A、B两种原料的消耗如表5-2所示.该工厂每生产一件产品甲可获利2元，每生产一件产品乙可以获利3元，问应如何安排生产计划使工厂获利最多.

表5-2　产品消耗表

【解题思路】

设x₁，x₂分别表示在计划期内生产甲、乙的产量.因为设备的有效台数为8台，这是一个生产条件的限制，所以在确定甲、乙的产量时，要考虑不超过设备的有效台数，即可用不等式表示为：x₁+x₂≤8.同理，因原材料A、B的限量，可以得到以下不等式：4x₁≤16，4x₂≤12，该工厂的目标是在不超过所有资源限制的条件下，如何确定产量以得到最大的利润.若用z表示利润，则有：z=2x₁+3x₂.综上所述，该计划问题可用数学模型表示为：

Lindo线性规划源程序如下所示：

max 2x1+3x2

s.t. x1+x2＜=8 x1＜=4 x2＜=3 x1＞=0 x2＞=0按住Ctrl＋S运行，得到运行结果如下：LP OPTIMUM FOUND AT STEP　　　2

OBJECTIVE FUNCTION VALUE

1）　　　17.00000

VARIABLE　　　　VALUE　　　　　REDUCED COST

　　X1　　　　4.000000　　　　　0.000000

　　X2　　　　3.000000　　　　　0.000000

ROW　SLACK OR SURPLUS　　DUAL PRICES

2）　　　　1.000000　　　　　0.000000

3）　　　　0.000000　　　　　2.000000

4）　　　　0.000000　　　　　3.000000

5）　　　　4.000000　　　　　0.000000

6）　　　　3.000000　　　　　0.000000

NO.ITERATIONS=　　　2

RANGES IN WHICH THE BASIS IS UNCHANGED：

OBJ COEFFICIENT RANGES

VARIABLE　　　CURRENT　　　　ALLOWABLE　　　　ALLOWABLE

COEF　　　　　INCREASE　　　　DECREASE

X1　　　　2.000000　　　　INFINITY　　　　2.000000

X2　　　　3.000000　　　　INFINITY　　　　3.000000

RIGHTHAND SIDE RANGES

ROW　　CURRENT　　　　ALLOWABLE　　　　ALLOWABLE

RHS　　　　　INCREASE　　　　DECREASE

2　　　　8.000000　　　　INFINITY　　　　1.000000

3　　　　4.000000　　　　1.000000　　　　4.000000

4　　　　3.000000　　　　1.000000　　　　3.000000

5　　　　0.000000　　　　4.000000　　　　INFINITY

6　　　　0.000000　　　　3.000000　　　　INFINITY

通过2次迭代可以得到问题的最优值17，此时工厂所该做的正确决策为生产甲产品4个，生产乙产品3个.

通过上面两个例子，希望大家能够明白如何建立线性规划，以及如何通过Lindo求解线性规划.在图5-1中，可以看到Lingo也可以用以求解线性规划.那么通过下面一个例子加以说明，如何通过Lingo软件求解线性规划.

例5-3 居民用水问题

某市有甲、乙、丙、丁四个居民区，自来水由A、B、C3个水库供应.4个区每天必须得到保证的基本生活用水分别为30千吨、70千吨、10千吨、10千吨，但由于水源紧张，3个水库每天最多只能分别供应50千吨、60千吨、50千吨自来水.由于地理位置的差别，自来水公司从各水库向各区送水所需付出的引水管理费不同（见表5-3，其中C水库与丁区之间没有输水管道），其他管理费用都是450元/千吨.根据公司规定，各区用户按照统一标准900元/千吨收费.此外，4个区都向公司申请了额外用水费，分别为每天50千吨、70千吨、20千吨、40千吨.该公司应如何分配供水量，才能获利最多？

表5-3　引水费用表

【解题思路】

分配供水量就是安排从3个水库向4个区送水的方案，目标是获利最多.而从题目给出的数据看，A、B、C3个水库的供水量160千吨，不超过4个区的基本生活用水量与额外用水量之和300千吨，因而总能全部卖出并获利，于是自来水公司每天的总收入是900×（50＋60＋50）＝144000元，与送水方案无关.同样，公司每天的其他管理费用为450×（50＋60＋50）＝72000元也与送水方案无关.所以，要使利润最大，只需使引水管理费最小即可.另外，送水方案自然要受3个水库的供应量和4个区的需求量的限制.

很明显，决策变量为A、B、C3个水库（i＝1，2，3）分别向甲、乙、丙、丁4个区（j＝1，2，3，4）的供水量.设水库i向j区的日供水量为x_ij.由于C水库与丁区之间没有输水管道，即x₃₄=0，因此只有11个决策变量.由以上分析，问题的目标可以从获利最多转化为引水费用最少，于是有：

约束条件有两类：一类是水库的供应量限制，另一类是各区的需求量限制.

Lingo线性规划源程序如下所示：

Model：

min=160*x11+130*x12+220*x13+170*x14+140*x21+130*x22+190*x23+150 *x24+190*x31+200*x32+230*x33；

x11+x12+x13+x14=50；x21+x22+x23+x24=60；x31+x32+x33=50；

x11+x21+x31＞=30；x12+x22+x32＞=70；x13+x23+x33＞=10；

x14+x24＞=10；x11+x21+x31＜=80；x12+x22+x32＜=140；

x13+x23+x33＜=30；x14+x24＜=50；

其中第二行为目标函数，首先用max＝或者min＝声明求解的目标函数最大化或者最小化，然后键入目标函数.与Lindo语法不同，在Lingo的语法操作中有乘号，就一定要乘号，末尾结束出现分号.而且数值不能出现在左边，键入的表达式应该为最简表达式.

按住Ctrl＋S运行，得到运行结果如下：Global optimal solution found．

Objective value：　　　　　　　　　　　　　　24400.00

Total solver iterations：　　　　　　　　　　　　8

X11　　0.000000　　30.00000　　1　　24400.00　　-1.000000

X12　　50.00000　　0.000000　　2　　0.000000　　-130.0000

X13　　0.000000　　50.00000　　3　　0.000000　　-130.0000

X14　　0.000000　　20.00000　　4　　0.000000　　-190.0000

X21　　0.000000　　10.00000　　5　　10.00000　　0.000000

X22　　50.00000　　0.000000　　6　　30.00000　　0.000000

X23　　0.000000　　20.00000　　7　　0.000000　　-40.00000

X24　　10.00000　　0.000000　　8　　0.000000　　-20.00000

X31　　40.00000　　0.000000　　9　　40.00000　　0.000000

X32　　0.000000　　10.00000　　10　　40.00000　　0.000000

X33　　10.00000　　0.000000　　11　　20.00000　　0.000000

　　　　　　　　　　　　　　　12　　40.00000　　0.000000

Lingo得到的结果与Lindo得到的结果类似，但是Lingo不支持灵敏度分析.上述结果显示：通过8次迭代可以得到全局最优值24400.工厂A向乙地区供应50千吨自来水；工厂B向乙提供50千吨自来水，向丁提供10千吨自来水；工厂C向甲地区提供40千吨自来水，向丙地区提供10千吨自来水.结果后一部分为自来水供应的影子价格分析.

需要注意的是：Lindo和Lingo在求解规划问题时，可能存在多个最优决策都能得到最优值，但是软件只会显示其中一种.Lindo公司已经将Lindo软件从其产品目录中删除，这意味着以后不会再有Lindo软件的新版本了，而Lingo还在不断地更新.从上面的编程过程中，大家可以发现一个问题：当决策变量或者约束很多时，一条一条输入约束将是一件非常麻烦的事情.Lingo语言又称为建模化语言，其优势在于它能够支持数学语言的输入，尤其是能够提供集合支持，给编程带来了极大的便利.依然是例5-3，使用建模化语言编程代码如下所示.

Lingo建模化语言解决线性规划问题源代码如下：

model：

sets：

chandi1..3：a；

yonghu1..4：b，d；

routes（chandi，yonghu）：c，x；

endsets

data：

a=50，60，50；

b=30，70，10，10；

d=80，140，30，50；

c=160，130，220，170，

140，130，190，150，

190，200，230，99999999；

enddata

min=@sum（routes∶c*x）；

@for（chandi（i）：@sum（yonghu（j）：x（i，j））=a（i））；

@for（yonghu（j）：@sum（chandi（i）：x（i，j））＜=d（j））；

@for（yonghu（j）：@sum（chandi（i）：x（i，j））＞=b（j））；

End

与以前的Lindo，Lingo语法不同，程序首先定义了集合，以sets开始，定义了三种属性的集合：a为1×3的向量，b和d为1×4的向量，c和x为3×4的矩阵，以endsets结束.然后对定义的集合进行数据初始化，以data开始：分别对a，b，c，d进行初始化.其中由于自来水厂c不能给用户丁供水，因此可以定义一个非常大的数，代表非常大的代价，以enddata结束.接下去的就是目标函数和约束条件，在目标函数中使用了@sum求和函数，在约束中使用了@for循环函数.可见，如果决策变量或者约束很多，也可以不用一条一条输入了，只需要一条循环便可以解决.得到结果如下所示：

Global optimal solution found．

Objective value：　　　　　　　　　　　　　　　24400.00

Total solver iterations：　　　　　　　　　　　　　8

Variable　Value　Reduced Cost　Row　Slack or Surplus　Dual Price

A（1）　　50.00000　　0.000000　　1　　24400.00　　-1.000000

A（2）　　60.00000　　0.000000　　2　　0.000000　　-130.0000

A（3）　　50.00000　　0.000000　　3　　0.000000　　-130.0000

B（1）　　30.00000　　0.000000　　4　　0.000000　　-190.0000

B（2）　　70.00000　　0.000000　　5　　40.00000　　0.000000

B（3）　　10.00000　　0.000000　　6　　40.00000　　0.000000

B（4）　　10.00000　　0.000000　　7　　20.00000　　0.000000

D（1）　　80.00000　　0.000000　　8　　40.00000　　0.000000

D（2）　　140.0000　　0.000000　　9　　10.00000　　0.000000

D（3）　　30.00000　　0.000000　　10　　30.00000　　0.000000

D（4）　　50.00000　　0.000000　　11　　0.000000　　-40.00000

C（1，1）　　160.0000　　0.000000　　12　　0.000000　　-20.00000

C（1，2）　　130.0000　　0.000000　　　　　　

C（1，3）　　220.0000　　0.000000　　　　　　

C（1，4）　　170.0000　　0.000000　　　　　　

C（2，1）　　140.0000　　0.000000　　　　　　

C（2，2）　　130.0000　　0.000000　　　　　　

C（2，3）　　190.0000　　0.000000　　　　　　

C（2，4）　　150.0000　　0.000000　　　　　　

C（3，1）　　190.0000　　0.000000　　　　　　

C（3，2）　　200.0000　　0.000000　　　　　　

C（3，3）　　230.0000　　0.000000　　　　　　

C（3，4）　　0.1000000E+09　　0.000000　　　　　　

X（1，1）　　0.000000　　30.00000　　　　　　

X（1，2）　　50.00000　　0.000000　　　　　　

X（1，3）　　0.000000　　50.00000　　　　　　

X（1，4）　　0.000000　　20.00000　　　　　　

X（2，1）　　0.000000　　10.00000　　　　　　

X（2，2）　　50.00000　　0.000000　　　　　　

X（2，3）　　0.000000　　20.00000　　　　　　

X（2，4）　　10.00000　　0.000000　　　　　　

X（3，1）　　40.00000　　0.000000　　　　　　

X（3，2）　　0.000000　　10.00000　　　　　　

X（3，3）　　10.00000　　0.000000　　　　　　

X（3，4）　　0.000000　　0.9999979E+08

上述结果显示：通过8次迭代可以得到全局最优值24400.x就是所需的决策变量矩阵，工厂A向乙地区供应50千吨自来水；工厂B向乙提供50千吨自来水，向丁提供10千吨自来水；工厂C 向甲地区提供40千吨自来水，向丙地区提供10千吨自来水.结果后一部分为自来水供应的影子价格分析，与以前得到的结果相同.

通过以上三例可以看出：尽管所提问题的内容不同，但从构成数学问题的结构来看却属于同一优化问题，其结构具有如下特征：目标函数是决策变量的线性函数；约束条件都是决策变量的线性等式或不等式.具有以上结构特点的模型就是线性规划模型，简记为LP，它具有一般形式为：