Introduction To Basic Feasible Solutions In Engineering

You know what it means to optimize a system to get the best result possible if you are an engineering student or an engineer.

Optimizing a solution is the key to success in everything from building bridges to making software.

The idea of a basic feasible solution comes in at this point.

It is a basic idea in linear programming that lets you figure out which of a set of possible solutions is the best.

But why does it matter so much? In this article, I'll talk about basic feasible solutions and how they can be used to solve engineering problems in the real world.

I'll talk about how to find them, what they are made of, and why they are important.

So, whether you are an experienced engineer or a student just starting out, come with us as I dive into the world of basic feasible solutions and show you how to use the power of linear programming.

Understanding Basic Feasible Solution

Formal definition:

A basic solution to a linear program model in which all the variables are nonnegative.

A basic feasible solution (BFS) is a key idea in linear programming that helps find the best solutions.

A BFS is a solution with the smallest possible number of non-zero variables.

It is a corner of the polyhedron of feasible solutions.

In other words, a BFS is a basic solution that meets the non-negative constraints and is in the feasible region or problem area.

Finding an Optimal Basic Feasible Solution

To find the best BFS, we need to do the following:

  • Write the program in standard form for a linear sequence.
  • Turn the system of inequalities into an augmented matrix.
  • Figure out which variables are basic and which are not.
  • Figure out what the basic variables are in terms of the other variables.
  • Put these expressions into the objective function to get a function of only the variables that aren't basic.
  • Find a non-basic variable that can be increased without breaking any constraints and that will make the objective function better.

This variable is now a basic variable, and one of the other basic variables is no longer a basic variable.

If there is an optimal solution, it must be at one of the ends, or vertices, of the region where solutions are possible.

So, if an LP has an optimal solution, it has an optimal solution at an extreme point of the feasible set.

Also, there is always an optimal BFS if there is an optimal solution.

Using the Simplex Method to Find an Optimal BFS

The Simplex Method is an algorithm for solving problems in linear programming.

It moves from one BFS to a "adjacent" BFS by using the pivot procedure.

In the pivot procedure, a non-basic variable is chosen to become a basic variable, and then the current BFS is used to solve for the new basic variables.

When no non-basic variable can be changed to make the objective function better, the algorithm is done.

Why Basic Feasible Solutions Are Crucial for Solving Complex Engineering Problems

Still hard to understand? Let me change the point of view a bit:

Who needs simple, workable answers anyway? Just throw everything together and hope for the best.

After all, who needs optimization when chaos is so much more fun? Welcome to the world of nonnegative variables, where everything is just a suggestion and failure is almost certain.

Or is it?

Let's explore why the seemingly basic concept of basic feasible solutions is anything but basic and why they might just be the key to solving even the most complex engineering problems.

Okay, that was just a joke made to look like a TV ad.

Now let's go back to the explanation.

Finding Basic Feasible Solution

A basic feasible solution (BFS) is a solution to a linear optimization problem that meets all constraints and has the fewest number of non-zero variables.

Each BFS is a corner of the polyhedron of feasible solutions from a geometric point of view.

If there is a best solution, there must also be a best first step.

In this article, we'll talk about how to find an initial basic feasible solution, how to find all basic feasible solutions, and how to find a basic feasible solution with no slack variables.

Finding an Initial Basic Feasible Solution

We can use different methods, depending on how the problem is set up, to find an initial basic solution that works for a linear optimization problem.

One way is to add slack variables to the constraints on inequalities and set all the other variables to zero.

The slack variables become the basic variables, and the rest are non-basic variables.

The two-phase Simplex Method is another way to solve the problem.

This method involves solving an extra linear programming problem to find an initial basic solution that is feasible.

Once an initial basic feasible solution has been found, the Simplex Method can be used to move from one basic feasible solution to the next and then to the best solution.

Finding All Basic Feasible Solutions

There can be more than one basic solution that works for a linear program.

We can change the system by adding slack variables and then use the new system to find all basic feasible solutions for a linear program.

Then, these basic feasible solutions are used to find the basic feasible solutions for the original problem.

