文档介绍：线性规划与目标规划
*
*
目录
一. 线性规划概述
二. 线性规划问题及其数学模型
*
*
一、线性规划概述
线性规划是运筹学的一个重要分支。
线性规划是由丹捷格（ x1+2x2 ≤ 8
4x1 ≤16 x1,x2 ≥ 0
4x2 ≤12
甲
乙
设备
1
2
8台时
原材料A
4
0
16kg
原材料B
0
4
12kg
*
*
二、线性规划问题及其数学模型
从上例中我们可以看出如下特征：
（1）每个问题都用一组决策变量（x1,x2,x3,···xn）表示某一方案，这组决策变量的值就表示一个具体方案。一般这些变量取值是非负且连续的。
（2）存在相关数据，同决策变量构成互不矛盾的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。
（3）都有一个要求达到的目标，它可以用决策变量及其有关的价值系数构成的线性函数（称为目标函数）来表示。按照问题的不同，要求的目标函数实现最大化或最小化。
满足以上三个条件的数学模型称为线性规划的数学模型。其一般形式如下：
*
*
二、线性规划问题及其数学模型
一般形式：
目标函数： max(min) z = c1x1+c2x2+···+cnxn (2-1)
满足约束条件： a11x1+a12x2+···+a1nxn≤(=, ≥)b1
a21x1+a22x2+···+a2nxn≤(=, ≥)b2
··· (2-2)
am1x1+am2x2+···+amnxn≤(=, ≥)bm
x1, x2, ···, xn ≥ 0 (2-3)
在线性规划的数学模型中，式(2-1)称为目标函数，cj为价值系数；式(2-2)、式(2-3) 称为约束条件；aij称为技术系数，bij称为限额系数；式(2-3) 也称为非负约束条件。“=”即为标准形式。
*
*
二、线性规划问题及其数学模型
图解法
图解法简单直观，有助于了解线性规划问题求解的基本原理
0
1
2
3
4
1
2
3
x1
x2
Q4
Q1
Q2
Q3
X1+2X2=8
4X1=16
4X2=12
(4,2)
Z=2x1+3x2
*
*
二、线性规划问题及其数学模型
图解法
上例中求解得到的问题的最优解是唯一的，但对一般线性规划问题，求解结果还可能出现以下几种情况：
1）无穷多最优解（多重最优解）
2）无界解
3）无可行解
当求解结果出现2）、3）情况时，一般说明线性规划问题的数学模型由错误。前者缺乏必要的约束条件，后者是有矛盾的约束条件，建模时应注意。
*
*
二、线性规划问题及其数学模型
图解法
0
1
2
3
4
1
2
3
x1
x2
Q4
Q1
Q2
Q3
X1+2X2=8
4X1=16
4X2=12
(4,2)
Z=2x1+3x2
从图解法中直观地见到，当线性规划问题的可行性域非空时，它是有界或无界凸多边形。若线性规划问题存在最优解，它一定在有界可行域的某个顶点得到；若在两个顶点同时得到最优解，则它们连线上的任意一点都是最优解，即有无穷多最优解。
简单地说，这也算线性规划的几何意义。
*
*
三、单纯形法
单纯形概念
（乔治·丹捷格被认为是线性规划之父）于1947年首先提出来的。
它的理论根据是：线性规划问题的可行域是 n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。
单纯形是指0维中的点，一维中的线段，二维中的三角形，三维中的四面体，n维空间中的有n+1个顶点的多面体。
例如在三维空间中的四面体，其顶点