线性规划lingo实现示例

加工奶制品的生产计划

问题 品加工厂用牛奶生产A1，A2两种奶制品，1桶牛奶可以在设备甲用12小时加工成3公斤A1，或者在设备乙上用8小时加工成4公斤A2。根据市场需求，生产的A1，A2全部能售出，且每公斤A1获利24元，每公斤A2获利16元。现在加工厂每天能得到50桶牛奶的供应，每天正式工人总的劳动时间魏480小时，并且设备甲每天至多能加工100公斤A1，设备乙的加工能力没有限制。试为该厂制订一个生产计划，使每天获利最大，并进一步讨论以下三个附加问题：

1） 若用35元可以买到1桶牛奶，应否作这项投资？ 若投资，每天最多购买多少桶牛奶？

2） 若可以聘用临时工人以增加劳动时间，付给临时工人的工资最多是每小时几元？

3） 由于市场需求变化，每公斤A1的获利增加到30元，应否改变生产计划？

问题分析 这个优化问题的目标是使每天的获利最大，要作的决策是生产计划，即每天用多少桶牛奶生产A1，用多少桶牛奶生产A2，决策受到3个条件的限制：原料（牛奶）供应、劳动时间、设备甲的工作能力。按照题目所给，将决策变量、目标函数和约束条件用数学符号及式子表示出来，就得到下面的模型。

基本模型

决策变量：设每天用x1桶牛奶生产A1，用x2桶牛奶生产A2。

目标函数：设每天获利Z元。x1桶牛奶可生产3x1公斤A1，获利243x1，x2桶牛奶可

生产4x2公斤A2，获利164x2，故Z=72x164x2.

约束条件

原料供应：生产A1，A2的原料（牛奶）总量不得超过每天的供应，即x1+x250桶；

劳动时间：生产A1，A2的总加工时间不得超过每天正式工人总的劳动时间，即12x1+8x2480小时；

设备能力：A1的产量不得超过设备甲每天的加工能力，即3x1100；

非负：x1，x2均不能为负值，即x10，x20。

综上可得 Max Z=72x164x2 (1)

s.t. x1+x250 (2)

12x1+8x2480 (3)

3x1100； (4)

x10，x20 (5)

这就是该问题的基本模型。由于目标函数和约束条件对于决策变量而言都是线性的，所以称为线性规划（Linear Programming,简记作LP）.

模型分析与假设

1）A1，A2两种奶制品每公斤的获利是与它们各自产量无关的常数，每桶牛奶加工出A1，

A2的数量和所需时间是与它们各自产量无关的常数；

2）A1，A2每公斤的获利是与它们相互间产量无关的常数，每桶牛奶加工出A1，A2的数量和所需的时间是与它们相互产量无关的常数；

3）加工A1，A2的牛奶的桶数可以是任意实数。

软件实现 求解线性规划有不少现成的数学软件，比如用LINDO软件就可以很方便的实现。在LINDO6.1版本下打开一个新文件，像书写模型（1）—（5）一样，直接输入：

max 72x1+64x2

st

2)x1+x2<50

3)12x1+8x2<480

4)3x1<100

end

注：LINDO中已经规定所有的决策变量均为非负，故（5）式不必输入；乘号省略，

式中不能有括号，右端不能有数学符号；模型中符号，，用<=,>=形式输入，它们与<,>等效；输入文件中第一行为目标函数，2），3），4）是为了标示个约束条件，便于从输出结果中查找相应信息；程序最后以end结束。

将文件存储并命名后，选择菜单“solve”并对提示“DO RANGE(SENSITIVITY)ANALYSIS?”(灵敏性分析)回答“是”，即可得到如下输出：

LP OPTIMUM FOUND AT STEP 2

OBJECTIVE FUNCTION VALUE

1) 3360.000

VARIABLE VALUE REDUCED COST

X1 20.000000 0.000000

X2 30.000000 0.000000

ROW SLACK OR SURPLUS DUAL PRICES

