222 CHAPTER 11. LINEAR PROGRAMMING

burgers than those two and there are many considerations other than demand and availablepatty. Each will likely give you a constraint which must be considered in order to solvea more realistic problem and the end result will likely be a problem in many dimensions,probably many more than three so your ability to draw a picture will get you nowhere forsuch a problem. Another method is needed. This method is the topic of this section. Iwill illustrate with this particular problem. Let x1 = x and y = x2. Also let x3 and x4 benonnegative variables such that

x1 +2x2 + x3 = 9000, 2x1 + x2 + x4 = 9000.

To say that x3 and x4 are nonnegative is the same as saying x1 + 2x2 ≤ 9000 and 2x1 +x2 ≤ 9000 and these variables are called slack variables at this point. They are called thisbecause they “take up the slack”. I will discuss these more later. First a general situation isconsidered.

11.2 The Simplex TableauHere is some notation.

Definition 11.2.1 Let x,y be vectors in Rq. Then x≤ y means for each i,xi ≤ yi.

The problem is as follows:Let A be an m× (m+n) real matrix of rank m. It is desired to find x ∈ Rn+m such that

x satisfies the constraints,x≥ 0,Ax = b (11.1)

and out of all such x,

z≡m+n

∑i=1

cixi

is as large (or small) as possible. This is usually referred to as maximizing or minimizing zsubject to the above constraints. First I will consider the constraints.

Let A =(

a1 · · · an+m

). First you find a vector x0≥ 0, Ax0= b such that n of

the components of this vector equal 0. Letting i1, · · · , in be the positions of x0 for whichx0

i = 0, suppose also that{

a j1 , · · · ,a jm}

is linearly independent for ji the other positionsof x0. Geometrically, this means that x0 is a corner of the feasible region, those x whichsatisfy the constraints. This is called a basic feasible solution. Also define

cB ≡ (c j1 . · · · ,c jm) , cF ≡ (ci1 , · · · ,cin)

xB ≡ (x j1 , · · · ,x jm) , xF ≡ (xi1 , · · · ,xin) .

and

z0 ≡ z(x0)= ( cB cF

)( x0B

x0F

)= cBx0

B

since x0F = 0. The variables which are the components of the vector xB are called the basic

variables and the variables which are the entries of xF are called the free variables. Youset xF = 0. Now

(x0,z0

)T is a solution to(A 0−c 1

)(xz

)=

(b0

)