Linear programming Introduction

A mathematical model is a set of equations and inequalities that describe a system. Eg.E = mc², Y = 5.4 + 2.6 X. These models are designed to have several types of programming:

• Linear programming
• Integer programming
• Non- linear programming

A linear programming procedure involves mathematical technique to solve optimization models with linear objectives and constraints. It allocates scarce resources to achieve an objective.

Examples of linear programming problems:

• Scheduling school buses to minimize the total distance travelled.
• Scheduling tellers at banks to minimize the total cost of labour.
• Blending raw materials in feed mills for maximizing the profit of producing animal feed.
• Selecting the product mix in a factory to make the best use of available machine- and labour-hours available while maximizing profit.
• Allocating space for tenants in a shopping mall for maximizing the profits of the leasing office.

Characteristics of a linear programming problem are:

• Deterministic (no probabilities): LP assumes all relevant input data and parameters are known with certainty
• Single Objective: maximize or minimize some quantity (the objective function) for optimization.
• Continuous decision variables (unknowns to be determined).
• Constraints limit the ability to achieve the objective.
• Objectives and constraints must be expressed as linear equations or inequalities.

The formulation is a process of translating problem scenario into a simple LP model framework with a set of mathematical relationships. The solution presents mathematical relationships resulting from the formulation process are solved to identify the optimal solution.

Interpretation and What-if Analysis: A problem solver or analyst interprets the results and implications of problem solution. The main purpose of this solver is to investigate changes in input parameters and model variables and impacts on problem solution results.

Basic assumptions of linear programming:

1. Conditions of certainty exist.
2. Proportionality in the objective function and constraints to form equations showing the relationship between variables (1 unit – 3 hours, 3 units- 9 hours).
3. Additivity property which includes that the total of all activities equals the sum of individual activities.
4. Divisibility assumption that solutions don’t need to be in whole numbers (integers); ie. decision variables can take on any fractional value in the problem solver.

Example: Toy manufacturer can produce skateboards and dolls. Both require plastic, of which there are 60 units available. Skateboards take five units of plastic while making  \$1 profit. Dolls take two units of plastic to make a \$0.55 profit.

What is the number of dolls and skateboards the company can produce to maximize profit for the manufacturer?

First, identify components of the problem:

1. Resources – Plastic (60 available)

2. Products – Skateboards & Dolls

3. Recipes – Skateboards (5 units), Dolls (2 units)

4. Profits – Skateboards (\$1.00), Dolls \$0.55)

5. Objective – Maximize profit

Second, make a mixture chart:

Groups of Equations:

– Objective Equation (profit equation)

– Constraints (minimum constraints, resource constraints…)

Objective Equation – total profit given for a number of units produced

P = 1x + 0.55y

Constraints – usually inequalities

5x + 2y ≤ 60