第2讲 线性规划
第2讲 线性规划
第二章线性规划 2.1线性规划模型的建立 ◇2.2线性规划模型的求解 23对偶原理及灵敏度分析 ◇2.4运输问题
第二章 线性规划 ❖2.1 线性规划模型的建立 ❖2.2 线性规划模型的求解 ❖2.3 对偶原理及灵敏度分析 ❖2.4 运输问题
2.1线性规划模型的建立 在生产管理和经营活动中经常提出的一类问题是:如何合理地利用 有限的人力、物力、财力等资源,以便获得最好的经济效益。 引例、资源配置:某工厂生产A、B、C三种产品,每吨利润分别为2000 元,3000元,3000元;生产单位产品所需的工时及原材料如表1-所示 若供应的原材料每天不超过9t,所能利用的劳动力日总工时为3个单位, 问如何制定日生产计划,使三种产品总利润最大? 表1-1每吨产品工时、材料消耗表 生产每吨 产品所需 资源 资源品 A B C 工时 材料 147
表1-1 每吨产品工时、材料消耗表 产 品 生产每吨 产品所需 资 源 资源 A B C 工 时 材 料 1 1 1 1 4 7 在生产管理和经营活动中经常提出的一类问题是：如何合理地利用 有限的人力、物力、财力等资源，以便获得最好的经济效益。 引例、资源配置： 某工厂生产A、B、C三种产品，每吨利润分别为2000 元，3000元，3000元；生产单位产品所需的工时及原材料如表1-1所示。 若供应的原材料每天不超过9t，所能利用的劳动力日总工时为3个单位， 问如何制定日生产计划，使三种产品总利润最大？ 2.1 线性规划模型的建立
2.1线性规划棋型的建立 问题:工时和材料的日可供量已知,求使利润最大的 生产方案 解:产品A,B,C的日生产量:x1,x2,x3 每日工时=x1+x2+x3 每日消耗材料量=x1+4x2+7x3 每天可得利润(以千元为单位) Z=2x1+3x,+3x maxz=2x1+3x2+3x3利润最大 x1+x2+x3≤3 工时约束 stx,+4x,+7x≤9 材料约束 x1≥0,x2≥0,x2≥0 非负约束
问题：工时和材料的日可供量已知，求使利润最大的 生产方案 解：产品A，B，C的日生产量： x1，x2，x3 每日工时= x1 + x2 + x3 每日消耗材料量= x1 + 4x2 + 7x3 每天可得利润（以千元为单位） Z = 2x1 + 3x2 + 3x3 工时约束 材料约束 非负约束 max 2 1 3 2 3 3 Z = x + x + x + + + + 0, 0, 0 4 7 9 3 . . 1 2 3 1 2 3 1 2 3 x x x x x x x x x st 利润最大 2.1 线性规划模型的建立
2.1线性划模型的建立 21.1线性规划模型的概念 模型的组成部分( Components of the Model) 1.决策变量( Decision variables) 2.目标函数( Objective function) 3.约束( Constraints) 定义:对于求取一组变量x(=1,2 使之既 满足线性约束条件,又使具有线性的目标函数取 得极值的一类最优化问题称为线性规划问题
❖ 模型的组成部分（Components of the Model） 1. 决策变量（Decision variables） 2. 目标函数（Objective function） 3. 约束（Constraints） ❖ 定义：对于求取一组变量xj (j=1,2,…..,n)，使之既 满足线性约束条件，又使具有线性的目标函数取 得极值的一类最优化问题称为线性规划问题。 2.1 线性规划模型的建立 2.1.1 线性规划模型的概念
线性规划模型的一般形式 目标函数(线性) max(或min)z=C1x1+C2x2+…+Cnx a1x1+a12x2+…+a1nxn≤(=2)b 约束条件 (线性) 21x1+a2x+……+a2 nn st an1x1+an2x2+…+anxn≤(=2)b n x1,x2…x20(≤0自由) 非负约束 x(=12,…,n)称为决策变量 C,(j=1,2,…,n)称为价值系数或目标函数系数 b(i=12…,m)称为资源常数或约束右端常数 (!=1…w1=r…)称为技术系数或约束系数
max（或min） ( ) + + + = + + + = + + + = , , , 0 0,自由 ( , ) ( , ) ( , ) . . 1 2 1 1 2 2 2 1 1 2 2 2 2 2 1 1 1 1 2 2 1 1 n m m mn n m n n n n x x x a x a x a x b a x a x a x b a x a x a x b st n n Z = c x + c x ++ c x 1 1 2 2 目标函数（线性） 约束条件 （线性） 非负约束 x j ( j = 1,2, ,n) 称为决策变量 c j ( j = 1,2, ,n) 称为价值系数或目标函数系数 bi (i =1,2, ,m) 称为资源常数或约束右端常数 称为技术系数或约束系数 a (i 1,2, ,m, j 1,2, ,n) i j = = 线性规划模型的一般形式：
线性规划建模 线性规划模型的一般形式: 紧缩形式: max(或min)z=∑cx ∑anx,≤(=≥)b st x1≥0j=1,2,…,n 线性规划的假设 1.线性( Linearity) 2.可分性( Divisibility) 3.确定性( Certainty) 4.非负性( Nonnegativity)
❖ 紧缩形式： 线性规划建模 max(或min) = = n j j j Z c x 1 = = = x j n a x b st j n j i j j i 0 1,2, , ( , ) . . 1 i=1,2,…..,n ❖ 线性规划的假设 1. 线性（Linearity） 2. 可分性（Divisibility ） 3. 确定性（Certainty） 4. 非负性（Nonnegativity） 线性规划模型的一般形式：
线性规划建模 矩阵形式: Max(或Min)z=CX AX≤(=,≥)b s t X≥0 C=(c1,C2…,Cn)称为价值系数向量或目标函数系数向量 b X A 2 m2 称为决策变量向量 称为技术系数或约束系数矩阵称为资源常数向量或 约束右端常数向量
矩阵形式： Max(或Min) Z = CX = X 0 AX b st ( , ) . . 称为决策变量向量 = n x x x X 2 1 C = (c1 ,c2 , ,cn ) 称为价值系数向量或目标函数系数向量 称为技术系数或约束系数矩阵 = m m mn n n a a a a a a a a a A 1 2 2 1 2 2 2 1 1 1 2 1 称为资源常数向量或 约束右端常数向量 = m b b b b 2 1 线性规划建模
线性规划建模 线性规划模型特点: ①用一组未知变量(决策变量)表示要求的方案 通常,根据决策变量所代表的事物的特点可以 对变量的取值加以约束,例如非负约束。 ②存在一定的限制条件,通常称为约束条件,这 些约束条件可以用一组线性等式或者线性不等 式来表示。 ③有一个目标要求,并且可以表示为决策变量的 线性函数,称为目标函数,按所研究问题的不 同,要求目标函数实现最大化或者最小化
线性规划模型特点： ① 用一组未知变量（决策变量）表示要求的方案。 通常，根据决策变量所代表的事物的特点可以 对变量的取值加以约束，例如非负约束。 ② 存在一定的限制条件，通常称为约束条件，这 些约束条件可以用一组线性等式或者线性不等 式来表示。 ③ 有一个目标要求，并且可以表示为决策变量的 线性函数，称为目标函数，按所研究问题的不 同，要求目标函数实现最大化或者最小化。 线性规划建模
2.1.2线性规划问题建模步骤 需要做哪些决策?决策变量是什么 问题的目标是什么?写出目标函数 资源和需求之间的情况如何?确定约 束条件
❖ 需要做哪些决策？决策变量是什么 ❖ 问题的目标是什么？写出目标函数 ❖ 资源和需求之间的情况如何？ 确定约 束条件 2.1.2 线性规划问题建模步骤
