An assessment on the effect of different characteristics of symmetric matrices to primal and dual solutions in linear programming
A linear optimization model or linear programming (LP) problem involves the optimization of linear function subject to linear constraints, where every constraints form oflinear equation. In particular this research is focused on an interpretation on the effect of five different characteristics of...
Saved in:
| Main Author: | |
|---|---|
| Format: | Thesis |
| Language: | English English |
| Published: |
2013
|
| Subjects: | |
| Online Access: | http://eprints.utem.edu.my/id/eprint/14954/1/An%20assessment%20on%20the%20effect%20of%20different%20characteristics%20of%20symmetric%20matrices%20to%20primal%20and%20dual%20solutions%20in%20linear%20programming.pdf http://eprints.utem.edu.my/id/eprint/14954/2/An%20assessment%20on%20the%20effect%20of%20different%20characteristics%20of%20symmetric%20matrices%20to%20primal%20and%20dual%20solution%20in%20linear%20programming%20problems.pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | A linear optimization model or linear programming (LP) problem involves the
optimization of linear function subject to linear constraints, where every constraints form
oflinear equation. In particular this research is focused on an interpretation on the effect of
five different characteristics of symmetric matrices i.e. positive definite (PD), negative
definite (ND), positive semi-definite (PSD), negative semi-definite (NSD), and indefinite
(ID) to primal-dual solutions (duality) in LP problems. Various sizes of matrices order
(5x5, 1Oxl0, 20x20, 30x30, 50x50) were simulated, each size simulated for 30 times.
There were 150 simulations of matrices generated for one type of matrix. In total, 750
simulated of LP problems were solved.
Based on simulations result, it was demonstrated that PD, ND, and some ID
symmetric matrices were non-singular, whereas PSD, NSD and some ID matrices have
been shown to be singular. An optimal solutions for a Primal and Dual of the PD, the PSD,
and some ID matrices have been found with no duality gap. These were due to the matrices
form a convex set of the LP problem. However, there was no optimal solution for the ND,
the NSD, some ID matrices, provided that some ID matrices were concave functions. If the
coefficient matrix of the LP problem was non-singular matrix then the LP solution did not
necessarily had the optimal solution. In other words there was no correlation between
singularity of the matrices and optimality of the Duality LP solutions. Experimental results
by the simulation in MATLAB and EXCEL Solver show that the optimal solutions of both
the primal and the dual solutions were same in the PD and the PSD matrices. This research
provided new findings about the effects of the different characteristics of five types of the
symmetric matrices in the LP duality problem which may contribute to an advancement of
the LP theory and practice. |
|---|