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

learn more… | top users | synonyms

1
vote
2answers
42 views

Linear Programming with target values.

I'm trying to figure out the general solution to a min-max problem. The general form of the problem is as follows: ...
0
votes
1answer
42 views

Non computational approach to this equation?

I was thinking about the following problem (not homework): Let $a,b,c,d \in {0,1,2,3,4,5,6,7,8,9}$ Find all four digit numbers $abcd$ where the two digit numbers $$ ...
0
votes
0answers
2 views

Direction in Dual Simplex method

In the dual simplex problem, when primal become inconsistent then dual have direction. How can we find this direction using dual simplex algo ?
0
votes
0answers
12 views

Linear Programming, Dual Solution and Slackness [on hold]

I have a test coming up and I can't seem to find a way to solve these questions would anyone have a step by step I can use to try to solve these?
0
votes
0answers
20 views

Constraints linear programming

I have an optimising problem but don't understand what constraint to put here ; Currently the firm has a contract to produce $4$ products. The contract assumes production of $20$ units of product ...
1
vote
0answers
14 views

Sensitivity in perturbing coefficient matrix in a linear program

Consider the linear program: $\min p^Tx $ subject to $\mathcal{A}x = b, x \geq 0.$ Suppose that $x^*$ is the solution with optimal basis $B$. Now suppose we perturb $\mathcal{A}$ slightly to ...
-1
votes
0answers
15 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
20 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$ ...
2
votes
0answers
69 views
+100

Is optimal solution to dual not unique if optimal solution to the primal is degenerate?

If optimal solution to the primal is degenerate, does it necessarily follow that optimal solution to dual not unique? That is, is uniqueness an unnecessary assumption? Spin-off from here. In my ...
0
votes
1answer
45 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
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
3answers
177 views

Is an unit-cube polyhedron? What about other platonic solids?

Definitions According to my linear programming course and screenshot here (Finnish), a polyhedron is such that it can be constrained by a finite amount of inequalities such that $$P=\{\bar x\in ...
3
votes
1answer
10 views

linear programming and flow network

Here is the problem: I have hard time understanding the problem , what does it mean by "conservation factors" and how to approach the problem using linear programming. For what I understand, if a ...
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
23 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
85 views

Proof required for an alternate method in solving a linear programming problem

Suppose that P and Q are two of the corner points of the feasible region lying completely in the first quadrant. In addition, P is located at South-East of Q*. z = 0 (or more specifically, Ax + By = ...
1
vote
2answers
101 views

Linear programming: expressing the fact that precisely $k$ variables are nonzero

Given some variables $x_1,\ldots,x_n$ is it possible to somehow express in a linear program the fact that precisely $k$ of them are non-zero? I suspect this would already be enough to simulate ...
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 ...
4
votes
1answer
353 views

Linear Programming with One Quadratic Equality Constraint

I have a problem which can be formulated as a Linear Programming with One Quadratic Equality Constraint: where variable x is n-dimensional vector and H is a Semi-Positive Definite n-by-n matrix. I ...
2
votes
5answers
330 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 ...
1
vote
1answer
23 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
27 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
59 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 ...
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} + ...
2
votes
1answer
1k views

primal to dual solution conversion ??

i have an optimization problem $$\text{ maximize } z=3x+4y$$ $$\text{ such that: } x+y ≤ 450 \text{ and } 2x+y ≤ 600$$ the optimal solution to this problems comes to be $x=0$; $y=450$; $p=150$ ...
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 ...
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: ...
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 ...
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 ...
0
votes
0answers
35 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: ...
1
vote
1answer
1k views

Linear programming: basic solutions?

http://www.math.toronto.edu/kergin/236_t1_2.pdf For number 3(a), I don't get how "any of the last 4 columns are linearly dependent" and how x1 is the basic variable... I thought only the last 2 ...
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 ...
0
votes
2answers
782 views

Optimal Basic Feasible Solutions

In linear programming, is it true that you can only have at most 2 optimal basic feasible solutions? If so, why?
2
votes
2answers
335 views

Linear Programming: Breaking Variables Product

Given two sets of binary variables $x_{i...N} \in X$ and $y_{i...M} \in Y$ and another binary variable $\alpha$ how can I linearize the following constraint, i.e break the product of variables? ...
0
votes
1answer
958 views

How to describe minimization of L1 norm error using linear programming?

Given a set of $n$ pair points $(x_1, y_1), ..., (x_n, y_n)$ in the plane, I need to find a line $ax + by = c$ that fits the points of the L1 norm error points as closely as possible. I need a linear ...
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 ...
0
votes
1answer
327 views

Formulate model

Carter Enterprises is a soybean trading company. Once a month a representative attends a commodity sale where he either buys or sells soybeans in bulk. Carter uses a local warehouse for storing ...
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 ...
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 + ...
1
vote
2answers
615 views

Removing linear redundant constraints using Gauss Elimination

I have a set of linear constraints in the form of $c_i x \ge d_i$ and I need to identify if an additional constraint is redundant with respect of the previously mentioned set. Here I found a similar ...
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 ...
2
votes
2answers
448 views

Exploring underdetermined linear system with non-negative solution

I haven't had much luck searching for this specific problems. Any pointers would be greatly appreciated. I have an underdetermined system where $ A $ and $ b $ are known. $ x $ is a real vector with ...
-1
votes
0answers
20 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 ...