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

learn more… | top users | synonyms

0
votes
0answers
23 views

When is a quadratically constrained quadratic program (indefinite objective matrix) unbounded?

I have a nonconvex QCQP of the form $$x^TQ_0x + c^T x$$ such that $x^TQ_1x+c_1^Tx=b_1$, $Ax=b$, and $l\leq x\leq m$ where $Q_0$ is indefinite diagonal matrix and $Q_1$ is positive semidefinite ...
1
vote
1answer
50 views

Using linear algebra (e.g. matrix) methods to solve a system of linear inequalities

Say we have the equation $Ax>b$, where $A$ is an M-by-N matrix, $b$ is a known vector of length N, x is an unknown vector of length N, and the inequality sign means that each element of $Ax$ is ...
1
vote
1answer
36 views

What to do about equality constraints in the Simplex Tableau method

The question I've got is: Maximise $$2x-y+3z$$ subject to $$2y+z \leq 2$$ $$x+y+z=4$$ $$x-2y+z \geq 3$$ $$x,y,z \geq 0$$ Using the Simplex Tableau method. I know that for $\leq$ constraints you need ...
1
vote
1answer
57 views

Minimize $w=9y_1+4y_2$ subject to linear inequalities

Minimize $w=9y_1+4y_2$ subject to : $4y_1+9y_2\geq 360$ $y_1+4y_2\geq 40$ $y_1\geq 0,~y_2\geq 0$
1
vote
1answer
39 views

Real linear combinations of intervals

Given intervals at $i\in\{0,1\}$ $I_i=[-a_i,a_i]$ where $0<a_0<a_1<1$ and a third interval $I=[-a,a]$ where $0<a<{1}$, when is there an $\alpha,\beta\in\Bbb R$ such that $\alpha I_0 ...
1
vote
2answers
60 views

Positive linear combinations of intervals

Given two intervals at $i\in\{0,1\}$ $I_i=[-a_i,a_i]$ where $0<a_0<a_1=1-a_0<1$ and a third interval $I=[-a,a]$ where $0<a<\frac{1}2$, when is there an $\alpha,\beta\in\Bbb R$ such that ...
1
vote
0answers
16 views

Linear diophantine inequality maximum

For an irrational $\xi$ and given bound $x$, find integer $a, b \ge 0$ maximizing $y = a + b\xi$ subject to $y \le x$. $\xi$ is a square root of an integer, but I guess it doesn't matter. It's ...
0
votes
1answer
45 views

Question about Game theory, matrix games.

Lets say you have a matrix game, where the matrix $A$ is the matrix, the column player can choose a column, the row player a row, and the row player pays the column player $A_{i,j}$. Assume we want ...
1
vote
0answers
25 views

Operations Research - complementary Slackness and optimal Solution

I have to verify the complementary Slackness, but I don't understand what it says and how to do it. Given: primal LP $$\begin{align*}\max&\quad c^tx\\\mathrm{s.t.}&\quad Ax=b\\&\quad ...
1
vote
1answer
46 views

Operation research - postoptimality analysis - find all solutions to problem

I'm currently learning Operations Research from "Introduction to Operations Research - Hillier". I know that somethimes a problem has many optimal solutions. For example in a two dimensional problem ...
0
votes
0answers
74 views

Is a polyhedron an affline manifold?

