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

线性规划图解法经典运筹学第1页，共54页，2023年，2月20日，星期六

1、建模的一般步骤：步骤一：确定决策变量即用变量取不同的值来表示可供选择的各种不同方案步骤二：建立目标函数即找到目标值与决策变量的数量关系步骤三：确定约束条件即决策变量所受到的外界条件的制约。约束条件一般为决策变量的等式或不等式要求：目标函数与约束条件均是线性的，且目标函数只能是一个。第2页，共54页，2023年，2月20日，星期六2、线性规划模型的一般形式：决策变量约束方程非负约束目标函数第3页，共54页，2023年，2月20日，星期六三、线性规划求解：四、线性规划应用举例计算机应用软件第4页，共54页，2023年，2月20日，星期六时间所需售货员人数星期日28人星期一15人星期二24人星期三25人星期四19人星期五31人星期六28人例3福安商场是个中型的百货商场，它对售货人员的需求经过统计分析如下所示：为保证售货人员充分休息，售货人员每周工作五天，休息两天，并要求休息的两天是连续的，问应该如何安排售货人员的作息，既满足了工作的需要，又使配备的售货人员的人数最少？解第5页，共54页，2023年，2月20日，星期六时间所需售货员人数星期日28人星期一15人星期二24人星期三25人星期四19人星期五31人星期六28人约束条件:星期日售货员人数要求:星期一售货员人数要求:星期二售货员人数要求:星期三售货员人数要求:星期四售货员人数要求:星期五售货员人数要求:星期六售货员人数要求:数学模型:非负约束:第6页，共54页，2023年，2月20日，星期六数学模型:解得:第7页，共54页，2023年，2月20日，星期六时间所需售货员人数星期日28人星期一15人星期二24人星期三25人星期四19人星期五31人星期六28人例3福安商场是个中型的百货商场，它对售货人员的需求经过统计分析如下所示：为保证售货人员充分休息，售货人员每周工作五天，休息两天，并要求休息的两天是连续的，问应该如何安排售货人员的作息，既满足了工作的需要，又使配备的售货人员的人数最少？解第8页，共54页，2023年，2月20日，星期六方案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用套裁方式下料方案：第9页，共54页，2023年，2月20日，星期六方案1方案2方案3方案4方案52.9m120102.1m002211.5m31203合计7.4m7.3m7.2m7.1m6.6下角料0m0.1m0.2m0.3m0.8m方案下料数(根)长度下料方案：第10页，共54页，2023年，2月20日，星期六方案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,问应如何下料,可使所用原料最省.下料方案：最优下料方案：按方案1下料30根，方案2下料10根，方案4下料50根，共需原料90根。第11页，共54页，2023年，2月20日，星期六例5(产品配套问题）假定一个工厂的甲、乙、丙三个车间生产同一个产品，每件产品包括4个A零件，和3个B零件。这两种零件由两种不同的原材料制成，而这两种原材料的现有数额分别为100克和200克。每个生产班的原材料需要量和零件产量如下表所示。问这三个车间各应开多少班才能使这种产品的配套数达到最大约束条件为：第12页，共54页，2023年，2月20日，星期六三个车间共生产A零件：三个车间共生产B零件非线性要求：目标函数：目标函数Z=x4线性第13页，共54页，2023年，2月20日，星期六数学模型：线性规划问题第14页，共54页，2023年，2月20日，星期六例6（多周期动态生产计划问题）华津机器制造厂专为拖拉机厂配套生产柴油机，今年头四个月收到的定单数量分别为3000台、4500台、3500台、5000台。该厂正常生产每月可生产3000台，利用加班还可生产1500台，正常生产成本为每台5000元，加工生产还要追加1500元，库存成本为每台每月200元。问华津厂如何组织生产才能使生产成本最低？分析：设C=成本=四个月正常生产的成本+四个月加班生产的成本+四个月库存成本约束条件：第15页，共54页，2023年，2月20日，星期六需求约束：第4个月第3个月第2个月第1个月生产能力约束：数学模型：四个月定单数量分别为3000台、4500台、3500台、5000台每月可生产3000台，利用加班还可生产1500台库存约束：第16页，共54页，2023年，2月20日，星期六例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%假设当年的投资金额及其收益均可用于下一年的投资，问公司应如何投资才能使第五年末收回的资金最多？第17页，共54页，2023年，2月20日，星期六假设当年的投资金额及其收益均可用于下一年的投资，问公司应如何投资才能使第五年末收回的资金最多？第18页，共54页，2023年，2月20日，星期六连续投资问题模型:第19页，共54页，2023年，2月20日，星期六1.1.2、线性规划的标准形式和矩阵表达式线性规划问题的一般形式：第20页，共54页，2023年，2月20日，星期六1、线性规划的标准形式第21页，共54页，2023年，2月20日，星期六标准型式的特征:1、求目标函数的最大值2、约束方程为等式方程3、约束方程的右边非负4、决策变量均非负非标准型式有以下几种可能：1、求目标函数的最小值4、决策变量<0或无限制2、约束方程为不等式方程3、约束方程的右边第22页，共54页，2023年，2月20日，星期六2、非标准型式线性规划问题的标准化-max（1）对求目标函数最小值:=第23页，共54页，2023年，2月20日，星期六（2）约束条件为“≤”型松弛变量第24页，共54页，2023年，2月20日，星期六（3）约束条件为“≥”型剩余变量第25页，共54页，2023年，2月20日，星期六(4)约束条件右边为负（6）决策变量无符号限制（5）决策变量≤0例如带入约束方程及目标函数第26页，共54页，2023年，2月20日，星期六则原线性规划问题的标准型为:第27页，共54页，2023年，2月20日，星期六第28页，共54页，2023年，2月20日，星期六3.线性规划问题的矩阵表达式：第29页，共54页，2023年，2月20日，星期六

§1.3线性规划的基本理论第30页，共54页，2023年，2月20日，星期六一、线性规划的解1、可行解：2、可行域：（LP）的全体可行解构成的集合称为可行域3、最优解及最优值：设S是（LP）的可行域不唯一唯一4、若对任意大的M>0,都存在可行解使得该线性规划的目标函数值，则称该线性规划问题无界第31页，共54页，2023年，2月20日，星期六二、两个变量的线性规划的图解法解：（1）在直角坐标系上画出可行域（2）做目标函数的等值线0可行域凸多边形顶点.第32页，共54页，2023年，2月20日，星期六解：（1）在直角坐标系上画出可行域（2）做目标函数的等值线0无穷多..第33页，共54页，2023年，2月20日，星期六解：（1）在直角坐标系上画出可行域（2）做目标函数的等值线0目标函数无上界，该问题无界无最优解第34页，共54页，2023年，2月20日，星期六解：（1）在直角坐标系上画出可行域0可行域为空集无可行解该问题无最优解第35页，共54页，2023年，2月20日，星期六图解法的基本步骤：（一般是一个凸多边形）注意：若是求目标函数的最小值，目标函数直线向下移动第36页，共54页，2023年，2月20日，星期六关于线性规划解的结论：1、若（LP）问题有可行解，则可行域是一个凸多边形（或凸多面体）。它可能是有界的；也可能是无界的。2、若（LP）问题有最优解，则最优解可能是唯一的；也可能是无穷多个。如果是唯一的，这个解一定在该凸多边形的某个顶点上；如果是无穷多个，则这些最优解一定充满凸多边形的一条边界（包括此边界的两个顶点）总之，若（LP）问题有最优解，则最优解一定可以在凸多边形的某个顶点达到3、若（LP）问题有可行解，但没有有限最优解，此时凸多边形是无界的（反之不成立）4、若（LP）问题没有可行解，则该问题没有最优解第37页，共54页，2023年，2月20日，星期六三、基与基本可行解不妨设AX=b有解，且m≤n利用线性代数的方法求出无穷多解？×只讨论r<n,此时第38页，共54页，2023年，2月20日，星期六且r(A)=r=m(若r<m,必有多余方程，可去掉）由线性代数结论知:若r(A)=m，则A中至少存在一个m阶子式|B|≠0即A中存在满秩的m阶矩阵B,称B为（LP）问题的一个基不妨设m≤n第39页，共54页，2023年，2月20日，星期六定义1.3在（LP）问题中，A的任意一个m×m阶的非奇异子方阵B（即|B|≠0）称为（LP）问题的一个基一个线性规划问题最多有基设r(Amxn)=r=m第40页，共54页，2023年，2月20日，星期六基基不是基第41页，共54页，2023年，2月20日，星期六设r(A)=m<n不妨设A的前m列构成A的一个基基变量非基变量第42页，共54页，2023年，2月20日，星期六基,基非基,第43页，共54页，2023年，2月20日，星期六由于B可逆基本解定义1.4设B是（LP）问题的一个基，,A=（B,N）,称此解为对应于基B的基本解自由未知量第44页，共54页，2023年，2月20日，星期六基,非基,第45页，共54页，2023年，2月20日，星期六定义1.5基本可行解的个数基本可行解对应的基称为可行基第46页，共54页，2023年，2月20日，星期六基,非基,基本可行解可行基第47页，共54页，2023年，2月20日，星期六A的任意一个m×