Questions tagged [linear-programming]

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

Filter by
Sorted by
Tagged with
0
votes
0answers
28 views

Prove that any hyperplane and halfspace in $\mathbb{R}^n$ is a convex set

$a)$ Prove that a hyperplane in $\mathbb{R}^n$ is convex. Recall that a hyperplane is a set of the form $\{x\in\mathbb{R}:a^Tx= b\}$ for some vector $a$ and scalar $b$. $b)$ Prove that a ...
1
vote
1answer
36 views

Expressing a norm as an LP

Let $\mathbf{x}\in \mathbb{R}^n$, and let $\|\mathbf{x}\|_L$ be the sum of the $L$ largest absolute components of $\mathbf{x}$. That is to say, write the (absolute values of) components of $\mathbf{x}$...
0
votes
0answers
21 views

Maximize a variable bounded by a convex hull

Consider the optimization problem: $$\max \theta$$ $$\text{s.t. }\theta\leq min\{A\alpha\}$$ $$\sum_{i=1}^{k} \alpha_i =1$$ $$\alpha_i\geq 0 \text{ for }\forall i$$ where $\alpha=[\...
0
votes
0answers
13 views

Wording for programming equation system- Get all possible results for combinations

I stumbled upon a real life example regarding possible combinations for different sets of items (food groups for diets) that then would be programmed to generate an automatic lists of recipes based on ...
1
vote
0answers
17 views

Should I factor in time as a parameter or a variable in a scheduling problem with MILP?

I am trying to formulate a problem that will spit out an optimal schedule for my tasks to be completed and I need help defining some of the variables. To keep the information confidential, I will ...
0
votes
1answer
54 views

Linear Program with Mutually Exclusive Variables - Best Method to Solve

So I'm pretty sure that its not possible to set up a linear-program that has non-binary mutually exclusive variables (but would love to be wrong here). It seems like it would be possible to solve the ...
0
votes
1answer
42 views

Standard Form of linear programming

How can we prove that all linear programming problem cannot be converted to the form below: \begin{array}{ll} \text{maximize} & c^T x \\ \text{subject to}& A x = b \\ \end{array} I think we ...
0
votes
0answers
7 views

Prove if $x,y$ are vectors and $A$ is a matrix then $\exists x$ st $x \le 0$ and $Ax \le b$ xor $\exists y$ st $A^Ty\ge 0, y\ge 0$ and $by<0$

I'm supposed to use the fundamental theorem of LP, weak duality and strong duality to prove this. Fundamental Theorem of LP: 1) If there's a feasible solution there's a basic feasible solution 2) ...
0
votes
1answer
72 views

Converting Standard form to Canonical form

This is what my lecturer says on standard and canonical forms: "Two particular forms of the linear programming problem are of interest for m equations in n unknowns. These are called the standard form,...
0
votes
1answer
51 views

Minimization problem with absolute value in objective function

Consider the following (piecewise linear) minimization problem where $(x,y) \in \mathbb{R}^2$. $$\begin{array}{ll} \text{minimize} & |x| + y\\ \text{subject to} & x + y = 2\\ & x \le ...
2
votes
0answers
222 views

Prove that a convex polytope has finitely many extreme points.

$a)$ Prove that a convex polytope has finitely many extreme points. $b)$ Prove that the unit disc $S:=\{x\in\mathbb{R}^2:x_1^2+x_2^2\le1\}$ is not a convex polytope. Hint : what are the ...
1
vote
1answer
70 views

Write LPP in canonical form

