文档介绍：第五章线性规划问题的Lingo求解
1
一般线性规划模型的建立与求解
基本理论
线性规划问题的标准形式是等约束的,用矩阵表示如下:
一般线性规划问题都可以通过引入松弛变量与剩余变量的方法化成标准形式。
线性规划模型的一般性质:
(1)比例性,每个决策变量对目标函数以及右端项的贡献与该决策变量的取值成正比。
(2)可加性,每个决策变量对目标函数以及右端项的贡献与其他决策变量的取值无关。
(3)连续性,每个决策变量的取值都是连续的。
比例性和可加性保证了目标函数和约束条件对于决策变量的线性性质,连续性则允许得到决策变量的实数最优解。
单纯形算法的实质:在保证可行(最小比值法则)的前提下,先在可行解上取一个顶点,判断是否达到最优解,如果没有,则通过一定的规则(入基,旋转等)到另一个更优
2
的顶点,如此迭代下去直到最优,或者判断不可行或者判断无界为止。
应用举例
例5-1(运输问题) 两个粮库A1,A2,向三个粮站B1,B2,B3调运大米,两个粮库现存大米分别为4t,8t,三个两站至少需要大米分别为2t,4t,5t,两个粮库到三个粮站的距离(km)如下表,求使运费最低。
解: (1)问题分析:总需求量为11t,小于总库存量12t,所以问题可行。
(2)从线性规划的三个要素出发,决策变量:问题是各个粮仓向粮站调运了多少大米,此调运量就是决策变量。
目标函数:运费和运量和距离有关系,即t*km最小,所以要将运量与相应的距离相乘然后使总和最小。
约束条件:两个粮库的库存量限制和三个粮站需求量的限制。
3
(3)建立模型,设A1,A2分别向B1,B2,B3运送大米x11,x12,x13,x21,x22,x23,则有:
min f=12*x11+24*x12+8*x13+30*x21+12*x22+24*x23
. x11+x12+x13<=4
x21+x22+x23<=8
x11+x21>=2
x12+x22>=4
x13+x23>=5
x11,x12,x13,x21,x22,x23>=0
(4)转化成对应的Lingo建模语言程序1,求解模型,结果如下页图示:
4
5
通过选择Lingo|Generate|Display model将模型展开,方便查看求解报告的第三部分。
相应的添加的剩余变量或者松弛变量。
6
程序改进一、上面解法是一种傻瓜式的直接输入法,适用于程序规模不大的问题,如果问题规模很大的话用这种方式很费力,可以使用矩阵生成器来编写程序2
min f=12*x11+24*x12+8*x13+30*x21+12*x22+24*x23
. x11+x12+x13+y1=4
x21+x22+x23+y2=8
x11+x21-y3=2
x12+x22-y4=4
x13+x23-y5=5
x11,x12,x13,x21,x22,x23,y1,y2,y3,y4,y5>=0
转换成Lingo语言如下所示:
7
8
注:1、写程序要习惯给程序用title命名
2、为了方便查看报告,用行号区分约束
3、此程序的格式可以固定为标准形式的求解模式。
程序改进三:可以减少引入的变量个数,将模型修改为下面的形式
min f=12*x11+24*x12+8*x13+30*x21+12*x22+24*x23
. x11+x12+x13<=4
x21+x22+x23<=8
-x11-x21<= -2
-x12-x22<= -4
-x13-x23<= -5
x11,x12,x13,x21,x22,x23>=0
写成lingo语言如下所示:
9
10