当前位置：文档之家 › 线性规划的基本理论和单纯型算法

线性规划的基本理论和单纯型算法

  • 格式：pdf
  • 大小：268.69 KB
  • 文档页数：22

下载文档原格式

  / 22

合集下载

线性规划的理论与实例分析

线性规划的理论与实例分析

线性规划的理论与实例分析线性规划（Linear Programming，简称LP）是一种重要的运筹学工具，常常被应用于生产、物流、金融等领域中的优化问题。

本文将从理论和实例两个角度，介绍线性规划的基本概念、模型及求解方法。

一、线性规划的基本概念线性规划的基本概念包括决策变量、目标函数、约束条件等。

（一）决策变量决策变量是指影响问题结果的变量，通常用x1、x2、 (x)表示。

例如，生产线上的机器数量、产品的产量等都是决策变量。

（二）目标函数目标函数是指要最大化或最小化的某个指标，通常用z表示。

例如，最小化成本、最大化利润等都是目标函数。

（三）约束条件约束条件是指在问题求解中要满足的条件。

例如，不超过机器限制数量、满足生产需求等都是约束条件。

通常用不等式或等式形式表示。

二、线性规划的模型线性规划的一般形式可表示为：最大化或最小化目标函数：Z = c1x1 + c2x2 + … + cnxn约束条件：a11x1 + a12x2 + … + a1nxn ≤ b1a21x1 + a22x2 + … + a2nxn ≤ b2……am1x1 + am2x2 + … + amnxn ≤bm或x1, x2, … , xn ≥ 0 （非负性约束条件）其中，c1、c2、…、cn为各决策变量的系数，a11、a12、…、amn为各约束条件中各决策变量的系数，b1、b2、…、bm为约束条件的值，x1、x2、…、xn为决策变量，非负性约束条件也称为非负约束。

三、线性规划的求解方法线性规划有多种求解方法，这里主要介绍两种：单纯性法和对偶理论。

（一）单纯性法单纯性法是线性规划的一种基本算法，其实质是在各约束条件限制下寻找目标函数最大或最小值。

单纯性法基于以下两个原则：①某个极值点必定满足目标函数的所有约束条件；②各个变量所形成的可行解区域有限，且该区域的可行解点数有限。

单纯性法的具体过程如下：Step 1 建立初始单纯形表将约束条件转化为标准形式，即将约束条件化为”≤“的形式，并加入人工变量，得到初始单纯形表。

第二章线性规划及单纯形法总结

第二章线性规划及单纯形法总结

第一章
工厂需要的原棉存放在三个仓库中，现将原棉运往工 厂以满足工厂生产的需求。已知原棉运到各个工厂的单位 运费如表所示。问使总运费最小的运输方案？
仓库\工厂
1 2 3 需求
1
2 2 3 40
2
1 2 4 15
3
3 4 2 35
库存
50 30 10
2．线性规划数学模型
解：设xij为i 仓库运到 j工厂的原棉数量(i =1,2,3
1．线性规划介绍
第一章
线性规划研究的主要问题： 有一定的人力、财力、资源条件下，如何 合理安排使用，效益最高?
某项任务确定后，如何安排人、财、物， 使之最省?
2．线性规划数学模型
第一章
例1 美佳公司计划制造I，II两种家电产品。已知各 制造一件时分别占用的设备A、B的台时、调试时间及A、 B设备和调试工序每天可用于这两种家电的能力、各售出 一件时的获利情况如表I—l所示。问该公司应制造A、B两 种家电各多少件，使获取的利润为最大？
第一章
j =1,2,3)
minZ= 2x11 + x12+3x13+2x21 +2x22 +4x23 +3x31 +4x32 +2x33 x11 +x12+x13 x21+x22+x23 x31+x32+x33 50 30 10 40
st.
x11 +x21+x31 =
x12 +x22+x32 =
x13 +x23+x33 = xij 0
15
35
2．线性规划数学模型
第一章
练习4 连续投资10万元 A：从第1年到第4年每年初投资，次年末回收本利1.15； B：第3年初投资，到第5年末回收本利1.25，最大投资4万元； C：第2年初投资，到第5年末回收本利1.40，最大投资3万元； D：每年初投资，每年末回收本利1.11。 求：使5年末总资本最大的投资方案。 分析： A 1 x1A 2 x2A x2C x1D x2D x3D x4D x5D 3 x3A 4 x4A 5

第一章 线性规划及单纯形法

