论线性规划企业利润最大化baqt.docx

《论线性规划企业利润最大化baqt.docx》由会员分享，可在线阅读，更多相关《论线性规划企业利润最大化baqt.docx（54页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、引 言线性规划主要用用于解决生活活、生产中的的资源利用、人人力调配、生生产安排等问问题，它是一一种重要的数数学模型简简单的线性规规划指的是目目标函数含两两个自变量的的线性规划，其其最优解可以以用数形结合合方法求出。涉涉及更多个变变量的线性规规划问题不能能用初等方法法解决。线性性规划问题的的难点表现在在三个方面：一是将实际际问题抽象为为线性规划模模型；二是线线性约束条件件和线性目标标函数的几何何表征；三是是线性规划最最优解的探求求。线性规划的发展展史法国数学家 JJ.- B.- J.傅傅里叶和 CC.瓦莱普普森分别于11832和11911年独独立地提出线线性规划的想想法，但未引引起注意。 193

2、9年年苏联数学家.康托托罗维奇在生生产组织与计计划中的数学学方法一书书中提出线性性规划问题，也也未引起重视视。 1947年年美国数学家GG.B.丹齐齐克提出线性性规划的一般般数学模型和求求解线性规划划问题的通用用方法单单纯形法，为为这门学科奠奠定了基础。 1947年年美国数学家家J.vonn诺伊曼提出出对偶理论,开开创了线性规规划的许多新新的研究领域域，扩大了它它的应用范围围和解题能力力。 1951年年美国经济学学家T.C.库普曼斯把把线性规划应应用到经济领领域，为此与与康托罗维奇奇一起获19975年诺贝贝尔经济学奖奖。 50年代后后对线性规划划进行大量的的理论研究，并并涌现出一大大批新的算法

3、法。例如，11954年CC.莱姆基提提出对偶单纯纯形法，19954年S.加斯和T.萨迪等人解解决了线性规规划的灵敏度度分析和参数数规划问题，11956年AA.塔克提出出互补松弛定定理，19660年G.BB.丹齐克和和P.沃尔夫夫提出分解算算法等。 线性规划的的研究成果还还直接推动了了其他数学规规划问题包括括整数规划、随随机规划和非非线性规划的的算法研究。由由于数字电子子计算机的发发展，出现了了许多线性规规划软件，如MPPSX，OPPHEIE，UUMPIREE等，可以很很方便地求解解几千个变量量的线性规划划问题。 1979年年苏联数学家家L. G. Khacchian提提出解线性规规划问题的椭椭

4、球算法，并并证明它是多多项式时间算算法。 1984年年美国贝尔电电话实验室的的印度数学家NN.卡马卡提提出解线性规规划问题的新新的多项式时时间算法。用用这种方法求求解线性规划划问题在变量量个数为50000时只要要单纯形法所所用时间的11/50。现现已形成线性性规划多项式式算法理论。550年代后线线性规划的应应用范围不断断扩大。随着经济的发展展，关于线性性规划在企业业中的应用越越来越广泛。林林海明早在11996年就就立足于较强强的普及性，从从经济常识的的角度来认知知线性规划问问题的解法，初初步论述这一一问题；熊福福力、张晓东东等在20004年作了基基于利润最大大化的油田开开发非线性规规划一文，他

5、们们根据油田开开发的实际情情况，将油田田和利润细分分为几个部分分，以获得最最大利润为目目标，建立了了油田开发的的数学模型；吴海华和王王志江在关关于影子价格格作为企业资资源配置依据据的探讨根据线性规规划模型资源源影子价格的的经济意义，讨讨论了在企业业以收入最大大化和利润最最大化两种情情况下，影子子价格作为企企业资源配置置依据时存在在的问题。胡胡徐胜、刘娟娟和汪发亮在在最优控制制在汽车企业业利润最大化化中的应用一一文中从汽车车企业职工结结构角度出发发，研究在企企业提供职工工工资总量不不超过某一限限定值的情况况下,如何分分配汽车企业业中普通职工工与高级职工工的比例来达达到实现汽车车企业利润最最大化的

