线性规划和单纯形法.

运筹帷幄之中决胜千里之外第二章线性规划和单纯形法运筹学主讲：李文全Email:[e-mail]:13580109088掌握线性规划的基本建模法和单纯形法基本原理会在不同条件下运用单纯形法求解线性规划问题了解线性规划在经济和管理中的基本应用方法教学要求线性规划实例与模型线性规划的图解法与基本性质单纯形法原理线性规划的初始解解法目录第一节线性规划实例与模型线性规划是运筹学中理论最完善、方法最成熟，并具有广泛应用的一个分支线性规划主要研究两类问题：一、在现有资源有限的条件下，如何合理地安排，才能以最少的人力、物力资源去完成任务二、在任务确定后，如何计划、安排、才能在完成任务的前提下，使得现在资源的消耗最低两类问题本质是一样的：即在一定约束条件下，使某一目标达到最优第一节线性规划实例与模型一、应用实例在许多经济管理中的问题都能用线性规划模型来表示，如在企业的生产计划问题中，为了制造同种产品，必须利用各种生产要素，如原材料、劳动力、运输等，同时又有多种生产的工艺模式，在这些模式中，生产要素在制造产品的单位时间内的消耗量是不同的，生产要素的消耗量和产品的产出量依赖于以某种工艺模式生产时所花费的时间。那么，如何在各种生产要素的消耗量都有限的限制条件下，使得产品的产出量最大呢?实例说明：实用举例例1某公司通过市场调研，决定生产中高档新型拉杆箱。某分销商决定买进该公司3个月内的全部产品。拉杆箱生产需经过原材料剪裁、缝合、定型、检验和包装4过程。通过分析生产过程，得出：生产中档拉杆箱需要用7/10小时剪裁、5/10小时缝合、1小时定型、1/10小时检验包装；生产高档拉杆箱则需用1小时剪裁、5/6小时缝合、2/3小时定型、1/4小时检验包装。由于公司生产能力有限，3月内各部的最大生产时间为剪裁部630小时、缝合部600小时、定型部708小时、检验包装部135小时。通过市场调研得出结论：生产中档拉杆箱的利润是10元，高档拉杆箱的利润是9元。公司应各生产多少中档和高档拉杆箱才能使公司利润最大？某公司通过市场调研，决定生产高中档新型拉杆箱。某分销商决定买进该公司3个月内的全部产品。拉杆箱生产需经过原材料剪裁、缝合、定型、检验和包装4过程。通过分析生产过程，得出：生产中档拉杆箱需要用7/10小时剪裁、5/10小时缝合、1小时定型、1/10小时检验包装；生产高档拉杆箱则需用1小时剪裁、5/6小时缝合、2/3小时定型、1/4小时检验包装。由于公司生产能力有限，3月内各部的最大生产时间为剪裁部630小时、缝合部600小时、定型部708小时、检验包装部135小时。通过市场调研部和会计部的调查核算得出结论：生产中档拉杆箱的利润是10元，高档拉杆箱的利润是9元。公司应各生产多少中档和高档拉杆箱才能使公司利润最大？可以通过线性规划求解！实用举例解：将一个实际问题转化为线性规划模型有以下几个步骤：1．确定决策变量：x1：表示中档拉杆箱的数量x2：表示高档拉杆箱的数量2．确定目标函数：公司的追求目标是总利润最大，即maxz=10x1+9x23．确定约束条件：生产能力受下列条件约束7/10X1+X2≤630（剪裁时间≤公司剪裁部门最大工作时间）1/2X1+5/6X2≤600(缝合时间≤公司缝合部门最大工作时间)X1+2/3X2≤780(定型时间限制)1/10X1+1/4X2≤135(检验包装时间限制)4．变量取值限制：一般情况，决策变量只取正值（非负值）x10,x20第一节线性规划实例与模型二、线性规划模型的建立建立相应的线性规划模型：其中的x1,x2称为决策变量。0,0135708600630..910zmax21241110123212651212110721xxxxxxxxxxtsxx目标函数约束条件这是个典型的多产品生产问题(Max,)第一节线性规划实例与模型生产计划问题III资源限量设备原材料A原材料B1402048台时16kg12kg利润23第一节线性规划实例与模型产品I产品2如何安排生产使利润最大？第一节线性规划实例与模型x1x2是问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定和控制。•第1步-确定决策变量x1x2z•设——I的产量——II的产量——利润第一节线性规划实例与模型第2步--定义目标函数MaxZ=x1+x2第一节线性规划实例与模型MaxZ=2x1+3x2第2步--定义目标函数第一节线性规划实例与模型对我们有何限制?第3步--表示约束条件x1+2x284x1164x212x1、x20III资源限量设备原材料A原材料B1402048台时16kg12kg利润23第一节线性规划实例与模型该计划的数学模型目标函数MaxZ=2x1+3x2约束条件x1+2x284x1164x212x1、x20x1x2第一节线性规划实例与模型例某饲料希望用玉米、红薯作原料配制一种混合饲料，各种原料包含的营养成分和采购都不同，公司管理层希望能够确定混合饲料中的各种原料数量，使得饲料能够以最低成本达到一定的营养要求，研究者根据这一目标收集到的有关数据如下所示营养成分每公斤玉米每公斤红薯每公斤最低要求碳水化合物8420蛋白质3618维他命1516采购成本0.80.5第一节线性规划实例与模型解：将一个实际问题转化为线性规划模型有以下几个步骤：1．确定决策变量：x1：表示混合饲料中玉米的数量x2：表示混合饲料中红薯的数量2．确定目标函数：公司的追求目标是总成本最低，即minz=0.8x1+0.5x23．确定约束条件：生产能力受下列条件约束8X1+4X2≥20（碳水化合物要求）3X1+6X2≥18(蛋白质要求)X1+5X2≥16(维他命物要求)4．变量取值限制：一般情况，决策变量只取正值（非负值）x10,x20第一节线性规划实例与模型建立相应的线性规划模型：（min,)0,016518632048..5.00.8zmin2121212121xxxxxxxxtsxx第一节线性规划实例与模型原料甲原料乙最低含量A1237B236C3158单价32问如何采购原料才能使在保证最低需求的前提下花费最省？解：设x1,x2分别代表每单位该产品中甲、乙两种原料的用量,该问题的数学模型为：minZ=3x1+2x2s.t.12x1+3x272x1+3x263x1+15x28x1，x20第一节线性规划实例与模型例2配料问题（min,)线性规划数学模型三要素：决策变量、目标函数、约束条件技术系数右端项价值系数线性规划问题的规模约束行数变量个数:;:;::;:;:0,,,),(),(),(..)(max(min)21221122222121112121112211ijjjnmnmnmmnnnnnnabcmnmnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcxf一般形式三、一般线性规划模型第一节线性规划实例与模型x1..xnb1..bma11…a1n…………am1…amnx=b=A=c1..cnc=0Xb),(AXt.scxzmin)max(或Tmbbbb21称为资源限制向量X=(x1,x2,…,xn)T称为决策变量向量aaaaaaaaamnmmnnA212222111211称为约束方程系数矩阵(也称消耗系数矩阵)其中c=(c1,c2,…,cn)，称为价值系数向量；第一节线性规划实例与模型（一）标准化：为了讨论方便，把最大化、等式约束型的线性规划称为线性规划的标准型，即0,,,..)(max21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcxf2143三、线性规划模型的标准形式第一节线性规划实例与模型（1）目标函数为min型，价值系数一律反号。令f(x)=-f(x)=-CX,有minf(x)=-max[-f(x)]=-maxf(x)Example:minZ=x1+2x2+x3maxZ’=-x1-2x2-x3Maxz’Minzab注意：z与z’的解相同但目标函数值相差一负号zz’（一）不标准化标准的方法第一节线性规划实例与模型（2）第i个约束的bi为负值，则该行左右两端系数同时反号，同时不等号也要反向Example:4x1-2x2-3x3=-6-4x1+2x2+3x3=62x1+3x2-4x3-3-2x1-3x2+4x33(3)第i个约束为型，在不等式左边增加一个非负的变量xn+i，称为松弛变量；同时令cn+i=0Example:-2x1+x2+x39-2x1+x2+x3+x4=9第i个约束为型，在不等式左边减去一个非负的变量xn+i，称为剩余变量；同时令cn+i=0Example:-3x1+x2+2x34-3x1+x2+2x3–x5=4(4)若xj0，令xj=-xj，代入非标准型，则有xj0若xj不限，令xj=xj-xj，xj0，xj0，代入非标准型第一节线性规划实例与模型•例:将如下线性规划模型标准化：minz=x1+5x2-8x3-x4s.t.2x1-3x2+x3+x4≤20x1+2x2+3x3-x4≥302x2+2x3+3x4≥-50x1,x3,x4≥0，x2取值无约束。决策变量标准化y2-y3=x2第一节线性规划实例与模型minz=x1+5(y2-y3)-8x3-x4s.t.2x1–3(y2-y3)+x3+x4≤20x1+2(y2-y3)+3x3-x4≥302(y2-y3)+2x3+3x4≥-50x1,x3,x4，y2,y3≥0minz=x1+5y2-5y3-8x3-x4s.t.2x1–3y2+3y3+x3+x4≤20x1+2y2-2y3+3x3-x4≥302y2-2y3+2x3+3x4≥-50x1,x3,x4，y2,y3≥0约束条件标准化:第一节线性规划实例与模型B30两边乘负号minz=x1+5y2-5y3-8x3-x4s.t.2x1–3y2+3y3+x3+x4≤20x1+2y2-2y3+3x3-x4≥302y2-2y3+2x3+3x4≥-50x1,x3,x4，y2,y3≥0minz=x1+5y2-5y3-8x3-x4s.t.2x1–3y2+3y3+x3+x4≤20x1+2y2-2y3+3x3-x4≥30-2y2+2y3-2x3-3x4≤50x1,x3,x4，y2,y3≥0minz=x1+5y2-5y3-8x3-x4＋0x5+0x6+0x7s.t.2x1–3y2+3y3+x3+x4+x5=20x1+2y2-2y3+3x3-x4-x6=30-2y2+2y3-2x3-3x4+x7=50x1,x3,x4，y2,y3,x5,x6,x7≥0Maxz2=-x1-5y2+5y3+8x3+x4s.t.2x1-3y2+3y3+x3+x4+x5=20x1+2y2－2y3+3x3-x4-x6=30-2y2+2y3-2x3-3x4+x7=50x1,x3,x4,x5,x6,x7,y2,y3≥0目标函数标准化第一节线性规划实例与模型minz=x1+5y2-5y3-8x3-x4＋0x5+0x6+0x7s.t.2x1–3y2+3y3+x3+x4+x5=20x1+2y2-2y3+3x3-x4-x6=30-2y2+2y3-2x3-3x4+x7=50x1,x3,x4，y2,y3,x5,x6,x7≥00,,20040065300432..423)(min:213321321321321xxxxxxxxxxxxtsxxxxf不限原非标准型0,,