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

learn more… | top users | synonyms

0
votes
1answer
19 views

Linear equation system to standard form

So I have this linear equation system: $inf \{3x_1 - x_2 - 2x_3 + x_4\}$ $x_1 + 4x_2 - x_3 - 3x_4 ≤ 3$ $-2x_1 + x_2 + 2x_3 - x_4 ≥ -1$ $5x_1 - 3x_2 + x_3 + 2x_4 ≤ 4$ $x_1 ≥ 0, x_2 ∈ R, x_3 ≤ 0, x_4 ...
3
votes
1answer
31 views

Transforming a $0$-$1$ knapsack problem into the standard form

I have the following $0$-$1$knapsack problem: $$\begin{align*} &\mathrm{Max} : \quad z= 3x_1 -4x_2+5x_3+7x_4-6x_5+x_6\\ & \mathrm{subject\ to}: -2x_1 +x_2 +10x_3 +3x_4 -5x_5+12x_6 \leq 4 \...
1
vote
0answers
37 views

Transform an assignment problem to use the Hungarian algorithm

I have this assignement problem: There are three machines to perform four tasks. The costs of assigning to a machine each of the tasks are given by the following matrix: $$\begin{pmatrix} ...
1
vote
0answers
19 views

Linear programming is continuous

Consider an arbitrary linear program: $$\max \vec c \cdot \vec x$$ subject to: $$\textbf{A}\cdot \vec x = 0, \quad \vec a \le \vec x \le \vec b$$ Assume that this program is feasible and bounded. ...
2
votes
0answers
27 views

Show that matrix is totally unimodular

I want to show that this matrix is totally unimodular: \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & ...
3
votes
1answer
866 views

Prove optimal solution to dual is not unique if optimal solution to the primal is degenerate and unique.

How do I prove an optimal solution to dual is not unique if an optimal solution to the primal is degenerate and unique? What I tried: Let the primal be $$\max z=cx$$ subject to $$Ax \...
1
vote
1answer
21 views

A more general case of assignment problem

Recently I've learned hungarian algorithm for solving the assignment problem, Now I'm curious about how to solve more general problem: for given $n \times m$ table select several numbers, maximizing ...
2
votes
2answers
45 views

linear programming infeasibility, dual & primal relation

By the strong duality theorem we know that LP can have 4 possible outcomes: dual and primal are both feasible, dual is unbounded and primal is infeasible, dual is infeasible and primal is unbounded, ...
2
votes
0answers
8 views

How to get inequality representation of cone give by generators

To be as specific as possible, I have a subspace $I \subset R^{14}$ of dimension $3$ and an $11\times14$ matrix $A$ with linearly independent rows spanning the orthogonal complement of $I$. I have an ...
0
votes
1answer
30 views

Can an unfeasible solution be optimal in an LPP

In a linear programming problem, Is it possible to have an unfeasible solution that is optimal?
-1
votes
2answers
35 views

Solving a linear problem using complementary slackness condition

Question $\max \space\space z= 8x_1 + 6x_2 -10x_3+20x_4+2x_5$ $\text{s.t.}\space\space\space\space\space 2x_1+x_2-x_3+2x_4+x_5= 25$ $\space\space\space\space\space\space\space\space\space\...
0
votes
1answer
57 views

Setting up an LP problem on producing linear board in jumbo reels

I have to set up a linear programming problem corresponding to the following scenario: What I tried: I think we have 8 templates for 1 $68 \times l$ reel (or whatever): $22,22,22$ (66) $20,...
2
votes
0answers
16 views

Is there a good term for pairs of related variables in a system?

