Linear optimization: Upper and lower bounds 2

Theory

Linear optimization can be used for set of different problems, which have restrictions such as a given amount of resources or a certain budget. The lower bound is the smallest possible value, and the upper bound is the highest possible value.

Linear programming is the most commonly used optimisation technique in embedded industrial applications. There are many reasons for this. Linear programs are relatively easy to formulate, use and understand. The LP optimisation techniques are also relatively efficient and well developed. A surprisingly large set of real-life problems can be represented as linear programs, or approximated sufficiently well with linear programs. Finally, a number of more advanced modelling and solution techniques are based on linear programming, such as quadratic programming, fractional programming, integer programming, mixed integer programming, constraint logic programming, etc.

Lower bounds are classified like: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{j}\geq l_{j}

Upper bounds are classified like: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{j}\leq l_{j}

Example

Suppose that a farmer has a piece of farm land, say L km², to be planted with either wheat or barley or some combination of the two. The farmer has a limited amount of fertilizer, F kilograms, and insecticide, P kilograms. Every square kilometer of wheat requires F₁ kilograms of fertilizer, and P₁ kilograms of insecticide, while every square kilometer of barley requires F₂ kilograms of fertilizer, and P₂ kilograms of insecticide. Let S₁ be the selling price of wheat per square kilometer, and S₂ be the price of barley. If we denote the area of land planted with wheat and barley by x₁ and x₂ respectively, then profit can be maximized by choosing optimal values for x₁ and x₂. This problem can be expressed with the following linear programming problem in the standard form:

Maximize: S1x1 + S2x2		(maximize the revenue—revenue is the "objective function")
Subject to:	x1 + x2 ≤ L	(limit on total area)
	F1x1 + F2x2 ≤ F	(limit on fertilizer)
	P1x1 + P2x2 ≤ P	(limit on insecticide)
	x1 ≥ 0, x2 ≥ 0	(cannot plant a negative area).

Which in matrix form becomes:

maximize ${\begin{bmatrix}S_{1}&S_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}$

subject to Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \begin{bmatrix} 1 & 1 \\ F_1 & F_2 \\ P_1 & P_2 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \le \begin{bmatrix} L \\ F \\ P \end{bmatrix}, \, \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \ge \begin{bmatrix} 0 \\ 0 \end{bmatrix}.

Detailed solution process with explanation

== Sources ==