线性规划问题的Lingo求解

第五章线性规划问题的Lingo求解opt f ( x) hi ( x) 0, i 1,..., m g ( x) 0, j 1,..., l j s.t. tk ( x) 0, k 1,..., n x D Rn 线性规划 数学规划或连续规划 非线性规划 整数线性规划 整数非线性规划 优化问题 整数规划 纯整数规划 离散优化或组合优化 混合整数规划 其他组合优化

线性规划问题的Lingo求解

5.1 一般线性规划模型的建立与求解5.1.1 基本理论线性规划问题的标准形式是等约束的，用矩阵表示如下： min f ( x) cx Ax b s.t. x 0

一般线性规划问题都可以通过引入松弛变量与剩余变量的方法化成标准形式。 线性规划模型的一般性质：

(1)比例性，每个决策变量对目标函数以及右端项的贡献与该决策变量的取值成正比。(2)可加性，每个决策变量对目标函数以及右端项的贡献与其他决策变量的取值无关。 (3)连续性，每个决策变量的取值都是连续的。

比例性和可加性保证了目标函数和约束条件对于决策变量的线性性质，连续性则允许得到决策变量的实数最优解。 单纯形算法的实质：在保证可行(最小比值法则)的前提下，先在可行解上取一个顶点， 判断是否达到最优解，如果没有，则通过一定的规则(入基，旋转等)到另一个更优

线性规划问题的Lingo求解

的顶点，如此迭代下去直到最优，或者判断不可行或者判断无界为止。

5.1.2 应用举例例5-1(运输问题) 两个粮库A1,A2,向三个粮站B1,B2,B3调运大米，两个粮库现存大 米分别为4t,8t,三个两站至少需要大米分别为2t,4t,5t,两个粮库到三个粮站的距 离(km)如下表，求使运费最低。 B1 A1 12 B2 24 B3 8 库存 4

A2需求

302

124

245

8

解： (1)问题分析：总需求量为11t,小于总库存量12t,所以问题可行。 (2)从线性规划的三个要素出发，决策变量：问题是各个粮仓向粮站调运了多少大米， 此调运量就是决策变量。 目标函数：运费和运量和距离有关系，即t*km最小，所以要将运量与相应的距离相 乘然后使总和最小。 约束条件：两个粮库的库存量限制和三个粮站需求量的限制。

线性规划问题的Lingo求解

(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 s.t. 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,求解模型，结果如下页图示：

线性规划问题的Lingo求解

线性规划问题的Lingo求解

通过选择Lingo|Generate|Display model将模型展开，方便查看求解报告的第三部分。

相应的添加的剩 余变量或者松弛 变量。

线性规划问题的Lingo求解

程序改进一、上面解法是一种傻瓜式的直接输入法，

适用于程序规模不大的问题，如 果问题规模很大的话用这种方式很费力，可以使用矩阵生成器来编写程序2 min f=12*x11+24*x12+8*x13+30*x21+12*x22+24*x23 s.t. 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语言如下所示：

线性规划问题的Lingo求解

线性规划问题的Lingo求解

注：1、写程序要习惯给程序用title命名 2、为了方便查看报告，用行号区分约束 3、此程序的格式可以固定为标准形式的求解模式。程序改进三：可以减少引入的变量个数，将模型修改为下面的形式 min f=12*x11+24*x12+8*x13+30*x21+12*x22+24*x23 s.t. 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语言如下所示：

线性规划问题的Lingo求解

线性规划问题的Lingo求解

注：1、改程序把不等式约束全部转化为小于等于约束，是为了将约束可 以写到一个循环语句中实现，如果还有等是约束的话，则要在写一个循 环语句来控制约束。 2、当程序比较大的时候，一般将约束按性质进行分类程序改进四：将约束进行分类，代码如下：

线性规划问题的Lingo求解

注：1、在进行调试程序时，可以用!号某些语句屏蔽，缩小寻找出错的范围。 2、可以编写程序边运行，保证每行书写都是正确的 3、常见的出错情况有： (1)定义了多个长度一样的集合，而在使用中区分不明确； (2)定义了同名的属性； (3)漏掉了括号； (4)分号不是英文半角； (5)使用的字母没有定义； (6)循环语句中元素下标颠倒或者不明； (7)约束错误变成不可行或者无界； (8)关系运算符误用成逻辑运算符； (9)函数调用错误等等…

线性规划问题的Lingo求解

例5-2 (阶段生产问题)某公司产品最大生产能力为10000单位，每单位存储费2元， 预定的销售量与单位成本如下表所示： 月份 1 2 3 4 单位成本 70 71 80 76 销售量 6000 7000 12000 6000

求一生产计划，使(1)满足需求；(2)不超过生产能力；(3)成本(生产成本与存储费之和最低) 问题分析：这是一个多阶段生产计划问题，设计多阶段存储，只需要制定1~4月份的 生产计划，不妨假定1月初无库存，4月底卖完，当月生产的不作为当月的库存，库 存量无限制。 模型建立(1): 设xi为第i月产量，di为销售量，ei为存储费，ci为单位成本，则目 标生产成本为:

线性规划问题的Lingo求解

c xj 1 j

4

j

第j月到j+1月的库存量(记作第j+1月的库存量)应该是1月到j月的总产量减去1月到j月的总销售量，即：

x di 1 i i 1

j

j

i

j j xi di e j 1 总的库存费用为： j 1 i 1 i 1 j 4 3 j c j x j xi di e j 1 总成本为： j 1 j 1 i 1 i 1 3

即求总成本的最小值。 约束条件1:如果每个月都有非负的存储量，显然满足要求，可用约束：

线性规划问题的Lingo求解

x di

1 i i 1

j

j

i

0

约束条件2:4个月的总产量等于总需求量即：

x di 1 i i 1

4

4

i

0

约束条件3:产量限制，0<=xi<=10000。 综上，建立如下数学模型：j j min f c j x j xi d i e j 1 j 1 j 1 i 1 i 1 j j xi d i 0, j 1, 2, 3 i 1 i 1 4 4 s.t. xi di 0 i 1 i 1 0 xi 10000, i 1, 2, 3, 4 4 3

转成相应的Lingo语言如下：

线性规划问题的Lingo求解