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

learn more… | top users | synonyms

1
vote
2answers
2k views

Help with binary variable

I need to make a constraint for the following condition: Among students 1, 2, 3, and 4, at least two of them must be on the team, if there are any on the team at all. I have defined Y1, Y2, Y3, and ...
2
votes
1answer
1k views

primal to dual solution conversion ??

i have an optimization problem $$\text{ maximize } z=3x+4y$$ $$\text{ such that: } x+y ≤ 450 \text{ and } 2x+y ≤ 600$$ the optimal solution to this problems comes to be $x=0$; $y=450$; $p=150$ ...
1
vote
1answer
12 views

Expressing problems in canonical form for solving with simplex

The Picnic Hamper Company has a store containing 10,000kg of nuts, 4000 packs of smoked salmon, 2000 bottles of wine and 1500 Victoria sponges. It intends to use these goods to make up three different ...
2
votes
3answers
48 views

Least Squares method and Octave/Matlab [on hold]

I'll try to be as clear as possible so that you understand what I'm trying to do and can help me I have twelve pairs of data $(x_1,y_1),....,(x_{12},y_{12})$ and from this data we established a model ...
0
votes
0answers
40 views

Solving constrained linear programming problem

For the variable $t$, problem is to find best multipliers $k$ which minimizes the objective function. Time: $t_1$, $t_2$, $t_3$,... given in input Multiplier $k_1$, $k_2$, $k_3$,... (These are ...
0
votes
0answers
32 views

Necessary condition for existence of a positive solution of a linear system

I would like to know what are the necessary conditions of existence of a positive (componentwise) solution of the system : Ax=b, with A a square ...
8
votes
2answers
4k views

How the dual LP solves the primal LP

When I heard someone discussing LP the other day, I heard him say, "Well, we could just solve the dual." I know that both the primal LP and its dual must have the same optimal objective value ...
2
votes
1answer
60 views

Knight movement on chess field

I had this task in programming competition: There are two knights, which are $(p_1,q_1)$ and $(p_2, q_2)$. $(p,q)$ knight is figure, with p(q)-length first step, and q(p)-length second step in ...
0
votes
1answer
441 views

Linear programming: the optimum of the shortest path problem is attained by $x \in [0, 1]^m$

Let $G=(V,E)$ be a graph, where $|E|=m$, and suppose we formulate the shortest path problem on $G$ as follows: minimize ${}^t(1,\dots,1)x$ such that $Bx={}^t(1,-1,0,\dots,0), x\in \{0,1\}^m$, where $B ...
-1
votes
1answer
19 views

Inversion of a matrix in a system of linear inequalities

I would like to know if someone knows sufficient conditions on $A\in\mathbb{R}^{n\times n}$ and $b\in\mathbb{R}^{n}$ such that for all $x\in\mathbb{R}^{n}$: $$Ax\leq b \Rightarrow x\leq A^{-1}b \text{ ...
1
vote
1answer
17 views

goal programming, mixed-integer program, optimal compromise goals, statistics

QUESTION Can someone help me figuring out how to calculate this question? In this question, I have 4 variables (I think it would be more easily to calculate), and 5 goals. SO for the 27 boxes, I ...
2
votes
1answer
7k views

What is the standard form of a linear programming (LP) problem?

According to Bertsimas' text, the standard form of a LP problem is: According to Vanderbei's text, the standard form of a LP problem is: So, what is the standard form of a linear programming ...
0
votes
1answer
20 views

How to formulate constraints given the following information

The following question was given in one of my class but none of us got the use of the market requirements in the problem: A form produces and sells three products namely Product1, Product2 and ...
0
votes
0answers
8 views

Lemke Howson Algorithm Tableau

I am working on an implementation of Lemke Howson Algorithm and I am reading this paper below. http://cnl.gmu.edu/TAVRI/research/LemkeHowson.pdf Can someone please explain why on page 7 they say ...
0
votes
1answer
974 views

How to describe minimization of L1 norm error using linear programming?

Given a set of $n$ pair points $(x_1, y_1), ..., (x_n, y_n)$ in the plane, I need to find a line $ax + by = c$ that fits the points of the L1 norm error points as closely as possible. I need a linear ...
0
votes
1answer
51 views

Algorithms For Large-Scale $\ell_{\infty}$ Minimization

The general problem I want to solve is well studied: $$ \min_x \Vert Ax\Vert_\infty \;\;\; \mathrm{s.t.} \;\;\; Bx=c, $$ which is equivalent to the following linear program: $$ \min_{t,x} \, t ...
0
votes
0answers
14 views

How to linearize this constraint?

I have a MILP model but one of my constraints is nonlinear and I need to convert it to some linear constraints. Assume that the constraint is like this: U-X*F=0 and U,X,and F are variables and I have ...
-1
votes
1answer
19 views

Maximum Profit with limited resources. [closed]

A farmer has 10km2 of land in which he can sow either wheat or barley. The farmer has only 10kg fertilizer and 5kg insecticide. Per square kilometers wheat requires 2kg fertilizer and 2kg insectiside ...
0
votes
0answers
29 views

Range of feasibility, feasibility interval, allowable increase and allowable decrease.

Can someone please explain how the values (allowable decrease, allowable increase, for constraints) within the blue box (under "Range of Feasibility") are determined? I understand how they determined ...
0
votes
1answer
291 views

Multiple Choice Knapsack Problem (MCKP) where one class requires more than one item

I have the following problem of which I am attempting to find a near optimal solution: I have one knapsack which can hold a maximum weight. I must select exactly one distinct item from a number of ...
4
votes
1answer
2k 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 ...
0
votes
0answers
15 views

Help required in solving the lagrangian dual?

I'm trying to write the Lagrangian dual to the following problem \begin{align*} (P) \quad \min\;&\text{Trace}(CG)\\ \text{s.t.}\;&G \succcurlyeq 0\\ & G_{i,i}=I_d (i=1,..,M+1)\end{align*} ...
0
votes
0answers
30 views

Simplex/Big-M/Dual Simplex methods

I just want to know when to use which method. This is my current understanding, please say if I am incorrect: If all constraint equations can be turned into s.t. the RHSs of all are positive and all ...
0
votes
0answers
23 views

code in R program [closed]

I have some question about code in R program. When we want to find 1+2+3+4+5, we use x <- c(1,2,3,4,5) then sum <- sum(x). How I can write the code to compute 1*2*3*4*5 in R? Thanks.
1
vote
1answer
23 views

Interpretation or definition of “shadow prices”

I do understand that shadow price associated to a resource is the marginal profit you would get if you buy one more unit of that resource. I also know that it is the minimum profit you would accept to ...
2
votes
2answers
350 views

Linear Programming: Breaking Variables Product

Given two sets of binary variables $x_{i...N} \in X$ and $y_{i...M} \in Y$ and another binary variable $\alpha$ how can I linearize the following constraint, i.e break the product of variables? ...
1
vote
1answer
36 views

Limmiting solution of $Ax=b$ to positive quantities

My personal trainer put me on a diet recently which has had me tracking the macro-nutrients that I eat i.e. protein, carbohydrates and fat. I am supposed to eat a specific amount each meal and eat ...
0
votes
1answer
14 views

Linear programming: Condition on index variable

Let $i \in \{1,2,...n\}$. And let $X_i \in \{0,1\}$. I need to write the condition: if all $X_i$ where $i$ is even index take the value 1, then there need to be at least three $X_i$ with value $0$ ...
1
vote
0answers
17 views

Proving vectors as a basis in $E^{m}$

Show that if the vectors $a_{1}$, $a_2$, $\cdots$, $a_m$, are a basis in $E^{m}$, the vectors $a_{1}$, $a_2$, $\cdots$, $a_{p-1}$, $a_{q}, a_{p+1}, \cdots,a_{m}$, also are a basis if and only if ...
1
vote
1answer
104 views

Proving that Unit Intersection is NP-complete

I am extremely stuck on how to go about this problem and any help would be so appreciated. We are told to consider the following combinatorial problem: Unit Intersection: Let X = {1, 2,...,n}. ...
3
votes
2answers
45 views

Proving UNIT INTERSECTION NP-complete [duplicate]

I am working on some review problems right now and am extremely stuck on how to solve problem - any help would be so appreciated. We are told to consider the following combinatorial problem: Unit ...
0
votes
2answers
850 views

Optimal Basic Feasible Solutions

In linear programming, is it true that you can only have at most 2 optimal basic feasible solutions? If so, why?
-2
votes
0answers
52 views

Maximum of inner product

The question is to maximize $\langle a, x\rangle$ subject to $\langle b, x^2\rangle = 1$ where $a$, $b$ and $x$ are positive $n$-dimensional vectors in $\mathbb R$, and $\langle\cdot,\cdot \rangle$ is ...
1
vote
1answer
1k views

Linear programming: basic solutions?

http://www.math.toronto.edu/kergin/236_t1_2.pdf For number 3(a), I don't get how "any of the last 4 columns are linearly dependent" and how x1 is the basic variable... I thought only the last 2 ...
1
vote
2answers
40 views

$Minimize$ $z=-2x-5y$ subject to $3x+4y\ge 5$ , $x\ge 0$ , $y\ge 0$.

Consider the linear programming problem: $Minimize$ $z=-2x-5y$ subject to $3x+4y\ge 5$ , $x\ge 0$ , $y\ge 0$. Which is correct ? (A) Set of feasible solutions is empty. (B) Set of feasible ...
4
votes
1answer
1k views

Finding all basic feasible solutions in a linear program

Given the following constraints \begin{equation} \begin{split} x_1 &+&x_2&+&x_3&+&x_4&\le 10 \\ x_1&-&x_2&&&&&\le0\\ ...
1
vote
0answers
16 views

Multiple optimal solutions / LP

In the optimal primal simplex tableau, if we have a non-basic variable with a reduced cost of zero, can we say for sure the primal has multiple optimal solutions? Or can the same thing also happen ...
2
votes
2answers
470 views

Exploring underdetermined linear system with non-negative solution

I haven't had much luck searching for this specific problems. Any pointers would be greatly appreciated. I have an underdetermined system where $ A $ and $ b $ are known. $ x $ is a real vector with ...
0
votes
1answer
329 views

Formulate model

Carter Enterprises is a soybean trading company. Once a month a representative attends a commodity sale where he either buys or sells soybeans in bulk. Carter uses a local warehouse for storing ...
0
votes
1answer
27 views

Constructing canonical tableau for a linear programming problem involving SVM

I have the following set of inequalities and equalites $$\begin{align}y_1x_1+\cdots +y_nx_n &= 0\\ x_1 &\geq 0\\\vdots\\x_n&\geq0 \\ x_1&\leq c\\\vdots \\x_n&\leq ...
2
votes
1answer
43 views

Sensitivity Analysis, RHS change in some constraints

I am going to first layout the problem, then I'll get to the thing that is troubling me. I am enrolled in a course called "Optimization I", and this exercise is from a chapter called "Sensitivity ...
0
votes
1answer
28 views

How to find the maximum value subject to constraints

I am currently enrolled in a college algebra course and am having difficulty finding the solution to the following problem since it is not covered in our textbook or in class. Any helpful hints or ...
0
votes
0answers
15 views

Simplex method state after first phase

I'm implementing a simplex method solver for a standard problem $$ \begin{aligned} \operatorname{minimize} \qquad&c^T x\\ \operatorname{subjected to} \qquad&Ax = b\\ &x \geq 0\\ ...
3
votes
1answer
673 views

Linearization of a product of two decision variables

I am trying to solve a problem that involves constraints in which products of two decision variables appear. So far, I read that such products can be reformulated to a difference of two quadratic ...
0
votes
1answer
16 views

Dealing with free variables in Linear Programming

I have a free variable in my formulation. In the objective function, this free variable has a cost, and another cost coefficient which is only incurred when the free variable is negative. I used the ...
1
vote
2answers
631 views

Removing linear redundant constraints using Gauss Elimination

I have a set of linear constraints in the form of $c_i x \ge d_i$ and I need to identify if an additional constraint is redundant with respect of the previously mentioned set. Here I found a similar ...
0
votes
1answer
53 views

Single factor model question, related to the benefits of diversifying one's portfolio.

The question: Suppose in a single period investment problem we may divide our wealth between n assets and that the return on the ith security is given by $r_i = \alpha + \beta_i\theta + \epsilon_i,$ ...
1
vote
0answers
25 views

Seating at a large wedding

I have a large wedding of 500 people and 100 tables, each table containing 5 seats. Each person at the wedding lists (up to) 4 people they would like to sit at their table (order of the ranking ...
0
votes
1answer
18 views

Strong duality theorem written with iffs?

Our strong duality theorem is: If both the primal LP and the dual LP have feasible solutions, then they both have optimal solutions, and for any primal optimal solution $x$ and dual optimal solution ...
1
vote
1answer
59 views

how to work out 3 equations simultaneously

So i was doing this linear programming question and got stuck on this part, so how do you workout simultaneously $2x + 3y = 30 $ $(2/3)x + 2y = 16 $ $(16/3)x + 4y = 64$ According to lpsolve we ...