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

learn more… | top users | synonyms

0
votes
0answers
47 views

Hungarian Method algorithm question. Dual solution.

I have included two images which I have to prove the next problem. The first image is the alternate(k) algorithm (alternate paths algorithm) and the second is the Hungarian Method algorithm. ...
1
vote
1answer
54 views

Linear Programming Duality Proof

I have really no idea where to go in this problem. This is from Bertsimas Introduction to Linear Optimization, Exercise 4.26. My teacher would like us to create a primal and dual LP to solve the ...
2
votes
1answer
30 views

Is there a connection between duality in linear programming and duality in functional analysis?

In linear programming we optimize a linear function which is constrained by linear inequalities or linear equalities. Under some conditions you can rewrite the problem to the dual problem, so that you ...
0
votes
1answer
27 views

Linear programming with quadratic constraints

I have a given set of variables: $x_1,y_1,x_2,y_2,x_3,y_3$ The objective function is to minimize the sum of these with quadratic equality constraints: $y_1(x_1+x_2+x_3)$=0 $y_2(x_2+x_3)$=0 ...
1
vote
1answer
27 views

How to set up linear programming problem for maximizing score of various combinations?

I have a sample data set that looks like this: x y w 1 1 5 1 2 1 6 2 3 1 7 3 4 2 8 4 5 2 7 5 6 3 5 6 7 4 6 7 8 4 5 8 x and ...
0
votes
1answer
39 views

Formulate the dual problem for primal problem with absolute value constraint

Let $y \in R$, the goal is to find the dual problem to: $$\min y\\ s.t. |y| \leq 0$$ The lagrangian of the problem is: $$L(y, \lambda) = y + \lambda|y|$$ The dual function is: $$g(\lambda) = ...
1
vote
1answer
25 views

What is $ {z_j} $ in this tableau? (Simplex algorithm)

I've hightlighted the section in the tableau I don't understand. Clearly the 28 comes from plugging in the 4 and 2 in the objective function but where do the other numbers in the row come from? Any ...
1
vote
1answer
40 views

Transportation problems

i'm a master student at the deparment of statistics. And i will prepare a presentation on transportation problems in the course of optimization (or linear programming / mathematical programming) I ...
0
votes
2answers
27 views

How to minimize given functional

I confronted the next problem: we have certain values $\psi_1, \psi_2, \psi_3$ in 3 points $x_1, x_2, x_3$, also we have a general functtion with 2 undefined coefficients ($A,x_0$): ...
4
votes
1answer
42 views

How to setup the correct transportation tableu for this Caterer Problem?

The problem said: A caterer must supply 110 napkins on Monday, 90 on Tuesday, 130 on Wednesday, and 170 on Thursday. The caterer initially has no napkins on hand. New napkins can be bought for ...
0
votes
1answer
32 views

How to solve this linear programming problem?

Basically I have to minimize a linear equation with a bunch of $\leq$ constraints. I know only how to use simplex method to maximise the equation with the $\leq$ constraints. How can I use the ...
0
votes
0answers
26 views

Dual of chromatic number problem

It is well known that every linear minimization problem has a dual maximization problem. For example, the minimum vertex covering problem and the maximum matching problem are primal-dual. I am ...
0
votes
1answer
53 views

Linear programming. Find the maximum number of vertex disjoint paths in a directed graph.

How I can write like an objective function subject to its corresponding restriccions the next problem? (max "...") subject to ($\sum "..." - \sum "..."=0$ $\forall$ "...") I have a directed graph ...
0
votes
1answer
23 views

Is $x^TAy$ convex or concave, for $x,y$ not identically equivalent?

It is well known if we had something like: $f(x) = x^TQx$ A quadratic form, is positive semidefinite of $Q$ is positive semidefinite How is the structure of $f(x,y) = x^TQy$ analyzed? i.e. what ...
1
vote
0answers
19 views

Algorithm for calculating the nearest Euclidean matrix with constraints

In the area of symmetrizing the atom positions of a molecule, one runs typically into the so called Euclidean distance matrix problem. After symmetrization a distance matrix $D$ which is symmetric ...
0
votes
1answer
19 views

The cost function in the Weighted Bipartite Matching Problem (a.k.a the Assignment Problem)

