Questions tagged [linear-programming]
Questions on linear programming, the optimization of a linear function subject to linear constraints.
0
votes
0answers
18 views
Why in Big M method there is no nonbasic variables with following condition
Consider following standard form linear optimization problem:
P:$\hspace{4 ex}$ min $\hspace{1.5 ex}$ CX
s.t. $\hspace{3 ex}$ AX=b
$\hspace{7 ex}$ X $\geq$ 0,
$\hspace{1 ex}$ b $\geq$ 0,
And ...
0
votes
0answers
32 views
Help with linear programming problem!!
I'm working through the following question, and I'm stuck to how you'd use a GRAPHICAL 2D method to solve this
Betsy is planning her baking schedule. She can make 3 cakes, apple, banana, and ...
0
votes
2answers
26 views
Write the dual for the following linear program
Write the dual for the following linear program:
max($3x_1 + 8x_2$)
subject to
$x_1 + 4x_2$ ≤ 20
$x_1 + x_2$ ≥ 7
$x_1$ ≥ -1
$x_1$ ≤ 5
The posted solution is as follows, but does not show the ...
0
votes
1answer
15 views
finding optimal solution of a min network flow problem
We have the following the min cost network flow problem. Notice that the arcs $(1,2), (2,3), (4,2), (3,6), (5,6)$ give a feasible basis. We easily find a feasible solution:
$$ (x_{12}, x_{23}, x_{...
1
vote
1answer
25 views
The shape of a feasible region with equality and inequality constraints
I was wondering if anyone can help me with this (probably basic) question.
I want to know how the following feasible region looks like if we have thousands of variables. The constraints are linear. ...
1
vote
0answers
67 views
How to show that exactly one of the following inequality systems has a solution?
This is from a homework set of my optimization class.
Let $A \in \mathbb{R}^{m \times n}$. Show that exactly one of the following inequality systems has a solution:
$$
\mathbf{I}: \,\,\,Ax \leq 0,...
0
votes
0answers
13 views
Property of submodular non-decreasing function
Let $f:\mathcal{P}(N) \longrightarrow \mathbb{R}$
be a set function. $f$ is submodular if
\begin{align}
f(A) + f(B)
&\geq
f(A \cup B) + f(A \cap B)
&\text{for all } A, B \in \mathcal{P}(N),
\...
0
votes
1answer
7 views
Big M method in LPP
In big M method the artificial variable is given cost as -M in case of maximisation problem. But what is the reason for taking "-M" ( M being a very large value)
-2
votes
0answers
18 views
Conditional constraint in linear programming [on hold]
I want a constraint that says:
Y=2000-x if x<= 2000
Y=0 if x>=2000
How can I formulate this constraint? Thanks.
1
vote
1answer
21 views
Question to the solution of “Indicator Variable if x is in specific range”
This question is to query the solution provided by Erwin Kalvelagen to the post
Indicator Variable if x is in specific range
and
conditional constraint: if $x \in [a,b]=> z=1$
(Sorry for ...
0
votes
0answers
10 views
Need help writing a Matlab function that generates a minimum and maximum possible solution for a randomized set of constraints [on hold]
I am writing Matlab code that generates a random compact polyhedron. The arguments are ni (the length of the x column vector), the H matrix has dimensions (ni-1,ni) so that there is no unique solution ...
0
votes
0answers
25 views
Solve a linear problem using bounded variables method
Consider the following
$$\min 3x_1+4x_2\\ s.t. 4x_1+3x_2\ge12 \\ 3x_1+4x_2\le12\\ x_1,x_2\ge0$$
Substitute the first restriction by $x_1\le3$ and solve the LP by bounded variable method.
Attempt
...
2
votes
2answers
46 views
Linear program with parameter $t$ as coefficient of basic variable
Consider the following linear problem
$$\max tx_1+x_2\\ s.t. 4x_1+3x_2\le12 \\ 3x_1+4x_2\le12\\ x_1,x_2\ge0$$
where the parameter $t$ grows exponentially $t\in[1,\infty).$
Find the sequence of ...
0
votes
0answers
14 views
Linear Program with finite optimal value has strictly complemenetary solution
In my lecture, the following statement was given without any proof:
Given a primal-dual linear problem
(P) $$\{min~ c'x \mid Ax=b, x \geq 0\}$$
(D) $$\{max~ b'y \mid A'y+s=c, s \geq 0\},$$
it ...
1
vote
1answer
22 views
Model formulation: a conclusion about the model before solving it
I have found this simple model in a paper discussing robust optimization [1]
$$\max \vec{c}^{T}\vec{x}$$
s.t.
$$\sum_j a_{ij}x_j + \sum_j \tilde{a}_{ij}y_j \leq b_i \;\;\;\forall i$$
$$ -y_j \leq ...
0
votes
1answer
21 views
Converting a first norm into a linear program
I want to convert the following problem into a linear program.
$$ \min_{x \in \mathbb{R}^n} \qquad \lvert\lvert Ax - b \rvert\rvert_1$$
Here $A \in \mathbb{R}^{m\times n}$, $x \in \mathbb{R}^n$ and $...
0
votes
1answer
22 views
Determine the optimal point satisfying the given condition
We are given the following linear problem:
$\max\left\{5x_1-2x_2\mid3x_1+x_2\leq7,4x_1-2x_2\leq3,x_1\geq0,x_2\geq0\right\}$.
If there exists an optimal point where at least one of its coordinates
...
1
vote
0answers
19 views
How should I create a matrix of costs based on a set of variable?
I'm trying to make a matrix that depicts costs for a set of tasks. These tasks are the rows of the matrix. The cost matrix is to be based on a multi-attribute weightage of the tasks based on their ...
0
votes
3answers
28 views
How many boxes of each mixture should the company make to maximize profit? Linear Programming Problem
A company makes two snack mixtures.
A box of mixture A contains 6 ounces of peanuts, 1 ounce of M&M's, and 4 ounces of raisins and sells for \$4.25.
A box of mixture B contains 12 ounces of ...
1
vote
1answer
32 views
How can both these definitions be equivalent (duality)?
Definition 1: Given linear programming problem (LP) $\max\left\{\left \langle c,x\right \rangle| Ax=b, x
\geq 0\right\}$. Then its dual is $\min\left\{\left \langle b,u \right
\rangle | A^Tu \geq c\...
0
votes
0answers
31 views
which combination(partiotioning ) has the smallest value?
A positive integer can be partitioned, for example, the number 7 can be partitioned into the following:
$7=7$
$ 7=6+1$ , $ \ \ 7=5+2$,$ \ \ 7=4+3$
$ \ \ 7=4+2+1$,$ \ \ 7=3+3+1$,$ \ \ 7=3+2+2$,
$ \ ...
0
votes
0answers
30 views
Given LP and its dual. If LP is infeasible, what's the objective value of its dual?
Given is the linear programming problem $(P) \max \left\{\left\langle c,x \right\rangle\mid A \cdot x \leq b, x \geq 0_n\right\}$ and its dual $(D) \min\left\{\left\langle b,y \right\rangle \mid A^T \...
0
votes
2answers
119 views
Transportation problem into initial simplex tableau
I did (b) .
For (a), I got this
$$\min 3x_1+2.7x_2+2.9x_3+2.8x_4\\ s.t. x_1+x_2\le 5\\ x_3+x_4\le4\\ x_1+x_3=3\\ x_2+x_4\ge4\\ x_i\ge0$$
The standard form is
$$\min 3x_1+2.7x_2+2.9x_3+2.8x_4\\ s.t....
0
votes
1answer
111 views
One redundant equation in linear program?
Consider the general linear programming formulation of the transportation problem (see Table 8.6). Verify that the set of $(m+n)$ functional constraint equations $(m$ supply constraints and $n$ demand ...
0
votes
1answer
36 views
Measuring infeasibility in convex optimization, relations with dual problem
A question regarding convex optimization and (maybe) duality.
I have a problem in the form
\begin{align}
x^* = \mathrm{arg} \min_x f(x) \quad \text{s.t.} \quad A x \leq b, C x = d,
\end{align}
where $...
2
votes
0answers
38 views
Constraint satisfaction problem (CSP) for inequalities of vectors
I have two vectors $Y= (y_1, y_2, \ldots, y_m)^T$ and $S= (s_1, s_2,\ldots, s_m)^T$, where all entries in $Y$ and $S$ being positive integers. $Y$ is defined by $Y = A + B \cdot X$, where $A$ is a ...
0
votes
0answers
16 views
Farkas lemma and matrix spectrum
I am currently looking at a problem of the following type :
I have a matrix $\mathbf{M}\in\mathbb{R}^{N \times N}$ such that it's general term is given by
$(\mathbf{M})_{ij}=z_i \delta_{ij} - A_{ij}...
1
vote
0answers
31 views
changes on RHS of a constraint in LP
Question: What change in the RHS vector $b=(8,4)^T$ would increase on the optimal value of the objective function?
Attempt:
Suppose we change the first component of $b$, say now we have $b' = (k,4)$,...
3
votes
1answer
34 views
Clarification about Simplex Algorithm concepts
We have the following generic program:
$max \;\; c^Tx$
$\quad \quad Ax \le b$
$\quad \quad x \ge 0$
where $x$ is the vector of variables $(x_1, x_2,..., x_n)$.
Suppose the origin is feasible. ...
1
vote
1answer
25 views
Changes in Primal and Dual Solutions When Scaled
Suppose that we have an LP in the standard form
$$\text{(P) min }c^Tx: Ax=b, x\le 0$$
and it's dual would be
$$\text{(D) max }b^Tx: Ax\le c$$
Let $\overline{x}$ and $\overline{y}$ be the ...
0
votes
1answer
19 views
Linear Programming Word Problem: Theater
I'm having trouble understanding the second constraint.
A theater is presenting a program on drinking and driving for students and their parents[...] admission is 2.00 dollars for parents and 1.00 ...
1
vote
1answer
32 views
how to express the following constraint for linear programming
I would like to express the following constraints mathematically:
For a flow $f$ the sum of all the weights $w_{ij}$ of the edges for which $x^f_{i,j} \gt 0$ should be less than $W^f$.
I apologize I ...
0
votes
0answers
18 views
Expected number of comparisons in sequencial search to find t if t is repeated k times in an array of n elements
How to show that the expected number of comparisons required to find an element "$t$" from an array of "$n$" elements if the element occurs "$k$" in the array is $(n+1)/(k+1)$.(using Sequencial ...
0
votes
2answers
35 views
Multiple inputs, multiple outputs; solving when you have simple linear models
I am working on a mathematical problem related to a steady state controls problem, and I think this might be the place to ask this. I've figured out some of the simple cases, and am wondering where ...
0
votes
0answers
24 views
Representing game with map through Extensive Form
I have a task to represent game using extensive form. I know how to work with extensive form in general, but I have problem how to represent this type of the game.
Rules: (Player 1 = P1, Player 2 = ...
0
votes
3answers
73 views
Binary variables in time series: integer linear programming
I'm working on a problem and I can't seem to find an easy solution to it. It's about an optimization problem, concerning a time series.
I have a binary variable $\alpha_t$ for $t \in [0, 24[$. I ...
1
vote
0answers
24 views
Why does the Canonical Form of linear programming have non-negativity?
Aren't the non-negativity constraints special cases of the general constraints?
Isn't
$$x_1 \ge 0$$
just
$$-1 \cdot x_1 + 0 \cdot x_2 \le 0?$$
Then you could just summarize the general form of ...
1
vote
2answers
31 views
Find at least one solution to matrix inequality
I have the following problem posed:
find at least one vector $\mathbf{x}$ such that
$$
A\mathbf{x} + \mathbf{b} \geqslant \mathbf{0}
$$
for a given matrix $A$ and vector $\mathbf{b}$. Nothing is ...
0
votes
0answers
18 views
Optimized surface covering using rolls of membrane
I want to cover a surface that has quite a complex geometry limited with straight lines. Covering will be done using a membrane that is sold in 2 meters wide and 25 meters long rolls, with an overlap ...
0
votes
1answer
30 views
What is the dual for the following LP
Minimize $c^Tx$
subject to, $b_l \leq Ax \leq b_u \\ l\leq x \leq u$
where $A$ is an $m \times n$ matrix.
My approach was to separate each inequality into two.
So,
$b_l \leq Ax\\
Ax\leq b_u\\
l\...
0
votes
1answer
56 views
Changes to LP if a new constraint is added
Applying simplex, I found out the optimal solution to be $z^*=16$ and $x^{*} = (8,0,0,0,12)$ where $x_4,x_5$ are slack variables.
Now, suppose we add constraint $x_2+2x_3 = 3$
So, If I were to add ...
0
votes
1answer
22 views
Finding the Dual of an LP, where variables are not well isolated.
Could someone guide me through how I could go about finding the dual of the following LP. Let $A \subset \Bbb R^{m x n}$, and $x = (x_1, ..., x_m)$.
$$\text{max } z
\\
\text{st } z \le x^TA_{.j} , \...
1
vote
1answer
34 views
Facility Location Problem with Integer Linear Programming
I am trying to create a linear programming formulation based on a facility location problem. In this problem, it is the goal to minimize the costs of travelling from 50 customers to 3 facilities. ...
0
votes
0answers
25 views
Prove that in finite steps you can know if the solution set of linear programming problem is unbounded [duplicate]
Given is $\max\left\{c^T \cdot x | Ax \leq b, x \geq 0\right\}$ which is a linear programming problem and its solution set $M$. Prove that you can find out in finite steps if $M$ is unbounded.
It ...
1
vote
0answers
22 views
Solving motion equations using linear programming
I'm trying to solve this physics problem using the Simplex method
$$\text{Minimize}\qquad \int _0 ^T |f(t)|dt \qquad \text{subject to}\\
j(t) = j(0) + \int_0^t f(t)dt, \forall t \in [0,T] \\
m(t) = m(...
1
vote
2answers
29 views
Knowing how to order $\{a,b,c,0\}$ implies knowing how to order $\{a,b,c,0,-a,-b,-c\}$?
Suppose I have $4$ real numbers $\{a,b,c,0\}$ and I know
that they are all different
how to order them from smallest to largest, e.g., I know that $b<a<0<c$
Does this imply that I know how ...
0
votes
2answers
43 views
Linear Program to find line that best fits a set of points
Given a set of points $(x1,y1),(x2,y2),...,(xn,yn)$ the following is supposed to be a linear program that finds a line$ $ax+by=c that minimizes $max|ax_i+by_i-c|$.
Let $z=max|ax_i+by_i-c|$
This ...
0
votes
1answer
102 views
Solving an LP problem with an upper limit for the variables
Im trying to solve the Above LP. Now, can we apply just simplex considering that we can treat the upper bounds of the variables as constraints.
Meaning, we need to add $6$ slack variables, and it ...
0
votes
0answers
12 views
Raise as a problem of $ PL $ the following non-linear programming problem $ (P) $ without restrictions:
Be $ f_{i}: \mathbb{R}^{n} \rightarrow \mathbb{R} $, $ m $ related functions of the form: $$ \left \{\begin{array}{l} f_{ i} (x) = a_{i}^{T} x + b_{i} \\ i = 1,2 \cdots, m \end{array} \right. $$ where ...
0
votes
1answer
45 views
2 player zero-sum-game rock paper scissors expected loss
For the Rock-Paper-Scissors game, I am trying to determine the expected loss for P1.
The following matrix displays how much P1 has lost:
A:
| 0 1 -1 |
| -1 0 1 |
| 1 -1 0 |
I am trying to find ...
