当前位置：文档之家 › 运筹学第二章线性规划

运筹学第二章线性规划

  • 格式：doc
  • 大小：420.00 KB
  • 文档页数：12

下载文档原格式

  / 12

合集下载

管理运筹学第二章 线性规划的图解法

管理运筹学第二章 线性规划的图解法

B、约束条件不是等式的问题：
若约束条件为 ai1 x1+ai2 x2+ … +ain xn ≤ bi 可以引进一个新的变量si ，使它等于约束右 边与左边之差 si=bi–(ai1 x1 + ai2 x2 + … + ain xn ) 显然，si 也具有非负约束，即si≥0， 这时新的约束条件成为 ai1 x1+ai2 x2+ … +ain xn+si = bi
第二章 线性规划 的图解法
一、线性规划的概念 二、线性规划问题的提出 三、线性规划的数学模型 四、线性规划的图解法 五、线性规划解的情况 六、LP图解法的灵敏度分析
一、线性规划的概念
线性规划Linear Programming 简称LP，是一 种解决在线性约束条件下追求最大或最小的 线性目标函数的方法。 线性规划的目标和约束条件都可以表示成线 性的式子。
max z 3 x1 2 x2
2 x1 x2 ≤ 10 设备B台时占用 s.t. x1 x2 ≤ 8 x , x ≥ 0 产量非负 1 2
决策变量 （decision variable） 目标函数 （objective function） 约束条件 （subject to）

-ai1
x1-ai2 x2- … -ain xn = -bi 。
例1.3：将以下线性规划问题转化为标准形式 Min f = 3.6 x1 - 5.2 x2 + 1.8 x3 s. t. 2.3 x1 + 5.2 x2 - 6.1 x3 ≤15.7 4.1 x1 + 3.3 x3 ≥8.9 x1 + x2 + x3 = 38 x 1 , x 2 , x3 ≥ 0

第二章线性规划

第二章线性规划



线性规划要研究的两类问题中都包含有约束条件和目 标函数。用数学的方式描述，规划的目的就是在给定 的限制条件（或称约束条件）下，求目标函数的极值 问题（包括极小值和极大值）。
2
线性规划的数学模型
3
解： 设产品 的产量为：1 , 产品 的产量为：x2 x
4
5
6
7

配料问题：由若干种不同价格、不同成分含量的原料，用 不同的配比混合调配出一些不同规格的产品，在原料的供 应量限制和保证产品成分含量的前提下，如何进行配料来 获取最大利润或使总成本最低。
15
2.2.3 线性规划求解的可能结局
1、有唯一的最优解
2、有无穷多个最优解 （将目标函数改为 z=4x1+3x2 ）
x2
max z 4 x1 3 x2 x1 2 x2 5 2 x x 4 1 2 s.t. 4 x1 3 x2 9 x1 , x2 0
3x1 2 x2 4 x3 3
3x1 2 x2 4 x3 xs 3
剩余变量
变量xs实际上是原式左端减去右端的差，即 ：
xs 3x1 2 x2 4 x3 3
当约束条件是“ ”型的不等式时，只要将该约 束条件左端减去一个非负的剩余变量即可化为等式。 无论是松弛变量还是剩余变量在决策中都不产生实际价 值，因此它们在目标函数中的系数都应该为零。有时也将松 29 弛变量和剩余变量统称为松弛变量。
2x1+x2=4 D C
x1+2x2=5 B 4x1+3x2=9 O A x1
16
3、无界解
指线性规划问题有可行解，但是 在可行域，目标函数值是无界的， 因而达不到有限最优值。因此线 性规划问题不存在最优解。

管理运筹学第二章线性规划的图解法

管理运筹学第二章线性规划的图解法