6、目标标。随着经济社会的的发展，线性性规划在资源源配置和企业业管理方面发发挥着独特的的作用。在企企业的各项管管理活动中，例例如计划、生生产、运输、技技术等问题，从从各种限制条条件的组合中中，通过对实实际数据的分分析处理和数数学模型的建建立，选择出出最为合理的的计算方法，建建立线性规划划模型从而求求得最佳结果果，给出了更更多的决策参参考信息。这这也将成为未未来企业生产产与管理的普普遍方法。 不单如如此，企业现现如今更着重重于对各种条条件组合中限限制条件作局局部调整以达达到对获得利利润的一种控控制，而这恰恰恰也是线性性规划问题中中灵敏度分析析所研究的对对象。本文共分为四章章。在第一章章，介绍本文的的

7、背景和线性性规划的发展展状况；在第第二章，介绍线性规划划本身和一系系列相关性质质问题及企业业利润最大化化数学模型的的基础知识；在第三章，介介绍利用线性性规划建立企业利润润最大化数学学模型；最后，求解解模型最优解解。第2章线性规划划问题本章主要介绍线线性规划本身身和一系列相相关性质问题题，并相应举举出一些简单单的例子更好好的阐述了线线性规划问题题。本章主要要借鉴于胡运运权、郭耀煌煌等编著，清清华大学出版版社出版的运运筹学教程（第第二版）的的内容。2.1线性规划划模型及标准准型211线性性问题的数学学模型例1：美佳公司司计划制造，两种家电产产品。已知各各制造一件时时分别占用的的设备A，BB的台时、

8、调调试工序及每每天可用于这这两种家电的的能力、各售售出一件时的的获利情况，如如表1所示。问问该公司应制制造两种家电电各多少件，使使获取的利润润为最大。表1项目每天可用能力设备A（h）0515设备B（h）6224调试工序（h）113利润（元）21 对上例用和分分别表示美佳佳公司制造家家电和的数量。这这时此例数学学模型可表示示为 由此例可以看出出，规划问题题的数学模式式型由三个要要素组成：变量，或称称决策变量，是是问题中要确确定的未知量量，它用以表表明规划中的的用数量表示示的方案、措措施，可由决决策者决定和和控制；目标函，它它是决策变量量的函数，按按优化目标分分别在这个函函数前加上或；约束条件，指

9、指决策变量取取值时受到的的各种资源条条件的限制，通通常表达为含含决策变量的的等式或不等等式。假定线性规划问问题中含个变变量，分别用用（）表示，在在目标函数中中的系数为（通常称为价价值系数），的取值受项资源的限制，用（）表标第种资源的拥有量，用表示变量取值为1个单位时所消耗或含有的第种资源的数理量，通常称为技术系数或工艺系数。刚上述线性规划问题的数学模型可表示为：上述模型的简写写形式为用向量形式表达达时，上述模模型可写为：式中；用矩阵和向量形形式来表示可可写为：称为约束方程组组（约束条件件）的系数矩矩阵。 变量的的取值一般配配为非负，即即；从数学意意义上可以有有。又如果变变量表示第种产品品期内产

10、量相相对于前期产产量的增加值值，则的取值值范围为，称称取值不受约约束，或无约约束。21122线性规划问问题的标准形形式线性规是问题的的标准形式如如下：标准形式的线性性规划模型中中，目标函数数为求极大值值，约束条件件全为等式，约约束条件右端端常数项全为为非负值，变变量的取值全全为非负值。对对不符合标准准形式的线笥笥规划问题，可可分别通过下下列方法化为为标准形式。1）目标函数为为求极小值，即即为：因为求等价于求求，令，即化为为：2）约束条件的的右端项时，只只需将等式或或不等式两端端同乘（-11），则等式式右端项必大大于零。3）约束条件为为不等式。当当约束条件为为“”时，如如，可令，得，显然。当约约

