A Computer Technique for Duality Theory in Linear Programs
A. K. M. Nazimuddin, Ahsan Ali
Department of Electronics and Communications Engineering, East West University, Dhaka, Bangladesh
Email address:
A. K. M. Nazimuddin, Ahsan Ali. A Computer Technique for Duality Theory in Linear Programs. American Journal of Applied Mathematics. Vol. 3, No. 3, 2015, pp. 95-99. doi: 10.11648/j.ajam.20150303.13
Abstract: The aim of this paper is to develop a computer oriented program for analyzing duality of a Linear Program (LP) by the programming language MATHEMATICA. Also we will show the efficiency of our program by analyzing the duality with numerical examples.
Keywords: Linear Programs, Duality, Computer Technique
1. Introduction
Linear Programming (LP) has a wide range of applications including agriculture, industry, transportation and other problems in economics and management sciences. Linear programming is programming in science of planning which deals with situations where a number of resources, such as men, materials, machines are to be combined to yield one or more products. Usually programming is a common word which is related to computer developments. When it’s required to solve any LP problems, in practice is too difficult. But using computer programming it’s easy to solve. Sometimes, we need to change the data values of the solution and this type of changes brings the concept of Duality in linear programming.
2. Linear Programs
We first briefly discuss the general LP problems. Consider the standard LP problem as follows,
Maximize (1)
Subject to (2)
(3)
where is an matrix, . Let be any non-singular sub-matrix ofand be the vector of variables associated with the columns of . The general properties and solution procedures of LP problems can be found in [1] and [2]. Also we can be found a history of LP in [3]. We will now concentrate our discussion into duality theory.
3. Duality Theory
From both the theoretical and practical point of view, the theory of duality is one of the most important tools for developing computational procedures that take advantage of the relationships between the primal and dual problems .The basic idea behind the duality theory is that every linear programming problem has an associated linear program called its dual problem .The original problem is called primal problem also gives a solution to the dual problem and vice-versa. On the other hand, the most famous duality theory for multiobjective linear programs is due to Isermann (see [4,5]). Isermann's dual solutions also verify some primal-dual relations and measure the primal sensitivity if the Pareto solutions of the program are restricted to be basic feasible solutions of the primal feasible set.
Weak duality property: If is a feasible solution for the primal problem and is a feasible solution for the dual problem, then.
Strong duality property: If is an optimal solution for the primal problem and is an optimal solution for the dual problem, then.
Thus, these two properties imply thatfor feasible solutions if one or both of them are not optimal for their respective problems, whereas equality holds when both are optimal. [6]
4. Complementary Slackness Condition
The Theorem of Complementary Slackness [7] is an important result that relates the optimal primal and dual solutions. To state this theorem, we assume that the primal is a normal max problem with variables,,and constraints. Let,,be the slack variables for the primal. Then the dual is a normal min problem with variables,,and constraints. Let ,, be the excess variables for the dual. A statement of the theorem of Complementary Slackness as follows. Let be a feasible solution and be a feasible dual solution. Then is primal optimal and is dual optimal if and only if
(4)
(5)
From (4), it follows that the optimal primal and dual solutions must satisfy
primal slack 0 implies dual variable0 (6)
dual variable 0 implies primal slack 0 (7)
From (5), it follows that the optimal primal and dual solutions must satisfy
dual excess 0 implies primal variable 0 (8)
primal variable 0 implies dual excess 0 (9)
From (6) and (8), we see that if a constraint in either the primal or dual is non-binding (has either 0 or 0), then the corresponding variable in the other (or Complementary) problem must equal 0.
5. Dual Simplex Method
Dual Simplex Method of solving a LP Problem is one of the methods of solving a LP problem in which the theory relating to primal problem has been developed with the help of the properties of its dual problem. That is why, the method is known as Dual Simplex Method (DSM). In this method we try to move from infeasible optimality to the feasible optimality. Using this method, we are able to solve many problems without using artificial variables. Now we will discuss the dual simplex algorithm as follows:
STEP (0) The problem is initially in canonical form and all 0.
STEP (1) If 0, 1, 2, then stop, we are optimal. If we continue, then there exists some 0.
STEP (2) Choose the row to pivot in (i.e., variable to drop from the basis) by:
0
If 0, 1, 2, …, then stop; the primal problem is infeasible (dual unbounded). If we continue, then there exists 0 for some 1, 2, …,.
STEP (3) Choose column s to enter the basis by:
0
STEP (4) Replace the basic variable in row with variable and re-establish the canonical form (i.e., pivot on the coefficient).
STEP (5) Go to step (1).
6. Main Program
In this section, we discuss our computer oriented program with its algorithm. We have used the programming language Mathematica [8]for developing our computer oriented program for duality theory. For our program we need an LP problem which is solved by any method.
6.1. Algorithm
Input:, real matrix, a set of constants and a set of cost vector components.
Step 1: Express the LP to its standard form.
Step 2: Find all sub-matrices of the coefficient matrix by setting variables equal zero.
Step 3: Test whether the linear system of equations has unique solution or not.
Step 4: If the linear system of equations has got any unique solution, find it.
Step 5: Dropping the solutions with negative elements. Determine all basic feasible solutions.
Step 6: Calculate the values of the objective function for the basic feasible solutions found in step 5.
Step 7: For the maximization of LP, the maximum value of is the optimal value of the objective function and the basic feasible solution which yields the optimal value is the optimal solution.
Now we develop a Mathematica code for solving LP problems.
6.2. Mathematica Code for Solving LP
Now, we present our computer codes of Mathematica for analyzing duality theory. We have written the following codes using Mathematica 5.2. Our computer oriented program is presented as follows:
<<LinearAlgebra`MatrixManipulation`
basic[AA_,bb_]:=Block[{m,n,pp,ss,ns,B,v,vv,var,vplus,vzero,BB,RBB,sol,new,sset,bs},{m,n}=Dimensions[AA];pp=Permutations[Range[n]];
ss=Union[Table[Sort[Take[pp[[k]],m]],{k,1,Length[pp]}]];
ns=Length[ss];B={};
For[k=1,k<=ns,k=k+1,v=Table[TakeColumns[AA,{ss[[k]][[j]]}],{j,1,m}];
vv=Transpose[Table[Flatten[v[[i]]],{i,1,m}]];
B=Append[B,vv]];
var=Table[x[i],{i,1,n}];
vplus[k_]:=var[[ss[[k]]]];
vzero[k_]:=Complement[var,vplus[k]];
sset={};For[k=1,k<=ns,k=k+1,BB=B[[k]];RBB=RowReduce[BB];
If[RBB==IdentityMatrix[m],sol=LinearSolve[BB,bb],sol={}];
If[Length[sol]==0||Min[sol]<0,new={},new=sol;
sset=Append[sset,{vplus[k],new}]]];
bs[k_]:=Block[{u,v,w,zf1,f2},
u=sset[[k,1]];v=sset[[k,2]];w=Complement[var,u];
z=Flatten[ZeroMatrix[Length[w],1]];
f1=Transpose[{u,v}];f2=Transpose[{w,z}];
Transpose[Union[f1,f2]][[2]]];
Table[bs[k],{k,1,Length[sset]}]]
optimal [AA_, bb_, cc_]:= Block[{vertex, val, opt, pos, optsol, lpsoln},
vertex = basic [AA, bb];
val = Table[vertex[[k]].c, {k, 1, Length[vertex]}];
opt = Min/Max[val];
pos = Flatten[Position[val, opt]];
optsol = vertex[[pos[[1]]]];
lpsoln = {optsol, opt};
Print ["The optimal value of the objective function is ", lpsoln[[2]]];
Print ["The optimal solution is ", lpsoln[[1]]]]
Now we will compare and discuss the following numerical examples with the methods discussed in section 4, 5 and with our developed program discussed in section 6.2.
7. Numerical Illustrations
In this section, we use two different examples to illustrate our computer oriented program.
7.1. Example 1
A factory manufactures three products, which require three resources - labor, materials, and administration. The unit profits on these products on these products are 10, 6 and4 respectively. There are 100 of labor, 600 of material, and 300 of administration available per day. In order to determine the optimal product mix, the following LP model is formulated,
Max 1064
Subject to100 (labor)
1045600 (material) 226300(administration)
, 0
where, , and are the daily production levels of products 1, 2 and 3 respectively [9] and the dual of the above problem is
Min100600300
Subject to10210
426
564
0
The solution of the problem can be found from any existing technique[10] as, the optimal primal solution is 100/3, 200/3, 000100 and Max 2200/3. The optimal dual solution is 10/32/300, 08/3 and Min2200/3
From the Complementary Slackness condition, (4) reduces to = 0, which is indeed satisfied by the optimal primal and dual solutions. Again, from the Complementary Slackness condition, (5) reduces to 0, which is also satisfied by the optimal primal and dual solutions.
According to the dual simplex algorithm discussed in section 5.1, the dual simplex method cannot be applicable for the primal problem, then it is impossible to solve the LP by using dual simplex method and also for the dual problem we can solve this with the help of dual simplex method. The optimum feasible solution is 10/3, 2/3, 0, 0,0,8/3 andMin2200/3.
Now we will illustrate this numerical example with our computer technique.
If we write the Mathematica code written in section 6.2 with opt = Max[val];in place ofopt = Min/Max[val];for this particular factory problem (primal problem) given with all input data values as bellow:
A={{1,1,1,1,0,0},{10,4,5,0,1,0},{2,2,6,0,0,1}};
b={100,600,300};
c={10,6,4,0,0,0};
basic[A,b]
optimal[A, b, c]
Now, if we run the above program, we will appear the following output as:
{{175/6,275/6,25,0,0,0},{100/3,200/3,0,0,0,100},{42,0,36,22,0,0},{60,0,0,40,0,180},{0,75,25,0,175,0},{0,100,0,0,200,100},{0,0,50,50,350,0},{0,0,0,100,600,300}}
The optimal value of the objective function is 2200/3
The optimal solution is {100/3,200/3,0,0,0,100}
We get the same solution as in previously discussed methods.
Now to get the solution of the dual problem with opt = Min[val];in place ofopt = Min/Max[val] in the Mathematica code written in section 6.2, we have to change only input as:
A={{1,10,2,-1,0,0},{1,4,2,0,-1,0},{1,5,6,0,0,-1}};
b={10,6,4};
c={100,600,300,0,0,0};
basic[A,b]
optimal[A, b, c]
Now, if we run the program, we will appear the following output as:
{{10/3,2/3,0,0,0,8/3},{10,0,0,0,4,6},{0,2/3,5/3,0,0,28/3},{0,3/2,0,5,0,7/2},{0,0,5,0,4,26}}
The optimal value of the objective function is 2200/3
The optimal solution is {10/3,2/3,0,0,0,8/3}
7.2. Example 2
Consider, the following problem
Max 35
Subjectto 3218
4
6
, 0
And the dual of the above problem is
Min1846
s. t. 3+ 3
2+5
,, 0
The solution of the problem can be found from any existing technique as: The optimal primal solution is 2,6, 0, 2, 0 and Max 36.The optimal dual solution is1,0, 3, 0, 0 and Min 36. Now, from the Complementary Slackness condition, (4) reduces to 0, which is indeed satisfied by the optimal primal and dual solutions. Again, from the Complementary Slackness condition, (5) reduces to0, which is also satisfied by the optimal primal and dual solutions.
According to the dual simplex algorithm discussed in section 5.1, the dual simplex method cannot be applicable for the primal problem, then it is impossible to solve the LP by using dual simplex method and also for the dual problem we can solve this with the help of dual simplex method. The optimum feasible solution is 1,0, 3, 0, 0 and Min 36.
Now we will illustrate this numerical example with our computer technique.
If we write the Mathematica code written in section 6.2 with opt = Max[val];in place ofopt = Min/Max[val];for this particular factory problem (primal problem) given with all input data values as bellow:
A={{3,2,1,0, 0},{1,0,0,1, 0}, {0, 1, 0, 0, 1}};
b={18,4,6};
c={3,5,0,0, 0};
basic[A,b]
optimal[A, b, c]
Now, if we run the above program, we will appear the following output as:
{{2,6,0,2,0},{4,3,0,0,3},{4,0,6,0,6},{0,6,6,4,0},{0,0,18,4,6}}
The optimal value of the objective function is 36
The optimal solution is {2,6,0,2,0}
We get the same solution as in previously discussed methods.
Now to get the solution of the dual problem with opt = Min[val];in place ofopt = Min/Max[val] in the Mathematica code written in section 6.2, we have to change only input as:
A={{3,1,0,-1,0},{2,0,1,0, -1}};
b={3, 5};
c={18,4,6,0,0};
basic[A,b]
optimal[A,b,c]
Now, if we run the program, we will appear the following output as:
{{1,0,3,0,0},{5/2,0,0,9/2,0},{0,3,5,0,0}}
The optimal value of the objective function is 36
The optimal solution is {1,0,3,0,0}
By our program, we can analyze the duality theory of various LP problems by changing only input values. Finally, we can say that, our computer oriented program with Mathematica for analyzing duality theory of an LP problem is more efficient than any method.
8. Conclusion
The program developed by us is a powerful program, because we can analyze the duality theory of any LP problem by this program in one click with entering some necessary data values. Hand calculation is very tough and time consuming for analyzing duality theory of an LP problem with large number of variables and constraints, where we can do the same by our program within a second by one click. Nowadays, the world is being ruled by the fastest. So we must try to finish our job as fast as we can. If we can find a way to solve a problem in a very short time, then what will we use the time consuming methods? Many practical problems formulated as linear programs run into hundreds of constraints and thousands of decision variables. Computer technique is the best way to analyze with such a large amount of data values. We can analyze the duality theory of any kind of problem by our program, no matter how big it is or solved by which method.
References