线性规划与单纯形法

第二章 线性规划问题及单纯形法n 线性规划问题及其数学模型 n 图解法 n 单纯形法原理n 单纯形法计算步骤n 单纯形法的进一步讨论n 数据包络分析第一节 线性规划问题及其数学模型线性规划在经营管理中，常常用来解决有限资源（人、财、物）的合理分配问题。在经营管理中，几乎一切问题都与有限资源的合理分配利用有关。线性规划为解决有限资源的合理分配利用提供了一个有效的数学工具。 建立线性规划数学模型是解决线性规划问题的一个重要步骤。建立的线性规划数学模型是否真正的反映客观实际，数学模型本身是否正确，都直接影响求解结果，从而影响决策结果，所以，建立正确的线性规划模型尤为重要。下面举例说明线性规划数学模型的建立。一、线性规划数学模型的建立某厂利用 A、 B两种原料，生产甲、乙两种产品，有关数据如下：例 1：（产品组合问题）产品名称甲 乙单位产品消耗原料原料名称可供利用的原料数量（ T/日）681 22 1AB产品售价 （千元 /T） 3 2根据市场调查，有如下资料：1.乙产品的需求量至多 2 T/日 ;2.乙产品的需求量比甲产品的需求量至多大 1 T/日。求该厂产值最大的 生产方案 。提出三个问题大家考虑：1.问题的未知数是什么？ 设未知数2.以什么准则进行决策？ 目标函数3.约束条件是什么？ 约束方程这里生产方案指的是如何安排甲、乙产品的产量。显然，产量是未知数。 设：甲产品的产量为 x1 T/日乙产品的产量为 x2 T/日 决策准则是产值最大，用 Z 代表产值，则有： Z=3x1+2x2 Z 是 x1、 x2 的函数，称为目标函数，目标是求极大值，即： max Z= 3x1+2x2 约束条件（分三部分：资源限制、市场限制、非负限制）x1+2x262x1+x28x22x2 -x11x1， x20约束条件 资源限制市场限制非负限制2万 m31.4万 m32万 m31.4万 m3整理得数学模型：目标函数： min z = 1000 x1 + 800 x2约束条件： s.t. x1 10.8 x1 + x2 1.6x1 2x2 1.4x1 0， x2 0例 3、配料问题（ min, )设 x1, x2分别代表每粒胶丸中甲、乙两种原料的用量某厂生产一种胶丸，已知如下资料：例 4、合理下料问题用 7.4m长的钢筋，分别截取 2.9m、 2.1m、 1.5m各至少100根，要求用料最少。设 xj 分别代表采用切割方案 18所需 7.4米的钢筋的数量。二、线性规划问题的共同特征 每一个问题都用一组决策变量 (x1， x2， ， xn)表示某一方案；这组决策变量的值就代表一个具体方案。一般这些变量取值都是非负的。 存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。 都有一个要求达到的目标，它可用决策变量的线性函数（称为目标函数）来表示。按问题的不同，要求目标函数实现最大化或最小化 。三、线性规划数学模型的一般表示方式求解线性规划问题的任务是：在满足约束条件的所有 (x1， x2， ， xn)（可行解）中求出使目标函数达到最大 (小 )z 值的决策变量值 (x1*， x2*， ， xn*)（最优解）。 1.和式2.向量式3.矩阵式课堂作业：建立线性规划模型某城市在一昼夜间，市内交通需要车辆数如图，对车辆的需求在昼夜间是变化的，车辆的工作制度是一天连续工作 8小时，派车时间在各时间间隔的端点，一旦派出，就连续工作 8小时。求保证需要的最小车辆数。车辆数时间0 4712 16 20 24481248121084派车时间在各时间间隔的端点，一旦派出，就连续工作 8小时。设：各时间间隔所派车辆数为 xj j=1， 2， ， 6则有：min Z=x1+x2+x3+x4+x5+x6x1+x64x1+x28x2+x3 10x3+x47x4+x512x5+x6 4x1， x2， x3， x4， x5， x6 0第二章 线性规划问题及单纯形法n 线性规划问题及其数学模型 n 图解法 n 单纯形法原理n 单纯形法计算步骤n 单纯形法的进一步讨论n 数据包络分析第二节 图 解法对模型中只含 2个变量 的线性规划问题，可以通过在平面上作图的方法求解。一、图解法的步骤 1.等直线法 x1x20 4Q2(4,2)Q1Q3Q44x1=164x2=12x1+2x2=82x1+3x2=031.建立平面直角坐标系；4 向着目标函数的优化方向平移等值线，直至得到等值线与可行域的最后交点，这种点就对应最优解。 2.找出表示每个约束的 半平面 ，所有半平面的交集是可行域（全体可行解的集合）；3.画出目标函数的 等值线 ；2.试算法x1x20 4Q2(4,2)Q1Q3Q44x1=164x2=12x1+2x2=82x1+3x2=03最优解在顶点达到：O点： X1=0, X2=0, Z=0Q1: X1=4, X2=0, Z=8Q2: X1=4, X2=2, Z=14Q3: X1=2, X2=3, Z=10Q4: X1=0, X2=3, Z=6二、线性规划问题解的存在情况1.存在唯一最优解x1x20 4Q2(4,2)Q1Q3Q44x1=164x2=12x1+2x2=82x1+3x2=03如例 12.有无穷多最优解若将例 1目标函数变为 max z = 2x1+ 4x2，则问题变为存在无穷多最优解。如图 :x1x20 4Q2(4,2)Q1Q3Q44x1=164x2=12x1+2x2=82x1+4x2=033. 有无界解z可行域可伸展到无穷，由