In the definition of this problem, the weight/cost function generally takes value in $\mathbb{Z}$ (or sometimes $\mathbb{Q}$). This is what I observed from some books (e.g. "Combinatorial ...
0
votes
1answer
51 views

Big M formulation of an indicator constraint.

This is my first question here. I am working on a binary LP wherein I want to turn on a variable when a condition is met else make it zero. I want to share my formulation with you and need your help ...
1
vote
1answer
60 views

How to solve this linear program?

I was given the following linear program with the supposed answers to be $x_1 = 45/103$, $x_2 = 27/103$, $x_3 = 31/103$. Howerver, I tried to solve it using the Simplex Algorithm with no success, ...
0
votes
1answer
36 views

vogel approximation and dummy column

I am solving a linear programming problem for transportation and have to use the VAM method, vogel approximation. As the problem is unbalanced, I know that I have to add a dummy column to balance it. ...
1
vote
0answers
22 views

Show that the dual of the dual is the primal for a min problem

I have LP of the form min $c^tx$ such that $Ax\leq b$, there is no restricition on $x$. I need to show the dual of the dual of this LP is the original LP. To get the dual of my LP, I need to put it ...
0
votes
2answers
95 views

How can I linearize the distance from two points?

I'm studying Operations Resarch and the professor give us the following problem: • There is a 10*10 matrix in which there are 20 villages on random coordinates. • We have to drop two supply packages ...
0
votes
1answer
43 views

Is mathematical programming an analytical or numerical technique?

Is linear programming, mixed-integer programming, integer programming, nonlinear programming, etc. numerical or analytical techniques? I always thought they were numerical methods because you can't ...
0
votes
0answers
30 views

Sequential linear programming

I need some help starting this problem. I'm not sure how to put this in SLP form from the general form. And, how do I use the X^0 vector in this? For the optimization problem below, put the problem ...
1
vote
1answer
58 views

Particle swarm optimization

I don't know where to start. Like, I don't know how to plug the info into the algorithm. Show two iterations of particle swarm optimization (neighborhood approach) method. Mathematically show two ...
1
vote
1answer
28 views

Separable linear programs

Assume, we have two distinct LPs: \begin{equation*} \begin{aligned} & \text{min}_{x_1} & & c_1^Tx_1 \\ & \text{subject to} & & A_1x_1 = b \\ & & & x_1 \geq 0 \\ ...
0
votes
3answers
44 views

modeling a set S as a mixed integer linear programming problem

This is actually a homework question and I am very much stumped. I have to model the following set as an MILP S = {x,y∈R| |x| + |y| = 1} There is no need for an objective function but an arbitrary ...
0
votes
1answer
28 views

Solving a PL using complementary slackness conditions - dual

I have to find the optimal solution of the dual with the complementary slackness conditions. This is the primal: $\max \space\space z= x_1 - 2x_2 $ $\text{s.t.}\space\space\space\space\space ...
1
vote
1answer
23 views

Is $2n$ the smallest number of halfspaces to determine a segment in $\mathbb{R}^n$?

I proved that a segment in $\mathbb{R}^n$ is a polyhedron, and it is determined by $2n$ halfspaces. My question follows: Is $2n$ the smallest number of halfspaces to determine a segment in ...
1
vote
0answers
39 views

Projection of a convex set in $\mathbb R^n$ onto $\mathbb R^2$

Suppose $A$ is an $n\times n$ matrix and $b$ is an $n\times 1$ column vector. $$X=\{ x\in \mathbb R^n: A x\leq b\}$$ Is it possible to compute the projection of $X$ on $(x_1,x_2) $ ...
0
votes
1answer
33 views

Progressive Solving of Linear Programming Problem

Suppose you solve a linear optimisation problem: **Maximize:** 2a + 3b + 4c **Subject to:** 3a + 5b + 2c <= 5 8a + 3b + 1c <= 8 C = 0 And then remove the C ...
0
votes
1answer
82 views

Solve $\max_{x_1,x_2,x_3} \{ \alpha \min \{a x_1,b x_2,c x_3\}\}$ s.t. $p_1 x_1 + p_2 x_2 + p_3 x_3 = w$

Consider the objective function \begin{equation*} f(x_1,x_2,x_3)=\alpha \min \{a x_1,b x_2,c x_3\} \end{equation*} where $\alpha, a, b, c \in \mathbb{R}$ are arbitrary constants. We wish to maximize ...
0
votes
0answers
14 views

Construct a Primal-Dual Linear Programming Pair such that the feasible domains of both are non-empty and bounded

I've been studying duality and I've been trying to construct primal-dual pairs that satisfy specific properties. I'm wondering if they can both have bounded feasible domains?
0
votes
1answer
256 views

How many beers can be bought (using exchanges) starting with $n?

This is an extension/generalization of this question. Suppose $2 can buy 1 bottle of beer. 4 bottle caps can be exchanged for 1 bottle of beer. 2 empty bottles can be exchanged for 1 bottle of ...
1
vote
0answers
31 views

Ex. 1.11 in “Linear Optimization” by Bertsimas, Tsitsiklis

I'm trying to follow the syllabus of 6-251j at MIT OCW and need to understand whether I'm doing fine with the exercises. This is what Ex. 1.11 says: Suppose that there are $N$ available ...
0
votes
1answer
19 views

Integer Programming Problem - Machines To Products

A man is trying to decide how he can assign his five machines to four products in order to maximize output. The estimated output per day for each machine is shown and reflect its productivity for each ...
1
vote
1answer
49 views

Linear Programming Problem Exercise.

A firm has to transport $1200$ packages using large vans which can carry $200$ packages each and small vans which can take $80$ packages each.The cost for engaging each large van is Rs $ 400$ and each ...
0
votes
0answers
10 views

Linear Program for the maximal radius of an insphere inside a simplex

We are given $n$ linear inequalities in a $d$-dimensional space, i.e. $a_i^T x \leq b_i$ for $i=1, \dotsc, n$, where $a_i^T x = \sum_{j=1}^d a_{ij} x_j$. Now we are interested in not only solving ...
0
votes
1answer
18 views

Finding feasible solution s.t. value of objective function is greater than $248$.

I was asked the following question in examination : Using the simplex method ,verify that following problem is unbounded and hence find a feasible solution for which the value of the ...
1
vote
1answer
74 views

Simplex method - multiple optimal solutions?

I have to solve this optimization problem: $\min \space\space z= x_1 - x_2 + 3x_3 $ $\text{s.t.}\space\space x_1-x_2+x_3-x_4=2$ $\space\space\space\space\space\space\space\space\space ...
0
votes
0answers
16 views

Using the simplex algorithm to measure sensitivity of objective function

Say I use the Simplex algorithm to solve a standard LP problem. I know that the last tableau's reduced cost coefficients tell me how much I need to increase the coefficient of a variable before it ...
2
votes
2answers
63 views

Linear Programming Model (or IP) - Staff Allocation

A retailer is trying to decide how best to assign its 3 staff to two internal departments in order to maximize sales. The estimated sales revenues per day for each staff member are shown and reflect ...
0
votes
1answer
38 views

Farkas with strict inequalities

I have proven the following result. Let $a_i \in \mathbb{R}^n$ for $i = 1, \ldots, m$. Then precisely one of the following statements is true. $$\text{(1) } c^t x < 0, \: a^t_i x \leq 0 \text{ ...
0
votes
0answers
30 views

dual when the primal is generic

Suppose to have a generic instance of the max-flow problem. Given a graph G=(N,A) $ \max \sum_{si \in A} f_{si} $ s.t. $\sum_{ij \in A} f_{ij} $ - $\sum_{ji \in A} f_{ji}$=0 $\forall i ...
1
vote
0answers
31 views

Proof of Stiemke's Theorem via Dubovitskii–Milyutin

Prove that the system $$\sum_{i=1}^{m} x_i a_i = 0, x_i > 0, i = 1, . . . , m,$$ has no solution if and only if the system $$<a_i , y> ≤ 0, i = 1, . . . , m,$$ not all zero has a solution. ...
1
vote
3answers
103 views

Conditional Constraints in Linear Programming

My variables are [$x_1,x_2,x_3,x_4,x_5,x_6,x_7,x_8$]. All are continuous variables within the range of $[0,1]$. I want to impose a conditional constraint which is as follows: if $x_6 \gt 0$ then ...
-1
votes
2answers
29 views

Programmatically derive a matrix form of quadratic equation [closed]

Is there a way to do that? For example from this equation: To this matrix form: We especially would like to get thos matrices circled-red. This is the code I have at the moment: ...
0
votes
0answers
113 views

Simplex Method and Unrestricted Variables

I was hoping someone here could explain this issue: say you are working with a set of linear equations in standard form ($a_1 x_1 + a_2 x_2 + a_3 x_3 + \ldots + a_n x_n= c$ where $c$ is the constant), ...
0
votes
0answers
23 views

KKT condition and linear program

Since all linear program all convex, and the Slater's condition always hold for linear programs. Is it always possible to solve the linear programs with KKT conditions? because it will convert the ...
1
vote
0answers
10 views

$j$-fold summation

I need a fast way (closed form would be better) to calculate $ S=\sum_{a_{1}=1}^{a_{1}=c}\sum_{a_{2}=a_{1}}^{a_{2}=c}\dots\sum_{a_{j}=a_{j-1}}^{a_{j}=c}1$. I derived this from $S=\sum_{a_{1}\leq ...
0
votes
0answers
25 views

Probabilistic methods that deals with problem solved by linear programming

Let's say we have a problem that is typically solved using linear-programming. What are the probabilistic models generally used to solve the same problem?