導覽
近期變更
隨機頁面
新手上路
新頁面
優質條目評選
繁體
不转换
简体
繁體
3.144.23.143
登入
工具
閱讀
檢視原始碼
特殊頁面
頁面資訊
求真百科歡迎當事人提供第一手真實資料,洗刷冤屈,終結網路霸凌。
檢視 线性规划 的原始碼
←
线性规划
前往:
導覽
、
搜尋
由於下列原因,您沒有權限進行 編輯此頁面 的動作:
您請求的操作只有這個群組的使用者能使用:
用戶
您可以檢視並複製此頁面的原始碼。
{| class="wikitable" align="right" |- | style="background: #E6C3C3" align= center| '''<big>线性规划</big>''' |- |<center><img src=https://txt22263.book118.com/2017/0514/book106701/106700859.jpg width="300"></center> <small>[https://max.book118.com/html/2017/0514/106700859.shtm 来自 原创力文档 的图片]</small> |- | style="background: #E6C3C3" align= center| '''<big></big>''' |- | align= light| 中文名:线性规划 外文名:linear programming 所属学科:运筹学 研究内容:线性最优化问题 |} '''线性规划'''(Linear programming,简称LP),是[[运筹学]]中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,是辅助人们进行[[科学管理]]的一种[[数学方法]],是研究[[线性约束条件]]下[[线性目标函数]]的[[极值问题]]的数学理论和方法。 线性规划是运筹学的一个重要分支,广泛应用于[[军事作战]]、[[经济分析]]、[[经营管理]]和[[工程技术]]等方面。为合理地利用有限的人力、物力、财力等资源作出的最优决策,提供科学的依据。 ==线性规划简介== ===数学模型=== (1)列出约束条件及目标函数 (2)画出约束条件所表示的可行域 (3)在可行域内求目标函数的最优解及最优值 ==标准型== 描述线性规划问题的常用和最直观形式是标准型。标准型包括以下三个部分: 一个需要极大化的线性函数: 以下形式的问题约束: 和非负变量: 其它类型的问题,例如极小化问题,不同形式的约束问题,和有负变量的问题,都可以改写成其等价问题的标准型。 ==模型建立== ===从实际问题中建立数学模型一般有以下三个步骤:=== 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个以上的线性规划问题。为了提高解题速度,又有改进单纯形法、[[对偶单纯形法]]、[[原始对偶方法]]、[[分解算法]]和各种多项式时间算法。对于只有两个变量的简单的线性规划问题,也可采用[[图解法]]求解。这种方法仅适用于只有两个变量的线性规划问题。它的特点是直观而易于理解,但实用价值不大。通过图解法求解可以理解线性规划的一些基本概念。 ==发展== 法国数学家J.- B.- J.[[傅里叶]]和C.[[瓦莱-普森]]分别于1832和1911年独立地提出线性规划的想法,但未引起注意。 1939年[[苏联]]数学家Л.В.[[康托罗维奇]]在《生产组织与计划中的数学方法》一书中提出线性规划问题,也未引起重视。<ref>[https://zhuanlan.zhihu.com/p/509030805 线性规划简介],知乎</ref> 1947年[[美国]]数学家G.B.Dantzing提出求解线性规划的单纯形法,为这门学科奠定了基础。 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年代后线性规划的应用范围不断扩大。 建立线性规划模型的方法 ==应用== 在企业的各项管理活动中,例如计划、生产、运输、技术等问题,线性规划是指从各种限制条件的组合中,选择出最为合理的计算方法,建立线性规划模型从而求得最佳结果。 ==视频== <center> ===线性规划问题=== {{#iDisplay:f335717c81s|640|360|qq}} </center> ==参考资料== [[Category:319 應用數學;機率]]
返回「
线性规划
」頁面