Program linier, ( Linear Program)

Linear Programming (LP) Problem

A linear programming problem is one in which we are to find the maximum or minimum value of a linear expression
ax + by + cz + . . .
(called the objective function), subject to a number of linear constraints of the form
Ax + By + Cz + . . .≤ N
or
Ax + By + Cz + . . .≥ N.
The largest or smallest value of the objective function is called the optimal value, and a collection of values of x, y, z, . . . that gives the optimal value constitutes an optimal solution. The variables x, y, z, . . . are called the decision variables.

Example
Here is an example of an LP problem:
Find the maximum value of
p = 3x - 2y + 4z
subject to
4x + 3y - z ≥ 3
x + 2y + z ≤ 4
x ≥ 0, y ≥ 0, z ≥ 0
The objective function is p = 3x - 2y + 4z. The constraints are
4x + 3y - z ≥ 3
x + 2y + z ≤ 4
x ≥ 0, y ≥ 0, z ≥ 0.
Q Wait a minute! Why can't I simply choose, say, z to be really large (z = 1,000,000 say) and thereby make p as large as I want?
A You can't because

Top of Page




Sketching the Solution Set of a Linear Inequality
To sketch the region represented by a linear inequality in two variables:
A. Sketch the straight line obtained by replacing the inequality with an equality.
B. Choose a test point not on the line ((0,0) is a good choice if the line does not pass through the origin, and if the line does pass through the origin a point on one of the axes would be a good choice).
C. If the test point satisfies the inequality, then the set of solutions is the entire region on the same side of the line as the test point. Otherwise it is the region on the other side of the line. In either case, shade out the side that does not contain the solutions, leaving the solution region showing. Example
To sketch the linear inequality
3x - 4y ≤ 12,
first sketch the line 3x - 4y = 12.

Next, choose the origin (0, 0) as the test point (since it is not on the line). Substituting x=0, y=0 in the inequality gives
3(0) - 4(0) ≤ 12.
Since this is a true statement, (0, 0) is in the solution set, so the solution set consists of all points on the same side as (0, 0). This region is left unshaded, while the (grey) shaded region is blocked out.

Top of Page

Feasible Region
The feasible region determined by a collection of linear inequalities is the collection of points that satisfy all of the inequalities.
To sketch the feasible region determined by a collection of linear inequalities in two variables: Sketch the regions represented by each inequality on the same graph, remembering to shade the parts of the plane that you do not want. What is unshaded when you are done is the feasible region. Example
The feasible region for the following collection of inequalities is the unshaded region shown below (including its boundary).
3x - 4y ≤ 12,
x + 2y ≥ 4
x ≥ 1
y ≥ 0.

Top of Page

Graphical Method
The graphical method for solving linear programming problems in two unknowns is as follows.
A. Graph the feasible region.
B. Compute the coordinates of the corner points.
C. Substitute the coordinates of the corner points into the objective function to see which gives the optimal value.
D. If the feasible region is not bounded, this method can be misleading: optimal solutions always exist when the feasible region is bounded, but may or may not exist when the feasible region is unbounded. The textbook shows a straightforward way for determining whether optimal solutions exist in the case of unbounded feasible regions.
If you want to see a utility that automates the whole process, try our Linear Programming Grapher. It does everything automatically! Example
Minimize C = 3x + 4y subject to the constraints
3x - 4y ≤ 12,
x + 2y ≥ 4
x ≥ 1, y ≥ 0.
The feasible region for this set of constraints was shown above. Here it is again with the corner points shown.

The following table shows the value of C at each corner point:
Point C = 3x + 4y
(1, 1.5) 3(1)+4(1.5) = 9 minimum

(4, 0) 3(4)+4(0) = 12
Therefore, the solution is x = 1, y = 1.5, giving the minimum value C = 9.
Top of Page

Standard Maximization Problem
A standard maximization problem in n unknowns is a linear programming problem in which we are required to maximize (not minimize) the objective function, subject to constraints of the form
x≥ 0, y≥ 0, z≥ 0, . . . ,
and further constraints of the form
Ax + By + Cz + . . . ≤ N,
where A, B, C, . . . and N are numbers with N nonnegative.
Note that the inequality here must be a "≤," and not "=" or "≥." Examples
The following is a standard LP problem:
Maximize P = 2x - 3y + z subject to
4x - 3y + z ≤ 3
x + y + z ≤ 10
x ≥ 0, y ≥ 0, z ≥ 0.
The following is not a standard LP problem:
Maximize P = 2x - 3y + z subject to
4x - 3y + z ≥ 3
x + y + z ≤ 10
x ≥ 0, y ≥ 0, z ≥ 0.
Top of Page

