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

learn more… | top users | synonyms

1
vote
1answer
32 views

Why is this simplex procedure not working? $\min z = y - x + 1$

I have read of two ways to solve this program with the Simplex algorithm. One worked and the other didn't. The only difference is that, in the one that didn't work, I rewrote the function. I will ...
4
votes
2answers
364 views

Linear programming for combinatorics/graph theory

I just went to a graph theory talk talking about various fractional graph parameters (but focusing on one). These were defined using linear programming. A question was asked, "How can we learn more ...
1
vote
0answers
33 views

Linear programming - Textbook recommendations

Next term, I will attend a course on linear programming. Due to the assignments, we will have to write many thorough proofs. I anticipate that we will be supposed to cope with in-depth background ...
0
votes
2answers
298 views

Optimal Basic Feasible Solutions

In linear programming, is it true that you can only have at most 2 optimal basic feasible solutions? If so, why?
0
votes
0answers
16 views

Closed-form solution of the following LP problem

I am considering the following LP problem: $$ \begin{array}{cl} \text{maximize} & c^Tx\\ \text{subject to} & a^Tx\geq0 \\ & 0\leq x\leq x^\max \end{array} $$ where ...
0
votes
0answers
25 views

Linear Algebra - find basis without reduced echelon

For the start of a simplex solver I'm building in Python, I need to find a basic feasible solution. To do that, I need to find a basic solution/find the basis of the constraint matrix. Here's my ...
4
votes
1answer
187 views

Book on advanced topics of Network Flows

I am taking linear optimization class. Could you suggest me good fundamental textbook on advanced topics of network flows. To be more specific I am interested in: Multicommodity flow and multicut, the ...
0
votes
1answer
716 views

How to describe minimization of L1 norm error using linear programming?

Given a set of $n$ pair points $(x_1, y_1), ..., (x_n, y_n)$ in the plane, I need to find a line $ax + by = c$ that fits the points of the L1 norm error points as closely as possible. I need a linear ...
0
votes
0answers
26 views

k- maximally link disjoint paths and equations

This problem is NP-complete and also discussed to some extent in Graph problems which are NP-Complete on directed graphs but polynomial on undirected graphs from the level of my reading from various ...
3
votes
1answer
220 views

Finding all basic feasible solutions in a linear program

Given the following constraints \begin{equation} \begin{split} x_1 &+&x_2&+&x_3&+&x_4&\le 10 \\ x_1&-&x_2&&&&&\le0\\ ...
0
votes
1answer
22 views

Maximum cardinality affinely independent subset of $\mathbb{R}^n$

Let $S \subset \mathbb{R}^n$ such that $S$ is affinely independent. Then $$|S| \le n + 1.$$ Why? (e.g. does anybody know some place where this is proven?)
1
vote
2answers
425 views

Removing linear redundant constraints using Gauss Elimination

I have a set of linear constraints in the form of $c_i x \ge d_i$ and I need to identify if an additional constraint is redundant with respect of the previously mentioned set. Here I found a similar ...
0
votes
1answer
20 views

Linear programming, how to do the opposite transformation?

This is from a pdf file I found linked to from this site: They first define the primal dual problem like this: Then they have another representation of (p), and show that it's dual is: Now here ...
1
vote
1answer
25 views

Affine and Linear programming

Can someone give a simple explanation as to why the feasible region of a set of linear program/equations is affine?
0
votes
0answers
20 views

Finding the optimal solution to an ILP, when feasibility is not ultimately required

I have the following problem: I would like to solve an ILP with binary variables, i.e. I have a set of possible items, each having properties like "size" "weight" "value" "age" and so on, in total, ...
0
votes
0answers
18 views

Every polyhedron $P \ne \mathbb{K}^n$ equals an intersection of finitely many half spaces.

Currently, I am reading some lecture notes on linear optimisation. I cannot see why the following (seemingly trivial) proposition holds. (How could I understand/proove it?) Every polyhedron $P \ne ...
2
votes
1answer
818 views

Linear Programming: Three variable graphical solution

A small bank offers three type of loans: housing loans at $8.50$% interest, education loans at $13.75$% interest rates, and loans to senior citizens at $12.25$% interest. Further, it needs to ...
2
votes
1answer
23 views

Find the minimum value of C subject to the given constraints.

C=2x+5y Constraints: x+y>=2 2x-3y<=-6 3x-2y>=6 A-42 B-4 C-49 D-10 I encountered this question while doing the Systems of Linear Equations and Inequalities test at ...
0
votes
1answer
25 views

