整数规划和01规划

一、Matlab在线性规划中的应用Linear Programing, 又叫线性最优化(Linear Optimization)1、(1)线性规划首先要有一个目标函数(2)要有一组控制变量(或叫决策变量),且目标函数必须是控制变量的线性组合（即只能是一个线性方程）.(3)需要一组约束条件(等式、不等式约束，特别注意这些变量是否大于0或变量的可能的取值范围) (要尽可能挖掘出所有的条件) （4）线性规划的目标是控制变量在满足约束条件下使目标函数达到最大或最小值。

1、线性规划问题即线性方程求最小值----有一个万能函数fmincon（当目标函数为多元一次方程时，它的最小值可以用此求，但有个万能的命令的fmincon）---且不能带常数项2、线性规划的函数为linprog此函数只能（只能线性方程（每项最多只有一次的多项式），n元-----------(即n元一次方程)完全可以用(因fmincon可以用来求任意方程的最小值)（任意方程，任意n元----任意条件）完全可以用代替（即可以不学linprog）两个函数都只能求最小值，（条件都只能是<=）（什么都是“小”）如要求最大值，两个函数都必须前后两次取反(1)使用格式为:x=linprog(f,A,b)x=linprog(f,A,b,Aeq,beq)x=linprog(f,A,b,Aeq,beq,l,u)x=linprog(f,A,b,Aeq,beq,l,u,x0)（参数个数为：3/5/7/8, 少了X0或让其置于末尾）不要编程序，用向量f来表示目标方程（同线性代数中的线性方程）(2)左边还可为:[x,fval]=……[x,fval,exitflag]=……[x,fval,exitflag,output]=……[x,fval,exitflag,output,lambda]=其中lambda表示拉格朗日乘子的内容所以最好是用三个返回结果，最后要根据exitflag判断结果的有效性(用法与fmincon把函数换成了系数向量(不要编程)(2)x0不要或置于末尾---因为没有额外编写程序)(3)x0为初始向量,一般不要使用f为目标函数的系数向量A*x<=b 构成了线性不等式条件Aeq*x=beq 构成了线性等式条件l<=x<=u 构成了上下限(4)注意:A:如要求最大值,则必须对目标函数取反,转化为先求出最小值,最后再将函数值取反即为所求的最大值.B:不等式约束条件是<=,如果为>=,则必须两边乘以-1,C:如前面的某些项没有使用,必须用空矩阵[ ]d:有3、5、7个等参数线性方程中不能有常数项，如有，先不要考虑，最后在结果上再加（或减）去该常数。

0 1整数规划课程设计一、课程目标知识目标：1. 理解整数规划的基本概念，掌握0-1整数规划的特点及适用场景；2. 学会构建0-1整数规划的数学模型，并能用相关数学语言进行表达；3. 了解0-1整数规划问题的求解方法，掌握其基本原理。

技能目标：1. 能够运用0-1整数规划解决实际问题，独立设计并优化解决方案；2. 学会使用计算工具（如Excel、Lingo等）求解0-1整数规划问题；3. 能够对0-1整数规划问题进行有效分析，提出改进措施。

情感态度价值观目标：1. 培养学生面对实际问题时，运用数学知识解决问题的积极态度和自信心；2. 增强学生的团队协作意识，培养沟通与表达的能力；3. 培养学生的逻辑思维能力和创新意识，提高解决问题的综合素质。

课程性质：本课程为数学学科的一门应用型课程，旨在帮助学生掌握0-1整数规划的基本知识，培养解决实际问题的能力。

学生特点：针对高中年级学生，具备一定的数学基础，对实际问题具有较强的探究欲望。

教学要求：结合学生特点，注重理论与实践相结合，强调学生的主体地位，提高学生的参与度和积极性。

在教学过程中，将课程目标分解为具体的学习成果，便于教学设计和评估。

二、教学内容1. 教学大纲：a. 0-1整数规划基本概念及适用场景；b. 0-1整数规划数学模型的构建；c. 0-1整数规划求解方法及原理；d. 实际问题中的应用案例分析。

2. 教学内容安排与进度：a. 0-1整数规划基本概念及适用场景（1课时）；- 介绍0-1整数规划的定义、特点；- 分析0-1整数规划在实际问题中的应用。

b. 0-1整数规划数学模型的构建（2课时）；- 学习如何用数学语言表达0-1整数规划问题；- 掌握构建0-1整数规划数学模型的方法。

c. 0-1整数规划求解方法及原理（2课时）；- 介绍求解0-1整数规划问题的主要方法；- 分析各种求解方法的原理及优缺点。

d. 实际问题中的应用案例分析（2课时）；- 分析典型实际问题，运用0-1整数规划求解；- 学生动手实践，培养解决实际问题的能力。

