查看“︁线性规划”︁的源代码

{{NoteTA
|G1=Math
}}
[[File:Linear optimization in a 2-dimensional polytope.svg|thumb|一个简单的二元线性规划问题的图示表示。其中包含六个不等式约束，可行解集用黄色表示，形成了一个[[多边形]]，即二维[[多胞形]]。线性目标函数的最优解位于红线与多边形的交点处。这条红线是目标函数的[[水平集|等值线]]，箭头指示了优化的方向。]]
[[File:3dpoly.svg|thumb|right|一个具有三个变量的问题的闭合可行域是一个凸[[多面体]]。目标函数的固定值所形成的表面是[[平面 (数学)|平面]]（图中未显示）。线性规划问题就是要在这个多面体上找到一个点，使其位于具有最高可能值的平面上。]]

'''线性规划'''（{{lang-en|Linear Programming}}，简称LP）是一种数学方法，通过线性方程或不等式描述问题的约束条件和目标，以实现最佳结果（例如利润最大化或成本最小化）。作为[[最优化]]的一种特例，线性规划在许多领域都有重要应用。

更严谨地说，线性规划旨在优化一个[[線性關係|线性]][[损失函数|目标函数]]，该函数需满足一定的[[一次方程|线性等式]]和不等式[[約束 (數學)|约束]]。其解的[[可行域]]是一个[[凸多胞形]]，这一区域由若干线性不等式描述的有限半空间的交集定义。目标函数本质上是定义在这一凸多面体上的[[实数|实值]][[仿射变换|仿射函数]]。通过线性规划[[算法]]，可以在[[多胞形]]内找到目标函数的最大值或最小值（若解存在）。

线性规划问题通常用[[规范形|标准型]]表达为：
:<math> \begin{align}
& \text{Find a vector} && \mathbf{x} \\
& \text{that maximizes}   && \mathbf{c}^\mathsf{T} \mathbf{x}\\
& \text{subject to} && A \mathbf{x} \le \mathbf{b} \\
& \text{and} && \mathbf{x} \ge \mathbf{0}.
\end{align} </math>
其中，<math>\mathbf{x}</math>是待求解的变量向量，<math>\mathbf{c}</math>和<math>\mathbf{b}</math>是已知向量，<math>A</math>是已知[[矩阵]]。需要最大化的<math>\mathbf x\mapsto\mathbf{c}^\mathsf{T}\mathbf{x}</math>被称为[[损失函数|目标函数]]，而约束条件<math>A \mathbf{x} \le \mathbf{b}</math>和<math>\mathbf{x} \geq \mathbf{0}</math>定义了目标函数优化范围内的[[凸多胞形|凸多面体]]。

线性规划的应用覆盖多个领域。它在数学研究中尤为常见，同时也在商业、[[经济学]]以及某些工程问题中具有重要价值。线性规划与特征方程、[[约翰·冯诺伊曼|冯·诺依曼]]的总体均衡模型及结构均衡模型紧密相关（详见[[對偶線性規劃]]）。<ref>{{cite journal |last=von Neumann |first=J. |year=1945 |title=A Model of General Economic Equilibrium |journal=The Review of Economic Studies |volume=13 |pages=1-9}}</ref>
<ref>{{Cite journal
| last1 = Kemeny
| first1 = J. G.
| last2 = Morgenstern
| first2 = O.
| last3 = Thompson
| first3 = G. L.
| year = 1956
| title = A Generalization of the von Neumann Model of an Expanding Economy
| url = https://archive.org/details/sim_econometrica_1956-04_24_2/page/n4
| journal = Econometrica
| volume = 24
| pages = 115–135
}}</ref>
<ref>{{Cite book
| author = 李武
| title = 一般均衡与结构动态研究：新结构经济学视角
| year = 2019
| publisher = 经济科学出版社
| location = 北京
| isbn = 978-7-5218-0422-5
| pages = 122 - 125
}}</ref>
目前，运输、能源、电信和制造业等行业广泛使用线性规划模型。通过这种方法，可以高效解决规划、[[路由]]、日程安排、[[任务分配问题|任务分配]]和设计等各类复杂问题，为实际应用提供精确的数学支持。

