什么是线性规划问题,及有那些相关概念?如何解决

什么是线性规划问题,及有那些相关概念?如何解决
什么是线性规划问题,及有那些相关概念?如何解决

什么是线性规划问题,及有那些相关概念?如何解决
线性规划问题的数学模型的一般形式　　（1）列出约束条件及目标函数
　　（2）画出约束条件所表示的可行域
　　（3）在可行域内求目标函数的最优解 [编辑本段]线性规划的发展　　法国数学家 J.- B.- J.傅里叶和 C.瓦莱－普森分别于1832和1911年独立地提出线性规划的想法,但未引起注意.
　　1939年苏联数学家Л.В.康托罗维奇在《生产组织与计划中的数学方法》一书中提出线性规划问题,也未引起重视.
　　1947年美国数学家G.B.丹齐克提出线性规划的一般数学模型和求解线性规划问题的通用方法──单纯形法,为这门学科奠定了基础.
　　1947年美国数学家J.von诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域,扩大了它的应用范围和解题能力.
　　1951年美国经济学家T.C.库普曼斯把线性规划应用到经济领域,为此与康托罗维奇一起获1975年诺贝尔经济学奖.
　　50年代后对线性规划进行大量的理论研究,并涌现出一大批新的算法.例如,1954年C.莱姆基提出对偶单纯形法,1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题,1956年A.塔克提出互补松弛定理,1960年G.B.丹齐克和P.沃尔夫提出分解算法等.
　　线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究.由于数字电子计算机的发展,出现了许多线性规划软件,如MPSX,OPHEIE,UMPIRE等,可以很方便地求解几千个变量的线性规划问题.
　　1979年苏联数学家L. G. Khachian提出解线性规划问题的椭球算法,并证明它是多项式时间算法.
　　1984年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划问题的新的多项式时间算法.用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50.现已形成线性规划多项式算法理论.50年代后线性规划的应用范围不断扩大. 建立线性规划模型的方法 [编辑本段]线性规划的模型建立　　从实际问题中建立数学模型一般有以下三个步骤；
　　1.根据影响所要达到目的的因素找到决策变量；
　　2.由决策变量和所在达到目的之间的函数关系确定目标函数；
　　3.由决策变量所受的限制条件确定决策变量所要满足的约束条件.
　　所建立的数学模型具有以下特点：
　　1、每个模型都有若干个决策变量（x1,x2,x3……,xn）,其中n为决策变量个数.决策变量的一组值表示一种方案,同时决策变量一般式非负的.
　　2、目标函数是决策变量的线性函数,根据具体问题可以是最大化（max）或最小化（min）,二者统称为最优化（opt）.
　　3、约束条件也是决策变量的线性函数.
　　当我们得到的数学模型的目标函数为线性函数,约束条件为线性等式或不等式时称此数学模型为线性规划模型.
　　例：
　　生产安排模型：某工厂要安排生产Ⅰ、Ⅱ两种产品,已知生产单位产品所需的设备台时及A、B两种原材料的消耗,如表所示,表中右边一列是每日设备能力及原材料供应的限量,该工厂生产一单位产品Ⅰ可获利2元,生产一单位产品Ⅱ可获利3元,问应如何安排生产,使其获得最多?
　　
　　1、确定决策变量：设x1、x2为产品Ⅰ、Ⅱ的生产数量；
　　2、明确目标函数：获利最大,即求2x1+3x2最大值；
　　3、所满足的约束条件：
　　设备限制：x1+2x2≤8
　　原材料A限制：4x1≤16
　　原材料B限制：4x2≤12
　　基本要求：x1,x2≥0
　　用max代替最大值,s.t.（subject to 的简写）代替约束条件,则该模型可记为：
　　max z=2x1+3x2
　　s.t. x1+2x2≤8
　　4x1≤16
　　4x2≤12
　　x1,x2≥0 [编辑本段]线性规划的解法　　求解线性规划问题的基本方法是单纯形法,现在已有单纯形法的标准软件,可在电子计算机上求解约束条件和决策变量数达 10000个以上的线性规划问题.为了提高解题速度,又有改进单纯形法、对偶单纯形法、原始对偶方法、分解算法和各种多项式时间算法.对于只有两个变量的简单的线性规划问题,也可采用图解法求解.这种方法仅适用于只有两个变量的线性规划问题.它的特点是直观而易于理解,但实用价值不大.通过图解法求解可以理解线性规划的一些基本概念.
　　对于一般线性规划问题：
　　Min z=CX
　　S.T.
　　AX =b
　　X>=0
　　其中A为一个m*n矩阵.
　　若A行满秩
　　则可以找到基矩阵B,并寻找初始基解.
　　用N表示对应于B的非基矩阵.则规划问题1可化为：
　　规划问题2：
　　Min z=CB XB+CNXN
　　S.T.
　　B XB+N XN = b (1)
　　XB >= 0, XN >= 0 (2)
　　(1)两边同乘于B-1,得
　　XB + B-1 N XN = B-1 b
　　同时,由上式得XB = B-1 b - B-1 N XN,也代入目标函数,问题可以继续化为：
　　规划问题3：
　　Min z=CB B-1 b + ( CN - CB B-1 N ) XN
　　S.T.
　　XB+B-1N XN = B-1 b (1)
　　XB >= 0, XN >= 0 (2)
　　令N:=B-1N,b:= B-1 b,ζ= CB B-1b,σ= CN - CB B-1 N,则上述问题化为规划问题形式4：
　　Min z= ζ + σ XN
　　S.T.
　　XB+ N XN = b (1)
　　XB >= 0, XN >= 0 (2)
　　在上述变换中,若能找到规划问题形式4,使得b>=0,称该形式为初始基解形式.
　　上述的变换相当于对整个扩展矩阵（包含C及A） 乘以增广矩阵 .所以重在选择B,从而找出对应的CB.
　　若存在初始基解
　　若σ>= 0
　　则z >=ζ.同时,令XN = 0,XB = b,这是一个可行解,且此时z=ζ,即达到最优值.所以,此时可以得到最优解.
　　若σ >= 0不成立
　　可以采用单纯形表变换.
　　σ中存在分量0.
　　l βq+βi*(-aq,j/ai,j)>=0,其中q!=i.即βq>=βi/ ai,j * aq,j.
　　n 若aq,j0,则需要βq / aq,j >=βi/ ai,j.因此,要选择i使得βi/ ai,j最小.
　　如果这种方法确定了多个下标,选择下标最小的一个.
　　转换后得到规划问题4的形式,继续对σ进行判断.由于基解是有限个,因此,一定可以在有限步跳出该循环.
　　若对于每一个i,ai,j

