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

learn more… | top users | synonyms

-2
votes
2answers
48 views

Is the area of linear programming dead right now?

By dead i mean not much/completely no research there . Is the area of linear programming dead right now? If it is not dead, what are the active area called for example except computer science?
2
votes
2answers
490 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
0answers
4 views

Removing variables from convex linear program

I am solving linear program (possibly non-convex). Then we know that dual is always convex. Then I noticed that depending on objective functional I can sometimes remove particular variables from this ...
2
votes
1answer
590 views

Binary constraint integer programming problem

I have a question to the folowing question: Explain how to use integer variables and linear inequality constraints to ensure: A) let $x$ and $y$ be integer variables bounded at 1000. How can you ...
2
votes
1answer
525 views
0
votes
0answers
11 views

Matching of points in two discrete linear sequences with potentially missing points

This is a question that I've been thinking about in my research lately. I've gone down the route of a few linear-optimization techniques, but nothing particularly spectacular has come up. Anyway, ...
0
votes
2answers
1k 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?
0
votes
1answer
42 views

How to configure simplex method to start from a specific point

If I have a linear programming problem e.g. $$\max 2x_1 + x_2$$ with these constraints $$x_1-2x_2 \leq 14$$ $$2x_1-x_2\leq 10$$ $$x_1-x_2 \leq 3$$ And I want to solve the problem starting from a ...
0
votes
1answer
15 views

Does optimal solution from primal problem follow from optimal solution to dual?

In a linear programming context, does the primal optimal solution yield an explicit way to find the primal dual solution? I vaguely remember something like this from an optimization class but can't ...
2
votes
2answers
369 views

Multiple solutions for both primal and dual

If matrix $A$ in an LP (or $A^T$ in its dual) has full row (column- in dual) rank, is it possible that both primal and dual have multiple solutions?
0
votes
0answers
8 views

Legal operation to transform a linear program into the canonical form

Good morning! What are the legal operations to transform a linear program into the canonical form? For instance can the following linear program \begin{cases} \begin{array}{col1col2…coln} \max ...
0
votes
0answers
46 views

Intersecting rational polyhedral cones

Call A the cone generated by the rays (1,0,0) and (0,1,0) and B the cone generated by the rays (1,1,0),(1,0,1), and (0,1,1). I want to compute the intersection of these polyhedral cones, but I am ...
0
votes
1answer
29 views

set up Linear programming problem

How do I set up this problem ? A product can be made in three sizes, large, medium, and small, which yield a net unit profit of $12, 10$ and $9$ respectively. The company has three centers where ...
1
vote
1answer
34 views

How can L1-sparse representation be formulated as linear programming?

Problem Statement Show how the $L_1$-sparse reconstruction problem: $$\min_{x}{\left\lVert x\right\rVert}_1 \quad \text{subject to} \; y=Ax$$ can be reduced to a linear programming problem of form ...
1
vote
1answer
35 views

What is the difference between linear and integer programming?

Recently I tried to solve a maximization integer programming problem using linear programming by flooring the max point - but got the wrong answer. I'm wondering if someone can explain mathematically ...
0
votes
0answers
24 views

Solving a set of linear equations

I have the following linear equations I need to solve: $$Y=\sum_{n=1}^{N}A_nX_nB_n$$ where Y is m x m $A_n$ are m x $\frac{m}{\sqrt{N}}$ $X_n$ are $\frac{m}{\sqrt{N}}$ x $\frac{m}{\sqrt{N}}$ ...
0
votes
1answer
26 views

Canonical form simplex method

In 2-phases simplex method what kind of operations must be done to get the canonical form tableau? In this step(phase 2 of 2-phases method) after the remotion of artificial variables columns of ...
1
vote
1answer
43 views

Project allocation optimization with tricky constraint

I have an allocation problem that should be straightforward, except that it has very specific constraints. I want to assign approximately 300 students to 170 projects in pairs - so that each project ...
1
vote
2answers
843 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 ...
1
vote
1answer
3k views

simplex M-method minimization problem

Solve using the simplex method. Identify the solution of the dual in the final simplex tableau Minimize: $$z=12x_{1}+4x_{2}+2x_{3}$$ **Constraints:**$$ x_{i}\ge 0$$ $$-6x_{1}+3x_{2}\ge 9$$ ...
0
votes
0answers
29 views

Minimum cost linear programming problem formulation

I need to formulate a graph and a linear programming problem, and provide a basic solution for the following problem: A singer who lives in city A wants to plan a tour and end it in city E. The ...
0
votes
2answers
18 views

What if we get fractional value while finding the numbers of workers in a linear programming problem?

I came across a LP problem in which a factory recruited workers on daily basis giving them wages per day. I don't remember the figures but I remember what was in the question. We had to find the ...
0
votes
1answer
28 views
1
vote
1answer
26 views

Solving integer programming problem using the graphical method

I have an integer programming problem I need to solve using the graphical method. Maximize $55x_1 + 500x_2$ such that $$\begin{align} 4x_1 + 5x_2 &\le 2000\\ 2.5x_1 + 7x_2 &\le 1750\\ ...
1
vote
1answer
2k 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
20 views

Can we relax the assumption of nonnegativity in this proof on convexity of a feasible region in a linear programming problem?

Is the $\color{red}{\text{non-negativity constraint (see red box)}}$ used at all in the proof? If so, where? If not, does the proof then hold for a standard LP problem without the non-negativity ...
0
votes
0answers
23 views

On the proof of corner points maximising or minimising a linear function over a bounded convex region

This proof says if $Z_P \ne Z_Q$, then $Z$ is maximised (or minimised, I guess) at one of the endpoints -- of what exactly? $\overline{PQ}$? So the maximum value of $Z$ occurs at either $P$ or $Q$? ...
0
votes
1answer
34 views