11、束条件为“”时，如有有，可令，得，。和是新加上去去的变量，取取值均为非负负，加到原约约束条中去的的变量其目的的是使不等式式转化为等式式，其中称为为松弛变量，一般配称为剩余变量，但也有称松弛变量的。松弛变量或剩余变量在实际问题中分别表示未被充分利用的资源和超出的资源数，均未转化为价值和利润，所以引进模型后它们在目标函数中的系数均为零。4）取值无约束束的变量是。如如果变量代表表某产品当年年计划数与上上一年计划数之差差，显然的以以值可能是正正也可能是负负，这时可令令，其中，将其代入入线性规划模模型即可。5）对的情况，令令，显然。22线性规划划模型的求解解221线性性规划问题的的基与解 线性无关：对于

12、于n维空间的的一组向量，若若数域F中有有一组不全为为0的数（），使 成成立，则称这这组向量在FF上线性相关关。否则称这这组向量在FF上线性无关关。秩：设A是mn矩阵。若若A的n个列列向量中有rr个线性无关关（），而所所有个数大于于r的列向量量组都线性相相关，则称数数r为矩阵AA的列秩。类似可定久矩阵阵A的行秩。矩矩阵A的列秩秩与行秩一定定相等，它也也称为矩阵AA的秩。基：已知A是约约束条件的mmn系数矩阵阵，其秩为mm。若B是AA中mm非奇异子子矩阵（即可可逆矩阵，有有），则称B是是线性规划问问题的一个基基，B是由AA中m个线性性无关的系数数列向量组成成的。基向量：B中一一列（共m个个）基变量

13、非基向量：B外外（A中）一一列（共nm个）非基变量可行解：满足、的解最优解：满足的可行解基本解：令所有有非基变量=0，求出的的满足的解基本可行解：满满足的基本解最优基本可行解解：满足的基本可行行解基本解退化的基本解：有基变量=0的基本解解退化的基本可行行解退化的最优化基基本可行解222线性性规划的图解解法l 适于求解二维问问题l 不必化为标准型型22111图解法步骤骤例2： 1）由全部约束束条件作图求求出可行域2）作出一条目目标函数的等等值线3）平移目标函函数等值线，作作图得最优点点，再算出最最优值 图1最优点Q： ；最优值ZZ： .22122从图解法看看线性规划问问题解的几种种情况1）有唯一

14、最优优解（一般情情况）2）有无穷多组组最优解（平平行；最优值值相同）对例2，修改为为：3） 无可行解（可行行域空集）对例2，增加一一个约束条件件：4） 无有限最优解（无无界域；取决决于求还是？）对例2，去掉第第一个约束条条件l 线性规划的可行行域为凸集，特特殊情况下为为无界域（有有有限个顶点点）或空集。l 线性规划若有最最优解，一定定可在可行域域顶点上得到到。223单纯纯形法22311单纯形法迭迭代原理1）确定初始基基可行解 当线性性规划问题的的所有约束条条件均为号是，松弛弛变量对应的的系数矩阵即即为单位矩阵阵，以松弛变变量为基变量量可确定基可可行解。 对约束束条件含或号时，可可构造人工基基，

15、人为产生生一个单位矩矩阵，用大法法或两阶段法法获得初始基基可行解。2）最优性检验验与解的判别别（目标函数数极大型） 当所有有变量对应的的检验数均非非正时，现有有的基可行解解即为最优解解。若存在某某个非基变量量的检验数为为零时，线性性规划问题有有无穷多最优优解；当所有有非基变量的的检验数均严严格小于零时时，线性规划划问题具有唯唯一最优解。 若存在在某个非基变变量的检验数数大于零，而而该非基变量量对应的系数数均非正，则则该线性规划划问题具有无无界解（无最最优解）。 当存在在某些非变量量的检验数大于于零，需要找找个一个新的的基可行解，即即要进行基变变换。22322单纯形法迭迭代步骤1）求出初始可可行

