Now Playing Tracks

lessons in MATHEMATICS2 under Dr. Esther Moguer

Linear programming (LP, or linear optimization) is a mathematical method for determining a way to achieve the best outcome (such as maximum profit or lowest cost) in a given mathematical model for some list of requirements represented as linear relationships. Linear programming is a specific case of mathematical programming (mathematical optimization).

More formally, linear programming is a technique for the optimization of a linear objective function, subject to linear equality and linear inequality constraints. Its feasible region is a convex polyhedron, which is a set defined as the intersection of finitely many half spaces, each of which is defined by a linear inequality. Its objective function is a real-valued affine function defined on this polyhedron. A linear programming algorithm finds a point in the polyhedron where this function has the smallest (or largest) value if such point exists.

Linear programs are problems that can be expressed in canonical form:

 \begin{align} & \text{maximize}   && \mathbf{c}^\mathrm{T} \mathbf{x}\\ & \text{subject to} && A \mathbf{x} \leq \mathbf{b} \\ & \text{and} && \mathbf{x} \ge \mathbf{0} \end{align}

where x represents the vector of variables (to be determined), c and b are vectors of (known) coefficients and A is a (known) matrix of coefficients. The expression to be maximized or minimized is called the objective function (cTx in this case). The equations Ax ≤ b are the constraints which specify a convex polytope over which the objective function is to be optimized. (In this context, two vectors are comparable when every entry in one is less-than or equal-to the corresponding entry in the other. Otherwise, they are incomparable.)

Linear programming can be applied to various fields of study. It is used most extensively in business and economics, but can also be utilized for some engineering problems. Industries that use linear programming models include transportation, energy, telecommunications, and manufacturing. It has proved useful in modeling diverse types of problems in planning, routing, scheduling, assignment, and design.

History

 

http://bits.wikimedia.org/skins-1.18/common/images/magnify-clip.png

Leonid Kantorovich

The problem of solving a system of linear inequalities dates back at least as far as Fourier, after whom the method of Fourier-Motzkin elimination is named. The earliest linear programming was first developed by Leonid Kantorovich in 1939.[1] It was used during World War II to plan expenditures and returns in order to reduce costs to the army and increase losses to the enemy. The three founding figures in the subject are considered to be Leonid Kantorovich, who developed the earliest linear programming problems in 1939, George Dantzig, who published the simplex method in 1947, and John von Neumann, who developed the theory of the duality in the same year. The method was kept secret until 1947 when George B. Dantzig published the simplex method and John von Neumann developed the theory of duality as a linear optimization solution, and applied it in the field of game theory. Postwar, many industries found its use in their daily planning.

The linear-programming problem was first shown to be solvable in polynomial time by Leonid Khachiyan in 1979, but a larger theoretical and practical breakthrough in the field came in 1984 when Narendra Karmarkar introduced a new interior-point method for solving linear-programming problems.

Dantzig’s original example of finding the best assignment of 70 people to 70 jobs exemplifies the usefulness of linear programming. The computing power required to test all the permutations to select the best assignment is vast; the number of possible configurations exceeds the number of particles in the universe. However, it takes only a moment to find the optimum solution by posing the problem as a linear program and applying the Simplex algorithm. The theory behind linear programming drastically reduces the number of possible optimal solutions that must be checked.

[edit]Uses

Linear programming is a considerable field of optimization for several reasons. Many practical problems in operations research can be expressed as linear programming problems. Certain special cases of linear programming, such as network flow problems and multicommodity flow problems are considered important enough to have generated much research on specialized algorithms for their solution. A number of algorithms for other types of optimization problems work by solving LP problems as sub-problems. Historically, ideas from linear programming have inspired many of the central concepts of optimization theory, such as duality, decomposition, and the importance of convexity and its generalizations. Likewise, linear programming is heavily used in microeconomics and company management, such as planning, production, transportation, technology and other issues. Although the modern management issues are ever-changing, most companies would like to maximize profits or minimize costs with limited resources. Therefore, many issues can be characterized as linear programming problems.

[edit]Standard form

