设备C每增加1小时,可增加利润3.166667千元。
对问题二,有Lingo程序:
min=10*x11+5*x12+6*x13+4*x21+8*x22+12*x23;
x11+x12+x13=60; x13+x23=40;
求解结果为:
Global optimal solution found.
Objective value: 940.0000 Infeasibilities: 0.000000 Total solver iterations: 1
Variable Value Reduced Cost X11 0.000000 9.000000 X12 20.00000 0.000000 X13 40.00000 0.000000 X21 50.00000 0.000000 X22 50.00000 0.000000 X23 0.000000 3.000000
Row Slack or Surplus Dual Price 1 940.0000 -1.000000 2 0.000000 0.000000 3 0.000000 -3.000000 4 0.000000 -1.000000 5 0.000000 -5.000000
6 0.000000 -6.000000
x21+x22+x23=100; x11+x21=50; x12+x22=70;
结果解释:分配供煤量为(0,20,40;50,50,0),最小运输量为940,
三、线性规划问题解的理论 1.线性规划模型的标准型
实际问题的线性规划模型是多种多样的,在众多的样式中可规定一种样式为标准型,以便于研究和求解.
在线性规划模型的标准型中,有n个决策变量,m个约束条件,约束条件为等式约束,且决策变量为非负.
求目标函数的最小值.标准型表达式为:
max(min)Z?c1x1?c2x2????cnxn
?a11x1?a12x2????a1nxn?b1?ax?ax????ax?b2112222nn2??s.t.?????????????????
?ax?ax????ax?bm22mnnm?m11??xi?0,i?1,2,?n在标准型中,规定各约束条件的右端项bi≥0,否则等式两端乘以“-1”,其简写形式为;
minz?cTX?AX?b
s.t.??X?0其中,A称为约束条件的系数矩阵,c为价值向量,b为资源向量,X为决策向量。
关于线性规划模型的求解,通常用单纯形法。这里不讲,只讲如何用Lingo11.0规划软件来求解。(Lingo软件的算法就是单纯形法)
先建立如下例题的线性规划模型。
例2 某工厂生产甲、乙、丙三种铝合金产品,生产每单位产品甲需用铝和铁分别是3公斤和2公斤,生产每单位产品乙需用铝和铁分别是1公斤和3公斤,生产每单位产品丙需用铝和铁分别是1公斤和2公斤,已知生产每单位产品分别能获得5元、4元和3元,而工厂每天能得到的原料供应为铝840公斤、铁700公斤。试问如何安排三种铝合金产品的生产,可使工厂能获得最大利润?
解:将所有关系用表格形式表出,便于建立模型。
甲 乙 丙 铝 3 1 1 铁 获利 2 3 2 5 4 3 供应量 840 700 建立模型如下:设决策变量:x1,x2,x3分别为甲、乙、丙的产量,则 Max = 5*x1+4*x2+3*x3; S.t. 3*x1+x2+x3<=840; 2*x1+3*x2+2*x3<=700; 结果为:
Global optimal solution found.
Objective value: 1540.000 Infeasibilities: 0.000000 Total solver iterations: 2
Variable Value Reduced Cost X1 260.0000 0.000000 X2 60.00000 0.000000 X3 0.000000 0.000000
Row Slack or Surplus Dual Price 1 1540.000 1.000000 2 0.000000 1.000000
3 0.000000 1.000000
x1=260,x2=60,x3=0,最大利润为1540元。资源全部用完。
灵敏度分析:
先设置:LINGO->Options->General Solver->Dual Computations:选中prices & Rangens,点OK。
再作灵敏度分析:LINGO->Range,得如下结果:
Ranges in which the basis is unchanged:
Objective Coefficient Ranges
Current Allowable Allowable Variable Coefficient Increase Decrease X1 5.000000 7.000000 0.0 X2 4.000000 3.500000 0.0 X3 3.000000 0.0 INFINITY
Righthand Side Ranges
Row Current Allowable Allowable RHS Increase Decrease 2 840.0000 210.0000 606.6667 3 700.0000 1820.000 140.0000
当前价值系数为5,4,3,当x1系数在[5-0,5+7]范围内变化时,最优解不变,但最优值(即最优获利)会随之改变。当x2系数在[4-0,4+3.5]范围内变化时,最优解不变。
当前资源量为840,700,当铝供应量在[840-606.6667,840+210]范围内变化时,最优基不变(即原来不生产的x3仍不生产),但最优解会改变,最优值也会改变。同理,铁供应量在[700-140,700+1820]内变化时,最优基不变。
例3 某药厂生产A、B、C三种药物,可供选择的原料有甲、乙、丙、丁。四种原料的成本分别是每公斤5、6、4、8元,每公斤不同原料所能提取的各种药物的数量如下表
甲 乙 丙 丁
A 1 1 1 1 B 5 4 5 6 C 2 1 1 2 成本 5 6 4 8 药厂要求每天生产A恰好100单位,B至少530单位,C不超过160单位,要求选配各种原料的数量既满足生产需要,又使总成本最小。试建立此问题的数学模型。
请自己完成。
例4 某厂制造三种仪器,甲种仪器需要17小时加工装配,8小时校验,售价300元;乙种仪器需要10小时加工装配,4小时校验,售价200元;丙种仪器需要2小时加工装配, 2小时校验,售价100元.可供利用的加工装配时间为1000小时,校验时间为500小时,三种仪器所用的元件和材料基本一样。又据市场预测表明,对甲种仪器的要求不超过50台,乙种仪器不超过80台,丙种仪器不超过150台.(整数规划)
工厂要决定能获得最大总产值的最优生产计划.试写出这个问题的数学模型. 解:建立表格形式: 甲仪器 乙仪器 丙仪器 可供资源 装配 17 10 2 1000 校验 8 4 2 500 售价 300 200 100 要求 <50 <80 <150 建立模型如下:设生产仪器分别为x1,x2,x3 Max = 300*x1+200*x2+100*x3; 17*x1+10*x2+2*x3<=1000; 8*x1+4*x2+2*x3<=500;
X1<50 ;x2<80 ;x3<150 ; @gin(x1);@gin(x2);@gin(x3);
!(@gin(x1)指x1为整数,若要求x1为0-1变量,则@bin(x1))