运筹学：约束极值问题

一、引言在管理科学，经济学和许多工程、科技问题中，常常需求一个多元函数的最大值或最小值，他们统称为最值问题。

通常我们称实际问题中出现的需求最值的函数为目标函数，该函数的自变量称为决策变量，相应的问题在数学上可称为优化问题，在经济管理科学中非常重要的运筹学。

最值（最优化）问题占有较大比重。

最值问题涉及工业、农业、交通运输、军事、商品经济等诸多方面，与人们的生活息息相关。

二、极值定义如果一个函数在一点的一个邻域内处处都有确定的值，而以该点处的值为最大（小），这函数在该点处的值就是一个极大（小）值。

如果它比邻域内其他各点处的函数值都大（小），它就是一个严格极大（小）。

该点就相应地称为一个极值点或严格极值点。

极值的概念来自数学应用中的最大最小值问题。

定义在一个有界闭区域上的每一个连续函数都必定达到它的最大值和最小值，问题在于要确定它在哪些点处达到最大值或最小值。

如果不是边界点就一定是内点，因而是极值点。

这里的首要任务是求得一个内点成为一个极值点的必要条件。

设函数f（x）在x。

附近有定义，如果对x。

附近的所有的点都有f（x）<f（x。

），则f（x。

）是函数f（x）的一个极大值。

如果附近的所有的点，都有f（x）>f（x。

），则f （x）。

是函数f（x）的一个极小值，极大值与极小值统称为极值。

三、多元函数1、多元函数的定义设D为一个非空的n 元有序数组的集合，f为某一确定的对应规则。

若对于每一个有序数组（x1,x2,…,xn）∈D，通过对应规则f，都有唯一确定的实数y与之对应，则称对应规则f为定义在D上的n元函数。

记为y=f （x1,x2,…,xn），（x1,x2,…,xn）∈D 。

变量x1,x2,…,xn称为自变量；y称为因变量。

（xi,其中i是下标。

下同）当n＝1时，为一元函数，记为y=f(x),x∈D;当n＝2时，为二元函数，记为z=f(x,y),(x,y)∈D.二元及以上的函数统称为多元函数。

一、线性规划问题约束条件：不超过各工序可用时间非负约束1）0.7x1+x2≤6302) x1,x2≥0图解法：设定Z值然后带入值取各个公式的两个端点描点画图二、单纯形法步骤：标准化目标函数最大约束条件等式化≤引入松弛变量S ≥剩余变量e 右端非负Max Z=x1+x2. x1+2x2≤6 ,2x1+x2≤16,x1,x2≥0z−x1−x2=0 x1+2x2+s1=6 ,2x1+x2+s2=16 ,x1,x2,s1,s2 ≥0两组约束四个变量故有2个非基本变量，2个基本变量进入变量与离开变量的确定从非基本变量中找一个进入变量（进入到基本变量中），从基本变量中找一个离开变量（作为非基本变量）在Row 0 中，从左往右选择非基本变量中系数最小的作为进入变量（前面化为单位矩阵，为最优解）大M法：步骤同上，约束等式化≤引入松弛变量S ≥剩余变量e+人工变量a（=也是加a）min z=4x1+x2. s.t 3x1+x2=3 ,4x1+3x2≥6, x1+2x2≤4,x1,x2≥0 max z=−4x1−x2−Ma1−Ma2(M=100) s.t 3x1+x2+a1=3 , 4x1+3x2−e2+a2=6, x1+2x2+s3=4,x1,x2,e2,s3,a1,a2 ≥0M假定为无限大正值1.判断是否为最优解ROW a1 a2 系数化为0. 由于此时ROW 0 非基本变量的系数不全为非负数，因此，并非最优解。

进入变量与离开变量的确定重复以上步骤化为单位矩阵取得最优解。

两阶段法：第一阶段：引入人工变量a1,a2 min z=a1+a2 , max z=−a1−a2 min z=4x1+x2, s.t. 3x1+x2=3 ,4x1+3x2≥6 ,x1+2x2≤4,x1,x2≥0 max z=−a1−a2 s.t.3x1+x2+a1=3,4x1+3x2−e2+a2=6x1+2x2+s3=4,x1,x2,e2,s3,a1,a2≥0经过前面变换单位矩阵得到最优解的单纯形表第二阶段：min z=4x1+x2→max z=−4x1−x2将第一阶段最后最优解的单纯形表Row 0 替换为z+4x1+x2=0的系数然后重复上述步骤得到最优解。

