Questions tagged [linear-programming]
Questions on linear programming, the optimization of a linear function subject to linear constraints.
3,078 questions
0
votes
2answers
22 views
Find the Dual of a Linear Programming Problem
I have a very simple linear programming problem with the following constraints:
Minimize $3x_1 + 2x_2 - 33x_3$
subject to
$x_1 - 4x_2 + x_3 \leq 15$
$9x_1 + 6x_3 \leq 12$
$5x_1 + 9x_2 \geq 3$
$...
1
vote
0answers
9 views
Simplex method, amount to reduce basic by when non-basic is entered.
Where I've written the vector with $x_B, x_N$ here that should be considered as
a partition between them (there should be a horizontal dashed lines or something
between them).
\begin{align*}
f(x_{...
0
votes
1answer
29 views
The simplex algorithm--example
Here on the page 30, why $(z_3,z_3)=1$: as written on that page 30:
minimize the sum of the artificial variables, starting from the BFS where the absolute value of the artificial variable for each ...
-1
votes
0answers
46 views
How do I set up this linear programming question? [on hold]
A company has planned, authorized and budgeted 10MM in capital expenditure over the
next five years to acquire new fixed assets such as property, plants and equipment. Design
and solve four ...
0
votes
0answers
18 views
A concrete example of some simplex theory
I have the following :
What I'm interested in is a concrete example that relates to these expressions,
I'm not sure what one would be.
"If we have at hand an explicit representation of $B^{-1}$...
0
votes
0answers
13 views
Simplex Algorithm, determining Two Phase is required and choice of artificial variables
Given the following system :
\begin{align*}
\text{minimise } z = &2x_1 &+ 3x_2 &+ 3x_3 &+ x_4 &- 2x_5& \\
\end{align*}
Subject to
\begin{align*}
&...
0
votes
1answer
19 views
How can I efficiently find the number of quadruples in an array which sum up to k?
Example : $[4,2,2,2,2], k=8$
Answer : $- (1)$
As only $1$ quadruple $(2+2+2+2=8)$ exists whose sum is '$8$'.
I know the brute-force $O(n^4)$ algorithm , I even know an $O(n^2\cdot log(n))$ ...
0
votes
1answer
14 views
Dual problemn -> what to do with summand in objective function not connected to variable
say I have the simple primal problem
$$
\text{max } Z = 3x_1 + 2x_2 -7
$$
s.t.
\begin{align*}
3x_1 + 5x_2 &\ge 6 \\
7x_1 + 55 x_2 &\ge 44 \\
x_1,x_2 &\ge 0
\end{align*}
Now would I be able ...
0
votes
1answer
38 views
Writing integer programming math statements
I am currently in a linear programming class, and we are on the topic of integer programming. I am asked to write certain relationships in "integer mathematical formulation" with binary ($y_i$), ...
0
votes
0answers
14 views
Optimal basis generation using simplex
Given the objective function $\sum_{i=0}^{i=n} t_i$ (which I want to minimize), constraints $At = u, t \geq 0$ where $A \in m \times n$, and $ n>m$, I'm trying to determine all of the possible ...
0
votes
0answers
17 views
Convex combination and zero sum game
Diagram 1
Diagram 2
Hello, I have some questions regarding zero sum games and linear programming. As you all can see, in Diagram 1, there is no pure Nash Equilibrium unless if we use mixed strategy ...
-1
votes
0answers
27 views
How do I transform this non linear optimization to a linear? [on hold]
Hello I've been working with this problem, I used a software that transformed the equation and gave results apart from x1,x2...xn=0 but treated the problem as mixed int linear, but I want to be able ...
-1
votes
0answers
15 views
Step-by-step method for taking dual of min-cost flow [on hold]
I have been struggling to find how text books actually take dual of the following function. I don't mind either Lagrangian, normal method, or Farkas as long as there is a systematic way to show this. ...
1
vote
1answer
29 views
Linear programming - optimality conditions
From Bertsimas intro to linear optimization - exercise 3.7:
Consider a feasible solution x to a standard linear program:
\begin{align*}
\min\quad & \textbf{c'x} ...
1
vote
1answer
26 views
Is the revised simplex method picky?
I found these notes: https://www.math.ubc.ca/~loew/m340/rsm-notes.pdf on Google. I'm trying to implement this algorithm in C to help me learn about linear programming and programming in C. Right now I'...
0
votes
0answers
20 views
How ot use indicator variables as an objective function
I have a decision variable Y[c,j,i] = 1 if machine j is candidate for machine i of client c, 0 otherwise.
I am using the weighted Euclidean distance to measure the ...
0
votes
0answers
11 views
Scalable size of feasible linear constraints generator in matlab
I need to generate linear constraints in Matlab with the hope that I can scale the size.
I can easily generate constraints of the following form
$$ i/n \leq x_i \leq n/i, \ \forall i\in[n].$$
Here, ...
1
vote
0answers
31 views
Did I formulate this problem in the correct way?
A company makes two products, product 1 (X1) and product 2 (X2).
Profits per unit are $\$30.00$ for $X_1$ and $\$15.00$ for $X_2$.
Hours per unit for each of the three departments are:
Dept. A (hrs....
1
vote
0answers
17 views
Show that Feasible Region of Linear Program is a Single Point
I have a set of variables $x_i$ for which $x_i \ge 0$, and a set of linear equations relating them: $A \mathbf{x} \le \mathbf{b} $. The typical constraints for a linear program. Is there a general way ...
-1
votes
1answer
49 views
Help with a minimization question
Let
$$z_1 = 3x_1 + x_2 + x_3$$
$$z_2 = 2x_1 + 5x_2 + 2x_3$$
$$z_3 = x_2 + 7x_3$$
There exists a variable $w$ defined as:
$$w = \min(z_1, z_2, z_3)$$
Also, the $x$-variables are subject to the ...
0
votes
0answers
70 views
+50
How to solve the following equations using simplex method?
Software Engineer here,
I am trying to find an algorithm to solve the following problem, basically I have 3 equations that you can see bellow, and all values of X, Y, Z, and Xi, Yi, Zi's are known. ...
0
votes
1answer
26 views
simplex method - full tableau negative coefficients for basic variable
Minimize -10𝑥1−12x2-12x3
Subject to :
x1+2x2+2x3+x4=20
2x1+x2+2x3+x5 =20
2x1+2x2+x3+x6 =20
xi >= 0
With x4,x5,x6 the slack variables which we take as our basic variable and all equal to 20 ...
2
votes
1answer
26 views
How can the sum of one and infinity norm minimization problem subject to constraints be rewritten as a linear program?
I have been trying to convert the following problem into a standard LP problem
$$\begin{array}{ll} \text{minimize} & \|x\|_1 + \|x\|_\infty\\ \text{subject to} & A x = b\end{array}$$
I know ...
0
votes
0answers
15 views
Luenberger - Linear programming - The simplex method [on hold]
Show that if the vectors $a_1, a_2, . . . , a_m$ are a basis in $E^m$,
the vectors $a_1, a_2, . . . , a_{p−1}, a_q, a_{p+1}, . . . , a_m$ also
are a basis if and only if $\overline a_{pq} \neq 0$, ...
-1
votes
1answer
35 views
Solving multiple equations to a maximum value [closed]
I am trying to solve an order inventory problem that can be shown as:
$$B,C,D,E,A+B,A+D,B+E<100$$
And I need $A+B+C+D+E $ to be as large as possible. Since these equations will change over ...
2
votes
1answer
38 views
Linear Programming - Labor Allocation
Looking for guidance on specification for an unknown subset of linear programming. The task at hand:
For a firm making staffing allocation decisions, accept exogenous levels of required services (b),...
0
votes
0answers
34 views
TRUE OR FALSE: A noncanonical linear programming problem with more unconstrained independent variables than constraints is unbounded.
I believe this is true because when we have unconstrained independent variables, we must pivot each one and file it in order to convert the tableau to canonical form.
Now, if we have more columns ...
0
votes
0answers
46 views
Using non-negative continuous variable to constrain binary variable
I have a problem. I am programming a mixed integer linear model. $S_{ij}$ $\in$ {$0$,$1$}. And $o_{ij}$ is a non-negative continuous variable. $o_{ij}$ lower bound is zero. where $i$ and $j$ $=1,2,3,.....
1
vote
0answers
31 views
Are there any known methods for transforming a system of linear inequalities into a system of linear Equalities?
Begin Question
Are there any known algorithms for transforming a system of linear inequalities into a system of linear equalities? The resulting system is only allowed to use equality statements ($=$)...
1
vote
0answers
41 views
Linear programming question: Sensitivity Analysis
I was given a problem where a home computer table sells for $36$ dollars and uses $6$ board ft of lumber, $2$ finishing hrs, and $2$ carpentry hrs.
Should the company manufacture any home computer ...
2
votes
1answer
40 views
How to linearize a min equality?
I have a linear program that has a constraint as follows :
$$a = \min\{b,x\},$$
where $x$ is the variable.
I tried to write it as $$a\leq\min\{b,x\}\tag{1},$$
and
$$a\geq\min\{b,x\}.\tag{2}$$
...
1
vote
1answer
27 views
State a system as a canonical minimum problem
Suppose we have a linear system $$Ax=b,\,\,x\ge0,$$ where $A$ is a $m\times n$ matrix and $b$ is a given $n\times 1$ column vector.
Def: We say a problem is a canonical minimum problem if the problem ...
0
votes
1answer
29 views
Why there isn't lexicographically smallest solution to a bounded linear program?
I am learning computational geometry when I run into this confusion. "A bounded 2D linear program may not have a lexicographically smallest solution", as the book says. I wonder why? I think we can ...
0
votes
0answers
26 views
Maximization using dual simplex method - problem
My teacher gave us on a test following problem:
Following ILP(Integer linear programming) problem:
$ 2x_1 +5x_2+4x_3 ->max $
$ 3x_1 +3x_2 + x_3 \leq 20 $
$ 2x_1+ 3x_2 + 4x_3 \leq 30 $
$ x_1,...
0
votes
1answer
39 views
Need help to determine basic solutions of the system of linear equations
I'm currently stuck in determining the basic solutions for the following system of linear equations, would anyone be kind enough to determine it for me? Thanks!
0
votes
0answers
30 views
Linear inequality constraint - in KKT optimisation
I have a query regarding whether KKT is optimal with some linear inequality constraint and non-linear inequality constraint. For KKT to be optimal the inequality constraints must be convex.
We know ...
2
votes
0answers
80 views
LP-problem simplex with 3 variables
I have this LP-problem which I need to solve using simplex calculations.
$$
\max Z = 12x_1 + 18x_2 + 10x_3
$$
when,
\begin{align}
2x_1 + 3x_2 + 4x_3 &= 50\\
-x_1 + x_2 + x_3 &= 0\\
-x_2 + \...
0
votes
1answer
241 views
How can I maximize the probability?
John is playing a game against a magician.In this game, there are initially 'N' identical boxes in front of him and one of them contains a magic pill ― after eating this pill, he becomes immortal.
He ...
0
votes
1answer
46 views
How to show that a linear program has no maximum?
Suppose you have a standard maximum program, where the constants on the right hand side are nonnegative. Suppose further that a variable 𝑥 occurs on the objective with positive coefficient, but ...
0
votes
0answers
24 views
Linear programming relation between unbounded solution set and homogeneous system
I need to show that the solution set K to the constraints Ax $\le$ b, x$\ge$0, b$\ge$0 is unbouded if and only if the corresponding homogenous system Ax$\le$0, x$\ge$0 has a non-zero solution. I'm not ...
0
votes
0answers
10 views
A rational solution to a MILP of polynomial size
I have a question regarding the size of a rational solution to MILP. Suppose that I am given an MILP problem where all coefficients are rational numbers. I know that if the problem is feasible, then ...
0
votes
1answer
17 views
Finding basic feasible solution graphically
I'm supposed to find the basic solutions of the given LPP graphically. I know what a bfs means, I can find that in other way (I mean by method mentioned in this post), but I don't know how to do it ...
0
votes
1answer
32 views
Why does this happen in the linear program?
Use the BIP brach and cut algorithm to solve the following problem interactively.
$$\max \ z=2x_1-x_2+5x_3-3x_4+4x_5\\ s.t. 3x_1-2x_2+7x_3-5x_4+4x_5\le6\\ x_1-x_2+2x_3-4x_4+2x_5\le0 \\ x_j \\ binary$$...
3
votes
1answer
61 views
Why is the following not a a linear programming problem?
$$\begin{array}{ll} \text{maximize} & 3x + 3y − 30\\ \text{subject to} & |x−2|−|y| \leq 5\end{array}$$
This is totally a LLP to me, just not in its standard form. I really don't know why it ...
1
vote
1answer
15 views
Computing initial feasible basis in the simplex algorithm
My textbook introduces the following method to compute initial feasible basis in the simplex algorithm:
What is the implication for the original LP if the auxiliary LP's objective function can't ...
2
votes
1answer
30 views
Transforming a linear program into its canonical form for use in the simplex algorithm
A typical example of a LP in my lectures looks like this:
From what I've learnt, we are ready to implement the simplex algorithm on this LP, since $x_3, x_4, x_5$ all have positive signs, and so are ...
0
votes
1answer
30 views
in linear programming, why does the dual have constraints?
in introduction to linear optimization ($\text{p. 142}$), they take the standard form problem:
minimize $c'x$, s.t. $Ax = b$, $x\geq 0$
they relax the constraints and define:
$g(p) = \min_{x\geq 0}[...
0
votes
1answer
33 views
Linear Programming Negativity Constraints
What happens when a variable is negative?
An example would be:
Maximize z = 3x1 + 4x2, subject to constraints:
2x1 + 3x2 <= 10
2x1 - 4x2 <= 20
x2 <= 10
x1 >= 0
To set up an Linear ...
0
votes
1answer
33 views
Given $\epsilon \in [0, 1]$, find an analytic solution to $\underset{x \in \Delta_k | x_1 \ge \epsilon}{\text{argmax}}\;x^Tb$.
Let $\epsilon \in [0, 1]$, $b \in \mathbb R^k$, and $\Delta_k := \{x \in \mathbb R^k | x \ge 0,\; 1^Tx = 1\}$ be the unit $(k-1)$-dimensional simplex with $k\ge 2$.
Question
Find a closed-form ...
0
votes
0answers
28 views
Pivoting Proof on a Canonical Maximum Tableau
Problem in Question
For this problem, we are supposed to prove that pivoting on $a_{ij}$ in a canonical maximum tableau is equivalent to solving the $i^{th}$ equation of the tableau for the $j^{th}$ ...
