Graduate
  1. Real Analysis  1.1. Set Theory and Logic  1.1.1. Sets and Operations  1.1.2. Relations and Functions  1.1.3. Logic and Quantifiers  1.1.4. Cardinality of Sets  1.2. Metric Spaces  1.2.1. Open and Closed Sets  1.2.2. Convergence of Sequences  1.2.3. Continuous Functions in Metric Spaces  1.2.4. Compactness and Completeness in Metric Spaces in Real Analysis  1.3. Sequence and Series  1.3.1. Convergence of Sequences  1.3.2. Infinite Series  1.3.3. Uniform Convergence  1.3.4. Power Series  1.4. Differentiation  1.4.1. Mean Value Theorems  1.4.2. Taylor Series  1.4.3. Functions of Several Variables  1.4.4. Partial Derivatives  1.5. Integration  1.5.1. Riemann and Lebesgue Integration  1.5.2. Improper Integrals  1.5.3. Measure Theory  1.5.4. Fubini’s Theorem  1.6. Functional Analysis  1.6.1. Banach Spaces  1.6.2. Hilbert Spaces  1.6.3. Operators on Spaces  1.6.4. Spectral Theory
  2. Abstract Algebra  2.1. Groups  2.1.1. Definitions and Examples in Groups in Abstract Algebra  2.1.2. Group Homomorphisms  2.1.3. Normal Subgroups  2.1.4. Sylow Theorems  2.2. Rings and Fields  2.2.1. Ideals and Factor Rings  2.2.2. Field Extensions  2.2.3. Galois Theory  2.2.4. Polynomial Rings  2.3. Modules  2.3.1. Module Homomorphisms  2.3.2. Free Modules  2.3.3. Tensor Products  2.3.4. Exact Sequences  2.4. Linear Algebra  2.4.1. Vector Spaces  2.4.2. Eigenvalues and Eigenvectors  2.4.3. Inner Product Spaces  2.4.4. Diagonalization
  3. Topology  3.1. General Topology  3.1.1. Open and Closed Sets  3.1.2. Compactness and Connectedness  3.1.3. Continuous Maps  3.1.4. Separation Axioms  3.2. Algebraic Topology  3.2.1. Fundamental Groups  3.2.2. Homotopy and Homology  3.2.3. Simplicial Complexes  3.2.4. Exact Sequences in Homology  3.3. Differential Topology  3.3.1. Manifolds  3.3.2. Smooth Functions  3.3.3. Tangent and Cotangent Spaces  3.3.4. Vector Bundles
  4. Differential Equations  4.1. Ordinary Differential Equations  4.1.1. First-Order Equations  4.1.2. Second-Order Linear Equations  4.1.3. Systems of Differential Equations  4.1.4. Stability Analysis  4.2. Partial Differential Equations  4.2.1. Classification of PDEs  4.2.2. Fourier Series  4.2.3. Green's Functions  4.2.4. Method of Characteristics  4.3. Dynamical Systems  4.3.1. Stability Theory  4.3.2. Limit Cycles  4.3.3. Chaos Theory  4.3.4. Bifurcation Theory
  5. Probability and Statistics  5.1. Probability Theory  5.1.1. Random Variables  5.1.2. Probability Distributions  5.1.3. Law of Large Numbers  5.1.4. Central Limit Theorem  5.2. Statistical Inference  5.2.1. Hypothesis Testing  5.2.2. Confidence Intervals  5.2.3. Bayesian Methods  5.2.4. Maximum Likelihood Estimation  5.3. Stochastic Processes  5.3.1. Markov Chains  5.3.2. Brownian Motion  5.3.3. Poisson Processes  5.3.4. Martingales
  6. Numerical Analysis  6.1. Numerical Solutions of Equations  6.1.1. Root Finding  6.1.2. Iterative Methods  6.1.3. Convergence Analysis  6.1.4. Error Bounds in Numerical Solutions of Equations  6.2. Numerical Linear Algebra  6.2.1. Matrix Factorizations  6.2.2. Eigenvalue Computations  6.2.3. Sparse Matrices  6.2.4. Preconditioning Techniques  6.3. Numerical Integration and Differentiation  6.3.1. Quadrature Methods  6.3.2. Finite Differences  6.3.3. Error Analysis in Numerical Integration and Differentiation  6.3.4. Adaptive Methods
  7. Complex Analysis  7.1. Complex Numbers  7.1.1. Polar Form  7.1.2. Complex Conjugates  7.1.3. Exponential Form  7.1.4. Roots of Unity  7.2. Analytic Functions  7.2.1. Cauchy-Riemann Equations  7.2.2. Power Series  7.2.3. Conformal Mappings  7.2.4. Harmonic Functions  7.3. Integration in the Complex Plane  7.3.1. Cauchy’s Theorem  7.3.2. Residue Theorem  7.3.3. Contour Integration  7.3.4. Integral Transforms
  8. Mathematical Logic and Foundations  8.1. Propositional Logic  8.1.1. Truth Tables  8.1.2. Logical Equivalences  8.1.3. Proof Techniques in Propositional Logic  8.1.4. Resolution  8.2. Predicate Logic  8.2.1. Quantifiers in Predicate Logic  8.2.2. Formal Systems in Predicate Logic  8.2.3. Completeness and Soundness  8.2.4. Model Theory  8.3. Set Theory  8.3.1. Cardinality and Ordinality  8.3.2. Axiomatic Systems  8.3.3. Zermelo-Fraenkel Set Theory  8.3.4. Forcing
  9. Optimization  9.1. Linear Programming  9.1.1. Simplex Method  9.1.2. Duality in Linear Programming  9.1.3. Sensitivity Analysis  9.1.4. Interior Point Methods  9.2. Nonlinear Programming  9.2.1. Gradient Descent  9.2.2. Lagrange Multipliers  9.2.3. Convex Optimization  9.2.4. Quadratic Programming  9.3. Combinatorial Optimization  9.3.1. Graph Algorithms  9.3.2. Integer Programming  9.3.3. Network Flows  9.3.4. Approximation Algorithms
  10. Discrete Mathematics  10.1. Graph Theory  10.1.1. Graph Representations  10.1.2. Planarity and Coloring  10.1.3. Shortest Path Algorithms  10.1.4. Network Flows  10.2. Combinatorics  10.2.1. Permutations and Combinations  10.2.2. Generating Functions  10.2.3. Recurrence Relations  10.2.4. Inclusion-Exclusion Principle  10.3. Cryptography  10.3.1. Number Theory Applications in Cryptography  10.3.2. Symmetric and Asymmetric Cryptography  10.3.3. RSA and Elliptic Curve Cryptography  10.3.4. Post-Quantum Cryptography

