第五章 线性规划(全部).pdf

第五章 线性规划 ●线性规划问题举例线性规划问题举例 ●线性规划的标准形式及图解法 ●线性规划的基本概念及基本性质 ●单纯形法 ●两阶段法及大 M 法 修正单纯形法 ●●线性规划的对偶理论线性规划的对偶理论 对偶单纯形法对偶单纯形法 1／140 §1 线性规划问题举例 例例 11:某工厂拥有某工厂拥有 AA 、BB 、CC 三种类型的设备三种类型的设备，生生 产甲、乙两种产品。每件产品在生产中需要占用 的设备机时数，每件产品可以获得的利润以及三 种设备可利用的时数如下表所示种设备可利用的时数如下表所示，问题问题：工厂应工厂应 如何安排生产可获得最大的总利润？ x i 解：设变量 为第 种（甲、乙）产品的生产件数 i i （（＝1，2 ））。 2／140 产品甲 产品乙 设备能力（h） 设备A 3 2 65 设备B 2 1 40 设备C 0 3 75 利润（元/件） 1500 2500 根据题意，我们知道两种产品的生产受到设 备能力备能力 （机时数机时数）的限制的限制。该问题建该问题建立的数的数 学规划模型如下： 3／140 目标函数 max z 1500x1 2500x2 约束条件约束条件 s.t. 33x1 22x2 6565 2x x 40 1 2 3x 75 2 xx11 00,,xx22 00 4／140 例 2 （运输问题） 一个制造厂要把若干单位的产品从个制造厂要把若干单位的产品从 AA , AA 两个仓两个仓 1 2 B ,B ,B ,B A 库发送到零售点 1 2 3 4 。仓库 能供应产品 i a (i 1, 2) B 的数量为 i ，零售点 j 所需产品的数量为 b ((jj 1,, 2,, 3,, 4)) jj 。假设能供应的总量等假设能供应的总量等于需于需要的总要的总 2 4 a b   量量，，即即 i j 。且已知从仓库且已知从仓库Ai 运运一个单位个单位 ii 11 jj 1