当前位置：文档之家 › MBA2 管理运筹学讲义：线性规划

MBA2 管理运筹学讲义：线性规划

  • 格式：pdf
  • 大小：8.44 MB
  • 文档页数：9

下载文档原格式

  / 9

合集下载

运筹学讲义_1线性规划

运筹学讲义_1线性规划

第一章 线性规划【教学内容】线性规划模型，图解法，可行区域的几何结构，基本可行解及线性规划的基本定理，单 纯形方法，单纯形表，两阶段法，关于单纯形方法的几点说明，对偶线性规划，对偶理论， 对偶单纯形法，求解线性规划问题的几个常用软件。

【教学要求】要求学生理解线性规划的标准形式，能熟练的将一般的线性规划问题化为标准形式；掌 握图解法，能用单纯形法求解线性规划问题；掌握灵敏度分析方法，能够建立线性规划模型 及用常用软件求解线性规划问题。

【教学重点】线性规划模型，图解法，单纯形方法，单纯形表，两阶段法，对偶线性规划，对偶单纯 形法，灵敏度分析。

【教学难点】基本可行解及线性规划的基本定理，单纯形方法，对偶线性规划，对偶理论，对偶单纯 形法。

第一节 线性规划模型线性规划(Linear Programming ， 简记为 LP )问题研究的是在一组线性约束条件下一个线 性函数最优问题。

§1．1 线性规划问题举例例 1.1.1 某工厂用 3 种原料 3 2 1 , , P P P 生产 3 种产品 3 2 1 , , Q Q Q 。

已知单位产品所需原 料数量如表 1.1.1 所示，试制订出利润最大的生产计划。

453 单位产品的利润（千元）20005 2 800 4 2 0 P 2 1500 0 3 2 P 1 原料可用量Q 3Q 2 Q 1 单位产品所需产品原料数量(kg)原料3P 3表 1.1.1分析 设产品 j Q 的产量为 j x 个单位， 3 , 2 , 1 = j ，它们受到一些条件的限制。

首先， 它们不能取负值，即必须有 3 , 2 , 1 , 0 = ³ j x j ；其次，根据题设，三种原料的消耗量分别不 能超过它们的可用量，即它们又必须满足：1223 123 231500 24800 3252000 x x x x x x x +£ ì ï+£ í ï ++£ î我们希望在以上约束条件下，求出 3 2 1 , , x x x ，使总利润 3 2 1 4 5 3 x x x z + + = 达到最大， 故求解该问题的数学模型为：123 12 23 123 max 354 231500 24800 .. 3252000 0,1,2,3j z x x x x x x x s t x x x x j =++ +£ ì ï +£ ï í++£ ï ï ³= î 类似这样的问题非常多。

管理运筹学第二章 线性规划的图解法

管理运筹学第二章 线性规划的图解法

B、约束条件不是等式的问题：
若约束条件为 ai1 x1+ai2 x2+ … +ain xn ≤ bi 可以引进一个新的变量si ，使它等于约束右 边与左边之差 si=bi–(ai1 x1 + ai2 x2 + … + ain xn ) 显然，si 也具有非负约束，即si≥0， 这时新的约束条件成为 ai1 x1+ai2 x2+ … +ain xn+si = bi
第二章 线性规划 的图解法
一、线性规划的概念 二、线性规划问题的提出 三、线性规划的数学模型 四、线性规划的图解法 五、线性规划解的情况 六、LP图解法的灵敏度分析
一、线性规划的概念
线性规划Linear Programming 简称LP，是一 种解决在线性约束条件下追求最大或最小的 线性目标函数的方法。 线性规划的目标和约束条件都可以表示成线 性的式子。
max z 3 x1 2 x2
2 x1 x2 ≤ 10 设备B台时占用 s.t. x1 x2 ≤ 8 x , x ≥ 0 产量非负 1 2
决策变量 （decision variable） 目标函数 （objective function） 约束条件 （subject to）

