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

learn more… | top users | synonyms

0
votes
0answers
17 views

Ford-Falkerson's algorithm for undirected graphs (What am I missing?)

I "found" an algorithm for finding maximum flow in undirected graph which I think isn't correct, but I can't find my mistake. Here is my algorithm: We construct a new directed graph in the following ...
1
vote
1answer
17 views

Formulating Solution for Branch and Bound

I have a linear programming question which I am setting up for a branch and bound solution. I am having issues with where to begin. The question is asking to find the minimum operating cost to ...
0
votes
1answer
30 views

Combining the duality principle and the graphical method

I am trying to minimize this linear program by combining the duality principle and the graphical method: I can't seem to find an example of how to approach this, can anyone show me how I would go ...
0
votes
0answers
14 views

Solve LP-problem in standard form where the right-hand side vector depend on real variable

Suppose we have a LP-problem in standard form $\min c^T x \\ s.t. \ A x = b \,, \ x\ge 0$ where $b$ is an $1 \times 2$-matrix. Suppose we have an optimal basis $B$ corresponding to $b$ and suppose ...
1
vote
1answer
38 views

How to find a polynomial of order $4$ which minimizes a given condition

How to find a polynomial $P(x)$ of order $4$ such that $\max\{\vert\ln(n)-P(n)\vert : 1\leq n \leq12\}$ is as small as possible? I guessed the solution with linear programming, but I don't know ...
0
votes
0answers
21 views

Maximal area intersection of half-planes in $\mathbb{R}^2$

Suppose we have $m$ half-planes $H_1,...,H_m$ in $\mathbb{R}^2$ such that $H_1 \cap \dots \cap H_m = \emptyset$. Let $A$ be a set of subsets $S$ of $\{H_1,...,H_m\}$ with non empty intersection and ...
1
vote
0answers
14 views

Expressing nonlinear problem as LP

I am using GLPK to solve a simple linear problem. Given is a set of distances $d_{ij}$ between nodes of a graph. We want to assign to each edge a velocity $v_{ij}$ such that the average time of ...
0
votes
0answers
20 views

Simplex Method Geometrically

Suppose that at some iteration of the simplex method the slack variable $x_s$ is basic in the $i$th row. Show that $$ \large y_{ij\leq 0, j =1,\ldots, n, j \neq s } $$ then the constraint ...
0
votes
1answer
25 views

unnecessary constraint in optimization problem

I have some optimization problem (optimizing parameter $\alpha$)with those constraints: $$\alpha_i\ge0$$ $$\sum\limits_i \alpha_i y_i =0$$ and a third constraints: $$w-\sum\limits_i \alpha_i y_i x_i = ...
-1
votes
0answers
29 views

Linear Programming question involving a data set of consumer purchases

I am from Netherlands and preparing for an interview with Two Sigma Capital, which for the position I am applying for is notorious for asking linear programming questions. I was trying to solve this ...
2
votes
0answers
33 views

Effective convexity criterion for the finite point set in $\mathbb{R}^3$

I need to find effective convexity criterion for the finite point set. Below there is description of what is meant by "effective" criterion. Definition. Let $M = \{A_{1}, \ldots, A_{n}\}$ be the ...
1
vote
1answer
3k views

Finding dual of linear programming problem

I have to find the dual to this linear programming problem: Maximize $-15z-\frac{11}{20}w-3a-3b=-132+p$ subject to $y+9z+\frac{13}{10}w+3a-2b=12$ $x-2z-\frac{7}{20}-a+b=4$ ...
2
votes
1answer
28 views

Expressing a Set Using Linear Inequalities

Let $D = {x ∈ R^3: |2x1 − x2 + 3x3 + 1| + |x2 + 2x3 − 2| + |5x2 − 3x3| ≤ 10}$. Express D as the feasible solution set of a linear system of inequalities (meaning, a system of the form $Ax ≤ b$). How ...
1
vote
2answers
35 views

Take two pieces of wood one 84 inches the other 74 inches. Need to cut equal amounts of 12.5 inches and 7.75 inches. How to solve?

So the system would look something like this. 74" < 12.5x + 7.75y < 84" 60" < 12.5w + 7.75z < 74" y + z = x + w where x, y, w, z are natural numbers ...
1
vote
1answer
35 views

On the Proof of Fundamental Theorem of Linear Programming.

