10,471
次編輯
變更
线性规划
,無編輯摘要
{| 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|
|}
线性规划是运筹学的一个重要分支，广泛应用于[[军事作战]]、[[经济分析]]、[[经营管理]]和[[工程技术]]等方面。为合理地利用有限的人力、物力、财力等资源作出的最优决策，提供科学的依据。
==线性规划简介==
===数学模型===
（2）画出约束条件所表示的可行域
（3）在可行域内求目标函数的最优解及最优值<ref>[外链网址 网页标题]，外链网站</ref>
==标准型==
和非负变量：
其它类型的问题，例如极小化问题，不同形式的约束问题，和有负变量的问题，都可以改写成其等价问题的标准型。<ref>[外链网址 网页标题]，外链网站</ref>
==模型建立==
===从实际问题中建立数学模型一般有以下三个步骤：===
===所建立的数学模型具有以下特点：===
1、每个模型都有若干个 [[ 决策变量 ]] （x1，x2，x3……，xn），其中n为决策变量个数。决策变量的一组值表示一种 [[ 方案 ]] ，同时决策变量一般是非负的。
2、目标函数是决策变量的 [[ 线性函数 ]] ，根据具体问题可以是最大化（max）或最小化（min），二者统称为最优化（opt）。
3、约束条件也是决策变量的线性函数。
当我们得到的 [[ 数学模型 ]] 的目标函数为线性函数，约束条件为线性等式或 [[ 不等式 ]] 时称此数学模型为线性规划模型。 例：
===例：===
生产安排模型：某工厂要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表所示，表中右边一列是每日设备能力及原材料供应的限量，该工厂生产一单位产品Ⅰ可获利2元，生产一单位产品Ⅱ可获利3元，问应如何安排生产，使其获利最多？
解：
1、确定决策变量：设x1、x2分别为产品Ⅰ、Ⅱ的生产数量；
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:997 319 智力遊戲應用數學；機率]]