第一章-线性规划及单纯形法(7)

第一章线性规划及单纯形法1§7线性规划应用举例一般情况下，一个经济管理问题满足以下条件时才能建立线性规划（LP）模型.(1)目标函数能用线性函数的形式，用数值指标反映；(2)该问题有多中可行方案；(3)要求达到的目标是在一定的约束条件下实现的，这些约束条件能用线性等式或不等式表示。第一章线性规划及单纯形法2§7线性规划应用举例•例1.13生产计划问题（P.27）•例1.14合理下料问题（P.29）•例1.15多阶段投资问题（P.30）•例1.16场地租借问题（P.32）•例1.17分配问题（P.33）•例1.18选址问题（P.34）第一章线性规划及单纯形法3合理下料问题要制作100套钢筋架子，每套有长2.9m、2.1m和1.5m的钢筋各一根。已知原料长7.4m，应如何切割，使所用原料最节省。考察如下方案的综合使用：方案毛坯方案1方案2方案3方案4方案5方案6方案7方案82.9211100002.1021032101.510130234合计7.37.16.57.46.37.26.66.0剩余料头0.10.30.901.10.20.81.4设xj（j=1，2，…，8）分别表示第j种方案下料的原材料根数。该问题的LP模型如下：第一章线性规划及单纯形法412345678123423567134678min2100232100..32341000(1,2,,8)jzxxxxxxxxxxxxxxxxxstxxxxxxxj材料根数最少:12345678123423567134678min0.10.30.901.10.20.81.42100232100..32341000(jzxxxxxxxxxxxxxxxxxstxxxxxxx剩余料头最少:1,2,,8)j（Ⅰ）（Ⅱ）思考：如何求解（Ⅰ）、（Ⅱ）？第一章线性规划及单纯形法5模型（Ⅰ）利用大M法求解，得到：*10,50,0,30,0,0,0,0Tx*90z12345678910111213141234912235671013134max0002100232100..3zxxxxxxxxxxxMxMxMxxxxxxxxxxxxxxstxxx材料根数最少:67811142341000(1,2,,14)jxxxxxxj此时剩余料头16m第一章线性规划及单纯形法6兴安公司有一笔30万元的资金，考虑今后三年内用于下列项目的投资：1.三年内的每年年初均可投入，每年获利为投资额的20%，其本利可一起用于下一年的投资；2.只允许第一年初投入，于第二年年末收回，本利合计为投资额的150%，但此类投资限额15万以内；3.允许于第二年初投入，于第三年末收回，本利合计为投资额的160%，但限额投资20万元以内；4.允许于第三年初投入，年末收回，可获利40%，但限额为10万元以内；试为该公司确定一个使第三年末本利总和为最大的投资组合方案。多阶段投资问题第一章线性规划及单纯形法7解：用xij表示第i年初投放到j项目的资金数，则可投资的变量表如下第一章线性规划及单纯形法8由于第三年末收回的本利只包含第三年初项目一的投资、第二年初项目三的投资和第三年初项目四的投资，因此目标函数为：3423314.16.12.1maxxxxz第一年初投资总额为30万，因此有：111230xx第二年初的投资额与第一年末收回的本利总额相同：1123212.1xxx第三年初投资额与第二年末收回的本利总额相同：122134315.12.1xxxx第一章线性规划及单纯形法9再考虑各项目的投资限额，得到该问题的线性规划模型如下：312334111221231131342112122334max1.21.61.4301.21.21.5..15201001,2,3;1,2,3,4ijzxxxxxxxxxxxxstxxxxij第一章线性规划及单纯形法10某糖果厂用原料A、B、C加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中A、B、C含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费及售价如下表，问该厂每月生产这三种牌号糖果各多少千克，使该厂获利最大，试建立该问题的线性规划模型。练习：混合配料问题第一章线性规划及单纯形法11解：用i=1,2,3分别代表原料A、B、C，用j=1,2,3分别代表甲、乙、丙三种糖果。设xij为生产第j种糖果使用的第i种原料的数量，则问题的数学模型可归结为：目标函数:112131122232132333111213212223313233112131122232max3.400.502.850.402.250.302.01.501.00.91.41.90.450.951.45zxxxxxxxxxxxxxxxxxxxxxxxx1323330.050.450.95xxx第一章线性规划及单纯形法12约束条件:11121321222331323311112131311121311212223232122232331323332000250012000.60.2..0.30.50.601,2,3;1,2,3ijxxxxxxxxxxxxxxxxxstxxxxxxxxxxxxxij原料供应限制含量要求条件第一章线性规划及单纯形法13作业：P.36第一章习题：2第一章线性规划及单纯形法14补充：应用LINDO求解LP问题•LINDO可以从下面的网址下载：•LINDO由美国芝加哥大学开发，可求解线性规划和线性整数规划等。其可按自然格式输入模型，使用方便。例如:第一章线性规划及单纯形法15第一章线性规划及单纯形法16例：应用LINDO求解下面LP问题：12345678123423567134678min2100232100..32341000(1,2,,8)jzxxxxxxxxxxxxxxxxxstxxxxxxxj第一章线性规划及单纯形法17