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

learn more… | top users | synonyms

0
votes
0answers
6 views

Single factor model question, related to the benefits of diversifying one's portfolio.

The question: Suppose in a single period investment problem we may divide our wealth between n assets and that the return on the ith security is given by $r_i = \alpha + \beta_i\theta + \epsilon_i,$ ...
0
votes
1answer
10 views

Linear programming with equality constraints

I want to find a solution to the minimisation problem $$ \text{min } c^Tx \qquad \text{subject to } Ax=b $$ I have implemented the parametric self-dual simplex by R. Vanderbei in Matlab and it works ...
0
votes
0answers
4 views

Determine the cone and the conical shell of sets

I have two sets: $$a) \{x \in\ \mathbb R^2 : x_1 > 0 , x_2 = 1\}$$ $$b) \{x \in\ \mathbb R^2 : (x_1 \geq 0 \mbox{ and } x_2 \geq 0) \mbox{ or } (x_1 \leq 0 \mbox{ and }x_2 \leq 0)\}$$ The Cone ...
0
votes
3answers
31 views

Check whether $x_1 + x_2 \leq 3$ is a convex set or not? [on hold]

How do I check and prove that the following set is a convex set or not? $S$ = { $(x_1,x_2)$ : $x_1 + x_2 \leq 3, x_1 \geq 0, x_2 \geq 0 $}
0
votes
0answers
16 views

Solving (one variable) Linear Equation by Dividing Slope by Constants Accumulation? [on hold]

I've been Google searching for this, and apparently my Googlefu is not strong today, or I'm doing something wrong. I have been told that it is possible to solve a one variable linear equation by first ...
1
vote
2answers
36 views

Effect on Minimizer of Tightening Constraints

The Statement of the Problem: Consider the minimization problem $f(x,y)=14x+20y$ under the constraints $x+2y \ge 4 $, $7x+6y \ge 20$, and $x,y \ge 0$. Don't use the simplex method! (i) Draw the ...
1
vote
0answers
15 views

Question about LP Model

I have a aggregate production planning problem. As the company want to have a stable output, the quantities produced per month should (x) not fluctuate to heavily from a specified amount, say g. So ...
1
vote
1answer
27 views

Showing $T:K^n \to K^{n-1}$ is surjective

Hi everyone, I'm a bit stuck on this question. Could anyone share some ideas? Note: $K$ is the field I believe from the definition of the $ker(T)$ we can tell $n = 3$, but I am unsure as to how ...
0
votes
0answers
21 views

simplex algorithm - minimization

So I get the basic concept of simplex algorithm but I am working on a project where I have to implement any linear programming algorithm (I chose simplex method) to minimize a function, but I don't ...
0
votes
1answer
33 views

Rotation Matrix with (Cos(theta) = 0,Sin(theta) = 1) as Identity

In my program, all rotations are handled with unit-vector orientations: $$[x,y] = [\cos{\theta}, \sin{\theta}]$$ In the game engine I'm using for visualization (Unity3D), the $Y$ axis is forwards - ...
0
votes
1answer
32 views

How do you avoid cycling in a linear programming problem?

When running the simplex method on a linear programming problem that cycles The only thing I can think of to avoid cycling is to stop running it when the same dictionary appears twice? however i'm not ...
0
votes
1answer
30 views

meaning of Farkas' Lemma

Quoting from Jorge Nocedal's Numerical Optimization second edition, page 326 bottom to page 327, Farkas' Lemma Let the cone K be defined as in (12.45). Given any vector $g \in \mathbb{R}^n$, we ...
0
votes
0answers
11 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
1answer
48 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
14 views

Linear Programming, Dual Solution and Slackness [closed]

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?
2
votes
3answers
55 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
0answers
22 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
21 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
21 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
13 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
19 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
47 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
14 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
16 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
19 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
24 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
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
61 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
51 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} + ...
0
votes
1answer
26 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
16 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
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: ...
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
32 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
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 ...
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
25 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, }\\ ...