下载文档原格式
线性规划中的最优整数解线性规划中的最优解，就是在线性约束条件下使目标函数取得最大值或最小值的可行解，而求最优整数解，是同学们的棘手问题，下面以例题的形式讲讲如何求最优解。
例. 某人承揽了一项业务：需做文字标牌6个，绘画标牌5个。
现有两种规格的原料，甲种规格每张32m ，可做文字标牌1个、绘画标牌2个；乙种规格每张22m ，可做文字标牌2个、绘画标牌1个，求两种规格的原料各用多少张才能使总的用料面积最小？最小用料面积是多少？分析：将已知数据列成如下所示的表格：解法一：设甲种规格的原料用x 张，乙种规格的原料用y 张，总的用料面积为z 2m ,则z=3x+2yx+2y ≥62x+y ≥5x ≥0y ≥0其可行域如图所示：解方程组x+2y=62x+y=5得M 的坐标为47(,)33当直线z=3x+2y过点M47(,)33时z最小，此时472632333z=⨯+⨯=由题意可知，点M47(,)33不是最优解，因为此问题最优解(x,y)中x，y应都是非负整数，所以目标函数z的最小值一定是大于263的整数，且x，y都是非负整数。
取z=9,得3x+2y=9，其非负整数解是（1，3）和（3，0），但点（3，0）不在可行域内，舍去，所以点（1，3）是最优解，min 9z=解法二：由解法一可知，点M47(,)33不是最优解，这时可求出可行域内左下侧靠近边界的整点，依次为A（0，5），B（1，3），C（2，2），D（3，2），E（4，1），F（5，1），G（6，0），将这些点的坐标分别代入目标函数z=3x+2y，求出z的各对应值，经检验可知，在整点B（1，3）处z取得最小值9。
答：甲种规格的原料用1张，乙种规格的原料用3张时，总的用料面积最小，其最小用料面积为92m。
对于线性规划中的最优整数解问题，当解方程组得到的解不是整数解时，可采用如下的方法：1.调整优值法：先求“非整点最优解”及“最优值”，根据题意调整“最优值”，再求目标函数中的整数解，便可得出最优整数解。
求线性规划问题的最优整数解的方法作者：陈树礼来源：《中学教学参考·理科版》2010年第01期线性规划是新教材新增内容,在近几年高考中都以较易题目出现,要学好本节内容,应注意以下三点.一、判定最优解求线性目标函数z=ax+by(a≠0、b≠0)在线性约束条件下的最优解问题,可转化为求直线y=-abx+zb在y轴上的截距的最大值和最小值.易知在b>0时,当zb最大时,z取得最大值,当zb最小时,z取得最小值;在b二、求出最优解依据边界直线的斜率(或倾斜角)计算出最优解.三、修正最优解,得到最优整数解现改编人教版高二(上例3的问题,以求达到抛砖引玉的目的.【例】某工厂生产甲、乙两种产品.已恬生产甲种产品1t需耗A种矿石10t、B种矿石5t、煤4t;生产乙种产品1t需耗A种矿石4t、B种矿石4t、煤9t.每1t甲种产品的利润是600元,每1t乙种产品的利润是1000元.工厂在生产这两种产品的计划中要求消耗A种矿石不超过300t、B种矿石不超过200t、煤不超过360t.求:(1)甲、乙两种产品各生产多少吨(精确到1吨)才能使利润最大?(2)若甲种产品每吨利润600元,乙产品每吨利润200元.甲、乙两种产品各生产多少吨(精确到1吨)才能使利润最大?(3)若甲种产品每吨利润400元,乙产品每吨利润200元.甲、乙两种产品各生产多少吨(精确到1吨)才能使利润最大?(4)若甲种产品每吨利润200元,乙产品每吨利润600元.甲、乙两种产品各生产多少吨(精确到1吨)才能使利润最大?(5)若甲种产品每吨利润1000元,乙产品每吨利润800元.甲、乙两种产品各生产多少吨(精确到1吨)才能使利润最大?解:(1)设生产甲、乙两种产品分别为x吨,y吨.利润为z元.则10x+4y≤300,5x+4y≤200,4x+9y≤360,x≥0,y≥0,z=600x+1000y.作出以上不等式组表示的平面区域,即可行域.作直线:600x+1000y=0,即直线:3x+5y=0,则z=200(3x+5y).设u=3x+5y,则当u最大时,z最大.易知直线NQ、MN、PM的斜率分别为-52,-54,-49,直线l的斜率为-53.平移直线∵M点为最优解点.由方程组5x+4y=200,4x+9y=360得M点的坐标为(36029,100029).∵x,y都是正整数,∴u=3x+5y=608029也应为正整数.∴u=3x+5y≤209.于是整点(11,35)为所求.当生产甲产品11吨,乙产品35吨时,能使利润总额最大.(2)此时目标函数为z=600x+200y.作直线平移直线∵直线经过点Q(30,0)时,z取得最大值.即只生产甲产品30吨时,获得利润最大.(3)此时目标函数为z=400x+200y.作直线平移直线∵-类似(1)可求解.(4)此时目标函数为z=200x+600y.作直线平移直线∵--49.∴当直线经过点P(0,40)时,5x+4y=0,即只生产乙产品40吨时,获得利润最大.(5)此时目标函数为z=1000x+800y.作直线平移直线∵-∴当直线与直线5x+4y=0重合时,z取得最大值.∴当点位于线段MN上任意一点时,都能使z取得最大值.总之,在本部分内容的学习中,要做到“一定、二算、三修正”.(责任编辑金铃)。
线性规划的解与最优解知识点总结在现实生活和工作中，我们经常会遇到需要最优化某个目标函数的问题。
线性规划作为一种常见的数学优化方法，在各个领域中得到了广泛应用。
它能够帮助我们在一定的约束条件下，找到目标函数的最佳解。
本文将对线性规划的解与最优解的相关知识点进行总结。
1. 基本概念线性规划问题由目标函数和一组线性约束条件组成。
目标函数的形式通常是最大化或最小化一些变量的线性组合，而约束条件则给出了这些变量的取值范围。
线性规划问题的一般形式如下：```max/min Z = c₁x₁ + c₂x₂ + ... + cₙxₙsubject to:a₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ ≤ b₁...aₙ₁x₁ + aₙ₂x₂ + ... + aₙₙxₙ ≤ bₙx₁, x₂, ..., xₙ ≥ 0```其中，Z表示目标函数的值，c₁, c₂, ..., cₙ为目标函数的系数，aᵢₙ为约束条件中的系数，b₁, b₂, ..., bₙ为约束条件的右边常数，x₁,x₂, ..., xₙ为决策变量。
2. 解的存在性线性规划问题存在三种解的情况：无解、有界解和无界解。
如果约束条件与目标函数之间存在矛盾，例如出现一个约束条件为 a₁₁x₁ +a₁₂x₂ + ... + a₁ₙxₙ ≤ b₁，而目标函数的系数为 c₁ > a₁₁，那么这个线性规划问题就没有解。
有界解指的是线性规划问题在满足所有约束条件的情况下，能够找到目标函数的最大值或最小值。
无界解意味着目标函数可以无限制地增大或减小。
3. 最优解的性质线性规划问题的最优解具有以下性质：- 最优解必然出现在可行域的顶点上。
可行域是指所有满足约束条件的解的集合，而顶点则指可行域的边界上的点。
- 如果最优解存在，那么至少存在一个顶点是最优解。
- 如果可行域是有限的，则一定存在一个顶点是最优解。
- 如果最优解存在，那么一定有一条或多条约束条件在最优解上取等号。
线性目标函数最优解的求解方法线性规划中寻求最优解是解析几何的重点，也是难点。
现就如何利用可行域寻求最优解的常见方法作些探讨.一、 平移直线法平移法是一种最基本的方法，其基本原理是两平行直线中的一条上任意一点到另一条直线的距离相等.例1变量x 、y 满足下列条件：⎪⎪⎩⎪⎪⎨⎧≥≥≥+≥+≥+0,0............2432...........3692..............122y x ③y x ②y x ①y x 则使z=3x+2y 的值最小的（x ，y ）是（ ）A ． ( 4.5 ,3 )B ． ( 3,6 )C ． ( 9, 2 )D ． ( 6, 4 ) 解析：作出约束条件的可行域（如图），由z=3x+2y 知223zx y +-=,于是作一系列与直线x y 23-=平行的直线，当直线223zx y +-=过图中的B 点时，2z取得最小值。
于是由⎩⎨⎧==⇒⎩⎨⎧=+=+6336922432y x y x y x ，从而知当⎩⎨⎧==63y x 时，z=3x+2y 取得最小值。
故选B 。
评析：解决线性规划中的最值问题的关键是：作出可行域，找出最优解。
二、代入检验法通过平移法可以发现，取得最优解对应的点往往是可行域的顶点，其实这具有必然性.于是在有关选择题的线性规划中的最值问题，可采用求解方程组代入检验的方法求解。
例2，已知x 、y 满足约束条件：⎩⎨⎧≤+≤+3623242y x y x ，则Z=10x+15y 的最大值为（）A 195B 200C 210D 220解：解程组⎩⎨⎧==⇒⎩⎨⎧=+=+963623242y x y x y x 从而代入Z=10x+15y 可得Z max =195,故选A 。
评析：代入检验法在涉及最优解为近似解或整格解的问题时，是一种行之有效的方法，具有其它方法不可替代的作用.三、 比较斜率法 平移法的缺陷在于，当可行域的顶点数较多时，不易直观地判断出哪个或哪几个顶点的坐标是最优解.这时若进一步考虑直线斜率的大小，则可以确定出最优解.例3 某工厂生产甲、乙两种产品.已知生产甲种产品1t 需耗A 种矿石10t 、B 种矿石5t 、煤4t ；生产乙种产品1t 需耗A 种矿石4t 、B 种矿石4t 、煤9t.每1t 甲种产品的利润是600元，每1t 乙种产品的利润是1000元.工厂在生产这两种产品的计划中要求消耗A 种矿石不超过300t 、B 种矿石不超过200t 、煤不超过360t .甲、乙两种产品应各生产多少（精确到0.1t ），能使利润总额达到最大？解：设生产甲、乙两种产品分别为xt 、yt ，利润总额为z 元，那么⎪⎪⎩⎪⎪⎨⎧≥≥≤+≤+≤+0,0360942004515025y x y x y x y x 且Z=600x+1000y 作出约束条件所表示的平面区域（如左图），即可行域. 作直线l ：600x+1000y=0,即直线l ：3x+5y=0.因为94534525-<-<-<-，即k EN <k MN <k l <k FN ，所以把直线l 向上方移至m 的位置，直线经过可行域上的点M ，此时Z=600x+1000y 取最大值.解方程组⎩⎨⎧=+=+3609420045x x y x 得M 的坐标x=29360=12.3，y=291000=34.5，代入计算得Z max =291216000． 答：应生产甲产品约12.3t,乙产品34.5t ，能使利润总额达到最大.评析：这是高中新教材第二册上册第七章，“简单的线性规划”一节中的例3（P62～63）,确定了直线斜率的大小，实质是确定了直线在向上平移的过程中，在经过可行域X 围内时，即可确定最优解。
如何求最优整数解求线性规划中最优整数解的问题，是学生最感头疼的事．下面仅举一例谈谈此类问题的求解策略，以供参考．题目：要将两种大小不同的钢板截成A B C ，，三种规格，每张钢板可同时截得三种规格的小钢板块数如下表所示：今需要A B C ，，三种规格的成品为15，18，27块，问各截这两种钢板多少张可得所需三种规格的成品，且使所用钢板张数最少．分析：这是一道求线性规划中最优整数解的问题，设两种钢板分别需要x y ，张，那么约束条件为21521832700.x y x y x y x y +⎧⎪+⎪⎪+⎨⎪⎪⎪⎩，，，，≥≥≥≥≥目标函数z x y =+，对应的可行域如下图．那么，怎样寻找其最优整数解呢？分解步骤如下：步骤1：作出一组平行直线x y t +=中经过可行域内的点且和原点距离最近的直线．步骤2：求出直线327x y +=和直线215x y +=的交点183955A ⎛⎫ ⎪⎝⎭，． 步骤3：写出过交点的目标函数的方程575x y +=． 步骤4：判断A 点是不是最优解．因为183955，都不是整数，所以可行域内的183955A ⎛⎫ ⎪⎝⎭，不是最优解．步骤5：找出接近575且适合题意的整数．经过可行域内的点且与原点距离最近的直线为12x y +=． 步骤6：确定适合题意的整点，得(39)(48)B C ，，，，即为所求的最优解． 评注：线性规划问题主要是在图上完成的，所以作图应尽可能精确，图上操作尽可能标准．但考虑到作图毕竟会有误差，假假设图上的最优点并不明显易辨时，不妨将几个可能是最优点的坐标都求出来，然后逐一检查，以“验明正身〞．小结：运用线性规划的理论求解实际问题，与求解其它类型的实际问题一样，关键是建立数学模型，这既是学习中的重点，也是一个难点．对此，我们一定要予以充分的重视，加强训练，努力提高应用数学理论分析和解决实际问题的能力．。
《管理运筹学》(第二版)课后习题参考答案第1章线性规划(复习思考题)1 .什么是线性规划线性规划的三要素是什么答：线性规划(Linear Programming, LP)是运筹学中最成熟的一个分支，并且是应用最广泛的一个运筹学分支。
线性规划属于规划论中的静态规划，是一种重要的优化工具，能够解决有限资源的最佳分配问题。
建立线性规划问题要具备三要素：决策变量、约束条件、目标函数。
决策变量是决策问题待定的量值，取值一般为非负；约束条件是指决策变量取值时受到的各种资源条件的限制，保障决策方案的可行性；目标函数是决策者希望实现的目标，为决策变量的线性函数表达式，有的目标要实现极大值，有的则要求极小值。
2.求解线性规划问题时可能出现几种结果，哪种结果说明建模时有错误答：(1)唯一最优解：只有一个最优点；(2)多重最优解：无穷多个最优解；(3)无界解：可行域无界，目标值无限增大；(4)没有可行解：线性规划问题的可行域是空集。
当无界解和没有可行解时，可能是建模时有错。
3.什么是线性规划的标准型松弛变量和剩余变量的管理含义是什么答：线性规划的标准型是：目标函数极大化，约束条件为等式，右端常数项b i 0,决策变量满足非负性。
如果加入的这个非负变量取值为非零的话，则说明该约束限定没有约束力，对企业来说不是紧缺资源，所以称为松弛变量；剩余变量取值为非零的话，则说明“学”型约束的左边取值大于右边规划值，出现剩余量。
4.试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相互关系。
答：可行解：满足约束条件AX b, X 0的解，称为可行解。
基可行解：满足非负性约束的基解，称为基可行解。
可行基：对应于基可行解的基，称为可行基。
L~ —1|最优解：使目标函数最优的可行解，称为最优解。
最优基：最优解对应的基矩阵，称为最优基。
它们的相互关系如右图所示：基可行解5.用表格单纯形法求解如下线性规划max Z 4x1 x2 2x38x1 3x2 x3 26x1 x2 x3 8x1, x2,x3 0解：标准化maxZ 4x1 x2 2x38x1 3x2 x3 x4 26x1 x2 x3 x5 8x1,x2,x3,x4,x5 0列出单纯形表12 5 2故最优解为X* (0,0,2,0,6)T ,即x1 0,x2 0,x3 2,此时最优值为Z(X*) 4.6.表1—15中给出了求极大化问题的单纯形表，问表中“，a2，C i，C2，d为何值及变量属于哪一类型时有：(1)表中解为唯一最优解；(2)表中解为无穷多最优解之一；(3) 下一步迭代将以必代替基变量X5；(4)该线性规划问题具有无界解；(5)该线性规划问题无可行解。
线性规划问题的最优解引言线性规划是运筹学的一个基本分支，其应用极其广泛，其作用以为越来越多的人所重视。
线性规划主要就实际问题抽象成数学形式，即求一组变量的值，在满足一定的约束条件下，是某个目标达到最小或最大，而这些约束条件用可以用一组线性不等式或线性方程来表示。
而求得目标函数的最优解尤为重要，本文就线性规划问题的最优解求解方法作出阐述，并举出实例加以强化，同时也指出了线性规划问题应用于生产与运作管理的重要性。
1.线性规划问题的最优解探讨1.1线性规划问题的提出考虑下面的线性规划问题的标准型： 目标函数：CX Z =min (1)约束条件：⎩⎨⎧≥=0X b AX (2)其中，),,,(21n c c c C =,T n x x x X ),,,(21 =,T m b b b b ),,,(21 =,n m ij a A ⨯=)(阶矩阵。
设B 是A 中m 个线性无关的列向量构成的一个基，m m ij a B ⨯=)( 阶矩阵，这样将矩阵A 分成两个部分，即A=),(N B ,X=),(N B X X ,C=()N B C C ,,B X ,B C 为基B 对应的非基变量和系数，N X ,N X 为N 对应的非基变量和系数，这样将线性规划问题改写为：minZ ()N B C C ,=⎥⎦⎤⎢⎣⎡B B X X (3)约束条件：⎪⎩⎪⎨⎧≥=⎥⎦⎤⎢⎣⎡0),(NB N B X X bX X N B (4)经过矩阵变换，得出关于基B 的标准型如下：1min -=B C Z B +(N C -1-B C B N)N X (5)约束条件：⎩⎨⎧≥=+--0,11NB N B X X bB NX B X (6)T m b b b b B ),,,(''21'1 =-⎪⎪⎪⎪⎪⎭⎫⎝⎛=++++++-mnmm mm nm m n m m a a a a a a a a a N B2122212121111 将（5）（6）展开为：=Z min '1i mi i b c ∑=+∑+=nm j 1('1ij mi i j a c c ∑=-)j x (7)约束条件：i nm j j iji b x ax '1'=+∑+= ,m i ,,2,1 = (8)0≥j x ,n j ,,2,1 = (9)令 '10i mi i b c Z ∑== , =j σ'1ij mi i j a c c ∑=- ,n m m j ,,2,1 ++= ,称j σ为检验数。
