整数规划模型
实际问题中x x x x f z Max Min T
n ")
,(),()(1==或的优化模型m
i x g t s i ",2,1,0)(..=≤x ~决策变量
f (x )~目标函数
g i (x )≤0~约束条件多元函数决策变量个数n 和
数线性规划条件极值约束条件个数m 较大最优解在可行域学规非线性规划解
的边界上取得
划
整数规划
Programming
+Integer
所有变量都取整数，称为纯整数规划；有一部分取整数，称为混合整数规划；限制取0，1称为0‐1型整数规划。
型整数规划
+整数线性规划
max(min) n
z c x =1
j j
j n
=∑1
s.t. (,) 1,2,,ij j i j a x b i m
=≤=≥=∑"12 ,,,0 ()
n x x x ≥"且为整数
或部分为整数
+例：假设有m 种不同的物品要装入航天飞机，
它们的重量和体积分别为价值为w j 和v j ，价值为c j ，航天飞机的载重量和体积限制分别为W 和V ，如何装载使价值最大化？
m
1⎧1max j j
j c y =∑ 1 0j j y =⎨
被装载 s.t. m
j j v y V
≤∑0
j ⎩没被装载1j m
=1
j j j w y W
=≤∑ 0 or 1 1,2,,j y j m
=="
(Chicago)大学的Linus Schrage教授于1980年美国芝加哥(Chi)Li S h
前后开发, 后来成立LINDO系统公司（LINDO Systems Inc.），网址：
I）网址htt//li d
LINDO: Interactive and Discrete Optimizer (V6.1) Linear(V61) LINGO: Linear Interactive General Optimizer (V8.0) LINDO——解决线性规划LP—Linear Programming，整数规划IP—Integer Programming问题。
LINGO——解决线性规划LP—Linear Programming，非线性规划NLP—Nonlinear Programming，整数规划IP—Integer Programming
g g整划g g g 问题。
1.“>”（或“<”）号与“>=”（或“<=”）功能相同
2.甚至回车 但无运算变量与系数间可有空格(甚至车),但算符
3.变量名以字母开头，不能超过变量名字母开头，不能超过8个字符
4.变量名不区分大小写（包括LINDO 中的关键字）
5.目标函数所在行是第一行，第二行起为约束条件
6.
行号(行名)自动产生或人为定义。行名以“）”结束
7.变量不能出现在一个约束条件的右端
变量不能出现在个约束条件的右端
8. 表达式中不接受括号“( )”和逗号“,”等任何
符号, 例: 400(X1+X2)需写为400X1+400X2 9.表达式应化简，如2X1+3X2‐4X1应写成‐
2X1+3X2
2X13X2
10.缺省假定所有变量非负；可在模型的“END”
语句后用“FREE name”将变量name的非负
假定取消
11.“END”后对0‐1变量说明：INT n或INT name
12.“END”后对整数变量说明：GIN n或GIN
12后对整数变量说明
name
汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量。材劳动时间的需求利润及工厂每月的现有量。
小型中型大型现有量钢材（吨） 1.5 3 5 600
劳动时间（小时）280 250 400 60000
利润（万元）2 3 4
•制订月生产计划，使工厂的利润最大。
制订月生产计划使工厂的利润最大
•如果生产某一类型汽车，则至少要生产80辆，
那么最优的生产计划应作何改变？
汽车厂生产计划汽车厂产计划模型建立小型
中型大型
现有量
设每月生产小、中、大型模建
中
钢材
1.5 3 5 600
60000汽车的数量分别为x 1,x 2,x 3
时间280 250 400 利润
2 3 4
3
21432x x x z
Max ++=线性
600
535.1..321≤++x x x t s 60000400250280≤++x x x 线规划
模型
3210
,,3
2
1
≥x x x (LP)
模型OBJECTIVE FUNCTION VALUE 求解
1)632.2581VARIABLE VALUE REDUCED COST X164.5161290.000000X2167.7419280.000000X30.0000000.946237结果为小数，
ROW SLACK OR SURPLUS DUAL PRICES
2)0.0000000.731183
3)0.0000000.003226
怎么办？1）舍去小数：取x 1=64，x 2=167，算出目标函数值z =629，与LP 最优值632.2581相差不大。
2）试探：如取x 1=65，x 2=167；x 1=64，x 2=168等，计算函数值z ，通过比较可能得到更优的解。
•但必须检验它们是否满足约束条件。
3）模型中增加条件：x 1,x 2,x 3均为整数，重新求解。
