整数规划模型实际问题中x x x x f z Max Min Tn "),(),()(1==或的优化模型mi 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) nz c x =1j jj n=∑1s.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 ，如何装载使价值最大化？m1⎧1max j jj c y =∑ 1 0j j y =⎨被装载 s.t. mj j v y V≤∑0j ⎩没被装载1j m=1j 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 dLINDO: 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 Programmingg g整划g g g 问题。
1.“>”（或“<”）号与“>=”（或“<=”）功能相同2.甚至回车 但无运算变量与系数间可有空格(甚至车),但算符3.变量名以字母开头，不能超过变量名字母开头，不能超过8个字符4.变量名不区分大小写（包括LINDO 中的关键字）5.目标函数所在行是第一行，第二行起为约束条件6.行号(行名)自动产生或人为定义。
行名以“）”结束7.变量不能出现在一个约束条件的右端变量不能出现在个约束条件的右端8. 表达式中不接受括号“( )”和逗号“,”等任何符号, 例: 400(X1+X2)需写为400X1+400X2 9.表达式应化简，如2X1+3X2‐4X1应写成‐2X1+3X22X13X210.缺省假定所有变量非负；可在模型的“END”语句后用“FREE name”将变量name的非负假定取消11.“END”后对0‐1变量说明：INT n或INT name12.“END”后对整数变量说明：GIN n或GIN12后对整数变量说明name汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量。
材劳动时间的需求利润及工厂每月的现有量。
小型中型大型现有量钢材（吨） 1.5 3 5 600劳动时间（小时）280 250 400 60000利润（万元）2 3 4•制订月生产计划，使工厂的利润最大。
制订月生产计划使工厂的利润最大•如果生产某一类型汽车，则至少要生产80辆，那么最优的生产计划应作何改变？汽车厂生产计划汽车厂产计划模型建立小型中型大型现有量设每月生产小、中、大型模建中钢材1.5 3 5 60060000汽车的数量分别为x 1,x 2,x 3时间280 250 400 利润2 3 4321432x x x zMax ++=线性600535.1..321≤++x x x t s 60000400250280≤++x x x 线规划模型3210,,321≥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 PRICES2)0.0000000.7311833)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均为整数，重新求解。
整数规划(Integer Programming ,简记IP )IP 可用LINDO 直接求解max 321432x x x z Max ++=模型求解2x1+3x2+4x3st600535.1..321≤++x x x t s 60000400250280321≤++x x x 1.5x1+3x2+5x3<600280x1+250x2+400x3<60000end为非负整数321,,x x x “gin 3”表示“前3个变量为gin 3OBJECTIVE FUNCTION VALUE )IP 结果输出整数”，等价于：gin x1i 21)632.0000VARIABLE VALUE REDUCED COST X164.000000‐2.000000gin x2gin x3 的最解6680最值632X2168.000000‐3.000000X3 0.000000 ‐4.000000IP 的最优解x 1=64，x 2=168，x 3=0，最优值z =632汽车厂生产计划汽车厂产计划•若生产某类汽车，则至少生产80辆，求生产计划。
M 80,0,0321≥==x x x 0,80,0321=≥=x x x 321432x x x z Max ++=600535.1..321≤++x x x t s 80,80,0321≥≥=x x x 60000400250280321≤++x x x x x x =0 ≥80×0,0,80321==≥x x x 0,80,80321=≥≥x x x 方法1：分解为8个LP 子模型1,2,3或其中3个子模型应去掉，然后逐一求解比较目标函数值80,0,80321≥=≥x x x 808080≥≥≥x x x ×逐求解，比较目标函数值，再加上整数约束，得最优解：,,3210,,321=x x x ×x 1=80，x 2= 150，x 3=0，最优值z =610•若生产某类汽车，则至少生产80辆，求生产计划。
方法2：引入0‐1变量，化为整数规划产车产产计M 为大的正数，x 1=0 或≥800}1,0{,80,11111∈≥≤y y x My x 可取1000 x 2=0 或≥80x =0 或≥80}1,0{,80,22222∈≥≤y y x My x }1,0{,80,33333∈≥≤y y x My x LINDO 中对0‐1OBJECTIVE FUNCTION VALUE 1)610.00003变量的限定：int y1VARIABLE VALUE REDUCED COST X180.000000‐2.000000‐最优解同前int y2int y3 X2150.000000 3.000000X30.000000‐4.000000Y1 1.0000000.00000010000000000000解同前Y2 1.0000000.000000Y3 0.000000 0.000000售价4800元/吨汽油甲库存500吨(A ≥50%) 原油A汽油乙市场上可买到不超过售价5600元/吨库存1000吨原油B (A ≥60%)1500吨的原油A ：•购买量不超过500吨时的单价为10000元/吨；•购买量超过500吨但不超过1000吨时，超过500吨的8000元/吨；该公司应如何安排原油的采购和加部分•购买量超过1000吨时，超过1000吨的部分6000元/吨。
该公司应如何安排原油的采购和加工？问题•利润：销售汽油的收入A 分析利润销售汽油的收购买原油的支出•难点：原油A 的购价与购买量的关系较复杂决策原油A 的购买量,原油A, B 生产汽油甲,乙的数量变量甲(A ≥50%) A购买x →x 11x 12x 214.8千元/吨目标B 乙(A ≥60%) x 22 5.6千元/吨函数c (x ) ~ 购买原油A 的支出利润(千元))()(6.5)(8.422122111x c x x x x z Max −+++=c (x )如何表述？•目标x ≤500吨单价为10千元/吨；•500吨≤x ≤1000吨，超过500吨的8千元/吨；吨超过吨函数⎧•1000吨≤x ≤1500吨，超过1000吨的6千元/吨。
⎪⎨≤≤+≤≤=1000)(500 1000 8500)(0 10)(x x x x x c 约束⎪⎩≤≤+500)1(1000 30006x x 原油供应条件x x x +≤+5001211购买x ↓Ax 11x 500吨10002221≤+x x B 12x 21x 库存库存1000吨1500≤x 22汽油含原油约束A 的比例限制条件x 115.011≥+x x x 2111x x ≥⇔甲(A ≥50%) Ax 12x 21211112x B 乙(A ≥60%)x 22数中是线数是线划6.02212≥+x x 221232x x ≥⇔¾目标函数中c (x )不是线性函数，是非线性规划；¾，一般的非线性规划软对于用分段函数定义的c (x )，般的非线性规划软件也难以输入和求解；想法将型简用成的软件求解¾想办法将模型化简，用现成的软件求解。
x x x ~以价格10, 8, 6(A 模型求解1 ,2 ,3 价格,,(千元/吨)采购的吨数=+x +x c =+8+6目标x x 1x 2x 3, (x ) 10x 18x 26x 3函数)6810()(6.5)(8.432122122111x x x x x x x z Max ++−+++=y 1, y 2 , y 3=1 ~以价格10, 8, 6(千元/吨)采购A 增108加112500500y x y ≤≤223500500y x y ≤≤x 1 , x 2 , x 3 ~以价格10, 8, 6(千元/吨)采购A 的吨数y =0 →x =0约束33500y x ≤y 1,y 2,y 3 =0或1 x >0 →y =1Max 4.8x11+4.8x21+5.6x12+5.6x22‐10x1‐8x2‐6x3stx11+x12‐x<500x21+x22<100005x1105x21>00.5x11‐0.5x21>00.4x12‐0.6x22>0x ‐x1‐x2‐x3=0‐x1500y1<0x2‐500y2<0x3‐500y3<0‐500y2>0x1500y20x2‐500y3>0endint y1yint y2int y30‐1线性规划模型，可用LINDO求解OBJECTIVE FUNCTION VALUE1)5000.000VARIABLE VALUE REDUCED COSTY1 1.0000000.000000Y2 1.0000002200.000000Y3 1.0000001200.000000X110.0000000.80000000000000800000X210.0000000.800000X121500.0000000.000000X221000.0000000.000000X1500.0000000.000000X2500.0000000.000000X30.0000000.400000X 1000.0000000.00000010000000000000000购买1000吨原油A，与库存的500吨原油A和1000吨原油B 一起，生产2500吨汽油乙，利润为5,000千元。