《建模的一般步骤步骤一确定决策变量即用变量取不同.ppt》由会员分享，可在线阅读，更多相关《建模的一般步骤步骤一确定决策变量即用变量取不同.ppt（53页珍藏版）》请在三一办公上搜索。
1、1、建模的一般步骤：步骤一：确定决策变量 即用变量取不同的值来表示可供选择的各种不同方案,步骤二：建立目标函数,即找到目标值与决策变量的数量关系,步骤三：确定约束条件,即决策变量所受到的外界条件的制约。,约束条件一般为决策变量的等式或不等式,要求：目标函数与约束条件均是线性的，且目标函数只能是一个。,2、线性规划模型的一般形式：,决策变量,约束方程,非负约束,目标函数,三、线性规划求解：,四、线性规划应用举例,计算机应用软件,例3 福安商场是个中型的百货商场，它对售货人员的 需求经过统计分析如下所示：,为保证售货人员充分休息，售货人员每周工作五天，休息两天，并要求休息的两天是连续的，问应该如何
2、安排售货人员的作息，既满足了工作的需要，又使配备的售货人员的人数最少？,解,约束条件:,星期日 售货员人数要求:,星期一 售货员人数要求:,星期二 售货员人数要求:,星期三 售货员人数要求:,星期四 售货员人数要求:,星期五 售货员人数要求:,星期六 售货员人数要求:,数学模型:,非负约束:,数学模型:,解得:,例3 福安商场是个中型的百货商场，它对售货人员的 需求经过统计分析如下所示：,为保证售货人员充分休息，售货人员每周工作五天，休息两天，并要求休息的两天是连续的，问应该如何安排售货人员的作息，既满足了工作的需要，又使配备的售货人员的人数最少？,解,方案,下料数,(根),长度,例4 某工厂
3、要做100套钢架,每套用长为2.9m,2.1m,和1.5m的圆钢各一根,已知原料每根长7.4m,问应如何下料,可使所用原料最省.,分析:,每根原料做一套钢架,下角料：,0.9m,用套裁方式,下料方案：,方案,下料数,(根),长度,下料方案：,方案,下料数,(根),长度,例4 某工厂要做100套钢架,每套用长为2.9m,2.1m,和1.5m的圆钢各一根,已知原料每根长7.4m,问应如何下料,可使所用原料最省.,下料方案：,最优下料方案：,按方案1下料30根，,方案2下料10根，,方案4下料50根，,共需原料90根。,例5(产品配套问题）假定一个工厂的甲、乙、丙三个车间生产同一个产品，每件产品包括
4、4个A零件，和3个B零件。这两种零件由两种不同的原材料制成，而这两种原材料的现有数额分别为100克和200克。每个生产班的原材料需要量和零件产量如下表所示。,问这三个车间各应开多少班才能使这种产品的配套数达到最大,约束条件为：,三个车间共生产A零件：,三个车间共生产B零件,非线性,要求：,目标函数：,目标函数 Z=x4,线性,数学模型：,线性规划问题,例6（多周期动态生产计划问题）华津机器制造厂专为拖拉机厂配套生产柴油机，今年头四个月收到的定单数量分别为3000台、4500台、3500台、5000台。该厂正常生产每月可生产3000台，利用加班还可生产1500台，正常生产成本为每台5000元，加
5、工生产还要追加1500元，库存成本为每台每月200元。问华津厂如何组织生产才能使生产成本最低？,分析：,设C=成本,=四个月正常生产的成本,+四个月加班生产的成本,+四个月库存成本,约束条件：,需求约束：,第4个月,第3个月,第2个月,第1个月,生产能力约束：,数学模型：,四个月定单数量分别为3000台、4500台、3500台、5000台,每月可生产3000台，利用加班还可生产1500台,库存约束：,例7.连续投资问题建模:某投资公司有100万元资金用于投资，投资的方案可以有以下六种，现要做一个5年期的投资计划，具体可选择的投资方案如下：方案A：5年内的每年年初均可投资，且金额不限，投资期限1
6、 年，年投资回报率7%。方案B：5年内的每年年初均可投资，且金额不限，投资期限2 年，年投资回报率10%（不计复利）。方案C：5年内的每年年初均可投资，且金额不限，投资期限3 年，年投资回报率12%（不计复利）方案D：只在第一年年初有一次投资机会，最大投资金额为50 万元，投资期限4年，年投资回报率20%方案E：在第二年和第四年年初有一次投资机会，最大投资金额 均为30万元，投资期限1年，年投资回报率30%方案F：在第四年年初有一次投资机会，金额不限，投资期限2 年，年投资回报率25%,假设当年的投资金额及其收益均可用于下一年的投资，问公司应如何投资才能使第五年末收回的资金最多？,假设当年的投
7、资金额及其收益均可用于下一年的投资，问公司应如何投资才能使第五年末收回的资金最多？,连续投资问题模型:,1.1.2、线性规划的标准形式和矩阵表达式,线性规划问题的一般形式：,1、线性规划的标准形式,标准型式的特征:,1、求目标函数的最大值,2、约束方程为等式方程,3、约束方程的右边非负,4、决策变量均非负,非标准型式有以下几种可能：,1、求目标函数的最小值,4、决策变量0或无限制,2、约束方程为不等式方程,3、约束方程的右边,2、非标准型式线性规划问题的标准化,-,max,（1）对求目标函数最小值:,=,（2）约束条件为“”型,松弛变量,（3）约束条件为“”型,剩余变量,(4)约束条件右边为负
8、,（6）决策变量无符号限制,（5）决策变量0,例如,带入约束方程及目标函数,则原线性规划问题的标准型为:,3.线性规划问题的矩阵表达式：,1.3 线性规划的基本理论,一、线性规划的解1、可行解：,2、可行域：,（LP）的全体可行解构成的集合称为可行域,3、最优解及最优值：,设S是（LP）的可行域,不唯一,唯一,4、若对任意大的M0,都存在可行解使得该线性规划的目标 函数值,，则称该线性规划问题无界,二、两个变量的线性规划的图解法,解：（1）在直角坐标系上画出可行域,（2）做目标函数的等值线,0,可行域,凸多边形,顶点,.,解：（1）在直角坐标系上画出可行域,（2）做目标函数的等值线,0,无穷多
9、,.,.,解：（1）在直角坐标系上画出可行域,（2）做目标函数的等值线,0,目标函数无上界，,该问题无界,无最优解,解：（1）在直角坐标系上画出可行域,0,可行域为空集,无可行解,该问题无最优解,图解法的基本步骤：,（一般是一个凸多边形）,注意：若是求目标函数的最小值，,目标函数直线向下移动,关于线性规划解的结论：,1、若（LP）问题有可行解，则可行域是一个凸多边形（或凸多面体）。它可能是有界的；也可能是无界的。,2、若（LP）问题有最优解，则最优解可能是唯一的；也可能 是无穷多个。如果是唯一的，这个解一定在该凸多边形的某 个顶点上；如果是无穷多个，则这些最优解一定充满凸多边 形的一条边界（包
10、括此边界的两个顶点）,总之，若（LP）问题有最优解，则最优解一定可以在凸多边形的某个顶点达到,3、若（LP）问题有可行解，但没有有限最优解，此时凸多边形 是无界的,（反之不成立）,4、若（LP）问题没有可行解，则该问题没有最优解,三、基与基本可行解,不妨设AX=b有解，且mn,利用线性代数的方法求出无穷多解？,只讨论rn,此时,且r(A)=r=m,(若rm,必有多余方程，可去掉）,由线性代数结论知:若r(A)=m，则A 中至少存在一个m阶子式|B|0,即A中存在满秩的m阶矩阵B,称B为（LP）问题的一个基,不妨设mn,定义1.3 在（LP）问题中，A的任意一个mm阶 的非奇异子方阵B（即|B|
11、0）称为（LP）问题的一个基,一个线性规划问题最多有 基,设r(Amxn)=r=m,设r(A)=mn,不妨设A的前m列构成A的一个基,基变量,非基变量,基,基,非基,由于B 可逆,基本解,定义1.4 设B是（LP）问题的一个基，,A=（B,N）,称此解为对应于基B的基本解,自由未知量,基,非基,定义1.5,基本可行解的个数,基本可行解,对应的基称为可行基,基,非基,基本可行解,可行基,A的任意一个mm阶的非奇异子方阵B,设r(A)=r=m,基:,基本解:,基本可行解:,可行解,基本解,基本可行解,有限,设X为基本可行解，,则X的n个分量中，最多有 个分量0,基本可行解,退化基本可行解：基本可行解中，存在取0值的基变量,非退化基本可行解：基本可行解中，基变量的取值均0,对应的基称为退化基,对应的基称为非退化基,线性规划问题,：存在退化基,：所有基均非退化,m,1.运输问题建模:,运输问题要解决的问题是：,如何利用现有的交通条件，以最低的运费安排调度,供销平衡,作业：,则该问题的数学模型为：,原线性规划问题的标准型为:,
