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

learn more… | top users | synonyms

1
vote
1answer
54 views

Linear Programming Word Problems

A bakery has bought 250 pounds of muffin dough. They want to make waffles or muffins in half-dozen packs out of it. Half a dozen of muffins requires 1 lb of dough and a pack of waffles uses 3/4 ...
2
votes
0answers
20 views

Duality between $Ax<b$ and another system, but Gordan's just misses

I am trying to show that $$Ax < b$$ Is feasible iff $$ A^T y =0 , b^Ty + s = 0, (y,s) \ge 0, (y,s) \ne 0$$ Is infeasible. Work So Far Now when I try to hit this with Gordan's Lemma I seem ...
0
votes
1answer
94 views

Can I skip numerical analysis altogether and jump to other courses [closed]

So the situation is I have completed Single and multivariate calculus, linear algebra, differential equations and and Real analysis. Now I'm thinking about skipping numerical analysis as it's of no ...
1
vote
1answer
44 views

Is there Any Benefits for Casting a Convex Program Problem into Linear Program Problem?

I'm curious a relative broad question: Suppose I have a convex program problem in hand. (hence, I could use many well-developed software packages to solve this problem for sure; e.g., CVX..) But ...
1
vote
0answers
18 views

How to regress certain non-linear data

How can I perform a regression onto data of that follows this shape: \begin{equation} U(x):=\sum_{i=1}^N\, a_ix^ie^{-b_ix} \end{equation} where the $a_i\in \mathbb{R}$ and the $b_i \in (0,\infty)$ ...
0
votes
2answers
34 views

geometric program maximizing using Arithmetic-Geometric mean inequality

Maximize $xy^2z^3$ subject to $x^3+y^2+z = 39$ and $x,y,z > 0$. I have that $39 = x^3 + y^2 + z = ..$ I am unsure what value I should use for $\delta_i$ in each coefficient when using the A-G ...
0
votes
0answers
24 views

What are the lawful operations in the simplex method?

Having the following: \begin{equation*} \begin{cases} \max& 3 x_1 & + 2x_2 & +4x_3\\ &x_1 &+ x_2 &+ 2 x_3 &\le 4\\ &2x_1 & &+3 ...
0
votes
0answers
25 views

How to use a LP solver to solve this problem?

I want to use a LP solver (doesn't matter which one) to solve this linear problem: $\mbox{Maximize }\sum_{i=1}^N \sum_{j=1}^N z_{ij} $ subject to: \begin{align*} &\sum_{i=1}^N a_i=1\\ ...
1
vote
0answers
52 views

Any linear way to express this expression

Do you think that there is a linear way to express this, using maybe a characteristic of this system that I cannot see. This is a set of equations involving exactly all sets of $(x_i, y_j, y_k)$ or ...
0
votes
1answer
71 views

LP problem involving producing assemblies

I have to construct an LP problem based on the ff scenario that might be similar to a scenario in another question (in the sense that I felt the need to use $mod$): The productivities are ...
2
votes
1answer
52 views

How does one use the 'input/hr' column in the table below in setting up the problem?

I have to set up a linear programming problem corresponding to the following scenario: If my understanding of the problem is correct, I use $mod$: Let $i$ be $A$ or $B$. Let $x$ be amount ...
1
vote
1answer
24 views

Max/Min flow of a network

I have a network: How do I figure out the maximum and minimum possible flow through each undefined branch?
1
vote
1answer
27 views

Best basic feasible solution NOT optimal solution to LP

Assuming that we are working with a minimization objective function and we have identified the best basic feasible solution, i.e. the basic feasible solution that yields the most minimal objective ...
2
votes
0answers
30 views

Why does the cutting plane method for integer programming run in exponential time?

I am looking for a proof of the fact that the cutting plane algorithm for integer programming does not run in polynomial time. The algorithm consists in adding constraints to the initial problem in ...
1
vote
2answers
49 views

How to solve 8 unknowns and 12 linear equations OVER DETERMINED system?

How to solve for a system of 8 unknowns and 12 linear equations? I use MATLAB, but answers change based on the choice of equations set. Is there any way can I solve and get consistent answer using all ...
1
vote
1answer
34 views

Airline scheduling using minimum network flow

Consider the following table for an airline company:               ...
0
votes
0answers
35 views

How is the dual of a LPP defined?

The dual of a cone is the set of vectors which have a non-positive dot product with any vector in the original cone.This definition does not seem to be valid in the LPP formulation wherein the ...
0
votes
1answer
33 views

Does Linear Programming always require equality (e.g. >=0) in the solution?

In linear programming system we encounter problem statement as below $maximize\ c^T \\ subject\ to \ Ax \leq b\\ and\ x \ge 0 $ My question is that is it possible to set the solution to be strictly ...
0
votes
1answer
50 views

Setting up an LP problem on producing linear board in jumbo reels

I have to set up a linear programming problem corresponding to the following scenario: What I tried: I think we have 8 templates for 1 $68 \times l$ reel (or whatever): $22,22,22$ (66) ...
1
vote
1answer
51 views

Are my constraints in this LP problem correct? Any redundant?

I have to set up an LP problem based on the situation below: What I tried: Let $b_i$ denote sacks bought at month i (i=1,2,3) Let $s_i$ denote sacks sold at month i (i=2,3,4) We want to ...
0
votes
2answers
71 views

How do I go about splitting up 1 LP problem into 2?

I have to set up a linear programming problem corresponding to the following scenario: From Chapter 2 here.
0
votes
1answer
43 views

LP problem: Does ratio of capacity refer to volume? Weight?

I have to set up an LP problem based on this situation below: What I tried: Let $x_{i,j}$ denote amount of loot i in hold j for i = 1,2,3 corresponding to materials, gold and spice for j = ...
0
votes
1answer
47 views

general solution for Linear Programming problem

Given a generic LP with a single constraint: maximize $c_1x_1 + c_2x_2 +.... c_nx_n$ such that: $a_1x_1 + a_2x_2 + .... + a_nx_n \le b$ Is there an obvious solution? I had originally thought this ...
0
votes
0answers
29 views

Why is one of the following always true in a given matrix A?

Consider A, a given matrix. I want to show that exactly one of the following holds: 1) $\exists x\neq 0$ such that $Ax=0$ 2) $\exists p$ such that $p^TA>0$ I tried proving that this is ...
0
votes
1answer
25 views