Graduate → Optimization ↓


Linear Programming


Linear programming (LP) is a mathematical method for determining how to achieve the best result in a given mathematical model. Its function is represented by linear relations. Linear programming is a technique for optimizing a linear objective function, subject to linear equality and linear inequality constraints.

The key components of a linear programming problem are as follows:

  • Objective function: The function that needs to be optimized, usually maximized or minimized.
  • Decision variables: Variables that decide the output and are usually represented as x, y, z etc.
  • Constraints: These are restrictions or limits on the decision variables, often in the form of linear inequalities or equations.
  • Non-negativity restriction: It is assumed that the decision variables are non-negative, i.e. all values are either zero or positive.

Formulation of the linear programming problem

To understand Linear Programming consider the following example:

Imagine that a company makes two products: chairs and tables. Each chair contributes $30 to profit, and each table contributes $50. The company has labor and material limitations. It takes 2 hours of labor and 3 units of material to make one chair. It takes 4 hours of labor and 2 units of material to make one table. The company has a maximum of 100 hours of labor and 120 units of material available.

To maximize profit, we can formulate a linear programming problem as follows:

Maximum: Profit = 30x + 50y
subject to:
   2x + 4y ≤ 100 (Labor constraint)
   3x + 2y ≤ 120 (Physical constraint)
   x ≥ 0, y ≥ 0 (Non-negativity constraint)