-ai1
x1-ai2 x2- … -ain xn = -bi 。
例1.3：将以下线性规划问题转化为标准形式 Min f = 3.6 x1 - 5.2 x2 + 1.8 x3 s. t. 2.3 x1 + 5.2 x2 - 6.1 x3 ≤15.7 4.1 x1 + 3.3 x3 ≥8.9 x1 + x2 + x3 = 38 x 1 , x 2 , x3 ≥ 0

管理运筹学课件第2章 线性规划

管理运筹学课件第2章 线性规划

x1 x2 ≤ 8
产量非负 x 1 , x 2 ≥ 0
决策变量
（decision variable）
总利润表三达要式素
目标函数 （objective function）
约束条件 生产能力,不 （subject to） 允许超过 当目标函数与约束条件均为决策变
量的线性函数，且变量取连续值时，
当xk的值由0增加到θ时，原来的基变 量xl取值首先变成零，选择其为出基变 量。称θ的表达式为最小比值原则。
如果所有aik ≤0, xk的值可以由0增加到 无穷，表示可行域是不封闭的，且目 标函数值随进基变量的增加可以无限 增加，此时不存在有限最优解。
下面对以上讨论进行总结.
2019/8/31
课件
15
称为线性规划LP；变量取整称为整
数线性规划ILP；变量取二进制为
0-1规划BLP。
2019/8/31
课件
5
2.1.2 线性规划的数学模型
【例2.1】（合理配料问题）由下表建立一个LP模型求解满足动物成长 需要又使成本最低的饲料配方。
饲料 营养甲(g/kg) 营养乙(g/kg) 营养丙(g/kg) 成本(g/kg)
x1+x2=8

x1
2019/8/31
课件
11
2.2.3 线性规划几何解的讨论
线性规划几何解存在四种情况：唯一最优解、无穷 多最优解、无界解、无可行解。 可行域为封闭有界区域时，可能存在唯一最优解， 无穷多最优解两种情况； 可行域为非封闭无界区域时，可能存在唯一最优解， 无穷多最优解，无界解三种情况； 可行域为空集时，没有可行解，原问题没有最优解。
1
0.5
0.1
0.08

管理运筹学_第二章_线性规划的图解法

管理运筹学_第二章_线性规划的图解法

A
1×250=250千克．
原料B 0 1 250千克
约束条件中没使用的资源或能力称之为松弛量。
用Si表示松弛量，对最优解 x1=50,x2=250来说：
约束条件
松弛变量的值
设备台时数
s1=0
原料A
s2=50
原料B
s3=0
8
线性规划标准型
加了松弛变量后例1的数学模型可写成：
目标函数：max z=50x1+100x2+0s1+0s2+0s3，
约束条件： x1+x2+s1=300,
2x1+x2+s2=400,
x2+s3=250, x1,x2,s1,s2,s3≥0
如何把模型化为 标准型？
三个特征：
一、约束条件为等式；
二、约束条件右端常数项非负；
三、所有变量非负。
称为线性规划的标准形式。
9
线性规划问题解的情况：
1．若有最优解，一定能在可行域的顶点取得。
a21x1+a22x2+…+a2nxn=b2, ………………………… am1x1+am2x2+…+am nxn=bm. x1, x2,…,xn≥0.
其中ci为第i个决策变量xi在目标函数中的系数， aij为第i个约束条件中第j个决策变量xj的系数， bj(≥0)为第j个约束条件中的常数项。
16
灵敏度分析
C 100
1设备台时获利500/10=50
元。 x1
O 100 D300 X1+X2=300
X1+X2=310
你知道对偶价格吗？
21
对偶价格的概念

管理运筹学第二章线性规划的图解法

管理运筹学第二章线性规划的图解法

