02 Preliminaries
Outline
Standard form LP / LP的标准形式
Embedded assumptions /
- 一个问题想要变成一个LP问题,就一定有一些内含的假设。
- 我们要去探究到底有哪些假设的条件时,我们可以使用这个优化的模型。
Converting to standard form / 转变成标准形式
02-1 Standard form LP
Key Elements:
- n个有限的变量x1,x2,....,xn
- 单一的,没有常数项的,线性的,目标函数,且我们的目标一定是最小化.
- 例如又想马儿跑得快,又想马儿吃的少,这就是两个目标函数了。对于标准的线性规划,只能一个线性目标函数。 z=c1x1+c2x2+....+cnxn
- m个有限的等式线性约束(constrains)
- 仍然是为了标准化,将所有的不等式都要化成等式。
a11x1+a12x2+......+a1nxn=b1a21x1+a22x2+......+a2nxn=b2..............................am1x1+am2x2+......+amnxn=bm
- n个有限的决策变量都是非负的:x1≥0,x2≥0,....,xn≥0
Explicit Form
三个要素:决策变量,目标函数,约束条件
Minimize z=c1x1+c2x2+....+cnxn subject toa11x1+a12x2+......+a1nxn=b1a21x1+a22x2+......+a2nxn=b2..............................am1x1+am2x2+......+amnxn=bm x1≥0,x2≥0,....,xn≥0
简化:矩阵形式(全部都是列向量的形式)
cost vector:c=⎩⎪⎪⎨⎪⎪⎧c1c2.....cn⎭⎪⎪⎬⎪⎪⎫sulution vector:x=⎩⎪⎪⎨⎪⎪⎧x1x2.....xn⎭⎪⎪⎬⎪⎪⎫right−hand−side vector:b=⎩⎪⎪⎨⎪⎪⎧b1b2.....bn⎭⎪⎪⎬⎪⎪⎫ constraint maxtrix :A=⎩⎪⎪⎨⎪⎪⎧a11a21...am1a12a22...am2............a1na2n...amn⎭⎪⎪⎬⎪⎪⎫
所以,矩阵形式为:
Min cTxs.t. Ax=bx≥0
02-2 Embedded assumptions in LP
1.Proportionallity Assumption
- No discount
- No economy of return to scale
- 这一点就是说,优化的过程中,我们严格按照线性的指标来。如一个价格,1KG五块钱,那么2KG就是10块钱,没有折扣,按照比例来。如果有折扣,那就不是线性规划。(动态)
2.Additivity Assumption
3.Divisibility Assumption
- 这一点就是说我们的问题里面,可以任意取小数,不论分解到多少部分都可以。价格可以定为2.999999999这样子。线性优化里是没有对整数之类的规定的
4.Certainly Assumption
- Each parameter is known for sure
- 解释:除了变量以外,其他的所有参数,在线性规划中,是确定性的知道的。例如我们想知道配送的各个商品的数量,那么除了数量之外,其他的东西都必须知道。
02-3 Converting to standard form
Example:
Maxmize3x1−2x2−4∣x3∣ s.t −x1+2x2≤−53x2−x3≥62x1+x3=12 x1,x2≥0
我们根据之前的标准形式来看这个例子:
Key elements |
Elements of our Example |
n个有限的变量 |
符合,有3个决策变量 |
单一的,没有常数项的,线性的,目标函数,且我们的目标一定是最小化 |
不符合,目标函数不是最小化 |
m个有限的等式线性约束 |
符合 |
n个有限的决策变量都是非负的 |
不符合,x3并没有约束 |
(1) Unrestricted(Free) variables-对无约束的决策变量的转换,这个方法也可以用来对绝对值的转换
核心原理:每个数都有正的部分和负的部分,例如5,正的部分就是5,负的部分就是0.那么对于任意的在实数域上的数x都有:
即:
- 每个数都等于,自己的正的部分减去负的部分。 5=5−0−5 =0−5
- 每个数的绝对值都等于自己的正的部分加上自己的负的部分(两个部分都大与等于0) ∣5∣=5+0∣−5∣ =5=0+5
那么根据以上的规则,我们就可以对上面那个例子来进行变化:
Maxmize3x1−2x2−4(x3++x3−) s.t −x1+2x2≤−53x2−(x3+−x3−)≥62x1+(x3+−x3−)=12 x1,x2,x3+,x3−≥0
(2)Inequality constraints-将约束中的不等变为等式
核心思想:对于每一个不等式,我们都引入一个非负项。使得等式能够成立。例如:对于a>b,我们可以引入一个数c使得,a-c=b成立。这就是基本的思想。
- slack variable 松弛变量
ai1x1+ai2x2+......+ainxn≤bi add a slack variable si:ai1x1+ai2x2+......+ainxn+si=bi
- excess variable 富余变量
ai1x1+ai2x2+......+ainxn≥bi subtract a excess variable ei:ai1x1+ai2x2+......+ainxn−ei=bi
(3)Minimization of the objective function
记得有两个负号:负负得正!
这时我们的例子就变成这样了:
(−)Minimize−3x1+2x2+4x3++4x3− s.t −x1+2x2+x4=−53x2−(x3+−x3−)−x5=62x1+(x3+−x3−)=12 x1,x2,x3+,x3−,x4,x5≥0
(4) More on free variable and absolute value(更多关于*变量和绝对值的问题)
思考,上述化为标准式的式子,就等同于原来的问题了吗?
不,还真不。
Potential probleam
xi+∗xi+=0
- 其次,我们增加了解空间的维度
- 我们忽略的那个约束,可能会带来的问题:思考:5可以写成5-0,也可以写成6-1。很多,如果我们不约束其中一个为0,那么就会有很多可能的新解。这个要仔细体会一下,假设原来的解就是5,我们如果不做限制它拆分为5和0,那么实际上,可以拆分成很多很多的解。
- 还有绝对值的问题(与本例无关):如果一个目标函数里,我们有一个目标是:max c∣x∣那么我们将其变成求min的目标的时候,它就变成了min −c∣x∣如果这个常数c是一个正值,这是一个凹函数(concave),无法求最小值。
02-4 Conclusion
1 Three elements of LP model:
- decision variables
- objective function
- constraints
2 The embedded assumptions
3 How to convert to standard form
-
(1) Unrestricted(Free) variables-对无约束的决策变量的转换,这个方法也可以用来对绝对值的转换
-
(2)Inequality constraints-将约束中的不等变为等式
-
(3)Minimization of the objective function