02
图解法的基本原理
图解法的概念
图解法是一种通过图形来直观展示线性规划问题解的方法。它通过在坐标系中绘 制可行域和目标函数，帮助我们理解问题的结构和最优解的位置。
图解法适用于线性规划问题中变量和约束条件较少的情况，能够直观地展示出最 优解的几何意义。
图解法的步骤
确定决策变量和目标函数
明确问题的决策变量和目标函数，以便在图 形中表示。
目标函数是要求最小化或最大化的函数，通常表示为 $f(x) = c_1x_1 + c_2x_2 + ldots + c_nx_n$。
04
约束条件是限制决策变量取值的条件，通常表示为 $a_1x_1 + a_2x_2 + ldots + a_nx_n leq b$或 $a_1x_1 + a_2x_2 + ldots + a_nx_n = b$。
LINDO是一款开源的线性规划求解器，用 户可以免费使用。
软件工具的使用方法
Excel
用户需要先在Excel中设置好线性规划模型，然后使 用“数据”菜单中的“规划求解”功能进行求解。
Gurobi/CPLEX/LINDO
这些软件通常需要用户先在软件界面中输入线性规划 模型，然后通过点击“求解”按钮进行求解。
实例三：分配问题
总结词
分配问题是指如何根据一定的分配原则 或目标，将有限的资源分配给不同的需 求方，以最大化整体效益。
VS
详细描述
分配问题在实际生活中广泛存在，如物资 分配、任务分配等。通过图解法，可以将 分配问题转化为线性规划模型，并利用图 形直观地展示最优解的资源分配方案。在 分配问题中，通常需要考虑不同需求方的 重要性和优先级，以及资源的有限性等因 素，以实现整体效益的最大化。

管理运筹学_第二章_线性规划的图解法

管理运筹学_第二章_线性规划的图解法

线性规划中超过约束最低限的部分，称为剩余量。 记s1,s2为剩余变量，s3为松弛变量，则s1=0, s2=125,
s3=0，加入松弛变量与剩余变量后例2的数学模型变为 标准型： 目标函数： min f =2x1+3x2+0s1+0s2+0s3 约束条件： x1+x2-s1=350， x1-s2=125, 2x1+x2+s3=600, x1, x2, s1,s2,s3≥0.
阴影部分的每 一点都是这个线 性规划的可行解， 而此公共部分是 可行解的集合， 称为可行域。
B
X2=250
100
100
300
x1
B点为最优解， X1+X2=300 坐标为（50, 250）， Z=0=50x1+100x2 此时Z=27500。 Z=10000=50x1+100x2 问题的解： 最优生产方案是生产I产品50单位，生产Ⅱ产品250单位，可得 最大利润27500元。
Z=10000=50x1+50x2
线段BC上的所有点都代表了最优解，对应的最优值相 同： 50x1+50x2=15000。
10
3. 无界解，即无最优解的情况。对下述线性规划问题：
目标函数：max z =x1+x2 约束条件：x1 - x2≤1 -3x1+2x2≤6 x1≥0, x2≥0．
x2 -3x1+2x2=6 3
其中ci为第i个决策变量xi在目标函数中的系数， aij为第i个约束条件中第j个决策变量xj的系数， bj(≥0)为第j个约束条件中的常数项。
16
灵敏度分析
灵敏度分析：求得最优解之后，研究线性规划的

运筹学第二章第6节矩阵法求解线性规划问题

运筹学第二章第6节矩阵法求解线性规划问题

（3）初始单纯性表与当前单纯性表关系
单纯性法的每一步就是：令非基变量XN（XN1和 XS2）=0，则当前基本可行解X=（XB，0） =（B-1b，0）。当前的目标函数值为 Z=CBB-1b，通过刚才用矩阵法的展示，我们发现： 1）B：初始单纯性表中基。 2）BN：初始单纯性表非基变量在A中对应的矩阵。 3）B-1：初始单纯性表中单位矩阵所对应的列在当 前矩阵中所构成的矩阵。 4）CB：当前基变量的价值向量。 5）CN：当前非基变量的价值向量。
2 x1 [1] 4 0 2
3 x2 0 0 1 0
0 x3 1 0 0 0
0 x4 0 1 0 0
0 x5 0 1/4 -3/4 θ 4 -
-1/2 2
在迭代到单纯性表2时，当前的基变量为x3，x4，x2，其中 x3和x4是松弛变量。这时，松弛变量中，x5为基变量，x3和 x4为非基变量，因此：基变量XB由两部分组成，一部分是 XB1=x2，一部分是XS1=x3和x4；非基变量XN由两部分组成， 一部分是XN1=x1，另外一部分是XS2=x5。
BX X
B
B
b BN X
1
N1
S2 X
N1
S2
;
1
B b B B N1 X
1
1
1
B S 2 X s2 ;
1
目标函数： z C B B b (C N1 C B B B N1 ) X (C S 2 C B B I ) X
1 S N1
令非基变量=0，由上式得到：
x1 2 x 2 x 3 4 x1 4 x2 x
j

