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

learn more… | top users | synonyms

0
votes
0answers
21 views

Lp Problem Of Production Of a company over quarters

ArkTec assembles PC computers for private clients.The orders for the next four quarters are 400, 700, 500, and 200, respectively. ArkTec has the option to produce more than is demanded for the ...
1
vote
1answer
33 views

linear programming 'increasing profit'

Consider, $$\max 1.000.000x_1 + 2.500.000x_2 $$ \begin{align} s.t. x_1 + 2x_2 \le 7 \\ x_1 + 3x_2 \le 10 \\ -3x_1 + x_2 \le 0 \\ x_1, x_2 \ge 0\end{align} which is an LP-problem on a company's wishes ...
0
votes
1answer
28 views

lagrange method, linear constraints and unique global maximum

My book in linear programming states two things that I do not understand. We are working with the lagrange method with linear constraints.: From multivariate calculus we have that at a critical ...
1
vote
1answer
37 views

Recovering the optimal primal solution from dual solution

I'm having trouble finding the optimal primal solution of a particular problem from its dual solution. Primal: $\texttt{Maximize} \ \ 10 x_1 + 24 x_2 + 20 x_3 + 20 x_4 + 25 x_5$ Subject to $x_1 + ...
0
votes
0answers
16 views

cut/fill triangle volume to a plane as a linear approximation

I need an approximate solution for a linear programming problem. Assume you have a triangle defined by the three points (x1,y1,z1) (x2,y2,z2) and (x3,y3,z3). The volume to the zero height plane is ...
0
votes
0answers
28 views

Radio factory linear program

I need a help with this exercise. I’m supposed to write a liner program for the problem below and then solve it using simplex method, but I’ don’t know how to include all the factors into variables. ...
0
votes
1answer
26 views

How to write this to a linear programming problem?

A procedure of animal feed makes two food products: F1 and F2. The products contain three major ingredients: M1, M2, and M3. Each ton of F1 requires 200 pounds of M1, 100 pounds of M2, and 100 pounds ...
1
vote
1answer
57 views

Representation of a point in terms of extreme points and extreme directions in a LP feasible region

We know that every point in a feasible region (X) of a Linear Program can be represented as a convex combination of the extreme points of X plus a non-negative combination of the extreme directions of ...
1
vote
1answer
22 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
2answers
65 views

How to find on each face of a polyhedron one point?

We have a polyhedron in $\mathbb R^n$ generated by the intersection of a collection of finete hyperplanes or the convex hull of the set of vertices. My question is: Is there any algorithm for ...
2
votes
0answers
34 views

Nearest non-negative solution for $Av=b$

Let $A$ be a $n\times m$ matrix. Let us define the system $$Av=b$$ $$v\geq 0$$ I want to find a solution $v$ of this system that is the closest (euclidean norm) to $v_0$, a given $n$-dimensional ...
4
votes
4answers
6k views

Converting absolute value program into linear program

I have the generic optimization problem: $$ \max c^T|x|$$ $$ \text{s.t. } Ax \le b $$ $x$ is unrestricted How do I convert it into a linear programming problem? Online I read something about ...
1
vote
1answer
41 views

primal to dual conversion problem

primal problem is: $$\min z = 4x_1-3x_2+5x_3$$ $$7x_1+6x_2+24x_3\le16$$ $$2x_1+5z_2+3x_3\le10$$ $$x_i\ge0$$ the optimal solution is: $(0,2,0), z = -6$ The dual problem is : $$ \max g = ...
-1
votes
2answers
344 views

Linear Programming Problem?

You are about to take a test that contains computation problems worth 6 points each and word problems worth 10 points each. You can do a computation problem in 2 minutes and a word problem in 4 ...
4
votes
0answers
26 views

Parameterizing equilateral polygons

I'm not exactly sure how to describe what I want, so if I butcher terms, please forgive me :) I want to "parameterize" the space of simple irregular equilateral polygons with n sides, or at least a ...
0
votes
0answers
10 views

Linear Programming Duality with Big M

I wanted to check of my proof for the following is correct. I am least sure of step 3. Given a linear program $LP1$. $$\text{minimize}\left\{\sum_{i\in I}c_iy_i\right\}\\ \text{subject to, }\\ ...
0
votes
1answer
20 views

Question about problem linear programming math modeling

Consider points $A(4.7,−4.1,−1.5)$,$B(−0.4,−2.4,1.9)$,$C(−0.3,−2.1,−6.5)$ and $D(2.7,−3.6,4.0)$. How to discover if segment $AB$ has intersection different of zero with the segment $CD$? Formulate ...
0
votes
0answers
27 views

Mixed strategies as LP problem

