北京经济管理职业学院：实用线性代数与线性规划ch3

第三章 线性规划数学模型的建立 (1) 教学目的 通过本章学习，使学生理解线性规划数学模型的概念及一般示形式；掌握线性规划数学模型的三要素；掌握建立线性规划数学模型的步骤和方法；能熟练的建立一些问题的线性规划数学模型；理解线性规划数学模型解的含义． (2) 教学重点 线性规划数学模型的建立． (3) 教学难点 建立线性规划数学模型． (4) 教学内容 1、 供求平衡条件下的运输问题模型的建立； 2、 线性规划数学模型的三要素； 3、 建立线性规划数学模型的步骤； 4、 线性规划问题解的概念（可行解、可行解集、最优解、最优值）； 5、 线性规划的概念； 6、 线性规划数学模型的一般形式． 本章通过例题说明线性规划数学模型的形式、三要素及建立数学模型的方法． 一、建立线性规划数学模型的例 例1 供求平衡状态下的运输问题 有两个农场 和 ，产粮量分别为23万吨和27万吨，要将粮食运往 ， ， 三个城市，三个城市的粮食需求量分别为17、18和15万吨．农场到各城市的运价如下表 运价表　　 　　单位：元/万吨 运价 城市 农场 50 60 70 60 110 160 问：应如何调运，可使总运费最省？试建立该问题的数学模型． 分析　此问题有两个供应方 和 ，三个需求方 ， ， ，假设这五者组成一个封闭系统，两个供应者的粮食只能提供给这三个需求方，同时三个需求方的粮食也只能从这两个供应者处获得． 要建立该问题数学模型，必须首先从问题出发． 该题问“应如何调运，使总运费最省”． “应如何调运”指从农场 分别向三个城市运多少万吨粮食(三个量)，从农场 分别向三个城市运多少万吨粮食(三个量)，共计6个量． 上述6个量是可以变化的，在计算前是未知的，是有待决策的，称其为决策变量．在建立数学模型时应首先将其设出．为便于区分供应方和需求方，将其设为双下标变量． 设：从农场 运往城市 的调运量为 万吨． 注意，此时的 既表示从农场 发往城市 的发出量，同时也表示城市 从农场 处的接收量． 如 表示从农场 运往城市 的粮食量，同时表示城市 从农场 处的接收量． 为方便讨论问题，运输问题通常先列出如下调运表． 调运表 调运量　 城市 农场 产粮量 (可供应量) 23 27 需求量 17 18 15 供求平衡 在这五个部门组成的封闭系统中，所有供应方的可供应量之和(23+27=50)为整个系统的可供应量，整个系统中所有城市粮食需求量之和(17+18+15=50)构成系统的总需求量．由于该系统的总供应量和总需求量都是50，相等，故在调运表最后一个单元格中填写“供求平衡”．此问题即为供求平衡状态下的运输问题． 上述所设的6个决策变量(调运量)应满足一定要求，这些要求就应从供求平衡开始． 由于供求平衡，供应方和需求方均恰好得到满足，即：两个供应方的粮食恰好全部运出，三个需求方所需要的粮食也恰好全部得到满足，下面通过列表将文字语言转化为数学表达式． 供应方：调出量恰好等于产粮量 供应方 调出量 恰好等于 产粮量 = 23 = 27 需求方：调入量恰好等于需求量 需求方 调入量 恰好等于 需求量 = 17 = 18 = 15 于是，所设决策变量同时满足以上五个方程，且由于 为调运量，必须非负．所以 应满足： ． 称上述条件为约束条件，满足约束条件的解称为可行解． 分析可行解的情况． 由于方程组中无矛盾方程，且有效方程的个数(4个)少于未知量的个数(6个)，方程组有无穷多个解，进一步满足非负条件的解也有无穷多个，即可行解有无穷多个，每个可行解对应着一个调运(可执行方案)．如： 解 解 显然，应有无穷多种调运方案．每个调运方案都对应着一个总运费． 方案1对应的总运费为： (元)； 方案2对应的总运费为： (元)． 即该题有无穷多个调运方案，不同调运方案对应不同运费，该问题要从无穷多个调运方案中找出一个使总运费最省的方案，即使总运费函数 取得最小值的一组变量 的取值． 综上，该问题数学模型列写如下： 解 设：由农场 运往城市 的调运量为 万吨． 则该问题的数学模型为： 求一组变量 的值，使其满足： 并使 最小． 此问题充分体现了全局观念．需求方不能仅考虑自己运费是否最低，而必须从整个封闭系统总运费最低的角度出发，做到局部利益服从整体利益． 该题属第一类问题，即任务一定，如何安排，使人、财、物最省． 通过例1对线性规划数学模型有关问题作如下归纳． 二、线性规划数学模型的三要素 所有线性规划数学模型都要求一组变量的值，称该组变量为决策变量；该组决策变量都要满足一组条件，称该组条件为约束条件．一般，约束条件由两部分组成：一部分为非负约束，剩下部分为数量约束；通常，满足约束条件的解若存在有无穷多个，我们最终不是求这无穷多个解分别是什么，而要寻求一个目标．这个目标由函数表示，称为目标函数，线性规划问题最终要使目标函数取得最大值或最小值． 决策变量、约束条件、目标函数分别构成了线性规划数学模型的三大要素．即 三、建立线性规划数学模型的步骤 建立实际问题线性规划数学模型的过程，实际是“翻译”的过程，即将实际问题翻译成数学表达式的过程．通常先用文字将实际问题表示出来，再将文字转化为数学表达式．具体步骤如下： 1、设决策变量——根据题目的“问题”，设决策变量； 2、列写约束条件——根据题目要求(字面或隐含)列出约束条件，约束条件中通常包含非负限制． 3、写目标函数，并注明求最大或最小．通常目标函数要求在题目的问中提出． 四、线性规划问题解的概念 1、可行解：满足约束条件的解称为线性规划问题的可行解． 2、可行解集：全体可行解组成的集合． 3、最优解：使目标函数实现最优的可行解． 4、最优值：最优解对应的目标函数值． 由上述分析知，线性规划问题最终就是要求最优解和最优值，该过程称作解线性规划问题的过程，或求线性规划问题的解的过程． 通常人们靠经验、靠想象求最优解，如上述例1，人们通常从当今的最低运费开始，直至满足所有需求方的需求，具体操作如下： 由于 到 的运费最低，因而 的需求17万吨全部从 处获得， 得到满足；在余下的运费中， 到 的运费最低，将 剩余的6万吨给 ， 所需的另12吨只能从运费相对较低的 处获得；由于此时 的粮食已全部运出，尽管运费较高， 所需要的15万吨粮食也只能从 处获得．于是调运表如下 方案 17 6 0 23 0 12 15 27 17 18 15 该调运方案所对应的总运费为4930元．显然不是最优方案．因而必须有专用的、科学的方法解线性规划问题． 解线性规划问题的方法有图解法、单纯形方法、对偶单纯形方法、两阶段法、大M法等，我们在第五章中主要学习使用计算机软件求解． 通过计算机软件求解，可得例1的最优调运方案为： 最优方案 0 8 15 23 17 10 0 27 17 18 15 该调运方案对应的运费为3650元，是所有可执行方案中运费最省的方案． 至于如何用程序解模型我们将在§5.1中学习．下面我们仍然介绍建立数学问题的数学模型的方法． 例2 资源利用问题 某企业生产A，B两种产品，已知生产单位产品A和B分别需要消耗钢材8吨和9吨，煤5吨和8吨，电力6度和4度，劳动力4人日和12人日．现该企业有钢材400吨，煤320吨，电力280度，劳动力350人日．又知生产单位产品A和B各能获利8千元和1万元．问应如何安排生产，可使企业利润最大？试建立该问题的数学模型． 分析 可将已知条件列表如下： 单耗 产品 资源 A B 现有量 钢材 (吨) 8 9 400 煤 (吨) 5 8 320 电力 (度) 6 4 280 人力 (人日) 4 12 350 单位利润 (千元) 8 10 显然，B的单位利润高于A的单位利润，应多生产，但B对资源的消耗大，在资源有限的情况下，生产数量必然少于同样资源条件下A产品的生产数量．另外，现有资源数量与B的单耗间也不成比例，因此应对两种产品产量进行合理搭配，才能在现有资源条件下创造出最高利润．此处的“如何安排生产”指在现有资源条件下，A、B两种产品产量分别为多少． 决策变量：A、B两种产品产量，分别为 和 约束条件：生产过程中对各种资源的消耗量不超过现有量 资源 消耗量 不超过 现有量 钢材 400 煤 320 电力 280 劳动力 350 显然，满足上述条件的解有无穷多个，每个解对应一个生产方案，不同生产方案对应不同的企业利润． 目标函数：企业利润最大，即 最大． 该问题数学模型列写如下． 解 设：A、B两种产品产量分别为 和 ． 则该问题的数学模型为： 求一组变量 和 的值，使其满足： 并使 最大． 此问题属第二类问题，即人、财、物一定，如何安排，使任务完成量最多． 此题需要说明的几个问题： (1)关于决策变量：资源利用问题中的决策变量只能设各种产品的产量，而不能设资源消耗量．因为产量作为决策变量，约束条件中的资源消耗量及目标函数中的企业利润都可以通过决策变量(产量)表示，也便于利用计算出的结果安排生产．但若设资源消耗量为决策变量，则很难分辨这些资源是由哪些产品消耗的，因而企业利润无法表示，也就无法写出目标函数． (2)关于约束条件：约束条件中的数量约束不能写成等式约束 这是由于： ①等式约束表示各种资源恰好全部用完，与实际问题不符，此时的利润未必最大．因为利润最大时，某些资源可能恰好用完，但某些资源可能有剩余； ②上述方程组可能无解； ③即使方程组有解，即使此时利润最大，在列约束条件时，也不必写成“=”，因为没有普遍性．而“ ”中包含“=”，应靠解规划问题解出结果可能均为=，但不能事先写成=． (3)此题通过计算机程序解得最优解和最优值为： 即：产品A生产27.5个单位，产品B生产20个单位时，企业利润最大，最大利润为420千元． (1) 资源利用问题分析：将最优解代入约束条件的左端，即可得到最优生产方案条件下各种资源的实际消耗量(如下表)，将实际消耗量与资源现有量作比较，可分析出各种资源的属性． 资源 消耗量 现有量 余量 钢材 400 0 煤 320 22.5 电力 280 35 劳动力 350 0 由于钢材和劳动力恰好用完，称其为稀缺资源，而煤和电力有剩余，称其为剩余资源，同时可计算出剩余资源的剩余量． (5)假设采用预先买电的方式，该企业应买245度电． (6)假设要求劳动力全部上岗，则约束条件变为 ． (7)假设劳动力市场有充足的劳动者供应，则约束条件中应将劳动力约束删去，变为： ． 例3 营养问题 有一位消费者欲购买营养物，根据医生要求，他所购买的营养物中，维生素A的含量不低于9克，维生素C的含量不低于19克．现有六种营养物可供选择，单位该营养物所含维A和维C的数量，及六种营养物的购买价格如下表： 单位含量 营养物 维生素 维A (克) 1 0 2 2 1 2 维C (克) 0 1 3 1 3 2 购买价格 (元) 20 25 60 35 37 39 问：他应如何购买，既符合医生要求，又花钱最省？试建立该问题的数学模型． 分析 显然，满足医生要求的购买方案有很多，但不同购买方案所花的钱数不同，该题要求找出花钱最少的方案． 决策变量：此处的“应如何购买”指六种营养物应分别购买多少．设六种营养物的购买量分别为 ， ，……， ． 约束条件：购买营养物的实际含量不低于医生要求 维生素 实际含量 不低于 医生要求 维Ａ 9 维Ｃ 19 显然，满足上述数量约束条件和非负限制的解有无穷多个，每个解对应一个购买方案，花的钱数各不相同． 目标函数：花钱最少，即 最小． 该问题数学模型列写如下． 解 设：营养物 的购买量为 则该问题的数学模型为： 求一组变量 值，使其满足： 并使 最小． 思考一下，该题属于第几类问题． 以上三个问题虽属于三个不同领域，但都是优化问题，都是要求满足一定约束条件的最值问题，因而都属于规划问题，它们具有以下共同特点： 1、都要求一组决策变量的值．决策变量的每一组取值对应着一个可执行方案．通常一个规划问题有无穷多个可执行方案． 2、都要满足一组约束条件，约束条件由数量约束和非负限制组成，其中数量约束可能是等式约束、可能是不等式约束，在不等式约束中，可能是“ ”约束，也可能是“ ”约束． 3、都有一个目标函数，根据题目不同，有的目标函数求最大，有的求最小． 若约束条件为“ ”约束，目标函数一般求最大，对应着人、财、物一定，如何安排，使任务完成量最多问题；若约束条件为“ ”约束，目标函数通常求最小，对应着任务一定，如何安排，使成本最低问题． 4、约束条件和目标函数都是决策变量的线性表达式． 五、线性规划数学模型的一般形式 当规划问题中的约束条件和目标函数都是决策变量的线性表达式时，称规划问题为线性规划问题． 线性规划数学模型的一般形式为： 求一组变量 的值，使其满足： 并使 最大(或最小)． 或写成 ． 例4 供求不平衡时的运输问题 例1中若农场 的粮食产量提高到了25万吨，其他条件不变，问如何调运，使总运费最省？试建立该问题的数学模型． 解　由农场 运往城市 的调运量为 万吨． 调运表 调运量 　 城市 农场 产粮量 (可供应量) 25 27 需求量 17 18 15 供>求 由于供>求，供应方不能得到满足，而需求方则恰好得到满足，即： 供应方：调出量不超过产粮量 供应方 调出量 不超过 产粮量 25 27 需求方：调入量恰好等于需求量 需求方 调入量 恰好等于 需求量 = 17 = 18 = 15 该问题的数学模型为： 求一组变量 的值，使其满足： 并使 最小． 例5 供求不平衡时的运输问题 例4在即将执行最优运输方案时，接到城市 的信息， 的粮食需求量增至20万吨．问如何调运，使总运费最省？试建立该问题的数学模型． 解　设：由农场 运往城市 的调运量为 万吨． 调运表 调运量 　 城市 农场 产粮量 (可供应量) 25 27 需求量 17 18 20 供<求 由于供<求，供应方能得到满足，而需求方则不能得到满足，即： 供应方：调出量恰好等于产粮量 供应方 调出量 恰好等于 产粮量 = 25 = 27 需求方：调入量不超过需求量 需求方 调入量 不超过 需求量 17 18 20 该问题的数学模型为： 求一组变量 的值，使其满足： 并使 最小． 例6 生产问题（工时利用问题） 某精密仪器厂生产甲、乙、丙三种仪器，平均每生产一台甲需7小时加工、6小时装配、售价为3000元；每生产一台乙需8小时加工、4小时装配、售价为2500元；每生产一台丙需5小时加工、3小时装配、售价为1800元．每季度可供利用的加工工时为2000小时，装配工时为1000小时，三种仪器所需元器件基本相同．又据市场预测知：市场对甲的需求量每季度不超过200台，乙不低于180台，丙无要求．问应如何安排生产，可使企业产值最高？试建立该问题的数学模型． 将已知条件列表如下： 单位工时 　产品 工序 甲 乙 丙 每季度 可用工时 加工 7 8 5 2000 装配 6 4 3 1000 售价 3000 2500 1800 市场需求 分析 决策变量：三种仪器每季度产量，分别为 ， 和 台； 约束条件：两方面 (1)加工时对设备的消耗工时数不超过每季度可利用工时数； (2)甲、乙两种仪器每季度实际产量应满足市场对该仪器的需求量． (1)加工时对设备的消耗工时数不超过每季度可利用工时数： 工序 实际消耗量 不超过 可用量 加工 2000 装配 1800 (2)甲、乙两种仪器每季度实际产量应满足市场对该仪器的需求量： 甲不超过200台 仪器 季度产量 不超过 需求量 甲 200 乙不低于180台 仪器 季度产量 不低于 需求量 乙 180 可行解也有无穷多个． 目标函数：企业产值最高，产值＝产量 销售价格． 解 设：甲、乙、丙三种仪器每季度产量分别为 ， 和 台， 则该问题的数学模型为： 求一组变量 ， ， 的值，使其满足： 并使 最大． 例7 进售货计划问题 某专卖店要制定明年一季度商品进货及售货计划．已知该店的仓库最多可容纳该种商品500件，且今年底尚有200件库存．该店每月初进一次货．总店规定明年一季度各月份进货及售货单价如下表： 月　份 1 2 3 买入价 8 6 9 售出价 9 8 10 问该店各月应分别购入和售出多少件该种商品，可使一季度效益最高？试建立该问题的数学模型． 分析 决策变量：共6个，分别为各月份买入量和售出量，为便于区分，将买入量分别设为 ， ， ；将售出量分别设为 ， ， ． 约束条件 (1)专卖店各月初进货后拥有商品数量不超过仓库容量： 月份 月初量 不超过 仓库容量 1月 500 2月 500 3月 500 (2)专卖店各月份销售商品数量不超过该月该店拥有该商品数量： 月份 销售量 不超过 月初量 1月 2月 3月 进、销货方案有无穷多个． 目标函数：一季度效益最高，一季度效益 ． 解 设：1、2、3月买入量分别为 ， ， ；售出量分别为 ， ， ． 则该问题的数学模型为： 求一组变量 ， ， ， ， ， 的值，使其满足： 并使 最大． 例8 投资问题 某投资公司准备将1千万元的资金对A、B两家企业投资．对企业A每投资1元，当年底投资公司可获利0.7元，对企业B每投资1元，第二年底投资公司可获利2元．对企业A、B的投资期限必须分别为一年和两年的整数倍．问应如何投资，可使投资公司在第三年底本利和最大？试建立该问题数学模型． 分析　决策变量：该题的问题“如何投资”指每年分别向两家企业投资多少．因而设 分别表示第 年向企业A和B的投资额，为列写模型方便，将有关数据列表如下： 年份 年初资金 对A投资 对B投资 年底资金 1 1 2 3 约束条件：由于只要有投入，不管投向哪家企业一定有正回报，要想获得最大本利和，每年必须将手中的资金全部投出去，只不过，投向不同企业、投不同金额回报大小不同而已，因而约束条件应为：每年投资额等于投资公司当年初手中的资金额． 目标函数：第三年底本利和最大． 解 如上表，设 分别表示第 年向企业A和B的投资额 则该问题的数学模型为： 求一组变量的 值，使其满足： 并使 最大． 例9 配套生产问题 某服装厂加工上衣和裤子，已知加工一件上衣可获利5元，加工一条裤子可获利2元，而每个工人加工一件上衣需2小时，加工一条裤子需1小时，由于布料的限制，每个工人每天最多只能安排加工3件上衣和4条裤子．若每个工人每天工作8小时，问如何安排，才能使每人每天的利润最大？试建立该问题的数学模型． 分析 决策变量：该题中的“如何安排”指每个工人每天生产多少件上衣、多少条裤子，因而设：每天每人加工上衣 件，裤子 条； 约束条件 由每个工人每天工作8小时，有 ； 由每天每人生产上衣数不超过3件，有： 由每天每人生产裤子数不超过4条，有： 产量非负： ，且为整数； 目标函数：每人每天创造的利润 最大． 解　设：每天每人加工上衣 件，裤子 条． 则该问题的数学模型为： 求一组变量 、 的值，使其满足： 并使 最大． 例10 配料问题 某养鸡场有100只鸡，用动物饲料和谷物饲料混合喂养，平均每天每只鸡吃混合饲料1斤．其中动物饲料所占比例不低于20%．根据市场调查动物饲料每斤售价为0.1元，谷物饲料每斤0.08元，且饲料公司每周只保证供应谷物饲料500斤．问应如何混合才能使饲料成本最低？试建立该问题数学模型． 分析　决策变量：“应如何混合” 指每斤混合饲料中包含动物饲料和谷物饲料分别为多少，也可按每天或每周需消耗两种饲料数量为决策变量； 约束条件：应从总数量和营养要求两个角度考虑； 目标函数：饲料成本最低． 法一：解　设：每斤饲料中含动物饲料 斤，谷物饲料 斤 则该问题的数学模型为： 求一组变量 ， 的值，使其满足： 并使 最小． 法二：解　设：每周用动物饲料 斤，谷物饲料 斤 则该问题的数学模型为： 求一组变量 ， 的值，使其满足： 并使 最小． 例11 植树问题 某班有男同学30人，女同学20人，植树节准备去植树，根据以往经验：男同学平均每人每天可挖坑20个，或栽树30棵，或给25棵树浇水；女同学平均每人每天可挖坑10个，或栽树20棵，或给15棵树浇水．问应如何安排，才能使植树（包括挖坑、栽树、浇水）量最多？试建立该问题数学模型． 分析　决策变量：“如何安排”指男生、女生分别有多少人挖坑、栽树、浇水，共6个决策变量； 约束条件 目标函数：植树量最大． 解　设：男生挖坑、栽树、浇水人数分别为 、 、 人 女生挖坑、栽树、浇水人数分别为 、 、 人. 则该问题的数学模型为： 求一组变量 的值，使其满足： 并使植树量 最大． 例12 配套生产问题 某木器公司有A、B、C三个加工厂，接受了为合资饭店赶制一批高档沙发的任务，每个客房放置一只大沙发和两只小沙发．各工厂每天工作8小时，各厂生产能力为：A厂每天若只做大沙发可做60只，若只做小沙发可做75只；B厂每天若只做大沙发可做15只，若只做小沙发可做30只；C厂每天若只做大沙发可做45只，若只做小沙发可做50只．规定每天按套交一次货．问应如何安排生产，可使公司每天的总产量最大？试建立该问题的数学模型． 分析　决策变量：可设三个工厂每天生产大、小沙发数量或时间； 约束条件 目标函数：每天生产沙发套数最多． 此题涉及数量与时间的转换，如Ａ厂生产能力为：每天工作8小时可做大沙发60只，则Ａ厂每小时可作大沙发 个；作一个大沙发所用时间为 小时． 法一：设生产时间 解　设A厂每天生产大、小沙发时间分别为 和 小时 B厂每天生产大、小沙发时间为 和 小时 C厂每天生产大、小沙发时间为 和 小时 则该问题的数学模型为： 求一组变量的值，使其满足： 并使 最大． 法2　设生产沙发数量 解　设A厂每天生产大、小沙发产量为 和 只 B厂每天生产大、小沙发产量为 和 只 C厂每天生产大、小沙发产量为 和 只 则该问题的数学模型为： 求一组变量的值，使其满足： 并使 最大． 例13 　排班问题 某饭店日夜服务，一天24小时所需服务员人数如下表： 序号 时间 所需服务员最少人数 1 2---6 3 2 6--10 8 3 10-14 10 4 14-18 7 5 18-22 12 6 22--2 4 如果每个服务员每天连续工作8小时，且必须在上述时间段开始时间开始上班．试确定满足以上条件的最少人数．试建立该问题的数学模型． 分析 此题的关键是区分以下四种人数：(1)每个时间段上所需最少人数；(2)每个时间段上实际在班上的人数；(3)每个时间段开始上班的人数；(4)饭店所需服务员总人数． 该题显然不能设(1)和(4)为决策变量，设(2)为决策变量显然也不合适，因为每个时间段在班上的人数由上个时间段开始上班人数和本时间段开始上班人数之和组成，无法进一步分解出有多少人属于哪一种，也无法表示饭店所需总人数．反之，若按各时间段开始上班人数设决策变量，每个时间段在班上的人数及饭店所需服务员总数则可以很容易的表示出来，因而，本题关键设每个时间段开始上班人数为决策变量． 解 设第 个时间段开始时间开始上班的人数为 ． 则该问题的数学模型为： 求一组变量的值，使其满足： 并使 最小． 例14 合理下料问题 某厂要做100套钢架，每套由2根2.9米、2根2.1米和4根1.5米的圆钢组成．已知原料长7.4米．问应如何下料，使所用原料最省？试建立该问题的数学模型． 分析：所有有关合理下料问题，均应将所有可能的下料方法列写出来，统计时必须从最长者的最多根数开始有规律递减，以保证下料方法不重复和遗漏． 该题所有下了方法如下： 下料方法 1 2 3 4 5 6 7 8 2.9米(根) 2 1 1 1 0 0 0 0 2.1米(根) 0 2 1 0 3 2 1 0 1.5米(根) 1 0 1 3 0 2 3 4 余料(米) 0.1 0.3 0.9 0 1.1 0.2 0.8 1.4 解 设第 种下料方式用原料 根 则该问题数学模型为： 求一组变量 EMBED Equation.3 的值，使其满足： 并使 最小 例15 合理下料问题 例14中考虑到设备调试问题，需要选择五种余料较少的方法进行套裁，应如何下料，使所用原料最省？试建立该问题的数学模型． 选第1,2,4,6,7种截法，作为第1,2,3,4,5种截法． 解 设第 种下料方式用原料 根 ． 则该问题数学模型为： 求一组变量 EMBED Equation.3 的值，使其满足： 并使 最小． 例16 资源利用问题及其对偶问题 某工厂利用三种原料 生产两种产品 ，三种原料的现有存量分别为150、240、300单位，生产单位产品 所消耗各种原料的数量及销售单位产品 所能得到的收益如下表： 单耗 产品 原料 现有存量 1 1 150 2 3 240 3 2 300 单位收益 2.4 1.8 问：(1) 工厂应如何安排生产使总收益最大？试建立该问题的数学模型． (2) 若有一企业欲从该厂购买现有原料 ，这批原料的销售单价应为多少，可使该厂愿意停止自己生产 ，而将原料 全部出售？试建立该问题数学模型． 解 (1)设： 的产量为 单位， 的产量为 单位． 则该问题的数学模型为： 求一组变量 的值，使其满足 并使 最大． (2) 分析 设原料 的单价分别为 ， 出售原料用于生产 所得收益不低于自己生产 所得收益：即 出售原料用于生产 所得收益不低于自己生产 的收益： 为保证成交，应使买方所付购买费最低，即 使 最小． 解　设：原料 的销售单价分别为 ． 则该问题的数学模型为： 求一组变量 的值，使其满足： 并使 最小． 称(2)为(1)的对偶问题． 通过求解，两个问题的最优值相等，说明只有当工厂销售这批原料获得总收益与利用原料自己生产产品所获总收益相等时，销售这批原料才合算． 例17 工时利用问题及对偶问题 某铁器厂生产甲、乙、丙三种产品，生产一件甲种产品需要1小时车工加工、2小时铣工加工、2小时装配，获得利润100元；生产一件乙种产品需要2小时车工加工、1小时铣工加工、2小时装配，获得利润90元；生产一件丙种产品需要2小时车工加工、1小时铣工加工、1小时装配，获得利润60元．工厂每月可供利用的车工加工工时为4200小时、铣工工时为6000小时，装配工时为3600小时． (1) 工厂每月应如何安排生产，使总利润最大？ (2) 如果企业将所有生产能力转化为来料加工，在不降低经济效益的情况下，各工种每小时的加工费为多少． 将已知条件列表如下 工时定额　　　　产品 工种 甲 乙 丙 可利用工时 车 1 2 2 4200 铣 2 1 1 6000 装配 2 2 1 3600 单位利润 (元) 100 90 60 解 (1)设：甲、乙、丙三种产品月产量分别为 ． 则该问题的数学模型为： 求一组变量 的值，使其满足： 并使 最大． (2)设：车工、铣工、装配工种每小时加工费分别为 元． 显然，为外商来料加工所得到的收入应不低于自己生产甲、乙、丙三种产品的利润．由于生产生产一件甲种产品需要1小时车工加工、2小时铣工加工、2小时装配，获得利润100元，将这些工时用于来料加工所得到的收入应不低于100元，即 同理，生产乙和丙的工时用于来料加工所得到的收入分别不低于乙和丙的单位利润． 目标函数应从每月三个工种工时全部用于来料加工所得到的收入角度考虑，此时不能让收入最大，因为该收入也即对方的付出，要想通过来料加工获得收入，必须保证双方都合适，约束条件保证了工厂的利益，只有目标函数中使对方付出最小时，对方才能接受，因而目标函数应求最小． 于是，该问题的数学模型为： 则该问题的数学模型为： 求一组变量 的值，使其满足： 并使 最小． 方案1� � EMBED Equation.3 ���� � EMBED Equation.3 ���� � EMBED Equation.3 ���� � � � EMBED Equation.3 ���� 1� 13� 9� 23� � � EMBED Equation.3 ���� 16� 5� 6� 27� � � 17� 18� 15� � � 对应 对应 方案2� � EMBED Equation.3 ���� � EMBED Equation.3 ���� � EMBED Equation.3 ���� � � � EMBED Equation.3 ���� 1� 12� 10� 23� � � EMBED Equation.3 ���� 16� 6� 5� 27� � � 17� 18� 15� � � 24 1 _1170961002.unknown _1170965346.unknown _1170965830.unknown _1170966011.unknown _1170966211.unknown _1170966247.unknown _1170966330.unknown _1170966343.unknown _1172171609.unknown _1172259241.unknown _1170966352.unknown _1170966357.unknown _1170966336.unknown _1170966340.unknown _1170966333.unknown _1170966255.unknown _1170966328.unknown _1170966252.unknown _1170966228.unknown _1170966235.unknown _1170966239.unknown _1170966231.unknown _1170966221.unknown _1170966224.unknown _1170966214.unknown _1170966218.unknown _1170966144.unknown _1170966181.unknown _1170966193.unknown _1170966202.unknown _1170966185.unknown _1170966190.unknown _1170966162.unknown _1170966176.unknown _1170966159.unknown _1170966103.unknown _1170966136.unknown _1170966141.unknown _1170966109.unknown _1170966132.unknown _1170966049.unknown _1170966098.unknown _1170966019.unknown _1170965933.unknown _1170965992.unknown _1170965998.unknown _1170966001.unknown _1170965994.unknown _1170965983.unknown _1170965987.unknown _1170965937.unknown _1170965886.unknown _1170965925.unknown _1170965931.unknown _1170965890.unknown _1170965876.unknown _1170965881.unknown _1170965833.unknown _1170965540.unknown _1170965779.unknown _1170965803.unknown _1170965819.unknown _1170965824.unknown _1170965813.unknown _1170965796.unknown _1170965799.unknown _1170965791.unknown _1170965639.unknown _1170965689.unknown _1170965702.unknown _1170965753.unknown _1170965707.unknown _1170965699.unknown _1170965695.unknown _1170965669.unknown _1170965686.unknown _1170965654.unknown _1170965562.unknown _1170965575.unknown _1170965632.unknown _1170965636.unknown _1170965629.unknown _1170965625.unknown _1170965571.unknown _1170965555.unknown _1170965558.unknown _1170965544.unknown _1170965446.unknown _1170965526.unknown _1170965533.unknown _1170965537.unknown _1170965530.unknown _1170965478.unknown _1170965481.unknown _1170965521.unknown _1170965475.unknown _1170965379.unknown _1170965435.unknown _1170965443.unknown _1170965431.unknown _1170965371.unknown _1170965376.unknown _1170965350.unknown _1170964410.unknown _1170964971.unknown _1170965118.unknown _1170965132.unknown _1170965146.unknown _1170965158.unknown _1170965342.unknown _1170965141.unknown _1170965125.unknown _1170965129.unknown _1170965122.unknown _1170965086.unknown _1170965095.unknown _1170965099.unknown _1170965092.unknown _1170964991.unknown _1170965079.unknown _1170964986.unknown _1170964752.unknown _1170964957.unknown _1170964964.unknown _1170964967.unknown _1170964960.unknown _1170964765.unknown _1170964890.unknown _1170964757.unknown _1170964514.unknown _1170964530.unknown _1170964748.unknown _1170964521.unknown _1170964506.unknown _1170964509.unknown _1170964414.unknown _1170961559.unknown _1170962133.unknown _1170962260.unknown _1170962267.unknown _1170962270.unknown _1170962263.unknown _1170962252.unknown _1170962256.unknown _1170962137.unknown _1170962020.unknown _1170962026.unknown _1170962030.unknown _1170962023.unknown _1170961631.unknown _1170961970.unknown _1170961609.unknown _1170961031.unknown _1170961532.unknown _1170961551.unknown _1170961556.unknown _1170961542.unknown _1170961546.unknown _1170961539.unknown _1170961054.unknown _1170961059.unknown _1170961525.unknown _1170961046.unknown _1170961050.unknown _1170961043.unknown _1170961015.unknown _1170961024.unknown _1170961027.unknown _1170961020.unknown _1170961009.unknown _1170961012.unknown _1170961005.unknown _1166779438.unknown _1170958828.unknown _1170958933.unknown _1170960199.unknown _1170960987.unknown _1170960995.unknown _1170960998.unknown _1170960991.unknown _1170960210.unknown _1170960984.unknown _1170960204.unknown _1170960072.unknown _1170960192.unknown _1170960196.unknown _1170960122.unknown _1170960119.unknown _1170959908.unknown _1170959915.unknown _1170959995.unknown _1170959996.unknown _1170959939.unknown _1170959994.unknown _1170959934.unknown _1170959912.unknown _1170959886.unknown _1170959901.unknown _1170959905.unknown _1170959891.unknown _1170959870.unknown _1170958896.unknown _1170958915.unknown _1170958922.unknown _1170958929.unknown _1170958919.unknown _1170958903.unknown _1170958908.unknown _1170958912.unknown _1170958900.unknown _1170958868.unknown _1170958889.unknown _1170958893.unknown _1170958871.unknown _1170958857.unknown _1170958861.unknown _1170958854.unknown _1170958759.unknown _1170958796.unknown _1170958813.unknown _1170958821.unknown _1170958825.unknown _1170958817.unknown _1170958806.unknown _1170958809.unknown _1170958803.unknown _1170958779.unknown _1170958789.unknown _1170958793.unknown _1170958783.unknown _1170958766.unknown _1170958770.unknown _1170958762.unknown _1170958713.unknown _1170958740.unknown _1170958747.unknown _1170958755.unknown _1170958743.unknown _1170958722.unknown _1170958732.unknown _1170958736.unknown _1170958726.unknown _1170958717.unknown _1166784339.unknown _1166798428.unknown _1166798444.unknown _1167513723.unknown _1167513726.unknown _1167944318.unknown _1168115616.unknown _1168115690.unknown _1170958700.unknown _1168115678.unknown _1168024830.unknown _1168025359.unknown _1167947086.unknown _1167513729.unknown _1166907722.unknown _1166907748.unknown _1166907757.unknown _1166907740.unknown _1166906667.unknown _1166906726.unknown _1166907448.unknown _1166907456.unknown _1166907208.unknown _1166907177.unknown _1166907197.unknown _1166906732.unknown _1166906698.unknown _1166906707.unknown _1166906674.unknown _1166798837.unknown _1166798844.unknown _1166799631.unknown _1166798739.unknown _1166798749.unknown _1166798713.unknown _1166798438.unknown _1166798441.unknown _1166798431.unknown _1166798434.unknown _1166793236.unknown _1166796097.unknown _1166796127.unknown _1166796131.unknown _1166796104.unknown _1166796112.unknown _1166796119.unknown _1166796108.unknown _1166796101.unknown _1166793253.unknown _1166796091.unknown _1166793242.unknown _1166784545.unknown _1166788986.unknown _1166784523.unknown _1166781852.unknown _1166783308.unknown _1166783324.unknown _1166783289.unknown _1166780608.unknown _1166781838.unknown _1166780397.unknown _1166780404.unknown _1166699142.unknown _1166713472.unknown _1166772068.unknown _1166772627.unknown _1166778446.unknown _1166778829.unknown _1166772920.unknown _1166778426.unknown _1166772601.unknown _1166727505.unknown _1166728050.unknown _1166728062.unknown _1166727735.unknown _1166727113.unknown _1166727131.unknown _1166701991.unknown _1166702007.unknown _1166702172.unknown _1166702179.unknown _1166705139.unknown _1166705302.unknown _1166702176.unknown _1166702018.unknown _1166702000.unknown _1166700542.unknown _1166700565.unknown _1166700585.unknown _1166700558.unknown _1166700535.unknown _1083659730.unknown _1166528676.unknown _1166610697.unknown _1166610714.unknown _1166610726.unknown _1166699056.unknown _1166528715.unknown _1166528728.unknown _1166532323.unknown _1166528709.unknown _1166525846.unknown _1166528638.unknown _1083928298.unknown _1083929678.unknown _1083659900.unknown _1083659064.unknown _1083659176.unknown _1083659692.unknown _1083659121.unknown _1083657777.unknown _1083657818.unknown _1082715563.unknown