Linear programming: How to find extreme points and extreme directions?

In summary: It's always a good idea to ask for help when you're stuck. Don't be afraid to reach out to others who may have more experience or knowledge on the subject. Linear programming can be a challenging topic, but with practice and guidance, you can master it. Good luck!In summary, the conversation discusses the topic of linear programming and network flows, specifically the concepts of convex sets, extreme points, extreme directions, and slack variables. The speaker has trouble understanding how to find extreme points and directions, as well as the definition of a slack variable. They express frustration with the lack of examples in the book and seek help from others. The expert encourages the speaker to seek help and offers an explanation of slack variables.
  • #1
Arian.D
101
0
Hi guys

I'm reading a book about linear programming and network flows. In chapter 2 when it talks about convex sets and their analysis it talks about extreme points and extreme directions of a convex set. I understand the definitions of extreme points and extreme directions, but I don't know how I should find them. Unfortunately the book doesn't show how to find them with examples. :( I also don't know what a 'slack variable' is. I guess it must've been defined somewhere but I missed it :/

Any helps would be appreciated.
 
Last edited:
Mathematics news on Phys.org
  • #2
C'mon.. it's really an easy question. No one here has ever passed a course in linear programming? really?
 
  • #3
Arian.D said:
Hi guys

I'm reading a book about linear programming and network flows. In chapter 2 when it talks about convex sets and their analysis it talks about extreme points and extreme directions of a convex set. I understand the definitions of extreme points and extreme directions, but I don't know how I should find them. Unfortunately the book doesn't show how to find them with examples.
It might be that the author is merely setting the stage by defining some terms before looking at some examples.
Arian.D said:
:( I also don't know what a 'slack variable' is. I guess it must've been defined somewhere but I missed it :/
Slack variables are used to turn constraint inequalities into equations. For example, if you have a constraint inequality 2x + 3y ≤ 10, you can rewrite this as 2x + 3y + a = 10, where a is a slack variable such that a ≥ 0.

Generally you'll have one slack variable for each constraint inequality.

If you keep reading, you'll probably run into some examples.
Arian.D said:
Any helps would be appreciated.
 

1. What is linear programming?

Linear programming is a mathematical optimization technique used to find the best solution to a problem with linear constraints. It involves finding the maximum or minimum value of a linear objective function, subject to a set of linear constraints.

2. How do you find extreme points in linear programming?

Extreme points, also known as corner points, are the vertices of the feasible region in linear programming. They can be found by graphing the constraints and locating the points where the boundaries intersect. Alternatively, they can be found by solving a system of linear equations using methods such as substitution or elimination.

3. What are extreme directions in linear programming?

Extreme directions, also known as extreme rays, are the edges of the feasible region in linear programming. They represent the direction in which the objective function can be increased or decreased without violating any constraints. These directions can be found by evaluating the gradients of the objective function at the extreme points.

4. How do you use linear programming to solve real-world problems?

Linear programming has a wide range of applications in various fields, such as business, economics, engineering, and science. It can be used to optimize production processes, allocate resources, plan investments, schedule activities, and more. By formulating a problem as a linear programming model, we can use algorithms to find the most efficient solution.

5. What are some limitations of linear programming?

While linear programming is a powerful tool for solving optimization problems, it has some limitations. One limitation is that it can only handle linear constraints and objective functions, which may not accurately represent real-world problems. Additionally, it assumes that all parameters are known and constant, which may not always be the case. Lastly, it may not always provide a unique or feasible solution, and it can be computationally intensive for large-scale problems.

Similar threads

Linear programming and resolution theorem
    • Calculus and Beyond Homework Help
Replies
18
Views
2K
I Area divided by linear function
    • General Math
Replies
8
Views
1K
I The Price of Beer - Linear Algebra Problem
    • General Math
2
Replies
44
Views
3K
I Five points in space with rational distances that are not co-linear
    • General Math
Replies
13
Views
1K
I Line count in a simple program
    • General Math
Replies
16
Views
2K
I Open source software for integer programming
    • General Math
Replies
3
Views
996
MHB Fixed point,, Jacobi- & Newton Method, Linear Systems
    • General Math
Replies
7
Views
1K
B Reprise: Calculate the distance between two points without using a coordinate system
    • General Math
Replies
1
Views
215
I Expressing any given point on plane with one unique number
    • General Math
Replies
4
Views
610
MHB Formula to find arc radius using arc length, chord length, and/or segment angle
    • General Math
Replies
4
Views
4K

Hot Threads

Recent Insights

Back
Top