(Non-mathematician here. Sorry). Suppose you have a problem with lots of unknowns. The problem allows many solutions (possibly infinite). Certain pairs of unknowns (you don't know which ones) ...
1
vote
3answers
56 views

Mixed Integer Linear Programming Conditional Constraints

I have a set of variables: $x_1,x_2,x_3,x_4$ $x_1$ is a binary integer variable while the rest are real numbers all between 0 and 1 I want a constraint such that: if $x_2+x_3+x_4$>0 then $x_1=1$ ...
0
votes
0answers
18 views

Total support in matlab

I need help writing an algorithm in Matlab telling me if a radom matrix has total support or not. I'm trying to use the Linprog formula, but I don't understand it.
1
vote
1answer
40 views

Method to convert a worded problem to a linear problem

Acme manufacturing company has contracted to deliver home windows over the next $6$ months. The demands for each month are $100, 250, 190, 140, 220,$ and $110$ units, respectively. Production cost per ...
1
vote
1answer
36 views

Is this a correct formulation of a linear programming problem?

I apologise as English is not my first language so sometimes I get stuck on problems like these as it can confuse easily. Show & Sell can advertise its products on local radio and television ...
0
votes
0answers
7 views

the optimal solution of $min$ $-x-y+(1/2)(x+2y-3)$

the optimal solution of $min$ $-x-y+(1/2)(x+2y-3)$ s.t. $x,y=0,1,2, or $ $ 3$ Attempt: if we tale the gradient of the objective function we have $[-1/2,0]^T$. This means that y could take any ...
0
votes
1answer
20 views

Has $\max\{cx:Ax\le b\}$ an optimal solution $x_1=\sqrt 2$ with $A\in \{-1,0,1\}^{m*n}$ with exactly one $1$ and one $-1$?

Let be $A\in \{-1,0,1\}^{m*n}$ with exactly one $1$ and one $-1$ and zeroes at each line. $c\in\mathbb{Z}^n$ such that $\sum\limits_{j=1}^{j=n}c_j=0$. $b\in\mathbb{Z}^m$ positive. How to start to ...
1
vote
0answers
51 views

Develop a model for determining the optimal production schedule in a manufacturing facility

I have to formulate (linearly) the following problem mathematically: What I tried: 1. Variables Let $x_{ijk} = 1$ if, in month k, product i should be made in production line j, where $i=...
0
votes
0answers
39 views

Weights in goal programming

I'm not quite convinced about assigning weights in goal programming. Here is an example formulation problem. What I tried: Let $x_j$ be the number of minutes for ad $j = R, T$ We want to ...
1
vote
0answers
34 views

Model linearly: Determine amount of units for production

A company produces 2 products in a week. Let $x_i$ denote the number of units of product $i$ to produce. Each product requires liters of Chemical X to make. Info is given below: \begin{array}...
0
votes
1answer
18 views

Why the dual and the canonical dual may have the same optimal solution?

For instance let be \begin{cases} \max & 3x_1 &+2x_2 &+4x_3 & -x_4\\ &x_1 &+x_2 &-2x_3&&\le4\\ &2x_1&+3x_3&&-4x_4&\ge 5\\ &2x_1&+x_2&...
1
vote
1answer
35 views

Converting generic linear problems into their dual

I'm revising how to do dual problems in linear algebra. I'm very weak in Linear programing but I struggle to cope with the topic during lectures and assignements. I have to convert the following ...
0
votes
0answers
10 views

Computational complexity of a feasibility LP with $m$ inequalities, in $d$ dimension?

How would you quantify the computational complexity of feasibility LPs? Say for example an LP with $m$ inequalities : $$ \begin{cases} \mathbf{a_i}.\mathbf{x} \leq b_i, i \in [m] \\ \mathbf{x} \in \...
0
votes
0answers
29 views

Extreme Points, BFS, Extreme Directions

I'm trying to prove the two theorems below. 1) Every basic feasible ray of standard-form (P) is an extreme ray of its feasible region. 2) Every extreme ray of the feasible region of standard-form (P)...
0
votes
1answer
27 views

All faces of the n-dimensional hypercube

I am asked to determine all faces of the $n$-dimensional hypercube $$C_n = \left\lbrace x\in\mathbb R^n \;|\;\forall i\in\lbrace1\ldots n\rbrace : |x_i|\leq1\right\rbrace $$ I already know that the ...
1
vote
1answer
30 views

Solving Linear Optimization Problem with Shortest path Algorithm

A little while ago I read a wiki about alternating between linear programming and shortest path problem (https://en.wikipedia.org/wiki/Shortest_path_problem#Linear_programming_formulation). I'm just ...
1
vote
2answers
70 views

Find the optimal solution without going through the ERO's

All I got is that $$12y_1 + 7y_2 + 10y_3 = 2(0) + 4(10.4) + 3(0) + 1(0.4)$$ and $y_2 = 0$ because $x_6$ is in basis. How do I find $y_1$ and $y_3$ without going through the simplex method? I took ...
0
votes
0answers
9 views

Three variable linear diophantine.

Assume I know $a,b,c,d\in\Bbb N$ in $ax+by+cz=d$ and I know there is an unique $x,y,z>0$ such that this holds can I find such $x,y,z$ in $O((\log (abcd))^\alpha)$ time for some fixed $\alpha>0$?
1
vote
2answers
36 views

Transforming a worded problem into a Linear Problem system of equation

(Advertising problem) Show & Sell can advertise its products on local radio and television (TV). The advertising budget is limited to $£10,000$ a month. Each minute of radio advertising costs $£15$...
1
vote
1answer
38 views

piecewise linear minimization equivalent to linear programming

Why is \begin{equation} \begin{aligned} & \min\max_{i=1,\ldots,n} & &a_i^Tx+b_i\\ \end{aligned} \end{equation} equivalent to an LP \begin{equation} \begin{aligned} & \min & &...
-1
votes
1answer
23 views

Where does the duality comes from in linear programing and can we get the optimal basis from it?

$$\begin{cases} \max & c^Tx\\ & Ax\le b\\ & x\ge 0 \end{cases}\Leftrightarrow \begin{cases} \min & y^Tb\\ & y^TA\ge c^T\\ & y^T\ge 0 \end{cases}$$ Then we come to the ...
0
votes
0answers
8 views

Why $x_B=\tilde b +\tilde A x_{\bar B};c^Tx=\psi+\tilde c^Tx_{\bar B}$ doesn't describe an optimal solution iif $\tilde c_i\le 0,\forall i$

How to counterprove the assertion that if a feasible dictionnary in the type \begin{cases} x_B=\tilde b +\tilde A x_{\bar B}\\c^Tx=\psi+\tilde c^Tx_{\bar B} \end{cases} describe an optimal ...
6
votes
1answer
3k views

Linear Programming: Three variable graphical solution

A small bank offers three type of loans: housing loans at $8.50$% interest, education loans at $13.75$% interest rates, and loans to senior citizens at $12.25$% interest. Further, it needs to ...
-1
votes
1answer
75 views

Linear Programming - The Big M Method - Proof questions [closed]

I'm having difficulties on answering the following questions (first time I'm trying to prove something), any help would be awesome! Thanks in advance. Q: It is possible to combine the two phases of ...
0
votes
1answer
29 views

Max-Flow Min-Cut

So I have worked out that there is a Max Flow of 10, which therefore means there is a minimum cut also of 10 however how do I draw a minimum cut of 10 on this image? (Something like this - image)
0
votes
0answers
15 views

Basic Linear Algebra/Root finding question

What is the general method for solving this problem? $\theta_n.1_T'.z_T=0_n$ where $\theta_n$ is a n x 1 vector of parameters that are free to vary, $1_T'$ is a 1 x T vector of ones, $z_T$ is a T x ...
2
votes
0answers
23 views

Linear programming: choosing entering variable

maximize 10𝑥1 + 12𝑥2 +12𝑥3 subject to 𝑥1 + 2𝑥2 + 2𝑥3 + 𝑥4= 20 2𝑥1 + 𝑥2 + 2𝑥3+𝑥5= 20 2𝑥1 + 2𝑥2 + 𝑥3 +𝑥6= 20 𝑥1, … , 𝑥6 ≥ 0 This is my first step for simplex tableau x1 x2 ...
5
votes
0answers
43 views

Optimizing value of discrete harmonic function at a given point

Let $n>0$, and let $S_n$ denote the discrete square $S_n=[|-n,n|]^2$ (so $S_n$ has $(2n+1)^2$ elements). Let $K_n$ denote the set of four corner points $\lbrace (\pm n,\pm n)\rbrace$, and $C_n=S_n\...
0
votes
0answers
19 views

$\max\{c^Tx:Ax\le b,x\ge 0\}=+\infty$ iif it exists $j\in\{1,…,n\}$ such that $\max \{x_j:Ax\le b, x\ge 0\}=+\infty$

Show a vector $\vec c$ exists such that $\max\{c^Tx:Ax\le b,x\ge 0\}=+\infty$ if and only if it exists $j\in\{1,...,n\}$ such that $\max \{x_j:Ax\le b, x\ge 0\}=+\infty$ I'm only asking for a hint ...
1
vote
1answer
36 views

Write the dual LP of the primal LP problem

I have to find the dual of the lp problem given below Minimise $$z=-x_1+\frac43 x_2$$ subject to∶ $$\begin{array}[t]{l} 2x_1+4x_2\le16\\ -\frac{1}2 x_1-x_2\le4\\ -3x_1+4x_2\ge-24\\ x_1≥0,x_2≤0 \end{...
1
vote
1answer
59 views

Is this a proper alternative way for math model for TSP(Travelling Salesman Problem)?

I have never seen a model that uses indexing in any article.So I have decided to publish it to be sure. I think indexing model is more suitable for generalizing the model than the subtour elimination ...
0
votes
0answers
20 views

$\{x\in R^n | Ax \leq b\} \cap \{x \in R^n | Dx \leq d\}= \emptyset$ iff there is a vector $c \in R^n$ such that $c^Tx < c^T y$

Consider two non-empty polyhedra $P := \{x\in R^n | Ax \leq b\}$ and $Q := \{x \in R^n | Dx \leq d\}$. Show that $P \cap Q = \emptyset$ if and only if there is a vector $c \in R^n$ such that $c^Tx <...
2
votes
0answers
173 views

Prove an artificial variable that leaves the basis will never return.

This is in the context of the Big M Method in the simplex algorithm in linear programming. Prove an artificial variable that leaves the basis will never return. I have no idea how to start this. ...
1
vote
1answer
63 views

Solving a linear program thanks to complementary slackness theorem

Using the complementary slackness theorem, say if the following basis optimal: $$x_1*=0=x_5*,x_2*=4/3,x_3*=2/3,x_4*=5/3$$ \begin{cases} \max & 7x_1 &+6x_2&+5x_3&-2x_4&+...
1
vote
0answers
22 views

Can a linear program be optimal if its basis is infeasible?

I want to know thanks to the dual theorem wether the following basis is or isn't optimal. That is to say looking for the slack variables. As far as the third line doesn't respect the constraints: $...
0
votes
0answers
12 views

Which coefficient to start with in the dictionary method?

I used to start with the variable with the biggest coefficient in the goal function (in the case of max). yet I read an article that behaving like this may lead to loop. It is rather preferred to do ...
0
votes
0answers
21 views

Which Denominations to use for payroll with no returned change

I want to solve the following problem. It is not a homework. Assume that a company pays payroll to employees every period, the sum of the salaries for period is $T$. The accountant goes to the bank ...
0
votes
1answer
36 views

Linear Optimization proof. Duality proof.

I need help with this problem. The exact problem is in this link http://d2vlcm61l7u1fs.cloudfront.net/media%2F959%2F959d289e-6f26-4e21-875e-bb71f3f5a49f%2Fphprimn1q.png Sorry for the poor formatting. ...