1.2线性规划图解法(经典运筹学)

上堂课主要内容：一、线性规划模型引例二、线性规划模型的建立1、建模的一般步骤：步骤一：确定决策变量即用变量取不同的值来表示可供选择的各种不同方案步骤二：建立目标函数即找到目标值与决策变量的数量关系步骤三：确定约束条件即决策变量所受到的外界条件的制约。约束条件一般为决策变量的等式或不等式要求：目标函数与约束条件均是线性的，且目标函数只能是一个。2、线性规划模型的一般形式：nnxcxcxcz2211minmax）（或mnmnmmnnnnbxaxaxabxaxaxabxaxaxats），或或），或或），或或(((.22112222212111212111为已知常数其中),,2,1;,,2,1(,,njmicbajiij0,,21nxxx决策变量约束方程非负约束目标函数三、线性规划求解：四、线性规划应用举例nnxcxcxcz2211minmax）（或mnmnmmnnnnbxaxaxabxaxaxabxaxaxats），或或），或或），或或(((.221122222121112121110,,21nxxx计算机应用软件时间所需售货员人数星期日28人星期一15人星期二24人星期三25人星期四19人星期五31人星期六28人例3福安商场是个中型的百货商场，它对售货人员的需求经过统计分析如下所示：为保证售货人员充分休息，售货人员每周工作五天，休息两天，并要求休息的两天是连续的，问应该如何安排售货人员的作息，既满足了工作的需要，又使配备的售货人员的人数最少？解，为周二开始休息的人数，为周一开始休息的人数设21xx，为周日开始休息的人数，为周六开始休息的人数76xx表示商场的售货员人数Z721xxx721minxxxZ求2854321xxxxx时间所需售货员人数星期日28人星期一15人星期二24人星期三25人星期四19人星期五31人星期六28人约束条件:星期日售货员人数要求:1565432xxxxx星期一售货员人数要求:2476543xxxxx星期二售货员人数要求:2576541xxxxx星期三售货员人数要求:1976521xxxxx星期四售货员人数要求:3176321xxxxx星期五售货员人数要求:2874321xxxxx星期六售货员人数要求:数学模型:721minxxxZ求ts.非负约束:7,,2,1,0ixi2854321xxxxx1565432xxxxx2476543xxxxx2576541xxxxx1976521xxxxx3176321xxxxx2874321xxxxx7,,2,1,0ixi7,,2,1,iixi日开始休息的人数为星期数学模型:721minxxxZ求ts.2854321xxxxx1565432xxxxx2476543xxxxx2576541xxxxx1976521xxxxx3176321xxxxx2874321xxxxx7,,2,1,0ixi解得:36.0,8,0,5,11,0,1207654321Zxxxxxxx时间所需售货员人数星期日28人星期一15人星期二24人星期三25人星期四19人星期五31人星期六28人例3福安商场是个中型的百货商场，它对售货人员的需求经过统计分析如下所示：为保证售货人员充分休息，售货人员每周工作五天，休息两天，并要求休息的两天是连续的，问应该如何安排售货人员的作息，既满足了工作的需要，又使配备的售货人员的人数最少？解，为周二开始休息的人数，为周一开始休息的人数设21xx，为周日开始休息的人数，为周六开始休息的人数76xx表示商场的售货员人数Z36.0,8,0,5,11,0,1207654321Zxxxxxxx解得：方案1方案2方案3方案4方案52.9m120102.1m002211.5m31203合计7.4m7.3m7.2m7.1m6.6下角料0m0.1m0.2m0.3m0.8m下料数(根)长度例4某工厂要做100套钢架,每套用长为2.9m,2.1m,和1.5m的圆钢各一根,已知原料每根长7.4m,问应如何下料,可使所用原料最省.分析:每根原料做一套钢架,下角料：0.9m用套裁方式下料方案：方案1方案2方案3方案4方案52.9m120102.1m002211.5m31203合计7.4m7.3m7.2m7.1m6.6下角料0m0.1m0.2m0.3m0.8m下料数(根)长度下料方案：)5,4,3,2,1iixi数（第种方案下料的原料根为按解：设表示总用料数Z数学模型：54321minxxxxxZ求ts.1002421xxx10022543xxx1003235321xxxx.0,0,0,0,054321xxxxx方案1方案2方案3方案4方案52.9m120102.1m002211.5m31203合计7.4m7.3m7.2m7.1m6.6下角料0m0.1m0.2m0.3m0.8m下料数(根)长度例4某工厂要做100套钢架,每套用长为2.9m,2.1m,和1.5m的圆钢各一根,已知原料每根长7.4m,问应如何下料,可使所用原料最省.下料方案：90.0,05,0,01,30054321Zxxxxx最优值最优解：)5,4,3,2,1iixi数（第种方案下料的原料根为按总用料数Z最优下料方案：按方案1下料30根，方案2下料10根，方案4下料50根，共需原料90根。例5(产品配套问题）假定一个工厂的甲、乙、丙三个车间生产同一个产品，每件产品包括4个A零件，和3个B零件。这两种零件由两种不同的原材料制成，而这两种原材料的现有数额分别为100克和200克。每个生产班的原材料需要量和零件产量如下表所示。每班进料数（克）每班产量（个数）第1种原材料第2种原材料A零件B零件甲8675乙5969丙3884车间问这三个车间各应开多少班才能使这种产品的配套数达到最大车间所开的生产班数分别是甲、乙、丙三个，，解：设321xxx产品的配套数z约束条件为：100358321xxx200896,321xxx000321xxx，，三个车间共生产A零件：321867xxx三个车间共生产B零件321495xxx4867321xxxminz则3495,321xxx非线性表示生产出的产品数设4x要求：每班进料数（克）每班产量（个数）第1种原材料第2种原材料A零件B零件甲8675乙5969丙3884车间车间所开的生产班数分别是甲、乙、丙三个，，321xxx产品的配套数z目标函数：目标函数Z=x4线性43214867xxxx43213495,xxxx数学模型：100358321xxx200896321xxx.0,0004321xxxx，，4maxxz线性规划问题ts.048674321xxxx034954321xxxx例6（多周期动态生产计划问题）华津机器制造厂专为拖拉机厂配套生产柴油机，今年头四个月收到的定单数量分别为3000台、4500台、3500台、5000台。该厂正常生产每月可生产3000台，利用加班还可生产1500台，正常生产成本为每台5000元，加工生产还要追加1500元，库存成本为每台每月200元。问华津厂如何组织生产才能使生产成本最低？分析：设C=成本=四个月正常生产的成本+四个月加班生产的成本+四个月库存成本台柴油机个月正常生产设第ixi台柴油机加班生产iy,台柴油机个月初库存第izi4,3,2,1iC则415000iix416500iiy41200iiz41)20065005000(iiiizyx约束条件：台柴油机个月正常生产设第ixi台柴油机加班生产iy,台柴油机个月初库存第izi01z其中4,3,2,1i需求约束：第4个月5000444zyx第3个月35004333zzyx第2个月45003222zzyx第1个月3000211zyx生产能力约束：4,3,2,13000ixi4,3,2,11500iyi数学模型：ts.4,3,2,1,0,,izyxiii41)20065005000(miniiiizyxC5000444zyx35004333zzyx45003222zzyx3000211zyx4,3,2,13000ixi4,3,2,11500iyi四个月定单数量分别为3000台、4500台、3500台、5000台每月可生产3000台，利用加班还可生产1500台库存约束：01z01z例7.连续投资问题建模:某投资公司有100万元资金用于投资，投资的方案可以有以下六种，现要做一个5年期的投资计划，具体可选择的投资方案如下：方案A：5年内的每年年初均可投资，且金额不限，投资期限1年，年投资回报率7%。方案B：5年内的每年年初均可投资，且金额不限，投资期限2年，年投资回报率10%（不计复利）。方案C：5年内的每年年初均可投资，且金额不限，投资期限3年，年投资回报率12%（不计复利）方案D：只在第一年年初有一次投资机会，最大投资金额为50万元，投资期限4年，年投资回报率20%方案E：在第二年和第四年年初有一次投资机会，最大投资金额均为30万元，投资期限1年，年投资回报率30%方案F：在第四年年初有一次投资机会，金额不限，投资期限2年，年投资回报率25%假设当年的投资金额及其收益均可用于下一年的投资，问公司应如何投资才能使第五年末收回的资金最多？假设当年的投资金额及其收益均可用于下一年的投资，问公司应如何投资才能使第五年末收回的资金最多？所投资的金额，，，，，年初按方按分别表示第解：设FEDCBAiiFEDCBAiiiiii)5,4,3,2,1(,,,,,年末收回的总资金第5Z第一年初第二年初第三年初第四年初第五年初第五年末1A107.1A207.1A307.1A407.1A5A507.1A1B12.1B22.1B32.1B42.1B1C136.1C236.1C3A3B3C336.1C1D18.1D2A2B2C2E23.1E43.1E4A4B4E4F45.1E544307.15.12.136.1maxAFBCz求10000001111DCBA007.112222AECBA03.107.12.1211333EABCBA007.12.136.11214344ABCFEBA03.107.12.136.18.1413215EABCDA5000001D3000002E3000004E)5,4,3,2,1(0,,,,,iFEDCBAiiiiiits.连续投资问题模型:1.1.2、线性规划的标准形式和矩阵表达式线性规划问题的一般形式：nnxcxcxcz2211minmax）（或mnmnmmnnnnbxaxaxabxaxaxabxaxaxats），或或），或或），或或(((.22112222212111212111为已知常数其中),,2,1;,,2,1(,,njmi