# Tagged Questions

14 views

### Choosing pivot while solving Linear Programming in case the constraints are lesser than the available variables.

I am trying to solve a LP with simplex method which says like. Suppose, Maximize $$10x_1+20x_2+20x_3$$ subject to \begin{align} \tfrac{2}{3}x_1+4x_2+x_3&\leq 50&& (I)\\[0.5em] x_1 + ...
62 views

### Finite Math Word Problem

I have been having trouble with this word problem for a while. A bicycle manufacturer builds one-, three-, and ten-speed models. The bicycles need both aluminum and steel. The company has available ...
71 views

### On optimal solution

Given $Bx \leq b$ (1) Consider the linear programming problem $\max \{1.y:Bx+y-\beta b \leq 0, 0 \leq y \leq 1, \beta \geq 1\}$ (2) a. Suppose that (2) is feasible and $(x^*,y^*,\beta^*)$ is an ...
33 views

### Transportation problem in supply chain

I understand how to solve transportation problem with only members in the chain, but how can I solve the transport problem with multiple members in the chain? Thank you.
35 views

### Designing an algorithm to determine if a linear combination of k-1 sets is contained in the k-th set .

I am trying to solve the following problem - given $k$ sets : $A_1,A_2,...,A_k$ containing $O(n)$ integers each I need to design an algorithm that will determine if there is such a group of elements ...
63 views

### Are my linear program equations correct?

Here's the problem: "An electronics company has a contract to deliver 21,475 radios within the next four weeks. The client is willing to pay 20 dollars for each radio delivered by the end of the first ...
17 views

### elements of oriented matroids belonging either to positive circuits or positive cocircuits

I need to prove the following, which seems trivial because it follows from the Farkas lemma (you may know this as the 3 or 4 painting lemma). Can someone show me how to prove this, please? I'm a bit ...
84 views

53 views

### Finding the dual of this primal LP.

I am going over sample questions from a sample exam, and I got stuck on the following question. I need to determine the dual of this LP: $min: c^Tx + d^Tu \\ s.t: Ax + Du = b\\ x \ge 0$ $A$ is an ...
138 views

### Optimal Solution Set To Linear Programs

I have the following assignment question, and I am not quite sure how to proceed. Q: Consider the following LP (P): $\max\{{c^Tx:Ax=b, x \geq 0}\}$, where $A$ is an $m$ by $n$ matrix. Prove or ...
56 views

### Determine the values of $a,b,c,d$ and $e$ for a convex, piecewise function

Consider the following Linear Programming problem \begin{align} z(\lambda)=\max(1+3\lambda)x_1+(3+2\lambda)x_2 & \\[8pt] -x_1+x_2 & \leq 1\\[8pt] x_2 & \leq 2\\[8pt] 2x_1+3x_2 & \leq ...
43 views

### Semi definite programming for MAX-2-SAT

I didn't understand something in formulating this program, to a vector program. Assume that each clause is of the form $C_{j}=\left(u_{j}\lor v_{j}\right)$ where $u_{j},v_{j}$ are literals (meaning, ...
98 views

### Formulate the dual problem in matrix notation

Consider the standard LP problem $\max\{c_0^Tx : A_0x \leq b, x\geq 0\}$. After introducing the slack variables this problem can be written as $$\max c_0^Tx$$ $$s.t. Ax = b$$ $$x\geq 0$$ ...
100 views

### Determining the convex hull of the union of two polyhedra

I'm doing an introductory course to linear programming and I'm working through some exercises to prepare for the final exam, I'm stuck on an exercise and I would really appreciate a hint: Let ...
34 views

### How to visualize duality

In My course of linear programming we are given the definition of a primal/dual problem. However I cannot really get my heard around what it actually is? It helps us in later exercises. Are we ...
45 views

### How to construct an LP problem that makes a (partial) theorem fail?

I am following a course on linear programming, and one of the exercises calls for an example, that may show that a theorem fails, if a assumption is omitted from the theorem. The theorem is Theorem ...
75 views

### Model Linear-Programming Problem

