1 / 77
十万种考研考证电子书、题库视频学习平台 圣才电子书
第1章 线性规划与单纯形法
1.1 用图解法求解下列线性规划问题，并指出问题是具有惟一最优解、无穷多最优解、
无界解还是无可行解?
（1）
12max3 zxx
12
12
2
1251050
1
..
4
,0xx
xx
st
x
xx
解：如图l-1所示，该问题的可行域为有界域。目标函数
123zxx在点A3处取得最
大值，求解方程组
12
251050
4xx
x
可得A3的坐标为(2，4)，所以**(2,4),14TXz，该线性规划问
题具有惟一最优解。
（2）
12min1.5 zxx
12
12
1233
..2
,0xx
stxx
xx
解：如图1-2所示，该线性规划问题的可行域无界。目标函数
121.5zxx在点A处
取得最小值，求解方程组12
1233
2xx
xx
得A点的坐标为3/2,1/2，所以*3/2,1/2X，
2 / 77
十万种考研考证电子书、题库视频学习平台 圣才电子书
*9/4z，该问题具有惟一最优解。
（3）
12max22 zxx
12
12
121
..0.52
,0xx
stxx
xx
解：如图1-3所示，该问题的可行域无界。目标函数可以增加到无穷大，因此该问题
无最优解或称为无界解。
（4）
12max zxx
12
12
120
..33
,0
x
x
stxx
xx
解：如图l-4所示，该问题的可行域为空集，因此该线性规划无可行解。
3 / 77
十万种考研考证电子书、题库视频学习平台 圣才电子书
1.2 将下列线性规划问题变换成标准型，并列出初始单纯形表。
（1）
1234min3425 zxxxx
1234
第三章运输问题
一、学习目的与要求
1、掌握表上作业法及其在产销平衡运输问题求解中的应用
2、掌握产销不平衡运输问题求解方法
二、课时 6学时
第一节 运输问题及其数学模型
一、运输问题的数学模型
单一品种运输问题的典型情况：设某种物品有m个产地A1,A2,…,Am，各产地的产量分别是a1,a2,…,am；有N个销地B1,B2,…,Bn，各销地地销量分别为b1,b2,…,bn。假定从产地Ai(i=1,2, …,m)向销地Bj(j=1,2,…,n)运输单位物品的运价是cij，问怎样调运这些物品才能使总运费最小
为直观清楚起见，列出运输表：
销地
产地
B1 B2 … Bn 产量
A1 c11 c12 c1n
a1
x11 x12 x1n
A2 c21 c22 c2n
a2
x21 x22 x2n
… c11 c12 c1n
…
x11 x12 x1n
Am cm1 cm2 cmn
am
xm1 Xm2 xmn
销量 b1 b2 … bn
表中xij为由产地Ai到销地Bj的物品数量，cij表示产地Ai到销地Bj的单位运价。
如果运输问题的总产量等于其总销量，即有
njjmiiba11
则称该运输问题为产销平衡运输问题；反之，称为产销不平衡运输问题。
产销平衡运输问题的数学模型如下： 0,...,2,1,...,2,1..min11111ijmijijnjiijminjijijxnjbxmiaxtsxcz
这就是运输问题的数学模型，它包含m×n个变量，(n十m)个约束方程．其系数矩阵的结构比较松散，且特殊。
二、运输问题数学模型的特点
1、运输问题有有限最优解，即必有最优基本可行解
2、运输问题约束条件的系数矩阵A的秩为(m+n-1)
该系数矩陈中对应于变量xij的系数向量pij，其分量中除第i个和第m十j个为1以外，其余的都为零．即
第三章——1 第三章 运输问题
在生产实际中，经常需要将某种物资从一些产地运往一些销地，因而存在如何调运使总的运费最小的问题。这类问题一般可用线性规划模型来描述，当然可以用单纯形法求解。但由于其模型结构特殊，学者们提供了更为简便和直观的解法——表上作业法。此外，有些线性规划问题从实际意义上看，并非运输问题，但其模型结构类似运输问题，也可以化作运输问题进行求解。
第一节 运输问题及其数学模型
首先来分析下面的问题。
例3.1 农产品经销公司有三个棉花收购站，向三个纺织厂供应棉花。三个收购站A 1、A2、A3的供应量分别为50kt、45kt和65kt，三个纺织厂B1、B2、B3的需求量分别为20kt、70kt和70kt。已知各收购站到各纺织厂的单位运价如表3—1所示（单位：千元/kt），问如何安排运输方案，使得经销公司的总运费最少？
表3—1
纺织厂
收购站 B1 B2 B3
A1
A2
A3 4
6
2 8
3
5 5
6
7
设xij表示从Ai运往Bj的棉花数量，则其运输量表如下表所示。
表3—2
纺织厂
收购站 B1 B2 B3 供应量（kt）
A1
A2
A3 x11
x21
x31 x12
x22
x32 x13
x23
x33 50
45
65
需求量（kt） 20 70 70 160
由于总供应量等于总需求量，因此，一方面从某收购站运往各纺织厂的总棉花数量等该收购站的供应量，即
x11+x12+x13 = 50
x21+x22+x23 = 45
x31+x32+x33 = 65 第三章——2 另一方面从各收购站运往某纺织厂的总棉花数量等该纺织厂的需要量，即
x11+x21+x31 = 20
x12+x22+x32 = 70
x13+x23+x33 = 70
因此有该问题的数学模型为
min f= 4x11+8x12+5x13+6x21+3x22+6x23+2x31+5x32+7x33
00运输问题
运输问题（transportation problem）一般是研究把某种商品从若干个产地运至若干个销地而使总运费最小的一 类问题。然而从更广义上讲，运输问题是具有一定模型特征的线性规划问题。它不仅可以用来求解商品的调运问题，还可以解决诸多非商品调运问题。运输问题是一种特殊的线性规划问题，由于其技术系数矩阵具有特殊的结构，这就有可能找到比一般单纯形法更简便高效的求解方法，这正是单独研究运输问题的目的所在。 §1运输问题的数学模型 [例4-1] 某公司经营某种产品，该公司下设A、B、C三个生产厂，甲、乙、丙、丁四个销售点。公司每天把三个工厂生产的产品分别运往四个销售点，由于各工厂到各销售点的路程不同，所以单位产品的运费也就不同案。各工厂每日的产量、各销售点每日的销量，以及从各工厂到各销售点单位产品的运价如表4-1所示。问该公司应如何调运产品，在满足各销售点需要的前提下，使总运费最小。 表4-1 甲 乙 丙 丁 产量（ai） A 3 11 3 10 7 B 1 9 2 8 4 C 7 4 10 5 9 销量（bj） 3 6 5 6 设代表从第个产地到第个销地的运输量（；），用代表从第个产地到第个销地的运价，于是可构造如下数学模型：
（；运出的商品总量等于其产量） 00 （；运来的商品总量等于其销量） 通过该引例的数学模型，我们可以得出运输问题是一种特殊的线性规划问题的结论，其特殊性就在于技术系数矩阵是由“1”和“0”两个元素构成的。 将该引例的数学模型做一般性推广，即可得到有个产地、个销地的运输问题的一般模型。注意：在此仅限于探讨总产量等于总销量的产销平衡运输问题，而产销不平衡运输问题将在本章的后续内容中探讨。
（；运出的商品总量等于其产量） （；运来的商品总量等于其销量） 供应约束确保从任何一个产地运出的商品等于其产量，需求约束保证运至任何一个销地的商品等于其需求。除非负约束外，运输问题约束条件的个数是产地与销地的数量和，即；而决策变量个数是二者的积，即。由于在这个约束条件中，隐含着一个总产量等于总销量的关系式，所以相互独立的约束条件的个数是个。 §2运输问题的求解 运输问题的求解采用表上作业法，该方法是单纯形法求解运输问题的一种特定形式，其实质是单纯形法。既然表上作业法是一种特定形式的单纯形法，它自然与单纯形法有着完全相同的解题步骤，所不同的只是完成各步采用的具体形式。表上作业法的基本步骤可参照单纯形法归纳如下： 1． 找出初始基可行解：即要在阶产销平衡表上给出“”个数字格（基变量）； 2． 求各非基变量（空格）的检验数，判断当前的基可行解是否是最优解，如已得到最优解，则停止计算，否则转到下一步；