Having read the link: Why maximum/minimum of linear programming occurs at a vertex? I understand why the optimal solution of any linear programming problem must be on the corner or lies on a face of ...
4
votes
1answer
62 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
36 views

Non linear programming

Could you please help me in solving the problem posted below. A company uses a raw material to produce two types of products. When processed, each unit of raw material yields 2 units of product 1 and ...
1
vote
0answers
38 views

Linear Programming cycling

Suppose that a linear programming problem has the following property: its initial dictionary is not degenerate and, when solved by the simplex method, there is never a tie for the choice of the ...
1
vote
1answer
24 views

Linear programming - geometric change between canonical and standard forms

Suppose that we are given a LP in canonical form, that is in the form $\{x \in \mathbb{R}^d |\ Ax \geq b \}$ and that we want to convert it to an equivalent LP in standard form $\{x \in \mathbb{R}^k \ ...
0
votes
1answer
29 views

Proof concerning basic solutions

Prove that every basic solution of $Ax=b$ (where $A$ is a matrix of rank $r$) is set by $r$ linearly independent columns of matrix $A$ (so it is $[A^{k_1}\dots A^{k_r}]\bar{x}=b$ where $A^{k_1},\dots ...
0
votes
1answer
39 views

How to solve systems of linear equations of multiple variables (more than 3 to 100s)?

This was a question asked during an interview for programming job. And the bottom line was to write an alogrithm to solve such equations. As much as it numbed my neurons - it really provoked me. I had ...
0
votes
0answers
28 views

Find non degenerate linear programming problems

I have to find non degenerate linear programming problem in a canonical form such that: a) it has no solutions b) it has solutions, but but doesn't have an optimal solution A ...
1
vote
1answer
23 views

Converting a Linear Program to Canonical Form

A linear program is said to be in canonical form if it has the following format: Maximize $c^Tx$ subject to $Ax ≤ b$, $x ≥ 0$ where $c$ and $x$ are n-dimensional real vectors, $A$ is an $m × n$ matrix ...
0
votes
1answer
24 views

Simplex method and basic solutions

I have put this into the form $0.5x_1 + 0.25x_2 + x_3=6$ $-x_1 - 3x_2 + x_4=-2$ $x_1 + x_2 = 10$ Is this correct? If so, how do I find a basic solution so that I can begin the simplex algorithm? ...
1
vote
0answers
49 views

Mixed-Integer Linear Programing : get the maximum constant associated to a non null variable

Does anyone know a way get the maximum constant associated to a non null variable using Mixed-Integer Linear Programing ? I would like to get the variable $a$ in this description : $$ i = 1,\ldots,m ...
0
votes
0answers
16 views

Optimal basis versus optimal basis matrix

I have a conceptual doubt about the difference of optimal basis and optimal basis matrix. Some books have defined optimal matrix basis as the following: Consider a linear program on standard form. ...
1
vote
0answers
234 views

Constraints of a linear programming problem

QUESTION Sandy Arledge is the program scheduling manager for WCBN‐TV. Sandy would like to plan the schedule of television shows for next Wednesday evening. Of the nine possible one‐half hour ...
1
vote
0answers
18 views

Can this specific Linear Program constraint be expressed? [duplicate]

Thanks for your time. I have a linear program and no idea how I could express a form of constraint and even if it's possible. Maybe someone here know a solution. A company assembly and sells a ...
1
vote
1answer
36 views

What optimization problem is this?

Minimize $$\sum_{i=1}^{m}w_i x_i$$ with $w_i \in \mathbb{Z}_{\ge0}$, and $x_i \in \{0, 1\}$ subject to a set of $n$ conditions of the form $$\sum_{i\in S_k} x_i \equiv c_k \pmod{2}$$ for $S_k ...
0
votes
0answers
99 views

Complementary slackness condition in economic terms

In linear programming how can one interpret the complementary slackness conditions in economic terms? The linear programming problem is to maximize $\sum_{j=1}^n c_j x_j$ subject to $\sum_{j=1}^n ...
0
votes
1answer
14 views

Relation between minimum of a function and minimum of the sum of the same function and a linear term

I'd like to know if it's true that if given a function $f(x):X \mapsto \mathbb{R}$ and a vector $c \in X$, then if $$v = \arg\min_x f(x) + x^tc$$ one can say that $$v-c = \arg\min_x f(x)$$ Does this ...
1
vote
1answer
9 views

Formula for rate that changes when negative

