线性规划模型

模型简介

一种特殊形式的数学规划模型，即目标函数和约束条件是待求变量的线性函数、线性等式或线性不等式的数学规划模型。它可用于解决各种领域内的极值问题。它所描述的典型问题是怎样以最优的方式在各项活动中间分配有限资源的问题。

任何一个线性规划问题可以按下列方式表述：假设有м项有限的资源要在n项活动中间进行分配。给各项资源规定脚标1,2,…,м,给各项活动规定脚标1,2,…,n,设xj（即决策变量,有时亦称控制变量）为j项活动的水平，j=1,2,…,n。决策变量x1,x2,…,xn的一组数值代表一个方案（或计划）。设z为选定的某个效益量度（总效益指标），它的数值衡量当采取一组活动水平（x1，x2，…，xn）时所得到的总效益。设cj为每一单位的xj所提供的效益。设bj为i项资源在分配时可被利用的量，最后，设aij（i=1,2,…,м；j=1,2,…,n）为i项资源被每单位j项活动所消耗（或使用）的量。于是，将各项资源分配给各项活动以获得最优化结果的规划问题具有下列数学模型：

选择x1，x2，…,xn的值，借以使

z=c1x1 c2x2 …… cnxn达到最大，且满足下列各项限制条件：

a11x1 a12x2 ……a1nxn≤b1

a21x1 a22x2 …… a2nxn≤b2

am1x1 am2x2 …… amnxn≤bm

及x1≥0，x2≥0，…，xn≥0

这个数学模型可以等价地表述为下列更为简洁的矩阵形式：

选择x的值，借以使z=cTx达到最大，且满足下列条件：

AX≤b

x≥0

式中

x=（x1,x2…,xn）T（n维列向量）

cT=（c1,c2,…cn）（n维行向量）

b=（b1,b2,…bm）T（m维列向量）

（м×n矩阵）

线性规划模型的几何意义是：在R（n）内给定了一个多面体Ω={x/（A x≤b,x≥0）}，同时还给定了一个向量c，要求找出向量x∈Ω，使得x与c的内积达到最大。

线性规划模型中z称为目标函数，A x≤b和x≥0称为约束条件；x是决策变量，A、b以及c称为模型的参数。

以上是线性规划模型的典型形式。

然而，在实际工作中，并不是所有的线性规划问题都能表述为典型形式的数学模型，而可能出现下列情形：①使目标函数z达到最小，而不是使z达到最大；②约束条件组Ax≤b被破坏,即其中有些约束条件是“≥”的不等式；③有些约束条件是等式；④非负性约束条件x≥0被破坏。

在上述几种情况下，只需将模型的有关部分加以改写，便可使模型等价地变成典型形式。2100433B

线性规划的数学模型(mathematical model oflinear programming)是线性规划问题的一种数学表述。

即:求一组x;(j=1,2, """,n)，使满足

其中c;,b;,a;; (i=1,2,w,m;j=1,2,""",n)为常数. 符号s. t.见“数学规划”.2100433B

线性规划是运筹学的一个最重要的分支，理论上最完善，实际应用得最广泛。主要用于研究有限资源的最佳分配问题，即如何对有限的资源作出最佳方式地调配和最有利地使用，以便最充分地发挥资源的效能去获取最佳的经济效益。由于有成熟的计算机应用软件的支持，采用线性规划模型安排生产计划，并不是一件困难的事情。在总体计划中，用线性规划模型解决问题的思路是，在有限的生产资源和市场需求条件约束下，求利润最大的总产量计划。该方法的最大优点是可以处理多品种问题。

全书共分八章，分别讲解了线性规划问题的建模方法、线性规划问题模型的标准型、用单纯形算法求解线性规划问题、灵敏度分析等内容。