[管理学]2第二章 线性规划的图解法.pptVIP

第二章 线性规划的图解法 第二章 线性规划的图解法 线性规划（Linear Programming，简记为LP）是运筹学的一个重要分支，是运筹学中研究较早、发展较快、理论上较为成熟和应用上极为广泛的一个分支。 特别是1947年G.B. Dantying提出了一般线性规划问题求解的方法——单纯形法之后，线性规划的理论与应用都得到了极大的发展。单纯形法的有效性使它不仅是线性规划的最基本的算法之一，而且已成为整数规划和非线性规划某些算法的基础。 §1 线性规划问题及其数学模型 一、 线性规划问题的提出 要利用线性规划的方法解决实际问题，首先要建立其数学模型. 数学模型是描述实际问题共性的抽象的数学形式，因此可以利用纯数学的方法进行研究，从而得到实际问题的性质及其解决的办法。从实际问题中建立数学模型，主要有以下三个步骤： (1) 根据影响所要达到目的的因素确定决策变量； (2)由决策变量和所要达到目的之间的函数关系确定目标函数. (3)由决策变量所受的限制条件确定决策变量所要满足的约束条件； 例1.资源的合理利用问题 某厂生产甲、乙两种产品，要消耗A、B、C三种资源，已知每生产单位产品甲需要A 、B、C资源分别是3、2、0，生产单位产品乙需要A 、B、C资源分别是2、1、3， 资源A 、B、C的现有数量分别是65、40、75，甲、乙两种产品的单位利润分别是1500、2500，问如何安排生产计划，使得既能充分利用现有资源又使总利润最大 ？ 例2 配料问题 某化工厂根据一项合同要为用户生产一种用甲、乙两种原料混合配制而成的特殊产品. 甲、乙两种原料都含有A、B、C三种化学成分，其含量（%）和单位成本以及按合同规定产品中三种化学成分的最低含量（%）限制如表所示. 问厂方应如何配制该产品，使得总成本达到最小？ 解：(1) 确定决策变量： 设每单位该产品用x1单位甲原料和x2单位乙原料配制而成. (2) 明确目标函数：成本最小，即求 z = 3x1 + 2x2的最小值 (3) 所满足的约束条件 对化学成分A的要求：12 x1+ 3 x2 ≥ 4 对化学成分B的要求：2 x1 + 3 x2 ≥ 2 对化学成分C的要求：3 x1 + 15 x2 ≥ 5 配料平衡条件：x1 + x2 = 1 (4) 变量基本要求： x1，x2 ≥ 0 则问题的数学模型为： 记为 min z = 3x1 + 2x2 12x1 + 3x2 ≥ 4 2x1 + 3x2 ≥ 2 S.t. 3x1 + 15x2 ≥ 5 x1 + x2 = 1 x1，x2 ≥ 0 例3 运输问题 设某种物资有两个产地A1，A2，其产量分别为2000吨、1100吨，另有四个销地B1、B2、B3、B4需要该种物资，其需求量分别为1700吨、1100吨、200吨、100吨. 已知每吨运费如表所示，问如何调运，才能使总运费最省？ 解： 设xij表示由产地Ai运往销地Bj（i = 1,2；j = 1,2,3,4）的运量. 目标函数为总运费最小: minZ = 21x11 + 25x12 + 7x13 + 15x14 + 51x21 + 51x22 + 37x23 + 15x24 由于总产量与总需求量相等（产销平衡）,所以有约束条件： 对产地产量的约束 : x11 + x12 + x13 + x14 = 2000 x21 + x22 + x23 + x24 = 1100 对销地需求量的约束 : x11 + x21 = 1700 x12 + x13 = 1100 x13