讨论一：模型求解时，可得到如下几种解的状况： （1）唯一最优解：只有一点为最优解点，简称唯一解； （2）无穷多最优解：有许多点为最优解点，简称无穷多解； （3）无界最优解：最优解取值无界，简称无界解； （4）无可行解：无可行域，模型约束条件矛盾。
讨论二：LP模型求解思路： （1）若LP模型可行域存在，则为一凸形集合； （2）若LP模型最优解存在，则其应在其可行域顶点上找到； （3）顶点与基本解、基本可行解的关系：
如 x1+x23 x1+x2+ x3=3
zmin
当 “”时，引进剩余（surplus）
z
变量 - xs； 如 x1+2x2 4 x1+2x2－x4=4
x
z = -
（4）约束右端项：当 bi < 0，则不等式 两端同乘（- 1）
z max z
例2-2 将以下线性规划问
题转化为标准形式
min z 2x1 3x2 x3
LP的标准化：
（1）变量：若 xj0，令 xj=-xj，xj0 若 xj无约束，则令 xj= xj－xj，xj0，xj0
（2）目标函数：若求 min z，则 即有 min z= - max （- z）
（3）约束方程：当 “”时，引进松 弛（slack）变量+xs； z
am1x1 am2x2 amjx j anmxn ()bm 称为约束条件，
x1，x2，…，xj，…，xn³0
称为变量的非负约束。
线性规划问题矩阵和向量的表达式
， ，
或 写 成
二 图解法
图解法的优点是直观性强，计算方便，但缺点是只适 用于问题中有两个变量的情况。
图解法的步骤是：建立坐标系，将约束条件在图上表 示；确立满足约束条件的解的范围；绘制出目标函数的图 形；确定最优解。
c2x2 a12x2 a22x2
cjx j a1jx j a2jx j
cn x n a1nxn a2nxn
(,)b1 (,)b2
am1x1 am2x2 amj x j amn xn (, )bm
x1
x2
xj
xn
0
线性规划模型的三要素：
（1）决策变量：指模型中要求解的未知量，简称变量。 （2）目标函数：指模型中要达到的目标的数学表达式。
目标函数 max z 2x1 3x2
2x1 2x2 12
约束条件
:
x1 2x2 8 4x1 16
4x2 12
x1 , x2 0
-4-
例2-1 美佳公司下设两个分工厂，两个仓库及一个配送中心。其中F1和 F2是两个工厂，W1和W2是两个仓库。DC是一个分销中心。由工 厂生产的产品经由图2-1所示的运输网络运往仓库。每一条路线 运输的单位成本在线段上给出，其中，F1→F2与DC→W2路线由
以如下线性规划问题为例说明如下：
max z 2x1 3x2
2 x1 2 x2 12
s.t.
x1 2 x2 8
4 x1
16
4 x2 12
x1, x2 0
a
b c d e f
图1-2
x2 2x1+2x2=12
Q4
Q3
Q2 (4,2)
max z 2x1 3x2
2x1 2x2 12
300元/单位 X7
X6
需求60 W2 单位
图2-1 美佳公司的配送网络
第二节 线性规划模型与图解法
一 线性规划问题的数学模型
数学模型就是用数学表达式和符号对研究对象数量关系所进 行的定量描述。
线性规划问题的一般形式通常表现为以下几种形式
max(min) z c1x1
s.t.
a11x1
a 21x1
---第 1 章 线性规划---
第三节 单纯形法
一、线性规划模型的标准形式
（1）变量：所有变量均xj 0 （2）目标函数：为取“max”形式 （3）约束条件：全部约束方程均为“=”连接 （4）约束右端项：bi 0
非标准形式情况有
变量： xj 0 ,或xj无约束 目标函数：min 约束条件：“”或“” 约束右端项： bi<0
第 二 章 线性规划
Linear Programming
-1-
第二章 线性规划
第一节：线性规划问题及其建模 第二节：线性规划模型与图解法 第三节：单纯形法 第四节：对偶问题 第五节：灵敏度分析 第六节：运输问题 第七节：数据包络分析 第八节：线性规划的应用
第一节 线性规划问题及其建模
某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位
产品所需的设备台时及A、B两种原材料的消耗，如表1-1所示。 每生产一件产品Ⅰ可获利2元，每生产一件产品Ⅱ可获利3元，问 应如何安排计划使该工厂获利最多?
资源 产品
Ⅰ
Ⅱ
拥有量
设备 A
2
2
12
设备 B
1
2
8
原材料 A
4
/
16
原材料 B
/
4
12
-3-
建立模型：
设 产品的产量 甲x1件 ，乙 x2件，则
x1 x2 2x3 3
s.t .
2x1 3x2 x1 x2
x3 5 x3 4
x1,
x3 0
解：设 z= - z, x2= x2 - x2 , x2 0 , x2 0, x40, x50, 则有
（3）约束条件：指模型中的变量取值所需要满足的一 切限制条件。
其中 max(min) z c1x1 c2x2 c jx j cn xn 称为目标函数
a11x1 a 21x1
a12x2 a22x2
a1jx j a2jx j
a1n x n a2nxn
()b1 ()b2
x1 2x2 8
4 x1
16
4x1=16
4x2 12
4x2 =12 x1, x2 0
x1+2x2=8
O
Q1
x1
唯一解 A
无界解
无穷多解 A
B
无可行解
步骤：（1）作平面直角坐标系，标上刻度； （2）做出约束方程所在直线，确定可行域； （3）做出一条目标函数等值线，判定优化方向； （4）沿优化方向移动，确定与可行域相切的点，确定最优 解，并计算最优值。
于受到路线中的桥梁承重上限的要求，因此有最大运输量限制。 其他路线有足够的运输能力来运输两个工厂生产的货物。
生产50 单位 F1
900元/单位 400元/单位
x3
W1 需求30
单位
200 x1
x2
元/
DC
单位 最多10单位
生产40 单位 F2
300元/单位 x4
200元/单位
100元/单位 最多80单位 x5