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

learn more… | top users | synonyms

0
votes
1answer
1k views

Construct a linear programming problem for which both the primal and the dual problem has no feasible solution

Construct (that is, find its coefficients) a linear programming problem with at most two variables and two restrictions, for which both the primal and the dual problem has no feasible solution. For ...
0
votes
0answers
68 views

Basic Solutions in Linear System

I am studying Linear programming and we have just learnt about Basic solutions. I know that a basic solution (x) should have 2 properties: should indeed be a solution. $Ax = b$ should hold. for some ...
1
vote
2answers
78 views

Linear programming problem neither max nor min

Heres the actual question: television provider broadcasts two movie channels, A and B. Channel A broadcasts 1 romantic movie, 3 action movies and 3 comedies per month at a cost of 50 Euro. ...
1
vote
1answer
138 views

Minimizing deviations from threshold value from a given group of numbers

Given a set of numbers $a_n$, a threshold level $t$, how do I find the combination of numbers that will sum to at least the threshold with minimum deviation? Added: That is, they must always exceed ...
0
votes
1answer
126 views

Partial linear relaxation yields an integer solution

Consider a binary integer program \begin{align} \min \quad &\sum _{j \in J}f_j x_j +\sum _{i \in I} c_i y_i \notag \\ \mbox{s.t.} \quad &\sum _{j \in N_i} x_j \ge 1-y_i, \quad \forall i\in I ...
0
votes
1answer
424 views

How to linearize the following LP

I want to minimize $|d_1-d_2|+e1+e2+e3$ where $d_1,d_2,e_1,e_2,e_3>=0$ and $|.|$ denotes the absolute value, for some linear constraints. Is there any way I can linearize the objective function?
1
vote
0answers
45 views

What are the available libraries or programs for finding extremes of a function with no symbolic definition?

In my current mathematical inquiry, I would like to gain insight on behaviour of a $d$-dimensional continuous function by locating its maximum over the hyperplane $\sum_{i=1}^d x_i = 1$ for $x_i$ ...
0
votes
2answers
999 views

Optimal Basic Feasible Solutions

In linear programming, is it true that you can only have at most 2 optimal basic feasible solutions? If so, why?
2
votes
1answer
245 views

Show that two Linear Programming problems are equal

Consider the general linear programming problem $min \sum_{j=1}^n c_jx_j$ s.t. $\sum_{j=1}^n a_{ij}x_j \leq b_i$, for $i=1,\dots , m$ $x_j \geq 0$ for $j=1,\dots , n$ And the ...
0
votes
1answer
213 views

How to solve an underdetermined linear system with variables limited to an interval

If I have an underdetermined linear system of equations, with the additional constraint that all of the variables are limited to the interval $[0, 1]$, what techniques are there to solve this in the ...
2
votes
2answers
512 views

Exploring underdetermined linear system with non-negative solution

I haven't had much luck searching for this specific problems. Any pointers would be greatly appreciated. I have an underdetermined system where $ A $ and $ b $ are known. $ x $ is a real vector with ...
1
vote
1answer
425 views

Strict inequality in MILP

I have a problem with the following constraint. There are 2 variables $p \in [0,1] \subseteq \mathcal{R}$ $\sigma \in [0,1] \subseteq \mathcal{Z}$ The constraint over the variables is $c - p < ...
0
votes
1answer
40 views

How to solve Linear programs of the form Maximize v

I face difficulties in solving LPs in the form Maximize v subject to: a11x1+a12x2<=v ...........<=v The v is the variable I want to maximize. Should I ...
0
votes
1answer
101 views

Show using duality that exactly one of the following systems has a solution

(I) $Ax=b$ ; $0≤ x ≤e$ (II) $uA +v ≥0 ; ub + ve = -1 ; v ≥ 0$
1
vote
0answers
96 views

Prove mathematically

Q.1 Consider the dual simplex method applied to a standard form problem with linearly independent rows. Suppose we have a basis which is primal infeasible, but dual feasible, and let i be such that ...
1
vote
0answers
220 views

Strictly Dominated and Never Best Response in LP

There is a well known notion of Strategic Dominance in Game Theory. I am interested in elimination of strictly dominated strategies by Linear Programming and in LP for definition of never best ...
0
votes
1answer
2k views

Finding the number of basic/zero variables at an optimal corner point in linear programming

