疯性视剡 本章内容重点 线性规划模型与解的主要概念 √线性规划的草纯形法,线性规划多解 分析 √线性规划应用—建棋
本章内容重点 ü线性规划模型与解的主要概念 ü线性规划的单纯形法，线性规划多解 分析 ü线性规划应用——建模
疯性视剡 运用分析理论,在第三次世界大战后,有着突飞猛进的 发畏。从运筹学理论和应用观点看,最大的发展或称之为成 就的,是线性规划。线性规划的莫基人是 GBDantzig。线性 规划发畏的重火事件如下: √1947年, Dantzig提出单纯形解法; 1950-1956年,主要研究线性规划的对偶性理论 √1958年,发表整数规划的割平面方法; √1960年, Dantzig和Wole研究成劝分解算法,莫定了 大规模线性规划狸论和算法的基础; √1979年, Khachiyan以及1984年, Karmarkar研究成 功线性规划的多项式算法,轰动了整个运筹学术界
运用分析理论，在第二次世界大战后，有着突飞猛进的 发展。从运筹学理论和应用观点看，最大的发展或称之为成 就的，是线性规划。线性规划的莫基人是G•B•Dantzig。线性 规划发展的重大事件如下： ü 1947年，Dantzig提出单纯形解法； ü 1950—1956年，主要研究线性规划的对偶性理论 ü 1958年，发表整数规划的割平面方法； ü 1960年，Dantzig和Wolfe研究成功分解算法，奠定了 大规模线性规划理论和算法的基础； ü 1979年，Khachiyan以及1984年，Karmarkaa研究成 功线性规划的多项式算法，轰动了整个运筹学术界
线性视剡数学模型 例1-1(资源利用问题) 某建筑公司的预制厂利用沙、石、水泥三种原料A1、 A2、A3来生产两种预制件B1和B2,巳知该厂各种原料的 现有数量、单位预制件对各种原料的消耗量及单位预制 件的利涧如下表所示。在现有资嫄的条件下,如何分配 预制件B1和B2的生产,才能使公司获刑最大? 单位产品消耗 产品\B1 B2 原料现有数量 原料 45 草位利涧(百元) 5 4
例1-1 (资源利用问题) 某建筑公司的预制厂利用沙、石、水泥三种原料A1、 A2、A3来生产两种预制件B1和B2，已知该厂各种原料的 现有数量、单位预制件对各种原料的消耗量及单位预制 件的利润如下表所示。在现有资源的条件下，如何分配 预制件B1和B2的生产，才能使公司获利最大？ 原料现有数量 (M3) B1 B2 单位产品消耗 产品 原料 单位利润(百元) 5 4 A3 1 1 45 A2 2 1 80 A1 1 3 90
线性视剡数学模型 苇1步;磅定求吏量 °诞x1——Bn 7的声量是何趣中要嚼史的杀量 長明觑划中的眉子表示的 2B2的声量、施,可岭敦奇岭 定和嬗制。 第2步“定义日标函数 Max Z=5X1+4x2
x1 x2z
线性视剡数学模型 第3步一表示约乘杀件 B1B2资娠限量 x1+3x2≤90 1390 21 80 2x1+x2≤80 AAA 23 45 +x2≤45利54 x1、x2≥0
B1 B2 资源限量 A1 A2 A3 121 311 908045 利润 5 4
线性视剡数学模型 孩计刺的学摸型 目标函数MaxZ=5X1+4x2 约束条件x1+3x2≤90 2x1+x2≤80 1+12≤45 x2≤0
线性视剡数学模型 一般地设用A142,…,4m种原料,可以生产B1,B2,…,Bn种 产品,已知A种原料现有数量为a单位,生产单位B种产品需 要A1种原料an单位,B种单位产品的利润为c元,如何安排 生产才能获得最大利涧? 设x为计划生产第B种产品的教量,则: Maxf(x)= ∑c 2y412m x:≥0
一般地设用A1 ,A2 ,…,Am种原料，可以生产B1 ,B2 ,…,Bn 种 产品，已知Ai种原料现有数量为ai单位，生产单位Bj种产品需 要Ai种原料aij单位， Bj种单位产品的利润为cj 元，如何安排 生产才能获得最大利润？ 设xj为计划生产第Bj种产品的数量，则： ï î ï í ì ³ £ = å å = = 0 ( ) 1 1 j i n j ij j n j j j x a x a st Maxf x c x i=1,2,…m
线性视剡数学模型 例1-2(物资调运问题) 有两个砖厂A1、A2,其产量分别为23万块砖和27万 块砖,其产品供应B1,B2和B3三个工地,各工地需要量 分别为17万块砖,18万块砖和15万央砖,已知从A1、A2 分别向B1,B2和B3运送1万块砖所需要的费用如下表所 示。如何调运才能使恿运费最小? 价 砖厂 2 工地 50 60 70 160
例1-2(物资调运问题) 有两个砖厂A1、A2，其产量分别为23万块砖和27万 块砖，其产品供应B1 、B2和B3三个工地，各工地需要量 分别为17万块砖，18万块砖和15万块砖，已知从A1、A2 分别向B1 、B2和B3运送1万块砖所需要的费用如下表所 示。如何调运才能使总运费最小？ A1 A2 运 价 砖厂 工地 B3 70 160 B2 60 110 B1 50 60
线性视剡数学模型 一般地,设有某种物资有m个产地:A1,A2,…, Am联合供应阻个销地:B1,B2,…,Bn。各产地产量 各销地销量以及个产地至各销地草位运价如下表。如何 调运才能使恿运费录小? 还 菊地 产地 B B2 B 产量 A C 11 12 C mt 销量 b 垂 b
一般地，设有某种物资有m个产地：A1，A2，…， Am联合供应n个销地：B1，B2，…，Bn 。各产地产量、 各销地销量以及个产地至各销地单位运价如下表。如何 调运才能使总运费最小？ 运价 销地 产地 B1 B2 … Bn 产量 A1 C11 C12 … C1n a1 A2 C21 C22 … C2n a1 … … … … … … Am Cm1 Cm2 … Cmn am 销量 b1 b2 … bn
线性视剡数学模型 倒13(节约下料问题 某工厂要儆100套钢杂,每套用长为2.9m,2.1m,1.5m的圓钢 各一根。已知原料每根长74m,应如何下料可使所用原料录省? 一般地,设用甚种原料下零件A1,A2,…,Am的毛坯,一件原 料上有B1,B2,…,Bn种不同的下料方式,每种下料方式可得各 种毛坯个數及每种零件需要量见下表。怎样下料既能满足需要又能 使所用原料最少? 零件个教下料方式 零件 零件名称 B B 需要量 A C1 A
例1-3(节约下料问题) 某工厂要做100套钢架，每套用长为 2.9m，2.1m，1.5m 的圆钢 各一根。已知原料每根长 7.4 m，应如何下料可使所用原料最省？ 一般地，设用某种原料下零件A1，A2，…，Am的毛坯，一件原 料上有B1，B2，…，Bn 种不同的下料方式，每种下料方式可得各 种毛坯个数及每种零件需要量见下表。怎样下料既能满足需要又能 使所用原料最少？ 零件个数 下料方式 零件名称 B1 B2 … Bn 零件 需要量 A1 C11 C12 … C1n a1 A2 C21 C22 … C2n a1 … … … … … … Am Cm1 Cm2 … Cmn am