1、*第十一章线第十一章线 性性 规规 划划 初初 步步(一)本 章 内 容 小 结(二)常见问题分类及解法(一一)本章内容小结本章内容小结一、本章主要内容一、本章主要内容1、几个概念：线性规划问题，决策变量，约束条件，目标函数，可行解，可行解域。最优解，可行基，基变量，单纯形表。2、建立线性规划问题的数学模型，图解法，单纯形方法。二、本章重点、难点二、本章重点、难点1、重点：如何建立线性规划问题的数学模型，用图解法，单纯形方法求解线性规划问题。2、难点：决策变量的选取，用图解法求解时可行解域的确定，单纯形方法的判断。三、对学习的建议三、对学习的建议 复习二次不等式的解法及几何意义，掌握线性代数中
2、有关矩阵的初等变换，向量的线性相关性。四、本章关键词四、本章关键词线性规划问题可行解可行基标准形单纯形(二二)常见问题分类及解法常见问题分类及解法一、建立线性规划问题的数学模型一、建立线性规划问题的数学模型 应用线性规划方法解决实际问题，其首要的、关键的一步是建立揭示实际问题本质内容的线性规划问题的数学模型，通常分以下几个步骤。分析问题，搞清实际问题的背景，抓住主要矛盾，明确该问题所要实现的目标与受到的限制，为了建模方便，可以将已知条件列成表格的形式。将决策中关键的量，即实际问题中待求的量设为决策变量，并注意到这些决策变量一般都受到非负约束，然后，将问题的限制条件表示成决策变量的线性等式或不等
3、式。明确目标是最大值还是最小值，从所求的实际问题出发，将目标函数表示为决策变量的线性函数。例例1 1 某厂用A、B、C三种原材料生产甲、乙两种产品。每生产一件甲种产品耗费材料A为9kg，B为3kg，C为4kg，可获利700元；每生产一件乙产品需要消耗4kg的A，10kg的B，5kg的C，可获利1200元，现在原材料360kg的A、300kg的B和200kg的C，怎样安排生产才能使获得的利润最大？解解将已知条件列表见表11-1.表11-1 原料消耗表/kg原料产品甲乙原料9344 10 5 ABC360300200单利/(百元/件)7121212设生产甲产品 件，生产乙种产品 件可获利 元，由已
4、知，受到所给原料数的限制，则该规划问题的数学模型为xxSxx12求一组决策变量，的值，使其满足约束条件：xx1212121212943603103004520000(,)，xxxxxxxxx xZ12712并使目标函数 取得最大值.Sxx二、用图解法求解线性规划问题二、用图解法求解线性规划问题 由二元一次不等式的求解方法，将只含两个决策变量的线性规划问题的解通过作图求出，其求解步骤如下：(1)将满足每一个约束条件的解在平面直角坐标系中表示出来，求出满足所有约束条件的公共解。即可行解域；(2)做两条目标函数的等值线，并判断因目标函数值的变化导致等值线位置变化的情况；(3)平移等值线至可行解域，找
5、出距原点(S=0)最远或最近的点或线段，若存在，则线性规划问题的最优解存在，否则，规划问题无解。121221212min232:.32100 用图解法求解，如图11-1所示。，SxxxxxStxxxx例例2 2解解1201 将满足所有约束条件的解在直角坐标系 中表示出来，为该问题的可行解域.令,做两条等值线.显然向上平移等值线.目标函数值变小，过可行解域 上的 点的等值线所对应的目标函数值最小，故 点坐标即为该规划问题的最优解.xOxDSSDAA12123213由方程组，xxxx(1,2).得A12123.故该规划问题的最优解为，目标函数的最小值为xxS D1x2x12321xxA21S 0S
6、 123xxO图11-1 例2示意12121212max222.00 用图解法求解 ，：,SxxxxStxxxx 例例3 3解解12 在直角坐标系 中，做出满足所有约束条件的可行解域，如图 11-2所示.xOxDD1x2x22S 0S O图11-2 例3示意24402令，作等值线，显然在无界可行解域 上找不到一点，使得过该点的等值线离原点最远.故该规划问题无解.SSD12min2(思考：若将目标函数改为，该问题是否有最优解？若有，最优值为多少？)Sxx三、利用单纯形法求解线性规划问题三、利用单纯形法求解线性规划问题 利用单纯形方法求解线性规划问题时首先化为规划问题的标准形，然后利用单纯形方法的
7、求解步骤，判断方法，通过单纯形表的变化，最终求出规划问题的最优解或判断规划问题无解。注意，最后一定给出原规划问题的最优解和最优值。例例4 4 某工厂利用甲、乙、丙三种原料，生产B1、B2、B3、B4 四种产品，每月可供该厂原料甲500t，乙300t，丙200t。生产一吨不同的产品可获得的利润及生产一吨不同产品所消耗的原料数量，见表11-2。表11-2 原料消耗表问工厂每月应如何安排生产计划，使利润最大？解解1234.设计划生产 种产品 (吨，吨，吨，吨)，可获 元利润jjBxjS12341234234123max20025030015022500330022000(1,2,3,4)则该问题的数
8、学模型为 ：jSxxxxxxxxxxxStxxxxj原料产品原料 供量/t500300200利润/(元/t)1B2B3B4B甲乙丙101112211230200250300150将上述问题化为标准形：12341234523461237min20025030015022500330022000(1,2,7)jSSxxxxxxxxxxxxxStxxxxxj ：156731(,).()取基 得，见表 11-3.BP P PIT B表11-3 T(B1)单纯形表T(B1)S02002503001500001x2x3x4x5x6x7x5x6x7x20030050010111221123010010010
9、01显然因 行有正数.故基 不是最优基.SB3725672300500 300 200200min2111(,)()行中是最大正数.故 为换入变量，又因，故 为换出变量，从而得新基，其对应的见表11-4.SxxBP P PT B表11-4 T(B2)单纯形表T(B2)S6001003500150003001x2x3x4x5x6x7x5x6x3x2001001001013120012311001001122显然，因 行仍有正数，故基不是最优基.因 行中只有正数SBS4635433100 100100min,233(,)()150，故 为换入变量，又因，故 为换出变量，从而得新基，其对应的 见表 11-5.xxBP P PT B表11-5 T(B2)单纯形表T(B3)S56002503100030085031x2x3x4x5x6x7x5x4x3x20010031003130173200100101131300150313231343312345671001000020000335600.显然 行无正数，即基 为最优基.,为最优解，最优值 SBxxxxxxxS1234341000020031003故原规划问题的最优解为,目标函数 最大值为5600.即工厂每月安排生产产品200，产品，可使利润最大为5600元.ttxxxxSBB