Draw a graph of the following problem $$\begin{align}4x+3y &\leq 180 \\ 7x+4y &\leq 280 \\ y &\leq 40 \\ x &\geq 0 \\ y &\geq 0\end{align}$$ a) If the problem is to ...
1
vote
1answer
229 views

How tell if a polyhedron contains a lattice point

So given a polyhedron $Ax \le b$ Is there an Algorithm or formula to determine whether said polyhedron contains a lattice point (integer point) I was thinking a couple things: brute force ...
2
votes
0answers
54 views

Linear Program Transformations

I have a Linear Program with constrains of the form: $$a_{11}x_1+a_{12}x_2+\ldots\le 0$$ $$a_{21}x_1+a_{22}x_2+\ldots\le 0$$ $$a_{31}x_1+a_{32}x_2+\ldots\le 0$$ My problem is that if I try to ...
0
votes
1answer
313 views

Multiple Choice Knapsack Problem (MCKP) where one class requires more than one item

I have the following problem of which I am attempting to find a near optimal solution: I have one knapsack which can hold a maximum weight. I must select exactly one distinct item from a number of ...
1
vote
1answer
2k views

Linear programming vs. Integer programming

I was trying to solve a problem where I want to choose which items to choose where each item has a number b_i associated with it and a reward r_i associated with it. I need to choose items that ...
1
vote
0answers
21 views

Issues with solving large sparse linear equations

I have some issues solving sparse linear equations Ax = b My matrix A is sparse with dimension of 5 million by 5 million. Actually, it is a combination of two matrices. One is tridiagonal and the ...
2
votes
1answer
375 views

Simplex on Linear Program with equations

My linear program instead of inequations also contains one equation. I do not understand how to handle this in every tutorial I searched the procedure is to add slack variables to convert the ...
1
vote
1answer
37 views

How to calculate the variance of linear prediction parameters?

I'm using linear prediction with singular value decomposition (LPSVD) to analyze signals that are damped sinusoids. If my understanding of the theory of linear prediction is correct (and it may not ...
3
votes
1answer
150 views

Correctness of these linear programming formulations

Problem: A Company can use 3 different procedures to produce a product, for the production of every product are necessary 3 machines as below: The numbers relate the hours necessary. every ...
4
votes
1answer
412 views

Is the inverse of an invertible totally unimodular matrix also totally unimodular?

My question is learned from here. Let me restate it as follows: A unimodular matrix $M$ is a square integer matrix having determinant $+1$ or $−1$. A totally unimodular matrix (TU matrix) is a matrix ...
2
votes
1answer
137 views

Is this linear programming?

I have the following problem and I'd like to know if it is formalizable as a LP program. (or, more generally, if it is solvable in polynomial time). Let us fix some terminology first which will ...
0
votes
1answer
37 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
29 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 ...
0
votes
1answer
73 views

Graphical solution of LOP with three variables and a parameter

For what values of $\lambda$ does the following linear optimization problem has no solution? $$ x_2 - \lambda x_3 \to \operatorname{min} $$ subject to \begin{align*} -x_1 + 3x_2 + x_3 & ~=~ 3 \\ ...
0
votes
1answer
75 views

Finding a dual Linear-Program

We are trying to prove Von-Neumann's MINIMAX Theorem namely $$\max_{x\in\Delta_{n}}\min_{y\in\Delta_{m}}y^{T}Ax=\max_{x\in\Delta_{n}}\min_{1\leqslant i\leqslant n}(Ax)_{i}$$ (Here $\Delta_k$ is the ...
1
vote
1answer
258 views

Farkas lemma variations

Suppose the system: $Ax=0,x \geq 0, $ and $c \cdot x > 0$ does not have a solution. How can I apply Farkas' lemma to create a system that must have a solution? I'm not so sure how to proceed, ...
3
votes
1answer
38 views

Is it necessary to state that $y_i \leq 1$

In a class test for Linear Programming, my professor deducted some marks because I missed the condition $y_i \leq 1$ in the mixed strategy games solution. $ y_i $ stands for the probability of any ...
1
vote
0answers
333 views

Showing a dual LP solves a primal LP

