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

learn more… | top users | synonyms

3
votes
1answer
65 views

Bland's Ratio Details

Bland's Finite Pivoting Method is often used as the standard pivoting rule in simplical optimization for linear programs. However, some literature conflicts - for maximization, some state that only ...
3
votes
1answer
3k 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
0answers
27 views

Closed-form solution of a linear programming question

Among all the probability matrices \begin{equation*} P = \left(\begin{array}{cccc} p_{00} & p_{01} & \ldots & p_{0,J-1} \\ p_{10} & p_{11} & \ldots & p_{1,J-1} \\ \vdots & ...
0
votes
0answers
26 views

An polynomial time algorithm to solve LP

Is there a polynomial time algorithm that gives the extreme point as output for which objective function is minimized/maximized ? I am not looking for any solution that minimizes/maximizes the ...
0
votes
0answers
28 views

Optimization using Linear programming

I have a set of machines in the cloud (charged hourly). Some of them have been running already. I want to add and remove these machines dynamically in the cloud. Each type of machine has a ...
0
votes
1answer
18 views

How many tight constraints does a linear program have?

I have the following constraints of a linear program: $$\sum_{j=1}^{m}x_{ij}=1,\quad\quad1\le i\le n,$$ $$\sum_{i=1}^{n}p_i^k x_{ij}=1,\quad\quad1\le j\le m,\;1\le k\le d,$$ $$x_{ij}\ge ...
0
votes
0answers
12 views

optimize search through parameter space to find parameters sets

I have a simulation which calculates the amount of time it takes for a tank/tube to drop below a certain temperature, given a set of parameters. The simulation takes quite a while to run and I would ...
0
votes
0answers
17 views

linear inequalities and reduction

Let $X\subset \mathbb R^m$ be a convex compact subset. Let $E=\{-1,0,1\}^m$. What would be the necessary or sufficient conditions on $X$ such that for any $f\in [-1,1]^m$, there exists at least ...
0
votes
1answer
47 views

Minimize the function $f(n,k)=(n-1)-\sqrt{(n-1)^2-4(k-1)(n-k-1)}$ over n,k

For $k\in N, n-2\ge k\ge2$, and $n \in N, n\ge4$ minimize the function $f(n,k)=(n-1)-\sqrt{(n-1)^2-4(k-1)(n-k-1)}$ over n,k EDIT: Attempt to solve First I differentiated it partially w.r.t $k$ and ...
2
votes
2answers
141 views

Why can/should we use 5 instead of 10?

Problem: A pharmacy has a uniform annual demand for 200 bottles of a certain antibiotic. It costs \$10 per year for a storage place for one bottle, and $40 to place an order. How many times during ...
0
votes
1answer
26 views

Challenging Linear Programming Question - Determining Objective Function

Working Out: X = Num. of bottles sold from Vineyard 1 Y = Num. of bottle sold from Vineyard 2 A = Num. of bottles demanded by Rest 1 B = Num. of bottles demanded by Rest 2 C = Num of bottles ...
0
votes
0answers
25 views

Need optimal tableaus be unique assuming unique solution?

If so, why? If not, do they differ by some ERO/s? That is, they are row equivalent? This is the problem (taken from Chapter 2 here): My classmate gave an optimal tableau that is different ...
0
votes
2answers
64 views

How to generate a feasible point for a program with both equality and inequality contraints?

I am using an optimization method that requires a starting point within the feasible domain: $$\min f(x)$$ $$Ax=b$$ $$Cx>r$$ where $$x \in R^l$$ $$b \in R^n$$ $$r \in R^m$$ and $$ (m+n) ...
0
votes
0answers
15 views

How to calculate the Bouligand derivative (B-derivative)

Let $H(x)=\min (f(x),h(x))$ where $f$ and $h$ are continuously differentiable functions from $\mathbf{R}^n$ to $\mathbf{R}^1$. The Bouligand derivative (B-derivative) $BH(z)$ at $z$ of $H$ is given ...
0
votes
0answers
24 views

How does changing the cost vector of a primal linear programming problem affect the solution of the dual?

Say the linear program: max $p'x$ such that $Ax=b$ and $x \geq 0$ is primal and dual feasible, and $\bar{u}$ is known to be the optimal solution to the dual. If the $\lambda \ne 0$ times the $i$th row ...
0
votes
1answer
30 views

Formulating the Dual of a linear program

I have a linear program: Maximize 18x + 12y subject to: x+y <= 20 x <= 12 y <= 16 x,y >=0 I have found ...
0
votes
1answer
11 views

Unbounded solution of LPP

In connection with LPP, what is meant by 'unbounded solution' and 'unbounded objective function'? Are they same or they are distinct concepts?
0
votes
0answers
6 views

Use duality to solve LPP

I have some confusion regarding the solution of LPP by solving its dual. I have drawn the following table to indicate possibility/possibilities. I have made an attempt to correlate the two columns but ...
0
votes
1answer
180 views

Regression with equally spaced set

I'm working on an algorithm (written in Python/Cython, but it reads like pseudo-code) that estimates the gradient of each point in noisy data, using a variable window size. It's working very well, but ...
0
votes
0answers
23 views

Conditionals without use of binary variables

I would like a linear programming expression that has to satisfy certain criteria without the use of binary variables. i.e.: Let 0 <= B <= C However, if ...
1
vote
2answers
43 views

Optimization over linear combinition of min functions

Assume we are given these six variables: $x_{12},x_{21},x_{13},x_{31},x_{23},x_{32}$. Then if, $A_{ij} = min\{x_{ij},x_{ji} \}, B_{ik} = min\{x_{ik} - A_{ij}, x_{ki} \}, C_{jk} = min\{x_{jk} - ...
1
vote
2answers
2k views

Minimizing the sum of absolute values with a linear solver

I need a linear program to minimize the sum of several absolute values, but the inclusion of an absolute value means the linear solver won't work. I know there are ways around using an absolute value, ...
0
votes
1answer
45 views

Shortest Path Problem as a Minimum Cost Flow Problem

I have to formulate the well known shortest path problem as a min-cost flow problem, but I don't know how to do it. I need your help and suggestions. Thanks in advance!
0
votes
1answer
15 views

Graphical solution of lpp

I need to solve the following LPP using graphical method Min $z=-2x_1+x_2$ subject to $x_1+x_2 \geq 6$, $3x_1+2x_2 \geq 16$, $x_2 \leq 9$, $x_1, x_2 \geq 0$ The common feasible region is ...
0
votes
0answers
20 views

Definition of Concave set

We know that a set is convex if the straight line joining any two points of the set lies completely in the set. or mathematically a set $X$ is convex if $x_1, x_2 \in X \Rightarrow\lambda ...
0
votes
0answers
22 views

Mathematical formulation of LPP

I want to formulate the following problem as a LPP A manufacturing company produces two types of computer monitor- color and monochrome. The data in the manufacturing context are as follows 6 days ...
0
votes
0answers
9 views

Estimate size of smallest solution to linear program

I have a linear program: a system of linear inequalities of the form $$Ax \le b, \qquad x \ge 0.$$ where $x \in \mathbb{R}^n$, $b \in \mathbb{R}^m$, and $A$ is a $m\times n$ matrix. I am looking ...
1
vote
1answer
33 views

Vertex and barycentric coordinate enumeration for a polytope

Problem 1 Enumerate all the vertices of the polytope defined by: ${\bf Ax}\leq {\bf b}$ where ${\bf A} \in R^{m \times n}$, ${\bf x} \in R^n$, ${\bf b} \in R^m$ and each element of ${\bf x} = ...
1
vote
1answer
62 views

A linear programming problem concerning find equalities from $Ax\le b$

I found this problem on page 96 of Alexander Schrijver's book Theory of Linear and Integer programming:(Robert Freund): Given a system $Ax\le b$ of linear inequalities, describe a linear ...
0
votes
1answer
41 views

Prove a set is convex

I have problems to make proof for below two statements. Let Γ be the LP max cᵀx s.t. Ax ≤ b. prove that set of all optimal solutions to Γ is a convex set Let x' be a basic feasible solution of Γ. ...
2
votes
1answer
19 views

Express the feasible solution (3,1) as a convex combination of extreme points

So i am given four extreme points: $A: (0,0)$ $B: (8,0)$ $C: (2,3)$ $D: (0,1)$ and I need to express the feasible solution $(3,1)$ as a convex combination of extreme points. My professor did the ...
12
votes
1answer
158 views

Fitting a parabola to separate two classes of points in the plane

Suppose we have a set of points $(x,y)$ in the plane where each point is either boy or a girl. Does there exists a randomized linear-time algorithm to determine if we can fit a parabola (given by a ...
0
votes
0answers
38 views

Solution of LPP by graphical method

I need to solve the following LPP using graphical method Min $z=4x_1+x_2$ subject to $2x_1+x_2 \geq 2$, $x_1+3x_2 \leq 4$, $x_2 \leq 4$, $x_1, x_2 \geq 0$ But I am not finding any common ...
-1
votes
1answer
64 views

Linear Programming Mixed Assortment of Nuts

Below is a problem on Linear Programming. I think I have a start to it, but I'm in a rut right now so I was wondering if I could receive a little help. Here's the problem A candy store sells three ...
0
votes
1answer
19 views

proof of existence of solution to componentwise inequality using only linear algebra

For $A \in \mathrm{Lin}(\mathbb{R}^n, \mathbb{R}^m)$ , $m=n$ and $A$ is invertible, I am able to prove the existence of a solution $x$ such that $A x \succeq 0$ where $\succeq$ denotes componentwise ...
0
votes
0answers
15 views

Necessary and sufficient condition for basic solution

We know that for a basic solution at least $n-m$ variables must be zero and basic vectors must be Linearly independent. My question is What are the necessary and sufficient conditions for a ...
0
votes
1answer
81 views

value of a matrix game

Suppose I have a matrix $$ \begin{bmatrix} 1&4&2\\ 3&2&1 \end{bmatrix} $$ How do I find the minimax value of the matrix? ( It will be considered as a matrix of a matrix game where ...
1
vote
4answers
670 views

Find a nonnegative basis of a matrix nullspace / kernel

I have a matrix $S$ and need to find a set of basis vectors $\{\mathbf{x_i}\}$ such that $S\mathbf{x_i}=0$ and $\mathbf{x_i} \ge \mathbf{0}$ (component-wise, i.e. $x_i^k \ge 0$). This problem comes ...
0
votes
0answers
20 views

Formulation of LP Problem with three constraints

I have an assignment in a Linear Programming course that I'm having some trouble with understanding. The problem is, or should be, pretty simple, but for the life of me I can't seem to be able to get ...
0
votes
0answers
18 views

Solution to simultaneous minimum and maximum objective function

What will be the closed form solution for a vector $\mathbf{w} \in \mathbb{R}^{n\times 1}$ and matrix $\mathbf{X} \in \mathbb{R}^{n\times l}$, such that simultaneously $\Vert ...
0
votes
1answer
37 views

Convert non-linear into linear

What I tried: Let $$u_1 = x_1^3$$ $$u_2 = x_2 x_3$$ $$u_3 = x_3^3$$ Then we have $z = u_1 + u_2 + u _3$ s.t. $1 \le u_3 \le 343$ $u_3^{1/3}$ should be integer $u_1 \in \{0, 1\}$ $u_2 \in ...
1
vote
1answer
21 views

Optimal basis in linear programming

Given the following linear program: \begin{cases} \max &5x_1 + x_2 + 6x_3 + 2x_4\\ &4x_1 + 4x_2 + 4 x_3 + x_4\le 24\\ &8x_1 + 6x_2 + 4x_3 + 3x_4\le 36\\ &\forall i, x_i\ge 0 ...
0
votes
0answers
22 views

Lagrange Duality clarification

For a given Linear programming problem \begin{align} max \ c^Tx \\s.t\ Ax \leq b \end{align} and for lagrange multiplier $p\geq0\\$ \begin{align} g(p):= max \{ c^Tx + p^T(b-Ax): x\in \mathbb{R}^n\} ...
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 ...
1
vote
0answers
24 views

How to know in the matrix form when a linear program isn't feasible and what to do from it?

Good morning, I'm preparing my exam first exam in linear programing and try to sharpen my skills over how to handle such programs. I want to know when can we know that a linear program isn't feasible ...
0
votes
0answers
21 views

Complementary Slackness Condition clarification

So for the dual part of the complementary slackness, the theorem says this: If $y_i^* > 0$, then the $i^{th}$ constraint is binding in Primal $\ \ \ (1)$ If the $i^{th}$ constraint in Primal is ...
1
vote
1answer
66 views

To show a closed convex set $S \subseteq R^n$ is bounded if and only if $S$ contains no rays.

I want to show that a closed convex set $S \subseteq R^n$ is bounded if and only if $S$ contains no rays. Where $r \in S$ is a ray of $S$ if $x \in S$ implies that $x+\mu r \in S$ for all $\mu \in ...
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
34 views

Constraints within a linear program?

I am doing a linear program problem about motor cars. I need to write a constraint to say that the stock for ten models of cars at the end of each month, is the initial stock for the next month? ...
0
votes
0answers
28 views

Find a set of points so that feasible region of a system is the Voronoi cell of these points

There's a set of inequalities in linear 3 dimensional space, with non-negative constraints. How do I find a set of points (S) such that the voronoi cell of a point from the set is the feasible region ...