A Linear Programming Program and Fundamental Theorem of Linear Programming

4/4/26, 9:26 AM3.2 and 3.3: A Linear Programming Program and Fundamental Theorem of Linear Programming: Finite Mathematics (005)

Page 1 of 7https://csustan.instructure.com/courses/41160/pages/3-dot-2-and-3-…fundamental-theorem-of-linear-programming-2?module_item_id=2503684

3.2 and 3.3: A Linear Programming Program and Fundamental Theorem of Linear Programming

3.2 and 3.3: A Linear Programming Program and Fundamental Theorem of Linear Programming

Motivation Question: A furniture manufacturer makes two types of furniture - chairs and sofas. For simplicity, divide the production process into three distinct operations - carpentry, finishing, and upholstery:

Problem Information

Process Chair Sofa Available Time

Carpentry 6 hours 3 hours at most 96 labor-hours

Finishing 1 hour 1 hour at most 18 labor-hours

Upholstery 2 hours 6 hours at most 72 labor-hours

Profit $80 $70 Goal: maximize the

profit

How many chairs and how many sofas should be produced each day to maximize the profit?

Answer: The factory should produce 14 chairs and 4 sofas each day in order to achieve maximum profit, and the maximum profit is $1400 per day.

Definitions at most: " " at least: " " Problems to maximize/to minimize an expression in a certain number of variables, where the

4/4/26, 9:26 AM3.2 and 3.3: A Linear Programming Program and Fundamental Theorem of Linear Programming: Finite Mathematics (005)

Page 2 of 7https://csustan.instructure.com/courses/41160/pages/3-dot-2-and-3-…fundamental-theorem-of-linear-programming-2?module_item_id=2503684

variables are subject to restrictions in the form of one or more inequalities are called mathematical programming problems. A linear programming problem is where both the expression to be maximized/minimized and the inequalities are linear.

A restriction inequality on variables is called a constraint. The objective of the problem is to optimize profit is called the objective function. In general, we maximize a profit function and minimize a cost function.

A feasible set is the graph of a system of inequalities. The line segments intersect at various points and these form a corner of the feasible set. Such a corner is called a vertex. A point corresponding to a problem that yields a maximum/a minimum is called an optimal point. Fundamental Theorem of Linear Programming

The maximum (or minimum) value of the object function is achieved at one of the vertices of the feasible set.

Method Steps to Solve Linear Programming Problems

Step 1. Translate the problem into mathematical language. A. Organize the data into a chart. B. Identify the unknown quantities, and define corresponding variables. C. Translate the restrictions into linear inequalities, called constraints. D. Form the objective function. Step 2. Graph the feasible set. A. Simplify the inequalities into the slope-intercept form. B. Graph the straight line corresponding to each inequality.

Find intercept (set ) and intercept (set ). Find intersecting points by using addition/subtraction or substitution method.

C. Determine the side of the line belonging to the graph of each inequality. Use the test point. Cross out the other side. The remaining region is the feasible set.

Step 3. Determine the vertices of the feasible set. Step 4. Evaluate the objective function at each vertex. Determine the optimal point. Step 5. Interpret the result.

Examples

4/4/26, 9:26 AM3.2 and 3.3: A Linear Programming Program and Fundamental Theorem of Linear Programming: Finite Mathematics (005)

Page 3 of 7https://csustan.instructure.com/courses/41160/pages/3-dot-2-and-3-…fundamental-theorem-of-linear-programming-2?module_item_id=2503684

#1. [Maximizing Profit Example] A furniture manufacturer makes two types of furniture - chairs and sofas. For simplicity, divide the production process into three distinct operations - carpentry, finishing, and upholstery:

Problem Information

Process Chair Sofa Available Time

Carpentry 6 hours 3 hours at most 96 labor-hours

Finishing 1 hour 1 hour at most 18 labor-hours

Upholstery 2 hours 6 hours at most 72 labor-hours

Profit $80 $70 Goal: maximize the

profit

How many chairs and how many sofas should be produced each day to maximize the profit?

Solution Step 1: Let be the number of chairs and be the number of sofas to maximize the profit.

