下载文档原格式
1、线性规划和整数规划实验1、加工奶制品的生产计划（1）一奶制品加工厂用牛奶生产A1, A2两种奶制品，1桶牛奶可以在甲车间用12小时加工成3千克A1产品，或者在乙车间用8小时加工成4千克A2 产品.根据市场需求，生产的A1、A2产品全部能售出，且每千克A1产品获利24元，每千克A2产品获利16元.现在加工厂每天能得到50桶牛奶的供应，每天正式工人总的劳动时间为480小时，并且甲车间的设备每天至多能加工100 千克A1产品，乙车间的设备的加工能力可以认为没有上限限制.试为该厂制订一个生产计划，使每天获利最大，并进一步讨论以下3个附加问题: （i）若用35元可以买到1桶牛奶，是否应作这项投资?若投资，每天最多购买多少桶牛奶?(ii)若可以聘用临时工人以增加劳动时间，付给临时工人的工资最多是每小时几元?(iii)由于市场需求变化，每千克A1产品的获利增加到30元，是否应改变生产计划?(2)进一步，为增加工厂获利，开发奶制品深加工技术.用2小时和3元加工费，可将1千克A1加工成0.8千克高级奶制品B1，也可将1千克A2加工成0.75千克高级奶制品B2，每千克B1可获44元，每千克B2可获32元.试为该厂制订一个生产销售计划，使每天获利最大，并进一步讨论以下问题:(i)若投资30元可增加供应1桶牛奶，投资3元可增加1小时劳动时间，是否应作这项投资?若每天投资150元，或赚回多少?(ii)每千克高级奶制品B1, B2的获利经常有10%的波动，对制订的生产销售计划有无影响?若每千克B1的获利下降10%，计划是否应作调整?解：由已知可得1桶牛奶，在甲车间经过十二小时加工完成可生产3千克的A1，利润为72元；在乙车间经八小时加工完成可生产四千克的A2，利润为64元。
利用lingo软件，编写如下程序：model:max=24*3*x1+16*4*x2;s.t.12*x1+8*x2≤480;x1+x2≤50;3*x1≤100;X1≥0,x2≥0end求解结果及灵敏度分析为：Objective value: 3360.000Total solver iterations: 2Variable Value Reduced CostX1 20.00000 0.000000X2 30.00000 0.000000Row Slack or Surplus Dual Price1 3360.000 1.0000002 0.000000 2.0000003 0.000000 48.000004 40.00000 0.000000Objective Coefficient RangesCurrent Allowable Allowable Variable Coefficient Increase DecreaseX1 72.00000 24.00000 8.000000X2 64.00000 8.000000 16.00000Righthand Side RangesRow Current Allowable AllowableRHS Increase Decrease2 480.0000 53.33333 80.000003 50.00000 10.00000 6.6666674 100.0000 INFINITY 40.00000 分析结果：1）从结果可以看出在供应甲车间20桶、乙车间30桶的条件下，获利可以达到最大3360元。
整数规划模型实际问题中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问题。
数学建模线性规划与整数规划数学建模是一门将实际问题转化为数学问题，并利用数学方法解决的学科。
线性规划和整数规划是数学建模中常用的两种模型，它们在实际问题中有着广泛的应用。
本文将重点介绍线性规划和整数规划的概念、模型形式以及求解方法。
一、线性规划（Linear Programming）线性规划是一种在约束条件下求解线性目标函数最优解的数学模型，它的基本形式可以表示为：Min（或Max）：C₁X₁ + C₂X₂ + ... + CₙXₙSubject to：A₁₁X₁ + A₁₂X₂ + ... + A₁ₙXₙ ≤ b₁A₂₁X₁ + A₂₂X₂ + ... + A₂ₙXₙ ≤ b₂...Aₙ₁X₁ + Aₙ₂X₂ + ... + AₙₙXₙ ≤ bₙX₁, X₂, ... , Xₙ ≥ 0在上述模型中，C₁,C₂,...,Cₙ为目标函数的系数，Aᵢₙ为不等式约束条件的系数，bᵢ为不等式约束条件的右端常数，X₁,X₂,...,Xₙ为决策变量。
线性规划的求解可以通过单纯形法或内点法等算法实现。
通过逐步优化决策变量的取值，可以得到满足约束条件并使目标函数达到最优的解。
二、整数规划（Integer Programming）整数规划是在线性规划基础上增加了决策变量必须取整的要求，其模型形式为：Min（或Max）：C₁X₁ + C₂X₂ + ... + CₙXₙSubject to：A₁₁X₁ + A₁₂X₂ + ... + A₁ₙXₙ ≤ b₁A₂₁X₁ + A₂₂X₂ + ... + A₂ₙXₙ ≤ b₂...Aₙ₁X₁ + Aₙ₂X₂ + ... + AₙₙXₙ ≤ bₙX₁, X₂, ... , Xₙ ≥ 0X₁,X₂,...,Xₙ为整数整数规划在实际问题中常用于需要求解离散决策问题的情况，如装配线平衡、旅行商问题等。
然而，由于整数规划问题的整数约束，其求解难度大大增加。
求解整数规划问题的方法主要有分支定界法、割平面法、遗传算法等。
实验四：整数规划一、实验目的：整数规划问题建模及软件求解。
二、实验要求：1.掌握一般整数规划、0-1整数规划问题、指派问题的建模；2.了解求解整数规划问题的方法：分支定界法、割平面法、隐枚举法、匈牙利法；3.学会用matlab 、 lingo 软件求解整数规划问题。
三、实验内容：1、求解下列整数规划问题：⎪⎪⎩⎪⎪⎨⎧≥≤+≤++=.,0,30561652..max 2121212121为整数x x x x x x x x t s x x z(1)给出lingo 原始代码；(2)求解结果粘贴。
(1)model :max =x1+x2;2*x1+5*x2<=16;6*x1+5*x2<=30;@gin (x1);@gin (x2);end(2)Global optimal solution found.Objective value: 5.000000Objective bound: 5.000000Infeasibilities: 0.000000Extended solver steps: 0Total solver iterations: 0Variable Value Reduced Cost X1 5.000000 -1.000000 X2 0.000000 -1.000000Row Slack or Surplus Dual Price 1 5.000000 1.000000 2 6.000000 0.000000 3 0.000000 0.0000002、求解下列0-1整数规划问题：⎪⎩⎪⎨⎧==≤+-+-≤--+-+-+-=.5,4,3,2,1,100242645723..4352max 543215432154321i x x x x x x x x x x x t s x x x x x z i或 (1)给出matlab 、lingo 原始代码；(2)求解结果粘贴。
(1)Lingomodel :max =2*x1-x2+5*x3-3*x4+4*x5;3*x1-2*x2+7*x3-5*x4-4*x5<=6;x1-x2+2*x3-4*x4+2*x5<=0;@bin (x1);@bin (x2);@bin (x3);@bin (x4);@bin (x5);!sets: A/1..5/x @(for(A:@bin(x)));end(2)Global optimal solution found.Objective value: 7.000000Objective bound: 7.000000Infeasibilities: 0.000000Extended solver steps: 0Total solver iterations: 0Variable Value Reduced Cost X1 1.000000 -2.000000X2 1.000000 1.000000X3 1.000000 -5.000000X4 1.000000 3.000000X5 1.000000 -4.000000Row Slack or Surplus Dual Price1 7.000000 1.0000002 7.000000 0.0000003 0.000000 0.000000(1)matlabf=[-2 1 -5 3 -4];A=[3 -2 7 -5 -4;1 -2 2 -4 2];b=[6 0];[x,z]=bintprog(f,A,b)z=-z(2)>> exOptimization terminated.x =11111z =-7z =73、（指派问题）现有A,B,C,D,E 5个人，挑选其中4个人去完成4项工作。
整数规划的数学模型及解的特点整数规划IP (integer programming ）:在许多规划问题中,如果要求一部分或全部决策变量必须取整数。
例如,所求的解是机器的台数、人数、车辆船只数等，这样的规划问题称为整数规划，简记IP 。
松弛问题(slack problem)：不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。
若松弛问题是一个线性规化问题，则该整数规划为整数线性规划(integer linear programming)。
一、整数线性规划数学模型的一般形式∑==nj jj x c Z 1min)max(或中部分或全部取整数n j nj i jij x x x mj ni x b xa ts ,...,,...2,1,...,2,10),(.211==≥=≥≤∑=整数线性规划问题可以分为以下几种类型1、纯整数线性规划（pure integer linear programming ）:指全部决策变量都必须取整数值的整数线性规划。
有时,也称为全整数规划.2、混合整数线性规划(mixed integer liner programming)：指决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。
3、0—1型整数线性规划（zero —one integer liner programming ）：指决策变量只能取值0或1的整数线性规划。
1 解整数规划问题0—1型整数规划0-1型整数规划是整数规划中的特殊情形，它的变量仅可取值0或1，这时的变量xi 称为0-1变量，或称为二进制变量.⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≤+≥+≤-+=且为整数0,5210453233max 2121212121x x x x x x x x x x z0—1型整数规划中0—1变量作为逻辑变量(logical variable ），常被用来表示系统是否处于某一特定状态,或者决策时是否取某个方案。
数学建模作业(实验4 整数规划和对策论模型)基本实验1.遗嘱问题一个行为古怪的阿拉伯酋长留下了一份遗嘱，遗嘱中将他的骆驼群分给他的三个儿子：长子至少得到驼群的1/2，次子至少得到驼群的1/3，三子至少得到驼群的1/9，剩余的捐献给慈善机构。
遗嘱中没有指出到底驼群的数目是多少，只是告诉了这个驼群的数目是奇数，并且这个指定的慈善机构恰好得到了一匹骆驼。
利用整数线性规划确定这个酋长到底留下了多少匹骆驼，并指出每个儿子各得到多少匹。
解答解：设长子、次子、三子得到的骆驼数分别为：X1，X2，X3，则目标函数为：X1+X2+X3+1约束条件：X1>=（X1+X2+X3+1）/2X2>=（X1+X2+X3+1）/3X3>=（X1+X2+X3+1）/9X1，X2，X3为整数，且（X1+X2+X3+1）为奇数。
要想求出本题的可行解，则目标函数取得最小。
LINGO程序min=X1+X2+X3+1;X1+X2+X3+1<=2*X1;X1+X2+X3+1<=3*X2;X1+X2+X3+1<=9*X3;Y=(X1+X2+X3)/2;@gin(X1);@gin(X2);@gin(X3);@gin(Y);运行结果Global optimal solution found.Objective value: 27.00000Objective bound: 27.00000Infeasibilities: 0.000000Extended solver steps: 0Total solver iterations: 3Model Class: PILPTotal variables: 4Nonlinear variables: 0Integer variables: 4Total constraints: 5Nonlinear constraints: 0Total nonzeros: 16Nonlinear nonzeros: 0Variable Value Reduced Cost X1 14.00000 1.000000 X2 9.000000 1.000000 X3 3.000000 1.000000 Y 13.00000 0.000000Row Slack or Surplus Dual Price1 27.00000 -1.0000002 1.000000 0.0000003 0.000000 0.0000004 0.000000 0.0000005 0.000000 0.000000由运行结果可得：这个酋长的骆驼数量为27只，长子得到14只，次子得到9只，三子得到3只。
2.固定费用问题由于工作需要张先生打算办理长途电话业务。
现有A ，B 和C 三家电话公司，其中A 公司每月固定话费16元，通话费0.25元/min ；B 公司每月固定话费25元，通话费0.21元/min ；C 公司每月固定话费18元，通话费0.22元/min 。
在一般情况下，张先生每月使用的长途电话时间是200min 。
请问张先生如何选择这3家电话公司，使得每月的电话费最少？解答解：设Xi 表示使用第i 家公司的业务，i=1，2，3。
则目标函数为：X1*(16+200*0.25)+X2*(25+200*0.21)+X3*(18+200*0.22) 约束条件： X1+X2+X3=1X1，X2，X3为整数。
最优解使得目标函数取得最小。
LINGO 程序min =X1*(16+200*0.25)+X2*(25+200*0.21)+X3*(18+200*0.22); X1+X2+X3=1;@bin (X1);@bin (X2);@bin (X3);运行结果Global optimal solution found.Objective value: 62.00000 Objective bound: 62.00000 Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 01,0i i x i ⎧=⎨⎩选择第个公司，不选择第个公司Model Class: PILPTotal variables: 3Nonlinear variables: 0Integer variables: 3Total constraints: 2Nonlinear constraints: 0Total nonzeros: 6Nonlinear nonzeros: 0Variable Value Reduced Cost X1 0.000000 66.00000X2 0.000000 67.00000X3 1.000000 62.00000Row Slack or Surplus Dual Price1 62.00000 -1.0000002 0.000000 0.000000由运行结果可得：张先生应该选择C家电话公司，使得每月电话公司最少为62元。
3.串并联系统可靠性问题有一台电器由三个部件组成，这三个部件串联，假如有一个部件发生故障，电器就不能工作。
可以通过在每个部件里安装1到2个备份元件来提高该电器的可靠性（不发生故障的概率）。
表4.1列出了可靠性和成本费用。
假设制造该电器的已有资金共10万元，那么怎样来构造这件电器呢？解答解：设Xij 表示使用第i 个部件并联就j 个元件，i=1，2，3；j=1，2，3。
则目标函数为：(X11*0.6+X12*0.8+X13*0.9)*(X21*0.7+X22*0.8+X23*0.9)*(X31*0.5+X32*0.7+X33*0.9) 约束条件： X11+X12+X13=1 X21+X22+X23=1 X31+X32+X33=11*X11+2*X12+3*X13+3*X21+5*X22+6*X23+2*X31+4*X32+5*X33<=10 Xij 为整数。
最优解使得目标函数取得最大。
LINGO 程序max =(X11*0.6+X12*0.8+X13*0.9)*(X21*0.7+X22*0.8+X23*0.9)*(X31*0.5+X32*0.7+X33*0.9); X11+X12+X13=1; X21+X22+X23=1; X31+X32+X33=1;1*X11+2*X12+3*X13+3*X21+5*X22+6*X23+2*X31+4*X32+5*X33<=10;@bin (X11);@bin (X12);@bin (X13);@bin (X21);@bin (X22);@bin (X23);@bin (X31);@bin (X32);@bin (X33);运行结果Local optimal solution found.Objective value: 0.5040000 Objective bound: 0.5040000 Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 161,0ij x ⎧=⎨⎩选择这个方案，不选择这个方案Model Class: PINLPTotal variables: 9Nonlinear variables: 9Integer variables: 9Total constraints: 5Nonlinear constraints: 1Total nonzeros: 27Nonlinear nonzeros: 9Variable Value Reduced Cost X12 1.000000-0.1166667E-01X21 1.000000-0.7733333E-01X33 1.000000 0.000000Row Slack or Surplus Dual Price2 0.000000 0.34300003 0.000000 0.20266674 0.000000 0.13066675 0.0000000.7466667E-01由运行结果可得：部件1并联两个元件，部件2并联1个元件，部件3并联3个元件，最终的可靠性为0.504。
4.二选一约束条件某汽车公司正在考虑生产3种类型的汽车：微型、中型和大型。
表4.2给出了每种汽车需要的资源及产生的利润。
目前有6000吨钢材和60000小时的劳动时间。
要生产一种在经济效益上可行的汽车，这种汽车必须至少生产1000辆。
试为该公司制定一个使生产利润达到最大的方案。
解答解：设X1、X2、X3分别表示生产微型汽车、中型汽车、大型汽车的数量； 设Yi 表示生产第i 种汽车，i=1，2，3。
。
则目标函数为：2000*X1*Y1+3000*X2*Y2+4000*X3*Y3 约束条件： X11+X12+X13=1 X21+X22+X23=1 X31+X32+X33=11*X11+2*X12+3*X13+3*X21+5*X22+6*X23+2*X31+4*X32+5*X33<=10 Xij 为整数。
最优解使得目标函数取得最大。
LINGO 程序max =2000*X1*Y1+3000*X2*Y2+4000*X3*Y3; 1.5*X1+3*X2+5*X3<=6000; 30*X1+25*X2+40*X3<=60000; X1>=1000*Y1;X1<=9999*Y1;1,y 0i i i ⎧=⎨⎩生产第种汽车，不生产第种汽车X2>=1000*Y2;X2<=9999*Y2;X3>=1000*Y3;X3<=9999*Y3;@bin(Y1);@bin(Y2);@bin(Y3);@gin(X1);@gin(X2);@gin(X3);运行结果Linearization components added:Constraints: 12Variables: 3Global optimal solution found.Objective value: 6000000.Objective bound: 6000000.Infeasibilities: 0.000000Extended solver steps: 0Total solver iterations: 23Model Class: MILPTotal variables: 9Nonlinear variables: 0Integer variables: 6Total constraints: 21Nonlinear constraints: 0Total nonzeros: 51Nonlinear nonzeros: 0Variable Value Reduced Cost X1 0.000000 0.000000 Y1 0.000000-0.2000000E+09X2 2000.000 -3000.000 Y2 1.0000000.3000000E+09X3 0.000000 0.000000 Y3 0.000000-0.4000000E+09Row Slack or Surplus Dual Price 1 6000000. 1.0000002 0.000000 0.0000003 10000.00 0.0000004 0.000000 0.0000005 0.000000 0.0000006 1000.000 0.0000007 7999.000 0.0000008 0.000000 0.0000009 0.000000 0.000000由运行结果可得：生产中型车2000辆可以使生产利润达到最大为6000000美元。
