Table of Contents

## LINEAR PROGRAMMING AND OPTIMIZATION TECHNIQUES

### PRIMAL TO DUAL LINEAR PROGRAMMING

**PRIMAL TO DUAL CONVERSION RULE**

In Primal | Then in Dual |

The objective function is maximum | The objective function is minimum |

x1 unrestricted in sign | 1st constraint is = type |

1st constraint is = type | y1 unrestricted in sign |

the constraint is ≤ type | the constraint is ≥ type |

Objective function : total 3 variables (x1,x2,x3) and coefficient c1,c2,c3 | constraints : total 3 constraints and right hand side constraint b1,b2,b3. (c1 becomes b1, c2 becomes b2, c3 becomes b3) |

constraints : total 2 constraints and right hand side constraint b1,b2 | Objective function : total 2 variables (y1,y2) and coefficient c1,c2. (b1 becomes c1, b2 becomes c2) |

__EXAMPLE__

Find dual from primal conversion

MAX Z = 40x_{1} + 30x_{2}

subject to

x_{1} + x_{2} <= 120

4x_{1} + 2x_{2} <= 320

and, x_{1},x_{2} >=0

__Solution__

According to the conversion rule:

**Dual is:**

MIN Zy = 120Y₁ + 320Y₂

subject to

Y_{1} + 4Y_{2} ≥40

Y_{1} +2Y_{2} ≥30

and Y₁, Y₂ ≥ 0;

__SOLVE THIS PROBLEM USING A CALCULATOR__

### 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:**

D1 | D2 | D3 | D4 | D5 | SUPPLY | |

O1 | 5 | 1 | 8 | 7 | 5 | 15 |

O2 | 3 | 9 | 6 | 7 | 8 | 25 |

O3 | 4 | 2 | 7 | 6 | 5 | 42 |

O4 | 7 | 11 | 10 | 4 | 9 | 35 |

DEMAND | 30 | 20 | 15 | 10 | 20 | (demand)95\(supply)117 |

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.

D1 | D2 | D3 | D4 | D5 | D6(DUMMY) | SUPPLY | |

O1 | 5 | 1 | 8 | 7 | 5 | 0 | 15 |

O2 | 3 | 9 | 6 | 7 | 8 | 0 | 25 |

O3 | 4 | 2 | 7 | 6 | 5 | 0 | 42 |

O4 | 7 | 11 | 10 | 4 | 9 | 0 | 35 |

DEMAND | 30 | 20 | 15 | 10 | 20 | 22 | (demand)117\(supply)117 |

NOW OUR PROBLEM IS BALANCED.

NOW USE ANY OF THREE METHODS TO GET TRANSPORTATION COSTS:

**TRANSPORTATION PROBLEM CALCULATORS LINKS:**

__Minimum Transportation Cost Calculator Using North West Corner Method__

__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__

__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.

**ASSIGNMENT PROBLEM**** CALCULATOR LINK:**

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.

**TRAVELLING SALESMAN PROBLEM CALCULATOR LINK:**

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

**Dual Simplex method**

**Dual simplex method Steps (Rule)**

Step1 | Formulate the Problem a. Formulate the mathematical model of the given LPP b. If the objective function is minimized then convert it into maximize. c. Convert all ≥ constraint to ≤ constraint by multiply -1 d. Convert each and every ≤ constraint into an = constraint by adding a slack variable to every constraint and assigning a 0 cost coefficient in the objective fn. |

Step2 | Find out the Initial basic solution Find the initial basic feasible solution by setting zero value to the decision variables. |

Step3 | Test for Optimality a. If all the values of X _{B}≥0, then-current solution is the optimal solution, terminate the process. b. If any XB<0, then select the Minimum negative XB, and this row is called key row. c. Find Ratio= Cj-Zj / KeyRowj and KeyRowj<0. d. Find Minimum +ve ratio, and this column is called a key column. e. Find the new solution table. f. Repeat step-3. |

**Dual** **Simplex Method Calculator Link:**

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.

**Simplex Method Calculator Link:**

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.

** LINEAR PROGRAMMING PROBLEM CALCULATOR LINK:**

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

### LINEAR PROGRAMMING PROBLEM GRAPHICAL METHOD

**RULES OF GRAPHICAL METHOD**

- Replace every inequality sign to equal(=) sign for every constraints
- Find the two points from each constraint and draw those points on graph.
- Find area of feasible solution and shade that common area.
- Find extreme points of that feasible region.
- Calculate Objective function using extreme points.
- 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.**

__CALCULATOR LINK:__

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

### TWO PHASE METHOD

**RULES FOR TWO-PHASE METHOD**

**PHASE 1**

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

**PHASE 2**

- 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

**TWO PHASE METHOD CALCULATOR LINK:**

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**

** BISECTION METHOD CALCULATOR LINK:**

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 *x*_{0}.

**NEWTON-RAPHSON METHOD CALCULATOR LINK:**

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= y_{1}+x-x_{1}/x_{2}-x_{1} *(y_{2}-y_{1})

**LAGRANGE’S INTERPOLATION FORMULA:**

y= {(x-x_{1})(x-x_{2})…(x-x_{n})/(x_{0}-x_{1})(x_{0}-x_{2})..(x_{0}-x_{n})}y_{0} + {(x- x_{0})(x-x_{2})…(x-x_{n})/(x_{1-} x_{0})(x_{1}-x_{2})..(x_{1}-x_{n})}y_{1 + ……..}+

**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

**INTERPOLATION CALCULATOR LINK:**

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

__ALSO CHECK SOME OTHER METHODS OPTIMIZATION CALCULATOR:__

**Numerical Differentiation using Lagrange’s formula calculator**

__CALCULATOR LINK:__

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

**Gaussian elimination**

__CALCULATOR LINK:__

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

**GAUSS NEWTON METHOD**

__CALCULATOR LINK:__

https://keisan.casio.com/exec/system/1244946907

Also Check:

Numerical Optimization Techniques and Dynamic Programming Lagrange Multipliers Knapsack

adding and subtracting fractionsCloud GPU with up to 80GB VRAM A100, gpu rental at cheap prices. Deploy popular flavors like PyTorch, Jupyter, or any AI model.huaykk.co
## Leave a comment