Graphical representation

Linear programming problems in two variables can be solved and represented graphically. It looks like this:

x (chairs) y (tables) 2x + 4y = 100 3x + 2y = 120

The feasible region is the set of all points that satisfy all the constraints. It is shaded in grey above. The optimal solution lies in this region. In this example, the optimal strategy is at the intersection of the constraints, represented by the red point.

Simplex method

When there are more than two variables, graphical representation is not possible. Hence, we use the simplex method, which is an iterative method used to solve linear programming problems.

The simplex method involves the following steps:

  1. Start at the initial corner point of the feasible region.
  2. Evaluate the objective function at each vertex of the feasible region.
  3. Move to a neighboring vertex that improves the objective function value.
  4. Continue this process until no further improvement is possible.
  5. The current vertex point provides the maximum or minimum value of the objective function.

Example using the simplex method

Consider the following linear programming problem:

Maximize: Z = 3x1 + 2x2
subject to:
   x1 + x2 ≤ 4
   x1 - x2 ≤ 2
   x1, x2 ≥ 0

Steps to solve using simplex:

  1. Convert the inequalities into equalities by including the relaxed variables, s1 and s2:
    2.     x1 + x2 + s1 = 4
    x1 - x2 + s2 = 2
  2. Create the initial simplex table:
    3. x1 x2 S1 S2 Solution
    S1 1 1 1 0 4
    S2 1 -1 0 1 2
    Jade -3 -2 0 0 0
  3. Find the pivot column (the column with the most negative coefficient in the Z-row):

    4. The most negative value is -3 ( x1's column).

  4. Calculate the ratios to find the pivot line.
    5.     For row s1: 4/1 = 4
    For row s2: 2/1 = 2

    Choose the line with the smallest positive ratio: line s2.

  5. Perform a pivot operation to make the pivot element 1 and all other elements in the pivot column 0.
  6. Repeat this process until there are no negative coefficients left in the objective row.

Duality in linear programming

Every linear programming problem, called a primal problem, can be transformed into another linear programming problem known as a dual problem. The solutions of the dual and primal problems provide bounds for the value of the objective function.

Example:

Primary problem:
Maximize: Z = 3x1 + 4x2
subject to:
   2x1 + 3x2 ≤ 8
   3x1 + 3x2 ≤ 6
   x1, x2 ≥ 0

Its dual will be:

Minimize: W = 8y1 + 6y2
subject to:
   2y1 + y2 ≥ 3
   3y1 + 3y2 ≥ 4
   y1, y2 ≥ 0

The objective functions in primal and dual are interconnected. Solving one of these gives insight or limitation to the other.

Applications of linear programming

Linear programming is widely used in a variety of fields, including:

  • Manufacturing: Determining optimal production levels and inventories.
  • Finance: Designing portfolios to maximize returns with minimal risk.
  • Transportation: Minimizing the cost of shipping goods across the network.
  • Diet planning: Determining the most affordable diet that meets all nutritional requirements.
  • Telecommunications: For optimal bandwidth allocation and network analysis.

Limitations of linear programming

Despite its wide applications, linear programming has some limitations:

  • Models are based on linearity, while real-world scenarios are not always linear.
  • It assumes certainty in the coefficients; however, real-life data may be uncertain or variable.
  • The solution must completely satisfy all the constraints, which may not always be possible.
  • It does not accommodate integer variables in a straightforward way, which may be important in some practical problems.

Conclusion

Linear programming provides a framework for finding optimal solutions under given constraints. While it focuses primarily on optimizing linear objective functions, its principles are foundational in operations research and management science. Innovations and optimizations such as integer linear programming and nonlinear programming extend its applicability to more complex scenarios.


Graduate → 9.1


U
username
0%
completed in Graduate

← Prev (9)
Optimization
Next (9.1.1) →
Simplex Method

Comments 



Linear Programming

https://www.buddymath.com/g/9.1?bmal=en