Simplex Method for Standard Maximization Problem
To solve a standard maximization problem using the simplex method, we take the following steps:
Step 1. Convert to a system of equations by introducing slack variables to turn the constraints into equations, and rewriting the objective function in standard form.
Step 2. Write down the initial tableau.
Step 3. Select the pivot column: Choose the negative number with the largest magnitude in the bottom row (excluding the rightmost entry). Its column is the pivot column. (If there are two candidates, choose either one.) If all the numbers in the bottom row are zero or positive (excluding the rightmost entry), then you are done: the basic solution maximizes the objective function (see below for the basic solution).
Step 4. Select the pivot in the pivot column: The pivot must always be a positive number. For each positive entry b in the pivot column, compute the ratio a/b, where a is the number in the Answer column in that row. Of these test ratios, choose the smallest one. The corresponding number b is the pivot.
Step 5. Use the pivot to clear the column in the normal manner (taking care to follow the exact prescription for formulating the row operations described in Chapter 2) and then relabel the pivot row with the label from the pivot column. The variable originally labeling the pivot row is the departing or exiting variable and the variable labeling the column is the entering variable.
Step 6. Go to Step 3. Some Useful Links
On-Line Tutorial on the Simplex Method
Pivot and Gauss-Jordan Tool
Excel Pivot and Gauss-Jordan Tool
Simplex Method Tool
Free Macintosh Simplex Method Tool.

Top of Page

Basic Solution
To get the basic solution corresponding to any tableau in the simplex method, set to zero all variables that do not appear as row labels (these are the inactive variables).
The value of a variable that does appear as a row label (an active variable) is the number in the rightmost column in that row divided by the number in that row in the column labeled by the same variable. Example
In the following tableau
x y z s t u p Ans
________________________________________
-1 0 0 1 0 0 0 4
1 0 3 0 0 8 0 12
4 0 0 0 3 0 0 2
-5 2 0 0 0 6 0 4
________________________________________
6 0 0 0 0 0 5 -25
the basic solution is
x = 0, y = 2, z = 4, s = 4, t = 2/3, u = 0, p = -5,
and the active variables are y, z, s, t, and p.
Top of Page

Nonstandard Constraints
To solve a linear programming problem with constraints of the form Ax + By + . . .≥ N with N positive, subtract a surplus variable from the left-hand side, rather than adding a slack variable. The basic solution corresponding to the initial tableau will not be feasible since some of the active variables will be negative, and so the rules for the initial pivoting are different from those above.
Star all rows that give a negative value for the associated active variable (except for the objective variable, which is allowed to be negative). If there are starred rows, you will need to begin with Phase I:
Phase I: Getting into the Feasible Region (Getting Rid of the Stars) In the first starred row, find the largest positive number. Use test ratios as in the preceding section to find the pivot in that column (exclude the bottom row), then pivot on that entry. If the lowest ratio occurs both in a starred row and an unstarred row, pivot in a starred row rather than the unstarred one. Repeat until no starred rows remain, then go on to Phase II.
Phase II: Use the Simplex Method for Standard Maximization Problems If there are any negative entries on the left side of the bottom row after Phase I, use the method described above for solving standard maximization problems.
For some on-line interactive examples, visit the tutorial for general linear programming problems.
Top of Page

Simplex Method for Minimization Problem
To solve a minimization problem using the simplex method, convert it into a maximization problem. If you need to minimize c, instead maximize p = -c. Example
The minimization LP problem:
Minimize C = 3x + 4y - 8z subject to the constraints
3x - 4y ≤ 12,
x + 2y + z ≥ 4
4x - 2y + 5z ≤ 20
x ≥ 0, y ≥ 0, z ≥ 0
can be replaced by the following maximization problem:
Maximize P = -3x - 4y + 8z subject to the constraints
3x - 4y ≤ 12,
x + 2y + z ≥ 4
4x - 2y + 5z ≤ 20
x ≥ 0, y ≥ 0, z ≥ 0.
Top of Page

Solving a Matrix Game Using the Simplex Method
A game may be solved using the simplex method as follows.
Before you start, check for saddle points. If you find one, you have already solved the game; the optimal strategies are the pure strategies passing through a saddle point. Otherwise, continue with the following steps.
1. Reduce the payoff matrix by dominance.
2. Add a fixed number k to each of the entries so that they all become non-negative.
3. Set up and solve the associated linear programming problem using the simplex method.
4. Obtain the optimal strategies and the expected value as follows:
Column Strategy
a. Express the solution to the linear programming problem as a column vector.
b. Normalize by dividing each entry of the solution vector by the sum of the entries, or by the value of the objective variable p.
c. Insert zeros in positions corresponding to the columns deleted during reduction.

Row Strategy
d. Write down the row vector whose entries are the numbers appearing in the bottom row of the final tableau underneath the slack variables.
e. Normalize by dividing each entry of the solution vector by the sum of the entries.
f. Insert zeros in positions corresponding to the rows deleted during reduction.

Value of the Game
e = 1/p - k.
Top of Page


Last Updated: March, 2006
Copyright © 2000-2006 Stefan Waner