== 历史 ==
[[File:Leonid Kantorovich 1975.jpg|thumb|[[列昂尼德·坎托罗维奇]]]]
[[File:JohnvonNeumann-LosAlamos.gif|thumb|[[约翰·冯诺伊曼]]]]

线性不等式组求解问题可追溯到[[约瑟夫·傅里叶|傅里叶]]的时期，他于1827年发表了一种求解方法，<ref name="SierksmaZwols2015">{{cite book|author1=Gerard Sierksma|author2=Yori Zwols|title=Linear and Integer Optimization: Theory and Practice|edition=3rd|year=2015|publisher=CRC Press|isbn=978-1498710169|page=1}}</ref> 这一方法后来被称为{{le|傅里叶-莫茨金消元法|Fourier–Motzkin elimination}}。

20世纪30年代末期，苏联数学家[[列昂尼德·坎托罗维奇|康托罗维奇]]和美国经济学家[[瓦西里·列昂季耶夫|列昂惕夫]]各自独立开展了线性规划的应用研究。康托罗维奇致力于解决生产调度问题，列昂惕夫则专注于经济领域的应用。然而，他们的开创性成果在相当长的时期内并未受到应有的重视。

二战期间，线性规划迎来了重大转机。这一数学工具在应对战时各种复杂挑战时展现出独特优势，特别是在运输物流、任务调度和资源分配等方面。考虑到成本和资源限制等现实约束条件，线性规划在优化这些环节时发挥了不可替代的作用。

