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

1、上堂课主要内容：,一、线性规划模型引例,二、线性规划模型的建立,1、建模的一般步骤： 步骤一：确定决策变量 即用变量取不同的值来表示可供选择的各种不同方案,步骤二：建立目标函数,即找到目标值与决策变量的数量关系,步骤三：确定约束条件,即决策变量所受到的外界条件的制约。,约束条件一般为决策变量的等式或不等式,要求：目标函数与约束条件均是线性的， 且目标函数只能是一个。,2、线性规划模型的一般形式：,决策变量,约束方程,非负约束,目标函数,三、线性规划求解：,四、线性规划应用举例,计算机应用软件,例3 福安商场是个中型的百货商场，它对售货人员的 需求经过统计分析如下所示：,为保证售货人员充分休息，

2、 售货人员每周工作五天，休 息两天，并要求休息的两天 是连续的，问应该如何安排 售货人员的作息，既满足了 工作的需要，又使配备的售 货人员的人数最少？,解,约束条件 :,星期日 售货员人数要求:,星期一 售货员人数要求:,星期二 售货员人数要求:,星期三 售货员人数要求:,星期四 售货员人数要求:,星期五 售货员人数要求:,星期六 售货员人数要求:,数学模型:,非负约束 :,数学模型:,解得:,例3 福安商场是个中型的百货商场，它对售货人员的 需求经过统计分析如下所示：,为保证售货人员充分休息， 售货人员每周工作五天，休 息两天，并要求休息的两天 是连续的，问应该如何安排 售货人员的作息，既满

3、足了 工作的需要，又使配备的售 货人员的人数最少？,解,方案,下料数,(根),长度,例4 某工厂要做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

4、根，,共需原料90根。,例5 (产品配套问题）假定一个工厂的甲、乙、丙三个车间生产同一个产品，每件产品包括4个a零件，和3个b零件。这两种零件由两种不同的原材料制成，而这两种原材料的现有数额分别为100克和200克。每个生产班的原材料需要量和零件产量如下表所示。,问这三个车间各应开多少班才能使这种产品的配套数达到最大,约束条件为：,三个车间共生产a零件：,三个车间共生产b零件,非线性,要求：,目标函数：,目标函数 z=x4,线性,数学模型：,线性规划问题,例6 （多周期动态生产计划问题）华津机器制造厂专为拖拉机厂配套生产柴油机，今年头四个月收到的定单数量分别为3000台、4500台、3500台

5、、5000台。该厂正常生产每月可生产3000台，利用加班还可生产1500台，正常生产成本为每台5000元，加工生产还要追加1500元，库存成本为每台每月200元。问华津厂如何组织生产才能使生产成本最低？,分析：,设c=成本,=四个月正常生产的成本,+四个月加班生产的成本,+四个月库存成本,约束条件：,需求约束：,第4个月,第3个月,第2个月,第1个月,生产能力约束：,数学模型：,四个月定单数量分别为3000台、4500台、3500台、5000台,每月可生产3000台，利用加班还可生产1500台,库存约束：,例7.连续投资问题建模:某投资公司有100万元资金用于投资，投资的方案可以有以下六种，现

6、要做一个5年期的投资计划，具体可选择的投资方案如下： 方案a：5年内的每年年初均可投资，且金额不限，投资期限1 年，年投资回报率7%。 方案b：5年内的每年年初均可投资，且金额不限，投资期限2 年，年投资回报率10%（不计复利）。 方案c：5年内的每年年初均可投资，且金额不限，投资期限3 年，年投资回报率12%（不计复利） 方案d：只在第一年年初有一次投资机会，最大投资金额为50 万元，投资期限4年，年投资回报率20% 方案e：在第二年和第四年年初有一次投资机会，最大投资金额 均为30万元，投资期限1年，年投资回报率30% 方案f：在第四年年初有一次投资机会，金额不限，投资期限2 年，年投资回

7、报率25%,假设当年的投资金额及其收益均可用于下一年的投资，问公司应如何投资才能使第五年末收回的资金最多？,假设当年的投资金额及其收益均可用于下一年的投资，问公司应如何投资才能使第五年末收回的资金最多？,连续投资问题模型:,1.1.2、线性规划的标准形式和矩阵表达式,线性规划问题的一般形式：,1、线性规划的标准形式,标准型式的特征:,1、求目标函数的最大值,2、约束方程为等式方程,3、约束方程的右边非负,4、决策变量均非负,非标准型式有以下几种可能：,1、求目标函数的最小值,4、决策变量0或无限制,2、约束方程为不等式方程,3、约束方程的右边,2、非标准型式线性规划问题的标准化,-,max,（

8、1）对求目标函数最小值:,=,（2）约束条件为“”型,松弛变量,（3）约束条件为“”型,剩余变量,(4) 约束条件右边为负,（6）决策变量无符号限制,（5）决策变量0,例如,带入约束方程及目标函数,则原线性规划问题的标准型为:,3. 线性规划问题的矩阵表达式：,1.3 线性规划的基本理论,一、线性规划的解 1、可行解：,2、可行域：,（lp）的全体可行解构成的集合称为可行域,3、最优解及最优值：,设s是（lp）的可行域,不唯一,唯一,4、若对任意大的m0,都存在可行解使得该线性规划的目标 函数值,，则称该线性规划问题无界,二、两个变量的线性规划的图解法,解： （1）在直角坐标系上画出可行域,（

9、2）做目标函数的等值线,0,可行域,凸多边形,顶点,.,解： （1）在直角坐标系上画出可行域,（2）做目标函数的等值线,0,无穷多,.,.,解： （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,

11、即a中存在满秩的m阶矩阵b,称b为（lp）问题的一个基,不妨设mn,定义1.3 在（lp）问题中，a的任意一个mm阶 的非奇异子方阵b（即|b|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,基本可行解,