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

learn more… | top users | synonyms

2
votes
2answers
29 views

Formulation of Linear Programming problem?

I want to maximise the function: $$l(\beta,\sigma,\alpha) = -n\log(\sigma) - \frac{1}{\sigma} A(\alpha)\vert{\bf y}-{\bf X}\beta\vert,$$ where $\vert \cdot \vert $ represents the entry-wise absolute ...
1
vote
0answers
54 views

How to solve this using computer.?

Given $B = \begin{pmatrix} 0.3 & 0 \\ 0 & 0.4 \\ \end{pmatrix}$, and $\pi = \begin{pmatrix}0.4\\0.6\end{pmatrix} $, I need to find the elements of the stochastic matrix (the rows sum to ...
2
votes
1answer
39 views

Simplex Method: simplifying constraints

In my Computer Science class we've been exploring the Simplex Method and the applications it has with discovering optimal solutions. I've loved the challenge how much easier it makes finding solutions ...
1
vote
1answer
23 views

Changing a linear map such that given properties are satisfied

We are given $\{v_1, \dots, v_s\} \subseteq \mathbb{R}^n$, all with the same euclidean norm, say $\|v_i\| = \sqrt{(v_i^{(1)})^2 + \dots + (v_i^{(n)})^2} = 1$. Let's also assume $v_i \notin ...
0
votes
1answer
17 views

Optimalization, plan comparision

Let's say there are two tariff plan options of a provider offering internet access and landline telephony. Option 1: DSL flatrate, landline flatrate : 29,95 \$ Option 2: DSL flatrate: 24,95 \$ , ...
0
votes
0answers
30 views

Transforming into a convex program

$\max c^Tx$ $s.t. xy = a, \quad x \le b, \quad L \le y \le H$ Is there a way to transform this problem into a convex problem? $a,b,L,H$ are constants. $x,y$ are optimization variables.
1
vote
0answers
24 views

Dantzig-Wolfe Decomposition

While reading revised simplex method, I came to know about Datnzig-Wolfe Decompostion. Can you please explain whats the connection here ?
0
votes
0answers
28 views

Linear Programming $\boldsymbol{c}^T \boldsymbol{x}$ s.t. $\boldsymbol{Ax} = \boldsymbol{b}$

Prove for the linear programming \begin{equation} \left\{ \begin{array}{cc} min & \boldsymbol{c}^T \boldsymbol{x} \\ s.t. & \boldsymbol{Ax} = \boldsymbol{b} \end{array} \right. ...
1
vote
0answers
27 views

Linear program of 0-1 knapsack problem and proof of integer

I have some questions about the knapsack problem. How can the 0-1 knapsack problem described as a linear program? How to proof that the solution of the 0-1 knapsack problem are integer? (I'm ...
1
vote
1answer
40 views

Linear optimization problem with additional constant cost for non-zero variables

I have a linear optimization problem with integer variables of the form minimize $a_1 x_1 + ... + a_n x_n$ under a set of constraints Bounds for each variable $a_i \le constant_i$ Bounds for ...
0
votes
0answers
31 views

Feasible set for linear system with linear constraints

I have a linear underdetermined system $Ax = b$ with constraints $0 \le x \le 1$. Matrix $A \in \mathbf{R}^{n \times m}$ with $n < m$, elements of which are either $0$ or $1$, and sum of each ...
0
votes
0answers
37 views

how to solve a simplex with n variables

I don't know how to resolve a simplex with n variables I have this primal problem \begin{cases} \text{min}& z=-x_1 - x_2 -... - x_n\\ &a_1x_1 + a_2x_2 +... + a_nx_n \le 1\\ &x_1... ...
1
vote
0answers
33 views

A System of Inequalites arising from the Divisors of a Number, Showing Its Non-Solvability

Let $n$ be a natural number. Denote by $d(n)$ the number of divisors of $n$, i.e. with the notation from Wikipedia:Divisor Function we have $d(n) = \sigma_0(n)$. Suppose we have the $d(n) - 2$ ...
0
votes
1answer
223 views

How to test if a feasible solution is optimal - Complementary Slackness Theorem - Linear Programming

I have this linear program $$\begin{cases} \text{max }z=&5x_1+7x_2-3x_3\\ &2x_1+4x_2-2x_3&\le8\\ &-x_1+x_2+2x_3&\le10\\ &x_1+2x_2-x_3&\le6\\ &x_1,\,x_2,\,x_3\ge0 ...
0
votes
0answers
22 views

Interpretation of the dual of shortest path problem

I am trying to find an interpretation of the dual of shortest path problem of the form: $ maximze \; y_s - y_t$ subject to $y_i - y_j \leq c_{ij}$ $y_i$ are unrestricted, $c_{ij}$ being the cost ...
0
votes
0answers
17 views

Am I understanding this question correctly? Linear programing

A company produces and sells two products A and B. Let x denote the number of items of product A and let y denote the number of products of product B. The profit is DKK 30 per unit of product A and ...
0
votes
1answer
65 views

If we start with a feasible tableau in simplex method, are we basically generating a different feasible point in every pivot step?

This is a true and false question. The actual question reads: "In solving a linear program by the simplex method, starting with a feasible tableau, a different feasible point is generated after every ...
0
votes
0answers
10 views

How to test if a set of underdetermined equations have solution in a particular region?

For a underdetermined system $A\cdot x = b$ where $A$ is a $m \times n$ matrix with $m<n$, how to test if it has a solution within a specific region $\{ x | lb<x_i<ub \}$? Basically I have ...
0
votes
1answer
25 views

finding a plane in R3 given 5 points

I have multiple vertices that I need to create a plane out of. What is a formula/method for having a plane that contains 5 points? I believe I could use just 3 and the other two will be included
2
votes
1answer
26 views

Matrix that doesn't lose zeros

I have a vector $\vec x$ with some entries that are zero, and I apply a linear transformation so that for some matrix $A$, $A \vec x$ = $\vec b$. I would like to find a matrix $A$ (or better yet, ...
0
votes
0answers
13 views

Give a solution set of a dodecahedron [duplicate]

Using basic inequalities, find a set of inequalities so that the set of all solutions is a dodecahedron with twelve pentagons for sides.
3
votes
1answer
19 views

linear programming and flow network

Here is the problem: I have hard time understanding the problem , what does it mean by "conservation factors" and how to approach the problem using linear programming. For what I understand, if a ...
0
votes
0answers
38 views

How can I find multiple solutions for a system of equations?

I'm writing a program for CheckIO.org that is supposed to return an array, $$ \begin{bmatrix} x\\ y\\ z \end {bmatrix} $$ , that satisfies the System of Equations $$ A \begin{bmatrix} x\\ y\\ z \end ...
0
votes
0answers
44 views

The set of all vectors satisfying $Ax\ge\vec{0}$

Consider a rectangle matrix $A\in\mathbb{R}^{m\times n}$ with $m\ge n$, and the set of all vectors $x\in\mathbb{R}^n$ satisfying $Ax\ge\vec{0}$. I note this set is closed under multiplication by a ...
0
votes
0answers
27 views

Uniqueness of Solution in infinite linear programming

I would like to ask about a sufficient condition under which a solution for an infinite linear programming is unique. In standard finite dimensional linear programmings, like $\min_x p\cdot x$ ...
0
votes
2answers
58 views

Setting up a linear programming word problem

Problem: A metalworking shop needs to cut at least 32 large disks and 219 small ones. There are three cutting patterns for the standard size metal rectangle. One cutting pattern produces two large ...
0
votes
1answer
35 views

How is the pivot chosen for the symbolic weights for the Cassowary algorithm?

I am trying to understand The Cassowary Linear Arithmetic Constraint Solving Algorithm, and I am having trouble understanding symbolic weights, starting in section 2.3. Working through the example, ...
1
vote
1answer
84 views

Linear Programming - deriving the Dual of the Primal

I've the following linear programming problem: This is the LP representation of the uncapacitated facility location problem. This is the dual representation of this problem: My question is how ...
0
votes
0answers
7 views

Linear Programming Neighborhood Problem 2

Suppose we are given a set of 2n integers and we wish to partition into 2 sets $S_1$ and $S_2$ so that |$S_1$|=|$S_2$| and so that sum of number in $S_1$ is as close to sum of numbers in $S_2$.Let ...
0
votes
0answers
21 views

Linear Programming Neighbourhood problem

In the n-city TSP what is the cardinality of $N_2(t)$ , the neighborhood of tour t determined by 2 change? What is the cardinality of $N_3(t)$?
0
votes
1answer
211 views

Primal feasible solution implies Dual optimal solution?

Every feasible solution of P puts an upper(or lower, depending on whether it is a maximization or minimization problem) bound on the optimal solution of D(assuming of course that D has a feasible ...
0
votes
1answer
55 views

Mixed Integer Linear Programming: Construction Rods

I have an interesting problem involving linear programming. The problem is the following, I have 4 different kinds of rods (rod sized found in the local market): 9m rod 11m rod 12m rod 15m rod ...
0
votes
1answer
18 views

Conditions for a LP to be integral

What are the conditions to be met by a LP that allows to infer that its optimum solution will be integral? Is total unimodularity a necessary and/or sufficient condition? What if all variables are ...
0
votes
1answer
41 views

LP Word Problem Construction

I am having difficulty constructing the constraints on a word problem as follows: The Brite-lite Company receives an order for 78 floor lamps, 198 dresser lamps, and 214 table lamps from condoski ...
0
votes
0answers
81 views

Indicator Variable, Mixed Integer Linear Programming

Assume $x$ is a real variable, and $0\leq x \leq1$. Besides, $y$ is a binary random variable. I need a linear program that: if $y$ is $1$: $x>0$, if $y$ is $0$: $x=0$ I know the following ...
1
vote
1answer
25 views

Solving a linear program using just one call to a procedure that gives a feasible solution.

Suppose we have some procedure $F$ which takes any set of linear constraints and either returns either infeasible or returns a vector satisfying these constraints. If we now take a linear program ...
0
votes
1answer
49 views

linear programming problem solving

I have written in lp solve and obtain the solution of 0.58 highqualitymeat and 0.41 lowqualitymeat the thing that confuses is doing it through a graph as: let x be high quality meat and y be low ...
0
votes
0answers
26 views

Linear programming and complementary slackness

If there's a given basic solution $ A = (x,w)$ for the primal problem (where $x$ are decision variables and $w$ are slacks), I can determine the dual variables $y$ and slacks $z$ associated with B.S. ...
4
votes
1answer
37 views

Maximize $Z=-x+2y$ given $x\geq 3,\ x+y\geq 5,\ x+2y\geq 6,\ y\geq 0$

I am a highschool senior that's new to this topic. So, apologies for my lack of knowledge and misconceptions. The proof of the theory of this chapter is beyond the scope of my textbook, so that may be ...
0
votes
1answer
29 views

Linear Programming:What combination of two loams to minimize cost

I am fairly new to linear programming so simplification would be helpful.Came across a certain question and unfortunately no answer for it at the back of the book. The question is adopted from a book ...
0
votes
2answers
52 views

Prove linear program is unbounded

So I need help on my homework (I feel like a 10 year old). The exercise goes like this: Prove algebraically that the following program is unbounded: Max: $x_1 - x_2$ Constraints: $-2x_1 + x_2 ...
2
votes
1answer
265 views

Lemke-Howson pivoting in degenerate bimatrix games

I'm working on an implementation of the Lemke-Howson algorithm for finding Mixed Nash Equilibria of bimatrix games, and I'm running into a roadblock when the algorithm is fed a degenerate game. For ...
0
votes
0answers
31 views

Feasibility Sets for Integer Program

I have two set of constraints defining feasibility sets $A$ and $A'$ of a mixed integer program. $x_{i}, y_{ij}$ are continuous positive variables, $a_{ij}, b_{ij}, c_{ij}, d_j$ are known ...
1
vote
1answer
66 views

A linear program for maximizing a fraction

Given $\lambda_1,\ldots,\lambda_n \geq 0$ and an $n\times n$ matrix $A$, I wish to maximize the ratio $$ \frac{\lambda_1x_1 + \cdots + \lambda_nx_n}{x_1+\cdots+x_n}, $$ where $x_1,\ldots,x_n \geq 0$ ...
0
votes
0answers
39 views

simplex algorithm with tableau

in the picture below you can see the tableau representation of a linear programm with a coefficient $b\in \mathbb{R}$. BV stands for basic variable. For which $b$ is $y_1=\frac{1}{2}, ...
2
votes
1answer
79 views

how Determine the maximum values of C.

how Determine the maximum values of C. my try is that : To graph the last two bounding lines, I'll want to put the equations into slope–intercept form. The bounding line corresponding to the 3rd ...
0
votes
1answer
28 views

LP program: does the decision variable coefficients affect the problem?

I just started reading up on linear programming by myself, and am a bit confused by the decision variable coefficients $c_j$, in the objective function $ \sum_j c_jx_j$. Do they matter? I mean, if ...
3
votes
1answer
83 views

What gambling/board game or real life thing can (surprisingly) be modelled as a linear programming problem?

So I've taken Linear Programming 101. I've read my textbook, took the test and all that, and - besides all the theory, the nice algebraic interpretations, etc - I've encountered a lot of textbook ...
1
vote
0answers
153 views

duality theory question

Let $A$ be a given $m$ x $n$ matrix, and $c\in R^n$ and $b\in R^m$ be given vectors. Use LP duality theory to show that if the problem $$\min\{x^Tx: Ax=b, x\geq0\}$$ has a finite optimal solution, ...
0
votes
0answers
44 views

extreme points and representing

$$X=\{(x_1,x_2)^T : x_1-x_2\leq3, 2x_1+x_2\leq 4, x_1\geq -3\}$$ Find all extreme points of $X$, and represent $x^*= {0\choose1}$ as a convex combination of those extreme points. I sketched it out ...