A linear programming, polyhedron and extreme points

  • A
  • Thread starter Thread starter mertcan
  • Start date Start date
mertcan
Messages
343
Reaction score
6
Hi,

First assume that there is a polyhedron P, where Ax<=b and x is free variable whose dimension is n. Besides, rank(A) = n. I really wonder if extreme points in a polyhedron can be linearly dependent? I used even ChatGPT, but it includes some shaky calculations while proofing. In short, if extreme points in a polyhedron can be linearly dependent or not, could you provide me with a proof?

Thanks
 
Physics news on Phys.org
mertcan said:
Hi,

First assume that there is a polyhedron P, where Ax<=b and x is free variable whose dimension is n. Besides, rank(A) = n. I really wonder if extreme points in a polyhedron can be linearly dependent? I used even ChatGPT, but it includes some shaky calculations while proofing. In short, if extreme points in a polyhedron can be linearly dependent or not, could you provide me with a proof?

Thanks
As an example you can consider a triangle in the plane R^2 with vertices
A=(0,1)
B=(1,0)
C=(1,1)

x<=1
y<=1
x+y>=1 ( -x-y<=-1 )
 
Last edited:
very thanks for your reply. Well, may I ask if ANY TWO extreme points in a polyhedron can be linearly dependent or not (those 2 extreme points are multiple of each other or not), could you provide me with a proof?

Thanks
 
It's trivial that you can get two points to be linearly dependent. For example the square with vertices (0,0), (0,1), (1,0) and (1,1). (0,0) Is linearly dependent with every other vertex.
 
Thread 'Determine whether ##125## is a unit in ##\mathbb{Z_471}##'
This is the question, I understand the concept, in ##\mathbb{Z_n}## an element is a is a unit if and only if gcd( a,n) =1. My understanding of backwards substitution, ... i have using Euclidean algorithm, ##471 = 3⋅121 + 108## ##121 = 1⋅108 + 13## ##108 =8⋅13+4## ##13=3⋅4+1## ##4=4⋅1+0## using back-substitution, ##1=13-3⋅4## ##=(121-1⋅108)-3(108-8⋅13)## ... ##= 121-(471-3⋅121)-3⋅471+9⋅121+24⋅121-24(471-3⋅121## ##=121-471+3⋅121-3⋅471+9⋅121+24⋅121-24⋅471+72⋅121##...
Back
Top