线性规划实验举例.docx

最优化算法实验指导书1.线性规划求解1.1 生产销售计划问题 一奶制品加工厂用牛奶生产 A 、A2 两种普通奶制品，以及 B 、B 两种高级奶制品， 分别是由A、深加工开发得到的，已知每1桶牛奶可以在甲类设备上用"12h加工成3kg A1, 或者在乙类设备上用8h加工成4kg A?；深加工时，用2h并花1.5元加工费，可将1kg A加 工成0.8kg B1,也可将1kg A2加工成0.75kg B2,根据市场需求，生产的4种奶制品全部能售 出，且每公斤A2、B］、B获利分别为12元、8元、22元、16元现在加工厂每天能得到50桶牛奶的供应，每天正式工人总的劳动时间最多为480h, 并且乙类设备和深加工设备的加工能力没有限制，但甲类设备的数量相对较少，每天至多能 加工100kg A】，试为该厂制定一个生产销售计划，使每天的净利润最大，并讨论以下问题: ( 1 )若投资1 5元可以增加供应1桶牛奶，应否作这项投资；(2)若可以聘用临时工人以增加劳动时间，支付给临时工人的工资最多是每小时几 元？(3)如果B「B2的获利经常有10%的波动，波动后是否需要制定新的生产销售计划？ 模型 这是一个有约束的优化问题，其模型应包含决策变量、目标函数和约束条件。

决策变量用以表述生产销售计划，它并不是唯一的，设A「A2、B「B2每天的销售量分别为x ,x ,x ,x (kg), x ,x也是B、B的产量，设工厂用x(kg)A加工B，x (kg)1 2 3 4 3 4 1 2 5 1 1 6A加工B (增设决策变量x、x可以使模型表达更清晰)2 2 5 6目标函数是工厂每天的净利润z，即A2、B］、B2的获利之和扣除深加工费，容易写出 z = 12x + 8x + 22x +16x -1.5x -1.5x (元)1 2 3 4 5 6约束条件原料供应：A1每天的产量为x + x (kg)，用牛奶(x + x )/3 (桶)，A的每天产1 1 5 1 3 2量为x + x (kg)，用牛奶(x + x )/4 (桶)，二者之和不得超过每天的供应量50 (桶)2 6 2 6劳动时间：每天生产A、A2的时间分别为4( x + x )和2( x + x )，加工B、B的1 2 1 5 2 6 1 2时间分别为2x和2x，二者之和不得超过总的劳动时间480h56设备能力：A1每天的产量x + x ,不得超过甲类设备的加工能力100 (kg)1 1 5加工约束：1 (kg)入加工成0.8 (kg) B，故x二0.8x ；类似的x二0.75x。