Then we have the following system of linear inequalities, constraints

with to maximize the profit which is the objective function.

Step 2:

How to Solve the Problem

4/4/26, 9:26 AM3.2 and 3.3: A Linear Programming Program and Fundamental Theorem of Linear Programming: Finite Mathematics (005)

Page 4 of 7https://csustan.instructure.com/courses/41160/pages/3-dot-2-and-3-…fundamental-theorem-of-linear-programming-2?module_item_id=2503684

Equation Slope-Intercept

Form intercept intercept

(16,0) (0,32)

(18,0) (0,18)

(36,0) (0,12)

Vertex Information

Vertex Profit =

(14, 4)

80(14)+70(4)=1400

(9, 9) 80(9)+70(9)=1350

(0, 12)

80(0)+70(12)=840

(0, 0) 80(0)+70(0)=0

(16, 0)

80(16)+70(0)=1280

Answer: The factory should produce 14 chairs and 4 sofas each day in order to achieve maximum profit, and the maximum profit is $1400 per day.

#2. [Minimizing Cost Example]: Suppose that a person decides to make rice and soybeans part of their staple diet. The object is to design a lower-cost diet that provides certain minimum levels of protein, calories, and vitamin B2 (riboflavin). Suppose that one cup of uncooked rice costs 21 cents and contains 15 grams of protein, 810 calories, and milligram of riboflavin. On the other

hand, one cup of uncooked soybeans costs 14 cents and contain 22.5 grams of protein, 270 calories, and milligram of riboflavin. Suppose that the minimum daily requirements are 90 grams of protein, 1620 calories, and 1 milligram of riboflavin. Design the lowest-cost diet meeting these specifications.

4/4/26, 9:26 AM3.2 and 3.3: A Linear Programming Program and Fundamental Theorem of Linear Programming: Finite Mathematics (005)

Page 5 of 7https://csustan.instructure.com/courses/41160/pages/3-dot-2-and-3-…fundamental-theorem-of-linear-programming-2?module_item_id=2503684

lower-cost diet process using protein, calories, and vitamin B2 (riboflavin):

Problem Description

Three Methods Rice Soybeans Required

Protein 15 grams/cup 22.5 grams/cup 90 grams per day

Calories 810 per cup 270 per cup 1620 per day

Riboflavin milligram/cup milligram/cup 1 milligram per day

Cost 21 cents/cup 14 cents/cup Goal: minimize the

cost

How many cups of rice and soybeans should be taken each day to design trhe lowest-cost diet meeting these specifications?

Solution Step 1: Let be the number of cups of rice and be the number of cups of soybeans to be taken each day to design the lowest-cost diet meeting these specifications. Then we

have the following system of linear inequalities, constraints

with to minimize the cost which is the objective function.

Step 2:

4/4/26, 9:26 AM3.2 and 3.3: A Linear Programming Program and Fundamental Theorem of Linear Programming: Finite Mathematics (005)

Page 6 of 7https://csustan.instructure.com/courses/41160/pages/3-dot-2-and-3-…fundamental-theorem-of-linear-programming-2?module_item_id=2503684

Steps to Find Solutions

Equation Slope-

Intercept Form

intercept intercept

(6,0) (0,4)

(2,0) (0,6)

(9,0) (0,3)

Feasible Sets

Vertex Cost =

(0, 6) 21(0)+41(6)=84

( ,

) 21( )+14( )=66

(3, 2) 21(3)+14(2)=91

(9, 0) 21(9)+14(0)=189

Answer: The optimal diet with the minimum cost is the one that has cup of rice per day and cups pf soybean per day with 66 cents/day.

4/4/26, 9:26 AM3.2 and 3.3: A Linear Programming Program and Fundamental Theorem of Linear Programming: Finite Mathematics (005)

Page 7 of 7https://csustan.instructure.com/courses/41160/pages/3-dot-2-and-3-…fundamental-theorem-of-linear-programming-2?module_item_id=2503684

Reference: Review linear inequalities from the Khan Academy (https://www.khanacademy.org/math/algebra-basics/alg-basics-linear-equations-and-inequalities)