Linear Programming and Resource Allocation Modeling

13Simplex‐Based Methods of Optimization

13.1 Introduction

In this chapter the standard simplex method, or a slight modification thereof, will be used to solve an assortment of specialized linear as well as essentially or structurally nonlinear decision problems. In this latter instance, a set of transformations and/or optimality conditions will be introduced that linearizes the problem so that the simplex method is only indirectly applicable. An example of the first type of problem is game theory, while the second set of problems includes quadratic and fractional functional programming.

13.2 Quadratic Programming

The quadratic programming problem under consideration has the general form

(13.1)

Here, the objective function is the sum of a linear form and a quadratic form and is to be optimized in the presence of a set of linear inequalities. Additionally, both C and X are of order (p × 1), Q is a (p × p) symmetric coefficient matrix, A is the (m × p) coefficient matrix of the linear structural constraint system, and b (assumed ≥O) is the (m × 1) requirements vector. If Q is not symmetric, then it can be transformed, by a suitable redefinition of coefficients, into a symmetric matrix without changing the value of X′QX. For instance, if a matrix A from X′AX is not symmetric, then it can be replaced by a symmetric matrix B if for all i, j or B = (A + A′)/2. Thus, b_ij + b_{ji ...}