《线性规划及单纯形》PPT课件

《《线性规划及单纯形》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运筹学2讲课教师：赵晋都太原理工大学经济管理学院第一章线性规划及单纯形法1.1线性规划问题的数学模型1.2线性规划问题的图解法1.3线性规划问题的单纯形解法1.4非标准型线性规划问题的解法线性规划问题的实践背景线性规划问题的数学模型线性规划问题数学模型的标准型1.1线性规划的数学模型一、线性规划问题的实践背景线性规划问题起源于20世纪初期，在二战期间得到迅速发展线性规划问题大致可以分为两类给出一定量的人力、物力、财力或其它资源，如何统筹规划这些有限的资源完成最大任务；给定一项任务，如何运筹规划，合理安排，以最少的资源来完成它。二、线性规划问

2、题的数学模型例1-1某工厂生产甲，乙两种产品，这些产品分别需要在ABCD四种不同的设备上加工。按工艺规定，产品甲，乙在各设备上所需要的加工台时数如表1所示，已知各设备在计划期内有效台时数分别是12、8、16和12。该工厂每生产一件产品甲可得边际利润2元，每生产一件产品乙边际利润3元。问应当如何安排生产计划，才能使利润最大化？（表1）设备ABCD边际利润产品甲21402元产品乙22043元有效台时数1281612分析：上述实际问题，通俗地说，就是在有效台时数一定的前提下，求使利润最大化的生产方案。建模：若以分别代表产品甲，乙在计划期内的生产量

3、。因为设备A的有效台时数为12，这是一个限制产量的条件，所以在确定产品甲，乙的产量时，要肯定不能超出设备A的有效台时数，即可用不等式表示为≤12同理，对设备B、C、D也可以得到以下不等式：≤8≤16≤12考虑到实际意义，不可能为负值，即≥0用Z表示利润，则目标函数于是，上述最优生产问题可以归纳为以下数学形式其中必须满足以下条件≤12≤8s.t.≤16≤12≥0思考：模型与表（1）的对应关系？设备ABCD边际利润产品甲21402元产品乙22043元有效台时数1281612其中必须满足以下条件≤12≤8s.t.≤16≤12≥0例1.2某汽车厂生

4、产大轿车和载重汽车，所需资源、资源可用量和产品价格如下表所示:大轿车载重汽车可用量钢材（吨）221600工时(小时)52.52500座椅10400（辆）获利(千元/辆)43问应如何组织生产才能使工厂获利最大？例1.2的数学模型s.t.,例1.3营养配餐问题成年人每天需要从食物中摄取的营养以及四种食品所含营养和价格见下表。问如何选择食品才能在满足营养的前提下使购买食品的费用最小？例1.3数学模型例1.4下料问题某工厂要做100套钢架，每套有长2.9米、2.1米和1.5米的圆钢组成，已知原料长7.4米，问应如何下料使需用的原材料最省。解：如果从

5、每根7.4米长的原料上各截一根2.9米、2.1米和1.5米长的圆钢，则还余0.9米，用100根原料，浪费预料共90米。现采用套裁的办法，设计五种方案，如下表所示。圆钢套裁方案方案长度一x1二x2三x3四x4五x52.92.11.513210221213合计（米）料头（米）7.407.30.17.20.27.10.36.60.8例1.4数学模型设每个方案各下料根，则有小结.线性规划问题数学模型的特征线性规划模型的特征上述问题可看出线性规划问题有如下特点：1．用一组未知变量表示某一方案，这组未知变量的一组确定值就代表一个具体的方案，这些未知变量

6、称为决策变量。通常，根据决策变量所代表的事物的特点可以对变量的取值加以约束，例如非负约束、整数约束等。2．存在一定的限制条件，通常称为约束条件，这些约束条件可以用一组线性等式或者线性不等式来表达。3．有一个目标要求，并且这个目标可以表示为决策变量的线性函数，称为目标函数。按所研究问题的不同，要求目标函数实现最大化或者最小化。小结：线性规划问题数学模型的特征≤12≤8s.t.≤16≤12≥0决策变量目标函数约束条件小结：线性规划问题的规范描述线性规划问题的规范描述s.t.约束条件目标函数决策变量价值系数技术系数限定系数三、线性规划问题的标准型

7、(SLP)为什么要规定线性规划问题的标准型？便于比较，便于交流，便于计算机处理可以只针对这种标准形式来研究它的求解方法，对于不同形式的线性规划问题，只需要将其转换为标准型，然后再按标准型的求解方法求解。线性规划问题的标准型(SLP)s.t极大化型约束方程为等式所有的决策变量为非负值约束方程的右端项系数为非负值1、极大化型2、约束方程为等式3、所有的决策变量为非负值4、约束方程的右端项系数为非负值形式线性规划标准数学模型的特征标准型的和式标准型的矩阵式各种符号的定义非标准形式如何转换成标准形式1、目标函数是极小化的转化4.决策变量有上下界的转

8、换例1.1的标准型s.t例1.2的标准型s.t1.2线性规划问题的图解法图解法可行解及可行解集的特性线性规划问题解的特点单纯形法的思路1.2线性规划问题的图解法图解法就是利用坐标