《运筹学》试题及答案（六）《运筹学》试题及答案第⼆章线性规划的基本概念⼀、填空题1．线性规划问题是求⼀个线性⽬标函数_在⼀组线性约束条件下的极值问题。

2．图解法适⽤于含有两个变量的线性规划问题。

3．线性规划问题的可⾏解是指满⾜所有约束条件的解。

4．在线性规划问题的基本解中，所有的⾮基变量等于零。

5．在线性规划问题中，基可⾏解的⾮零分量所对应的列向量线性⽆关6．若线性规划问题有最优解，则最优解⼀定可以在可⾏域的顶点（极点）达到。

7．线性规划问题有可⾏解，则必有基可⾏解。

8．如果线性规划问题存在⽬标函数为有限值的最优解，求解时只需在其基可⾏解_的集合中进⾏搜索即可得到最优解。

9．满⾜⾮负条件的基本解称为基本可⾏解。

10．在将线性规划问题的⼀般形式转化为标准形式时，引⼊的松驰数量在⽬标函数中的系数为零。

11．将线性规划模型化成标准形式时，“≤”的约束条件要在不等式左_端加⼊松弛变量。

12．线性规划模型包括决策（可控）变量，约束条件，⽬标函数三个要素。

13．线性规划问题可分为⽬标函数求极⼤值和极⼩_值两类。

14．线性规划问题的标准形式中，约束条件取等式，⽬标函数求极⼤值，⽽所有变量必须⾮负。

15．线性规划问题的基可⾏解与可⾏域顶点的关系是顶点多于基可⾏解16．在⽤图解法求解线性规划问题时，如果取得极值的等值线与可⾏域的⼀段边界重合，则这段边界上的⼀切点都是最优解。

17．求解线性规划问题可能的结果有⽆解，有唯⼀最优解，有⽆穷多个最优解。

18.如果某个约束条件是“≤”情形，若化为标准形式，需要引⼊⼀松弛变量。

19.如果某个变量X j为⾃由变量，则应引进两个⾮负变量X j′,X j〞,同时令X j＝Xj ′－Xj。

20.表达线性规划的简式中⽬标函数为max(min)Z=∑c ij x ij。

21..(2.1 P5))线性规划⼀般表达式中，a ij表⽰该元素位置在i⾏j列。

