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

learn more… | top users | synonyms

0
votes
0answers
29 views

The set of all vectors satisfying $Ax\ge\vec{0}$

Consider a rectangle matrix $A\in\mathbb{R}^{m\times n}$ with $m\ge n$, and the set of all vectors $x\in\mathbb{R}^n$ satisfying $Ax\ge\vec{0}$. I note this set is closed under multiplication by a ...
0
votes
0answers
10 views

Uniqueness of Solution in infinite linear programming

I would like to ask about a sufficient condition under which a solution for an infinite linear programming is unique. In standard finite dimensional linear programmings, like $\min_x p\cdot x$ ...
0
votes
0answers
16 views

graphing dodecahedron with inequalities [duplicate]

Write a set of inequalities so that the set of all solutions is a dodecahedron. Is there a better way to do this than brute force? It needs to be a regular dodecahedron. All im given is knowledge of ...
0
votes
2answers
23 views

Setting up a linear programming word problem

Problem: A metalworking shop needs to cut at least 32 large disks and 219 small ones. There are three cutting patterns for the standard size metal rectangle. One cutting pattern produces two large ...
0
votes
0answers
13 views

How is the pivot chosen for the symbolic weights for the Cassowary algorithm?

I am trying to understand The Cassowary Linear Arithmetic Constraint Solving Algorithm, and I am having trouble understanding symbolic weights, starting in section 2.3. Working through the example, ...
0
votes
1answer
20 views

Linear Programming - deriving the Dual of the Primal

I've the following linear programming problem: This is the LP representation of the uncapacitated facility location problem. This is the dual representation of this problem: My question is how ...
0
votes
0answers
7 views

Linear Programming Neighborhood Problem 2

Suppose we are given a set of 2n integers and we wish to partition into 2 sets $S_1$ and $S_2$ so that |$S_1$|=|$S_2$| and so that sum of number in $S_1$ is as close to sum of numbers in $S_2$.Let ...
0
votes
0answers
16 views

Linear Programming Neighbourhood problem

In the n-city TSP what is the cardinality of $N_2(t)$ , the neighborhood of tour t determined by 2 change? What is the cardinality of $N_3(t)$?
0
votes
1answer
12 views

Primal feasible solution implies Dual optimal solution?

