
As mentioned in Linear Program almost every linear program has to be converted to Standard Form. There are several situations could be encountered:
Maximization linear program lies to find such values of variables that maximize the objective function. Such type of linear program can be converted to minimization linear program simply by multiplying the objective function by a negative sign. For example,
Maximize f(X) = 12x_{1} + 4x_{2}  6x_{3}.
Converted linear program is the following:
Minimize f(x) = 12x_{1}  4x_{2} + 6x_{3}
Both the linear programs are the same.
Negative Values on the RightSide of Constraints
All constraints in Standard Form of linear program are required to have positive rightsides. If any constraint has negative quantity at the rightside then this constraint has to be multiplied by 1 and the direction of inequality has to be swapped (that <= becomes >=, and vice versa). For example:
4x_{1} + 5x_{2}  6x_{3} >= 4.2 is the same as 4x_{1}  5x_{2} + 6x_{3} <= 4.2
Linear program constraint of this type has to be converted by adding one extra positive variable (called a slack variable) to convert to Less or Equal (<=) type. Slack variable has 0 as costs coefficient in appropriate position in the linear program objective function. For example:
Minimize f(x) = 2x_{1} + 3x_{2}  4x_{3}
Subject to x_{1} + 2x_{2} < 4
x_{1}  x_{3} <= 5
x_{1},x_{2},x_{3} >= 0
The slack variable x4 is added to the first constraint and the linear program is converted as the following:
Minimize f(x) = 2x_{1} + 3x_{2}  4x_{3} + 0x_{4}
Subject to x_{1} + 2x_{2} + x_{4} <= 4
x_{2}  x_{3} <= 5
x_{1},x_{2},x_{3},x_{4} >= 0
Greater (Greater or Equal) than Type Constraints
Linear program constraint of this type has to be converted by subtracting one extra positive variable (called a surplus variable) to convert to Equal (=) type. Surplus variable has 0 as costs coefficient in appropriate position in the linear program objective function. For example:
Minimize f(x) = 2x_{1} + 3x_{2}  4x_{3}
Subject to x_{1} + 2x_{2} >= 4
x_{2}  x_{3} <= 5
x_{1},x_{2},x_{3} >= 0
The surplus variable x_{4} is subtracted from the first constraint and the linear program is converted as the following:
Minimize f(x) = 2x_{1} + 3x_{2}  4x_{3} + 0x_{4}
Subject to x_{1} + 2x_{2}  x_{4} <= 4
x_{2}  x_{3} <= 5
x_{1},x_{2},x_{3},x_{4} >= 0
The Standard Form of linear program requires all variables to be positive. If some of variables are not restricted to be positive only then those variables have to be substituted by the difference of two positive variables. For example, if variable x_{2} is unrestricted in sign, it is replaced by two new positive variables x_{21} and x_{22} with x_{2} = x_{21} x_{22}.
Example:
Minimize f(x) = 2x_{1} + 3x_{2}  4x_{3}
Subject to x_{1} + 2x_{3} >= 40
x_{1}  x_{2} <= 5
x_{1},x_{2} >= 0
So, x_{3} is unrestricted in sign. Substitute x_{3} by x_{31}  x_{32}. The linear program is the following now:
Minimize f(x) = 2x_{1} + 3x_{2}  4x_{3}
Subject to x_{1} + 2x_{31}  2x_{32} >= 40
x_{1}  x_{2} <= 5
x_{1},x_{2},x_{31},x_{32} >= 0
If a variable has a negative lower bound then another method is applied. Let assume that variable x_{2} has lower limit L = 20. Then all linear program constraints contained x_{2} have to be modified as the following:
x_{1} + 2x_{2} >= 40
x_{1} >= 0, x_{2} >= L
Introduce variable y_{2} = x_{2}  L (hence, x_{2} = y_{2} + L) and rearrange the constraint as:
x_{1} + 2y_{2} + 2L >= 40
Finally:
x_{1} + 2y_{2} >= 40  2L
x_{1}, y_{2} >= 0
linear programming GIPALS Start
Linear programming examples
There are several examples of linear programming intended to make the users of GIPALS familiar with it. These examples are included in GIPALS installation and can be found in ..\GIPALS\Examples folder.
See Screen Shots: Variables Page  Calculation Process  Constraint Page (Compact view)  Matrix Palette Dialog  Result Page  Debug Options Dialog
GIPALS Linear Programming $197.95  15000 Constraints & Variables  $297.00  Unlimited Number of Constraints & Variables
Special ! Free Choice of Complete Excel Training Course or Excel Addins Collection on all purchases totaling over $70.00. ALL purchases totaling over $150.00 gets you BOTH! Purchases MUST be made via this site. Send payment proof to special@ozgrid.com 31 days after purchase date.
Instant Download and Money Back Guarantee on Most Software
Excel Trader Package Technical Analysis in Excel With $139.00 of FREE software!
Microsoft ® and Microsoft Excel ® are registered trademarks of Microsoft Corporation. OzGrid is in no way associated with Microsoft
Some of our more popular products are below...
Convert Excel Spreadsheets To Webpages  Trading In Excel  Construction Estimators  Finance Templates & Addins Bundle  CodeVBA  SmartVBA  PrintVBA  Excel Data Manipulation & Analysis  Convert MS Office Applications To......  Analyzer Excel  Downloader Excel
 MSSQL Migration
Toolkit 
Monte Carlo Addin 
Excel
Costing Templates