某仓库某次需要运输水泥和玻璃两种货物,水泥质量体积为0.9m3 /t。玻璃是1.6m3/t。计划使用的车辆载重量为11t,车厢容积为15m3试问如何载重使车辆的载重能力和车厢容积都被充分利用?
【求解答案】最优解:水泥 4.81490 米³,玻璃 4.16689米³
【求解思路】该题属于运筹学中的线性规划问题。
设水泥1x米³,玻璃x2米³,则根据题意,得到下列关系:
Max 0.9x1+1.6x2 《===使车辆的载重能力达到最大
x1+x2≤15 《===车厢容积不大于15立方米
0.9x1+1.6x2≤11 《===车辆的载重量不大于11吨
由于运筹学中的线性规划问题解决的方法,都是以最小值问题为主,所以最大值可以看成是最小值反问题。因此,本题的线性规划问题可以改写成
Min -0.9x1-1.6x2
s.t. -x1-x2≥15
-0.9x1-1.6x2≥11
x1,x2>0
该线性规划问题,可采用制约函数法的内点法来求解。
内点罚函数法的基本思想:为在目标函数上引入一个关于约束的障碍项,当迭代点由可行域的内部接近可行域的边界时,障碍项将趋于无穷大来迫使迭代点返回可行域的内部,从而保持迭代点的严格可行性。
如:本题的内点罚函数可以这样来写
有了内点罚函数,就可以分别对x1和x2求偏导数,然后用数值分析的方法求解其联立方程组,最后得到其最优解。
【求解过程】
【本题知识点】
1、制约函数法 称为罚函数。罚函数的基本思想是, 通过一系列罚因子构造罚函数,将问题转化为序列无约束极值问题,求罚函数的极小点来逼近原约束极值问题的最优解。
2、内点法。内点罚函数总是从内点出发,并保持在可行域内部进行搜索。
两种B(x)障碍函数的形式为
3、内点罚函数计算步骤:
【说明】本题给出的求解并不是一次完成的,需要预设障碍因子r=1开始计算,并比较结果,如不满足,则进一步减小r值,如 r=0.1,r=0.01,r=0.001,直到结果满足约束条件之一。所以说,求解线性规划问题是一个与时共进的过程。