A row player is playing against a column player and his yield table is -, C1, C2, C3 R1, -3, 2, -1 R2, 0, -2, 1 R3, -1, 3, -5 Is it then correct to ...
-2
votes
1answer
38 views

Modelling Problem in Linear Programming Standard Form

I'm having a hard time setting this up, so that's what I need help with. The solving I understand. We’re making a drink with the following requirements: at least 500 calories, at least 20 mg. of ...
0
votes
0answers
23 views

How do I convert this to a linear programming problem?

It takes a tailoring 2 hours of cutting and 4 hours of sewing to make a knit suit. To make a worsted suit, it takes 4 hours of cutting and 2 hours of sewing. At most 20 hours per day are available for ...
0
votes
1answer
29 views

How do I convert this into a linear programming problem?

A farmer is planning to raise wheat and barley. Each acre of wheat yields a profit of \$50 and each acre of barley yields a profit of \$70. To sow the crop, two machines, a tractor and tiller, are ...
0
votes
1answer
57 views

convertion into integer linear program

I am trying to model the Ising spin state problem into Integer linear program and find the optimal ground state using lp_solve. (This is just a miniature version of Ising state problem) $$ maximise: ...
2
votes
2answers
85 views

When change making problem has an optimal greedy solution?

A well-known Change-making problem, which asks how can a given amount of money be made with the least number of coins of given denominations for some sets of coins (50c, 25c, 10c, 5c, 1c) will ...
2
votes
1answer
36 views

How to remove fields from sudoku puzzle in such way to assure there's still only 1 solution?

I'm trying to create a Sudoku puzzle (programatically, if that matters). Here's how I do it. STEP 1: Creating an initial set, with unique solution: 123456789 456789123 789123456 ...etc... STEP 2: ...
0
votes
0answers
23 views

finding the dual

I am supposed to find the dual of max $c^Tx$ subject to $a \le Ax \le b$ $l \le x \le u$. In order to find the dual I think I have to write it in standard form, the standard form is: max $Ax'$ ...
1
vote
0answers
41 views

Tucker's theorem from Farkas lemma

I am trying to understand the proof of Tucker's theorem using Farkas lemma but there are some points that are not clear to me. The proof I am following is in this paper at page 16. What I do not ...
3
votes
1answer
141 views

Can I know all the elements of a matrix given that I know its sum along one dimension and the fact that it is axisymmetric?

For this discussion I will assume a 9x9 matrix but my question is for a general nxn matrix. I have a matrix which is not only symmetric along the vertical and the horizontal axis, but is axisymmetric ...
2
votes
2answers
54 views

How to maximize the sum of vectors in target direction.

Given a number of vectors, and an unknown variable for each vector, say for example: $v_1, v_2, v_3,\dots,v_n$ and $x_1, x_2, x_3,\dots,x_n$ and a target vector $v_t$ I am trying to create an ...
1
vote
1answer
55 views

Can you generate math problems that are solveable?

If you take Linear Programming, it problems are formulated like this: You know that Cabinet X costs 10 cents per unit, requires 6 square feet of floor space, and holds 8 cubic feet of files. ...
1
vote
2answers
30 views

Linear equations - how to find the solution over the boolean field closest to zero

I want to solve a system of linear equations over the field of $F_2$, in a way such that the solution vector is as close to the zero vector as possible. For example, suppose I have a system of ...
3
votes
2answers
69 views

In a linear program, how to add a conditional bound to x?

I am working with a standard linear program: $$\text{min}\:\:f'x$$ $$s.t.\:\:Ax = b$$ $$x ≥ 0$$ Goal: I want to enforce all nonzero solutions $x_i\in$ x to be greater than or equal to a certain ...
0
votes
0answers
22 views

Simplex method: tableau at some stage, finding objective row

How do I find the objective row for the tableau if all I am given is the tableau values at the certain stage (without RHS)? Here is the tableau $T$ without the objective row: $$ \begin{bmatrix} 0 ...
1
vote
1answer
29 views

Simplex updates for the inequality LP

Consider the task of minimizing $c^Tx$ subject to the constraint that $Ax \leq b$. I had a couple of questions in relation to the simplex algorithm (applied to this problem): How does one ...
0
votes
1answer
61 views

Explicit solution for a linear program with two constraints

This is not a homework problem, although it wouldn't surprise me if it happens to exist in a textbook somewhere. Is there an explicit solution for the linear program $$\max_x c^Tx ~~ s.t. \\ d^Tx = q ...
1
vote
0answers
22 views

Find the vertices of the polygon given by $|f_1(x,y)|+…+|f_n(x,y)| \le C$

