6.5线性规划初步

6.5线性规划初步一、线性规划的数学模型二、两个变量线性规划问题的图解法三、单纯形法一、线性规划的数学模型1．线性规划问题实例例5．1

（配料问题）某工厂在计划期内要生产甲、乙两种产品，已知生产单位产品所需要的设备台时，A、B两种原材料的消耗以及每件产品可获得的利润见下表．问应如何安排生产计划使得该工厂获得利润最多？产品消耗材料甲乙资源限量设备１２8（台时）原材料Ａ４０17(千克)原材料Ｂ０４12（千克）单位产品利润（万元）54解设、分别表示在计划期内产品甲、乙的产量，，表示利润．由于资源的限制有利润的最大化，受条件这就是该问题的线性规划问题的数学模型．的限制．例5．2

（运输问题）在A1、A2两个粮库里分别装有6吨玉米和102吨玉米，要运到B1、B2、B3三个市场去出售．三个市场的需求量分别是34吨、75吨、49吨，各仓库到各市场的运价（元/吨）见表6．3．如何调运，才能使总运费最省？表6．3仓库到市场的运价表单位元/吨市场运价仓库B1B2B3

A1607090

A2758070解以表示从仓库运到市场的玉米数量，

显然

根据分析，将其转化为数学问题：就是求一组变量的值，使它满足限制条件：

并使运费最小，即例5．3某商业银行开展贷款业务，有两种方案可供选择．方案Ａ每一元贷款一年后可获利润0．7元；方案Ｂ每一元贷款两年后可获利润２元．在方案Ｂ中，要求贷款的时间是两年的倍数，要想在第三年年底所获本利最多，应该怎样贷款1000000元？按方案Ａ进行投资，投资元到第三年年底的本利和为（元），按方案Ｂ进行投资，投资元到第二年年底的本利和为解设方案A的投资为元，方案Ｂ的投资元．（元），然后再把元按方案Ａ进行投资到第三年年底的本利和为，因此，到第三年年底商业银行可获得本利和为．由此题的条件可知，根据以上分析将其转化为数学问题就是求满足约束条件下，使的解．2．线性规划问题的标准形式目标函数为：约束条件为：在约束条件中，称为决策变量．这种形式的线性规划问题称为线性规划问题的标准形式．其特征为：（１）所有约束条件都由等式表示，且等式右端的常数非负；（２）决策变量非负；（３）求目标函数的最大值．用矩阵形式表示为：

其中

例5.4

将下列线性规划数学模型化成标准形式．设目标函数约束条件解因为没有非负限制，引入新变量

使；引入松弛变量则化成标准型为二、两个变量线性规划问题的图解法例5．5

求的最大值，约束条件为．解以为横坐标轴，为纵坐标轴，建立坐标系

0C（1.5，1）即，．例５．6

用图解法解线性规划问题解步骤同前题，画出可行域．0阴影部分是无界区域．因为可行域无界，所以找不到的最大值，故无最优解．

三、单纯形法1．线性规划问题的基与解设线性规划问题的标准形式用矩阵表示为：假设矩阵的秩为，则称中任意一个阶满秩矩阵为该线性规划问题的一个基．如果变量所对应的列则称为基变量。其余的个变量称为非基变量．

例5.8

设有线性规划问题，写出它的一个基和该基对应的基变量和非基变量．解约束方程组的系数矩阵显然矩阵是该线性规划问题的一个基它所对应的基变量是非基变量是．

在标准形式的线性规划中，非基变量取零值的可行解叫做线性规划问题的基本可行解，相对应的基叫做基本可行基．最优的基本可行解叫最优解，所对应的基叫最优基．2．单纯形法例5.9

用单纯形法求下面线性规划问题的最优解．解本题的约束条件的线性规划问题已经是标准形，约束方程组的系数矩阵为，，选可行基所对应的基变量就是．1.

作出对应的单纯形表6．４

221001（2）01040001181230000

表中最左边的列是基变量，第一行是所有变量，中间是系数矩阵，最右边的列是常数列，最下边行是目标函数各变量相对应的系数，叫做检验数，该行也叫做检验行．检验行与b列相交的数值为目标函数值的相反数，即非基变量取零时的基本可行解．2．判定最优解（1）若所有检验数均小于或等于零，则已求得的基本可行解就是最优解；（2）若检验数中有正数，正数所对应的列中均为非正数则问题无最优解；（3）若检验数中有正数，且这些正数所在的列中的其他元素有正数则需要继续改进来寻找更优的解．在本例题中,因此不是最优解．3．改进基本可行解（1）选主元当表中有正检验数时，为了使目标函数值尽可能的提高，一般选择检验数大的所在列对应的非基变量为进基变量，用该列上各正数去除同一行中b列上的元素，比值最小者所对应的除数即为主元，用（）标出．主元所对应的变量即为出基变量．在本例题中，最大检验数，最小比值为所以为主元，进基，为出基变量．(2)换基迭代方法是：对单纯形表施行初等行变换使主元变为1，主元所在的列上的其余元素全都化为零．得单纯形表6．5

101-10½10½0(4)000144161/230-3/20-12由表６．5可知，基变量为，非基变量为基本可行解为检验数为，

所以不是最优解，选进基，

由最小比值法选出基，

可得表6．6

001-1-1/4010½-1/810001/4024000-3/2-1/8

由于检验数均小于等于０，因此为最优解．此时，最优解为此时目标函数的最优值为例5．10

用单纯形法解线性规划问题解

为基变量，为非基变量．

列单纯形表，在做题时将单纯形表合并在一起，见下表6．7．

2-１１0023010

-1(1)0016184-330000

10１015001-1-1100111640000-3-12由表可知，最优解为最优解

例5．11用单纯形法解线性规划问题解引入松弛变量把原问题化成标准型则为基变量，为非基变量，可得单纯形表

1-110-3（1）01