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

learn more… | top users | synonyms

0
votes
0answers
8 views

Extreme rays and lineality spaces

Consider the polyhedron $P$ defined as $$P = \{(x_1,x_2) \mid 4x_1 + 2x_2 \geq 8, \quad 2x_1 + x_2 \leq 8 \}$$ Then $P$ has no extreme points, as the corresponding matrix $A$ is given by $$A = ...
1
vote
1answer
25 views

Application Farkas Lemma

Let $A$ be a $m \times n$ matrix and $C$ a $k \times n$ matrix. Let $b \in \mathbb{R}^m$ and $d \in \mathbb{R}^k$. Show that exactly one of the following holds: a) There exists an $x \in ...
2
votes
2answers
46 views

What is the interpretation of the following optimization problem?

Suppose we have $N$ variables $x_1,\ldots,x_N$. Let $\mathbf{A}$ a $M \times N$ matrix, and $\mathbf{b}$ a $M \times 1$ vector. I have the following minimization problem: \begin{array}{rl} \min ...
0
votes
1answer
23 views

Characterize polytopes resulting from cutting a convex polytope by a hyperplane

We have a convex polytope $P$ for which we know its set of vertices. Using this set we characterize the H-representation of $P$ as: $\mathbf{A}\mathbf{x} < \mathbf{b}$. If a hyperplane defined by ...
0
votes
0answers
133 views

Linear - Quadratic optimization for system of objectives

I have two distinct data sets, $\{x^{\mu},J^{\mu}\}$, $\mu=1,\ldots,n$ and $\{x^{\nu},V^{\nu}\}$, $\nu=1,\ldots,m$ that also include uncertainties $\delta J^{\mu}$ and $\delta V^{\nu}$. In these I fit ...
1
vote
1answer
19 views

Simplex Method issues solving this problem

I have an exam coming up so I have been going over math questions in my textbook to practice the simplex method. I ran into an issue with questions like this one, and also any that have more ...
1
vote
1answer
18 views

Solving an integer linear programming problem without a graph

I am new to linear prorgramming and so far I have been solving LP problems with the help of a graph solution. However, when there are more than 2 variables obviously I can't plot them on the graph. ...
0
votes
0answers
26 views

how can we explain that the all slack point is feasible

how can we explain that the all slack point is feasible when solving a linear programming problem using the simplex method Thanks in advance, i appreciate all the help.
1
vote
1answer
19 views

Expressing problems in canonical form for solving with simplex

The Picnic Hamper Company has a store containing 10,000kg of nuts, 4000 packs of smoked salmon, 2000 bottles of wine and 1500 Victoria sponges. It intends to use these goods to make up three different ...
0
votes
0answers
52 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 ...
4
votes
1answer
67 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 ...
-2
votes
1answer
23 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
49 views

Least Squares method and Octave/Matlab [closed]

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
32 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 ...
2
votes
1answer
41 views

Chocolatier sampler boxes problem: applying goal programming and mixed-integer programing to optimally compromise goals.

QUESTION: A boutique chocolatier is planning to make a number of sampler boxes, each containing $36$ chocolates. (Therefore the total number of chocolates should be divisible by $36$.) The ...
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
14 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 ...
0
votes
1answer
54 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
32 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
30 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 ...
1
vote
1answer
24 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
21 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
36 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 ...
-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
40 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
16 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
31 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
44 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
29 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
61 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
30 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
43 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
15 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 ...
1
vote
1answer
32 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
56 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
58 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
14 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 ...