I originally asked this question: Does solving the LP dual SOLVE the primal LP? It was answered using an example of how the primal and dual solve each other (because of knowledge from strong ...
1
vote
0answers
93 views

Linear Programming: Modifying Coefficients of the Objective Function

Consider a final tableau with entries: Row 1: 0,(-1/2),1,1,2,0,-1 Row 2: 1,(1/2),0,2,-1,0,-2 Row 3: 0,2,0,-1,(-1/2),1,3 Basic variable values (4,2,1) and objective function coefficients ...
1
vote
1answer
214 views

Linear Programming for Integer Solutions

Connsider the linear programming problem Max $z = 5x_1 + 6x_2$ st. $10x_1 + 3x_2 \leq 52,2x_1 + 3x_2 \leq 18$ and $x_1, x_2 \geq 0$ and integer. How would one manipulate the resources so that the ...
7
votes
2answers
438 views

Finding the payoff matrix of a game

A two player zero-sum game can be represented by a $m\times n$ payoff matrix $M$ having $m$ rows and $n$ columns with values in $[0,1]$. The value $M(x,y)$ represent the payoff given to player $1$ ...
1
vote
1answer
305 views

How to prove this? The existence of solutions to linear inequalities

A system of real homogeneous linear inequalities $\lambda_i>0$, $i=1,2,\ldots,m$, has a solution if and only if there is no nontrivial linear dependence with nonnegative coefficients among the ...
0
votes
2answers
36 views

What are the constraints on this system

A company produces 2 types of frames, an ATB frame and a race frame For the ATB frama you need 4kg of aluminum and 6kg of steel, for the race from you need 5kg of aluminum and 2kg of steel. They ...
1
vote
1answer
257 views

Drawing in 3 dimensions: Feasible region

We have the following constraints: $$ 0 \leq x \leq 10$$ $$ 0 \leq y \leq 20$$ $$ 0 \leq z \leq 25$$ $$ 0 \leq x + y + z \leq 15$$ We have to draw this in an 0xyz - coordinate system, I did the ...
3
votes
1answer
320 views

Linear Programming question - Optimal solution

In Linear programming, you want to optimize stuff. For example; minimize the costs and maximize the profit. We have a series of constraints, in my case on either 2 or 3 variables. You can draw them in ...
4
votes
2answers
258 views

Wolves and chicks puzzle

This problem is from the handheld video game, Professor Layton and the Curious Village. I think the solution is very cool, but more than that, I want to know how to show that the minimum number of ...
0
votes
2answers
108 views

Checking the existence of a solution for a set of linear equality and ineaulity equations

I would like to know if there is a method to check the existence of the solution for a given set of linear equations composed with both equalities and inequalities? I'm not interested in the solution, ...
2
votes
1answer
222 views

Convex optimization and linear programming please help! :)

How would I write the following as a standard form LP? Minimizing $\sum_{i=1}^n x_i + c\max(a_i-x_i)$ for $a_i \ge 0$ and what is the optimal value for when $c=n$ How to express minimize $\frac{1}{2} ...
1
vote
2answers
558 views

Max and min value of $7x+8y$ in a given half-plane limited by straight lines?

So, there are four inequalities: $$\begin{eqnarray*} y &\geq &-3x+15; \\ y &\leq &-11/3x+56/3; \\ x &\geq &0; \\ y &\geq &0. \end{eqnarray*}$$ If we draw all those ...
0
votes
1answer
124 views

Bounded and Feasible of Linear Program?

I have a question on usage of terminology in Linear programming. Why do we have terms like "If an LP is bounded and feasible, then..." My confusion is, if a Linear program is bounded then it has to ...
0
votes
0answers
39 views

Please help with the LP formulation

I would like to formulate the following constraints as a Linear constraint $|x_1-y_1| + |x_2-y_2| + |x_3-y_3| > |\sum_{i=1}^nx_i- \sum_{i=1}^ny_i|$ $ \bf{x,y} \in \bf{R}^n $ Basically I am ...
0
votes
1answer
1k views

How to a plot a line for ax+by-c in MATLAB?

The title basically says it all. I'm doing an assignment and need to include a plot of my scatter and the line generated by linprog(). I ran ...
2
votes
0answers
49 views

Put positive polynomial in finite intersection of half-spaces

Denote by $V={\mathcal P}_{n,d}$ the space of polynomials in $n$ variables with degree at most $d$, with rational coefficients. Thus ${\mathcal P}_{n,d}$ had dimension $\binom{n+d}{n}$ over $\mathbb ...
2
votes
0answers
103 views

Need help finding unknowns in simplex tableau.

I need help with this homework problem. The objective is to maximize $2x_1 - 4x_2$, and the slack variables are $x_3 and x_4$. The constraints are $=<$ type. Tableau $\begin{matrix}z & x_1 ...