Tagged Questions
0
votes
0answers
17 views
finding the optimal solution of the dual problem
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 ...
0
votes
0answers
17 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.\\
...
0
votes
1answer
38 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 ...
0
votes
0answers
12 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: ...
2
votes
1answer
42 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 ...
0
votes
1answer
27 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$
1
vote
0answers
33 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 ...
0
votes
1answer
30 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 ...
1
vote
1answer
44 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, ...
0
votes
0answers
17 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 ...
2
votes
0answers
33 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 ...
0
votes
1answer
79 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 ...
1
vote
1answer
58 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\} = ...
1
vote
0answers
123 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 ...
3
votes
0answers
43 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:
...
0
votes
0answers
144 views
Linear Programming-minimize cost
Exeter Mines produces iron ore at four different mines; however, the ores extracted at each mine are different in their iron content. Mine 1 produces magnetite ore, which has 70% iron content; mine 2 ...
0
votes
0answers
29 views
Road lighting LP formulation
Bertsimas & Tsitsiklis text Introduction to Linear Optimization, p. 35, Exercise 1.8:
My attempt:
Let $c$ be the cost per unit power for a road lamp, a possible linear programming formulation ...
0
votes
2answers
80 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 ...
1
vote
1answer
352 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 ...
0
votes
2answers
195 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 ...
0
votes
1answer
94 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$ ...
0
votes
0answers
115 views
Gram-Schmidt orthogonalization process for Hermite functions
I am trying to do Gram-Schmidt orthogonalization process for functions. I need to use this process on [-1,1] for the Hermite functions with n=1,2,...40: $$
h_n(x)=(-1)^n\gamma_ne^{x^2/2} ...
0
votes
1answer
272 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 ...
0
votes
1answer
138 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 ...
1
vote
2answers
230 views
Need help with a Linear Programming homework.
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 ...
2
votes
0answers
72 views
Linear optimization, homework problem.
Please help with the following problem:
Given a $m$ x $n$ matrix $A$, $m$-vectors $b$ and $y$, and $n$-vectors $c$ and $x$.
Write the dual $LP$ problems $P$ and $P^d$ in the standard form.
Whether ...
1
vote
2answers
85 views
Solving LP from tableau
$$\begin{array}{cccccc}
& x1 & x2 & x3 & x4& x5 \\
-4& 2 & 0& -2 & 0& 3\\
3 & 1 & 0 & -1& 1 & 3\\
2 ...
4
votes
1answer
517 views
Proving Helly's theorem
The problem is to prove Helly's theorem for the case, when the convex bodies are polytopes, by using linear programming duality.
Helly's theorem
Let $B_{1},...,B_{m}$ be a collection of convex ...
1
vote
1answer
2k views
Degeneracy in Linear Programming
Consider the standard form polyhedron, and assume that the rows of the matrix A are linearly independent.
$$ \left \{ x | Ax = b, x \geq 0 \right \} $$
(a) Suppose that two different bases lead to ...
1
vote
1answer
210 views
Sudoku mathematically, MILP?
My homework contains a word (freely-translated) "target-function" that I should generate somehow for 9x9 sudoku solver with some MILP problem. But I am bit lost what they mean. I have sofar described ...
1
vote
2answers
426 views
Optimizing with Absolute Value Objective Function
max : $w = |q^T y|$
subject to
$A y \leq b$
$y \geq 0$
Please describe how one could solve the non-linear programming prob. above by using linear programming methods.
I tried changing $y$ to $y' ...
3
votes
1answer
77 views
Sensitivity of a solution to an LP Problem to a change in the objective function
Suppose I have a LP problem of the kind $\max f(x) = 2x_1 + c_2x_2$, subject to several restrictions. Suppose I know that the point $(a, b)$ is optimal. How much can $c_2$ change so that $(a, b)$ ...
