线性规划实际问题中如何寻找最优解

【摘要】最优解不是通过任何手段去精确得到的，利用“竹排法”通过一点一点移动参照线从可行域中找出来的才是真正的最优解。

【关键词】可行域；滑动；参照线

线性规划类的实际问题中，可行域一般都是一整片区域不存在间断现象，所以题目所要求的最优解无论精确到0.1还是精确到0.01，符合要求的最优解都确实存在在可行域中，我们要做的应该是把它找出来，而不是通过任何手段去精确。如何才能把它找出来呢？我的办法是，不考虑x、y需要精确的要求，先依其他条件列出不等式组，作出可行域，求出符合题中其他条件的最优解，然后看此最优解是否符合题目要求，若符合，则即为所求解．若不符合，则应继续滑动参照线，求出经过可行域内的符合要求的且与原点距离最远（或最近）的点的直线，在该线经过可行域的部分上寻找最优解即可。具体操作请看以下示范：

例：某工厂生产甲、乙两种产品，已知生产甲种产品1t需消耗A种矿石10t、B种矿石5t、煤4t；生产乙种产品1t需消耗A种矿石4t、B种矿石4t、煤9t。每1 t甲种产品的利润是600元，每1 t甲种产品的利润是1000元。工厂在生产这两种产品的计划中要求消耗A种矿石不超过300t、B种矿石不超过200t、煤不超过360t。甲、乙两种产品应各生产多少（精确到0.1t），能使利润总额达到最大？

分析：将已知数据列成下表1：

表1

解：设生产甲、乙两种产品分别为x t、y t，利润总额为z元，那么10x+4y3005x+4y2004x+9y360x0y0

Z=600x+1000y

图1

如图1：

作出以上不等式组的可行域如下

作直线：600x+1000y=0

即直线：3x+5y=0

把直线向右上方平移，使其划过可行域，此时3x+5y>0

当直线经过点M 时3x+5y达到最大,即z也达到最大，此时3x+5y= 209.655,

若要将最优解精确到0.1，需将直线向回平移到3x+5y=209.6,由3x+5y=209.64x+9y=360得到3x+5y=209.6与可行域左边界的交点A（12.343,34.514）,

由3x+5y=209.65x+4y=200得到3x+5y=209.6与可行域右边界的交点B（12.431,34.462）

可知有可能成为最优解的点的横坐标为12.4 代入3x+5y=209.6得到纵坐标约为34.48，不符合题目精确到0.1要求继续将直线向回平移到3x+5y=209.5 由3x+5y=209.54x+9y=360得到3x+5y=209.5与可行域左边界的交点C（12.214,34.571）由3x+5y=209.55x+4y=200得到3x+5y=209.5与可行域右边界的交点D(12.462,34.423)

可知有可能成为最优解的点的横坐标为12.3、12.4 ，将12.3代入3x+5y=209.5得到纵坐标约为34.52，将12.4代入3x+5y=209.5得到纵坐标约为34.46，均不符合题目精确到0.1要求继续将直线向回平移到3x+5y=209.4 ,由3x+5y=209.44x+9y=360得到3x+5y=209.4与可行域左边界的交点C（12.086,34.6284）,由3x+5y=209.45x+4y=200得到3x+5y=209.4与可行域右边界的交点D(12.4923，34.3846)

可知有可能成为最优解的点的横坐标为12.1、12.2、12.3、12.4 ，将12.1代入3x+5y=209.4得到纵坐标约为34.62，将12.2代入3x+5y=209.4得到纵坐标约为34.56，将12.3代入3x+5y=209.4得到纵坐标约为34.5，将12.4代入3x+5y=209.4得到纵坐标约为34.44，其中只有（12.3，34.5 ）符合要求。所以符合题目要求的最优解只有（12.3，34.5 ）

答：应生产甲种产品12.3吨，乙种产品34.5吨，能使利润总额达到最大。

实际问题有时要求精确到0.1，有时要求取整解，但无论哪一种，我们都要明确最优解绝不是我们能够按照四舍五入等原则取舍得到的，只有用“竹排法”通过一点一点滑动参照线从可行域中找出来的才是真正的最优解。

收稿日期：2012-04-05