文档介绍：线性规划(xiàn xìnɡ ɡuī huá)整数规划规划
第一页，共54页。
一、引言(yǐnyán)
我们从2005年“高教(ɡāo jiào)社杯”全国大学生数模竞
谈起.
其中第二个问题是一个如何(rúhé)来分配有限资源，
从而达到人们期望目标的优化分配数学模型.
这类问题一般可以归结为数学规划模型.
赛的B题“DVD在线租赁”问题的第二问和第三问
第1页/共54页
第二页，共54页。
规划(guīhuà)模型的应用极其广泛，其作用已为越来
来越急速地渗透(shèntòu)于工农业生产、商业活动、军事
行为核科学研究(yánjiū)的各个方面，为社会节省的财富、
创造的价值无法估量.
特别是在数模竞赛过程中，规划模型是最常
见的一类数学模型. 从历年全国大学生数模竞赛
越多的人所重视. 随着计算机的逐渐普及，它越
试题的解题方法统计结果来看，每年至少有一道
题涉及到利用规划理论来分析、求解.
第2页/共54页
第三页，共54页。
二、线性规划(xiàn xìnɡ ɡuī huá)模型
线性规划模型(móxíng)是所有规划模型(móxíng)中最基本、最
例1.（食谱问题）设有 n 种食物(shíwù)，各含 m 种营养
素，第 j 种食物中第 i 中营养素的含量为 aij , n 种
食物价格分别为c1, c2, …, cn，请确定食谱中n 种食
物的数量x1, x2, …, xn，要求在食谱中 m 种营养素
简单的一种.
线性规划模型的标准形式
的含量分别不低于b1, b2, …, bm 的情况下，使得总
总的费用最低.
第3页/共54页
第四页，共54页。
首先(shǒuxiān)根据食物数量及价格可写出食谱费用为
其次(qícì)食谱中第 i 种营养素的含量为
因此上述(shàngshù)问题可表述为：
解
第4页/共54页
第五页，共54页。
上述食谱问题就是一个典型(diǎnxíng)的线性规划问题，
寻求以线性函数的最大（小）值为目标(mùbiāo)的数学模
型.
它是指在一组线性的等式(děngshì)或不等式(děngshì)的约束条件下，
第5页/共54页
第六页，共54页。
线性规划模型(móxíng)的三种形式
⑴ 一般(yībān)形式
目标函数
价值向量
价值系数
决策变量
右端向量
系
数
矩
阵
非负约束
自由变量
第6页/共54页
第七页，共54页。
⑵ 规范(guīfàn)形式
⑶ 标准(biāozhǔn)形式
三种(sān zhǒnɡ)形式的LP问题全都是等价的，即一种形式的LP可以简单的变换为另一种形式的LP，且它们有相同的解 .
以下我们仅将一般形式化成规范形式和标准形式.
第7页/共54页
第八页，共54页。
目标函数(hánshù)的转化
x
o
z
-z
第8页/共54页
第九页，共54页。
约束条件和变量(biànliàng)的转化
①．为了把一般形式的LP问题变换为规范形式，我们必须消除等式约束(yuēshù)，一个等式约束(yuēshù)
可用下述两个不等式约束(yuēshù)去替代
第9页/共54页
第十页，共54页。