[其它]线性规划.ppt

1. 引言 在工程技术、经济管理、科学研究和日常生活等诸多领域中，人们经常遇到的一类决策问题：在一系列客观或主观限制条件下，寻求所关注的某个或多个指标达到最大（或最小）的决策。例如，生产计划要按照产品工艺流程和顾客需求，制定原料、零件、部件等订购、投产的日程和数量，尽量降低成本使利润最高；运输方案要在满足物资需求和装载条件下安排从各供应点到各需求点的运量和路线，使运输总费用最低。它们的特点就是：在若干可能的方案中寻求某种意义下的最优方案。数学上称为最优化问题,而研究处理这种问题的方法叫最优化的方法。 优化模型是一类既重要又特殊的数学模型，而优化建模方法是也一种特殊的数学建模方法。优化模型一般有下面三个要素： （1）决策变量，它通常是该问题要求解的那些未知量。 （2）目标函数，通常是该问题要优化（最大或最小）的那个目标的数学表达式，它是决策变量的函数。 （3）约束条件，由该问题对决策变量的限制条件给出。 优化模型从数学上可表示成如下一般形式： opt (opt表示最优化(optimize)的意思) s.t. (Ⅰ) (Ⅱ) 如果 均为线性函数，则上述模型称为线性规划 （Linear Programming,简记为LP），否则称为非线性规划(NLP) 3.1线性规划问题几个概念：线性规划问题有解：指能找出一组满足约束条件的向量，并称这组为问题的可行解。线性规划问题无解：指不存在可行解或最优趋向无限大。可行域：指全部可行解组成的集合。最优解：指可行域中使目标函数值达到最优的可行解。 3.3 求解一般方法： (1)图解法：对于只含2个变量的线性规划问题，可通过在平面上作图的方法求解。步骤如下： ①在平面上建立直角坐标系； ②图示约束条件，找出可行域； ③图示目标函数，即为一直线； ④将目标函数直线沿着其法线方向向可行解域边界平移，直至与可行解域第一次相切为止，这个切点就为最优点(2)单纯形法可以用Matlab或LINGO等软件编程计算 线性规划模型的实例例1 家具生产的安排 家具公司生产桌子和椅子，用于生产的劳力共计450个工时，木材共有4立方米,每张桌子要使用15个工时，0.2立方木材，售价80元。每张椅子使用10个工时，0.05立方木材，售价45元。问为达到最大的收益，应如何安排生产？ 分析： 1. 求什么？ 生产多少桌子？ x1 生产多少椅子？ x2 2. 优化什么？ 收益最大 Max f=80 x1+45 x2 3. 限制条件？ 原料总量 0.2 x1 +0.05 x2 ≤4  劳力总数 15 x1 +10 x2 ≤450 模型：以产值为目标取得最大收益. 设：生产桌子 x1张, 椅子 x2张,(决策变量)  将目标优化为：max f=80x1+45x2 对决策变量的约束： 0.2x1+0.05x2≤4 （Ⅰ） 15x1+10x2 ≤ 450,（Ⅱ） x1 ≥ 0, x2 ≥ 0, 模型求解：（1）图解法（用于决策变量是2维） 线性规划问题的目标函数(关于不同的目标值是一族平行直线)目标值的大小描述了直线离原点的远近,并且最优解一定在可行解集的某个极点上达到(穿过可行域的目标直线组中最远离(或接近)原点的直线所穿过的凸多边形的顶点). （2）用Matlab实现------- lp 线性优化函数线性优化问题即目标函数和约束条件均为线性函数的问题。其标准形式为：Min  Sub.to: Ax=b 其中 （通常 ）， ，  均为数值矩阵。 max f=80 X1+45 X2 s.t. 0.2 X1+0.05 X2≤4  15 X1+10 X2 ≤ 450 X1 ≥ 0, X2