线性规划模型_线性规划模型解的步骤_线性规划三大常用题型

线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料.二是生产组织与计划的改进，即合理安排人力物力资源.线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好.一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题。满足线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域。决策变量、约束条件、目标函数是线性规划的三要素。

标准型

描述线性规划问题的常用和最直观形式是标准型。标准型包括以下三个部分：

一个需要极大化的线性函数:

以下形式的问题约束：

和非负变量：

其他类型的问题，例如极小化问题，不同形式的约束问题，和有负变量的问题，都可以改写成其等价问题的标准型。

模型建立

从实际问题中建立数学模型一般有以下三个步骤；

1.根据影响所要达到目的的因素找到决策变量；

2.由决策变量和所在达到目的之间的函数关系确定目标函数；

3.由决策变量所受的限制条件确定决策变量所要满足的约束条件。

所建立的数学模型具有以下特点：

1、每个模型都有若干个决策变量（x1，x2，x3……，xn），其中n为决策变量个数。决策变量的一组值表示一种方案，同时决策变量一般是非负的。

2、目标函数是决策变量的线性函数，根据具体问题可以是最大化（max）或最小化（min），二者统称为最优化（opt）。

3、约束条件也是决策变量的线性函数。

当我们得到的数学模型的目标函数为线性函数，约束条件为线性等式或不等式时称此数学模型为线性规划模型。

例：

生产安排模型：某工厂要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表所示，表中右边一列是每日设备能力及原材料供应的限量，该工厂生产一单位产品Ⅰ可获利2元，生产一单位产品Ⅱ可获利3元，问应如何安排生产，使其获利最多？

解：

1、确定决策变量：设x1、x2分别为产品Ⅰ、Ⅱ的生产数量；

2、明确目标函数：获利最大，即求2x1+3x2最大值；

3、所满足的约束条件：

设备限制：x1+2x2≤8

原材料A限制：4x1≤16

原材料B限制：4x2≤12

基本要求：x1，x2≥0

用max代替最大值，s.t.（subject to 的简写）代替约束条件，则该模型可记为：

max z=2x1+3x2

s.t. x1+2x2≤8

4x1≤16

4x2≤12

x1，x2≥0

解法

求解线性规划问题的基本方法是单纯形法，现在已有单纯形法的标准软件，可在电子计算机上求解约束条件和决策变量数达 10000个以上的线性规划问题。为了提高解题速度，又有改进单纯形法、对偶单纯形法、原始对偶方法、分解算法和各种多项式时间算法。对于只有两个变量的简单的线性规划问题，也可采用图解法求解。这种方法仅适用于只有两个变量的线性规划问题。它的特点是直观而易于理解，但实用价值不大。通过图解法求解可以理解线性规划的一些基本概念。

对于一般线性规划问题： Min z=CX

S.T.

AX =b

X>=0

其中A为一个m*n矩阵。

若A行满秩

则可以找到基矩阵B，并寻找初始基解。

用N表示对应于B的非基矩阵。则规划问题1可化为：

规划问题2：

Min z=CB XB+CNXN

S.T. B XB+N XN = b （1）

XB >= 0， XN >= 0 （2）