线性规划问题的四种求解方法

线性规划问题的四种求解方法

江苏溧阳中学(213300) 吕清平

线性规划问题是现实生活中一类重要的应用问题,它常用来研究物资调运、生产安排、下料等工作的资源优化配制问题,寻求线性规划问题的最优解具有十分重要的现实意义.现介绍几种求解线性规划问题的最优解的策略.

一、截距法

例1 某厂需从国外引进两种机器.第一种机器每台10万美元,维护费为人民币4000元;第二种机器每台20万美元,维护费为人民币1000元;而第一种机器产生的年利润为每台12万美元;第二种机器产生的年利润为18万美元.但政府核准的外汇是130万美元,并要求总维护费不得超过人民币24000元.问每种机器应购买多少台时,才能使工厂获得的年利润最大?

解:设购买第一种机器x 台,购买第二种机器y 台.

则10x +20y 1304000x +1000y 24000

x 0 y 0即x +2y 134x +y 24

x 0,y 0

总年利润z =12x +18y

作出以上不等式组所表示的平面区域,即可行域.由z =12x +18y 得y =-23x +z

18

,则

z 18为直线y =-23x +z 18的截距.令z =0,则可画出直线l 0:y =-2

3

x ,把直线l 0向右上方平移,当经过可行域上点B 时,直线的截距最大.此时z =12x +18y 取最大值.解方程组x +2y =13

4x +y =24

得B (5,4).故当x =5,y =4

时,z max =12!5+18!4=132(万美元)

答:购买第一种机器5台,第二种机器4台时能使工厂获得的年利润最大.

二、等值线法

所谓等值线是指直线上任一点的坐标(x ,y )都使F (x ,y )=Ax +By 取等值C 的直线l:Ax +By =C (A 、B 不同时为零).通过比较等值线的值的大小可以求得简单线性规划问题的最优解.

例2 甲、乙两地生产某种产品.甲地可调出300吨,乙地可调出750吨,A 、B 、C 三地需要该种产品分别为200

吨、450吨和400吨.每吨运费如下表(单位:元):

A B C 甲地635乙地

5

9

6

问怎样调运,才能使总运费最省?

解 设由甲地调往A 、B 两地分别为x 吨,y 吨.则由甲调往C 地为[300-(x +y )]吨;由乙地调往A 、B 、C 三地分别为(200-x )吨、(450-y )吨、(100+x +y )吨.于是x +y 300x 200

x 0,y 0

z =6x +3y +5[300-(x +y )]+5(200-x )+9(450-y )+6(100+x +y )=2x -5y +7150

作出以上不等式组所表示的平面区域即可行域.令z =0,则可画出直线l 0:2x -5y +

7150=0.画出一组与l 0平行的等值线,比较等

11

?中学理科#2002年第7期

值线值的大小知,当等值线经过可行域上点C 时,等值线的值最小.z有最小值5650元,此时x=0、y=300,故甲地产品运往B地;乙地产品运往A、B、C三地分别为200吨、150吨、400吨时能使总运费最省.

三、顶点法

如果可行域是一个多边形围成的区域(包括边界多边形)时,线性目标函数z=f(x、y)的最优解必在多边形顶点上取到.因此算出z =f(x、y)在各项点的值,再比较大小可以找出最优解.

例3 某工厂每天要生产甲、乙两种产品,每件甲产品需分别在A、B、C、D四台不同设备上加工2、1、4、0小时;每件乙产品需分别在A、B、C、D上加工2、2、0、4小时。已知A、B、C、D 每天最多能转动的时数分别是12、8、16、12小时.生产一件甲产品该厂得利润200元,生产一件乙产品得利润300元.问每天如何安排生产才能得到利润最大?

解 设每天生产甲、乙产品的件数分别是

作出以上不等式组所表示的平面区域,即可行域.可行域为一五边形,五个顶点对应的z 值如下表

(x,y)(0,0)(4,0)(4,2)(2,3)(0,3)

z=200x+300y080014001300900

由表可知:在可行域的顶点B(4,2)处z取得最大值.故x=4,y=2,z有最大值1400元.

答:每天生产4件甲产品,2件乙产品能得到最大利润.

四、待定系数法

对于特殊的线性规划问题也可以用待定系数法求解.

例4 甲、乙、丙三种维生素A、B含量及成本如下表:

甲乙丙维生素A(单位/千克)600700400

维生素B(单位/千克)800400500

成本(单位/千克)1194

某食物营养所想用x千克甲种食物,y千克乙种食物,z千克丙种食物配成100千克混合物,并使混合物至少含有56000单位维生素A 和63000单位维生素B

(1)用x、y表示混合物的成本c(元);

(2)确定x、y、z的值,使成本最低.

解 (1)c=11x+9y+4z

x+y+z=100

%c=400+7x+5y

(2)由题意得

600x+700y+400z56000

800x+400y+500z63000

x0,y0

&z=100-x-y

%

2x+3y160

3x-y130

x0 y0

成本c=400+7x+5y

令7x+5y= (2x+3y)+ (3x-y)( 、 是待定系数)

则7x+5y=(2 +3 )x+(3 - )y

于是

2 +

3 =7

3 - =5

解得=2、 =1

%c=400+7x+5y=400+2(2x+3y) +(3x-y)400+2!160+130=850当且仅当

2x+3y=160

3x-y=130

即

x=50

y=20

时等号成立.

答:x为50千克,y为20千克,z为30千克时成本最低为850元.

需要说明的是,若所求的最优解是整数解,而用以上方法求得的最优解不是整数,则可以用平移法寻找到最优整数解.

12?中学理科#2002年第7期

考虑如下线性规划问题

