An LP problem asked in the comment

This is the only problem where it looked to me that the student has tried something from his side also. The question is as follows

min z=y1+y2
s.t
2y1+4y2>=4
y1+7y2>=7
y1,y2>=0
in simplex method.........solution........
max z*=-y1-y2
2y1+4y2-s1+a1=4
y1+7y2-s2+a2=7
y1,y2>=0
now.........z*+y1+y2=0
2y1+4y2-s1+a1=4
y1+7y2-s2+a2=7
y1,y2>=0
now here o.f line is positive so we apply M method(or due to artificial var.)then what is the next process i only want first iteration then after that i solve it.......

Before going further read the post titled "About Artificial Variables in Linear Programming (LP)" on this blog.

Artificial variables are needed to get the initial basic variables from the constraints of >= and = type. It will help to recall the properties of basic variables to understand the reason behind this.
To ensure that the artificial variables don't enter the basis after leaving, you have to associate a high penalty M in the o.f.

The revised O.f. is
max z* = -y1-y2. In maximization problem, high penalty means high negative coefficient of the variable.
so the o.f should be max z* = -y1-y2-Ma1-Ma2
Now, since a1 and a2 are to be in the initial basis, their co-efficients ahould be 0. To get this substitute
a1 = 4-2y1-4y2+s1 and a2 = 7-y1-7y2+s2 in this o.f. You can notice that these values of a1 and a2 have been taken from the two constraints where these variables were introduced.
So the o.f is max z* = -y1-y2-4M+2My1+4My2-Ms1-7M+My1+7My2-Ms2
= (3M-1)y1+ (11M-1)y2-Ms1-Ms2-11M
So now you have z*-(3M-1)y1-(11M-1)y2+Ms1+Ms2 = 11M

I hope, you can solve from here. You have to write the initial basic feasible solution table and do the simplex iterations. You can see that the most negative coefficient in the above o.f.line is for y2.

Revised Simplex Method

As we have been discussing that the revised simplex method is nothing different than the simplex method except that it's operations are based on matrix operations instead of elementary row operations in simplex. This approach is specially suited for computerization because it provides better computational performance and reduces truncation/ overflow errors. The below link will be useful. Go through this at your own pace and try to understand each step instead of memorizing them.

http://www.me.utexas.edu/~jensen/ORMM/methods/unit/linear/subunits/teach/teach_lp_revised.html

Sensitivity Analysis

Sensitivity analysis is also known as post-optimality analysis. And as the names indicate, it is some kind of analysis done after obtaining the optimal solution. This analysis is related to sensitivity of the solution towards possible changes in the problem.

Such analysis is very important considering that an LP represents a real life problem and there is always some possibility of changes in real life situation. So, if you formulate a LP for finding optimum product mix, solve it and the organization starts producing as per this; and one fine day the supplier of an important raw material cuts-down the supply changing the availability of the raw material. Will you have to again formulate the LP and solve? Similarly, if the management decides to introduce another product, will we have to do all the computation once again?

Sensitivity analysis analyses the impact of such changes on the optimal solution and helps us in getting the new optimal solution, if needed, without doing the entire exercise afresh. This analysis covers all possible changes such as:

-- Changes in the right hand side values in the LP,

-- Changes in the objective function coefficients,

-- Changes in the constraint coefficients,

-- Introduction or elimination of new constraint,

-- Introduction or removal of new product,

-- Changes in the valid range of decision variables, etc.

These changes can affect the optimality and feasibility of the solution. There is always a range of such changes in which the optimal solution remains unchanged. But, if a change is outside that range then the optimal solution changes. The changed optimal can be obtained easily from the previous optimal solution itself.

The basic Simplex iteration through an example

Following link describes a basic simplex iteration. Read it at your own pace and try to understand the concepts involved. Practice on at least one problem.

http://www2.isye.gatech.edu/~spyros/LP/node23.html#SECTION00050010000000000000

Post your comments freely so that I can understand the difficulty areas.

About Artificial Variables in Linear Programming (LP)

Another frequently asked question by students is related to use of artificial variables
while preparing the initial basic feasible solution table. The common flow of discussion
forces the student to think in a logical way as he has been thinking about slack and surplus
variables but the artificial variables can not be considered in the same logical category as
the previous two.

Just to recall, slack and surplus variables are used in LP to convert inequality constraints
to that of equality. If the constraint is of <= type, we add a slack variable to the left
hand side expression to make it equal to the right hand side value. It has some meaning. If
we write a constraint related to a raw material in a product mix problem, the left hand side
expression gives the raw material consumption while the r.h.s. value is the availabilty of
that raw material. The consumption has to be less than or equal to the availability, it can
not be more. And so the constraint is of <= type. The value of the slack variable is the
difference between the availability and the consumption. So at any stage it gives the
quantity of raw material unused.

Similarly, when the constraint is of >= type, we subtarct a surplus variable from the l.h.s.
expression to make it equal to the r.h.s. value. Why should such type of constraint arise in
real life situation? May be that the production of a product has to be more than a given
quantity because this much is needed by a very important customer. Or may be that intake of
a combination of items by human body has to be more than a prescribed quantity to keep the
body healthy. You can understand that here again the surplus variable has some meaning and
it's value gives an idea as to how much surplus one has produced or how much surplus one has
eaten.

Coming to the artificial variables, they don't have such meaning. Here, suddenly you have to
reduce your understanding capability. Don't try to find much meaning. Artificial variables
are not there to make out much meaning. They are used to get an initial basic variable from
the constraints while preparing the initial basic feasible solution table. Constraints of >=
type and = type don't provide any basic variable. So, artificial variable is added
arbitrarily to get the basic variable. And also a heavy penalty is associated for this
misdeed so that these variables are pushed out of the basis. Values of these variables don't
make much sense because they should go out of the basis and never come back. But if they
remain in the optimal basis then you have to say that there is no feasible solution to the
given LP. This conclusion depends just on the presence of the articial variable in the basis
of the optimal table, it doesn't change with it's value.

What is dual of a Linear Program?

During a lecture, some of the students were not clear about why do we think about the dual of a Linear Program and how this can be useful in various applications. Here some of the points are listed for ready reference:

1: With every linear program, there is a dual program associated. The relationship of dual variables with the values in the optimal primal table gives lot of useful information that can be used in decision making. If these features are build in the Business Intelligence Software, it can bring decison makers closer to decision.

2: If we maximize something say, profit in a product mix problem, we try to find out how much of different products should be produced under the constraints posed by availability of resources and demands so that the profit is maximum. When we solve this problem and move towards optimality, we are simultaneously minimizing the profit generating capability of the remaining resources. Thus another linear program which is actually a minimization problem is also getting solved simultaneously when we are solving the maximization problem. These problems are dual to each other.

3: Identifying the dual program is easy and the techniques are discussed in any book on OR. So, interested students can take help from there. But, if you find any difficulty, please get in touch by writing comment or at the contact detail available on the page.

4: Optimal solution of the primal problem gives solution of the dual problem as well. And this relationship can be used in making many decisions. To list a few:
... It can be used in finding out the resources that should be given priority in buying if additional fund is available.
... It can be used in deciding about the training priorities for different people.
... It can also be used in prioritizing the areas for technical improvements and so on.

You use your innovativeness and you can see that it can provide a useful tool in helping scientifc decision making in various areas. Some peoblems for practice will be posted soon.