01型整数规划模型§5.4 0—1型整数规划模型1、 0—1型整数规划模型概述整数规划指的是决策变量为⾮负整数值的⼀类线性规划，在实际问题的应⽤中，整数规划模型对应着⼤量的⽣产计划或活动安排等决策问题，整数规划的解法主要有分枝定界解法及割平⾯解法（这⾥不作介绍，感兴趣的读者可参考相关书籍）。

在整数规划问题中，0—1型整数规划则是其中较为特殊的⼀类情况，它要求决策变量的取值仅为0或1，在实际问题的讨论中，0—1型整数规划模型也对应着⼤量的最优决策的活动与安排讨论，我们将列举⼀些模型范例，以说明这个事实。

0—1型整数规划的的数学模型为：⽬标函数 n n x c x c x c z Min Max +++=ΛΛ2211)( 约束条件为：==≥≤++=≥≤++=≥≤++1| 0 ) ,() ,() ,(22112222212111212111n m n mn m m n n n n x x x b x a x a x a b x a x a x a b x a x a x a , , ,21ΛΛΛΛΛΛΛΛΛΛΛΛ这⾥，0 | 1表⽰0或1。

2、0—1型整数规划模型的解法0—1型整数规划模型的解法⼀般为穷举法或隐枚举法，穷举法指的是对决策变量nx x x , , ,21ΛΛ的每⼀个0或1值，均⽐较其⽬标函数值的⼤⼩，以从中求出最优解。

这种⽅法⼀般适⽤于决策变量个数n 较⼩的情况，当n 较⼤时，由于n 个0、1的可能组合数为n2，故此时即便⽤计算机进⾏穷举来求最优解，也⼏乎是不可能的。

隐枚举法是增加了过滤条件的⼀类穷举法，该法虽能减少运算次数，但有的问题并不使⽤。

此时，就只能⽤穷举法了。

3. 应⽤实例例1 ⼯程上马的决策问题1）问题的提出某部门三年内有四项⼯程可以考虑上马，每项⼯程的期望收益和年度费⽤（千元）如下表所⽰：假定每⼀项已选定的⼯程要在三年内完成，是确定应该上马哪些⼯程，⽅能使该部门可能的期望收益最⼤。

0-1型整数线性规划模型理论(1) 0-1型整数线性规划0-1型整数线性规划是一类特殊的整数规划,它的变量仅取值0或1.其模型如下:T min ..01(1,2,,)j f s t x j n =⎧⎨=⎩c xAx =b 取或 其中()T 12,,,,n c c c =c ()T 12,,,,n x x x =x (),ij m na ⨯=A ()T 12,,,.mb b b =b 称此时的决策变量为0-1变量,或称二进制变量.在实际问题中,如果引进0-1变量,就可以把各种需要分别讨论的线性(或非线性)规划问题统一在一个问题中讨论了.(2) 求解0-1型整数线性规划的分支界定法Matlab 指令x = bintprog(f,A,b): 求解0-1型整数线性规划,用法类似于linprog.x = bintprog(f,A,b,Aeq,beq): 求解下述线性规划问题:T min ,z =f x ≤Ax b ,≤Ax b ,⋅≤Aeq x beq ,x 分量取0或1.x = bintprog(f,A,b,Aeq,beq,x0): 指迭代初值x0,如果没有不等式约束,可用[]代替A,b 表示默认,如果没有等式约束,可用[]代替Aeq 和beq 表示默认;用[x,fval]代替上述各命令行中左边的x,则可得到最优解处的函数值fval.例如：求解0-1型整数线性规划模型:1min ni i Z x ==∑()()()12345356894679123471256758129232200..20002001(1,2,,9)j x x x x x x x x x x x x x x x x x x x s t x x x x x x x x x x x j ⎧-++++≤-⎪-++++≤-⎪⎪-+++≤-⎪⎪--+≤⎪-≤⎪⎨--+≤⎪⎪-≤⎪-+≤⎪⎪--+≤⎪⎪==⎩或用Matlab 软件编程可解得1236791x x x x x x ======,其他变量为0,共六门课,满足所给条件, Matlab程序代码如下：c = ones(1,9);a =[-1,-1,-1,-1,-1,0,0,0,0;0,0,-1,0,-1,-1,0,-1,-1;0,0,0,-1,0,-1,-1,0,-1;-1,-1,2,0,0,0,0,0,0;0,0,0,1,0,0,-1,0, 0;-1,-1,0,0,2,0,0,0,0;0,0,0,0,0,1,-1,0,0;0,0,0,0,-1,0,0,1,0;-1,-1,0,0,0,0,0,0,2];b = [-2;-3;-2;0;0;0;0;0;0];A = [5 4 4 3 4 3 2 2 3];x = bintprog(c,a,b)f = A*x运行结果：Optimization terminated.x =111111f =20。

MATLAB 求解线性规划（含整数规划和0-1规划）问题线性规划是数学规划中的一类最简单规划问题，常见的线性规划是一个有约束的，变量范围为有理数的线性规划。

如：max 712z x y =+9430045200s.t 310300,0x y x y x y x y +≤⎧⎪+≤⎪⎨+≤⎪⎪≥⎩对于这类线性规划问题，数学理论已经较为完善，可以有多种方法求解此类问题。

但写这篇文章的目的并不是为了介绍数学理论，我们这里主要讲解如果利用工具求解这一类线性规划问题。

最著名，同时也是最强大的数学最优化软件是LINGO/LINDO 软件包，它能够求解多种的数学规划问题，同时还提供了多种的分析能力。

但LINGO 软件并不容易上手，同时，应用LINGO 的场合一般是大规模的线性规划问题，小小的线性规划完全可以不使用它。

一个更受科研人员欢迎的数学软件是MATLAB ，它以功能强大而称著，并有数学软件中的“航空母舰”之称。

我们这里就是要学习使用MATLAB 软件求解线性规划（含整数规划和0-1规划）问题。

为了使得不熟悉MATLAB 的人员也能够使用MATLAB 进行线性规划问题求解，本文将对MATALB 中使用到的函数和过程以及结果进行详细的分析，最后会对每一个问题都给出一个可以完全“套用”的MATLAB 程序。

我们首先从上面的线性规划问题开始，为了便于表达，将上面的式子写成矩阵形式：max 712z x y =+9430045200s.t 310300,0x y x y ⎧⎛⎫⎛⎫⎛⎫⎪ ⎪ ⎪∙≤⎪ ⎪ ⎪ ⎪⎨⎝⎭ ⎪ ⎪⎝⎭⎝⎭⎪⎪≥⎩于是约束就表达为了一个Ax b ≤不等式。

求解MATLAB 线性规划时，最常用的函数是linprog 函数，下面来介绍一下这个函数的使用。

打开MATLAB 帮助文档（PS:帮助文档的内容是最全的，只要你的英文过了专业8级），可以看到linprog 函数求解的是具有如下标准形式的线性规划：min .Tx f x A X b s t Aeq X beq lb x ub ≤⎧⎪=⎨⎪≤≤⎩公式中各符号的意义是自明的，在这里简单介绍下，首先MATLAB 中求解的是目标函数是最小值的问题，但如果我们的目标函数是求最大值，可以通过对目标函数中每一项中乘以-1，将求最大值问题转化为求最小值问题；A ，b 分别为不等式约束中的系数矩阵。

0-1整数规划0-1整数规划1.什么是0-1整数规划？0-1 整数规划是⼀种特殊形式的整数规划，这时的决策变量x i 只取两个值0或1，⼀般的解法为隐枚举法。

2.什么时候采⽤0-1整数规划法？正如计算机只懂得0,1两个数，1代表是，0代表否。

同样的，在0-1整数规划中的0和1并不是真真意义上的数，⽽是⼀个衡量事件是否发⽣的标准。

⼀般来说，我们在从多个事物中选出其中⼀部分，在⼀定的条件下求解最优情况时可以采⽤0-1整数规划法。

⼀、0-1整数规划的求解例1 求解下列0-1规划问题1231231231223123max 3252 2 (1)4 4 (2).. 3 (3) 4 6 (4),,01Z x x x x x x x x x s t x x x x x x x =-++-≤??++≤??+≤??+≤??=?或解：对于0-1 规划问题，由于每个变量只取0，1两个值，⼀般会⽤穷举法来解，由上表可知，问题的最优解为X*=( x1 =1x2=0x3=1 ) 但此法太繁琐，⼯作量相当⼤。

⽽隐枚举法就是在此基础上，通过加⼊⼀定的条件，就能较快的求得最优解：找到x1 =0x2=0x3=1是⼀个可⾏解，为尽快找到最优解，可将3 x1－2 x2＋5 x3≥5作为⼀个约束，凡是⽬标函数值⼩于5的组合不必讨论，如软件进⾏求解。

⼆、0-1整数规划模型的建⽴值得注意的是在0-1整数规划模型建⽴的时候，0,1仅表⽰物件是否被选取，事件是否发⽣，⽆其他含义。

例2⼀个旅⾏者要到某地作两周的带包旅⾏,装背包时,他发现除了已装的必需物件外,他还能再装5公⽄重的东西.他打算从下列4种东西中选取,使增加的重量不超过5公⽄⼜能使使⽤价值最⼤.这4种东西的重量和使⽤价值(这⾥⽤打分解：建⽴模型为()12341234max Z=6x 7392345s.t. 0,11,2,3,4i x x x x x x x x i ++++++≤==??1 234思考：某公司拟在东、西、南三个区建⽴门市部,拟议中有七个点(建⽴门市部的地点)A j(j=1,2,…,7)可供选择;由于某种需要⽽规定:在东区:由A1,A2,A3中⾄多选2个点;在西区:由A4,A5中⾄少选1个点;在南区:由A6,A7中⾄少选1个点;据估计,如选A j点建⽴门市部,则需要投资a j元.⽽每年可获利润c j元,但这笔投资总额不能超过b元.问应选择哪⼏个点可使该公司的年利润为最⼤？。