16、解，列出出初始单纯形形表。 设为为基变量，为非基变量量基100001002）计算检验数数进行最优性性检验。 若已获得最优解解（或确定无无最优解），则停止止；否则进行行下一步。3）换基。根据的原则，确确定为换入变变量，计算（），按规则则，确定为换出出变量。4）通过初等行行变换将系数数矩阵中变量量对应列变换为第个元素为为1的单位列列向量，用代代为新的基变变量，列出新新的单纯形表表，回到第二二步骤。例3：用单纯形形法求解线性性规划问题 解 先将上述问问题化成标准准形式有 其约束条件系数数矩阵的增广广矩阵为 是单位矩阵，构构成一个基，对对应变量是基基变量。令非非基变量等于于零，即找到到一个初始基基可行

17、解以此列出初始单单纯形表记作作表2如下：表221000基0150510002462010051100121000因表中有大于零零的检验数，故故表中基可行行解不是最优优解。因，故故确定为换入入变量。将列列除以的同行行数字得，由由此6为主元元素，作为标标志对主元素素6加上方括括号 ，主主元素所在行行基变量为换换出量。用替替换基变量，得得到一个新的的基，按上述述单纯形法计计算步骤第三三步，可以找找到新的基可可行解，并列列出新的单纯纯形表，记作作表3如下：表321000基015051002412/601/600104/60-1/6101/30-1/30由于上表中还存存在大于零的的检验数，故故重复上述步

18、步骤得下表，记记作表4：表421000基015/20015/4-15/227/21001/4-1/213/2010-1/43/2000-1/4-1/2上表中所有，且且基变量中不不含人工变量量，故表中的的基可行解为为最优解，代代入目标函数数得。223对偶偶单纯形法22311单纯形法计计算的矩阵描描述对称形式线性规规划问题的矩阵表达式加加上松弛变量量后为： (1)上式中为松弛变变量，为单位矩阵。单纯形法计算时时，总选取为为初始基，对对应基变量为为。设迭代若若干步后，基基变量为，在初始单纯纯形表中的系系数矩阵为。将在初始单单纯形表中单单独列出，而而中去掉后的的若干列后剩剩下的列组成成矩阵，这样样(1

19、)的初始单单纯形表可列列成如表5的形式。 表5项目非基变量基变量00当迭代若干步，基基变量为时，则则该步的单纯纯形表中由系系数组成的矩矩阵为。又因因单纯形法的的迭代是对约约束增广矩阵阵进行的行的的初等变换，对对应的系数矩矩阵在新表中中应为。故当当基变量为时时，新的单纯纯形表具有表表6形式。 表6项目基变量非基变量10从表5和表6看看出，当迭代代后基变量为为时，其在初初始单纯形表表中的系数矩矩阵为，则有有：1）对应初始单单纯形表中的的单位矩阵，迭迭代后的单纯纯形表中为； 2）初始单纯形形表中基变量量,，迭代后后的表中；3）初始单纯形形表中约束系系数矩阵为，迭代后后的表中约束束系数矩阵为为，。4）

20、若初始矩阵阵中变量的系系数向量为迭迭代后为，则则有 （22）5）当为最优解解时，在表66中应有 （33） （4） 因的检验数可可写为 （55） 故(3)(5)式可重写写为 （66） （7）称为单纯乘子，若若令 则（66）、（7）式可改写为 （88） 看出这时时检验数行，若若取其相反数数恰好是其对对偶问题的一一个可行解。将将这个解代入入对偶问题的的目标函数值值 有 （9）由（9）式看出出，当原问题题为最优解时时，这时对偶偶问题为可行行解，且两者者具有相同的的目标函数值值。22322对偶问题的的基本性质 1）弱对偶性。如如果是原问题题的可行解，是其对偶问题的可行解，则恒有 由弱对偶性，可可得出以下

21、推推论： 原问问题任一可行行解的目标函函数值是其对对偶问题目标标函数值的下下界；反之对对偶问题任一一可行解的目目标函数值是是其原问题目目标函数值的的上界。 如原原问题有可行行解且目标函函数值无界(具有无界解解)，则其对对偶问题无可可行解；反之之对偶问题有有可行解且目目标函数值无无界，则其原原问题无可行行解(注意：本点性质的的逆不成立，当当对偶问题无无可行解时，其其原问题或具具有无界解或或无可行解，反反之亦然)。 若原原问题有可行行解而其对偶偶问题无可行行解，则原问问题目标函数数值无界；反反之对偶问题题有可行解而而其原问题无无可行解，则则对偶问题的的目标函数值值无界。2）最优性。如如果是原问题题