02
图解法的基本原理
图解法的概念
图解法是一种通过图形来直观展示线性规划问题解的方法。它通过在坐标系中绘 制可行域和目标函数，帮助我们理解问题的结构和最优解的位置。
图解法适用于线性规划问题中变量和约束条件较少的情况，能够直观地展示出最 优解的几何意义。
图解法的步骤
确定决策变量和目标函数
明确问题的决策变量和目标函数，以便在图 形中表示。
目标函数是要求最小化或最大化的函数，通常表示为 $f(x) = c_1x_1 + c_2x_2 + ldots + c_nx_n$。
04
约束条件是限制决策变量取值的条件，通常表示为 $a_1x_1 + a_2x_2 + ldots + a_nx_n leq b$或 $a_1x_1 + a_2x_2 + ldots + a_nx_n = b$。
LINDO是一款开源的线性规划求解器，用 户可以免费使用。
软件工具的使用方法
Excel
用户需要先在Excel中设置好线性规划模型，然后使 用“数据”菜单中的“规划求解”功能进行求解。
Gurobi/CPLEX/LINDO
这些软件通常需要用户先在软件界面中输入线性规划 模型，然后通过点击“求解”按钮进行求解。
实例三：分配问题
总结词
分配问题是指如何根据一定的分配原则 或目标，将有限的资源分配给不同的需 求方，以最大化整体效益。
VS
详细描述
分配问题在实际生活中广泛存在，如物资 分配、任务分配等。通过图解法，可以将 分配问题转化为线性规划模型，并利用图 形直观地展示最优解的资源分配方案。在 分配问题中，通常需要考虑不同需求方的 重要性和优先级，以及资源的有限性等因 素，以实现整体效益的最大化。

线性规划讲义

线性规划讲义

线性规划讲义一、引言线性规划是一种数学优化方法，用于解决线性约束条件下的最优化问题。

它广泛应用于工程、经济学、运筹学等领域。

本讲义将介绍线性规划的基本概念、模型建立和求解方法。

二、线性规划的基本概念1. 线性规划的定义线性规划是在一组线性约束条件下，寻找目标函数的最大值或最小值的数学优化问题。

2. 基本术语- 决策变量：用来表示问题中需要决策的量，通常用x1, x2, ..., xn表示。

- 目标函数：表示需要最大化或最小化的量，通常用z表示。

- 线性约束条件：表示问题中的限制条件，通常以不等式或等式的形式给出。

- 可行解：满足所有线性约束条件的决策变量取值。

- 最优解：使目标函数达到最大值或最小值的可行解。

三、线性规划模型的建立1. 确定决策变量根据问题的特点，确定需要决策的变量及其表示方式。

2. 建立目标函数根据问题的要求，构建目标函数，它通常是决策变量的线性组合。

3. 确定约束条件根据问题的限制条件，建立线性约束条件，通常以不等式或等式的形式给出。

4. 求解最优解利用线性规划的求解方法，求解出使目标函数达到最大值或最小值的可行解。

四、线性规划的求解方法1. 图形法对于二维或三维问题，可以使用图形法来求解线性规划问题。

首先将约束条件绘制成图形，然后通过图形的分析找到最优解。

2. 单纯形法单纯形法是一种常用的求解线性规划问题的方法。

它通过迭代计算，不断改进可行解，直到找到最优解。

3. 整数规划当决策变量需要取整数值时，可以使用整数规划方法来求解线性规划问题。

整数规划通常比线性规划更复杂，需要使用特定的求解算法。

五、线性规划的应用案例1. 生产计划问题假设一家工厂有多种产品需要生产，每种产品有不同的生产成本和利润。

通过线性规划，可以确定每种产品的生产数量，使得总利润最大化。

2. 运输问题假设有多个供应地和多个需求地，每个供应地和需求地之间有不同的运输成本。

通过线性规划，可以确定各个供应地和需求地之间的运输量，使得总运输成本最小化。

运筹学 线性规划

运筹学线性规划运筹学是一门研究如何进行最优决策的学科。

它包括了多个数学分支，如线性规划、整数规划、非线性规划、动态规划等。

其中，线性规划在运筹学中占有重要地位。

线性规划是一种数学优化方法，用于解决一类特定结构的最优化问题。

它的基本思想是在给定的约束条件下，通过构建目标函数和决策变量之间的线性关系，寻找使目标函数达到最优值的决策变量取值。

