2022年2022年简单的线性规划模型 .pdf

线性规划模型线性规划是 运筹学 中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而生产组织与计划的改进即合理安排人力物力资源是提高经济效果的途径之一线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好.一般地，求线性目标函数在线性约束条件 下的最大值或最小值的问题，统称为线性规划问题。满足线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域。决策变量、约束条件、目标函数是线性规划的三要素.一、基本概念1.线性规划模型的一般形式可以表示为：目标函数max(或 min)=clx1+c2x2+cnxn。约束条件：nnnnnnnnnnbxaxaxabxaxaxabxaxaxa),(),(),(22112222212111212111或或或非负条件：x10,x20,xn0 可简写为max(或 min)=njjjxc1约束条件：njjijxa1(或=，)bi，i=1，2，m 非负条件：xj0，j=1，2，n 目标函数中的系数ci,i=1,2,，n,常称为价值系数，它反映某种价名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 5 页 -值（如利润、收益或效益）；约束条件中的右端项bj，j=1,2,，m，右端系数，它反映某种资源的限制（如劳动力、原材料等）；约束条件中的 aij常称为技术系数。一般，它们都是已知的常数。2.一个线性规划问题有解，是指能找出一组xj（j=1，2，n），使其满足所有的约束条件和非负条件。称任何一组这样的 xj（j=1，2，n）是线性规划问题的一个可行解。通常，线性规划问题含有多个可行解。称全部可行解的集合为该线性规划问题的可行域。使目标函数值达到最优的可行解称为该线性规划问题的最优解，最优目标函数值称为该线性规划问题的 最优值。对不存在可行解的线性规划问题，称该线性规划问题无解。二、两个变量的线性规划问题的图解法图解法的步骤为：第 1 步：在平面上建立直角坐标系；第 2 步：图示约束条件和非负条件，找出可行域；第 3 步：图示目标函数，并寻找最优解。例 1 max z=l00 x1+80 x2约束条件4x1+2x2400 2x1+4x2500 非负条件：xl0,x20 名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 5 页 -唯一最优解（求最大值）示意图例max z=80 x1+40 x2约束条件：4x1+2x2400 2x1+4x2 500 非负条件：xl0,x20 无穷多个最优解 示意图有无穷多个 最优解（BE 线段上的所有点），相应的最优值 400*25 例：max z=3x1+4x2约束条件：20 x1+30 x2900 40 x1+30 x21200 非负条件：xl0,x20 名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 5 页 -目标函数的直线由原点向右上方逐渐移动时，与可行域，即与无穷凸多边形 x2CEBx1永远都有相交点。所以，最优解是无界解最优解是无界解示意图例max z=4x1+5x2约束条件：2x1+x22 3x1+2x26 非负条件：xl0,x20 可行域是空集，因而该例的线性规划问题没有可行解，即无解。图 6-1-5 无可行解示意图我们可以得到关于一般线性规划问题的几点结论：(1)线性规划问题可能没有可行解，因而无解；有可行解时，可能是有无界解，也可能是有 惟一的最优解，或是有 无穷多个最优解。(2)当线性规划问题有可行解时，其可行域必是一个凸域。(3)当线性规划问题有最优解时，其最优解或最优解之一(如果有无名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 5 页 -穷多个最优解的话)必是可行域凸域的某个顶点。名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 5 页 -