运筹学的线性规划问题

月文档

筹学EquationChapter1Section1课程论文：线性规划问

题

(一)摘要

怒线性规划是运筹学的一个基本分支，其应用及其广泛，其作月已为越

来越多的人所重视，从线性规划诞生至今的儿十年中，随着计算机的逐渐

密

普及，它越来越急速地渗透于工农业生产、商业活动、军事行动和科学研

究的各个方面.为了跟上时代的发展和高节奏生活的需要，对于掌握一些有

关线性规划的问题可以为我们避免很多不必要的麻烦，也可以提高我们的

中生产工作效率，下面就探讨一下关于线性规划的一些简单的问题，及其在

料

现实生活中的应用.

(二)引言

塔封

各类经济活动中，经常遇到这样的问题：在生产条件不变的情况下，

如何通过统筹安排，改进生产组织或计划，合理安排人力、物力资源，组

织生产过程使总的经济效益最好.这样的问题常常可以化成或近似的化成

所谓的"线性规划"(LinearProgramming，简记为LP)问题.

(三)相关理论与预备知识

：1、线性规划的数学模型的一般形式：

孳、〃

：max(或min)Z=工生兀(1.1)

:/=1

套：约束条件；

阴：卜1内+《2工2+…。1,凡4(=2片

：出内+%2工2+…生,卢“((=2笫2

J...................................................(1.2)

：4m+。〃y2+…％居W(=，2次”

：西士,…工〃20(L3)

：目目标函数中J为价值系数；

•第1页共8页

实用文档

称为约束条件中因为技术系数，々为限额系数；

(1.3)也称为变量的非负约束条件.

根据问题的实际背景，首先利用人的智慧，分析约束条件(1.3)中哪些约

束应取等式可使目标最优，假设有〃，个约束取等式；其次根据线性规划理论，

n个决策变量中至少有〃-加个为零的决策变量.n必大于或等于加、这样就将

变量数降至最少，剩下加'个一般不为零(特殊情况其中也有可能为零)的决策

变量，恰好由疝个等式约束方程求得其解.这就是线性规划问题的方法的思想

和基点.

2、运筹学中的线性规划问题一般采用修正单纯形法和单纯形法求解，也可以

采用图解法来求解，下面就探讨应用单纯形法解决线性规划问题的理论，基本

计算步骤及具体实施运算的单纯形法.

思想：单纯形法考虑的是标准形式的LP问题

minz=cTx(2.1)

,s.t.Ax=b(2.2)

x>0(2.3)

单纯形法的基本思想就是先找一个基本可行解，判别它是否为最优解，如不是,

就找一个更好的基本可行解，再进行判别，如此迭代进行，直至找到最优解，

或者判定该问题无界.

(四)算法步骤

步骤:

第一步：找一个初始的可行基B；

第二步：求出对应的典式及检验数向量U

第三步:求媒=max但|/=1,…,〃)；

第四步：若停止;

第2页共8页

实用文档

b

已找到最优解X=及最优值2=以〃；

<XN)16

第五步：若4V0,停止，原问题无界;

h-h

第六步：求min（—^|々位＞0,i=1,•••,/??）=—；

第七步：以为代替4%得到新的基，转第二步.

（五）算例

求解线性规划问题

maxz=3七+4x2-x3+2x4

x,4-x2+x3+x4<25

s.Z.<X]+2X2+x3+2X4<36

Xj>0,j=l,2,---,4

解：把模型化为标准形式

minz'=-3犬]一%+X3-2匕

%+%2+工3+工4+工5=25

X

芭+2X2+当+24+z=36

Xj>0,J=1,2,…,6

故初始单纯表为:

RHS

玉&%4X5工6

34-12（）00

11111025

C*2036

%111

以毛、4为基变量可得一个基本可行解:

第3页共8页

实用文档

X=(0,0,0,0,25,36/

此时z=0,因为刍=max{3,4,2}=4〉0

此时的基本可行解不是最优解

」.[2536]36

X.,/min<————=——

故£为入基变量，4为离基变量，进行迭代得:

RHS

X%

10-3-20-2-72

00

七1/2*1/21-1/27

1018

%1/21/211/2

。=1〉0,故此时的基本可行解不是最优解

故须为入基变量，毛为离基变量，进行迭代:

RHS

演了24

00-4-2-2-1-86

再10102-114

0101-1111

工2

以王，占为基变量可得一个基本可行解：

X=(14,11,0,0,0,0)7

此时才=-86,因为所有的检验数都小于等于0,故此时的基本可行解为最优解.

第4页共8页

实用文档

（六）实际运用

实例：某工厂在计划期内要安排生产I、II两种产品.已知生产产品所需的设备

台时及A、B两种原材料的消耗，如下表所示.该工厂每生产一件产品I可获利

2元，每生产一件产品n可获利3元.问I、II两种产品的产量各为多少时使

该工厂取得最大利润？

产品I产品II

设备128台时

原材料A4016kg

原材料B0412kg

分析：设玉，X2分别表示在计划期内产品T、U的产量•

III汇总约束条件目标

设备12

X1+2X2（8台时

原材料A404E<16kg

原材料

B044X2《12修

产量

X工2

单位利润23

利润max

2Xj3X22%1+3X2

建模：

该生产计划问题可用数学模型表示为:

目标函数maxz=2xl+3x2

X+2J2<8

4玉<16

约束条件

4X2<12

再,x2>0

第5页共8页

实用文档

求解：

把模型化为标准形式

minz'=-2^1-3x2

%+2X2+x3=8

4r,+x4=16

4X2+x5=12

x2,x3,x4,x5>0

则有初始单纯表为:

RHS

X]工2不%工5

230000

121008

4001016

%

04*00112

%

此时以七，%，玉为基变量可能一个基本可行解，X=(o,0,8,16,12)"此时2=0

v&2=max{2,3}=320,此时的基本可行解不是最优解;

又...min{|号与，故以天为离基变量，起为入基变量，进行迭代得:

RHS

演元2七工4%

2000-3/4-9

1*010-1/22

4001016

%

了201001/43

以为七，x4,占为基变量可得一个基本可行解：X=(0,3,2,16,0)7；

第6页共8页

实用文档

此时z，=-9,・.・。=2〉0,故此时的基本可行解不是最优解；

又•・,争=彳，故/为入基变量，当为离基变量，进行迭代得:

玉匕RHS

00-201/4-13

1010-1/22

008

%-412*

01001/43

工2

以芭，x4,%为基变量可得一个基本可行解：X=(2,3,0,8,0)J

此时z=-13,・・・女=；＞0,故此时的基本可行解不是最优解；

又・・・min{*告}=1,故兀为离基变量/为入基变量进行迭代得：

RHS

玉%工3%4不

00-3/2-1/80-14

1001/404

001/24

&-21

011/2