文档介绍：第五章线性规划向题的ingo求解
opt f(r)
1(x)=0,=1,…,m
81(x)≤0,j=1
4(x)20,k=1…,n
X∈
线性规划
数学规划或连续规划
非线性规划
整数线性规划
优化问题
整数非线性规划
离散优化或组合优整数规划纯整数规划
混合整数规划
其他组合优化
线性规划问题的标准形式是等约束的,用矩阵表示如下
min f(r)=cr
Ax= b
般线性规划问题都可以通过引入松弛变量与剩余变量的方法化成标准形式。
线性规划模型的一般性质
(1)比例性,每个决策变量对目标函数以及右端项的贡献与该决策变量的取值成正比
(2)可加性,每个决策变量对目标函数以及右端项的贡献与其他决策变量的取值无关。
(3)连续性,每个决策变量的取值都是连续的。
比例性和可加性保证了目标函数和约束条件对于决策变量的线性性质,连续性则允许得
到决策变量的实数最优解。
单纯形算法的实质:在保证可行(最小比值法则的前提下,先在可行解上取一个顶点
判断是否达到最优解,如果没有,则通过一定的规则(入基,旋转等)到另一个更优
的顶点,如此迭代下去直到最优,或者判断不可行或者判断无界为止
512应用举例
例5-1(运输问题)两个粮库A1A2向三个粮站B1,B2,B3调运大米,两个粮库现存大
米分别为4t,8t,三个两站至少需要大米分别为2t4t5t,两个粮库到三个粮站的距
离(km)如下表,求使运费最低
库存
A2
30
12
24
8
需求24
解:(1)问题分析:总需求量为1t,小于总库存量12t,所以问题可行。
(2)从线性规划的三个要素出发,决策变量:问题是各个粮仓向粮站调运了多少大米,
此调运量就是决策变量。
目标函数:运费和运量和距离有关系,即t*km最小,所以要将运量与相应的距离相
乘然后使总和最小
约束条件:两个粮库的库存量限制和三个粮站需求量的限制。
(3)建立模型,设A1,A2分别向B1,B2,B3运送大米x1112,x13x21,x22,x23,则有
minf=12*×11+24*x12+8*x13+30*x21+12*×22+24*x23
+X12+X13<=4
x21+X22+×23<=8
11+x21>=2
X12+X22>=4
X13+X23>=5
11,x12x13,X21,x22,x23>=0
(4)转化成对应的 Lingo建模语言程序1,求解模型,结果如下页图示:
mode↓
min=1211+2412+83×13+303x21+12×22+245×2
1b1apta1=a1ut1o。trd
Iver iterat
slack
000000
通过选择 Lingo Generate Display model将模型展开,方便査看求解报告的第三部分
8+5<一日
ariable
相应的添加的剩
余变量或者松弛
变量。
0. 000000
程序改进一、上面解法是一种傻瓜式的直接输入法,适用于程序规模不大的问题,如
果问题规模很大的话用这种方式很费力,可以使用矩阵生成器来编写程序2
minf=12×11+24*×12+8*×13+30*x21+12*x22+24*x23
st.×11+×12+x13+y1=4
X21+x22+X23+y2=8
11+x21y3=2
X12+x22y4=4
x13+x23y5=5
11.×12,x13x21,×22,x23,y1,y2y3,y4,y5>=0
转换成 Lingo语言如下所示:
NGO Mode-LINGO 1
rma cel
it1e:调运大米的运输问题程序2
et彐
hamg}1..5/:};!定义矩阵的行
1/1,,11/:c,x:!定义矩阵的列以及变量
ihu(hang,lie:既:!定义约東系数矩阵
insets
data
111nn1nd口
1010000-10
101000
12248301
00 0
R
enddata
标准形式的目
YUE SHU
[ OBu]min=aur【11e:c*x)
H(2
fpr(hang∴i】:
YUESHU( 3)
esum(lie(3):a(1,3)*x())=b(i
enc
JE SHU( 5)
注:1、写程序要****惯给程序用ttle命名
2、为了方便查看报告,用行号区分约束
此程序的格式可以固定为标准形式的求解模式
程序改进