建模的一般步骤步骤一确定决策变量即用变量取不同ppt课件

1、 1、建模的普通步骤： 步骤一：确定决策变量 即用变量取不同的值来表示可供选择的各种不同方案步骤二：建立目的函数 即找到目的值与决策变量的数量关系步骤三：确定约束条件即决策变量所遭到的外界条件的制约。约束条件普通为决策变量的等式或不等式要求：目的函数与约束条件均是线性的， 且目的函数只能是一个。2、线性规划模型的普通方式：nnxcxcxcz2211minmax）（或mnmnmmnnnnbxaxaxabxaxaxabxaxaxats），或或），或或），或或(.22112222212111212111为已知常数其中),2, 1;,2, 1(,njmicbajiij0,21nxxx决策变量约束方程非

2、负约束 目的函数三、线性规划求解：四、线性规划运用举例nnxcxcxcz2211minmax）（或mnmnmmnnnnbxaxaxabxaxaxabxaxaxat s），或或），或或），或或(.221122222121112121110,21nxxx计算机运用软件时间所需售货员 人数星期日28人星期一15人星期二24人星期三25人星期四19人星期五31人星期六28人例3 福安商场是个中型的百货商场，它对售货人员的 需求经过统计分析如下所示：为保证售货人员充分休憩，售货人员每周任务五天，休息两天，并要求休憩的两天是延续的，问应该如何安排售货人员的作息，既满足了任务的需求，又使配备的售货人员的人数

3、最少？解，为周二开始休息的人数，为周一开始休息的人数设21xx，为周日开始休息的人数，为周六开始休息的人数76xx表示商场的售货员人数Z721xxx721minxxxZ求2854321xxxxx时间所需售货员人数星期日28人星期一15人星期二24人星期三25人星期四19人星期五31人星期六28人约束条件 :星期日 售货员人数要求: 1565432xxxxx星期一 售货员人数要求: 2476543xxxxx星期二 售货员人数要求: 2576541xxxxx星期三 售货员人数要求: 1976521xxxxx星期四 售货员人数要求: 3176321xxxxx星期五 售货员人数要求: 2874321x

4、xxxx星期六 售货员人数要求: 数学模型:721minxxxZ求ts.非负约束 :7 , 2 , 1, 0ixi2854321xxxxx1565432xxxxx2476543xxxxx2576541xxxxx1976521xxxxx3176321xxxxx2874321xxxxx7 , 2 , 1, 0ixi7 , 2 , 1,iixi日开始休息的人数为星期数学模型:721minxxxZ求ts.2854321xxxxx1565432xxxxx2476543xxxxx2576541xxxxx1976521xxxxx3176321xxxxx2874321xxxxx7 , 2 , 1, 0ixi解

5、得: 36. 0, 8, 0, 5,11, 0,1207654321Zxxxxxxx时间所需售货员 人数星期日28人星期一15人星期二24人星期三25人星期四19人星期五31人星期六28人例3 福安商场是个中型的百货商场，它对售货人员的 需求经过统计分析如下所示：为保证售货人员充分休憩，售货人员每周任务五天，休息两天，并要求休憩的两天是延续的，问应该如何安排售货人员的作息，既满足了任务的需求，又使配备的售货人员的人数最少？解，为周二开始休息的人数，为周一开始休息的人数设21xx，为周日开始休息的人数，为周六开始休息的人数76xx表示商场的售货员人数Z36. 0, 8, 0, 5,11, 0,1

6、207654321Zxxxxxxx解得：方案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.

7、8m方案下料数(根)长度下料方案：)5 , 4 , 3 , 2 , 1iixi数（第种方案下料的原料根为按解：设表示总用料数Z数学模型：54321minxxxxxZ求ts.1002421xxx10022543xxx1003235321xxxx. 0, 0, 0, 0, 054321xxxxx方案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, 问应如何下

8、料,可使所用原料最省.下料方案：90. 0, 05, 0, 01,30054321Zxxxxx最优值最优解：)5 , 4 , 3 , 2 , 1iixi数（第种方案下料的原料根为按总用料数Z最优下料方案： 按方案1下料30根， 方案2下料10根，方案4下料50根，共需原料90根。例5 (产品配套问题假定一个工厂的甲、乙、丙三个车间消费同一个产品，每件产品包括4个A零件，和3个B零件。这两种零件由两种不同的原资料制成，而这两种原资料的现有数额分别为100克和200克。每个消费班的原资料需求量和零件产量如下表所示。 每班进料数（克）每班产量（个数）第1种原材料第2种原材料A零件B零件甲8675乙5

9、969丙3884车间问这三个车间各应开多少班才干使这种产品的配套数到达最大车间所开的生产班数分别是甲、乙、丙三个，解：设321xxx产品的配套数z约束条件为：100358321xxx200896 ,321xxx000321xxx，三个车间共消费A零件：321867xxx三个车间共消费B零件321495xxx4867321xxxminz则3495,321xxx非线性表示生产出的产品数设4x要求： 每班进料数（克）每班产量（个数）第1种原材料第2种原材料A零件B零件甲8675乙5969丙3884车间车间所开的生产班数分别是甲、乙、丙三个，321xxx产品的配套数z目的函数：目的函数 Z=x4线性4

10、3214867xxxx43213495,xxxx数学模型：100358321xxx200896321xxx. 0, 0004321xxxx，4maxxz 线性规划问题t s.048674321xxxx034954321xxxx例6 多周期动态消费方案问题华津机器制造厂专为迁延机厂配套消费柴油机，今年头四个月收到的定单数量分别为3000台、4500台、3500台、5000台。该厂正常消费每月可消费3000台，利用加班还可消费1500台，正常消费本钱为每台5000元，加工消费还要追加1500元，库存本钱为每台每月200元。问华津厂如何组织消费才干使消费本钱最低？分析：设C=本钱 =四个月正常消费的

11、本钱+四个月加班消费的本钱 +四个月库存本钱台柴油机个月正常生产设第ixi台柴油机加班生产iy,台柴油机个月初库存第izi4 , 3 , 2 , 1iC则415000iix416500iiy41200iiz41)20065005000(iiiizyx约束条件：台柴油机个月正常生产设第ixi台柴油机加班生产iy,台柴油机个月初库存第izi01z其中4 , 3 , 2 , 1i需求约束：第4个月5000444zyx第3个月35004333zzyx第2个月45003222zzyx第1个月3000211zyx消费才干约束：4 , 3 , 2 , 13000ixi4 , 3 , 2 , 11500iyi

12、数学模型：ts.4 ,3 , 2 , 1,0,izyxiii41)20065005000(miniiiizyxC5000444zyx35004333zzyx45003222zzyx3000211zyx4 , 3 , 2 , 13000ixi4 , 3 , 2 , 11500iyi四个月定单数量分别为3000台、4500台、3500台、5000台每月可消费3000台，利用加班还可消费1500台库存约束：01z01z例7.延续投资问题建模:某投资公司有100万元资金用于投资，投资的方案可以有以下六种，现要做一个5年期的投资方案，详细可选择的投资方案如下：方案A：5年内的每年年初均可投资，且金额不限

13、，投资期限1 年，年投资报答率7%。方案B：5年内的每年年初均可投资，且金额不限，投资期限2 年，年投资报答率10%不计复利。方案C：5年内的每年年初均可投资，且金额不限，投资期限3 年，年投资报答率12%不计复利方案D：只在第一年年初有一次投资时机，最大投资金额为50 万元，投资期限4年，年投资报答率20%方案E：在第二年和第四年年初有一次投资时机，最大投资金额 均为30万元，投资期限1年，年投资报答率30%方案F：在第四年年初有一次投资时机，金额不限，投资期限2 年，年投资报答率25%假设当年的投资金额及其收益均可用于下一年的投资，问公司应如何投资才干使第五年末收回的资金最多？假设当年的投

14、资金额及其收益均可用于下一年的投资，问公司应如何投资才干使第五年末收回的资金最多？所投资的金额，年初按方按分别表示第解：设FEDCBAiiFEDCBAiiiiii)5 , 4 , 3 , 2 , 1(,年末收回的总资金第5Z第一年初 第二年初 第三年初 第四年初 第五年初 第五年末1A107. 1A207. 1A307. 1A407. 1A5A507. 1A1B12.1B22 . 1B32 . 1B42 . 1B1C136.1C236. 1C3A3B3C336. 1C1D18 .1D2A2B2C2E23 . 1E43 . 1E4A4B4E4F45 . 1E544307. 15 . 12 . 1

15、36. 1maxAFBCz求10000001111DCBA007. 112222AECBA03 . 107. 12 . 1211333EABCBA007. 12 . 136. 11214344ABCFEBA03 . 107. 12 . 136. 18 . 1413215EABCDA5000001D3000002E3000004E)5 , 4 , 3 , 2 , 1(0,iFEDCBAiiiiiit s.延续投资问题模型:1.1.2、线性规划的规范方式和矩阵表达式线性规划问题的普通方式：nnxcxcxcz2211minmax）（或mnmnmmnnnnbxaxaxabxaxaxabxaxaxat

16、s），或或），或或），或或(.22112222212111212111为已知常数其中),2, 1;,2, 1(,njmicbajiij0,21nxxx1、线性规划的规范方式nnxcxcxcz2211maxmnmnmmnnnnbxaxaxabxaxaxabxaxaxats22112222212111212111.0,21nxxx0,21mbbbniiixcz1maxnijijibxa1mj, 2 , 1nixi, 2 , 10mjbj, 2 , 10niiixcz1max即nijijibxats1.mjbj, 2 , 10nixi, 2 , 10nnxcxcxcz2211maxmnmnmmnnn

17、nbxaxaxabxaxaxabxaxaxats22112222212111212111.0,21nxxx0,21mbbb规范型式的特征:1、求目的函数的最大值2、约束方程为等式方程3、约束方程的右边非负4、决策变量均非负非规范型式有以下几种能够：1、求目的函数的最小值4、决策变量0,都存在可行解使得该线性规划的目的 函数值MZ ，那么称该线性规划问题无界二、两个变量的线性规划的图解法0,3482.52max121212121xxxxxxtsxxz划用图解法解以下线性规例解： 1在直角坐标系上画出可行域2做目的函数的等值线3*,2*)4(21xx最优解为193522*z最优值01x2x.822

18、1xx41x32x可行域kxx2152105221 xx求交点：) 3(382221xxx)3 , 2(),(21xx凸多边形顶点.0,3482.2max221212121xxxxxxtsxxz划用图解法解以下线性规例解： 1在直角坐标系上画出可行域2做目的函数的等值线8*)3(z最优值01x2x.8221xx41x32x2221xx求交点：382221xxx)3 , 2(),(21xx2221xx482121xxx) 2 , 4(),(21xx）之间的所有点。，）与点（，上界于点（最优解：直线24328221xx无穷多.0,4422.32max321212121xxxxxxtsxxz划用图解

19、法解以下线性规例解： 1在直角坐标系上画出可行域2做目的函数的等值线01x2x.2221 xx63221xx4421xx目的函数无上界，该问题无界无最优解0,43222.32max4212212121xxxxxxxtsxxz划用图解法解以下线性规例解： 1在直角坐标系上画出可行域01x2x.3221 xx42x2221xx可行域为空集无可行解该问题无最优解图解法的根本步骤：的图形上做出可行域、在直角坐标系Soxx211普通是一个凸多边形,2k给定的常数、令目标函数值取一个kxcxcZ2211做等值线,max3由小变大问题，令目标函数值、对k即让等值线向上平移，点边界线上的点均是最优的一条边界重

20、合，此时若与点，则该点就是所求的最优的一个顶点），是最后交于一个点（一般若它与可行域SSS，即得最优解立求解，边界线所代表的方程联、将最优点所在的两条*4X*CXZX值带入目标函数，得最优把最优解留意：假设是求目的函数的最小值，目的函数直线向下挪动关于线性规划解的结论：1、假设LP问题有可行解，那么可行域是一个凸多边形或凸多面体。它能够是有界的；也能够是无界的。2、假设LP问题有最优解，那么最优解能够是独一的；也能够 是无穷多个。假设是独一的，这个解一定在该凸多边形的某 个顶点上；假设是无穷多个，那么这些最优解一定充溢凸多边 形的一条边境包括此边境的两个顶点总之，假设LP问题有最优解，那么最优

21、解一定可以在凸多边形的某个顶点到达3、假设LP问题有可行解，但没有有限最优解，此时凸多边形 是无界的反之不成立4、假设LP问题没有可行解，那么该问题没有最优解三、基与根本可行解nxxxX21ncccC21mnmmnnaaaaaaaaaA212222111211其中mbbbb210,0.max)(bXbAXtsCXzLP 问题对无妨设AX=b有解，且mn，解的结构：对bAX ，唯一解若nrArAr)()(有无穷多解bAX 利用线性代数的方法求出无穷多解？ 只讨论rn, 此时nrArAr)()(有解的充要条件是且r(A)=r=m(假设rm,必有多余方程，可去掉0,0.max)(bXbAXtsCXz

22、LP问题对由线性代数结论知: 假设r(A)=m，那么A 中至少存在一个m阶子式 |B|0即A中存在满秩的m阶矩阵B ,称B为LP问题的一个基325323222432143214321xxxxxxxxxxxx例如：321115323221121A110100000021121，对bAX nrArAr)()(且无妨设mn321110000021121mArAr2)()(定义1.3 在LP问题中，A的恣意一个mm阶 的非奇特子方阵B即|B|0称为 LP问题的一个基一个线性规划问题最多有 基mnC0,0.max)(bXbAXtsCXzLP问题对设r(Amxn)=r=m0,2162.7max211212

23、121xxxxxxxtsxxz对线性规划问题例0,2162.7max543215142132121xxxxxxxxxxxxxt sxxz其标准型为100010101100121A系数矩阵54321PPPPP5432PPPB 3211PPPB 基基4323PPPB 不是基设r(A)=m0根本可行解非退化基本可行解退化基本可行解退化根本可行解：根本可行解中，存在取0值的基变量非退化根本可行解：根本可行解中，基变量的取值均0对应的基称为退化基对应的基称为非退化基，即001bBX01bB线性规划问题非退化的线性规划问题退化的线性规划问题：存在退化基：一切基均非退化mBxxxX21得, bAX 即对01nmNxxX令m1.运输问题建模:运输问题要处理的问题是：如