Questions on linear programming, the optimization of a linear function subject to linear constraints.
1
vote
1answer
16 views
How to construct an LP problem that makes a (partial) theorem fail?
I am following a course on linear programming, and one of the exercises calls for an example, that may show that a theorem fails, if a assumption is omitted from the theorem.
The theorem is Theorem ...
1
vote
0answers
25 views
Wealth indicator function for bidder agent logic
I want to create a wealth indicator function used by the logic of a bidder agent, that tells the agent if he's rich (in comparison to others).
Given:
Total number of competitors $n$
Amount of all ...
1
vote
0answers
32 views
Model Linear-Programming Problem
A factory needs to complete $n$ jobs by using $m$ machines. To complete each job $j, j=1,\dots,n$, an amount of $r_j\geq 0$ processing units is required. Each machine $i$ has a processing speed ...
0
votes
0answers
17 views
finding the optimal solution of the dual problem
This is homework.
I have the following dual problem, formed by using lagrangian relaxation.
$$
\begin{align}
min & \{&89y_1 +&3y_2 +&10y_3\}\\
s.t.& &3y_1+& &y_3 ...
0
votes
0answers
18 views
Prove that this linear programming problem has the following dual problem
Consider the following Linear Programming problem:
$$max \sum_{j=1}^nc_jx_j$$
\begin{align} s.t. \quad
\sum_{j=1}^na_{ij}x_j=b_i \quad 1\leq i\leq m\\
x_j\geq 0 \quad 1\leq j \leq n.\\
...
0
votes
1answer
40 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
32 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
35 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
15 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
38 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 ...
4
votes
0answers
106 views
Can you verify a Wikipedia article I wrote? [closed]
I'm a college student in a country of Serbia (South East Europe) studying IT and CS, and for one of the courses I have an asignment to do. The assignment is to make a good, standards following, ...
0
votes
1answer
21 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?
0
votes
0answers
11 views
Whats the deal with phase 1 of 2 phase simplex?
I have been reading online to brush up on my linear programming and I tend to find that people have so many different versions of going about the same thing, its frustrating partly because I don't see ...
0
votes
0answers
13 views
How to add artificial variables to a linear programming matrix
I was working on a linear programming assignment where we are given (via textfile) A, b, c and need to solve the problem:
Max c^t * x (c-transpose x)
such that Ax = b
Now if I recall correctly: ...
1
vote
0answers
27 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
23 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
42 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
24 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
34 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 ...
0
votes
0answers
16 views
linear programing vs. dynamic programing
Is there any similarity or dual principle between both linear programing and dynamic programing ? Any prove or an example would be wonderful.
e.g. can I present this problem as dynamic programing:
...
1
vote
1answer
46 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
22 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
0answers
19 views
Job assignment problem
I want to solve job assignment problem using Hungarian algorithm of Kuhn and Munkres in case when matrix is not square. Namely we have more jobs than workers. In this case adding additional row is ...
0
votes
1answer
28 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
33 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 ...
0
votes
0answers
20 views
Proof by Farkas theorem
2) Show using duality that exactly one of the following systems has a solution:
I) Ax=b, 0 ≤ x ≥ e
II) A^T u + v ≥ 0, b^T u + e^T v=-1,v ≥ 0
Solution:
(P) ...
0
votes
0answers
29 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 ...
-1
votes
0answers
61 views
Proof mathematically [closed]
Can anyone prove it mathematically, please help?
Consider the following linear programming problem:
Min $z=c^Tx$ such that $Ax=b, x\ge 0$. Here $c,x$ are $n\times 1$ matrices, $b$ is a $m\times 1$ ...
0
votes
1answer
40 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
42 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 ...
1
vote
0answers
33 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
49 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 ...
0
votes
0answers
29 views
Fourier Motzkin Elimination for Linear Program
I am trying to solve an LP using Fourier Motzkin elimination. I know that it is not very efficient for LPs but I want to understand how it works in cases where I do not face the worst case(Every ...
1
vote
1answer
68 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
13 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
44 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
0answers
21 views
Linear Programming problem with n variables
Consider a linear programming problem with n variables in standard form. Explain why a non-negative solution to $m$ $\le$ $n$ equality constraints in which at least $n - m$ variables are zero ...
0
votes
0answers
11 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
92 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 ...
3
votes
1answer
69 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 ...
0
votes
0answers
8 views
Find the centroid of an inequality-bounded integer lattice.
Let $Ax \ge c$ be a system of $k$ linear inequalities that define a bounded region in $\mathbb{R}^n$. Suppose we assign each point on the integer lattice (i.e. all coordinates are integers) of ...
2
votes
1answer
60 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
25 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
0answers
35 views
Transportation Problem - Linear Algebra
Say we have a standard transportation problem with supply and demand vectors S = [50, 60] and d = [20, 50, 40] and the cost matrix
C =
R1) 4 3 5
R2) 3 6 2
The minimum cost method provides a way ...
0
votes
0answers
21 views
Examples of exp. sized LPs that can be solved in polynomial time by the GLS variant of the ellipsoid method?
The GLS (grötschel lovasz schrijver) variant of the ellipsoid method is a method that can solve LP with exponentially many facets or variables (by considering the dual LP) in polynomial time if the LP ...
0
votes
1answer
18 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
0answers
14 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
30 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
44 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
31 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 ...
