第5章线性规划方法

运筹学概念整理

名解5、简答4、建模与模型转换2、计算5~6

第1章 线性规划与单纯形法(计算、建模:图解法)

线性规划涉及的两个方面：使利润最大化或成本最小化

线性规划问题的数学模型包含的三要素：

一组决策变量：是模型中需要首确定的未知量。

一个目标函数：是关于决策变量的最优函数，max或min。

一组约束条件：是模型中决策变量受到的约束限制，包括两个部分：不等式或等式；非负取值（实际问题）。

线性规划问题(数学模型)的特点：目标函数和约束条件都是线性的。

1.解决的问题是规划问题；

2解决问题的目标函数是多个决策变量的线性函数，通常是求最大值或最小值；

3解决问题的约束条件是多个决策变量的线性不等式或等式。

图解法利用几何图形求解两个变量线性规划问题的方法。

求解步骤：第一步：建立平面直角坐标系；

第二步：根据约束条件画出可行域；

第三步：在可行域内平移目标函数等值线，确定最优解及最优目标函数值。

LP问题的解：（原因）

唯一最优解、无穷多最优解（有2个最优解，则一定是有无穷多最优解）

无界解（缺少必要的约束条件）、无可行解（约束条件互相矛盾，可行域为空集）

标准形式的LP模型特点：目标函数为求最大值、约束条件全部为等式、约束条件右端常数项bi全部为非负值，决策变量xj的取值为非负

● 线性规划模型标准化（模型转化）

(1) “决策变量非负”。若某决策变量 xk 为“取值无约束”(无符号限制)，令：xk = x’k – x”k ，(x’k≥0, x”k ≥0) 。

(2) “目标函数求最大值”。如果极小化原问题minZ = CX，则令Z’ = – Z，转为求 maxZ’ = –

CX 。注意：求解后还原。

(3) “约束条件为等式”。对于 “≤”型约束，则在“≤”左端加上一个非负松弛变量，使其为等式。 对于“≥”型约束，则在“≥”左端减去一个非负剩余变量，使其为等式。

(4) “资源限量非负”。若某个 bi < 0，则将该约束两端同乘“–1” ，以满足非负性的要求。

1 第５章 整数规划（割平面法）

求解整数规划问题：

Max Z=3x1+2x2

2x1+3x214

4x1+2x218

x1,x20，且为整数

解：首先，将原问题的数学模型标准化，这里标准化有两层含义：（1）将不等式转化为等式约束，（2）将整数规划中所有非整数系数全部转化为整数，以便于构造切割平面。从而有：

Max Z=3x1+2x2

2x1+3x2+x3=14

2x1+x2+x4=9

x1,x20，且为整数

利用单纯形法求解，得到最优单纯形表，见表1：

表1

CB XB b 3 2 0 0

X1 X2 X3 X4

2 X2 5/2 0 1 1/2 -1/2

3 X1 13/4 1 0 -1/4 3/4

j 59/4 0 0 1/4 5/4

最优解为：x1=13/4, x2=5/2, Z=59/4

2 01234567891001234567892x1+3x2=142x1+x2=9BAC

根据上表，写出非整数规划的约束方程，如：

x2+1/2x3-1/2x4=5/2 (1)

将该方程中所有变量的系数及右端常数项均改写成“整数与非负真分数之和”的形式，即：

(1+0)x2+(0+1/2)x3+(-1+1/2)x4=2+1/2

把整数及带有整数系数的变量移到方程左边，分数及带有分数系数的变量称到方程右边，得：

x2 - x4-2 =1/2-(1/2x3+1/2x4) (2)

由于原数学模型已经“标准化”，因此，在整数最优解中，x2和x4也必须取整数值，所以(2)式左端必为整数或零，因而其右端也必须是整数。又因为x3,x40，所以必有：

1/2-(1/2x3+1/2x4)<1

3 由于(2)式右端必为整数，于是有：

1/2-(1/2x3+1/2x4)0 (3)

或

x3+x41 (4)

这就是考虑整数约束的一个割平面约束方程，它是用非基变量表示的，如果用基变量来表示割平面约束方程，则有：

第5章 优化问题

5.1 线性规划问题

线性规划问题是目标函数和约束条件均为线性函数的问题，MATLAB6.0解决的线性规划问题的标准形式为：

min nRxxf

sub.to：bxA

beqxAeq

ubxlb

其中f、x、b、beq、lb、ub为向量，A、Aeq为矩阵。

其它形式的线性规划问题都可经过适当变换化为此标准形式。

在MATLAB6.0版中，线性规划问题（Linear Programming）已用函数linprog取代了MATLAB5.x版中的lp函数。当然，由于版本的向下兼容性，一般说来，低版本中的函数在6.0版中仍可使用。

函数 linprog

格式 x = linprog(f,A,b) %求min f ' *x sub.to bxA线性规划的最优解。

x = linprog(f,A,b,Aeq,beq) %等式约束beqxAeq，若没有不等式约束bxA，则A=[ ]，b=[ ]。

x = linprog(f,A,b,Aeq,beq,lb,ub) %指定x的范围ubxlb，若没有等式约束beqxAeq ，则Aeq=[ ]，beq=[ ]

x = linprog(f,A,b,Aeq,beq,lb,ub,x0) %设置初值x0

x = linprog(f,A,b,Aeq,beq,lb,ub,x0,options) % options为指定的优化参数

[x,fval] = linprog(…) % 返回目标函数最优值，即fval= f ' *x。

[x,lambda,exitflag] = linprog(…) % lambda为解x的Lagrange乘子。

[x, lambda,fval,exitflag] = linprog(…) % exitflag为终止迭代的错误条件。

实用标准文案

精彩文档 第五章 整数规划

主要内容：1、分枝定界法；

2、割平面法；

3、0－1型整数规划；

4、指派问题。

重点与难点：分枝定界法和割平面法的原理、求解方法，0－1型规划模型的建立及求解步骤，用匈牙利法求解指派问题的方法和技巧。

要 求：理解本章内容，熟练掌握求解整数规划的方法和步骤，能够运用这些方法解决实际问题。

§1 问题的提出

要求变量取为整数的线性规划问题，称为整数规则问题（简称IP）。如果所有的变量都要求为（非负）整数，称之为纯整数规划或全整数规划；如果仅一部分变量要求为整数，称为混合整数规划。

例1 求解下列整数规划问题

211020maxxxz

为整数21212121,0,13522445xxxxxxxx

如果不考虑整数约束，就是一个线性规划问题（称这样的问题为原问题相应的线性规划问题），很容易求得最优解为：96max,0,8.421zxx。

实用标准文案

精彩文档 用图解法将结果表示于图中画“+”号的点都是可行的整数解，为满足要求，将等值线向原点方向移动，当第一次遇到“+”号点（1,421xx）时得最优解为1,421xx，最优值为z=90。

由上例可看出，用枚举法是容易想到的，但常常得到最优解比较困难，尤其是遇到变量的取值更多时，就更困难了。下面介绍几种常用解法。

§2 分枝定界法

分枝定界法可用于解纯整数或混合的整数规划问题。基本思路：设有最大化的整数规划问题A，与之相应的线性规划问题B，从解B开始，若其最优解不符合A的整数条件，那么B的最优值必是A的最优值*z的上界，记为z；而A的任意可行解的目标函数值是*z的一个下界z，采取将B的可行域分枝的方法，逐步减少z和增大z，最终求得*z。现举例说明：

例2 求解A

219040maxxxz