0
votes
0answers
31 views

Exam Review Homework: Geometry and Algebra of Linear Programs

I have two connected problems: 7.6 Given the solutions $P = \{(1,1),(2,5),(3,3),(4,6),(5,2),(6,3)\}$ what linear inequalities describe the convex hull of $P$? What are its extreme points? My ...
2
votes
2answers
45 views

How can I calculate if a given point is wrapped inside a pentagon?

If I have a pentagon and I know the coordinates of it's nodes, how do I calculate if a point is wrapped inside it? An example to clarify what I mean: Assume that we know the coordinates of the ...
0
votes
0answers
48 views

Basic feasible solutions of a linear program in equational form

I'm trying to understand the simplex algorithm. For a polytope $P \subseteq \mathbb{R}^n$ of full dimension given by a set of inequalities $Ax \leq b$, there are several equivalent ways to define a ...
1
vote
2answers
73 views

How to determine this?

For any 6 coplanar points $\left(x_{1}+y_{1},x_{2}+y_{2},x_{3}+y_{3}\right)$, $\left(x_{1}+y_{2},x_{2}+y_{1},x_{3}+y_{3}\right)$,$\left(x_{1}+y_{3},x_{2}+y_{2},x_{3}+y_{1}\right)$, ...
2
votes
1answer
85 views

Optimizing Rectilinear Distance Traveled

I have a simple pipe network like this (not to scale): I can place a "valve" on any point on that pipe. What the valve does is it permits a certain viscous fluid to fill the pipes. However, because ...
0
votes
1answer
57 views

Describing a set using linear inequalities

I am having a hard time understanding the answer to the following exercise (which was taken from "Linear Optimization and Extensions: Problems and Solutions" by Padberg and Alevras). My problem ...
0
votes
1answer
30 views

Find a point in a polytope that always cuts off a constant fraction of the polytope.

I have $k$ linear inequalities in $\mathbb{R}^n$, which we can express as $Ax \ge c$ (where $A \in \mathbb{R}^{k \times n}$ and $c \in \mathbb{R}^k$). Assume that the set of $x \in \mathbb{R}^n$ that ...
0
votes
1answer
26 views

Compute the point of contraction of a bounded region in $\mathbb{R}^n$

Say we have a list of linear inequalities that define a bounded region in $\mathbb{R}^n$. These inequalities are: $a_1 \cdot x \ge c_1, \dots, a_k \cdot x \ge c_k$. Assume general position (i.e. it ...
1
vote
0answers
24 views

Background of choosing standard for of a linear program as type III inequalities?

In linear programming where we seek to minimize $c^Tx \to \text{min}_{x\in P}!$ with respect to some inequality constraints, why do we choose $P$ in the form $Ax \leq b$, $x \geq 0$ as the ...
0
votes
0answers
61 views

Using a corner-polyhedra-characterization to proof a connection of edges <-> base solutions

For polyhedra $P = \{x \in \mathbb{R}^n \mid Ax \leq b \}$, which I want to call type-I-polyhedra (as the inequality constraint in its definition is a type I-inequality), we have a ...
2
votes
0answers
110 views

Why is every nontrivial surface of a polyhedron an intersection of facets?

In the geometry of (convex) polyhedra used for linear optimization, one has the lemma: Consider the inequality $Ax \leq b$ where $A^+ x \leq b^+$ (the non-implicit inequalities of $Ax \leq b$) ...
3
votes
1answer
75 views

The Hirsch conjecture in $3$-dimensions

What I am wondering is if the Hirsch conjecture has a simple proof (just a few lines) in $3$ dimensions, perhaps by using Steinitz's theorem or Kuratowski's theorem and some kind of induction ...
2
votes
2answers
256 views

How to calculate volume given by inequalities?

I need to find the volume of the 3d space that is given by the following conditions: \begin{array}{c} 0 < x_1 < 1\\ 0 < x_2 < 1\\ 0 < x_3 < 1\\ x_1 + x_2 + x_3 < a. ...