考虑如下线性规划问题： Min z=60 x+402x+803x 1 . 3 x+22x+3x≥2 1 4 x+2x+33x≥4 1 2 x+22x+23x≥3 1 x,2x,3x≥0 1 要求：（1）写出其对偶问题； （2）用对偶单纯形法求解原问题； （3）用单纯形法求解其对偶问题； （4）对比（2）与（3）中每步计算得到的结果。 解：(1)设对应于上述约束条件的对偶变量分别为 y,2y,3y；则 1 由原问题和对偶问题，可以直接写出对偶问题为： Max Z’=2 y+42y+33y 1 3 y+42y+23y≤60 1 2 y+2y+23y≤40 1 y+32y+23y≤80 1 y,2y,3y≥0 1 (2)用对偶单纯形法求解原问题（添加松弛变量 x,5x,6x） 4 MaxZ= -60 x-402x-803x+04x+05x+06x 1 -3 x-22x-3x+4x=-2 1 -4 x-2x-33x+5x=-4 1 -2 x-22x-23x+6x=-3 1

1x ,2x ,3x ≥0 建立此问题的初始单纯形表，可见： 从表中可以看到，检验数行对应的对偶问题的解是可行解。因b 列数字为负，故需进行迭代运算。 换出变量的确定，计算min （-2，-4，-3）=-4，故5x 为换出变量。 换入变量的确定，计算得15,40，80/3,故1x 为换入变量。

由表可知，6x 为换出变量。2x 为换入变量。然后继续画单纯形表： 可得4x 为换出变量，3x 为换入变量。继续做单纯形表：

所以此问题的最优解为X=（11/10,19/30，1/10），此对偶问题的最优解为Y=（16,12,30），原问题的最小值为118/3. （3）MaxZ ’=21y +42y +33y +04y +05y +06y 31y +42y +23y +4y =60 21y +2 y +23y +5y =40 1y +32y +23y +6y =80 1y ,2y ,3y ,4y ,5y ,6y ≥0 然后建立单纯形表，可得 i

线性规划计算方法

线性规划法的数学模型如下： 设X1，X2，X3，…，X n为各变量，n为变量个数，m为约束条件数，a ij(i＝1，2…,m；j＝1，2…,n)为各种系数，b1,b2,b3,…，b m为常数，C1，C2,C3,…C n为目标函数系数，Z为目标值，则线性规划模型如下： a11X1＋a12X2＋…＋a1n X n≥(＝≤)b1 a21X1＋a22X2＋…＋a2n X n≥(＝≤)b2 ………………… a m1X1＋a m2X2＋…＋a mn X n≥(＝≤) b m X1，X2，…，X n≥0 目标函数Zmin（max）＝C1X1＋C2X2十…＋C n X n 线性规划计算方法: 鲜花店向李大民预定两种花卉——百合、玫瑰。其中每株收购价百合为4元,玫瑰为3元,鲜花店需要百合在1100～1400株之间,玫瑰在800～1200株之间,李大民只有资金5000元, 要去购买良种花苗, 在自家902m的温室中培育,每株苗价百合为2.5元,玫瑰为2元,由于百合与玫瑰生长所需采光条件的不同,百合每株大约占地0.052m，玫瑰每株大约占地0.032m，应如何配置才能使李大民获利最大? 数学建模：设种百合x1 株,玫瑰x2 株,则 2. 5 x1 + 2 x2 ≤5000 0. 05 x1 + 0. 03 x2 ≤90 x1 ≥1100 x1 ≤1400 x2 ≥800

x2 ≤1200 目标函数求最大值(即获利)Max z = (4 - 2. 5) x1 + (3 - 2) x2 = 1. 5 x + x1 可以看出,变量数为2,约束方程数为6,目标函数求最大值,打开线性规划计算软件,输入如下所示: 输入完成后点“计算”按纽，即可完成计算结果如下图：

考虑如下线性规划问题

考虑如下线性规划问题

考虑如下线性规划问题： Min z=60 x+402x+803x 1 s.t. 3 x+22x+3x≥2 1 4 x+2x+33x≥4 1 2 x+22x+23x≥3 1 x,2x,3x≥0 1 要求：（1）写出其对偶问题； （2）用对偶单纯形法求解原问题； （3）用单纯形法求解其对偶问题； （4）对比（2）与（3）中每步计算得到的结果。 解：(1)设对应于上述约束条件的对偶变量分别为 y,2y,3y；则由原问 1 题和对偶问题，可以直接写出对偶问题为： Max Z’=2 y+42y+33y 1 s.t 3 y+42y+23y≤60 1 2 y+2y+23y≤40 1 y+32y+23y≤80 1 y,2y,3y≥0 1 (2)用对偶单纯形法求解原问题（添加松弛变量 x,5x,6x） 4 MaxZ= -60 x-402x-803x+04x+05x+06x 1 s.t -3 x-22x-3x+4x=-2 1 -4 x-2x-33x+5x=-4 1 -2 x-22x-23x+6x=-3 1

x,2x,3x≥0 1 建立此问题的初始单纯形表，可见： 从表中可以看到，检验数行对应的对偶问题的解是可行解。因b列数字为负，故需进行迭代运算。 换出变量的确定，计算min（-2，-4，-3）=-4，故 x为换出变量。 5 换入变量的确定，计算得15,40，80/3,故 x为换入变量。 1 由表可知， x为换出变量。2x为换入变量。然后继续画单纯形表： 6

可得 x为换出变量，3x为换入变量。继续做单纯形表： 4 所以此问题的最优解为X=（11/10,19/30，1/10），此对偶问题的最优解为Y=（16,12,30），原问题的最小值为118/3. （3）MaxZ’=2 y+42y+33y+04y+05y+06y 1 s.t 3 y+42y+23y+4y=60 1 2 y+2y+23y+5y=40 1 y+32y+23y+6y=80 1 y,2y,3y,4y,5y,6y≥0 1 然后建立单纯形表，可得

线性规划问题求解