线性规划的数学模型可以表示为以下形式：最大化（或最小化）目标函数：Z = c₁x₁ + c₂x₂ + ... +cₙxₙ所有的约束条件：a₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ ≤ b₁...aₙ₁x₁ + aₙ₂x₂ + ... + aₙₙxₙ ≤ bₙx₁ ≥ 0, x₂ ≥ 0, ... , xₙ ≥ 0其中，c₁、c₂、...、cₙ表示目标函数中的系数，x₁、x₂、...、xₙ为决策变量，a₁₁、a₁₂、...、aₙₙ为约束条件中的系数，b₁、b₂、...、bₙ为约束条件右侧的常数。

线性规划的解法有多种，其中最常用的是单纯形法。

单纯形法通过逐步进行基变量的选择和替换，不断改进目标函数值，从而找到最优解。

它的基本思想是通过基变量的变换，使目标函数值不断减小，直到达到最小值或者无法继续改进为止。

线性规划的应用十分广泛。

它可以用于生产计划、资源分配、物流管理、投资组合等多个领域。

例如，在生产计划中，线性规划可以帮助企业合理分配生产资源，降低成本，提高效益。

在物流管理中，线性规划可以优化货物的调度方案，减少运输成本。

在投资组合中，线性规划可以帮助投资者选择合适的投资组合，以获得最大的收益。

总之，运筹学中的线性规划是一种重要的决策优化方法。

通过构建数学模型，并应用单纯形法等求解方法，可以在给定的约束条件下寻找最优解，从而提高决策的效果。

随着计算机技术的发展，线性规划的应用领域和规模将会进一步扩大，为各行各业提供更好的决策支持。

《管理运筹学》02-1线性规划的数学模型及相关概念


03 线性规划的求解方法
单纯形法
1
单纯形法是一种求解线性规划问题的经典算法， 其基本思想是通过不断迭代来寻找最优解。
2
单纯形法的基本步骤包括：建立初始单纯形表格、 确定主元、进行基变换、更新单纯形表格和判断 是否达到最优解。
3
单纯形法在处理大规模线性规划问题时，由于其 迭代次数与问题规模呈指数关系，因此计算量较 大。
06 线性规划的案例分析
生产计划问题
总结词
生产计划问题是一个常见的线性规划应用场景，通过合理安排生产计划，企业可以优化资源利用，降低成本并提 高利润。
详细描述
生产计划问题通常涉及确定不同产品组合、生产数量、生产批次等，以满足市场需求、资源限制和利润目标。线 性规划模型可以帮助企业找到最优的生产计划，使得总成本最低或总利润最大。
最优性条件由单纯形法推导得出，是判断线性规划问题是否达到最优解的 重要依据。
解的稳定性
解的稳定性是指最优解在参数变化时保持相对稳定的能力。
在实际应用中，由于数据的不确定性或误差，参数可能会发生变化。因此，解的稳 定性对于线性规划问题的实际应用非常重要。
解的稳定性取决于目标函数和约束条件的性质，以及求解算法的鲁棒性。在某些情 况下，可以通过敏感性分析来评估解对参数变化的敏感性。
输标02入题
决策变量是问题中需要求解的未知数，通常表示为 $x_1, x_2, ldots, x_n$。
01
03
目标函数是需要最大或最小化的函数，通常表示为 $f(x) = c_1x_1 + c_2x_2 + ldots + c_nx_n$。
04
约束条件是问题中给定的限制条件，通常表示为 $a_1x_1 + a_2x_2 + ldots + a_nx_n leq b$ 或 $a_1x_1 + a_2x_2 + ldots + a_nx_n = b$。

管理运筹学 线性规划的图解法课件