Every feasible solution of P puts an upper(or lower, depending on whether it is a maximization or minimization problem) bound on the optimal solution of D(assuming of course that D has a feasible ...
0
votes
1answer
34 views

Mixed Integer Linear Programming: Construction Rods

I have an interesting problem involving linear programming. The problem is the following, I have 4 different kinds of rods (rod sized found in the local market): 9m rod 11m rod 12m rod 15m rod ...
-2
votes
1answer
28 views

linear programming project [closed]

A local business plans on advertising their new product by purchasing advertisements on the radio and on TV. the business plans to purchase at least 60 total ads and they want to have at least twice ...
0
votes
1answer
15 views

Conditions for a LP to be integral

What are the conditions to be met by a LP that allows to infer that its optimum solution will be integral? Is total unimodularity a necessary and/or sufficient condition? What if all variables are ...
0
votes
1answer
12 views

LP Word Problem Construction

I am having difficulty constructing the constraints on a word problem as follows: The Brite-lite Company receives an order for 78 floor lamps, 198 dresser lamps, and 214 table lamps from condoski ...
0
votes
0answers
21 views

Indicator Variable, Mixed Integer Linear Programming

Assume $x$ is a real variable, and $0\leq x \leq1$. Besides, $y$ is a binary random variable. I need a linear program that: if $y$ is $1$: $x>0$, if $y$ is $0$: $x=0$ I know the following ...
1
vote
0answers
11 views

Solving a linear program using just one call to a procedure that gives a feasible solution.

Suppose we have some procedure $F$ which takes any set of linear constraints and either returns either infeasible or returns a vector satisfying these constraints. If we now take a linear program ...
0
votes
1answer
30 views

linear programming problem solving

I have written in lp solve and obtain the solution of 0.58 highqualitymeat and 0.41 lowqualitymeat the thing that confuses is doing it through a graph as: let x be high quality meat and y be low ...
0
votes
0answers
10 views

Linear programming and complementary slackness

If there's a given basic solution $ A = (x,w)$ for the primal problem (where $x$ are decision variables and $w$ are slacks), I can determine the dual variables $y$ and slacks $z$ associated with B.S. ...
4
votes
1answer
29 views

Maximize $Z=-x+2y$ given $x\geq 3,\ x+y\geq 5,\ x+2y\geq 6,\ y\geq 0$

I am a highschool senior that's new to this topic. So, apologies for my lack of knowledge and misconceptions. The proof of the theory of this chapter is beyond the scope of my textbook, so that may be ...
-1
votes
0answers
13 views

Turning a slack constraint into an excess constraint

Given a Linear Programming Problem with an excess constraint $ax+by\ge c$ We could turn it into Canonical form by adding an excess variable: $ax+by+e_1=c$ Solving using the Simplex Method requires ...
0
votes
1answer
21 views

Linear Programming:What combination of two loams to minimize cost

I am fairly new to linear programming so simplification would be helpful.Came across a certain question and unfortunately no answer for it at the back of the book. The question is adopted from a book ...
0
votes
2answers
22 views

Prove linear program is unbounded

So I need help on my homework (I feel like a 10 year old). The exercise goes like this: Prove algebraically that the following program is unbounded: Max: $x_1 - x_2$ Constraints: $-2x_1 + x_2 ...
2
votes
1answer
93 views

Lemke-Howson pivoting in degenerate bimatrix games

I'm working on an implementation of the Lemke-Howson algorithm for finding Mixed Nash Equilibria of bimatrix games, and I'm running into a roadblock when the algorithm is fed a degenerate game. For ...
0
votes
0answers
22 views

Feasibility Sets for Integer Program

I have two set of constraints defining feasibility sets $A$ and $A'$ of a mixed integer program. $x_{i}, y_{ij}$ are continuous positive variables, $a_{ij}, b_{ij}, c_{ij}, d_j$ are known ...
1
vote
1answer
19 views

A linear program for maximizing a fraction

Given $\lambda_1,\ldots,\lambda_n \geq 0$ and an $n\times n$ matrix $A$, I wish to maximize the ratio $$ \frac{\lambda_1x_1 + \cdots + \lambda_nx_n}{x_1+\cdots+x_n}, $$ where $x_1,\ldots,x_n \geq 0$ ...
0
votes
0answers
22 views

simplex algorithm with tableau

in the picture below you can see the tableau representation of a linear programm with a coefficient $b\in \mathbb{R}$. BV stands for basic variable. For which $b$ is $y_1=\frac{1}{2}, ...
2
votes
1answer
39 views

how Determine the maximum values of C.

how Determine the maximum values of C. my try is that : To graph the last two bounding lines, I'll want to put the equations into slope–intercept form. The bounding line corresponding to the 3rd ...
0
votes
1answer
19 views

LP program: does the decision variable coefficients affect the problem?

I just started reading up on linear programming by myself, and am a bit confused by the decision variable coefficients $c_j$, in the objective function $ \sum_j c_jx_j$. Do they matter? I mean, if ...
3
votes
1answer
46 views

What gambling/board game or real life thing can (surprisingly) be modelled as a linear programming problem?

So I've taken Linear Programming 101. I've read my textbook, took the test and all that, and - besides all the theory, the nice algebraic interpretations, etc - I've encountered a lot of textbook ...
1
vote
0answers
133 views

duality theory question

Let $A$ be a given $m$ x $n$ matrix, and $c\in R^n$ and $b\in R^m$ be given vectors. Use LP duality theory to show that if the problem $$\min\{x^Tx: Ax=b, x\geq0\}$$ has a finite optimal solution, ...
0
votes
0answers
41 views

extreme points and representing

$$X=\{(x_1,x_2)^T : x_1-x_2\leq3, 2x_1+x_2\leq 4, x_1\geq -3\}$$ Find all extreme points of $X$, and represent $x^*= {0\choose1}$ as a convex combination of those extreme points. I sketched it out ...
0
votes
0answers
35 views

L_1 norm optimization as a sequence of linear optimizations?

Does someone know of numerical methods to approximately solve ${\bf x_0} = \min_{\bf x}\{ \left\|\bf Mx - b\right\|_1\}$ by using some sequence of linear optimizations? Links or ideas are both ...
0
votes
0answers
24 views

Computing a lower bound for the minimal componentwise distance of vertices of polyhedra

Let $A$ be a matrix in $\mathbb{R}^{m \times n}$ and let $P = \{ x \in \mathbb{R}^n \mid Ax \leq b \}$ be a polytope. I want to compute a lower bound on the minimal componentwise distance of two ...
1
vote
0answers
56 views

Linear programming optimization problem formulation

I need help in formulating an optimization problem. I have a system of equations as follows: $c_1x_1+c_2x_2+c_3x_3=1$ $b_1x_1+b_2x_2+b_3x_3=1$ $a_1x_1+a_2x_2+a_3x_3=1$ In my case the ...
0
votes
0answers
13 views

Complementary slackness to find out values of variables

I am stuck here. This is my progress so far: Since $x_5 \neq 0$ then there must be some slack in row two. Therefore $y_2=0$ in the dual solution. Secondly $x_3\neq 0$ and so we have equality in ...
0
votes
1answer
20 views

Why is a local min also a global min for convex functions?

As the title states, for an unconstrained minimizaton problem, of a convex function, why is it that the local minimum is also the global solution?
2
votes
1answer
19 views

How does the Simplex method handle test ratios with zeros?

I've been running into an issue choosing a pivot when there are constraints with an RHS of zero. It appears that sometimes you should include zero test ratios when searching for the minimum test ...
2
votes
2answers
49 views

Integer Linear Programming

Without using a computer, I have to solve the following integer linear programming:$$\min \quad x_1+x_2+x_3$$ $$\operatorname{sub} ...
0
votes
2answers
23 views

If $\phi$ is injective linear map $\mathbb{R}^r \rightarrow \mathbb{R}^s$ then $Im \phi$ is closed in $\mathbb{R}^s$

My optimization theory handbook says that If $\phi$ is injective linear map $\mathbb{R}^r \rightarrow \mathbb{R}^s$ then $Im \phi$ is closed in $\mathbb{R}^s$, where $Im \phi$ denotes image of map ...
1
vote
1answer
22 views

Prove a property of primal-dual problems

When I was studying the computation aspects of quantile regression, I consulted some linear programming book and found an interesting property as follows: If the primal problem have unbounded ...
0
votes
1answer
34 views

$ \mathbb{F} = \{x \in \mathbb{R}^n:Ax=b\}= \mathbb{F}_r=\{x \in \mathbb{R}^{n}:A^{(r)}x=b^{(r)}\}$

Show that these two sets are equal. $A$ is an $m\times n$ matrix of rank $r$, $b \in \mathbb{R}^m$. $A^{(r)}$ denotes an $r\times n$ matrix with $r$ linearly independent rows of $A$ and $b^{(r)}$ is ...
0
votes
0answers
18 views

Systematic Gaussian elimination on a binary matrix?

I am trying to understand the mathematics behind the lights out puzzle (http://mathworld.wolfram.com/LightsOutPuzzle.html). There's a very helpful webpage at ...
0
votes
0answers
48 views

Converting nonlinear program into linear program

Consider the following nonlinear optimization problem \begin{align} \min \quad c^Tx &+ f(d^Tx)\\ \text{s.t.} \quad Ax &\geq b\\ x &\geq 0 \end{align} where $$ f(y) = \begin{cases} -y+2 ...
0
votes
0answers
13 views

A basic solution to a linear program

I know that with an objective function of two variables, the basic solutions to a linear programming problem are the points where the constraints intersect in an xy-graph. But, if we are given an ...
2
votes
1answer
32 views

Constructing a newton sequence

How may I construct the newton sequence for the following: $(1) f(x_1,x_2) = x_1^4 + 2x_1^2x_2^2 + x_2^4$ with $x_0 = (1,1)$ and $x_0 = (1,0)$ $(2) f(t) = t^4 - 32t^2$ and $t_0 = 1$ To find ...
0
votes
2answers
35 views

Transpose notation question

In a course I am undertaking, I was exposed to the following notation for Taylor's theorem: Fix $x^∗ , x ∈ \mathbb{R}^n$ and assume that $f : \mathbb{R}^n → \mathbb{R}$ has continuous first and ...
0
votes
1answer
27 views

Convolution Properties

I have a quick question about certain algebraic properties of convolution. If I have 3 functions $f(x)$, $g(x)$ and $h(x)$, is the following true? $\Big[ f(x) . g(x)\Big] \circ h(x) = \Big[f(x) \circ ...
0
votes
0answers
31 views

Lowest upper bound for linear system?

Assume you have an under-determined linear system $AX=B$ where you have more variables than constraints. It is also known that $X>0$ (element-wise). How can you determine the (scalar) lowest ...
0
votes
0answers
21 views

Linear Programming problem - Packing Trucks Objective Function

I'm learning about linear programming and I want to see if it's applicable to a problem I'm trying to solve (one that's probably been solved many times before). I'm having trouble writing a good ...
0
votes
0answers
17 views

Linear System with non zeros count constraint

I trying to solve a simple linear system: $Ax=b$ But with constraints like: $\sum{x_i}=S$, Usually S = 1. $L \le x \le U$, Lower & Upper bounds (usually $0 \le x \le 1$) And "Maximum count of ...
0
votes
1answer
31 views

Prove that optimal solution is an extreme point in LPP.

While proving this I have proved that Optimal solution cannot lie inside the feasible set and that each supporting hyperplane to a set bounded from below (which is the case as in LPP we can always set ...