Sign Up

Sign In

Forgot Password

Lost your password? Please enter your email address. You will receive a link and will create a new password via email.

You must login to ask a question.

LINEAR PROGRAMMING AND OPTIMIZATION TECHNIQUES

PRIMAL TO DUAL LINEAR PROGRAMMING

PRIMAL TO DUAL CONVERSION RULE

In PrimalThen in Dual
The objective function is maximumThe objective function is minimum
x1 unrestricted in sign1st constraint is = type
1st constraint is = typey1 unrestricted in sign
the constraint is ≤ typethe constraint is ≥ type
Objective function : total 3 variables (x1,x2,x3) and coefficient c1,c2,c3constraints : 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,b2Objective function : total 2 variables (y1,y2) and coefficient c1,c2. (b1 becomes c1, b2 becomes c2)

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:

 D1D2D3D4D5SUPPLY
O15187515
O23967825
O34276542
O4711104935
DEMAND3020151020(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.

 D1D2D3D4D5D6(DUMMY)SUPPLY
O151875015
O239678025
O342765042
O47111049035
DEMAND302015102022(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

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.

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)

Step1Formulate 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.
Step2Find out the Initial basic solution  
Find the initial basic feasible solution by setting zero value to the decision variables.  
Step3Test for Optimality  
a. If all the values of XB≥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

  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.

CALCULATOR LINK:

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

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

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

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 fractions

//www.discoverturnkey.com

cqb traininghuaykk.coCloud GPU with up to 80GB VRAM A100, gpu rental at cheap prices. Deploy popular flavors like PyTorch, Jupyter, or any AI model.

Leave a comment

You must login to add a new comment.