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

learn more… | top users | synonyms

1
vote
1answer
22 views

On/off variables in MILPs with infinite bounds

I have an LP defined by $$A x = b$$ $$0 \leq x \leq U$$ and would like to extend it to an MILP through introduction of binary on/off variables $z$ such that $$z_i = 0 \implies x_i = 0.$$ This ...
0
votes
0answers
22 views

Solution of a general linear system of equations: 4-term n-equations

I have the following system of equations.... $$y_1 = c_{11} \cdot x_{11} + c_{12} \cdot x_{12} + c_{13} \cdot x_{13} + c_{14} \cdot x_{14}$$ $$y_2 = c_{21} \cdot x_{21} + c_{22} \cdot x_{22} + ...
-4
votes
0answers
38 views

Positive solutions to $A^T A x \geq 0$ [on hold]

Find a positive solution $x$ to the linear inequality $A^T A x \geq 0$. $A$ is an arbitrary matrix. I was wondering if there is a general solution. EDIT: One special solution is when $A^TA$ is row ...
-2
votes
1answer
26 views

What would be the basic solution of this maximization problem? [on hold]

Maximize $P=40x_1+50x_2$ Subject to $x_1+6x_2 \leq 72$ $x_1+3x_2 \leq45$ $x_1, x_2 \geq0$
0
votes
1answer
20 views

An LP problem from David G. Luenberger's Linear and Nonlinear Programming book

Could someone help me to solve the following problem? A class of piecewise linear functions can be represented as $f(x) = Maximum (c_{1}^Tx+ d_{1}, c_{2}^Tx, \cdots, c_{p}^Tx + d_{p})$. For such a ...
0
votes
1answer
9 views

Revised Simplex Method w/o Identity Matrix

For a homework problem we're forced into using revised simplex, but I cannot seem to even get past the first step. My biggest problem is: ...
0
votes
0answers
32 views

Maximum of $x_1 - x_2 - x_3 + x_4 - 2x_5$ with some constraints

I have to find maximum of $x_1 - x_2 - x_3 + x_4 - 2x_5$ with constraints: $-x_1 +x_2 + x_3 = 2$ $x_1 + 2x_2 + x_4 = 10$ $x_1 - x_2 + x_5 = 4$ of course $x_i \ge 0$. From constrains I have: ...
0
votes
0answers
16 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 ...
0
votes
0answers
20 views

Is there any other way to model Seven Bridge of Königsberg? [on hold]

Can we Model and solve Königsberg problem or similar problem using mathematical Programming? if the answer is yes How to write the mathematical programming model for this problem?
-1
votes
0answers
14 views

new staff training planning [closed]

An airline must decide how many new flight attendants to hire and train over the next six months. The staff requirements in person-flight-hours are respectively 8000, 9000, 7000, 10,000, 9000, and ...
1
vote
1answer
31 views

checking optimality using complementary slackness

I am trying to see if [3,-1,0,2] is an optimal solution to the following LP using complementary slackness: maximize $6x_1 + x_2 -x_3 - x_4 $ s.t. $x_1 + 2x_2 + x_3 + x_4 \leq 5 $ $3x_1 + x_2 -x_3 ...
1
vote
1answer
30 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 ...
1
vote
1answer
29 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 ...
-1
votes
0answers
15 views

Find original linear programming problem given the final optimal tableau

Please could someone explain to me the steps i need to take to find the original linear programming problem given the final optimal tableau? My notes are terrible for this and I can't find anything ...
0
votes
1answer
27 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 ...
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. ...
2
votes
0answers
32 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 ...
1
vote
1answer
32 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 = ...
4
votes
0answers
20 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
1answer
25 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 ...
0
votes
0answers
9 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
18 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
23 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 ...
0
votes
0answers
22 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
26 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 ...
-2
votes
1answer
35 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
1answer
56 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
1answer
35 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
31 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
136 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
49 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
votes
0answers
29 views

Linear Programming - Finding the objective function

So I have this problem and I can't find the answer, only about half of it.. They give a graphic of the feasable region, with important points: $A(0,5), B(1,3), C(3,1)$ and $D(7,0).$ The point of ...
1
vote
1answer
54 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
25 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
63 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
16 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 ...
1
vote
0answers
21 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 ...
0
votes
1answer
53 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 ...
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
52 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 ...
2
votes
1answer
27 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
27 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
17 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 ?
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
17 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 ...