Finding a Basic Feasible Solution with No Slack Variables

We need to use slack variables to get rid of the less-than constraints so we can find a basic solution that works without slack variables.

A slack variable is just the difference between the right side of a constraint and the left side.

For example, for the first constraint, we define a slack variable x4 = 14 - 2x1 - x2 - x3. In terms of this new variable, the first constraint is equivalent simply to x4 ≥ 0, which is a positivity constraint for x4.

When we add these slack variables, we get a linear program that is the same as the original one, except that all of the constraints are either equations or constraints that say something is positive.

The set of basic variables, which have values other than zero in the basic solution, is called the basis.

Variables that have a value of zero in the basic solution are not basic variables.

To find the best solution, we need to find a vector x that meets all the rules and gets the biggest or smallest value for the objective.

But finding the best solution takes more steps than just finding a solution that works and has no slack variables.

It's not always possible to find a basic solution with no slack variables, especially for problems with less-than constraints.

To find a basic feasible solution, you need to use the simplex method or another linear programming algorithm to look for a solution that meets all constraints and has the fewest non-zero variables.

Properties and Significance of Basic Feasible Solution

Properties of Basic Feasible Solution

A basic feasible solution has at most m variables that are not zero and at least n-m variables that are zero, where n is the number of decision variables and m is the number of constraints.

A BFS is a corner of the polyhedron of possible solutions, and each BFS has n active constraints that are linearly independent.

If there is a best solution, there must also be a best first step.

The most important thing about basic feasible solutions is that they are the ends of the set of convex solutions for a linear programming problem.

To find the best answer, the simplex algorithm goes through a series of BFSs.

The Simplex Algorithm searches through all of the basic possible solutions in an organized way to find the best one.

Significance of Basic Feasible Solution

Finding a basic solution that is possible is important because it helps find the best answer to linear programming problems.

It also gives complex algorithms a place to start and can be used to figure out if a linear program is possible or not.

To find all basic feasible solutions for a linear program, you can change the system by adding slack variables and then use the changed system to find all basic feasible solutions.

Then, these basic feasible solutions are used to find the basic feasible solutions for the original problem.

Video: Basic Feasible Solutions

Tip: Turn on the caption button if you need it. Choose “automatic translation” in the settings button, if you are not familiar with the spoken language. You may need to click on the language of the video first before your favorite language becomes available for translation.

Use cases

Used in:Description:
Allocation of Resources:BFS can be used to divide limited resources among several projects so that the most can be done with the least. This method can be used in many different fields, like transportation, farming, and finance.
Optimization of the Network:BFS can be used to make communication, transportation, and logistics networks work better. BFS can help find the best routes for goods and services, cut down on time and money spent on transportation, and speed up and make more accurate deliveries.
Planning for Production:BFS can be used to plan production so that resources like labor, raw materials, and equipment are used in the best way possible to get the most out of them. BFS can help lower production costs, cut down on waste, and improve efficiency.
Financial Planning:In financial planning, BFS can be used to optimize investment portfolios, lower risk, and get the most money back. BFS can help find the best way to divide up assets, lower transaction costs, and make more money.
Management of the Supply Chain:BFS can be used to improve the flow of goods and services from suppliers to customers as part of supply chain management. BFS can help figure out the best amount of stock to keep on hand, shorten lead times, and improve customer service.

Conclusion

As this look at basic feasible solutions comes to a close, it's clear that they're an important tool for any engineer or engineering student.

From figuring out the best way to build a complicated system to making the most of the resources available, basic feasible solutions provide a framework for getting the best possible result.

But more than just being useful, they show how elegant and beautiful math can be.

It is amazing that you can boil down complicated problems to a simple set of equations and then use those equations to solve problems in the real world.

It's a good reminder that engineering is all about solving problems, and that by using the power of math, we can find answers that were once thought to be impossible.

So, as you learn more about engineering, keep in mind what you've learned about simple solutions that work and use them to make the world a better, more efficient place.

Links and references

Books:

  • Linear Programming: Foundations and Extensions
  • Linear Programming: Theory and Applications

Share on…