22、的可行解, 是其对偶偶问题的可行行解，且有 则是原问题的最最优解，是对对偶问题的最最优解。3）强对偶性(或称对偶定定理)。若原原问题及其对对偶问题均具具有可行解，则则两者均具有有最优解，且且它们最优解解的目标函数数值相等。4）互补松弛性性。在线性规规划问题的最最优解中，如如果对应某一一约束条件的的对偶变量值值为非零，则则该约束条件件取严格等式式；反之如果果约束条件取取严格不等式式，则其对应应的对偶变量量一定为零。也也即 若，则则有， 即， 若，即即，则有， 因此一一定有。将互补松弛性质质应用于其对对偶问题时可可以这样叙述述：如果有，则；如果有, 则。22333对偶单纯形形法的基本思思路 求解线

23、线性规划的单单纯形法的思思路是：对原原问题的一个个基可行解，判判别是否所有有检验数。若若是，又基变变量中无非零零人工变量，即即找到了问题题最优解；若若为否，再找找出相邻的目目标函数值更更大的基可行行解，并继续续判别，只要要最优解存在在，就一直循循环进行到找找出最优解为为止。根据对偶问题的的性质，因为为，当，即有或，也即其对对偶问题的解解为可行解，由由此原问题和和对偶问题均均为最优解。反反之，如果存存在一个对偶偶问题的可行行基，即对，有或，这时只要要有，即原问问题的解也为为可行解，即即两者均为最最优解。否则则保持对偶问问题为可行解解，找出原问问题的相邻基基本解，判别别是否有，循循环进行，一一直使

24、原问题题也为可行解解，从而两者者均为最优解解。对偶单纯形法的的基本思路：先找出一个个对偶问题的的可行基，并并保持对偶问问题为可行解解条件下，如如不存在，通通过变换到一一个相邻的目目标函数值较较小的基本解解(因对偶问问题是求目标标函数极小化化)，并循环环进行，一直直到原问题也也为可行解(即)，这时时对偶问题与与原问题均为为可行解。22344对偶单纯形形法的计算步步骤设某标准形式的的线性规划问问题 （10） 存在一个对对偶问题的可可行基，不妨妨设，列出单单纯形表（见表7）。 表7基100010001000 表表7中必须有有，的值不要求求为正。当对对，有时，即表中中原问题和对对偶问题均为为最优解。否

25、否则，通过变变换一个基变变量，找出原原问题的一个个目标函数值值较小的相邻邻基本解。1）确定换出基基的变量因为总存在00的，令，其对应应变量为换出出基的变量。2）确定换入基基的变量为了使下一个个表中第行基基变量为正值值，因而只有有对应的非基基变量才可以以考虑作为换换入基的变量量。为了使下一个个表中对偶问问题的解仍为为可行解，令令 （111）称为主元素，为为换入基的变变量。设下一个表中的的检验数为，由由式 （112）分两种情况说明明满足（111）式来选取取主元素时，式式（12）中（对）。（a）对 ，因因 故 ，又又因主元素，故故，由此式（122）方括弧内内的值0，故有。（b）对，因，故故有。 3）

26、用换入变量量替换换出变变量，得到一一个新的基。对对新的基再检检查是否所有有。如是，找找到了两者的的最优解，如如为否，回到到第1步再循环进进行。因为由对偶问题题的基本性质质知，当对偶偶问题有可行行解时，原问问题可能有可可行解，也可可能无可行解解。对出现后后一种情况的的判断准则是是：对，而对对所有有。因为这种种情况，若把把表中第行的的约束方程列列出有 （113）因，又，故不可可能存在的解解。故原问题题无可行解，这这时对偶问题题的目标函数数值无界。第三章线性规划划中灵敏度分分析31含义和研研究对象311什么么是灵敏度分分析？是指研究线性规规划模型的某某些参数（）或或限制量（，约约束条件）的的变化对最

