数学规划模型——线性规划问题
title: 数学规划模型——线性规划问题
date: 2020-02-26 20:08:59
categories: 数学建模
tags: [MATLAB, 数学规划模型]
Matlab中线性规划的标准型
标准型
min CTX s.t. AX<=b不等式约束Aeg∗x=beg等式约束lb<=x<=ub上下界约束(也可以当成不等式约束)
向量的内积 ,
c=C1C2...
Cnx=x1x2...
xn,n是决策变量的个数
练习题
min->maxm 加负号不等式约束的标准是<=,>=需要转换变量如果不在约束条件，⽤inf与-inf巧妙转换Matlab 求解线性规划 的函数
[x ,fval] = linprog [ c, A, b, Aeq, beq, lb, ub, X0]
① X0 表⽰给定Matlab迭代求解的初始值 ( ⼀般不⽤给)
② c, A, b, Aeq, beq, lb, ub的意义和 标准型中的意义⼀致
③ 若不存在不等式约束, 可⽤ " [ ] " 替代 A和b
④ 若不存在等式约束, 可⽤ " [ ] "替代 Aeq 和 beq
⑤ 苦某个 x⽆下界或上界, 则设置lb(i)=-inf,ub(i)=+inf
⑥ 返回的 x表⽰⼩值处的 x取值 ; fval表⽰优解处时取得的最⼩值
7.不是所有的线性规划都有唯⼀解，可能⽆解或有⽆穷多的解。
8.如果求的是最⼤值，别忘在最后给fval加⼀个负号。
上⾯三个题的代码 ：
[x, fval]=linprog[c, A, b, [], [], lb][x, fval]=linprog[c, A, b,Aeg, beg, lb][x, fval]=linprog[c, A, b,Aeg, beg, lb]fval=-fval代码
%% Matlab求解线性规划
% [x fval] = linprog(c, A, b, Aeq, beq, lb,ub, x0)
2.线性规划及单纯形法2
1/31/3000-4/32/31009x31-1001
01x21-2/31/30014x1-31000-1-0010-21x31-
-100101x214-2100312x40x5x4x3x2x1bXBCB0
011-3cj由于人工变量x6=x7=0,所以（0,1,1,12,0）T是该线性规划问题的基可行解。于是转入第二阶段
运算：此时达到该LP问题的最优解：X=(4,1,9,0,0)T;目标函数值Z=-2。三、单纯形法中存在的问题
1.存在两个以上的最大正检验数。选择任何变量（对应最大正检验数）作为换入变量。2.最小比值相同。LP问题出现退化现象，
即基变量取值为0000-61/2-203/4010001001x700103-
1/2-121/20x600019-1-81/40x50x7x6x5x4x3x2x1
bXBCB3/4-201/2-6000
cj00-3217/240010001001x70010-153/24
00x6000436-4-3210x13/4x7x6x5x4x3x2x1bXBCB
3/4-201/2-6000cj选取
x1为换入变量；按Bland算法，选取下标最小的x5为换出变量，得下表：此时换出变量为x1，换入变量为x4，迭代
后目标函数值不变，继而出现了循环现象，达不到最优解。解决退化的方法有：“摄动法”、“辞典序法”、Bland规则等197
4年Bland提出Bland算法规则：3.最小比值原则失效-30011-12cj-Zj101-34
x23110-26x30x4x3x2x1bXBCB0032cj经过一次迭代后可得右表
4.在最优表中出现某非基变量检验数为01/3-2/30014x13-10000-36
cj-Zj01/20106x24-1/32/31004x30x5x4x3x2x1b
XBCB-10000-36cj-Zj001018x131/40-3/4103x24
运筹学作业
王程
信管1302
130404026
目录
运筹学作业 .................................................................................. 1
第一章 线性规划及单纯形法 ................................................... 3
第二章 线性规划的对偶理论与灵敏度分析 ......................... 24
第三章 运输问题 ................................................................... 53
第四章 目标规划 ..................................................................... 63
第五章 整数规划 ................................................................... 73
第六章 非线性规划 ................................................................. 85
第七章 动态规划 ................................................................... 94
第八章 图与网络分析 ............................................................. 97
第九章 网络计划 ..................................................................... 99
第一章 线性规划及单纯形法
第二章 线性规划（LP）
§2.1 线性规划数学模型的建立
LP问题提出：苏联：康德洛维奇 1939
一、线性规划数学模型的三要素：
1.决策变量(decision variable)：决策问题待定的量值。用字母（例如X1,X2,···,Xn）来表示可控制的因
素。每一组决策变量的实际值就表示一个具体方案。 2.目标函数（objective function）：MaxZ=CX 或 MinZ=CX；(衡量决策优劣的准则)
特点：（1）单一目标；（2）关于决策变量的线性函数。（定义：课本P20） 3.约束条件(constraint conditions)：s.t. (subject to) 受制于约束；AX≤(≥，=)b
特点：若干关于决策变量的线性函数。
二、LP数学模型的一般形式
（1）繁写形式 目标函数：Max （Min）z = c1 x1 + c2 x2 + … + cn xn 约束条件：
a11 x1 + a12 x2 + … + a1n xn ≤ （ =, ≥ ）b1
a21 x1 + a22 x2 + … + a2n xn ≤ （ =, ≥ ）b2
s.t. …… …… am1 x1 + am2 x2 + … + amn xn ≤ （ =, ≥ ）bm
x1 ，x2 ，… ，xn ≥ 0
（2）向量形式 目标函数：Max （Min） z = CX
≤(≥，=)b
Xj≥ 0 (j=1,2, …,n)
其中，C=(c1 , c2 , … , cn )(价值向量) X= (x1 , x2 , … , xn )T(决策变量向量)
b=(b1 , b2 , … , bm )T (限定向量)
pj= (a1j ， a2j … amj ) T (约束条件系数列向量)
注：矩阵相乘条件：左列=右行 (3)矩阵形式★
目标函数：Max （Min） z = CX
约束条件：
n
jjjxp