第一章 线性规划及单纯形法
37
线性规划问题的标准形式： 线性规划问题的标准形式：
max f = ∑ c j x
j =1 j n
n ∑ aij x j = bi , i = 1,2,L , m j =1 x j ≥ 0, j = 1,2,L , n
日产量（ 日产量（吨） 9 5 7 21
11
）（模型 例2（运输问题）（模型） （运输问题）（模型）
minf = 2 x11 + 9 x12 + 10 x13 + 7 x14 + x21 + 3 x22 + 4 x23 + 2 x24 + 8 x31 + 4 x32 + 2 x33 + 5 x34 x11 + x12 + x13 + x14 = 9 x +x +x +x =5 23 24 21 22 x31 + x32 + x33 + x34 = 7 x11 + x21 + x31 = 3 s.t. x12 + x22 + x32 = 8 x13 + x23 + x33 = 4 x14 + x24 + x34 = 6 xij ≥ 0(i = 1,2,3; j = 1,2,3,4)
18
3、（线性规划）数学模型的三要素 、（线性规划） 、（线性规划 变量/决策变量 决策变量； ①变量 决策变量； 目标函数（ ②目标函数（max/min）； ）； 约束条件。 ③约束条件。
19
决策变量： ①变量/决策变量：指决策者为实现规划目标采 变量 决策变量 取的方案、措施，是问题中要确定的未知量； 取的方案、措施，是问题中要确定的未知量；

线性规划与单纯形法

线性规划与单纯形法

线性规划与单纯形法线性规划（Linear Programming）是一种在资源有限的情况下，通过最优化目标函数来确定最佳解决方案的数学优化方法。

而单纯形法（Simplex Method）则是一种常用的求解线性规划问题的算法。

本文将介绍线性规划与单纯形法的基本概念和运算步骤，以及实际应用中的一些注意事项。

一、线性规划的基本概念线性规划的基本思想是在一组线性不等式约束条件下，通过线性目标函数的最小化（或最大化）来求解最优解。

其中，线性不等式约束条件可表示为：```a1x1 + a2x2 + ... + anxn ≤ b```其中，x1、x2、...、xn为决策变量，a1、a2、...、an为系数，b为常数。

目标函数的最小化（或最大化）可表示为：```min(c1x1 + c2x2 + ... + cnxn)```或```max(c1x1 + c2x2 + ... + cnxn)```其中，c1、c2、...、cn为系数。

二、单纯形法的基本思想单纯形法是由乔治·丹尼尔·丹齐格尔（George Dantzig）于1947年提出的求解线性规划问题的算法。

其基本思想是通过逐步迭代改进当前解，直至达到最优解。

三、单纯形法的运算步骤1. 初等列变换：将线性规划问题转化为标准型，即将所有约束条件转化为等式形式，并引入松弛变量或人工变量。

2. 初始化：确定初始可行解。

通常使用人工变量法来获得一个初始可行解。

3. 检验最优性：计算当前基础解的目标函数值，若目标函数值小于等于零，则该基础解即为最优解。

否则，进入下一步。

4. 基本可行解的变换：选择一个入基变量和一个出基变量，并进行基本变换，得到新的基础解。

5. 迭代求解：根据目标函数值是否小于等于零，判断是否达到最优解。

若达到最优解，则算法终止；若未达到最优解，则返回步骤3进行下一轮迭代。

四、单纯形法的实际应用注意事项1. 线性规划问题的约束条件必须是线性的，且可行解集合必须是有界的。

第2章 线性规划与单纯形法(2)

第2章 线性规划与单纯形法(2)

max z = 20 x1 + 30 x2 3 x1 + 10 x2 ≤ 150, x1 ≤ 30, x1 + x2 ≥ 40, x1 , x2 ≥ 0.
管
max z = 20 x1 + 30 x2 − Mx6 3x1 + 10 x2 + x3 = 150, x1 + x4 = 30, x1 + x2 − x5 + x6 = 40, xi ≥ 0, i = 1, 2,..., 6
管
理
运
筹
学
4
要注意到人工变量是与松弛、剩余变量不同的。 松弛变量、剩余变量它们可以取零值，也可以取 正值，而人工变量只能取零值。一旦人工变量取 正值，那么有人工变量的约束方程和原始的约束 方程就不等价了，这样所求得的解就不是原线性 规划的解了。为了竭尽全力地要求人工变量为零， 我们规定人工变量在目标函数中的系数为－M， M 这里M为任意大的数。这样为了使目标函数实现 最大就必须把人工变量从基变量中换出。如果一 直到最后，人工变量仍不能从基变量中换出，也 就是说人工变量仍不为零，则该问题无可行解。 以下讨论如何解含有人工变量的线性规划问题
• 由于不存在单位矩阵,在第1,2个约束条件加上 一个人工变量x6,x7,并在目标函数中加上-Mx6Mx7得到的线性规划问题：
max f ' = −2 x1 − 3 x2 + 0 x3 + 0 x4 + 0 x5 − Mx6 − Mx7
x1 + x 2 − x 3 + x 6 = 3 5 0, x1 − x 4 + x 7 = 1 2 5, 2 x1 + x 2 + x 5 = 6 0 0, x1 , x 2 , x 3 , x 4 , x 5 , x 6 , x 7 ≥ 0 .