27、优优解的影响及及其程度的分分析过程也也称为优化后后分析。 312灵敏敏度分析的研研究对象l 目标函数的系数数变化对最优优解的影响；l 约束方程右端系系数变化对最最优解的影响响；l 约束方程组系数数矩阵变化对对最优解的影影响；综合体现在两个个问题上： 这些系数在什么么范围内发生生变化时，最最优解不变？ 系数变化超出上上述范围，如如何用最简便便的方法求出出新的最优解解？32进行灵敏敏度分析的基基本原则 在最终单纯纯形表的基础础上进行。 尽量减少附附加的计算工工作量。33灵敏度分分析的步骤1）将参数的改改变通过计算算反映到最终终单纯形表上上来；2）检查是否仍仍为原问题的的可行解；3）检查是否仍仍为对

28、偶问题题的可行解；4）依据表8所所列情况决定定继续计算或或得到结论。表8原问题对偶问题结论或继续计算算的步骤可行解可行解问题的最优解或或最优基不变变可行解非可行解用单纯形法继续续迭代求最优优解 非可行解可行解用对偶单纯形法法继续迭代求求最优解 非可行解非可行解引进人工变量，编编制新的单纯纯形表重新计计算34灵敏度分分析的主要内内容341分析析的变化线性规划目标函函数中变量系系数的变化仅仅仅影响到检验验数的变化.所以将的变变化直接反映映到最终单纯纯形表中,只只可能出现如如表8中的前两种种情况.下面举例说明。例3 在例11的美佳公司司例子中，（11）若加电的利润降至至1.5元/件，而家电电的利润增

29、至至2元/件时时，美佳公司司最优生产计计划有何变化化；（2）若若加电的利润不变变，则加电的利润在什么么范围内变化化时，则该公公司的最优生生产计划将不不发生变化。 解 （1）将将家电，的利润变化化直接反映到到最终单纯形形表（表4）中得表9。 表91.52000基015/200 15/4-15/21.57/21001/4-1/223/2010-1/43/20001/8-9/4因变量的检验数数大于零，故故需继续用单单纯形法迭代代计算得表110。表10基0600 4/51-61.5210-1/50123011/50000-1/100-3/2即美佳公司随加加电，的利润变化化应调整为生生产2件，3件。 （

30、2）设设家电的利润为（）元元，反映到最最终单纯形表表中，得表111。表11项 目2000基015/200 15/4-15/227/21001/4-1/23/2010-1/43/2000为使表11中的的解仍为最优优解，应有 , 解得 即加电的利润润的变化范围围应满足 342分析析的变化右端项的变化在在实际问题中中反映为可用用资源数量的的变化。由式式看出变化反映映到最终单纯纯形表上将引引起列数字的的变化，在表表8中可能出现现第一或第三三的两种情况况。出现第一一种情况时，问问题的最优基基不变，变化化后的列值为为最优解。出出现第三种情情况时，用对对偶单纯形法法迭代继续找找出最优解。例4 在上述述美佳公

31、司的的例子中：(1)若设备备和调试工序序的每天能力力不变，而设设备每天的能能力增加到332小时，分分析公司最优优计划的变化化；(2)若若设备和每天可用能能力不变，则则调试工序能能力在什么范范围内变化时时，问题的最最优基不变。解 （1）因因有由式有 将其反映到最终终单纯形表中中得表12 表1221000基035/200 15/4-15/2211/21001/4-1/21-1/2010-1/43/2000-1/4-1/2因表12中原问问题为非可行行解，故用对对偶单纯形法法继续计算得得表13。 表1321000基01505 1002511001020-401-60-100-2由此美佳公司的的最优计划

