0-1线性规划模型
- 格式:ppt
- 大小:446.51 KB
- 文档页数:25
线性规划一、判断题1.在线性规划的模型中全部变量要求是整数(✗)2.如果一个线性规划问题有两个不同的最优解,则它有无穷多个最优解。
(✓)3.如果一个线性规划问题有可行解,就一定有最优解。
(✗)4.线性规划的基本类型是“max”型问题。
(✗)5.图解法提供了求解线性规划问题的通用方法。
(✗)6.线性规划问题的可行解集不一定是凸集。
(✗)7.若线性规划问题的可行域无界,则该线性规划问题一定没有最优解。
(✗)8.若线性规划模型的可行域非空有界,则其顶点中必存在最优解。
(✓)9.线性规划数学模型中的决策变量必须是非负的。
(✗)10.凡具备优化、限制、选择条件且能将有关条件用关于决策变量的线性表达式表示出来的问题可以考虑用线性规划模型来处理。
(✓)二、选择题1.建立模型的一个基本理由是去揭晓那些重要的或有关的( B )。
A.数量B.变量C.约束条件D.目标函数2.线性规划模型不包括下列( D )要素。
A.目标函数B.约束条件C.决策变量D.状态变量3.下面( D )不属于构成线性规划问题的必要条件。
A.有一个待实现的目标B.有若干个可供选择的方案C.所有资源具有一定的约束限制D.明确求目标函数的极大值4.关于线性规划模型,下面( D )的叙述正确。
A.约束方程的个数多于一个B.求极大值问题时,约束条件都是小于或等于号C.求极小值问题时,目标函数中变量的系数均为正D.变量的个数一般多于约束方程的个数对偶问题一、判断题1 、任何线性规划问题存在并具有唯一的对偶问题。
(✓)2 、对偶问题的对偶问题一定是原问题。
(✓)3 、如线性规划的原问题存在可行解,则其对偶问题也一定存在可行解。
(✗)4 、如线性规划的对偶问题无可行解,则原问题也一定无可行解。
(✗)5 、若原问题为无界解,则其对偶问题无可行解。
(✓)二、选择题1 、线性规划原问题的目标函数为求极小值型,若其某个变量小于等于0 ,则其对偶问题约束条件为( A )形式。
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。