Tagged Questions

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

learn more… | top users | synonyms

0
votes
0answers
23 views

How to practically perform reinversion in PFI (Product Form of Inverse) Simplex.

While doing Revised Simplex using Product Form of Inverse. We have product of set of Eta Vectors(Elementary Matrix) to describe the Basis Inverse after certain number of steps in simplex. ...
0
votes
1answer
75 views

Game Theory in relation to economics and sociology [closed]

I know some algebra and calculus, and have been reading about Linear Programming/Game Theory. How are the models in this field, even the infinite calculus models, usable in macro economics. Even ...
1
vote
2answers
71 views

Minimization of log-sum-exponential function subject to constraints.

I would like to minimize the following function: $f(x)=log(e^{-x_1}+..+e^{-x_n})$ Subject to: $\sum_{i=1}^{n}{x_i}=1$ $0 \leq x_i \leq 1$ So far I have discovered the following: If all the ...
0
votes
0answers
31 views

Mixed Interprogramm remodeling

for example i have the following problem min z 5 x_1a + 6 x_1b - 3 x_2a + 0 x_2b <= z -3 x_1a + 0 x_1b - 1 x_2a + 2 x_2b <= z x_1a + x_1b = 1 (Constraint say of this group only one variable ...
0
votes
1answer
29 views

About canonical linear programs.

Starting out with linear programming, I'm having some questions about canonical linear programs: Do all linear programs have a canonical form? So far I couldn't figure an example stating otherwise. ...
1
vote
0answers
30 views

On the injection of exactly two artificial variables into the Phase I of a two-phase simplex

I am relatively new still to linear optimization and as I understand it, the two phase method is a common practice for finding the bfs before using the simplex or a simplex like solver (a solver ...
0
votes
0answers
20 views
0
votes
0answers
15 views

Objective Value of LP as a function of RHS of Constraints

I saw the following statement in a paper, but am having trouble finding a reference for it. Consider the optimization problem $y = \max_x c^\top x$ subject to $Ax = b$ and $x \ge 0$. Then, written as ...
0
votes
1answer
29 views

Reference request: optimal solution for linear program is rational

From various lecture notes and such that are floating around, I get the impression that if a linear program has rational coefficients and has a finite optimal solution, then that solution will be ...
0
votes
0answers
114 views

What are canonical vectors?

I just begun with linear programming. Given an objective function $z$ and certain restrictions defined by $Ax = b$, we got to find the values necessary to maximise or minimise that function's ...
1
vote
0answers
45 views

Minimising waste in a cutting problem.

I have three possible board sizes: $8$, $10$ and $12$ feet long. I want to make some number of cuts to these, say, $3, 2,1,1,1,6,5,3,4,2,1$ feet cuts and I want to minimize waste. I've done a quick ...
1
vote
1answer
61 views

Linear Programming - Simplex Method

Let, $\begin{array}{lcl}Min: z =10x_{1}+5x_{2} \\ \\ 20x_{1}+50x_{2} \geq 200 \\ 50x_{1}+10x_{2} \geq 150 \\30x_{1}+30x_{2} \geq 210 \\x_{1},x_{2} \geq 0\end{array}$ a linear programming problem. ...
0
votes
1answer
90 views

can I get help in solving this equation using simplex method big-M method

Objective: $\max Z= 100x_1+300x_2+400x_3$ s.t. $10x_1+20x_2+30x_3≤1600$ $\;\,\quad10x_1+15x_2+20x_3≤1500$ $\;\,\quad x_2+x_3≤50$ $\;\,\quad x_1+x_2+x_3=70$ $\;\,\quad x_1,x_2,x_3≥0$
0
votes
0answers
14 views

Transportation problem with intermediate depots

So I've got the following transportation problem (where I have to find the lowest costs while satisfying the demands) with depots $1,2,3$ and destinations $6,7$. There are also two intermediate depots ...
1
vote
1answer
93 views

Cycling in Simplex Method - Smallest Subscript Rule

Could someone explain to me how using the smallest subscript rule causes a cycling LP to terminate? At the moment it looks to me that a program would use it to determine whether the matrix from the ...
0
votes
0answers
110 views

How do I convert max min problem into a linear programming problem?

Let $A$ be a given $m \times n$ matrix, $c$ a given $n$-vector, and $b$ a given $m$-vector. $$\max \min (c^T x - y^T Ax + b^Ty) \text{ such that } x,y \ge 0$$ Show that this problem can be reduced ...
1
vote
0answers
267 views

Transportation problem: optimal solution

So I have an issue with finding the optimal solution (the lowest costs) to a transportation problem. Given the following problem, with $A$ the depots, $B$ the destinations and $C$ the $(i,j)$ matrix ...
2
votes
0answers
72 views

Post-optimality analysis: Change in one of the constraints

Consider the LP: max $\, -3x_1-x_2$ $\,\,$s.t. $\,\,\,\,$ $2x_1+x_2 \leq 3$ $\quad \quad \ -x_1+x_2 \geq 1$ $\quad \quad \quad \quad \ > x_1,x_2 \geq 0$ Suppose I have solved the above ...
2
votes
1answer
39 views

How do I solve max min (x − y) and min max (x − y) such that y≥0 and x≥0?

solve max min (x − y) and min max (x − y) such that y≥0 and x≥0 I don't have a clue where to start.
0
votes
0answers
29 views

Linear programming problem - do we have enough data here?

I am to solve a following problem, but it seems to me that it is ill-formulated, i.e. there's not enough data. Am I right? If not what would be the mathematical model for it? Every coffee table ...
1
vote
1answer
23 views

Linear program that is taking a maximum over $n$ linear programs?

Suppose I have feasible linear programming problems $P_1, \dots, P_n$. Say $f$ assigns a feasible linear program its optimum value. How can I find a linear program $P'$, such that $f(P') = ...
1
vote
0answers
22 views

Is leq sufficient for the existence of a slack variable based bfs in a simplex?

I'm attempting to write a MPS to custom format converter for a generalized simplex algorithm and I am running into a couple of difficulties. According to this tutorial on the Big-M method for ...
3
votes
1answer
39 views

Runs in Rummikub simulation in AMPL

I'm taking a class in linear programming and the project involves modelling a Rummikub game. I have made the simplifying assumptions (for now) that there is no joker and only one piece of each ...
1
vote
1answer
48 views

Solving a minimization of the minimum problem

Let ${\bf c}_{1}$, ${\bf c}_{2}\in \mathbb{R}^{n}$, ${\bf A}\in\mathbb{R}^{m\times n}$ and ${\bf b}\in\mathbb{R}^{m}$. Show how one can solve the optimization problem: min ...
0
votes
0answers
51 views

Linearization of multiple normal functions

I have noticed that it takes a very long time to perform non-linear least squares fitting on datasets similar to this: where there are multiple Gaussian distributions to be fit to experimental ...
0
votes
1answer
23 views

Notation of a linear inequality system.

Sorry to bother with this rather trivial question, but nowhere in my lectures or books can I quite find out what the topmost line means. Maybe I'm forgetting something. Anyway: Line 2 and 3 are ...
0
votes
0answers
30 views

How to pick the leaving variable for Perturbation method? (Linear programming)

I am studying Optimization, a math course. We are going over simplex method and its variances. One of which is called the perturbation method. From this example, O is the objective function and ...
2
votes
0answers
21 views

Determining maximum number of groups - maybe Linear Programming

Given a set D dogs, C cats, and B birds, for each dog d in D, there is a set c(d) which indicates the set of cats that dog d likes and a set b(d) birds that dog d likes. How do I find the maximum ...
0
votes
1answer
64 views

Underdetermined system with inequality constraints

I have an underdetermined system of equations of the form \begin{equation} Ax = b, \end{equation} where $A \in \mathbf{R}^{m \times n}$ with $m < n$, subject to \begin{equation}0 \preceq x ...
0
votes
1answer
72 views

A question about rational number.

Denote $M$ as a $m\times n$ matrix whose components are all nonnegative integers (actually 0 or 1) and $1$ as the $m$ dimensional vector $(1,1,\cdots,1)$. Show that: There is a vector $x_0$ ...
1
vote
1answer
53 views

Why optimization problems cannot be solved by simple derivative?

Let $f(\cdot)$ be a linear function. $f:\mathbb{R}^n\rightarrow\mathbb{R}$ $\;\quad\;\mathbf{x}\;\rightarrow f(\mathbf{x})$. Let $\mathbf{A}$ be a matrix in $\mathbb{R}^{m\times ...
1
vote
0answers
27 views

Optimizing over a set of optimization problems

This is my first time asking an optimization question on here, so I am looking forward to see what will happen here. In the lack of a better title, I wrote it as it is. At a high-level, I can perhaps ...
0
votes
1answer
26 views

making a function non-linear using a Lagrangian function

How Is this formula a Lagrangian function ? And how can a non-linear element be added to a function using this "Lagrangian function" This is where i got this In order to improve the performance ...
0
votes
1answer
21 views

Duality and Optimality Conditions

I have seen the solution and it involves adding a $x_5$ and $x_6$ to the inequalities. I really do not understand why this happens? I have not seen any questions like this yet. Any pointers would ...
0
votes
1answer
33 views

Is the polar of the polar set the original set?

For each $Q \subset \Bbb R^n$, denote $Q^*:=\{z \in \Bbb R^n:z\cdot x \leq 1,\;\;\text{for all}\; x \in Q\}$. Let $P:=\{x \in \Bbb R^n: Ax \leq b\}$, for the matrix $A$ and the vector $b$. It is ...
1
vote
0answers
45 views

Linear Programming, Optimal Solutions

I posted the whole question to give some context, but my problem lies with (iv). I think you're meant to use a formula for the generalization of the optimal solution, but I'm not really sure what ...
0
votes
0answers
29 views

Linear programming to find minimal additive and multiplicative factors

Consider samples $\{x_i,y_i\}$ with $x_i\in\mathbb{R}^N$ and $y_i=\pm1$ and additional $z\in\mathbb{R}^N$. Can one use linear programming to find the minimal $m>0$ and minimal $\epsilon>0$ (e.g. ...
1
vote
1answer
57 views

Enquiry to network flow

Could anyone advise me on how to find a feasible flow to the following graph so that the edges $(2,5), (4,5), (6,5),(6,7)$ are saturated? This means, I have to formulate the network flow as a linear ...
0
votes
1answer
27 views

condition for having a positive solution to a linear equation.

Let $Y$ be a member of $\mathbb{R}^m$. I need a necessary and sufficient condition on a $n\times m$ binary matrix $A$ for having a solution to the linear equation: $$AX=Y$$ Such that $X_i\geq 0$, ...
0
votes
1answer
55 views

Min-Cost-Flow Problem

Given a directed graph $G = (V,E)$ with a cost function $\gamma: E \to \Bbb R_{\geq 0}$ and two vertices $u,v \in V$. How to reduce the problem of finding a directed path from $u$ to $v$ with minimum ...
0
votes
0answers
42 views

Application of Combinatorics, Logic and computability theory in physical science: Tiling of Wang Tile with proportionality

The original problem of Domino Tiling and Wang Tile has great theoretical interest on computability theory... However, the great emerging problem on application of Wang Tile in material science and ...
0
votes
1answer
69 views

Linear programming with non-convex quadratic constraint

Could anyone let me know if the following linear programming problem can be solved in polynomial time or should be NP-hard? $\min c^Tx$ s.t. $x^TQx\geq C^2, x\in [0,1]^n,c\in ...
1
vote
0answers
25 views

Reduced Cost in Network Simplex Algorithm

On page 5 of the slide, [T]he reduced cost of a non-basic arc $(i, j)$ is the sum of the costs of the arcs forming a cycle with $(i, j)$ in the current tree solution. Why is that the case?
0
votes
0answers
80 views

maximization function of a matrix given a scoring system

This is, from a mathematics standpoint, trivially solvable, but my goal is to solve it with the fewest number of comparisons. I'm hoping to discover that this problem is identical to something in ...
0
votes
0answers
51 views

Model a shortest path linear programming problem

I have a graph with 8 vertex, and i'm supposed to model a linear programming problem which consists in delivering 10 trash containers (1 is in vertex 1, 3 are at vertex 2, 2 are located at vertex 5, ...
1
vote
3answers
498 views

Linear Programming to find the loan plan to minimize the interest payment

Assume that it is the first of July and you are running a small shop. The sales revenue and the amount of bills you have to pay for the next six months are estimated as following: In short, you ...
0
votes
1answer
18 views

Formulation of linear problem

I'd like to ask you how to formulate this problem as linear problem (equations)? Marie wants to buy oranges and apples. She has to buy at least 5 oranges and the number of oranges has to be less ...
0
votes
1answer
19 views

Finding matching weight for two differing types of cat food

Attempting to figure out how much cat food to give my cat I came across a problem which I am unsure of any way other than iteration to solve. The problem I have is that I have been advised to feed my ...
0
votes
1answer
28 views

Linear programming with reuse of services

I came across some questions of this style and was not sure what the minimization function would be. A hotel requires a known number of hand towels for guests to be given during the week and the ...
0
votes
1answer
34 views

Linear Inequalities - Allocation Problem

The problem at hand can be summarized as follows: we have to allocate a ressource to $n$ production units. The allocation to production unit $i$ is $x_i$. Each of the production unit will produce at ...