运筹学-钱颂迪-第2章.ppt

第2章 线性规划及 单纯形法 本章主要内容 线性规划问题及其数学模型 图解法 单纯性法的计算步骤 应用举例 2.1 线性规划问题及其数学模型 2.1.1 问题的提出 例1：某工厂计划制造Ⅰ、Ⅱ两种产品，占用一种设备和两种原材料A、B，通过分析与抽象，各数据见下表。 例1中 设该公司应该制造Ⅰ类家电X1件 设该公司应该制造Ⅱ类家电X2件 这样，其利润为 根据这个目标函数，我们只要把尽量做大，利润就一定会高。但这可行吗？不可行！我们还有许多制约条件： 对设备: 对原材料A: 对原材料B： 还有，每个家电要么生产，要么不生产 非负条件 其它例子 数学模型的一般表达式 设有n个决策变量xj (j=1,2,…,n)。目标函数中的系数cj （价值系数）; 设有m个约束条件，该条件中各变量的系数aij称为技术系数或工艺系数，i=1,2,…,m; 约束条件等式（或不等式）右侧为bi. 这样，线性规划问题数学模型的一般表达式 2.1.2 图解法 (Graphical Solution) 一、基本概念 目标函数等值线(Objective function line)——为于同一直线上的点，具有相同的目标函数值； 二、图解法步骤(Procedure) （1）画出线性规划问题的可行域； （2）画出两条目标函数等值线； （3）平行移动目标函数等值线，使目标函数在可行域范围内达到最优。 三、图解法只能适用于模型中仅含两个变量的问题 再看书上的例1 其他情况 由图解法得到的启示 解的情况有：唯一最优解；无穷最优解；无界解；也有无解（可行区矛盾或者不存在） 可行域若存在，则它是个凸多边形，为凸集 若线性规划问题的最优解存在，它一定可以在可行域的某一个顶点上得到 若在两个顶点上同时得到最优解，则该两点连线上的所有点都是最优解，即LP有无穷多最优解 若可行域非空有界，则一定有最优解 解题思路：先找出凸集的任一顶点，计算顶点处的目标函数值；依次比较，目标函数值最大的即为最优解 2.1.3 线性规划问题的标准形式 标准形式 目标函数为寻求最大 约束条件除决策变量约束为非负约束外（Xi ≥0 ），其余为等式约束，且b≥0 如果不满足这些条件或者要求，均可“改造”成标准形式。改造方式如下： 1、如果目标函数为min Z，则将右边乘以（-1） 如果bi0（即不满足b为非负条件）,则将该式两边同乘（-1） 2、如果约束条件为不等式 1）当约束条件为“≤”时，如2x1+2x2 ≤12，增加一个非负变量x3，使得2x1+2x2 +x3=12 松弛变量(slack variable) 2）当约束条件为“≥”时，如10x1+12x2 ≥18，增加一个非负变量x4，使得10x1+12x2 -x4=18 过剩变量(surplus variable) 新增加的决策变量，在目标函数中的系数为零 3、如果xj无约束，即它的取值可能为正，可能为负，还可能为零，则令 Xj= xj′- xj′′ 其中 xj′≥0， xj′′≥0 这样，原来的一个变量变成了二个变量 4、如果xj≤0,令xj′=-xj 其中 xj′≥0 例子 将下例线性规划问题化为标准形式 问题 目标函数追求最小，而不是最大 x3取值无约束 第一个约束方程为“≤”，第二个约束方程为“≥” 第三个约束方程为等式 2.1.4 线性规划问题解的概念 对于标准形式的线性规划： max z=cX （a） AX=b X≥0 （b） 线性规划问题就是求解X，要保证X满足约束条件，有使目标函数取得最大 可行解(feasible solution)——满足约束条件（b）的点X=（x1，x2，…，xn）T称为该LP的一个可行解； 可行域(Feasible Region)——所有可行解组成的集合，也称为可行解集； 最优解(optimal solution)——使目标函数值达到最大的可行解 3．基、基变量、非基变量 (base, basic variable, nonbasic variable) 设约束方程的系数矩阵A中，有m个线性无关的列向量， 且设 B=（P1，P2，…，Pm）线性无关，则称B为该LP的一个基； 相应的 P1，P2，…，Pm——为基向量； 与之对应的变量 x1，x2，…，xm——基变量，记为： XB= （x1，x2，…，xm）T ； 其余的向量为非基向量，记为： N=（Pm+1，Pm+2，…，Pn）； 其余的变量为非基变量 ，记为： XN=（xm+1，xm+2，…，x