线性规划模型及其应用

第四章 线性规划模型及应用

线性规划是运筹学的一个重要分支。运筹学：包括

数学规划 图论与网络 排队论 存储轮 对策论 决策论 模拟论等 线性规划 目标规划 非线性规动态规划 整数规划 随机规划

线性规划所研究的问题：一是在资源（如钢材、电力等）受限制的前提下，研究如何合理使用这些资源，以完成更多的任务；二是在任务一定的前提下，研究如何合理安排，用最少的资源来完成给定的任务。

线性规划在实际应用中包括下列四个步骤： 1.确定问题，明确目标和限制因素； 2.建立模型； 3.模型求解；

4.应用模型和数据进行经济分析。 第一节 线性规划问题的数学模型-p2 第二节 线性规划问题的图解法-p8 第三节 线性规划问题的基本理论-p11 第四节 单纯形法-p16

第五节 运输问题的特殊解法-p

第一节 线性规划问题的数学模型 一、问题的提出P138 二、数学模型的建立

例1：P137生产计划——最大利润问题

某企业拟生产A、B两种产品，需要经过车、铣两个工段，加工的工时定额、每天可用工时和两种产品可能获得的利润见下表。要求拟订一个获得利润最大的生产计划。

加工工时定额（h/件） 车床工段 铣床工段 可获得利润（元/件） 6 8 产品A 5 4 产品B 10 4 可利用工时（h/日） 60 40 解：⑴确定变量。⑵确定目标函数。⑶列出约束条件。⑷决策变量为非负值。

设X1、X2分别为产品A、B的生产数量，则建立线性规划模型为：

MaxZ?6x1?8x2

?5x1?10x2?60?s.t.?4x1?4x2?40

?x,x?0?12例2：某工厂要做100套钢架，每套用长为2.9米、2.1米、

1.5米的圆钢各一根。已知原坯料每根长7.4米。如何下料，可使所用原材料最省？

解：单一下料，利用率低；套裁法，利用率高。 套裁下料方案： 各方案下 下料方案 一 坯料根数 坯料长度（m） 2.9（m） 2.1（m） 1.5（m） 总长度（m） 余料（m） 2 0 1 7.3 0.1 1 2 0 7.1 0.3 1 1 1 6.5 0.9 1 0 3 7.4 0 0 3 0 6.3 1.1 0 2 2 7.2 0.2 0 1 3 6.6 0.8 0 0 4 6 1.4 二 二 四 三 六 四 一 五 七 六 三 七 五 八 八 设Ｘ1，Ｘ2，Ｘ3，Ｘ4，Ｘ5，Ｘ6分别表示六种下料方案切割的钢管根数，则截出：

（1）长2.9m的坯料数：Ｘ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根； 建模：

x,x,x,x,x,x123456 求

MinZ?0.1x2?0.2x3?0.3x4?0.8x5?0.9x6?x1?2x2?x4?x6?100?2x?2x?x?x?1003456??s.t.?3x1?x2?2x3?3x5?x6?100?x,x,x,x,x,x?0?123456??1.一般形式 Max(或Min)Z?c1x1?c2x2???cnxn?a11x1?a12x2???a1nxn?(?,?)b1?ax?ax??ax?(?,?)b2112222nn2? ?s.t.???? ?ax?ax???ax?(?,?)bm11m22mnnm? ??x1,x2,?,xn?0 2.紧缩形式 Max(或Min)Z? ?cj?1njxj?ni?1,2,?m??aijxj?(?,?)bi s.t.?j?1?xj?0j?1,2,?n ?定义：求一组变量xj (j=1,2,......,n)的值，在满足线性约束条件下，使具有线性表达式的目标函数取得极大值或极小值的一类最优化问题称为线性规划问题，简称线性规划。 3.标准形式 MaxZ?c1x1?c2x2???cnxn?a11x1?a12x2???a1nxn?b1?ax?ax???ax?b2222nn2?211⑴目标函数为求最大值。若MinZ?c1x1?c2x2?数化为求最大值，只需令：Z1??Z，

?cnxn，为把目标函

于是MinZ??Max??Z???MaxZ1，即MaxZ1??MinZ??c1x1?c2x2???cnxn ⑵约束条件为等式。若约束条件为不等式，需化不等式约束条件为等式约束条件，只需引入新的非负变量以表示不等式左右两端的差额就可以了。这些新变量统称为松弛变量（剩余变量），它在目标函数中所对应的系数为零。

⑶决策变量xj有非负限制。若决策变量xk无非负限制，这样的变量称为自由变量。将它化为标准形式有两种方法：

?①引进新的非负变量xk???0，令xk?xk??xk??，?0，xk代入约束条件和目

标函数中，于是原问题就化为用n+1个非负变量来描述的线性规划问题。

②从约束条件中，选自由变量xk的系数不为零的等式，解出xk并代入其它m-1个约束方程和目标函数中，于是原问题就化为含n-1个非负变量，满足m-1个约束方程的线性规划问题。 ⑷约束条件右端常数bi≥0，若bi＜0时，对于等式约束，只需在等式两边同时乘以-1；对于不等式约束，只需在不等式两边同时乘以-1，同时改变不等号的方向。 若xk

例3.将线性规划问题的数学模型

???xk ?0，令xk

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库线性规划模型及其应用在线全文阅读。