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

learn more… | top users | synonyms

0
votes
1answer
35 views

Finding the dual of a LP

I am trying to find the dual of the following linear program. The primal LP's purpose is to find the lowest possible L1 (sum of absolute values of coefficients) of a degree $d$ polynomial such that (1)...
2
votes
1answer
22 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 ...
0
votes
1answer
25 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 ...
-1
votes
1answer
79 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
0answers
17 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
0answers
40 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 ...
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 ...
1
vote
1answer
25 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 \end{...
1
vote
0answers
26 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
23 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
2answers
70 views

Find the optimal solution without going through the ERO's

All I got is that $$12y_1 + 7y_2 + 10y_3 = 2(0) + 4(10.4) + 3(0) + 1(0.4)$$ and $y_2 = 0$ because $x_6$ is in basis. How do I find $y_1$ and $y_3$ without going through the simplex method? I took ...
0
votes
0answers
57 views

optimal, infeasible, degenerate solutions

Note that $c_i$'s in the $z_j-c_j$ row are not coefficients of the $x_i$'s. I use instead: $r_1, r_2, r_3$. I'm assuming there's a non-negativity constraint. we need to state necessary ...
0
votes
1answer
38 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 \{0, ...
12
votes
3answers
283 views

Variable leaving basis in linear programming - when does it happen?

In the simplex algorithm in linear programming, what are conditions for a variable to leave a basis (not necessarily basis for the/an optimal solution)? I'm supposed to list as many sufficient and ...
1
vote
0answers
23 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\} ...
0
votes
1answer
35 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? I'...
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 ...
1
vote
1answer
69 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 R_{...
0
votes
1answer
87 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 ...
0
votes
0answers
27 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
0answers
21 views

Linear program solved with Simplex out of given bound

I believe to be missing something important in the Simplex algorithm because it goes beyond the given objective. Let be the following linear programming program: \begin{cases} \max Z(x,y,z)=&x&...
0
votes
1answer
28 views

How to formulate this Linear Programming Problem?

A business executive has the option to invest money in two plans: Plan A guarantees that each dollar invested will earn $0.70$ dollar a year later, and plan B guarantees that each dollar invested ...
0
votes
1answer
21 views

How to initialise a linear program?

Good morning! I'm absolutely new to linear programing since this year, yet I'm struggling to understand and learn. I was given during my lecture that to chose the initial vertice we had to determine ...
1
vote
0answers
21 views

Convergence rate for such modified method of steepest descent

We consider only the quadratic case. $f(x,y)=\frac{1}{2}x^TQx. $ And suppose we can choose $x_0$ to make $g_0$ in the span of its eigenvectors $e_i$, where $g_k=Qx_k$, being the gradient in each ...
0
votes
1answer
47 views

Interpreting optimal tableau in manufacturing

What I tried: 3a1 Make $c_3$ greater than the current $z_3$ so any value greater than 20/3? 3a2 I just do EROs to make the $x_3$ column into $[0, 0, 1]^T$ ? 3b $c_1 \ge 10$? idk 3c If we ...
1
vote
1answer
26 views

How to find a realisable starting point with the Simplex algorithm?

Let be the following linear program: \begin{equation*} \begin{cases} \max f(x_1,x_2) =3x_1+2x_2\\ 5x_1 + 2x_2 \ge 8\\ x_1 - x_2 \le 1\\ x_1 + x_2 \le 3\\ ...
0
votes
0answers
16 views

How to find the minimum index value of a binary variable for which the value is one?

Let $Y_{i,j,k}$ be a binary variable, $X_{i,k}$ be a continuous variable and $Z_{j,k}$ is a constant. 1)For every $i,k$ need to find the minimum $j'$ such that $Y_{i,j',k} = 1$. 2)For every $i,j',k$ ...
2
votes
0answers
34 views

What is the subscript of the max notiation stating?

I am a physics graduate interested in moving into the field of AI. My knowledge of pure maths is limited, leading to difficulties in even understanding notation in the subject. I do not understand ...
0
votes
0answers
19 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 \mathbf{X}^T\mathbf{w}-\...
12
votes
1answer
170 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 ...
1
vote
1answer
23 views

the dual of the LP

