第三章线性规划及LINGO求解

的约束条件数等于原问题的变量数； 5)原问题中的每个约束条件(行)对应于对偶问题的每一列，因此，对
原问题的每个约束条件都存在一个对偶变量； 6)对偶之对偶是原问题。
min cx s.t. Ax b (1)
x0
max yb s.t. yA c (2)
y0
对于原问题(1)和对偶问题(2)有：
x3
= 12－2x1－2x2
x4
= 8－x1－2x2
x5 = 16－4x1
x6 = 12－4x2
对目标函数
（1）
Z=2x1+3 x2
（2）
当非基变量x1=x2=0,便得z=0，这时得到一个基本可行解
X
(0)
x1(0)


x 2 (0) x3(0) x 4 (0)

x5 (0) x6 (0)
2. 线性规划的基本算法——单纯形法 用单纯法求解时，常将标准形式化为：
min f = cx (or max f=cx)
s.t. A x =b
(1)
这里
x≥0
A=(aij)m×n , b=(b1, b2, …, bn)T,
x = (x1, x2, …, xn)T c=(c1,c2, …, cn)
例 min z = 10x1 + 9x2 s．t．6x1 + 5x2 ≤ 60 10x1 + 20x2 ≥ 150 x1 ≤ 8 x1, x2 ≥ 0
于是 f = cBxB + cNxN , Ax = BxB + NxN = b, 则 xB = B-1b-B-1N xN , f = cBB-1b + (cN – cBB-1N)xN
令非基变量 xN = 0, 解得基变量 xB = B 1 b, 称(xB, xN)为基解. 基解的所有变量的值都非负，则称为基可行解，此时的基称为可行基.

线性规划应用及求解华北理工大学管理学院华北理工大学机械工程学院063210摘要：工农业生产、交通运输、商业贸易等行业为了提高效益，合理安排有限的人力和物力资源，最合理的组织生产过程，通常会用到线性规划的模型。

数学规划能够为更好的配置资源、组织生产提供理论和方法，包括线性规划、非线性规划、整数规划、多目标规划等很多分支。

其中线性规划是在现代管理中应用最广、理论比较完善的一个部分。

本文主要介绍线性规划的数学模型和求解方法。

关键词：线性规划；实际应用；Lingo求解1.引言线性规划（Linear programming,简称LP），是运筹学中研究比较早、发展比较快的一个重要方法，线性规划应用比较广泛、方法成熟。

它是帮助人们进行科学管理的一种数学方法。

线性规划被广泛应用于军事作战、经济分析、经营管理和工程技术等方面。

它为合理地利用有限的人力、物力、财力等资源作出的最优决策，提供科学的依据。

运筹学，是现代管理学的一门重要专业基础课。

它是20世纪30年代初发展起来的一门新兴学科，其主要目的是在决策时为管理人员提供科学依据，是实现有效管理、正确决策和现代化管理的重要方法之一。

该学科应用于数学和形式科学的跨领域研究，利用统计学、数学模型和算法等方法，去寻找复杂问题中的最佳或近似最佳的解答。

1.线性规划模型及求解方法1、线性规划模型的标准形式如下：2、线性规划的图解法图解法可分为两步进行。

第一步，根据约束条件画出与约束条件相应方程的直线，由这些直线共同确定的区域即为可行解的区域（满足约束条件的决策变量集合）；第二步，画出目标函数的等值线，然后平行移动至与可行区域边界“相切”之点，此点即为最优点，相应的坐标[x1 x2]T即为最优解。

3、单纯形法单纯形法要求先将模型化为标准型。

把最大化、等式约束型的线性规划称为线性规划的标准型，即标准型的矩阵形式为其中 ，T ，T ，A=习惯上称 为价格系数向量； 为资源向量，标准型中设； 为技术系数矩阵。

• 在满足一组约束条件下，求一组决策变 量的值，使目标函数达到最优。
精选课件ppt
4
线性规划的特点
❖决策变量连续性：求解出的决策变量值 可以是整数、小数；
❖线性函数：目标函数方程和约束条件方 程都是线性方程；
❖单目标：目标函数是单目标，只有一个 极大值或一个极小值；
❖确定性：只能应用于确定型决策问题。
精选课件ppt
5
例1、生产计划问题
A B 备用资源
煤ቤተ መጻሕፍቲ ባይዱ2
30
劳动日 3 2
60
仓库 0 2
24
利润 40 50
A, B各生产多少, 可获最大利润?
精选课件ppt
6
解:设产品A, B产量分别为变量x1 ， x2 x1 + 2x2 30 3x1 + 2x2 60 2x2 24 x1，x2 0
4x1 + 6x2 + x3+2x4 12 x1 + x2 +7x3+5x4 14
2x2 + x3+3x4 8 xi 0 (i =1,…,4)
精选课件ppt
9
一般式
Max(min)Z=C1X1+ C2X2+…+CnXn
a11X1+ a12X2+…+ a1nXn (=, )b1 a21X1+ a22X2+…+ a2nXn (=, )b2
救灾抢险、消防灭火、制止犯罪的最快反应问
题；控制污染、能源规划、经济布局的最优化
问题，等等。
精选课件ppt
1
• 冯•诺伊曼(Von Neuman)和摩根斯坦 (Morgenstern)1944年发表的 《博弈论与 经济行为》涉及与线性规划等价的对策 问题及线性规划对偶理论

附1：用LINGO求解线性规划的例子一奶制品加工厂用牛奶生产A1、A2两种奶制品，1桶牛奶可以在设备甲上用12小时加工成3公斤A1，或者在设备乙上用8小时加工成4公斤A2。

根据市场需求，生产的A1、A2能全部售出，且每公斤A1获利24元，每公斤A2获利16元。

现在加工厂每天能得到50桶牛奶的供应，每天正式工人总的劳动时间为480小时，并且设备甲每天至多能加工100公斤A1，设备乙的加工能力没有限制。

试为该厂制定一个生产计划，使每天获利最大，并进一步讨论以下3个附加问题：1）若用35元可以购买到1桶牛奶，应否作这项投资？若投资，每天最多购买多少桶牛奶？2）若可以聘用临时工人以增加劳动时间，付给临时工人的工资最多是每小时几元？3）由于市场需求变化，每公斤A1的获利增加到30元，应否改变生产计划？数学模型：设每天用x1桶牛奶生产A1 ，用x2桶牛奶生产A2目标函数：设每天获利为z元。

x1桶牛奶可生产3x1公斤A1，获利24*3x1，x2桶牛奶可生产4*x2公斤A2，获利16*4x2，故z=72x1+64x2约束条件：原料供应：生产A1、A2的原料（牛奶）总量不超过每天的供应50桶，即x1+x2≤50劳动时间：生产A1、A2的总加工时间不超过每天正式工人总的劳动时间480小时，即12x1+8x2≤480设备能力：A1的产量不得超过设备甲每天的加工能力100小时，即3x1≤100非负约束：x1、x2均不能为负值，即x1≥0，x2≥0综上所述可得max z=72x1+64x2s.t.x1+x2≤5012x1+8x2≤4803x1≤100x1≥0，x2≥0显然，目标函数和约束条件都是线性的，这是一个线性规划（LP），求出的最优解将给出使净利润最大的生产计划，要讨论的问题需要考虑参数的变化对最优解和影响，一般称为敏感性（或灵敏度）分析。

LINGO求解线性规划用LINGO求解线性规划时，首先在LINGO软件的模型窗口输入一个LP模型，模型以MAX或MIN 开始，按线性规划问题的自然形式输入（见下面例子所示）。