线性规划与单纯形法

《线性规划与单纯形法》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、§1.1　线性规划问题及其数学模型一、问题的提出在生产经营管理中，需要经常进行计划或者规划，虽然各行业的计划或规划千差万别，但其共同点可归纳为：在各项资源条件的限制下，如何确定方案，使预期的目标达到最优。例1.1　某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗如下表所示：ⅠⅡ资源限制设备128台时原材料A4016㎏原材料B0412㎏利润23该工厂生产一件产品Ⅰ、Ⅱ的利润分别为2元、3元，问应如何安排生产才使该工厂的获利最大？二、数学模型的建立L.P问题数学模型的三要素：1.决策变量：一般是根据所问问题假设决策变量，一组决

2、策变量（）表示某一方案，这一组决策变量的值就代表一个具体方案。2.目标函数：通过决策变量，将要实现的目标用函数式表示出来，常见的目标函数有两种表达式。（1）目标是求最大化：（2）目标是求最小化：233.约束条件：主要是对变量或目标的约束，通常用未知量的线性等式或不等式来表示。例1.3：某公司经销一种产品，它下设三个生产点，每日产量分别为，，，该公司把这些产品分别运往四个销售点，各销售点每日销量分别为，已知每吨产品从各生产点到各销售点的运价如下表所示，问该公司应如何调运产品，在满足各销售点需要前提下，使总运费最少？销量运价411310192874105解：23三、L.P数

3、学模型的一般形式st.　上述模型的简写形式为：st.用向量形式表达时，上述模型可写为：st.式中：；价值系数　　　　　用矩阵形式来表示可写为：23技术系数工艺系数资源系数st.　（假定线性规划问题中含n个变量，分别用表示，在目标函数中的系数为，称为价值系数；的取值受m种资源的限制，用表示i第种资源的拥有量，用表示变量取值为1单位时所消耗或含有的第i种资源的数量，通常称为技术系数或工艺系数）§1.2图解法图解法简单直观，能帮助我们了解L.P的基本原理。一、图解法基本步骤1.在平面上建立直角坐标系；2.图示全部约束条件，找出可行域；3.图示目标函数和寻找最优解。例1.4：通

4、过例1.1来说明图解法的具体运用　　　　　　①　　　　　　　②s.t　　③④⑤23二、L.P求解的几种解的情况1.有唯一最优解。（如上例所示）2.有无穷多最优解（多重解）如上例中，若将目标函数改为，则表示目标函数中以参数z的这族平行直线与约束条件的边界线平行。当z值由小变大时，将与线段Q2Q3重合，则点Q2与Q3之间的可行域边界上各点均为最优点，它们对应同一最优值。3.无可行解若上例中再增加一个约束条件，时，该问题的可行域为空集，即该LP模型无可行解也不存在最优解。如出现这种情况表明数学模型中存在矛盾的约束条件。4.无界解23如果全部约束条件构成的可行域是无界的，则有可

5、能出现最优解无界，产生无界解的原因是由于在建立实际问题的数学模型时，遗漏了某些必要的资源约束条件。如下述线性规划问题：　　　　　　　　　　三、由图解法得到的启示从LP图解法可以得出以下几点启示：1.LP的解的情况有四种：唯一最优解、无穷多最优解、无界解、无可行解。2.LP的可行域为凸集，特殊情况下为无界域或空集；3.LP若有最优解，一定可以在其可行域的顶点上得到；4.解题思路是：先找出凸集的任一顶点，计算在顶点处的目标函数值。比较周围相邻顶点的目标函数值是否比这个值大，如果否，则该顶点是最优解的点若最优解的点之一，否则，转到比这个点的目标函数值更大的另一顶点，重复上述过

6、程，一起到找到使目标函数值最大的顶点为止。图解法虽然直观、简便，但当变量数多于三个以上时，它就无能为力，只能用另外一种代数法～～单纯形法来求解。作业：1.用图解法求解下列线性规划问题，并指出问题具有惟一最优解、无穷多最优解、无界解还是无可行解。23（1）　　　　4　　　　　　　s.t　　(2)　　　　　　　　　　　s.t　　(3)　　　　　　　　　　　s.t　　(4)　　　　　　　　　　　s.t　　232.美佳公司计划制造I、II两种家电产品。已知各制造一件时分别占用的设备A,B的台时、调试时间及调试设备和调试工序每天可用于这两种家电的能力、各售出一件时的获利情况如表1

7、—1所示。问该公司应制造A、B两种家电各多少件，使获取的利润为最大。表1-1项目III每天可用能力设备A(h)0515设备B(h)6224调试工序(h)115利润（元）213.(仓库租用问题)捷运公司拟在下一年度的1-4月的4个月内需租用仓库堆放物资.已知各月份所需仓库面积数列于表1.仓库租借费用随合同期而定,期限越长,折扣越大,具体数字见表2.租借仓库的合同每月初都可办理,每份合同具体规定租用面积数和期限.因此该厂可根据需要,在任何一个月初办理租借合同.每次办理时可签一份,也可签若干份租用面积和租借期限不同的合同,试确定该公司签订租借合