СИМПЛЕКС-МЕТОД

 

Для решения ряда задач линейного программирования существуют специальные методы. Есть, однако, общий метод решения всех таких задач. Он носит название симплекс-метода и состоит из алгоритма отыскания какого-нибудь произвольного допустимого решения и алгоритма последовательного перехода от этого решения к новому допустимому решению, для которого функция f изменяется в нужном направлении (для получения оптимального решения).

Пусть система ограничений состоит лишь из уравнений

и требуется отыскать минимум линейной функции (7.81). Для отыскания произвольного опорного решения приведем (7.85) к виду, в котором некоторые r неизвестных выражены через остальные, а свободные члены неотрицательны (как это сделать - обсудим позднее):

Неизвестные x₁, x₂, ..., x_r - базисные неизвестные, набор {x₁, x₂, ..., x_r} называется базисом, а остальные неизвестные {x_r+1, x_r+2, ..., x_n} - свободные. Подставляя (7.86) в (7.81), выразим функцию

f через свободные неизвестные: