# LINEAR PROGRAMMING AND OPTIMIZATION TECHNIQUES

## PRIMAL TO DUAL LINEAR PROGRAMMING

PRIMAL TO DUAL CONVERSION RULE

EXAMPLE

Find dual from primal conversion

MAX Z = 40x1 + 30x2

subject to

x1 + x2 <= 120

4x1 + 2x2 <= 320

and, x1,x2 >=0

Solution

According to the conversion rule:

Dual is:

MIN Zy = 120Y₁ + 320Y₂

subject to

Y1 + 4Y2 ≥40

Y1 +2Y2 ≥30

and Y₁, Y₂ ≥ 0;

SOLVE THIS PROBLEM USING A CALCULATOR

https://cbom.atozmath.com/CBOM/Simplex.aspx?q=pd&q1=2%602%60MAX%60Z%60×1%2cx2%6040%2c30%601%2c1%3b4%2c2%60%3c%3d%2c%3c%3d%60120%2c320%60%60D%60false%60true%60false%60true%60false%60false%60true&do=1#PrevPart

## TRANSPORTATION PROBLEM

Transportation is a special type of Linear Programming Problem (LPP) in which goods are transported from a collection of sources to a destination depending on supply and demand of resources and location respectively so that the total amount of transport is reduced. Icon and is sometimes called the Hitchcock problem.

NOTE: Check problem is balanced(supply = demand) or Unbalanced(supply not equal to demand).

CHANGE UNBALANCED TO BALANCED

If Transportation Problem is an Unbalanced problem i.e supply and demand are not equal then

Add dummy row or column (if demand is less than supply then add dummy column and if supply is less then add dummy row)

Example:

THIS IS AN UNBALANCED TRANSPORTATION PROBLEM CASE:

SO CONCEPT OF DUMMY ROW OR COLUMN WILL BE USED HERE.

A/Q  DEMAND IS LESS THAN SUPPLY SO WE HAVE TO ADD A DUMMY COLUMN TO MAKE IT EQUAL.

WE HAVE TO ADD (117-95 =22) TO DEMAND.

NOW OUR PROBLEM IS BALANCED.

NOW USE ANY OF THREE METHODS TO GET TRANSPORTATION COSTS:

Minimum Transportation Cost Calculator Using North West Corner Method

https://www.easycalculation.com/operations-research/minimum-transportation-northwest-corner-method.php

Minimum Transportation Cost Calculator Using Least cost Method

https://www.easycalculation.com/operations-research/minimum-transportation-least-cost-method.php

Minimum Transportation Cost Calculator Using Vogel’s Approximation Method

https://www.easycalculation.com/operations-research/minimum-transportation-vogel-approximation-method.php

MODI METHOD( TO GET MINIMUM OR OPTIMUM TRANSPORTATION COST):

https://www.easycalculation.com/operations-research/minimum-transportation-modi-method.php

### Assignment Problem

An assignment problem is a particular case of a transportation problem where the aim is to provide a number of resources to an equal number of jobs to reduce total cost or maximize total profit.

The problem of assignment arises because available resources such as men, machines, etc. they have different levels of efficiency in performing different tasks, therefore, the cost, profit, or loss of performing different functions is different.

http://cbom.atozmath.com/CBOM/Assignment.aspx?q=hm

### Travelling Salesman Problem

The travelling salesman problem consists of the seller and the group of cities. The seller must visit each city from a specific location (e.g home town) and return to the area of the same city. The challenge of the problem is that the travelling seller wants to minimize the amount the length of the journey.

Travelling Salesman Problem is Based on Hamiltonian cycle.

A Hamiltonian cycle is a cycle in a graph that visits all the vertices once.

https://www.easycalculation.com/operations-research/traveling-salesman-problem.php

### Dual Simplex method

Dual simplex method Steps (Rule)

http://cbom.atozmath.com/CBOM/Simplex.aspx?q=ds

### Simplex method (BigM method)