正是战时的显著成效让线性规划逐渐受到广泛关注。二战结束后，这一方法获得了学界普遍认可，并在运筹学、经济学等诸多领域奠定了基础性地位。康托罗维奇和列昂惕夫在30年代末期提出的理论贡献，最终成为线性规划在决策优化领域广泛应用的重要基石。<ref>{{Cite web |title=Linear programming {{!}} Definition & Facts {{!}} Britannica |url=https://www.britannica.com/science/linear-programming-mathematics |access-date=2023-11-20 |website=www.britannica.com |language=en}}</ref>

康托罗维奇的研究成果起初在[[苏联]]并未得到重视。<ref name="dantzig1982">{{cite journal|url = https://apps.dtic.mil/sti/pdfs/ADA112060.pdf|archive-url = https://web.archive.org/web/20150520183722/http://www.dtic.mil/cgi-bin/GetTRDoc?Location=U2&doc=GetTRDoc.pdf&AD=ADA112060|url-status = live|archive-date = May 20, 2015|title = Reminiscences about the origins of linear programming|author=George B. Dantzig|date = April 1982|journal = Operations Research Letters|volume = 1|issue = 2|pages = 43–48|doi = 10.1016/0167-6377(82)90043-8}}</ref> 同一时期，美籍荷兰经济学家[[佳林·库普曼斯|库普曼斯]]开始用线性规划方法处理经典经济问题。两位学者后来共同获得了1975年[[诺贝尔经济学奖]]。<ref name="SierksmaZwols2015" /> 1941年，希区柯克（Frank Lauren Hitchcock）将运输问题也纳入线性规划框架，提出了一种与后来的[[单纯形法]]极为相似的解法。<ref name="Schrijver1998">{{cite book |author=Alexander Schrijver |title=Theory of Linear and Integer Programming |publisher=John Wiley & Sons |year=1998 |isbn=978-0-471-98232-6 |pages=221–222}}</ref> 可惜希区柯克于1957年去世，而诺贝尔奖是不能追授的。

1946年至1947年间，[[喬治·伯納德·丹齊格|丹齐格]]独立开发了通用线性规划方法，用于解决美国空军的规划难题。<ref name=":0">{{Cite book|title=Linear programming|last1=Dantzig|first1=George B.|last2=Thapa|first2=Mukund Narain|date=1997|publisher=Springer|isbn=0387948333|location=New York|page=xxvii|oclc=35318475}}</ref> 1947年，他发明了[[单纯形法]]，这是首个能够高效解决大多数线性规划问题的方法。<ref name=":0" /> 当丹齐格与[[约翰·冯诺伊曼|冯·诺伊曼]]会面讨论单纯形法时，后者敏锐地发现这一理论与其正在研究的[[博弈论]]问题本质上是等价的，由此提出了对偶理论。<ref name=":0" /> 丹齐格在1948年1月5日完成的未发表报告《线性不等式定理》（A Theorem on Linear Inequalities）中对此作出了严格证明。<ref name="dantzig1982"/> 他的研究成果于1951年正式发表，此后在战后各行业的日常规划中得到广泛应用。

丹齐格最初研究的是一个70人对应70个岗位的最优分配问题。若要穷举所有可能的排列组合来寻找最佳方案，所需的计算量是天文数字，甚至超过了[[可觀測宇宙]]中的[[化學元素豐度|粒子总数]]。然而，将这一问题转化为线性规划模型并使用[[单纯形法]]，却能在很短时间内求得最优解。这得益于线性规划理论大幅降低了需要检验的可行解数量。

1979年，哈奇扬（Leonid Khachiyan）首次证明了线性规划问题可在多项式时间内求解。<ref name = "khachiyan79">{{cite journal|title = A Polynomial Algorithm for Linear Programming|author = Leonid Khachiyan|date = 1979|journal = Doklady Akademii Nauk SSSR|volume=224|issue=5|pages=1093–1096}}</ref> 而该领域更具突破性的理论与实践进展出现在1984年，当时卡马卡（Narendra Karmarkar）提出了求解线性规划的新型[[内点法]]。<ref name = "karmarkar84" >{{cite journal|title = A New Polynomial-Time Algorithm for Linear Programming|author = Narendra Karmarkar|date = 1984|journal = Combinatorica|volume=4|issue = 4|pages=373–395|doi = 10.1007/BF02579150|s2cid = 7257867}}</ref>

== 用途 ==
线性规划作为一个被广泛应用的优化领域，这绝非偶然。[[運籌學]]中大量的实际问题都可以转化为线性规划问题。<ref name="dantzig1982"/> 在线性规划领域，'''网络流问题'''和[[多物網絡流問題|多商品流问题]]等特殊案例因其重要性而催生了大量针对性的算法研究。许多其他类型的优化算法也往往通过解决线性规划的子问题来实现其目标。从发展历程来看，线性规划孕育了优化理论中的诸多核心理念，包括'''对偶性'''、'''分解'''，以及'''凸性'''及其推广的重要性等。线性规划不仅在[[微观经济学]]的创立期发挥了重要作用，如今在企业管理中仍然扮演着关键角色，广泛应用于规划、生产、运输和技术等领域。虽然现代企业面临的管理挑战日新月异，但在有限资源条件下实现[[利润最大化]]和成本最小化始终是企业追求的目标。值得一提的是，谷歌也将线性规划应用于YouTube视频的稳定性优化。<ref>{{cite book |author1=M. Grundmann |author2=V. Kwatra |author3=I. Essa |title=CVPR 2011 |chapter=Auto-directed video stabilization with robust L1 optimal camera paths |date=2011 |pages=225–232 |doi=10.1109/CVPR.2011.5995525 |isbn=978-1-4577-0394-2 |s2cid=17707171 |url=https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/37041.pdf |language=English}}</ref>

== 标准型 ==
'''标准型'''是描述线性规划问题时最常用、最直观的形式。其由以下三个部分组成：
* '''需要最大化的线性（或仿射）目标函数'''
: e.g. <math> f(x_{1},x_{2}) = c_1 x_1 + c_2 x_2</math>
* '''问题约束条件'''，形式如下：
: e.g.
:: <math>\begin{matrix}
  a_{11} x_1 + a_{12} x_2 &\leq b_1 \\
  a_{21} x_1 + a_{22} x_2 &\leq b_2 \\
  a_{31} x_1 + a_{32} x_2 &\leq b_3 \\
\end{matrix}</math>
* '''非负变量'''
: e.g.
:: <math>\begin{matrix}
 x_1 \geq 0 \\
 x_2 \geq 0
\end{matrix}</math>

问题通常以'''[[矩阵]]形式'''表达，形式如下：
: <math>\max \{\, \mathbf{c}^\mathsf{T} \mathbf{x} \mid \mathbf{x}\in\mathbb{R}^n\land A \mathbf{x} \leq \mathbf{b} \land \mathbf{x} \geq 0 \,\}</math>

其他形式，例如最小化问题、包含其他形式约束条件的问题以及涉及负变量的问题，均可以重写为等价的标准型问题。

=== 示例 ===
[[File:linear_programming_feasible_region_farmer_example.svg|thumb|农夫例子的图形解法——在标出违反条件的区域后，无阴影区域中距离原点最远的顶点（与虚线相交）给出了最优组合（该点位于土地和农药线上，说明收入受到土地和农药的限制，而不是化肥的限制）。]]
假设一位农民有一片面积为 ''L'' [[公顷]]的农田，可以种植小麦或大麦，或者两者的组合。农民拥有 ''F'' 千克的肥料和 ''P'' 千克的农药。每公顷小麦需要 ''F''<sub>1</sub> 千克肥料和 ''P''<sub>1</sub> 千克农药，而每公顷大麦需要 ''F''<sub>2</sub> 千克肥料和 ''P''<sub>2</sub> 千克农药。设 S<sub>1</sub> 和 S<sub>2</sub> 分别为每公顷小麦和大麦的售价。如果用 ''x''<sub>1</sub> 和 ''x''<sub>2</sub> 分别表示种植小麦和大麦的面积，则通过选择 ''x''<sub>1</sub> 和 ''x''<sub>2</sub> 的最佳值可以实现利润最大化。这个问题可以表示为以下标准型的线性规划问题：
{|
|-
| valign="top"|max:
| valign="top"|<math>S_1\cdot x_1+S_2\cdot x_2</math>
| （最大化收益，即小麦总销售额加大麦总销售额，收益是“目标函数”）
|-
| {{nowrap|s.t.}}
| <math>x_1 + x_2\leq L</math>
| （总面积限制）
|-
|
| <math>F_1\cdot x_1+F_2\cdot x_2\leq F</math>
| （肥料限制）
|-
|
| <math>P_1\cdot x_1 + P_2\cdot x_2\leq P</math>
| （农药限制）
|-
|
| <math>x_1\geq 0, x_2\geq 0</math>
| （种植面积不能为负）
|}

矩阵形式表示为：
: max <math>\begin{bmatrix} S_1 & S_2 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} </math>
: s.t. <math>\begin{bmatrix} 1 & 1 \\ F_1 & F_2 \\ P_1 & P_2 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \le \begin{bmatrix} L \\ F \\ P \end{bmatrix}, \, \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \ge \begin{bmatrix} 0 \\ 0 \end{bmatrix}. </math>

== 增广型（松弛型） ==
线性规划问题可以转换为'''增广型'''，以便使用[[单纯形法]]的通用形式求解。这种形式引入非负的松弛变量（slack variable），将约束中的不等式转化为等式。此时问题可以用以下[[分塊矩陣]]形式表示：
: max <math>z</math>：
: <math>
  \begin{bmatrix}
    1 & -\mathbf{c}^\mathsf{T} & 0 \\
    0 & \mathbf{A} & \mathbf{I}
  \end{bmatrix}
  \begin{bmatrix}
    z \\ \mathbf{x} \\ \mathbf{s}
  \end{bmatrix} =
  \begin{bmatrix}
    0 \\ \mathbf{b}
  \end{bmatrix}
</math>
:<math>\mathbf{x} \ge  0, \mathbf{s} \ge 0</math>
其中，<math>\mathbf{s}</math>是新引入的松弛变量，<math>\mathbf{x}</math>是决策变量，<math>z</math>是需要最大化的变量。

=== 示例 ===
上述例子可转换为以下增广型：
:{|
|-
| colspan="2" | max: <math>S_1\cdot x_1+S_2\cdot x_2</math>
| （目标函数）
|-
| s.t.
| <math>x_1 + x_2 + x_3 = L</math>
| （增广约束）
|-
|
| <math>F_1\cdot x_1+F_2\cdot x_2 + x_4 = F</math>
| （增广约束）
|-
|
| <math>P_1\cdot x_1 + P_2\cdot x_2 + x_5 = P</math>
| （增广约束）
|-
|
| <math>x_1,x_2,x_3,x_4,x_5 \ge 0.</math>
|}
其中<math>x_3, x_4, x_5</math>是（非负的）松弛变量，分别表示未使用的面积、未使用的肥料量和未使用的农药量。

矩阵形式表示为：
: max <math>z</math>：
: <math display=block>
  \begin{bmatrix}
    1 & -S_1 & -S_2 & 0 & 0 & 0 \\
    0 &   1    &   1    & 1 & 0 & 0 \\
    0 &  F_1  &  F_2  & 0 & 1 & 0 \\
    0 &  P_1    & P_2 & 0 & 0 & 1 \\
  \end{bmatrix}
  \begin{bmatrix}
    z \\ x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5
  \end{bmatrix} =
  \begin{bmatrix}
    0 \\ L \\ F \\ P
  \end{bmatrix}, \,
  \begin{bmatrix}
    x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5
  \end{bmatrix} \ge 0.
</math>

== 对偶==
{{main|对偶线性规划}}

每个线性规划问题，称为原问题，都可以变换为一个对偶问题。可将“原问题”表达成矩阵形式：
: max <math>\mathbf{c}^T \mathbf{x} </math>

: s.t. <math>\mathbf{A}\mathbf{x} \le \mathbf{b}, \, \mathbf{x} \ge 0 </math>

而相应的对偶问题就可以表达成以下矩阵形式：

: min   <math>\mathbf{y}^T \mathbf{b} </math>
: s.t. <math>\mathbf{y}^T \mathbf{A} \ge \mathbf{c}^T, \, \mathbf{y} \ge 0 </math>

这里用<math> y </math>来作为未知向量。

=== 例子 ===

[[线性规划#.E4.BE.8B.E5.AD.90|上述线性规划例子]]的对偶问题：

假如有一个种植园主缺少肥料和农药，他希望同这个农夫谈判付给农夫肥料和农药的价格。可以构造一个数学模型来研究如何既使得农夫觉得有利可图肯把肥料和农药的资源卖给他，又使得自己支付的金额最少？

问题可以表述如下

假设<math> y_1, y_2 </math>分别表示每单位肥料和农药的价格，则所支付租金最小的目标函数可以表示为

{| 
| colspan="2" | <math> \min E=F y_1 + P y_2 </math>
|-
| <math> s.t. </math>
|-
| <math> F_1 y_1 + P_1 y_2 \ge S_1 </math>
| (控制肥料與農藥的價格，使得农夫觉得比起拿那些肥料和農藥去種植小麥，賣給園主更有利可图)
|-
| <math> F_2 y_1 + P_2 y_2 \ge S_2 </math> 
| (與上相似，但改為大麥)
|-
| <math> y_1 \ge 0,\, y_2 \ge 0 </math>
|（不可用负数单位金額购买）
|}

== 理論 ==

幾何上，線性約束條件的集合相當於一個凸包或凸集，叫做可行域。因為目標函數亦是線性的，所以其極值點會自動成為最值點。線性目標函數亦暗示其最優解只會出現在其可行域的邊界點中。

在兩種情況下線性規劃問題沒有最優解。其中一種是在約束條件相互矛盾的情況下（例如<math> x \ge 2 </math>和<math> x \le 1 </math>），其可行域將會變成空集，問題沒有解，因此亦沒有最優解。在這種情況下，該線性規劃問題會被稱之為「不可行」。

另一種情況是，約束條件的[[多面體]]可以在目標函數的方向無界（例如：<math> \max z = x_1 + 3x_2\ s.t.\ x_1 \ge 0, x_2 \ge 0, x_1 + x_2 \ge 10 </math>），目標函數可以取得任意大的數值，所以沒有最優解。

除了以上兩種病態的情況以外（問題通常都會受到資源的限制，如上面的例子），最優解永遠都能夠在多面體的[[頂點 (幾何)|頂點]]中取得。但最優解未必是唯一的：有可能出現一組[[最優解]]，覆蓋多面體的一條邊、一個面、甚至是整個多面體（最後一種情況會在目標函數只能等於0的情況下出現）。

== 演算法 ==

[[File:Linear programming example graph (zh).png|thumb|240px|兩個變量的線性規劃問題中，一組線性約束條件劃定了對兩個變量的解的可行域。可解的問題會有一個[[簡單多邊形]]的可行域。]]

[[单纯形法|單純形演算法]]利用多面體的[[頂點 (幾何)|頂點]]構造一個可能的解，然後沿著多面體的邊走到目標函數值更高的另一個頂點，直至到達最優解為止。雖然這個[[演算法]]在實際上很有效率，在小心處理可能出現的「迴圈」的情況下，可以保證找到最優解，但它的最壞情況可以很壞：可以構築一個線性規劃問題，單純形演算法需要問題大小的指數倍的運行時間才能將之解出。事實上，有一段時期內人們曾不能確定線性規劃問題是[[NP完全|NP完全問題]]還是可以在[[多項式時間]]裏解出的問題。

第一個在最壞情況具有多項式時間複雜度的線性規劃算法在1979年由前蘇聯數學家{{le|列昂尼德·哈奇揚|Leonid Khachiyan}}提出。這個算法建基於[[非線性規劃]]中{{le|瑙姆·Z·索爾|Naum Z. Shor}}發明的[[橢球法]]（ellip-soid method），該法又是[[阿爾卡迪·內米羅夫斯基]]（2003年{{le|約翰·馮·諾伊曼理論獎|John von Neumann Theory Prize}}得主）和 [[D. Yudin]]的[[凸集最優化]]橢球法的一般化。

理論上，「橢球法」在最惡劣的情況下所需要的計算量要比「單形法」增長的緩慢，有希望用之解決超大型線性規劃問題。但在實際應用上，Khachiyan的演算法令人失望：一般來說，單純形演算法比它更有效率。它的重要性在於鼓勵了對[[内点法]]的研究。內點演算法是針對單形法的「邊界趨近」觀念而改採「內部逼近」的路線，相對於只沿著可行域的邊沿進行移動的單純形演算法，內點演算法能夠在可行域內移動。

1984年，[[貝爾實驗室]]印度裔數學家{{le|納倫德拉·卡爾瑪卡爾|Narendra Karmarkar}}提出了[[投影尺度法]]（又名{{le|卡爾瑪卡爾演算法|Karmarkar's algorithm}}）。這是第一個在理論上和實際上都表現良好的算法：它的最壞情況僅為多項式時間，且在實際問題中它比單純形演算法有顯著的效率提升。自此之後，很多內點演算法被提出來並進行分析。一個常見的內點演算法為[[Mehrotra predictor-corrector method]]。儘管在理論上對它所知甚少，在實際應用中它卻表現出色。

單形法沿著邊界由一個[[頂點 (幾何)|頂點]]移動到「相鄰」的頂點，內點演算法每一步的移動考量較周詳，「跨過可行解集合的內部」去逼近最佳解。當今的觀點是：對於線性規劃的日常應用問題而言，如果演算法的實現良好，基於單純形法和內點法的演算法之間的效率沒有太大差別，只有在超大型線性規劃中，頂點幾成天文數字，內點法有機會領先單形法。

線性規劃的求解程式在各種各樣的工業最優化問題裡被廣泛使用，例如運輸網路的流量的最優化問題，其中很多都可以不太困難地被轉換成線性規劃問題。

线性规划理论中存在几个尚未解决的问题，这些开放问题的答案将会是数学运算中的根本突破，并且很可能是解决大规模线性规划问题的主要进展。

* LP存在强多项式时间算法吗？
* LP存在多项式时间算法以得到一个严格互补解吗?
* LP在实数（单位成本）模型下存在多项式时间算法吗?
这些问题已经由[[斯蒂芬·斯梅尔]]在[[斯梅尔问题|二十一世纪十八个尚未解决的最伟大的问题]]中应用。用斯梅尔的话来说，“第三个问题是线性规划理论中最主要的尚未解决的问题”。然而，对于线性规划问题存在弱多项式时间算法，比如[[椭球法]]和内点法，尚未发现限制在约束条件个数和变量个数的强多项式时间算法，此算法的发展将会带来理论上重大意义，或者是解决大规模线性规划上的实际收益。

儘管[[赫爾希博士猜想]]近來被證明是錯誤的，但是它依舊留下下面的開放問題：
* Are there pivot rules which lead to polynomial-time Simplex variants?
* Do all polytopal graphs have polynomially-bounded diameter?

== 整數規劃 ==

要求所有的未知量都為整數的線性規劃問題叫做'''整數規劃'''（integer programming, IP）或'''整數線性規劃'''（integer linear programming, ILP）問題。相對於即使在最壞情況下也能有效率地解出的線性規劃問題，整數規劃問題的最壞情況是不確定的，在某些實際情況中（有約束變量的那些）為[[NP-hard|NP困難問題]]。

'''0-1整數規劃'''是整數規劃的特殊情況，所有的變量都要是0或1（而非任意整數）。這類問題亦被分類為[[NP-hard|NP困難問題]]。

只要求當中某幾個未知數為整數的線性規劃問題叫做'''混合整數規劃'''（mixed integer programming, MIP）問題。這類問題通常亦被分類為[[NP-hard|NP困難問題]]。

存在著幾類IP和MIP的子問題，它們可以被有效率地解出，最值得注意的一類是具有完全[[單位模]]約束矩陣，和約束條件的右邊全為整數的一類。

一個解決大型整數線性規劃問題的先進演算法為[[delayed column generation]]。

== 参见 ==
* [[单纯形法]]，一种用于线性规划问题求解的常用方法
* [[列昂尼德·维塔利耶维奇·坎托罗维奇|列昂尼德·坎托罗维奇]]（線性規劃奠基者之一）
* [[影子价格]]
* [[MPS (format)|MPS file format]]
* [[Job-shop problem|LP example, Job Shop problem]]

== 参考文献 ==
{{reflist|30em}}

== 参考书目 ==
* Alexander Schrijver: "Theory of Linear and Integer Programming". John Wiley and Sons. 1998.
* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 978-0-262-03293-3. Chapter 29: Linear Programming, pp.770–821.
* {{cite book|author = [[Michael R. Garey]] and [[David S. Johnson]] | year = 1979 | title = [[Computers and Intractability: A Guide to the Theory of NP-Completeness]] | publisher = W.H. Freeman | id = ISBN 978-0-7167-1045-5}} A6: MP1: INTEGER PROGRAMMING, pg.245.

== 外部連結 ==
*[http://people.brunel.ac.uk/~mastjjb/jeb/or/lp.html Guidance on Formulating LP problems] {{Wayback|url=http://people.brunel.ac.uk/~mastjjb/jeb/or/lp.html |date=20090904020655 }}
*[http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/pb-benchmarks.htm 0-1 Integer Programming Benchmarks with Hidden Optimum Solutions] {{Wayback|url=http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/pb-benchmarks.htm |date=20090505010001 }}
*[http://www.coin-or.org/ COIN-OR- Open Source Library for linear programming] {{Wayback|url=http://www.coin-or.org/ |date=20081219115931 }}
*[https://web.archive.org/web/20070919213139/http://www.ilog.com/products/cplex/ Cplex - Commercial library for linear programming]
*[http://www.dashoptimization.com/ Xpress-MP - Optimization software free to students] {{Wayback|url=http://www.dashoptimization.com/ |date=20080329220645 }}
*[http://www.mosek.com/ MOSEK - Optimization software for LP, QP, MIP, SOCP and more] {{Wayback|url=http://www.mosek.com/ |date=20081218000937 }}
*[http://mat.gsia.cmu.edu/orclass/integer/integer.html  A Tutorial on Integer Programming] {{Wayback|url=http://mat.gsia.cmu.edu/orclass/integer/integer.html |date=20090905151918 }}
*[http://www-unix.mcs.anl.gov/otc/Guide/faq/linear-programming-faq.html The linear programming FAQ] {{Wayback|url=http://www-unix.mcs.anl.gov/otc/Guide/faq/linear-programming-faq.html |date=20050708081651 }}

求解軟件包
* {{tsl|en|AIMMS||AIMMS}}—include linear programming in industry solutions (free trial license available);
* [http://www.coin-or.org/ COIN-OR] {{Wayback|url=http://www.coin-or.org/ |date=20081219115931 }}—COmputational INfrastructure for Operations Research, open-source library
* [https://web.archive.org/web/20070919213139/http://www.ilog.com/products/cplex/ Cplex]—Commercial library for linear programming
* [http://www.maths.ed.ac.uk/~gondzio/software/hopdm.html HOPDM] {{Wayback|url=http://www.maths.ed.ac.uk/~gondzio/software/hopdm.html |date=20080203074115 }}—Higher Order Primal Dual Method
* [http://www.lindo.com/ LINDO] {{Wayback|url=http://www.lindo.com/ |date=20080323060407 }}—LP, IP, Global solver/modeling language
* [http://sourceforge.net/projects/lipside/ LiPS] {{Wayback|url=http://sourceforge.net/projects/lipside/ |date=20110606043239 }}—Free easy-to-use program intended for solving linear, integer and goal programming problems.
* [http://groups.yahoo.com/group/lp_solve/ lp_solve] {{Wayback|url=http://groups.yahoo.com/group/lp_solve/ |date=20060903201013 }}
* [http://www.mosek.com/ MOSEK] {{Wayback|url=http://www.mosek.com/ |date=20081218000937 }}—Optimization software for LP, QP, MIP, SOCP and more
* [http://www.solver.com/ Premium Solver] {{Wayback|url=http://www.solver.com/ |date=20080326085723 }}—Spreadsheet add-in
* [http://www.lindo.com/ What's Best!] {{Wayback|url=http://www.lindo.com/ |date=20080323060407 }}—Spreadsheet add-in
* [http://www.dashoptimization.com/ Xpress-MP] {{Wayback|url=http://www.dashoptimization.com/ |date=20080329220645 }}—Optimization software free to students
* [http://www.optimalon.com/ GIPALS] {{Wayback|url=http://www.optimalon.com/ |date=20210126015300 }}—Linear programming environment and dynamic link library (DLL)
* [https://web.archive.org/web/20060820065558/http://www.vanguardsw.com/decisionpro/linear-program-optimization-software.htm  DecisionPro Linear Programming Optimization Software]
* [http://www2.isye.gatech.edu/~wcook/qsopt/ QSopt] {{Wayback|url=http://www2.isye.gatech.edu/~wcook/qsopt/ |date=20080328083456 }} Optimization software for LP (free for research purposes).
* [https://web.archive.org/web/20060722021212/http://mips.gsf.de/proj/mdcs/  Microarray Data Classification Server (MDCS)]  based on linear programming
* [ftp://garbo.uwasa.fi/pc/ts/tslin35c.zip Linear programming and linear goal programming]{{dead link|date=2018年1月 |bot=InternetArchiveBot |fix-attempted=yes }} A freeware program for MS-DOS
* [https://web.archive.org/web/20060427143036/http://people.hofstra.edu/faculty/Stefan_Waner/RealWorld/simplex.html Simplex Method Tool] A quick-loading web page

{{算法}}


{{Authority control}}
[[Category:線性規劃| ]]
[[Category:凸最佳化]]
[[Category:几何算法]]
[[Category:P完全问题]]