Engineering Optimization: Theory and Practice, Fourth Edition

124 Linear Programming I: Simplex Method

Similarly, if the constraint is in the form of a “greater than or equal to” type of

inequality as

ak 1 x 1 +ak 2 x 2 + · · · +aknxn≥bk

it can be converted into the equality form by subtracting a variable as

ak 1 x 1 +ak 2 x 2 + · · · +aknxn−xn+ 1 =bk

wherexn+ 1 is a nonnegative variable known as asurplus variable.

It can be seen that there aremequations inndecision variables in a linear pro-

gramming problem. We can assume thatm < n; for ifm>n, there would bem−n

redundant equations that could be eliminated. The casen=mis of no interest, for then

there is either a unique solutionXthat satisfies Eqs. (3.2) and (3.3) (in which case there

can be no optimization) or no solution, in which case the constraints are inconsistent.

The casem < ncorresponds to an underdetermined set of linear equations, which, if

they have one solution, have an infinite number of solutions. The problem of linear

programming is to find one of these solutions that satisfies Eqs. (3.2) and (3.3) and

yields the minimum off.

3.4 Geometry of Linear Programming Problems

A linear programming problem with only two variables presents a simple case for which

the solution can be obtained by using a rather elementary graphical method. Apart

from the solution, the graphical method gives a physical picture of certain geometrical

characteristics of linear programming problems. The following example is considered

to illustrate the graphical method of solution.

Example 3.2 A manufacturing firm produces two machine parts using lathes, milling

machines, and grinding machines. The different machining times required for each part,

the machining times available on different machines, and the profit on each machine

part are given in the following table.

Machining time required (min)

Maximum time available

Type of machine Machine part I Machine part II per week (min)

Lathes 10 5 2500

Milling machines 4 10 2000

Grinding machines 1 1.5 450

Profit per unit $50 $100

Determine the number of parts I and II to be manufactured per week to maximize the

profit.

SOLUTION Let the number of machine parts I and II manufactured per week be

denoted byxandy, respectively. The constraints due to the maximum time limitations