优化问题中的数学规划模型 (2)

利润=高价电利润+低价电利润 P=200(u1+u2)+140(v1+v2) Step 4. 寻找约束条件

1. 电量守恒：每月发电量=每月卖出量（2个） 2. 水量守恒：

发电用水量+直接放走量+库存量=原有库存量+来水量（4个） 3. 发电能力限制：4个 4. 水库蓄水量限制：4个 5. 高价电量限制：2个 Step 5. 构成数学模型

max200(u1?u2)?140(v1?v2)s.t.400xA1?200xB1?u1?v1,400xA2?200xB2?u2?v2xA1?yA1?zA1?1900?200xB1?yB1?zB1?850?40?xA1?yA1xA2?yA2?zA2?zA1?130xB2?yB2?zB2?zB1?15?xA2?yA2

400xA1?60000,400xA2?60000200xB1?35000,200xB2?350001200?zA1?2000,1200?zA2?2000800?zB1?1500,800?zB2?1500u1?50000,u2?50000xA1,xA2,xB1,xB2,yA1,yA2,yB1,yB2,zA1,zA2,zB1,zB2,u1,u2,v1,v2?0

【实例3】有4名同学到一家公司参加三个阶段的面试：公司要求每个同学必须首先到秘书处初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队（即在任何一个阶段4名同学的顺序是

一样的）。由于4名同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如下表所示（单位：分钟）：

秘书初试 主管复试 经理面试 15 20 16 10 20 18 10 15 同学甲 13 同学乙 10 同学丙 20 同学丁 8 这4名同学约定他们全部面试完以后一起离开公司。假定现在时间是早上8:00，问他们最早何时离开公司？ Step 1. 寻求决策，即回答什么？ 1. 同学甲、乙、丙、丁的面试次序

1）同学甲、乙、丙、丁每个阶段面试的开始时间 2）先后次序 2. 离开时间 Step 2. 确定决策变量

1. 同学甲、乙、丙、丁参加第j阶段面试的开始时间ti,j； 2. 同学甲、乙、丙、丁面试结束时间：T1，T2，T3，T4 3. 离开时间：T=max{ T1，T2，T3，T4} 4. 先后次序：ri,j，0—1变量 5. 面试时间（已知）：ci,j Step 3. 确定优化目标 Min T

Step 4. 寻找约束条件

1. 单人面试先后次序约束：ti,j+ci,j≤ti,j+1，i=1,2,3,4；j=1,2 2. 每个阶段j在同一时间只能由一个同学参加面试： ti,j + ci,j - tk,j ≤ T ri,k （i,k=1,2,3；j=1,2,3；i

MinT?max{T1,T2,T3,T4}s.t.T1?t1,3?c1,3T2?t2,3?c2,3T3?t3,3?c3,3

T4?t4,3?c4,3ti,j?ci,j?ti,j?1,i?1,2,3,4;j?1,2ti,j?ci,j?tk,j?Tri,k,i,k?1,2,3,4;j?1,2,3;i?ktk,j?ck,j?ti,j?T(1?ri,k),i,k?1,2,3,4;j?1,2,3;i?kti.j?0,Ti?0i,?1,2,3,4;j?1,2,3ri,k?0or1

4．模型的理论求解方法

线性规划问题和整数规划问题是两类非常重要的数学规划问题，它们的求解方法是很多数学规划问题的求解方法的基础。 4.1 线性规划问题的单纯形法 4.1.1 一般的线性规划问题模型

min(或max)z?c1x1?c2x2???cnxns.t.AAA(1)

x?bx?b(1)(2)(2) (1.2)

(3)x?bT(3)其中x???x1,x2,?,xn??列向量。

?Rn(2)(3)b,b为，A(1),A(2),A(3)为矩阵，b(1)，4.1.2 标准的线性规划问题

minz?cxT 其中：x,c?Rn4.13 单纯形法

ms.t.Ax?bx?0,b?R,b?0,A?Rm?n 。

(1.3)

,m?nG.B.Dantzig的单纯形法（Simplex method）是一个顶点迭代算法，即从一个顶点出发，沿着凸多面体的棱迭代到另一个顶点，使目标函数值下降（至少不升），由顶点个数的有限性，可以证明经过有限次迭代一定可以求得最优解或者判定该问题无最优解，这就是单纯形法的基本思想。而几何上一个的顶点对应在代数上的一个基可行解，因此，单纯形法求解线性规划问题只需要关心基可行解。

若线性规划问题(1.3)中：A??I,N?，其中I是一个m阶单位矩阵，且

b1,b2,?,bm?0，即为

minz?c1x1?c2x2???cnxnmniim?s.t.?cbi?1??j?m?1(?cj??caii?1i,j)xj

?a1,m?1xm?1???a1,nxn?b1?x1?x2?a2,m?1xm?1???a2,nxn?b2?????????xm?am,m?1xm?1???am,nxn?bm??xj?0,j?1,2,?,n? (1.4)

则I称为线性规划问题(1.4)的一个基，而对应着基的变量

xj,j?1,2,?,m称为基变量，其余变量xj,j?m?1,m?2,?,n为非基变

量。非基变量均取值零的可行解x???b1,b2,?,bm,0,?,0??T称为基可行

解。

对于式 (1.4)，单纯形法的计算步骤如下： Step 1. 检验各非基变量x的检验系数?jj??cj??ca，若

ii,ji?1m?j?0,j?m?1?,,n，则基可行解已是最优解，计算结束；否则转入

下一步；

Step 2. 若有某个?k(?k?0)对应xk的系数向量pk?0，则此问题无

最优解，停止计算；否则转入下一步；

Step 3. 根据

blal,k?k?max?{j?|?j，确定

xk为进基变量，

???b?设xl?min?i|ai,k?0?，

?ai,k???为对应的基变量，则xl为出基变量，转入

下一步；

Step 4. 以a为主元素进行迭代（即高斯消元法），把xk所对应

l,k的列向量：

?Pk???a1,k,?,al,k,?,am,k?T???0,?,0,1,0,?,0?T

目标函数中

xk也相应消去。将基变量中xl换为xk，重复

Step1—Step4，直到终止。

?max??s.t.【示例】利用单纯形法求解线性规划问题??????w?1000x1?1500x29x1?5x2?3504x1?5x2?2002x1?5x2?150x1,x2?0。

【解】：第一步，构造初始单纯形表

引入松弛变量x3，x4,x5将原问题化成标准形式：

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新教学研究优化问题中的数学规划模型 (2)全文阅读和word下载服务。