Is it possible to reduce this code to a single formula, rather than check if x is negative? ...
0
votes
1answer
31 views

Linear Programming Inventory

A company is opening a new franchise and wants to try minimizing their quarterly cost using linear programming. Each of their workers gets paid 500 per quarter and works 3 contiguous quarters per ...
1
vote
1answer
71 views

books on the application of linear algebra on statistics/finance/machine learning

I am reading "linear algebra done right" by Axler and like it a lot. One thing though, in the end I would like to put these theory to use and as a math textbook it doesn't cover much application. ...
0
votes
0answers
29 views

Linear Programing : get the maximum constant associated to a non null variable

Does anyone know a way get the maximum constant associated to a non null variable using only linear programing ? For example, supposed that there is 3 linear variable x, y and z. x being associated ...
0
votes
1answer
57 views

Linear programming and the simplex method

I am trying to solve this system of equations. My approach would be to introduce slack variables and then somehow use the simplex algorithm to solve this. Can anyone show me how this is done?
0
votes
0answers
16 views

Maximization over linear surjective mapping of polyhedron

I am reading this paper and confused about the derivation of equation (11) (page 3, bottom of column 2). I will rephrase it in this question. Let $\mathcal{P}_r = \{ x \in \mathbb{R}^n : P_r x \leq ...
0
votes
0answers
11 views

Properties of an LP when the coefficients are variables of the problem

If I had a standard LP problem, and the coefficients of it are variable to the problem and I want to draw on the properties of the LP to say something about the coefficients. What such properties can ...
0
votes
0answers
40 views

LP transformation of multi-commodity flow problem

I have the following multi-commodity flow problem that I would like to bring into canonical LP format. \begin{equation*} \begin{aligned} & \underset{d}{\text{minimize}} & &d(x) = ...
2
votes
0answers
36 views

What is a closed chain (or circuit) that is used in solving a transportation problem (a special type of linear programming problem)?

What is a closed chain (or circuit) that is used in solving a transportation problem (a special type of linear programming problem)? I'm having some problems with it. Please clarify it. I have posted ...
3
votes
1answer
42 views

Finiteness of the Supremum of Inner Product of Two Finite Sum Positive Sequence

Let $$A = \Big\{(a_1,a_2,\dots)\ \Big|\ a_i\ge 0, \sum_{i=1}^\infty a_i=1\Big\},$$ $$v(x)=\sup\left(\bigg\{\sum_{i=1}^\infty a_ib_i\ \bigg|\ (a_i)_{i=1}^\infty,\, (b_i)_{i=1}^\infty \in ...
0
votes
1answer
27 views

Optimization options to select multiple items with different features and values

I'm trying to identify which approach would work best to select a set of elements that have different features that minimise a certain value. To be more specific, I might have a group of elements with ...
1
vote
1answer
38 views

Taking the dual of this non-standard linear program

I am just beginning to learn linear programming have a question about taking the dual of a non-standard LP specifically the one below: $\min M\\ 2x_1 + 3x_2 + 4x_3 \leq M \\ 2x_1 - x_2 + x_3 \leq M\\ ...
0
votes
0answers
14 views

Linear Optimization: What is the difference between these two theorems?

I attend a lecture about linear optimization where we had the following two Theorems. But I somehow cannot spot the difference: Theorem 1: Let $P$ be a polyhedron with an extreme Point and $c \in ...
1
vote
0answers
39 views

Proof of Simplex Method, Adjacent CPF Solutions

I was looking at justification as to why the simplex method runs and the basic arguments seem to rely on the follow: i)The optimal solution occurs at some vertex of the feasible region (CPF points) ...
0
votes
1answer
34 views

Conversion of a general linear program into a standard linear program

I am trying to teach myself the basics of optimization of linear programmes, for example the following question: How do I tackle such a question?
0
votes
0answers
19 views

Tableau Condition for dual simplex algorithm

The following is a tableau obtained when solving a minimization linear programming problem via the dual simplex algorithm. basic $x_1$ $x_2$ $x_3$ $x_4$ $x_5$ $x_6$ $x_7$ RHS ...
0
votes
1answer
437 views

Programación Lineal (PL)

quería ver si me pueden ayudar en plantear el modelo de Programación Lineal para este problema. Sunco Oil tiene tres procesos distintos que se pueden aplicar para elaborar varios tipos de gasolina. ...
0
votes
1answer
31 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 ...
2
votes
0answers
37 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 ...