下载文档原格式
第四章 线性规划的求解法当线性规划的变量和约束条件比较多，而初始基本可行解又不知道时，是不容易用尝试的方法得到初始基本可行解的，何况有可能基本可行解根本就不存在。
在此时，大M 法可能是应付此类情况的一个行之有效的算法。
§4.1 大M 法的原理当初始基本可行解不知道时，则1.，2.两个特点不能兼得，即下列两条件不能兼得： 1. 中心部位具有单位子块； 2. 右列元素非负；这时可以先用容许的运算使由列为非负，然后在中心部位人为添加一个单位子块。
如下例所述： 例4.1123123123123min 32..323624,,0z x x x s tx x x x x x x x x =-+++-=-+-=-≥ （4.1.1）列成表格：上述第三张表中人工增加了两个变量45,x x ，称为人工变量，即把原来的约束条件改为：1234123512345..323624,,,,0s tx x x x x x x x x x x x x +-+=-++=≥ （4.1.2） 式（4.1）和（4.2）的约束方程组并不同解，但（4.1）的解和（4.2）中450x x ==的解是相对应的。
只要找到以（4.2）为约束条件，且人工变量45,x x 均为自由变量的基本可行解，也就找到了（4.1）的基本可行解，于是，要设法迫使450x x ==。
以上途径通过修改（4.1）的目标函数来实现。
具体修改为：12345min 32z x x x Mx Mx =-++++ （4.1.3）其中M 为足够大的正数，然后以（4.2）为约束条件，求（4.3）的最小值。
只要45,x x 不为零，就一定为正数，于是目标函数的值就会增加它们和的M 倍。
由于M 为足够大的正数，所以只要原问题有基本可行解，就不会在45,x x 取正值时达到最小值。
本例中把表改为：通过运算使它具备第三个特点：底行相应于单位子块位置的元素为0，然后再严格按照单纯形法的步骤求解：由于M 为足够大的正数，所以-3-4M 应视为负数，故选它。
线性规划的理论与实例分析线性规划（Linear Programming，简称LP）是一种重要的运筹学工具，常常被应用于生产、物流、金融等领域中的优化问题。
本文将从理论和实例两个角度，介绍线性规划的基本概念、模型及求解方法。
一、线性规划的基本概念线性规划的基本概念包括决策变量、目标函数、约束条件等。
（一）决策变量决策变量是指影响问题结果的变量，通常用x1、x2、 (x)表示。
例如，生产线上的机器数量、产品的产量等都是决策变量。
（二）目标函数目标函数是指要最大化或最小化的某个指标，通常用z表示。
例如，最小化成本、最大化利润等都是目标函数。
（三）约束条件约束条件是指在问题求解中要满足的条件。
例如，不超过机器限制数量、满足生产需求等都是约束条件。
通常用不等式或等式形式表示。
二、线性规划的模型线性规划的一般形式可表示为：最大化或最小化目标函数：Z = c1x1 + c2x2 + … + cnxn约束条件：a11x1 + a12x2 + … + a1nxn ≤ b1a21x1 + a22x2 + … + a2nxn ≤ b2……am1x1 + am2x2 + … + amnxn ≤bm或x1, x2, … , xn ≥ 0 （非负性约束条件）其中，c1、c2、…、cn为各决策变量的系数，a11、a12、…、amn为各约束条件中各决策变量的系数，b1、b2、…、bm为约束条件的值，x1、x2、…、xn为决策变量，非负性约束条件也称为非负约束。
三、线性规划的求解方法线性规划有多种求解方法，这里主要介绍两种：单纯性法和对偶理论。
（一）单纯性法单纯性法是线性规划的一种基本算法，其实质是在各约束条件限制下寻找目标函数最大或最小值。
单纯性法基于以下两个原则：①某个极值点必定满足目标函数的所有约束条件；②各个变量所形成的可行解区域有限，且该区域的可行解点数有限。
单纯性法的具体过程如下：Step 1 建立初始单纯形表将约束条件转化为标准形式，即将约束条件化为”≤“的形式，并加入人工变量，得到初始单纯形表。
线性规划问题的两种求解⽅式线性规划问题的两种求解⽅式线性规划是运筹学中研究较早、发展较快、应⽤⼴泛、⽅法较成熟的⼀个重要分⽀，它是辅助⼈们进⾏科学管理的⼀种数学⽅法。
线性规划所研究的是：在⼀定条件下，合理安排⼈⼒物⼒等资源，使经济效果达到最好。
⼀般地，求线性⽬标函数在线性约束条件下的最⼤值或最⼩值的问题，统称为线性规划问题。
解决线性规划问题常⽤的⽅法是图解法和单纯性法，⽽图解法简单⽅便，但只适⽤于⼆维的线性规划问题，单纯性法的优点是可以适⽤于所有的线性规划问题，缺点是单纯形法中涉及⼤量不同的算法，为了针对不同的线性规划问题，计算量⼤，复杂繁琐。
在这个计算机⾼速发展的阶段，利⽤Excel建⽴电⼦表格模型，并利⽤它提供的“规划求解”⼯具，能轻松快捷地求解线性模型的解。
⽆论利⽤哪种⽅法进⾏求解线性规划问题，⾸先都需要对线性规划问题建⽴数学模型，确定⽬标函数和相应的约束条件，进⽽进⾏求解。
从实际问题中建⽴数学模型⼀般有以下三个步骤；1、根据所求⽬标的影响因素找到决策变量；2、由决策变量和所求⽬标的函数关系确定⽬标函数；3、由决策变量所受的限制条件确定决策变量所要满⾜的约束条件。
以下是分别利⽤单纯形法和Excel表格中的“规划求解”两种⽅法对例题进⾏求解的过程。
例题：某⼯⼚在计划期内要安排⽣产I、II两种产品，已知⽣产单位产品所需的设备台时分别为1台时、2台时，所需原材料A分别为4单位、0单位，所需原材料B分别为0单位、4单位，⼯⼚中设备运转最多台时为8台时，原材料A、B的总量分别为16单位、12单位。
每⽣产出I、II产品所获得的利润为2和3，问I、II两种产品的⽣产数量的哪种组合能使总利润最⼤？这是⼀个典型的产品组合问题，现将问题中的有关数据列表1-1如下：表1-1I II 限量设备 1 2 8台时原材料A 4 0 16单位原材料B 0 4 12单位所获利润 2 3⾸先对例题建⽴数学模型。
问题的决策变量有两个：产品I的⽣产数量和产品II的⽣产数量；⽬标是总利润最⼤；需满⾜的条件是：(1)两种产品使⽤设备的台时<= 台时限量值(2) ⽣产两种产品使⽤原材料A、B的数量<= 限量值(3)产品I、II的⽣产数量均>=0。
单纯形法的计算步骤例题
单纯形法是一种用于线性规划问题的求解方法，它通过不断地移动解空间中的顶点，逐步逼近最优解。
下面我将通过一个简单的例题来说明单纯形法的计算步骤。
考虑以下线性规划问题：
最大化目标函数Z = 3x1 + 4x2
约束条件：
2x1 + x2 <= 10
x1 + 2x2 <= 8
x1, x2 >= 0
首先，我们将这个线性规划问题转化为标准型，引入松弛变量将不等式约束转化为等式约束。
得到如下形式：
最大化目标函数Z = 3x1 + 4x2
约束条件：
2x1 + x2 + x3 = 10
x1 + 2x2 + x4 = 8
x1, x2, x3, x4 >= 0
然后，我们构建初始的单纯形表格，包括目标函数系数矩阵、系数矩阵、单位矩阵和右端常数向量。
初始单纯形表格如下：
基变量x1 x2 x3 x4 常数
x3 2 1 1 0 10
x4 1 2 0 1 8
Z -3 -4 0 0 0
接下来，我们通过单纯形法进行迭代计算，每次迭代都要找到一个入基变量和一个出基变量，然后更新单纯形表格，直到满足最优解的条件。
在这个例子中，我们不再继续举例，因为单纯形法的计算步骤较为复杂，需要逐步进行迭代计算。
希望这个简单的介绍对你有所帮助。
百度文库 - 让每个人平等地提升自我
1
线性规划求解的例子
1. 基于数学规划的数学建模：用不等式解法求解下列线性规划模型：
max64 240000 250000 0, 0Lxys.t. xyxyxy
2．基于数学规划的数学建模：某工厂在计划内要安排生产Ⅰ、Ⅱ、Ⅲ三种产品。
已知生产单位产品所需的设备台时及 A、 B 两种原材料的消耗以及工厂拥有的
资源总数如下表所示：
产品Ⅰ 产品Ⅱ 产品Ⅲ 资源总数
所需台时 10 20 30 1900
原料 A (km) 40 50 20 2600
原料 B (km) 30 40 50 2200
该工厂每生产一件产品Ⅰ可获利 2 万元，每生产一件产品Ⅱ可获利 3 万
元，每生产一件产品Ⅲ可获利 5万元。
现由于设备故障，不得不停止生产产品Ⅱ。问该厂如何安排生产计划可获利
最多？
3. 基于数学规划的数学建模：某工厂有资金9000元，用于购置新机器，可在A、
B两种机器中任意选购。已知机器A、B的购置费每台分别为2000元和4000元。
该厂维修能力只能维修7台机器B；若维修机器A，1台机器A折算为2台机器B。
已知1台机器A可增加产值6000元，1台B可增加产值4000元，问应购置机器
A、B各几台，才能使产值增加最多？
4. 基于数学规划的数学建模：下表为某建筑公司下属五个工程队作A、B、C、D、
E五项工程所化的时间，试分配各队工作（每队一项工程），使总时间最少。
工程队1 工程队2 工程队3 工程队4 工程队5
工程A 14 19 15 29 10
工程B 19 21 30 25 20
工程C 14 31 22 50 20
工程D 40 42 31 21 17
工程E 33 51 33 32 50
百度文库 - 让每个人平等地提升自我
2
习题1【分析与解答】
本线性规划模型的变量个数为2，基本约束条件个数也是2，两者相一致，
可用第一章第三节“数学建模实例”中介绍的不等式解法通过待定系数法求解。
要求64Lxy的最大值，即为找一个常数C，使得PC，且当PC时
相应的(,)xy存在而且符合限制条件。
考虑到限制条件：
240000xy， 250000xy
我们设
64(2)(2) (2)(2)Lxyaxybxyabxaby
其中,ab为待定系数。
于是26, 24abab，解得：28, 33ab。所以有：
28
64(2)(2)3328 400005000033 160000Pxyxyxy
。
.
当240000xy，且250000xy时，解得：20000, 10000.xy
又由于200000, 100000xy，所以当20000, 10000xy时，L取得
最大值160000。
习题2【分析与解答】
设需生产产品Ⅰ计x件，生产产品Ⅱ计y件（因为产品Ⅱ停止生产，0y），产品Ⅲ计z件，
于是有数学模型为：
max
25s.t. 10301900 40202600, 30502200 0, 0, Pxz
xzxzxzxzxz，
,
，均为整数
习题3【分析与解答】
（1）设购买机器A、B的台数分别为1x和2x台。根据这里的实际意义，
12
, xx
百度文库 - 让每个人平等地提升自我
3
只能取非负整数。可以建立的模型如下：
12
12
12
12
12
max =60004000s.t. 200040009000 27 0, x0, , Lxxxxxxxxx
为整数
（2）相应的松弛模型为：
12
12
12
12
max =60004000s.t. 200040009000 27 0, x0Lxxxxxxx
习题4【分析与解答】
本指派模型的工程队数与任务数n均为5；
引进25个变量,ijx，,1,2,,5ij，其意义是：当指派工程i由工程队j来
做时，,1ijx，否则,0ijx。数学模型可表示为
55
,,11,1,1(P) min 1 (1~5) () 1 (1~5) ()ijij
ijnijjnijiZcxs.t. xixj
每一项任务必有一工程队去完成
每个工程队做一件任务
费用矩阵（或效益矩阵）为,14191529101921302520()143122502040423121173351333250ijCc
这是一个指派模型。
注意：参考LINDO程序：
min
14x11+19x12+15x13+29x14+10x15
+19x21+21x22+30x23+25x24+20x25
+14x31+31x32+22x33+50x34+20x35
+40x41+42x42+31x43+21x44+17x45
+33x51+51x52+33x53+32x54+50x55
百度文库 - 让每个人平等地提升自我
4
.
x11+x12+x13+x14+x15=1
x21+x22+x23+x24+x25=1
x31+x32+x33+x34+x35=1
x41+x42+x43+x44+x45=1
x51+x52+x53+x54+x55=1
x11+x21+x31+x41+x51=1
x12+x22+x32+x42+x52=1
x13+x23+x33+x43+x53=1
x14+x24+x34+x44+x54=1
x15+x25+x35+x45+x55=1
end
int 25
参考结果：
可使得总时间最少为99（此时，仅有x13=x22=x31=x45=x54=1，在最优解
方阵中的其余元素全部为0，即可：指派工程A由工程队3来做；指派工程B
由工程队2来做；指派工程C由工程队1来做；指派工程D由工程队5来做；
指派工程E由工程队4来做）
