Optimizations and Programming. Abdelkhalak El Hami

Чтение книги онлайн.

      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:

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 P₁ and P₂ 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 P₁ and P₂ yield effective profits of 6 dhs and 4 dhs per unit. The goal is to determine which (possibly non-integer) quantities of the products P₁ and P₂ the factory should produce to maximize the total profit from selling these two products, subject to the availability of the resources.

      Let x₁ and x₂ be the quantities of the products P₁ and P₂, respectively.

      The LP may be expressed as follows: maximize z(x₁, x₂) = 6x₁ + 4x₂ 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 is a vector in ℝ^m. Note that the admissible set of an LP is a polyhedron.

      DEFINITION 1.3.– A polyhedron P is said to be bounded if there exists a constant c such that ||x|| ≤ c for every x ∈ P.

Figure 1.1. Bounded polyhedron (left) and unbounded polyhedron (right). For a color version of this figure, see www.iste.co.uk/radi/optimizations.zip

      DEFINITION 1.4.– Let a be a non-zero vector of ℝⁿ, and let b be a scalar.

       – The set {x ∈ ℝn|aTx = b} is said to be a hyperplane.

       – СКАЧАТЬ