线性规划基本知识

线性规划基本知识

线性规划基本知识线性规划是一种数学优化方法，用于在给定限制条件下最大或最小化线性目标函数。

它是现代数学、工程学和运筹学的基础之一，被广泛应用于制造业、金融、交通、物流等领域。

本文将介绍线性规划的基础知识，包括线性规划问题的表达方式、标准形式、单纯形法求解以及对偶理论等。

一、线性规划问题的表达方式线性规划问题的表达方式通常包含以下部分：1. 决策变量：表示求解问题时需要确定的变量，通常用x1、x2、......、xn表示。

2. 目标函数：表示优化的目标，通常是一个线性函数，用c1x1+c2x2+......+cnxn表示。

3. 约束条件：表示限制决策变量的取值范围，通常是线性等式或不等式，用a11x1+a12x2+......+a1nxn≤b1、a21x1+a22x2+......+a2nxn≤b2、......、am1x1+am2x2+......+amnxn≤bm 表示。

其中，决策变量x1、x2、......、xn的取值范围可以是非负实数集合、整数集合或者其他特定取值范围。

二、线性规划的标准形式通常情况下，线性规划问题都可以通过一些变换，转化为标准形式进行求解。

标准形式的线性规划问题包括以下三个部分：1. 最大化或最小化的目标函数2. 约束条件，所有约束条件都是小于等于号3. 决策变量的取值范围，所有决策变量都是非负实数三、单纯形法求解线性规划问题单纯形法是线性规划问题最常用的求解方法之一，它是一种迭代的过程，通过一系列基本变换（基本可行解、进入变量、离开变量、更新表格）逐步接近最优解。

单纯形法求解线性规划问题的步骤如下：1. 将线性规划问题转化为标准形式。

2. 确定一个初始可行解。

3. 计算第一行表格的系数，并找出最小的系数所在的列，作为进入变量。

4. 确定离开变量，通过将所有正数元素对应的值除以对应进入变量的系数，找到最小的元素所在的行，作为离开变量所在行。

5. 更新表格，完成一次迭代。

6. 重复第三至第五步，直至得到最优解或者确定问题无可行解或是无界问题。

2.3 线性规划(单纯形算法).


（2.3.5）
j m1
线性方程组相对于基B的典式
线性方程组化典式就是把基变量的系数向量化为 单位向量。
典式的右端向量为基变量的取值。
符号 Aj , b , Aj , b 的含义
（2）目标函数 z cT x 的转化 相应于基 B ，记价值向量为 cT (cBT ,cTN ) ，
则
z

cT
j m 1

b
(2.3.8)
x 0
例
min z x1 2x2 x3 8x4 2x5
s.t.
x1 x1 x2
3x4 2x5 1 5x4 x5 3

x1
x3 2x4 5x5 4
x j 0, j 1,,5
z0

cT
x

(cBT , cTN
)
xB xN


cBT
xB

cTN
xN
所以
z0 cBT xB cBT B1b cBT b
，则
令
j cBT Aj c j , j 1,, n.
称 j 为 xj 的检验数，
的检验数向量。
(1,, n )T .
1、单纯形算法的主要思想：
先找一个基本可行解，判定它是否为 最优解，若不是，就找一个“更好”的基 本可行解，再进行判定，如此迭代进行， 直到找到最优解，或判定问题无界。
2、需解决两个问题：
（1）如何得到第一个基本可行解（§2.4）
（2）如何判定和迭代（本节）
本节总是假定已经找到了一个基本可行
解 x ，即找到了一个基 B
已知 x (1, 2, 3, 0, 0)T 是它的基本可行解，对应的基为

4线性规划的基本理论

第四章线性规划本章主要内容：线性规划的基本理论线性规划的单纯形法线性规划的对偶理论线性规划的对偶单纯形法教学目的及要求：理解线性规划的基本理论；掌握线性规划的单纯形法；理解线性规划的对偶理论；掌握线性规划的对偶单纯形法。

