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

learn more… | top users | synonyms

0
votes
0answers
10 views

Why we always chose minimum Ratio in Simplex method? [on hold]

Why we always chose minimum ratio in simplex method? (linear programming problem)
1
vote
2answers
35 views

Combinations of fruits and their “nutrients”

As a computer scientist and not a mathematician, I know not some of the formal language to describe my problem, so I'll present it in a word problem form. Maybe someone can help me hone my search and ...
0
votes
0answers
8 views

linear programming Q [on hold]

Actully I dont know about that but I'm trying to solve this case: we have a 300000 LE and we want to make surgeries for children in three fields "Cardio, burn and Eyes surgeries" the cardio ...
0
votes
0answers
7 views

How can the max-flow and min-cut problems, if dual to one another, both have unbounded optimal value?

The max-flow min-cut theorem states that the value of the maximum flow is equal to the minimum cut capacity. It is possible that the max-flow and min-cut is equal to $\infty$. However, reading ...
0
votes
0answers
17 views

How can I use Mehrotra's predictor-corrector primal-dual interior point method to solve a problem that is not in the form of cTx?

I am not very familiar with optimization methods. I am studying the paper "Blind channel identification for speech dereverberation using l1-norm sparse learning" (here: http://linyq.com/NIPS2007.pdf). ...
2
votes
1answer
24 views

Modeling with Linear Programming

Here is the scenario; Let's say that a wholesaler have a storage with the capacity of $75,000$ $m^3$. The stock of corn at the beginning of the year is $15.000$ $m^3$ and the working capital is $ ...
0
votes
2answers
20 views

Maximising radius of a circle inside a 2D shape

I'm given a set of inequalities which define constraints of a geometric shape. For simplicity, let's assume its a 2D object, say a triangle. I want to find the maximum radius $r$ of a circle $c$, that ...
0
votes
1answer
13 views

LP model constraint formulation

We have a production plant that for each ton of $a$ requires $p_x$ tons of $x$ and $p_y$ tons of $y$ and we must decide how much material to ship to this plant. Is it just $a = y/p_y = x/p_x$? Do I ...
0
votes
0answers
10 views

Show that B is an optimal basis matrix obtained by replacing b with b*?

I need help with the following 2 part question: Let $B = [a_{B1}, a_{B2}, \ldots , a_{Bm}]$ be an optimal basis matrix for the following linear program: Maximize $CX$ Subject to $AX \leq b$, ...
0
votes
0answers
19 views

Transportation mininum cost problem

I've got a bit stuck trying to solve the following problem: A number of transport companies each offer various means of transportation, for example company A offers: ...
1
vote
1answer
41 views

Games on betting from a set

Two players each chooses a number from the set $\{1,2,4\}$ and correspondingly bets an amount of \$$1$, \$$2$, or \$$4$. There is no collaboration between players. Rules: $1.$ If the two chosen ...
3
votes
1answer
34 views

Upper bound on maximum absolute value of all subdeterminants of a matrix

Let $A \in \mathbb{R}^{m \times n}$ and let $\Delta(A)$ be the maximal absolute value of the determinants of the square submatrices of $A$. A simple lower bound would be $$ \Delta(A) \geq ...
2
votes
0answers
18 views

mathematical model of an assignment/scheduling problem

I am solving a scheduling problem and I am able to abstract it into an assignment problem of assigning 45 machines to 42 jobs. the assignment problem was given as having 14 jobs, each with 3 tasks and ...
0
votes
0answers
10 views

Solving the problem of Affinity using Linear Programming

The affinity problem states that when we have a set of requested instances to be launched on a set of hosts, the placement of instances should be such that they must be close to each other. There can ...
-1
votes
0answers
15 views

Optimization (Excel Solver) [closed]

Coordinating Advertising and Production. The Hawley Lighting Company manufactures four families of household lighting at its factory. The product families are table lamps, floor lamps, ceiling ...
0
votes
1answer
48 views

How can I tell if a two-person game is non-degenerate, given its payoff matrices?

Consider a two-person game with payoff matrices defined by \begin{equation} P= \left( \begin{array}{ccc} 0 & 4 & 1 \\ 2 & 2 & 4 \\ 3 & 2 & 2 \end{array} \right) \quad ...
1
vote
1answer
47 views

Payoff matrix with a specific form

I am very stuck on this question: Suppose that $b \in \mathbb{R}^m$, $c \in \mathbb{R}^n$, $A$ is a $m \times n$ real matrix, and all components of $A$, $b$ and $c$ are positive. Consider the ...
2
votes
3answers
41 views

Convert the non linear problem into standard minimization linear programming form

I have to convert the non linear problem into standard minimization linear programming form Minimize: $|x|+|y|+|v|$ Subject to: $$x+y\le1$$ $$2x+v=3$$ I dont have any idea how can I do it...I would ...
0
votes
0answers
9 views

Necessary and sufficient conditions for a feasible Linear Programme

I am trying to solve the following problem. I have set up the dual, and drawn a graph of the dual. I know solutions must be in the first quadrant as $ x\ge0$ but I don't know how to complete the ...
2
votes
1answer
24 views

Linear Programming Problem - Looking for an Explicit Solution

How can I solve a linear program of the form: $$\min c^Tx\\ \mathrm{s.t.}\ Ax=b\\ x\geq0\\$$ where $c$ is fixed. In the specific case I am looking at, $$x \in R^n$$ $A$ is an $m\times n$ ...
0
votes
0answers
16 views

Spectral methods with linear programming

Is it possible to model and solve some fundamental spectral methods (say Singular-Value Decomposition) with (Integer?) Linear Programming? Update: say you want to do SVD. Can you model it as a ...
1
vote
0answers
4 views

solve multicommodity flow in polynomial size

The original linear program for multicommodity flow has exponentially many variables. How to find equivalent linear program that has polynomial size?
-3
votes
0answers
18 views

Simplex Algorithm go wrong [closed]

When can Simplex Algorithm go wrong? Is there any other way to solve Simplex other than the traditional way of pivoting?
0
votes
1answer
35 views

Probability & darts(in Python)

Suppose you toss a dart at a circular target of radius 10 inches. Given that the dart lands in the upper half of the target, find the probability that its distance from the center is less than 5 ...
2
votes
0answers
30 views

Simple Linear Program Problem in Constrained Optimization

Here is a subproblem I am having difficulties with: $$d = \arg\min_x \ c^Tx$$ subject to $$x: \sum_{i=1}^{n} x_i = 0,\quad x_i \ge -b_i$$ for some $b \in \mathbb R^n$. So I'm looking for an ...
1
vote
1answer
21 views

Question about “linear programming problem” in reference to joint pmf

I'm working on a homework problem and I'm not totally sure what the question is asking... The question reads: "Consider the linear programming problem: maximize $Ax_1+Bx_2$ subject to $x_1+x_2\leq ...
0
votes
0answers
16 views

Let $P$ be a minimization primal problem $\min c^T x$. Does $P$ and its dual $P^*$ always have the same number of optimal solutions?

Let $P$ be a minimization primal problem $\min c^T x$ and let $P^*$ be its dual. I've been wondering about the following: Suppose $P$ has exactly $n$ optimal solutions. I know that $P^*$ also has ...
1
vote
1answer
10 views

Dual problem of a maximization primal problem $P$?

Suppose we have a primal problem $P$ which is stated as a maximization problem $\max c^{T} x$. The dual problem is defined (Introduction to Linear Optimization by Dimitris Bertsimas) only for a ...
1
vote
0answers
55 views

Normalizing Vectors to get short numbers

$\vec{A}$ is vector agent, $\vec{O}$ is vector Object, $m$ is a constant integer. The following expression is repeated with a different O for every loop cycle: ...
0
votes
0answers
30 views

Shadow Prices in relation to a Simplex Tableau

I've solved the maximisation problem $z = 5x_1+6x_2+2x_3$ subject to $x_2 + 0.5x_3 \leq 2000$ $20x_1+20x_2+12x_3 \leq 100000$ $x_1 \geq 2000$ $x_3 \geq 2000$ using long-hand Simplex Method ...
0
votes
1answer
35 views

How does the Simplex method of solving LPs use the starting solution?

Say one looks at the LP (in slack form) and sees that assigning $0$s to all the non-basic variables doesn't give a valid solution but some other non-trivial assignment of values to the non-basic ...
0
votes
0answers
13 views

The network simplex algorithm: finding initial basic feasible solution by auxiliary problem.

Suppose we have a network flow problem without capacities on the edges and want to find a basic feasible solution to start of the network simplex algorithm. It is then stated that if we introduce an ...
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
25 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
13 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
35 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 = ...
0
votes
0answers
25 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
32 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 ...
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
1answer
30 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 ...
1
vote
2answers
34 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 ...
0
votes
1answer
34 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
1answer
22 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
0answers
24 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 ...