1 1 3 5 4 6非负约束： x,x ,x,x ,x,x 均为非负123456由此得如下基本模型：max z 二 12 x + 8 x + 22 x +16 x —1.5 x —1.5 x1 2 3 4 5 6£ 50x + x x + x —1 5 + ―2——3 44(x + x ) + 2(x + x ) + 2x + 2x < 4801 5 2 6 5 6St J x + x < 10015x = 0.8 x3 5x = 0.75 x4 6x , x , x , x , x , x > 0123456显然，目标函数和约束函数都是线性的，这是一个线性规划问题，求出的最优解将给 出使净利润最大的生产销售计划，要讨论的问题需考虑参数的变化对最优解和最优值的影 响，即灵敏度分析，整理后为：maxz = 1 x + 8 + 2x2 + k6- 1x 5 x1. 51 2 3 4 54x + 3x + 4x + 3x < 60012 5 62 x + x + 3 x + 2 x < 2401 2 5 6x + x < 100S.t J 1 5x - 0.8 x = 035x - 0.75 x = 046x,x ,x,x ,x,x >01 2 3 4 5 6编程计算如下：c=[-12 -8 -22 -16 1.5 1.5];>> A1=[4 3 0 0 4 3;2 1 0 0 3 2;1 0 0 0 1 0];>> c=[-12 -8 -22 -16 1.5 1.5];>> a=[4 3 0 0 4 3;2 1 0 0 3 2;1 0 0 0 1 0]; b=[600 240 100];aeq=[0 0 1 0 -0.8 0;0 0 0 1 0 -0.75]; beq=[0 0];lb=[0 0 0 0 0 0];ub=[];[x,fval]=linprog(c,a,b,aeq,beq,lb,ub) Optimization terminated successfully.0.0000168.000019.20000.000024.00000.0000fval =-1.7304e+0031.2 配料问题例 某炼油厂生产 3 种规格的汽油：70 号，80 号与 85 号，它们各有不同的辛烷值与含硫量 的质量要求，这 3 种汽油由3 种原料油调和而成，每种原料油每日可用量、质量指标及生产 成本见下表 1，每种汽油的质量要求和销售价格见表2，假定在调和中辛烷值和含硫量指标 都符合线性可加性，问该炼油厂如何安排生产才能使其利润最大？表 1 原料油的质量及成本数据序号G)原料辛烷值含硫量/%成本/元•t-1可用里/t•日-11直馏汽油621.560020002催化汽油780.890010003重整汽油900.21400500表2 汽油产品的质量要求与销售价序号G)产品辛烷值含硫量/%销售价/元・t-1170号汽油三70W1900280号汽油三80W11200385号汽油三85<0.61500解 本例建立数学模型的关键是决策变量的选择，如果选择各种汽油产品的质量，在建立数学模型时会遇到一些困难，定义决策变量x为第i种原料调入第j种产品油中的数量，记ijp表示单位第j种产品的销售价格，c为单位第i种原料的生产成本，e及e'分别为原料j i i j油和产品油的辛烷值，h和h'分别为原料油和产品油的含硫量，s为原料油每日的可用量,i j i首先考虑问题的目标函数，第 j 种汽油产品所产生的利润为£ (p - c ) xj i iji=1因此目标函数为 ££ ( p - c )xj i ijj =1 i=1约束条件应有3 组：汽油产品的辛烷值要求：ex + ex + ex >e' (x + x + x ),j = 1,2,31 1j 2 2j 3 3j j 1j 2 j 3j汽油产品的含硫量要求：hx + h x + h x > h' (x + x + x ), j = 1,2,31 1j 2 2 j 3 3j j 1j 2j 3j原料油可用量的限制：x + x + x < s , i 二 1,2,3i1 i 2 i3 i因此本题的数学模型为33max乙乙j=1 i=1(p - c ) xj i ij工(e - e' )x > 0, j = 1,2,3i j ij i=1工(h - h' )x > 0, j = 1,2,3S.t < i j iji=1工 x < s , j = 1,2,3ij ix > 0,i, j =1,2,3ij将已知数值代入并化简后，其数学模型为max z = 300x + 0x - 500x + 600x + 300x - 200x + 900x11 21 31 12 22 32 13+600x +100x23 33-8x + 8x + 20x > 011 21 31-18 x - 2 x +10 x > 012 22 32-23x — 7x + 5x > 013 23 330.5x - 0.2x - 0.8x < 011 21 310.5x - 0.2x - 0.8x < 0s.t < 12 22 320.9x +0.2x -0.4x <013 23 33x +x +x <200011 12 13x + x + x < 100021 22 23x + x + x < 50031 32 33x > 0,i, j =1,2,3ij>> c=[-300 0 500 -600 -300 200 -900 -600 -100];>> a=[8 -8 -20 0 0 0 0 0 0;0 0 0 18 2 -10 0 0 0;0 0 0 0 0 0 23 7 -5;0.5 0.2 -0.8 0 0 0 0 0 0;0 0 0 0.5-0.2 -0.8 0 0 0;...0 0 0 0 0 0 0.9 0.2 -0.4;1 0 0 1 0 0 1 0 0;0 1 0 0 1 0 0 1 0;0 0 1 0 0 1 0 0 1];>> b=[0 0 0 0 0 0 2000 1000 500];>> aeq=[];beq=[];lb=[0 0 0 0 0 0 0 0 0];ub=[];[x,fval]=linprog(c,a,b,aeq,beq,lb,ub) Optimization terminated successfully.x =0.00000.00000.00000.0000750.0000150.00000.0000250.0000350.0000 fval =-3.8000e+005作业布置：建立模型并求解 1.34 1.35（抄题目）。