Standard form is the usual and most intuitive form of describing a linear programming problem. It consists of the following four parts:

§  A linear function to be maximized

e.g. \max_{x_{1},x_{2}} f(x_{1},x_{2}) = c_1 x_1 + c_2 x_2

§  Problem constraints of the following form

e.g.

\begin{matrix}   a_{11} x_1 + a_{12} x_2 &\leq b_1 \\    a_{21} x_1 + a_{22} x_2 &\leq b_2 \\   a_{31} x_1 + a_{32} x_2 &\leq b_3 \\ \end{matrix}

§  Non-negative variables

e.g.

\begin{matrix}  x_1 \geq 0 \\  x_2 \geq 0 \end{matrix}

§  Non-negative right hand side constants

b_i \geq 0,\; i=1,2,3

The problem is usually expressed in matrix form, and then becomes:

\max \{ c^\mathrm{T} x \;|\; 0 \leq A x \leq b \and x \geq 0 \}

Other forms, such as minimization problems, problems with constraints on alternative forms, as well as problems involving negative variables can always be rewritten into an equivalent problem in standard form.

[edit]Example

Suppose that a farmer has a piece of farm land, say L km2, to be planted with either wheat or barley or some combination of the two. The farmer has a limited amount of fertilizer, F kilograms, and insecticide, P kilograms. Every square kilometer of wheat requires F1 kilograms of fertilizer, and P1 kilograms of insecticide, while every square kilometer of barley requires F2 kilograms of fertilizer, andP2 kilograms of insecticide. Let S1 be the selling price of wheat per square kilometer, and S2 be the price of barley. If we denote the area of land planted with wheat and barley by x1 and x2 respectively, then profit can be maximized by choosing optimal values for x1 and x2. This problem can be expressed with the following linear programming problem in the standard form:

Maximize: S1x1 + S2x2

(maximize the revenue—revenue is the “objective function”)

Subject to:

0 ≤ x1 + x2 ≤ L

(limit on total area)

0 ≤ F1x1 + F2x2 ≤ F

(limit on fertilizer)

0 ≤ P1x1 + P2x2 ≤ P

(limit on insecticide)

x1 ≥ 0, x2 ≥ 0

(cannot plant a negative area).

Which in matrix form becomes:

maximize \begin{bmatrix} S_1 & S_2 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}

subject to \begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix} \le \begin{bmatrix} 1 & 1 \\ F_1 & F_2 \\ P_1 & P_2 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \le \begin{bmatrix} L \\ F \\ P \end{bmatrix}, \, \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \ge \begin{bmatrix} 0 \\ 0 \end{bmatrix}.

[edit]Augmented form (slack form)

Linear programming problems must be converted into augmented form before being solved by the simplex algorithm. This form introduces non-negative slack variables to replace inequalities with equalities in the constraints. The problem can then be written in the following block matrix form:

Maximize Z:

  \begin{bmatrix}     1 & -\mathbf{c}^T & 0 \\     0 & \mathbf{A} & \mathbf{I}   \end{bmatrix}   \begin{bmatrix}     Z \\ \mathbf{x} \\ \mathbf{x}_s   \end{bmatrix} =   \begin{bmatrix}     0 \\ \mathbf{b}   \end{bmatrix}

xxs ≥ 0

where xs are the newly introduced slack variables, and Z is the variable to be maximized.

[edit]Example

The example above is converted into the following augmented form:

Maximize: S1x1 + S2x2

(objective function)

Subject to:

x1 + x2 + x3 = L

(augmented constraint)

F1x1 + F2x2 + x4 = F

(augmented constraint)

P1x1 + P2x2 + x5 = P

(augmented constraint)

x1x2x3x4x5 ≥ 0.

where x3, x4, x5 are (non-negative) slack variables, representing in this example the unused area, the amount of unused fertilizer, and the amount of unused insecticide.

In matrix form this becomes:

Maximize Z:

  \begin{bmatrix}     1 & -S_1 & -S_2 & 0 & 0 & 0 \\     0 &   1    &   1    & 1 & 0 & 0 \\     0 &  F_1  &  F_2  & 0 & 1 & 0 \\     0 &  P_1    & P_2 & 0 & 0 & 1 \\   \end{bmatrix}   \begin{bmatrix}     Z \\ x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5   \end{bmatrix} =   \begin{bmatrix}     0 \\ L \\ F \\ P   \end{bmatrix}, \,   \begin{bmatrix}     x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5   \end{bmatrix} \ge 0.

[edit]Duality

See also: Dual linear program

Every linear programming problem, referred to as a primal problem, can be converted into a dual problem, which provides an upper bound to the optimal value of the primal problem. In matrix form, Minimize bTy subject to ATy = c, y ≥ 0.

we can express the primal problem as:

Maximize cTx subject to Ax  b, x ≥ 0;

with the corresponding symmetric dual problem,

Minimize bTy subject to ATy  c, y ≥ 0.

An alternative primal formulation is:

Maximize cTx subject to Ax  b;

with the corresponding asymmetric dual problem,

"Ideal teachers are those who use themselves as bridges over which they invite their students to cross, then having facilitated their crossing, joyfully collapse, encouraging them to create bridges of their own." — Nikos Kazantzakis

"Learning is finding out what we already know. Doing is demonstrating that you know it. Teaching is reminding others that they know just as well as you. You are all learners, doers, and teachers." — Richard Bach

"A teacher who can arouse a feeling for one single good action, for one single good poem, accomplishes more than he who fills our memory with rows and rows of natural objects, classified with name and form." — Johann Wolfgang von Goethe

"Thought flows in terms of stories — stories about events, stories about people, and stories about intentions and achievements. The best teachers are the best storytellers. We learn in the form of stories." — Frank Smith

"Treat people as if they were what they ought to be and you help them become what they are capable of becoming." — Goethe
“Optimism is the faith that leads to achievement, nothing can be done without hope and confidence.” — Helen Keller

"Once children learn how to learn, nothing is going to narrow their mind. The essence of teaching is to make learning contagious, to have one idea spark another." — Marva Collins

"In education it isn’t how much you have committed to memory or even how much you know. It’s being able to differentiate between what you do know and what you don’t. It’s knowing where to go to find out what you need to know and it’s knowing how to use the information you get." —William Feather

"A teacher who is attempting to teach without inspiring the pupil with a desire to learn is hammering on cold iron." — Horace Mann

"They may forget what you said but they will never forget how you made them feel." - Carol Buchner
“I think a hero is an ordinary individual who finds strength to persevere and endure in spite of overwhelming obstacles.” — Christopher Reeve

"Watch your thoughts, they become words. Watch your words, they become your actions. Watch your actions, they become habits. Watch your habits, they become character. Watch your character, it becomes your destiny." — Frank Outlaw

"If a seed of a lettuce will not grow, we do not blame the lettuce. Instead, the fault lies with us for not having nourished the seed properly." - Buddhist proverb

"The great end of education is to discipline rather than to furnish the mind; to train it to the use of its own powers rather than to fill it with the accumulation of others." — Tyron Edwards

"Good teaching is more a giving of right questions than a giving of right answers." —Josef Albers
“Let us think of education as the means of developing our greatest abilities, because in each of us there is a private hope and dream which, fulfilled, can be translated into benefit for everyone and greater strength of the nation.” — John F. Kennedy

"Your role as a leader is even more important than you might imagine. You have the power to help people become winners." —Ken Blanchard

"If you want to live more, you must master the art of appreciating the little everyday blessings of life. This is not altogether a golden world but there are countless gleams of gold to be discovered in it." —Henry Alfred Porter

"Don’t limit yourself. Many people limit themselves to what they think they can do. You can go as far as your mind lets you. What you believe, you can achieve." — Mary Kay Ash

"One never notices what has been done; one can only see what remains to be done." — Marie Curie
“Every truth has four corners: as a teacher I give you one corner, and it is for you to find the other three.” —Confucius

"Life is no brief candle for me. It is a sort of splendid torch which I have got hold of for the moment and I want to make it burn as brightly as possible before handing it on to future generations." — George Bernard Shaw