Euclidean and rectilinear distance and nonlinearity

Can some one please explain why Euclidean distance and rectilinear distance make a problem nonlinear? Thanks
2
votes
1answer
37 views

Two forms of duality in linear programming

I do not know much about this subject, but I am trying to learn a little. In a book I have it says that a primal problem is: max $c'X$ subject to $AX \ge b$ $X \ge 0$ It says ...
0
votes
0answers
22 views

Converting nested IF's to ILP

I'm trying to convert a nested if structure into a linear programming problem. Here is a simplified example of what I'm trying to do- r1, r2 are binary s1, s2 are natural (I can give an upper bound ...
0
votes
1answer
27 views

Linear problem: maximizing net income

Problem: A company produces and sells two different products. The demand for each product is unlimited, but the company is constrained by cash avaliable and machine capacity. Each unit of the first ...
0
votes
1answer
362 views

Minimize LPP using graphical method [ operational research ]

Question: Minimize z = 2x + 6y Subject to 2x + y >= 2; 3x + 4y <= 12 x,y >=0 Is min z = 2 the right answer ? if not how do i solve this ?
1
vote
1answer
746 views

Linear programming: basic solutions?

http://www.math.toronto.edu/kergin/236_t1_2.pdf For number 3(a), I don't get how "any of the last 4 columns are linearly dependent" and how x1 is the basic variable... I thought only the last 2 ...
2
votes
2answers
308 views

Exploring underdetermined linear system with non-negative solution

I haven't had much luck searching for this specific problems. Any pointers would be greatly appreciated. I have an underdetermined system where $ A $ and $ b $ are known. $ x $ is a real vector with ...
2
votes
1answer
296 views

A variation of the Assignment Problem

In the following Wikipedia article about the Assignment Problem in the Example section, it says: Similar tricks can be played in order to allow more tasks than agents, tasks to which multiple ...
3
votes
1answer
205 views

Solving special boolean equation set

I have boolean equation sets that look like this (where ^ means xor): eq 1: x1^x3^x5^x6^x9^x10^x11^x13^x17^x18 = 0 eq 2: 1^x1^x3^x10^x12^x17 = 0 eq 3: 1^x2^x3^x5^x8^x10^x14^x16 = 0 ...
4
votes
5answers
420 views

Why maximum/minimum of linear programming occurs at a vertex?

I'm in high-school and I'm told that the maximum/minimum of a linear programming occurs at the vertex.For more info see the chapter here. For convinience I'm putting relevant excerpt here: Now, we ...
0
votes
2answers
32 views

Line that passes between two vectors

I encountered the following in a text book I'm reading and I can't seem to understand why this is true (I'm translating this into English so excuse me if I'm not using the correct english terms): ...
1
vote
1answer
32 views

How to linearize a quadratic objective function with linear constraints?

I have an optimization problem that I'm working on. The objective is defined as follows: $Maximize: c_i\cdot w_i \cdot x_i - d_i \cdot y_i \cdot \delta_i $ subject to some linear constraints where ...
0
votes
1answer
29 views

Can there be a unique natural number vector solution to $Ax =b$ where $A$ is not a specific type of square matrix?

Let $A$ be $(n-1) \times n$ matrix that is of the following form: $$\left( \begin{array}{ccc} n-1 & 1 & 0 &.... & ....\\ 0 & n-2 & 2 & .... & ....\\ 0 & 0 & n-3 ...
0
votes
0answers
16 views

Quadratic programming using Python

guys I'm trying to solve quadratic programming problem with constraints. I know how to solve simple quadratic problems using scipy.optimize like following: Define objective function as F = ...
1
vote
1answer
316 views

Programación Lineal (PL)

quería ver si me pueden ayudar en plantear el modelo de Programación Lineal para este problema. Sunco Oil tiene tres procesos distintos que se pueden aplicar para elaborar varios tipos de gasolina. ...
1
vote
1answer
241 views

Business Linear Programming Question

Now I don't need you guys to do my homework for me; however, I am a little stumped Xara Stores in Canada imports the designer-inspired clothes it sells from suppliers in China and Brazil. Xara ...
2
votes
1answer
240 views

Linear Programming: Breaking Variables Product

Given two sets of binary variables $x_{i...N} \in X$ and $y_{i...M} \in Y$ and another binary variable $\alpha$ how can I linearize the following constraint, i.e break the product of variables? ...
-1
votes
1answer
66 views

Sum of two polyhedra is a polyhedron

I'm reviewing for a midterm next week in an optimization course. Currently, I'm having a great deal of trouble with a review problem. The problem is as follows: Let $P$ and $Q$ be polyhedra in ...
2
votes
1answer
43 views

Prove vertices of a simplex are affinely independent

I'm given that the definition of a simplex $T$ is $x \in\mathbb R^n$ such that $x$ satisfies $n+1$ linear inequalities: $(u_k, x) \lt c_k$ for $k = 1,\ldots,n+1$ (i.e. $T$ is the intersection of $n+1$ ...
0
votes
1answer
37 views

Shadow Price in Linear Programming - Finite Mathematics [closed]

Why is it true that if a slack variable is nonzero, then the shadow price of the associated constraint will be zero?
0
votes
1answer
21 views

The meaning of initial value in linear programming

I am new to LPP. I would like to know what is meant by setting an initial value(IV) to a variable. For example I was solving a problem where objective function(OF) is non-negative. When I give some IV ...
0
votes
1answer
148 views

Minimizing shipping cost under given constraints

I have a question that has been bugging me for about a day now. A manufacturing company receives orders for engines from two assembly plants. Plant I needs at least 45 engines and Plant II needs at ...
0
votes
0answers
37 views

Counting the Number of Combinations Conditionally

A bank issues 10 loans ranging from 1000 to 10000 dollars each and charges 5% interest on each loan. On average, the bank finds that 1 in 10 loan recipients defaults. If the loan that defaulted is ...
0
votes
1answer
30 views

Is the polar of the polar set the original set?

For each $Q \subset \Bbb R^n$, denote $Q^*:=\{z \in \Bbb R^n:z\cdot x \leq 1,\;\;\text{for all}\; x \in Q\}$. Let $P:=\{x \in \Bbb R^n: Ax \leq b\}$, for the matrix $A$ and the vector $b$. It is ...
1
vote
0answers
56 views

Proving boundedness of a function .

Consider the function \begin{eqnarray} f(x_1,x_2,\cdots, x_n) = \frac{\sum_{i}^{n}a_ix_i}{\sum_{i}^{n}b_ix_i}, \end{eqnarray} over the set $S = \{x := (x_1,x_2,\cdots, x_n):-1 \leq x_i \leq 1,\; ...
0
votes
1answer
49 views

Proving boundedness of a function (part 1).

Consider the function \begin{eqnarray} f(x_1,x_2,\cdots, x_n) = \frac{\sum_{i}^{n}a_ix_i}{\sum_{i}^{n}b_ix_i}, \end{eqnarray} over the set $S = \{x := (x_1,x_2,\cdots, x_n):-1 \leq x_i \leq 1,\; ...
1
vote
0answers
32 views

Proof of Strong Duality via Farkas Lemma

I am trying to prove what is often titled the strong duality theorem. There is a hint in the book that I'm following, and I want to follow the method they have outlined for me. I will outline the ...
1
vote
2answers
34 views

How to introduce flat cost of flow over a node using mixed integer programming.

In the set up for the program we have a graph where we are trying to minimize the cost of sending flow over the arcs. I have formulated the following linear program. \begin{array}{ll} \text{minimize} ...
0
votes
1answer
26 views

shortest point on a line segment from point out side the line

from the above pic I found the value x from line (p1,p2) and point a using y=mx+b and imaginary red line which is perpendicular to black line having slope -1/m and the intersecting point x. the ...
1
vote
3answers
465 views

Linear Programming to find the loan plan to minimize the interest payment

Assume that it is the first of July and you are running a small shop. The sales revenue and the amount of bills you have to pay for the next six months are estimated as following: In short, you ...
1
vote
1answer
2k views

Finding dual of linear programming problem

I have to find the dual to this linear programming problem: Maximize $-15z-\frac{11}{20}w-3a-3b=-132+p$ subject to $y+9z+\frac{13}{10}w+3a-2b=12$ $x-2z-\frac{7}{20}-a+b=4$ ...
0
votes
1answer
26 views

Above what order of magnitude a pure cutting-plane algorithm must be forgotten in favour of branch-and-cut?

Crawling the web on the subject of the cutting-plane algorithm, I have seen everywhere that a pure cutting-plane method cannot be used for numerical instability reasons after some iterations. But do ...