高中线性规划问题简析 何江南 数学与信息学院学科教学专业 2014级 摘要：线性规划问题是高中阶段一个比较重要的知识点，它是在学习了不等式的基础上，对不等式的应用及延伸。解决线性规划问题是沟通几何知识和代数知 识的桥梁是，数形结合思想的集中体现。高中线性规划一般考的比较简单，但类 型比较多，比较繁琐。因而高中阶段很多学生线性规划这个知识点掌握的不够好， 在考试中经常失分。本文主要针对高中阶段学生作图难的情况，总结了可行域的 画法、简单的线性规划问题的分类、以及解决一些简单线性规划问题的简便方法。 关键词：线性规划问题;作图;分类;简便方法 一、线性规划问题在中学的作用和地位 线性规划这节课是在学习了直线方程和不等式的基础上，介绍直线方程的一 个简单应用，反映了对数学知识在实际应用方面的重视．在实际生活中，经常会 遇到在一定的人力、物力、财力等资源条件下，如何精打细算巧安排的问题.用 最少的资源取得最大的效益就是线性规划研究的基本内容．中学所学的线性规划 体现了数学的工具性、应用性，同时渗透了化归、数形结合的数学思想。因此， 本节内容的学习，既是对前面所学知识的深化与拓展，又是提高学生解决实际问 题能力的一种途径，更是加强学生应用意识的良好素材；其次就是为高等数学的 学习打下基础；而且线性规划问题也经常在高考中出现。 二、线性规划问题的求解步骤 简单线性规划问题就是求线性目标函数在线性约束条件下的最优解；有的是以应用题的形式给出，无论此类题目是以什么实际问题提出，其求解的格式与步骤是不变的： （1）寻找线性约束条件，线性目标函数； （2）由二元一次不等式表示的平面区域做出可行域； （3）在可行域内求目标函数的最优解。 在解此类题目时要注意，在实际问题中有些隐含的约束条件，因此在寻找约束条件的时候一定要把所有的约束条件全，还有的题目直接给出约束条件，要求求出目标函数的最优解，相对于第一类问题来说，此类问题相对简单，因为不必去找约束条件。 可行域的画法： 准确的画出可行域是求解线性规划问题的前提，画出可行域最根本的问题是确定二元一次不等式所表示的区域，确定二元一次不等式所表示的平面区域有

2021届高考数学一轮知能训练：第六章第4讲 简单的线性规划

第4讲 简单的线性规划 1．(2019年北京)若x ，y 满足|x |≤1－y ，且y ≥－1，则3x ＋y 的最大值为( ) A ．－7 B ．1 C ．5 D ．7 2．(2019年四川成都模拟)设实数x ，y 满足不等式组???? ? y ≥0，x －y ≥0， 2x －y －2≥0，则ω＝y －1 x ＋1 的取值 范围是( ) A.????－12，1 B.????－1 2，1 C.????12，1 D.??? ?1 2，1 3．(2014年新课标Ⅰ)设x ，y 满足约束条件? ???? x ＋y ≥a ，x －y ≤－1，且z ＝x ＋ay 的最小值为7，则 a ＝( ) A ．－5 B ．3 C ．－5或3 D ．5或－3 4．设二元一次不等式组???? ? x ＋2y －19≥0，x －y ＋8≥0， 2x ＋y －14≤0 所表示的平面区域为M ，使函数y ＝a x (a ＞0， a ≠1)的图象过区域M 的a 的取值范围是( ) A ．[1,3] B ．[2，10] C ．[2,9] D ．[10，9] 5．x ，y 满足约束条件???? ? x ＋y －2≤0，x －2y －2≤0， 2x －y ＋2≥0.若z ＝y －ax 取得最大值的最优解不唯一，则实 数a 的值为( ) A.12或－1 B ．2或12 C ．2或1 D ．2或－1 6．已知x ，y 满足约束条件???? ? x ≥0，3x ＋4y ≥4， y ≥0， 则x 2＋y 2＋2x 的最小值是( ) A.2 5 B.2－1 C.24 25 D ．1 7．不等式组???? ? y ≥0，x －y －1≥0， 3x －2y －6≤0 表示的平面区域的面积等于________．

《运筹学》习题线性规划部分练习题及答案

《运筹学》线性规划部分练习题 一、思考题 1．什么是线性规划模型，在模型中各系数的经济意义是什么？ 2．线性规划问题的一般形式有何特征？ 3．建立一个实际问题的数学模型一般要几步？ 4．两个变量的线性规划问题的图解法的一般步骤是什么？ 5．求解线性规划问题时可能出现几种结果，那种结果反映建模时有错误？ 6．什么是线性规划的标准型，如何把一个非标准形式的线性规划问题转化成标准形式。 7．试述线性规划问题的可行解、基础解、基础可行解、最优解、最优基础解的概念及它们之间的相互关系。 8．试述单纯形法的计算步骤，如何在单纯形表上判别问题具有唯一最优解、有无穷多个最优解、无界解或无可行解。 9．在什么样的情况下采用人工变量法，人工变量法包括哪两种解法？ 10．大M 法中，M 的作用是什么？对最小化问题，在目标函数中人工变量的系数取什么？最大化问题呢？ 11．什么是单纯形法的两阶段法？两阶段法的第一段是为了解决什么问题？在怎样的情况下，继续第二阶段？ 二、判断下列说法是否正确。 1．线性规划问题的最优解一定在可行域的顶点达到。 2．线性规划的可行解集是凸集。 3．如果一个线性规划问题有两个不同的最优解，则它有无穷多个最优解。 4．线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大。 5．线性规划问题的每一个基本解对应可行域的一个顶点。 6．如果一个线性规划问题有可行解，那么它必有最优解。 7．用单纯形法求解标准形式（求最小值）的线性规划问题时，与 > j σ 对应的变量都 可以被选作换入变量。 8．单纯形法计算中，如不按最小非负比值原则选出换出变量，则在下一个解中至少有一个基变量的值是负的。 9．单纯形法计算中，选取最大正检验数k σ对应的变量k x作为换入变量，可使目标函数值得到最快的减少。 10．一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。 三、建立下面问题的数学模型 1．某公司计划在三年的计划期内，有四个建设项目可以投资：项目Ⅰ从第一年到 第三年年初都可以投资。预计每年年初投资，年末可收回本利120% ，每年又可以重新将所获本利纳入投资计划；项目Ⅱ需要在第一年初投资，经过两年可收回本利150% ，又可以重新将所获本利纳入投资计划，但用于该项目的最大投资额不得超过20万元；项目Ⅲ需要在第二年年初投资，经过两年可收回本利160% ，但用于该项目的最大投资额不得超过15万元；项目Ⅳ需要在第三年年初投资，年末可收回本利140% ，但用于该项目的最大投资额不得超过10万元。在这个计划期内，该公司第一年可供投资的资金有30万元。问怎样的投资方案，才能使该公司在这个计划期获得最大利润？ 2．某饲养场饲养动物，设每头动物每天至少需要700克蛋白质、30克矿物质、100克维生素。现有五种饲料可供选用，各种饲料每公斤营养成分含量及单 价如下表2—1所示：

