Linear Programming: Solving Maximization Problems using Simplex Method

I seriously don't know how to start this post.

So let's put it this way: As the title says, this will be a tutorial for Linear Programming Simplex Method concentrating on Maximization Problems.

Linear Programming is a method of dealing with decision problems that can be expressed as constrained linear models. Simplex Method is a method formulated by George L. Dantzig in solving linear programming models.

Simplex Method is an iterative or repetitive process whereby, following a standard pattern, the computational process is repeated over and over until the optimum solution is reached. It starts with a zero profit (in maximization of profit problems) or with a very high cost figure (in minimization of cost problems). Gradually, the solution is improved until the optimum solution is reached.

 Procedures for Maximization of Profit Problems:

1. Represent the unknowns in the problems in mathematical form.
2. Tabulate the data about the facts (if necessary).
3. Formulate the objective function and constraints by restating the information in mathematical form.
• Objective Function - an expression which shows the relationship between the variables in the problem and the firm's goal.
• Structural Constraint (Explicit Constraint) - limit on the availability of resources.
• Non-negativity Constraint (Implicit Constraint) - restrict all the variables to zero or positive numbers.
4. Convert the constraints to equality.
• For <= inequalities, add slack variables the change the sign to =
• For >= inequalities, multiply the whole equation by -1, add slack variables, then change to = sign
• Ex. 2x + 9y >= 36        to       -2x - 9y + S1 = -36
• For equalities, just add slack variables.
5. Enter the coefficient of the constraints in the tableau. The tableau looks like the table at the bottom.
6. Determine the optimum column by choosing the largest positive entry in the [Cj - Zj] row.
7. Identify the pivot row by dividing the quantity columns to the optimal column.
8. Compute the values of the replacing row by dividing all the entries by the pivot.
9. Compute the new values of the remaining numbers.
10. Calculate Zj and [Cj - Zj]. If there are still positive entries in the [Cj - Zj] row, repeat from step 6.
11. If [Cj - Zj] row do not contain a positive entry, the tableau is optimum.

For illustration, I will use my homework. <(^^<)

Maximize:

   Zj = 4x + 2y - 3z + 5w

Subject to:

   2x - y + z + 2w >= 50

   3x - z + 2w <= 80

    x + y + w = 60

    x,   y,   z,   w   >= 0

Adding slack variables and changing inequalities, the new program would look like:

Maximize:

  Zj = 4x + 2y - 3z + 5w + 0S1 + 0S2 + 0S3

Subject to:

  -2x + y - z - 2w + S1 = -50

   3x - z + 2w + S2 = 80

    x + y + w + S3 = 60

    x,   y,   z,   w >= 0

Next step is to plot the constraints on the tableau.

To find Zj, multiply the Cj column with the values on the left. To find [Cj - Zj], subtract Zj from the uppermost values in the tableau. The results would be:

Now the optimum column is the column with the highest value. Column w is the optimum column with 5 as value.

To find the pivot row, Divide the values in the quantity column by the values in the optimum column. The row with the lowest positive value is the pivot row.

s1: -50 / -2 = 25

s2: 80 / 2 = 40

s3: 60 / 1 = 60

Now we will be computing the values of the incoming row (w). The values are computed as follows:

Next, we will be computing the values of the remaining row(s). This is done as follows:

Solving for the remaining rows, we have our next tableau (optimum column and pivot row highlighted).

Since there are still non-negative values in the [Cj - Zj] row, we will repeat steps 6 - 11.

Tableau 3 would look like this:

Again, there is still non-negative value, so repeat steps 6 - 11.

Tableau 4:

Since there are no more non-negative values in the tableau, the solution is now optimum.

The decision will be:

x = 0

y = 20

z = 0

w = 40

s1 = 10

s2 = 0

s3 = 0

Zj = 240

To check, you can substitute the values in the program we created earlier.

There are also online applications for solving linear programming problems using simplex method. Here are the sites.

http://adf.ly/DvW6

http://adf.ly/DvXE

Suggestions and comments will be appreciated. Thanks. (^^,)

Second Semester

So this is it.

Just this morning, I went to my college to see my grades and enroll as well. I was really nervous this morning because I have no idea what my grade will turn out knowing that I have not exerted any effort during my final exams (well that’s another story).

I was quite surprised that I don’t have any grades lower than 1.50. I have no hard copy yet since some of our teachers encoded our grades so late. However this is my grades according to the online database:

Yes, PE is included in computing our GWA. Well according to our school.

Enrollment.

Now comes the enrollment. This was a challenge for me, because for the first time, I had spent a whole day just to enroll. I normally consume just a couple of hours in the previous enrollments. But for this enrollment, I spent the whole day.

A whole working day. Even overtime.

I had two problems with this enrollment. First, my grades have been given a NC (no credit status) because of some unexplainable accountabilities with the Finance Department. Second, my enrollment was blocked because of organizational documents that is still not submitted to the OSA (I was the President of JPIA, and I still am. They rejected my resignation letter).

The Plight of the NC

After going to the Registrar, I went to the Finance Department to sign my clearance. I was forced by the Security Guards to wait in a long line when minutes later, they permitted those who need clearance to “singit” in the line (out of words, apologies). I gave my clearance form to the Teller and that’s where the “Long Wait” started.

