一般整数规划
LINDO和LINGO软件能求解的优化模型
LINDO/LINGO软件的求解过程
建模时需要注意的几个基本问题
1、尽量使用实数优化模型，减少整数约束和整数变量的 个数 2、尽量使用光滑优化模型，减少非光滑约束的个数 如：尽量少地使用绝对值函数（|x|）、符号函数 （当变量x为正数时取1，为0时取0，为-1时取-1）、 多个变量求最大（或最小）值、四舍五入函数、取整函数 等 3、尽量使用线性优化模型，减少非线性约束和非线性变 量 的个数（如x/y<5 改为x<5y） 4、合理设定变量的上下界，尽可能给出变量的初始值 5、模型中使用的单位的数量级要适当(如小于1000倍)
也可理解为： 为了使该非基变 量变成基变量， 目标函数中对应 系数应增加的量
LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) 3360.000 VALUE REDUCED COST
VARIABLE
X1
X2
20.000000
30.000000
DO RANGE(SENSITIVITY) ANALYSIS? Yes
最优解不变时目标函数 RANGES IN WHICH THE BASIS IS UNCHANGED: 系数允许变化范围 OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE (约束条件不变) COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 x1系数范围(64,96) 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 3 4 50.000000 480.000000 100.000000 10.000000 53.333332 INFINITY 6.666667 80.000000 40.000000 X2 x2系数范围(48,72)
模型求解
Lindo 6.1 软件实现
LP OPTIMUM FOUND AT STEP 2
max 72x1+64x2 st 2) x1+x2<50 3) 12x1+8x2<480 4) 3x1<100 end
OBJECTIVE FUNCTION VALUE 1) 3360.000 VALUE 20.000000 30.000000 REDUCED COST 0.000000 0.000000 DUAL PRICES
LINDO的一些注意事项（一）
1.LINDO中的变量名由字母和数字组成，但必须以字母开头， 且长度不能超过8个字符（只能是英文字符，不能含有中文字 符）。 2.LINDO中不区分大小写字母，包括LINDO中本身的关键字 （如：MAX、MIN等）也不区分大小写字母。 3.LINDO中对优化模型的目标和约束用行号（行名）进行标识， 这些标识会在将来的求解结果报告中用到。用户没有指定行号 （行名）时，系统将自动产生行号，将目标函数所在的行作为 第1行，从第2行起为约束条件。用户也可以人为定义行号或 行名，行号或行名总是以“）”结束，放在相应的约束之前； 行号或行名可以和变量名一样命名，也可以只用数字命名，但 长度同样不能超过8个字符。 4.在LINDO模型的任何地方都可以用“TITLE”语句对输入的 模型命名，用法是在TITLE后面写出其名字（最多72个字符， 可以有汉字），在程序中单独占一行。如：TITLE 第2个例子。
Lindo语法规则
max z 2 x 3 y; 4 x 3 y 10, 3x 5 y 12, x, y 0 (1) (2) (3) (4)
目标函数以MAX或MIN开 头，以END结束，约束条 件以下面几个符号开始。 SUBJECT TO S.T. ST
s.t.
MAX 2x+3y ST !说明：也可以写成 S.T. 或 SUBJECT TO c2) 4X+3y<=10 c3) 3x+5y<12 END
LINDO的一些注意事项（三）
9.可以在模型的“END”语句后面用命令“SUB”（即设置上 界）设定变量的上界，用命令“SLB”设定变量的下界。其用 法是：“SUB vname value”将变量vname的上限设定为 value；但是，用“SUB”和“SLB”表示的上下界约束不计 入模型的约束，因此LINDO也不能给出其松紧判断和敏感性分 析。 10.数值均衡化及其他考虑：约束系数矩阵中的各非零元的绝 对值的数量级差别不能大于1000倍；此外，系数中非零元的 绝对值不能大于100000或者小于0.0001。 11.简单错误的检查和避免。菜单命令“Report|Pictures （Alt+5）”，可以将目标函数和约束表达式中的非零系数通 过列表（或图形）显示出来。
1) 3360.000 VALUE REDUCED COST
结果解释
0.000000
0.000000 DUAL PRICES
VARIABLE
X1
X2
20.000000
30.000000
最优解下“资源”增加1 单位时“效益”的增量
ROW SLACK OR SURPLUS
影子价格
2)
3) 4)
0.000000
Iterations （迭代次数） Infeasibility （不可行性） Objective （当前的目标值） Best IP （整数规划当前的最 佳目标值） IP Bound （整数规划的界） Branches（分支数） Elapsed Time （所用时间） Update Interval （刷新本界 面的时间间隔） Interrupt Solver （中断求解 程序） Close （关闭）
优化模型与LINDO 软件
何亚辉 重庆理工大学网络信息中心
Email：hyh@
优化模型
决策问题：在一系列客观或主管限制条件下，寻求使所关注的某 个或多个指标达到最大（或最小）的决策。例如：
资源分配要在有限资源约束下制定各用户的分配数量，使资 源生产的总效益最大； 运输方案要在满足物资需求和装载条件下安排从各供应点到各需 求点的运量和路线，使运输总费用最低； 生产计划要按照产品工艺流程和顾客需求，制定原料、零件、部 件等订购、投产的日程和数量，尽量降低成本使利润最高。
上述这种决策问题通常称为最优化（Optimization，简称为优 化）问题。 解决优化问题的手段： （1）依赖过去的经验判断面临的问题 （2）做大量的试验反复比较 （3）用数学建模的方法建立优化模型求解最优决策，简称为优化建 模。
优化模型
实际中的 优化模型
Min(Max)
z f ( x)(x ( x1, x2 ...xn )T )
0.000000 40.000000
48.000000
2.000000 0.000000
原料增加1单位, 利润增长48 时间增加1单位, 利润增长2 加工能力增长不影响利润
NO. ITERATIONS=
பைடு நூலகம்
2
35元可买到1桶牛奶，要买吗？ 35 <48, 应该买！ 聘用临时工人付出的工资最多每小时几元？ 2元！
x1系数由24 ×3=72增 加为30×3=90，在 允许范围内
A1获利增加到30元/千克，应否改变生产计划？
不变。
结果解释
影子价格有意义时约束右端的允许变化范围
RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 3 4 50.000000 480.000000 100.000000 10.000000 53.333332 INFINITY 6.666667 80.000000 40.000000 X2
0.000000
0.000000 DUAL PRICES
ROW SLACK OR SURPLUS 2) 3) 4) 0.000000 0.000000 40.000000 2
48.000000 2.000000 0.000000
NO. ITERATIONS=
结果解释
max 72x1+64x2 st 2) x1+x2<50 3) 12x1+8x2<480 4) 3x1<100 end
LINDO求解器运行状态窗口显示的相应信息及含义
名 称 Status （当前状态） 说明 给出当前解决方案的状态，可能的值包括：Optimal（最 优的）, Feasible（可行的）, Infeasible（不可行的） ,Unbounded（未定的） 显示迭代次数 约束不满足的量：“0”表示这个解是可行的。 目标函数的当前值 显示整数规划当前的最佳目标值：“N/A”表示无答案或 无意义。该项只出现在IP（整数规划）模型。 整数规划的界（对最大化问题显示上界；最小化问题显 示下界） 显示分支定界算法已经计算的分支数 显示计算所用时间（单位：s）：“0.00”说明计算太快 了，用时不到0.005s 显示和控制刷新本界面的时间间隔：“1”表示1s；用户 可以直接在界面上修改这个时间间隔 当模型规模比较大时（尤其对整数规划），可能求解时 间会很长，如果不想再等待下去时，可以在程序运行过 程中用鼠标单击该按钮终止计算。 按下该按钮关闭状态窗口，并不终止计算。状态窗口可 以通过选取相应命令重新打开。