Подготовка задачи к решению симплексным методом

Предварительным шагом метода является приведение задачи к каноническому виду. («Каноническая» – равнозначно названию «Типовая»).

То есть, в задаче (1) все основные ограничения (не относящиеся к условию неотрицательности переменных), приводятся к виду уравнений.

Левая часть всех ограничений данной задачи меньше или равна правой, т.е. все ограничения имеют тип: <. Для того, чтобы левая часть ограничения была равна правой, необходимо к ней прибавить неотрицательную переменную, которая называется дополнительной. В данной задаче в каждое ограничение добавляется по одной неотрицательной дополнительной переменной: Х₃ – в первое ограничение, Х₄ - во второе, Х₅ – в третье. Дополнительные переменные в целевую функцию вводятся с нулевыми коэффициентами, чтобы не изменилось ее значение.

Запишем задачу (1) в каноническом виде:

Х₁ + Х₂ + Х₃ = 2000

4Х₁ + 40Х₂ + Х₄ = 28000 (2)

2Х₁ + 9Х₂ + Х₅ = 9000

Х₁ > 0 , Х₂ > 0

Z = 1500Х₁ + 5000Х₂ + 0 * Х₃ + 0 * Х₄ + 0 * Х₅ => max

Дополнительные переменные Х₃, Х₄, Х₅ экономически будут интерпретироваться как количество недоиспользуемых ресурсов: пашни, труда и удобрений соответственно.

До рассмотрения алгоритма симплексного метода вспомним еще раз такие понятия, как решение, допустимое решение, базисное решение, оптимальное решение.

Решение -это набор значений переменных.

Допустимое решение – это набор значений переменных, при которых выполняются ограничения задачи (2). Как правило, любая задача линейного программирования имеет бесконечное множество допустимых решений. Все допустимые решения образуют область допустимых решений (область допустимых значений; область определения задачи).

Базисное решение –это такое допустимое решение (частный случай допустимого решения), которое соответствует координатам угловых точек области допустимых решений.

В базисном решении количество базисных переменных, отличных от нуля, равно количеству уравнений.

Базисное решение системы mлинейных уравнений относительно nпеременных (n > m) можно получить следующим образом: какие-либо (n-m) переменных приравниваются к нулю, затем из системы уравнений определяются значения остальных (базисных) переменных

В задаче, записанной в каноническом виде, в качестве базисных берутся переменные, которые входят только в одно из уравнений системы с коэффициентом, равным +1. В исходном допустимом базисном решении в качестве базисных выбираются дополнительные переменные. Остальные (небазисные) переменные приравниваются к нулю.

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