"No matter how he may think himself accomplished, when he sets out to learn a new language, science or the bicycle, he has entered a new realm as truly as if he were a child newly born into the world." — Frances Willard

"We should not teach children the sciences but give them a taste for them." — Jean Jacques Rousseau

"Much education today is monumentally ineffective. All too often we are giving young people cut flowers when we should be teaching them to grow their own plants." — John Gardner
“The teacher who is indeed wise does not bid you to enter the house of wisdom but rather leads you to the threshold of your mind.” — Kahlil Gibran

"A very wise old teacher once said: "I consider a day’s teaching wasted if we do not all have one hearty laugh." He meant that when people laugh together, they cease to be young and old, master and pupils, jailer and prisoners. They become a single group of human beings enjoying its existence." — Gilbert Highet

"To ensure that your work is also a play, I recommend that you develop a personal mission statement. This will help you find what it is to enjoy so much that you lose track of time when you’re doing it." — Ken Blanchard

"Each man must look to himself to teach him the meaning of life. It is not something discovered. It is something molded." — Antoine De Saint-Exupery

"It is not what is poured into a student that counts but what is planted." -Linda Conway
“The greatest sign of a success for a teacher…is to be able to say, “The children are now working as if I did not exist.” — Maria Montessori

"There is in every child a painstaking teacher so skillful that he obtains identical results in all children in all parts of the world. The only language men ever speak perfectly is the one they learn in babyhood, when no one teaches them anything." —Maria Montessori

"We learn by example and by direct experience because there are real limits to the adequacy of verbal instruction." — Malcom Gladwell

"You must train the children to their studies in a playful manner and without any air of constraint with the further object of discerning more readily the natural bent of their respective characters." — Plato

"Worry a little bit every day and in a lifetime you will lose a couple of years. If something is wrong, fix it if you can. But train yourself not to worry. Worry never fixes anything." — Mary Hemingway
“As you begin changing your thinking, start immediately to change your behavior. Begin to act the part of the person you would like to become. Take action on your behavior. Too many people want to feel, then take action. This never works.” — John C. Maxwell

"Education is not the filling of a pail but the lighting of a fire." —William Butler Yeats

"If a child is to keep alive his inborn sense of wonder, he needs the companionship of at least one adult who can share it, rediscovering with him the joy, the excitement, and the mystery of the world we live in." —Rachel Carlson

"Good teaching is one-fourth preparation and three-fourths theatre." — Gail Goldwin

"No one but us ourselves-no one can and no one way. We ourselves must walk the path, teachers merely show the way." — Nancy Wilson Ross
“There are two kinds of people; those who do the work and those who take the credit. Try to be in the first group; there is less competition there.” — Indira Gandhi

"One looks back with appreciation to the brilliant teachers, but with gratitude to those who touched our human feelings. The curriculum is so much necessary material, but warmth is the vital element for the growing plant and for the soul of the child." — Carl Jung

"Every time you wake up and ask yourself, "What good things am I going to do today?," remember that when the sun goes down at sunset, it takes a part of your life with it." —Indian proverb
“Education would be much more effective if its purpose was to ensure that by the time they leave school every boy and girl should know how much they do not know and be imbued with a lifelong desire to know it.” — William Haley

"It is the supreme art of the teacher to awaken joy in creative expression and knowledge." — Albert Einstein
“Do not think that love, in order to be genuine, has to be extraordinary. What we need is to love without getting tired.” — Mother Theresa

"To be yourself in a world that is constantly trying to make you something else is the greatest accomplishment." — Ralph Waldo Emerson

"Tell me and I forget. Teach me and I remember. Involve me and I learn." — Benjamin Franklin

"I challenge you to make your life like a masterpiece. I challenge you to join the ranks of those people who live what they teach, who walk their talk." — Anthony Robbins

"A hundred years from now, it will not matter what kind of car I drove, what kind of house I lived in, how much money I had in the bank…but the world may be a better place because I made a difference in the life of a child." — Forest Witcraft

http://ripplemaker.hubpages.com/hub/50_Inspirational_Quotes_for_Teachers
We make Tumblr themes