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

learn more… | top users | synonyms

0
votes
1answer
44 views

Polytopes defined by $x_i >=0, Ax = b$ are generic ? (Understanding simplex method)

Consider polytopes in $R^n$ defined by $x_i >= 0, Ax = b$, for $b > 0$. Assume $A$ is of full rank $r$ and $Ax=b$ has solutions. The following properties seems to be correct. I would be ...
0
votes
1answer
20 views

About Dual Simplex Method

I have a question about Dual Simplex Method (for minimization problem). While we are solving the method, when we obtain a non-negative $\bar b$, we stop the algortihm. But in addition to $\bar b ...
0
votes
0answers
29 views

Does this transformation of a problem into a Linear Programing normal form is correct?

An oil refinery produces four types of raw gasoline: alkylaten catalytic, striaght and isopentane. Two important characteristics of each gasoline are its performance number $PN$ and ints vapore ...
0
votes
1answer
35 views

Definition of Optimality test - Simplex method

To clarify, this is not a question about how to conduct test of optimality or about what is the test good for. Nor am I asking for mathematical proof supporting it. I am asking specifically for ...
0
votes
1answer
36 views

Maximise volume given inequality constraint on its dimensions without using Lagrange, KKT or Linear Programming

The problem (from Calculus for Business, Economics, Life Sciences and Social Sciences 12e): I found this and that, but they use Lagrange/KKT. What I tried: Girth $= 2w + 2h$ Maximise ...
0
votes
1answer
32 views

How to find what maximizes the total net profit?

A meat packing plant produces $480$ hams, $400$ pork bellies and $230$ picnic hams every day; each of these products can be either fresh or smoked. The total number of hams, bellies and picnics ...
0
votes
2answers
36 views

Help buying a calculator program [closed]

Is there an economical calculator program I can buy that will let me multiply and divide numbers in the hundreds of digits and show all of the digits?
0
votes
1answer
32 views

Basic and non basic variables in linear programming

I dont understand what are Basic and non basic variables,why we are talking them specially, what they have got to do with the rank of the coefficient matrix and augmented matrix ,and some deal with ...
0
votes
2answers
40 views

Operation Research: system of equations

I have a system of equations for my Operations Research class, and the book is solving them by using algebra. However, I think it would be easier to solve them using linear algebra, and will also ...
0
votes
1answer
18 views

Bounded feasible region condition

Suppose $M=\{x \in \mathbb{R}^n: Ax \ge b\}$ is nonempty and $x_0 \in M$. Prove that $M$ is unbounded, then there exists a vector $d \in \mathbb{R}^n$, such that $x_0+\lambda d \in M,\forall \lambda ...
1
vote
3answers
53 views

How do I graph Linear Programming questions?

So let's say I have the following constraints: $2a + 3b \leq 30$ $a + b \leq 15$ $a \geq 0$ $b \geq 0$ (I just made this problem up, so I'm not sure if it may make any sense when I graph it.) ...
1
vote
3answers
45 views

Minimum Enclosing Ellipsoid To Maximal Enclosed Ellipsoid

