Tagged Questions

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

learn more… | top users | synonyms

0
votes
1answer
24 views

Proof concerning basic solutions

Prove that every basic solution of $Ax=b$ (where $A$ is a matrix of rank $r$) is set by $r$ linearly independent columns of matrix $A$ (so it is $[A^{k_1}\dots A^{k_r}]\bar{x}=b$ where $A^{k_1},\dots ...
0
votes
0answers
19 views

Find non degenerate linear programming problems

I have to find non degenerate linear programming problem in a canonical form such that: a) it has no solutions b) it has solutions, but but doesn't have an optimal solution A ...
0
votes
1answer
24 views

How to solve systems of linear equations of multiple variables (more than 3 to 100s)?

This was a question asked during an interview for programming job. And the bottom line was to write an alogrithm to solve such equations. As much as it numbed my neurons - it really provoked me. I had ...
1
vote
1answer
16 views

Converting a Linear Program to Canonical Form

A linear program is said to be in canonical form if it has the following format: Maximize $c^Tx$ subject to $Ax ≤ b$, $x ≥ 0$ where $c$ and $x$ are n-dimensional real vectors, $A$ is an $m × n$ matrix ...
0
votes
1answer
22 views

Simplex method and basic solutions

I have put this into the form $0.5x_1 + 0.25x_2 + x_3=6$ $-x_1 - 3x_2 + x_4=-2$ $x_1 + x_2 = 10$ Is this correct? If so, how do I find a basic solution so that I can begin the simplex algorithm? ...
-3
votes
1answer
19 views

Linear programming problem --is not singular , what does it mean? [on hold]

[picture - in the linked picture while reading the marked area i have got following questions 1)Lp problem is not singular what does it mean on sense of given notations 2)what is Asi(vector) & ...
0
votes
0answers
8 views

Optimal basis versus optimal basis matrix

I have a conceptual doubt about the difference of optimal basis and optimal basis matrix. Some books have defined optimal matrix basis as the following: Consider a linear program on standard form. ...
1
vote
0answers
47 views

Mixed-Integer Linear Programing : get the maximum constant associated to a non null variable

Does anyone know a way get the maximum constant associated to a non null variable using Mixed-Integer Linear Programing ? I would like to get the variable $a$ in this description : $$ i = 1,\ldots,m ...
1
vote
0answers
14 views

Can this specific Linear Program constraint be expressed? [duplicate]

Thanks for your time. I have a linear program and no idea how I could express a form of constraint and even if it's possible. Maybe someone here know a solution. A company assembly and sells a ...
1
vote
0answers
79 views

Can this specific Linear Programming constraint be expressed? [closed]

Thanks for your time. I have a linear program and no idea how I could express a form of constraint and even if it's possible. Maybe someone here know a solution. A company assembly and sells a ...
1
vote
1answer
31 views

What optimization problem is this?

Minimize $$\sum_{i=1}^{m}w_i x_i$$ with $w_i \in \mathbb{Z}_{\ge0}$, and $x_i \in \{0, 1\}$ subject to a set of $n$ conditions of the form $$\sum_{i\in S_k} x_i \equiv c_k \pmod{2}$$ for $S_k ...
0
votes
0answers
61 views

Complementary slackness condition in economic terms

In linear programming how can one interpret the complementary slackness conditions in economic terms? The linear programming problem is to maximize $\sum_{j=1}^n c_j x_j$ subject to $\sum_{j=1}^n ...
1
vote
1answer
9 views

Formula for rate that changes when negative

Is it possible to reduce this code to a single formula, rather than check if x is negative? ...
0
votes
1answer
13 views

Relation between minimum of a function and minimum of the sum of the same function and a linear term

I'd like to know if it's true that if given a function $f(x):X \mapsto \mathbb{R}$ and a vector $c \in X$, then if $$v = \arg\min_x f(x) + x^tc$$ one can say that $$v-c = \arg\min_x f(x)$$ Does this ...
0
votes
1answer
30 views

Linear Programming Inventory

A company is opening a new franchise and wants to try minimizing their quarterly cost using linear programming. Each of their workers gets paid 500 per quarter and works 3 contiguous quarters per ...
0
votes
1answer
32 views

Linear programming and the simplex method

I am trying to solve this system of equations. My approach would be to introduce slack variables and then somehow use the simplex algorithm to solve this. Can anyone show me how this is done?
0
votes
0answers
15 views

Maximization over linear surjective mapping of polyhedron