$max \sum _{j=1}^nc_jx_j$ $\sum _{j=1}^na_jx_j\le b$ where $a_j, b$ are real numbers (not vectors) $x_j\ge 0$ for all $j$ Could you please help to write its dual? Attempt: $min \sum _{j=1}^nu_j*b$...
1
vote
1answer
40 views

Is dynamic addition of values to a set possible in Integer Linear Programming?

$X_{it}$ is a binary decision variable. Need to construct a set $V_t$ such that if $X_{it}$ = $1$ then i is an element of set $V_t$. Is it possible to formulate this in integer linear programming? if ...
0
votes
1answer
24 views

Transforming the sum of min functions into one min function with the aim of translating the max-min problem into the linear program

I have to solve the following optimization problem: $\text{For } x\in \mathbb{R}^+, \ \ \alpha, \beta, \omega_i, \pi_i \in \mathbb{R}^+, \ i \in \{ 1, \dots, s \}, \text{ and } \sum_{i=1}^s \pi_i=...
0
votes
0answers
25 views

RINS: start - incumbent and relaxation solution have all different values

RINS: Relaxation induced neighborhood search; introduced by Danna et.al in 2010 this paper. I wanted to design an example how the RINS algorithm works to make sure that I have it completly understood ...
1
vote
0answers
8 views

Symmetric Roles of the two problem solutions in RINS

Currently, I am reading the paper "Exploring relaxation induced neighborhood to improve MIP solutions by Danna et.al. from 2004 and they are talking about a symmetric role of incumbent and the relaxed ...
0
votes
0answers
20 views

Design an algorithm to solve this LP

$max \sum _{j=1}^nc_jx_j$ $\sum _{j=1}^na_jx_j\le b$ where $a_j,b$ are real numbers (not vectors) $x_j\ge 0$ for all $j$ How to design an algorihm to solve this LP? Attempt: I have tried to ...
0
votes
0answers
17 views

If $\text{min}\{C^Tx:Ax=b,x \geq 0\}$ has a finite optimal solution then $\text{min}\{C^Tx:Ax=b',x \geq 0\}$ cannot be unbounded proof?

Here is the question I'm working with If $\text{min}\{C^Tx:Ax=b,x \geq 0\}$ has a finite optimal solution then $\text{min}\{C^Tx:Ax=b',x \geq 0\}$ cannot be unbounded no matter how large $b'$ is. I ...
0
votes
0answers
24 views

How to convert a linear program into canonical form?

I'm having trouble converting this linear program into canonical form. A linear program in canonical form permits only <= constraints, requires that the objective function be maximized, and ...
1
vote
1answer
49 views

Is this fact true or how to make it true?

Let $a_1,\ldots,a_n, A$ be positive real numbers and $k$ a positive integer. Is this correct? If we have $$\sum_{i=1}^n\ln\left(1+a_i\right)\geq k\ln\left(1+A/k\right),$$ and $$\sum_{i=1}^na_i\leq A,$$...
1
vote
0answers
41 views

Strict inequalities in an LP problem

So I have to formulate an LP problem out of this scenario converting 3 variables into just 2 variables in order to use the graphical method. I guess I do that by using the demand constraint: I ...
0
votes
0answers
29 views

Use graphical analysis to solve a parameterised LP problem

For $c < 0$, we have no feasible solutions and hence no optimal solutions. For $c=0$, our only feasible solution is $z=0$ obtained by $(0,0)$. For $c > 0$, well... I graphed the constraints ...
1
vote
1answer
45 views

Finding a linear programming model

Question: Acme manufacturing company has contracted to deliver home windows over the next 6 months. The demands for each month are 100, 250, 190, 140, 220, and 110 units, respectively. Production ...
0
votes
1answer
80 views

Linear Programming #3

A small tailors’ company wants to use at least 130 yards of fabric to sew evening skirts and dresses. A dress requires 4 yards of fabric and the production of a skirt will need 3 yards. Research shows ...
0
votes
1answer
82 views

Linear Programming Word Problems (#2)

A small tailors’ company wants to use at least 130 yards of fabric to sew evening skirts and dresses. A dress requires 4 yards of fabric and the production of a skirt will need 3 yards. Research shows ...
1
vote
1answer
58 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 lb ...
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
96 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
39 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 ...