线性规划与单纯形法第1节

《线性规划与单纯形法第1节》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章线性规划与单纯形法第1节线性规划问题及其数学模型1.1问题的提出例1某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗如下表资源产品ⅠⅡ拥有量设备128台时原材料A4016kg原材料B0412kg该工厂每生产一件产品Ⅰ可获利2元，每生产一件产品Ⅱ可获利3元，问应如何安排计划使该工厂获利最多?解：设x1和x2分别表示计划生产产品I和II的数量，则有线性规划的一般模型形式1.2图解法步骤：(1)建立平面直角坐标系(2)图示约束条件，确定可行域(3)图示目标函数，即一条直线(4)目标函数直线沿法线方向向可行域边界平移，直至与可行域相切为止，从切点

2、中确定最优点目标值在(4,2)点，达到最大值14目标函数可能出现的几种情况(1)无穷多最优解(多重最优解)目标函数maxz=2x1+4x2(2)无界解(3)无可行解由图解法可以看出，对于LP问题(1)非空可行域是有界或无界凸多边形(2)若存在最优解，则一定在有界可行域的顶点取到(3)若两个顶点同时得到最优解，则连线上任一点都是最优解1.3线性规划问题的标准形式利用求和号写成用向量表示为：用矩阵表示为：非标准型化标准型步骤：(1)决策变量x≤0,令x/=-x，则x/≥0(2)取值无约束的变量x=x/-x//,x/≥0,x//≥0(3)约束条件右端项(限额系数)bi<0时，两端同时乘以(

3、-1)，不等号方向改变(4)约束条件为”≤”不等式时，左端加上非负松弛变量，不等式改为等式约束条件为”≥”不等式时，左端减去非负剩余变量，不等式改为等式(5)目标函数最小化minz，取z/=-z，则maxz/=min(-z)例1的数学模型，加松驰变量后化为标准型：例：将下列LP问题化为标准形式1.4线性规划问题的解的概念约束方程的解空间基解可行解非可行解基可行解退化解