运筹学结课论文

运筹学结课论文

题 目：班 级：姓 名：学 号：编 号：

线性规划问题

运筹学线性规划

摘要：运筹学这一名词最早出现于1938年。当时英，美等国盟军在与德国的战争中遇到了许多错综复杂的战略和战术问题难以解决，比如防空雷达的布置问题、护航舰队的编队问题。在中国，最早的运筹学思想有战国时期的田忌赛马，它是对策论的一个典型例子，北宋时期的丁渭造皇宫，它是统筹规划的一个例子。线性规划（Linear Program）是一个成熟的分支，它有效的算法——单纯形法，主要解决生产计划问题，合理下料问题，最优投资问题。如何利用现有的有限资源，最大限度地发挥资源的能力，产生最优的效果，这就是线性规划问题甚至于整个运筹学学科一直在研究的问题

一、线性规划的发展与运用 中国国内：

50年代中期，钱学森、许国志等教授在国内全面介绍和推广运筹学知识

1956年，中国科学院成立第一个运筹学研究室 1957年运筹学运用到建筑和纺织业中

1958年提出了图上作业法，山东大学的管梅谷教授提出了“中国

邮递员问题”

1970年，在华罗庚教授的直接指导下，在全国范围内推广统筹方法和优选法。

1978年11月，在成都召开了全国数学年会，对运筹学的理论与应用研究进行了一次检阅

1980年4月在山东济南正式成立了“中国数学会运筹学会”，1984年在上海召开了“中国数学会运筹学会第二届代表大会暨学术交流会”，并将学会改名为“中国运筹学会”。

国外发展：

1832年法国数学家傅里叶首次提出线性规划的思想；

1939年苏联数学家坎托罗维奇为解决生产组织中的相关问题，如机器负荷的分配、原材料的合理利用等，发表《生产组织与计划中的数学方法》等论文，这是世界上最早研究线性规划的文章；

1947年美国数学家丹齐克首次提出线性规划的概念，并提出了线性规划的一般模型和求解线性规划问题的通用单纯形法，为这门学科奠定了基础；

1951年美国经济学家库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一起获得1975年诺贝尔经济学奖；

与此同时由于电子计算机的发展，出现了许多线性规划软件，可以很方便地求解几千个变量的线性规划问题，使得线性规划的应用范围更加广阔，从解决技术问题的最优设计到工业、农业、商业、交通

运输、军事、经济、管理决策等众多领域都可以发挥作用。

二、线性规划在生产运作管理的问题提出

[例] 吉利玩具厂生产A、B两种高级玩具，主要有结构制造、组装和喷漆等工序。一个玩具

A的利润为450元；一个玩具B的利润为550元。下表给出了工厂各车间在 全部生产某一种玩具时的生产能力，若混合生产时，可对下表中的数据进行线性组合。利用线性规划确定两种产品各生产多少，从而使利润最大，并求出总利润

______________________________________________________________________________ 车间 A B 结构制造 550 550 组装 800 300

喷漆 600 400

在企业投资决策中，经常需要用到线性规划。例如案例二： 随着人们经济水平的不断提高，某投资商决定投资建汽车厂生产大轿车和载重汽车两种型号的的汽车，已知生产每辆汽车所用的钢材都是2吨／辆，该工厂每年的供应的钢材为1600吨，工厂的生产能力是载重汽车2.5小时／辆，大轿车5小时／辆，工厂全年的有效工时为2500小时；已知供应给该厂的大轿车用的座椅400辆／年。据市场调查，出售一辆大轿车可获利4千元，出售一辆载重汽车可获利3千元.问在这些条件下，该投资商如何安排生产才能使工厂获利最大？

1、 分析与建模：该问题是在有限资源约束下求利润最大化的问题， 设x1为生产大汽车的数量，x2为生产载重汽车的数量. 模型：maxZ=4x1+3x2 ST: 2x1+2x2≤1600 5x1+2.5x2≤2500

x1≤400 x1≥0, x2≥0

1、 模型求解（表解式单纯形法）

增加三个变量x3,x4,x5,先将该问题化成标准型: maxZ=4x1+3x2

ST: 2x1+2x2+x3=1600

5x1+2.5x2+x4=2500 x1+x5=400

x1,x2，x3,x4,x5≥0 表解形式如表：

列 行 x 1 2 3 4 5 1 2 3 4 5 X3 X4 X5 zj zj-cj X3 X4 X1 zj zj-cj 0 0 4 c 0 0 0 X1 X2 X3 X4 X5 4 3 0 0 0 2 2 1 0 0 5 2.5 0 1 0 1 0 0 0 1 1600 800 2500 500 400 400 1 2 3 4 5 b θ 4 0 0 0 0 0 -4 -3 0 0 0 0 2 1 0 -2 800 400 0 2.5 0 1 -5 500 200 1 0 0 0 1 400 4 0 0 0 4 1600 0 0 0 0 4

本文来源：https://www.bwwdw.com/article/0est.html