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

learn more… | top users | synonyms

0
votes
0answers
5 views

How to solve binary equation which has mod?

Three messages in binary format are sent $$ a_0 a_1 a_2 a_3 $$ and coded in binary format $$b_0 b_1 b_2 b_3 b_4 b_5 b_6$$ Symbols $$b_0,b_1,b_2,b_3,b_4,b_5,b_6$$ are the coefficients of the Boolean ...
0
votes
1answer
14 views

Does optimal solution from primal problem follow from optimal solution to dual?

In a linear programming context, does the primal optimal solution yield an explicit way to find the primal dual solution? I vaguely remember something like this from an optimization class but can't ...
0
votes
0answers
6 views

Legal operation to transform a linear program into the canonical form

Good morning! What are the legal operations to transform a linear program into the canonical form? For instance can the following linear program \begin{cases} \begin{array}{col1col2…coln} \max ...
0
votes
0answers
36 views

Intersecting rational polyhedral cones

Call A the cone generated by the rays (1,0,0) and (0,1,0) and B the cone generated by the rays (1,1,0),(1,0,1), and (0,1,1). I want to compute the intersection of these polyhedral cones, but I am ...
0
votes
1answer
38 views

How to configure simplex method to start from a specific point

If I have a linear programming problem e.g. $$\max 2x_1 + x_2$$ with these constraints $$x_1-2x_2 \leq 14$$ $$2x_1-x_2\leq 10$$ $$x_1-x_2 \leq 3$$ And I want to solve the problem starting from a ...
1
vote
1answer
34 views

How can L1-sparse representation be formulated as linear programming?

Problem Statement Show how the $L_1$-sparse reconstruction problem: $$\min_{x}{\left\lVert x\right\rVert}_1 \quad \text{subject to} \; y=Ax$$ can be reduced to a linear programming problem of form ...
0
votes
1answer
26 views

Canonical form simplex method

In 2-phases simplex method what kind of operations must be done to get the canonical form tableau? In this step(phase 2 of 2-phases method) after the remotion of artificial variables columns of ...
0
votes
1answer
29 views

set up Linear programming problem

How do I set up this problem ? A product can be made in three sizes, large, medium, and small, which yield a net unit profit of $12, 10$ and $9$ respectively. The company has three centers where ...
0
votes
0answers
24 views

Solving a set of linear equations

I have the following linear equations I need to solve: $$Y=\sum_{n=1}^{N}A_nX_nB_n$$ where Y is m x m $A_n$ are m x $\frac{m}{\sqrt{N}}$ $X_n$ are $\frac{m}{\sqrt{N}}$ x $\frac{m}{\sqrt{N}}$ ...
1
vote
1answer
43 views

Project allocation optimization with tricky constraint

I have an allocation problem that should be straightforward, except that it has very specific constraints. I want to assign approximately 300 students to 170 projects in pairs - so that each project ...
1
vote
1answer
34 views

What is the difference between linear and integer programming?

Recently I tried to solve a maximization integer programming problem using linear programming by flooring the max point - but got the wrong answer. I'm wondering if someone can explain mathematically ...
0
votes
0answers
29 views

Minimum cost linear programming problem formulation

I need to formulate a graph and a linear programming problem, and provide a basic solution for the following problem: A singer who lives in city A wants to plan a tour and end it in city E. The ...
0
votes
1answer
28 views

Solve a linear programming minimization problem with greater-than-equal sign in the constraints using the Simplex method

I need to solve the following linear programming minimization problem using the Simplex method: ...
0
votes
2answers
18 views

What if we get fractional value while finding the numbers of workers in a linear programming problem?

I came across a LP problem in which a factory recruited workers on daily basis giving them wages per day. I don't remember the figures but I remember what was in the question. We had to find the ...
1
vote
1answer
26 views

Solving integer programming problem using the graphical method

I have an integer programming problem I need to solve using the graphical method. Maximize $55x_1 + 500x_2$ such that $$\begin{align} 4x_1 + 5x_2 &\le 2000\\ 2.5x_1 + 7x_2 &\le 1750\\ ...
0
votes
1answer
34 views

