4. Solve the following problem by Simplex method adding artificial variable:
Max Z=2x1 + 5x2 + 7x3
Subject to the constraints 3x1 + 2x2 + 4x3 <=100;
x1 + 4x2+ 2x3<=100;
x1 + x2 + 3x3<=100 and X1, x2, x3>=0
Answers
Step-by-step explanation:
Chapter 9
Linear programming
The nature of the programmes a computer scientist has to conceive often requires some knowledge in a specific domain of application, for example corporate management, network protocols, sound and video for multimedia streaming,. . . Linear programming is one of the necessary
knowledges to handle optimization problems. These problems come from varied domains as
production management, economics, transportation network planning, . . . For example, one can
mention the composition of train wagons, the electricity production, or the flight planning by
airplane companies.
Most of these optimization problems do not admit an optimal solution that can be computed
in a reasonable time, that is in polynomial time (See Chapter 3). However, we know how to efficiently solve some particular problems and to provide an optimal solution (or at least quantify
the difference between the provided solution and the optimal value) by using techniques from
linear programming.
In fact, in 1947, G.B. Dantzig conceived the Simplex Method to solve military planning
problems asked by the US Air Force that were written as a linear programme, that is a system
of linear equations. In this course, we introduce the basic concepts of linear programming. We
then present the Simplex Method, following the book of V. Chvatal [2]. If you want to read ´
more about linear programming, some good references are [6, 1].
The objective is to show the reader how to model a problem with a linear programme when
it is possible, to present him different methods used to solve it or at least provide a good approximation of the solution. To this end, we present the theory of duality which provide ways
of finding good bounds on specific solutions.
We also discuss the practical side of linear programming: there exist very efficient tools
to solve linear programmes, e.g. CPLEX [3] and GLPK [4]. We present the different steps
leading to the solution of a practical problem expressed as a linear programme.
9.1 Introduction
A linear programme is a problem consisting in maximizing or minimizing a linear function
while satisfying a finite set of linear constraints. 130 CHAPTER 9. LINEAR PROGRAMMING
Linear programmes can be written under the standard form:
Maximize ∑n
j=1 c jx j
Subject to: ∑n
j=1 ai jx j ≤ bi for all 1 ≤ i ≤ m
x j ≥ 0 for all 1 ≤ j ≤ n.
(9.1)
All constraints are inequalities (and not equations) and all variables are non-negative. The
variables x j are referred to as decision variables. The function that has to be maximized is
called the problem objective function.
Observe that a constraint of the form ∑n
j=1 ai jx j ≥ bi may be rewritten as ∑n
j=1(−ai j)x j ≤
−bi. Similarly, a minimization problem may be transformed into a maximization problem:
minimizing ∑n
j=1 c jx j is equivalent to maximizing ∑n
j=1(−c j)x j. Hence, every maximization
or minimization problem subject to linear constraints can be reformulated in the standard form
(See Exercices 9.1 and 9.2.).
A n-tuple (x1,...,xn) satisfying the constraints of a linear programme is a feasible solution
of this problem. A solution that maximizes the objective function of the problem is called an
optimal solution. Beware that a linear programme does not necessarily admits a unique optimal
solution. Some problems have several optimal solutions while others have none. The later case
may occur for two opposite reasons: either there exist no feasible solutions, or, in a sense, there
are too many. The first case is illustrated by the following problem.
Maximize 3x1 − x2
Subject to: x1 + x2 ≤ 2
−2x1 − 2x2 ≤ −10
x1,x2 ≥ 0
(9.2)
which has no feasible solution (See Exercise 9.3). Problems of this kind are referred to as
unfeasible. At the opposite, the problem
Maximize x1 − x2
Subject to: −2x1 + x2 ≤ −1
−x1 − 2x2 ≤ −2
x1,x2 ≥ 0
(9.3)
has feasible solutions. But none of them is optimal (See Exercise 9.3). As a matter of fact, for
every number M, there exists a feasible solution x1,x2 such that x1 − x2 > M. The problems
verifying this property are referred to as unbounded. Every linear programme satisfiesextended by