June 26, 2019

What is Linear Programming?

Linear programming is used to optimize a linear objective function and a system of linear inequalities or equations. The limitations set on the objective function are called as constraints. The objective function represents the quantity which needs to be minimized or maximized. Linear programming's main objective is to optimize the objective function.

The assumptions for a linear programming problem are given below:

- The limitations on the objective function known as constraints are written in the form of quantitative values.
- The objective function must be a linear function.
- The relationship between the objective function and the constraints must be linear.

Linear programming problems can be solved using multiple methods. The most common methods are simplex method, solving the problems using R or open solver, and graphical method. In this article, we will solve the linear programming problems using the graphucal method.

## Example 1

A store has requested a manufacturer to produce pants and sports jackets.

For materials, the manufacturer has of cotton textile and of polyester. Every pair of pants (1 unit) needs of cotton and of polyester. Every jacket needs of cotton and of polyester. The price of the pants is fixed at $50 and the jacket, $40. What is the number of pants and jackets that the manufacturer must give to the stores so that these items obtain a maximum sale?

^{st}lesson free!

^{st}lesson free!

^{st}lesson free!

^{st}lesson free!

^{st}lesson free!

^{st}lesson free!

^{st}lesson free!

^{st}lesson free!

## Solution

### Step 1 - Identify the Decision Variables

**Choose the unknowns.**

x = number of pants

y = number of jackets

### Step 2 - **Write the objective function**.

### Step 3 - Identify the set of Constraints

To write the constraints, use a table:

pants | jackets | available | |
---|---|---|---|

cotton | 1 | 1,5 | 750 |

polyester | 2 | 1 | 1,000 |

As the number of pants and jackets are natural numbers, there are two more constraints:

x ≥ 0

y ≥ 0

### Step 4 - Choose the method for solving the problem

There are many methods to solve a linear programming method. In this problem, we will find the solution of the problem graphically.

### Step 5 - Construct the graph

Represent the constraints graphically.

As x ≥ 0 and y ≥ 0, work in the first quadrant.

Represent the straight lines from their points of intersection with the axes.

Example 1 - Graph

Solve the inequality graphically: , and take a point on the plane, for example (0,0).

Since then the point (0,0) is in the half plane where the inequality is satisfied.

Similarly, solve .

### Step 6 - Identify the feasible region

The area of intersection of the solutions of the inequalities would be the solution to the system of inequalities, which is the set of **feasible solutions**.

### Step 7 - Find the optimum point

Calculate the coordinates of the vertices from the compound of feasible solutions.

The optimal solution, if unique, is in a vertex. These are the solutions to the systems:

;

Now, we will calculate the value of the objective function at each of the vertices to determine which of them has the maximum or minimum values. It must be taken into account the possible non-existence of a solution if the compound is not bounded.

In the **objective function**, place each of the vertices that were determined in the previous step.

**Maximum**

The optimum solution is to make 375 pants and 250 jackets to obtain a benefit of $28,750.

The solution is not always unique, so we can also find other solutions.

## Example 2

Maria has an online shop where she sells hand made paintings and cards. She sells the painting for $50 and the card for $20. It takes her 2 hours to complete 1 painting and 45 minutes to make a single card. She also has a day job and makes paintings and cards in her free time. She cannot spend more than 15 hours a week to make paintings and cards. Additionally, she should make not more than 10 paintings and cards per week.

She makes a profit of $25 on painting and $15 on each card. How many paintings and cards should she make each week to maximize her profit.

## Solution

Follow these steps to solve the above problem.

### Step 1 - Identify the decision variables

x = number of paintings

y = number of cards

### Step 2 - Write the objective function

Since she makes $25 profit in each sold painting and $15 on each sold card, therefore the objective function is:

### Step 3 - Identify the set of constraints

It takes her 2 hours to complete a painting and 45 minutes to make a card. She cannot spend more than 15 hours a week in making cards and painting.

She should make at most 10 paintings and cards a week.

We also have two other constraints:

and

### Step 4 - Choose the method for solving the problem

We will use the graphical method to solve this problem.

### Step 5 - Construct the graph

Graph- Example 2

### Step 6 - Identify the feasible region

The green highlighted area is the feasibility region of the graph

Feasibility region of the graph

### Step 7 - Find the optimum point

Use the coordinates of the vertices and substitute them in the objective function to yield the maximum point.

**Maximum **

The above calculations show that Maria can make the maximum profit of $210 a week by making **6 paintings** and **4 cards**.

great

Linear programing geometric approch

Can you please show the solution of exercise 4

Q1.A manufacturer of purses makes four styles of purses: a three-compartment bag which takes 45

minutes to assemble: a shoulder-strap bag. taking one hour to assemble; a tote hag, needing 45

minutes for assembly, and pocket purse requiring 30 minutes to assemble. There are 32 hours of

assembly time available per day. The profit contribution on the sale of a three-compartment bag is Rs.

16, Rs 25 on a shonlder-strap hag. and Rs 12 each on tnte hag and pocket rurse

A special kind of fancy pins are used in decorating pocket purses and they are available for only thirty

pieces. Diferent types of pins are used in other three types of bags of which only seventy are in stock.

Enough raw material is available for a total of sixty pocket purses and tote bags which need the same

quantity of raw material. The manufacturer estimates a minimum demand of six pocket purses and the

shoulder strup bags every day. Formulate a linear programming problenm to optimize daily production.

1. Evening shift resident doctors in a government hospital work five consecutive days and have two consecutive days off.

Their five days of work can start on any day of the week and the schedule rotates indefinitely. The hospital requires the

following minimum number of doctors working:

Sun Mon Tues Wed Thurs Fri Sat

35 55 60 50 60 50 45

No more than 40 doctors can start their five working days on the same day. Formulate a LPP model to minimize the

number of doctors employed by the hospital.

Owesome

Wow that’s nice

Thanks for posting this. It’s a great help. Very clear and detailed.

Can you tell me the constraints of this problem?

A retiree has 60 garden plots on which he could plant cabbage and pechay. His friend told him that he could make a profit of Php 100 per slot of cabbage and Php 90 per slot of pechay. His household could not possibly take care of more than20 plots of cabbage and 40 plots of pechay. How many plots of each vegetable should he plant for him to have a maximum profit? What is the maximum profit?

Thanks so much for this. Really appreciate it.

Good explanation