Given a convex body $K$ and an ellipsoid of minimal volume which contains $K$, find the maximal ellipsoid contained in $K$. I have tried to multiply the matrix by 4 (since the eigenvalues are the ...
3
votes
1answer
84 views

Proof of Why Optimal Solutions Occur at Extreme Points

I'm taking my first class in Linear Programming. The book I am reading from is good in that it uses a lot of examples, but bad in that it provides few proofs. I need a proof for the following theorem. ...
0
votes
0answers
17 views

Creation of a cononical form

I wrote during a lecture that the canonical form of linear program was \begin{equation*} \begin{cases} \max C^Tx \\ Ax = b\\ x\ge 0 \end{cases} \end{equation*} But ...
0
votes
2answers
17 views

Constraint Set of Canonical Linear Programming Problem is Convex

I'm reading through my first textbook on linear optimization. The book states a theorem without proof and I'd like to understand why it's true. Glossary of Terms: Definition 1 The problem Maximize ...
2
votes
3answers
29 views

When to use which simplex algorithm?

in linear programming we use simplex method to find optimal solution. But I have also seen methods like Two Phase Method, Dual method, M-method. My question is, how do I know which method to use? For ...
0
votes
0answers
24 views

What is the definition for “equivalent linear programming problems”?

My question is in the title: How can we define exactly when two linear programming problems are equivalent? I used to see some definition such as "$B$ is equivalent to $A$ if $B$ is solvable, ...
0
votes
1answer
34 views

What is the dual problem in linear programming

In linear programming, Von Neumann define the dual of $$(I)\, \left\{ \begin{array}{rl} c^Tx &\to \min\\ Ax &\ge b\\ x&\ge 0 \end{array} \right. $$ is the problem $$(II)\, ...
1
vote
2answers
51 views

How to find the number of possible solutions of LP problems?

Let us assume that we have a linear optimization problem (LP) that has multiple optimal solutions. I would like to know if there is a solver or an algorithm that can provide the number of optimal ...
1
vote
0answers
15 views

An unfamiliar constraint in dual of LP for 'extreme point' optimal solution

I am trying to understand two-stage chance-constrained LP and reading a paper, which has a title "A branch-and-cut decomposition algorithm for solving chance-constrained mathematical programs with ...
0
votes
0answers
15 views

Transforming an array of equations as a canonical form?

Today was my first course of linear programing, I've just read again my notes and I'm not sure how does this array of equations actually transformed itself. \begin{equation*} \begin{cases} ...
1
vote
2answers
73 views

How can I solve the following linear program?

I want to find the answer for the following linear program. Max $v$ subject to $$v-5x_1-x_2 \le 0 $$ $$ v-x_1-4x_2 \le 0 $$ $$ v-2x_1-3x_2 \le 0 $$ $$ x_1+x_2 = 1 $$ $$ x_1, x_2 \ge 0 $$ $$ v \in R ...
1
vote
1answer
40 views

Apply Simplex method using M-method

I want to solve the following linear programming problem: $$\min (3y_1-y_2+2y_3) \\ 3y_1+2y_2-y_3 \leq 9 \\ 5y_2-y_3 \leq 1 \\ 4y_1-y_2 \geq 1 \\ y_1+y_2+y_3 \leq 3 \\ y_1, y_2, y_3 \geq 0$$ In this ...
1
vote
0answers
22 views

Find max min with linear programming

I need to solve $$ \max_x \min_y x^T M y $$ subject to $$ \sum_{i=1}^n y_i = 1, \sum_{j=1}^m x_j = 1,\\ x \geq 0, y \geq 0 $$ where $ M \in \mathbb{R}^{m\times n} $, $ x \in ...
4
votes
1answer
53 views

Exercise 2.27 from Bazaraa (LP)

Consider the system $Ax=b$ where $A=[a_1,a_2,...,a_n]$ is an $m \times n$ matrix of rank $m$. Let $x$ be any solution of this system. Starting with $x$, construct a basic solution. There is a hint ...
0
votes
1answer
47 views

How to derive the dual problem of Knapsack problem

Knapsack problem is $$ \text{max} \, v^Tx$$ $$ \text{s.t.} \, w^Tx \le W, \, \, 0\le x_i \le 1 \, \, (i=1,...,n)$$ This is equivalent to $$ \text{min} \, -v^Tx$$ $$ \text{s.t.} \, ...
0
votes
1answer
30 views

How can I derive the following dual problem?

Standard form of the linear program is $$\text{Min} \, C^{T} x$$ $$ s.t. Ax=b $$ $$x\ge 0$$ Dual is $$\text{Max}\, b^Ty$$ $$s.t. C-A^{T}y \ge 0$$ By using the above definition, I want to find ...
0
votes
1answer
40 views

Linear Programming Free Variables

I am using a book called Introduction to Operations Research. I'm not sure how to deal with free variables that are not constrained i.e. they could be positive or negative. I understand how any ...
1
vote
1answer
63 views

Integer programming, system of linear inequalities.

I am woring on a problem and I got these inequalities. $t_{01}+t_{11}+t_{21}\ge 4$ $t_{02}+t_{12}+t_{22}\ge 4$ $t_{10}+t_{11}+t_{12}\ge 4$ $t_{10}+t_{01}+t_{22}\ge 4$ $t_{10}+t_{02}+t_{21}\ge 4$ ...
0
votes
0answers
51 views

Integer programming model not working

I have to formulate an Integer programming model for the following using XPRESS; There are 10 items that need to assigned to 2 categories, A and B. Each item has a weight and 30 % of the weight is ...
2
votes
1answer
111 views

Simplex method - identity matrix

I want to solve the following linear programming problem: $$\min (5y_1-10y_2+7y_3-3y_4) \\ y_1+y_2+7y_3+2y_4=3 \\ -2y_1-y_2+3y_3+3y_4=2 \\ 2y_1+2y_2+8y_3+y_4=4 \\ y_i \geq 0, i \in \{ 1, \dots, 4 ...
0
votes
1answer
37 views

Refinery - Mathematical formulation of problem

In a refinery, two types of crude oil $T_1, T_2$ get mixed with two different procedures $R$ and $W$ and produce two types of petrol $P_1, P_2$ as shown at the following matrix: $\begin{matrix} ...
0
votes
1answer
18 views

Does {$a_2,a_3$} define a basic feasible solution for the Linear Program?

Question: Consider the following linear program \begin{equation} \begin{split} \text{Minimize} \ x_2 \\ \text{subject to} \ x_1+ x_2 +x_3 = 4\\ -2x_1+x_2 = -3\\ x_1,x_2,x_3 \ge 0 \\ \end{split} ...
0
votes
0answers
28 views

Integer program with known non-integer “solutions”

I have an integer program (IP) (see the formulation here for example) with the matrix $A$ being total unimodular. In this case, the linear program (LP) relaxation of the IP provides an integer ...
0
votes
0answers
28 views

Mixed-integer (Linear) Programming (MILP) standard/canonical form

Is there a standard or canonical form for mixed-integer (linear) programming problems? For linear programms the standard form is sometimes given by: $$ \max_{\boldsymbol x} \boldsymbol c^T \boldsymbol ...
1
vote
1answer
84 views

Wrong optimal solution

If we have a linear programming problem that is of the form as the following: The initial tableau is the following: Then we get this: $\begin{matrix} B & b & P_1 & P_2 & P_3 ...
0
votes
0answers
19 views

Percentage constraint for Integer programming model

Th question is as follows: There are 10 items that need to assigned to 2 categories, A and B. Each item has a weight and 30 % of the weight is allocated to A and the remaining 70% to B.The objective ...
1
vote
2answers
44 views

Minimising a convex set. Is set of solutions convex?

We are minimising a convex function on a non-empty set defined by linear constraints (equalities and inequalities). $X^O$ is the set of all optimal solutions and we assume it is non-empty. Is it true ...
1
vote
1answer
40 views

How to write an absolute value expression in linear programming?

My objective function for the Xpress-IVE (Mosel lang) model is minimize |a-b| where a and b the number of elements in the decision variables which are arrays. Since there is no function to ...
0
votes
0answers
23 views

All facets' coefficients contain only integers -1,0,1

Suppose a polytope $C\subset \mathbb R^{kl}$ is the $l$-product of $k-1$-simplex with extreme points containing coordinates $0$ or $1$ in each coordinate. A linear transformation is given by ...
0
votes
1answer
24 views

integer valued outer normal vectors

Suppose a bounded polyhedra $C$ is given by $$x\in \mathbb R^n: Ax\leq b$$ The matrix $A\in\mathbb R^{m\times n}$ contains only elements from $\{-1,0,1\}$, which implies the outer normal vectors of ...
3
votes
0answers
126 views

Linear programming and shortest path

Given the linear programming formulation of the shortest path problem: $$ \begin{align*} \min & \sum_{u,v \in A} c_{uv} x_{uv}\\ \text{s.t } & \sum_{v \in V^{+}(s)} x_{sv} - \sum_{v \in ...
0
votes
1answer
41 views

Problem in forming linear equations in Linear Programming problem

Here is the given question: A toy manufacturer produces two types of dolls; a basic version doll $A$ and a deluxe version doll $B$. Each doll of type $B$ takes twice as long to produce as one doll of ...
1
vote
3answers
189 views

What are common Mathematical Programming Languages out there?

I've seen the term used Mathematical Programming to describe a superset of: Linear programming Quadratic programming Nonlinear programming Mixed-integer programming Mixed-integer nonlinear ...
0
votes
1answer
46 views

Books on Multi-Commodity Minimum Cost Flow Problems

I'm searching for books on Multi-Commodity Minimum Cost Flow Problems (MCMCF) with theoretical aspects (solvability, optimality conditions, similar statements like in the case of Min Cost Flow,...). ...
1
vote
1answer
62 views

MILP optimization constraint formulation

I'm trying to find a sensible way to add constraint for my optimization problem. Lets assume we have binary decision variables $x_i\in\{0,1\}$ and two constraints \begin{align*} \sum\limits_{i=1}^n ...
0
votes
0answers
13 views

How to graph polygon rising at an angle in 3D space from the origin of the coordinate axes with shaded region on the $x$-$y$ plane?

I am trying to obtain a graph just like this one that visually shows that an objective function is maximised in z-direction at a certain point and where the “ground” of the graph is the $x$-$y$ ...
0
votes
1answer
30 views

How to represent 2D lines (i.e. on $x$ and $y-axis$) on a 3D graph using either Cartesian ($z=f(x,y)$) or Parametric $(x,y,z)=f(u,v)$

How to represent 2D lines (i.e. on $x$ and $y-axis$) on a 3D graph using either Cartesian ($z=f(x,y)$) or Parametric $(x,y,z)=f(u,v)$ Hi, I've been working on a Simplex problem and would like to ...
2
votes
2answers
92 views

Formulating equation for two mutual exclusive integers

I have a problem with formulating non-binary linear equation with mutual exclusivity \begin{cases} x_1 \gt 0, \quad \text{OR} &x_2 \gt 0 \\[2ex] x_1 + x_2 = 300 \end{cases} As the result I want ...
2
votes
2answers
55 views

Convert any convex optimization problem to a linear objective

Wikipedia claims that: Any convex optimization problem can be transformed into minimizing (or maximizing) a linear function over a convex set by converting to the epigraph form. Is there a ...