Stack Exchange Network

Stack Exchange network consists of 174 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
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 ...