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

learn more… | top users | synonyms

1
vote
1answer
23 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
24 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? ...
0
votes
0answers
16 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
49 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
18 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
1answer
35 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
97 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
14 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
31 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
56 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
16 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
11 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
40 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
71 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
42 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
27 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
38 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\\ ...
1
vote
0answers
39 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
36 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
34 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
19 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 ...
2
votes
0answers
37 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
30 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
1answer
37 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
42 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
12 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
53 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
29 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
41 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
31 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
42 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
29 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
11 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
56 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
10 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
26 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
26 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
18 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
18 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 ...
0
votes
0answers
19 views

Maximize Net Profit with Simplex Tableau

I have a profit maximization problem and have been asked to solve it using the simplex tableau method. The thing is as far as I can tell there are no constraints present, so I'm really not quite sure ...
0
votes
1answer
31 views

Given a set of integers find two disjoint subsets $I$ and $J$ so $|I|+|J|=k$ and $\sum\limits_{i \in I}x_i = \sum\limits_{j \in J}x_j = n^2$

Given a set of integers $1 \le x_1,x_2\dots,x_n \le n^2$ and a number $k \le n$. describe an algorithm that will determine if there exists two disjoned subsets $I$ and $J$ such that $|I|+|J|=k$ and ...
1
vote
0answers
108 views

Show that every extreme point in Q is either an extreme point of P or a convex combination of two adjacent extreme points of P

P is a bounded polyhedron in $\mathbb{R}^n$, $a$ a vector in $\mathbb{R}^n$, and $b$ some scalar. Define $$Q = {x \in P | a'x = b}$$. Show that every extreme point in Q is either an extreme point of P ...
0
votes
1answer
35 views

Find Maximum of Lower Envelope

Okay, I'm not really sure whether the title is good. Consider \begin{align*} \min\{ 5x_1 + \frac{5}{2}x_2 + \frac{5}{3}x_3 + \frac{5}{4}x_4, \\ x_1 + \frac{6}{2}x_2 + \frac{6}{3}x_3 + ...
1
vote
1answer
47 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
1answer
34 views

Feasible Condition with a single constraint

A linear program with a single constraint minimize $z = c_{1}x_{1} + c_{2}x_{2} +· · ·+c_{n}x_{n}$ subject to $a_{1}x_{1} + a_{2}x_{2} +· · ·+a_{n}x_{n} ≤ b$, $x_{1}, x_{2}, . . . , x_{n} ≥ 0.$ (a) ...
4
votes
1answer
61 views

Easy elementary proof of Farkas Lemma?

Is there any elementary proof of Farkas lemma which does not use convex analysis and hyperplane separation theorem? What about special case below: If the Matrix $A$ is invertible, then there is ...
0
votes
1answer
44 views

Set of optimal solutions for a linear programs

Consider the linear program: minimize $z = x_{1} - x_{2}$, $x_{1}, x_{2}\geq 0$ subject to: $-x_{1} + x_{2}\leq 1$ , $x_{1} - 2x_{2}\leq 2$ Derive an ...