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

learn more… | top users | synonyms

0
votes
0answers
37 views

Solving constrained linear programming problem

For the variable $t$, problem is to find best multipliers $k$ which minimizes the objective function. Time: $t_1$, $t_2$, $t_3$,... given in input Multiplier $k_1$, $k_2$, $k_3$,... (These are ...
2
votes
1answer
57 views

Knight movement on chess field

I had this task in programming competition: There are two knights, which are $(p_1,q_1)$ and $(p_2, q_2)$. $(p,q)$ knight is figure, with p(q)-length first step, and q(p)-length second step in ...
-1
votes
1answer
18 views

Inversion of a matrix in a system of linear inequalities

I would like to know if someone knows sufficient conditions on $A\in\mathbb{R}^{n\times n}$ and $b\in\mathbb{R}^{n}$ such that for all $x\in\mathbb{R}^{n}$: $$Ax\leq b \Rightarrow x\leq A^{-1}b \text{ ...
2
votes
3answers
45 views

Least Squares method and Octave/Matlab [on hold]

I'll try to be as clear as possible so that you understand what I'm trying to do and can help me I have twelve pairs of data $(x_1,y_1),....,(x_{12},y_{12})$ and from this data we established a model ...
0
votes
0answers
30 views

Necessary condition for existence of a positive solution of a linear system

I would like to know what are the necessary conditions of existence of a positive (componentwise) solution of the system : Ax=b, with A a square ...
1
vote
1answer
17 views

goal programming, mixed-integer program, optimal compromise goals, statistics

QUESTION Can someone help me figuring out how to calculate this question? In this question, I have 4 variables (I think it would be more easily to calculate), and 5 goals. SO for the 27 boxes, I ...
0
votes
0answers
8 views

Lemke Howson Algorithm Tableau

I am working on an implementation of Lemke Howson Algorithm and I am reading this paper below. http://cnl.gmu.edu/TAVRI/research/LemkeHowson.pdf Can someone please explain why on page 7 they say ...
0
votes
0answers
13 views

How to linearize this constraint?

I have a MILP model but one of my constraints is nonlinear and I need to convert it to some linear constraints. Assume that the constraint is like this: U-X*F=0 and U,X,and F are variables and I have ...
-1
votes
1answer
19 views

Maximum Profit with limited resources. [on hold]

A farmer has 10km2 of land in which he can sow either wheat or barley. The farmer has only 10kg fertilizer and 5kg insecticide. Per square kilometers wheat requires 2kg fertilizer and 2kg insectiside ...
0
votes
1answer
51 views

Algorithms For Large-Scale $\ell_{\infty}$ Minimization

The general problem I want to solve is well studied: $$ \min_x \Vert Ax\Vert_\infty \;\;\; \mathrm{s.t.} \;\;\; Bx=c, $$ which is equivalent to the following linear program: $$ \min_{t,x} \, t ...
0
votes
0answers
15 views

Help required in solving the lagrangian dual?

I'm trying to write the Lagrangian dual to the following problem \begin{align*} (P) \quad \min\;&\text{Trace}(CG)\\ \text{s.t.}\;&G \succcurlyeq 0\\ & G_{i,i}=I_d (i=1,..,M+1)\end{align*} ...
0
votes
0answers
28 views

Simplex/Big-M/Dual Simplex methods

I just want to know when to use which method. This is my current understanding, please say if I am incorrect: If all constraint equations can be turned into s.t. the RHSs of all are positive and all ...
0
votes
0answers
29 views

Range of feasibility, feasibility interval, allowable increase and allowable decrease.

Can someone please explain how the values (allowable decrease, allowable increase, for constraints) within the blue box (under "Range of Feasibility") are determined? I understand how they determined ...
0
votes
0answers
22 views

code in R program [closed]

I have some question about code in R program. When we want to find 1+2+3+4+5, we use x <- c(1,2,3,4,5) then sum <- sum(x). How I can write the code to compute 1*2*3*4*5 in R? Thanks.
1
vote
1answer
23 views

Interpretation or definition of “shadow prices”

I do understand that shadow price associated to a resource is the marginal profit you would get if you buy one more unit of that resource. I also know that it is the minimum profit you would accept to ...
0
votes
1answer
20 views

How to formulate constraints given the following information

The following question was given in one of my class but none of us got the use of the market requirements in the problem: A form produces and sells three products namely Product1, Product2 and ...
1
vote
1answer
35 views

Limmiting solution of $Ax=b$ to positive quantities

My personal trainer put me on a diet recently which has had me tracking the macro-nutrients that I eat i.e. protein, carbohydrates and fat. I am supposed to eat a specific amount each meal and eat ...
0
votes
1answer
14 views

Linear programming: Condition on index variable

Let $i \in \{1,2,...n\}$. And let $X_i \in \{0,1\}$. I need to write the condition: if all $X_i$ where $i$ is even index take the value 1, then there need to be at least three $X_i$ with value $0$ ...
1
vote
0answers
17 views

Proving vectors as a basis in $E^{m}$

Show that if the vectors $a_{1}$, $a_2$, $\cdots$, $a_m$, are a basis in $E^{m}$, the vectors $a_{1}$, $a_2$, $\cdots$, $a_{p-1}$, $a_{q}, a_{p+1}, \cdots,a_{m}$, also are a basis if and only if ...
3
votes
2answers
45 views

Proving UNIT INTERSECTION NP-complete [duplicate]

I am working on some review problems right now and am extremely stuck on how to solve problem - any help would be so appreciated. We are told to consider the following combinatorial problem: Unit ...
-1
votes
0answers
43 views

Solving equation with sin [closed]

Basicly I just need to solve the equation in MATLAB ...
-2
votes
0answers
52 views

Maximum of inner product

The question is to maximize $\langle a, x\rangle$ subject to $\langle b, x^2\rangle = 1$ where $a$, $b$ and $x$ are positive $n$-dimensional vectors in $\mathbb R$, and $\langle\cdot,\cdot \rangle$ is ...
1
vote
1answer
104 views

Proving that Unit Intersection is NP-complete

I am extremely stuck on how to go about this problem and any help would be so appreciated. We are told to consider the following combinatorial problem: Unit Intersection: Let X = {1, 2,...,n}. ...
1
vote
0answers
16 views

Multiple optimal solutions / LP

In the optimal primal simplex tableau, if we have a non-basic variable with a reduced cost of zero, can we say for sure the primal has multiple optimal solutions? Or can the same thing also happen ...
1
vote
2answers
38 views

$Minimize$ $z=-2x-5y$ subject to $3x+4y\ge 5$ , $x\ge 0$ , $y\ge 0$.

Consider the linear programming problem: $Minimize$ $z=-2x-5y$ subject to $3x+4y\ge 5$ , $x\ge 0$ , $y\ge 0$. Which is correct ? (A) Set of feasible solutions is empty. (B) Set of feasible ...
0
votes
1answer
28 views

How to find the maximum value subject to constraints

I am currently enrolled in a college algebra course and am having difficulty finding the solution to the following problem since it is not covered in our textbook or in class. Any helpful hints or ...
0
votes
0answers
15 views

Simplex method state after first phase

I'm implementing a simplex method solver for a standard problem $$ \begin{aligned} \operatorname{minimize} \qquad&c^T x\\ \operatorname{subjected to} \qquad&Ax = b\\ &x \geq 0\\ ...
0
votes
1answer
16 views

Dealing with free variables in Linear Programming

I have a free variable in my formulation. In the objective function, this free variable has a cost, and another cost coefficient which is only incurred when the free variable is negative. I used the ...
1
vote
0answers
25 views

Seating at a large wedding

I have a large wedding of 500 people and 100 tables, each table containing 5 seats. Each person at the wedding lists (up to) 4 people they would like to sit at their table (order of the ranking ...
2
votes
1answer
43 views

Sensitivity Analysis, RHS change in some constraints

I am going to first layout the problem, then I'll get to the thing that is troubling me. I am enrolled in a course called "Optimization I", and this exercise is from a chapter called "Sensitivity ...
0
votes
1answer
27 views

Constructing canonical tableau for a linear programming problem involving SVM

I have the following set of inequalities and equalites $$\begin{align}y_1x_1+\cdots +y_nx_n &= 0\\ x_1 &\geq 0\\\vdots\\x_n&\geq0 \\ x_1&\leq c\\\vdots \\x_n&\leq ...
1
vote
1answer
58 views

how to work out 3 equations simultaneously

So i was doing this linear programming question and got stuck on this part, so how do you workout simultaneously $2x + 3y = 30 $ $(2/3)x + 2y = 16 $ $(16/3)x + 4y = 64$ According to lpsolve we ...
3
votes
0answers
29 views

Converting a max-min problem to a max problem with a constraint

The objective is to find the greatest lower bound of the variable $\mu$. The lower bound is resulting from the positive-semidefinite (PSD) constraint $$\tilde{\mathbf{T}}:=\left( \begin{array}{ccc} ...
1
vote
2answers
54 views

Linear Programming - How to maximise the maximum

I want to do the following: max: greatest(a1+b1+c1, a2+b2+c2, a3+b3+c3); ... constraints involving a1,a2,a3,b1,b2,b3,c1,c2,c3... Since there is no greatest() ...
1
vote
0answers
15 views

Binary depending on the sign of another variable

I'm writing a mixed integer linear problem, where I have an indicator function in the objective function counting the instances of negative values of a decision variable. I thought of defining a ...
0
votes
1answer
18 views

Strong duality theorem written with iffs?

Our strong duality theorem is: If both the primal LP and the dual LP have feasible solutions, then they both have optimal solutions, and for any primal optimal solution $x$ and dual optimal solution ...
1
vote
1answer
42 views

Linear Programming 3 decision variables (past exam paper question)

This is an exam question I was practising. I have the general understanding of Linear programming, but how would you go about finding the Decision Variables, Objective function and Constraints for ...
2
votes
0answers
14 views

Linear Programming 3 decision variables (past exam paper question) [duplicate]

This is an exam question I was practising. I have the general understanding of Linear programming, but how would you go about finding the Decision Variables, Objective function and Constraints for ...
0
votes
0answers
23 views

How do I convert a constraint with a product of two integer variables to a linear constraint?

I have a constraint of the form: $$\theta \leq a_1x_1 + a_2x_2 + a_3x_1x_2$$ where, $x_1$ and $x_2$ are integer variables with ranges $x_1 \in \{0, m\}$ and $x_2 \in \{0, n\}$. I would want to ...
0
votes
3answers
43 views

Solving Linear System with inequalities

I have the following system: \begin{align} b - x = 0 \\ a - 0.33b - 0.5x =0 \\ d - 0.33b = 0 \\ a - 0.33b + c = 0 \\ a + b + c + d + 2x = 1 \\ a + b + c + d - 8.8x \le 0 \\ a + b + c + d - 7.27x ...
0
votes
0answers
9 views

Say optimal solution to the primal is degenerate. Does it hold that optimal solution to dual not unique?

I think it's supposed to be that existence of a degenerate and unique solution of the primal implies multiple solutions to the dual, according to this book (pages 141-145, proof of Theorem 4.5). In ...
0
votes
1answer
53 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
2answers
57 views

How to check if given polyhedron is empty

Consider a polyhedron specified as following set of equalities and inequalities $$ \begin{aligned} &\mathbf{A}\mathbf{x} = \mathbf{b},\\ &\mathbf{x} \geqslant \mathbf{0}. \end{aligned} $$ Are ...
0
votes
1answer
13 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 ...
1
vote
2answers
39 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
16 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
32 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
24 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
44 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
34 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 ...