I am reading this paper and confused about the derivation of equation (11) (page 3, bottom of column 2). I will rephrase it in this question. Let $\mathcal{P}_r = \{ x \in \mathbb{R}^n : P_r x \leq ...
0
votes
0answers
16 views

In the problem below, what is the right mix of drugs to maximize the expected revenue without exceeding R&D resources?

This is not a homework question. It's a question for a class I have yet to take that my friend gave me. I haven't been able to figure it out. Help is appreciated because it's driving me crazy. A ...
0
votes
0answers
10 views

Properties of an LP when the coefficients are variables of the problem

If I had a standard LP problem, and the coefficients of it are variable to the problem and I want to draw on the properties of the LP to say something about the coefficients. What such properties can ...
0
votes
0answers
35 views

LP transformation of multi-commodity flow problem

I have the following multi-commodity flow problem that I would like to bring into canonical LP format. \begin{equation*} \begin{aligned} & \underset{d}{\text{minimize}} & &d(x) = ...
1
vote
1answer
50 views

books on the application of linear algebra on statistics/finance/machine learning

I am reading "linear algebra done right" by Axler and like it a lot. One thing though, in the end I would like to put these theory to use and as a math textbook it doesn't cover much application. ...
3
votes
1answer
32 views

Finiteness of the Supremum of Inner Product of Two Finite Sum Positive Sequence

Let $$A = \Big\{(a_1,a_2,\dots)\ \Big|\ a_i\ge 0, \sum_{i=1}^\infty a_i=1\Big\},$$ $$v(x)=\sup\left(\bigg\{\sum_{i=1}^\infty a_ib_i\ \bigg|\ (a_i)_{i=1}^\infty,\, (b_i)_{i=1}^\infty \in ...
0
votes
1answer
26 views

Optimization options to select multiple items with different features and values

I'm trying to identify which approach would work best to select a set of elements that have different features that minimise a certain value. To be more specific, I might have a group of elements with ...
0
votes
0answers
14 views

Linear Optimization: What is the difference between these two theorems?

I attend a lecture about linear optimization where we had the following two Theorems. But I somehow cannot spot the difference: Theorem 1: Let $P$ be a polyhedron with an extreme Point and $c \in ...
1
vote
1answer
27 views

Taking the dual of this non-standard linear program

I am just beginning to learn linear programming have a question about taking the dual of a non-standard LP specifically the one below: $\min M\\ 2x_1 + 3x_2 + 4x_3 \leq M \\ 2x_1 - x_2 + x_3 \leq M\\ ...
0
votes
0answers
18 views

Proof of Simplex Method, Adjacent CPF Solutions

I was looking at justification as to why the simplex method runs and the basic arguments seem to rely on the follow: i)The optimal solution occurs at some vertex of the feasible region (CPF points) ...
2
votes
0answers
33 views

What is a closed chain (or circuit) that is used in solving a transportation problem (a special type of linear programming problem)?

What is a closed chain (or circuit) that is used in solving a transportation problem (a special type of linear programming problem)? I'm having some problems with it. Please clarify it. I have posted ...
0
votes
1answer
29 views

Conversion of a general linear program into a standard linear program

I am trying to teach myself the basics of optimization of linear programmes, for example the following question: How do I tackle such a question?
0
votes
0answers
12 views

Tableau Condition for dual simplex algorithm

The following is a tableau obtained when solving a minimization linear programming problem via the dual simplex algorithm. basic $x_1$ $x_2$ $x_3$ $x_4$ $x_5$ $x_6$ $x_7$ RHS ...
0
votes
0answers
50 views

Linear Programming- Steelco manufactures two types of steel

Problem 1 Steelco manufactures two types of steel (steel 1 and steel 2) at two locations (plant 1 and plant 2). Three resources are needed to manufacture a ton of steel: iron, coal, and blast furnace ...
2
votes
0answers
25 views

Convert a problem o minimizing a function to linear programming problem in standard form

I have to 1) convert a problem o minimizing a function to linear programming problem in standard form. It is something new to me. Can somebody explain it to me? $$\min(\mathbb{R}^2\ni(x,y)\rightarrow ...
0
votes
1answer
26 views

Optimization problem in the standard form

Let $x\rightarrow x^{T}c$ be an objective function of an optimization problem in the standard form, for which the optimal solution doesn't exist. Does then exist an optimal solution to $x\rightarrow ...
0
votes
0answers
22 views

Grouping elements such that optimizing inter group communication cost

Suppose we have n elements. We need to group them into m group such that each group cannot take more than $x_1,x_2...x_m$ elements respectively. Sum of $x_i \geq n$. We need to optimize the inter ...
0
votes
1answer
24 views

Dual simplex doubt (unrestricted)

I have this two problems and i only want to find the dual form: $\begin{gather} max\hspace{.1cm}z =5x_1+6x_2\\ s.t\hspace{.1cm}x_1+2x_2=5\\ -x_1+5x_2 \ge 3\\ x_2 \ge 0\\ x_1\hspace{.1cm} ...
0
votes
0answers
9 views

LP: generic objective guarantees a unique solution?

Suppose that I have a linear program \begin{align} & \text{maximize} && \mathbf{c}^\mathrm{T} \mathbf{x}\\ & \text{subject to} && A \mathbf{x} \leq \mathbf{b} \\ & ...
0
votes
1answer
28 views

Linear Programming : Is there any other way to solve than graphs?

In my highschool curriculum there's a a chapter on Linear Programming Problems. In the chapter there are bunch of unproved statements and mechanical ways to solve linear problem. But my question is- ...
0
votes
0answers
10 views

Convert the problem into an equivalent stalndard lpp

Consider the optimization problem, Minimize, $C_{1}|x_{1}|+C_{2}|x_{2}+C_{3}|x_{3}|+...+C_{n}|x_{n}|$ subject to, $AX = b$ , $C_{i} \neq 0$ Convert the above problem into an equivalent standard ...
0
votes
1answer
52 views

Linear Programming and Geometry Question

I have a question that involves some linear programming and linear algebra, and I really don't have a clue how to approach this question. Could someone give me some hints and ideas as to how to attack ...
0
votes
0answers
28 views

Linear Programing : get the maximum constant associated to a non null variable

Does anyone know a way get the maximum constant associated to a non null variable using only linear programing ? For example, supposed that there is 3 linear variable x, y and z. x being associated ...
1
vote
1answer
29 views

Linear Programming and Standard Form

In order to find the dual of a primal linear program, do I always have to convert it to the standard form first? For example, if I have the following LP, would the dual also be a min since the LP in ...
0
votes
0answers
25 views

When to stop Simplex algorithm.

How do we understand when optimal solution is reached and we should stop iteration in simplex method algorithm using tabular method?
0
votes
2answers
34 views

References for Linear Algebra needed for Differential Equations and Linear Programming

I am in need of learning the Linear Algebraic theory behind the following Applied disciplines. Could someone please recommend Linear Algebra books for: Differential Equations: Specifically learning ...
1
vote
0answers
25 views

Write down a linear programming problem

I want to replicate a linear programming problem.I have the following information, for the background." A fuzzy regression analysis with only one independent variable X results in the following ...
0
votes
0answers
10 views

Binary linear programming (matrix)

I formulated a linear programming problem (real life case, so I won't disclose here) into this form: $$ Minimize\sum a_{ij} x_{ij} $$ subject to $$\sum_{i} x_{ij} = m, j = 1,2,..,n $$ $$\sum_{j} ...
2
votes
2answers
53 views

Is $[u_1,u_2]$ an edge of the polytope $conv(F)$?

Here's the problem. I have a finite set of vectors $F \subset \mathbb{Z}_{\geq 0}^d$. I define $P$ to be the convex polytope $conv(F)$ i.e. the convex hull of $F$. Given $u_1, u_2 \in F$, is the ...
0
votes
0answers
7 views

grouping with linear programming

Suppose the following: I have a set (U) containing elements with at least one way to discriminate them. Let's just say exactly one. Maybe think of integer numbers x and the way to discriminate them ...
0
votes
0answers
25 views

optimisation problem with linear constraint

optimisation problem with linear constraint I have an optimisation problem. I wish to maximise a function subject to a constraint. It is the constraint that is causing me problems. I am using an ...
0
votes
0answers
18 views

mathematical formulation Minimum Cost Flow

I have a problem of minimum cost flow that can be defined as the following matrix. I want to solve it how a linear program (without using kruskal algorithms, prim etc). How can I formulate it like a ...
0
votes
0answers
17 views

How to I see that $n-1$ linearly independent constraints $a_i^Tx \ge b, i \in \{1,\dots, n-1\}$ define a line in $\mathbb R^n$?

How to I see that $n-1$ linearly independent constraints $a_i^Tx \ge b, i \in \{1,\dots, n-1\}$ define a line in $\mathbb R^n$ ? ($b, a_i, x \in \mathbb R^n$) If I can find a vector $p$ that ...
0
votes
0answers
12 views

Having trouble finding the right variables and constraints for linear programming problem.

I've got a word problem that needs to be solved via the simplex tableau method but from reading I can't decide what my variables and constraints will be: Slapshot Inc. makes two types of hockey ...