南开大学数学课件ja5.4 mathematica软件解线性方程组与线性规划.pdf

276 5 4 解线性方程组与线性规划解线性方程组与线性规划 教学要求教学要求 要求掌握用 Mathematica 解线性方程组的方法 了解齐次线性方程组的基础解系的概念 理解线性规划问题的提法 并掌握用 Mathematica 处理线性规划问题的办法 知识点知识点 1 齐次线性方程组的基础解系 2 非齐次线性方程组的通解 3 线性规划问题的提法 4 线性规划问题的解与求解 5 4 1 齐次线性方程组的基础解系齐次线性方程组的基础解系 我们知道一般的n 元线性方程组 5 4 1 2211 22222121 11212111 mnmnmm nn nn bxaxaxa bxaxaxa bxaxaxa L LLL L L 可写成矩阵形式AX B 若B 0 则 5 4 1 称为齐次线性方程组 当齐次线性方程组系数矩 阵A的秩r A n时 它有唯一的零解 当r A 9 b5 9 a y 9 b 9 a2 解二 In 9 LinearSolve P a b Out 9 9 b5 9 a 9 b 9 a2 解三 In 10 Inverse P a b Out 10 9 b5 9 a 9 b 9 a2 于是得方程组的唯一解 99 2 9 5 9 ba y ba x 注 当方程组的系数行列式为0时 上面的求解过程就失效了 此时应按定理5 4 1来解 也可直接用语句Solve 求出所有解 例5 4 6 求线性方程组 022 22 1 12 6432 6421 65432 54321 xxxx xxxx xxxxx xxxxx 的全部解 显然此方程组的未知数个数多于方程的个数 因此有无穷多个解 我们可用语句 Solve 来求解 解 In 11 A1 1 2 1 1 1 0 0 1 1 1 1 1 1 1 0 1 0 2 0 2 2 1 0 1 Out 11 1 2 1 1 1 0 0 1 1 1 1 1 1 1 0 1 0 2 0 2 2 1 0 1 279 In 12 A1 x1 x2 x3 x4 x5 x6 1 1 2 0 Out 12 x1 2x2 x3 x4 x5 x2 x3 x4 x5 x6 x1 x2 x4 2x6 2x2 2x3 x4 x6 1 1 2 0 In 13 Solve x1 x2 x3 x4 x5 x6 Out 13 x1 1 x3 x5 x6 x2 1 x3 x5 2x6 x4 2 2x5 3x6 因此给定方程组的通解是 X 0 0 2 0 1 1 c1 0 0 0 1 1 1 c2 0 1 2 0 1 1 c3 1 0 3 0 2 1 其中c1 c2与c3是任意常数 实验5 4 7 某地区有三个产业 煤矿 发电厂和地方铁路 开采一元钱的煤 煤矿要支付 0 25元的电费及0 25元的运输费 生产一元钱的电力 发电厂要支付0 65元的煤费 0 05 元的电费及0 05元的运输费 创收一元钱的运输费 铁路要支付0 55元的煤费及0 10元的 电费 在某一周内 煤矿接到外地金额为50000元的定货 发电厂接到外地金额为25000 元的定货 外界对地方铁路没有需求 请你编制投入产出表 并求三个企业在这一周内总产 值多少才能满足自身及外界的需求 关于投入产出可参看1 4 3线性方程组在经济中的 应用 实验5 4 7 假定我国兵器工业主要由五个行业组成 某年度兵器工业主要行业简化的投 入产出平衡表如下 产值单位是亿元 1 2 3 4 5 A行业 B行业C行业D行业E行业合计 最终产品 总产值 1 A行业 10 20 30 40 50 150 350 500 2 B行业 40 30 20 50 60 200 200 400 3 C行业 50 30 60 20 20 180 220 400 4 D行业 30 30 20 10 40 130 270 400 5 E行业 40 30 20 20 30 140 360 500 6 物资 130 160 150 160 180 7 能源 110 50 40 30 40 8 工资利税 90 50 60 70 80 总投入 500 400 400 400 500 如果要求把最终产品均提高8 那么各行业应如何修改生产计划 5 4 3 线性规划问题的提法线性规划问题的提法 例5 4 8 某工厂有甲 乙 丙 丁四个车间 生产A B C D E F六种产品 根据车 间生产条件与原有生产情况 得知生产各种产品每单位所需工作小时数 各车间每月工作 小时的上限 以及产品的价格如下表所示 A B C D E F 每月工作小时上限 甲 0 1 0 1 0 1 0 3 0 3 0 3 850 乙 0 2 0 5 700 丙 0 2 0 5 100 280 丁 0 3 0 8 900 单价 4 0 2 8 3 2 7 2 6 4 6 0 各种产品每月应该生产多少 才能使该厂每月的生产总值最大 我们用x1 x2 x6分别表示每月生产A B C D E F六种产品的单位数 于是 它们应满足下列约束条件 0 1x1 0 1x2 0 1x3 0 3x4 0 3x5 0 3x6 850 0 2x1 0 5x4 700 0 2x2 0 5x5 100 0 3x3 0 8x6 900 其中xj 0 j 1 2 6 于是问题成为求生产总值函数 f 4 0 x1 2 8 x2 3 2 x3 7 2 x4 6 4 x5 6 0 x6 在上述约束条件下达到最大 这个f 称为目标函数 xj 称为决策变量 它们应满足的不等式组称为约束条件 其中 xj 0称为非负约束 在这里 目标函数与约束条件不等式的左端均为决策变量的线性函数 因此把这个问题称为线性规划 一般情况 约束条件可以是包含 的不等式 也可以是包含 的不等式或等式 同样 目 标函数可以是求最大值 也可以是求最小值 但我们总可以把给定线性规划问题化为等价的 标准形式 njx mibxa xcf j i n j jij n j jj 1 0 1 s t min LP 1 1 L L 其中目标函数 f 是求最小值 约束条件是包含 的不等式 也可以写成矩阵形式 min f c x s t Ax b x 0 5 4 4 线性规划问题的解与求解线性规划问题的解与求解 满足约束条件Ax b x 0的向量x称为线性规划问题 LP 的一个可行解 全体可行解 的集合称为 LP 的可行域 使目标函数 f 达到最小值的可行解称为 LP 的最优解 其对应的目 标函数的值称为最优值 我们先用作图的方法解一个简单线性规划问题 从直观上理解线性规划问题的解 例5 4 9 求解两个变量的线性规划问题 min f x y s t 2 x y 2 x 2 y 2 x y 5 x y 0 解 我们知道 二元一次方程a x b y c 0 表示直角坐标平面上的一条直线 该直线又把 整个平面分成两个半平面 分别可以用二元一次不等式a x b y c 0 与a x b y c 与 分别改成 与 即可 现在 问题中的五个不等式分别表示五个半 平面 于是问题成为在这五个半平面的交集上求函数 f x y的最小值 我们作图如下 图5 12 281 图中的四边形ADEC 包括边界 是问题的可行域 其中顶点的坐标分别是 A 7 3 8 3 D 1 0 E 2 0 C 4 1 另一方面 二元线性函数f x y显然连续 而且其线性性质使它只能在可行域四边形 ADEC的边界上取得最小值 进一步 它又在边界的四条线段AD DE EC CA的各自端点 处取得该线段上函数的最小值 因此 我们只要计算出四个顶点A D E C处的函数值 f A 1 3 f D 1 f E 2 f C 3 其中的最小者f C 3就是问题的解 在Mathematica 中解线性规划问题可用下面的三种语句 在约束条件下求目标函数f的最大值 用语句 ConstrainedMax f inequalities x y 在约束条件下求目标函数f的最小值 用语句 ConstrainedMin f inequalities x y 以上两种语句不必将问题标准化 如果解矩阵形式的线性规划问题 则应先将问题化为 等价的标准形式 LP 然后用语句 LinearProgramming c A b 例5 4 10 Max f 5 x 7y s t 2 x 5 y 50 3x 2 y 42 x y 0 解 In 14 ConstrainedMax 5x 7y 2x 5y 50 3x 2y10 y 6 于是得f 10 6 92 是问题的解 例5 4 11 Min f 5 x 7y s t 2 x 5 y 10 3x 2 y 42 x y 0 解 In 15 ConstrainedMin 5x 7y 2x 5y 42 x y 运行后 屏幕出现下述内容 ConstrainedMin nsat Specified constraints cannot be satisfied Out 15 ConstrainedMin 5x 7y 2x 5y 42 x y 这表明问题无可行解 例5 4 12 Max f 5 x 7y s t 2 x 5 y 10 3x 2 y 42 x y 0 解 In 16 ConstrainedMax 5x 7y 2x 5y 10 3x 2y 42 x y 运行后 屏幕出现下述内容 ConstrainedMax nbdd Specified domain appears unbouned Out 16 Infinity x Indeterminate 这表明问题有可行解 但无最优解 例5 4 13 现在用语句LinearProgramming 来解例5 4 8中的问题 首先将问题标准化 即求 求目标函数的最小值 并用 不等式的约束条件 In 17 c 4 0 2 8 3 2 7 2 6 4 6 0 A 0 1 0 1 0 1 0 3 0 3 0 3 0 2 0 0 0 5 0 0 0 0 2 0 0 0 5 0 0 0 0 3 0 0 0 8 b 850 700 100 900 LinearProgramming c A b Out 17 3500 500 3000 0 0 0 注 只给出最优解 但不给出最优值 实验 5 4 14 某煤矿公司拥有两个分矿 甲矿每班能生产 10t 优质煤 30t 中等煤 50t 次煤 乙矿 每班能生产三种煤各 20t 该公司生产的煤能全部卖掉 但两个矿的运作费用不同 因此为公 司挣得的利润不同 甲矿每班能挣得利润 2000 元 乙矿是 2100 元 而公司的最大开采量是 8800t 优质煤 16000t 中等煤 20000t 次煤 公司可任意安排班次 问如何计划生产 才能获得最 大利润 最大利润又是多少 282 实验 5 4 15 某人需补充维生素 现有两种维生素胶囊 都含维生素 A C D E 及 Z 甲