线性规划的方法及应用

线性规划的方法及应用 1 引言 运筹学最初是由于第二次世界大战的军事需要而发展起来的，它是一种科学方法，是一种以定量的研究优化问题并寻求其确定解答的方法体系．线性规划（Linear Progromming ，简称LP ）是运筹学的一个重要分支，其研究始于20世纪30年代末，许多人把线性规划的发展列为20世纪中期最重要的科学进步之一．1947年美国的数学家丹泽格提出了一般的线性规划数学模型和求解线性规划问题的通用方法――单纯形法，从而使线性规划在理论上趋于成熟．此后随着电子计算机的出现，计算技术发展到一个高阶段，单纯形法步骤可以编成计算机程序，从而使线性规划在实际中的应用日益广泛和深入．目前，从解决工程问题的最优化问题到工业、农业、交通运输、军事国防等部门的计划管理与决策分析，乃至整个国民经济的综合平衡，线性规划都有用武之地，它已成为现代管理科学的重要基础之一． 2 线性规划的提出 经营管理中如何有效地利用现有人力物力完成更多的任务，或在预定的任务目标下，如何耗用最少的人力物力去实现．这类问题可以用数学语言表达，即先根据问题要达到的目标选取适当的变量，问题的目标通常用变量的函数形式（称为目标函数），对问题的限制条件用有关变量的等式或不等式表达（称为约束条件）．当变量连续取值，且目标函数和约束条件为线性时，称这类模型为线性规划的模型．有关对线性规划问题建模、求解和应用的研究构成了运筹学中的线性规划分支．线性规划实际上是:求一组变量的值，在满足一组约束条件下，求得目标函数的最优解.从而线性规划模型的基本结构为： ①变量：变量又叫未知数，它是实际系统的位置因素，也是决策系统中的可控因素，一般称为决策变量，常引用英文字母加下标来表示，如n x x x ,,,21 等． ②目标函数：将实际系统的目标用数学形式表示出来，就称为目标函数，线性规划的目标函数是求系统目标的数值，即极大值（如产值极大值，利润极大值）或极小值（如成本极小值，费用极小值等等）． ③约束条件：约束条件是指实现系统目标的限制因素．它涉及到企业内部条件和外部环境的各个方面，如原材料供应设备能力、计划指标．产品质量要求和市场销售状态等等，这些因素都对模型的变量起约束作用，故称其为约束条件．约束条件的数学表示有三种，即 ,,,线性规划的变量应为非负值，因为变量在实际问题中所代表的均为实物，所以不能为负． 线性规划问题有多种形式，函数有的要求实现最大化，有的要求最小化；约束条件可以是“ ”，

《运筹学》习题线性规划部分练习题及答案.doc

《运筹学》线性规划部分练习题 一、思考题 1． 什么是线性规划模型，在模型中各系数的经济意义是什么？ 2． 线性规划问题的一般形式有何特征？ 3． 建立一个实际问题的数学模型一般要几步？ 4． 两个变量的线性规划问题的图解法的一般步骤是什么？ 5． 求解线性规划问题时可能出现几种结果，那种结果反映建模时有错误？ 6． 什么是线性规划的标准型，如何把一个非标准形式的线性规划问题转化成标准形式。 7． 试述线性规划问题的可行解、基础解、基础可行解、最优解、最优基础解的概念及它们之间的相互关系。 8． 试述单纯形法的计算步骤，如何在单纯形表上判别问题具有唯一最优解、有无穷多个最优解、无界解或无可行解。 9． 在什么样的情况下采用人工变量法，人工变量法包括哪两种解法？ 10．大M 法中，M 的作用是什么？对最小化问题，在目标函数中人工变量的系数取什么？最大化问题呢？ 11．什么是单纯形法的两阶段法？两阶段法的第一段是为了解决什么问题？在怎样的情况下，继续第二阶段？ 二、判断下列说法是否正确。 1． 线性规划问题的最优解一定在可行域的顶点达到。 2． 线性规划的可行解集是凸集。 3． 如果一个线性规划问题有两个不同的最优解，则它有无穷多个最优解。 4． 线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大。 5． 线性规划问题的每一个基本解对应可行域的一个顶点。 6． 如果一个线性规划问题有可行解，那么它必有最优解。 7． 用单纯形法求解标准形式（求最小值）的线性规划问题时，与0 >j σ对应的变量都可以被选作换入变量。 8． 单纯形法计算中，如不按最小非负比值原则选出换出变量，则在下一个解中至少有一个基变量的值是负的。 9． 单纯形法计算中，选取最大正检验数k σ对应的变量k x 作为换入变量，可使目 标函数值得到最快的减少。 10． 一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。 三、建立下面问题的数学模型 1． 某公司计划在三年的计划期内，有四个建设项目可以投资：项目Ⅰ从第一年到 第三年年初都可以投资。预计每年年初投资，年末可收回本利120% ，每年又可以重新将所获本利纳入投资计划；项目Ⅱ需要在第一年初投资，经过两年可收回本利150% ，又可以重新将所获本利纳入投资计划，但用于该项目的最大投资额不得超过20万元；项目Ⅲ需要在第二年年初投资，经过两年可收回本利160% ，但用于该项目的最大投资额不得超过15万元；项目Ⅳ需要在第三年年初投资，年末可收回本利140% ，但用于该项目的最大投资额不得超过10万元。在这个计划期内，该公司第一年可供投资的资金有30万元。问怎样的投资方案，才能使该公司在这个计划期获得最大利润？ 2．某饲养场饲养动物，设每头动物每天至少需要700克蛋白质、30克矿物质、 100克维生素。现有五种饲料可供选用，各种饲料每公斤营养成分含量及单 价如下表2—1所示：

