1、1/107运筹学卢有杰2015年 2月 26日内容绪论第一章 线性规划及单纯形法第二章 线性规划对偶理论与灵敏度分析第三章 运输问题第四章 整数规划第六章 非线性规划第七 章 动态规划 第八 章 图与网络 分析2/107绪论第一节 运筹学释义与发展简史第二节 运筹学研究的基本特征第三节 运筹学主要分支第四节 运筹学与管理学科3/107第一章 线性规划及单纯形法第一节 线性规划问题及其数学模型第二节 图解法第三节 单纯形法原理第四节 单纯形法计算步骤第五节 单纯形法进一步讨论第六节 数据包络分析第七节 其他应用例子4/107第一节 线性规划问题及其数学模型一、问题的提出5/1076/107设备台
2、时 /件产品 可用台时（千小时）产 品 1 产 品 2下料 设备 A 1 0 4机加工 设备 B 0 2 12焊 接 设备 C 3 2 18产 品 单 价 3元 /件 5元 /件例 1 某厂用三种设备生产两种产品，各自需用的设备时间和单件售价均不同。n问：两种产品各生产多少，销售收入最多？7/107分别用 x1 和 x2（称 “决策变量 ”）表示两种 产品 日产量，用 z表示每日销售收入，z=3x1+5x2，希望越大越好， z称 “目标函数 ”， 亦可写成 f(x)但因设备可用时间有限， x1和 x2亦受 限制。1x1+0x2 4,000 下料设备0x1+2x2 12,000 机加工设备3x1
3、+2x2 18,000 焊接设备另外 ， x1， x2 0，这 5个要求，叫做 “约束条件 ”8/107现将目标函数和约束条件写在一起，Max z=3x1+5x2 (1)s.t. x1 4,000 (2)2x2 12,000 (3)3x1+2x2 18,000 (4)x1， x2 0， (5)s.t.=subject to(1)(5)就是上述合理安排产量问题的 数学模型 。就是 ， “如何在既定的约束条件下，选择 决策变量之 值，使目标函数取得最大值（最优值）。 ”9/107欠土 B1 欠土 B2 欠土 B3 欠土 B4 余方量多土A1 x11 x12 x13 x147多土A2 x21 x22
4、 x23 x244多土A3 x31 x32 x33 x349需量 3 6 5 6 20 203 11 3 101 9 2 87 4 10 5例 2平整某场地，有三处高，需削平，有四处低，需填高。已算出高处总余方量恰好满足低处总需方量。 12种运价也已算出，在右上角方格内。问 ：如何调度，才花费最少？10/107用 xij表示从第 i个高处 Ai调往第 j个低处 Bj的土方量， xij仍然称为 “决策变量 ”，用 z表示将所有多余土方调往所有欠方处的总费用，则Min z=3x11+11x12+3x13+10x14+x21+9x22+2x23+8x24+7x31+4x32+10x33+5x34s.t. x11+x12+x13+x14=7 x11+x21+x31=3x21+x22+x23+x24=4 x12+x22+x32=6x31+x32+x33+x34=9 x13+x23+x33=5x14+x24+x34=6xij 0， 1 i3 , 1 j4 ， i和 j 皆为正整数