Given functions $f_1(x,y),...,f_n(x,y)$, we know that the locus of points $(x,y)$ satisfying $|f_1(x,y)|+...+|f_n(x,y)| \le C$ for some real constants $C$ is the interior of a polygon. How do I find ...
2
votes
2answers
25 views

Formulation of Linear Programming problem?

I want to maximise the function: $$l(\beta,\sigma,\alpha) = -n\log(\sigma) - \frac{1}{\sigma} A(\alpha)\vert{\bf y}-{\bf X}\beta\vert,$$ where $\vert \cdot \vert $ represents the entry-wise absolute ...
1
vote
0answers
54 views

How to solve this using computer.?

Given $B = \begin{pmatrix} 0.3 & 0 \\ 0 & 0.4 \\ \end{pmatrix}$, and $\pi = \begin{pmatrix}0.4\\0.6\end{pmatrix} $, I need to find the elements of the stochastic matrix (the rows sum to ...
0
votes
1answer
34 views

Robust LP question using box uncertainty model

I am trying to solve this robust LP problem by writing it as a QP $$\min_x x^TSx : \mu \leq r^T x , Ax \leq b$$ Under Box uncertainty model: $$R = \{r : \| r - \hat{r}\|_\infty \leq \rho\}$$ Here ...
2
votes
1answer
29 views

Simplex Method: simplifying constraints

In my Computer Science class we've been exploring the Simplex Method and the applications it has with discovering optimal solutions. I've loved the challenge how much easier it makes finding solutions ...
1
vote
1answer
22 views

Changing a linear map such that given properties are satisfied

We are given $\{v_1, \dots, v_s\} \subseteq \mathbb{R}^n$, all with the same euclidean norm, say $\|v_i\| = \sqrt{(v_i^{(1)})^2 + \dots + (v_i^{(n)})^2} = 1$. Let's also assume $v_i \notin ...
0
votes
1answer
17 views

Optimalization, plan comparision

Let's say there are two tariff plan options of a provider offering internet access and landline telephony. Option 1: DSL flatrate, landline flatrate : 29,95 \$ Option 2: DSL flatrate: 24,95 \$ , ...
0
votes
0answers
29 views

Transforming into a convex program

$\max c^Tx$ $s.t. xy = a, \quad x \le b, \quad L \le y \le H$ Is there a way to transform this problem into a convex problem? $a,b,L,H$ are constants. $x,y$ are optimization variables.
1
vote
0answers
19 views

Dantzig-Wolfe Decomposition

While reading revised simplex method, I came to know about Datnzig-Wolfe Decompostion. Can you please explain whats the connection here ?
1
vote
1answer
32 views

Linear optimization problem with additional constant cost for non-zero variables

I have a linear optimization problem with integer variables of the form minimize $a_1 x_1 + ... + a_n x_n$ under a set of constraints Bounds for each variable $a_i \le constant_i$ Bounds for ...
3
votes
4answers
772 views

Finding the minimal cost edge cover for a bipartite graph

I have got two sets of elements and a pruned graph of bipartite edges with weights assigned to each edge. I need to find the minimal set of edged with the minimum cost covering all nodes from both ...
0
votes
0answers
28 views

Linear Programming $\boldsymbol{c}^T \boldsymbol{x}$ s.t. $\boldsymbol{Ax} = \boldsymbol{b}$

Prove for the linear programming \begin{equation} \left\{ \begin{array}{cc} min & \boldsymbol{c}^T \boldsymbol{x} \\ s.t. & \boldsymbol{Ax} = \boldsymbol{b} \end{array} \right. ...
1
vote
0answers
22 views

Linear program of 0-1 knapsack problem and proof of integer

I have some questions about the knapsack problem. How can the 0-1 knapsack problem described as a linear program? How to proof that the solution of the 0-1 knapsack problem are integer? (I'm ...
0
votes
2answers
881 views

Minimize LPP using graphical method [ operational research ]

Question: Minimize z = 2x + 6y Subject to 2x + y >= 2; 3x + 4y <= 12 x,y >=0 Is min z = 2 the right answer ? if not how do i solve this ?
0
votes
0answers
35 views

how to solve a simplex with n variables

I don't know how to resolve a simplex with n variables I have this primal problem \begin{cases} \text{min}& z=-x_1 - x_2 -... - x_n\\ &a_1x_1 + a_2x_2 +... + a_nx_n \le 1\\ &x_1... ...
0
votes
0answers
27 views

Feasible set for linear system with linear constraints

I have a linear underdetermined system $Ax = b$ with constraints $0 \le x \le 1$. Matrix $A \in \mathbf{R}^{n \times m}$ with $n < m$, elements of which are either $0$ or $1$, and sum of each ...