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

learn more… | top users | synonyms

-1
votes
0answers
11 views

Linear Programming problem

Find values of the variables x1, x2,, and x3 which satisfy x1 + 2x2 + x3 ≤ 16 4x1 + x2 + 3x3 ≤ 30 x1 + 4x2 + 5x3 ≤ 40 so that the minimum value of x1, x2, and x3 is as large as possible. Write this ...
0
votes
1answer
14 views

Turning the program with absolute terms into the linear program

I am studying the linear programming and stuck with the following two problems. I don't have any clues how to convert programs with absolute terms into a linear program. I highly appreciate your help. ...
0
votes
0answers
12 views

Optimising money in bonds

Hi im doing an optimisation problem but dont understand what the terms mean. Suppose someone wants to invest $\$110,000$. They have $4$ choices as to what they invest their money into: $\bullet$ ...
0
votes
0answers
17 views

Formulate a solvable optimization problem

I am trying to solve an optimization problem which could be temporarily formulated as follows, Objective: $\min \quad c_0(1-x_1)x_2x_3(1-x_4) + c_1x_1x_2(1-x_3)x_4 + c_2x_1(1-x_2)x_3(1-x_4)$ ...
0
votes
1answer
42 views

Which optimization class does the following problem falls into (LP, MIP, CP..) and which solver to use

I have the following optimization problem. I want to solve it using a computer solver. But I am not sure which problem class it falls into or which solver to use. Problem: There is a set of objects ...
0
votes
0answers
12 views

splitting a system of ODEs into linear constraints and a smaller system using matrix Null Space

This problem originates from chemistry. Let us assume we want to solve a system of ODEs describing the evolution of the concentrations of the species in a chemical system with n species and k kinetic ...
0
votes
1answer
13 views

Solution of the LP relaxation - always round to the nearest integer?

If an optimal solution to the LP relaxation of an IP is not integer, can we always get a feasible IP solution by rounding it to the nearest integer? Or can we generalize this process by saying, if we ...
0
votes
1answer
20 views

Find the dual of the given primal linear programming problem

The primal problem is as followed: Minimize $z=4x-5y$ Subject to $y\le10-x$, $y\le2+3x$, $x,y\ge0$ Write out its dual and solve it geometrically. ...I have found its dual and graphed out the ...
0
votes
0answers
18 views

Hierarchical Linear Programming

I am stuck with the following problem from research. For each time, $t$, I get a new data point $x_t$ and the current optimum value is a function of $\{x_t:t=1,2,\dots,T\}$ obtained by solving a LP. ...
2
votes
0answers
18 views

Finding number of basic solution based on different cases

I need help understanding the question. Consider the polyhedron P = {x in R^n | Ax = b x => 0}, where A in R^mxn and b in R^m. Assume that any m columns of A are linearly independent. (a) Suppose ...
1
vote
0answers
21 views

Feasible solution with positive $m+1$ components

Can anyone give me a suggestion? Let \begin{equation} \min \hspace{0.3cm} \{c^Tx: \text{ s.t. } Ax = b, x \geq 0 \} \end{equation} Suppose that $x$ is a feasible solution to the previous LP, with ...
1
vote
1answer
22 views

The dual of transporting problem

So basically I'm trying to figure out what does a certain variable in dual of transporting problem mean. Transporting problem in matrix form: (We are searching for a min cost of transferring goods ...
0
votes
0answers
26 views

when will dual optimal solution and primal optimal solution will be equal? [closed]

I don't mean like the optimizing value of the primal and dual what I mean is the individual feasible solutions of primal and dual being equal.An example would be good.
0
votes
0answers
14 views

Linear programming (or possibly nonlinear) formulation

The problem is like this; The construction company is considering erecting three office buildings. The time required to complete each of them and the number of workers required required to be on the ...
-2
votes
1answer
58 views

Linear programming Mathematical modeling [closed]

Bubba and Bubbette had a son eight years ago. In anticipation of the immense college expenses for Bubba Jr., they decided to start an annual investment program on the child's eighth birthday ...
2
votes
1answer
50 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
27 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
43 views

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

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? [closed]

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
25 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
14 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
34 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
18 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

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
30 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
19 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
33 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
23 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
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 ...
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
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
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
27 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
36 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
32 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
137 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
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
27 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
64 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 ...