《第1章线性规划与单纯形法第1节课件》由会员分享，可在线阅读，更多相关《第1章线性规划与单纯形法第1节课件（18页珍藏版）》请在金锄头文库上搜索。
1、第一章 线性规划与单纯形法,第1节 线性规划问题及其数学模型,1.1 问题的提出 例1 某工厂在计划期内要安排生产、两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗如下表,该工厂每生产一件产品可获利2元，每生产一件产品可获利3元，问应如何安排计划使该工厂获利最多? 解：设x1和x2分别表示计划生产产品I和II的数量，则有,线性规划的一般模型形式,1.2 图解法,步骤：(1) 建立平面直角坐标系(2) 图示约束条件，确定可行域(3) 图示目标函数，即一条直线(4) 目标函数直线沿法线方向向可行域边界平移，直至与可行域相切为止，从切点中确定最优点,目标值在(4,2)点，达到最大值1
2、4,目标函数,可能出现的几种情况,(1) 无穷多最优解(多重最优解),目标函数 max z= 2x1+4x2,(2) 无界解 (3) 无可行解,由图解法可以看出，对于LP问题(1) 非空可行域是有界或无界凸多边形(2) 若存在最优解，则一定在有界可行域的顶点取到(3) 若两个顶点同时得到最优解，则连线上任一点都是最优解,1.3 线性规划问题的标准形式,利用求和号写成,用向量表示为：,用矩阵表示为：,非标准型化标准型,步骤：(1) 决策变量x0, 令x/=-x，则x/0(2) 取值无约束的变量x= x/- x/, x/0, x/0 (3) 约束条件右端项(限额系数)bi0时，两 端同时乘以(-1)，不等号方向改变(4) 约束条件为”不等式时，左端加上非 负松弛变量，不等式改为等式 约束条件为”不等式时，左端减去非 负剩余变量，不等式改为等式(5) 目标函数最小化min z，取z/=-z，则 max z/=min (-z),例1的数学模型，加松驰变量后化为标准型：,例：将下列LP问题化为标准形式,1.4 线性规划问题的解的概念,约束方程的 解空间,基解,可行解,非可行解,基可行解,退化解,