Monotonic optimal value function

Are there any theorems/sufficient conditions about when the optimal value function of a parametrized optimization problem is monotonic in the parameter? Specifically, are there simple conditions ...
2
votes
0answers
25 views

Can the non-uniqueness of a linear program's dual feasible set be exploited?

I was originally under the impression that a primal LP had a single corresponding dual feasible set. However, it is possible to alter the primal to an algebraically equivalent form which has a ...
0
votes
0answers
35 views

Problem writing linear programming equations

I need to create the inequalities for the next problem: Given 5 objects $(x_1, x_2, x_3, x_4, x_5)$ with $3$ properties $(a, b, c)$ with the values: $x_1: (23, 0, 10)$ $x_2: (42, 50, 0)$ $x_3: ...
0
votes
0answers
47 views

condition for having a positive solution to these linear equations.

Consider the following system of linear equations: $\displaystyle\sum_{j=1}^n c_{ij}\cdot x_{ij}=a_i$ for $j=1,\cdots,m$ and $\displaystyle\sum_{i=1}^m c_{ij}\cdot x_{ij}=b_j$ for $j=1,\cdots, n$ ...
0
votes
1answer
69 views

Express the constraint “$x = 0$ or $y = 0$” in linear programming

How to express the constraint "$x = 0$ or $y = 0$" in a linear program? Is it possible at all?
0
votes
0answers
25 views

Computing a new inverse given information from an earlier inverse:

Suppose I have linearly independent set of vectors $v_1 ... v_k \in \mathbb{R}^{k}$. I can let $B = [v_1 ... v_k]$ and by applying Gaussian elimination on the matrix $$ [ B \ I_k] $$ I end up ...
1
vote
1answer
48 views

Set up an integer programming problem so that all variables in the solution are different [closed]

I have a relatively simple minimisation problem. I have to minimise a linear function with many variables (more than 20), and I would like all the solutions to be different and in set $ x \in ...
0
votes
0answers
28 views

Converting a linear-fractional program with an integer constraint to a linear program

Is it possible to convert the following linear-fractional program to a linear program ? $$ \max_x \frac{v\cdot x}{z \cdot x}\\s.t \\x_i \in \{0,1\}\\ \\ \sum_i x_i = k$$ where $v \in R^{d}$, $z \in ...
0
votes
0answers
10 views

Optimize polling frequency between producer and consumer to achieve minimum waiting time

Background: I am trying to optimize what we call AJAX request polling frequency in the domain of web design, and I wanted to check if I could use some help from math guys to explore a better ...
0
votes
0answers
7 views

Polyhedral Sets and $min$-function

I'm asked to verify if the following set is polyhedral, $$ X = \{[x_1;x_2]: min(x_1,x_2) \leq 0\}$$ Definition of a polyhedral set, A set $Y$ is polyhedral if $Y = \{y: Ay \leq b\}$, for finite ...
0
votes
0answers
10 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, ...
1
vote
1answer
68 views

minimum possible value of a linear function of n variables

Suppose $x_1,x_2,\ldots,x_n$ are unknowons satisfying the constraint $a_1x_1 + \cdots + a_nx_n ≥ b$, where $a_1, \ldots , a_n, b ≥ 0$. Then the minimum possible value of the expression $c_1x_1 + ...
-2
votes
2answers
84 views

Is the area of linear programming dead right now? [closed]

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?
0
votes
1answer
26 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 ...
0
votes
0answers
13 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
77 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
49 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 ...
1
vote
1answer
48 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 ...
0
votes
1answer
41 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 ...
0
votes
1answer
40 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 ...
0
votes
0answers
35 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}}$ ...
1
vote
1answer
49 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
1answer
50 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
30 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
1answer
56 views

Solve a linear programming minimization problem with greater-than-equal sign in the constraints using the Simplex method

I need to solve the following linear programming minimization problem using the Simplex method: ...
0
votes
2answers
22 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 ...