Linear Programming

LINEAR PROGRAMMING II

1

Linear Programming II: Minimization

© 2006 Samuel L. Baker

Assignment 11 is on page 16.

Introduction

A minimization problem minimizes the value of

the objective function rather than maximizing it.

Minimization problems generally involve finding

the least-cost way to meet a set of requirements.

Classic example -- feeding farm animals.

Animals need:

14 units of nutrient A,

12 units of nutrient B, and

18 units of nutrient C.

Learning Objective 1: Recognize problems that

linear programming can handle.

Linear programming lets you optimize an

objective function subject to some constraints.

The objective function and constraints are all

linear.

Two feed grains are available, X and Y.

A bag of X has 2 units of A, 1 unit of B, and 1 unit of C.

A bag of Y has 1 unit of A, 1 unit of B, and 3 units of C.

A bag of X costs $2. A bag of Y costs $4.

Minimize the cost of meeting the nutrient requirements.

To solve, express the problem in equation form:

Cost = 2X + 4Y

objective function to be minimized

Constraints:

2X + 1Y $ 14 nutrient A requirement

1X + 1Y $ 12 nutrient B requirement

1X + 3Y $ 18 nutrient C requirement

8

8

Read vertically to see how much of each nutrient is in each grain.

X $ 0, Y $ 0

non-negativity

Learning objective 2: Know the elements of a linear programming problem -- what you need to

calculate a solution.

The elements are

(1) an objective function that shows the cost or profit depending on what choices you make,

(2) constraint inequalities that show the limits of what you can do, and

(3) non-negativity restrictions, because you cannot turn outputs back into inputs.

LINEAR PROGRAMMING II

2

Graph method of solution

Graph the constraints as equalities, like before. The constraints are now $ rather than #, so the feasible

area is everything to the right and above all of the constraint lines. You want to find the lowest cost point

of this area. It will be a corner. You...