用单纯形法求解线性规划问题.docx

目录

TOC\o1-1\h\z\u一．摘要 2

二．实验目的 2

三．实验内容 2

四．建立数学模型 ……………… 3

五．实验原理 5

六．MALTAB程序代码及注释…… 7

七．结果运行测试 13

八．心得与感悟 15

2

2

一．摘要：

线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.研究线性约束条件下线性目标函数的极值问题的数学理论和方法,英文缩写LP。

自1946年G.B.Dantizig提出单纯形法以来，它一直是求解线性规划问题的最有效的数学方法之一。单纯形法的理论根据是：线性规划问题的可行域是 n维向量空间Rn中的多面凸集,其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。通过引入普通单纯形法，依次迭代并判断，逐步逼近，最后得到最优解。若不是，则按照一定法则转换到另一改进的基本可行解，再鉴别；若仍不是，则再转换，按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。

关键字：线性规划，单纯形法，最优值，最优解

二．实验目的：

加强学生分析问题能力，锻炼数学建模能力。

了解并掌握MATLAB软件中的线性规划问题的编程、求解和分析。

利用所学的MALTAB语言，完成对单纯形法问题的编程设计。

三．实验内容：

某商场决定，营业员每周连续工作5天后连续休息2天，轮流休息，据统计，商场每天需要营业员如下：星期一：300，二：300；三：350，四：400，五：480，六：600；日：500；

商场人力资源部应如何安排每天上班的人数才能使商场总的营业员最

少

若商场可以雇佣临时工，上班时间同正式工，若正式工每天工资80，

临时工每天100，问商场是否应雇佣临时工及雇佣多少名？

四．建立数学模型：

从实际问题中建立数学模型一般有以下三个步骤：1.根据影响所要达到目的的因素找到决策变量；

由决策变量和所在达到目的之间的函数关系确定目标函数；

由决策变量所受的限制条件确定决策变量所要满足的约束条件。

当我们得到的数学模型的目标函数为线性函数，约束条件为线性等式或不等式时称此数学模型为线性规划模型。

线性规划问题的标准形式：

由题可知，可设每天上班人数分别应为x1,x2,x3,x4,x5,x6,x7;建立下列数学模型

3

PAGE

PAGE10

将其转化为标准形式为：

IminZ=x

I

+x2

+x,3,+x 4

.+x.5.\+xf6i+x 7

st.. X1 +x4 +xs+xo+x7 - xax1+_x2 +x5+x6 + x7

- x9

=300

==300

xl.

+ x2.

+ x3 +x6 +x7

- x10

==350

Xi + xi +x3+x4

+x1

-x ll

=400

X1+X.2+X3+X4+X5

-x 12

=480

X2 +x3 +x4 +x5+,

..x.6

-x 13

=600

x3 +x4

+x1 +x6 +x勹

- X14=550

x1 ==0 j==1,2,3,4,5,6,7.,8,9,,10,11,12,13.,I4

即

r -n-

n..-nz--

=c_Tx

-s.t. A.x==b

x=O

｀｀

价值向量

约束矩阵

右端向量

c= (I 1 1 11 I10 0 0 0 0 0 0)

...1 0 0 1 1 l 1 - 1 0 0 0 0 0 0

1100111 0-100000

]1[001100-10000

A=11[1001000-1000

11111000000-100

0111110 00000—10

0 0 1 1 1 1 [ 000000-[

b=(300 300 350 400 480 600 550)

五．实验原理：

根据单纯形法的原理，在线性规划问题中，决策变量（控制变量）x1，x2，…xn的值称为一个解,满足所有的约束条件的解称为可行解。使目标函数达到最大值（或最小值）的可行解称为最优解。这样，一个或多个最优解能在整个由约束条件所确定的可行区域内使目标函数达到最大值（或最小值）。求解线性规划问题的目的就是要找出最优解。

最优解可能出现下列情况之一：①存在着一个最优解；②存在着无穷多个最优解；③不存在最优解，这只在三种情况下