第四章 线性规划进一步讨论.pptVIP

第四章 线性规划进一步讨论 4.1 目标规划 4.2 运输问题 4.1 目标规划基本概念 （1）偏差变量 d+：正偏差变量，表示决策值超出目标值的部分 d-：负偏差变量，表示决策值未达到目标值的部分 按定义有：d+ ≥0， d- ≥0 ，d+ ? d- = 0 （2）绝对约束和目标约束 绝对约束（硬约束）：必须严格满足的约束条件 目标约束（软约束）：目标规划特有 （3）优先因子（P）和权系数（W） 优先因子用P1，P2，…， Pl表示，规定 Pl Pl+1，表示Pl比Pl+1有更大的优先权。 （4）目标函数 决策值=目标值 min{ f (d+ + d- ) } 决策值目标值 min{ f (d+) } 决策值目标值 min{ f (d- ) } 4.1.2 目标规划模型的建立 例4.1 某企业计划生产甲、乙两种产品。已知有关数据见表4-1。问如何安排生产使获得的总利润最大？ 设x1、x2分别表示计划生产产品甲、乙的产量，它的数学模型为： 例4.2 例4.1的决策者经过综合考虑，决策者的目标分别为：首先原材料使用限额不能突破；其次产品甲的产量不大于产品乙；再次充分利用设备台时，不希望加班；最后利润额不少于56元。问应如何安排生产？ 解：原材料使用限额的约束是绝对约束，其他三个约束是属于目标约束，分别赋予这三个目标的优先因子为P1，P2，P3。这问题的数学模型为： 目标规划模型的一般形式： 4.1.3 目标规划的图解法 4.1.4 解目标规划的单纯形法 目标规划可以用单纯形法求解。 检验数是各优先因子的线性组合，其正负首先决定于P1的系数的正负。若为正，此时检验数的正负就决定于P2的系数的正负，依此类推。 目标规划问题以检验数非负作为最优准则。 例4.4 试用单纯形法求解例4.2。 解：首先将此目标规划模型化为线性规划标准形式： 取x3、d1-、 d2- 、 d3-为初始基变量，列初始单纯形表 4-2 继续迭代，得单纯形表 4-3 继续迭代，得单纯形表 4-4 以d3+为换入变量， d1-为换出变量，经迭代得表 4-5 4.2 运输问题 产销平衡的运输问题的数学模型如下 4.2.3 运输问题的表上作业法 对偶变量法（位势法） 4.2.4 产销不平衡运输问题 1.一般产销不平衡运输问题 总产量 总销量 2. 带弹性需求的产销不平衡运输问题 4、再进行检验 3 3 5 1 2 6 1 9 12 0 2 2 因为σij ≥0，所以此运输方案是最优方案，而σ11= 0 说明还有另一最优解 1)总产量 总销量 假想一销地Bn+1，令销量为 , 运价c = 0 A A A 销量 B 1 B 2 B 3 3 12 3 1 11 2 5 2 6 7 1 3 4 3 5 B 4 4 9 5 6 产量 8 5 9 B 5 0 0 0 4 4 3 5 4 2 2 2 * * 10 8 利 润（元/件） 10 2 1 设备（台时) 11 1 2 原材料（kg） 拥有量 乙 甲 项 目 表 4-1 它的最优解为x1=4，x2=3，最大目标函数值为62。 max z=8x1+10x2 2x1+ x2 ≤11 st. x1+ 2x2 ≤10 x1 , x2≥0 但企业的经营目标不仅是利润，企业还考虑了以下问题： （1）根据市场信息，产品甲开始出现滞销现象，故考虑产品甲的产量应不超过产品乙； （2）超过计划供应的原材料需高价采购，应避免过量消耗； （3）应尽可能充分利用设备台时，但不希望加班； （4）应尽可能达到并超过计划利润指标56元。 2x1 + x2 ≤11 x1 - x2 + d1- - d1+ =0 x1 + 2x2 + d2- - d2+ =10 8x1 + 10x2 + d3- - d3+ =56 x1,x2,di-,di+ ≥0 i=1,2,3 min{ P1 d1+ , P2 ( d2- + d2+ ) , P3 d3- } s.t. Min ﹛Pl（∑（ wlk-dk- + wlk+dk+ ））,l=1,2…,