8
x4 0
16 x 5 12
j 1, 2 , , 5

运筹学第二章

运筹学第二章

例2.4：将以下线性规划问题转化为 标准形式
Max s.t. Z = 3 x1 - 5 x2 + 8 x3 2x1 + 2x2 - x3 = 15.7
4 x1
+ 3x3 = 8.9
x1 + x2 + x3 = 38 x2 , x3 ≥ 0
4.右端项有负值的问题：
在标准形式中，要求右端项 必须每一个分量非负。当某一个 右端项系数为负时，如 bi<0，则 把该等式约束两端同时乘以-1， 得到：
产品甲 设备A 3 产品乙 2 设备能力 （h） 65
设备B
设备C 利润（元/件）
2
0 1500
1
3 2500
40
75
问：如何安排生产计划，才能使制药厂利润最大？
解：设变量 xi为第i种（甲、乙）产品的生 产件数（i＝1，2）。根据前面分析，可 以建立如下的线性规划模型： Max
z = 1500 x1 + 2500 x2
MinZ=∑xi
i=1
X6 +
x1 x1 + x2 x2 + x3 x3 + x4 x4 + x5 x5 + x6
≥ 8 ≥ 12
≥ 10
≥ 8 ≥ 6 ≥ 4
二、线性规划模型的一般形式
目标函数 s.t.
产品对资源的 单位消耗量
利润系数
Max(Min)z=c1x1+c2x2+……+cnxn
a11x1+a12x2+……+a1nxn≥(=、≤)b1 a21x1+a22x2+……+a2nxn≥(=、≤)b2 …… am1x1+am2x2+……+amnxn≥(=、≤)bm

运筹学第2章：线性规划的对偶理论

运筹学第2章：线性规划的对偶理论

目
标函数求极小时取“≥”号
注：对称形式与线性规划标准型是两种不同的形 式，对称形式中约束条件的符号由目标函数决定
从以下方面比较(LP1)与(LP2)：
原问题
对偶问题 约束系数矩阵的转 臵 目标函数中的价格 系数向量 约束条件的右端项 向量 Min w=Y’b A’Y≥C’ Y≥0
A
b C 目标函数 约束条件 决策变量
非基变量 基变量
XB
0 b Xs C j - zj B
XN
N
Xs
I
0
初始 单纯形表
非基变量
CB
CN
基变量
最终
单纯形表
CB
XB
XB B-1b Cj - zj
I 0
Xs B-1 N B-1 CN-CBB-1N -CBB-1
XN
若B-1b为最优解，则
CB CB ( B 1B) 0 C N CB B N 0 CB B 1 0
令 y 2 y 2 , y3 y3 y3 ，则
min 2 y1 y2 4 y3
2 y1 3 y2 y3 1 3 y y y 4 1 2 3 s.t. 5 y1 6 y2 y3 3 y1 0, y2 0, y3无约束
n j 1 m j j
C X Y b, 即 c j x j y i bi
j 1 i 1
__
__
n
m
c x ( a
j 1 m i 1 n i i i 1 i 1 j 1
n
m
ij
yi ) x j aij x j yi ( a ji yi c j )
例1

运筹学第二章线性规划的对偶理论

运筹学第二章线性规划的对偶理论