Scheduling Optimization Problem - 5 days/week

A 24/7 calling center works as follows: every agent works 5 days in a row and has two days rest, e.g., every week works Tuesday-Saturday and rests on Sunday and Monday. The numbers of agents working ...
0
votes
0answers
21 views

Explicit solution for minimization over unit box with total budget constraint

I am trying to solve question 4.8, part (e) from Convex Optimization by Boyd. The problem is to find an explicit solution for the minimization problem: Minimize $\textbf{c}^T \textbf{x}$ subject to ...
-4
votes
0answers
23 views

Can anyone give some help [closed]

I have problem i can not find the way to solve it. Is there anyone who have ability to solve this problem? I do not know where to start Can anyone give some guide step? Here is problem: Can ...
1
vote
1answer
53 views

Dual program is wrong. Authors claim is right.

In a well respected book, I found the following. The authors claim that it is correct. But I think it is wrong. This is the primal Linear Problem: $$ \begin{array}{cccc} ...
0
votes
0answers
35 views

Showing λu + (1 − λ)v is an optimal solution

$$\max \quad c \cdot x \\ \mathrm{s.t.} \ Ax \leq b\\ x\geq 0 \\$$ There are two optimal solutions to the LP $u$ and $v$. How do I show that for $\lambda \in [0,1]$, $\lambda u + (1-\lambda)v$ is ...
0
votes
0answers
23 views

On the proof of corner points maximising or minimising a linear function over a bounded convex region

This proof says if $Z_P \ne Z_Q$, then $Z$ is maximised (or minimised, I guess) at one of the endpoints -- of what exactly? $\overline{PQ}$? So the maximum value of $Z$ occurs at either $P$ or $Q$? ...
0
votes
0answers
20 views

Can we relax the assumption of nonnegativity in this proof on convexity of a feasible region in a linear programming problem?

Is the $\color{red}{\text{non-negativity constraint (see red box)}}$ used at all in the proof? If so, where? If not, does the proof then hold for a standard LP problem without the non-negativity ...
0
votes
2answers
31 views

How to describe $\lbrace \mathbf{x}\in \mathbb{R^n}: |x_j|\le1 $ for$ 1\le j\le n \rbrace $ in terms of $x_j=x_j^+-x_j^-$

How to describe the set $A$=$\lbrace \mathbf{x}\in \mathbb{R^n}: |x_j|\le1 $ for$ 1\le j\le n \rbrace $ in terms of $x_j=x_j^+-x_j^-$ where $x_j^+\ge0$ and $x_j^-\ge0$ The answer says: $B$=$\lbrace ...
0
votes
0answers
13 views

Optimization: second order condition

This is the condition Where $L(x, \mu\,\lambda)$ is the Lagrangian function in a given point that satisfy the first order condition. Problem $ min (-4x -y)$ $ -x^2 -y^2 +1 <= 0 $ $ y- 1 ...
3
votes
1answer
89 views

Discrete Linear Programming over Finite Fields?

$A$ is an $l\times m$ matrix with integer entries and each column of which contains at least one negative entry. $y$ is a column matrix with integer entries of length $l$. Define the set of sequence ...
0
votes
1answer
42 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
14 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 ...
-1
votes
0answers
11 views

mathematica Linear programming with summation and product

I want to solve Linear programming in mathematica that have summation and products in objective function and in constraints. I ...
0
votes
0answers
44 views

How to do linear programing in Ogame? [closed]

I'm trying to apply my linear programming courses to my everyday life for bettter understanding and learning. More precisely I started playing a game called Ogame about war in the universe and I have ...
0
votes
0answers
24 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
21 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
29 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
17 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
35 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
21 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
27 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
16 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
43 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
34 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
60 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
16 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
27 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
23 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
28 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
41 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
12 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
13 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} ...
0
votes
2answers
68 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
39 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 ...