线性规划程序.doc

线性规划问题及其数学模型 两个变量问题的图解法 单纯形法原理 单纯形法计算步骤 人工变量及其处理方法 人工变量及其处理方法 3.1.1 线性规划及其数学模型 问题的提出 资源有限和目标确定： 在生产管理和经营活动中，经常会遇到两类问题：一类是（资源有限）如何合理的使用现有的劳动力、设备、资金等资源，以得到最大的效益；另一类是（目标一定）为了达到一定的目标，应如何组织生产，或合理安排工艺流程，或调整产品的成分等，以使所消耗的资源（人力、设备台时、资金、原材料等）为最少。 例如： (1)配载问题：某种交通工具（车、船、飞机等）的容积和载重量一定，运输几种物资，这些物资有不同的体积和重量，如何装载可以使这种运输工具所装运的物资最多？ (2)下料问题：某厂使用某种圆钢下料，制造直径相同而长度不等的三种机轴，采用什么样的下料方案可以使余料为最少？ (3)物资调运：某种产品有几个产地和销地，物资部门应太如何合理组织调运，从而既满足销地需要，又不使某个产地物资过分积压，同时还使运输费用最省？ (4)营养问题：各种食品所含营养成分各不相同，价格也不相等，食堂应该如何安排伙食才能既满足人体对各种营养成分得需要，同时又使消费者得经济负担最少？ 此外，在地质勘探、环境保护……等方面也都有与上述情况类似的问题。 某制药厂生产甲、乙两种药品，生产这两种药品要消耗某种维生素。生产每吨药品所需要的维生素量分别为30Kg，20Kg，所占设备时间分别为5台班，1台班，该厂每周所能得到的维生素量为160kg，每周设备最多能开15个台班。且根据市场需求，甲种产品每周产量不应超过4t。已知该厂生产每吨甲、乙两种产品的利润分别为5万元及2万元。问该厂应如何安排两种产品的产量才能使每周获得的利润最大？ 每吨产品的消耗 每周资源总量 甲 乙 维生素 /kg 30 20 160 设备/台班 5 1 15 解：设该厂每周安排生产甲、乙两种药品的产量分别为x1,x2吨，则有 例2：喜糖问题: 设市场上有甲级糖和乙级糖，单价分别为20元/斤，10元/斤。今要筹办一桩婚事，筹备小组计划怎样花费不超过200元，使糖的总斤数不少于10斤，甲级糖不少于5斤。问如何确定采购方案，使糖的总斤数最大。 解：设采购甲、乙两种糖各x1,x2斤，则 线性规划问题的数学模型 1. 从上述两个例子可以看出，它们有3个共同点 (1)每个问题都有一组变量——称为决策变量 (2)都有一个关于决策变量的函数 (3)每个问题都有一组决策变量需满足的约束条件 2. 线性规划问题定义：将约束条件及目标函数都是决策变量的线性函数的规划问题称为线性规划问题。 3. 建立线性规划问题的数学模型步骤 (1)确定问题的决策变量 (2)确定问题的目标，并表示为决策变量的线性函数 (3)找出问题的所有约束条件，并表示为决策变量的线性方程或不等式 4. 线性规划的数学模型 假定线性规划问题中含n个变量，分别用xj(j=1,…,n)表示，在目标函数中，xj的系数为cj(通常称为价值系数)。xj的取值受m项资源的限制，用bi(i=1,…,m)表示第i 种资源的拥有量，用aij表示变量xj的取值为一个单位时所消耗或含有的第i 种资源的数量(通常称为技术系数或工艺系数)。则上述线性规划问题的数学模型可以表示为 线性规划的标准型 由于目标函数和约束条件内容和形式上的差别，线性规划问题有多种表达式，为了便于讨论和制定统一的算法，规定标准形式如下：(1)目标函数极大化；(2)约束条件为等式且右端项≥0；(3)决策变量≥0。 (1)一般表达式 （2）Σ记号简写式 （3）矩阵形式 式中C=(c1,…,cn) X=(x1,….xn)’ (4)向量形式 式中C,X,b,0的含义与矩阵表达式相同，而 Pj=[aij,a2j,…amj] (j=1,2,…,n)；即A=(p1,p2,…pn) 将非标准形式化为标准形式（5种情况） 目标函数为求极小值 minZ=CX, 则作Z’=-CX, 即maxZ’=-CX 右端项小于0 只需将两端同乘(-1)，不等号改变方向，然后再将不等式改为等式。 例 2x1+x2≥－6，－2x1－x2≤6，－2x1－x2＋x3＝6 约束条件为不等式 当约束条件为“≤”时，则在左边加上一个新变量——称为松弛变量，将不等式改为等式。如x1－2x2≤8，x1－2x2＋x3＝8，x3≥0； 当约束条件为“≥”时，则在不等式左边减去一个新变量——称为松弛变量，将不等式改为等式。如x1－2x2≥8，x1－2x2－x3＝8，x3≥0； 取值无约束的变量 即可正可负，则可引入两个新变量，x’，x”，令x=