线性规划模型及其应用

《线性规划模型及其应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章线性规划模型及应用线性规划是运筹学的一个重要分支。运筹学：包括数学规划图论与网络线性规划非线性规划整数规划目标规划动态规划随机规划模拟论等对策论存储轮排队论决策论线性规划所研究的问题：一是在资源（如钢材、电力等）受限制的前提下，研究如何合理使用这些资源，以完成更多的任务；二是在任务一定的前提下，研究如何合理安排，用最少的资源来完成给定的任务。线性规划在实际应用中包括下列四个步骤：1.确定问题，明确目标和限制因素；2.建立模型；3.模型求解；4.应用模型和数据进行经济分析。第一节线性规划问题的数学模型-p2第二节线性规划问题的图解法-p8第三节线性规划

2、问题的基本理论-p11第四节单纯形法-p16第五节运输问题的特殊解法-p第一节线性规划问题的数学模型一、问题的提出P138二、数学模型的建立例1：P137生产计划——最大利润问题某企业拟生产A、B两种产品，需要经过车、铣两个工段，加工的工时定额、每天可用工时和两种产品可能获得的利润见下表。要求拟订一个获得利润最大的生产计划。加工工时定额（h/件）可利用工时（h/日）产品A产品B车床工段51060铣床工段4440可获得利润（元/件）68解：⑴确定变量。⑵确定目标函数。⑶列出约束条件。⑷决策变量为非负值。设X1、X2分别为产品A、B的生产数量，则建立线性规划模

3、型为：例2：某工厂要做100套钢架，每套用长为2.9米、2.1米、1.5米的圆钢各一根。已知原坯料每根长7.4米。如何下料，可使所用原材料最省？解：单一下料，利用率低；套裁法，利用率高。套裁下料方案：各方案下下料方案坯料根数坯料长度（m）一二二四三六四一五七六三七五八八2.9（m）211100002.1（m）021032101.5（m）10130234总长度（m）7.37.16.57.46.37.26.66余料（m）0.10.30.901.10.20.81.4设Ｘ1，Ｘ2，Ｘ3，Ｘ4，Ｘ5，Ｘ6分别表示六种下料方案切割的钢管根数，则截出：（1）长2.9m的

4、坯料数：Ｘ1+2Ｘ2+Ｘ4+Ｘ6根；（2）长2.1m的坯料数：2Ｘ3+2Ｘ4+Ｘ5+Ｘ6根；（3）长1.5m的坯料数：3Ｘ1+Ｘ2+2Ｘ3+3Ｘ5+Ｘ6根；建模：求1.一般形式2.紧缩形式定义：求一组变量xj(j=1,2,......,n)的值，在满足线性约束条件下，使具有线性表达式的目标函数取得极大值或极小值的一类最优化问题称为线性规划问题，简称线性规划。3.标准形式⑴目标函数为求最大值。若，为把目标函数化为求最大值，只需令：，于是，即⑵约束条件为等式。若约束条件为不等式，需化不等式约束条件为等式约束条件，只需引入新的非负变量以表示不等式左右两端的差额就

5、可以了。这些新变量统称为松弛变量（剩余变量），它在目标函数中所对应的系数为零。⑶决策变量xj有非负限制。若决策变量xk无非负限制，这样的变量称为自由变量。将它化为标准形式有两种方法：①引进新的非负变量，代入约束条件和目标函数中，于是原问题就化为用n+1个非负变量来描述的线性规划问题。②从约束条件中，选自由变量xk的系数不为零的等式，解出xk并代入其它m-1个约束方程和目标函数中，于是原问题就化为含n-1个非负变量，满足m-1个约束方程的线性规划问题。⑷约束条件右端常数bi≥0，若bi＜0时，对于等式约束，只需在等式两边同时乘以-1；对于不等式约束，只需在不

6、等式两边同时乘以-1，同时改变不等号的方向。若例3.将线性规划问题的数学模型化为标准形式。解：根据公式：，得作业1：解：引入，令作业2：根据，解得，代入第二节线性规划问题的图解法图解法是用作图的方法来求线性规划问题的解，它适用于仅含两个决策变量的线性规划问题的数学模型求解。虽然这种方法的应用范围受到很大的限制，但这种方法简单、直观，而且有助于理解线性规划问题求解的基本原理。见教材P144图解法步骤：⑴求可行域：在平面直角坐标系中，可行域是各约束条件所表示的半平面的公共部分。⑵求最优解：将目标函数Z看成参数，作出等值线，然后根据原问题求最大值（或最小值）的要

7、求，令等值线沿Z值增加（或减少）方向在可行域内平行移动，直到找到等值线与可行域最后相交的一点，即为所要求的最优解。通过图解法求解，其可行域与最优解有可能出现下列情况：1.可行域为有界域。⑴有唯一的最优解;⑵有多个最优解。2.可行域为无界区域。⑴有唯一的最优解;⑵有多个最优解;⑶目标函数无界（即Z→∞），因此无有限最优解。3.可行域为空集，因此没有可行解。以上情况示于下图中。图中的虚线表示等值线，虚线上的箭头表示等值线的移动方向，阴影部分为可行域。综合上述讨论，可以看到：1.线性规划问题的解有四种可能：唯一最优解，多个最优解，无界解（即无有限最优解）和无可行

8、解。2.线性规划问题的可行域（解）如果存在，其可行域一般是凸多边形