Questions on linear programming, the optimization of a linear function subject to linear constraints.

learn more… | top users | synonyms

1
vote
0answers
100 views

Show that every extreme point in Q is either an extreme point of P or a convex combination of two adjacent extreme points of P

P is a bounded polyhedron in $\mathbb{R}^n$, $a$ a vector in $\mathbb{R}^n$, and $b$ some scalar. Define $$Q = {x \in P | a'x = b}$$. Show that every extreme point in Q is either an extreme point of P ...
0
votes
1answer
34 views

Find Maximum of Lower Envelope

Okay, I'm not really sure whether the title is good. Consider \begin{align*} \min\{ 5x_1 + \frac{5}{2}x_2 + \frac{5}{3}x_3 + \frac{5}{4}x_4, \\ x_1 + \frac{6}{2}x_2 + \frac{6}{3}x_3 + ...
1
vote
1answer
19 views

simplex M-method minimization problem

Solve using the simplex method. Identify the solution of the dual in the final simplex tableau Minimize: $$z=12x_{1}+4x_{2}+2x_{3}$$ **Constraints:**$$ x_{i}\ge 0$$ $$-6x_{1}+3x_{2}\ge 9$$ ...
0
votes
1answer
26 views

Feasible Condition with a single constraint

A linear program with a single constraint minimize $z = c_{1}x_{1} + c_{2}x_{2} +· · ·+c_{n}x_{n}$ subject to $a_{1}x_{1} + a_{2}x_{2} +· · ·+a_{n}x_{n} ≤ b$, $x_{1}, x_{2}, . . . , x_{n} ≥ 0.$ (a) ...
3
votes
0answers
33 views

Easy elementary proof of Farkas Lemma?

Is there any elementary proof of Farkas lemma which does not use convex analysis and hyperplane separation theorem? What about special case below: If the Matrix $A$ is invertible, then there is ...
0
votes
1answer
41 views

Set of optimal solutions for a linear programs

Consider the linear program: minimize $z = x_{1} - x_{2}$, $x_{1}, x_{2}\geq 0$ subject to: $-x_{1} + x_{2}\leq 1$ , $x_{1} - 2x_{2}\leq 2$ Derive an ...
0
votes
0answers
50 views

Linear Programming - Tableau Condition

The following tableau corresponds to an iteration of the simplex method: ...
0
votes
0answers
20 views

How to justify that a basic feasible solution to a Linear Program corresponds to an extreme point of the feasible region?

Say we have an LP Problem in standard form. That is, $$\text{Maximise} \;\; C^T X $$ $$ \text{subject to:} \;\;\; AX = B --(1) \;\;\;\; \text{where $A$ is an $m \times n$ matrix }$$ I read ...
0
votes
0answers
25 views

Linear Programming sufficient and necessary conditions

Find necessary and sufficient conditions for the numbers s and t to make the LP problem: ...
0
votes
0answers
14 views

Eliminating variables in convex program

This is a basic convex optimisation question. I have the following problem: $$\max_{\substack{t\le e\\ At\le b}} e^\top t$$ How do I find the optimum $t^*$? I write the KKT conditions, get ...
0
votes
0answers
10 views

Let V be the space of polynomials in t of degree

Let V be the space of polynomials in t of degree ≤ n.Show that the {1,t,t2,...tn-1is a basis of V.
0
votes
1answer
23 views

how to use linear programming for Heaviside Step function and L1 norm?

I want to find a hyperplane that can divide my sets of points into 2 groups that have nearly equal size. If the hyperplane is $w$, there is a scalar offset $b$. I have $N$ points that are ...
0
votes
0answers
15 views

Case of affine hull and linear hull possibly being euqal

Let C be a set in $\mathbb{R}^n$. Let $aff(X)$ denote the affine hull of $X$, and $lin(X)$ denote the linear hull of $X$. Suppose $x \in aff(C)$. Then, is it true that $aff(C-x)=lin(C-x)$? The ...
2
votes
1answer
92 views

Linear programming: Basic solution

Let $P = \{ x \in R^n : Ax \leq b, x\geq 0\}$ and $Q= \{ (x, r)' \in R^{n+m}: Ax + r= b, x \geq 0, r\geq 0\}.$ Show that $$x \text{ is basic solution of } P \iff (x, b-Ax) \text{ is basic solution of ...
1
vote
1answer
32 views

Do lagrangian multipliers converge to dual variables in LPs?

Can anybody clarify the following to me? Consider an LP, say a maximization problem, with solution x* and optimal value Z*. Its dual will have optimal value W*=Z* (by strong duality) and optimal ...
0
votes
0answers
28 views

What is the proof/show that the post of linear transformation generated by LDA is at most k-1

What is the proof/show that the matrix $Sw$ generated by LDA is at most rank $p-k$, where $p$ is the dimension of the data and $k$ is the number of classes. LDA: ...
0
votes
0answers
28 views

Let $P$ be a polyhedron. Prove, $P$ has at least one extreme point $\iff$ $P$ does not contain a line, by using a lemma.

Let $P$ be a polyhedron. Prove, $P$ has at least one extreme point $\iff$ $P$ does not contain a line, by using a lemma. I've a Lemma saying: Suppose $P=P(V,E)$ where $V,E \in \mathbb R^n$ are ...
0
votes
0answers
9 views

constraint formulation in linear programming

I have a integer variable with a constraint such that is unequal to specific. For example, x ≠ 4*k where k is an integer, which means x can be any value except 0, 4, 8, ... I have no idea to ...
1
vote
1answer
57 views

What constraints are needed to to switch on a binary variable in a linear programming model?

I am trying to create a binary variable ($z$) within a linear model which 'switches' on only when another variable ($d$) becomes greater than zero. I have had some success using the following two ...
1
vote
0answers
14 views

Find relationships between events

I have a set of Events $(E_i)_i$ which have a probability $(P_i)_i$. I am able to write each event as a sum of distinct events that form a partition of the space. My goal is to find all the ...
0
votes
1answer
54 views

Solving LP with two $L_1$ inequality constraints

Is there a "fast" way to solve the following LP formulation with the following constraints: $$ \max_{\mathbf{f}} \mathbf{f}'.\mathbf{g} \\ \mathbf{1}'\mathbf{f}=1\\ \|\mathbf{f}-\mathbf{h}\|_1\le ...
0
votes
0answers
21 views

Squaring Orthogonal Matrix Entrywise is Doubly Stochastic

I'm stuck on this question: Suppose Q is an orthogonal matrix. Show that $Q \circ Q$ is doubly stochastic, i.e. entries are nonnegative, every row sums up to 1, and every column sums up to 1. (the ...
0
votes
0answers
16 views

Let $P \subseteq R^n$ be a polyhedron. Why does $\{ x + \alpha d \mid \alpha > 0\} \subseteq P$ for some $x \in P$ imply $d$ is a recession direction?

Suppose we have a polyhedron $P \subseteq R^n$ and let $d \in P$ be a recession direction, that is $\{ x + \alpha d \mid \alpha > 0\} \subseteq P$ for all $x \in P$. Why does $\{ x + \alpha d \mid ...
0
votes
1answer
33 views

Need help formulating a Traveling Salesman (Deliveryman) Variation

I am working with the following TSP variation: A deliveryman has to deliver orders of items to several different locations around a city. The orders are: ...
0
votes
1answer
25 views

Write the convex hull of the points $(0,0), (1,1), (2,0) \in \mathbb R^2$ as the set of solutions to a finite number of inequalities.

Write the convex hull of the points $(0,0), (1,1), (2,0) \in \mathbb R^2$ as the set of solutions to a finite number of inequalities. The convex hull of $x_1, \ldots, x_n \in \mathbb R^n$ is defined ...
0
votes
0answers
11 views

How to prove that the solution in every next iteration of Simplex algorithm is a BFS

Let Ax = b x >= 0 be the feasible region. Let A be mxn matrix with m <= n and rank(A) = m. Simplex algorithm starts with a Basic Feasible solution. In each step it moves to a new solution. How do ...
0
votes
0answers
6 views

Linear programming with an independent variable

I have a bunch of linear programming problems to solve of the following form: Maximize $f(a, b, c)$ Subject to: $g_1(a, b, c | x) \ge 0$ $g_2(a, b, c | x) \ge 0$ $\dots$ Where the $g_i$ are all ...
0
votes
0answers
16 views

Devising objective function for integer linear programming

I am working to devise a objective function for a integer linear programming model. The goal is to determine the copy number of two genes as well as if a gene conversion event has happened (where one ...
0
votes
1answer
27 views

Finding Optimal Value with Linear Programming Subroutine

I am stuck on this question: Consider the problem: $\underset{x}{\text{minimize}}{\frac{c^{T}x+d}{f^{T}x+g}}$ $\text{s.t. } Ax\leq b$ $f^{T}x+g>0$ Suppose we have prior knowledge that the ...
1
vote
0answers
16 views

Executing Branch and Bound using a Simplex tableau

I'm studying the branch and bound method and how it is used in conjunction with a simplex tableau. The issue I'm struggling with is how you incorporate the branches in your tableau to find out ...
0
votes
0answers
21 views

sensitivity analysis - help!

Hi guys I am doing a quesetion on simplex method and am stuck on the second part of the sensitbity analysis question: I am stuck on the part that is asking for 12 + n. I know that I am changing ...
0
votes
0answers
45 views

Casio fx-83gt - help! Linear Programming

Hi guys I'm studying a module called Operational Research and in particular linear programming. I am doing the simplex method and as anyone who studies linear programming would know, you need to ...
0
votes
1answer
32 views

what is the dual of the following linear program over a convex set?

Let $\mathbf{x}=[x_0,x_1,\dots,x_N]^T$ be a $(N+1)\times 1$vector. Let $\mathcal{S}$ be a bounded, compact convex set in strictly positive quadrant of $\mathbb{R}^{N+1}$. Consider the following ...
1
vote
0answers
54 views

Linear programming - Textbook recommendations

Next term, I will attend a course on linear programming. Due to the assignments, we will have to write many thorough proofs. I anticipate that we will be supposed to cope with in-depth background ...
0
votes
0answers
25 views

Closed-form solution of the following LP problem

I am considering the following LP problem: $$ \begin{array}{cl} \text{maximize} & c^Tx\\ \text{subject to} & a^Tx\geq0 \\ & 0\leq x\leq x^\max \end{array} $$ where ...
0
votes
0answers
26 views

Linear Algebra - find basis without reduced echelon

For the start of a simplex solver I'm building in Python, I need to find a basic feasible solution. To do that, I need to find a basic solution/find the basis of the constraint matrix. Here's my ...
0
votes
0answers
37 views

k- maximally link disjoint paths and equations

This problem is NP-complete and also discussed to some extent in Graph problems which are NP-Complete on directed graphs but polynomial on undirected graphs from the level of my reading from various ...
0
votes
2answers
36 views

Maximum cardinality affinely independent subset of $\mathbb{R}^n$

Let $S \subset \mathbb{R}^n$ such that $S$ is affinely independent. Then $$|S| \le n + 1.$$ Why? (e.g. does anybody know some place where this is proven?)
0
votes
1answer
20 views

Linear programming, how to do the opposite transformation?

This is from a pdf file I found linked to from this site: They first define the primal dual problem like this: Then they have another representation of (p), and show that it's dual is: Now here ...
1
vote
1answer
36 views

Affine and Linear programming

Can someone give a simple explanation as to why the feasible region of a set of linear program/equations is affine?
0
votes
0answers
33 views

Finding the optimal solution to an ILP, when feasibility is not ultimately required

I have the following problem: I would like to solve an ILP with binary variables, i.e. I have a set of possible items, each having properties like "size" "weight" "value" "age" and so on, in total, ...
0
votes
0answers
20 views

Every polyhedron $P \ne \mathbb{K}^n$ equals an intersection of finitely many half spaces.

Currently, I am reading some lecture notes on linear optimisation. I cannot see why the following (seemingly trivial) proposition holds. (How could I understand/proove it?) Every polyhedron $P \ne ...
0
votes
1answer
34 views

Euclidean and rectilinear distance and nonlinearity

Can some one please explain why Euclidean distance and rectilinear distance make a problem nonlinear? Thanks
0
votes
0answers
28 views

Converting nested IF's to ILP

I'm trying to convert a nested if structure into a linear programming problem. Here is a simplified example of what I'm trying to do- r1, r2 are binary s1, s2 are natural (I can give an upper bound ...
2
votes
1answer
40 views

Two forms of duality in linear programming

I do not know much about this subject, but I am trying to learn a little. In a book I have it says that a primal problem is: max $c'X$ subject to $AX \ge b$ $X \ge 0$ It says ...
0
votes
1answer
61 views

Linear problem: maximizing net income

Problem: A company produces and sells two different products. The demand for each product is unlimited, but the company is constrained by cash avaliable and machine capacity. Each unit of the first ...
4
votes
5answers
691 views

Why maximum/minimum of linear programming occurs at a vertex?

I'm in high-school and I'm told that the maximum/minimum of a linear programming occurs at the vertex.For more info see the chapter here. For convinience I'm putting relevant excerpt here: Now, we ...
0
votes
2answers
36 views

Line that passes between two vectors

I encountered the following in a text book I'm reading and I can't seem to understand why this is true (I'm translating this into English so excuse me if I'm not using the correct english terms): ...
1
vote
1answer
135 views

How to linearize a quadratic objective function with linear constraints?

I have an optimization problem that I'm working on. The objective is defined as follows: $Maximize: c_i\cdot w_i \cdot x_i - d_i \cdot y_i \cdot \delta_i $ subject to some linear constraints where ...
0
votes
1answer
30 views

Can there be a unique natural number vector solution to $Ax =b$ where $A$ is not a specific type of square matrix?

Let $A$ be $(n-1) \times n$ matrix that is of the following form: $$\left( \begin{array}{ccc} n-1 & 1 & 0 &.... & ....\\ 0 & n-2 & 2 & .... & ....\\ 0 & 0 & n-3 ...