Linear Programming

What Is Linear Programming?

Linear Programming is the process of finding the extreme values (maximum and minimum values) of a function for a region defined by inequalities.

Formula :

Y > Mx + C

M = gradient

C = y-intercept

Solve the following linear program:
maximise 5x₁ + 6x₂
subject to
x₁ + x₂ <= 10
x₁ - x₂ >= 3
5x₁ + 4x₂ <= 35
x₁ >= 0
x₂ >= 0

Solution

It is plain from the diagram below that the maximum occurs at the intersection of
5x₁ + 4x₂ = 35 and
x₁ - x₂ = 3
Solving simultaneously, rather than by reading values off the graph, we have that
5(3 + x₂) + 4x₂ = 35
i.e. 15 + 9x₂ = 35
i.e. x₂ = (20/9) = 2.222 and
x₁ = 3 + x₂ = (47/9) = 5.222
The maximum value is 5(47/9) + 6(20/9) = (355/9) = 39.444 

 
A carpenter makes tables and chairs. Each table can be sold for a profit of £30 and each chair for a profit of £10. The carpenter can afford to spend up to 40 hours per week working and takes six hours to make a table and three hours to make a chair. Customer demand requires that he makes at least three times as many chairs as tables. Tables take up four times as much storage space as chairs and there is room for at most four tables each week.
Formulate this problem as a linear programming problem and solve it graphically.

Solution

Variables

Let
x_T = number of tables made per week
x_C = number of chairs made per week

Constraints

• total work time

6x_T + 3x_C <= 40

• customer demand

x_C >= 3x_T

• storage space

(x_C/4) + x_T <= 4

• all variables >= 0

Objective

maximise 30x_T + 10x_C
The graphical representation of the problem is given below and from that we have that the solution lies at the intersection of
(x_C/4) + x_T = 4 and 6x_T + 3x_C = 40
Solving these two equations simultaneously we get x_C = 10.667, x_T = 1.333 and the corresponding profit = £146.667 

 
Question!

1. A farmer has 10 acres to plant in wheat and rye. He has to plant at least 7 acres. However, he has only $1200 to spend and each acre of wheat costs $200 to plant and each acre of rye costs $100 to plant. Moreover, the farmer has to get the planting done in 12 hours and it takes an hour to plant an acre of wheat and 2 hours to plant an acre of rye. If the profit is $500 per acre of wheat and $300 per acre of rye how many acres of each should be planted to maximize profits?

2. A gold processor has two sources of gold ore, source A and source B. In order to kep his plant running, at least three tons of ore must be processed each day. Ore from source A costs $20 per ton to process, and ore from source B costs $10 per ton to process. Costs must be kept to less than $80 per day. Moreover, Federal Regulations require that the amount of ore from source B cannot exceed twice the amount of ore from source A. If ore from source A yields 2 oz. of gold per ton, and ore from source B yields 3 oz. of gold per ton, how many tons of ore from both sources must be processed each day to maximize the amount of gold extracted subject to the above constraints?

3. A publisher has orders for 600 copies of a certain text from San Francisco and 400 copies from Sacramento. The company has 700 copies in a warehouse in Novato and 800 copies in a warehouse in Lodi. It costs $5 to ship a text from Novato to San Francisco, but it costs $10 to ship it to Sacramento. It costs $15 to ship a text from Lodi to San Francisco, but it costs $4 to ship it from Lodi to Sacramento. How many copies should the company ship from each warehouse to San Francisco and Sacramento to fill the order at the least cost?