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

learn more… | top users | synonyms

2
votes
0answers
144 views

Convert a problem o minimizing a function to linear programming problem in standard form

I have to 1) convert a problem o minimizing a function to linear programming problem in standard form. It is something new to me. Can somebody explain it to me? $$\min(\mathbb{R}^2\ni(x,y)\rightarrow ...
0
votes
1answer
63 views

Optimization problem in the standard form

Let $x\rightarrow x^{T}c$ be an objective function of an optimization problem in the standard form, for which the optimal solution doesn't exist. Does then exist an optimal solution to $x\rightarrow x^...
0
votes
1answer
234 views

Dual simplex doubt (unrestricted)

I have this two problems and i only want to find the dual form: $\begin{gather} max\hspace{.1cm}z =5x_1+6x_2\\ s.t\hspace{.1cm}x_1+2x_2=5\\ -x_1+5x_2 \ge 3\\ x_2 \ge 0\\ x_1\hspace{.1cm} ...
0
votes
1answer
483 views

Linear Programming : Is there any other way to solve than graphs?

In my highschool curriculum there's a a chapter on Linear Programming Problems. In the chapter there are bunch of unproved statements and mechanical ways to solve linear problem. But my question is- ...
1
vote
1answer
64 views

Linear Programming and Geometry Question

I have a question that involves some linear programming and linear algebra, and I really don't have a clue how to approach this question. Could someone give me some hints and ideas as to how to attack ...
1
vote
1answer
249 views

Linear Programming and Standard Form

In order to find the dual of a primal linear program, do I always have to convert it to the standard form first? For example, if I have the following LP, would the dual also be a min since the LP in ...
1
vote
2answers
113 views

References for Linear Algebra needed for Differential Equations and Linear Programming

I am in need of learning the Linear Algebraic theory behind the following Applied disciplines. Could someone please recommend Linear Algebra books for: Differential Equations: Specifically learning ...
1
vote
0answers
56 views

Write down a linear programming problem

I want to replicate a linear programming problem.I have the following information, for the background." A fuzzy regression analysis with only one independent variable X results in the following ...
2
votes
2answers
73 views

Is $[u_1,u_2]$ an edge of the polytope $conv(F)$?

Here's the problem. I have a finite set of vectors $F \subset \mathbb{Z}_{\geq 0}^d$. I define $P$ to be the convex polytope $conv(F)$ i.e. the convex hull of $F$. Given $u_1, u_2 \in F$, is the ...
0
votes
1answer
63 views

Given a set of integers find two disjoint subsets $I$ and $J$ so $|I|+|J|=k$ and $\sum\limits_{i \in I}x_i = \sum\limits_{j \in J}x_j = n^2$

Given a set of integers $1 \le x_1,x_2\dots,x_n \le n^2$ and a number $k \le n$. describe an algorithm that will determine if there exists two disjoned subsets $I$ and $J$ such that $|I|+|J|=k$ and $\...
2
votes
1answer
365 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
53 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 + \frac{6}{...
1
vote
1answer
3k 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$$ $$2x_{1}-...
0
votes
1answer
102 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) ...
5
votes
1answer
226 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
175 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
98 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
1answer
163 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 $d$-...
2
votes
1answer
168 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
147 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
126 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 ...
1
vote
1answer
172 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
18 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 ...
1
vote
1answer
106 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
30 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
49 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
42 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
1answer
105 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
170 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
1answer
45 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
158 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 ...
1
vote
0answers
175 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 $c,a\in\mathbb{R}^{M\...
0
votes
2answers
50 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
44 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
47 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
1answer
58 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
178 views

Euclidean and rectilinear distance and nonlinearity

Can some one please explain why Euclidean distance and rectilinear distance make a problem nonlinear? Thanks
2
votes
1answer
63 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
248 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
6k 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
41 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
2k 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
42 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 ...
2
votes
1answer
178 views

Prove vertices of a simplex are affinely independent

I'm given that the definition of a simplex $T$ is $x \in\mathbb R^n$ such that $x$ satisfies $n+1$ linear inequalities: $(u_k, x) \lt c_k$ for $k = 1,\ldots,n+1$ (i.e. $T$ is the intersection of $n+1$ ...
2
votes
1answer
108 views

Find the minimum value of C subject to the given constraints.

C=2x+5y Constraints: x+y>=2 2x-3y<=-6 3x-2y>=6 A-42 B-4 C-49 D-10 I encountered this question while doing the Systems of Linear Equations and Inequalities test at http://www.classzone.com/books/...
0
votes
1answer
45 views

The meaning of initial value in linear programming

I am new to LPP. I would like to know what is meant by setting an initial value(IV) to a variable. For example I was solving a problem where objective function(OF) is non-negative. When I give some IV ...
1
vote
0answers
70 views

Proving boundedness of a function .

Consider the function \begin{eqnarray} f(x_1,x_2,\cdots, x_n) = \frac{\sum_{i}^{n}a_ix_i}{\sum_{i}^{n}b_ix_i}, \end{eqnarray} over the set $S = \{x := (x_1,x_2,\cdots, x_n):-1 \leq x_i \leq 1,\; \...
0
votes
1answer
109 views

Proving boundedness of a function (part 1).

Consider the function \begin{eqnarray} f(x_1,x_2,\cdots, x_n) = \frac{\sum_{i}^{n}a_ix_i}{\sum_{i}^{n}b_ix_i}, \end{eqnarray} over the set $S = \{x := (x_1,x_2,\cdots, x_n):-1 \leq x_i \leq 1,\; \...
1
vote
0answers
141 views

Proof of Strong Duality via Farkas Lemma

I am trying to prove what is often titled the strong duality theorem. There is a hint in the book that I'm following, and I want to follow the method they have outlined for me. I will outline the ...
1
vote
2answers
43 views

How to introduce flat cost of flow over a node using mixed integer programming.

In the set up for the program we have a graph where we are trying to minimize the cost of sending flow over the arcs. I have formulated the following linear program. \begin{array}{ll} \text{minimize} ...