线性规划习题

第一章 线性规划习题 1. 将下列线性规划问题变换成标准型，并列出初始单纯形表。 1) min Z ＝－3x 1＋4x 2－2x 3＋5x 4 s.t.???????≥≥+-+-≤-++-=-+-. ,0,,22321432244321432143214321无约束x x x x x x x x x x x x x x x x 2) max S ＝z x ／p k s.t.???? ????? ==≥=-=-=∑∑∑===).,...,2,1;,...,2,1(0),,...,2,1(1, 1 11 m k n i x n i x x a z ik m k ik n i m k ik ik k 2. 分别用单纯法中的大M 法和两阶段法求解下述线性规划问题： min Z ＝2x 1＋3x 2＋x 3 s.t.??? ??≥≥+≥++.0,,,623,8243 212 1321x x x x x x x x 并指出该问题的解属哪一类解。 3. 【表1-6】是某求极大化线性规划问题计算得到单纯形表。表中无人工变量， a 1, a 2, a 3, d , c 1, c 2为待定常数。试说明这些常数分别取何值时，以下结论成立。 1) 表中解为唯一最优解； 2) 表中解为最优解，但存在无穷多最优解； 3) 该线性规划问题具有无界解； 4) 表中解非最优，为对解进行改进，换入变量为x 1，换出变量为x 6。 表1-6 4. 某饲料厂用原料A 、B 、C 加工成三种不同牌号的饲料甲、乙、丙。已知各 种牌号饲料中A 、B 、C 含量，原料成本，各种原料的每月限制用量，三种牌号的饲料的单位加工费及售价如【表1-7】所示。 表1-7

考虑如下线性规划问题

考虑如下线性规划问题： Min z=60 x1+40 x2 +80 x3 s.t. 3 x1 +2 x2 + x3 2 4x1 +x2 +3x3 4 2x1 +2x2 +2x3 3 x1 , x2 , x3 0 要求：（1）写出其对偶问题； （2）用对偶单纯形法求解原问题； （3）用单纯形法求解其对偶问题； （4）对比（2）与（3）中每步计算得到的结果。解：（1）设对应于上述约束条件的对偶变量分别为y1,y2, y3 ；则由原问题和对偶问题，可以直接写出对偶问题为： Max Z'=2 y1+4 y2+3 y3 s.t 3y1+4 y2+2 y3 60 2y1+y2+2 y3 40 y1 +3y2 +2 y3 80 y1,y2,y3 0 （2）用对偶单纯形法求解原问题（添加松弛变量x4 ,x5 , x6 ）MaxZ= -60 x1 -40x2-80x3 +0x4 +0x5 +0x6 s.t -3x1 -2x2- x3+ x4 =-2 -4x1-x2-3x3+x5=-4 -2 x1-2 x2-2 x3+x6=-3

X i, X2 , X3 0 建立此问题的初始单纯形表，可见: 从表中可以看到，检验数行对应的对偶问题的解是可行解。因b列数字为负，故需进行迭代运算。 换出变量的确定，计算min (-2,-4, -3)=-4，故x为换出变量。换入变量的确定，计算得15,40, 80/3,故x i为换入变量。 由表可知，X6为换出变量。X2为换入变量。然后继续画单纯形表:

X i, X2 , X3 0

可得X4为换出变量，X3为换入变量。继续做单纯形表: 所以此问题的最优解为X= （11/10,19/30, 1/10）,此对偶问题的最优解为Y二（16,12,30），原问题的最小值为118/3. （3）MaxZ '2 y1+4 y2 +3 y +0 y +0 * +0 y S.t 3 y1+4 y2+2 y3+ y4=60 2 y1 + y2 +2 y 3 + y =40 y1 +3y2+2 出 + y6=80 y1, y2, y3, y4, y5, y6 0 然后建立单纯形表，可得

线性规划化问题的简单解法

简单线性规划问题的几种简单解法 依不拉音。司马义（吐鲁番市三堡中学，838009） “简单的线性规划问题”属于高中数学新课程必修5，进入了高考试题，并且保持了较大的考察比例，几乎是每年高考的必考内容，也是高中数学教学的一个难点。 简单的线性规划是指目标函数只含两个自变量的线性规划。简单线性规划问题的标准型为： 1112220(0)0(0),(),0(0) m m m A x B y C A x B y C m N z Ax By A x B y C +++≥≤??++≥≤?∈=+???++≥≤?L 约束条件 目标函数 ， 下面介绍简单线性规划问题的几种简单解法。 1. 图解法 第一步、画出约束条件表示的可行区域，这里有两种画可行区域的方法。 ⑴代点法：直线Ax+By+C=0（c 不为0）的某侧任取一点，把它的坐标代入不等式，若不等式成立，则不等式表示的区域在该点的那一侧；若不成立，则在另一侧。 ⑵B 判别法：若Ｂ＞0（＜０），则不等式Ax+By+C ＞0（＜０）表示的区域在直 线Ax+By+C ＝0的上方；若Ｂ＞０（＜０），则不等式Ax+By+C ＜０(＞0)表示的区域在直线Ax+By+C ＝0的下方。（即若B 与0的大小方向跟不等式的方向相同，则可行区域是边界线的上方；若B 与0的大小方向与不等式的方向相反，则可信分区域是边界线的下方） 用上面的两种方法画出可行区域是很简单，所以这里不必举例说明。 第二步、在画出的可行区域内求最优解（使目标函数取最大值或最小值的点），这 个可以用下面的两种办法解决。 ⑴y 轴上的截距法：若b >0，直线y a b x z b =- +所经过可行域上的点使其y 轴上的截距最大（最小）时，便是z 取得最大值（最小值）的点；若b <0，直线y a b x z b =-+所经过可行域上的点使其y 轴上的截距最大（最小）时，是z 取得最小值（最小值）的点（提醒：截距不是距离，截距可以取正负）。 例1．设x,y 满足约束条件x y y x y +≤≤≥???? ?10,,,求z x y =+2的最大值、最小值。 解：如图1作出可行域，因为y 的系数1大于0，目标函数z x y =+2表示直线 y x z =-+2在y 轴上的截距， 当直线过A （1，0）时，截距值最大z max =?+=2102，当直线过点O （0，0）时，截距值最小min 2000z =?+=。