32、改改为只生产加加电5件。（2）设调试工工序每天可用用能力为（）小时，因有有将其反映到最终终单纯形表中中，其列数字字为 当时问题的最优优基不变，解解得。由此调调试工序的能能力应在4小小时6小时时之间。343增加加一个变量的的分析增加一个变量在在实际问题中中反映为增加加一种新的产产品。其分析析步骤为：1）计算2）计算3）若，原最优优解不变，只只需将计算得得到的和直接写入最最终单纯形表表中；若，则则按单纯形法法继续迭代计计算找出最优优。例5 在美佳佳公司例子中中，设该公司司又计划推出出新型号的家家电，生产一件件所需设备、及调试工序序的时间分别别为3小时、44小时、2小小时，该产品品的预期盈利利为3元

33、件件，试分析该该种产品是否否值得投产；如投产，对对该公司的最最优生产计划划有何变化。解 设该公司生生产家电件，有，。 将其反映到最终终单纯形表（表表4）中得表144。表14210 003 基015/20015/4-15/2-727/21001/4-1/2013/2010-1/43/22000-1/4-1/21因 ，故用单单纯形表继续续迭代计算得得表15。表15210 003 基b051/407/213/8-9/4027/21001/4-1/2033/401/20-1/83/410-1/20-1/8-5/40由表15，美佳佳公司新的最最优生产计划划应为每天生生产件家电II，件家电。344分析析参

34、数的变化化的变化使线性规规划的约束系系数矩阵发生生变化。若变变量在最终单单纯形表中为为非基变量，其其约束条件中中系数的变化化分析步骤可可参照本节之之三，若变量量在最终单纯纯形表中为基基变量，则的的变化将使相相应的和发生变化，因因此有可能出出现原问题和和对偶问题均均为非可行解解的情况。出出现这种情况况时，需引进进人工变量将将原问题的解解转化为可行行解，再用单单纯形法求解解，下面举例例说明。例6 在美佳佳公司的例子子中，若家电电每件需设备备，和调试工时时变为8小时时、4小时、11小时，该产产品的利润变变为3元件件，试重新确确定该公司最最优生产计划划。解 先将生产产工时变化后后的新家电看作是一种种新

35、产品，生生产量为，仿仿本节三的步步骤直接计算算和并反映到最最终单纯形表表中。其中： 将其反映到最终终单纯形表(表4)中得表16。 表16213 000 基015/20011/215/4-15/227/2101/20 1/4-1/213/2011/20-1/43/2003/20-1/4-1/2因已变换为，故故用单纯形法法将替换出基基变量中的，并并在下一个表表中不再保留留，得表17。表1723000基0-900 14-24221001/2-233010-1/230001/2-5表17中原问题题与对偶问题题均为非可行行解，故先设设法使原问题题变为可行解解。表17第1行的的约束可写为为 （14）式（1

36、4）两端端乘以（-11），再加上上人工变量得得 （15）将式（15）替替换表17的第l行得得表18。表 1823000基900-1 -4241221001/2-2033010-1/230000因对偶问题为非非可行解，用用单纯形法计计算得表19。表 1923000基03/800-1/24 -1/611/24211/410-1/121/601/12315/8011/800-1/800-5/24-1/30由表19知，美美佳公司的最最优生产计划划为每天生产产件家电，件新家电。345增加加一个约束条条件的分析增加一个约束条条件在实际问问题中相当增增添一道工序序。分析的方方法是先将原原问题最优解解的变量值

37、代代入新增的约约束条件，如如满足，说明明新增的约束束未起到限制制作用，原最最优解不变。否否则，将新增增的约束直接接反映到最终终单纯形表中中再进一步分分析。 例7 仍以美佳佳公司为例，设设家电，经调试后，还还需经过一道道环境试验工工序。家电每件须环境境试验3小时时，家电每件2小时时，又环境试试验工序每天天生产能力为为12小时.试分析增加加该工序后的的美佳公司最最优生产计划划。 解 先将原问题题的最优解, 代入环境试试验工序的约约束条件。因因，故原问题题最优解不是是本例的最优优解。 在试验验工序的约束束条件中加松松弛变量得 （166） 以为基基变量，将式式(16)反映到到最终单纯形形表(表4)中得表200。表20210 000基