2) 0.000000 48.000000

3) 0.000000 2.000000

4) 40.000000 0.000000

NO. ITERATIONS= 2

RANGES IN WHICH THE BASIS IS UNCHANGED:

OBJ COEFFICIENT RANGES

VARIABLE X1 X2 ROW 2 3 4 CURRENT ALLOWABLE ALLOWABLE

COEF INCREASE DECREASE

72.000000 24.000000 8.000000

64.000000 8.000000 16.000000

RIGHTHAND SIDE RANGES

CURRENT ALLOWABLE ALLOWABLE

RHS INCREASE DECREASE

50.000000 10.000000 6.666667

480.000000 53.333332 80.000000

100.000000 INFINITY 40.000000

上面结果的第3，5，6行明确告诉我们，这个线性规划的最优解为x1=20,x2=30,最优值为Z=3360，即用20桶牛奶生产A1，30桶牛奶生产A2，可获最大利润3360元。

结果分析

上面的输出中除了告诉我们问题的最优解和最优值以外，还有许多对分析结果有用的信息，下面结合题目中提出的3个附加问题给予说明。

（1）3个约束条件的右下端不妨看作3种“资源” ：原料、劳动时间、设备甲的加工能力。输出第7~10行“SLACK OR SURPLUS”给出这3种资源在最优解下是否有剩余：2）原料，3）劳动时间的剩余均为零，4）设备甲尚余40公斤加工能力。一般称“资源”剩余为零的约束称为紧约束。

（2）目标函数可以看作“效益” ，成为紧约束的“资源”一旦增加，“效益” 必然跟着增长。输出第7~10行“DUAL PRICE”给出这3种资源在最优解下“资源”增加一个单位时“效益”的增量：2）原料增加1个单位（1桶牛奶）时利润增长48元，3）劳动时间增加一个单位（1小时）时利润增加2元，而增加非紧约束4）设备甲的能力显然不会使利润增长。这里，“效益”的增量可以看作“资源”的潜在价值，经济学上称为影子价格，即1桶牛奶的影子价格为48元，1小时劳动的影子价格为2元，设备甲的影子价格为零。

可以用直接求解的方法验证上面的结论，即将输入文件中原料约束2）右端的50改为51，看看得到的最优值（利润）是否恰好增长48元。

用影子价格很容易回答附加问题1）：用35元可以买一桶牛奶，低于1桶牛奶的影子，

当然应该作这项投资。回答附加问题2）：聘用临时工人以增加劳动时间，付给的工资低于劳动时间的影子价格才可以增加利润，所以工资最多是每小时2元。

（3）目标函数的系数发生变化时（假定约束条件不变），最优解和最优值会改变吗？这个问题不能简单的回答。上面输出的第13~17行“CURRENT COEF”的“ALLOWABLE INCREASE”和“ALLOWABLE DECREASE”给出了最优解不变条件下目标函数系数的允许变化范围：x1的系数为（72-8，72+24），即（64，96）；x2的系数为（64-16，64+8），即（48，72）。注意：x1系数的允许范围需要x2 系数64不变，反之亦然。

用这个结果很容易回答附加问题3）：若每公斤A1的获利增加到30元，则x1的系数变为303=90，在允许范围内，所以不应该改变生产计划。

（4）对“资源”的影子价格作进一步的分析。影子价格的作用（即在最优解下“资源”增加1个单位时“效益”的增量）是有限制的。上面输出的第18~23行“CURRENT RHS”的“ALLOWABLE INCREASE”和“ALLOWABLE DECREASE”给出了影子价格有意义条件下约束右端的限制范围：2）原料最多增加10桶牛奶，3）劳动时间最多增加53小时。

现在可以回答附加问题1）的第2问：虽然应该批准用35元买一桶牛奶的投资，但每天最多购买10桶牛奶。顺便指出，可以用低于每小时2元的工资聘用临时工人以增加劳动时间，但最多增加53小时。