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

learn more… | top users | synonyms

1
vote
0answers
34 views

Linear programming : avoid to choose manufacting costs that are greater than selling price [on hold]

Thanks for your time. I have a linear program and no idea how I could express a form of constraint and even if it's possible. Maybe someone here know a solution. A company assembly and sells a ...
1
vote
1answer
26 views

What optimization problem is this?

Minimize $$\sum_{i=1}^{m}w_i x_i$$ with $w_i \in \mathbb{Z}_{\ge0}$, and $x_i \in \{0, 1\}$ subject to a set of $n$ conditions of the form $$\sum_{i\in S_k} x_i \equiv c_k \pmod{2}$$ for $S_k ...
0
votes
0answers
22 views

Complementary slackness condition in economic terms

In linear programming how can one interpret the complementary slackness conditions in economic terms? The linear programming problem is to maximize $\sum_{j=1}^n c_j x_j$ subject to $\sum_{j=1}^n ...
1
vote
1answer
8 views

Formula for rate that changes when negative

Is it possible to reduce this code to a single formula, rather than check if x is negative? ...
0
votes
1answer
13 views

Relation between minimum of a function and minimum of the sum of the same function and a linear term

I'd like to know if it's true that if given a function $f(x):X \mapsto \mathbb{R}$ and a vector $c \in X$, then if $$v = \arg\min_x f(x) + x^tc$$ one can say that $$v-c = \arg\min_x f(x)$$ Does this ...
0
votes
1answer
30 views

Linear Programming Inventory

A company is opening a new franchise and wants to try minimizing their quarterly cost using linear programming. Each of their workers gets paid 500 per quarter and works 3 contiguous quarters per ...
0
votes
1answer
31 views

Linear programming and the simplex method

I am trying to solve this system of equations. My approach would be to introduce slack variables and then somehow use the simplex algorithm to solve this. Can anyone show me how this is done?
0
votes
0answers
14 views

Using Farkas Lemma to Prove Gale, Gordon and Stiemke's Theorems [on hold]

How can I use Farkas Lemma to prove Gale, Gordon and Stiemke's Theorems?
0
votes
0answers
14 views

Maximization over linear surjective mapping of polyhedron