⼆、单选题1．如果⼀个线性规划问题有n个变量，m个约束⽅程(mA．m个 B．n个 C．Cn m D．Cmn个2．下列图形中阴影部分构成的集合是凸集的是 A3．线性规划模型不包括下列_ D要素。

运筹学的公式运筹学是一门研究较为复杂的决策过程的学科，帮助人们以恰当的方式来决定问题的解决方案。

在决策任务中，运筹学利用一系列数学公式来提供精确的、普适的解决方案，因此常常用于复杂的决策任务中。

运筹学公式被广泛地应用于企业经营、遗传算法、制造调度、医学决策等领域。

下面是一些常用的运筹学公式：1. 优化公式：优化方程用来最大化或最小化目标函数，以获得目标函数的最优解。

通常特别使用极值点最大化或者最小化函数，因而被称为极值问题。

一般常见的优化函数有最小二乘法，最小交叉熵法，梯度矩陣搜索法和斜率方向法。

2. 规划公式：规划方程用于解决有约束条件决策问题，即满足约束条件的前提下，最大化或最小化目标函数。

一般常见的规划问题包括线性规划问题，二次规划问题，非线性规划问题，整数规划问题，多目标规划问题以及混合规划问题。

常见的规划求解方法有单纯形算法，简化模型算法，数值迭代算法，随机最优法等。

3. 模型公式：模型方程用于反映决策任务与现实中的关系，把现实情况抽象成数学问题的过程。

常用的模型方程包括线性模型，非线性模型，决策树模型，数学模型，模糊模型等。

有了模型，可以把决策者的抽象情况，映射为可量化的求解问题。

4. 算法公式：算法方程是用来解决某一具体问题的确定性运算步骤。

通常将算法与运筹学很难分开，因为运筹学依赖于算法来求解抽象的决策问题。

典型的算法方程有梯度下降法，模拟退火法，遗传算法，模糊逻辑推理，贪心算法等。

总的来说，运筹学中的公式都有其特定的应用，是有效决策和求解问题的有力工具。

在寻找最优解之前，必须先设定正确的目标函数，并注意到现实条件。

有了运筹学公式，人们可以以定量的方式评估和比较不同决策问题，更好地为复杂决策任务找到最佳解决方案。

第八章 约束最优化方法无约束优化方法是优化方法中最基本最核心的部分。

但是，在工程实际中，优化问题大都是属于有约束的优化问题，即其设计变量的取值要受到一定的限制，用于求解约束优化问题最优解的方法称为约束最优化方法。

由于约束最优化问题的复杂性，无论是在理论方面的研究，还是实际中的应用都有很大的难度。

目前关于一般的约束最优化问题还没有一种普遍有效的算法。

本书重点介绍几种常用的算法，力求使读者对这类问题的求解思路有一个了解。

8.1 约束优化方法概述一、约束优化问题的类型根据约束条件类型的不同可以分为三种，其数学模型分别如下： 1）等式约束优化问题 考虑问题l1,2,...,j x h t s x f j ==0)(..)(min其中，l 1,2,...,j x h x f j =),(),(为R R n→上的函数。

记为)(fh 问题。

2）不等式约束优化问题 考虑问题m1,2,...,i x g t s x f i =≤0)(..)(min其中，m 1,2,...,i x g x f i =),(),(为R R n→上的函数。

记为)(fg 问题。

3）一般约束优化问题()()()⎩⎨⎧===≤l ,1,2,j x h m ,1,2,i x g t s x f j i L L 00..min其中，l 1,2,...,j m i x h x g x f j i ==;,2,1),(),(),(L 为R R n→上的函数。

记为)(fgh 问题。

二、约束优化方法的分类约束优化方法按求解原理的不同可以分为直接法和间接法两类。

1）直接法只能求解不等式约束优化问题的最优解。

其根本做法是在约束条件所限制的可行域内直接求解目标函数的最优解。

如：约束坐标轮换法、复合形法等。

其基本要点：选取初始点、确定搜索方向及适当步长。

搜索原则：每次产生的迭代点必须满足可行性与适用性两个条件。

可行性：迭代点必须在约束条件所限制的可行域内，即满足m i x g i ,...,2,1,0)(=≤适用性：当前迭代点的目标函数值较前一点的目标函数值是下降的，即满足)()()()1(k k x F x F <+2）间接法该方法可以求解不等式约束优化问题、等式约束优化问题和一般约束优化问题。

运筹学试习题及答案《运筹学》复习试题及答案(一)一、填空题1、线性规划问题是求一个线性目标函数_在一组线性约束条件下的极值问题。

2、图解法适用于含有两个变量的线性规划问题。

3、线性规划问题的可行解是指满足所有约束条件的解。

4、在线性规划问题的基本解中，所有的非基变量等于零。

5、在线性规划问题中，基可行解的非零分量所对应的列向量线性无关6、若线性规划问题有最优解，则最优解一定可以在可行域的顶点(极点)达到。

7、线性规划问题有可行解，则必有基可行解。

8、如果线性规划问题存在目标函数为有限值的最优解，求解时只需在其基可行解_的集合中进行搜索即可得到最优解。

9、满足非负条件的基本解称为基本可行解。

10、在将线性规划问题的一般形式转化为标准形式时，引入的松驰数量在目标函数中的系数为零。

11、将线性规划模型化成标准形式时，“≤”的约束条件要在不等式左_端加入松弛变量。

12、线性规划模型包括决策(可控)变量，约束条件，目标函数三个要素。

13、线性规划问题可分为目标函数求极大值和极小_值两类。

14、线性规划问题的标准形式中，约束条件取等式，目标函数求极大值，而所有变量必须非负。

15、线性规划问题的基可行解与可行域顶点的关系是顶点多于基可行解16、在用图解法求解线性规划问题时，如果取得极值的等值线与可行域的一段边界重合，则这段边界上的一切点都是最优解。

17、求解线性规划问题可能的结果有无解，有唯一最优解，有无穷多个最优解。

18、19、如果某个变量Xj为自由变量，则应引进两个非负变量Xj , Xj,同时令Xj=Xj- Xj。

20、表达线性规划的简式中目标函数为ijij21、、(2、1 P5))线性规划一般表达式中，aij表示该元素位置在二、单选题1、如果一个线性规划问题有n个变量，m个约束方程(m行解的个数最为_C_。

′〞′A、m个B、n个C、CnD、Cm个2、下列图形中阴影部分构成的集合是凸集的是A mn3、线性规划模型不包括下列_ D要素。

运筹学试题及答案大家不妨来看看小编推送的运筹学试题及答案，希望给大家带来帮助！《运筹学》复习试题及答案(一)一、填空题1、线性规划问题是求一个线性目标函数_在一组线性约束条件下的极值问题。

2、图解法适用于含有两个变量的线性规划问题。

3、线性规划问题的可行解是指满足所有约束条件的解。

4、在线性规划问题的基本解中，所有的非基变量等于零。

5、在线性规划问题中，基可行解的非零分量所对应的列向量线性无关6、若线性规划问题有最优解，则最优解一定可以在可行域的顶点(极点)达到。

7、线性规划问题有可行解，则必有基可行解。

8、如果线性规划问题存在目标函数为有限值的最优解，求解时只需在其基可行解_的集合中进行搜索即可得到最优解。

9、满足非负条件的基本解称为基本可行解。

10、在将线性规划问题的一般形式转化为标准形式时，引入的松驰数量在目标函数中的系数为零。

11、将线性规划模型化成标准形式时，“≤”的约束条件要在不等式左_端加入松弛变量。

12、线性规划模型包括决策(可控)变量，约束条件，目标函数三个要素。

13、线性规划问题可分为目标函数求极大值和极小_值两类。

14、线性规划问题的标准形式中，约束条件取等式，目标函数求极大值，而所有变量必须非负。

15、线性规划问题的基可行解与可行域顶点的关系是顶点多于基可行解16、在用图解法求解线性规划问题时，如果取得极值的等值线与可行域的一段边界重合，则这段边界上的一切点都是最优解。

17、求解线性规划问题可能的结果有无解，有唯一最优解，有无穷多个最优解。

18、19、如果某个变量Xj为自由变量，则应引进两个非负变量Xj , Xj,同时令Xj=Xj- Xj。

20、表达线性规划的简式中目标函数为ijij21、、(2、1 P5))线性规划一般表达式中，aij表示该元素位置在二、单选题1、如果一个线性规划问题有n个变量，m个约束方程(m 行解的个数最为_C_。

′〞′A、m个B、n个C、CnD、Cm个2、下列图形中阴影部分构成的集合是凸集的是A mn3、线性规划模型不包括下列_ D要素。

运筹学清华大学第四版答案【篇一：运筹学作业2(清华版第二章部分习题)答案】s=txt>2．1 题（p. 77）写出下列线性规划问题的对偶问题：????（1）?????maxz?2x1?2x2?4x3s.t.x1?3x2?4x3?22x1?x2?3x3?3x1?4x2? 3x3?5x1?0，x2?0,x3无约束；解：根据原—对偶关系表，可得原问题的对偶规划问题为：?maxw?2y1?3y2?5y3?s.t.y1?2y2?y3?2??3y1?y2?4y3?2 ? ?4y1?3y2?3y3?4?y1?0,y2?0,y3?0??mn?minz???cijxij?i?1j?1?n???cijxij?ai,i?1,?,m（2）? j?1?n??cijxij?bj,j?1,?,n?j?1???xij?0,i?1,?,m;j?1,?,n解：根据原—对偶关系表，可得原问题的对偶规划问题为：mn??maxw??aiui??bjvji?1j?1??ui?vj?cij ??i?1,?,m;j?1,?,n???ui无约束，vj无约束2．2判断下列说法是否正确，为什么？（1）如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解；答：错。

因为：若线性规划的原问题存在可行解，且其对偶问题有可行解，则原问题和可行问题都将有最优解。

但，现实中肯定有一些问题是无最优解的，故本题说法不对。

maxz?3x1?x2例如原问题s.t.?x1?x2?1?x2?3??x?0,x?02?1有可行解，但其对偶问题minw?y1?3y2s.t.?3?y1?y2?1?y1??y?0,y?02?1无可行解。

（2）如果线性规划的对偶问题无可行解，则原问题也一定无可行解；答：错，如（1）中的例子。

（3）在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或求极小，原问题可行解的目标函数值一定不超过其对偶问题可行解的目标函数值。

答：错。

正确说法是：在互为对偶的一对原问题与对偶问题中，求极大的问题可行解的目标函数值一定不超过求极小的问题可行解的目标函数值。

运筹学中的线性规划和整数规划运筹学是一门涉及决策分析、优化、模型构建和仿真等知识领域的学科，应用广泛，如供应链管理、交通规划、制造业生产、金融投资等方面。

其中，线性规划和整数规划是运筹学中最为基础和重要的优化技术，被广泛应用于各个领域。

一、线性规划线性规划是一种在一组线性约束条件下，求解线性目标函数极值问题的数学方法。

在生产、运输、选址等问题中，线性规划都有着重要的应用。

其数学模型可以表示为：$\max c^Tx$$s.t. Ax \leq b,x\geq 0$其中$c$为目标函数的向量，$x$为决策变量向量，$A$为约束矩阵，$b$为约束向量，$c^Tx$表示目标函数的值，$\leq$表示小于等于。

如果目标函数和约束都是线性的，则可以通过线性规划的求解方法来确定决策变量的最优值。

线性规划的求解方法一般分为单纯形法和内点法两种方法。

单纯性法是线性规划中最为常用的方法，通过对角线交替调整，逐步从可行解中寻找最优解，收敛速度较快，但是存在不稳定的情况。

内点法是近年来发展起来的用于求解大规模线性规划问题的数值方法，其核心思想是迭代求解一系列线性方程组，每次保持解在可行域内部，直到找到最优解为止。

这种方法对大规模问题求解能力强，使用较多。

二、整数规划整数规划是线性规划的升级版，它要求决策变量必须取整数值。

整数规划在很多实际问题中都有着重要的应用，比如很多生产过程中需要将生产数量取整数，物流路径问题需要选取整数条路径等。

与线性规划不同的是，整数规划是NP难问题，没有一种有效的算法能够完全解决所有的整数规划问题。

因此，通常需要采用分支定界、割平面等方法来求解。

分支定界是一种常用的整数规划求解方法。

它通过将整数规划问题分为多个子问题，依次求解这些子问题并优化当前最优解，以逐步逼近最优解。

割平面法则是在分支定界方法的基础上加入约束条件，使得求解过程更加严格化，最终得到更好的结果。

总的来说，运筹学中线性规划和整数规划是不可或缺的优化工具，我们可以通过理论和实践加深对它们的理解。

《运筹学》试题及答案(代码：8054)一、填空题(本大题共8小题，每空2分，共20分)1．线性规划闯题中，如果在约束条件中出现等式约束，我们通常用增加_人工变量__的方法来产生初始可行基。

2．线性规划模型有三种参数，其名称分别为价值系数、_技术系数__和_限定系数__。

3．原问题的第1个约束方程是“=”型，则对偶问题相应的变量是_无非负约束(或无约束、或自由__变量。

4．求最小生成树问题，常用的方法有：避圈法和 _破圈法__。

5．排队模型M／M／2中的M，M，2分别表示到达时间为__负指数_分布，服务时间服从负指数分布和服务台数为2。

6．如果有两个以上的决策自然条件，但决策人无法估计各自然状态出现的概率，那么这种决策类型称为__不确定__型决策。

7．在风险型决策问题中，我们一般采用__效用曲线_来反映每个人对待风险的态度。

8．目标规划总是求目标函数的_最小__信，且目标函数中没有线性规划中的价值系数，而是在各偏差变量前加上级别不同的_优先因子(或权重)___。

二、单项选择题(本大题共l0小题，每小题3分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

多选无分。

9．使用人工变量法求解极大化线性规划问题时，当所有的检验数在基变量中仍含有非零的人工变量，表明该线性规划问题【 D 】A．有唯一的最优解 B．有无穷多最优解C．为无界解 D．无可行解10．对偶单纯形法解最大化线性规划问题时，每次迭代要求单纯形表中【 D 】A．b列元素不小于零 B．检验数都大于零C．检验数都不小于零 D．检验数都不大于零11．已知某个含10个结点的树图，其中9个结点的次为1，1，3，1，1，1，3，1，3，则另一个结点的次为【 A 】A．3 B．2C．1 D．以上三种情况均有可能12．如果要使目标规划实际实现值不超过目标值。

则相应的偏离变量应满足【 B 】13．在运输方案中出现退化现象，是指数字格的数目【 C 】A．等于 m+n B．等于m+n-1C．小于m+n-1 D．大于m+n-114．关于矩阵对策，下列说法错误的是【 D 】A．矩阵对策的解可以不是唯一的C．矩阵对策中，当局势达到均衡时，任何一方单方面改变自己的策略，都将意味着自己更少的赢得和更大的损失D．矩阵对策的对策值，相当于进行若干次对策后，局中人I的平均赢得或局中人Ⅱ的平均损失值【 A 】A．2 8．—l C．—3 D．116．关于线性规划的原问题和对偶问题，下列说法正确的是【 B 】A．若原问题为元界解，则对偶问题也为无界解B．若原问题无可行解，其对偶问题具有无界解或无可行解c．若原问题存在可行解，其对偶问题必存在可行解D．若原问题存在可行解，其对偶问题无可行解17．下列叙述不属于解决风险决策问题的基本原则的是【 C 】A．最大可能原则 B．渴望水平原则C．最大最小原则 D．期望值最大原则18．下列说法正确的是【 D 】A．线性规划问题的基本解对应可行域的顶点也必是该问题的可行解D．单纯形法解标准的线性规划问题时，按最小比值原则确定换出基变量是为了保证迭代计算后的解仍为基本可行解三、多项选择题(本大题共5小题，每小题2分，共l0分)在每小题列出的四个备选项中至少有两个是符合题目要求的，请将其代码填写在题后的括号内。

一、引言在管理科学，经济学和许多工程、科技问题中，常常需求一个多元函数的最大值或最小值，他们统称为最值问题。

通常我们称实际问题中出现的需求最值的函数为目标函数，该函数的自变量称为决策变量，相应的问题在数学上可称为优化问题，在经济管理科学中非常重要的运筹学。

最值（最优化）问题占有较大比重。

最值问题涉及工业、农业、交通运输、军事、商品经济等诸多方面，与人们的生活息息相关。

二、极值定义如果一个函数在一点的一个邻域内处处都有确定的值，而以该点处的值为最大（小），这函数在该点处的值就是一个极大（小）值。

如果它比邻域内其他各点处的函数值都大（小），它就是一个严格极大（小）。

该点就相应地称为一个极值点或严格极值点。

极值的概念来自数学应用中的最大最小值问题。

定义在一个有界闭区域上的每一个连续函数都必定达到它的最大值和最小值，问题在于要确定它在哪些点处达到最大值或最小值。

如果不是边界点就一定是内点，因而是极值点。

这里的首要任务是求得一个内点成为一个极值点的必要条件。

设函数f（x）在x。

附近有定义，如果对x。

附近的所有的点都有f（x）<f（x。

），则f（x。

）是函数f（x）的一个极大值。

如果附近的所有的点，都有f（x）>f（x。

），则f （x）。

是函数f（x）的一个极小值，极大值与极小值统称为极值。

三、多元函数1、多元函数的定义设D为一个非空的n 元有序数组的集合，f为某一确定的对应规则。

若对于每一个有序数组（x1,x2,…,xn）∈D，通过对应规则f，都有唯一确定的实数y与之对应，则称对应规则f为定义在D上的n元函数。

记为y=f （x1,x2,…,xn），（x1,x2,…,xn）∈D 。

变量x1,x2,…,xn称为自变量；y称为因变量。

（xi,其中i是下标。

下同）当n＝1时，为一元函数，记为y=f(x),x∈D;当n＝2时，为二元函数，记为z=f(x,y),(x,y)∈D.二元及以上的函数统称为多元函数。