114_Linear Programming

 

In optimization problems, Linear Programming (LP) involves finding the values of variables that maximize or minimize a linear function, subject to linear equations or inequalities as constraints.

 

In linear programming problems, the cost function is the objective function that we aim to minimize or maximize. This function is a linear function $f(x)$ with $k$ variables $x$, composed of first-order terms. The cost function can be expressed in expanded, sum, or matrix form as follows.

 

 

In linear programming problems, all functions are expressed in the form of the aforementioned cost function. However, when there are multiple linear functions, the constant $c$ must be denoted not with a single subscript but with two subscripts. Additionally, the $i$th linear constraint involving $k$ design variables ${x_j}$ can take one of the following three forms.

 

 

The process of converting a linear programming problem into standatd LP form through a simple example.

 

 

First, since the variable ${y_2}$ is unrestricted in sign, it is separated into its positive and negative parts, both of which must be non-negative.

 

 

Substitute the divided ${y_2}$ into each objective function and constraint.

 

 

Since the right-hand side of the second constraint is negative, multiply by -1 to convert it to standard form.

 

 

Convert the objective function into a minimization problem, and intorduce slack and suplus variables to transform all inequality constraints into equality constraints.

 

 

Where ${s_1}$ is a slack variable, and ${s_2}$ is a surplus variable. Now, redefine the variables and rewrite the problem in standard LP form.

 

 

Through the above process, the problem can be converted into standard linear programming form, with each variable and constraint now in a format that can be handled by a linear programming solver.