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


by Arian.D
Tags: directions, extreme, linear, points, programming
Arian.D
Arian.D is offline
#1
Nov25-12, 05:27 PM
P: 101
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.
Phys.Org News Partner Mathematics news on Phys.org
Researchers help Boston Marathon organizers plan for 2014 race
'Math detective' analyzes odds for suspicious lottery wins
Pseudo-mathematics and financial charlatanism
Arian.D
Arian.D is offline
#2
Nov26-12, 07:20 AM
P: 101
C'mon.. it's really an easy question. No one here has ever passed a course in linear programming? really???
Mark44
Mark44 is online now
#3
Nov26-12, 09:39 AM
Mentor
P: 21,004
Quote Quote by Arian.D View Post
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.
Quote Quote by Arian.D View Post
:( 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.
Quote Quote by Arian.D View Post
Any helps would be appreciated.


Register to reply

Related Discussions
Linear Algebra (Linear Programming) Feasible solutions and extreme points. Calculus & Beyond Homework 1
differentiability and extreme points question Calculus & Beyond Homework 16
CalcIII extreme values and saddle points Calculus & Beyond Homework 2
Extreme points Calculus & Beyond Homework 0
extreme points on parabola Calculus & Beyond Homework 5