---
title: "Linear programming — 线性规划"
source: "https://systems-analysis.info/int/Linear_programming_%E2%80%94_%E7%BA%BF%E6%80%A7%E8%A7%84%E5%88%92"
wiki: "systems-analysis.info/int"
article: "Linear_programming_—_线性规划"
language: "zh"
categories:
  - "Category:Chinese"
  - "Category:Mathematical modeling"
  - "Category:Modeling"
  - "Category:Operations research"
  - "Category:Optimization"
revision_id: 3869
wiki_created_at: 2026-09-06T23:27:18Z
wiki_modified_at: 2026-09-06T23:27:18Z
downloaded_at: 2026-09-07T22:59:30Z
---

# Linear programming — 线性规划

**线性规划**（Linear Programming，简称LP）是数学规划的一个分支，也是运筹学中广泛使用的一种方法，致力于研究和发展在线性约束条件下求解线性函数极值（最大值或最小值）问题的理论和方法。

LP是解决经济、管理、规划、物流等领域优化问题最强大和最常用的工具之一。

## 主题与目标

**线性规划的主要任务**是找到分配有限资源的最佳（最优）方式，以达成某个目标，而该目标和资源使用限制都可以用线性关系来表示。

线性规划可以解决以下实际问题：

- 生产的优化规划。
- 运输流的优化（运输问题）。
- 投资的优化配置。
- 材料的优化切割。
- 指派问题。

## LP问题的数学表述

标准的线性规划问题表述如下：

要求找到一组决策变量的值，以最大化或最小化一个线性目标函数。同时，这些决策变量受到一组线性等式和/或线性不等式形式的约束。通常，还会增加决策变量的非负性条件（其值必须大于或等于零），这通常是由问题的物理或经济意义决定的。

从数学上讲，这意味着处理线性函数以及线性方程/不等式组。

## LP的基本概念

- **决策变量**（可控变量）：在解决问题过程中需要确定的量（例如，不同产品的生产量、分配给不同目标的资源数量）。
- **目标函数**：由决策变量构成的线性函数，其值需要被最大化或最小化。它量化了问题的目标（例如，总利润、总成本）。
- **约束条件**：决策变量必须满足的一组线性等式和/或不等式。约束条件反映了资源限制、技术要求、计划任务及其他问题条件。
- **可行域**（Feasible Region）：满足问题所有约束条件的决策变量取值集合。在几何上，多维空间中的可行域是一个凸多面体，可能无界或为空集。
- **可行解**：属于可行域的任意一组变量值。
- **最优解**：使目标函数达到其极值（最大值或最小值）的可行解。如果存在最优解，它总位于可行域的边界上，并且至少在可行域凸多面体的一个顶点上（线性规划基本定理）。

## LP问题的求解方法

存在几种求解线性规划问题的主要方法：

- **图解法**：适用于只有两个决策变量的问题。该方法可以在平面上直观地表示可行域和目标函数，通过分析可行域的顶点或移动目标函数的等值线来找到最优解。
- **单纯形法**：由乔治·丹齐格（George Dantzig）开发的通用迭代算法。该方法从可行域的一个顶点依次移动到相邻顶点，在每一步都改进目标函数的值，直到找到最优解。它是求解LP问题最经典和最著名的方法。
- **内点法**：在单纯形法之后出现的另一类算法。它们在可行域内部而非边界上移动以趋近最优解。这类方法对于求解超大规模的LP问题尤其有效。

## 线性规划中的对偶性

每一个线性规划问题（称为原问题）都可以与另一个称为对偶问题的LP问题相对应。原问题和对偶问题之间联系紧密：

一个问题的解可以提供关于另一个问题解的信息。如果两个问题都存在最优解，则它们的目标函数最优值相等。对偶问题的变量具有重要的经济解释——它们对应于资源的影子价格（或对偶价格），显示当相应资源的约束发生微小变化时，原问题目标函数的最优值会改变多少。

## LP的应用

线性规划在以下领域有广泛应用：

- 经济与商业（生产规划、物流、金融、市场营销）。
- 工业（工艺流程优化、库存管理、材料切割）。
- 运输业（路线和时刻表优化）。
- 农业（优化播种面积、饲料配方）。
- 能源行业（发电设备负荷优化）。

## 参考文献

- *丹齐格 G. B.* 线性规划及其应用与推广. 1966.
- *尤金 D. B., 戈尔什坦 E. G.* 线性规划（理论、方法与应用）. 1969.
- *Taha, H. A.* Operations Research: An Introduction. 10th ed. Pearson, 2017.
- *Hillier, F. S., Lieberman, G. J.* Introduction to Operations Research. 11th ed. McGraw-Hill Education, 2021.