Алгоритм симплекс-метода решения общей задачи линейного программирования

Рассмотрим следующую основную задачу ЛП:

при ограничениях:

.

Перепишем ограничения этой задачи в векторной форме:

, (1.3)

где – k-мерные вектор-столбцы, составленные из коэффициентов при неизвестных и свободных членов системы ограничений основной задачи:

План называется опорным планом основной задачи линейного программирования, если его положительные коэффициенты (x _j>0) стоят при линейно независимых векторах P _j.

Так как векторы P jявляются k-мерными, то из определения опорного плана следует, что число его положительных компонент не может быть больше числа k.

Опорный план называется невырожденным, если он содержит ровно k положительных компонент, в противном случае он называется вырожденным.

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

· среди векторов выбрать k линейно независимых;

· найти опорный план, связанный с этой системой векторов;

· вычислить значение целевой функции для опорного плана.

Перебирая, таким образом, все опорные планы данной задачи и сравнивая между собой полученные значения целевой функции, найдем оптимальный план. Количество всех переборов определяется по следующей формуле:.

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

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

Если из некоторой системы векторов можно составить единичную матрицу, то такую систему векторов называют базисом.

Система единичных векторов является базисом. Соответствующие базису переменные будем называть базисными переменными, а остальные – свободными переменными.

Из системы ограничений задачи в векторной форме (1.3) имеем:

. (1.4)

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

. (1.5)

Разложение векторов по базису имеет вид:

. (1.6)

Для фиксированного выберем некоторое число и вычтем из (1.4), тогда получим:

.

Введем обозначение

Если выбрать из условия

, (1.7)

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

. (1.8)

Обозначим через z (j) следующее выражение:

.

Вычтем из (1.5), получим:

Отсюда и (1.8) имеем:

,

где .

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

Теорема 1.5. Опорный план задачи линейного программирования является оптимальным, если выполняется неравенство для любого .

Пусть для некоторого номера выполняется соотношение

.

Если среди чисел нет положительных, то план не является опорным, так как содержит k+1 отличную от нуля компоненту. В этом случае целевая функция исходной задачи не ограничена на множестве ее планов.

Если же для некоторых индексов , то покажем, что план – опорный план. Для этого достаточно показать, что система векторов линейно независима (b – индекс i, на котором достигается минимум в (1.7)).

Покажем это от противного. Пусть указанная система векторов линейно зависима. Тогда можно указать числа , среди которых имеются ненулевые такие, что

Подставляя в эту формулу разложение вектора из (1.6), получим следующее:.

Система векторов линейно независима, а . Это значит, что последнее соотношение выполняется лишь при . Получили противоречие.

Дата добавления: 2015-11-14