In order to find the first possible solution, it is necessary to convert the given LPP into its standard form; in order to obtain a standard form; a non-negative variable is added to the left side of each figure that lacks the most basic variables. The additional variable is therefore called an artificial variable and plays a role in providing the first possible solution.

The beginning of the Big-M approach is a basic solution to the problem of performance. This solution allows us to start the Simplex algorithm quickly, but it is not a possible solution to the initial problem. Our goal is to duplicate solutions within a possible real set, assuming it is empty.

http://cbom.atozmath.com/CBOM/Simplex.aspx?q=sm

### Linear Programming Problem

The main goal of linear programming is to optimize or maximize numeric values. It contains linear functions which are subject to its constraints which are in linear form or inequality form.

LPP is a special technique to find optimize resource utilization.

https://www.wolframalpha.com/widgets/view.jsp?id=daa12bbf5e4daec7b363737d6d496120

### LINEAR PROGRAMMING PROBLEM GRAPHICAL METHOD

RULES OF GRAPHICAL METHOD

1. Replace every inequality sign to equal(=) sign for every constraints
2. Find the two points from each constraint and draw those points on graph.
3. Find area of feasible solution and shade that common area.
4. Find extreme points of that feasible region.
5. Calculate Objective function using extreme points.
6. Find maximum and minimum value of that objective function.

NOTE: IF THERE ARE MORE THAN TWO VARIABLES IN OBJECTIVE FUNCTION OR CONSTRAINTS THEN USE THE SIMPLEX METHOD TO SOLVE THEM.

http://cbom.atozmath.com/CBOM/Simplex.aspx?q=gm

### TWO PHASE METHOD

RULES FOR TWO-PHASE METHOD

PHASE 1

1. Formation of new objective function by assigning zero to all original variable  and put -1 to all artificial variables.
2. By using Simplex method eliminate artificial variable from basis.
3. At End of phase 1 we ‘ll get basic feasible solution for phase 2.

PHASE 2

1. In phase 2 original objective fn is used and all artificial variable coefficient become 0 so, Artificial variables get removed from the whole process.

Now, We can use the simplex method algorithm to find optimal Solution

http://cbom.atozmath.com/CBOM/Simplex.aspx?q=tp

### Bisection method

The Bisection method is the measurement method for obtaining the roots of a given number by dividing the interval.

This method will divide the interval until the resulting interval is obtained which is so small.

Example

Let say given interval is [a,b] in bisection method

Then,

Midpoint of interval = a+b/2

https://atozmath.com/CONM/Bisection.aspx

### Newton Raphson method

The Newton-Raphson method is one of the best methods for root finding.

Like other methods, the bisection and false position methods, the Newton-Raphson technique requires only one initial value say x0.

https://atozmath.com/CONM/Bisection.aspx?q=nr

### Numerical Interpolation using Forward, Backward, Divided Difference

Interpolation is a simple way to find a function in a separate set of data so that the function can pass through the given data points.

This method is always required to calculate the intermediate value of an independent function.

LINEAR INTERPOLATION FORMULA:

y= y1+x-x1/x2-x1 *(y2-y1)

LAGRANGE’S INTERPOLATION FORMULA:

y= {(x-x1)(x-x2)…(x-xn)/(x0-x1)(x0-x2)..(x0-xn)}y0  + {(x- x0)(x-x2)…(x-xn)/(x1- x0)(x1-x2)..(x1-xn)}y1 + ……..+

DIFFERENT TYPES OF INTERPOLATION METHODS:

• Linear Interpolation Method
• Nearest Neighbour Method
• Cubic Spline Interpolation Method
• Shape-Preservation Method
• Thin-plate Spline Method
• Biharmonic Interpolation Method

https://atozmath.com/CONM/NumeInterPola.aspx

#### ALSO CHECK SOME OTHER METHODS OPTIMIZATION CALCULATOR:

Numerical Differentiation using Lagrange’s formula calculator

https://atozmath.com/CONM/NumeDiff.aspx?q=LI

Gaussian elimination

https://onlinemschool.com/math/assistance/equation/gaus/

GAUSS NEWTON METHOD