Scheduling Optimization Problem - 5 days/week

A 24/7 calling center works as follows: every agent works 5 days in a row and has two days rest, e.g., every week works Tuesday-Saturday and rests on Sunday and Monday. The numbers of agents working ...
0
votes
0answers
21 views

Explicit solution for minimization over unit box with total budget constraint

I am trying to solve question 4.8, part (e) from Convex Optimization by Boyd. The problem is to find an explicit solution for the minimization problem: Minimize $\textbf{c}^T \textbf{x}$ subject to ...
1
vote
1answer
53 views

Dual program is wrong. Authors claim is right.

In a well respected book, I found the following. The authors claim that it is correct. But I think it is wrong. This is the primal Linear Problem: $$ \begin{array}{cccc} ...
3
votes
1answer
89 views

Discrete Linear Programming over Finite Fields?

$A$ is an $l\times m$ matrix with integer entries and each column of which contains at least one negative entry. $y$ is a column matrix with integer entries of length $l$. Define the set of sequence ...
0
votes
1answer
42 views

Polytopes defined by $x_i >=0, Ax = b$ are generic ? (Understanding simplex method)

Consider polytopes in $R^n$ defined by $x_i >= 0, Ax = b$, for $b > 0$. Assume $A$ is of full rank $r$ and $Ax=b$ has solutions. The following properties seems to be correct. I would be ...
8
votes
1answer
1k views

Farkas Lemma proof

I am trying to prove the Farkas Lemma using the Fourier-Motzkin elimination algorithm. From Wikipedia: Let A be an $m \times n$ matrix and $b$ an $m$-dimensional vector. Then, exactly one of the ...
0
votes
0answers
35 views

Showing λu + (1 − λ)v is an optimal solution

$$\max \quad c \cdot x \\ \mathrm{s.t.} \ Ax \leq b\\ x\geq 0 \\$$ There are two optimal solutions to the LP $u$ and $v$. How do I show that for $\lambda \in [0,1]$, $\lambda u + (1-\lambda)v$ is ...
0
votes
2answers
31 views

How to describe $\lbrace \mathbf{x}\in \mathbb{R^n}: |x_j|\le1 $ for$ 1\le j\le n \rbrace $ in terms of $x_j=x_j^+-x_j^-$

How to describe the set $A$=$\lbrace \mathbf{x}\in \mathbb{R^n}: |x_j|\le1 $ for$ 1\le j\le n \rbrace $ in terms of $x_j=x_j^+-x_j^-$ where $x_j^+\ge0$ and $x_j^-\ge0$ The answer says: $B$=$\lbrace ...
0
votes
0answers
13 views

Optimization: second order condition

This is the condition Where $L(x, \mu\,\lambda)$ is the Lagrangian function in a given point that satisfy the first order condition. Problem $ min (-4x -y)$ $ -x^2 -y^2 +1 <= 0 $ $ y- 1 ...
0
votes
1answer
14 views

About Dual Simplex Method

I have a question about Dual Simplex Method (for minimization problem). While we are solving the method, when we obtain a non-negative $\bar b$, we stop the algortihm. But in addition to $\bar b ...
0
votes
1answer
533 views

Linear Programming formulate if then constraint

Consider an LP for which you want to add the restriction that Only if $x_1\geq 3$ then $x_2$ and $x_3$ are allowed to be larger than $0$; otherwise $x_2$ and $x_3$ are $0$. Demonstrate how to ...
-1
votes
0answers
11 views

mathematica Linear programming with summation and product

I want to solve Linear programming in mathematica that have summation and products in objective function and in constraints. I ...
0
votes
0answers
24 views

Does this transformation of a problem into a Linear Programing normal form is correct?

An oil refinery produces four types of raw gasoline: alkylaten catalytic, striaght and isopentane. Two important characteristics of each gasoline are its performance number $PN$ and ints vapore ...
0
votes
1answer
29 views

Maximise volume given inequality constraint on its dimensions without using Lagrange, KKT or Linear Programming

The problem (from Calculus for Business, Economics, Life Sciences and Social Sciences 12e): I found this and that, but they use Lagrange/KKT. What I tried: Girth $= 2w + 2h$ Maximise ...
0
votes
1answer
1k 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 ...
0
votes
1answer
21 views

Definition of Optimality test - Simplex method

To clarify, this is not a question about how to conduct test of optimality or about what is the test good for. Nor am I asking for mathematical proof supporting it. I am asking specifically for ...
5
votes
1answer
3k 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 ...
1
vote
3answers
43 views

How do I graph Linear Programming questions?

So let's say I have the following constraints: $2a + 3b \leq 30$ $a + b \leq 15$ $a \geq 0$ $b \geq 0$ (I just made this problem up, so I'm not sure if it may make any sense when I graph it.) ...
0
votes
1answer
17 views

How to find what maximizes the total net profit?

A meat packing plant produces $480$ hams, $400$ pork bellies and $230$ picnic hams every day; each of these products can be either fresh or smoked. The total number of hams, bellies and picnics ...
0
votes
2answers
35 views

Help buying a calculator program [closed]

Is there an economical calculator program I can buy that will let me multiply and divide numbers in the hundreds of digits and show all of the digits?
0
votes
1answer
23 views

Basic and non basic variables in linear programming

I dont understand what are Basic and non basic variables,why we are talking them specially, what they have got to do with the rank of the coefficient matrix and augmented matrix ,and some deal with ...
3
votes
1answer
2k 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$ ...
0
votes
2answers
27 views

Operation Research: system of equations

I have a system of equations for my Operations Research class, and the book is solving them by using algebra. However, I think it would be easier to solve them using linear algebra, and will also ...