Optimizations and Programming. Abdelkhalak El Hami
Читать онлайн книгу.
industry and private sector for many years. In the last decade or so, its applications have been extended to other domains, such as economics, finance, marketing and corporate planning. More recently, operations research has been used to manage healthcare and education systems, solve environmental problems and in other areas of public interest. Its principal users are manufacturing, distribution and retail companies in the mining, energy, transportation and construction sectors, as well as service companies such as banks, and various government bodies. Noteworthy examples of recent applications of operations research include logistical studies, railway safety, packaging design, strategic workforce planning, aerial transportation, forestry operations, nuclear fuel optimization, production planning, and so on.
The optimization part of this book is divided into three chapters: combinatorial optimization, nonlinear optimization without constraints and nonlinear optimization with constraints. It is entirely dedicated to numerical optimization algorithms, their theoretical foundations and convergence properties, their implementation and application, and other practical aspects. The objective is to familiarize readers with these numerical algorithms in order to understand how they behave in practice, how to properly take advantage of Matlab as a tool, how to design and adequately implement such algorithms and how to correctly diagnose any difficulties that might arise.
Each chapter starts with a few reminders of key results, but readers should not hesitate to consult the references listed at the end of the book. This book is organized according to a strictly linear approach. As a general rule, the concepts are illustrated with examples. Each chapter ends with an example in Matlab.
Acknowledgments
We would like to thank everyone who contributed, directly or indirectly, to the writing of this book and especially, the engineering and PhD students of INSA Rouen whom we have had the pleasure of supervising over the past few years.
Bouchaib RADI
Abdelkhalak EL HAMI
November 2020
1
Linear Programming
1.1. Introduction
Linear programming can be defined as a mathematical technique for solving management problems. For example, suppose that a manager faced with various options wishes to determine the optimal way to use the resources of a company to achieve a specific objective, such as maximizing the utility or minimizing the cost. The company’s problems can usually be modeled as a linear program (LP) consisting of a certain number of resources [HIL 90]. For instance, the labor, raw materials and capital are all resources available in limited quantities that must be distributed optimally over various manufacturing processes. The approach to solving this type of problem is divided into two key steps:
– model the problem with linear equations or inequalities that allow us to properly identify and structure the constraints satisfied by the variables of the model. The contribution of each variable to the company’s overarching objective must also be defined as a function that will be optimized;
– find the mathematical optimum using specific linear programming techniques. We will study three methods for solving the various types of linear programming problems. The first is based on graphical solving and is therefore limited to two or three variables. The second method is more algebraic; it motivates the third method presented in this chapter, which is known as the simplex method (or algorithm).
1.2. Definitions
DEFINITION 1.1.– An LP is in canonical form if it is expressed as follows:
[1.1]
An LP is in standard form if it is expressed as follows:
Every linear problem can be expressed in canonical form: min cTx = – max cTx.
THEOREM 1.1.– Every LP in standard form can be expressed in canonical form and vice versa.
Terminology
– The function cT x is the objective function, cost function or loss function.
– The components of the vector x are called decision variables.
– If the vector x satisfies all constraints, then x is an admissible solution.
– The set of all admissible solutions is the admissible set or admissible region.
– An admissible solution x* that maximizes the loss function (i.e. cTx* ≥ cTx for every admissible x) is called an optimal admissible solution or optimal solution.
EXAMPLE 1.1.– A factory manufactures two products P1 and P2 while consuming certain resources: equipment, labor and raw materials. The needs are listed in the following table. Each resource is available in limited quantities.
| P 1 | P 2 | Availability | |
| Equipment | 3 | 9 | 81 |
| Labor | 4 | 5 | 55 |
| Raw materials | 2 | 1 | 20 |
The two products P1 and P2 yield effective profits of 6 dhs and 4 dhs per unit. The goal is to determine which (possibly non-integer) quantities of the products P1 and P2 the factory should produce to maximize the total profit from selling these two products, subject to the availability of the resources.
Let x1 and x2 be the quantities of the products P1 and P2, respectively.
The LP may be expressed as follows: maximize z(x1, x2) = 6x1 + 4x2 subject to:
– availability of resources:
– positivity of variables: x1, x2 ≥ 0
1.3. Geometry of the linear program
1.3.1. Polyhedra
DEFINITION 1.2.– A polyhedron is a set that can be described as
where A is an m × n matrix and b