Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [linear-programming]

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

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}$ ...