线性规划中的整点问题求解方法.pdf

线性规划中的整点问题求解方法

宜昌市一中祝海燕

线性规划是运筹学的一个重要分支，在实际生活中有着广泛的应用。新教材中增加了

线性规划的内容，充分体现了数学的实际应用，发展了学生的数学应用意识。由于实际问

题中线性规划问题的最优解多为整数解，也是学生学习线性规划的难点，因而求线性规划

的整数最优解的方法就显得尤为重要了。但教材中对此类问题却一带而过，对于具体的验

算过程并没有作必要的描述，以致学生在解题过程中对于具体的验算过程掌握还不够清

晰。以下为教材（人教版必修第二册上，2006年第2版）第69页的例4：

要将两种大小不同的的

钢板截成A、B、C三种规格，钢板类型规格类型A规格B规格C规格

每张钢板可同时截得三种规第一种钢板211

格的小钢板的块数如表所第二种钢板123

示，今需要A、B、C三种规

格的成品分别为15，18，27块，问各截这

两种钢板多少张可得所需三种规格成品，

15

且使所用钢板张数最少。

解：设需要截第一种钢板x张，第二

B(3,9)

2xy159

1839C(4,8)

x2y18A(,)

张钢板y张，则x3y27，作出可行55



x0x+3y=27

2x+y=15

y0x+2y=18

Ox+y=4x+y=11x+y=1227

域（如图所示）,目标函数为zxy，作

出在一组平行直线xyt中（为参数）经过可行域内的点且和原点距离最近的直线，此t

直线经过直线x3y27和直线2xy15的交点1839，直线方程为572，由

A(,)xy11

5555

于1839都不是整数，而最优解(x,y)中，，必须都是整数，所以可行域内点y1839

和xA(,)

5555

不是最优解。

经过可行域内的整点（横坐标和纵坐标都是整数的点）且与原点距离最近的直线是

xy12且经过的整点是B（3，9）和C（4，8），它们都是最优解。

答：要截得所需三种规格的钢板，且使所截两种钢板的张数最少的方法有两种，第一

种截法是截第一种钢板3张、第二种钢板9张；第二种截法是截第一种钢板4张、第二种

钢板8张。两种方法都最少要截两种钢板共12张。

线性规划问题中的整点最优解是教学中的一个难点，教材中利用图解法比较直观有效

地突破了这一难点，但其中有两个问题需