线性规划的应用领域
生产计划
线性规划可以用于制定生产计划，优 化资源配置，提高生产效率。
物流优化
线性规划可以用于优化物流配送路线 、车辆调度等问题，降低运输成本。
金融投资
线性规划可以用于金融投资组合优化 ，实现风险和收益的平衡。
资源分配
线性规划可以用于资源分配问题，如 人员、资金、设备等资源的合理分配 ，提高资源利用效率。
束条件。
线性规划的目标是在满足一系列 限制条件下，使某一目标函数达
到最优值。
线性规划问题通常表示为求解一 组变量的最优值，使得这些变量 满足一系列线性等式或不等式约
束。
线性规划的数学模型
线性规划的数学模型由决策变量、目标函数和约束条 件三部分组成。
输标02入题
决策变量是问题中需要求解的未知数，通常表示为 $x_1, x_2, ldots, x_n$。
01
03
约束条件是限制决策变量取值的条件，通常表示为 $a_1x_1 + a_2x_2 + ldots + a_nx_n leq b$或 $a_1x_1 + a_2x_2 + ldots + a_nx_n = b$。
04
目标函数是问题要优化的函数，通常表示为$f(x) = c_1x_1 + c_2x_2 + ldots + c_nx_n$。
03
绿色发展与线性规 划的结合
将可持续发展理念融入线性规划 ，实现资源节约、环境友好的发 展目标。
THANKS
[ 感谢观看 ]
约束条件
生产计划问题通常受到资源限制、市场需求和生 产能力等约束条件的限制。
详细描述
生产计划问题通常涉及到如何分配有限的资源， 以最大化某种目标函数（如利润）。通过图解法 ，我们可以将约束条件和目标函数在二维平面上 表示出来，从而找到最优解。

管理运筹学讲义：线性规划


1
相关数据如表所示： • •
10
11
12
问如何安排甲、乙两产品的产量，使利润为最大。 第一节 线性规划一般模型 (1)决策变量。要决策的问题是甲、乙两种产品的产量，因此有两个决策变量：设x1为甲 产品产量，x2为乙产品产量。 (2)约束条件。生产这两种产品受到现有生产能力的制约，用量不能突破。 生产单位甲产品的零部件需耗用A车间的生产能力1工时， 生产单位乙产品不需耗用A车间的生产能力， A车间的能力总量为8工时，则A车间能力约束条件表述为 x1 ≤8 同理，B和C车间能力约束条件为 2x2 ≤12 3x1 +4 x2 ≤36 第一节 线性规划一般模型 (3)目标函数。目标是利润最大化，用Z表示利润，则 maxZ= 3x1 +5 x2 (4)非负约束。甲乙产品的产量不应是负数，否则没有实际意义，这个要求表述为 x1 ≥0， x2 ≥0 第一节 线性规划一般模型 某名牌饮料在国内有三个生产厂，分布在城市A1、A2、A3,其一级承销商有4个，分布在 城市B1、B2、B3、B4，已知各厂的产量、各承销商的销售量及从Ai到Bj的每吨饮料运费为 Cij，为发挥集团优势，公司要统一筹划运销问题，求运费最小的调运方案。 第一节 线性规划一般模型 (1)决策变量。设从Ai到Bj的运输量为xij， (2)目标函数。运费最小的目标函数为 minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34 (3)约束条件。产量之和等于销量之和,故要满足： 供应平衡条件 第一节 线性规划一般模型 • 用一组非负决策变量表示一个决策问题， • 存在一定的等式或不等式的线性约束条件， • 有一个希望达到的目标，可表示成决策变量的线性函数。可能是最大化，也可能是最小 化。 • 线性规划一般模型的代数式 为： 第二节 线性规划的图解法 • 图解法即是用图示的方法来求解线性规划问题。 • 一个二维的线性规划问题，可以在平面图上求解，三维的线性规划则要在立体图上求解， 这就比较麻烦，而维数再高以后就不能图示了。 第二节 线性规划的图解法
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

