第07章 线性规划与归约.pdf

2015-1-4  7.1 线性规划简介  7.2 网络流  7.3 二部图的匹配  7.4 对偶  7.5 零和博弈  7.6 单纯形算法 1 2015-1-4  巧克力工厂两种产品: （1）Pyramide三角形巧克 力 （2）奢华高级Pyramide Nuit。  问题：两种产品各生产多少可以使得利润最大化。 品种 数量 利润 Pyramide X1 $1 Nuit X2 $6 2 2015-1-4 利润线  唯一的例外是最优解不存在，两种可能情况： ◦ 该线性规划本身不可行，即约束条件过紧，导致所有的约 束不可能全部同时满足 （可行区域为空）。 ◦ 例如，x=1,x=2 ◦ 约束条件过松，导致可行区域无界，目标函数可能得到任 意大 （或小）的值。 ◦ 例如，max x1+x2 x1,x2=0 3 2015-1-4 中文名 乔治·伯纳德·丹齐格 外文名 George Bernard Dantzig 国 籍 美国 出生地 美国俄勒冈州波特兰 出生日期 1914年11月8 日 逝世日期 2005年5月13日 职 业 数学家 毕业院校 加州大学伯克利分校博士 主要成就 单纯型法 4 2015-1-4 品种 数量 利润 Pyramide X1 $1 Nuit X2 $6 Luxe X3 $13 5 2015-1-4  每个月的需求d1、d2、……d12 （440~920）。  30名员工，20条地毯/人月，$ 2000工资/人月。  主要挑战：需求起伏不定。  分析：三种途径 ◦ (1)加班。80%工资/人小时，加班时间不能超过正常工时 的30%。 ◦ (2)聘用和解聘。一次性费用$ 300和$400 ◦ (3)仓库囤积。每条地毯的仓储费用$ 8/月  解决方法  （1）72个变量 ◦ w =第i个月时的工人数，其中w =30 i