线性规划的理论与实例分析.pdfVIP

线性规划的理论与实例分析

线性规划（LinearProgramming，简称LP）是一种重要的运筹

学工具，常常被应用于生产、物流、金融等领域中的优化问题。

本文将从理论和实例两个角度，介绍线性规划的基本概念、模型

及求解方法。

一、线性规划的基本概念

线性规划的基本概念包括决策变量、目标函数、约束条件等。

（一）决策变量

决策变量是指影响问题结果的变量，通常用x1、x2、…、xn

表示。例如，生产线上的机器数量、产品的产量等都是决策变量。

（二）目标函数

目标函数是指要最大化或最小化的某个指标，通常用z表示。

例如，最小化成本、最大化利润等都是目标函数。

（三）约束条件

约束条件是指在问题求解中要满足的条件。例如，不超过机器

限制数量、满足生产需求等都是约束条件。通常用不等式或等式

形式表示。

二、线性规划的模型

线性规划的一般形式可表示为：

最大化或最小化目标函数：

Z=c1x1+c2x2+…+cnxn

约束条件：

a11x1+a12x2+…+a1nxn≤b1

a21x1+a22x2+…+a2nxn≤b2

……

am1x1+am2x2+…+amnxn≤bm

或x1,x2,…,xn≥0（非负性约束条件）

其中，c1、c2、…、cn为各决策变量的系数，a11、a12、…、

amn为各约束条件中各决策变量的系数，b1、b2、…、bm为约束

条件的值，x1、x2、…、xn为决策变量，非负性约束条件也称为

非负约束。

三、线性规划的求解方法

线性规划有多种求解方法，这里主要介绍两种：单纯性法和对

偶理论。

（一）单纯性法

单纯性法是线性规划的一种基本算法，其实质是在各约束条件

限制下寻找目标函数最大或最小值。单纯性法基于以下两个原则：

①某个极值点必定满足目标函数的所有约束条件；

②各个变量所形成的可行解区域有限，且该区域的可行解点数

有限。

单纯性法的具体过程如下：

Step1建立初始单纯形表

将约束条件转化为标准形式，即将约束条件化为”≤“的形式，

并加入人工变量，得到初始单纯形表。

Step2寻找主元素

寻找主元素，并选择进入变量和离开变量。进入变量选择的原

则是：选取目标函数系数为正的变量中，系数绝对值最大的变量；

离开变量选择的原则是：选取该进入变量能够使约束条件退化出

现的系数最小的变量。

Step3迭代计算

通过基变量方程，确定各变量的值，并计算出Z值。如果Z值

为负数，则不满足最大化的要求。如此，就可以通过更改主元素，

重新迭代计算。直到目标函数值不在减小，得到最终的结果。

（二）对偶理论

对偶理论是用来求解线性规划的一种方法，可以将线性规划问

题转化为另一个线性规划问题来求解。对于每个线性规划问题，

都可以建立一个对应的次级问题，次级问题是原来线性规划问题

的对偶（dual）。

对偶问题的一般形式可表示为：

最大化或最小化目标函数：

W=b1y1+b2y2+…+bmym

约束条件：

a11y1+a21y2+…+am1ym≥c1

a12y1+a22y2+…+am2ym≥c2

……

a1ny1+a2ny2+…+amnym≥cn

或y1,y2,…,ym≥0

其中，y1、y2、…、ym为次级问题的决策变量，b1、b2、…、

bm为各次级问题决策变量的系数，a11、a21、…、amn为线性规

划约束条件中各决策变量的系数，c1、c2、…、cn为线性规划目

标函数中各决策变量的系数。

对偶理论的具体过程如下：

Step1建立对偶问题的初始单纯形表

将原来问题的目标函数系数变为对偶问题的约束条件系数，将

原来问题的约束条件系数变为对偶问题的目标函数系数，然后添

加系数为负的假设标量，得到初始单纯形表。

Step2寻找主元素

寻找主元素，并选择进入变量和离开变量