(5.5) (5.6)
4.3 对偶问题的基本性质
证： 设B是一可行基，于是A=(B,N)
max z=CBXB+ CNXN BXB+BXN +Xξ=b X,XB,Xξ ≥0
其中Yξ=(Yξ1, Yξ2)
min ω =Yb YB－Yξ1=CB YN－Yξ2=CN Y, Yξ1 Yξ2 ≥0
(5.5) (5.6)
x1﹐x2 ≥0
关系？
对原模型设： 1 2
A= 4 0 b=(8,16,12)T C=(2，3) 04
X=（x1，x2）T Y=（y1，y2 ，y3 ） 则可得:
4.1 对偶问题的提出
min ω=8 y1+16y2 +12y3
y1+4y2
≥2
2 y1 +4y3≥3
与
y1 ， y2 ，y3≥0 12
max z＝2x1+3x2 x1＋ 2x2 ≤8
4x1
≤16
4x2 ≤12
x1﹐x2 ≥0
有何关 系？
对愿模型设： A= 4 0 04
b=(8,16,12)T C=(2，3)
X=（x1，x2）T
Y=（y1，y2 ，y3 ） 则可得:
max z=CX AX≤b （5.1） 和
min ω =Yb YA ≥ C （5.2）
120
A=
1 -3
0 2
1 1
1 -1 1
b=(2,3,-5,1)T C=(5,4, 6)
确定约束条件
YA
C
x1 ≥0 ﹐x2≤0, x3 无约束
解：因原问题有3个变 于是 量，4个约束条件， 所以对偶问题4个 变量，3个约束条

运筹学第2章-线性规划的对偶理论

运筹学第2章-线性规划的对偶理论
❖ 影子价格不是市场价格，而是在现有技术和管理条件下， 新增单位资源所能够创造的价值，是特定企业的一种边 际价格；不同企业或同一企业不同时期，同种资源的影 子价格可能不同；当市场价格高于影子价格，可以卖出； 相反，则应买进，以获取更大收益
Ma例x：Z （ 2第x一1 章3例x22）
2 x1 2 x2 12
当原问题和对偶问题都取得最优解时，这 一对线性规划对应的目标函数值是相等的：
Zmax=Wmin
二、原问题和对偶问题的关系
1、对称形式的对偶关系
（1）定义：若原问题是
MaxZ c1 x1 c2 x2 cn xn
a11x1 a12 x2 a1n xn b1
s.t.a21
x1
a22
二、 手工进行灵敏度分析的基本原则 1、在最优表格的基础上进行； 2、尽量减少附加计算工作量；
5y3 3
，y
2
3
0
（用于生产第i种产 品的资源转让收益不 小于生产该种产品时 获得的利润）
对偶变量的经济意义可以解释为对工时及原材 料的单位定价 ；
若工厂自己不生产产品A、B和C，将现 有的工时及原材料转而接受外来加工时， 那么上述的价格系统能保证不亏本又最富 有竞争力（包工及原材料的总价格最低）
内，使得产品的总利润最大 。
MaxZ 2x1 3x 2
2x1 2x2 12
s.t.54xx12
16 15
x1, x 2 0
它的对偶问题就是一个价格系统，使在平衡了 劳动力和原材料的直接成本后，所确定的价格系统 最具有竞争力：
MinW 12y1 16y2 15y3
2y1 4y2
2
s.t.2y1y，1y
y1, y2, , ym 0

运筹学线性规划

运筹学线性规划
其次线性规划模型必须满足如下两个要求： ① 目标函数必须是决策变量的线性函数； ② 约束条件必须是含决策变量的线性等式或不等式。
运筹学建模步骤: 识别问题 定义决策变量
建立约束条件 建立目标函数
整理课件
2.2 线性规划模型的一般形式和标准形式
2.2.1 线性规划的一般模型
为了讨论一般的线性规划问题的求解。我们先给出线性规 划模型的一般形式如下：
max(或min)z CX
n
s.t. j1
Pj x j
(或 ，或)b
X 0
其中
x1
a1j b1
Xx2,Cc1 c2 cn,Pj a2j,bb2
xn
amj bm
整理课件
用矩阵的记号可以将线性规划模型一般形式写成：
max(或min)z CX
AX (或，或)b s.t.X 0
其中 X, C, b 同上，而矩阵 A 是由各约束条件的系数（技术
养分
饲料
A
B
C
M
0.5
0.2
0.3
D
价格
0
300
N
0.1
0.3
0.4
0.2
200
每头日需 10
5
8
7
答案：设购买M饲料x1，N饲料x2
Min Z=300 x1 +200x2 0.5 x1 +0.1x2≥10
0.2x1 +0.3x2 ≥5
s.t.
0.3x1 +0.4x2 ≥8
0.2x2 ≥7
x1 , x2≥0 整理课件
x1 2 x2 5
s.t.
2
4
x1 x1
x2 4 3x2 9

