最优化算法实验指导书
1.线性规划求解
1.1 生产销售计划
问题 一奶制品加工厂用牛奶生产A1、A2两种普通奶制品，以及B1、B2两种高级奶制品，分别是由A1、A2深加工开发得到的，已知每1桶牛奶可以在甲类设备上用12h加工成3kg A1，或者在乙类设备上用8h加工成4kg A2；深加工时，用2h并花1.5元加工费，可将1kg A1加工成0.8kg B1，也可将1kg A2加工成0.75kg B2，根据市场需求，生产的4种奶制品全部能售出，且每公斤A1、A2、 B1、B2获利分别为12元、8元、22元、16元。
现在加工厂每天能得到50桶牛奶的供应，每天正式工人总的劳动时间最多为480h，并且乙类设备和深加工设备的加工能力没有限制，但甲类设备的数量相对较少，每天至多能加工100kg A1，试为该厂制定一个生产销售计划，使每天的净利润最大，并讨论以下问题： （1）若投资15元可以增加供应1桶牛奶，应否作这项投资；
（2）若可以聘用临时工人以增加劳动时间，支付给临时工人的工资最多是每小时几
元？
（3）如果B1、B2的获利经常有10%的波动，波动后是否需要制定新的生产销售计划？ 模型 这是一个有约束的优化问题，其模型应包含决策变量、目标函数和约束条件。
决策变量用以表述生产销售计划，它并不是唯一的，设A1、A2、 B1、B2每天的销售量分别为x1,x2,x3,x4（kg），x3,x4也是B1、B2的产量，设工厂用x5（kg）A1加工B1，x6（kg）A2加工B2（增设决策变量x5、x6可以使模型表达更清晰）。
目标函数是工厂每天的净利润z，即A1、A2、 B1、B2的获利之和扣除深加工费，容易写出z?12x1?8x2?22x3?16x4?1.5x5?1.5x6(元)。 约束条件
原料供应：A1每天的产量为x1?x5（kg），用牛奶(x1?x3)/3（桶），A2的每天产量为x2?x6（kg），用牛奶(x2?x6)/4（桶），二者之和不得超过每天的供应量50（桶）。 劳动时间：每天生产A1、A2的时间分别为4(x1?x5)和2(x2?x6)，加工B1、B2的时间分别为2x5和2x6，二者之和不得超过总的劳动时间480h。
设备能力：A1每天的产量x1?x5，不得超过甲类设备的加工能力100（kg）。 加工约束：1（kg）A1加工成0.8（kg）B1，故x3?0.8x5；类似的x4?0.75x6。 非负约束：x1,x2,x3,x4,x5,x6均为非负。 由此得如下基本模型：
maxz?12x1?8x2?22x3?16x4?1.5x5?1.5x6
?x1?x5x2?x6?3?4?50??4(x1?x5)?2(x2?x)6?2x?52x?6480? s.t?x1?x5?100
?x3?0.8x5??x4?0.75x6?x,x,x,x,x,x?0?123456 显然，目标函数和约束函数都是线性的，这是一个线性规划问题，求出的最优解将给出使净利润最大的生产销售计划，要讨论的问题需考虑参数的变化对最优解和最优值的影响，即灵敏度分析，整理后为： maxz?1x281?x2?2x2?31x46?1.x55? x1.5?4x1?3x2?4x5?3x?6600?2x?x?3x?2x?240256?1??x1?x5?100 s.t?
x?0.8x?05?3?x4?0.75x6?0???x1,x2,x3,x4,x5,x6?0编程计算如下：
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. x =
0.0000 168.0000 19.2000 0.0000 24.0000 0.0000
fval =
-1.7304e+003
1.2 配料问题
例 某炼油厂生产3种规格的汽油：70号，80号与85号，它们各有不同的辛烷值与含硫量的质量要求，这3种汽油由3种原料油调和而成，每种原料油每日可用量、质量指标及生产成本见下表1，每种汽油的质量要求和销售价格见表2，假定在调和中辛烷值和含硫量指标都符合线性可加性，问该炼油厂如何安排生产才能使其利润最大？ 表1 原料油的质量及成本数据 序号（i） 1 2 3 序号（i） 1 2 3 原料 直馏汽油 催化汽油 重整汽油 产品 70号汽油 80号汽油 85号汽油 辛烷值 62 78 90 辛烷值 ≥70 ≥80 ≥85 含硫量/% 1.5 0.8 0.2 成本/元?t-1 600 900 1400 含硫量/% ≤1 ≤1 ≤0.6 可用量/t?日-1 2000 1000 500 销售价/元? t-1 900 1200 1500 表2汽油产品的质量要求与销售价
解 本例建立数学模型的关键是决策变量的选择，如果选择各种汽油产品的质量，在建立数学模型时会遇到一些困难，定义决策变量xij为第i种原料调入第j种产品油中的数量，记
pj表示单位第j种产品的销售价格，ci为单位第i种原料的生产成本，ei及e'j分别为原料
油和产品油的辛烷值，hi和h'j分别为原料油和产品油的含硫量，si为原料油每日的可用量，首先考虑问题的目标函数，第j种汽油产品所产生的利润为
?(pi?13j?ci)xij
因此目标函数为
??(pj?1i?133j?ci)xij
约束条件应有3组：
汽油产品的辛烷值要求：
e1x1j?e2x2j?e3x3j?e'j(x1j?x2j?x3j),j?1,2,3 汽油产品的含硫量要求：
h1x1j?h2x2j?h3x3j?h'j(x1j?x2j?x3j),j?1,2,3
线性规划实验举例
