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