运筹学第四版第二章线性规划及单纯形法

运筹学第四版第二章线性规划及单纯形法

方案的制定受到那些现实条件制约：
确定约束条件
人力资源（劳动力）的限制： 9x1 4x2 360
设备工时的限制：
4x1 5x2 200
原材料资源的限制：
3x1 10x2 300
此外，决策变量的取值不应为负值即 x1 0, x2 0
6
综上所述，我们得到了这个问题的数学模型
目标函数 约束条件
大？
项目
Ⅰ
设备A (h)
0
设备B (h)
6
调试工序(h) 1
利润（元） 2
Ⅱ 每天可用能力
5
15
2
24
表1-2
1
5
1
12
其数学模型为：
max Z 2x1 x2
5x2 15
6xx11
2x2 x2
24 5
x1, x2 0
13
例3：捷运公司在下一年度的1～4月份的4个月内拟租用仓库
堆放物资。已知各月份所需仓库面积列于下表1-3。仓库租
借费用随合同期而定，期限越长，折扣越大，具体数字见表
1-4。租借仓库的合同每月初都可办理，每份合同具体规定
租用面积和期限。因此该厂可根据需要，在任何一个月初办
理租借合同。每次办理时可签一份合同，也可签若干份租用
面积和租用期限不同的合同。试确定该公司签订租借合同的
最优决策，目的是使所租借费用最少。
14
max Z 70 x1 120 x2
9x1 s.t. 43xx11
x1,
4x2 5x2 10x2 x2 0
360 200 300
资源约束
非负约束
其中 约束条件可记 s.t (subject to), 意思为“以… 为条件“、”假定“、”满足“之意。

运筹学第二章——第八节—线性规划的对偶理论

运筹学第二章——第八节—线性规划的对偶理论

四、对偶问题经济学含义——影子价格
因为Z*=Y*=Yb 所以：Δ Z/ Δ b=Y b——资源的量 Z——目标函数 经济学含义：资源每变动一个单位，目标函 数（利润、总产值等）变动的大小。 资源对生产做出的贡献。（影子价格） 是对现有资源实现最大效益的一个评价，叫 机会成本。
V*X=0， Y*U=0，其中V是对偶问题的剩余变量，U是 原问题的松弛变量。
（七）原问题在单纯性法迭代过程中的检验 数对应于对偶问题的一个基本解。（对应性 定理） 原问题 XB XN 对应基B检验数 0 CN-CBB-1BN 对偶问题的变量 -YS1 -YS2 XS –CBB-1 -Y
对偶问题性质的启示
原问题 有最优解 无可行解 有可行解无上界 无有限最优解 对偶问题 有最优解 无可行解 无有限最优解 有可行解但无下界
由互补松弛性定理可知： 当U>0，即AX <b时，资源未充分利用时，影 子价格为0。
二、原问题与对偶问题之间的转化
1、目标函数 MAX——Min 2、约束条件——变量 约束条件n个——变量n个 约束条件≥0 ——变量≤ 0 约束条件≤ 0 ——变量 ≥ 0 约束条件=0——变量无约束 要点：max为反向关系（约束条件——变量）
二、原问题与对偶问题之间的转化
3、变量——约束条件 变量m个——约束条件m个 变量≥0——约束条件≥ 0 变量≤ 0 ——约束条件≤ 0 变量无约束——约束条件=0 4、目标函数中变量的系数C为对偶问题中约 束条件的右端常数项b，个数对等变动。
（五）若原问题和对偶问题具有可行解，若 原问题或对偶问题之一有最优解，则另一个 对偶问题也必有最优解，且最优值相同。 （主对偶性定理） 证明 含义： 若原问题有一个对应于基B的最优解，则 CBB-1为对偶问题的最优解。

运筹学_线性规划1

