Метод искусственного базиса

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

Если же ограничения задачи заданы в виде неравенств вида Метод искусственного базиса - student2.ru или уравнений

Метод искусственного базиса - student2.ru и (или) Метод искусственного базиса - student2.ru ,

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

Рассмотрим примеры постановок задач такого рода.

Преобразование ограничений, заданных в виде уравнений, рассмотрим на примере:

Метод искусственного базиса - student2.ru

В систему равенств вводим искусственные переменные Метод искусственного базиса - student2.ru с коэффициентами, равными единице, позволяющими образовать искусственный базис:

Метод искусственного базиса - student2.ru

Здесь Метод искусственного базиса - student2.ru .

Целевая функция имеет вид:

при решении задачи на максимум –

Метод искусственного базиса - student2.ru

при решении задачи на минимум –

Метод искусственного базиса - student2.ru

За использование искусственных переменных, вводимых в целевую функцию, накладывается так называемый «штраф» величиной М, очень большое положительное число, которое обычно не задается Метод искусственного базиса - student2.ru .

Преобразование ограничений в виде неравенств вида Метод искусственного базиса - student2.ru рассмотрим на примере:

Метод искусственного базиса - student2.ru

Для получения системы уравнений вводим дополнительные переменные Метод искусственного базиса - student2.ru .

Метод искусственного базиса - student2.ru

Поскольку в этой системе уравнений отсутствует базис, то вводим в нее искусственные переменные Метод искусственного базиса - student2.ru с коэффициентами, равными + 1, которые образуют искусственный базис

Метод искусственного базиса - student2.ru

Целевая функция имеет вид:

при решении задачи на максимум –

Метод искусственного базиса - student2.ru

при решении задачи на минимум –

Метод искусственного базиса - student2.ru .

Здесь Метод искусственного базиса - student2.ru .

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

Пример.Определить минимальное значение целевой функции

Метод искусственного базиса - student2.ru

при следующих смешанных условиях-ограничениях:

Метод искусственного базиса - student2.ru

Запишем систему ограничений в виде равенств, для чего введем дополнительные переменные Метод искусственного базиса - student2.ru и Метод искусственного базиса - student2.ru , в результате получим следующую систему:

Метод искусственного базиса - student2.ru

Теперь введем искусственные переменные Метод искусственного базиса - student2.ru и Метод искусственного базиса - student2.ru в первое и второе уравнения:

Метод искусственного базиса - student2.ru

Целевая функция запишется в виде:

Метод искусственного базиса - student2.ru .

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

Поскольку решается задача на минимум, то ключевым столбцом в первой симплексной таблицы будет Метод искусственного базиса - student2.ru , а все остальные преобразования проводятся по стандартной схеме до тех пор, пока в индексной строке не получатся только неположительные числа Метод искусственного базиса - student2.ru , а в оптимальном решении должны отсутствовать положительные значения искусственных переменных Метод искусственного базиса - student2.ru и Метод искусственного базиса - student2.ru .

Метод искусственного базиса - student2.ru Б Метод искусственного базиса - student2.ru Метод искусственного базиса - student2.ru Метод искусственного базиса - student2.ru Метод искусственного базиса - student2.ru Метод искусственного базиса - student2.ru Метод искусственного базиса - student2.ru Метод искусственного базиса - student2.ru Метод искусственного базиса - student2.ru Метод искусственного базиса - student2.ru
М М
М Метод искусственного базиса - student2.ru Метод искусственного базиса - student2.ru
М Метод искусственного базиса - student2.ru -1
Метод искусственного базиса - student2.ru Метод искусственного базиса - student2.ru
Метод искусственного базиса - student2.ru 11М Метод искусственного базиса - student2.ru Метод искусственного базиса - student2.ru Метод искусственного базиса - student2.ru Метод искусственного базиса - student2.ru
М Метод искусственного базиса - student2.ru Метод искусственного базиса - student2.ru Метод искусственного базиса - student2.ru Метод искусственного базиса - student2.ru Метод искусственного базиса - student2.ru
Метод искусственного базиса - student2.ru Метод искусственного базиса - student2.ru Метод искусственного базиса - student2.ru Метод искусственного базиса - student2.ru -
Метод искусственного базиса - student2.ru Метод искусственного базиса - student2.ru - Метод искусственного базиса - student2.ru -
Метод искусственного базиса - student2.ru Метод искусственного базиса - student2.ru Метод искусственного базиса - student2.ru Метод искусственного базиса - student2.ru Метод искусственного базиса - student2.ru Метод искусственного базиса - student2.ru Метод искусственного базиса - student2.ru
Метод искусственного базиса - student2.ru Метод искусственного базиса - student2.ru Метод искусственного базиса - student2.ru Метод искусственного базиса - student2.ru Метод искусственного базиса - student2.ru    
Метод искусственного базиса - student2.ru Метод искусственного базиса - student2.ru Метод искусственного базиса - student2.ru Метод искусственного базиса - student2.ru Метод искусственного базиса - student2.ru
Метод искусственного базиса - student2.ru Метод искусственного базиса - student2.ru Метод искусственного базиса - student2.ru
Метод искусственного базиса - student2.ru Метод искусственного базиса - student2.ru Метод искусственного базиса - student2.ru Метод искусственного базиса - student2.ru Метод искусственного базиса - student2.ru

Оптимальному плану соответствует точка с координатами Метод искусственного базиса - student2.ru и Метод искусственного базиса - student2.ru , Метод искусственного базиса - student2.ru .

Следует заметить, что эту задачу можно решить с помощью графоаналитического метода.

Наши рекомендации