第二十四章--线性规划初步.pptVIP

*第二十四章线性规划初步

(一)本章内容小结

(二)常见问题分类及解法

(一)本章内容小结

一、本章主要内容

1、几个概念：线性规划问题，决策变量，约束条件，目标

函数，可行解，可行解域。最优解，可行基，基变量，单纯

形表。

2、建立线性规划问题的数学模型，图解法，单纯形方法。

二、本章重点、难点

1、重点：如何建立线性规划问题的数学模型，用图解法，

单纯形方法求解线性规划问题。

2、难点：决策变量的选取，用图解法求解时可行解域的确

定，单纯形方法的判断。

三、对学习的建议

复习二次不等式的解法及几何意义，掌握线性代数中有

关矩阵的初等变换，向量的线性相关性。

四、本章关键词

线性规划问题

可行解

可行基

标准形

单纯形

(二)常见问题分类及解法

一、建立线性规划问题的数学模型

应用线性规划方法解决实际问题，其首要的、关键的一

步是建立揭示实际问题本质内容的线性规划问题的数学模型，

通常分以下几个步骤。

①分析问题，搞清实际问题的背景，抓住主要矛盾，明确该

问题所要实现的目标与受到的限制，为了建模方便，可以将已

知条件列成表格的形式。

②将决策中关键的量，即实际问题中待求的量设为决策变量，

并注意到这些决策变量一般都受到非负约束，然后，将问题的

限制条件表示成决策变量的线性等式或不等式。

③明确目标是最大值还是最小值，从所求的实际问题出发，

将目标函数表示为决策变量的线性函数。

例1某厂用A、B、C三种原材料生产甲、乙两种产品。每生

产一件甲种产品耗费材料A为9kg，B为3kg，C为4kg，可获利

700元；每生产一件乙产品需要消耗4kg的A，10kg的B，5kg

的C，可获利1200元，现在原材料360kg的A、300kg的B和

200kg的C，怎样安排生产才能使获得的利润最大？

解

将已知条件列表见表24-1.

表24-1原料消耗表/kg

二、用图解法求解线性规划问题

由二元一次不等式的求解方法，将只含两个决策变量的

线性规划问题的解通过作图求出，其求解步骤如下：

(1)将满足每一个约束条件的解在平面直角坐标系中表示

出来，求出满足所有约束条件的公共解。即可行解域；

(2)做两条目标函数的等值线，并判断因目标函数值的变

化导致等值线位置变化的情况；

(3)平移等值线至可行解域，找出距原点(S=0)最远或

最近的点或线段，若存在，则线性规划问题的最优解存在，

否则，规划问题无解。

解

解

三、利用单纯形法求解线性规划问题

利用单纯形方法求解线性规划问题时首先化为规划问题的

标准形，然后利用单纯形方法的求解步骤，判断方法，通过单

纯形表的变化，最终求出规划问题的最优解或判断规划问题无

解。注意，最后一定给出原规划问题的最优解和最优值。

例4某工厂利用甲、乙、丙三种原料，生产B1、B2、B3、B4

四种产品，每月可供该厂原料甲500t，乙300t，丙200t。生产

一吨不同的产品可获得的利润及生产一吨不同产品所消耗的原

料数量，见表24-2。

表24-2原料消耗表

问工厂每月应如何安排生产计划，使利润最大？

解

表24-3T(B1)单纯形表

表24-4T(B2)单纯形表

表24-4T(B2)单纯形表