A factory needs to complete $n$ jobs by using $m$ machines. To complete each job $j, j=1,\dots,n$, an amount of $r_j\geq 0$ processing units is required. Each machine $i$ has a processing speed ...
This is homework. I have the following dual problem, formed by using lagrangian relaxation. \begin{align} min & \{&89y_1 +&3y_2 +&10y_3\}\\ s.t.& &3y_1+& &y_3 ... 0answers 41 views ### Prove that this linear programming problem has the following dual problem Consider the following Linear Programming problem:max \sum_{j=1}^nc_jx_j\begin{align} s.t. \quad \sum_{j=1}^na_{ij}x_j=b_i \quad 1\leq i\leq m\\ x_j\geq 0 \quad 1\leq j \leq n.\\ ... 1answer 328 views ### Construct a linear programming problem for which both the primal and the dual problem has no feasible solution Construct (that is, find its coefficients) a linear programming problem with at most two variables and two restrictions, for which both the primal and the dual problem has no feasible solution. For ... 0answers 65 views ### How to add artificial variables to a linear programming matrix I was working on a linear programming assignment where we are given (via textfile) A, b, c and need to solve the problem: Max c^t * x (c-transpose x) such that Ax = b Now if I recall correctly: ... 1answer 99 views ### Show that two Linear Programming problems are equal Consider the general linear programming problem min \sum_{j=1}^n c_jx_j s.t. \sum_{j=1}^n a_{ij}x_j \leq b_i, for i=1,\dots , m x_j \geq 0 for j=1,\dots , n And the ... 1answer 64 views ### Show using duality that exactly one of the following systems has a solution (I) Ax=b ; 0≤ x ≤e (II) uA +v ≥0 ; ub + ve = -1 ; v ≥ 0 0answers 48 views ### Prove mathematically Q.1 Consider the dual simplex method applied to a standard form problem with linearly independent rows. Suppose we have a basis which is primal infeasible, but dual feasible, and let i be such that ... 1answer 60 views ### Finding a dual Linear-Program We are trying to prove Von-Neumann's MINIMAX Theorem namely\max_{x\in\Delta_{n}}\min_{y\in\Delta_{m}}y^{T}Ax=\max_{x\in\Delta_{n}}\min_{1\leqslant i\leqslant n}(Ax)_{i}$$(Here \Delta_k is the ... 1answer 96 views ### Farkas lemma variations Suppose the system: Ax=0,x \geq 0,  and c \cdot x > 0 does not have a solution. How can I apply Farkas' lemma to create a system that must have a solution? I'm not so sure how to proceed, ... 1answer 141 views ### How to a plot a line for ax+by-c in MATLAB? The title basically says it all. I'm doing an assignment and need to include a plot of my scatter and the line generated by linprog(). I ran ... 0answers 52 views ### Need help finding unknowns in simplex tableau. I need help with this homework problem. The objective is to maximize 2x_1 - 4x_2, and the slack variables are x_3 and x_4. The constraints are =< type. Tableau \begin{matrix}z & x_1 ... 1answer 103 views ### Linear programming problem Some additional information: In the next season the harvesting amount is estimated at 900 for farm A, 1200, 1500, 1800 for farm B,C and D respectively. In this scenario I'm asked to minimize the ... 1answer 90 views ### Linear programming duality theorem As far as I know, there are 2 versions of this theorem: 1) \max \{xc^T: xA \le b, x \ge 0, x \in R^n\} = \min \{by^T: Ay^T \ge c^T, y \ge 0, y \in R^m\} 2) \max \{xc^T: xA \ge b, x \in R^n\} = ... 0answers 211 views ### Linear programming: writing a problem with artificial variables? Use artificial variables to write a linear programming problem in canonical form with non-negative resource vector whose solution will determine whether there exists (and if so, find) non-negative ... 0answers 49 views ### finding the largest p components of x Given an n \times n matrix A, and an n \times 1 vector b, the conventional way of computing an n \times 1 vector x such that x=Ax+b is to use the following iterations: ... 2answers 98 views ### When does \max x+y  subject to ax+by \le 1, x,y\ge 0 have a unique optimal solution? From reading online I found someone said that it has a unique optimal solution when a and b are positive and a \neq b. Could someone explain why this is the case? I know that if a = b then ... 1answer 562 views ### Example of a quadratic programming problem with no optimal solution on vertices? Is there a way to write a quadratic programming problem with two variables bounded, nonempty feasible region linear constraints and yet have none of the vertices of the region optimize the ... 2answers 384 views ### Need Homework Help: A small corportion borrowed 500,000, some at 9%, 10% and 12%. Use a system of equations--how much was borrowed at each rate if… A small software corporation borrowed 500,000 cash to expand its software line. The corporation borrowed some of the money at 9%, some at 10%, and some at 12%. Use a system of equations to determine ... 1answer 182 views ### Prove that an optimal solution x^* of the problem 1 \min f(x) s.t x\in \mathbb{R}^n and.. Prove that an optimal solution x^* of the problem 1 \min f(x) s.t x\in \mathbb{R}^n and an optimal solution (\bar{x},\bar{z}) of the problem 2 \min z  s.t z\ge f(x)\,, x\in \mathbb{R}^n ... 1answer 324 views ### Linear programming: the optimum of the shortest path problem is attained by x \in [0, 1]^m Let G=(V,E) be a graph, where |E|=m, and suppose we formulate the shortest path problem on G as follows: minimize {}^t(1,\dots,1)x such that Bx={}^t(1,-1,0,\dots,0), x\in \{0,1\}^m, where B ... 1answer 150 views ### Linear Programming Duality (Basic optimization) Suppose that A is an m\times n matrix, D is a p\times n matrix, b is an m-vector, and d is a p-vector. Prove that there does not exist n-vector x satisfying$$Ax \geq b, Dx \leq ...
Please help with the problem: A polyhedron P in $R^n$ is given by the system of m linear inequalities (of n variables). Furthermore, let P have k vertices (that is, k vectors satisfying all m ...