单纯形法在线性规划中的应用
摘要
求解线性规划问题，就是在各项资源条件的限制下，如何确定方案，使预期的目标达到最优。本文重点介绍了求解线性规划问题目前最常见的两种方法，图解法和单纯形法。图解法适合于只含两个变量的线性规划问题，文中只做了简单的描述。而单纯形法是求解线性规划问题的通用方法，适合于求解大规模的线性规划问题，本文作了重点描述，对单纯形法中的基本概念如基变量、非基变量、基向量、非基向量、可行基以及基本可行解等概念作了详细的陈述，在此基础上，介绍了线性规划问题的标准化、单纯形法的基本原理、确定初始可行解、最优性检验、解的判别、基本可行解的改进、换入变量的确定-最大增加原则、换出变量的确定-最小比值原则、表格单纯形法、大M法、两阶段法等。
关键词：线性规划图解法单纯形法基变量基向量可行基基本可行解
正文
引言
在生产管理和经济活动中，经常遇到这些问题，如生产计划问题，即如何合理利用有限的人、财、物等资源，以便得到最好的经济效果；材料利用问题，即如何下料使用材最少；配料问题，即在原料供应量的限制下如何获取最大利润；劳动力安排问题，即如何用最少的劳动力来满足工作的需要；运输问题，即如何制定调运方案，使总运费最小；投资问题，即从投资项目中选取方案，使投资回报最大等等。对于这些问题，都能建立相应的线性规划模型。事实上，线性规划就是利用数学为工具，来研究在一定条件下，如何实现目标最优化。
解线性规划问题目前最常见的方法有两种，图解法和单纯形法。单纯形法是求解线性规划问题的通用方法。
1 线性规划问题的求解方法
1.1 图解法解线性规划问题
只含两个变量的线性规划问题，可以通过在平面上作图的方法求解，步骤如下：
(1)以变量x
1为横坐标轴，x
2
为纵坐标轴，适当选取单位坐标长度建立平面
坐标直角坐标系。由变量的非负性约束性可知，满足该约束条件的解均在第一象限内。
(2)图示约束条件，找出可行域（所有约束条件共同构成的图形）。
(3)画出目标函数等值线，并确定函数增大（或减小）的方向。
(4)可行域中使目标函数达到最优的点即为最优解。
然而，图解法虽然直观、简便，但当变量数多于三个以上时，其实用意义不大。
1.2 单纯形法解线性规划问题
它的理论根据是：线性规划问题的可行域是 n 维向量空间Rn 中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。
单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。
单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。
1.3 线性规划问题的标准化
使用单纯形法求解线性规划时，首先要化问题为标准形式 所谓标准形式是指下列形式：
∑==
n
j j j
x c
z 1
max
?????=≥==??∑=),,2,1(0),,1(1n j x m i b x a t s j
n
j i j ij
当实际模型非标准形式时，可以通过以下变换化为标准形式： ①当目标函数为∑==n
j j j x c z 1min 时，可令Z ′=-Z ，而将其写成为
∑=-='n
j j j x c z 1
min
求得最终解时，再求逆变换Z=-Z ′即可。
②当s ·t ·中存在i n in i i b x a x a x a ≤+++ 2211形式的约束条件时，可引进变量
??
?≥+++-=++0)
(1
22111n n in i i i n x x a x a x a b x 便写原条件成为
??
?≥=++++++0
112211n i
n n in i i x b x x a x a x a 其中的x n +1称为松驰变量，其作用是化不等式约束为等式约束。
同理，若该约束不是用“≤”号连接，而是用“≥”连接，则可引进松驰变量
??
?≥-+++=++0)(1
22111n i
n in i i n x b x a x a x a x 使原条件写成
??
?≥=-++++0
1111n i
n n in i x b x x a x a 2 单纯形法
2.1单纯形法的基本原理
单纯形法迭代原理： （1） 确定初始可行解
① 当线性规划问题的所有约束条件均为≤号时，松弛变量对应的系
数矩阵即为单位矩阵，以松弛变量为基变量可确定基可行解。 ② 对约束条件含≥号或=号时，可构造人工基，人为产生一个m ×m
单位矩阵用大M 法或两阶段法获得初始基可行解。
（2） 最优性检验与解的判别（目标函数极大型）
① 当所有变量对应的检验数均非正时，现有的基可行解即为最优解。
若存在某个非基变量的检验数为零时，线性规划问题有无穷多最
优解；当所有非基变量的检验数均严格小于零时，线性规划问题具有唯一最优解。
② 若存在某个非基变量的检验数大于零，而该非基变量对应的系数
均非正，则该线性规划问题具有无界解（无最优解）。
③ 当存在某些非基变量的检验数大于零，需要找一个新的基可行解，
基要进行基变换。
2.1 确定初始可行解
确定初始的基本可行解等价于确定初始的可行基，一旦初始的可行基确定了，那么对应的初始基本可行解也就唯一确定，为了讨论方便，不妨假设在标准型线性规划中，系数矩阵Ａ中前m 个系数列向量恰好构成一个可行基，即Ａ=（ＢＮ），其中Ｂ=（Ｐ1，Ｐ2，…Ｐm ）为基变量x1，x2，…xm 的系数列向量构成的可行基，Ｎ=(Ｐm+1，Pm+2， …Pn)为非基变量xm+1，xm+2， …xn 的系数列向量构成的矩阵。
所以约束方程AX=b 就可以表示为B B N N X AX=(BN)=BX +NX =b X ??
???
用可行基Ｂ的逆阵Ｂ-1左乘等式两端，再通过移项可推得：-1-1B N X =B b-B NX 若令所有非基变量N X =0，则基变量-1B X =B b
由此可得初始的基本可行解1B b X=0-?? ???
2.2 最优性检验
假如已求得一个基本可行解1B b X=0-??
???，将这一基本可行解代入目标函数，
可求得相应的目标函数值1-1
B N B B b Z=CX=(
C C )=C B b 0-?? ???
其中B 12m N m+1m+2
n C =(c ,c ,c ), C =(c ,c ,c ) 分别表示基变量和非基变量所对
应的价值系数子向量。
要判定-1B Z=C B b 是否已经达到最大值，只需将-1-1B N X =B b-B NX 代入目标函数，使目标函数用非基变量表示，即：
B B N N -1-1B B N N B N N N
X Z=CX=(C C )X =C X +C X =C (B b-B NX )+C X ??
?
??
m+1m+2-1-1B N N B m+1,m+1,n n x x
C B b+σX C B b+(σσσ)x ?? ? ?= ? ???
其中-1N N B m+1m+1n =C -C B N=(,,)σσσσ 称为非基变量ＸN 的检验向量，它的各个分量称为检验数。若σN 的每一个检验数均小于等于0，即σN ≤0，那么现在的基本可行解就是最优解。
2.3 解的判别
定理1：最优解判别定理
对于线性规划问题{}n maxZ=CX,D=X R /AX=b,X 0∈≥，若某个基本可行解所对应的检验向量-1N N B =C -C B N 0σ≤，则这个基本可行解就是最优解。
定理2：无穷多最优解判别定理
若1B b X=0-?? ???是一个基本可行解，所对应的检验向量-1
N N B =C -C B N 0σ≤，其
中存在一个检验数σm+k=0，则线性规划问题有无穷多最优解。
定理3：无最优解判别定理
若1B b X=0-?? ???是一个基本可行解，有一个检验数m+k 0σ>，但是-1
m+k B P 0≤，
则该线性规划问题无最优解。
2.4 基本可行解的改进
如果现行的基本可行解Ｘ不是最优解，即在检验向量-1N N B =C -C B N σ中存在
正的检验数，则需在原基本可行解Ｘ的基础上寻找一个新的基本可行解，并使目标函数值有所改善。具体做法是：
（1）先从检验数为正的非基变量中确定一个换入变量，使它从非基变量变成基变量（将它的值从零增至正值）。
（2）再从原来的基变量中确定一个换出变量，使它从基变量变成非基变量（将它的值从正值减至零）。
由此可得一个新的基本可行解，由m+1m+2-1B m+1,m+1,n n x x Z C B b+(σσσ)x ??
? ?
= ? ???
可知，
这样的变换一定能使目标函数值有所增加。 2.4.1 换入变量的确定-最大增加原则
把基检验数大于0的非基变量定为入基变量。若有两个以上的σj ＞0，则选其中的σj 最大者的非基变量为入基变量。
从最优解判别定理知道，当某个σj ＞0时，非基变量x j 变为基变量不取零值可以使目标函数值增大，故我们要选基检验数大于0的非基变量换到基变量中去（称之为入基变量）。若有两个以上的σj ＞0，则为了使目标函数增加得更大些，一般选其中的σj 最大者的非基变量为入基变量。
2.4.2 换出变量的确定-最小比值原则
把已确定的入基变量在各约束方程中的正的系数除以其所在约束方程中的常数项的值，把其中最小比值所在的约束方程中的原基变量确定为出基变量。
即若
lk l
ik ik i k a b
a a
b x =??????>=0|min
则应令xl 出基。其中bi 是目前解的基变量取值，aik 是进基变量xk 所在列的各个系数分量，要求仅对正分量做比，（这由前述作法可知，若aik ≤0，则对应的xi 不会因xk 的增加减值而成为出基变量）。
2.5 表格单纯形法
在单纯形法的求解过程中，有下列重要指标：
（1）每一个基本可行解的检验向量-1N N B σ=C -C B N ，根据检验向量可以确定所求得的基本可行解是否为最优解。如果不是最优又可以通过检验向量确定合适的换入变量。
（2）每一个基本可行解所对应的目标函数值 1B Z=C B b ，通过目标函数值可以观察单纯形法的每次迭代是否能使目标函数值有效地增加，直至求得最优目标函数为止。
在单纯形法求解过程中，每一个基本可行解Ｘ都以某个经过初等行变换的约束方程组中的单位矩阵Ι为可行基。
当Ｂ=Ｉ时，Ｂ-1=Ｉ，易知：N N B σ=C -C N ，B Z=C b
可将这些重要结论的计算设计成如下一个简单的表格，即单纯形表来完成： C
C B
C N
θ C B X B b X 1 X 2 … X m
X m+1 X m+2 … X n
C 1 C 2 ﹕ C m
X 1 X 2 ﹕ X m
b 1 b 2 ﹕ b m
I
N
θ1 θ
2
﹕ θ
m
Z
C B b
C-C B N
2.6 大M 法
大M 法首先将线性规划问题化为标准型。如果约束方程组中包含有一个单位矩阵I ，那么已经得到了一个初始可行基。否则在约束方程组的左边加上若干个非负的人工变量，使人工变量对应的系数列向量与其它变量的系数列向量共同构成一个单位矩阵。以单位矩阵为初始基，即可求得一个初始的基本可行解。
为了求得原问题的初始基本可行解，必须尽快通过迭代过程把人工变量从基变量中替换出来成为非基变量。为此可以在目标函数中赋予人工变量一个绝对值
很大的负系数-Ｍ。这样只要基变量中还存在人工变量，目标函数就不可能实现极大化。
以后的计算与单纯形表解法相同，Ｍ只需认定是一个很大的正数即可。假如在单纯形最优表的基变量中还包含人工变量，则说明原问题无可行解。否则最优解中剔除人工变量的剩余部分即为原问题的初始基本可行解。
2.7 两阶段法
用大M法求解含人工变量的LP时，用手工计算不会碰到麻烦，但用电子计算机求解时，对M就只能在计算机内输入一个机器最大字长的数字，这就可能造成一种计算上的误差，为克服这个困难，对添加人工变量后的LP分两个阶段来计算，称为两阶段法。
第一阶段：不考虑原问题是否存在基可行解，给原LP加入人工变量，并构造仅含人工变量的目标函数Minw,然后用单纯形法求解，若得w=0，说明原LP 存在基可行解，可进行第二阶段计算，否则，停止计算。
第二阶段：将第一阶段计算得到的最终单纯形表除去人工变量，将目标函数行的系数换成原LP的目标函数，作为第二阶段计算的初始表。然后按照前面的方法进行计算。
参考文献
1习在筠，刘桂真，宿法，马建华，运筹学（第三版），2006年9月
上机实验报告 一、实验目的和要求 1、目的： ●掌握单纯形算法的计算步骤，并能熟练使用该方法求解线性规划问题。 ●了解算法→程序实现的过程和方法。 2、要求： ●使用熟悉的编程语言编制单纯形算法的程序。 ●独立编程，完成实验，撰写实验报告并总结。 二、实验内容和结果 1、单纯形算法的步骤及程序流程图。 （1）、算法步骤
（2）、程序图 各段代码功能描述： （1）、定义程序中使用的变量 #include
float b[m]; /*用于存储常约束条件中的常数*/ float CB[m]; /*用于存储基变量的系数*/ float seta[m]; /*存放出基与入基的变化情况*/ float delta[n]; /*存储检验数矩阵*/ float x[n]; /*存储决策变量*/ int num[m]; /*用于存放出基与进基变量的情况*/ float ZB=0; /*记录目标函数值*/ （2）、定义程序中使用的函数 void input(); void print(); int danchunxing1(); int danchunxing2(int a); void danchunxing3(int a,int b); (3)、确定入基变量，对于所有校验数均小于等于0，则当前解为最优解。 int danchunxing1() { int i,k=0; int flag=0; float max=0; for(i=0;i 简单的线性规划应用题解析 1．某人有楼房一幢，室内面积共180㎡,拟分隔两类房间作为旅游客房．大每间面积为18㎡，可住游客5名，每名游客每天住宿费为40元；小房间每间面积为15㎡，可住游客3名，每名游客每天住宿费为50元；装修大房间每间需1000元，装修小房间每间需600元．如果他只能筹款8000元用于装修，且游客能住满客房，他应隔出大房间和小房间各多少间，能获得最大收益？ 设应隔出大、小房间分别为x ,y 间，此时收益为z 元，则 1815180 1000600800000 x y x y x y +≤??+≤? ? ≥??≥? 200150z x y =+ 将上述不等式组化为 6560 534000 x y x y x y +≤??+≤? ? ≥??≥? 作出可行域，如图⑴，作直线l:200x+150y=0,即l:4x+3y=0. 将直线l 向右平移，得到经过可行域的点B ，且距原点最远的直线l 1. 解方程组 6560 5340 x y x y +=?? +=? 图⑴ 得最优解 20 7 60 7 2.9 8.6 x y =≈ ? ? =≈ ? 但是房间的间数为整数，所以，应找到是整数的最优解． ①当x=3时，代入5x+3y=40中，得401525 338 y- ==>，得整点（3，8），此时z=200×3＋150×8=1800（元）; ②当x=2时,代入6x+5y=60中，得601248 559 y- ==>，得整点（2，9），此时z=200×2＋150×9=1750（元）； ③当x=1时,代入6x+5y=60中，得60654 5510 y- ==>，得整点（1，10）,此时z=200×1＋150×10=1700（元）； ④当x=0时,代入6x+5y=60中，得60 512 y==，得整点（0，12），此时 z=150×12=1800（元）． 由上①～④知，最优整数解为（0，12）和（3，8）． 答：有两套分隔房间的方案：其一是将楼房室内全部隔出小房间１２间；其二是隔出大房间３间，小房间８间，两套方案都能获得最大收益为１８００元． 2．某家具厂有方木料90m3,五合板60㎡，准备加工成书桌和书橱出售．已知生产每张书桌需要方木料0.1 m3、五合板2㎡，生产每个书橱需要方木料0.2 m3、五合板1㎡，出售一张书桌可获得利润80元，出售一个书橱可获得利润120元．如果只安排生产书桌，可获利润多少？如果只安排生产书橱，可获利润多少？怎样安排生产可使所得利润最大？ 【解析】将已知数据列成下表: 用完五合板，此时获利润为80×300=24000（元）； ⑵只生产书橱因为90÷0.2=450，600÷1=600，所以，可产生450个书橱，用完方木料.此时获利润为120×450=54000（元）； 《简单的线性规划问题》教学设计 （人教A版高中课标教材数学必修5第三章第3.3.2节） 祁东二中谭雪峰 一、内容与内容解析 本节课是《普通高中课程标准实验教科书数学》人教A版必修5第三章《不等式》中第3.3.2《简单的线性规划问题》的第一课时. 本课内容是线性规划的相关概念和简单的线性规划问题的解法． 线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法.本节内容是在学习了不等式和直线方程的基础上，利用不等式和直线方程的有关知识展开的.简单的线性规划指的是目标函数含两个自变量的线性规划，其最优解可以用数形结合方法求出.简单的线性规划关心的是两类问题：一是在人力、物力、资金等资源一定的条件下，如何使用它们来完成最多的任务；二是给定一项任务，如何合理规划，能以最少的人力、物力、资金等资源来完成. 本节内容蕴含了丰富的数学思想方法，突出体现了优化思想、数形结合思想和化归思想. 通过这一部分的学习，使学生进一步了解数学在解决实际问题中的应用，体验数形结合和转化的思想方法，培养学生学习数学的兴趣、应用数学的意识和解决实际问题的能力. 二、教学目标 一）、知识目标 1.了解线性规划的意义、了解线性约束条件、线性目标函数、可行解、可行域、最优解等基本概念. 2.理解线性规划问题的图解法 3. 会用图解法求线性目标函数的最优解. 二）、能力目标 1.在应用图解法解题的过程中培养学生的观察能力、理解能力. 2.在变式训练的过程中，培养学生的分析能力、探索能力. 3.培养学生观察、联想、作图和理解实际问题的能力，渗透化归、数形结合的数学思想. 三)、情感目标 1.让学生体验数学来源于生活，服务于生活，品尝学习数学的乐趣. 2.让学生体验数学活动充满着探索与创造，培养学生勤于思考、勇于探索的精神. 三、教学重点、难点 重点：线性规划问题的图解法；寻求有实际背景的线性规划问题的最优解. 难点：借助线性目标函数的几何含义准确理解线性目标函数在y 轴上的截距与z最值之间的关系. 四、学习者特征分析 1. 已经掌握用平面区域表示二元一次不等式（组） 2. 初步学会分析简单的实际应用问题 3. 能根据实际数据假设变量，并从中抽象出不等的线性约束条件并用相应的平面区域进行表示 本节课学生在学习过程中可能遇到以下疑虑和困难： 1.将实际问题抽象成线性规划问题； 2.用图解法解线性规划问题中，为什么要将求目标函数最值问题转化为经过可行域的直线在y轴上的截距的最值问题？如何想到要这样转化？ 3.数形结合思想的深入理解. 五、教学与学法分析 本节课以学生为中心，以问题为载体，采用启发、引导、探索相结合的教学方法.课堂中应注重创设师生互动、生生互动的和谐氛围，通过学生动手实践、动脑思考等方法探究数学知识获取直接经验，进而培养学生的思维能力和应用意识等. 1.设置“问题”情境，激发学生解决问题的欲望； 2.提供“观察、探索、交流”的机会，引导学生独立思考，有效地调动学生思维，使学生在开放的活动中获取直接经验. 一、用单纯形第Ⅰ阶段和第Ⅱ阶段解下列问题 s.t. 解：1)、将该线性问题转为标准线性问题 一、第一阶段求解初始可行点 2)、引入人工变量修改约束集合 取人工变量为状态变量，问题变量和松弛变量为决策变量，得到如下单纯形表，并是所有决策变量的值为零，得到人工变量的非负值。 2 -2 -1 1 2 1 1 -1 -1 1 2 -1 -2 1 2 5 -2 -4 1 -1 1 5 0 0 0 0 0 3)、对上述单纯形表进行计算，是目标函数进一步减小，选为要改变的决策变量，计算改变的限值。 2 -2 -1 1 2 1 1 1 -1 -1 1 0 2 -1 -2 1 2 0 5 -2 -4 1 -1 1 5 1 0 0 0 0 0 0 1 0 0 0 4)、由于，为人工变量，当其到达零值时，将其从问题中拿掉保证其值不会再变。同时将以改变的决策变量转换为状态变量。增加的值使目标函数值更小。 1 -3 1 1 1 0 1 1 -1 1 1 -3 1 1 1 0 0 0 0 0 0 0 0 5）使所有人工变量为零的问题变量的值记为所求目标函数的初始可行点，本例为， 二、第二阶段用单纯形法求解最优解 -2 2 1 0 1 1 -1 0 -2 1 2 1 5 1 3 要使目标函数继续减小，需要减小或的值，由以上计算，已经有两个松弛变量为零，因此或不能再减小了，故该初始可行点即为最优解。 2、求解问题 s.t. 如果目标函数变成，确定使原解仍保持最优的c值范围，并把目标函数最 大值变达成c的函数。 解：先采用单纯形法求解最优解，再对保持最优解时C值的范围进行讨论。 1）将问题华为标准线性问题 s.t. 2）用单纯形表表示约束条件，同时在不引入人工变量的前提下，取松弛变量得初始值为零值，求解初始解和最优解 10 -1 -1 -1 10 -20 1 5 1 -20 -2 -1 -1 0 0 0 0 要使目标函数继续减小，可以增大，增大的限值是10。 10 -1 -1 -1 10 0 -20 1 5 1 -20 -10 -2 -1 -1 0 -20 0 0 0 10 0 0 3）转轴。将为零的松弛变量和决策变量交换进行转轴 10 -1 -1 -1 10 -10 4 0 -1 -10 0 -20 1 1 2 -20 简单的线性规划问题 [学习目标] 1.了解线性规划的意义以及约束条件、目标函数、可行解、可行域、最优解等基本概念.2.了解线性规划问题的图解法，并能应用它解决一些简单的实际问题． 知识点一 线性规划中的基本概念 1．目标函数的最值 线性目标函数z ＝ax ＋by (b ≠0)对应的斜截式直线方程是y ＝－a b x ＋z b ，在y 轴上的截距是z b ， 当z 变化时，方程表示一组互相平行的直线． 当b >0，截距最大时，z 取得最大值，截距最小时，z 取得最小值； 当b <0，截距最大时，z 取得最小值，截距最小时，z 取得最大值． 2．解决简单线性规划问题的一般步骤 在确定线性约束条件和线性目标函数的前提下，解决简单线性规划问题的步骤可以概括为：“画、移、求、答”四步，即， (1)画：根据线性约束条件，在平面直角坐标系中，把可行域表示的平面图形准确地画出来， 可行域可以是封闭的多边形，也可以是一侧开放的无限大的平面区域． (2)移：运用数形结合的思想，把目标函数表示的直线平行移动，最先通过或最后通过的顶点(或边界)便是最优解． (3)求：解方程组求最优解，进而求出目标函数的最大值或最小值． (4)答：写出答案． 知识点三简单线性规划问题的实际应用 1．线性规划的实际问题的类型 (1)给定一定数量的人力、物力资源，问怎样运用这些资源，使完成的任务量最大，收到的效益最大； (2)给定一项任务，问怎样统筹安排，使完成这项任务耗费的人力、物力资源量最小． 常见问题有： ①物资调动问题 例如，已知两煤矿每年的产量，煤需经两个车站运往外地，两个车站的运输能力是有限的，且已知两煤矿运往两个车站的运输价格，煤矿应怎样编制调动方案，才能使总运费最小？ ②产品安排问题 例如，某工厂生产甲、乙两种产品，每生产一个单位的甲种或乙种产品需要的A、B、C三种材料的数量，此厂每月所能提供的三种材料的限额都是已知的，这个工厂在每个月中应如何安排这两种产品的生产，才能使每月获得的总利润最大？ ③下料问题 例如，要把一批长钢管截成两种规格的钢管，应怎样下料能使损耗最小？ 2．解答线性规划实际应用题的步骤 (1)模型建立：正确理解题意，将一般文字语言转化为数学语言，进而建立数学模型，这需要在学习有关例题解答时，仔细体会范例给出的模型建立方法． (2)模型求解：画出可行域，并结合所建立的目标函数的特点，选定可行域中的特殊点作为最优解． 简单的线性规划问题 [ 学习目标 ] 1.了解线性规划的意义以及约束条件、目标函数、可行解、可行域、最优解等基本概念 .2. 了解线性规划问题的图解法，并能应用它解决一些简单的实际问题． 知识点一线性规划中的基本概念 知识点二线性规划问题 1．目标函数的最值 线性目标函数 z＝ax＋by (b≠0)对应的斜截式直线方程是 y＝－a x＋z，在 y 轴上的 截距是z， b b b 当 z 变化时，方程表示一组互相平行的直线． 当 b>0，截距最大时， z 取得最大值，截距最小时， z 取得最小值； 当 b<0，截距最大时， z 取得最小值，截距最小时， z 取得最大值． 2．解决简单线性规划问题的一般步骤在确定线性约束条件和线性目标函数的前提下，解决简单线性规划问题的步骤可以概括为：“画、移、求、答”四步，即， (1)画：根据线性约束条件，在平面直角坐标系中，把可行域表示的平面图形准确地画出来，可行域可以是封闭的多边形，也可以是一侧开放的无限大的平面区域．(2)移：运用数形结合的思想，把目标函数表示的直线平行移动，最先通过或最后通过的顶点 (或边界 )便是最优解． (3)求：解方程组求最优解，进而求出目标函数的最大值或最小值． (4)答：写出答案． 知识点三简单线性规划问题的实际应用 1．线性规划的实际问题的类型 (1)给定一定数量的人力、物力资源，问怎样运用这些资源，使完成的任务量最大，收到的效益最大； (2)给定一项任务，问怎样统筹安排，使完成这项任务耗费的人力、物力资源量最小．常见问题有： ①物资调动问题例如，已知两煤矿每年的产量，煤需经两个车站运往外地，两个车站的运输能力是有限的，且已知两煤矿运往两个车站的运输价格，煤矿应怎样编制调动方案，才能使总运费最小？ ②产品安排问题例如，某工厂生产甲、乙两种产品，每生产一个单位的甲种或乙种产品需要的A、B、C 三种 材料的数量，此厂每月所能提供的三种材料的限额都是已知的，这个工厂在每个月中应如何安排这两种产品的生产，才能使每月获得的总利润最大？ ③下料问题例如，要把一批长钢管截成两种规格的钢管，应怎样下料能使损耗最小？2．解答线性规划实际应用题的步骤 (1)模型建立：正确理解题意，将一般文字语言转化为数学语言，进而建立数学模型，这需要在学习有关例题解答时，仔细体会范例给出的模型建立方法． (2)模型求解：画出可行域，并结合所建立的目标函数的特点，选定可行域中的特殊点作为最优解． (3)模型应用：将求解出来的结论反馈到具体的实例中，设计出最佳的方案． 题型一求线性目标函数的最值 y≤2， 例 1 已知变量 x，y 满足约束条件 x＋y≥1，则 z＝3x＋y 的最大值为 ( ) x－y≤1， A ． 12 B ．11 C ．3 D ．－ 1 答案 B 解析首先画出可行域，建立在可行域的基础上，分析最值点，然后通过解方程组得最值点 的坐标，代入即可．如图中的阴影部分，即为约束条件对应的可行域，当直线y＝－3x＋z 经 y＝2，x＝ 3， 简单的线性规划问题 一、教学内容分析 普通高中课程标准教科书数学5（必修）第三章第3课时 这是一堂关于简单的线性规划的“问题教学”． 线性规划是数学规划中理论较完整、方法较成熟、应用较广泛的一个分支，它能解决科 学研究、工程设计、经济管理等许多方面的实际问题. 简单的线性规划（涉及两个变量）关心的是两类问题：一是在人力、物力、资金等资源 一定的条件下，如何使用它们来完成最多的任务；二是给定一项任务，如何合理规划，能以 最少的人力、物力、资金等资源来完成.突出体现了优化的思想． 教科书利用生产安排的具体实例，介绍了线性规划问题的图解法，引出线性规划等的概 念，最后举例说明了简单的二元线性规划在饮食营养搭配中的应用. 二、学生学习情况分析 本节课学生在学习了不等式、直线方程的基础上，又通过实例，理解了平面区域的意义， 并会画出平面区域，还能初步用数学关系式表示简单的二元线性规划的限制条件，将实际问 题转化为数学问题. 从数学知识上看，问题涉及多个已知数据、多个字母变量，多个不等关 系，从数学方法上看，学生对图解法的认识还很少，数形结合的思想方法的掌握还需时日， 这都成了学生学习的困难． 三、设计思想 本课以问题为载体，以学生为主体，以数学实验为手段，以问题解决为目的，以几何画 板作为平台，激发他们动手操作、观察思考、猜想探究的兴趣。注重引导帮助学生充分体验 “从实际问题到数学问题”的建构过程，“从具体到一般”的抽象思维过程，应用“数形结 合”的思想方法，培养学生的学会分析问题、解决问题的能力。 四、教学目标 1．了解线性规划的意义，了解线性约束条件、线性目标函数、可行解、可行域和最优解等概念；理解线性规划问题的图解法；会利用图解法求线性目标函数的最优解． 2．在实验探究的过程中，让学生体验数学活动充满着探索与创造，培养学生的数据分析能力、探索能力、合情推理能力及动手操作、勇于探索的精神； 3、在应用图解法解题的过程中,培养学生运用数形结合思想解题的能力和化归能力，体验数学来源于生活，服务于生活，体验数学在建设节约型社会中的作用. 五、教学重点和难点 求线性目标函数的最值问题是重点；从数学思想上看，学生对为什么要将求目标函数最值问题转化为经过可行域的直线在y轴上的截距的最值问题？以及如何想到要这样转化？存在一定疑虑及困难；教学应紧扣问题实际，通过突出知识的形成发展过程，引入数学实验来突破这一难点． 332简单线性规划问题 “简单的线性规划”是在学生学习了直线方程的基础上，介绍直线方程的一个简 单应用，这是《新大纲》对数学知识应用的重视?线性规划是利用数学为工具，来研究一定的人、财、物、时、空等资源在一定条件下，如何精打细算巧安排，用最少的资源，取得最大的经济效益?它是数学规划中理论较完整、方法较成熟、应用较广泛的一个分支，并能解决科学研究、工程设计、经营管理等许多方面的实际问题?中学 所学的线性规划只是规划论中的极小一部分，但这部分内容体现了数学的工具性、应用性，同时也渗透了化归、数形结合的数学思想，为学生今后解决实际问题提供了一种重要的解题方法一一数学建模法.通过这部分内容的学习，可使学生进一步了解数学在解决实际问题中的应用，培养学生学习数学的兴趣和应用数学的意识和解决实际问题的能力 依据课程标准及教材分析，二元一次不等式表示平面区域以及线性规划的有关概念比较抽象，按学生现有的知识和认知水平难以透彻理解，再加上学生对代数问题等 价转化为几何问题以及数学建模方法解决实际问题有一个学习消化的过程，故本节知 识内容定为了解层次 本节内容渗透了多种数学思想，是向学生进行数学思想方法教学的好教材，也是培养学生观察、作图等能力的好教材 本节内容与实际问题联系紧密，有利于培养学生学习数学的兴趣和“用数学”的意识以及解决实际问题的能力 教学重点重点是二元一次不等式（组）表示平面的区域教学难点难点是把实际问题转化为线性规划问题，并给出解答?解决难点的关键是根据实际问题中的已知条件，找出约束条件和目标函数，利用图解法求得最优解?为突 出重点，本节教学应指导学生紧紧抓住化归、数形结合的数学思想方法将实际问题数学化、代数问题几何化课时安排2课时 三维目标 一、知识与技能 1. 掌握线性规划的意义以及约束条件、目标函数、可行解、可行域、最优解等基本概念； 2. 运用线性规划问题的图解法，并能应用它解决一些简单的实际问题I 二、过程与方法 1. 培养学生观察、联想以及作图的能力，渗透集合、化归、数形结合的数学思想，提高学生“建模”和解决实际问题的能力； 2. 结合教学内容，培养学生学习数学的兴趣和“用数学”的意识，激励学生创新. 三、情感态度与价值观 1. 通过本节教学着重培养学生掌握“数形结合”的数学思想，尽管侧重于用“数”研究“形”，但同时也用“形”去研究“数”，培养学生观察、联想、猜测、 归纳等数学能力； 2. 结合教学内容，培养学生学习数学的兴趣和“用数学”的意识，激励学生勇于 创新. 使用单纯形法解线性规划问题 要求：目标函数为：123min 3z x x x =-- 约束条件为： 123123 1312321142321,,0 x x x x x x x x x x x -+≤??-++≥?? -+=??≥? 用单纯形法列表求解，写出计算过程。 解： 1） 将线性规划问题标准化如下： 目标函数为：123max max()3f z x x x =-=-++ s.t.： 123412356 1371234567211 42321,,,,,,0 x x x x x x x x x x x x x x x x x x x -++=??-++-+=??-++=??≥? 2） 找出初始基变量，为x 4、x 6、x 7，做出单纯形表如下： 表一：最初的单纯形表 变量 基变量 x 1 x 2 x 3 x 4 x 5 x 6 x 7 b i x 4 1 -2 1 1 0 0 0 11 x 6 -4 1 2 0 -1 1 0 3 x 7 -2 0 1 0 0 0 1 1 -f -3 1 1 3） 换入变量有两种取法，第一种取为x 2，相应的换出变量为x 6，进行第一次迭代。迭代后新的单纯形表为： 表二：第一种换入换出变量取法迭代后的单纯形表 变量 基变量 x 1 x 2 x 3 x 4 x 5 x 6 x 7 b i x 4 -7 5 1 -2 2 3 x2-4120-1103 x7-20100011 -f10-101-10-3 由于x1和x5对应的系数不是0就是负数，所以此时用单纯形法得不到最优解。 表一中也可以把换入变量取为x3，相应的换出变量为x7，进行一次迭代后的单纯形表为： 表三：第二种换入换出变量取法迭代后的单纯形表 变量 基变量x1x2x3x4x5x6x7 b i x43-20100-110 x60100-11-21 x3-20100011 -f-110000-1-1 4）表三中，取换入变量为x2，换出变量为x6，进行第二次迭代。之后的单纯形 表为： 表四：第二次迭代后的单纯形表 变量 基变量x1x2x3x4x5x6x7 b i x43001-22-512 x20100-11-21 x3-20100011 -f-10001-11-2 5）表四中，取换入变量为x7，换出变量为x3，进行第三次迭代。之后的单纯形 表为： 表五：第三次迭代后的单纯形表 变量 基变量x1x2x3x4x5x6x7 b i x4-7051-22017 x2-4120-1103 x7-20100011 -f10-101-10-3可以看出，此时x1，x5对应的系数全部非零即负，故迭代结束，没有最优解。 结论： 综上所述，本线性规划问题，使用单纯形法得不到最优解。 线性规划及单纯形法 一．选择 1. 运筹学应用分析、试验、（C ）的方法，对经济管理系统中人、财、物等有限资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。 A 统筹 B 量化 C 优化 D 决策 2. 运筹学研究的基本手段是（A ）。 A 建立数学模型 B 进行数学分析 C 进行决策分析 D 建立管理规范 3. 运筹学研究的基本特点是（ C ）。 A 进行系统局部独立分析 B 考虑系统局部优化 C 考虑系统的整体优化 D 进行系统的整体决策 4. 线性规划问题的数学模型包含三个组成要素：决策变量、目标函数、（B ） A 表达式 B 约束条件 C 方程变量 D 价值系数 5. 线性规划问题的基可行解X 对应线性规划问题可行域（凸集）的（ C ） A 边 B 平面 C 顶点 D 内部 6. 目标函数取极小化（Z min ）的线性规划问题可以转化为目标函数取极大化即（C ）的线性规划问题求解 A Z min B )min(Z - C )max(Z - D Z max - 7. 标准形式的线性规划问题，最优解（C ）是可行解 A 一定 B 一定不 C 不一定 D 无法确定 8. 在线性规划问题中，称满足所有约束条件方程和非负限制的解为（ C ）。 A 最优解 B 基可行解 C 可行解 D 基解 9. 生产和经营管理中经常提出任何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是所谓的（D ） A 管理问题 B 规划问题 C 决策问题 D 优化问题 10. 在线性规划问题中，图解法适合用于处理变量（ B ）个的线性规划问题 A 1 B 2 C 3 D 4 11. 求解线性规划问题时，解的情况有:唯一最优解、无穷多最优解、（ C ）、无可行解 A 无解B 无基解 C 无界解 D 无基可行解 12. 在用图解法求解的时，找不到满足约束条件的公共范围，这时问题有（D ），其原因是模型本身有错误，约束条件之间相互矛盾，应检查修正。 A 唯一最优解 B 无穷多最优解 C 无界解D 无可行解 13. 线性规划问题的基可行解()T n X X X ,,1 =为基可行解的充要条件是X 的正分量所对 应的系数列向量是（B ） A 线性相关 B 线性独立 C 非线性独立 D 无法判断 14. 线性规划问题进行最优性检验和解的判别时，如果当0≤j σ时，人工变量仍留在基本量中且不为零，（D ） A 唯一最优解 B 无穷多最优解 C 无界解 D 无可行解 15.如果集合C 中任意两个点21,X X 其连线上的所有点也都是集合C 中的点，称C 为（B ） 3.3.2 简单线性规划问题 从容说课 本节课先由师生共同分析日常生活中的实际问题来引出简单线性规划问题的一些基本概念，由二元一次不等式组的解集可以表示为直角坐标平面上的区域引出问题：在直角坐标系内，如何用二元一次不等式（组）的解集来解决直角坐标平面上的区域求解问题？再从一个具体的二元一次不等式（组）入手，来研究一元二次不等式表示的区域及确定的方法，作出其平面区域，并通过直线方程的知识得出最值.通过具体例题的分析和求解，在这些例题中设置思考项，让学生探究，层层铺设，以便让学生更深刻地理解一元二次不等式表示的区域的概念，有利于二元一次不等式（组）与平面区域的知识的巩固. “简单的线性规划”是在学生学习了直线方程的基础上，介绍直线方程的一个简单应用，这是《新大纲》对数学知识应用的重视.线性规划是利用数学为工具，来研究一定的人、财、物、时、空等资源在一定条件下，如何精打细算巧安排，用最少的资源，取得最大的经济效益.它是数学规划中理论较完整、方法较成熟、应用较广泛的一个分支，并能解决科学研究、工程设计、经营管理等许多方面的实际问题.中学所学的线性规划只是规划论中的极小一部分，但这部分内容体现了数学的工具性、应用性，同时也渗透了化归、数形结合的数学思想，为学生今后解决实际问题提供了一种重要的解题方法——数学建模法.通过这部分内容的学习，可使学生进一步了解数学在解决实际问题中的应用，培养学生学习数学的兴趣和应用数学的意识和解决实际问题的能力. 依据课程标准及教材分析，二元一次不等式表示平面区域以及线性规划的有关概念比较抽象，按学生现有的知识和认知水平难以透彻理解，再加上学生对代数问题等价转化为几何问题以及数学建模方法解决实际问题有一个学习消化的过程，故本节知识内容定为了解层次. 本节内容渗透了多种数学思想，是向学生进行数学思想方法教学的好教材，也是培养学生观察、作图等能力的好教材. 本节内容与实际问题联系紧密，有利于培养学生学习数学的兴趣和“用数学”的意识以及解决实际问题的能力. 教学重点重点是二元一次不等式（组）表示平面的区域. 教学难点难点是把实际问题转化为线性规划问题，并给出解答.解决难点的关键是根据实际问题中的已知条件，找出约束条件和目标函数，利用图解法求得最优解.为突出重点，本节教学应指导学生紧紧抓住化归、数形结合的数学思想方法将实际问题数学化、代数问题几何化. 单纯形法求解线性规划的步骤 1>初始化 将给定的线性规划问题化成标准形式,并建立一个初始表格,它最右边的单元格都就是非负的(否则无解),接下来的m 列组成一个m*m的单元矩阵(目标行的单元格则不必满足这一条件),这m列确定了初始的基本可行解的基本变量,而表格中行用基本变量来表示 2>最优化测试 如果目标行的所有单元格都就是非负的(除了最右列中代表目标函数值的那个单元格),就可以停止了,该表格代表了一个最优解,它的基本变量的值在最右列中,而剩下的非基本变量都为0 3>确定输入变量 从目标行的前n个单元格中选择一个负的单元格(选择绝对值最大的那个)该单元格所在的列确定的输入变量及主元列 4>确定分离变量 对于主元列的每个正单元格,求出θ比率(如果主元格的单元格为负或为0,说明该问题就是无解的,算法终止),找出θ比率最小的列,改行确定了分离变量与主元行 5>建立下一张表格 将主元行的所有单元格除以主元得到新的主元行,包括主元行在内的每一行,要减去改行主元列单元格与新主元行的成绩(除主元行为1外,这一步将主元列的所有单元格变成0)、把主元列的变量名进行代换,得到新的单纯形表,返回第一步 为求简单 在本程序中,需要自己建立标准矩阵(比如加入松弛变量等工作需要用户自己完成),程序的输入有两种方式: 1:指定行与列,由用户自行输入每一个元素SimpleMatrix(introw=0,int col=0); 2:直接在主程序中初始化一个二维数组,然后利用构造函数SimpleMatrix(introw,int col,double **M) 来初始化与处理(本程序所用的实例用的就是这种方法) 程序中主要的函数以及说明 ~SimpleMatrix(); 销毁动态分配的数组、用于很难预先估计矩阵的行与列,所以在程序中才了动态的内存分配、需要重载析构函数bool Is_objectLine_All_Positive(); //判断目标行就是否全部为非负数,最后一列不作考虑 这个函数用来判断就是否已经存在最优解 bool Is_MainCol_All_Negative(int col);//判断主元列就是否全部为负数或零 这个函数用来判断线性规划就是否就是无解的 bool Is_column_all_Positive(int col); //判断col列中就是否全部为正(不包括目标行) 单纯形法求解线性规划的步骤 单纯形法求解线性规划的步骤 1>初始化 将给定的线性规划问题化成标准形式,并建立一个初始表格,它最右边的单元格都是非负的(否则无解),接下来的m列组成一个m*m的单元矩阵(目标行的单元格则不必满足这一条件),这m列确定了初始的基本可行解的基本变量,而表格中行用基本变量来表示 2>最优化测试 如果目标行的所有单元格都是非负的(除了最右列中代表目标函数值的那个单元格),就可以停止了,该表格代表了一个最优解,它的基本变量的值在最右列中,而剩下的非基本变量都为0 3>确定输入变量 从目标行的前n个单元格中选择一个负的单元格(选择绝对值最大的那个)该单元格所在的列确定的输入变量及主元列 4>确定分离变量 对于主元列的每个正单元格,求出θ比率(如果主元格的单元格为负或为0,说明该问题是无解的,算法终止),找出θ比率最小的列,改行确定了分离变量和主元行 5>建立下一张表格 将主元行的所有单元格除以主元得到新的主元行,包括主元行在内的每一行,要减去改行主元列单元格和新主元行的成绩(除主元行为1外,这一步将主元列的所有单元格变成0).把主元列的变量名进行代换,得到新的单纯形表,返回第一步 为求简单 在本程序中,需要自己建立标准矩阵(比如加入松弛变量等工作需要用户自己完成),程序的输入有两种方式: 1:指定行和列,由用户自行输入每一个元素SimpleMatrix(introw=0,int col=0); 2:直接在主程序中初始化一个二维数组,然后利用构造函数SimpleMatrix(introw,int col,double **M) 来初始化和处理(本程序所用的实例用的是这种方法) 程序中主要的函数以及说明 ~SimpleMatrix(); 销毁动态分配的数组.用于很难预先估计矩阵的行和列,所以在程序中才了动态的内存分配.需要重载析构函数 bool Is_objectLine_All_Positive(); //判断目标行是否全部为非负数,最后一列不作考虑 这个函数用来判断是否已经存在最优解 bool Is_MainCol_All_Negative(int col);//判断主元列是否全部为负数或零 这个函数用来判断线性规划是否是无解的 bool Is_column_all_Positive(int col); //判断col列中是否全部为正(不包括目标行) 简单的线性规划问题 【知识概述】 线性规划是不等式应用的一个典型，也是数形结合思想所体现的一个重要侧面.近年的考试中，通常考查二元一次不等式组表示的平面区域的图形形状以及目标函数的最大值或最小值，或求函数的最优解等问题.通过这节课的学习，希望同学们能够掌握线性规划的方法，解决考试中出现的各种问题. 解决线性规划的数学问题我们要注意一下几点 1.所谓线性规划就是在线性约束条件下求线性目标函数的最值问题； 2.解决线性规划问题需要经历两个基本的解题环节 （1）作出平面区域；（直线定”界”，特“点”定侧）； （2）求目标函数的最值. （3）求目标函数z=ax+by最值的两种类型： ①0 b>时，截距最大（小），z的值最大（小）； ②0 b>时，截距最大（小），z的值最小（大）； 【学前诊断】 1.[难度] 易 满足线性约束条件 23, 23, 0, x y x y x y +≤ ? ?+≤ ? ? ≥ ? ?≥ ? 的目标函数z x y =+的最大值是（） A.1 B.3 2 C.2 D.3 2.[难度] 易 设变量,x y满足约束条件 0, 0, 220, x x y x y ≥ ? ? -≥ ? ?--≤ ? 则32 z x y =-的最大值为( ) A.0 B.2 C.4 D.6 3. [难度] 中 设1m >，在约束条件1y x y mx x y ≥??≤??+≤? 下，目标函数z x my =+的最大值小于2，则m 的取 值范围为（ ） A ．(1,1 B ．(1)+∞ C ．(1,3) D ．(3,)+∞ 【经典例题】 例1. 设变量,x y 满足约束条件1,0,20,y x y x y ≤??+≥??--≤? 则2z x y =+的最大值为( ) A.5 B.4 C.1 D.8 例2. 若变量,x y 满足约束条件1,0,20,y x y x y ≤??+≥??--≤? 则2z x y =-的最大值为( ) A.4 B.3 C.2 D.1 例3. 设,x y 满足约束条件2208400,0x y x y x y -+≥??--≤??≥≥? ，若目标函数(0,0)z abx y a b =+>>的最小 值为8，则a b +的最小值为____________. 例4. 在约束条件下0,0,,24, x y x y s x y ≥??≥??+≤??+≤?当35s ≤≤时，目标函数32z x y =+的最大值的变化范围是( ) 《简单的线性规划问题》（第一课时）教学设计 一、内容与内容解析 本节课是《普通高中课程标准实验教科书数学》人教A版必修5第三章《不等式》中3.3.2《简单的线性规划问题》的第一课时. 主要内容是线性规划的相关概念和简单的线性规划问题的解法． 线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法，广泛地应用于军事作战、经济分析、经营管理和工程技术等方面．简单的线性规划指的是目标函数含两个自变量的线性规划，其最优解可以用数形结合方法求出。简单的线性规划关心的是两类问题：一是在人力、物力、资金等资源一定的条件下，如何使用它们来完成最多的任务；二是给定一项任务，如何合理规划，能以最少的人力、物力、资金等资源来完成. 教科书利用生产安排的具体实例，介绍了线性规划问题的图解法，引出线性规划等概念，最后举例说明了简单的二元线性规划在饮食营养搭配中的应用. 本节内容蕴含了丰富的数学思想方法，突出体现了优化思想、数形结合思想和化归思想. 本节教学重点：线性规划问题的图解法；寻求有实际背景的线性规划问题的最优解. 二、目标和目标解析 （一）教学目标 1.了解约束条件、目标函数、可行解、可行域、最优解等基本概念. 2. 会用图解法求线性目标函数的最大值、最小值. 3.培养学生观察、联想、作图和理解实际问题的能力，渗透化归、数形结合的数学思想. 4.结合教学内容培养学生学习数学的兴趣和“用数学”的意识. （二）教学目标解析 1. 了解线性规划模型的特征：一组决策变量(,) x y表示一个方案；约束条件是一次不等式组；目标函数是线性的，求目标函数的最大值或最小值．熟悉线性 %单纯形法matlab程序-ssimplex % 求解标准型线性规划:max c*x; . A*x=b; x>=0 % 本函数中的A是单纯初始表，包括:最后一行是初始的检验数，最后一列是资源向量b % N是初始的基变量的下标 % 输出变量sol是最优解, 其中松弛变量（或剩余变量）可能不为0 % 输出变量val是最优目标值，kk是迭代次数 % 例：max 2*x1+3*x2 % . x1+2*x2<=8 % 4*x1<=16 % 4*x2<=12 % x1,x2>=0 % 加入松驰变量，化为标准型，得到 % A=[1 2 1 0 0 8; % 4 0 0 1 0 16; % 0 4 0 0 1 12; % 2 3 0 0 0 0]; % N=[3 4 5]; % [sol,val,kk]=ssimplex(A,N) % 然后执行 [sol,val,kk]=ssimplex(A,N)就可以了。 function [sol,val,kk]=ssimplex(A,N) [mA,nA]=size(A); kk=0; % 迭代次数 flag=1; while flag kk=kk+1; if A(mA,:)<=0 % 已找到最优解 flag=0; sol=zeros(1,nA-1); for i=1:mA-1 sol(N(i))=A(i,nA); end val=-A(mA,nA); else for i=1:nA-1 if A(mA,i)>0&A(1:mA-1,i)<=0 % 问题有无界解 disp('have infinite solution!'); flag=0; break; end end if flag % 还不是最优表，进行转轴运算 temp=0; for i=1:nA-1 if A(mA,i)>temp temp=A(mA,i); inb=i; % 进基变量的下标 end 图解法和单纯形法求解以下线性规划问题 1.1 图解法解线性规划问题 只含两个变量的线性规划问题，可以通过在平面上作图的方法求解，步骤如下： (1)以变量x1为横坐标轴，x2为纵坐标轴，适当选取单位坐标长度建立平面坐标直 角坐标系。由变量的非负性约束性可知，满足该约束条件的解均在第一象限内。 (2)图示约束条件，找出可行域（所有约束条件共同构成的图形）。 (3)画出目标函数等值线，并确定函数增大（或减小）的方向。 (4)可行域中使目标函数达到最优的点即为最优解。 然而，由于图解法不适用于求解大规模的线性规划问题，其实用意义不大。 1.2 单纯形法解线性规划问题 它的理论根据是：线性规划问题的可行域是n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。 单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。 单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。 1.3 线性规划问题的标准化 使用单纯形法求解线性规划时，首先要化问题为标准形式 使用单纯形法解线性规划 问题 The Standardization Office was revised on the afternoon of December 13, 2020 使用单纯形法解线性规划问题 要求：目标函数为：123min 3z x x x =-- 约束条件为： 123123 1312321142321,,0 x x x x x x x x x x x -+≤??-++≥?? -+=??≥? 用单纯形法列表求解，写出计算过程。 解： 1）将线性规划问题标准化如下： 目标函数为：123max max()3f z x x x =-=-++ .： 1234123561371234567211 42321,,,,,,0x x x x x x x x x x x x x x x x x x x -++=??-++-+=??-++=??≥? 2）找出初始基变量，为x 4、x 6、x 7，做出单纯形表如下： 表一：最初的单纯形表 3） 换入变量有两种取法，第一种取为x 2，相应的换出变量为x 6，进行第一 次迭代。迭代后新的单纯形表为： 表二：第一种换入换出变量取法迭代后的单纯形表 由于x1和x5对应的系数不是0就是负数，所以此时用单纯形法得不到最优解。 表一中也可以把换入变量取为x3，相应的换出变量为x7，进行一次迭代后的单纯形表为： 表三：第二种换入换出变量取法迭代后的单纯形表 4）表三中，取换入变量为x2，换出变量为x6，进行第二次迭代。之后的单纯形表为： 表四：第二次迭代后的单纯形表 5）表四中，取换入变量为x7，换出变量为x3，进行第三次迭代。之后的单纯形表为： 表五：第三次迭代后的单纯形表简单的线性规划应用题解析
《简单的线性规划问题》教案
最新单纯形法解线性规划问题
简单的线性规划问题附答案
(完整版)简单的线性规划问题(附答案)
人教版 高中数学 简单的线性规划问题教案
简单线性规划问题教案
使用单纯形法解线性规划问题
第1章线性规划及单纯形法
高中数学 简单线性规划问题教案 新人教A版必修
单纯形法求解线性规划的步骤
单纯形法求解线性规划的步骤
高中数学必修5：简单的线性规划问题 知识点及经典例题(含答案)
《简单的线性规划问题》(第一课时)教学设计
线性规划单纯形法matlab解法
图解法和单纯形法求解线性规划问题
使用单纯形法解线性规划问题
相关主题
文本预览