• 约束条件
任何管理决策问题都是限定在一定的条件下求解 把各种限制条件表示为一组等式或不等式，称之为约束条件 约束条件是决策方案可行的保障 LP的约束条件，都是决策变量的线性函数
• 目标函数
衡量决策方案优劣的准则，如时间最省、利润最大、成本最低 目标函数是决策变量的线性函数 有的目标要实现极大，有的则要求极小
24
上海财经大学国际工商管理学院 上海财经大学国际工商管理学院
4
SHUFE
第一节 线性规划的标准型
≤8 2x2 ≤12 3x1 +4 x2 ≤36 x1 ≥0, x2 ≥0 x1
x1 ≥0， x2 ≥0
• 例2. 运输问题 某名牌饮料在国内有三个生产厂，分布在城市A1、A2、 A3, 其一级承销商有 4 个，分布在城市 B1 、 B2 、 B3 、 B4，已知各厂的产量、各承销商的销售量及从Ai到Bj 的每吨饮料运费为 Cij ，为发挥集团优势，公司要统 一筹划运销问题，求运费最小的调运方案。
二、非标准型向标准型转化
• 目标函数极小化问题
minZ=CTX，只需将等式两端乘以 -1 即变为极大化问题。
• 右端常数项非正
两端同乘以 -1
• 为了求解方便，特规定一种线性规划的标准形式， 非标准型可以转化为标准型。标准形式为：
目标函数极大化 约束条件为等式 右端常数项bi≥0 决策变量非负
12
x1
17
上海财经大学国际工商管理学院 上海财经大学国际工商管理学院
18
3
SHUFE
第二节 线性规划的图解法
SHUFE
第二节 线性规划的图解法
二 、解的可能性 • 唯一最优解：只有一个最优点。 • 多重最优解：无穷多个最优解。若在两个顶点同时 得到最优解，则它们连线上的每一点都是最优解。
例1的数学模型变为 maxZ= 3x1 +4 x2 x1 ≤8 2x2 ≤12 S.t. 3x1 +4 x2 ≤36 x1 ≥0, x2 ≥0
x1 ≥0， x2 ≥0
(3)约束条件。 约束条件 产量之和等于销量之和,故要满足：
供应平衡条件
x11+x12+x13+x14=5 x21+x22+x23+x24=2 x31+x32+x33+x34 =3 x11+x21+x31=2 x12+x22+x32=3 x13+x23+x33=1 x14+x24+x34=4
第三章 线性规划的对偶理论 第四章 线性规划灵敏性分析
2
上海财经大学国际工商管理学院 上海财经大学国际工商管理学院
SHUFE
第一章 线性规划的数学模型
SHUFE
第一章 线性规划的数学模型
• 线性规划
Linear Programming, LP 规划论中的静态规划 解决有限资源的最佳分配问题
2. 最优解的确定
• 目标函数 Z= 3x1 +5 x2 代表以 Z 为参数的一族平行线。
x2
9
x
C
x1 =8 2x2 =12
D
6 3
C
Z=30
x1 =8 2x2 =12
B
8A
B Z=42
8A
Z=15
4 12 3x1 +4 x2 =36
0
x1
0
4
3x1 +4 x2 =36 上海财经大学国际工商管理学院 上海财经大学国际工商管理学院
15
上海财经大学国际工商管理学院 上海财经大学国际工商管理学院
16
上海财经大学国际工商管理学院 上海财经大学国际工商管理学院
SHUFE
第二节 线性规划的图解法
SHUFE
第二节 线性规划的图解法
1. 可行域的确定
• 满足所有约束条件的解的集合，称之为可行域。即所有约束 条件共同围城的区域。
2 • 例1的数学模型为 9 maxZ= 3x1 +5 x2 x1 ≤8 D 6 2x2 ≤12 S.t. 3x1 +4 x2 ≤36 3 x1 ≥0, x2 ≥0
• 建立模型 (1)决策变量。 决策变量 要决策的问题是甲、乙两种产品的产量，因 (2)约束条件。 约束条件 生产这两种产品受到现有生产能力的制约，
用量不能突破。
生产单位甲产品的零部件需耗用A车间的生产能力1工时， 生产单位乙产品不需耗用A车间的生产能力， A车间的能力总量为8工时，则A车间能力约束条件表述为 x1 ≤8 同理，B和C车间能力约束条件为 2x2 ≤12 3x1 +4 x2 ≤36
-1
3 2 1
-2x1 + x2 =2
Z=12 Z=6 x1 -3 x2 =3 x1
1 -1
20
2
3
4
8
12
3x1 +4 x2 =36 上海财经大学国际工商管理学院 上海财经大学国际工商管理学院
上海财经大学国际工商管理学院 上海财经大学国际工商管理学院
SHUFE
第二节 线性规划的图解法
SHUFE
第二章 线性规划单纯形法
23
• 约束条件为不等式
当约束方程为“≤”时，左端加入一个非负的松弛变量，就变成等式 当约束条件为“≥”时，左端减去一个非负的剩余变量(也称松弛变量)
• 决策变量xk没有非负性要求
令xk=xk′-x k〃， xk′，x k〃 ≥0 ，用xk′、x k〃 取代模型中xk
上海财经大学国际工商管理学院 上海财经大学国际工商管理学院
SHUFE
第一讲 线性规划
第一章 线性规划的数学模型
第一节 线性规划一般模型 第二节 线性规划的图解法
管理运筹学
魏 航
第二章 线性规划的单纯形法
第一节 线性规划的标准型 第二节 线性规划解的概念 第三节 线性规划单纯形法
单 位：上海财经大学国际工商管理学院企业管理系 位： 物流与供应链管理研究中心 E-mail：odeywei@ 电 话：65903541(O)
• 若有5种不同浓度的硫酸可选(30%,45%,73%,85%,92%) 会出现什么情况？
取这5种硫酸分别为 x1、x2、x3、x4、x5 数学模型则为：
• 若5种硫酸价格分别为400, 700, 1400, 1900, 2500元 /t，则有：
MinZ = 400x1 + 700x2 + 1400x3 + 1900x4 + 2500x5 ⎧x1 + x2 + x3 + x4 + x5 = 100 ⎪ s.t.⎨0.3x1 + 0.45x2 + 0.73x3 + 0.85x4 + 0.92x5 = 0.8 ×100 ⎪x ≥ 0, j = 1,2,",5 ⎩ j
销地 产地 A1 A2 A3 销量 B1 6 7 3 2 B2 3 5 2 3 B3 2 8 9 1
10
• 综上所述，该问题的数学模型表示为
maxZ= 3x1 +5 x2 x1 ≤8 2x2 ≤12 S.t. 3x1 +4 x2 ≤36 x1 ≥0, x2 ≥0
9
B4 5 4 7 4
产量 5 2 3
2 1
x1 -3 x2 =3
1 -1
21
2
3
x1
上海财经大学国际工商管理学院 上海财经大学国际工商管理学院
22
上海财经大学国际工商管理学院 上海财经大学国际工商管理学院
SHUFE
第一节 线性规划的标准型
SHUFE
第一节 线性规划的标准型
一 、标准型 • 线性规划问题的数学模型有各种不同的形式，如
目标函数有极大化和极小化 约束条件有“≤”、“≥”和“＝”三种情况 决策变量一般有非负性要求，有的则没有
• 例3. 配比问题 用浓度为45%和92%的硫酸配置100吨浓度为80% 的硫酸。 决策变量： 决策变量 取45%和92%的硫酸分别为 x1 和 x2 吨 约束条件： 约束条件 ⎧x + x = 100 1 2 ⎨ x 0 . 45 ⎩ 1 + 0.92x2 = 0.8 ×100 非负约束： 非负约束
xij≥0 (i=1,2,3；j=1,2,3,4)
11
销售平衡条件
非负性约束
求解二元一次方程组得解
12
上海财经大学国际工商管理学院 上海财经大学国际工商管理学院
上海财经大学国际工商管理学院 上海财经大学国际工商管理学院
2
SHUFE
第一节 线性规划一般模型
SHUFE
第一节 线性规划一般模型
上海财经大学国际工商管理学院 上海财经大学国际工商管理学院
上海财经大学国际工商管理学院 上海财经大学国际工商管理学院
SHUFE
第一节 线性规划一般模型
SHUFE
第一节 线性规划一般模型
(1)决策变量。 决策变量 设从Ai到Bj的运输量为xij， (2)目标函数。 目标函数 运费最小的目标函数为
minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34
• 线性规划一般模型的代数式 为： max(min)Z=c1x1+c2x2+…+cnxn a11x1+a12x2+…+a1nxn ≤(≥,＝)b1 a21x1+a22x2+…+a2nxn ≤(≥,＝)b2 …………… am1x1+am2x2+…+amnxn≤(≥,＝)bm x1,x2,…,xn ≥0