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

learn more… | top users | synonyms

1
vote
1answer
45 views

Reduction to LP

What will be the primal and dual of the following problem/ Given an undirected graph $G = (V,E)$, we want to assign non-negative weights to all the edges of $G$, denoted $\{ x_e \mid e\in E \}$ , such ...
1
vote
2answers
101 views

Optimal production for factories

A firm produces two different models of heavy machines; say (A) and (B). The market demand implies that the final profit of each model is 1200 and 2500, respectively. The production of each car (of both ...
1
vote
0answers
116 views

Linear Programming Problem About Inventory and Cost Minimizing

http://www.endustri.anadolu.edu.tr/zkamisli/ENM%20203/duyuru/ENM203%20Assignment%202.pdf In that link, you can find my question. I'm having trouble about defining decision variables. The objective ...
0
votes
0answers
51 views

Formulating an optimization problem

I am having difficulty formulating a schedule/pay statement in to an maximization problem. Problem: If you are AT work for ${\leq }40$ hours/week your pay/hour is $r$, if $>40$ your pay/hour is ...
1
vote
0answers
16 views

Equivalent System of equations

Let system $$\left\{ \begin{array}{l} {A_1}X = {b_1}\\ a_1^TX = {b_2} \end{array} \right.$$ where the last constraint is dependent to others. Prove that if this system be a feasible system then it is ...
2
votes
0answers
40 views

Calculating second derivative of $g(\alpha) = f(\textbf{y}(\alpha))$

I'm having problems with the second derivative of the function $g(\alpha) = f(\textbf{y}(\alpha))$ (which I will define more precisely below). I tried calculating it myself, could anyone just simply ...
1
vote
2answers
26 views

Linear program dual

We are trying to find the dual of the following linear program. $$ \max_x \ 2x_1 \ + x_2 \ \ \ \ -- (1) $$ such that, $$ x_1 + x_2 \leq 2 \ \ \ \ -- (2)\\ -x_1 - x_2 \leq -4 \ \ \ ...
1
vote
2answers
66 views

Duals of Linear Programs

We are trying to find the dual of the following linear program. $$ \max_x \ ax_1 \ + x_2 $$ such that: $$ v_1x_1 - v_2x_2 \geq b_1 \\ v_1x_1 - v_2x_2 \geq b_2 \\ x_1 \geq 0 \\ x_2 \geq 0$$ ...
1
vote
1answer
4k 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$ ...
1
vote
0answers
58 views

Linear Programming- are my equations correct?

A dairy produces cheese, milk, sour cream, and yogurt. Suppose: Every 100 lbs of cheese requires 2 units of plant capacity, 3 workers, and 7 gallons of culturing additive, and gives $1,500 in ...
1
vote
0answers
34 views

Is the coefficient uniquely determined by the sign function?

Suppose $a\in R^p$, $b\in R^p$, and $||a||=||b||=1$, is it true that if $sign(a'x)=sign(b'x)$ for any $x\in R^p$, then $a=b$, where $sign(t)=1$ if $t\geq 0$ and $sign(t)=-1$ if $t<0$?
1
vote
0answers
51 views

How to solve linear system of equations in 1 and inf-norm?

I have the problem to find a linear program that is equivalent to solving the problem that finds a minimum for $||Ax-b||_1$ and $||Ax-b||_{\infty}$. We defined a linear program as follows: $min_{x} ...
0
votes
1answer
138 views

Maximize two-variable linear function

How would you maximize the following function (with integer domain) $$f(x,y) = a * x + b * y$$ subject to $$c * x + d * y \leq N$$ $$x \geq 0, y \geq 0$$ the constants $a, b, c, d, N$ are known ...
1
vote
1answer
51 views

Having trouble understanding this proposition from my textbook.

I'm seeing this perplexing proposition in my optimization textbook: Suppose an LP $$\max\{z(x)=\vec{c}^{T}x+\bar{z}:A\vec{x}=\vec{b},\vec{x}\geq\vec{0}\}$$ and a basis $B$ of $A$ are given. Then, ...
1
vote
1answer
482 views

travelling salesman understanding constraints

I am trying to program TSP problem in R. From wikipedia page section "Integer linear programming formulation", I was able to understand all the constraints except the last one. Need help to ...
0
votes
0answers
52 views

travelling salesman [duplicate]

I am trying to program TSP problem in R. From wikipedia page section "Integer linear programming formulation", I was able to understand all the constraints except the last one. Need help to ...
1
vote
1answer
43 views

Proving certificate of inequality

I have a question about proving the certificate of inequality in the given question: If there exists $y$ such that $y^T A \leq 0$ and $y^T b < 0$, then $Ax = b$, $x \leq$ 0 has no solution. I ...
0
votes
1answer
55 views

Inequality Constrained Optimization Problem

I am working on the question displayed below. I am not sure if I understand it correctly and I am looking for some input. So, I am asked Why is $x^*$ a local maximum for $f$ subject to the set ...
1
vote
0answers
38 views

On solving non-linear programming problem and the relevant software

I have a non-linear programming problem, in which all the inequality is linear and only the optimization goal is in a non-linear form. The problem is as following. $x_j$ is the variables and $a_{k,j}$ ...
1
vote
1answer
729 views

Number of subtrees of a tree

Define a subtree to be any connected subgraph of a tree. Prove that the number of subtrees of a complete binary tree is not polynomial in the number of nodes. Give an example of a class of trees ...
1
vote
0answers
208 views

Strange but practical Bin packing problem

I am trying to solve the following MILP through LP solve. A link for the original problem is here I am re-iterating the problem as follows: I am trying to write an application that generates drawing ...
3
votes
0answers
203 views

The size of the maximum matching is bounded by the size of the minimum vertex cover

Prove, using the weak duality theorem of linear programming, that: For any graph $G$ (not necessarily bipartite), the size of the maximum matching is at most the size of the minimum vertex ...
0
votes
1answer
223 views

Linear Programming - Overtime restriction

hopefully I can get some help on this problem, it's got me quite stumped. I was given a linear programming problem with the goal of minimizing labor costs. The variables x_t represent the number of ...
1
vote
1answer
266 views

Binary constraint integer programming problem

Hi I have a question to the folowing question: Explain how to use integer variables and linear inequality constraints to ensure: A) let x and y be integer variables bounded at 1000. How can you ...
2
votes
1answer
53 views

Whether a feasible set is empty?

Given $a\in \mathbb{R}^N$ with at least one positive entry, and a positive definite $N\times N$ matrix $A$, I would like to prove the following set is non-empty: $$S=\{ x\in \mathbb{R}^N : x\geq 0, ...
1
vote
1answer
328 views

Business Linear Programming Question

Now I don't need you guys to do my homework for me; however, I am a little stumped Xara Stores in Canada imports the designer-inspired clothes it sells from suppliers in China and Brazil. Xara ...
1
vote
0answers
122 views

problem related to duality theorem in linear programming

Please help me to prove the above variant of the duality theorem. I am a masters student and linear programming is new to me. This question is a part of my assignment. I was not able to prove it.
0
votes
1answer
47 views

Conditions for a system to be solvable.

I have the following system of equations: $$\begin{aligned} \left\{\begin{array}{l} a+dz+cy+exy = 0\\ 10a+3bx-exy =0\\ -5a-dz = 0 \end{array}\right. \end{aligned}~~.$$ I would like to solve for ...
0
votes
1answer
29 views

have value of variable take on whether two other variables equal?

I'm having a hard time expressing something in a linear program I am writing. I have two variables a and b. I want the ...
1
vote
0answers
92 views

Area of a 2D convex polytope made of halfspaces

For a computer program I am attempting to solve the area of a convex polytope defined by a finite number of halfspaces. I understand that this forms a polygon and given the vertices of a polygon I am ...
1
vote
1answer
2k views

Linear Programming Inventory Problem

I'm still trying to get used to the nature of these problems and I'd appreciate some further explanation. ...
4
votes
1answer
2k views

Linear Programming: Three variable graphical solution

A small bank offers three type of loans: housing loans at $8.50$% interest, education loans at $13.75$% interest rates, and loans to senior citizens at $12.25$% interest. Further, it needs to ...
3
votes
2answers
1k views

Financial Linear Programming Problem

I'm very new at linear programming and I'm trying to figure out a way to approach this problem below: ...
1
vote
0answers
806 views

Graphically solving a Linear Programming Problem?

I was given the following linear programming problem and have been asked to find all optimal solutions graphically. I am quite new to the subject, so please forgive my naivety. ...
0
votes
1answer
109 views

Intersection of Cartesian product and set - what is the meaning?

I came across the following two definitions in a book about Integer Programming: Definition 1.1 A subset of $R^n$ described by a finite set of linear constraints $P=\{x \in R^n: Ax \leq b \}$ is a ...
0
votes
2answers
157 views

How can I find the center of a region in a linear programming problem?

I have an optimization problem that in most respects can be very elegantly expressed via linear programming. The twist is that I don't actually want to minimize or maximize any of my variables; I ...
1
vote
1answer
68 views

Containment of one convex hull in another

This question is related my previous question (Comparing two probability distributions) which are both related to my current research. Suppose we have two bounded convex hulls in $\mathbb{R}^n$ ...
2
votes
0answers
301 views

Comparing two probability distributions

In my research I have to find two discrete probability distributions by solving two separate linear programs. The domain of optimization is the probability space of $m^n$ atomic events, where $n$ is ...
1
vote
0answers
48 views

Least square with constraints

I want to solve the least squares problem $(Ax-b)^2$ with no intercept term for linear regression with the constraint that the sum of the params/weights is equal to 1. I am trying to get the closed ...
1
vote
4answers
333 views

What does $Ax\geq b$ mean in Linear Algebra?

I'm going through Farka's Lemma. I can understand what $Ax = b$ from a linear algebra perspective. But, I'm unable to understand what $Ax\geq b$?
1
vote
0answers
79 views

Speeding up solution of a binary integer program

To solve the problem of making a "good" schedule for a tournament between N teams, using memories from my (long gone) student days, I expressed it as a binary integer program. With the current set of ...
4
votes
2answers
190 views

Help with formulating a linear programming problem

I have the following linear programming problem I would like to be verified: I have sketched the problem in the following picture: Here is my attempted solution: I figured that I have ten ...
0
votes
1answer
321 views

Variations of the transportation problem in linear programming

The transportation problem is a famous problem in linear programming. For instance, http://www.utdallas.edu/~scniu/OPRE-6201/documents/TP1-Formulation.pdf or http://www.math.ucla.edu/~tom/LP.pdf ...
0
votes
2answers
242 views

Calculation of volume and centre of mass of an arbitrary polyhedron

Hi I am developing a thesis that will calculate the volume and center of mass of an arbitrary block of rock. 1- The calculation starts with triple volume integrals. The formulas are transformed to ...
1
vote
1answer
182 views

Formulating a linear programming problem

I have the following problem: Now I would like someone to verify whether my answer is correct or not :) Here goes: If I denote the different alloys by $x_1, x_2, x_3, x_4, x_5$ I get ...
1
vote
1answer
2k views

Converting linear programming problems into standard form

I have the following linear programming problem: Convert the following problems to standard form: $$\begin{align} \text{a)}&\text{minimize}&x+2y+3z\\ & \text{subject ...
3
votes
0answers
59 views

On the bounds of the objective function in a standard LP

Consider a standard linear programming (LP) such as: \begin{align} \sum_{i=1}^{N}\frac{a_{i}}{b_{i}}x_{i}\end{align} \begin{align}\text{s.t. }\left ( \sum_{i=1}^{N}x_{i}=1 \; , \; ...
0
votes
2answers
60 views

How is it possible to use normals in the definition of a linear programming constraint?

I'm trying to calculate the center of a feasible region in a system of linear inequalities using linear programming techniques. After a bit of research, it looked like defining the center as a ...
2
votes
5answers
352 views

Compressive sensing with non square matrices

I'm implementing the algorithm in the following paper: "Compressive sensing for wideband cognitive radios" http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=04218361 However I've run into a ...
0
votes
2answers
650 views

Help with proof: Hyperplane is an $(n-1)$-dimensional linear variety

I'm reading linear programming and I bumped into the following: I'm having trouble getting grasp on the proof of proposition 2. Could someone perhaps explain it to me in other terms? For some ...