运筹学
线性规划基本性质
线形规划基本性质目录
线性规划（概论）
线性规划问题:生产计划问题
例1.1 生产计划问题（资源利用问题）例1.1生产计划问题分析
例1.1生产计划问题模型
例1.1生产计划问题表格描述
例1 .2 营养配餐问题
各种食物的营养成分表
各种食物的营养成分表（转置）
例1 .2 营养配餐问题求解
用于成功决策的实例
线形规划的一般模型:特点
线形规划的一般模型:数学模型线性规划问题隐含的假定
比例性假定
可加性假定
连续性假定
确定性假定
线形规划的图解法
线形规划解的可能结果
线形规划的标准形式1
线形规划的标准形式2
非标准型LP的标准化:目标函数
非标准型LP的标准化:约束函数1
非标准型LP的标准化:约束函数2
非标准型LP的标准化:决策变量
线形规划解的概念：可行解
线形规划解的概念：最优解
线形规划解的概念：基本解
线形规划解的概念：最优基本解
线形规划的应用模型
生产计划问题
生产计划问题：表格分析
生产计划问题：模型
产品配套问题
产品配套问题：工时分析
产品配套问题：配套分析
产品配套问题：模型
结束放映
线性规划（概论）
线形规划是研究解决有限资源最佳分配的运筹学方法，即如何对有限的资源做出最佳方式的调配和最有利的利用，以便最充分地发挥资源的效能去获得最佳经济效益。
线性规划问题:生产计划问题
1、如何合理使用有限的人力、物力和资
金，实现最好的经济效益。
2、如何合理使用有限的人力、物力和资
金，以达到最经济的方式，完成生产
计划的要求。
例1.1 生产计划问题（资源利用问题）
胜利家具厂生产桌子和椅子两种家具。桌子售价50元/张，椅子销售价格30元/把，生产桌子和椅子要求需要木工和油漆工两种工种。生产一张桌子需要木工4小时，油漆工2小时。生产一把椅子需要木工3小时，油漆工1小时。该厂每个月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？
解：将实际问题转化为线性规划模型有以下几个步骤：1．确定决策变量：x1=生产桌子的数量
x2=生产椅子的数量
2．确定目标函数：家具厂的目标是销售收入最大
max z=50x1+30x2（1）3．确定约束条件：
4x 1+3x2≤120（木工工时限制)（2）
2x1+x2≤50（油漆工工时限制）（3）4．变量取值限制：
一般情况，决策变量只取正值（非负值）
x1≥0,x2≥0（4）
数学模型
max S=50x
1+30x
2（1）
s.t.4x
1+3x
2
≤120（2）
2x
1+x
2
≤50（3）
x 1，x
2
≥0（4）
线性规划数学模型三要素：
1、决策变量：X1,X2
2、目标函数：（1）
3、约束条件：（2、3、4）注：s.t.–Subject to
例1.1生产计划问题表格描述
桌子椅子总工时木工43120
漆工2150
单价5030
生产量X1X2
例1 .2 营养配餐问题
假定一个成年人每天需要从食物中获得3000千卡的热量、55克蛋白质和800毫克
的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量和营养成分和市场价格见各种食物的营养成分表。问如何选择才能在满足营养的前提下使购买食品的费用最小？
各种食物的营养成分表
序号食品
名称
热量
（千卡）
蛋白质
（克）
钙
（毫克）
价格
（元）
1猪肉10005040014 2鸡蛋800602006 3大米900203003 4白菜200105002
各种食物的营养成分表（转置）
猪肉鸡蛋大米白菜营养要求热量（千卡）10008009002003000蛋白质（克）5060201055
钙（毫克）400200300500800
价格（元）14632
食品需要量X1X2X3X4
例1 .2 营养配餐问题求解
设X
为第j种食品每天的购入量，则配餐
j
问题的线性规划模型为：
min S=14x1+6x2+3x3+2x4
s.t.1000x1+800x2+900x3+200x4≥3000 50x1+60x2+20x3+10x4≥55
400x1+200x2+300x3+500x4≥800
x1，x2，x3，x4≥0
用于成功决策的实例
1、美国航空公司关于哪架飞机用于哪一航
班和哪些机组人员被安排于哪架飞机的决策；
2、美国国防部关于如何从现有的一些基地
向海湾运送海湾战争所需要的人员和物资的决策；
3、北美长途运输公司关于每周如何调度数
千辆货车的决策。
线形规划的一般模型:特点
系统需要求解待定方案，方案必须满足指定的条件，而且需要实现指定的目标。
1、决策变量：表示待定方案，一组取值代表一个方案，决策变量需要满足一定条件；
2、约束条件：用等式或不等式表示；
3、期望目标：用确定的数量方法表示。
线形规划的一般模型:数学模型max z=c1x1 +c2x2 +… +c nxn
s.t.a11x1 +a12x2 +… +a1n x n ≤b1
a21x1 +a22x2 +… +a2n x n ≤b2
……………………………………………
a m1x1 +a m2x2 +… +a mn x n ≤
b m
x j ≥0 (j = 1,2,…,n)
线性规划问题隐含的假定
?比例性假定
?可加性假定
?连续性假定
?确定性假定
决策变量变化引起的目标函数的改变量和决策变量的改变量成比例，同样，每个决策变量的变化引起约束方程左端值的改变量和该变量的改变量成比例。
每个决策变量对目标函数和约束方程的影响是独立于其他变量的，目标函数值是每个决策变量对目标函数贡献的总和。
连续性假定
线性规划问题中的决策变量应取连续值。
确定性假定
线性规划问题中的所有参数都是确定的参数。线性规划问题不包含随机因素。
11（2），12,14,18 习题 2-1 判断下列说法是否正确： （1） 任何线性规划问题存在并具有惟一的对偶问题； T （2） 对偶问题的对偶问题一定是原问题；T （3） 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之， 当对偶问题无可行解时，其原问题具有无界解；F （4） 若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优 解； （5） 若线性规划问题中的b i ，c j 值同时发生变化，反映到最终单纯形表中，不会出 现原问题与对偶问题均为非可行解的情况； （6） 应用对偶单纯形法计算时，若单纯形表中某一基变量x i <0，又x i 所在行的元素全 部大于或等于零，则可以判断其对偶问题具有无界解。 （7） 若某种资源的影子价格等于k ，在其他条件不变的情况下，当该种资源增加 5个单位时，相应的目标函数值将增大5k ； （8） 已知y i 为线性规划的对偶问题的最优解，若y i >0，说明在最优生产计划中第 i 种资源已经完全耗尽；若y i =0，说明在最优生产计划中的第i 种资源一定有剩余。 2-2将下述线性规划问题化成标准形式。 ????? ? ?≥≥-++-≤+-+-=-+-+-+-=无约束 43 214321432143214321,0,,232142224.5243max )1(x x x x x x x x x x x x x x x x st x x x x z 2-3分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基 可行解对应图解法中可行()?????≥≤≤-+-=++-+-=无约束 321 3213213 21,0,06 24 .322min 2x x x x x x x x x st x x x z 域的哪一顶点。 ()??? ??≥≤+≤++=0,8259 43.510max 12 1212121x x x x x x st x x z ()??? ??≥≤+≤++=0,242615 53.2max 22 121212 1x x x x x x st x x z 2-4已知线性规划问题，写出其对偶问题： 5 43212520202410max x x x x x z ++++=
3.322简单的线性规划问题r??? in?E???K m?????WE???Hinm H H???m H?m e卫斗 学习目标 能解决简单线性规划的实际应用问题 典型例题 例1:某研究所计划利用“神舟十号”宇宙飞船进行新产品搭载实验，计划搭载新产品A, B,要根据该产 品的研制成本、产品质量、搭载实验费用和预计产生收益来决定具体安排，通过调查，有关数据如表： 总预计收益达到最大，最大收益是多少? 变式：某工厂生产A, B两种产品，已知制造A产品1 kg需用9 t煤，4 kW?h电，3个劳动力（按工作日计算）；
制造B产品1 kg需用4 t煤，5 kW- h电，10个劳动力.又知制造A产品1 kg可获利7万元，制造B产品1 kg可获利12万元.现在此工厂只有煤360 t，电200 kW ? h,劳动力300个.在这种条件下怎样搭配可使工厂获利最多？规律总结类型二求最小值的实际应用问题 例2: 某家电生产厂家在一次惠民政策活动中,要将 1 00台洗衣机运往邻近的乡镇.现有4辆甲型货车和8 辆乙型货车 可供使用. 每辆甲型货车运输费用400 元,可装洗衣机20 台；每辆乙型货车运输费用300 元, 可装洗衣机10台.若 每辆车至多只运一次,求该厂所花的最少运输费用。 变式：某汽车公司有两家装配厂,生产甲、乙两种不同型的汽车,若乙型车； A厂每小时可完成1辆甲型车和2辆 B厂每小时可完成3辆甲型车和1辆乙型车.今欲制造40辆甲型车和40辆 乙型车，问这两家工厂各工作几小时，才能使所用的总工作时数最少.
规律总结 类型三线性规划的整数解问题 例3：某厂有一批长为18米的条形钢板，可以割成1.8 米和1.5 米长的零件.它们的加工费分别为每个1 元和0.6 元.售价分别为20元和15元，总加工费要求不超过8元.问如何下料能获得最大利润． 规律总结： 三反馈训练 1某养鸡场有1万只鸡，用动物饲料和谷物饲料混合喂养?每天每只鸡平均吃混合饲料0.5 kg，其中动 物饲料不能少于谷物饲料的?动物饲料每千克0.9元，谷物饲料每千克0.28元，饲料公司每周仅保证供 应谷物饲料50 000 kg，问饲料怎样混合才使成本最低. 2、某厂生产甲、乙两种产品，产量分别为45个、50个，所用原料为A, B两种规格的金属板，每张面积 分别为2 m2, 3 m2,用A种金属板可生产甲产品3个，乙产品5个，用B种金属板可生产甲、乙产品各 6 个，则A, B 两种金属板各取多少张时，能完成计划并能使总用料面积最省？
《运筹学》线性规划部分练习题 一、思考题 1． 什么是线性规划模型，在模型中各系数的经济意义是什么？ 2． 线性规划问题的一般形式有何特征？ 3． 建立一个实际问题的数学模型一般要几步？ 4． 两个变量的线性规划问题的图解法的一般步骤是什么？ 5． 求解线性规划问题时可能出现几种结果，那种结果反映建模时有错误？ 6． 什么是线性规划的标准型，如何把一个非标准形式的线性规划问题转化成标准形式。 7． 试述线性规划问题的可行解、基础解、基础可行解、最优解、最优基础解的概念及它们之间的相互关系。 8． 试述单纯形法的计算步骤，如何在单纯形表上判别问题具有唯一最优解、有无穷多个最优解、无界解或无可行解。 9． 在什么样的情况下采用人工变量法，人工变量法包括哪两种解法？ 10．大M 法中，M 的作用是什么？对最小化问题，在目标函数中人工变量的系数取什么？最大化问题呢？ 11．什么是单纯形法的两阶段法？两阶段法的第一段是为了解决什么问题？在怎样的情况下，继续第二阶段？ 二、判断下列说法是否正确。 1． 线性规划问题的最优解一定在可行域的顶点达到。 2． 线性规划的可行解集是凸集。 3． 如果一个线性规划问题有两个不同的最优解，则它有无穷多个最优解。 4． 线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大。 5． 线性规划问题的每一个基本解对应可行域的一个顶点。 6． 如果一个线性规划问题有可行解，那么它必有最优解。 7． 用单纯形法求解标准形式（求最小值）的线性规划问题时，与0 >j σ对应的变量都可以被选作换入变量。 8． 单纯形法计算中，如不按最小非负比值原则选出换出变量，则在下一个解中至少有一个基变量的值是负的。 9． 单纯形法计算中，选取最大正检验数k σ对应的变量k x 作为换入变量，可使目 标函数值得到最快的减少。 10． 一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。 三、建立下面问题的数学模型 1． 某公司计划在三年的计划期内，有四个建设项目可以投资：项目Ⅰ从第一年到 第三年年初都可以投资。预计每年年初投资，年末可收回本利120% ，每年又可以重新将所获本利纳入投资计划；项目Ⅱ需要在第一年初投资，经过两年可收回本利150% ，又可以重新将所获本利纳入投资计划，但用于该项目的最大投资额不得超过20万元；项目Ⅲ需要在第二年年初投资，经过两年可收回本利160% ，但用于该项目的最大投资额不得超过15万元；项目Ⅳ需要在第三年年初投资，年末可收回本利140% ，但用于该项目的最大投资额不得超过10万元。在这个计划期内，该公司第一年可供投资的资金有30万元。问怎样的投资方案，才能使该公司在这个计划期获得最大利润？ 2．某饲养场饲养动物，设每头动物每天至少需要700克蛋白质、30克矿物质、 100克维生素。现有五种饲料可供选用，各种饲料每公斤营养成分含量及单 价如下表2—1所示：
3.3.2简单的线性规划问题(第四课时) 一、设计问题,创设情境 练习1：(1)作出不等式组表示的平面区域(如图阴影部分),即可行域. 将z1=x+y变形为y=-x+z1,这是斜率为-1、随z1变化的一簇平行直线. z1是直线在y轴上的截距.当然直线要与可行域相交,即在满足约束条件时目标函数z1=x+y取得最值. 由图可见,当直线z1=x+y经过可行域上的点B时,截距z1最小. 得B点的坐标为x=,y=. 所以z1的最小值为. 同理,当直线z1=x+y与可行域的边界x+y=6重合时,z1最大为6. (2)同理将z2=3x+y化为y=-3x+z2,这是斜率为-3的一簇平行直线.如图所示,当它过可行域上的点A(0,6)时,z2最小为6. (3)同理将z3=x+4y化为y=-x+,它是斜率为-的一簇直线.如图所示,当直线经过可行域上的点C时,最大,即z3最大. 解方程组 得点C的坐标为x=,y=. 所以z3的最小值为. 问题1：是目标函数对应的直线的斜率与可行域中边界对应的直线的斜率的大小关系不同导致的. 练习2：解：z=ax+y可化为y=-ax+z, 因为z=ax+y在可行域中的点B处取得最小值,
所以,直线z=ax+y与可行域只有一个公共点B或与边界AB重合,或与边界BC重合. 所以-2≤-a≤-. 所以实数a的取值范围是. 练习3：学生探究一：能够把可行域中的所有“整点”都求出来.求这些最优解时,可根据可行域对x的限制条件,先令x去整数,然后代入到可行域,求出y的范围,并进一步求出y的整数值. 学生探究二：因为x,y∈N,则必有x+y∈N.又因为当x=,y=时,z1的最小值为,且直线z1=x+y应该向上方(或右方,或右上方)移动,所以相对应的z1的值大于. 所以令z1=x+y=5,即y=-x+5,代入得 即1≤x≤3,所以当或时,z1取得最小值5. 问题2：结合等量关系,将“二元”问题转化为“一元”问题求解.当可行域范围较小,包含的整点个数很少时,方法一比较简洁;反之,方法二较为简洁. 二、使用规律,解决问题 【例题】解：设需截第一种钢板x张,第二种钢板y张,则 用图形表示以上限制条件,得到如图所示的平面区域(阴影部分). 由题意,得目标函数为z=x+y. 可行域如图所示. 把z=x+y变形为y=-x+z,得到斜率为-1、在y轴上截距为z的一族平行直线. 由图能够看出,当直线z=x+y经过可行域上的点M时,截距z最小. 解方程组 得点M.而此问题中的x,y必须是整数,所以M不是最优解.经过可行域内整点且使截距z最小的直线是
课题：_简单的线性规划教案（二） 教学任务 教学目标知识与技能目 标 巩固二元一次不等式和二元一次不等式组所表示的 平面区域,能用此来求目标函数的最值． 过程与方法目 标 围绕着集合、化归、数形结合的数学思想方法 情感,态度与价 值观目标 在探究活动中,培养学生独立的分析、正确的科 学观 重点理解二元一次不等式表示平面区域是教学重点． 难点如何扰实际问题转化为线性规划问题,并给出解答是教学难点 教学流程说明 活动流程图活动内容和目的 活动1问题引入－最值探究巩固二元一次不等式和二元一次不等式组所表示的平面区域,能用此来求目标函数的最值 活动2 讲授新课－深入探究集合、化归、数形结合的数学思想方法 活动3应用提高－实践体会使学生会利用二元一次不等式表示平面区域能用此来求目标函数的最值 活动4归纳小结－感知新知让学生在合作交流的过程总结知识和方法 活动5巩固提高－作业巩固教学、个体发展、全面提高 教学过程设计 问题与情境设计意图 活动1问题引入：先讨论下面的问题设 ,式中变量x、y满足下列条件 我们先画出不等式组①表示的平 面区域,如图中内部且包括 边界．点（0,0）不在这个三角形区 域内,当 时, ,点（0,0）在直线 上． 作一组和平等的直线 ① 求z的最大值和最小值． 可知,当l在的右上方时,直 线l上的点满足． 即 ,而且l往右平移时,t 随之增大,在经过不等式组①表示 的三角形区域内的点且平行于l的 直线中,以经过点A（5,2）的直线 l,所对应的t最大,以经过点 的直线 ,所对应的t最小,所以 活动2深入探究→交流归纳 一般地,求线性目标函数在线性约 束条件下的最大值或最小值的问 题,统称为线性规划问题,满足线性 约束条件的解叫做可行解, 由所有可行解组成的集合叫做可行 域,在上述问题中,可行域就是阴影 部分表示的三角形区域,其中可行 解（5,2）和（1,1）分别使目标函 数取得最大值和最小值,它们都叫 做这个问题的最优解． 活动3实践提高→资源展示 资源1：解下列线性规划问题：求 的最大值和最小值,使式中 的x、y满足约束条件
实验报告 课程名称：运筹学导论 实验名称：线性规划问题实例分析专业名称：信息管理与信息系统 指导教师：刘珊 团队成员：邓欣(20112111 蒋青青(20114298 吴婷婷(20112124 邱子群(20112102 熊游(20112110 余文媛(20112125 日期：2013-10-25 成绩：___________
1．案例描述 南部联盟农场是由以色列三个农场组成的联合组织。该组织做出了一个关于农场农作物的种植计划，如下： 每一个农场的农业产出受限于两个量，即可使用的灌溉土地量和用于灌溉的水量。数据见下表： 适合本地区种植的农作物包括糖用甜菜、棉花和高粱。这三种作物的差异在于它们每亩的期望净收益和水的消耗量不同。另外农业部门已经制定了南部联盟农场作物总亩数的最大配额，见下表： 作物的任何组合可以在任何农场种植，技术部门的任务是找出一个种植方案使南部联盟农场的净收益最大化。 2.建立模型 决策变量为Xi(i=1,2,……,9,表示每个农场每种作物的种植量。 MAX Z=1000(X1+X2+X3+750(X4+X5+X6+250(X7+X8+X9 约束条件： （1）每一个农场使用的土地 X1+X4+X7≤400
X2+X5+X8≤600 X3+X6+X9≤300 (2每一个农场的水量分布 3X1+2X4+X7≤600 3X2+2X5+X8≤800 3X3+2X6+X9≤375 (3每一种作物的总种植量 X1+X2+X3≤600 X4+X5+X6≤500 X7+X8+X9≤325 非负约束Xi≥0 , i=1,2, (9) 3.计算机求解过程 步骤1.生成表格 步骤2.输入数据
3.3.2 简单线性规划问题第二十九课时 教学目标 1.掌握线性规划的意义以及约束条件、目标函数、可行解、可行域、最优解等基本概念; 2.运用线性规划问题的图解法，并能应用它解决一些简单的实际问题. 教学重点 重点是二元一次不等式（组）表示平面的区域. 教学难点 难点是把实际问题转化为线性规划问题，并给出解答.解决难点的关键是根据实际问题中的已知条件，找出约束条件和目标函数，利用图解法求得最优解. 课时安排 3课时 教学过程 导入新课 二元一次不等式a x+b y+c ＞0和a x+b y+c ＜0表示什么图形 （ 答：表示直线a x+b y+c =0某一侧所有点组成的平面区域. 规律： ax+by+c ＞0（a ＞0）表示直线 ax+by+c=0的右侧区域， ax+by+c ＜0（a ＞0）表示直线ax+by+c=0的左侧区域 记忆口诀：a 正大＞右，a 负小＜左。 a 为负时可化为正。 推进新课 ［合作探究］ 在现实生产、生活中，经常会遇到资源利用、人力调配、生产安排等问题. 例如，某工厂用A 、B 两种配件生产甲、乙两种产品，每生产一件甲产品使用4个A 产品耗时1小时，每生产一件乙产品使用4个B 产品耗时2小时，该厂每天最多可从配件厂获得16个A 配件和12个B 配件，按每天工作8小时计算，该厂所有可能的日生产安排是什么 解：设甲、乙两种产品分别生产x 、y 件，由已知条件可得二元一次不等式组： ?????????≥≥≤≤≤+. 0,0,124,164,82y x y x y x z=2x+3y 如何将上述不等式组表示成平面上的区域 】 ［教师精讲］见教材 有关概念 1、线性约束条件：不等式组是一组对变量x 、y 的约束条件。 2、线性目标函数.t=2x+y 3、线性规划问题：求线性目标函数在线性约束条件下的最大值或最小值的问题， 4、可行解：满足线性约束条件的解（x,y) 5、可行域：由所有可行解组成的集合 6、最优解： ［知识拓展］再看下面的问题： 若设t=2x+y ，式中变量x 、y 满足下列条件?? ???≥≤+-≤-.1,2553,34x y x y x 求t 的最 大值和最小值. — 解：做可行域ABC . 作直线l 0：2x+y=0上.平行移动直线l 0经过点B （5，2）的直线l 2所对应的t 最大，以经过点A （1，1）的直线l 1所对应的t 最小.所以t m a x =2×5+2=12, t min =2×1+3=3. 课堂小结 用图解法解决简单的线性规划问题的基本步骤： 1.要根据线性约束条件画出可行域
第二章 线性规划 主要内容：1、线性规划问题及数学模型 2、线性规划问题的解及其性质 3、图解法 4、单纯形法 5、大M 法和两阶段法 重点与难点：线性规划数学模型的建立：一般形成转化为标准型的方法：单纯形法的求解步骤。 要 求：理解本章内容，掌握本章重点与难点问题；深刻理解线性规划问题的基本概念、基本性质，熟练掌握 其求解技巧；培养解决实际问题的能力。 §1 线性规划的数学模型及解的性质 一、数学模型（一般形式） 例 1 已知某市有三种不同体系的建筑应予修建，其耗用资源数量及可用的资源限量如下表，问不同体系的面积应各建多少，才能使提供的住宅面积总数达到最大？ 解：设三种体系的建筑面积依次为1x ,2x ,3x 万平方米， 则目标函数为 321max x x x z ++= 约束条件为 ?? ?? ???????=≥≤++≤≤++≤++≤++3,2,10 4005.335.41470021015000 180190110200025301211000 122137105 3211321321321j x x x x x x x x x x x x x x j 例2 某工厂要安排生产甲、乙两种产品。已知：
问：如何安排两种产品的生产数量，才能使总产值最高？ 解：设 21,x x 分别为甲、乙两种产品的生产量： 则目标函数为 21127m ax x x z += 约束条件为??? ??? ?=≥≤+≤+≤+2,1,03001032005436049112121j x x x x x x x j 从以上两例可以看出，它们都属于一类优化问题。它们的共同特征： ①每一个问题都有一组决策变量（n x x x 21,）表示某一方案；这组决策变量的值就代表一个具体方案。一般这 些变量的取值是非负的。 ②存在一定的约束条件，这些约束条件可以用一组线性等式或不等式来表示。 ③都有一个要求达到的目标，它可用决策变量的线性函数（称为目标函数）来表示；按问题的不同，要求目标函数实现最大化或最小化。 满足以上三个条件的数学模型称为线性规划的数学模型。其一般形式为： 目标函数 n n x c x c x c z +++= 2211m ax (m in) 约束条件 ()()()????? ????=≥=≥≤+++=≥≤+++=≥≤+++n j x b x a x a x a b x a x a x a b x a x a x a j m n mn m m n n n n ,,2,1,0,,,22112222212111212111 可行解：满足约束条件的一组决策变量，称为可行解。 最优解：使目标函数取得最大（小）值的可行解，称为最优解。 最优值：目标函数的最大（小）值，称为最优值。 二、标准型 （一）问题的标准形式： n n x c x c x c z +++= 2211ma x ????? ?? ??=≥=+++=+++=+++n j x b x a x a x a b x a x a x a b x a x a x a j m n mn m m n n n n ,,2,1,022112222212111212111
习题 2-1 判断下列说法是否正确： （1） 任何线性规划问题存在并具有惟一的对偶问题； （2） 对偶问题的对偶问题一定是原问题； （3） 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之， 当对偶问题无可行解时，其原问题具有无界解； （4） 若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优 解； （5） 若线性规划问题中的b i ，c j 值同时发生变化，反映到最终单纯形表中，不会出 现原问题与对偶问题均为非可行解的情况； （6） 应用对偶单纯形法计算时，若单纯形表中某一基变量x i <0，又x i 所在行的元素全 部大于或等于零，则可以判断其对偶问题具有无界解。 （7） 若某种资源的影子价格等于k ，在其他条件不变的情况下，当该种资源增加 5个单位时，相应的目标函数值将增大5k ； （8） 已知y i 为线性规划的对偶问题的最优解，若y i >0，说明在最优生产计划中第 i 种资源已经完全耗尽；若y i =0，说明在最优生产计划中的第i 种资源一定有剩余。 2-2将下述线性规划问题化成标准形式。 ??? ?? ? ?≥≥-++-≤+-+-=-+-+-+-=无约束43214321432143214321,0,,232142224.5243max )1(x x x x x x x x x x x x x x x x st x x x x z ()??? ??≥≤≤-+-=++-+-=无约束 321 3213213 21,0,06 24 .322min 2x x x x x x x x x st x x x z 解：(1)令''' 444 x x x =-，增加松弛变量5x ，剩余变量6x ，则该问题的标准形式如下所示： ''' 12344''' 12344''' 123445''' 123446'''1234456max 342554222214..232 ,,,,,,0 z x x x x x x x x x x x x x x x x s t x x x x x x x x x x x x x =-+-+-?-+-+-=?+-+-+=??-++-+-=??≥? (2)令' z z =-，'11x x =-，''' 333x x x =-，增加松弛变量4x ，则该问题的标准 形式如下所示：
第二章 线性规划的对偶理论与灵敏度分析习题 1. 写出下列线性规划问题的对偶问题。 (1)????? ? ?≥=++≤++≥++++=无约束 3213213213213 21,0,5343 32243422min x x x x x x x x x x x x x x x z (2) ????? ? ?≤≥≤++≥-+-=++++=0 ,0,8374355 22365max 3213213213213 21x x x x x x x x x x x x x x x z 无约束 (3)?? ??? ??? ???==≥=====∑∑∑∑====) ,,1;,,1(0) ,,1(),,1(min 1 111n j m i x n j b x m i a x x c z ij m i j ij n j i ij m i ij n j ij (4)???????????=≥++==<=<=∑∑∑===),,,,1(0),,2,1() ,,1(min 1 211111n n j x m m m i b x a m m i b x a x c z j n j i j ij n j i j ij n j j j 无约束 2. 判断下列说法是否正确，为什么? (1)如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解； (2)如果线性规划的对偶问题无可行解，则原问题也一定无可行解； ( 3)在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或极小，原问题可行解的目标函数值一定不超过其对偶问题可行解的目标函数值； (4)任何线性规划问题具有唯一的对偶问题。 3. 已知某求极大化线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形表如下表所示，求表中各括弧内未知数的值。
第一章线性规划 习题1.1（生产计划问题）某企业利用A、B、C三种资源，在计划期内生产甲、乙两种产品，已知生产单位产品资源的消耗、单位产品利润等数据如下表，问如何安排生产计划使企业利润最大？ 解：设x1、x2分别代表甲、乙两种产品的生产数量（件），z表示公司总利润。依题意，问题可转换成求变量x1、x2的值，使总利润最大，即 ma x z=50x1+100x2 且称z=50x1+100x2为目标函数。 同时满足甲、乙两种产品所消耗的A、B、C三种资源的数量不能超过它们的限量，即可分别表示为 x1 + x2≤300 2x1 + x2≤400 x2≤250 且称上述三式为约束条件。此外，一般实际问题都要满足非负条件，即x1≥0、x2≥0。 这样有 ma x z=50x1+100x2 x1 + x2≤300 2x1 + x2≤400 x2≤250 x1、x2≥0
习题1.2 靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m 3，在两个工厂之间有一条流量为200万m 3的支流。两化工厂每天排放某种有害物质的工业污水分别为2万m 3和1.4万m 3。从第一化工厂排出的工业污水流到第二化工厂以前，有20%可以自然净化。环保要求河流中工业污水含量不能大于0.2%。两化工厂处理工业污水的成本分别为1000元/万m 3和800元/万m 3。现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂处理工业污水的总费用最小。 解：设x 1、x 2分别代表工厂1和工厂2处理污水的数量(万m 3)。则问题的目标可描述为 min z =1000x 1+800x 2 约束条件有 第一段河流（工厂1——工厂2之间）环保要求 (2－x 1)/500 ≤0.2% 第二段河流（工厂2以下河段）环保要求 [0.8(2－x 1) +(1.4－x 2)]/700≤0.2% 此外有 x 1≤2； x 2≤1.4 化简得到 min z =1000x 1+800x 2 x 1 ≥1 0.8x 1 + x 2 ≥1.6 x 1 ≤2 x 2≤1.4 x 1、x 2≥0 习题1.3 ma x z =50x 1+100x 2 x 1 + x 2≤300 2x 1 + x 2≤400 x 2≤250 图1—1 x 2
3．3.2 简单的线性规划问题(二) 课时目标 1．准确利用线性规划知识求解目标函数的最值． 2．掌握线性规划实际问题中的两种常见类型． 1．用图解法解线性规划问题的步骤： (1)分析并将已知数据列出表格； (2)确定线性约束条件； (3)确定线性目标函数； (4)画出可行域； (5)利用线性目标函数(直线)求出最优解； 根据实际问题的需要，适当调整最优解(如整数解等)． 2．在线性规划的实际问题中，主要掌握两种类型：一是给定一定数量的人力、物力资源，问怎样运用这些资源能使完成的任务量最大，收到的效益最大；二是给定一项任务，问怎样统筹安排，能使完成的这项任务耗费的人力、物力资源最小． 一、选择题 1．某厂生产甲产品每千克需用原料A 和原料B 分别为a 1、b 1千克，生产乙产品每千克需用原料A 和原料B 分别为a 2、b 2千克，甲、乙产品每千克可获利润分别为d 1、d 2元．月初一次性购进本月用的原料A 、B 各c 1、c 2千克，要计划本月生产甲产品和乙产品各多少千克才能使月利润总额达到最大．在这个问题中，设全月生产甲、乙两种产品分别为x 千克、y 千克，月利润总额为z 元，那么，用于求使总利润z ＝d 1x ＋d 2y 最大的数学模型中，约束条件为( ) A.????? a 1x ＋a 2y ≥c 1， b 1 x ＋b 2 y ≥c 2 ，x ≥0，y ≥0 B.????? a 1x ＋b 1y ≤c 1， a 2 x ＋b 2 y ≤c 2 ， x ≥0， y ≥0 C.????? a 1x ＋a 2y ≤c 1， b 1 x ＋b 2 y ≤c 2 ，x ≥0，y ≥0 D.????? a 1x ＋a 2y ＝c 1， b 1 x ＋b 2 y ＝c 2 ， x ≥0， y ≥0 答案 C 解析 比较选项可知C 正确． 2. 如图所示的坐标平面的可行域内(阴影部分且包括边界)，若使目标函数z ＝ax ＋y (a >0)取得最大值的最优解有无穷多个，则a 的值为( ) A.14 B.35 C ．4 D.53
简单的线性规划（2） 一．课题：简单的线性规划（2） 二．教学目标：1.了解线性规划的意义及线性约束条件、线性目标函数、可行解、可行域、最优解 等概念； 2.能根据条件建立线性目标函数； 3.了解线性规划问题的图解法，并会用图解法求线性目标函数的最大值、最小值. 三．教学重、难点：线性规划问题的图解法；寻求线性规划问题的最优解. 四．教学过程： （一）复习练习： 1．画出下列不等式表示的平面区域： （1）()(233)0x y x y -+-<； （2）|341|5x y +-<． （二）新课讲解： 1．引例：设2z x y =+，式中变量,x y 满足条件4335251x y x y x -≤-?? +≤??≥? ，求z 的最大值和最小值. 问题：能否用不等式的知识来解决以上问题？（否） 那么，能不能用二元一次不等式表示的平面区域来求解呢？怎样求解？ 由题意，变量,x y 所满足的每个不等式都表示一个平面区域，不等式组则表示这些平面区域的公共区域。由图知，原点(0,0)不在公共区域内，当0,0x y ==时，20z x y =+=，即点(0,0)在直线 0l ：20x y +=上， 作一组平行于0l 的直线l ：2x y t +=，t R ∈， 可知：当l 在0l 的右上方时，直线l 上的点(,)x y 满足20x y +>，即0t >， 而且，直线l 往右平移时，t 随之增大。 由图象可知， 当直线l 经过点(5,2)A 时，对应的t 最大， 当直线l 经过点(1,1)B 时，对应的t 最小， 所以，max 25212z =?+=，min 2113z =?+=． 2．有关概念 在上述引例中，不等式组是一组对变量,x y 的约束条件，这组约束条件都是关于,x y 的一次不等式，所以又称为线性约束条件。2z x y =+是要求最大值或最小值所涉及的变量,x y 的解析式，叫目标函数。又由于2z x y =+是,x y 的一次解析式，所以又叫线性目标函数. 一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题。满足线性约束条件的解(,)x y 叫做可行解，由所有可行解组成的集合叫做可行域。在上述问题中，可行域就是阴影部分表示的三角形区域。其中可行解(5,2)和(1,1)分别使目标函数取得最大值和最小值，它们都叫做这个问题的最优解. O y x A C 430x y -+= 1x = 35250x y +-=
习题一1.1 用图解法求解下列线性规划问题，并指出各问题是具有唯一最优解、 无穷多最优解、无界解或无可行解。 (1) min z ＝6x1＋4x2(2) max z ＝4x1＋8x2 st. 2x1＋x2≥1 st. 2x1＋2x2≤10 3x1＋4x2≥1.5 －x1＋x2≥8 x1, x2≥0 x1, x2≥0 (3) max z ＝x1＋x2(4) max z ＝3x1－2x2 st. 8x1＋6x2≥24 st. x1＋x2≤1 4x1＋6x2≥－12 2x1＋2x2≥4 2x2≥4 x1, x2≥0 x1, x2≥0 (5) max z ＝3x1＋9x2(6) max z ＝3x1＋4x2 st. x1＋3x2≤22 st. －x1＋2x2≤8 －x1＋x2≤4 x1＋2x2≤12 x2≤6 2x1＋x2≤16 2x1－5x2≤0 x1, x2≥0 x1, x2≥0 1.2. 在下列线性规划问题中，找出所有基本解，指出哪些是基本可行解并分别代入目标函数，比较找出最优解。 (1) max z ＝3x1＋5x2(2) min z ＝4x1＋12x2＋18x3 st. x1＋x3＝4 st. x1＋3x3－x4＝3 2x2＋x4＝12 2x2＋2x3－x5＝5 3x1＋2x2＋x5＝18 x j≥0 （j＝1, (5) x j≥0 （j＝1, (5) 1.3. 分别用图解法和单纯形法求解下列线性规划问题，并对照指出单纯形法迭代的每一步相当于图解法可行域中的哪一个顶点。 (1) max z ＝10x1＋5x2 st. 3x1＋4x2≤9 5x1＋2x2≤8 x1, x2≥0 (2) max z ＝100x1＋200x2 st. x1＋x2≤500 x1≤200 2x1＋6x2≤1200 x1, x2≥0 1.4. 分别用大M法和两阶段法求解下列线性规划问题，并指出问题的解属于哪一类： ９
课题：简单的线性规划（3）主备人：审核： 【目标要求】1、了解线性规划的背景及定义，掌握线性约束条件、目标函数、可行域、可行解、最优解等基本概念； 2、重点掌握利用线性规划求最优解问题. 3、能利用线性规划的基础知识解决一些实际问题. 【课内探究】 一、含参数问题 例1、已知变量x,y满足约束条件 14 22 x y x y ≤+≤ ? ? -≤-≤ ? ,若目标函数z=ax+y（其中a>0）仅在 点（3，1）处取得最大值，则a的取值范围是________________________. 【变式探究】（09陕西）已知变量x,y满足约束条件 x+y1 1 22 x y x y ≥ ? ? -≥- ? ?-≤ ? ,目标函数z=ax+2y仅在 点（1，0）处取得最小值，则a的取值范围是（） A.(-1,2) B.(-4,2) C.(-4,0) D.(-2,4) 二、整数解问题 例2、预算用2000元购买单价为50元的桌子和20元的椅子，希望使桌、椅的总数尽可能的多，但椅子数不能少于桌子数，且不多于桌子数的1.5倍.问桌子、椅子各买多少才合适？ 【课堂小结】怎样寻找最优解？尤其是整数解的寻找方法
【当堂检测】 已知实数x,y满足 1 21 y y x x y m ≥ ? ? ≤- ? ?+≤ ? ,如果目标函数z=x-y的最小值为-1，则实数m等于（） A.7 B.5 C.4 D.3 【课后拓展】 1、已知平面区域D由以A（1，3）、B（5，2）、C（3，1）为顶点的三角形内部和外界组成.若在区域D内有无数多个点(x,y)可使目标函数z=x+my取得最小值，则m为（） A.-2 B.-1 C.1 D.4 2、某运输公司接受了向抗洪救灾地区每天送至少180t支援物资的任务.该公司有8辆载重6t的A型卡车与4辆载重为10t的B型卡车，有10名驾驶员，每辆卡车每天往返的次数为A型卡车4次，B型卡车3次；每辆卡车每天往返的成本费A型为320元，B型为504元.请为公司安排一下，应如何调配车辆，才能使公司所花费的成本费最低？若只安排A型或B型卡车，所花费的成本费分别是多少？
运筹学 线性规划基本性质
线形规划基本性质目录 线性规划（概论） 线性规划问题:生产计划问题 例1.1 生产计划问题（资源利用问题）例1.1生产计划问题分析 例1.1生产计划问题模型 例1.1生产计划问题表格描述 例1 .2 营养配餐问题 各种食物的营养成分表 各种食物的营养成分表（转置） 例1 .2 营养配餐问题求解 用于成功决策的实例 线形规划的一般模型:特点 线形规划的一般模型:数学模型线性规划问题隐含的假定 比例性假定 可加性假定 连续性假定 确定性假定 线形规划的图解法 线形规划解的可能结果 线形规划的标准形式1 线形规划的标准形式2 非标准型LP的标准化:目标函数 非标准型LP的标准化:约束函数1 非标准型LP的标准化:约束函数2 非标准型LP的标准化:决策变量 线形规划解的概念：可行解 线形规划解的概念：最优解 线形规划解的概念：基本解 线形规划解的概念：最优基本解 线形规划的应用模型 生产计划问题 生产计划问题：表格分析 生产计划问题：模型 产品配套问题 产品配套问题：工时分析 产品配套问题：配套分析 产品配套问题：模型 结束放映
线性规划（概论） 线形规划是研究解决有限资源最佳分配的运筹学方法，即如何对有限的资源做出最佳方式的调配和最有利的利用，以便最充分地发挥资源的效能去获得最佳经济效益。
线性规划问题:生产计划问题 1、如何合理使用有限的人力、物力和资 金，实现最好的经济效益。 2、如何合理使用有限的人力、物力和资 金，以达到最经济的方式，完成生产 计划的要求。
例1.1 生产计划问题（资源利用问题） 胜利家具厂生产桌子和椅子两种家具。桌子售价50元/张，椅子销售价格30元/把，生产桌子和椅子要求需要木工和油漆工两种工种。生产一张桌子需要木工4小时，油漆工2小时。生产一把椅子需要木工3小时，油漆工1小时。该厂每个月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？
第二章 线性规划 本章内容重点： 线性规划模型 解的主要概念 线性规划应用——建模 一. 线性规划模型 引例： （1）用一块边长为a 的正方形铁皮做一容器，应如何裁剪，使做成的容器的容积最大？ （2）某企业计划生产甲、乙两种产品。这两种产品都要分别在A 、B 、C 、D 四种不同设备上加工。按工艺资料规定，生产每件产品甲需占用设备分别为2、1、4、0小时，生产每件产品乙需占用设备分别为2、2、0、4小时。已知各设备计划期内用于生产这两种产品的能力分别为12、8、16、12小时，又已知每生产一件产品甲企业能获得2元利润，每生产一件产品乙企业能获得3元利润，问该企业应如何安排生产，使总的利润收入最大？ 讨论：（1）可用微积分的方法解决； （2）复杂一些 目标： 最大 2 132x x z +=
例2.1:某工厂拥有A 、B 、C 三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示： 问题：工厂应如何安排生产可获得最大的总利润？ 解：设变量xi 为第i 种（甲、乙）产品的生产件数（i ＝1，2）。根据题意，我们知道两种产品的生产受到设备能力（机时数）的限制。对设备A ，两种产品生产所占用的机时数不能超过65，于是我们可以得到不等式：3 x1 + 2 x2 ≤ 65； 对设备B ，两种产品生产所占用的机时数不能超过40，于是我们可以得到不等式：2 x1 + x2 ≤ 40； 对设备C ，两种产品生产所占用的机时数不能超过75，于是我们可以得到不等式：3x 2 ≤75 ；另外，产品数不可能为负，即 x 1 ,x 2 ≥0。同时，我们有一个追求目标，即获取最大利润。于是可写出目标函数z 为相应的生产计划可以获得的总利润：z =1500x 1+2500x 2 。综合上述讨论，在加工时间以及利润与产品产量成线性关系的假设下，把目标函数和约束条件放在一起，可以建立如下的线性规划模 ????? ????≥≤≤≤+≤+0 ,1241648212222121 2121x x x x x x x x
线性规划模型在实际生活中的应用 【摘要】线性规划在实际生活中扮演着很重要的角色，研究对象是计划管理工作中有关安排和估值的问题,其广泛应用于经济等领域，是实际生活中进行管理决策的最有效的方法之一。解决的主要问题是在给定条件下,按某一衡量指标来寻找安排的最优方案。本文通过对例题利用线性规划分析，如何合理的分配利用，最终找到最优解使企业利润最大，说明了线性规划在实际生活中的应用，而且对线性规划问题模型的建立，模型的解进行了分析，运用图解法和单纯形法解决问题。 【关键词】线性规划、建模、实际生活、图解法、单纯形法 前言：线性规划（Linear programming,简称LP）是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法。研究线性约束条件下线性目标函数的极值问题的数学理论和方法。英文缩写LP。它是运筹学的一个重要分支，广泛应用于军事作战、经济分析、经营管理和工程技术等方面。为合理地利用有限的人力、物力、财力等资源作出的最优决策，提供科学的依据。 在实际生活中，经常会遇到一定的人力、物力、财力等资源条件下，如何精打细算巧安排，用最少的资源取得最大的效益的问题，而这正是线性规划研究的基本内容，它在实际生活中有着非常广泛的应用．任何一个组织的管理者都必须对如何向不同的活动分配资源的问题做出决策，即如何有效地利用人力、物力完成更多的任务，或在预定的任务目标下如何耗用最少的人力、物力去实现目标。在许多情况下，大量不同的资源必须同时进行分配，需要这些资源的活动可以是不同的生产活动，营销活动，金融活动或者其他一些活动。随着计算技术的不断发展，使成千上万个约束条件和决策变量的线性规划问题能迅速地求解，更为线性规划在经济等各领域的广泛应用创造了极其有利的条件。线性规划已经成为现代化管理的一种重要的手段。本文运用常用的图解法和单纯形法解决利润最大化决
一、需要掌握的主要内容 1、单纯形法的计算过程 （1）确定初始基本可行解 （2）最优性检验； （3）基变换。 2、单纯形法的灵敏度分析 （1）最终单纯形表中，变量系数的灵敏度分析针对最优解不变时，判断其变化范围； （2）约束条件常数项b的灵敏度分析针对最优解不变时，判断其变化范围； （3）增加一个变量的灵敏度分析 首先，确定增加变量在初始单纯形表中的系数列P j ；然后，求出其对应在最终单纯形表 中的系数列P j ；最后求出σ j =C j -C B B-1P j 。 若σ j ≤0，则最优解不变；σ j ≥0，则继续进行基变换，直到求出最优解。 二、需要基本掌握的内容 1、解、基本解、可行解、基本可行解等基本概念； 2、利用单纯形法求解如何判断无可行解、无界解和无穷最优解等基本理论； 3、如何写出一个线性规划的对偶问题； 4、对偶单纯形法的基本思路和过程。 一、填空题 （1）线性规划模型中，松弛变量的经济意义是，它在目标函数中的系数是。 （2）设有线性规划问题：max z=CX AX≤b X≥0 有一可行基B，记相应基变量为X B ,非基变量为X N ，则可行解的定义为，基本可行 解的定义为，B为最优基的条件是。 （3）线性规划模型具有可行域，若其有最优解，必能在上获得。 二、选择题 1．线性规划一般模型中，自由变量可以用两个非负变量的（）代换。 A．和 B．差 C．积 D．商 2．满足线性规划问题全部约束条件的解称为（） A．最优解 B．基本解 C．可行解 D．多重解 3．当满足最优检验，且检验数为零的变量的个数大于基变量的个数时，可求得（） A．多重解 B．无解 C．无界解 D．退化解 4．原问题与对偶问题的（）相同。 A．最优解 B．最优目标值 C.解结构 D．解的分量个数 5.记线性规划原问题（p）max z=CX，对偶问题（D） min w=Yb AX≤b YA≥C