1. Linear programming:
-- Problem-solving model for optimal allocation of scarce resources, among a number of competing activities.
-- Fast commercial solvers available.
-- Widely applicable problem-solving model.
-- Key subroutine for integer programming solvers.
2. brewer’s problem: choose product mix to maximize profits.
-- formulation:
-- Let A be the number of barrels of ale.
-- Let B be the number of barrels of beer.
-- maximize 13A + 23B subject to the constraints :
- 5A + 15B ≤ 480
- 4A + 4B ≤ 160
- 35A + 20B ≤ 1190
- A , B ≥ 0
-- feasible region:
-- Optimal solution occurs at an extreme point.(intersection of 2 constraints in 2d)
3. Standard form linear program:
-- Maximize linear objective function of n nonnegative variables, subject to m linear equations. (linear means no x^2, xy, arccos(x), etc.)
-- Input: real numbers aij, cj, bi.
-- Output: real numbers xj.
4. Converting the brewer’s problem to the standard form:
-- Original formulation:
maximize 13A + 23B subject to the constraints:
- 5A + 15B ≤ 480
- 4A + 4B ≤ 160
- 35A + 20B ≤ 1190
- A , B ≥ 0
-- Transformation:
- Add variable Z and equation corresponding to objective function.
- Add slack variable to convert each inequality to an equality.
- Now a 6-dimensional problem:
5. Geometry of Linear Programming:
-- Inequalities define halfspaces; feasible region is a convex polyhedron.
-- A set is convex if for any two points a and b in the set, so is ½ (a + b).
-- An extreme point of a set is a point in the set that can't be written as ½ (a + b), where a and b are two distinct points in the set.
-- Extreme point optimal iff no better adjacent extreme point. ( local optima are global optima because objective function is linear and feasible region is convex)
6. Simplex algorithm
-- Generic algorithm:
-- Start at some extreme point.
-- Pivot from one extreme point to an adjacent one. (never decreasing objective function)
-- Repeat until optimal.
-- BFS:
-- A basis is a subset of m of the n variables.
-- Basic feasible solution (BFS):
-- Set n – m nonbasic variables to 0, solve for remaining m variables.
-- Solve m equations in m unknowns.
-- If unique and feasible ⇒ BFS.
-- BFS ⇔ extreme point.
-- initialization:
-- Start with slack variables { SC , SH , SM } as the basis.
-- Set non-basic variables A and B to 0.
-- 3 equations in 3 unknowns yields SC = 480, SH = 160, SM = 1190.
-- Pivot
-- use the variable whose coefficient in objective function is positive to replace some one in the basis. (each unit increase in that variable from 0 increases objective value due to positive coefficient)
-- which variable to replace: Preserves feasibility by ensuring RHS ≥ 0. Minimum ratio rule: min { 480/15, 160/4, 1190/20 }.
-- when to stop: When no objective function coefficient is positive.
-- pivot 1: substitute B = (1/15) (480 – 5A – SC) and add B into the basis (rewrite 2nd equation, eliminate B in 1st, 3rd, and 4th equations)
-- pivot 2: substitute A = (3/8) (32 + (4/15) SC – SH ) and add A into the basis (rewrite 3rd equation, eliminate A in 1st, 2nd, and 4th equations)
-- Why optimal: Z = 800 – SC – 2 SH, optimal objective value Z* ≤ 800 since SC , SH ≥ 0. Thus, current BFS has value 800 ⇒ optimal.
7. Java Implementation of Simplex:
-- Encode standard form LP in a single 2D array.
-- Simplex algorithm transforms initial 2D array into solution:
-- Implementation:
public class Simplex { private double[][] a; // simplex tableaux private int m, n; // M constraints, N variables public Simplex(double[][] A, double[] b, double[] c) { m = b.length; n = c.length; a = new double[m+1][m+n+1]; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) a[i][j] = A[i][j]; for (int j = n; j < m + n; j++) a[j-n][j] = 1.0; for (int j = 0; j < n; j++) a[m][j] = c[j]; for (int i = 0; i < m; i++) a[i][m+n] = b[i]; } //Find entering column q using Bland's rule: index of first column whose objective function coefficient is positive. private int bland() { for (int q = 0; q < m + n; q++) if (a[M][q] > 0) return q; return -1; } //Find leaving row p using min ratio rule. private int minRatioRule(int q) { int p = -1;//leaving row for (int i = 0; i < m; i++) { if (a[i][q] <= 0) continue; //consider only positive entries else if (p == -1) p = i; else if (a[i][m+n] / a[i][q] < a[p][m+n] / a[p][q]) p = i; } return p; } public void pivot(int p, int q) { for (int i = 0; i <= m; i++) for (int j = 0; j <= m+n; j++) if (i != p && j != q) a[i][j] -= a[p][j] * a[i][q] / a[p][q]; for (int i = 0; i <= m; i++) if (i != p) a[i][q] = 0.0; for (int j = 0; j <= m+n; j++) if (j != q) a[p][j] /= a[p][q]; a[p][q] = 1.0; } public void solve() { while (true) { int q = bland(); if (q == -1) break;//entering column q (optimal if -1) int p = minRatioRule(q);//leaving row p (unbounded if -1) if (p == -1) ... pivot(p, q); } }
-- Performance: In typical practical applications, simplex algorithm terminates after at most 2 (m + n) pivots.
-- Pivoting rules: Carefully balance the cost of finding an entering variable with the number of pivots needed.
- No pivot rule is known that is guaranteed to be polynomial.
- Most pivot rules are known to be exponential (or worse) in worst-case.
8. Reduction to standard form:
-- Minimization problem. Replace min 13A + 15B with max – 13A – 15B.
-- ≥ constraints. Replace 4A + 4B ≥ 160 with 4A + 4B – SH = 160, SH ≥ 0.
-- Unrestricted variables. Replace B with B = B0 – B1, B0 ≥ 0 , B1 ≥ 0.
9. Modeling of LP:
-- 1. Identify variables.
-- 2. Define constraints (inequalities and equations).
-- 3. Define objective function.
-- 4. Convert to standard form.
10. Maxflow problem reduces to LP:
-- Variables. xvw = flow on edge v→w.
-- Constraints. Capacity and flow conservation.
-- Objective function. Net flow into t.
11. bipartite matching reduces to LP:
-- LP formulation. One variable per pair.
-- Interpretation. xij = 1 if person i assigned to job j.
相关推荐
Linear Programming book
MIT Linear Programming Courseware- example. You can find more details from MIT's home page for Open Courseware
Linear Programming Using MATLAB 英文epub 本资源转载自网络,如有侵权,请联系上传者或csdn删除 本资源转载自网络,如有侵权,请联系上传者或csdn删除
Understanding and Using Linear Programming
Decoding by linear programming
Linear Programming.Foundations and Extensions.4Ed.pdf。Robert J. Vanderbei。英文第四版
This book: * Provides methods for modeling complex problems...* Explores linear programming (LP) and network flows, employing polynomial-time algorithms and various specializations of the simplex method.
如该书书名,个人认为是不错的LP入门的教材。。。。。。。。。
关于线性规划的英文文献原文,主要讨论线性规划方法的最新运用程序和方面。
The beginning of stochastic programming, and in particular stochastic linear programming (SLP), dates back to the 50’s and early 60’s of the last century. Pioneers who—at that time—contributed to ...
线性规划的入门材料,解决最为基本的最优化问题。
new chapter on financial applications, which discusses a linear programming variant of the portfolio selection problem and option pricing. I am grateful to Alex d’Aspremont for pointing out that the ...
This book is based on the lecture notes of the author delivered to the students at the Institute of Science, Banaras Hindu University, India. It covers simplex, revised simplex, two-phase method, ...
斯坦福管理科学与工程系叶荫宇老师的锥线性规划课程讲义和作业-conic linear programming
此类问题构成了运筹学的一个重要分支—数学规划,而线性规划(Linear Programming 简记 LP)则是数学规划的一个重要分支。自从 1947 年 G. B. Dantzig 提出 求解线性规划的单纯形方法以来,线性规划在理论上趋向成熟...
A linear programming approach to the cutting stock problem
UCBerkerly的一门课程的阅读材料,课程网址:http://www.eecs.berkeley.edu/~christos/classics/
It begins with a thorough treatment of linear programming and proceeds to convex analysis, network flows, integer programming, quadratic programming, and convex optimization. Along the way, dynamic ...