运筹学_线性规划1
min Z 2x1 3x2 x3
x1 x 2 x3 10 3 x 2 x x 8 1 2 3 s.t. x1 3 x 2 x3 1 x1 , x 2 0, x3 符号不受限制
Байду номын сангаас
标 准 化
maxZ 2x1 3x2 ( x3 x4 ) 0 x5 0 x6
I 设备A(h) 设备B(h) 调试工序（h） 利润（千元） 0 6 1 2
II 5 2 1 1
课堂练习
一家家电公司准备将一种新型电视机在三家商场进行销 售，每一个商场的批发价和推销费及产品的利润如表所示。 由于该电视机的性能良好，各商场都纷纷争购，但公司每 月的生产能力有限，只能生产1000台，故公司规定：商场 1至少经销100台，至多200台，商场2至少经销300台，商 场3至少经销200台。公司计划在一个月内的广告预算费为 8000元，推销人员最高可用工时数为1500。同时，公司只 根据经销数进行生产，试问公司下个月的市场对策？
④ 右端非负。
标准型的紧缩形式：
max Z c j x j
j 1 n
标 准 型
n aij x j bi s.t. j 1 x 0 j
i 1,2,, m j 1,2,, n
标准型的矩阵形式：
max Z CX
AX b s.t. X 0
例2-3 某饲料公司生产一种鸡饲料，每份饲料
问 题 的 导 出
为100公斤，饲料中的营养成份要求、配料及 其成本数据如下：
配料 营养成分 单位 蛋白质 配料 钙 含量 粗纤维 单位配料成本 大豆粉 玉米粉 石灰石 0.50 0.002 0.08 2.50 0.09 0.001 0.02 0.926 0 0.38 0 0.164 含量要求 ≥22% ≥0.8%且≤1.2% ≤5%
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

第二章线性规划教学目的和要求：目的：使学生具备线性规划的基本知识以及应用线性规划的基本能力。

要求：理解线性规划概念，标准型，解的概念，基本定理；掌握单纯形法，人工变量法，了解图解法。

重点：线性规划标准型，解的概念，单纯形法，人工变量法。

难点：线性规划基本定理，单纯形法。

教学方法：讲授法，习题法。

学时分配：12学时 作业安排：见教材P 38.线性规划是运筹学的一个重要分支。

1939年苏联科学家康托罗维奇提出了生产组织和计划中的线性规划模型。

1947年美国学者丹捷格(George B.Dantzig)提出了求解一般线性规划问题的方法。

此后，线性规划理论日趋成熟，应用也日益广泛和深入。

第一节线性规划问题一、问题的提出在企业的生产经营活动中经常会面临这样两类问题：一是如何合理地利用有限的人力、物力、财力等资源，取得最佳的经济效果；二是在取得一定的经济效果的前提下，如何合理安排使用人力、物力、财力等资源，使花费的成本最低。

例1.生产计划问题 某工厂利用甲、乙、丙、丁四种设备生产A 、B 、C 三种产品，具体数据如下表所示。

A 、B 、C 单位产品的利润分别是4.5、5、7(百元)。

问如何安排生产计划，才能使所获总利润最大？解：设产品A 、B 、C 产量分别为X 1,X 2,X 3件,Z 表示利润，要求总利润最大，即求Z=4.5X 1+5X 2+7X 3的最大值，故记作极大化Z=4.5X 1+5X 2+7X 3，另外对甲、乙、丙、丁设备需满足2X 1+2X 2+4X 3≦800，X 1+2X 2+3X 3≦650，4X 1+2X 2+3X 3≦850，2X 1+4X 2+2X 3≦700；同时产量应非负，故X j ≧0 (j=1,2,3)；以上问题可用数学模型表示为： 极大化Z=4.5X 1+5X 2+7X 3 满足 2X 1+2X 2+4X 3≦800 X 1+2X 2+3X 3≦6504X 1+2X 2+3X 3≦850 2X 1+4X 2+2X 3≦700X j ≧0 (j=1,2,3)例2.运输问题 设某种物资有m 个产地；A 1,A 2, …,A m ,它们的产量分别为a 1,a 2, …,a m ,有n 个销地B 1,B 2, …,B n 需要这种物资，它们的销量分别为b 1,b 2, …,b n 。

已知A i 到B j 的单位运价是C ij (i=1,2, …,m;j=1,2, …,n)。