教学重点：线性规划的单纯形法.教学难点：线性规划的对偶单纯形法.教学方法：启发式.教学手段：多媒体演示、演讲与板书相结合.教学时间：6学时.教学内容：§4.1线性规划的基本理论考虑线性规划问题nmin工耳号；J-In< =bJ = 12・・・M (LP)丿・ix j noj = i2・・・/・或min c l x\4 s.t. Ax = b.x>0.其中只=(呂山2、・・・必$工=(5工2、・・・£$少=(»6，・・・、叽丫小=(佝人初A称为约束矩阵，= b称为约束方程组，xXO称为非负约束.假定：rank(A) = m .定义在(LP)中，满足约束方程组及非负约束的向量'称为可行解或可行点；所有可行解的全体称为可行解集或可行域，记作K,即K = {Ax = b,x>0} •使目标函数在K上取到最小值的可行解称为最优解；最优解对应的目标函数值称为最优值.定义 在（LP ）中，约束矩阵A 的任意一个加阶满秩子方阵3称为基，B 中 加个线性无关的列向量称为基向量，土中与B 的列对应的分量称为关于B 的基变 量，其余的变量称为关于B 的非基变量.任取（LP ）的一个基B^p^Ph ，…，pQ,记勺=（&，%•••，①），若令关 于B 的非基变量都取0,则约束方程= b 变为Bx 厂b.由于3是满秩方阵，因 此3心"有唯一解心=B»b .记B~7? = （耳，兀•，兀）丁，则由Xj y = 1,2,…，加，Xj =0,刃已{1,2,…，川一 {j 丿,…,九}所构成的〃维向量丁是山"的一个解，称之为（LP ）的关于B 的基本解.基本解满足约束方程组，但不一定满足非负约束，所以不一定是可行解.若 B~l b > 0,即基本解无也是可行解，则称无为（LP ）的关于基〃的基本可行解， 相应的基B 称为（LP ）的可行基；当矿％>0时，称此基本可行解元是非退化的, 否则，称之为退化的.若一个（LP ）的所有基本可行解都是非退化的，则称该 （LP ）是非退化的，否则，称它是退化的.例1求下列线性规划问题的所有基本可行解.min 4Xj - 4x 2;s.t. %| -x 2+x 3 =4, < -x }+x 2 + x 4 = 2,>0J = l,2,3,4.解 约束矩阵的4个列向量依次为【1) 9、p 产 丄 ，卩3 = 1全部基为B\ =（门丿3）廻=5宀）4=（卩2，卩3）』4=（卩2，卩4）小5=（卩3丿4），对于B,, x,和“为基变量，勺和“为非基变量.令A2= A4=0,有X} +x3 =4,<一召=2,得到关于d的基本解x tn =(-2,0,6,0/ ,它不是可行解.对于B2, x,和“为基变量，心和心为非基变量.令x2 = x3 =0,有召=4,<-Xj +X4=2,得到关于％的基本解X⑵=(4,006)7 ,它是一个非退化的基本可行解.同理，可求得关于B2，B,的基本解分别为乳⑶=(0,2,6,0)r, x(4) = (0, -4,0,6)r, ?5) =(0,0,4,2j',显然，沪和芒均是非退化的基本可行解，而兀⑷不是可行解.因此，该问题的所有基本可行解为x⑵,x⑶,x⑸.此外，因为这些基本可行解都是非退化的，所以该问题是非退化的.定理1设天为(LP)的可行解，则元为(LP)的基本可行解的充要条件是它的非零分量所对应的列向量线性无关.证明不妨设丘的前，•个分量为正分量，即无=(召,禺,…,£,0,.・.,0)丁，耳>0(丿=1,2,...,厂).若无是基本可行解，则取正值的变量石禺，…，疋必定是基变量，而这些基变量对应的列向量iwm是基向量.故必定线性相关.反之,若Pi，P2,…，P F线性无关，则必有0<r<m.当r = m时，B =(乩心,…，pj 就是一个基；当厂<加时，一定可以从约束矩阵4的后〃-厂个列向量中选出加7 个,不妨设为咕，几+2,…，Pm，使3 =(必,“2,…,巴，几+1，…，几J成为一个基.由r m于无是可行解，因此工兀Pj=b,从而必有由此可知无是关于3的基本可行解.定理2无是（LP）的基本可行解的充要条件是元为（LP）的可行域的极点•证明 由定理4.1.1和定理2.2.2知结论成立. 例2求下列线性规划问题的可行域的极点.min Xj - x 2;s.t. X, + 2X 2 + A 3 = 2,x } + x 4 = 2,Xj >0,; = 1,2,3,4.解因为约束矩阵的4个列向量依次为"0、<1> ,卩2 = <0>”〔0丿 ,04 = <1>全部基为 B] =5，卩2），〃2 =（刃，卩3）遐=（P I ，P4）4 =（卩2，卩4）4 =（卩3，卩4），求得关于基d ，耳,尿的基本解分别为x ⑴=（2,0,0,0几 x ⑵=（2,0,0,0）7；%⑶=（2,0,0,0）',x ⑷=（0,1,0,2f,x ⑸=（0,0,2,2）『显然，x ⑴,2匕屮）均为退化的基本可行解，x <4>,x'51是非退化的基本可行解.可 行域有三个极点：（2,0,0,0）', （0,1,0,2/, （0,0,2,2）".定理3若（LP ）有可行解，则它必有基本可行解.证明 由定理2.2.1及定理4丄2知结论成立.定理4若（LP ）的可行域K 非空有界，则（LP ）必存在最优解，且其中 至少有一个基本可行解为最优解.证明 根据推论2.2.6, （LP ）的任一可行解x 都可表示为（LP ）的全部基 本可行解召,电,…，无 的凸组合，即 X = 2人x 已K ,其中1-1k&no （i = i,2,…火），工入=1./-I设兀是使（LP ）中目标函数值达到最小的基本可行解，即cl=mincy ,c' x =为人c‘ A ; > 为 2.c z A \ = c 1 x x , Vx e /L .r-i r-1这表明，基本可行解兀为(LP)的最优解.定理5设(LP)的可行域K无界，则(LP)存在最优解的充要条件是对K的任一极方向〃，均有c l d > 0.证明根据定理2.2.10, (LP)的任一可行解x都可写成x = £肚+乞“皿，r-l j-1其中召宀，…，忑为(LP)的全部基本可行解，也，…,/为K的全部极方向，且A r>0(/ = l,2,...^),^Aj=l，A.>0 () = 1,2,•••,/)・j-i于是，(LP)等价于下面以人\0(心1,2,…，灯和“no(J = 1,2,...,/)为决策变量的线性规划问题■* Imin工(c7兀)入+力("〃丿)〃丿；r-l j-1k< S.t.工4 = 1,r-ln0, i = 1,2,…,k ,山AO, ) = 1,2,•••,/.由于宀可以任意大，因此若存在某个心，使Jd’vO,则上述问题的目标函数无下界，从而不存在最优解，从而(LP)不存在最优解.若V 7 = 1,2,•••,/> 均有c T d >0,设c7x x=minc7x.,则J l<r<Ak Ix =工(*无)入 + 工从> c T x s , VxwK •所以基本可行解兀是(LP)的最优解.推论6若(LP)的可行域K无界,且(LP)存在最优解，则至少存在一个基本可行解为最优解.证明由定理4.1.5的证明过程可知结论成立.定理7设在(LP)的全部基本可行解召,兀，…，兀中，使目标函数值最小者为％,%•••";在K的全部极方向^，心,…,^中，满足Jdj =0者为心，你，…，心.若(LP)存在最优解，则才为(LP)的最优解的充要条件是存在S\ no(〃 = i,2,・・•,$),工人=\、卩扎 no(§ = 12・・・,/)“■I使“皿・ <*)p-! </-l证明因为(LP)存在最优解，所以由定理4.1.4和推论4丄6及其证明知, 基本可行解兔,毛,.・.,毛是(LP)的最优解.设x具有(*)式的形式，则由推论2.2.6和定理2.2.10知，x为(LP)的可行解，从而由(*)式知，3 tc，x = = & %p-i g-l因此，x为(LP)的最优解.反乙设x为(LP)的任一最优解，则x为可行解，于是由推论2.2.6和定k理2210知，存在&no(j = 12…火)，工人(丿・=12…,/-I使X =工入兀+工・(**)1 J-1根据定理1丄5,有c r J. >0,; = 1,2,•••,/,且由叫为最优解知/无>c T x. , 7 = 1,2,从而由上述两式容易用反证法证明：若(**)式中某个入>0 ,则脸必为(LP) 的最优解；若(**)式中某个耳>0 ,则必有c•仏=0。

线性规划模型的求解方法

线性规划模型的求解方法线性规划是数学中的一个分支，是用来解决优化问题的方法。

一般来说，它适用于那些具有一定限制条件，但是希望达到最优解的问题。

在实际应用中，无论是在工业、商业还是管理等领域，都可以使用线性规划模型来进行求解。

本文将详细介绍线性规划模型的求解方法，包括单纯形算法、内点法和分支定界法。

1、单纯形算法单纯形算法是线性规划求解中最常用的方法，它是基于不等式约束条件的优化算法，主要是通过这些不等式约束来定义一些可行域并寻找最优解。

单纯形算法的基本思路是将约束条件重写为等式，然后再将变量从这些等式中解出来，最后根据这些解来判断是否找到最优解。

举例来说，假设有如下线性规划的问题：$$\begin{aligned}\text { maximize } \quad &60 x_{1}+40 x_{2} \\\text { subject to } \quad &x_{1}+x_{2} \leq 100 \\&2 x_{1}+x_{2} \leq 150 \\&x_{1}+2 x_{2} \leq 120 \\&x_{1}, x_{2} \geq 0\end{aligned}$$我们可以将这些约束条件重写为等式：$$\begin{aligned}x_{3} &=100-x_{1}-x_{2} \\x_{4} &=150-2 x_{1}-x_{2} \\x_{5} &=120-x_{1}-2 x_{2}\end{aligned}$$然后我们可以利用这些等式来解出每个变量的取值，从而得到最优解。

通常情况下，单纯形算法利用较小的限制空间集合来缩小可行的解空间集合，并通过一定的规则，比如说乘子法则来找到最优的解。

2、内点法内点法则是比单纯形算法更快的一个线性规划求解方法，它通过不停地迭代，将可行域中的点从内部向最优解方向移动，从而找到最优解。

在实际应用中，内点法通常能够达到非常高的精确度，而且与单纯型算法相比，它在数值计算方面更加稳定。

线性规划知识点

线性规划知识点线性规划是一种数学优化方法，用于解决线性约束条件下的最优化问题。

它在各个领域中都有广泛的应用，例如生产计划、资源分配、运输问题等。

一、线性规划的基本概念1. 目标函数：线性规划的目标是最大化或最小化一个线性函数，称为目标函数。

目标函数通常表示为Z = c₁x₁ + c₂x₂ + ... + cnxn，其中ci为系数，xi为变量。

2. 约束条件：线性规划的变量需要满足一系列线性约束条件，如等式约束或不等式约束。

约束条件通常表示为a₁x₁ + a₂x₂ + ... + anxn ≤ b，其中ai为系数，b为常数。

3. 变量的非负性：线性规划中的变量一般要求非负，即xi ≥ 0。

二、线性规划的解法1. 图形法：对于二维线性规划问题，可以通过绘制约束条件的直线和目标函数的等高线，找到最优解的图形位置。

2. 单纯形法：对于多维线性规划问题，单纯形法是一种常用的解法。

它通过迭代计算，不断优化目标函数值，直到找到最优解。

3. 整数规划：当变量需要取整数值时，可以使用整数规划方法求解。

整数规划问题相比线性规划问题更复杂，通常需要借助分支定界等算法进行求解。

三、线性规划的应用案例1. 生产计划：线性规划可以用于制定最优的生产计划，包括确定生产数量、资源分配等问题。

例如，某工厂需要制定最佳的生产计划，以最大化利润或最小化成本。

2. 运输问题：线性规划可以用于解决运输问题，包括货物从供应地到需求地的最佳运输方案。

例如，某物流公司需要确定最优的货物调度方案，以最小化运输成本。

3. 市场营销：线性规划可以用于市场营销策略的制定，包括广告投放、产品定价等问题。

例如，某公司需要确定最佳的广告投放策略，以最大化销售额或利润。

四、线性规划的局限性1. 线性假设：线性规划的前提是目标函数和约束条件都是线性的。

如果问题中存在非线性关系，线性规划可能无法准确求解。

2. 数据不确定性：线性规划的解依赖于输入的数据，如果数据存在误差或不确定性，解的可靠性可能会受到影响。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

3
Case 2. 若 a1 , . . . , ap 线 性 相 关 ， 类 似 于 (i) 只 要 注 意 到 这 时 cT y = 0. 因 为 cT (x − εy ) = cT x − εcT y . 如果 cT y = 0, 我们可以取一个适当符号的相当小的 ε, 使得 x − εy 仍是可 行解, 而 cT (x − εy ) < cT x, 因此 cT y = 0. 这样我们得到的具有更少正向量的新的可行 解，也是最优可行解，最终我们得到一个最优可行解，其正向量对应的列向量线性独立.
这个基本定理告诉我们, 求解线性规划的任务可以归结为在基本可行解中去寻求问题的最优解. Theorem 2.2. D = {x ∈ Rn |Ax = b, x ≥ 0} is convex. Definition 2.1. 设 ∅ = C ⊂ Rn , C is convex. x ∈ C 称作 C 的极点(Extreme point) ⇔ 如果 x = λy + (1 − λ)z (0 < λ < 1, y, z ∈ C ), 则可推出 x = y = z . Theorem 2.3. 一个向量 x ∈ D 是 D 的极点 ⇔ x 是 {Ax = b, x ≥ 0} 的一个基本可行解. Proof: “⇒” 假设 x 是 D 的一个极点, 设 x 的某 k 个分量大于零, 则有 xj1 aj1 + . . . + xjk ajk = b. 用反证法. 假如 x 不是基本可行解, 那么 {aj1 , . . . , ajk } 线性相关，存在不全为零的 yj1 , . . . , yjk , 使 得 yj1 aj1 + . . . + yjk ajk = 0, 设 y 的其他分量为 0. 适当选取 ε 使 x ± εy ∈ D, x ± εy = b 当然成立. 1 那么 x = 2 (x + εy ) + 1 2 (x − εy ), 这与 x 不是极点矛盾, 所以 x 是一个基本可行解. “⇐” 假定 x = (x1 , . . . , xm , 0, . . . , 0) 是一个基本可行解, 于是x1 ax + . . . + xm am = b, 其中 a1 , . . . , am 线性独立. 假如 x 可以表示成 D 中另外两个向量的凸组合, x = λy + (1 − λ)z (0 < λ < 1, y, z ∈ D). 由 x, y, z ∈ D 和 0 < λ < 1 可得出 y, z 的后 n − m 个分量为0, 那么 y1 a1 + . . . + ym am = b, z1 a1 + . . . + zm am = b, 由于 a1 , . . . , am 线性无关, b 表成 a1 , . . . , am 的唯一的线性组合. 所以 x = y = z , x 是极点. Corollary 2.1. 如果 D = ∅, 那么 D 至少具有一个极点. Proof: D is convex, D = ∅, 即有可行解 ⇒ 有基本可行解 ⇔ D 有极点.
m n i=1 j =1 cij xij n j =1 xij = si , m i=1 xij = dj ,
for i = 1, 2, . . . , m for j = 1, 2, . . . , n
xij ≥ LP: min cT x s. t. Ax = b x ≥ 0.
例 3. 运 输问 题 假设m 个地方有大米外调，调出量为s1 , s2 , . . . , sm 吨，n 个城市要调进大米d1 , d2 , . . . , dn ，每吨 m n 大米从i 产地到j 市场的运价是cij 。问如何安排运输计划？(不失一般性，可令 i=1 si = j =1 dj ) min s. t.
d) LP具有多个最优解(线性规划的最优解不一定是唯一的) 我们考虑线性方程组 Ax = b, A ∈ Rm×n , m ≤ n, b ∈ Rn , A = (a1 , . . . , an ), N = {1, . . . , n} Definition 2. a) 我们称J = (j1 , . . . , jr ), ji ∈ N 为 Index Vector. AJ := (aj 1 , . . . , ajr ), xJ = (xj1 , . . . , xjr ) b) j ∈ J ⇔ ∃ i, ji = j 2
c) 称K = N \ J 为 J 的补. Definition 3. a) J = (j1 , . . . , jm ) 称作 Ax = b 的 basis, AJ 为 A 的非奇异子矩阵
b) 假如 J 是 Ax = b 的一个基，我们称 xJ 为基本变量 basic variables c) 与J = (j1 , . . . , jr ) 意义相同，为了方便起见，我们也常写 J = (xji , . . . , xjr ). Definition 4. 假如 J 是 Ax = b 的一个基，J ⊕ K = N ，相应于方程组 Ax = b 的解 x = x(J ) = 1 xJ A− J b = 称作相应于 J 的 basic solution，这样 Ax = AJ xJ + AK xK = b xK 0 Definition 5. 一个基本解如果又是 LP 的可行解，则称为 LP 的 basic feasible solution，如果又是 最优的，则称为 optimal basic feasible solution Definition 6. 如果基本解有一个或者若干个基本变量为零时，则称这个解是 degenerate basic solution. 练习 1. 设A ∈ Rm×n , b ∈ Rm , m > n. 请将问题 min Ax − b 转换成相应的线性规划问题.
b) D := {x ∈ Rn |Ax = b, x ≥ 0} 称为LP 的可行集，x ∈ D 称作LP 的可行解。 c) x∗ ∈ Rn 称作LP 的optimal solution ⇔ 下列的情形是可能的 a) D = Ø. b) D = Ø, c) D = Ø minx∈D f (x) = −∞ & ∃ optimal solution x∗ (D = Ø, infx∈D cT x = −∞) 1) x∗ ∈ D 2) cT x∗ ≤ cT x for all x ∈ D
k i=1
λ1 , . . . , λk ≥ 0,
λk = 1. 于是 cT x = λ1 cT x1 + . . . + λk cT xk . 令 z0 = min{cT xi |i = 1, . . . , k }, 那
么 cT x ≥ (λ1 + . . . + λk )z0 = z0 . 练习
Corollary 2.2. 若对一个线性规划问题存在有限的最优解, 则必存在一个是约束集合极点的有限最 优解.
n ) Corollary 2.3. D 具有有限多个极点(Ax = b 具有不同基本解的数目≤ Cm
Corollary 2.4. 如果 D 有界, 那么 D 是一个凸面体, 即 D 是由有限多个点的凸组合所组成的点 集. Proposition 2.1. 线性目标函数在凸面体 D 上的某个极点处到达最小. Proof: 令 x1 , . . . , xk 为 D 的有限多个极点, 那么 ∀x ∈ D 可表达为 x = λ1 x1 + . . . + λk xk , 其中
线性规划的基本理论和单纯形算法
何 炳 生
南京大学数学系 南京210093
1
线性规划例子与定义
约束优化中研究得最成熟，并得到广泛应用的是线性规划。为了使大家对线性规划有个初步的认 识，我们首先介绍几个例子。
1.1
一些例子
例1. 最佳效益问题 一个农夫有 72 公顷草地, 50 头奶牛和 200 只奶羊。全年花在饲养业上的工时不得超过 10000， 已知饲养一头奶牛需 12 公顷草地和 150 工时/年。饲养一只奶羊需要 0.2 公顷草地和 25 工时/年。 预计 1 年中能从每头奶牛获利 500 元，从每头奶羊获利 90 元，问该农夫应该如何制定他的饲养计 划？ 假设饲养 x1 头奶牛， x2 头奶羊，那么 (P) max 500x1 + 90x2 x1 ≤ 50 x2 ≤ 200 x1 + 0.2x2 ≤ 72 150x1 + 25x2 ≤ 10000 x1 ≥ 0, x2 ≥ 0.
为线性规划的标准问题。 注
T min cT 1 x1 + c2 x2 s. t. A11 x1 + A12 x2 = b1 A21 x1 + A22 x2 ≥ b2 x1 ≥ 0.
可以化成标准形式. Definition 1. a) cT x = c1 x1 + c2 x2 + · · · + cn xn 称为目标函数
1
和
min Ax − b
∞
2
线性规划的基本定理
Theorem 2.1. 假设 LP 标准形式中的矩阵 A 行满秩，那么 i) 若 LP 存在一个可行解，则必存在一个基本可行解 ii) 若 LP 具有一个最优可行解，则必具有一个最优基本可行解。 Proof: (i)的证明. 假定 x = (x1 , . . . , xn )T 是 feasible solution，则有 x1 a1 + . . . + xn an = b, x1 , . . . , xn ≥ 0. 假定前 p 个变量严格大于 0 ，那么 x1 a1 + . . . + xp ap = b Case 1. a1 , . . . , ap 线性无关, p ≤ m. 如果p = m, 那么该可行解就是基本可行解. 如果 p < m, 由 于 = m, 那么可以从剩下的 n − p 个列向量中找出 m − p 个列向量, 共同组成线性无关的 m 个矢量集, 令相应的 m − p 个变量为0, 就产生一个退化基本可行解. Case 2. 假定 a1 , . . . , ap 线性相关.那么存在不全为0的 y1 , . . . , yp 使得 y1 a1 + . . . + yp ap = 0. 不 失一般性, 可设至少有一个 yi > 0. 令 ε = min{xi /yi |yi > 0}. 由此 (x1 − εy1 )a1 + . . . + (xp − εyp )ap = b. 令 y = (y1 , . . . , yp , 0, . . . , 0), 那么 x − εy 也是可行解, 而且至多有 p − 1 个正的分量. 如果需要, 我们可以继续这个过程直到求得的可行解的正的分量对应的列向 量线性无关, 然后再用 Case 1 的结果. (ii)的证明 设 x = (x1 , . . . , xn )T 是一个 optimal feasible solution. 假如其中 x1 , x2 , . . . , xp 为正变 量, 又可如同(i)的证明, 分二种情况 Case 1. 若 a1 , . . . , ap 线性独立，证明如同 (i) 中的 Case 1.