Tham khảo tài liệu 'david g. luenberger, yinyu ye - linear and nonlinear programming international series episode 1 part 3', kỹ thuật - công nghệ, cơ khí - chế tạo máy phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | 40 Chapter 3 The Simplex Method In this case we have a new basic feasible solution with the vector aq replacing the vector ap where p corresponds to the minimizing index in 16 . If the minimum in 16 is achieved by more than a single index i then the new solution is degenerate and any of the vectors with zero component can be regarded as the one which left the basis. If none of the yiq s are positive then all coefficients in the representation 15 increase or remain constant as s is increased and no new basic feasible solution is obtained. We observe however that in this case where none of the yiq s are positive there are feasible solutions to 12 having arbitrarily large coefficients. This means that the set K of feasible solutions to 12 is unbounded and this special case as we shall see is of special significance in the simplex procedure. In summary we have deduced that given a basic feasible solution and an arbitrary vector aq there is either a new basic feasible solution having aq in its basis and one of the original vectors removed or the set of feasible solutions is unbounded. Let us consider how the calculation of this section can be displayed in our tableau. We assume that corresponding to the constraints Ax b x 0 we have a tableau of the form a1 a2 a3 am am 1 am 2 an b 1 0 0 0 y1 m 1 y1 m 2 y 1n y10 0 1 0 0 y2 m 1 y2 m 2 y20 0 0 1 17 0 0 1 ym m 1 ym m 2 ymn ym0 This tableau may be the result of several pivot operations applied to the original tableau but in any event it represents a solution with basis a1 a2 . am. We assume that y10 y20 . ym0 are nonnegative so that the corresponding basic solution x1 y10 x2 y20 . xm ym0 is feasible. We wish to bring into the basis the vector aq q m and maintain feasibility. In order to determine which element in the qth column to use as pivot and hence which vector in the basis will leave we use 16 and compute the ratios xjyiq yi0 yiq i 1 2 . m select the smallest nonnegative ratio and pivot on the corresponding yiq. Example