设供销满足平衡条件，即 。

问怎样组织运输，才能满足要求，且使总运费最少？---- 7 5 4.5 单位利润 700 2 4 2 丁 850 3 2 4 丙 650 3 2 1 乙 800 4 2 2 甲 设备可供工时(h) C B A产品 设备 ∑=∑==n 1j j b m 1i i a解：设X ij (i=1,2, …,m; j=1,2, …,n)表示由A i 到B j 的物资运输量，则总运费为∑=∑==m 1i ijXn1j ij C Z ，另外，对A i 应有i a n1j ij x =∑=, i=1,2, …,m 对B j ，应有j b m1i ij x =∑=, j=1,2, …,n同时，运输量应非负，故X ij ≧0，(i=1,2, …,m; j=1,2, …,n) 以上问题数学模型为：极小化∑=∑==m 1i ijXn1j ij C Z 满足 ia n1j ij x =∑=, i=1,2, …,mj b m 1i ij x =∑=, j=1,2, …,nX ij ≧0 (i=1,2, …,m; j=1,2, …,n)例3.配料问题要配制一种面包，每只面包要求含甲、乙、丙3种营养成分至少各为20、24、30单位。

现有4种原料可供选用，下表给出了每10g 原料所含各种营养成分的单位数。

试确定每种原料各取多少，才能使面包的配制成本最低？解：先假设配制一只面包，数量多只需扩大相应倍数即可。

由观察可知，原料A 不论在营养成分含量上还是价格上都优于C ，故C 不选用，设A 、B 、D 各取X 1, X 2 , X 4个10 g 。

