Симплекс - метод

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

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

Общей задачей линейного программирования (ОЗЛП), заданной в произвольной форме записи, называют задачу, в которой требуется максимизировать (минимизировать) функцию

f =cj xj (1)

при условиях

a ij x j <= a i0 ( i = 1, …, s) (2)

a ij x j = a i0 ( i = s + 1, …, m) (3) j >=0 ( j= 1, …, t)

Существуют разные формы записи ЗЛП, но по теме задания нас интересует каноническая форма записи ЗЛП, так как именно к такой форме записи применим широко используемый симплекс-метод.

Задачей линейного программирования в канонической форме записи называют задачу, в которой требуется максимизировать функцию

f =cj xj (4)

при условиях

a ij x j = a i0 ( i = 1, …, m) (5) j >=0 ( j= 1, …, n) (6)

Замечание: задачу минимизации f можно формально заменить задачей максимизации функции (-f).

Для того, чтобы выразить общую идею симплексного метода, приведем несколько основных понятий, относящихся к линейному программированию:

1. Набор чисел Х = (x 1; …; x n), удовлетворяющий всем ограничениям задачи называется планом.

2. Набор чисел Х = (x 1; …; x n), называется опорным планом, если он соответствует крайней точке многогранника решений.

3. План Х = (x 1; …; x n), доставляющий функцию в экстремум называется оптимальным.

Так вот суть симплекс - метода состоит в упорядоченном переборе только опорных планов при котором значение целевой функции возрастает. Таким образом мы постепенно приходим к оптимальному плану (если задача разрешима).

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

I Ограничения вида «»- ресурсные ограничения. Справа находится то, что мы используем на производстве, слева - то, что получаем. При таких ограничения вводят дополнительные переменные с коэффициентом «+1», образующие единичный базис. В целевую функцию эти переменные войдут с коэффициентом «0». Эти переменные несут определенный экономический смысл. Обычно они отражают недорасход ресурсов (остаток).