A health food store packages a nut sampler consisting of walnuts, pecans, and almonds. Suppose that each ounce of walnuts contains $\color{red}{\text{$12$ units of protein}}$ and $\color{blue}{\text{$...
3
votes
0answers
41 views

Showing a disc has infinitely many extreme points

EDIT: Stuck on a part of a problem for a Linear programming course. I want to show the unit disc is not a convex polytope and my strategy is to show that it has infinitely many extreme points. How ...
0
votes
1answer
30 views

A proof about the optimal values and extreme points [duplicate]

Show that if the optimal value of the objective function of a linear programming problem is attained at several extreme points, then it is also attained at any convex combination of these extreme ...
0
votes
0answers
38 views

Use the Extreme point theorem to find the maximized solution

Definition Extreme point A point $u$ in a convex set $S$ is called an extreme point of $S$ if it is not an interior point of any line segment in $S$. That is, $u$ is an extreme point of $S$ if ...
1
vote
2answers
30 views

How does $Ax = b$ define a feasible region of half spaces?

When a linear program is formulated like this: $\begin{align} \text{minimise}\quad &c^Tx\\ \text{subject to}\quad &Ax \ge b \end{align}$ With $c\in \mathbb{R}^{|x|}$, $A \in \mathbb{R}^{n \...
0
votes
0answers
21 views

Prove the half space of a polyhedron in $R^n$ is a polyhedron

Let $P$ be a polyhedron in $\Bbb R^n$, $a \in \Bbb R^n$ be a vector and $b \in \Bbb R$ be a scalar. Consider the set $Q= \{x \in P | {a^T} x \le b \}$. (a) Prove that $Q$ is also a polyhedron. (b) ...
0
votes
0answers
42 views

Graphical analysis and Visualization for LPP

$Q4.$Use graphical analysis to find the optimal solution(s) of the LPP a) Maximize $$3x+2y$$ subject to $$3x-4y\le11$$ $$x,y\ge0$$ $b)$ Maximize $$5x-7y$$ subject to $$x+...
0
votes
0answers
16 views

Chebyshev approximation to standard linear programming form

I'm looking for a way to write Chebyshev approximation in standard linear programming form, Let's say my Chebyshev approximation have the following for: $ min_{p,t} t $ s.t. $ -t1_T \le h - Fp \le ...
2
votes
0answers
42 views

continuity of lagrangian

Let $X,Y$ be normed vector spaces. Let $f$ be a linear continuous functional and $G:X\to Y$ is linear. By Kuhn-Tucker theorem, if $x_0$ minimize $f(x)$ subject to $G(x)\le 0$, then we can find $y^*\in ...
1
vote
1answer
50 views

A proof about feasible solution

$15.$ Consider the linear programming problem Maximize $$z=e^Tx$$ subject to $$Ax\le b$$ $$x\ge0$$ If $x_1$ and $x_2$ are feasible solutions, show that $$x=\frac{1}{3}x_1+\frac{2}{3}x_2$...
1
vote
0answers
16 views

linear programming issue

Hi I need help regarding a linear programming math problem. What I need is to formulate the equations. I tried this. But no idea whether the equations are correct. What I need to know is whether my ...
2
votes
0answers
56 views

What's the difference between GLPP and LPP

$a)$ Express the following optimization problem as a linear programming problem(LPP): $$\text{maximize }3x+3y-30$$$$\text{subject to }|x-2|+|y|\le5$$ Hint: you will need to express the ...
0
votes
0answers
30 views

Linear transformation over a set of linear inequalities

Let $A\in\mathbb{R}^{m \times n}$, $b\in\mathbb{R}^m$ such that $Ax\leq b$. Now let $\hat{x} = Tx$. What can be said about $A\hat{x}$? Concretely, is there an analytical way (without using $T^{-1}$) ...
0
votes
0answers
21 views

Scheduling Tasks with Non-Overlap & Precedent Requirements

Problem I want to optimize (complete in the shortest time possible) my morning routine with my family. There are steps that we have to do individually (ex. I shower), and there are steps we have to do ...
4
votes
1answer
146 views

Show that any linear function $f:\mathbb{R}^n\to\mathbb{R}$ is of the form $f(x)=a^Tx$ for some vector $a\in\mathbb{R^n}$.

$a)$ Let $a$ be a (column) vector in $\mathbb{R}^n$. Show that the function $f(x)=a^Tx$ is linear function from $\mathbb{R}^n$ to $\mathbb{R}$ $b)$ Show that any linear function $f:\mathbb{R}...
0
votes
0answers
31 views

A name for a specific type of optimization problem and solution

The optimization problem is as follows. Control variable : $x\in[a,b]$ Objective function : $xf(x)$ So the optimization problem is $$\max_{x\in[a,b]}xf(x).$$ What's special about $f$ is that $f$ ...
0
votes
1answer
56 views

A closed convex set which is bounded from below has extreme points in every supporting hyperplane.

(A proof from Linear Algebra by G.Hadley) Theorem III: A closed convex set which is bounded from below has extreme points in every supporting hyperplane. The convex set of feasible solutions to a ...
0
votes
1answer
42 views

Linearise a quadratic constraint to transform a quadratic program into a linear program