线性规划单纯形法(例题)

《吉林建筑工程学院城建学院人文素质课线性规划单纯形法例题》 ? ? ??≥=+ +=+++++=?? ? ??≥≤+≤++=0 ,,,24 261553).(002max ,,0,24 261553).(2max 14.1843214213 214 321432121212 1x x x x x x x x x x t s x x x x z x x x x x x x x t s x x z 标准型得到该线性规划问题的，分别加入松驰变量在上述线性规划问题中法求解线性规划问题。分别用图解法和单纯形）】 （页【为初始基变量， 选择43,x x )1000(00)0010(01 )2050(12)6030(24321=?+?-==?+?-==?+?-==?+?-=σσσσ 为出基变量。为进基变量，所以选择41x x

3 /1)6/122/10(00 )0210(03 /1)3/1240(10)1200(24321-=?+-?-= =?+?-==?+?-==?+?-=σσσσ 为出基变量。 为进基变量，所以选择32x x 24 /724/528/11012/112/124/1100 021110 120124321-=?+-?-=-=-?+?-==?+?-==?+?-=）（）（）（）（σσσσ 4 33 4341522max , )4 3,415(),(2112= +?=+===x x z x x X T T 故有：所以，最优解为

??? ??? ?≥=+ +=+=+ ++++=?????? ?≥≤+≤≤+=0,,,,18232424).(0002max ,,,0 ,182312212 ).(52max 24.185432152142315 43215432121212 1x x x x x x x x x x x x t s x x x x x z x x x x x x x x x t s x x z 标准型得到该线性规划问题的，分别加入松驰变量在上述线性规划问题中法求解线性规划问题。分别用图解法和单纯形）】 （页【 )000010(00001000000000100520200052300010254321=?+?+?-==?+?+?-==?+?+?-==?+?+?-==?+?+?-=σσσσσ）（）（）（）（ 为出基变量。为进基变量，所以选择42x x

利用excel软件求解线性规划问题

下面我们通过一个例子来解释怎样用“规划求解”来求解数学规划问题。 例1 公司通常需要确定每月（或每周）生产计划，列出每种产品必须生产的数量。具体来说就是，产品组合问题就是要确定公司每月应该生产的每种产品的数量以使利润最大化。产品组合通常必须满足以下约束： ● 产品组合使用的资源不能超标。 ● 对每种产品的需求都是有限的。我们每月生产的产品不能超过需求的数量，因为生产过剩就是浪费（例如，易变质的药品）。 下面，我们来考虑让某医药公司的最优产品组合问题。该公司有六种可以生产的药品，相关数据如下表所示。 设该公司生产药品1～6的产量分别为126,,,x x x （磅），则最优产品组合的线性规划模型为 123456 123456123456123456max 6 5.3 5.4 4.2 3.8 1.86543 2.5 1.545003.2 2.6 1.50.80.70.316009609281041..977108410550,16j z x x x x x x x x x x x x x x x x x x x x x s t x x x x j =++++++++++≤??+++++≤??≤?≤??≤??≤?≤??≤??≥≤≤? 下面用规划求解加载宏来求解这个问题： 首先，如下如所示，在Excel 工作表内输入目标函数的系数、约束方程的系数、右端常数项；

其次，选定目标函数单元、可变单元、约束函数单元，定义目标函数、约束函数 其中，劳动力约束函数的定义公式是“=MMULT(B3:G3, J5:J10)”，原料约束函数的定义公式是“＝MMULT(B4:G4,J5:J10)”，目标函数的定义公式是“MMULT(B5:G5, J5:J10)”。 注：函数MMULT(B3:G3, J5:J10)的意义是：单元区B3:G3表示的行向量与单元区J5:J10表示的列向量的内积。这一要特别注意的是，第一格单元区必须是行，第二格单元区必须是列，并且两个单元区所含的单元格个数必须相等。 最后，打开规划求解参数设定对话框设定模型 （1）（2）目标函数和可边单元的设定很简单，在此就不再赘述 （3）约束条件的设定 (3.1) 约束条件1234561234566543 2.5 1.545003.2 2.6 1.50.80.70.31600x x x x x x x x x x x x +++++≤??+++++≤? 的设定： 系数矩阵 目标函数的系数 系数矩阵右端常数 可变单元 约束函数单元 目标函数单元

图解法和单纯形法求解线性规划问题

图解法和单纯形法求解以下线性规划问题 1.1 图解法解线性规划问题 只含两个变量的线性规划问题，可以通过在平面上作图的方法求解，步骤如下： (1)以变量x1为横坐标轴，x2为纵坐标轴，适当选取单位坐标长度建立平面坐标直 角坐标系。由变量的非负性约束性可知，满足该约束条件的解均在第一象限内。 (2)图示约束条件，找出可行域（所有约束条件共同构成的图形）。 (3)画出目标函数等值线，并确定函数增大（或减小）的方向。 (4)可行域中使目标函数达到最优的点即为最优解。 然而，由于图解法不适用于求解大规模的线性规划问题，其实用意义不大。 1.2 单纯形法解线性规划问题 它的理论根据是：线性规划问题的可行域是n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。 单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。 单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。 1.3 线性规划问题的标准化 使用单纯形法求解线性规划时，首先要化问题为标准形式

运筹学--线性规划问题最优解的确定与改进

线性规划问题最优解的确定与改进 线性规划是运筹学的一个重要分支。自1947年丹捷格（G.B.Dantzig ）提出了一般线性规划问题求解的方法——单纯形法之后，线性规划在理论上趋向成熟，在实用中日益广泛与深入。线性规划最优解求解问题，在《运筹学》本科版给出了图解法和单纯形法。 一般线性规划问题的标准型为： 1 max (14)n j j i z c x ==-∑ 1,1,2(15)0,1,2,(16) n i j j i j j a x b i m x j n ===-≥=-?∑???? 满足约束条件（1-5）式、（1-6）式的解12(,,,)T n X x x x = ，称为线性规划问题的可行解，其中使目标函数达到最大值的可行解称为最优解。 2009年中国科教创新导刊，第三十期李高秀写的《线性规划中最优解的准确确定》中详细介绍了图解法的过程，图解法适合于二元线性规划问题，对于多元线性规划问题图解法相对较难。 图解法过程： 1 线性目标函数最值的分析 对于线性目标函数Z=ax+by ，若b ≠0时，目标函数可变为a z y x b b =-+，则是直线a z y x b b =-+在y 轴上的截距。 (1)b>0时，随着直线a z y x b b =-+的平移，直线在与可行域有公共点的条件下，它在y 轴上的截距 z b 最大时z 最大；当z b 最小时z 最小。 (2)b<0时，随着直线a z y x b b =-+的平移，直线在与可行域有公共点的条件下，它在y 轴上的 截距z b 最大时z 最小；当z b 最小时z 最大。 由以上两点可知，要求线性目标函数z=ax+by 的最大最小值要注意y 的系数b 的正负和平移直线在y 轴上的截距。 2 在图上分别作出约束函数和目标函数，平移目标函数线到可行域的交点时，要把目标函数的斜率与相交于这一点的直线的斜率进行比较 上述的最值分析是确定平移目标函数的大概方向，而这次是确定最优解的确凿位置。斜率比较大

《运筹学》使用Excel求解线性规划问题

第三节 使用Excel 求解线性规划问题 利用单纯形法手工计算线性规划问题是很麻烦的。office 软件是一目前常用的软件，我们可以利用office 软件中的Excel 工作表来求解本书中的所有线性规划问题。对于大型线性规划问题，需要应用专业软件，如Matlab ，Lindo ，lingo 等，这些软件的使用这里我们不作介绍，有需要的，自己阅读有关文献资料。 用Excel 工作表求解线性规划问题，我们需要先设计一个工作表，将线性规划问题中的有关数据填入该工作表中。所需的工作表可按下列步骤操作： 步骤1 确定目标函数系数存放单元格，并在这些单元格中输入目标函数系数。 步骤2 确定决策变量存放单元格，并任意输入一组数据。 步骤3 确定约束条件中左端项系数存放单元格，并输入约束条件左端项系数。 步骤4 在约束条件左端项系数存放单元格右边的单元格中输入约束条件左端项的计算公式，计算出约束条件左端项对应于目前决策变量的函数值。 步骤5 在步骤4的数据右边输入约束条件中右端项（即常数项）。 步骤6 确定目标函数值存放单元格，并在该单元格中输入目标函数值的计算公式。 例 建立如下线性规划问题的Excell 工作表： 12 121 21212max 1502102310034120..55150,0 z x x x x x x s t x x x x =++≤??+≤??+≤??≥? 解：下表是按照上述步骤建立的线性规划问题的Excell 工作表。 其中： D4=B2*B4+C2*C4, D5=B2*B5+C2*C5 , D6=B2*B6+C2*C6, C7= B2*B1+C2*C1 。 建立了Excel 工作表后，就可以利用其中的规划求解功能求相应的线性规划问题的解。求解步骤如下： 步骤1 单击[工具]菜单中的[规划求解]命令。 步骤2 弹出[规划求解参数]对话框，在其中输入参数。置目标单元格文本框中输入目标单元格；[等于]框架中选中[最大值＼最小值］单选按钮。 步骤3 设置可变单元格区域，按Ctrl 键，用鼠标进行选取，或在每选一个连续区域后，在其后输入逗号“，”。 步骤4 单击[约束］框架中的[添加]按钮。 步骤5 在弹出的[添加约束]对话框个输入约束条件． 步骤6 单击[添加]按钮、完成一个约束条件的添加。重复第5步，直到添加完所有条件 步骤7 单击[确定]按钮，返回到[规划求解参数]对话框，完成条件输入的[规划

考虑如下线性规划问题

考虑如下线性规划问题: Min z=60 x+402x+803x 1 s、t、3 x+22x+3x≥2 1 4 x+2x+33x≥4 1 2 x+22x+23x≥3 1 x,2x,3x≥0 1 要求:(1)写出其对偶问题; (2)用对偶单纯形法求解原问题; (3)用单纯形法求解其对偶问题; (4)对比(2)与(3)中每步计算得到的结果。 解:(1)设对应于上述约束条件的对偶变量分别为 y,2y,3y;则由原问题 1 与对偶问题,可以直接写出对偶问题为: Max Z’=2 y+42y+33y 1 s、t 3 y+42y+23y≤60 1 2 y+2y+23y≤40 1 y+32y+23y≤80 1 y,2y,3y≥0 1 (2)用对偶单纯形法求解原问题(添加松弛变量 x,5x,6x) 4 MaxZ= -60 x-402x-803x+04x+05x+06x 1 s、t -3 x-22x-3x+4x=-2 1 -4 x-2x-33x+5x=-4 1 -2 x-22x-23x+6x=-3 1

x,2x,3x≥0 1 建立此问题的初始单纯形表,可见: 从表中可以瞧到,检验数行对应的对偶问题的解就是可行解。因b列数字为负,故需进行迭代运算。 换出变量的确定,计算min(-2,-4,-3)=-4,故 x为换出变量。 5 换入变量的确定,计算得15,40,80/3,故 x为换入变量。 1 由表可知, x为换出变量。2x为换入变量。然后继续画单纯形表: 6

可得 x为换出变量,3x为换入变量。继续做单纯形表: 4 所以此问题的最优解为X=(11/10,19/30,1/10),此对偶问题的最优解为Y=(16,12,30),原问题的最小值为118/3、 (3)MaxZ’=2 y+42y+33y+04y+05y+06y 1 s、t 3 y+42y+23y+4y=60 1 2 y+2y+23y+5y=40 1 y+32y+23y+6y=80 1 y,2y,3y,4y,5y,6y≥0 1 然后建立单纯形表,可得

线性规划模拟练习

综合练习 一、填空题 1、线性规划的解有唯一最优解、无穷多最优解、 无界解 和无可行解四种。 2、在求运费最少的调度运输问题中，如果某一非基变量的检验数为4，则说明 如果在该空格中增加一个运量运费将增加4 。 3、“如果线性规划的原问题存在可行解，则其对偶问题一定存在可行解”，这句话对还是错？ 错 4、如果某一整数规划： MaxZ=X 1+X 2 X 1+9/14X 2≤51/14 -2X 1+X 2≤1/3 X 1,X 2≥0且均为整数 所对应的线性规划（松弛问题）的最优解为X 1=3/2，X 2=10/3，MaxZ=6/29，我们现在要对X 1进行分枝，应该分为 X 1≤1 和 X 1≥2 。 5. 假设某线性规划的可行解的集合为D ，而其所对应的整数规划的可行解集合为B ，那么D 和B 的关系为 D 包含 B 6. 已知下表是制订生产计划问题的一张LP 最优单纯形表（极大化问题，约束条 问：（1）写出B -1 =???? ? ??---1003/20.3/131 2 (2)对偶问题的最优解： Y ＝（5，0，23，0，0）T 7. 极大化的线性规划问题为无界解时，则对偶问题_无解_________； 8. 知下表是制订生产计划问题的一张LP 最优单纯形表（极大化问题，约束条件

问：(1)对偶问题的最优解： Y ＝(4,0,9,0,0,0)T （2）写出B -1= ??? ? ? ??611401102 二、计算题 1、已知线性规划 MaxZ=3X 1+4X 2 1+X 2≤5 2X 1+4X 2≤12 3X 1+2X 2≤8 1,X 2≥0 2）若C 2从4变成5，最优解是否会发生改变，为什么？ 3）若b 2的量从12上升到15，最优解是否会发生变化，为什么？ 4）如果增加一种产品X 6，其P 6=(2,3,1)T ，C 6=4该产品是否应该投产？为什么？ 解： 1)对偶问题为 Minw=5y1+12y2+8y3 y1+2y2+3y 3≥3 y1+4y2+2y 3≥4 y1,y2≥0 2)当C 2从4变成5时， σ4=-9/8 σ5=-1/4 由于非基变量的检验数仍然都是小于0的，所以最优解不变。 3）当若b 2的量从12上升到15 X ＝9/8

线性规划方法总结(自)

.【方法总结】 1．最优解问题 如果可行域是一个多边形，那么目标函数一般在某顶点处取得最大值或最小值，最优解就是该点的坐标，到底哪个顶点为最优解，只要将目标函数的直线平行移动，最先通过或最后通过的顶点便是．特别地，当表示线性目标函数的直线与可行域的某条边平行时(k＝k1)，其最优解可能有无数个． 【方法总结】常见的目标函数有 (1)截距型：形如z＝ax＋by. 求这类目标函数的最值常将函数z＝ax＋by转化为直线的斜截式：y＝－abx＋zb，通过求直线的截距zb的最值间接求出z的最值． (2)距离型：形如z＝(x－a)2＋(y－b)2. (3)斜率型：形如z＝y－bx－a. 【方法总结】解答线性规划应用题的一般步骤可归纳为： (1)审题——仔细阅读，明确有哪些限制条件，目标函数是什么？ (2)转化——设元．写出约束条件和目标函数; (3)求解——关键是明确目标函数所表示的直线与可行域边界直线斜率间的关系； (4)作答——就应用题提出的问题作出回答． 体现考纲中要求会从实际问题中抽象出二元线性规划.来年需要注意简单的线性规划求最值问题. 三．规律总结 一种方法 确定二元一次不等式表示的平面区域时，经常采用“直线定界，特殊点定域”的方法． (1)直线定界，即若不等式不含等号，则应把直线画成虚线；若不等式含有等号，把直线画成实线． (2)特殊点定域，即在直线Ax＋By＋C＝0的某一侧取一个特殊点(x0，y0)作为测

试点代入不等式检验，若满足不等式，则表示的就是包括该点的这一侧，否则就表示直线的另一侧．特别地，当C ≠0时，常把原点作为测试点；当C ＝0时，常选点(1,0)或者(0,1)作为测试点． 一个步骤 利用线性规划求最值，一般用图解法求解，其步骤是： (1)在平面直角坐标系内作出可行域； (2)考虑目标函数的几何意义，将目标函数进行变形； (3)确定最优解：在可行域内平行移动目标函数变形后的直线，从而确定最优解； (4)求最值：将最优解代入目标函数即可求出最大值或最小值． 两个防范 (1)画出平面区域．避免失误的重要方法就是首先使二元一次不等式标准化． (2)求二元一次函数z ＝ax ＋by(ab ≠0)的最值，将函数z ＝ax ＋by 转化为直线的斜截式：y ＝－abx ＋zb ，通过求直线的截距zb 的最值间接求出z 的最值．要注意：当b ＞0时，截距zb 取最大值时，z 也取最大值；截距zb 取最小值时，z 也取最小值；当b ＜0时，截距zb 取最大值时，z 取最小值；截距zb 取最小值时，z 取最大值． (经典习题)已知平面直角坐标系xOy 上的区域D 由不等式组??? 0≤x ≤ 2，y ≤2， x ≤ 2y 给定．若M (x ，y )为D 上的动点，点A 的坐标为(2，1)则z ＝OM →·O A →的最大值为 ( B )． A ．3 B ．4 C ．3 2 D ．4 2