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

learn more… | top users | synonyms

0
votes
0answers
2 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
17 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
33 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
1answer
15 views

Linear Transfromation Matrix

Reflect the diamond shape polygon whose vertices are $A(-1,0),B(0,-2),C(1,0)$ and $D(0,2)$ about: a) The horizontal Line $y=2$ b) The vertical line $x=2$ and c) The line $y=x+2$
0
votes
1answer
10 views

Linear programming problem answer

Big Seas makes regular ice cream and non fat ice cream. The ice cream mixer can make at most 300 gallons. Each regular ice cream requires 5 ounces of milk, and each non fat ice cream requires 2 ounces ...
0
votes
0answers
15 views

Find all possible optimal solutions for degenerate/multi-solution problem

I have an instance of LP problem. I know that problem has multiple optimal solutions. What is the right way to find all possible optimal solutions. As I understand I have to remove all possible ...
0
votes
0answers
13 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
15 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
8 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
17 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
27 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
66 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
33 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
21 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
17 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
0answers
32 views

Solving Matrix Value and Optimal Strategy (Matrix Games)

How would I solve this matrix game ? I'd like to find the value of the matrix and the optimal strategies for each player. $$ \left[ \begin{array}{cccc} 0 & 3 & -2 & 2 \\ -3 & 0 ...
1
vote
1answer
16 views

2 Linear equation problems [closed]

Write objective, constraints and graph for the following two problems: 1.A test offers 2 types of problems. Type A takes 3 Min to solve and B takes 2. You have 20 min to take the test and can only ...
0
votes
1answer
15 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
0answers
16 views

A question on linear programming

For each $Q \subset \Bbb R^n$, denote $Q^*:=\{z \in \Bbb R^n:zx \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 clear that ...
1
vote
0answers
23 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
19 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. ...
0
votes
0answers
15 views

Solving Linear Inequalities Using Primal and Dual LP's

I've been working through my linear programming homework, and I'm having difficulty understanding how and why you would want to use the dual to find the optimal solution to the primal. I'll write up ...
1
vote
1answer
48 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
19 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
37 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
20 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
35 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
7 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
71 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
30 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, ...
0
votes
0answers
21 views

Minimise a cost of elements into given length - Optimisation - Linear programming

I've been researching optimisation methods used to minimise the cost of elements that could be used in a given length. Here is an example of my problem : For a given length 40 : X1 Length l1 = 13 ...
1
vote
2answers
388 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
17 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
20 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 ...
0
votes
1answer
15 views

Where did i go wrong in this linear inequation evaluation?

We are currently studying Linear Programming in school and while going through it i seem to of come across a ridiculous error. Problem is, i can't seem to find it. Essentially there is an equation 8 ...
0
votes
0answers
18 views

Statistical Meaning of LP problem

What is the statistical interpretation of this LP problem for different values of $\mu$? $\min \sum_{j} \left( |x-b_j| + \mu (x-b_j) \right)$ I know that $\min \sum_{j} |x-b_j|$ is the median but ...
0
votes
1answer
26 views

orthogonal triangular decomposition and ordinary least squares

I have just come across orthogonal triangular decomposition whilst looking at ordinary least squares regression. I'm not quite sure how this is being used though to find a solution. In my example I ...
0
votes
0answers
21 views

Connect all nodes of a graph to satisfy demand

I have a non-complete non-oriented graph composed by one Supersource node which produces all the amount of goods the graph needs and n nodes. Every node require a specific amount of goods . What I ...
1
vote
1answer
21 views

Gradient Question-Linear Regression

When discussing linear regression, we discuss the error of the out of sample data prediction. That is, $$ E_{\operatorname{out}} = \frac{1}{N} \sum_{n=1}^{N} ...
1
vote
1answer
19 views

Is it possible to get the dual solution “quickly” once the optimal primal solution is found?

With the primal objective value, I know the dual objective value. I also know the right hand sides of the original program. However, I don't know the values of the dual variables at the optimal point. ...
2
votes
0answers
37 views

Examples of non trivial problems in this structure.

I'm looking for examples of non trivial problems that match with the follow structure. Let the function $$g: U \times V \rightarrow \mathbb{R}$$, where $U$ and $V$ are complex vetorial spaces of ...
1
vote
1answer
37 views

Minimize the minimum - Linear programming

Consider an optimization problem with variables $x_1, x_2, \dots, x_n \in \mathbb{R}$ (maybe subject to some linear constraints), and linear functions $\{f_i(x_1, \dots, x_n)\}_{1\leq i\leq m}$. We ...
0
votes
0answers
54 views

Application of the Simplex Method using Gauss-Jordan to solve Transportation Minimization Problem

I am attempting to implement the Simplex method using Gauss-Jordan elimination to solve the transportation problem. This is a minimisation problem, whereby I want to starting from a feasible solution ...
0
votes
1answer
29 views

Can the search space of a solvable linear optimization problem be discontinuous?

Background Say you have a traditional linear-optimization problem, there is a linear cost function, $\vec{c}\cdot\vec{x}$ and a set of linear constraints, $A_1\vec{x} \geq b_1 $ $A_2\vec{x} \leq ...
-1
votes
0answers
24 views

linear programing

suppose that the time(hours) required to produce desks, chairs and shelves through two processes are shown in the table below: process desks chairs shelves pressing 8 ...
1
vote
1answer
34 views

How to convert a linear optimization problem into a normal form?

The following linear optimization problem is given: $$ \begin{eqnarray} x_1 + 2x_2 -7x_3 \leq 1\\ |3x_1-5x_2-20| \leq 4 \\ x \geq 0 \\ 6x_1+5x_2-3x_3 \rightarrow min \end{eqnarray} $$ And it is my ...
1
vote
0answers
15 views

Get reduced costs from simplex tableau

This is probably a dumb question... but I'm trying to find how to calculate the reduced cost for a particular variable based on the information in a simplex tableau after I've minimized a linear ...
1
vote
0answers
27 views

Maximize minimum optimization using linear integer programming

I am trying to solve a maximize minimum optimization. I have four different items that each of them has 10 values of Rates and for each value it has a corresponding weight. Then I have a free table ...