1、运筹学教程第一章第一章 线性规划及单纯线性规划及单纯形法形法1-1 线性规划问题及其数学模型线性规划问题及其数学模型1-2 图解法图解法1-3 单纯形法原理单纯形法原理1-4 单纯形法计算步骤单纯形法计算步骤1-5 单纯形法的进一步讨论单纯形法的进一步讨论Date 1运筹学教程 引引 言言线性规划是运筹学的重要分支，也是运筹学中最基本的内容。早在 1939年，前苏联著名数学家康特洛维奇研究了运输和下料等问题，编著了 生产组织和计划中的数学方法 一书，为线性规划的研究奠定了基础。1947年 Dantgig提出了一般线性规划的算法 单纯形法。尔后 Kuhn提出了线性规划的对偶理论，使线性规划的理论
2、和方法日趋完善成熟。随着电子计算机的产生与发展，线性规划在工业、农业、商业、交通运输业、建筑业、军事等行业的计划和管理及决策分析中得到了广泛与深入的应用，取得了良好的效果。目前， 线性规划正以它具有理论成熟，计算简单精确，适应性强，应用面广的特点引起了工程技术人员、管理人员和经济学者的重视。 它已成为重要的优化技术和手段。 Date 2运筹学教程一、线性规划问题的数学模型在现有各项资源条件的限制下，如何确定方案，使预期目标达到最优，这就是规划方法。例 1 美佳公司计划制造 、 两种家电产品。已知各制造一件时分别占用的设备 A、 B的 台时、调试时间、调试工序每天可用于这两种家电的能力、各售出一
3、件时的获利情况，如表 1-1所示。问该公司应制造两种家电产品各多少件，使获取的利润为最大？1-1 线性规划问题及其数线性规划问题及其数学模型学模型返回第一章目录Date 3运筹学教程 1-1 线性规划问题及其数线性规划问题及其数学模型学模型用数学语言来描述这个问题。假设美佳公司每天制造 、 两种家电产品的数量分别是 x1和 x2件。max约束条件目标函数 Z 2x1 x25x2156x1 2x224x1 x25x1， x20这就是例 1的数学模型Date 4运筹学教程 运筹学基础及应用运筹学基础及应用 第一章例第一章例 2【 例 2】 某企业计划生产 I、 两种产品。这两种产品都要分别在 A、
4、 B、 C、 D四种不同设备上加工。按工艺资料规定，生产每件产品 I需占用各设备分别为 2、 1、 4、 0小时，生产每件产品 B，需占用各设备分别为 2、 2、 0、 4小时。已知设备计划期内用于生产这两种产品的能力分别为 12、 8、 16、 12小时，又知每生产一件产品 I企业能获得 2元利润、每生产一件产品 企业能获得 3元利润，问该企业应安排生产两种产品各多少件，使总的利润收入为最大？Date 5运筹学教程 产 品资 源 产 品 产 品 生 产 能力（ h）设备 A（ h） 2 2 12设备 B（ h） 1 2 8设备 C（ h） 4 0 16设备 D（ h） 0 4 12利 润 （
5、元 /件） 2 3假设：计划期内生产产品 x1件，产品 x2件。Date 6运筹学教程例例2捷运公司拟在下一年度的 1 4月份的 4个月内租用仓库堆放物资。已知各月份所需仓库面积数。仓库租借费用随合同期而定，期限越长，折扣越大，具体数字如表 1-2所示。租借仓库的合同每月初都可办理，每份合同具体规定租用面积和期限。因此，该厂可根据需要，在任何一个月初办理租借合同。每次办理可签一份，也可签若干份租用面积和租借期限不同的合同，试确定该公司签定租借合同的最优决策，目的是使所付租借费用最小。Date 7运筹学教程假设用 xij表示捷运公司第 i（ i 1， 2， ， 4） 个月月初签订租借期为 j（
6、j 1， 2， ， 4） 个月的仓库面积数 (单位为 100m2）。则min z 2800(x11+x21+x31+x41)+4500(x12+x22+x32)+6000(x13+x23)+7300x14x11+x12+x13+x1415x12+x13+x14+x21+x22+x23 10x13+x14+x22+x23+x31+x32 20x14+x23+x32+x41 12xij 0 (i 1， 2， ， 4； j 1， 2， ， 4）租借期为一个月的仓库面积租借期为二个月的仓库面积租借期为三个月的仓库面积租借期为四个月的仓库面积一月份拥有的租借面积二月份拥有的租借面积三月份拥有的租借面积四
7、月份拥有的租借面积一月份仓库需求面积约束二月份仓库需求面积约束三月份仓库需求面积约束四月份仓库需求面积约束非负约束Date 8运筹学教程 组成线性规划模型的三组成线性规划模型的三个要素个要素max Z 2x1 x25x2156x1 2x224x1 x25x1， x20目标函数 ：约束条件（ 1）变量（决策变量）变量（决策变量） :它是规划中要确定的未知量，它是规划中要确定的未知量，是用数量方式来表示的方案或是用数量方式来表示的方案或措施，可由决策者决定和控制措施，可由决策者决定和控制。（ 2）目标函数：）目标函数：它是决策变量的函数，是决策它是决策变量的函数，是决策者在一定的限制条件下希望得者
8、在一定的限制条件下希望得到的结果。到的结果。（ 3）约束条件：）约束条件：指决策变量取值时受到的各种指决策变量取值时受到的各种资源条件的限制，通常用等式资源条件的限制，通常用等式或不等式来表达。或不等式来表达。其中，其中， xij0叫做非负约束。叫做非负约束。由于目标函数是决策变量由于目标函数是决策变量的线性函数，约束条件是含决的线性函数，约束条件是含决策变量的线性等式或不等式，策变量的线性等式或不等式，所以此类模型称为线性规划的所以此类模型称为线性规划的数学模型。数学模型。实际问题中，线性的含义有二：实际问题中，线性的含义有二：一是一是 严格的比例性严格的比例性 ，即某种产品，即某种产品对资
9、源的消耗量和可获得的利润与其对资源的消耗量和可获得的利润与其生产数量严格成比例。生产数量严格成比例。二是二是 可迭加性可迭加性 。即生产多种产品。即生产多种产品对某种资源的消耗量等于各产品对该对某种资源的消耗量等于各产品对该项资源的消耗量之和。项资源的消耗量之和。Date 9运筹学教程模型中， cj称为价值系数。bi是资源限制量。aij称为技术系数或工艺系数。二、线性规划模型的一般二、线性规划模型的一般形式形式假设线性规划问题中含有假设线性规划问题中含有 n个变量，个变量， m个约束方程。则线性个约束方程。则线性规划模型的一般形式为：规划模型的一般形式为：max(或 min)z c1x1+c2x2+ cnxna11x1+a12x2+ a1nxn（ 或， ）b1a21x1+a22x2+ a2nxn（ 或， ）b2am1x1+am2x2+ amnxn（ 或， ）bmx1,x2, xn0简写为：向量形式：矩阵形式：Date 10
