Признак неоптимальности базисного решения транспортной задачи. Определение цикла. Построение улучшенного решения.

Циклом называется такая последовательность клеток таблицы транспортной задачи (i₁, j₁),(i₁, j₂),(i₂, j₂),...,(i_k, j₁), в которой две и только две соседние клетки распложены в одной строке или столбце, причем первая и последняя клетки также находятся в одной строке или столбце.

Последовательность дальнейших действий такова:

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

● вычисляем потенциалы (для занятых поставками клеток),

● вычисляем оценки (для незанятых клеток).

Если получится хотя бы одна отрицательная оценка, то план неоптимален, и для клетки с наибольшей (по модулю) отрицательной оценкой построим цикл пересчёта, тем самым улучшив план. Для нового опорного плана повторяем все вычисления, начиная с пункта.

Симплексный метод. Приведение ЗЛП к канонической форме. Дополнительные переменные. Выбор разрешающего элемента. (Признак неоптимального базисного решения / Признак неограниченного значения целевой функции/ Признак альтернативного рещения)

Стандартной задачей ЛП называется задача на максимум вида:

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

Здесь-план,-матрица системы ограничений размера,- вектор правых частей ограничений. Если правые части ограничений неотрицательные, то множество допустимых планов непустое. Если условие неотрицательности правых частей не выполняется, то множество допустимых планов может оказаться пустым.

Канонической называется задача вида:

где ранг матрицы A равен m (числу ее строк). В отличие от стандартной задачи в канонической задаче все ограничения являются уравнениями, а знаки правых частей уравнений могут быть произвольными. Для получения опорных планов задачи ЛП в канонической форме выбирается любой набор из m столбцов матрицы, образующих линейно независимую систему. Переменные, соответствующие этим столбцам, называются базисными. Решение уравнения, в котором все свободные переменные равны нулю, называется базисным решением. Допустимое базисное решение системы ограничений называется базисным планом задачи. Базисный план, содержащий точно нулевых компонент, называется невырожденным. Если нулевых компонент больше, то план вырожденный. Базис, соответствующий оптимальному плану задачи, называется оптимальным базисом.

Общая задача ЛП может быть приведена к специальным формам:

1) Задача на минимум (максимум) преобразуется в задачу на максимум (минимум) введением новой целевой функции,

2) Преобразование позволяет избавиться от коэффициента в целевой функции

3) Умножение неравенства на минус

4) Ограничение в виде уравнения эквивалентно системе из двух ограничений с противоположными знаками

5) Любое неравенство можно превратить в уравнение с помощью дополнительных (балансовых) неотрицательных переменных

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

(a) Признак оптимального базисного решения. Признак единственного оптимального решения.

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

Единственность оптимальное решение

Базисные переменные	положительны, либо равны нулю
Оценки базисных переменных	равны нулю
Свободные переменные	равны нулю
Оценки свободных переменных	положительны

(b) Признак неоптимального базисного решения.

Наличие отрицательной оценки требует продолжения исследования.

(Есть отрицательные оценки, можно выбрать разрешающую строку.)

 

(c) Признак неограниченного значения целевой функции.

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

(d) Признак альтернативного решения.

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

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

Альтернативное решение

Базисные переменные	положительны, либо равны нулю
Оценки базисных переменных	равны нулю
Свободные переменные	равны нулю
Оценки свободных переменных	какая-то оценка свободной переменной равна нулю

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

Вырожденное решение:

Базисные переменные	какая-то базисная переменная равна нулю
Оценки базисных переменных	равны нулю
Свободные переменные	равны нулю
Оценки свободных переменных	положительны

Вырожденное решение может быть и единственным.