1 线性规划
线性规划问题及其数学模型
问题的提出
图解法
线性规划问题的标准型
线性规划问题的求解——单纯形法
基本概念
单纯形法
单纯形法计算机软件
线性规划应用举例
线材的合理利用问题
配料问题
连续投资问题
线性规划问题及其数学模型
问题的提出(一)
例 某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时和原料A、B的消耗量如下表。 该工厂每生产一件
产品Ⅰ可获利2元，每生产一件产
品Ⅱ可获利3元，问应如何安排生
产计划能使该厂获利最多？
这个问题可以用下面的数学模型来描述，设计划期内产品Ⅰ、Ⅱ的产量分别为x1，x2，可获利润用z表示，则有：
Max Z=2x1+3x2
x1+2x2≤8
4x1 ≤16
4x2≤12
x1, x2≥0
问题的提出(二)
例 靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m3，两工厂之间有一条流量为每天200万m3的支流（见图）。
第一化工厂每天排放污水2万m3，第二化工厂每天排放污水 万m3。污水从工厂1流到工厂2前会有20%自然净化。根据环保要求，河水中污水的含量应不大于%。而工厂1和工厂2处理污水的成本分别为1000元/万m3和800元/万m3。问两工厂各应处理多少污水才能使处理污水的总费用最低？
设工厂1和工厂2每天分别处理污水x1和x2万m3，则有：
Min z=1000x1+800x2
(2-x1)/500 ≤
[(2-x1)+-x2]/700
≤
x1≤2, x2≤
x1, x2≥0
问题的提出(三)
以上两例都有一些共同的特征：
⑴用一组变量表示某个方案，一般这些变量取值是非负的。
⑵存在一定的约束条件，可以用线性等式或线性不等式来表示。
⑶都有一个要达到的目标，可以用决策变量的线性函数来表示。
满足以上条件的数学模型称为线性规划模型。线性规划模型的一般形式如下：
线性规划问题及其数学模型
图解法
唯一最优解
无穷多最优解
x1
x2
x1
x2
解无界
无可行解
线性规划问题如果有最优解,则最优解一定在可行域的边界上取得,特别地,一定可在可行域的顶点上取得.
线性规划问题及其数学模型
线性规划问题的标准型
线性规划问题的标准型
max z=c1x1+c2x2++cnxn
a11x1+a12x2++a1nxn=b1
a21x1+a22x2++a2nxn=b2
am1x1+am2x2++amnxn=bm
x1, x2, , xn≥0
其中，bi≥0 (i=1,2,,m)
令xj= xj - xj，对模型中的进行变量代换。
不符合标准型的几个方面：
⑴目标函数为 min z=c1x1+c2x2++cnxn
令z=-z ,变为 max z= -c1x1- c2x2- -cnxn
⑵约束条件为 a11x1+a12x2++a1nxn≤b1
加入非负变量xn+1，称为松弛变量，有
a11x1+a12x2++a1nxn+xn+1=b1
⑶约束条件为 a11x1+a12x2++a1nxn≥b1
减去非负变量xn+1，称为剩余变量，有
a11x1+a12x2++a1nxn - xn+1=b1
⑷变量xj无约束。
线性规划问题的求解——单纯形法
基本概念
可行解 满足约束条件（包括非负条件）的一组变量值，称可行解。
所有可行解的集合称为可行域。
最优解 使目标函数达到最大的可行解称为最优解。
基本解 对于有n个变量、m个约束方程的标准型线性规划问题，取其m个变量。若这些变量在约束方程中的系数列向量线性无关，则它们组成一组基变量。确定了一组基变量后，其它n-m个变量称为非基变量。
令非基变量都为 0 ，解约束方程，可唯一得到基变量的值，从而得到一个满足约束方程的解，称为基本解。由此可见，一个基本解的非零分量个数不超过m个。
基本可行解 满足非负条件的基本解称为基本可行解。
基本可行解既是基本解、又是可行解，它对应于线性规划问题可行域的顶点。
线性规划问题的求解——单纯形法
单纯形法(一)
要找到线性规划问题的最优解，只要在基本可行解中寻找就可以了。虽然基本可行解的数目是有限个（不超过Cnm个），但当m,n较大时，要用“穷举法”求出所有基本可行解也是行不通的。因此，必须寻求一种更有效的方法。
单纯形法的基本思路是：从线性规划问题的一个基本可行解开始，转换到另一个使目标函数值增大的基本可行解。反复迭代，直到目标函数值达到最大时，就得到了最优解。
为了便于单纯形法的实施，我们用单纯形表来描述线性规划问题的一个基本可行解的情况。
不妨设x1,x2,…,xm组成一组基变量，且对应一个基本可行解。用高斯消去法把等式约束和目标函数变形为
x1 +a'1m+1xm+1+…+a'1nxn=b'1
x2 +a'2m+1xm+1+…+a'2nxn=b'2
… ………………………
xm+a'mm+1xm+1+…+a'mnxn=b'm
-z +σm+1xm+1+…+σnxn= -z0
把其系数列成数据表即单纯形表:
单纯形法(二)
按照单纯形法的思路求解线性规划问题, 要解决三个技术问题:⑴给出第一个基本可行解; ⑵检验一个基本可行解是否是最优解; ⑶转换到另一个基本可行解.
⑴把线性规划问题变成标准型后, 观察是否每个约束方程中都有独有的、系数为1的变量. 如果是,则取这些变量作为基变量,变得到一个基本可行解; 否则,就给没有这种变量的约束条件添加一个人工变量,同时修改目标函数. (见例题)
⑵如果单纯形表最后以行中的σj都满足 σj≤0, 则对应的基本可行解是最优解; 否则就不是最优解. σj称为检验数.
⑶第一,确定换入变量. 在大于0的检验数中找最大的为σk, 对应变量xk为换入变量. 第二,确定换出变量. 取θ=min{bi/a‘ik|a’ik>0}=bl/a’lk, 对应的第l行的基变量为换出变量. 第三, 旋转运算. 换入变量所在的行与换出变量所在的列交叉点的元素称为中心元素,用高斯削去法把中心元素化成1, 同列的其他元素化成0, 得到一个新的单纯形表,也就得到一个新的基本可行解.
单纯形法(三)
用单纯形法求解线性规划问题的具体步骤如下：
①找出初始可行基，确定初始基本可行解，建立初始单纯形表；转②。
②检验对应于非基变量的检验数σj。若σj≤0（xj为非基变量）都成立，则当前单纯形表对应的基本解就是最优解，停止计算；否则转③。
③在所有σj>0中，若有一个σk对应的xk的系数a'ik≤0 (i=1,2,…,m)，则此问题为无界解（无解），停止计算；否则转④。
④根据 max（σj>0）=σk 确定xk为换入变量；根据θ规则 θ＝min{b'i/a'ik｜1≤i≤m, a'ik>0}＝b'l/a'lk
确定相应的换出变量，并得到中心元素a'lk。转⑤。
⑤以a‘lk为枢轴元素进行转轴运算，得到新的单纯形表。转②.
用单纯行法求解线性规划问题后，应回答下面几个问题：
⑴是否解无界？上面的步骤已作出回答。
⑵是否无可行解？求解后，若人工变量都已取0，则有可行解；否则，无可行解。
⑶唯一最优解还是无穷多最优解？在最后的单纯形表中，若所有非基变量的检验数都严格小于0，则为唯一最优解；若存在某个非基变量的检验数等于0，则有无穷多最优解。
单纯形法(四)
Max z=2x1+3x2
x1+2x2+x3 =8
4x1 +x4 =16
4x2 +x5=12
x1, x2, x3 ,x4,x5≥0
此问题的最优解为:
x1*=4, x2*=2, x5*=4, x3*= x4*= x1*=0, z*=24+32=14
例
Max z=2x1+3x2
x1+2x2 ≤ 8
4x1 ≤ 16
4x2 ≤ 12
x1, x2 ≥0
单纯形法(五)
例
Min z= -3x1 +x2 +x3
x1 -2x2+x3 ≤11
-4x1 +x2 +2x3 ≥3
-2x2 + x3=1
x1, x2, x3 ≥0
Max z'= 3x1 -x2 -x3 -M x6 -Mx7
x1 -2x2 +x3 +x4 =11
-4x1 +x2+2 x3 -x5 +x6 =3
-2x1 +x3 +x7 =1
x1, x2, x3, x4, x5, x6, x7≥0
x6, x7称为人工变量
此问题的最优解为:
x1*=4, x2*=1, x3*= 9,
x4*= x5*= x6*= x7*= 0,
z*= -34+9+1= -2
用计算机软件求解线性规划问题
关于线性规划问题的求解，有许多好的专业软件和商务软件，通过计算机可十分方便地完成求解过程。最简便易行的求解软件是Excel，下面介绍其使用方法。
（1）建立Excsl工作表。用 一组单元格表示变量，作为可变单元格（空）；用几组单元格分别表示各约束条件和目标函数的系数；用一些单元格输入公式表示各组系数和变量的关系。
（2）打开工具栏中的“规划求解”对话框，指定存有目标函数的单元格为目标单元格，指定表示变量的单元格为可变单元格，建立约束条件。
（3）在规划求解对话框中按下“求解”按钮，即可求出最优解和最优值。推出规划求解对话框。
应用举例(一)
解 先看有多少种裁料方案，再进行组合和选择。方案：
例 合理利用线材问题
现要做一百套钢管, 每套要长为、和的钢管各一根。已知原料长，问应如何下料，使用的原料最省。
设用方案Ⅰ,Ⅱ,…,Ⅷ分别裁原料钢管x1,x2,
…,x8根, 则：
Min z= x1+ x2+ x3+x4+ x5+x6+x7+x8
2x1+ x2+x3 + x4 ≥ 100
2x2+x3+ 3x5 +2x6+ x7 ≥ 100
x1+ x3 +3x4 +2x6+3x7+4x8≥ 100
x1, x2, x3, x4, x5 ,x6, x7, x8 ≥0
例 某工厂要用三种原材料C,P,H混合调配出三种不同规格的产品A,B,D。已知产品的规格要求、单价和原料的供应量、单价如下表。该厂应如何安排生产，能使利润最大？
应用举例(二）
根据产品要求有：
AC≥, AP≤
BC≥, BP≤
AC+AP+AH=A
BC+BP+BH=B
根据原料供应量有：
AC+BC+DC≤100
AP+BP+DP≤100
AH+BH+DH≤60
设AC,AP,,DH分别为x1,x2,,x9，有
Max z=50(x1+x2+x3)+35(x4+x5+x6)
+25(x7+x8+x9) - 65(x1+x4+x7)
- 25(x2+x5+x8) - 35(x3 +x6 +x9)
x1≥(x1+ x2+ x3)
x2 ≤(x1+ x2+ x3)
x4 ≥(x4+ x5+ x6)
x5 ≤(x4+ x5+ x6)
x1+ x4+ x7≤100
x2+ x5+ x8≤100
x3+ x6+ x9≤60
xj≥0, j=1,2,3,4,5,6,7,8,9
解：记产品A,B,D中C,P,H的含量分别为AC,AP,AH,BC,BP,BH,DC,DP,DH。
应用举例（三）
例 成批生产企业年度生产计划的按月分配。
在年度计划按月分配时一般要考虑：①从数量和品种上保证年度计划的完成；②成批的产品尽可能集中在几个月内生产；③由于技术方面的原因，某些产品在某个月后才能生产；④某些产品要求年初交货；⑤批量小的产品尽量集中在一个或几个月内生产出来，以便减少各月内的品种数量。考虑以上条件，使设备负荷均衡并使利用率最大化。
假定工厂有m类设备，用i表示(i=1,2,…,m)；生产n种产品，用j表示(j=1,2,…,n)。各产品的全年计划量用dj表示。
用aij表示加工单位j种产品所需要的第i类设备的台时数，bik表示k月份第i类设备的生产能力(台时)(k=1,2,…,12)。
再假定第5、8两种产品下半年投产，第4号产品要求二月底前完成全年计划。
如要对全年12个月同时考虑，会使模型非常复杂，我们根据上述条件从1月到12月份，一个月一个月地分别建模计算。设k月份计划生产j种产品的数量为xjk。
一月份模型为：
m n m
Max z=( aijxj1) (bi1)
i=1 j=1 i=1
n
aijxj1≤bi1 (i=1,2,…,m)
j=1
xj1≤dj (j=1,2,…,n)
x51=x81=0
xj1≥0 (j=1,2,…,n)
二月份模型为：
m n m
Max z=( aijxj2) (bi2)
i=1 j=1 i=1
n
aijxj2≤bi2 (i=1,2,…,m)
j=1
xj2≤dj-xj1 (j=1,2,…,n)
x52=x82=0
xj2≥0 (j=1,2,…,n)
应用举例(四)
例 连续投资问题。某单位有资金10万元，在今后5年内可考虑下列投资项目，已知：
项目A：从第1到第4年每年初可投资，并于次年末回收本利115%；
项目B：第3年初需要投资，到第5年末回收本利125%，但最大投资额不超过4万元；
项目C：第2年初需要投资，到第5年末能回收本利140%，但最大投资额不超过3万元；
项目D：5年内每年初可购买公債，当年末回收本利106%。
问它应该如何安排每年的投资，使到5年末拥有的资金最多？
x2A+x2C+x2D=
解：每年的投资额应不超过手中的资金。由于项目D每年都可投资，且当年末就可收回。所以该单位每年必然把资金全部投出去，即投资额等于手中的资金数。
设第i年投资各项目的资金为xiA,xib,xiC,xiD 。数学模型为：
Max z=+++
x1A+x1D=10
x3A+x3B+x3D=+
x4A+x4D=+
x5D=+
xiA,xib,xiC,xiD≥0