I was reading the definition of an affine manifold (https://www.wikiwand.com/en/Affine_manifold) and was wondering if a polyhedron is an affine manifold. Could you also provide any hints to the proof ...
0
votes
2answers
69 views

Linear optimization with “max” function (convex) constraint

I am working on a linear optimization problem which has a non-linear constraint. Suppose $x = [x_1 x_2]^T$, the problem is $$ \min_{x} \quad c^T x \\ \mathrm{s.t.} \quad Ax \leq b\\ x \geq 0 \\ ...
0
votes
0answers
23 views

Extreme rays and lineality spaces

Consider the polyhedron $P$ defined as $$P = \{(x_1,x_2) \mid 4x_1 + 2x_2 \geq 8, \quad 2x_1 + x_2 \leq 8 \}$$ Then $P$ has no extreme points, as the corresponding matrix $A$ is given by $$A = ...
2
votes
0answers
37 views

What subjects properly belong in operations research as their “owning” discipline?

Warning: This is a soft question, hence I would make it a wiki-community post if I could. Operations Research involves a broad swath of disciplines, ranging from probability and statistics/stochastic ...
1
vote
1answer
30 views

Application Farkas Lemma

Let $A$ be a $m \times n$ matrix and $C$ a $k \times n$ matrix. Let $b \in \mathbb{R}^m$ and $d \in \mathbb{R}^k$. Show that exactly one of the following holds: a) There exists an $x \in ...
2
votes
2answers
57 views

What is the interpretation of the following optimization problem?

Suppose we have $N$ variables $x_1,\ldots,x_N$. Let $\mathbf{A}$ a $M \times N$ matrix, and $\mathbf{b}$ a $M \times 1$ vector. I have the following minimization problem: \begin{array}{rl} \min ...
1
vote
1answer
52 views

Characterize polytopes resulting from cutting a convex polytope by a hyperplane

We have a convex polytope $P$ for which we know its set of vertices. Using this set we characterize the H-representation of $P$ as: $\mathbf{A}\mathbf{x} < \mathbf{b}$. If a hyperplane defined by ...
0
votes
0answers
161 views

Linear - Quadratic optimization for system of objectives

I have two distinct data sets, $\{x^{\mu},J^{\mu}\}$, $\mu=1,\ldots,n$ and $\{x^{\nu},V^{\nu}\}$, $\nu=1,\ldots,m$ that also include uncertainties $\delta J^{\mu}$ and $\delta V^{\nu}$. In these I fit ...
1
vote
1answer
22 views

Simplex Method issues solving this problem

I have an exam coming up so I have been going over math questions in my textbook to practice the simplex method. I ran into an issue with questions like this one, and also any that have more ...
1
vote
1answer
51 views

Solving an integer linear programming problem without a graph

I am new to linear prorgramming and so far I have been solving LP problems with the help of a graph solution. However, when there are more than 2 variables obviously I can't plot them on the graph. ...
0
votes
0answers
34 views

how can we explain that the all slack point is feasible

how can we explain that the all slack point is feasible when solving a linear programming problem using the simplex method Thanks in advance, i appreciate all the help.
1
vote
1answer
28 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 ...
0
votes
0answers
63 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 ...
4
votes
1answer
93 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 ...
-2
votes
1answer
24 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{ ...
2
votes
3answers
59 views

Least Squares method and Octave/Matlab [closed]

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
35 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 ...
2
votes
1answer
53 views

Chocolatier sampler boxes problem: applying goal programming and mixed-integer programing to optimally compromise goals.

QUESTION: A boutique chocolatier is planning to make a number of sampler boxes, each containing $36$ chocolates. (Therefore the total number of chocolates should be divisible by $36$.) The ...
0
votes
0answers
12 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
60 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
17 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
58 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
56 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 ...
1
vote
1answer
25 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 ...
0
votes
1answer
22 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 ...
1
vote
1answer
50 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
17 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
18 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 ...
3
votes
2answers
48 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 ...
1
vote
1answer
107 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}. ...
1
vote
0answers
24 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 ...
1
vote
2answers
47 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 ...
0
votes
1answer
34 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
22 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\\ ...
0
votes
1answer
24 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
0answers
36 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 ...
2
votes
1answer
67 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
40 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 ...
1
vote
1answer
65 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 ...
3
votes
0answers
44 views

Converting a max-min problem to a max problem with a constraint

The objective is to find the greatest lower bound of the variable $\mu$. The lower bound is resulting from the positive-semidefinite (PSD) constraint $$\tilde{\mathbf{T}}:=\left( \begin{array}{ccc} ...