运筹学南华大学经济管理学院 曾经莲运筹帷幄 ， 决胜千里1定义1第一章 线性规划与单纯形法线性规划是运筹学的一个重要分支。1947年丹捷格提出 了一般线性规划问题求解的方法单纯形法。知识点： 线性规划问题的有关概念 LP（linear programming）SLP（Standard ）的转换 用单纯形法求解线性规划问题21 线性规划问题及其数学模型u例1【经典例题】:某工厂在计划期内要安排生产I、II两种 产品。已知生产单位产品所需的设备台时及A、B两种原材料 的消耗，如表11所示。该工厂每生产一件产品I可获利2元 ，每生产一件产品II可获利3元。问I、II两种产品的产量各 为多少时，使该工厂获取最大利润？产品I产品II设备128台时 原材料A4016kg原材料B0412kg表1-11.1 问题提出3 分析设x1，x2分别表示在计划期内产品I、II的产量。III汇总汇总约约束条件目标标设备设备12x1+2x28台时时 原材料A404x116kg 原材料B044x212kg 产产量x1x2 单单位利润润23 利润润2x13x22x1+3x2max4 建模该生产计划问题可用数学模型表示为：目标函数 max z2x13x2约束条件 x12x284x1 164x2 12x1，x2 05 性质：线性规划是一个线性的条件极值问题，可分为两 类：当一项任务确定后，如何统筹安排尽量做到以最小 的人力、财力、物力等资源去完成。已知一定数量的人力、物力、财力等资源，如何安 排使用它们使完成的任务（或创的价值、实现的利 润等）最多。 线性规划定义：对于求取一组变量Xj（j1，2，3n) 使得它满足线性约束条件的目标函数取得极值的一类最 优化问题。6 特征（P10）每个问题都用一组决策变量（x1， x2 ， xn ）表示某一方案；这组决策变量的值就代表一个具体方案 。一般这些变量取值是非负的。存在一定的约束条件，这些约束条件可以用一组线性 等式或线性不等式来表示。都有一个要求达到的目标，它可用决策变量的线性函 数（称为目标函数）来表示。按问题的不同，要求目 标函数实现最大化或最小化。满足以上三个条件的数学模型称为线性规划的数学模型。7n线性规划数学模型的一般形式 目标函数 :max（min）zc1x1+ c2x2 + cnxn (1.1)约束条件：a11x1 + a12x2 + + a1nxn (=, )b1 a21x1 + a22x2 + + a2nxn (=, )b2 (1.2)am1x1 +am2x2 + + amnxn(=, )bmx1, x2, xn 0 (1.3)目标函数中cj为价值系数；称为约束条件中aij为技术系数, bi为限额系数；（1.3）也称为变量的非负约束条件。81.2 图解法 可行解，可行解集，可行域 图解法的步骤建立平面直角坐标系画出可行域作出目标函数等值线，求最优解 唯一最优解、无穷多最优解、无界解、无可行解9n例1的图解法在以x1、 x2为坐标轴的直角坐标系中，非负条件x1 ， x2 0是指第一 象限。例1的每个约束条件都代表一个半平面。例1的所有约束条件 为半平面交成的区域（见图中的阴影部分） 。阴影区域中的每一个 点（包括边界点）都是这个线性规划问题的解（称可行解）。此阴 影区域是例1的线性规划问题的解集合，称为可行域。在这个坐标平面上，目标函数z 2 x1 3 x2可表示以z为参数、2/3 为斜率的一族平行线： x2 （2/3） x1 z/3 。位于同一直 线上的点，具有相同的目标函数值，因而称它为“等值线”。当z值 由小变大时，直线x2（2/3） x1 z/3 沿其法线方向向右上方 移动。当移动到Q2点时，使z值在可行域边界上实现最大化。这就得 到了例1的最优解Q2，Q2点的坐标是（4，2）。于是可计算出z 14。10图1-211图1-3 目标值在（4，2）点，达到最大值14目标函数12一般线性规划问题可能出现的几种情况:（1）无穷多最优解(多重最优解)，见图1-4（2）无界解，见图1-5-1（3）无可行解，见图1-5-213图1-4 无穷多最优解(多重最优解) 目标函数 max z=2x1+4x2 图1-4 无穷多最优解(多重最优解)14图1-5-1 无界解15无可行解当存在矛盾的约束条件时，为无可行域。如果在例1的数学模型中增加一个约束条件: 该问题的可行域为空集，即无可行解， 16增加的约束条件图1-5-2 不存在可行域 17习题1 图解法解下列线性规划问题(1) MaxZ 3x14x2 S.T 2x1+x21 x1+2x2 42x1+x2 6x1 x2 1X1,x20(2) MinZ 5x1-6x2 S.Tx1+2x2 43x1+2x2 6x1 2 x2 0X1,x20181.3 线性规划问题的标准型式标准式中要求bi019线性规划问题的几种表示形式20用向量表示为：21用矩阵表示为：22如何变换为标准型：目标函数的标准化：Min Z=CX MaxZ =CX ( Z= Z)负右端系数的转换：当bi0时，两端同乘（1）约束条件的标准化：对于“型，则在不等式的左端加一非负变量（松弛变量），对于“型，则在不等式的左端减一非负变量（剩余变量）。决策变量的转换： 当xj0时，令xjxj，则xj0； 如xj无符号限制，则令xjxjxj/， xj，xj/ 023 例3：将下述线性规划模型（例1）化为标准型目标函数 max z2x13x2约束条件 x12x2 84x1 16 4x2 12x1，x2 024 在各不等式中分别加上一个松弛变量x3， x4， x5，使不等式变为等式，便得到标准型。目标函数 max z2x13x2约束条件 x12x2 x3 84x1 x4 16 4x2 x5 1x1，x2 ， x3 ， x4 ， x5 025 目标函数 min zx12x2 3x3 约束条件x1x2 x3 7x1 x2 x3 2 3x1 x2 2x3 5x1，x2 0， x3 为无约束例4：将下述线性规划问题化为标准型26 解：根据题意用x4 x5 替换x3替换，其中x4 ， x5 0在第一个约束不等式号的左端加入松弛变量x6在第二个约束不等式 号的左端加入剩余变量x7令z z令，把求minz改为求maxz。得标准型目标函数 max zx12x2 3（x4 x5 ） 约束条件 x1x2 （x4 x5 ） x6 7x1x2 （x4 x5 ） x7 23x1x2 2（x4 x5 ） 5x1，x2 ， x4 ， x5 ， x6 ，x70 27习题2：将下列模型化成标准型 min zx1x24x3 s.t 3x1 4x3- 9x1 +x2 65x1 +2x3 16x1 0,x2 0 ,x3无符号限制解：令zz， x1x， x3x3 x3 引入松弛变量x4， x6, 剩余变量x5， 并加以整理得：max z x1 +x24 x3 +4x3 s.t 3x1 + 4 x3 4x3 x4 9x1 +x2 x5 6-5x1 +2x3 2x3 + x6 16x1 ，x2 ， x3 ，x3 ， x4，x5 ， x6 028习题3：将下列模型化成标准型 min zx1x23x3 s.t x1 +x2 x3 =105x1 -7x2 +3 x3 -8x1 +X2 2 x3 18x1 0 , x2 0, x3无符号限制29习题5解答解:令x2x2， x3x3x3 ,Z=-Z/引入剩余变量x4， x5 ，松弛变量x6，并加以整理得：max z x1 x2 3 x33x3“s.t x1 x2 x3 x3 =10 5x1 7x2 3 x3 3x3 x4 = 8x1 x2 x5 = 2 x3 x3 x6 =18x1 ， x2 , x3，x3 ， x4， x5， x6 0301.4 线性规划问题的解的概念Max zCXs.t AXbX0其中A爲mn阶矩阵，mn，A的秩为m。可行解：满足约束条件的解称为线性规划问题的可行解。最优解：可行解中使目标函数达到最大值的解。基：中任何一组m个线性无关的列向量构成的子矩阵为，称B该问题的一个基，与这些列向量对应的变量称为的基变量，其余变量称为 的非基变量。基可行解：对于基，令非基变量为零，求得满足式AXb的解，称为 对应的基解；若同时又满足式 ，这种基本解称为基本可行解，基本可行解所对应的基称为可行基。退化解：若基本可行解中某基变量为零，称其为退化解，所对应的极点 为退化极点。31几种解之间的关系 可行解基可行解基解非可行解322 线性规划问题的几何意义2.1 基本概念 定义1 凸集设K是n维欧氏空间的一点集，若任意两点X(1)K，X(2)K 的连线上的所有点X(1)+(1-)X(2)K，(01)；则称K为凸集。 直观地看,就是区域内任两点的连线仍然在区域内。33X(1) , X(2) , ,X(k) 是n维欧氏空间 中的k个点，若有一组数1 , 2 , , k 满足0 i 1 (i=1, ,k)定义2 i =1ki=1有点 x= 1 X(1) + + k X(k)则称点X为 X(1) , X(2) , ,X(k) 的凸组合。凸组合34凸集D, 点 XD，若找不到两个不同的点X(1) , X(2) D 使得X= X(1) +(1- ) X(2) (00 j =1, ,kXj =0 j =k+1, ,n若p1 , , pk 线性相关，必有不全为0的1 , , k使 1 p1 + k pk = 0做 (1 , , k ,0 ,0 )T则有 A 1 p1 + k pk = 041选 min | j =0 0Xj j做 X(1) =X+