Frankly, I have no idea why am I being blocked by the Treasury Department. First, I am a 100% academic scholar. Second, I have a Php 7,500 grant from CHED every semester. Adding those two scholarships, it always exceeds my matriculation fees. So, where’s the accountability?

So for two long hours, there I am, standing on the front of the Treasury Department, waiting to be cleared. Three people already had “teamed up” to tackle my case. Making the long story short, after two hours, they told me I’m cleared and then I proceed to my next problem.

Blocked

Last September, I resigned as the President of JPIA. Unfortunately, they revoked my resignation. So, I have to pass all the necessary documents, paperworks, details of expenses and financial statements to be able to enroll. After a series of signatures, letters, balancing figures, blah blah blah, we (the officers) were cleared. I would like to thank Sir Ron Sarno and Ms. Mary Santiaguel for extending us help.

And then I became eligible to enroll. So I enrolled. And here is my schedule (just to show you :p)

And that was it. Anyways, I have some resolutions for the upcoming semester, but that is worth another post. 

Writer's Sentiments

courtesy of degreedirectory.org

Honestly, I do not know what I am going to write about. I have no concrete idea to concentrate on what this post is all about. This is my third post in this site, yet I still feel like I’m writing my first one.

This should have been my first post, I guess.

Third post. This is the farthest I have reached so far in the blogosphere. I have been a writer since my elementary days. I join essay-writing contests, journalistic competitions, etc. I won a few (I was champion Photojournalist on Private Schools Competition in Cavite Region), yet every time I hold a pen and stare on a blank canvass, I always run out of words. I feel so stupid every time the deadline comes and I still have nothing to pass.

It makes me wonder, “Am I really destined to be a writer, or am I just pretending to be one.”

I know my mind creates lots of brilliant ideas, but the timing for those ideas to pop-up isn’t just right. Ideas would arise in unexpected places or situations, e.g. bathroom, jeepney and bus rides, etc. The bad thing is, when I reach for a paper and pen, those ideas instantly vanish.

Another thing that makes me doubt my self is that most of the time I look out for inspiration from other writer’s work. No originality, as you can say it. I copy the format, relate it to my personal experiences, and then write.

If someone would ask me why I didn’t started blogging before, I would answer, “I did. A couple of times already. But I stopped after a single post.” Why? Because I feel that I wouldn’t make sense at all, or because I don’t have the right to talk or write something; that people will make fun of me; that no one will read nor care even to glance at my work. That I still don’t have a place in this world.

Third post. The farthest I have reached. I hope it will not be the end of my blogging career.

I have entered this world once again. I have mustered all my courage to write something, hoping that it could somehow touch lives and inspire others to write.

Third post. Hope there will be a fourth.

Jejemon and Bekimon: Hardcore Lingo

Although I had a little disappointment with my fellow Filipinos, they still continue to amaze me. Truly, creativity is an inborn talent to each of us.

The main topic for this blog is about two “lingos” that have emerged recently in the society. Yes, I am referring to Jejemon and Bekimon. These lingos, created primarily for self-identity, are now an internet sensation all over the country.

For the sake of those who do not know what they are, here are the definitions, as they have defined themselves:

Jejemon – n. Basically anyone with a low tolerance in correct punctuation, syntax and grammar. Jejemons are usually hated or hunted down by Jejebusters or the grammar nazi to eradicate their grammatical ways. (jejemon.com)

Jejebeth – n. The alphabet of Jejemons (jejemon.com)

Bekimon (Baklang Jejemon) – n. isang BAKLA, LALAKING BAKLA o BABAENG BAKLA na HARDCORE gumamit ng GAY LINGO sa usapan at kahit sarili n’ya ay hindi rin n’ya maintindihan minsan. (a gay, male gay, or female gay that is hardcore in using gay lingo in conversation, though sometimes they do not even comprehend what they are saying).

Alphabeks – n. the alphabet of Bekimon. (pinoylgbt.com)

Bekimon Video



Jejemon Video


Personally, I am not a fan of such. Although I try to keep up with the latest trends, lingos like this are a big NO for me.

1.) I do not wish to complicate my text messages with numerals and symbols

2.) I am not gay, so what’s the sense of using Bekimon?

3.) It deteriorates my grammar. Once you started texting like Jejemon, a habit will form in you. Gradually, you will apply Jejemon even to your studies.

I am not a Jejebuster nor an anti-Bekimon. I do not express hate and grudge to Jejemons or Bekimons. My point here is that we should know to use this lingos in proper places and in proper time. It’s like “Separation of Jejemon/Bekimon language and Scholastic Language (I’m out of proper terms)” scenario. For Jejemon/Bekimon language is detrimental to academic health.

I still believe in my fellow Filipinos. We are born talented. Our creativity and intellect has brought us to fame and recognition. Let us not waste all of our talents in something that cannot contribute to our society. Creating self-identity is not bad, as long as it has its limits. 

AY 2010-2011 First Semester: An Unforgettable Term

This is a repost from my other blog. I'll be trying to write different topics on each blog so as to ensure variety.