1.线性规划问题就是：线性目标函数在线性等式或线性不等式约束条件下的极值问题。
2.相关概念：可行解（满足约束条件的解），最优解（满足约束条件同时使目标函数取极值的解）；凸集论；优化理论，等等
3搜索法；单纯型法，内点法等等 ，已有众多的软件可解决线性规划问题。...

全部展开

1.线性规划问题就是：线性目标函数在线性等式或线性不等式约束条件下的极值问题。
2.相关概念：可行解（满足约束条件的解），最优解（满足约束条件同时使目标函数取极值的解）；凸集论；优化理论，等等
3搜索法；单纯型法，内点法等等 ，已有众多的软件可解决线性规划问题。

收起

线性规划问题的数学模型的一般形式　　（1）列出约束条件及目标函数
　　（2）画出约束条件所表示的可行域
　　（3）在可行域内求目标函数的最优解 [编辑本段]线性规划的发展　　法国数学家 J.- B.- J.傅里叶和 C.瓦莱－普森分别于1832和1911年独立地提出线性规划的想法，但未引起注意。
　　1939年苏联数学家Л.В.康托罗维奇在《生产组织与计划中的数学方法》一...

全部展开

线性规划问题的数学模型的一般形式　　（1）列出约束条件及目标函数
　　（2）画出约束条件所表示的可行域
　　（3）在可行域内求目标函数的最优解 [编辑本段]线性规划的发展　　法国数学家 J.- B.- J.傅里叶和 C.瓦莱－普森分别于1832和1911年独立地提出线性规划的想法，但未引起注意。
　　1939年苏联数学家Л.В.康托罗维奇在《生产组织与计划中的数学方法》一书中提出线性规划问题，也未引起重视。
　　1947年美国数学家G.B.丹齐克提出线性规划的一般数学模型和求解线性规划问题的通用方法──单纯形法，为这门学科奠定了基础。
　　1947年美国数学家J.von诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力。
　　1951年美国经济学家T.C.库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一起获1975年诺贝尔经济学奖。
　　50年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法。例如，1954年C.莱姆基提出对偶单纯形法，1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题，1956年A.塔克提出互补松弛定理，1960年G.B.丹齐克和P.沃尔夫提出分解算法等。
　　线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究。由于数字电子计算机的发展，出现了许多线性规划软件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解几千个变量的线性规划问题。
　　1979年苏联数学家L. G. Khachian提出解线性规划问题的椭球算法，并证明它是多项式时间算法。
　　1984年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划问题的新的多项式时间算法。用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。现已形成线性规划多项式算法理论。50年代后线性规划的应用范围不断扩大。 建立线性规划模型的方法 [编辑本段]线性规划的模型建立　　从实际问题中建立数学模型一般有以下三个步骤；
　　1.根据影响所要达到目的的因素找到决策变量；
　　2.由决策变量和所在达到目的之间的函数关系确定目标函数；
　　3.由决策变量所受的限制条件确定决策变量所要满足的约束条件。
　　所建立的数学模型具有以下特点：
　　1、每个模型都有若干个决策变量（x1,x2,x3……，xn），其中n为决策变量个数。决策变量的一组值表示一种方案，同时决策变量一般式非负的。
　　2、目标函数是决策变量的线性函数，根据具体问题可以是最大化（max）或最小化（min），二者统称为最优化（opt）。
　　3、约束条件也是决策变量的线性函数。
　　当我们得到的数学模型的目标函数为线性函数，约束条件为线性等式或不等式时称此数学模型为线性规划模型。
　　例：
　　生产安排模型：某工厂要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表所示，表中右边一列是每日设备能力及原材料供应的限量，该工厂生产一单位产品Ⅰ可获利2元，生产一单位产品Ⅱ可获利3元，问应如何安排生产，使其获得最多？
　　
　　1、确定决策变量：设x1、x2为产品Ⅰ、Ⅱ的生产数量；
　　2、明确目标函数：获利最大，即求2x1+3x2最大值；
　　3、所满足的约束条件：
　　设备限制：x1+2x2≤8
　　原材料A限制：4x1≤16
　　原材料B限制：4x2≤12
　　基本要求：x1,x2≥0
　　用max代替最大值，s.t.（subject to 的简写）代替约束条件，则该模型可记为：
　　max z=2x1+3x2
　　s.t. x1+2x2≤8
　　4x1≤16
　　4x2≤12
　　x1,x2≥0 [编辑本段]线性规划的解法　　求解线性规划问题的基本方法是单纯形法，现在已有单纯形法的标准软件，可在电子计算机上求解约束条件和决策变量数达 10000个以上的线性规划问题。为了提高解题速度，又有改进单纯形法、对偶单纯形法、原始对偶方法、分解算法和各种多项式时间算法。对于只有两个变量的简单的线性规划问题，也可采用图解法求解。这种方法仅适用于只有两个变量的线性规划问题。它的特点是直观而易于理解，但实用价值不大。通过图解法求解可以理解线性规划的一些基本概念。
　　对于一般线性规划问题：
　　Min z=CX
　　S.T.
　　AX =b
　　X>=0
　　其中A为一个m*n矩阵。
　　若A行满秩
　　则可以找到基矩阵B，并寻找初始基解。
　　用N表示对应于B的非基矩阵。则规划问题1可化为：
　　规划问题2：
　　Min z=CB XB+CNXN
　　S.T.
　　B XB+N XN = b (1)
　　XB >= 0, XN >= 0 (2)
　　(1)两边同乘于B-1，得
　　XB + B-1 N XN = B-1 b
　　同时，由上式得XB = B-1 b - B-1 N XN，也代入目标函数，问题可以继续化为：
　　规划问题3：
　　Min z=CB B-1 b + ( CN - CB B-1 N ) XN
　　S.T.
　　XB+B-1N XN = B-1 b (1)
　　XB >= 0, XN >= 0 (2)
　　令N:=B-1N，b:= B-1 b，ζ= CB B-1b，σ= CN - CB B-1 N，则上述问题化为规划问题形式4：
　　Min z= ζ + σ XN
　　S.T.
　　XB+ N XN = b (1)
　　XB >= 0, XN >= 0 (2)
　　在上述变换中，若能找到规划问题形式4，使得b>=0，称该形式为初始基解形式。
　　上述的变换相当于对整个扩展矩阵（包含C及A） 乘以增广矩阵 。所以重在选择B，从而找出对应的CB。
　　若存在初始基解
　　若σ>= 0
　　则z >=ζ。同时，令XN = 0，XB = b，这是一个可行解，且此时z=ζ，即达到最优值。所以，此时可以得到最优解。
　　若σ >= 0不成立
　　可以采用单纯形表变换。
　　σ中存在分量<0。这些负分量对应的决策变量编号中，最小的为j。N中与j对应的列向量为Pj。
　　若Pj <=0不成立
　　则Pj至少存在一个分量ai，j为正。在规划问题4的约束条件（1）的两边乘以矩阵T。
　　T=
　　则变换后，决策变量xj成为基变量，替换掉原来的那个基变量。为使得T b >= 0，且T Pj=ei（其中，ei表示第i个单位向量），需要：
　　l ai，j>0。
　　l βq+βi*(-aq,j/ai,j)>=0，其中q!=i。即βq>=βi/ ai,j * aq,j。
　　n 若aq,j<=0，上式一定成立。
　　n 若aq,j>0，则需要βq / aq,j >=βi/ ai,j。因此，要选择i使得βi/ ai,j最小。
　　如果这种方法确定了多个下标，选择下标最小的一个。
　　转换后得到规划问题4的形式，继续对σ进行判断。由于基解是有限个，因此，一定可以在有限步跳出该循环。
　　若对于每一个i，ai,j<=0
　　最优值无界。
　　若不能寻找到初始基解
　　无解。
　　若A不是行满秩
　　化简直到A行满秩，转到若A行满秩。 [编辑本段]线性规划的应用　　在企业的各项管理活动中,例如计划、生产、运输、技术等问题,线性规划是指从各种限制条件的组合中,选择出最为合理的计算方法,建立线性规划模型从而求得最佳结果

收起