I am trying to define a Linear Program but one of my constraints is quadratic. The program looks like this: f: $\min \sum x_{ij}$ s.t. $\forall_i x_{ii} + \sum_{j}c_{ij}x_{ij}x_{jj} = 1$ $\forall_{...
0
votes
2answers
33 views

Feasible region unbounded

How do we prove that if a linear programming problem is unbounded, then its feasible region is necessarily an unbounded set as well? It kind of seems intuitive but how do I rigorously show this?
1
vote
1answer
54 views

Write the min-max model in the standard LP form

I was given two linear systems {$2x=1$, $x=1$} and I was told to write the min-max model. Which I hope I did correctly and got $|| Ax-b||$ = max {$||2x-1||, ||x-1||$} -> min. now it is asking me to ...
0
votes
0answers
20 views

Stochastic programming/uknown numbers

Here on the page 77 in the lines 4 and 5, I would like to understand how were cretaed the \$7 and \$15 numbers. It should be the net margin for $A$ and for $B$, but I do not see what these definitions ...
0
votes
0answers
18 views

Network flow and uncertainty in supply/demand

I am trying to learn how to study uncertainty in supply in a network flow problem. Specifically, I am using network simplex method on an undirected graph with a bunch of nodes with source/supply and a ...
1
vote
0answers
27 views

Existence of Basic Feasible Solution: Polyhedron in Standard Form

Exercise 2.6 Bertsimas Linear Optimization: Let $A_1,...A_n$ be a collection of vectors in $\mathbb R^m$. Let $$C=\sum_{i=1}^{n}{\lambda_{i} A_{i} \mid \lambda_1,..\lambda_n \geq 0}.$$ Show that any ...
2
votes
3answers
148 views

Why is Unit Circle Including Its Interior not a Polyhedron

I'm in a linear programming class and I'm trying to understand why the unit circle with its interior is not a polyhedron. I know there is a proof by contradiction that the unit circle not including ...
0
votes
0answers
66 views

Can linear programing be used in Model Predictive Control?

I'm trying to implement Model Predictive Control onto a small micro controller. I know that is not "possible", but I want to minimize the "unnecessary" tools that are avaiable inside "regular" Model ...
1
vote
2answers
20 views

Assume an LP has 2 optimal solutions $u$ and $v$. Show for any t in [0,1] that $tu+(1-t)v$ is also optimal

Considering an LP with: \begin{align} &\text{max}\ \ c\cdot x \\ &Ax\le b\\ & x\geq 0 \\ \end{align} Assume this LP has two optimal solutions $u$ and $v$. Show for any $t \in [0,1]$ ...
0
votes
1answer
49 views

3d permutation matrices

$8 \times 8$ permutation matrices correspond to patterns of 8 rooks on a chessboard with exactly 1 rook in each row or column, never 2. Consider patterns of $n^2$ "3d rooks" in an $n \times n \times ...
2
votes
1answer
50 views

Finding an optimal solution to a linear program among solutions of another

I had the following question on my last Algorithms test which I didn't know how to solve, and the the professor didn't agree to publish the solution. I would like to know the solution though, since it'...
0
votes
0answers
28 views

Stochastic linear programming using empirical distribution

I have a stochastic linear optimization problem where one of my parameters is random (and most likely from a continuous distribution). I'd like to solve the problem by 'discretizing' into many ...
0
votes
1answer
18 views

How did they get the standard form of this LP?

I'm confused to what method they are using to get the standard form of this LP? Why is there an "e" variable? I need help with this problem.
0
votes
2answers
34 views

Let $f_1$,$f_2$ be two convex functions on $R^n$. Show $\max[f_1(x),f_2(x)]$ is a convex function as well

I'm getting confused on how to prove this. I was thinking 2 points $x$ and $y$ that satisfy the definition of convex function $f((1-\lambda)x+\lambda y \le (1-\lambda)f(x)+\lambda f(y)$ where $\lambda ...
0
votes
1answer
20 views

Linear stochastic programming/easy formulas

I have a question about some stochastic linear programming formulas, namely (4.3),(4.4),(4.5) and (4,6) in the snippet below. I do not follow how was created the argument of $c$ in (4.3), the formula (...
0
votes
1answer
18 views

Linear programming problem's primal seems to contradict its dual

Given $A\in\mathbb{R}^{m\times n},\ B\in\mathbb{R}^{m\times m}, c\in\mathbb{R}^n, b, d\in\mathbb{R}^m$, $B$ nonsingular, I've been tasked with solving the following LP problem (denoted (P)): $$ \max_{...
0
votes
1answer
30 views

Linear Programming Production Process Constraint Relationship

Objective function is to maximize profit. Decision variables is how much qty of $C$ and $D$ to produce? Raw material can produce either $A$ or $B$. Product $C$ requires an input of qty $A$ and $\...
2
votes
0answers
55 views

Linear Program such that Simplex (w/ any pivot rule) takes exponential time?

I had this exam question last semester, and it's still bothering me: For every natural number $n$, you want an LP (not necessarily with $n$ inequalities) such that simplex cannot solve it in ...
1
vote
0answers
13 views

How to tell if linear programming dictionary is unbounded using ratios?

I don't really get how they got negative for the ratio 2/5. Is it because if they make $x3$ a leaving variable it'll become $x3$ = -5/2 + (3/2)$x1$? How does non-positive ratios make a problem ...
0
votes
1answer
28 views

Linear Program Modelling Coinset pay amount $k$

You are given a coinset ov values c1,...,cn and a target value of k you need to pay. For each i element {1,...,n} let ni be the number of coins of value ci in your wallet. You want to pay (or overpay) ...
-1
votes
1answer
34 views

Write IF THEN constraint in Linear Programming for Non Binary Decision Variable

$ x_{t} $ is a decision variable bounded by some constraints and $t=1,2,3..24$ If at some point in t, the value of $x_{t}$ changes then the value must not change for ATLEAST the next 3 hours. After ...
1
vote
0answers
44 views

What software can I use to express a polynomial as a sum of squares?

I have a 169 term degree 8 homogeneous polynomial in 14 variables that I believe can be expressed as a sum of 8 squares. I discovered the other day that methods exist for expressing a polynomial as a ...