则可得数学模型如下： 极小化Z=10X 1+15X 2+25X 4 满足 X 1+2X 2+(1/4)X 4 ≧ 20 3X 1+ X 2+(1/2)X 4 ≧ 24 3X 1+ X 2+ 4X 4 ≧ 30X 1，X 2，X 4≧0 二、线性规划模型以上几个问题各有不同，但其数学模型有共同之处：它们都是要求一组变量(称为决策变量)X 1,X 2，…，X n ，这组变量全部或者其中一部分具有非负要求，且满足一系列线性等式或不等式∑=≥≤=n 1j i)b , (j x ij a , i=1,2, …,m, 使一个用线性式表示的目标(称为目标函25 30 15 10 价格(分/10g) 4 2 1 3 丙 1/22 13 乙 1/4 1/2 2 1 甲 D C B A原料营养种类数)Z=C 1X 1+C 2X 2+…+C n X n 达到极值，这类问题称为线性规划。

一般而言，线性规划数学模型为：极大化(极小化) Z=C 1X 1+C 2X 2+…+C n X n …………①，∑=≥≤=n1j i )b,(j x i a j , i=1,2, …,m……② X j ≧0 全部或部分j , j=1,2, …,n……③①式为目标函数，②为约束条件，③为非负要求；式①，②全为线性式，否则称为非线性规划。

满足②，③的一组变量X 1，X 2，…，X n 称为线性规划的可行解，由所有可行解组成的集合称为可行解集合或可行域，若X=(X 1，X 2，…，X n )T使目标函数达到极值的可行解，称为最优解。

为了表述方便及深入研究线性规划，线性规划模型可表示为矩阵和向量形式：极大化(极小化)Z=CX , 满足 AX=(≦，≧)b, X ≧0; 或极大化(极小化)Z=CX 满足P 1X 1+P 2X 2+…+P n X n = (≦，≧)b, X ≧0 其中C=(C1，C 2， … ，C n )，X=(X 1，X 2，…，X n )T ，b=(b 1,b 2, …,b m )T ，P j =(a 1j ,a 2j , …a mj )Tj=1,2, …,na 11 a 12 …a 1nA= a 21 a 22 …a 2n =(P 1，P 2，…，P n ) ………………a m1 a m2 …a mn第二节线性规划的图解法线性规划的图解法是一种解析几何方法，它简单直观，有助于理解其基本概念和求解一般原理。

例4.求解线性规划 极大化Z=600X 1+700X 2 满足 X 1+2X 2≦160 X 1+ X 2≦120 3X 1+ X 2≦300 X 2≦60X 1， X 2 ≧0解：(1)在平面上建立直角坐标系O-X 1X 2，X 1为横轴，X 2为纵轴。

(2)找出可行域，由解析几何知识可知， X 1+2X 2≦160代表直线X 1+2X 2=160左下半平面， X 1+X 2≦120代表直线X 1+X 2=120左下半平面，3X 1+X 2≦300代表直线3X 1+X 2=300左下半平面，X 2≦60代表直线X 2=60下半平面， X 1≧0，X 2≧0表示第一象限，以上区域的公共部分D 即为可行域。

(3)在可行域中找最优解，将Z 视为参数，则Z=600X 1+700X 2可表示为以Z 为参数的一族平行线，X 2=(－600/700) X 1+(Z/700),其中同一条直线上任何一点都具有相同的Z 值，故称之为等值线。

当Z 值由小变大时，等值线沿其法线方向(垂直方向)向右上方移动，当移动到过X *点时，Z 值最大，因为若Z 值再增大，则等值线与可行域无交点，不满足约束条件。

初始等值线可选择一个适宜的Z 值，与可行域相交即可，比如Z=42000,故本例最优解为X *=(80,40)T ,最优值为Z *=76000例5：用图解法求解下列线性规划 (1)极大化Z=2X 1+2X 2满足 X 1-X 2≧1 -X 1+2X 2≦0 X ，X ≧0(2)极小化Z=2X 1+2X 2满足 X 1-X 2≧1-X 1+2X 2≦0 X 1，X 2 ≧0解：这两个问题约束条件相同，其可行域如图2-3所示，是个无界集，从图2-3中可看出无论Z 多大，Z=2X 1+2X 2总与D 相交，故Z 可无限增大，则(1)无最优解但有可行解，当Z 减少时目标函数等值线过X*点时，Z 值最小，即X *=(1,0)T 为(2)的最优解。

例6：求解线性规划 极大化Z=X 1+X 2 满足 X 1+X 2 ≦1 X 1+X 2 ≧2 X 1，X 2 ≧0 解:如图2-4所示,可行域为空集故不存在可行解也无最优解。

例7：在例4中将目标函数改为极大化Z=600X 1+600X 2其它不变，则极大化Z=600X 1+600X 2与X 1+X 2=120平衡,Z 由0变大时,等值线最后将与可行域D 的边X ﹡X (3)(X 1+X 2=120所形成的边)重合,故线段X ﹡X (3)上的每一点都是最优解,(图2-5)综上可知，两个变量的线性规划有以下特点：1)可行域可能是空集，也可能是有界凸多边形，或无界凸区域；2)当D 非空时，D 至少有一个极点(顶点)；3)当D 非空有界时，线性规划一定有最优解，且最优解必在D 的一个极点上得到；4)当线性规划的最优解不唯一时，那么必有无穷多个最优解；5)如果D 无界，则线性规划可能无最优解(例5(1))也可能有最优解(例5(2)). 以上结论对于n ≧2也成立，下节将论证。

第三节线性规划的标准型和解线性规划的图解法虽直观简便，但对于n ≧2时就无能为力。

下面介绍一种代数方法—单纯形法，为了以后便于讨论，先研究一下线性规划数学模型的标准型和解的基本性质。

对于一个具体的线性规划应先化为标准型再用单纯形法求解。

一、线性规划的标准型规定线性规划的标准型为：1极大化Z=C 1X 1+C 2X 2+…+C n X n ……… (2-10)满足a 11X 1+a 12X 2+…+a 1n X n =b 1 a 21X 1+a 22X 2+…+a 2n X n =b 2 … … … … … … …a m1X 1+a m2X 2+…+a mn X n =b m …… (2-11)X j ≧0 j=1,2, …,n………………(2-12)矩阵形式:Max Z=CX, 满足 AX=b, X ≧0.向量形式:MinZ=CX,满足P 1X 1+P 2X 2+…+P n X n =b,X ≧0 二、化标准型1)若目标函数为―MinZ=CX‖, 因为MinZ=﹣Max(﹣Z),令Z '=﹣Z=(﹣C)X,则目标函数变为Max Z '=(﹣C)X ， Z '值的相反数就是所求目标函数值。