I am reading this paper and confused about the derivation of equation (11) (page 3, bottom of column 2). I will rephrase it in this question. Let $\mathcal{P}_r = \{ x \in \mathbb{R}^n : P_r x \leq ...
0
votes
0answers
13 views

In the problem below, what is the right mix of drugs to maximize the expected revenue without exceeding R&D resources?

This is not a homework question. It's a question for a class I have yet to take that my friend gave me. I haven't been able to figure it out. Help is appreciated because it's driving me crazy. A ...
-2
votes
1answer
30 views

Please Solve the following LP [on hold]

please help me to solve this question. Thank you in advance.
0
votes
1answer
14 views

Can this problem be solved using linear programming? [on hold]

I am not entirely certain if this can be solved with LP solvers or if it's a different kind of problem. I want to create a model that creates an optimal energy sector. Influencing factors include ...
0
votes
0answers
10 views

Properties of an LP when the coefficients are variables of the problem

If I had a standard LP problem, and the coefficients of it are variable to the problem and I want to draw on the properties of the LP to say something about the coefficients. What such properties can ...
1
vote
0answers
15 views

minimize the total cost of transportation [closed]

can anyone help me to solve this question to minimize the total cost of transportation,how to use Vogel’s approximation method
0
votes
0answers
34 views

LP transformation of multi-commodity flow problem

I have the following multi-commodity flow problem that I would like to bring into canonical LP format. \begin{equation*} \begin{aligned} & \underset{d}{\text{minimize}} & &d(x) = ...
1
vote
1answer
46 views

books on the application of linear algebra on statistics/finance/machine learning

I am reading "linear algebra done right" by Axler and like it a lot. One thing though, in the end I would like to put these theory to use and as a math textbook it doesn't cover much application. ...
-1
votes
0answers
14 views

Coupon Collector's Problem in Python [closed]

I need help with writing the simulation of Coupon Collector's Problem in Python. There are given n-nr of coupons and m-nr of necessary ...
3
votes
1answer
30 views

Finiteness of the Supremum of Inner Product of Two Finite Sum Positive Sequence

Let $$A = \Big\{(a_1,a_2,\dots)\ \Big|\ a_i\ge 0, \sum_{i=1}^\infty a_i=1\Big\},$$ $$v(x)=\sup\left(\bigg\{\sum_{i=1}^\infty a_ib_i\ \bigg|\ (a_i)_{i=1}^\infty,\, (b_i)_{i=1}^\infty \in ...
0
votes
1answer
25 views

Optimization options to select multiple items with different features and values

I'm trying to identify which approach would work best to select a set of elements that have different features that minimise a certain value. To be more specific, I might have a group of elements with ...
0
votes
0answers
14 views

Linear Optimization: What is the difference between these two theorems?

I attend a lecture about linear optimization where we had the following two Theorems. But I somehow cannot spot the difference: Theorem 1: Let $P$ be a polyhedron with an extreme Point and $c \in ...
1
vote
1answer
26 views

Taking the dual of this non-standard linear program

I am just beginning to learn linear programming have a question about taking the dual of a non-standard LP specifically the one below: $\min M\\ 2x_1 + 3x_2 + 4x_3 \leq M \\ 2x_1 - x_2 + x_3 \leq M\\ ...
0
votes
0answers
16 views

Proof of Simplex Method, Adjacent CPF Solutions

I was looking at justification as to why the simplex method runs and the basic arguments seem to rely on the follow: i)The optimal solution occurs at some vertex of the feasible region (CPF points) ...
2
votes
0answers
32 views

What is a closed chain (or circuit) that is used in solving a transportation problem (a special type of linear programming problem)?

What is a closed chain (or circuit) that is used in solving a transportation problem (a special type of linear programming problem)? I'm having some problems with it. Please clarify it. I have posted ...
0
votes
1answer
29 views

Conversion of a general linear program into a standard linear program

I am trying to teach myself the basics of optimization of linear programmes, for example the following question: How do I tackle such a question?
0
votes
0answers
12 views

Tableau Condition for dual simplex algorithm

The following is a tableau obtained when solving a minimization linear programming problem via the dual simplex algorithm. basic $x_1$ $x_2$ $x_3$ $x_4$ $x_5$ $x_6$ $x_7$ RHS ...
0
votes
0answers
49 views

Linear Programming- Steelco manufactures two types of steel

Problem 1 Steelco manufactures two types of steel (steel 1 and steel 2) at two locations (plant 1 and plant 2). Three resources are needed to manufacture a ton of steel: iron, coal, and blast furnace ...
2
votes
0answers
24 views

Convert a problem o minimizing a function to linear programming problem in standard form

I have to 1) convert a problem o minimizing a function to linear programming problem in standard form. It is something new to me. Can somebody explain it to me? $$\min(\mathbb{R}^2\ni(x,y)\rightarrow ...
0
votes
1answer
26 views

Optimization problem in the standard form

Let $x\rightarrow x^{T}c$ be an objective function of an optimization problem in the standard form, for which the optimal solution doesn't exist. Does then exist an optimal solution to $x\rightarrow ...
0
votes
0answers
22 views

Grouping elements such that optimizing inter group communication cost

Suppose we have n elements. We need to group them into m group such that each group cannot take more than $x_1,x_2...x_m$ elements respectively. Sum of $x_i \geq n$. We need to optimize the inter ...
0
votes
1answer
23 views

Dual simplex doubt (unrestricted)

I have this two problems and i only want to find the dual form: $\begin{gather} max\hspace{.1cm}z =5x_1+6x_2\\ s.t\hspace{.1cm}x_1+2x_2=5\\ -x_1+5x_2 \ge 3\\ x_2 \ge 0\\ x_1\hspace{.1cm} ...
0
votes
0answers
9 views

LP: generic objective guarantees a unique solution?

Suppose that I have a linear program \begin{align} & \text{maximize} && \mathbf{c}^\mathrm{T} \mathbf{x}\\ & \text{subject to} && A \mathbf{x} \leq \mathbf{b} \\ & ...
0
votes
1answer
27 views

Linear Programming : Is there any other way to solve than graphs?

In my highschool curriculum there's a a chapter on Linear Programming Problems. In the chapter there are bunch of unproved statements and mechanical ways to solve linear problem. But my question is- ...
0
votes
0answers
10 views

Convert the problem into an equivalent stalndard lpp

Consider the optimization problem, Minimize, $C_{1}|x_{1}|+C_{2}|x_{2}+C_{3}|x_{3}|+...+C_{n}|x_{n}|$ subject to, $AX = b$ , $C_{i} \neq 0$ Convert the above problem into an equivalent standard ...
0
votes
1answer
52 views

Linear Programming and Geometry Question

I have a question that involves some linear programming and linear algebra, and I really don't have a clue how to approach this question. Could someone give me some hints and ideas as to how to attack ...
0
votes
0answers
27 views

Linear Programing : get the maximum constant associated to a non null variable

Does anyone know a way get the maximum constant associated to a non null variable using only linear programing ? For example, supposed that there is 3 linear variable x, y and z. x being associated ...
1
vote
1answer
28 views

Linear Programming and Standard Form

In order to find the dual of a primal linear program, do I always have to convert it to the standard form first? For example, if I have the following LP, would the dual also be a min since the LP in ...
0
votes
0answers
23 views

When to stop Simplex algorithm.

How do we understand when optimal solution is reached and we should stop iteration in simplex method algorithm using tabular method?
0
votes
2answers
33 views

References for Linear Algebra needed for Differential Equations and Linear Programming

I am in need of learning the Linear Algebraic theory behind the following Applied disciplines. Could someone please recommend Linear Algebra books for: Differential Equations: Specifically learning ...
1
vote
0answers
24 views

Write down a linear programming problem

I want to replicate a linear programming problem.I have the following information, for the background." A fuzzy regression analysis with only one independent variable X results in the following ...
0
votes
0answers
10 views

Binary linear programming (matrix)

I formulated a linear programming problem (real life case, so I won't disclose here) into this form: $$ Minimize\sum a_{ij} x_{ij} $$ subject to $$\sum_{i} x_{ij} = m, j = 1,2,..,n $$ $$\sum_{j} ...
2
votes
2answers
53 views

Is $[u_1,u_2]$ an edge of the polytope $conv(F)$?

Here's the problem. I have a finite set of vectors $F \subset \mathbb{Z}_{\geq 0}^d$. I define $P$ to be the convex polytope $conv(F)$ i.e. the convex hull of $F$. Given $u_1, u_2 \in F$, is the ...
0
votes
0answers
6 views

grouping with linear programming

Suppose the following: I have a set (U) containing elements with at least one way to discriminate them. Let's just say exactly one. Maybe think of integer numbers x and the way to discriminate them ...
0
votes
0answers
25 views

optimisation problem with linear constraint

optimisation problem with linear constraint I have an optimisation problem. I wish to maximise a function subject to a constraint. It is the constraint that is causing me problems. I am using an ...
0
votes
0answers
17 views

mathematical formulation Minimum Cost Flow

I have a problem of minimum cost flow that can be defined as the following matrix. I want to solve it how a linear program (without using kruskal algorithms, prim etc). How can I formulate it like a ...
0
votes
0answers
17 views

How to I see that $n-1$ linearly independent constraints $a_i^Tx \ge b, i \in \{1,\dots, n-1\}$ define a line in $\mathbb R^n$?

How to I see that $n-1$ linearly independent constraints $a_i^Tx \ge b, i \in \{1,\dots, n-1\}$ define a line in $\mathbb R^n$ ? ($b, a_i, x \in \mathbb R^n$) If I can find a vector $p$ that ...
0
votes
0answers
11 views

Having trouble finding the right variables and constraints for linear programming problem.

I've got a word problem that needs to be solved via the simplex tableau method but from reading I can't decide what my variables and constraints will be: Slapshot Inc. makes two types of hockey ...
0
votes
0answers
10 views

Maximize Net Profit with Simplex Tableau

I have a profit maximization problem and have been asked to solve it using the simplex tableau method. The thing is as far as I can tell there are no constraints present, so I'm really not quite sure ...
0
votes
1answer
25 views

Given a set of integers find two disjoint subsets $I$ and $J$ so $|I|+|J|=k$ and $\sum\limits_{i \in I}x_i = \sum\limits_{j \in J}x_j = n^2$

Given a set of integers $1 \le x_1,x_2\dots,x_n \le n^2$ and a number $k \le n$. describe an algorithm that will determine if there exists two disjoned subsets $I$ and $J$ such that $|I|+|J|=k$ and ...
1
vote
0answers
100 views

Show that every extreme point in Q is either an extreme point of P or a convex combination of two adjacent extreme points of P

P is a bounded polyhedron in $\mathbb{R}^n$, $a$ a vector in $\mathbb{R}^n$, and $b$ some scalar. Define $$Q = {x \in P | a'x = b}$$. Show that every extreme point in Q is either an extreme point of P ...
0
votes
1answer
34 views

Find Maximum of Lower Envelope

Okay, I'm not really sure whether the title is good. Consider \begin{align*} \min\{ 5x_1 + \frac{5}{2}x_2 + \frac{5}{3}x_3 + \frac{5}{4}x_4, \\ x_1 + \frac{6}{2}x_2 + \frac{6}{3}x_3 + ...